Cours n° 1, 26 septembre 2013

Jean-François Perrot

Expressions et ensembles

1. Expressions
   1. Expressions arithmétiques (en programmation) ou algébriques (en mathématiques)
   2. Expressions régulières
   3. L'infini en puissance et l'infini en acte
      
      
2. Ensembles
   1. Notion d'ensemble
      1. Intuitivement
      2. La relation d'appartenance
      3. L'ensemble vide
   2. Ensembles en extension et en compréhension. Prédicats
   3. Sous-ensembles. Inclusion

Expressions

1. Expressions arithmétiques (en programmation) ou algébriques (en mathématiques)

   Du type "(a+b)^2" et "a2 + 2ab + b^2".
   
   Ce genre de texte, à la syntaxe très stricte, représente d'abord un calcul :
   
   • pour "(a+b)2", celui qui consiste en
     
     1. prendre les valeurs de a et de b
     2. calculer leur somme
     3. calculer le carré de la somme
   • pour "a2 + 2ab + b2", celui qui consiste en
     
     1. prendre la valeur de a, calculer son carré
     2. prendre les valeurs de a et de b, calculer leur produit, multiplier le résultat par 2
     3. ajouter ce résultat au carré de a
     4. prendre la valeur de b, calculer son carré
     5. ajouter ce carré au résultat précédent
        
   
   Dans un second temps, on oublie le processus de calcul pour ne plus s'intéresser qu'au résultat.
   C'est en ce sens qu'on écrit l'égalité "(a+b)2  = a2 + 2ab + b^2", qui affirme
   
   • non point que les deux expressions sont identiques,
     
   • mais que les deux séquences de calcul associées donnent toujours le même résutat.
     
     
   Pour les expressions arithmétiques, l'essentiel est que les calculs qu'elles décrivent opèrent sur des nombres
   et que par conséquent les valeurs qui leur sont associées sont des nombres.
   
   

2. Expressions régulières

   Elles sont tout-à-fait analogues aux expressions arithmétiques :
   
   • une e.r. représente d'abord un calcul, mais c'est un calcul sur des ensembles de mots et non sur des nombres
   • on s'intéresse au résultat de ce calcul, qui est aussi un ensemble de mots, et en général infini...
   
   Il y a un obstacle conceptuel à considérer qu'une expression (texte fini) peut représenter un objet infini.
   
   

3. L'infini en puissance et l'infini en acte

   • Exemple
     Si nous considérons l'infinitude la plus immédiate, celle des entiers, nous pouvons l'aborder de deux manières
     
     1. En restant toujours "à distance finie", et en constatant qu'on peut toujours trouver un entier plus grand.
        Cette attitude prudente ne soulève pas de problème (aujourd'hui).
        On parle alors d'infini en puissance, parce qu'il n'est jamais réalisé en tant qu'infini :
        tous les nombres envisagés sont de vrais nombres...
        
     2. En considérant d'un seul coup la collection de tous les entiers, et en tenant des discours sensés comme :
        la collection de tous les entiers est formée de deux sous-collections (également infinies), celle des enties pairs et celle des entiers impairs.
        On parle alors d'infini en acte, car on manipule (par la pensée) des infinis dans leur totalité.
        Cette démarche est nettement plus difficile à  accepter : comment puis-je raisonner sur des êtres que je n'ai jamais vus ?
        Car je n'ai jamais pu contempler la totalité des entiers...
        Et d'ailleurs je me heurte à quelque paradoxes : il y a autant d'entiers pairs que d'entiers !
        
        
   • Cette distinction remonte à Aristote. Son histoire est très bien racontée ici, elle peut se poursuivre ici.
     Pour vous faire une idée des débats médiévaux autour de l'infinité de Dieu, voyez la Somme théologique.
     
     
   • La chose nous intéresse ici car nos expressions rationnelles relèvent justement de l'infini en acte.
     
     
     

Ensembles

1. Notion d'ensemble

   1. Intuitivement

      La notion d'ensemble s'est imposée comme abstraction commune à diverses idées de collections, en abandonnant toute hypothèse d'homogénéité entre les éléments.
      Intuitivement, nous concevons une collection de tableaux, un groupe de personnes, une bande de malfaiteurs, un troupeau de moutons, une meute de chiens, etc. Notez ce point le raffinement du vocabulaire anglais : a herd of cattle, a flock of sheep, a school of porpoises, a pride of lions, a bevey of girls... Ce sont autant d'ensembles, et comme tels manipulables par les mêmes opérations !
      Cette abstraction peut se rapprocher de celle qui fait apparaître les entiers comme les nombres d'éléments de diverses collections (5 pommes ou 5 hommes, ça fait toujours 5...).
      
      Comme la notion de nombre, la notion d'ensemble sert de support à des opérations universelles de la pensée. Avec son cortège d'opérations et de lois qui les gouvernent, elle constitue un outil intellectuel extrêmement puissant, dont la vertu ne se limite pas aux mathématiques !
      

   2. La relation d'appartenance

      La notion d'ensemble est inséparable de celle d'élément, à laquelle elle est unie par la relation d'appartenance.
      Un ensemble, c'est un truc auquel d'autres trucs (les éléments) appartiennent ou n'appartiennent pas.
      
      Notation : si x est l'élément et E l'ensemble, on écrit x ∈ E si x appartient à E, et x ∉ E dans le cas contraire.
      Le symbole ∈ (n° x2208 dans le catalogue Unicode) est dérivé de la lettre grecque ε (epsilonn).
      
      Tout un vocabulaire dérive de l'acception ordinaire du mot appartenir : si x ∈ E, on dira que "x est un élément de E" (au génitif),
      ou, en parlant de E, que "x est un de ses éléments" (avec un possessif).
      On dira aussi que "E est formé de ses éléments", mais n'anticipons pas !
      Un vocabulaire concurrent est fondé sur l'idée de contenu : "x ∈ E" se lit aussi "E contient x", plutôt que "E possède x",
      ce qui crée une ambiguïté vis-à-vis de "E contient un sous-ensemble" (voir plus loin).
      Malgré cela, les expressions "les éléments contenus dans E" et "les éléments appartenant à E" sont équivalentes.
      

   3. L'ensemble vide

      C'est un ensemble spécial, celui qui ne contient aucun élément. Il joue un rôle analogue au zéro de l'arithmétique.
      On le désigne par ∅ (Unicode x2205), symbole dérivé du Ø majuscule danois (Unicode xD8).
      Il apparaîtra souvent dans la suite.
      

2. Ensembles en extension et en compréhension. Prédicats

   Il y a deux manières principales de définir un ensemble :
   
   
   1. par énumération de ses éléments (définition en extension) : { Pierre, Paul, Jacques, Jules, Michel, Nestor, ... }
      ce qui suppose qu'on sache désigner individuellement lesdits éléments.
      
      
   2. par sélection de ses éléments au moyen d'une propriété caractéristique (définition en compréhension) :
      { les membres du groupe qui sont de sexe masculin }.
      
      
   La définition en compréhension donne lieu aux célèbres paradoxes de la théorie des ensembles, qui ont imposé quelques contraintes aux propriétés acceptables pour définir un ensemble. Le plus facile à apprécier est celui de Berry, dont voici une formulation en français (pour une discussion en anglais, voir Wikipedia) :
   

   Considérons l'ensemble des entiers naturels qu'on peut décrire par une expression française de vingt mots ou moins.
   Le vocabulaire français étant fini, de telles expressions sont en nombre fini, et les entiers ainsi décrits sont donc aussi en nombre fini.
   Comme il y a une infinité d'entiers, il doit exister des entiers qu'on ne peut pas décrire par une expression française de vingt mots ou moins, et parmi eux il en existe un plus petit que tous les autres.
   Cet entier est donc décrit par l'expression :
   le plus petit entier qu'on ne peut pas décrire par une expression française de vingt mots ou moins.
1   2    3      4    5  6  7   8   9    10     11  12      13        14     15   16   17  18  19
Or cette expression ne compte que 19 mots, notre entier supposé est donc bel et bien descriptible en moins de vingt mots.

   La définition en compréhension met l'accent sur la formulation de la propriété caractéristique, qui est affaire de langage.
   Pour ne pas faire d'hypothèse sur cette expression, on la remplace par un prédicat (au sens des logiciens, c'est-à-dire une fonction à valeurs vrai ou faux).
   
   • Étant donné un prédicat P, on lui associe l'ensemble E formé de tous les éléments x pour lesquels P(x) est vrai,
     et on écrit : E = { x | P(x) }
     
   • Réciproquement, à tout ensemble E on associe le prédicat P défini par P(x) <--> x ∈ E.
   
   On peut donc voir les ensembles et les prédicats comme deux entités équivalentes, quoique porteuses d'intuitions différentes.
   C'est ici le lieu de rendre hommage à Gottlob Frege, à qui cette observation est due.
   Utilisons donc sa célèbre distinction entre Sinn et Bedeutung (en français sens et dénotation, en anglais sense et reference)
   pour dire que l'ensemble et le prédicat ont la même Bedeutung, mais pas le même Sinn.
   

3. Sous-ensembles. Inclusion

   Étant donné deux ensembles E et F, on dit que F est un sous-ensemble de E si tout élément qui appartient à F appartient aussi à E, 
   (en termes possessifs, si tous les éléments de F sont aussi des éléments de E).
   On dit aussi en ce cas que F est inclus dans E (ou contenu dans E)
   et on s'écrit  F ⊆ E.
   
   L'ensemble vide est inclus dans tout ensemble, quel qu'il soit : "∅⊆E" est vrai quel que soit l'ensemble E.
   
   Le symbole de relation ⊆ (n° x2286 dans le catalogue Unicode) est dérivé du signe d'inégalité numérique ≤.
   Il s'agit ici de l'inclusion (inégalité) large, pour laquelle E est (logiquement) sous-ensemble de lui-même.
   
   Le symbole d'inclusion stricte est ⊂, correspondant à l'inégalité stricte <.
   Il ne faut pas le confondre avec le symbole d'appartenance ∈ !
   Inclusion et appartenance sont des relations essentiellement différentes :
   
   • l'une met en rapport deux êtres de même rang (deux ensembles)
     
   • l'autre relie deux éléments de rangs différents :
     dans le vocabulaire des logiciens, l'élément est d'ordre 1 et l'ensemble d'ordre 2.
   
   En termes de prédicats associés, la relation d'inclusion des ensembles rejoint celle d'implication des prédicats
   (notée P(x)  => Q(x) : si P(x)  est vrai, Q(x) est vrai aussi) :
   
   
   • Soient P_E et P_F les prédicats associés à nos deux ensembles E et F :
     l'inclusion F ⊆ E signifie que "pour tout x, P_F(x)  => P_E(x)".
     
   • Réciproquement, étant donné deux prédicats P et Q, si "pour tout x, P(x)  => Q(x)",
     il s'ensuit que l'ensemble associé à P est inclus dans l'ensemble associé à Q :
     { x | P(x) } ⊆ { y | Q(y) }