Axiomes des théories des ensembles/Introduction

Début de la boite de navigation du chapitre

Ce chapitre expose les axiomes des théories des ensembles. Plusieurs approches complémentaires sont présentées.

fin de la boite de navigation du chapitre

L’axiome d’extensionalité

L’axiome d’extensionalité est commun à toutes les théories des ensembles. En effet, si un être n’obéissait pas à cette loi, il ne pourrait pas être un ensemble. Elle peut être énoncée comme suit.

Début d'un axiome

Axiome d'extensionalité

Si deux ensembles ont les mêmes éléments alors ils sont égaux.

Ou plus formellement :

$\forall x,y{\text{ ensembles}},(\forall z,z\in x\Leftrightarrow z\in y)\Rightarrow (x=y)$

On peut en conclure qu’un ensemble est complètement déterminé par ses éléments. C’est le cas dès que toutes les vérités atomiques d’appartenance à un ensemble sont définies.

L’approche de Zermelo, Fraenkel et Skolem

Pour exclure les paradoxes de la théorie de Cantor, il faut faire comme Frege et formuler la théorie d’une façon axiomatique. Mais il faut le faire d’une façon qui exclut les ensembles problématiques tels que ceux de Russell ou de Burali-Forti.

Zermelo a proposé (1908) que tous les ensembles soient construits de façon progressive. Si l’on part de l’ensemble N des entiers positifs et si l’on adopte ensuite P(N) l’ensemble des sous-ensembles de N, P(P(N)) l’ensemble des sous-ensembles de P(N) et ainsi de suite, on obtient des ensembles assez grands pour satisfaire tous les besoins ordinaires des mathématiciens, y compris pour les théories des nombres réels et des espaces de fonctions.

Avec cette image d’un univers d’ensembles construits progressivement à partir des ensembles finis et d’ensembles infinis de base, comme celui des entiers, on peut développer une théorie axiomatique suffisante pour donner des preuves rigoureuses des grands théorèmes de Cantor, aussi rigoureuses que celles des théorèmes d’Euclide.

Les axiomes proposés initialement par Zermelo ne sont pas tout à fait suffisants pour toutes les constructions utilisées dans les preuves de Cantor. Fraenkel et Skolem ont introduit un axiome supplémentaire, l’axiome de remplacement. On appelle ZFC (Zermelo, Fraenkel, axiome du choix) la théorie ainsi définie. Son formalisme dans le cadre du calcul des prédicats au premier ordre a été développé par Skolem. Elle suffit pour démontrer tous les théorèmes de Cantor et une très large partie des mathématiques contemporaines. Elle a été adoptée par le groupe Bourbaki.

La construction des ensembles finis

La façon la plus naturelle d’introduire les ensembles consiste à supposer qu’on a des non-ensembles, qu’on peut appeler des atomes, que l’on peut rassembler afin de former des ensembles.

Pour réaliser tous les ensembles finis d’atomes, on a seulement besoin des deux règles suivantes :

• si $x$ est un atome alors $\{x\}$ (Singleton de x) est un ensemble ;
• si $x$ et $y$ sont des ensembles alors $x\cup y$ est un ensemble.

En ajoutant la règle suivante, on peut construire tous les ensembles finis d’ensembles finis d’atomes, les ensembles finis d’ensembles finis d’ensembles finis et ainsi de suite.

• si $x$ est un ensemble alors $\{x\}$ est un ensemble.

Habituellement on exclut les atomes de la théorie ZFC. Cela permet de se passer du prédicat unaire « est un ensemble » parce qu’alors tous les êtres sont des ensembles. L’ensemble vide et les ensembles que l’on peut construire à partir de lui suffisent pour tous les besoins. On peut alors se donner les trois axiomes suivants.

Début d'un axiome

Axiome d’existence de l’ensemble vide

Il existe un ensemble vide.

Autrement dit,

$\exists x\quad \forall y\quad y\not \in x$.

Début d'un axiome

Axiome du singleton

Pour tout x, singleton de x existe.

Autrement dit,

$\forall x\quad \exists y\quad \forall z\quad (z\in y\Leftrightarrow z=x)$

Début d'un axiome

Axiome de la réunion finie

Pour tout x et y, x union y existe.

Autrement dit,

$\forall x\quad y\quad \exists z\quad \forall w\quad (w\in z\Leftrightarrow (w\in x{\text{ ou }}w\in y))$.

Ces deux axiomes (singleton et réunion finie) peuvent être déduits d’autres axiomes qui seront introduits plus loin.

L’axiome de l’infini

Le nombre infini des ensembles finis

Les axiomes précédents permettent de prouver l’existence de tous les ensembles finis, construits à partir des atomes ou du seul ensemble vide. Les ensembles finis sont en nombre infini, comme les nombres entiers et comme les suites finies de mots.

Mais de l’existence d’un nombre infini d’ensembles finis il ne s’ensuit pas qu’il existe un ensemble infini, c’est-à-dire un ensemble qui contient plus qu’un nombre fini d’éléments. L’existence d’un tel ensemble doit être postulée par un axiome supplémentaire qu’on appelle l’axiome de l’infini. On peut lui donner plusieurs formes, différentes quant à la taille de l’ensemble infini dont on postule l’existence.

La théorie ZFC fait un choix minimaliste. L’axiome de l’infini dit qu’il existe un ensemble assez grand pour contenir des représentants de tous les nombres entiers, et c’est tout. Les autres axiomes, exposés plus loin, suffisent alors pour construire tous les autres ensembles infinis dont on a couramment besoin. D’autres axiomes de l’infini, les axiomes des très grands ensembles, peuvent être introduits ultérieurement si on le souhaite.

Les nombres entiers sont-ils des ensembles ou des expressions formelles ?

La façon la plus naturelle d’introduire les nombres entiers est de les considérer comme des atomes, des non-ensembles, qui ont une existence indépendante de celle des ensembles. Mais ZFC permet de représenter tous les nombres entiers par des ensembles. Cette représentation est fondée sur les idées de Cantor à propos de la notion de nombre et de sa généralisation aux nombres infinis. Elle enrichit beaucoup les outils conceptuels du mathématicien parce qu’elle conduit à généraliser d’une façon naturelle des théorèmes énoncés initialement à propos des seuls ensembles finis. Elle est tellement intéressante qu’elle a parfois conduit certains mathématiciens, plus cantoriens que Cantor, à voir dans la théorie des ensembles la clé de tous les mystères sur l’essence des nombres, c’est-à-dire sur notre capacité à dire des vérités générales à leur sujet. Ce point de vue est très important à bien des égards mais il ne doit pas faire oublier qu’il y a d’autres approches possibles sur la nature des nombres entiers.

Définir les nombres entiers comme des mots, des expressions formelles, a l‘inconvénient de manquer la généralisation aux nombres infinis mais présente d’autres avantages. La théorie des systèmes formels est en un sens plus fondamentale qu’une théorie générale des ensembles comme celle de Zermelo, parce qu’elle est plus élémentaire.

Au point de vue de la fiabilité des principes, les théories élémentaires sont plus fondamentales que les autres. La question si ZFC est absurde ou non est une question qui se pose vraiment. Qu’elle soit en accord avec l’intuition ne suffit pas pour prouver sa cohérence. La théorie contradictoire de Frege était en accord avec l’intuition. Pour prouver que ZFC est cohérente on a besoin de la considérer comme un système formel, un ensemble de formules. La théorie des systèmes formels est donc une théorie des ensembles plus fondamentale que ZFC.

La représentation des nombres entiers par des ensembles

On pourrait représenter 0 par l’ensemble vide, 1 par $\{0\}$, 2 par $\{\{0\}\}$, 3 par $\{\{\{0\}\}\}$ et ainsi de suite. D’autres définitions sont possibles. La suivante est la plus avantageuse.

$0$ est représenté par l’ensemble vide $\varnothing$.

$1$ est représenté par Singleton de 0, c’est-à-dire $\{\varnothing \}$, l’ensemble qui contient un seul élément, $0$

$2$ est représenté par $\{1\}\cup 1$, c’est-à-dire l’ensemble qui contient deux éléments, 0 et 1 : $\{\{\varnothing \},\varnothing \}$.

$3$ est représenté par $\{2\}\cup 2$, c’est-à-dire $\{\{\{\varnothing \},\varnothing \}\}\cup \{\{\varnothing \},\varnothing \}=\{\{\{\varnothing \},\varnothing \},\{\varnothing \},\varnothing \}$.

De manière générale, $n+1$ est représenté par $\{n\}\cup n$ et contient $n+1$ éléments, $0,1,2,...,n$.

De cette façon tout nombre entier $n$ est représenté par un ensemble qui contient exactement $n$ éléments. La théorie générale des ordinaux, exposée plus loin, montre que cette représentation est très utile pour prouver commodément les théorèmes de Cantor.

L’existence de l’ensemble N des entiers positifs

Sous sa forme la plus élémentaire, l’axiome de l’infini peut être écrit comme ci-dessous.

Début d'un axiome

Axiome de l'infini

Il existe un ensemble qui contient tous les nombres entiers positifs.

Autrement dit,

$\exists x\quad (0\in x{\text{ et }}\forall y\in x\quad \{y\}\cup y\in x)$.

Les autres axiomes qui vont être exposés permettent alors de prouver qu’il existe un ensemble qui contient tous les entiers positifs et seulement eux, c’est-à-dire l’ensemble N des nombres naturels.

L’axiome de la somme

L’axiome de l’existence de la réunion de deux ensembles suffit pour construire la réunion d’un nombre fini d’ensembles, mais il ne suffit pas pour construire la réunion d’un ensemble infini d’ensembles. Pour cela un axiome supplémentaire est nécessaire, l’axiome de la somme, qu’on peut aussi appeler axiome de la réunion infinie.

Début d'un axiome

Axiome de la somme

Pour tout ensemble d’ensembles, leur réunion est un ensemble.

Autrement dit :

$\forall x\quad \exists y\quad \forall z\quad (z\in y\Leftrightarrow \exists w\quad (w\in x{\text{ et }}z\in w))$.

L’ensemble y est la réunion des éléments de x. On l’appelle aussi l’ensemble-somme de x, ou la somme de x, quand il n’y a pas d’ambiguïté.

On peut déduire l’axiome de la réunion de deux ensembles à partir de l’axiome de la somme si on introduit l’axiome de la paire.

Définition

On appelle paire de x et y l’ensemble qui contient x et y comme seuls éléments.

Début d'un axiome

Axiome de la paire

Pour tout x et y, la paire de x et y existe.

Autrement dit :

$\forall x\quad \forall y\quad \exists z\quad \forall w\quad (w\in z\Leftrightarrow (w=x{\text{ ou }}w=y))$.

L’axiome du singleton est une conséquence de l’axiome de la paire parce que Singleton de x égale Paire de x et x.

L’axiome de l’ensemble des sous-ensembles

Cet axiome permet de construire des grands ensembles infinis à partir de ce petit ensemble infini qu’est N. Ces nouveaux ensembles infinis sont tellement grands qu’ils sont indicibles. Nulle théorie ne peut nommer tous leurs éléments. Ils seront appelés aussi infinitaires, par contraste avec des ensembles infinis plus élémentaires, tels que N et les systèmes formels, qui seront dits finitaires.

Début d'un axiome

Axiome de l’ensemble des sous-ensembles

Pour tout ensemble, l’ensemble de tous ses sous-ensembles existe.

Autrement dit :

$\forall x\quad \exists y\quad \forall z\quad (z\in y\Leftrightarrow (\forall w\in z\quad w\in x))$

ou plus brièvement :

$\forall x\quad \exists y\quad \forall z\quad (z\in y\Leftrightarrow z\subset x)$.

y est aussi appelé l’ensemble P(x) des parties de x, ou l’ensemble-puissance de x, ou 2 puissance x, pour des raisons qui seront exposées plus loin.

Avec cet axiome, on peut construire P(N), P(P(N)) et ainsi de suite, en répétant cette opération un nombre fini de fois.

L’axiome de séparation de Zermelo

La plupart des ensembles sont définis comme des extensions conceptuelles, c’est-à-dire qu’ils sont définis comme des ensembles qui contiennent tous les êtres pour lesquels un prédicat est vrai. Comme l’axiome de Frege (tout concept a une extension) est contradictoire, et comme les axiomes précédents suffisent pour faire des ensembles infinis assez grands, Zermelo a réintroduit l’axiome de Frege sous une forme affaiblie, en limitant les extensions conceptuelles à des sous-ensembles d’ensembles déjà définis. Son axiome de séparation peut être énoncé plus précisément comme suit :

Pour tout ensemble x et tout concept, il existe un sous-ensemble de x qui contient tous les éléments de x pour lesquels ce concept est vrai et seulement eux.

Plus formellement, l’axiome de séparation est défini par un schéma d’axiomes, qui détermine des axiomes en nombre infini, qui sont tous des formes particulières de l’axiome de séparation.

Le schéma des axiomes de séparation

Pour tout prédicat $P(x_{0},x_{1},...,x_{n})$ qui contient n+1 variables libres et qui est défini à partir des seuls prédicats fondamentaux « être dans » et « égale » et des opérateurs de la logique du premier ordre, la formule suivante est un axiome :

$\forall x_{0}~x_{1}~...~x_{n},\exists y,\forall z,(z\in y)\Leftrightarrow (z\in x{\text{ et }}P(x_{0},x_{1},...,x_{n}))$.

La construction des extensions relationnelles

Il semble que les axiomes de séparation, tels qu’ils viennent d’être énoncés, ne permettent de définir que les extensions des prédicats unaires et qu’ils nous laissent dépourvus pour les extensions des concepts relationnels. Une astuce formelle montre cependant que tel n’est pas le cas.

L’extension d’un concept relationnel, binaire $x{\mathcal {R}}y$ pour fixer les idées, peut être définie comme l’ensemble des couples (x, y) qui satisfont à la relation ${\mathcal {R}}$. La notion de couple n’a pas été introduite mais on peut la définir de plusieurs façons à partir des constructions précédentes. Par exemple, on peut définir le couple de x et y par l’ensemble Paire de Singleton de x et Paire de x et y.

Définir Couple de x et y par Paire de x et y ne convient pas parce qu’on veut que Couple de x et y soit différent de Couple de y et x, quand x et y sont différents, pour des raisons formelles. En revanche Paire de Singleton de x et Paire de x et y convient très bien.

L’extension de la relation binaire ${\mathcal {R}}$ limitée à un ensemble x est alors définie par l’ensemble y tel que

pour tout z, z est dans y équivaut à il existe v et w tels que (z = (Couple de v et w) et z est dans x et $v{\mathcal {R}}w$)

L’existence de y est garantie par un axiome de séparation de Zermelo.

La même construction peut être faite pour toutes les relations ternaires et plus. On peut définir Triplet de x, y et z par Couple de x et Couple de y et z, par exemple.

L’axiome de remplacement de Fraenkel

Fraenkel et Skolem se sont rendus compte que les axiomes de séparation de Zermelo ne suffisaient pas pour démontrer certains théorèmes de Cantor, mais que pour cela il suffit d’échanger le schéma d’axiomes de Zermelo contre un autre, un peu différent, qui formalise l’idée de la construction d’un ensemble par des remplacements simultanés de tous les éléments d’un ensemble déjà construit.

Plus précisément, on suppose que si ${\mathcal {R}}$ est une relation binaire fonctionnelle alors :

$\forall x,\exists y,\forall z,(z\in y)\Leftrightarrow (\exists w,w\in x{\text{ et }}w{\mathcal {R}}z)$.

$y$ est appelé ensemble-image, ou image, de $x$ par la relation ${\mathcal {R}}$.

On peut alors formuler l'axiome de remplacement sous la forme suivante :

Début d'un axiome

Axiome de remplacement

Si R est une relation fonctionnelle alors pour tout x, l'ensemble-image de x par R existe.

${\mathcal {R}}$ est une relation fonctionnelle veut dire ici qu’elle associe au plus un élément z à tout élément w, autrement dit, pour tout w il existe au plus un z tel que $w{\mathcal {R}}z$, autrement dit encore, pour tous w, z et z’, si ($w{\mathcal {R}}z$ et $w{\mathcal {R}}z'$) alors z = z’.

L’axiome de remplacement est formulé par un schéma d’axiomes.

Pour tout prédicat P(w, z, x1…, xn) avec n+2 variables libres (et construit avec « être dans », « = » et la logique du premier ordre) la formule suivante est un axiome :

Pour tout x1…, xn,

si pour tout w, z et z’, (si (P(w, z, x1…, xn) et P(w, z’, x1…, xn) alors z = z’)

alors pour tout x, il existe un y tel que pour tout z, (z est dans y équivaut à (il existe un w tel que (w est dans x et P(w, z, x1…, xn)).

L’axiome de séparation de Zermelo peut être déduit de l’axiome de remplacement. Pour tout prédicat P(x, x1…, xn) il suffit de considérer la relation (P(x, x1…, xn) et x = y).

L’axiome de remplacement respecte la logique de construction progressive adoptée par Zermelo. Il ne permet pas de construire les grands ensembles contradictoires comme celui de Russell parce qu’un ensemble défini par remplacement n’est jamais plus grand que l’ensemble à partir duquel il est défini.

L’axiome de remplacement peut être formulé d’une façon apparemment plus restrictive, mais en fait équivalente, en imposant à une relation fonctionnelle de toujours associer un élément et un seul (et non au plus un) à tout élément de l’ensemble de départ.

L’axiome du choix

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

Une reformulation de ZFC, la théorie des classes de Von Neumann, Gödel et Bernays

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

La théorie des types de Whitehead et Russell

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

La théorie du zig-zag interdit de Quine

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

Le problème des définitions non-prédicatives

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

Les ensembles finitaires

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

Les ensembles finitaires sont définis avec des moyens élémentaires mais ils sont souvent infinis.

Les mathématiques finitaires consistent à mettre en pratique un principe de progression ontologique, commencer par ce qui est simple, évident, élémentaire, pour poursuivre sur des bases solides.

Texte déplacé ici

L’énumérabilité selon Smullyan

Voir la page Énumérabilité selon Smullyan.

Formules initiales et règles de production pour les vérités atomiques d’appartenance aux ensembles énumérables

Voir la page Formules initiales et règles de production pour les vérités atomiques d’appartenance aux ensembles énumérables.

Les théorèmes fondamentaux de l’énumérabilité et de l’indécidabilité

Voir la page Les théorèmes fondamentaux de l’énumérabilité et de l’indécidabilité.

La négation dans les prédicats finitaires

Voir la page La négation dans les prédicats finitaires.

Les axiomes d’une théorie élémentaire des ensembles finitaires

Les axiomes de Finitaire1

L’axiome d’extensionalité

Les axiomes d’existence des ensembles

Le principe d’induction complète

Les ensembles infinitaires

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

L’axiome de fondation, la circularité et les hyperensembles

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?