Théorie des ensembles
Premières notions: ensembles, applications et quantificateurs

Cette page est obsolète (13/9/2008). Voir le nouveau sommaire : Théorie des ensembles et fondements des mathématiques.

Ancien sommaire:
1.1. Qu'est-ce que la logique mathématique
1.2. A propos de théorie des ensembles


1.3. Variables et ensembles
1.4. Applications, relations unaires et compréhension


1.5. Le paradoxe du langage et son explication temporelle
1.6. Paradoxe de Russell et explications (notion de classe)


1.7. Ensembles finis, n-uplets, familles, produit
1.8. Opérations, relations
1.9. Construction des termes et énoncés


1.3. Variables et ensembles

Le langage mathématique est fait de symboles. Commençons par les plus simples cas.

Constantes
Un symbole de constante est un symbole désignant un objet mathématique bien précis, appelé sa valeur. Par exemple le chiffre 3, les symboles "∅", "ℕ" sont des symboles de constante qui désignent respectivement le nombre 3, l'ensemble vide et l'ensemble des entiers naturels. Aussi, "vrai" et "faux" sont des constantes désignant les deux valeurs de vérités qui seront les deux valeurs possibles des énoncés. Ils tiendront donc eux-mêmes lieu d'énoncés.
Le langage courant comporte aussi de nombreux symboles de constantes: tout nom propre et tout nom précédé d'un article défini ("le", "la") (sans complément, sinon ce serait une formule) est ce qui en langage courant joue le rôle de symboles de constantes.

Variables libres ou liées
Un symbole de variable est un symbole pouvant être interprété de plusieurs manières: chaque interprétation (point de vue) attribue à ce symbole une valeur particulière. Autrement dit, sa valeur (l'objet mathématique qu'il désigne) dépend de l'interprétation adoptée.
Ainsi, cette notion est marquée par une multiplicité de points de vue : les points de vue "de l'intérieur" dans lesquels cette variable est interprétée comme une constante prenant une valeur particulière parmi les possibilités, et le point de vue "de l'extérieur" sous l'angle duquel on est conscient de la multiplicité des interprétations possibles. On a bien besoin d'un tel outil afin d'avoir une chance de pouvoir désigner par nos symboles n'importe quel objet du monde mathématique qui est plus vaste que le langage dont nous disposons pour l'étudier: ainsi pourra-t-on évoquer beaucoup d'objets comme valeurs possibles d'une même variable.
On appelle fixer une variable le fait de se plonger (provisoirement) dans une interprétation particulière possible ("de l'extérieur") de cette variable, et la voir ainsi comme constante. Mais étant supposée constante, la situation qui en résultera dépendra de la valeur choisie qui n'est pas précisée. Ce qui sera fait dans ce cadre doit garder un sens quelle que soit la valeur utilisée, à moins bien sûr de distinguer explicitement différents cas.
On dit qu'une variable est libre tant qu'on l'utilise ainsi comme étant fixée (interprétée par une valeur particulière), et qu'on peut donc réemployer ce symbole pour désigner la même valeur, comme s'il s'agissait d'une constante. Mais quand on cesse de le faire pour regarder le bilan de toutes les interprétations, cette variable est alors dite liée. Nous verrons plus loin l'utilisation pratique de tout cela.
Remplacer toutes les occurences d'un symbole de variable liée par un autre même symbole qui ne figure pas déjà dans le même contexte, ne change pas la signification du tout; contrairement au cas d'un symbole de variable libre. (Autrement dit, ce que je dis à l'aide du symbole x, je peux le dire aussi en renommant šx en y pour signifier la même chose, du moment qu'aucun contexte extérieur ne vient fixer les valeurs de x ni de y).
Par plus ou moins un abus de langage, on se permettra de réemployer une même lettre pour désigner plusieurs variables liées séparées, autrement dit telles qu'on n'a jamais plus d'une d'entre elles fixées à la fois (et pouvant donc prendre des valeurs différentes entre les angles d'interprétation de l'une et de l'autre). Remarquons qu'en langage courant on fait sans cesse cet abus, n'ayant qu'un nombre fort réduit de symboles de variables à disposition ("lui", "elle", "eux", et quelques autres), au risque de toutes les confusions.
Une constante est essentiellement une variable ayant une unique valeur possible.

Termes
On appellera terme une structure de langage servant à désigner un objet. Les plus simples termes sont les symboles de constante ou de variable. On verra les autres plus tard.

Usage des variables, égalité, équivalence
On peut employer le symbole d'égalité entre des termes (par exemple "x=y"), pour former l'énoncé signifiant qu'ils ont la même valeur.
En fait, le langage employé à un endroit donné ne figurant pas lui-même parmi ses propres objets comme nous expliquerons plus loin, l'interprétation d'un symbole qui y est employé comme celui d'égalité n'a pas à se soucier de la manière dont les autres parties de la même formule forment leur signification, mais uniquement de leur valeur. On parle donc directement par exemple de la notion d'égalité entre des objets désignés par ailleurs (ces objets étant les valeurs des termes), pour signifier l'affirmation que c'est le même objet. On peut définir et étudier toute opération entre objets, à l'aide de symboles de variables recevant pour valeurs ces objets, symboles qui, ultérieurement, pourront être remplacés par tous les termes qu'on voudra, pour appliquer ces opérations aux valeurs de ces termes.
Si deux objets sont égaux, tout ce qui est vrai de l'un est vrai de l'autre.
L'égalité entre valeurs de vérité se nomme également équivalence, et se note  ⇔ .

Domaines et ensembles
Nous allons aborder ici des notions délicates, puisqu'il s'agit de tenter de définir des choses tellement fondamentales qu'elles ne sont pas rigoureusement définissables. Essayons donc d'en rendre l'idée par des formules littéraires et diverses explications.
On appelle domaine d'une variable, le concept (la connaissance) de la totalité des valeurs possibles de cette variable, lorsqu'un tel concept existe. C'est la signification de la variable comme liée, à condition qu'elle puisse effectivement être liée (cette condition est la même que celle de la phrase précédente). Ainsi cela oublie tout le contexte de ce qui peut être lié au choix d'une de ces valeurs, et voit les valeurs comme données en vrac.
Le domaine d'une variable est un objet mathématique appelé un ensemble.
Les expressions ci-dessus invoquent une "pensée" qu'on pourrait d'abord comprendre comme humaine; mais en réalité la notion d'ensemble ne se réfère pas à la pensée humaine, mais à une notion complètement abstraite, habitant l'univers des mathématique, de "pensée" capable de "concevoir" des multiplicités d'objets éventuellement infinies (ce dont la pensée humaine n'est pas capable d'une manière effective).
Avant que la domination de l'approche axiomatique de la théorie des ensembles n'ait fait perdre le sens de ces notions dans les cours standard, Cantor en avait rendu compte en des termes intéressants, dont voici les extraits qui me semblent les plus pertinents.
Cantor définissait la notion d'ensemble comme "un groupement en un tout d'objets bien distincts de notre intuition ou de notre pensée". Par ailleurs, voici un extrait des Lettres de Cantor à Dedekind de l'été 1899 :
Si la totalité des éléments d'une multiplicité peut être pensée comme "existant simultanément", de telle sorte qu'il soit possible de la concevoir comme un "seul objet" (ou un "objet achevé"), je la nomme une multiplicité consistante ou un "ensemble".
Ici, le terme de multiplicité traduit la notion de variable, à savoir qu'il s'agit de la multiplicité des valeurs possibles de la variable. Par ailleurs il y a l'autre cas de figure, où d'après lui "l'admission d'une coexistence de tous ses éléments mène à une contradiction", ce qu'il appelle une "multiplicité inconsistante". Cependant, ces formulations doivent être corrigées: il ne suffit pas qu'un énoncé soit irréfutable pour être vrai. En particulier il ne suffit pas qu'une certaine coexistence, si postulée, soit exempte de contradiction, pour exister véritablement. Et de fait, nous présenterons ultérieurement le grand exemple de coexistence irréfutable mais en quelque sorte fausse: l'axiome des parties !
Tout cela étant relatif au point de vue, on peut aussi bien, étant donnée une variable x, d'abord la fixer, puis, voyant donc x comme une constante, qui est un cas particulier de variable, regarder ce qu'est alors le domaine de x: ce domaine est appelé un singleton, noté {x}. Bien sûr, il dépend de la valeur de x, donc est variable, et a lui-même un domaine lorsque x varie.
La "connaissance" de toutes les valeurs possibles d'une variable, qu'exprime son domaine, est supposée réutilisable: étant donné un ensemble E, on peut introduire autant de fois qu'on veut une nouvelle variable de domaine E indépendamment des autres variables en présence.
Il reste à inclure le cas très spécial de l'ensemble vide ∅, qu'on pourrait à la limite comprendre comme domaine d'une "variable" impossible, pour laquelle il ne se trouverait aucune valeur qui puisse lui être attribuée.
Etant donnés un ensemble E et un symbole de variable x, on dit que x parcourt E pour signifier qu'on l'utilise comme ayant pour domaine E.
En pratique, dans le langage courant, un nom commun désigne un ensemble, et l'article indéfini ("un", "une") devant lui, introduit une variable de domaine cet ensemble (à moins qu'à travers l'usage du verbe être il ne serve à exprimer la relation d'appartenance).

Appartenance
(Note: on écrira "ssi" comme abbréviation de "si et seulement si", qui signifie que les énoncés écrits avant et après sont équivalents; ceci servant souvent à définir le premier à l'aide du deuxième.)
Etant donnés un objet y et un ensemble E, on dit que y appartient à E ou E contient y et on note yE ssi y est une valeur possible d'une variable de domaine E. Ce qui, dans le cas du langage courant où l'ensemble est désigné par un nom commun, apparaît très simplement: "c'est un...". Etant donnée une variable x de domaine E, l'énoncé xE est toujours vrai.
La notion d'appartenance à un ensemble E est une traduction de ce qu'est E: introduire un symbole de variable x de domaine E, c'est introduire un symbole de variable x avec pour seule hypothèse que xE.
L'énoncé x ∈ ∅ est toujours faux, et l'énoncé y ∈ {x} équivaut à y=x.

Négation
La négation d'un énoncé (affirmation de sa fausseté, donnant la valeur de vérité contraire de celle de cet énoncé) s'exprime généralement en écrivant "non" suivi de l'énoncé (entre parenthèse si besoin): non(vrai)=faux, non(faux)=vrai.
Si l'énoncé à nier est construit sur un symbole simple comme le symbole d'égalité, on pourra abbréger la négation en barrant ce symbole. Ainsi, xy est l'abbréviation de non(x=y) et se lit "x est différent de y"; de même, xE signifie non(xE) et se lit "x n'appartient pas à E".
Ainsi, pour tout énoncé P on a (non(nonP)) ⇔ P), et (P ⇎ (nonP)).

Quantificateurs
Nous avons présenté un ensemble E comme la "connaissance" de toutes les valeurs qu'on envisage comme interprétations pour une variable donnée "x" de domaine E. Soient donc une variable x de domaine E et un énoncé P(x) (cette notation étant l'abbréviation d'un énoncé où peut entre autres figurer x) vrai ou faux pour chaque interprétation particulière (une question clairement définie en oui ou non). Passant au point de vue global où x parcourt E, on peut faire le bilan de la situation sur cet ensemble et formuler ainsi d'autres énoncés (vrais ou faux) du point de vue où x est liée. En particulier:
- dire s'il existe une valeur de x pour laquelle P donne la valeur vrai, ce qu'on note "∃xE, P(x)" et on lit "il existe x appartenant à E tel que P(x)". Ce symbole ∃ est appelé le quantificateur existentiel.
- dire si P donne toujours la valeur vrai, ce qu'on note "∀xE, P(x)" ("quel que soit x dans E,..."). C'est le quantificateur universel.
Ce sont comme deux présentations d'une même opération au travers l'échange des valeurs vrai et faux: dire qu'un énoncé est toujours vrai équivaut à nier l'existence d'un contre-exemple, autrement dit, dire qu'il existe une valeur de x pour laquelle un énoncé est vrai, équivaut à nier qu'il soit toujours faux:
xE, P(x) ⇔  non
(∀xE, non
P(x))
non
(∃xE, P(x)) ⇔ ∀xE, non
P(x)
non
(∃xE, non
P(x)) ⇔ ∀xE, P(x)
xE, non
P(x) ⇔  non
(∀xE, P(x)).
Dans les notations des quantificateurs, le fait d'employer apparemment, entre la variable et son domaine, le même symbole ∈ que le symbole d'appartenance précédemment introduit, est une sorte d'abus de notation habituel: rigoureusement il faut comprendre cela comme étant deux notations différentes (toute confusion d'usage étant évitée par le contexte syntaxique de la formule).
La notion d'appartenance permet d'interpréter ∀xE, P(x) comme "Pour tout objet x, si xE alors P(x)", et d'interpréter ∃xE, P(x) comme "il existe x tel que (xE et P(x)" sauf que ce ne sont pas des formules "autorisées" en théorie des ensembles puisqu'elles invoquent les quantificateurs sans domaines, et que P(x) risque de n'avoir aucun sens si xE.
Inversement, la notion d'appartenance peut se redéfinir (de façon parfaitement correcte) au moyen du quantificateur existentiel et de la notion d'égalité :
xE ⇔ (∃yEy=x).
Notons le cas particulier de l'ensemble vide: un énoncé de la forme (∃x ∈ ∅, …) est toujours faux, et un énoncé de la forme (∀x ∈ ∅, …) est toujours vrai. On a (∃ ∈ E,vrai) ⇔ E ≠ ∅, et donc aussi (∀xE, faux) ⇔ E=∅.

Inclusion
Etant donné un ensemble E, on dit qu'un ensemble F est inclus dans E (ou qu'il est une partie ou un sous-ensemble de E, ou encore qu'il est plus petit que E, ou que E englobe F), et on écrit FE, ssi tout élément de F appartient à E:
FE ⇔ (∀xF, xE).
L'ensemble vide est inclus dans tout ensemble (y compris lui-même).
Si EF, pour tout énoncé P défini sur F (et donc aussi sur E), si ∀xF, P(x) alors ∀xE, P(x); si ∃xE, P(x) alors ∃xF, P(x).

Egalité entre ensembles

Axiome d'extensionnalité. Pour tous ensembles E et F, E=F ⇔ (EF  et FE).
En effet, EF  et FE signifie que E et F ont les mêmes éléments (pour tout x on a xE ⇔ xF); de plus, d'après la remarque ci-dessus, de EF  et FE il résulte que pour tout énoncé P sur F on a toujours (∀xF, P(x)) ⇔ (∀xE, P(x)), et de même pour ∃. Ceci caractérise bien ce qu'on attend de la notion d'égalité entre E et F.
De là on vérifie qu'il ne peut y avoir qu'un ensemble vide.
On dira que F est strictement inclus dans E et on note FE ssi FE et FE, autrement dit FE et EF.

Remarque à oublier
La description ci-dessus est conforme au concept d'ensemble tel qu'il est quasi-universellement accepté en mathématique, et constitue un point de départ pour développer les mathématiques de manière claire et naturelle, suivant une logique formalisable sans hésitation. On pourrait pourtant faire des mathématiques autrement.
Ainsi, certains mathématiciens développent une autre logique, la "logique intuitionniste", où la réunion de {0} et de ]0,1] serait incluse dans, mais non égale à [0,1]. (Hélas, je n'ai pas trouvé d'explication qui me satisfasse sur la signification de la logique intuitionniste ou ses rapports avec le reste des mathématiques, de sorte qu'en attendant je ne vois pas d'intérêt à faire davantage référence, dans les questions de fondements des mathématiques, à cette "logique" formelle qui me semble totalement arbitraire, parmi tant d'autres possibilités imaginables de changer les règles).
D'autre part (réflexion de mon cru cette fois-ci), certaines propriétés de la théorie de la mesure (qui inclut la théorie des probabilités) pourraient être interprétées sous forme d'énoncés plus simples mais portant sur un tout autre concept d'ensembles, qu'on pourrait présenter ainsi: Tirons une variable aléatoire x dans [0,1]. Pour cela, on peut par exemple dire qu'on tire successivement à pile ou face chacune de ses décimales binaires, ce qui fait un nombre infini de tirages au sort. Imaginons un instant qu'on puisse définir le domaine E de x, qui soit ainsi l'ensemble des nombres aléatoires dans [0,1], autrement dit ceux qu'on peut obtenir par tirage aléatoire. Cet ensemble est non vide puisqu'on peut effectuer des tirages aléatoires, obtenant des nombres réels qui existent. Alors, l'évènement qu'un autre nombre yE, tiré aléatoirement indépendamment de x soit égal à x, a la probabilité zéro de se produire, et doit donc être considéré comme une impossibilité. Ceci contredit l'affirmation plus haut qu'une variable y décrivant indépendamment le même ensemble E que x, pouvait prendre la même valeur que x.
Mais dorénavant banissons ces idées bizarres et tenons pour aquises les notions classiques de domaine et d'ensemble telles qu'esquissées plus haut.

1.4. Applications, relations unaires et compréhension


Notion d'application
On appellera application un objet mathématique f constitué des données suivantes:
- Un ensemble appelé domaine ou ensemble de définition de f et noté Domf.
- Pour chaque élément x de Domf, la donnée d'un objet noté f(x), appelé image de x par f.

De façon équivalente, on peut décrire une application f comme étant un symbole attaché à un symbole de variable, disons "x", de domaine Domf, tel que lorsqu'on fixe x (i.e. on lui fixe une valeur dans Domf), ce symbole f joue alors le rôle d'un symbole de constante.
Il y a une petite subtilité dans les notations du fait que dans l'utilisation d'une application, on ne se contentera pas de faire varier sa variable x sur son domaine mais on se permettra aussi de lui donner une valeur précise au moyen d'un terme, afin qu'il en résulte une valeur précise de f(x). Par exemple, si on donne à x la valeur de y, le résultat sera f(y). Pour cela, le rôle du symbole de variable x dont dépend f est en fait joué typographiquement, non par une lettre mais par le lieu intérieur à la parenthèse, dans lequel on pourra écrire le terme que l'on veut à condition que sa valeur appartienne au domaine de f, pour utiliser cette valeur comme valeur de x.

Axiome d'extensionnalité des applications. Pour toutes applications f et g, on a
f=g ⇔ ( Dom
f= Dom
g et ∀x Dom
f, f(x)=g(x)).
En particulier, il existe une unique application de domaine ∅, appelée l'application vide.
Soit une application f et soit E=Domf. L'ensemble des valeurs de f(x) pour tous les xE s'appelle l'ensemble image de f et se note Imf. C'est le domaine de f(x) vu comme objet variable du point de vue où x est variable de domaine E. Pour tout objet y on a yImf ⇔ ∃xE, y=f(x).
On dira qu'un ensemble F est un ensemble d'arrivée de f ssi ∀xDomf, f(x) ∈ F.
Cette condition est équivalente à : ImfF.
Etant donnés une application f et deux ensembles E et F, on dira que f est une application de E dans F pour signifier que (Domf=E) et (F est un ensemble d'arrivée de f).
On définit une application f de E dans F par les notations suivantes:
f:E
F
x
terme
où le "terme" est l'expression d'un objet dépendant de la variable x de domaine E, auquel f(x) devra être égal pour tout xE.
Nous désignerons aussi l'application définie par le terme de variable x en précisant son domaine E, mais sans préciser un ensemble d'arrivée, par la notation (Exterme). En pratique, on notera parfois simplement xterme lorsque le domaine E de x sera déterminé par le contexte.

Une application f est dite constante ssi elle admet un singleton comme ensemble d'arrivée, autrement dit il existe un y (dans un ensemble d'arrivée de f donné), tel que ∀xDomf,f(x)=y. Pour le dire encore autrement, l'image de f est vide ou un singleton.

Dans le langage courant, une application peut prendre la forme d'un nom suivi d'un complément de nom, ce complément servant de variable. Exemple: "le père de (Untel)". Un tel nom qui d'abord sert à désigner une application de cette manière par l'ajout d'un complément, peut aussi souvent être employé sans complément, et interprété alors comme signifiant l'ensemble image de cette application ("un père").

Relations unaires, retour sur les quantificateurs
Notons l'ensemble des valeurs de vérité V = {vrai, faux}.
On appelle relation unaire sur un ensemble E, une application de E dans V.
Tout comme on peut définir une application au moyen d'un terme, on peut définir une relation unaire au moyen d'un énoncé, qui n'est en fait rien d'autre qu'un terme à valeurs dans V. Implicitement, c'est ce que nous avions fait dans le contexte des notions de quantificateurs: quand nous disions qu'ils portaient sur un énoncé, en réalité nous voulions dire qu'ils portaient sur la relation unaire ainsi définie par cet énoncé. Prenant maintenant acte de ce fait, profitons-en pour reformuler les quantificateurs dans ce langage.
Soit donc R une relation unaire, et sous-entendons son domaine, fixe. Alors le quantificateur existentiel ∃x, R(x) se réécrit (vrai ∈ ImR), et également R ≠ (x ⟼ faux). Le quantificateur universel ∀x, R(x) se réécrit (faux ∉ Im R), et également R=(x ⟼ vrai).

Définition d'une partie par compréhension
Une relation unaire R sur E divise l'ensemble E en deux parties: l'ensemble A des valeurs de x telles que R(x) vaut vrai, noté {xE|R(x)}, et celui des valeurs pour lesquelles il vaut faux. Autrement dit, l'idée de la construction de A est celle-ci: on prend la variable x de domaine E, puis, à l'intérieur du point de vue où x est fixe (une variable libre), on introduit R(x) comme axiome (on le suppose vrai). Alors, vu de l'extérieur, on a ce nouveau domaine AE pour x, constitué des éléments de E sur lesquels R(x) est vrai. Formellement, l'égalité A={xE|R(x)} se reconnaît au fait que AE et ∀yE, yA ⇔ R(y). On dit que A est définie par compréhension.
L'ensemble vide s'obtient ainsi à partir de n'importe quel ensemble E par ∅ ={xE|faux}.
Cette notion de compréhension convertit les relations unaires sur E en parties de E, à l'inverse de celle d'appartenance, qui convertissait les parties F de E (ou généralement les ensembles F) en relations unaires x ⟼ (xF) (applicable à tout objet de l'univers en général et donc tout élément de E en particulier). Ainsi, relations unaires sur E et parties de E sont la traduction l'un de l'autre; toute partie FE peut être reconstruite par compréhension à partir de E et de la notion d'appartenance à F: F={xE|xF}.
Par cette traduction des relations unaires R sur E en parties F de E, les énoncés à quantificateurs se reformulent :
(∃xE, R(x)) ⇔ F ≠ ∅
(∀xE, R(x)) ⇔ F = E.
La principale différence est que la relation unaire ne comporte pas seulement la donnée de l'ensemble F mais aussi celle de son domaine E.