Zermelo coton ?

Soient $A,B$ des ensembles et $T$ l'ensemble des quadruplets $((A',f),(B',g))$ où $f,g$ sont des bijections réciproques entre $A'$ et $B'$ ($f:A'\to B'$ et $g:B' \to A'$), $A'\subseteq A$ et $B'\subseteq B$.
On ordonne $T$ par $((A_1,f_1),(B_1,g_1)) \leq ((A_2,f_2),(B_2,g_2))$ si $A_1\subseteq A_2$, $B_1\subseteq B_2$, $f_2|_{A_1}=f_1$ et $g_2|_{B_1}=g_1$.
Alors $(T,\leq)$ satisfait les hypothèses du lemme de Zorn. De plus $((A_m,f_m),(B_m,g_m))$ ne peut être maximal pour $\leq$ que si $A_m=A$ ou $B_m=B$ (sinon on prend un élément dans chacun des complémentaires de ces parties et on prolonge les applications) ce qui entraîne le résultat.

@ev, j'en ai souvent palé sur le forum :-D

Soit $E$ un ensemble (disons non vide) d'ensembles. Soit $L$ un ensemble de fonctions choix sur $E$.

On dira qu'il est bleu quand les éléments de $L$ sont deux à deux disjoints.

Soit $L$ maximal (pour l'inclusion, ici Zorn s'applique trivialement).

Il y a un $A\in E$ tel que $\forall x\in A\exists ! f_x\in L: f(A)=x$ (sinon $L$ ne serait pas maximal.

Soit $B\in E$. L'application $x\in A\mapsto f_x(B)$ injecte $A$ dans $B$.

Tu viens de gagner qu'il y a un cardinal minimum dans un $E$ quelconque non vide (bon ordre et pas seulement ordre total).

ev : à tout hasard, une description moins formelle de l'argument, mais qui peut être rendue précise à coup d'induction transfinie (la présentation de Foys on dirait que c'est compliqué parce que ça utilise "la boîte noire" Zorn, mais ça cache que c'est facile comme argument).

Bon déjà si l'un des deux est vide on a gagné. Sinon, je prends un $x$ dans $A$ et je lui associe un $y\in B$. Je prends un deuxième $x_1\in A$ et je lui associe un $y_1\in B$. Tant que je peux, je continue. Si je peux plus, c'est ou bien que j'ai plus personne dans $A$, ou bien plus personne dans $B$. Dans les deux cas, je me suis trouvé une injection.

A l'infini, je recolle tous mes choix; et je continue, à nouveau tant que je peux. A l'infini, je recolle encore. Et ainsi de suite.

L'argument de Foys sur la classe des ordinaux est le fait de dire que ce processus s'arrête à un moment parce que sinon $A$ (et $B$) auraient trop d'éléments.

Donc il y a deux ingrédients: l'axiome du choix, pour garantir que je peux choisir mes $x_i \in A$ et mes $y_i\in B$ sous prétexte que je n'ai pas d'obstruction (je le fais une infinité de fois); et une version du schéma de remplacement, pour garantir que le processus s'arrête.

je ne te mens pas quand je te dis que cette preuve peut être rendue formelle.

@ev : bonsoir. Voici un texte issu du livre d'Analyse I de Laurent Schwartz où l'on pourra s'attarder sur le 1° uniquement. Dans la démonstration, l'on y retrouve les mêmes ingrédients déjà évoqués, sous une forme plus simple.

De mon téléphone @ev: tu voulais éviter Zorn? Je demande ça parce que je t'ai posté comment le BON ORDRE (et pas seulement total) est conséquence évidente de Zorn et tu as pas eu l'air de noter.

A noter qu'il existe aucune preuve connue qui permette de qualifier AC => Zorn de trivial. Mais il faut dire que ça n'a pas bcp été cherché.

@ev : "Depuis un premier cours d'analyse où le prof nous a asséné la révélation avec la délicatesse de tonton René passant les chipolatas au lance-flamme."
Tu pourrais nous en dire un peu plus sur ce fameux Tonton René ?

Plus sérieusement : avec un peu d'habitude, les zornifications, on les voit arriver de loin. Exemple : tout idéal est inclus dans un idéal maximal, tout filtre admet un ultrafiltre plus fin que lui, le théorème de la base incomplète dans le cas général etc. Et en général les preuves avec Zorn "tombent sous le sens". Comme dit Christophe, le seul truc non trivial c'est de prouver que AC implique Zorn.

Aucun rapport, mais il y a un truc qui m'a toujours sidéré c'est la preuve du lemme de rigidité du bon ordre, celui qui dit que si $(A,R)$ et $(B,S)$ sont deux ensembles bien ordonnés, alors soit l'un est isomorphe à un segment initial de l'autre, soit ils sont isomorphes. (C'est ce qu'on appelle aussi la trichotomie).
Ce qui est sidérant dans cette preuve c'est qu'elle ressemble à s'y méprendre à une zornification. Et pourtant (Thanks God !), il n'y a pas une molécule d'axiome du choix derrière tout ça...

Martial : ça ressemble à une Zornification parce que les Zornifications ce sont exactement des récurrences le long de bons ordres, c'est juste qu'on les a cachées derrière Tonton Zorn (d'ailleurs si tu lis les vieux algébristes, tu verras que beaucoup font des preuves par récurrence qu'on ferait aujourd'hui par Zorn...)

Je ne vois pas de quel « répertoire » il s'agit. Ici c’était juste pour expliquer le jeu de mots du titre du fil, qui a pu échapper aux plus jeunes : Colette Magny (1926-1997) https://fr.wikipedia.org/wiki/Colette_Magny
Elle était plutôt de gauche, mais la question n'est pas là quand il s'agit de beauté.
Le rap n'existait pas encore, il y avait une mélodie harmonieuse et des paroles qui avaient un sens.

Colette Magny a écrit:

À droite, je ne suis pas attaquée, je suis ennemie. Sauf quelques bourgeois libéraux qui disent : « Bon, on l'engage quand même, parce que... elle a une belle voix. Elle chante des conneries mais enfin, on l'engage quand même. »

Source.

Qu'appelle-tu hors ordinaux?
Est-ce que l'argument suivant par exemple est "hors ordinaux"

On suppose que $E$ n'a pas d'élément max et que toute chaine est majorée. On veut une contradiction. Pour toute chaine , si elle n'est majorée que par un de ses éléments il y a contradiction. Donc on lui choisit à l'aide de la fonction de choix un majorant strict et ça donne une "chaine successeur". On complète la d'ordre sur les chaînes engendrée par successeur comme suit : on convient que l'union d' une chaine (pour cette relation d'ordre) de chaine (dans E) "domine"*** chaque chaine de la chaine et on considère l'enselble des majorants d'une chaine donnée pour la relation d'ordre engendrée par successeur et domination. Cet ensemble est une chaîne et cette chaîne n'a pas de majorant. Contradiction.

[EDIT*** : pour qu'une chaîne domine une chaine de chaine on demande que la "chaine de chaine" dominee soit égale à la chaine des successeurs de chaque chaine (au premier terme près évidemment. )]



La notion de (ordre engendré par le ) successeur puis celle de (ordre endré par la ) limite sont clairement liées aux ordinaux mais on a eu besoin que d'une fonction de choix sur E... apres certains passages demandent des petites discussions dont la résolution semble couler de l'idée qui elle-même correspond à l'intuition... donc on peut la qualifier de triviale , en tout cas de naturelle, mais pour toi "hors ordinaux" elimine ce genre de preuve ?

@Namiswan : " je souffre en la lisant".

Tu n'es pas le seul.
D'après wikipédia le lemme de Zorn sous sa forme actuelle remonte à 1933.
S'il en existait une preuve triviale à partir de AC (comme celle de LMPC), je pense que statistiquement elle aurait déjà été trouvée.

Bon, tout cela est bancal et n'engage que moi.

Merci Thierry,

Je pense que cette preuve correspond à celle que nous avait donnée Sabbagh en M2 en 2003.

Je tente une rédaction que j'espère digeste de AC=>Zorn suivant cette idée heuristique évoquée: "partant de rien je rajoute successivement un majorant strict jusqu'à que ce que contradiction s'ensuive.

Soit $E$ un ensemble ordonné, et soit $\mathcal{A}$ l'ensemble des parties totalement ordonnées. AC=>Zorn revient à montrer qu'il n'existe pas d'application $M:\mathcal{A}\rightarrow E$ telle que pour tout $A\in\mathcal{A}$, $M(A)$ est majorant strict de $A$. Supposons donné une telle fonction $M$.

Def 1: Soit $A,B\in \mathcal{A}$. On dit que $B$ est un début de $A$ si:
i) $B\subset A$
ii)$B$ est majoré par (tout élément de) $A\backslash B$. (autrement dit: $\forall x \in A,\forall y \in B, x\leq y\ \Rightarrow x\in B$)
On dit que $B$ est début strict de $A$ si de plus $B\not=A$.

Prop 1: Soit $A\in\mathcal{A}$ et soit $B$, $C$ deux débuts de $A$. Alors $B$ est un début de $C$ ou $C$ est un début de $B$.

Preuve: $B$ est majoré strictement par $C\backslash B$, et $C$ est majoré strictement par $B\backslash C$. En particulier les ensembles $B\backslash C$ et $C\backslash B$ se majorent strictement l'un l'autre. L'un des deux est donc vide et on conclut.

Def 2: Soit $A\in \mathcal{A}$. On dit que $A$ est $M$-ordonné si pour tout $B$ début strict de $A$:
i)$M(B)\in A$
ii)$M(B)$ minore $A\backslash B$
(autrement dit, $M(B)$ est le plus petit élément de $A\backslash B$).

Lemme 1: Soit $A$ un ensemble $M$-ordonné et soit $B$ un début strict de $A$. alors $B'=B\cup\{M(B)\}$ est un début de $A$.

Preuve'une part, $B\subset A$ et $M(B)\in A$ par définitions donc $B'\subset A$. D'autre part $A\backslash B'$ majore $B$ et $M(B)$ par définitions donc $A\backslash B'$ majore $B'$.

Prop 2: Soient $A$, $B$ deux ensembles $M$-ordonnés. Alors $A$ est début de $B$ ou $B$ est début de $A$.

Preuve: Soit $C$ le plus grand début commun à $A$ et $B$, que l'on peut définir au choix comme l'union de tous les débuts communs ou bien directement par $C=\{x\in A\cap B, x \mbox{ minore } A\backslash B \mbox{ et } B\backslash A\}$.
Si $C\not=A,B$, alors par la proposition 1, $C\cup \{M(C)\}$ est un début commun à $A$ et $B$ contenant strictement $C$, contradiction. Donc $C=A$ ou $C=B$ et on conclut.

Prop 3: Une union d'ensembles $M$-ordonnés est $M$-ordonné.

Preuve: Soit $A=\bigcup_i A_i$ avec $A_i$ ensemble $M$-ordonné.
Premièrement, par la proposition 2, $A$ est union totalement ordonnée des $A_i$ (pour l'inclusion), donc $A\in\mathcal{A}$.
Deuxièmement, toujours par la proposition 2, tout ensemble $A_i$ est début de $A_j$ si $A_j\not\subset A_i$, et $A_j$ étant arbitraire, tout ensemble $A_i$ est donc début de $A$.
Soit maintenant $B$ un début strict de $A$. Alors, pour tout $A_i$, les ensembles $B$ et $A_i$ sont des débuts communs de $A$, donc par la propostion 1, $B$ est début de $A_i$ ou $A_i$ est début de $B$.
En particulier, pour tout ensemble $A_i$ non inclus dans $B$, $B$ est début strict de $A_i$, et $A_i$ étant $M$-ordonné, $M(B)\in A_i$ et $M(B)$ minore $A_i\backslash B$. Puisque $A_i$ est arbitraire, on conclut que $M(B)\in A$ et $M(B)$ minore $A\backslash B$. $A$ est donc $M$-ordonné.

Prop 4: Si $A$ est $M$-ordonné, alors $A'=A\cup \{M(A)\}$ est $M$-ordonné.

Preuve: Soit $B$ un début strict de $A'=A\cup \{M(A)\}$. Puisque $M(A)$ est le plus grand élément de $A'$, nécessairement $B\subset A$. Alors:
- soit $B=A$ et il est trivial que $M(B)$ est dans $A'$ et minore $A'\backslash B$
- soit $B\not=A$ et donc $B$ début strict de $A$, et en utilisant que $A$ est $M$-ordonné il est de nouveau facile que $M(B)$ est dans $A'$ et minore $A'\backslash B$.

Conclusion: Par la proposition 3, il existe un plus grand ensemble $M$-ordonné, à savoir la réunion de tous. Par la propostion 4, il n'existe pas de plus grand ensemble $M$-ordonné. Contradiction.

Pour être tout à fait précis, vu que j'ai dit "il n'existe pas de preuve connue digérable et courte sans les ordinaux" ,la preuve bien rédigée de Namiswan qui a aussi été une bonne dizaine de fois en 10ans rappelée par foys (en sautant moins de lignes :-D ) est en fait LA preuve qui fait des ordinaux ce qu'ils sont ensuite en pratique.

Mais, je me dois de dire qu'il n'est pas interdit de construire les ordinaux (le fait que sans il se passe ceci, n'est pas une "galère obligatoire").

Comme je l'ai souvent dit, la définition qui me parait la plus rapidement tout donner en assez peu de lignes est de dire que le mot

"ordinal" signifie

"en semble $X$ tel que $X=T(X) \setminus \{X\}$, où $T(X)$ désigne l'ensemble des parties $Y$ de $X$ telles que $Y\subset P(Y)$.

Evidemment "in fine", on aura THE bon ordre qui sert de colonne vertébrale à l'univers. Mais "ce n'est pas grave". Zorn se déduit alors en 3 lignes, via, pour tout ordinal $\alpha $ prendre $u_\alpha$ majorant, si possible strict, de $\{u_\beta\mid \beta<\alpha\}$ et remarquer que l'un des $u_\alpha$ sera maximal.

Quand on n'a pas les ordinaux, l'ensemble des ordres $R$ partiels inclus dans $E$ telles que $\forall x\in E: x=$ un majorant, si possible strict, de $\{y\in E\mid yRx\}$ (ou $x$ n'est comparable à personne) est un bon ordre pour l'inclusion et ça va donner ce qu'on attendait sans en apparence utiliser les ordinaux (c'est la preuve de Namiswan ci-dessus). Mais en fait, c'est "profondément" les ordinaux qui sont implicites dans cette histoire tout de même.

A noter, cependant, que cela prouve que Zorn se prouve en n'utilisant QUE $P(P(E))$ et non pas la "marque commerciale ZF" qui repose sur le schéma de remplacement.

Non, c'est plus compliqué que ça.

Je rappelle ou signale aussi que si $E$ est bien ordonné avec un ordre $\leq_2$ (en plus de son ordre zornique $\leq_1$), pas besoin de "se fatiguer" pour avoir Zorn. On colorie en vert ou rouge comme suit:

Pour chaque $x: x$ est vert s'il est comparable (au sens de $\leq_1$) aux éléments strictement plus petits (au sens de $\leq_2$) que lui.

A la fin l'ensemble des éléments verts est totalement ordonné pour $\leq_1$ et son majorant est un élément maximal de $(E,\leq_1)$.

Dans mon tweet initial, par "problème ouvert" (je ne me rappelle pas si j'ai utilisé cette expression), j'entendais "recherche d'une preuve courte de AC=>Zorn qui soit fondamentalement différente de celles qu'on voit habituellement" (et c'est évidemment un appel très vague). Par exemple, a priori la preuve que j'ai donné en tout début de fil en quelques lignes que Zorn=> les cardinaux sont bien ordonnés est (peut-être que je me trompe) relativement inédite.

Je l'avais cherchée et finalement trouvée avec cette même démarche de vérifier si passer par les ordinaux ou des arguments qui les reconstruisent tacitement étaient nécessaires et avec elle trouvé finalement que non.

Ce sont évidemment des activités non rémunératrices, d'une part "trouver d'autres preuves" l'est peu en recherche scientifique (à tort!!!), mais en plus en TDE :-D ... Mais heureusement, on est tous vieux, payés, et pas à la recherche de complément de revenus :-D

Oui dans le livre Théorie des ensembles de Jean-Louis Krivine aux éditions Cassini une démonstration du théorème d'équipotence est donnée en exercice dans la théorie ZF des ensembles en utilisant l'axiome du choix dépendant. Ce livre donne aussi la démonstration du théorème de Gödel et aborde le théorème d'indépendance de Paul Cohen (par des méthode de forcing). À lire en prenant le temps et avec une aspirine!

@Cc

Comme d'habitude tu m'as lu en diagonale. Ou pas lu...

http://www.les-mathematiques.net/phorum/read.php?16,2205626,2209148#msg-2209148

Et


http://www.les-mathematiques.net/phorum/read.php?16,2205626,2209804#msg-2209804


Je ne suis en désaccord avec toi que sur le fait qu'on est en désaccord lol


Quand je disais "travaille toute seule" c'est au sens où on a pas besoin de définir les ordinaux. "L'union des <<-majorant du singleton vide forment une chaine" (*) d'où tout se déduit trivialement n'a pas besoin des ordinaux formels c'est tout ce que je disais... d'une part << rappelle les ordinaux dans sa construction (domination de type successeur et domination de type limite , et << est engendré par domination)

...d'autre part pour montrer (*) il semble difficile de se passer du fait que cet ensemble (les << majorants du singleton vide) est en fait bien ordonné, donc : et de l'extérieur (enoncé), et de l'intérieur (demo) on a la présence des ordinaux ou de bon ordre. Mais .... on a un énoncé (*) qui est vrai, il ne demande qu'une fonction de choix pour être vrai, et c'est en ce sens que je disais que << travaille toute seule, non pas par la preuve de (*) mais par la "vérité " de (*)... ce n'est pas très défini, je parle de ma motivation à avoir écrit "travaille tout seul" qui est déjà flou... mais je précise juste que ce flou n'était pas dirigé vers une proclamation d'indépendance de (*) et des ordinaux, loin de là.

Je vais regarder ton jeu il a l'air chouette. Et je risque d'avoir des questions, qui engloberont aussi le jeu des déterminations de boreliens (sur un ... euh deux ... autres fils) donc je le ferai dans un autre post.

[EDIT : je viens de comprendre le jeu qui est analogie au fait que si un ensemble est muni d'une fonction de choix, il est bien ordonable, ce qui confirme qu'on est d'accord : selon mon slogan (qui n'en est pas un) la fonction L, "fabrique toute seule" un successeur à toute stratégie de bob, en associant à une partie de E qui fait échouer la stratégie à etre une fonction de choix , un élément de cette partie et en ne changeant rien à s, partout ailleurs. on en déduit un successeur limite d'une famille denombrable de successeurs et la relation d'ordre engendrée par "etre successeur ou limite" est telle que les majorants d'une stratégie donnée est un ensemble bien ordonné, ainsi que l'ensemble des "bons ensembles " de chaque stratégie de cette chaine (ce qui s'envoient sur un de leurs element) bien ordonnés par inclusion et dont l'union ne peut qu'être que l'ensemble des parties de E, je ferai tout au propre plus tard]

@namiswan. Oui bien sûr j'avais compris ta démarche. Je ne critiquais pas ton post mais précisais un peu ma déclaration initiale.

Bonjour,

Les preuves basées sur les ordinaux, j'en ai un peu mon gonfle. C'est artificiel et une solution de facilité. Les preuves de Namiswan reposent sur les segment initiaux (et en aucun cas des débuts), tout comme celles de Bourbaki-Tarski.

L'usage des ordinaux doit être modéré !

@Titi : pourquoi es-tu fâché après les ordinaux ? C'est quand même la colonne vertébrale de $\mathbb{V}$, non ?

@Thierry
Au fond, à chaque spécialité ses outils. En théorie des ensembles pure et dure les ordinaux sont incontournables.