Ordinal de Hartogs
En théorie des ensembles, l'ordinal de Hartogs d'un ensemble A désigne le plus petit ordinal qui ne s'injecte pas dans A. Son existence utilise le remplacement et se démontre sans l'axiome du choix, contrairement au théorème de Zermelo qui revient à l'existence d'un ordinal en bijection avec A, et équivaut, lui, à l'axiome du choix.
L'ordinal de Hartogs étant nécessairement un ordinal initial, ou cardinal, on parle également de cardinal de Hartogs. En présence de l'axiome du choix, le cardinal de Hartogs de A est le plus petit cardinal strictement supérieur au cardinal de A, au sens où il s'injecte dans tout ensemble qui ne s'injecte pas dans A.
Le théorème de Hartogs sous sa forme originale énonce que l'on peut associer à tout ensemble A un ensemble bien ordonné qui ne s'injecte pas dans A. Il particularise à l'ensemble A la construction qui mène au paradoxe de Burali-Forti. Cette version ne nécessite pas le schéma d'axiomes de remplacement, et se démontre donc dans la théorie de Zermelo sans axiome du choix.
Hartogs en déduit que la comparabilité cardinale (étant donné deux ensembles, il existe une injection de l'un dans l'autre) entraîne l'axiome du choix, et donc est équivalente à ce dernier.
Existence et définition
[modifier | modifier le code]On se place dans la théorie de Zermelo-Fraenkel sans l'axiome du choix, les ordinaux sont obtenus par la construction de von Neumann. On sait alors qu'à tout ensemble bien ordonné on peut associer un unique ordinal isomorphe à celui-ci (on utilise le schéma d'axiomes de remplacement via par exemple une définition par récurrence transfinie). Étant donné un ensemble A, on peut définir par le schéma d'axiomes de compréhension l'ensemble BA des parties de A × A qui sont des graphes de relations de bon ordre sur un sous-ensemble de A. À chacune des relations de bon ordre de BA on associe l'unique ordinal isomorphe à celui-ci : l'image de BA par cette fonctionnelle est un ensemble d'ordinaux, soit hA, par remplacement. Cet ensemble est clairement un segment initial de la classe des ordinaux, donc un ordinal lui-même.
L'ordre strict sur les ordinaux est défini par l'appartenance: hA ne peut donc s'injecter dans A, car il appartiendrait à lui-même, et tous les ordinaux strictement inférieurs à hA s'injectent dans A. On a donc montré :
Proposition (ZF). — Pour tout ensemble A, il existe un unique ordinal hA qui est le plus petit ordinal qui ne s'injecte pas dans A.
Cardinalité
[modifier | modifier le code]Un ordinal qui est inférieur à hA s'injecte dans A, il ne peut donc être en bijection avec hA (qui lui ne s'injecte pas dans A). Un tel ordinal est dit ordinal initial, ou cardinal, car les ordinaux initiaux représentent les cardinaux des ensembles bien ordonnés, c'est-à-dire, en présence de l'axiome du choix, tous les cardinaux.
L'ordinal de Hartogs d'un ordinal initial κ, hκ est l'ordinal initial qui suit κ, le successeur de κ au sens cardinal, parfois noté κ+. Dans le cas des cardinaux infinis (les aleph), si κ = ℵα, son cardinal de Hartogs est κ+ = ℵα+1. En particulier pour ℵ0 le cardinal du dénombrable, on obtient que le cardinal de Hartogs de l'ensemble des entiers est ℵ1, c'est-à-dire que ℵ1 est le cardinal de l'ensemble des ordinaux au plus dénombrables, et même, comme il est facile de l'en déduire, de tous les ordinaux dénombrables (au sens infini dénombrable).
Le théorème de Cantor montre que l'ensemble des parties de A, 2A, tout comme hA, ne s'injecte pas dans A. Mais à la différence de hA, 2A n'est pas forcément bien ordonnable en l'absence de l'axiome du choix.
En présence de l'axiome du choix, tout ce que l'on sait pour les cardinaux infinis c'est que ℵα+1 (ordinal de Hartogs de ℵα) est inférieur ou égal à 2ℵα. Affirmer l'égalité de ces cardinaux revient à affirmer l'hypothèse généralisée du continu.
Le théorème de Hartogs dans la théorie de Zermelo
[modifier | modifier le code]La théorie de Zermelo Z, qui est la théorie des ensembles originale de Zermelo vue comme théorie du premier ordre, est la théorie des ensembles de Zermelo-Fraenkel sans le schéma de remplacement. Elle est strictement plus faible que cette dernière qui montre sa cohérence (on peut montrer l'existence d'un modèle de Z dans ZF). Bien qu'elle ait des défauts du point de vue de la théorie des ensembles, on considère qu'elle est suffisante pour formaliser la plupart des mathématiques classiques[1].
La théorie de Zermelo ne permet pas la construction des ordinaux de von Neumann, plus précisément en l'absence du remplacement on ne peut montrer que tout ensemble bien ordonné est isomorphe à un ordinal de von Neuman. Il est cependant possible d'énoncer un équivalent du théorème de Hartogs, qui devient :
Théorème de Hartogs (Z). — Pour tout ensemble A, il existe un ensemble bien ordonné (HA, ≤) qui ne s'injecte pas dans A, et qui est isomorphe à un segment initial de tout ensemble bien ordonné qui ne s'injecte pas dans A.
La construction est essentiellement la même que ci-dessus, le bon ordre construit est isomorphe à l'ordinal de Hartogs dans la théorie ZF, mais plus longue du fait que l'on développe en quelque sorte une théorie des ordinaux locale à A, par passage au quotient, puisque l'on ne dispose plus des représentants des classes d'isomorphies de bons ordres que sont les ordinaux de von Neumann.
On construit donc de la même façon l'ensemble BA des relations de bon ordre sur un sous-ensemble de A. On quotiente celui-ci par isomorphisme d'ordre. On définit une relation d'ordre strict entre deux bons ordres : le premier est isomorphe à un segment initial propre du second. Après passage au quotient on obtient un bon ordre qui est celui cherché[2].
Quelques applications du théorème de Hartogs
[modifier | modifier le code]Comparabilité cardinale
[modifier | modifier le code]L'existence de l'ordinal de Hartogs, en fait l'existence pour tout ensemble A d'un ensemble bien ordonné qui ne s'injecte pas dans A, permet de déduire immédiatement de la comparabilité cardinale que tout ensemble est bien ordonnable.
En effet, la comparabilité cardinale énonce qu'étant donné deux ensembles A et B, il existe une injection de A dans B ou il existe une injection de B dans A. C'est la totalité de la « relation » de subpotence qui compare les ensembles du point de vue cardinal. On la déduit de l'axiome du choix, par exemple par le théorème de Zermelo, car deux bons ordres sont toujours comparables, l'un étant isomorphe à un segment initial de l'autre ou réciproquement (c'est aussi une conséquence très simple du lemme de Zorn).
Le théorème de Hartogs établit sans l'axiome du choix l'existence, pour tout ensemble A, d'un ensemble bien ordonné qui ne s'injecte pas dans A. On déduit alors de la comparabilité cardinale que A s'injecte dans cet ensemble et donc est lui-même bien ordonné (en transportant l'ordre sur l'image) : la comparabilité cardinale équivaut au théorème de Zermelo, donc à l'axiome du choix, modulo les autres axiomes de la théorie des ensembles.
Produit cardinal
[modifier | modifier le code]Comme déjà vu au précédent paragraphe, il suffit de montrer qu'un ensemble s'injecte dans son ordinal de Hartogs, pour qu'il puisse être bien ordonné. Ceci peut être exploité pour montrer que les deux énoncés suivant sur les cardinaux, qui sont conséquences de l'axiome du choix[3], lui sont en fait équivalents[4].
- Pour tous ensembles infinis A et B, leur réunion, A ∪ B, est équipotente à leur produit cartésien, A × B.
- Tout ensemble infini A est équipotent à son carré cartésien, A × A.
La partie du premier énoncé qui entraîne l'axiome du choix est que A × B s'injecte dans A ∪ B. De ceci on déduit le second, en prenant le carré cartésien de A ∪ B : si (A ∪ B)×(A ∪ B) est équipotent à A ∪ B, alors par restriction il existe une injection de A × B dans A ∪ B.
On montre donc que pour un ensemble infini A, l'existence d'une injection φ de A × hA dans A ∪ hA entraîne que celui-ci est bien ordonné. En effet, comme hA ne s'injecte pas dans A, pour chaque élément a de A, {α ∈ hA |φ(a,α) ∈ hA} est non vide et possède donc un plus petit élément ��a. L'application qui à a associe φ(a,αa) est injective de A dans hA par injectivité de φ, d'où le résultat.
Ces deux énoncés ont pour conséquence que tout ensemble infini peut être bien ordonné, et donc l'axiome du choix (les ensembles finis, c'est-à-dire en bijection avec un entier, étant, par là même, bien ordonnés).
Ce résultat a été démontré par Alfred Tarski en 1924[4],[5].
L'hypothèse généralisée du continu entraîne l'axiome du choix
[modifier | modifier le code]On dira d'un ensemble A qui s'injecte dans un ensemble B que A est subpotent à B. L'hypothèse généralisée du continu énoncée, sous la forme suivante :
- Pour tout ensemble infini A, si un ensemble B est tel que A est subpotent à B et B est subpotent à 2A (c'est-à-dire à l'ensemble des parties de A), alors B est équipotent à A ou B est équipotent à 2A[6]
a pour conséquence l'axiome du choix dans ZF. Ce résultat a été démontré en 1947 par Wacław Sierpiński[7]. La démonstration utilise l'ordinal de Hartogs. En particulier Sierpinski démontre que dans ZF (sans axiome du choix) l'ordinal de Hartogs d'un ensemble A s'injecte dans l'ensemble des parties itéré 3 fois[8] sur A, soit 222A, en faisant correspondre à un ordinal subpotent à A la classe des ensembles de parties de A ordonnée par inclusion de façon isomorphe à cet ordinal[9].
Notes et références
[modifier | modifier le code]- Moschovakis 2006, p. 157 et 166.
- Détails dans Moschovakis 2006, chap 7, voir p. 100.
- Voir le § « Arithmétique cardinale et axiome du choix » de l'article sur les ensembles infinis.
- Voir par exemple Herrlich 2006, chap. 4, p. 54.
- Alfred Tarski, « Sur quelques théorèmes qui équivalent à l’axiome du choix », Fundam. Math., vol. 5, , p. 147-154 (lire en ligne). Tarski a raconté à Gregory Moore l'anecdote suivante. Quand il avait tenté de faire publier son papier dans les comptes rendus de l'académie des sciences, celui-ci lui fut refusé par Henri Lebesgue, qui était opposé à l'axiome du choix, et le renvoya sur Jacques Hadamard. Hadamard le refusa à son tour, expliquant qu'il ne voyait pas l'intérêt de démontrer un axiome qui était vrai (Herrlich 2006, chap. 4, p. 55, qui cite (en) G. H. Moore, Zermelo’s Axiom of Choice, its Origins, Development, and Influence, coll. « Springer Studies in the History of Mathem. and Physic. Sci. » (no 8), , p. 215).
- En présence de l'axiome du choix, ceci équivaut à la forme usuelle : pour tout ordinal α, 2ℵα = ℵα+1.
- Wacław Sierpiński, « L'hypothese généralisée du continu et l'axiome du choix », Fundam. Math., vol. 34, , p. 1-5 (lire en ligne).
- La seule chose utile pour la démonstration est que ce soit itéré un nombre fini de fois.
- Ce n'est qu'un argument de la démonstration. Pour une version de celle-ci légèrement simplifiée voir (en) Paul Cohen, Set Theory and the continuum hypothesis, Benjamin, , annexe, reprise dans (en) Elliott Mendelson (en), Introduction to Mathematical Logic, Van Nostrand, , 2e éd., p. 217.
Bibliographie
[modifier | modifier le code]- (de) Friedrich Moritz Hartogs, « Über das Problem der Wohlordnung », Math. Ann., vol. 76, , p. 438–443 (lire en ligne)
- René Cori et Daniel Lascar, Logique mathématique II. Fonctions récursives, théorème de Gödel, théorie des ensembles, théorie des modèles [détail des éditions], chap. 7L'ordinal de Hartogs, avec pour conséquence l'équivalence de la comparabilité cardinale avec AC, sont traités en exercice.
- (en) Horst Herrlich, Axiom of Choice, Berlin, Springer, , 194 p. (ISBN 978-3-540-30989-5, lire en ligne)
- (en) Yiannis Moschovakis, Notes on Set Theory [détail des éditions]Développement dans la théorie de Zermelo