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

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 B_A 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 B_A on associe l'unique ordinal isomorphe à celui-ci : l'image de B_A par cette fonctionnelle est un ensemble d'ordinaux, soit h_A, 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: h_A ne peut donc s'injecter dans A, car il appartiendrait à lui-même, et tous les ordinaux strictement inférieurs à h_A s'injectent dans A. On a donc montré :

Proposition (ZF). — Pour tout ensemble A, il existe un unique ordinal h_A qui est le plus petit ordinal qui ne s'injecte pas dans A.

Cardinalité

Un ordinal qui est inférieur à h_A s'injecte dans A, il ne peut donc être en bijection avec h_A (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 ℵ₀ le cardinal du dénombrable, on obtient que le cardinal de Hartogs de l'ensemble des entiers est ℵ₁, c'est-à-dire que ℵ₁ 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, 2^A, tout comme h_A, ne s'injecte pas dans A. Mais à la différence de h_A, 2^A 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

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.

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é (H_A, ≤) 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 B_A 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é.

Quelques applications du théorème de Hartogs

Comparabilité cardinale

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

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, lui sont en fait équivalents.

• 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 × h_A dans A ∪ h_A entraîne que celui-ci est bien ordonné. En effet, comme h_A ne s'injecte pas dans A, pour chaque élément a de A, {α ∈ h_A |φ(a,α) ∈ h_A} 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 h_A 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.

L'hypothèse généralisée du continu entraîne l'axiome du choix

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 à 2^A (c'est-à-dire à l'ensemble des parties de A), alors B est équipotent à A ou B est équipotent à 2^A

a pour conséquence l'axiome du choix dans ZF. Ce résultat a été démontré en 1947 par Wacław Sierpiński. 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 sur A, soit 2^22A, 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.

Bibliographie

• (de) Friedrich Moritz Hartogs, « Über das Problem der Wohlordnung », Math. Ann., vol. 76,‎ 1915, 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. 7
  L'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, 2006, 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