Axiome de l'infini

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En mathématiques dans le domaine de la théorie des ensembles, l'axiome de l'infini désigne l'un des axiomes de la théorie des ensembles de Zermelo-Fraenkel qui assure l'existence d'un ensemble infini, plus précisément d'un ensemble qui contient une représentation des entiers naturels. Il apparait dans la première axiomatisation de la théorie des ensembles, publiée par Ernst Zermelo en 1908, sous une forme cependant un peu différente de celle exposée ci-dessous.

Énoncé de l'axiome[modifier | modifier le code]

Il existe plusieurs variantes de l'axiome, suivant par exemple que l'on dispose de la notion d'ordinal ou non. Une façon très intuitive serait de dire qu'un ensemble qui représente celui des entiers naturels existe. En fait on a juste besoin de montrer qu'un ensemble ayant pour éléments des représentations des entiers naturels (et éventuellement d'autres) existe. Pour représenter les entiers naturels on utilise un 0 et une opération successeur. Suivant les idées de von Neumann, on va représenter 0 par l'ensemble vide (qui a 0 éléments) et le successeur par la fonction xx ∪ {x}, qui à un ensemble associe celui obtenu en ajoutant l'ensemble de départ comme élément (et qui vérifie intuitivement que si x a n éléments, alors x ∪ {x} en a n +1). L'existence de l'ensemble vide est assurée par un axiome ad hoc, ou par d'autres axiomes de la théorie. Pour un ensemble x donné, on peut former le singleton {x} par l'axiome de la paire, et la réunion x ∪ {x} par l'axiome de la réunion et à nouveau l'axiome de la paire.

On a évidemment que le successeur de tout ensemble est non vide : pour tout ensemble x, x ∪ {x} ≠ ∅. On montrera ensuite que, sur les entiers au moins, la fonction successeur est bien injective, ce qui assurera, avec la précédente propriété, qu'un ensemble qui contient 0 et le successeur de chacun de ses éléments contient bien une copie des entiers, et donc est infini au sens intuitif. On prendra d'ailleurs cette représentation comme définition des entiers en théorie des ensembles.

L'axiome s'écrit donc :

Il existe un ensemble auquel appartient l'ensemble vide et qui est clos par application du successeur xx ∪ {x},

c'est-à-dire dans le langage formel de la théorie des ensembles :

\exists A (\emptyset \in A \land \forall x (x \in A \Rightarrow x \cup \{x\} \in A))

à noter que \emptyset \in A est juste une abréviation pour par exemple \exists y (\forall z (z \notin y) \land y \in A), et que x \cup \{x\} \in A est une abréviation pour \exists y \{(\forall z (z \in y \Leftrightarrow z \in x \lor z = x)) \land y \in A\} c'est-à-dire que l'axiome s'énonce bien dans le langage de la théorie des ensembles : le calcul des prédicats du premier ordre égalitaire avec pour seul symbole non logique celui pour l'appartenance, « ∈ » .

L'ensemble des entiers naturels[modifier | modifier le code]

Définition[modifier | modifier le code]

Dès que l'on dispose des axiomes de l'ensemble vide, de la paire, et de la réunion, l'ensemble A dont on a affirmé l'existence contient pour chaque entier naturel un représentant, que l'on va prendre comme définition en théorie des ensembles. Par exemple 1 étant successeur de 0, et le singleton d'élément l'ensemble vide (c'est-à-dire 0) :

1 = 0 ∪ {0} = ∅ ∪ {∅} = {∅} = {0}.

De même, 2 en tant que successeur de 1, est la paire {0,1} :

2 = 1 ∪ {1} = {0} ∪ {1} = {∅, {∅}} = {0,1},

et ainsi de suite. Une conséquence de cette définition est que chaque nombre entier est égal à l'ensemble de tous les nombres entiers qui le précèdent. Ainsi l'axiome affirme essentiellement qu’il existe un ensemble contenant tous les nombres entiers naturels.

L'existence de chacun de ces entiers est assurée sans axiome de l'infini, mais on utilise celui-ci pour montrer que l'ensemble des entiers naturels existe. On peut former en effet un ensemble, noté ω en théorie des ensembles, qui est l'intersection de tous les ensembles contenant 0 et clos par successeur (c'est-à-dire le plus petit au sens de l'inclusion des ensembles contenant 0 et clos par successeur). Pour que cette définition soit correcte, il faut intuitivement que la classe des ensembles contenant 0 et clos par successeur soit non vide, ce qu'assure l'axiome de l'infini. Plus formellement l'existence de ω est assurée par le schéma d'axiomes de compréhension et son unicité par l'axiome d'extensionnalité. En effet, notons Cl(Y) pour « ∅ ∈ Y et ∀ y (yYy ∪ {y} ∈ Y) », c'est-à-dire « Y est clos par successeur et 0 lui appartient », et soit A un ensemble vérifiant Cl(A) dont l'existence est assurée par l'axiome de l'infini, alors ω se définit ainsi (A n'intervient que pour pouvoir définir ω, mais ω ne dépend pas de A) :

ω = { xA | ∀Y (Cl(Y) ⇒ xY) } (= { x | ∀Y (Cl(Y) ⇒ xY) }).

La définition même de l'ensemble ω donne un énoncé du principe de récurrence sur les entiers : tout ensemble à qui 0 appartient et qui est clos par successeur est un sur-ensemble de ω. On peut en donner un énoncé un peu plus familier mais équivalent en théorie des ensembles par le schéma de compréhension, on note x+ le successeur de x, on a alors pour une propriété arbitraire exprimée dans le langage de la théorie des ensembles par la formule P x a1ak (pas d'autre variable libre) :

a1, … ,ak{ [ P 0 a1ak et ∀ y ∈ ω (P y a1akP y+ a1ak)] ⇒ ∀ x ∈ ω P x a1ak }
(toute propriété vraie en 0 et qui passe au successeur sur les entiers est vraie pour tous les entiers).

La récurrence est valide pour toute propriété exprimée dans le langage de la théorie des ensembles : ce n'est pas anodin, cela fait de cette récurrence une propriété beaucoup plus forte que la récurrence de l'arithmétique de Peano (comme théorie du premier ordre), le langage de la théorie des ensembles étant strictement plus expressif que celui de l'arithmétique de Peano.

Ordre[modifier | modifier le code]

Pour qu'il soit tout à fait légitime de considérer ω comme l'ensemble des entiers naturels, il reste à vérifier que le successeur est bien injectif : comme un successeur, qui est un ensemble non vide, ne peut jamais être nul, cela confirme que l'ensemble construit est bien infini au sens intuitif. De plus, comme la propriété de récurrence est conséquence directe de la définition de l'ensemble des entiers naturels, on aura vérifié ainsi les axiomes de Peano, qui sont donc des théorèmes dans ce contexte, et qui associés aux axiomes de la théorie des ensembles, permettent de construire les ensembles de nombres usuels comme les relatifs, les rationnels, les réels, les complexes, …

Une façon simple pour obtenir cette propriété est d'étudier la structure définie par la relation d'appartenance sur les entiers que l'on a construit : on montre qu'il s'agit d'un ordre strict total (et la propriété de récurrence dit alors que c'est un bon ordre). On peut utiliser la propriété de récurrence, qui est déjà démontrée.

On montre que tout élément d'un entier est un entier par une récurrence immédiate. La transitivité de l'appartenance sur les entiers naturels s'écrit alors :

x ∈ ω ∀yz[yx ⇒ (zyzx)],

c'est-à-dire :

x ∈ ω ∀y(yxyx),

tout élément d'un entier en est aussi un sous-ensemble. Cette propriété se démontre à nouveau par récurrence. Elle est évidente pour l'ensemble vide. On la suppose pour x entier. Un élément de x+ est alors soit x, inclus donc dans x+=x ∪ {x}, soit appartient à x et on conclut par hypothèse de récurrence. On dit aussi que les entiers naturels sont des ensembles transitifs, et c'est également le cas de ω.

On montre maintenant l'irréflexivité de l'appartenance sur les entiers naturels : aucun entier naturel n'appartient à lui-même :

x ∈ ω xx,

Cette propriété se démontre par récurrence à l'aide de la propriété précédente. Elle est évidente pour l'ensemble vide. On la suppose pour x entier. On suppose que x+x+ et on montre que c'est absurde. Deux cas sont possibles : soit x+=x, mais alors xx ce qui contredit l'hypothèse de récurrence ; soit x+x et d'après la propriété précédente x+x, donc xx ce qui contredit à nouveau l'hypothèse de récurrence.

L'appartenance définit donc bien un ordre strict sur les entiers. Pour montrer la totalité, on caractérise d'abord l'ordre large sur les entiers correspondant à l'ordre strict de l'appartenance : c'est l'inclusion. On doit donc montrer l'équivalence :

x ∈ ω ∀y ∈ ω [yx ⇔ (yx ou y = x)]

La réciproque a déjà été démontrée (c'est essentiellement la transitivité de l'appartenance). On montre par récurrence sur x que tout entier naturel qui est sous-ensemble de x est soit x, soit un élément de x. Elle est évidente pour l'ensemble vide. Supposons là pour l'entier x. Soit y un entier sous-ensemble de x+=x ∪ {x}. Si xy, alors xy, donc x+y donc x+ = y. Sinon, y est sous-ensemble de x : par hypothèse de récurrence, c'est soit x, élément de x+, soit un élément de x donc de x+.

On peut maintenant montrer la totalité, à savoir que deux entiers distincts sont toujours comparables par l'appartenance :

x ∈ ω ∀y ∈ ω (xy ou x = y ou yx).

On démontre la totalité par récurrence sur x. L'ensemble vide est élément de tout entier naturel qui est un successeur par une récurrence immédiate, et on a donc le résultat quand x est vide. Supposons la propriété pour x :

y ∈ ω (xy ou x = y ou yx).

Soit donc un entier naturel y quelconque, si x = y ou yx, alors yx+. Reste à traiter le cas xy. On a donc, d'après la transitivité x+=x ∪ {x} ⊂ y. Alors x+ = y, ou x+ est élément de y, ce qui achève la récurrence.

Une fois définie la structure d'ordre total sur les entiers naturels, on obtient l'injectivité du successeur en montrant qu'il s'agit d'une application strictement croissante sur les entiers naturels. On suppose que xy. On en déduit par transitivité que x ∪ {x} = x+y, donc x+y+, et x+y+, puisque yy, donc x+y+. L'opération successeur est strictement croissante donc injective par totalité de l'ordre.

Axiomes de Peano[modifier | modifier le code]

En résumé, l'axiome de l'infini a permis de définir un ensemble ω qui représente fidèlement les entiers naturels, en particulier parce qu'il vérifie les axiomes de Peano (qui deviennent donc des théorèmes) :

  • x ∈ ω x+ ≠ 0 ;
  • x ∈ ω ∀y ∈ ω (x+ = y+x = y) ;
  • X { [ 0 ∈ X et ∀ y(yXy+X)] ⇒ ω ⊂ X }.

On a démontré directement au passage l'existence d'un bon ordre strict sur les entiers, dont on montre facilement qu'il est la clôture transitive du successeur, c'est-à-dire l'ordre usuel sur les entiers.

Une fois ces propriétés démontrées on peut ignorer la façon dont les entiers ont été construits pour les développements mathématiques usuels. On montre en particulier le principe de définition par récurrence qui permet d'introduire par exemple l'addition, la multiplication, l'exponentielle, etc. Le principe de définition par récurrence permet également de montrer qu'en théorie des ensembles deux structures munies d'un 0 et d'une opération successeur et qui vérifient ces trois axiomes sont isomorphes[1]. La façon dont on les a construits n'est donc pas très importante.

Par là même l'énoncé de l'axiome de l'infini n'a pas le caractère intrinsèque des autres axiomes : l'existence de n'importe quel ensemble qui permet une construction analogue convient. De plus, grâce à la définition par récurrence et au schéma de remplacement, on montre que l'existence de n'importe quel ensemble représentant les entiers a pour conséquence l'existence d'un autre ensemble représentant les entiers, avec un autre choix pour le 0 et le successeur.

Pour relativiser ce qui précède, il faut quand même ajouter que cette construction est particulièrement importante en théorie des ensembles. D'une part elle se généralise aux ordinaux et cette construction des ordinaux joue un rôle fondamental dans la théorie des ensembles moderne. D'autre part elle correspond à l'idée intuitive qui est de caractériser les classes d'équipotence des ensembles finis en en donnant un représentant par classe (chaque entier de von Neumann obtenu en appliquant n fois le successeur à partir de 0, a bien n éléments, (n étant l'entier au sens intuitif), et on choisit de définir un entier comme l'ensemble de tous les entiers qui le précèdent. Cette construction (pour les ordinaux en général) a d'ailleurs été découverte plusieurs fois : si elle a été introduite par Von Neumann en 1923, elle avait été développée de façon plus informelle dans deux articles de Dmitry Mirimanoff en 1917, et par Zermelo en 1915 dans des écrits non publiés[2].

Variantes[modifier | modifier le code]

Il existe plusieurs variantes pour l'énoncé de l'axiome. Celle donnée au-dessus fait directement référence à la construction la plus usuelle des entiers en théorie des ensembles et se développe naturellement dans la théorie de Zermelo (on n'a jamais eu besoin du schéma d'axiomes de remplacement). Cependant il existe d'autres énoncés de l'axiome avec des variations plus ou moins importantes.

Ordinaux[modifier | modifier le code]

Les ordinaux de la théorie des ensembles sont définis comme les ensembles transitifs (strictement) bien ordonnés par l'appartenance. On a vraiment défini ainsi les ordinaux au sens intuitif (tout bon ordre est isomorphe à un et un seul ordinal) en présence du schéma de remplacement (utile pour l'existence), donc dans la théorie de Zermelo-Fraenkel (ZF). Cela dit cette définition ne pose aucun problème en elle-même dans la théorie de Zermelo (sans axiome de l'infini).

Il est à peu près immédiat que la classe des ordinaux est stable par l'opération successeur introduite sur les entiers : si α est un ordinal α ∪ {α} est un ordinal. Un ordinal est dit limite s'il est non vide et n'est le successeur d'aucun ordinal. On remarque que l'ensemble vide est un ordinal, ainsi que tous les entiers non nuls définis ci-dessus par passage au successeur, aucun n'est donc un ordinal limite.

Un énoncé possible de l'axiome de l'infini[3] est le suivant :

Il existe un ordinal limite.

Il est équivalent à celui donné ci-dessus. En effet on a montré que ω était un ensemble transitif bien ordonné par l'appartenance, c'est-à-dire un ordinal. D'autre part, par construction, les seuls éléments de ω, c'est-à-dire les seuls ordinaux strictement inférieurs à ω, sont les entiers qui ont tous pour successeur un entier, donc ω est un ordinal limite.

Réciproquement on montre qu'un ordinal limite est nécessairement un sur-ensemble de ω. En effet un tel ordinal α a forcément l'ensemble vide pour élément, puisque son plus petit élément β (qui existe car α est non vide par définition) en est aussi un sous-ensemble par transitivité, et s'il n'était pas vide on aurait un élément de α strictement plus petit que β. D'autre part si γ appartient à α son successeur aussi. En effet son successeur γ ∪ {γ} est par transitivité un sous-ensemble de α, qui ne peut être α car celui-ci est limite, et qui est un ordinal. Il existe donc des éléments de α qui n'appartiennent pas à γ ∪ {γ} et donc auxquels γ appartient par totalité de l'ordre sur α. Le plus petit d'entre eux est la borne supérieure de l'ensemble γ ∪ {γ} pour l'appartenance dans α ; il ne peut avoir pour élément un ordinal de α qui n'appartienne pas à γ ∪ {γ} : on aurait trouvé un plus petit majorant de γ ∪ {γ} par totalité de l'ordre dans α. C'est donc γ ∪ {γ} lui-même, qui appartient alors à α.

Les deux énoncés sont donc équivalents, modulo les autres axiomes de la théorie des ensembles (ceux de Zermelo suffisent).

Version de Zermelo[modifier | modifier le code]

La version de Zermelo de l'axiome de l'infini est qu'il existe un ensemble auquel appartient l'ensemble vide, et tel que, si x appartient à cet ensemble, alors le singleton {x} y appartient également[4].

Indépendance de l'axiome de l'infini[modifier | modifier le code]

Dans la théorie ZFC, si on omet l'axiome de l'infini, la collection des entiers naturels peut être une classe propre, c'est-à-dire que l'axiome de l'infini est bien nécessaire pour l'existence de ω. En effet on montre que dans un univers de la théorie des ensembles, Vω (voir axiome de fondation), la classe des ensembles héréditairement finis (les ensembles finis dont les éléments sont des ensembles finis, et ainsi de suite), est un modèle de tous les axiomes de ZFC sauf l'axiome de l'infini. En effet dans ce cas tous les ordinaux sont des entiers, or la classe des ordinaux est forcément une classe propre (voir paradoxe de Burali-Forti).

Ce modèle montre donc également que l'axiome de l'infini est indépendant des autres axiomes de ZFC, bien sûr à supposer que ZFC soit une théorie cohérente.

Notes[modifier | modifier le code]

  1. cela n'a de sens qu'à l'intérieur d'un même univers de la théorie des ensembles, il peut tout à fait y avoir deux univers différents de la théorie des ensembles qui n'ont pas les mêmes entiers.
  2. (en) Akihiro Kanamori, The higher infinite : large cardinals in set theory from their beginnings, Berlin New York, Springer,‎ 2003 (ISBN 3-540-00384-3, lire en ligne), voir ref 14, p. 30.
  3. Krivine (98) p. 36
  4. Ernst Zermelo (1908) Untersuchungen über die Grundlagen der Mengenlehre I, Mathematische Annalen 65: 261-281, axiome VII.

Bibliographie[modifier | modifier le code]