Lemme de Zorn

En un sens précisé ci-dessous, un ensemble partiellement ordonné est dit inductif si toute partie « au moins totalement ordonnée » admet un « majorant ou mieux ». Les candidats usuels pour préciser « au moins totalement ordonnée » sont :

1) totalement ordonnée

2) bien ordonné

tandis que ceux pour « majorant ou mieux » sont :

3) majorant

4) borne supérieure

d'où quatre définitions voisines mais distinctes, la moins restrictive correspondant à (2,3) et la plus restrictive à (1,4). Comme l'acception la plus courante correspond au cas du couple (1,3), c'est la définition choisie dans la suite :

Un ensemble inductif est un ensemble partiellement ordonné où toute chaîne (partie totalement ordonnée) admet un majorant.

Pour beaucoup d'applications du lemme de Zorn la définition (1,4), qui est la plus restrictive, s'utilise naturellement, même si elle donne un énoncé en apparence plus faible. C'est le cas par exemple de l'application à la comparabilité cardinale du paragraphe précédent : la réunion des éléments de la chaîne n'est pas seulement un majorant mais une borne supérieure. La notion peut aussi être utile dans d'autres contextes[5]. Un ensemble tel que toute chaîne admet une borne supérieure (choix (1,4)), est d'ailleurs parfois appelé également ensemble inductif[6], mais aussi ensemble strictement inductif[7]. Un ensemble strictement inductif possède nécessairement un plus petit élément, la borne supérieure de la chaîne vide. Une variante est de supposer que l'ensemble est non vide mais que seules les chaînes non vides ont une borne supérieure, c'est-à-dire de ne pas supposer de plus petit élément (qui n'est pas utile pour le lemme)[8].

C'est bien sûr la définition la moins restrictive qui donne le meilleur énoncé du lemme de Zorn. Même si l'énoncé habituel correspond au choix du couple (1,3) dans la définition d'ensemble inductif, le couple (2,3) donne un énoncé (apparemment) plus fort, parfois bien utile.

Le lemme de Zorn peut se particulariser pour la relation d'inclusion sur un ensemble d'ensembles. Un candidat naturel pour le majorant d'une chaîne pour l'inclusion est la réunion des éléments de cette chaîne ; il s'agit alors forcément de la borne supérieure de la chaîne. On obtient ainsi comme conséquence du lemme de Zorn l'énoncé suivant, qui lui est en fait équivalent[9] :

Pour l'application à la comparabilité cardinale (voir ci-dessus), on était déjà dans ce cas particulier (${\displaystyle {\mathcal {A}}}$ est l'ensemble des graphes d'injections partielles de E dans F). C'est en fait un cas particulier de la version (1,4) du lemme de Zorn. On a un énoncé analogue en termes de chaînes bien ordonnées par l'inclusion (cas particulier de la version (2,4)).

Si (E, ≤) est un ensemble ordonné, l'ensemble ${\displaystyle {\mathcal {A}}}$ des chaînes de E (pour l'ordre de E) est lui-même un ensemble ordonné par inclusion. Si ${\displaystyle {\mathcal {C}}}$ est une chaîne de ${\displaystyle {\mathcal {A}}}$ pour l'inclusion, alors il est simple de montrer que la réunion des éléments de ${\displaystyle {\mathcal {C}}}$, qui sont des chaînes de (E, ≤), est encore une chaîne de (E, ≤). On obtient ainsi une version du principe de maximalité de Hausdorff (ou théorème de maximalité de Hausdorff).

Si de plus l'ensemble ordonné est inductif (au sens initial (1,3)), la chaîne maximale en question possède un majorant (en fait : un plus grand élément) qui, par maximalité de la chaîne, est un élément maximal de l'ensemble lui-même. On déduit donc le lemme de Zorn (version (1,3) initiale) du principe de Hausdorff[10]. On a donc démontré l'équivalence des énoncés du lemme de Zorn versions (1,3) et (1,4), du lemme de Zorn pour l'inclusion et du principe de Hausdorff.

On peut également déduire les versions du lemme de Zorn pour les chaînes bien ordonnées (versions (2,3) et (2,4)) du principe de maximalité de Hausdorff. Cependant, pour l'ordre de l'inclusion, une chaîne de chaînes bien ordonnées n'a pas nécessairement de borne supérieure. On les compare par segment initial : Étant donné un ensemble ordonné (E, ≤), on dit, pour deux chaînes bien ordonnées de (E, ≤) C₁ et C₂, que C₁ est un segment initial de C₂ quand :

C₁ ⊂ C₂ et ∀ x ∈ C₁ ∀ y ∈ C₂ (y ≤ x ⇒ y ∈ C₁).

On vérifie facilement que la relation « être un segment initial » est une relation d'ordre sur l'ensemble ${\displaystyle {\mathcal {A}}}$ des chaînes bien ordonnées de E et que, pour cet ordre, toute chaîne a un majorant et même une borne supérieure : sa réunion. L'ensemble ${\displaystyle {\mathcal {A}}}$, muni de l'ordre par segment initial, est donc un ensemble inductif au sens habituel (et même au sens (1,4)).

On peut donc déduire du lemme de Zorn habituel (ou même de sa version (1,4)) que ${\displaystyle {\mathcal {A}}}$ possède un élément maximal C. Si l'on suppose maintenant que (E, ≤) est un ensemble inductif au sens (2,3) (le plus restreint), c'est-à-dire que tout chaîne bien ordonnée de (E, ≤) possède un majorant, on a alors un majorant m pour C. Ce majorant m est nécessairement un élément maximal de E, car, si ce n'était pas le cas, un élément strictement supérieur à m permettrait de prolonger C en une chaîne bien ordonnée, dont C serait alors un segment initial, ce qui contredirait sa maximalité.

On a donc démontré (indépendamment des résultats du paragraphe précédent) que le lemme de Zorn pour la définition d'ensemble inductif (1,4), le plus faible en apparence, a pour conséquence le lemme de Zorn pour la définition d'ensemble inductif (2,3), le plus fort en apparence. Les quatre énoncés sont donc bien équivalents.

• Un énoncé possible de l'axiome du choix est l'existence, pour tout ensemble X d'ensembles non vides, d'une fonction de choix sur X, c'est-à-dire une fonction définie sur X telle que pour tout x de X, f(x) ∈ x. Soit E dont les éléments sont des graphes de fonctions de choix sur une partie de X, c'est-à-dire, parmi les ensembles de couples (x, u) tels que x ∈ X et u ∈ x, ceux qui vérifient : si (x, u) et (x, v) appartiennent à l'ensemble alors u = v. Cet ensemble, muni de l'inclusion, est strictement inductif : la réunion d'une chaîne d'éléments de E est un élément de E (il reste un graphe fonctionnel, du fait que c'est une chaîne). Un élément maximal m de E est nécessairement le graphe d'une fonction définie sur tout X : si elle n'était pas définie en y élément de X donc non vide, on aurait v ∈ y, et m ∪ {(y,v)} contredirait la maximalité de m.
• Pour le théorème de Zermelo, il faut montrer l'existence d'un bon ordre sur un ensemble X quelconque. On peut ordonner l'ensemble E des graphes de relation de bon ordre sur une partie de X par segment initial. L'ensemble E ainsi ordonné est inductif. Un élément maximal est forcément un bon ordre sur tout X, car il est toujours possible de prolonger un bon ordre sur Y en ajoutant un élément « au bout ».

Finalement, l'axiome du choix étant également une conséquence immédiate du théorème de Zermelo, il suffit de déduire le lemme de Zorn de l'axiome du choix, pour obtenir toutes les équivalences annoncées.

On trouve plusieurs démonstrations du lemme de Zorn, qui reposent en gros sur le principe suivant. On construit une chaîne à partir d'un élément quelconque, soit a. Si a = a₀ n'est pas maximal il possède un majorant strict a₁, et ainsi de suite. Le tout est d'arriver à itérer suffisamment le procédé, jusqu'à atteindre un élément maximal. Comme il faudra l'itérer en général une infinité de fois, l'axiome du choix est nécessaire pour choisir un majorant strict. En général une simple définition par récurrence sur les entiers ne suffit pas : il n'y a aucune raison que a_ω, majorant strict de la chaîne des a_n pour n entier, soit maximal. Pour ce cas particulier, un axiome du choix faible, l'axiome du choix dépendant, suffirait. La façon la plus directe de construire cette suite est d'utiliser une définition par récurrence transfinie sur les ordinaux. Cependant, l'intérêt du lemme de Zorn est justement de pouvoir se passer des ordinaux, ce qui est possible également pour sa démonstration, et se fait en construisant directement la suite que l'on obtiendrait par récurrence transfinie, soit par réunion d'« approximations » de celle-ci, soit comme intersection des relations ayant la propriété adéquate.

Soient (E, ≤) un ensemble ordonné inductif et f une fonction de choix sur les parties non vides de E. On suppose de plus, pour aboutir à une contradiction, que (E, ≤) ne possède pas d'élément maximal. On en déduit que toute chaîne C possède non seulement au moins un majorant, mais au moins un majorant strict. Notons g(C) l'image par f de l'ensemble des majorants stricts de C et posons, pour toute partie D de E qui n'est pas une chaîne, g(D) = a, où a est un élément arbitraire fixé de E.

On définit une fonctionnelle h par récurrence sur les ordinaux par :

h(α) = g({h(β)| β < α}).

Par une récurrence sur les ordinaux immédiate, {h(β)| β < α} est une chaîne de E pour tout ordinal α et h(α) est donc un majorant strict de cette chaîne. On a ainsi construit une fonctionnelle strictement croissante de la classe des ordinaux dans l'ensemble ordonné (E, ≤), c'est-à-dire que l'on met en correspondance bijective la classe propre des ordinaux et un sous-ensemble de E : ceci contredit le schéma d'axiomes de remplacement[14].

Dans la démonstration précédente, la fonctionnelle h est construite comme une classe fonctionnelle. Il est possible de développer la même démonstration purement en termes d'ensemble. Il suffit de définir h, qui devient une fonction au sens usuel, par récurrence sur l'ordinal de Hartogs de E, qui est un ordinal qui ne s'injecte pas dans E. Ceci donne justement la contradiction. De plus, cette démonstration peut même alors se développer dans la théorie de Zermelo (sans remplacement). En effet, dans cette théorie, la construction de Hartogs produit un ensemble bien ordonné qui ne s'injecte pas dans X[15], et auquel on peut appliquer le théorème de définition par récurrence sur un bon ordre.

On remarque que les chaînes construites par récurrence transfinie sont bien ordonnées : cette démonstration fonctionne donc en supposant l'existence d'un majorant seulement pour les chaînes bien ordonnées (variante (2,3)). Comme par ailleurs la démonstration de l'axiome du choix n'utilise en fait que le lemme de Zorn pour l'inclusion (cas particulier de la variante (1,4)), on a ainsi une autre démonstration de l'équivalence des variantes du lemme de Zorn.

Les éléments de la suite ordinale h forment une chaîne bien ordonnée maximale de (E, ≤). On l'a construite dans le cadre d'un raisonnement par l'absurde ; sinon, la suite s'interrompt à un certain ordinal équipotent à E, ce qui fournit au passage une preuve directe (à partir de l'axiome du choix) du théorème de Zermelo[16] - [17] qui, à son tour, implique le lemme de Zorn[18].

On donne dans le paragraphe suivant une démonstration qui construit directement cette chaîne bien ordonnée et évite la définition par récurrence.

On se propose de démontrer la version du théorème de Zorn pour les chaînes bien ordonnées (version (2,3)). Cette courte démonstration est une adaptation de celle donnée en 1904 par Ernst Zermelo pour son théorème du bon ordre[19]. Soit (E, ≤) un ensemble ordonné. Soit g une fonction partielle définie sur les chaînes bien ordonnées de (E, ≤) à valeurs dans E, et qui est telle que, si g est définie pour la chaîne bien ordonnée C, g(C) est un majorant strict de C. Pour les besoins de la démonstration, on appelle g-chaîne une chaîne bien ordonnée C telle que, pour tout x de C :

x = g({y ∈ C | y < x}).

En particulier, l'ensemble vide est une g-chaîne, et si C est une g-chaîne telle que g(C) soit définie, alors C ∪ {g(C)} est encore une g-chaîne. On déduit le théorème de Zorn du lemme suivant :

Lemme 1. — Sous les conditions données ci-dessus, il existe une g-chaîne maximale, c'est-à-dire une g-chaîne C telle que g(C) n'est pas définie.

Preuve du lemme de Zorn à partir du lemme 1. Soit (E, ≤) un ensemble ordonné inductif au sens des chaînes bien ordonnées (1,3). Soit S(C) l'ensemble (éventuellement vide) des majorants stricts de la chaîne bien ordonnée C, et f une fonction de choix sur P(E)\{∅}. La fonction g est définie sur les chaînes bien ordonnées C qui possèdent au moins un majorant strict et vaut alors f(S(C)). Elle satisfait les hypothèses du lemme. Soit M une g-chaîne maximale, c'est-à-dire que g(M) n'est pas définie, ou de façon équivalente, M n'a pas de majorant strict. La chaîne bien ordonnée possède par ailleurs un majorant par hypothèse. Si celui-ci n'était pas un élément maximal, la chaîne M aurait des majorants stricts, et g(M) serait définie. Le lemme de Zorn est démontré.

Pour démontrer le lemme 1, on utilise le lemme suivant[20].

Lemme 2. — Sous les conditions données ci-dessus, étant données deux g-chaînes, l'une est segment initial de l'autre.

À noter que les deux cas ne sont pas exclusifs (quand les chaînes sont égales).

Preuve du lemme 2. Soient deux g-chaînes C et D. Soit Σ l'ensemble des segments initiaux à la fois de C et de D. Clairement ∅ ∈ Σ. La réunion des éléments de Σ est encore un segment initial de C ainsi que de D, soit I.

• Si I = C ou I = D, on a la conclusion du lemme.
• Sinon, I est un segment initial de C et de D différent de chacun d'entre eux, qui sont des chaînes bien ordonnées, donc I a un plus petit majorant strict dans C, soit m_C, et un plus petit majorant strict dans D, soit m_D. Comme de plus C et D sont des g-chaînes, m_C = m_D = g(I). Mais alors I ∪ {g(I)} est un segment initial à la fois de C et de D, ce qui contredit la définition de I. Ce cas est donc exclu et le lemme 2 est démontré.

Preuve du lemme 1. Soit M la réunion de toutes les g-chaînes de E. On déduit du lemme 2 que toute g-chaîne est un segment initial de M. L'ensemble M (éventuellement vide sans autre hypothèse sur g) est donc bien ordonné. De plus, si x ∈ M, alors il existe une g-chaîne C telle que x ∈ C, et comme C est un segment initial de M, on a aussi x = g({y ∈ M | y < x}), ce pour tout x de M, donc M est une g-chaîne. Par définition de M, cette g-chaîne est maximale.

Une fois la fonction de choix donnée, le reste de la démonstration, dans chacun des deux cas ci-dessus, se développe sans plus faire appel à l'axiome du choix. En adaptant légèrement l'une ou l'autre démonstration, on fait apparaître un théorème de point fixe indépendant de l'axiome du choix.

Théorème de point fixe des ensembles ordonnés. — Soit f une fonction d'un ensemble strictement inductif (E, ≤) dans lui-même expansive, c'est-à-dire vérifiant x ≤ f(x) pour tout x de E, alors f possède au moins un point fixe, c'est-à-dire un élément m de E vérifiant f(m) = m[21].

Ce théorème se démontre facilement par récurrence ordinale, de manière analogue à la démonstration du lemme de Zorn ci-dessus (mais sans utiliser l'axiome du choix)[22]. Il peut aussi se montrer plus directement en adaptant la démonstration par réunion de chaînes bien ordonnées du paragraphe précédent comme suit[23].

Appelons f-ensemble toute partie C de E bien ordonnée telle que pour tout x de C,

x = sup {f(y) | y ∈ C et y < x}

(en particulier, ∅ est un f-ensemble, et f est croissante sur tout f-ensemble).

On montre de la même façon qu'au paragraphe précédent pour les g-chaînes, que, étant donnés deux f-ensembles C et D, l'un est segment initial de l'autre. On en déduit pour les mêmes raisons, que la réunion M des f-ensembles est un f-ensemble. En particulier M est une chaîne bien ordonnée, et f est croissante sur M. L'image de M par f, {f(y) | y ∈ M} est alors une chaîne (bien ordonnée), donc possède une borne supérieure z. Alors M ∪ {z} est un f-ensemble donc z ∈ M, donc f(z) ≤ z donc f(z) = z.

Cette démonstration n'utilise l'existence de bornes supérieures que pour les chaînes bien ordonnées de E et donc le théorème de point fixe peut s'énoncer avec cette hypothèse seulement (plutôt que celle plus forte que E est strictement inductif)[24].

Le lemme de Zorn version (1,4) (ou même (2,4) avec la remarque précédente)[25] se déduit du théorème de point fixe, par exemple ainsi[26]. On suppose que (E, ≤) est un ensemble strictement inductif, c'est-à-dire que toute chaîne de E possède une borne supérieure. Si (E, ≤) ne possédait pas d'élément maximal alors tout élément possèderait un majorant strict et l'on pourrait, par l'axiome du choix, définir sur E une fonction f vérifiant x < f(x) pour tout x de E. Il suffit donc de montrer qu'une telle fonction ne peut exister, ce qui résulte immédiatement du théorème de point fixe.

Une autre démonstration du lemme de Zorn consiste en construire la chaîne bien ordonnée maximale souhaitée, comme intersection d'ensemble ayant de bonnes propriétés, à savoir stable par passage à la borne supérieure, et par une fonction « successeur » obtenue par axiome du choix. Cette démonstration ne nécessite pas de parler de bon ordre (même si la notion est sous-jacente), et convient directement pour le théorème de maximalité de Hausdorff[27]. Elle convient également pour la version « faible » du lemme de Zorn pour les ensembles strictement inductifs (version (1,4) ou (2,4)).

Plutôt que de démontrer directement le lemme de Zorn, il suffit de démontrer le théorème de point fixe de la section précédente[28], démonstration qui est esquissée ci-dessous.

On distingue e un élément de E (non vide). Pour les besoins de la preuve, on appelle ensemble admissible un sous-ensemble A de E contenant e, clos par application de f et par passage à la borne supérieure pour les chaînes de A, autrement dit :

• e ∈ A
• f(A) ⊂ A
• Si C ⊂ A, et C totalement ordonné, la borne supérieure de C (qui existe dans E car celui-ci est strictement inductif) appartient à A.

L'ensemble E est admissible. On peut donc définir l'intersection M de tous les ensembles admissibles, qui est non vide (e ∈ M) et on montre facilement que c'est encore un ensemble admissible. Si l'on montre que M est totalement ordonné, il possède une borne supérieure, m. Comme M est admissible, m ∈ M et f(m) ∈ M. Donc f(m) = m.

Pour montrer que M est totalement ordonné, il suffit de montrer (sachant que x ≤ f(x) par hypothèse) le lemme suivant.

Lemme. — Pour tout x de M, pour tout y de M, y ≤ x ou f(x) ≤ y.

Pour ce lemme, on montre que M’ = {x ∈ M | ∀ y ∈ M (y ≤ x ou f(x) ≤ y)} est admissible, et l'on utilise le lemme suivant.

Lemme. — Pour tout x de M’, pour tout y de M, y ≤ x ou f(x) ≤ y.

Pour ce dernier lemme on montre que, si x ∈ M’, alors M_x = {y ∈ M | y ≤ x ou f(x) ≤ y} est admissible.

Il existe d'autres variantes du lemme de Zorn[29], on trouve par exemple dans Bourbaki[30] un énoncé utilisant les propriétés de caractère fini, qui sont les propriétés qui sont satisfaites pour l'ensemble vide et par un ensemble non vide donné si et seulement si elles sont satisfaites pour tout sous-ensemble fini de celui-ci. Une relation d'ordre étant donnée sur un ensemble E, la propriété d'être totalement ordonné par cette relation est de caractère fini. Un énoncé du lemme de Zorn (qui généralise l'énoncé usuel) est que sur tout ensemble E, et pour toute propriété de caractère fini, il existe un sous-ensemble de E maximal pour l'inclusion qui a cette propriété.

L'algèbre est historiquement le premier domaine des mathématiques, hors la théorie des ensembles, où l'axiome du choix a été largement utilisé, malgré les controverses suscitées lors de sa publication par Zermelo en 1904[43]. Beaucoup d'applications de l'axiome du choix en algèbre sont liées à des résultats de maximalité, ce que réalisa Zorn au milieu des années 1930. Les quelques applications à l'algèbre qui suivent sont déjà mentionnées par Zorn dans son article (à quelques variations près), et étaient démontrées avant Zorn par le théorème de Zermelo.

• Le théorème de la base incomplète, en particulier l'existence de bases pour tout espace vectoriel, se démontre facilement par le lemme de Zorn. Une base est un système de vecteurs libre maximal, et il suffit donc de remarquer que la réunion d'une famille croissante pour l'inclusion de systèmes libres est encore un système libre pour pouvoir appliquer le lemme de Zorn. Une conséquence de ce théorème est que dans tout corps commutatif K extension de k, il existe une base d'éléments de K au-dessus de k[44]. Georg Hamel avait démontré ce théorème en 1905 dans le cas particulier du corps des réels comme extension du corps des rationnels (et donc comme espace vectoriel sur les rationnels), mais sa démonstration (par le théorème de Zermelo) est générale.
• Le théorème de Krull (1929) est un autre exemple d'application très directe à l'algèbre que donne Zorn de son « principe du maximum ». Il s'agit de montrer que dans un anneau unitaire, tout idéal à gauche est inclus dans un idéal maximal (maximal au sens de l'inclusion parmi les idéaux à gauche différents de l'anneau tout entier), et il suffit de montrer qu'une réunion croissante d'idéaux est un idéal.
• L'existence, dans toute extension transcendante K d'un corps k, d'une base de transcendance (système maximal d'éléments transcendants algébriquement indépendants) de K au-dessus de k est une autre conséquence de l'axiome du choix (due à Ernst Steinitz en 1910) qui se démontre simplement par le lemme de Zorn.
• L'existence pour tout corps d'une clôture algébrique, et son unicité à isomorphisme près, résultats également dus à Steinitz en 1910, se démontrent aussi tous deux par le lemme de Zorn, comme celui-ci le montre dans son article[45].
• L'existence pour tout corps ordonné k de la clôture réelle de k, c'est-à-dire d'un corps réel clos maximal, extension de k et sous-corps de la clôture algébrique de k (résultat dû à Emil Artin et Otto Schreier en 1927[46]) est encore une conséquence directe du lemme de Zorn.
• Le théorème d'extension de Szpilrajn[47], selon lequel tout ordre partiel ≤ sur un ensemble E est prolongeable en un ordre total sur E, appelé une extension linéaire de ≤.

• Théorème de Hahn-Banach
• Théorème de Tychonov (équivalent à l'axiome du choix et donc au lemme de Zorn)

Quelques résultats de théorie des ensembles apparaissent naturellement comme des résultats de maximalité et se démontrent facilement par le lemme de Zorn. C'est le cas:

• du théorème de Zermelo (tout ensemble peut être bien ordonné) ;
• du théorème de comparabilité cardinale (étant donné deux ensembles A et B il existe une injection de A dans B ou une injection de B dans A) ;

tous deux sont équivalents à l'axiome du choix, et donc au lemme de Zorn.