Thread by @maxime_ramzi

Du coup, premier thread sur l'un des perdants du concours de @SimonBillouet . Comme je l'ai dit il y en a beaucoup dont je voulais parler - parmi ceux qui ont été mentionnés dans les réponses à mon tweet, je ne me sens pas forcément qualifié pour parler de Church-Rosser, parce

que je connais pas grand chose aux questions de réécriture ou de confluence, donc ce serait plus quelque chose sur le lambda-calcul (j'ai essentiellement jamais travaillé sur les détails techniques d'implémentation en logique, ce que ce théorème me semble être - j'espère que des

logicien-ne-s pourront me raconter autre chose s'il y a autre chose). Autrement, on a mentionné Zorn et le théorème d'inversion locale. Je commence par Zorn parce que je préfère et que je me sens plus à l'aise aussi (je verrai si je fais l'inversion locale 😁)

C'est parti !😃 première anecdote, sur le nom: on raconte que Zorn en dira "Ce n'est pas un lemme, et il n'est pas de moi" - en effet il a en premier été démontré par Kuratowski, mais Zorn l'a utilisé dans un article et l'a simplement redémontré (c'est une pratique courante,

"for the reader's convenience") donc je milite pour qu'on l'appelle "théorème de Kuratowski", ou si on veut quand même se faire comprendre, "Kuratowski-Zorn".
Bref, ceci étant dit, qu'est-ce qu'il dit ce théorème ?

"Soit E un ensemble ordonné inductif. Alors E a un élément maximal". Bon, pas très compréhensible... "ensemble ordonné" est relativement clair, c'est un ensemble E muni d'une relation d'ordre < (pas forcément totale ! autrement dit on peut n'avoir ni x < y, ni y < x, ni y = x)

Un élément maximal, c'est aussi relativement clair, à condition de ne pas confondre avec "maximum". Un élément maximal c'est un élément qui n'est strictement plus petit que personne (alors qu'un maximum c'est quelqu'un qui est plus grand que tout le monde !)

Il reste à voir ce fameux mot, "inductif". Bizarrement, ce n'est pas aussi compliqué que ce à quoi on pourrait s'attendre : un ensemble ordonné E est inductif lorsque toute chaîne C a un majorant dans E. Une chaîne c'est un sous-ensemble de E qui est totalement ordonné

c'est-à-dire tel que deux éléments de C sont toujours comparables. Un majorant c'est un élément de E qui est plus grand que tout élément de C. Maintenant on va pouvoir reformuler le théorème et voir pourquoi il est en fait tout à fait intuitif !

Il dit : "si dès que j'ai une chaîne, je peux rajouter un bonhomme en haut de la chaîne, alors je peux trouver un élément maximal". Comment, alors, voir qu'il est intuitif ?
Bah, je prends la chaîne vide, ça me dit que E est non vide puisqu'il doit avoir un majorant de cette

dernière (n'importe quel élément est un majorant de la chaîne vide, encore une instance de "negative thinking" comme j'en ai parlé récemment). Je pars donc de ce x quelconque, je l'appelle x_0. Ou bien il est maximal, auquel cas j'ai gagné; ou bien il y a quelqu'un de plus grand

(par définition): j'ai un x_1 tel que x_0 < x_1. Même débat avec x_1, ou bien j'ai gagné, ou bien j'ai un x_2. Je répète, une infinité de fois tant que je peux. ça me donne.... une chaîne ! les x_i sont deux à deux comparables par construction. J'en déduis un x_infini > x_n pour

tout n (que je vais plutôt noter x_omega 😇)

Maintenant, rebelote ! ou bien j'ai gagné avec x_omega, ou bien je peux trouver un x_{omega +1} qui est strictement plus grand, et je recommence.

Maintenant la théorie des ordinaux va intervenir (de l'intérêt d'utiliser omega et pas "infini") et me permettre de continuer ce

processus tant que je suis pas tombé sur un élément maximal : pour passer de alpha à alpha+1 je prends juste quelqu'un de plus grand, et pour gérer les étapes "limites" (comme le passage de n à omega), j'utilise on hypothèse d'avoir des majorants. Finalement, on assène

le coup final : un ensemble ne peut pas être assez gros pour contenir tous les ordinaux, donc ce processus *doit* s'arrêter à un certain stade. Potentiellement loin loin après omega, c'est pour ça qu'il "faut" des ordinaux, mais ça s'arrête un jour.
Je dis rapidement

ce que sont les ordinaux : ce sont des généralisations des entiers naturels, dans leur vocation à ordonner (un entier naturel ça a deux vocations: compter ("il y a 56 pommes") et ordonner ("c'est la 43è fois que vous suggérez un confinement")). ça commence comme les entiers :

0 < 1 < 2 <... , après lesquels on rajoute omega, le "premier ordinal infini", puis on continue : omega +1 < omega +2 < omega +3 < ... < omega + omega < etc. Seulement, ça va beaucoup plus loin. Pour construire quelque chose sur les ordinaux, il faut gérer les passages de alpha à

alpha +1 (comme pour les entiers naturels), mais aussi les passages dits "limite" comme le passage des entiers n à omega (omega n'est pas n+1). C'est ce que j'ai fait plus haut.
Bon, maintenant le lemme de Zorn devrait être plus intuitif, et paraître "presque" évident

("Evidemment, en rajoutant et rajoutant des choses, 'un jour' on ne peut plus continuer, E n'a pas assez d'éléments !"). Alors pourquoi tout ce bazar autour de lui ?
Bah, dans ma preuve j'ai triché 😁 Alors, sachez que j'ai triché à très peu d'endroits, c'est presque une preuve

totalement valable. En fait, c'en est une, si on accepte l'axiome du choix (le fameux !). Pourquoi ? où s'est glissé cet axiome ?
Eh bien, à deux endroits : si je fixe un x, qui n'est pas maximal, *il existe* un y tel que x < y. Mais là, dans ma preuve, je fais ce choix

beaucoup trop de fois (une fois pour chaque ordinal avant l'épuisement), et l'axiome du choix est là pour affirmer que je peux faire ce choix global (je répète un truc: pour un x fixé qui n'est pas maximal, je n'ai pas besoin d'AC pour affirmer l'existence d'un y tel que x < y.

C'est pour "systématiser" la procédure, en faire une fonction, que j'ai besoin d'AC - et j'ai besoin de cette systématisation pour que ma procédure soit bien définie)Le deuxième endroit est similaire, c'est pour choisir mes majorants de mes chaînes. A nouveau, étant donnée une

chaîne, l'existence d'un majorant est donnée par hypothèse - c'est pour définir une fonction qui à une chaîne associe un majorant que j'ai besoin d'AC et j'ai besoin de cette fonction pour rendre la preuve rigoureuse.
En fait, on peut démontrer AC à partir du lemme de Zorn, et

(ce sont des résultats dus à Gödel et Cohen - ça aura valu la médaille Fields au second) AC n'est ni démontrable, ni réfutable à partir du reste des axiomes des maths (si tant est que le reste des maths est cohérent).
On peut conclure qu'on peut choisir (sans mauvais jeu de

mots) si on accepte AC (et donc Zorn) ou pas, quand on fait des maths. Bon, en réalité le mieux c'est d'accepter les deux possibilités et de travailler avec l'un et l'autre quand c'est pertinent.
Mais pourquoi donc n'accepterait-on pas tout simplement AC , si on peut le faire

sans danger pour la cohérence des maths, et si en plus il est si intuitif ? (admettez quand même que la partie la moins intuitive de la preuve, c'est les ordinaux, pas les choix ! et pourtant la partie sur les ordinaux fonctionne *complètement sans AC*. C'est-à-dire qu'on peut

donner un énoncé "dans ZF" du lemme de Zorn si on dit que notre ensemble E a les fonctions de choix nécessaires)
Bah il est extrêmement intuitif, mais il a des conséquences contre-intuitives qui gênent beaucoup de monde. Il y a par exemple un théorème, dû à Zermelo, qui dit que

tout ensemble admet un bon ordre - je ne rentrerai pas dans ce que ça signifie, mais une des blagues à ce sujet c'est : "l'axiome du choix est évidemment vrai, le théorème de Zermelo évidemment faux, et le lemme de Zorn, qui sait ?" (alors que les trois résultats sont

équivalents dans ZF)
Une de ces conséquences c'est le paradoxe de Banach-Tarski. Bon je n'aime pas cet argument anti-choix, parce que la quasi-totalité de Banach-Tarski (et de son caractère paradoxal) se fait sans AC - c'est juste pour avoir un énoncé drôle et facilement

vulgarisable qu'on utilise AC. Je me souviens avoir vu la preuve pour la première fois en L3 et à un moment on arrivait à un "paradoxe" et je me suis dit "mais on n'a pas encore utilisé AC là" - j'invite donc tout le monde qui n'aime pas AC à cause de Banach-Tarski à relire les

preuves de ce paradoxe (il y a d'autres, meilleures raisons de ne pas être fan d'AC)
Mais ne nous focalisons pas là-dessus, regardons plutôt pourquoi le lemme de Zorn est intéressant ! Quelles sont ses applications ? (parce que bon, tout ce raffut pour un lemme sur des ensembles

ordonnés...)
En fait, très souvent, on utilise ce lemme sur des ensembles ordonnés de structures, ordonnés par l'inclusion, et on cherche une structure très grosse.
Par exemple, il implique que tout anneau non nul admet un idéal maximal - je vous fais la preuve,

c'est l'exemple typique d'application du lemme de Zorn (elles se ressemblent tellement toutes qu'on lira souvent "par une application standard du lemme de Zorn, blabla" sans détails !). Soit R un anneau, et soit E l'ensemble des idéaux propres de R, i.e. ne contenant pas 1;

ordonné par l'inclusion. E est non vide, car (0) est un idéal propre (hypothèse que R est non nul). Maintenant, soit C une chaîne de E, c'est-à-dire un ensemble d'idéaux propres totalement ordonné pour l'inclusion. Alors l'union des éléments de C est un idéal (exercice),

et il est propre: si 1 était dedans, il serait dans un des éléments de C qui constituent l'union, absurde. Donc E admet un élément maximal. C'est, par définition, un idéal maximal.

On montre de manière analogue l'existence d'une base pour tout espace vectoriel (pas uniquement

en dimension finie ! c'est un aspect surprenant d'AC : l'espace vectoriel des fonctions continues R-> R a une base !!)

Une autre application, toujours analogue mais un poil plus subtile parce que ce n'est pas "que" du Zornage standard, c'est la chose suivante :

étant donnés deux ensembles *quelconques* I et J, il existe une injection de I dans J, ou une injection de J dans I. Autrement dit, deux ensembles sont toujours comparables en cardinal ! Peu importe à quel point ils sont infinis.
En fait, plus généralement, avec AC,

toute l'"arithmétique cardinale" est énormément simplifiée et la théorie des cardinaux est vraiment puissante (bon, ça reste assez bizarre, et ça reste un domaine des maths actifs, donc beaucoup de choses à y découvrir).

La chose remarquable dans le lemme de Zorn c'est son

caractère ensembliste mais son application à peu près partout en algèbre (existence d'idéaux maximaux, d'idéaux premiers vérifiant des conditions particulières, de bases, etc.), en topologie (théorème de Tychonoff par exemple), mais aussi en analyse (théorème de Hahn-Banach pour

n'en citer qu'un). Et comme c'est un résultat ensembliste mais relativement élémentaire dans son énoncé, il a pu être utilisé à profit vraiment par tout le monde.
C'est pour ça qu'il est si connu, et c'est pour ses conséquences que le "débat" autour se cristallise un peu

Bon, je crois que je vais m'arrêter là - si vous avez (pas trop 😁😁) des questions additionnelles, je peux essayer d'y répondre.