En mathématiques, Le lemme de Zorn (ou théorème de Zorn, ou parfois lemme de Kuratowski-Zorn), est un théorème de la théorie des ensembles qui affirme que si un ensemble ordonné est tel que toute chaîne (sous-ensemble totalement ordonné) possède un majorant, alors il possède un élément maximal. Le lemme de Zorn est équivalent à l'axiome du choix modulo les axiomes de la théorie des ensembles de Zermelo-Fraenkel.
Le lemme de Zorn permet d'utiliser l'axiome du choix sans recourir à la théorie des ordinaux (ou à celle des bons ordres via le théorème de Zermelo). En effet, sous les hypothèses du lemme de Zorn, on peut obtenir un élément maximal par une définition par récurrence transfinie, la fonction itérée étant obtenue par axiome du choix. Cependant, les constructions par récurrence transfinie sont parfois plus intuitives (quoique plus longues) et plus informatives.
Le lemme de Zorn a des applications aussi bien en topologie, comme le théorème de Tychonov, qu'en analyse fonctionnelle, comme le théorème de Hahn-Banach, ou en algèbre, comme le théorème de Krull ou l'existence d'une clôture algébrique.
Il doit son nom au mathématicien Max Zorn qui, dans un article de 1935, en donnait le premier un large nombre d'applications, en redémontrant des résultats connus d'algèbre. Cependant Kazimierz Kuratowski en avait déjà publié une version en 1922, et plusieurs mathématiciens, à commencer par Felix Hausdorff en 1907, avaient introduit des principes du maximum proches du lemme de Zorn.
Un ensemble ordonné tel que toute chaîne (sous-ensemble totalement ordonné) possède un majorant est souvent appelé ensemble inductif. Le lemme de Zorn devient :
Lemme de Zorn — Tout ensemble inductif admet au moins un élément maximal.
L'ensemble des parties d'un ensemble E muni de l'inclusion est un exemple d'ensemble inductif : E est un majorant de toute chaîne (pour l'inclusion) de parties de E, qui ne présente cependant pas d'intérêt pour le lemme de Zorn, puisque E est également un élément maximal.
Par contre on obtient des applications utiles en choisissant un sous-ensemble adéquat de l'ensemble des parties de E (toujours muni de l'inclusion), qui doit alors être inductif, la réunion des éléments de la chaîne (non vide) peut fournir un candidat pour le majorant.
Prenons le cas de l'ensemble I(E,F) des graphes d'injections partielles de E dans F, où E et F sont deux ensembles quelconques : ce sont les sous-ensembles G de E × F vérifiant :
L'ensemble I(E,F) muni de l'inclusion est un ensemble inductif. En effet ∅ ∈ I(E,F) et majore la chaîne vide. Une chaîne non vide est majorée par la réunion de ses éléments qui est bien le graphe d'une injection partielle car deux couples de la réunion sont nécessairement dans un même élément de la chaîne (puisque celle-ci est totalement ordonnée). On déduit du lemme de Zorn l'existence d'un élément maximal, dont il n'est pas difficile de vérifier qu'il est le graphe d'une injection de E dans F, ou d'une injection de F dans E (cas non exclusifs).
On a donc montré qu'étant donné deux ensembles quelconques, il existait une injection de l'un dans l'autre ou réciproquement : c'est le théorème de comparabilité cardinale.
Les divers énoncés obtenus ci-dessus, équivalents entre eux, sont également équivalents à l'axiome du choix, modulo les autres axiomes de la théorie des ensembles, ceux de Zermelo par exemple. Il serait donc possible de considérer le lemme de Zorn comme un axiome, et l'« axiome du choix » comme un théorème qui serait sa conséquence. Le théorème de Zermelo ou principe du bon ordre, est également un équivalent de l'axiome du choix, qui a été utilisé pour démontrer les premières versions du lemme de Zorn (avant Zorn), et dont les démonstrations directes sont proches de celles de ce dernier.
Cependant, selon une boutade célèbre du mathématicien Jerry Bona, « L'axiome du choix est évidemment vrai,le principe du bon ordre est évidemment faux, et le lemme de Zorn personne n'en sait rien ». Serge Lang ne trouve pas « psychologiquement très satisfaisant » de prendre pour axiome un énoncé tel que le lemme de Zorn. Il s'avère que l'axiome du choix et le théorème de Zermelo sont des conséquences directes du lemme de Zorn, alors que la démonstration du lemme de Zorn ou du théorème de Zermelo par l'axiome du choix demande une construction un peu plus délicate. On peut énoncer d'ailleurs un théorème de point fixe qui ne dépend pas de l'axiome du choix, et qui, avec ce dernier, donne directement le lemme de Zorn.
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 = a0 n'est pas maximal il possède un majorant strict a1, 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 an 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.
Soit (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 possède non seulement au moins un majorant, mais au moins un majorant strict. Soit S la fonction définie sur les chaînes de E, qui à la chaîne C associe l'ensemble S(C) des majorants stricts de C.
Un ensemble inductif est forcément non vide (majorant de la chaîne vide), soit a ∈ E. On définit une fonctionnelle h par induction sur les ordinaux.
(formellement, pour que ce soit bien une définition par récurrence, on peut prolonger S à toutes les parties de E, en associant n'importe quel sous-ensemble de E, par exemple {a}, à toutes les parties non totalement ordonnées par inclusion, par une récurrence sur les ordinaux immédiate {h(α)| α < β} est une chaîne de E pour tout ordinal β, et la définition est donc bien celle indiquée).
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.
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 la construction de Hartogs ne nécessite pas vraiment la théorie des ordinaux de von Neumann (qui elle utilise le remplacement), on obtient un ensemble bien ordonné qui ne s'injecte pas dans X, et le théorème de définition par récurrence sur un ordinal utile se démontre en fait pour n'importe quel bon ordre, et sans remplacement.
On remarque que les chaînes construites par récurrence transfinies 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.
On a distingué trois cas pour la récurrence ordinale, ce qui n'était pas nécessaire ; si on pose g = f o S, la suite ordinale h vérifie pour tout ordinal α (cas où a = f(S(∅))=f(E)) :
dont les éléments forment une chaîne bien ordonnée maximale, au sens où on ne peut plus la prolonger, de l'ensemble ordonné (E, ≤) (on l'a construite dans le cadre d'un raisonnement par l'absurde, sinon la suite s'interrompt à un certain ordinal équipotent à E).
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. Soit (E, ≤) un ensemble ordonné. Soit g une fonction partielle définie sur les chaînes bien ordonnées de (E, ≤) à valeur 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 :
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 — 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.
En effet, 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 ce lemme, on utilise le lemme suivant.
Lemme — 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). Soient donc deux g-chaînes C et D. Soit Σ l'ensemble des segments initiaux de C et de D. Clairement ∅ ∈ Σ. La réunion des éléments de Σ est encore un segment initial de C et de D, soit I.
Pour démontrer le premier lemme, on prend M égal à la réunion de toutes les g-chaînes de E. Du lemme que l'on vient de démontrer, on déduit que toute g-chaîne est un segment initial de M. L'ensemble M (éventuellemennt 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. Si g(M) était définie, M ∪ {g(M)} serait une g-chaîne ce qui est exclu, donc M est bien maximale.
Il est possible également de construire la chaîne bien ordonnée maximale, 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-jaccente) , et convient directement pour le théorème de maximalité de Hausdorff. Elle convient également pour la version « faible » du lemme de Zorn pour les ensembles strictement inductifs (version (1,4) ou (2,4)).
On suppose donc que (E, ≤) est un ensemble non vide strictment 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, 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 suivant, qui est indépendant de l'axiome du choix.
Théorème de point fixe des ensembles ordonnés. — Soit f une fonction d'un ensemble ordonné (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.
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), mais le propos est ici de le démontrer directement. La démonstration 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 :
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 Mx = {y ∈ M | y ≤ x ou f(x) ≤ y} est admissible.
Il existe d'autres variantes du lemme de Zorn, on trouve par exemple dans Bourbaki 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 toute propriété de caractère fini, il existe un sous-ensemble de E maximal pour l'inclusion qui a cette propriété.