Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
274 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Zermelo coton ?

Envoyé par ev 
ev
Zermelo coton ?
il y a six semaines
avatar
Dans leur cours de mathématiques -1 les auteurs écrivent :

Citation
Arnaudiès & Fraysse
En 1904, Zermelo a démontré qu'étant donnés deux ensembles A et B quelconques, l'une au moins des deux assertions suivantes est vraie : « A est équipotent à une partie de B » ou « B est équipotent à une partie de A ».

Est-ce qu'il existe des démonstrations accessibles de ce théorème ?

Merci d'avance.

e.v.

Un peintre abstrait marche dans les rues de Moscou. Il est suivi par deux figuratifs en civil (Blague soviétique)
Re: Zermelo coton ?
il y a six semaines
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.
Re: Zermelo coton ?
il y a six semaines
NB: L'axiome du choix ou une de ses versions équivalentes est indispensable (l'énoncé l'entraîne, en effet soit $E$ un ensemble quelconque; si $E$ n'est équipotent à aucun ordinal alors tout ordinal s'injecte dans $E$ d'où une partie de $\mathcal P(E^2)$ -les bons ordres sur des parties de $E$ -en bijection avec la classe des ordinaux ce qui entraîne une contradiction dans $ZF$).
Re: Zermelo coton ?
il y a six semaines
@ev, j'en ai souvent palé sur le forum grinning smiley

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).

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
ev
Re: Zermelo coton ?
il y a six semaines
avatar
Merci à vous deux.

Si j'ai bien compris l'argument de Foys, on utilise Zorn puis l'axiome du choix.

Je me doutais bien que le résultat n'allait pas tomber en tirant à blanc.

Amicalement,

e.v.

Un peintre abstrait marche dans les rues de Moscou. Il est suivi par deux figuratifs en civil (Blague soviétique)
Re: Zermelo coton ?
il y a six semaines
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.

"Mathematics, rightly viewed, possesses not only truth, but supreme beauty"-Russell
Re: Zermelo coton ?
il y a six semaines
Ou sinon, il y a le théorème qui dit que pour tout couple d'ensembles bien ordonnés, il y en a forcément un qui est isomorphe à une section commençante de l'autre ; et, d'après le théorème de Zermelo (équivalent à l'axiome du choix) tout ensemble est bien ordonnable.
ev
Re: Zermelo coton ?
il y a six semaines
avatar
@ Max

Merci à toi. C'était un peu mon idée : Vas-y que je te colle un bon ordre sur A et sur B, tant qu'il reste des éléments dans A et dans B je t'envoie le plus petit élément de A sur le plus petit élément de B.

C'est entre " Je continue" et "il y a plus personne" que j'avais un peu de mal à faire tenir les bouts ensemble.

Sinon intuitivement, la proposition est acceptable pour l'esprit. Je n'en dirais pas autant de quelques zorneries bien senties.

Ce que je cherchais c'est une démonstration bien carrée sans boudin dans les coins.

Amicalement,

e.v.

Un peintre abstrait marche dans les rues de Moscou. Il est suivi par deux figuratifs en civil (Blague soviétique)
Re: Zermelo coton ?
il y a six semaines
@ev : "Je me doutais bien que le résultat n'allait pas tomber en tirant à blanc."

Tu as sacrément raison de penser ça, car en fait on peut démontrer que cette propriété est équivalente à l'axiome du choix. Par contraposée, cela veut dire que si AC est faux, alors il y a forcément 2 ensembles $A$ et $B$ tels qu'aucun des deux ne s'injecte dans l'autre.

C'est un truc assez méconnu, je trouve. Tu en trouveras une preuve à la fin de mon chap 10 (celui qui est consacré à AC), mais pour être honnête il faut bien reconnaître que Christophe C et Maxtimax m'ont beaucoup aidé pour rédiger cette preuve correctement. (Ce n'est pas difficile, mais il ne faut pas s'embrouiller).
Re: Zermelo coton ?
il y a six semaines
avatar
@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.
Pièces jointes:
ouvrir | télécharger - Selon Laurent Schwartz.pdf (945.2 KB)
Re: Zermelo coton ?
il y a six semaines
On peut reprendre ma preuve (qui est la même que celle du Schwartz) en allégeant les notations:
Une partie $X$ de $A\times B$ est "bonne" si pour tous $x\in A$, il existe un unique $y\in B$ tel que $(x,y)\in X$ et pour tous $y'\in B$, il existe un unique $x'\in A$ tel que $(x',y')\in X$.
Alors si $\mathcal G$ est un ensemble de parties bonnes totalement ordonné par l'inclusion, la réunion des éléments de $\mathcal G$ est encore une partie bonne (la preuve ne fait que déplier les définitions).
$\mathcal G$ est donc inductif pour l'inclusion et si $M$ est un élément maximal de $\mathcal G$ (qui existe par Zorn), alors $\{x\in A|(x,y)\in M\}=A$ ou $\{y\in A|(x,y)\in M\}=B$.
Dans le premier cas $M$ est une injection de $A$ dans $B$, dans le deuxième cas $M^{-1}=\{(y,x)\mid (x,y)\in M\}$ est une injection de $B$ dans $A$.

Exo: pourquoi cette preuve est la même que ci-dessus?
Re: Zermelo coton ?
il y a six semaines
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é.

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
ev
Re: Zermelo coton ?
il y a six semaines
avatar
@ Christophe.

Non. Je me doutais un peu que j'allais tomber sur du Zorn ou un de ses avatar à un coin de démonstration. Sinon, je suis au courant que Zorn était équivalent à un permis de bon ordre sur tout ensemble.

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.

Merci à tous. Spécial coucou à Titi.

e.v.

Un peintre abstrait marche dans les rues de Moscou. Il est suivi par deux figuratifs en civil (Blague soviétique)
Re: Zermelo coton ?
il y a six semaines
@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...
Re: Zermelo coton ?
il y a six semaines
Citation
Martial
Et pourtant (Thanks God !), il n'y a pas une molécule d'axiome du choix derrière tout ça...
Zorn est une induction transfinie qui ne dit pas son nom et ici les ensembles sont déjà livrés avec ce qu'il faut pour en faire une sans apport extérieur.



Edité 1 fois. La dernière correction date de il y a six semaines et a été effectuée par AD.
Re: Zermelo coton ?
il y a six semaines
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...)

"Mathematics, rightly viewed, possesses not only truth, but supreme beauty"-Russell
Re: Zermelo coton ?
il y a six semaines
@Foys : OK, merci pour la précision.

@Max : je sais ça. D'ailleurs le meilleur exemple est la preuve de Steinitz (toi qui parles allemand tu dois savoir s'il faut mettre un "t" ou pas) : tout corps admet une clôture algébrique (je précise pour les gens de passage). La preuve classique par Zorn est totalement artificielle, c'est d'ailleurs un très beau contre-exemple à ce que je disais plus haut à ev. En revanche les choses sont beaucoup plus simples si tu mets un bon ordre sur l'ensemble des polynômes et si tu procèdes par récurrence, de façon méthodique.

Bon, ce n'est que mon point de vue, on n'est pas obligés d'être d'accord.



Edité 1 fois. La dernière correction date de il y a six semaines et a été effectuée par Martial.
Re: Zermelo coton ?
il y a six semaines
avatar
Re: Zermelo coton ?
il y a six semaines
avatar
Chaurien par pitié change de répertoire, je ne sais pas pourquoi je continue à cliquer. Aurais-je un côté masochiste peut-être...eye rolling smiley
Re: Zermelo coton ?
il y a six semaines
avatar
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) [fr.wikipedia.org]
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.



Edité 1 fois. La dernière correction date de il y a six semaines et a été effectuée par Chaurien.
ev
Re: Zermelo coton ?
il y a six semaines
avatar
Exact, Chaurien.

Bonne soirée à tous.

e.v.

Un peintre abstrait marche dans les rues de Moscou. Il est suivi par deux figuratifs en civil (Blague soviétique)
Re: Zermelo coton ?
il y a six semaines
Citation
Colette Magny
À 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.
Re: Zermelo coton ?
il y a six semaines
Un truc qui semble être passé inaperçu sur lequel je me permets de ré-insister, c'est de combler (HORS ORDINAUX) le vide "de stations service" qu'il y a de AC à Zorn. C'est une problématique essentiellement ouverte.

Si vous prenez un matheux de bonne volonté, mais inculte et très loin des ordinaux, actuellement, vous le faites souffrir en lui exposant quelque preuve connue que ce soit de AC=>Zorn.

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Zermelo coton ?
il y a six semaines
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 ?



Edité 2 fois. La dernière correction date de il y a six semaines et a été effectuée par lesmathspointclaires.
Re: Zermelo coton ?
il y a cinq semaines
Je ne sais pas si cc exclut ou pas ta preuve, mais je peux apporter de l'eau à son moulin en confirmant : je souffre en la lisant (et je pense qu'il faudrait raisonnablement bien l'étaler pour que je la comprenne).



Edité 2 fois. La dernière correction date de il y a cinq semaines et a été effectuée par AD.
Re: Zermelo coton ?
il y a cinq semaines
@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.
Re: Zermelo coton ?
il y a cinq semaines
avatar
@Martial : bonsoir. Voici une preuve du lemme de Zorn à partir de AC rédigée par Laurent Schwartz, preuve extraite de son livre Analyse I. Elle est longue...
Pièces jointes:
ouvrir | télécharger - Lemme de Zorn à partir de AC.pdf (1.09 MB)
Re: Zermelo coton ?
il y a cinq semaines
Merci Thierry,

Je pense que cette preuve correspond à celle que nous avait donnée Sabbagh en M2 en 2003.
Re: Zermelo coton ?
il y a cinq semaines
@Martial : je demandais à cc un exemple de ce qu'il appelle trivial et hors ordinaux. Et j'ai donné une heuristique naturelle (sans aucune intelligence ou astuce) qui a du à coup sur etre employée avant moi. Le fait qu'il faille détailler la rendrait un peu plus "longue" mais pour moi elle est naturelle. Quelle est cette idée ? On veut montrer que si un ensemble n'a pas d'élément maximal il existe une chaine sans majorant : eh bien prenons une chaine, si elle n'a pas de majorant c'est fini et si elle en a , on en choisi un dans son complémentaire (si on ne peut pas , c'est que l'unique majorant de la chaine est aussi maximal dans l'ensemble, et c'est exclu. Donc on considère la chaine union le majorant choisi dans le complémentaire et ca donne le successeur de cette chaine.

Si on a les ordinaux c'est facile, on part d'une chaine 0 et on lui associe son successeur , c est la chaine 1 , pareil pour la chaine k+1, c'est la chaine successeur de la chaine K... pour tout ordinal limite alpha la chaine alpha est l'union des chaine précédente... ça s'arrête à un ordinal nécessairement limite. qdfd

Mais si on a pas le droit aux ordinaux on peut tout à fait utiliser Zormelo (j'ai une démo également "naturelle") mais ce que j'ai mis plus haut est une façon de se passer de bon ordre ou d'ordinaux , mais une façon artificielle , car ça copie l'idée des ordinaux sans prononcer le mot. C'est pourquoi je demandais à cc ce qu'il entendait par trivial et surtout par "hors ordinaux". Car ça n'est pas la première fois que j'entends dire que ça n'est pas trivial (mais comme si c'était dur, en mode litote, et c'est ce que dit cc, mais il dit hors ordinaux et je ne comprends pas trop ce que ça veut dire : on peut toujours copier l'idée... je voulais savoir s'il pensait qu'il peut y avoir une preuve simple pas comme celle dont j'ai donné l'heuristique ? Une sorte d'astuce avec la fonction de choix je ne sais pas, mais en tout cas , pour moi, s'il existait une preuve courte et astucieuse , ça ne voudrait pas dire qu'elle est plus simple.... que la preuve qui "va de soi" et peut-meme si elle peut être un peu pénible à écrire.

Je vais détailler l'heuristique que j'ai donnée, après tout peut-être que je me suis trompé quelque part ou que j'ai minimiser un point précis....
Re: Zermelo coton ?
il y a cinq semaines
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:D'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.
Re: Zermelo coton ?
il y a cinq semaines
@Namiswan : bien joué ! ... après une lecture rapide je suis convaincu. Je regarderai les mieux les détails plus tard. Si je ne dis pas de bêtise je vois un détail (sans gravité) : il faut dire que l'ensemble des M-ordonnés est non vide, mais bon c'est surtout pour pinailler et montrer que j'ai lu^^
Re: Zermelo coton ?
il y a cinq semaines
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 grinning smiley ) 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.

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Zermelo coton ?
il y a cinq semaines
En fait on peut avoir Zorn et Zormelo Zermelo juste avec une fonction de choix sur l'ensemble ; ça me fait penser au fait qu'il pourrait y avoir des ensembles typés (ceux qui sont muni d'une fonction de choix et les autres) Est-ce qu'on obtient (toutes? ) les principales versions moins fortes que AC , avec ce typage ?



Edité 2 fois. La dernière correction date de il y a cinq semaines et a été effectuée par Thierry Poma.
Re: Zermelo coton ?
il y a cinq semaines
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 grinning smiley ... Mais heureusement, on est tous vieux, payés, et pas à la recherche de complément de revenus grinning smiley

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Zermelo coton ?
il y a cinq semaines
Je reprends "mon argument " avec les notations de Namiswan, c'est le même mais juste dit autrement

$A$ domine $B$ si il existe $n$ tel que $A=F^k(B)$ ou si $A= \bigcup _{k\in \N}F^k(B)$ (**)
Avec $F(X)=X\cup \left\{M(X)\right\}$

Soit $<<$ la relation d'ordre engendrée par $B$ est dominé par $A$

Les majorant du singleton vide sont une chaine (*)

Contradiction


(Les majorants du singleton vide sont les ensembles $M$-ordonnés de Namiswan)

(*) est évidemment sujet à discussion et c'est à peu près voire exactement la preuve de Namiswan.


Pour Zermelo la preuve est similaire :

La relation de domination est définie par (**) Mais cette fois $F$ est une fonction (cette fois inclusion-decroissante) de tout $\mathcal P(E)$ dans lui-même
$F(X)= X-\left\{M(X)\right\}$

Où $M$ est une fonction de choix.

On montre que les majorants de $E$ pour la relation d'ordre engendrée par la " domination " est bien ordonné et on en déduit un bon ordre sur $E$

Pareil que (*) la preuve est naturelle, pas vraiment d'astuce requise.


Ce qui est amusant c'est que, certes ça copie les ordinaux... mais de façon optimale en quelque sorte : la fonction de choix travaille toute seule...

Ce qui me frappe et je n'y avais jamais réfléchi c'est qu'il suffit d'une fonction de choix pour avoir un bon ordre sur $E$

Pareil pour Zorn on a besoin que du fait que l'ensemble ordonné de base soit muni d'une fonction de choix (et sous cette hypothèses on peut se passer de l'axiome du choix pour la même conclusion) , du coup je me dis que pour avoir une preuve "sans l'idée des ordinaux" , il faut peut-être utiliser plus que la fonction de choix de E... mais sera - t - elle aussi "naturelle" que la preuve fint on parle.
Quand je dis "naturelle" ça ne veut pas dire immédiat, il faut quand même un peu
Re: Zermelo coton ?
il y a cinq semaines
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!

Les mathématiques ne sont pas vraies, elles sont commodes.
Re: Zermelo coton ?
il y a cinq semaines
@LMPC je ne suis pas totalement de ton avis sur des slogans comme "elle travaille toute seule", etc.

Comme je l'ai déjà dit, il y a une intuition ordinale, implicite ou explicite qui est derrière TOUTES les preuves connues de Zorn.

Pour te montrer que ton résumé philosophique renocntre des obstacles, je te propose de prouver sans ordinaux le théorème suivant:

Soit $E$ non vide. On joue au jeu suivant:

Lea joue $X\subset E$, Bob répond par $a\in E$ et Lea joue ensuite $b\in E$ (information parfaite, séquentiel, chacun voit ce qui a été joué avant).

La règle est la suivante: Bob gagne quand $(b\in X\to a\in X)$.

On ne dispose pas de l'axiome du choix (aucune forme, même faible). Soit $L$ une fonction telle que: que pour toute stratégie $s$ pour $Bob$, $L(s)$ est une stratégie pour Lea qui la fait gagner contre $s$.

Prouve qu'alors $0=1$.


Remarque: l'axiome du choix dit que Bob a forcément une stratégie gagnante, mais c'est un autre sujet.

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Zermelo coton ?
il y a cinq semaines
@Cc

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

[www.les-mathematiques.net]

Et


[www.les-mathematiques.net]


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]



Edité 3 fois. La dernière correction date de il y a cinq semaines et a été effectuée par lesmathspointclaires.
Re: Zermelo coton ?
il y a cinq semaines
-lmpc: merci d'avoir lu. Et pour l'histoire que l'ensemble des M-ordonnés est non vide, on peut considérer que c'est une conséquence de la proposition 3 en fasiant une union vide grinning smiley

-cc: tu disais qu'un matheux ne connaissant pas les ordinaux souffre en lisant une preuve de AC=>Zorn donc j'ai essayé d'écrire une preuve relativement concise et lisible (même si probablement améliorable). J'attend donc qu'un tel matheux passe par là la lire pour dire s'il a souffert ou pas pour savoir si j'ai réussi ou échoué grinning smiley
Mais je veux bien croire que les idées ne sont pas originales (y a t-il réellement plusieurs preuves de AC=>Zorn dans le fond?)
Re: Zermelo coton ?
il y a cinq semaines
@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.

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Zermelo coton ?
il y a cinq semaines
@LMPC: j'ai bien tout lu de ta réponse (et pas en diagonale). Ok.

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Zermelo coton ?
il y a cinq semaines
avatar
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é !
Re: Zermelo coton ?
il y a cinq semaines
@titi : ordinaux, bons ordres c'est essentiellement la même chose à des réécritures près.

L'avantage des ordinaux c'est juste qu'on n'a pas à préciser l'ordre typographiquement.

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Zermelo coton ?
il y a cinq semaines
@Titi : pourquoi es-tu fâché après les ordinaux ? C'est quand même la colonne vertébrale de $\mathbb{V}$, non ?
Re: Zermelo coton ?
il y a cinq semaines
avatar
@CC et Martial : bonsoir à tous les deux. Je ne suis nullement fâché avec les ordinaux. Pourquoi le serais-je ? J'affirme seulement que l'on utilise trop souvent ce concept (un ensemble transitif pourvu d'une structure de bon ordre, ce qui fait beaucoup), alors que l'on pourrait s'en passer. L'on peut s'en passer dans les démonstrations des théorèmes de Zermelo et Zorn, comme l'on peut le constater dans Bourbaki par exemple, après un bon lissage.

La partie $\mathrm{On}$ au sens intuitif de l'univers $\mathscr{U}$ (des ensembles) - univers pourvu de la relation binaire $\in$ bien connue - constituée de tous les ordinaux seulement, est bien ordonnée par la dite relation. Partant, la collection $\mathrm{On}$ de tous les ordinaux nous donne l’opportunité de donner naissance à la collection $\Bbb{V}$, par induction (transfinie) [moyennant une condition que l'on pourra préciser]. Comment pourrait-on faire autrement ?



Edité 3 fois. La dernière correction date de il y a cinq semaines et a été effectuée par Thierry Poma.
Re: Zermelo coton ?
il y a cinq semaines
@Thierry
Au fond, à chaque spécialité ses outils. En théorie des ensembles pure et dure les ordinaux sont incontournables.
Re: Zermelo coton ?
il y a cinq semaines
Citation
Titi
L'on peut s'en passer dans les démonstrations des théorèmes de Zermelo et Zorn, comme l'on peut le constater dans Bourbaki par exemple, après un bon lissage.

On ne s'en passe pas sur le fond, justement. C'est comme si tu disais qu'on peut se passer des entiers définis par leur ensemble:

$$\{\emptyset;\{\emptyset;\} ; \{\emptyset;\{\emptyset;\} \} ; \{\emptyset;\{\emptyset;\} ; \{\emptyset;\{\emptyset;\} \} \} ; \dots\}$$

en utilisant les cardinaux (en tant que classes) d'ensembles finis à la place.

Ce qu'il se passe pour Zorn, mais qui est aussi très présent en filigrane dès le lycée, c'est le fait que si $a\in \R$ et $f\in \R^\R$ alors l'ensemble des couples $(n,x)$ tels qu'il existe une suite finie $u$ vérifiant pour chaque $i\in dom(u)$ avec $i+1\in dom(u)$ que $u_0=a$ et $u_{i+1} = f(u_i)$ est une fonction définie sur $\N$. Au lieu de donner une définition propre et formelle de cet ensemble beaucoup de gens préfèrent dire: "axiome: la suite telle que blabla existe". Et ils ne le disent d'ailleurs même pas, c'est souvent à "leurs victimes" de deviner que c'est un axiome tacite de leur part.

Concernant $V$, je rappelle que c'est

$$ \{x\mid \forall y: [y\in MF\to x\cap y=\emptyset]$$

où $MF:=\{x \mid \forall y\in X\exists z\in y: z\in x$.

Là, pour le coup les ordinaux ne jouent que pour scanner $V$, mais pas pour le définir.

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 149 224, Messages: 1 506 869, Utilisateurs: 27 661.
Notre dernier utilisateur inscrit ibra.


Ce forum
Discussions: 2 516, Messages: 51 064.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page