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
232 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
 
 
 
 
 

Ensemble inductif

Envoyé par Julia Paule 
Ensemble inductif
il y a trois mois
Bonjour,

Ma question va certainement vous paraître naïve, en tout cas pour les initiés de la théorie des ensembles. J'essaie de comprendre intuitivement (je n'ai pas le temps d'approfondir) ce fameux Lemme de Zorn, que je vois apparaître assez souvent en Algèbre, car il aide visiblement à pas mal de démonstrations.

On part d'un ensemble $E$ muni d'une relation d'ordre, dit inductif, i.e. chacune de ses chaînes (parties totalement ordonnées) admet un majorant, que j'imagine dans $E$ (pas dans la partie considérée, ce n'est en effet assez souvent pas précisé).

Si je comprends bien, les grands ensembles comme $\mathbb{N}, \mathbb{Z}, \mathbb{Q}, \mathbb{R}$ munis de la relation d'ordre ($\leq$) ne sont pas inductifs ?
Mais $[0,1] (\subset \mathbb{R})$ muni de $\leq $ est inductif ?
Et pour tout ensemble $E$, l'ensemble de ses parties muni de l'inclusion est inductif ?
Mais $\cal{P}$$(E) \setminus E$ ne l'est pas forcément ?

Merci d'avance.
Re: Ensemble inductif
il y a trois mois
Tu comprends bien, sauf peut-être ton dernier point qui n'est pas tout à fait clair : qu'appelles-tu $P(E)\setminus E$ ? (enfin il y a un sens non ambigu, mais je ne pense pas que c'est ce que tu veux dire) Veux-tu dire $P(E)\setminus\{E\}$ ? Dans ce cas si, il est inductif: une chaîne est forcément incluse dans un $E\setminus\{e\}$ pour au moins un $e\in E$, donc ça reste inductif.

Tout ensemble ordonné qui a un maximum est inductif, trivialement: pour toute chaîne, prendre ledit maximum comme majorant (et effectivement, le majorant est dans $E$)

Les ensembles ordonnés inductifs auxquels on va vouloir appliquer Zorn, on ne sait en principe pas au départ qu'il y a des éléments maximaux, c'est d'ailleurs ça qu'on essaie d'obtenir.

"Mathematics, rightly viewed, possesses not only truth, but supreme beauty"-Russell
Re: Ensemble inductif
il y a trois mois
Oui, tu as compris. Tu auras probablement droit à un cadeau de Foys qui adore poster une des versions qu'il adore qui équivaut à Zorn et AC.

Mais si un jour tu as la dispo, étudie les ordinaux, car Zorn ne rend compte que de très peu de choses, dont une qui est la rapidité avec laquelle le maximal est produit par la recherche qui utilise une fonction choix.

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Ensemble inductif
il y a trois mois
@Julia : je pense qu'à moins d'être un génie en théorie des ensembles on ne peut bien comprendre le lemme de Zorn qu'à travers ses applications.

Par exemple, exercice : essaie de refaire toute seule (avec Zorn) la preuve du fait que dans un anneau (commutatif unitaire), tout idéal propre est inclus dans un idéal maximal.
Plus difficile : utiliser Zorn pour démontrer que de deux ensembles $A$ et $B$ il y en a toujours au moins un qui s'injecte dans l'autre.

Roughly speaking, Zorn est une trivialité : soit $E$ non vide et inductif. Tu choisis aléatoirement $x_0 \in E$. Si $x_0$ est maximal, tant mieux. Sinon tu choisis $x_1$ tel que $x_0 \leq x_1$. Et ainsi de suite. Si le procédé sature à $x_n$, tant mieux. Sinon tu as construit une suite $(x_n)$ telle que $\forall n, x_n \leq x_{n+1}$. Et c'est là que tu appliques l'hypothèse : ta suite est une chaîne, donc elle admet un majorant, mettons $x_{\omega}$. Si ce truc est maximal, tant mieux, sinon tu continues. Et comme il n'y a qu'une quantité fixée d'éléments dans $E$ tu finiras bien un jour ou l'autre par tomber sur un élément maximal.
Dans la preuve formelle toute la difficulté consiste à remplacer la dernière phrase écrite par de vraies maths, et c'est là qu'on a besoin de l'axiome du choix.
Mais si tu veux faire de l'algèbre ou de l'analyse tu n'as pas besoin de connaître la preuve formelle, il te suffit de bien appréhender l'énoncé du lemme de Zorn et de savoir l'appliquer. Tu verras qu'avec un peu d'habitude on le voit arriver à grands pas...
Re: Ensemble inductif
il y a trois mois
@Christophe : c'est quoi le dada de Foys ?
Le mien c'est justement AC $\Leftrightarrow$ "de 2 ensembles l'un s'injecte dans l'autre". (C'est le côté de la droite vers la gauche qui déchire).
Re: Ensemble inductif
il y a trois mois
Merci beaucoup à tous.

Maxtimax, oui c'est $\cal{P}$$(E) \setminus \{ E \} $ (on considère l'élément exclu comme un ensemble), et il est inductif. Elément maximum = plus grand élément ? Un ensemble $E$ qui a un plus grand élément est inductif (toute chaîne admet cet élément comme majorant), et il a un élément maximal (ce plus grand élément). Donc ce qui est intéressant, c'est quand $E$ n'a pas de plus grand élément.

Martial, "tout idéal propre est inclus dans un idéal maximal" : si on prend $E$ = l'ensemble des idéaux de l'anneau $A$, l'élément de $E$ maximal est $A$ lui-même, je suppose qu'il faut prendre $E$ = l'ensemble des idéaux propres de l'anneau $A$. Je vais regarder.
Re: Ensemble inductif
il y a trois mois
Martial, merci beaucoup, je comprends jusqu'à l'étape où on applique un majorant $x_w$ qui n'est pas maximal, mais je ne comprends pas ce que veut dire : on n'a qu'un quantité fixée d'éléments dans $E$.

Le problème, c'est que je n'arrive pas à retenir un théorème si je n'ai pas vu sa preuve, ou du moins si je n'en ai pas compris les étapes intuitivement ...



Edité 3 fois. La dernière correction date de il y a trois mois et a été effectuée par Julia Paule.
Re: Ensemble inductif
il y a trois mois
Martial : je me permets de te corriger :ce n'est pas (du tout grinning smiley) pour la dernière phrase qu'on utilise AC, mais pour les premières phrases (précisément le "tu choisis $x_1$ [...] tu continues"). Une fois que les $(x_\alpha)$ sont construits, la contradiction arrive sans AC, c'est lors de la construction qu'on l'utilise.

Julia: la dernière phrase de la preuve de Martial ("quantité fixée") signifie la chose suivante: "il n'y a pas d'ensemble dans lequel s'injecte la classe des ordinaux". Bon, qu'est-ce que ça veut dire ?
Le "tu continues" cache une difficulté, qui est savoir comment indexer la continuation (jusqu'à $\omega$, c'était les entiers, mais après ?). Il y a un truc qui s'appelle "les ordinaux" et qui permet de faire cette indexation, et de continuer (modulo les choix): tu obtiens une suite $x_\alpha$ strictement croissante (en particulier injective) indexée par les ordinaux.
Si ton processus ne s'arrête jamais, tu as injecté tous les ordinaux dans $E$ - et là le théorème que j'ai énoncé te dit que ce n'est pas possible. Pour comprendre ce théorème il faut comprendre, to some extent, les ordinaux, et l'axiome du remplacement. L'idée étant que s'il y avait un ensemble de tous les ordinaux, ce serait lui-même un ordinal (ce qui n'est pas compliqué à montrer en sachant ce que ça veut dire), et c'est absurde

"Mathematics, rightly viewed, possesses not only truth, but supreme beauty"-Russell
Re: Ensemble inductif
il y a trois mois
@Julia : oui, c'est ça, il faut prendre pour $E$ l'ensemble des idéaux PROPRES de $A$. Ton élément maximal sera dans $E$, donc ce ne sera pas $A$, et donc ce sera un VRAI idéal maximal.

Je peux me tromper mais j'ai l'impression que par moments tu confonds maximal avec maximum. Pense à l'idéal $2\mathbb{Z}$. Il est maximal puisqu'il n'y a rien entre lui et $\mathbb{Z}$, mais pas maximum, par exemple parce que $3\mathbb{Z}$ n'est pas inclus dedans.

C'est normal que tu ne comprennes pas ma phrase : "on n'a qu'un quantité fixée d'éléments dans $E$", c'est tout sauf des maths.
Si tu connais un peu les ordinaux tu peux t'en sortir de la façon suivante : si $x_{\omega}$ n'est pas maximal tu construit un $x_{\omega+1} > x_{\omega}$ et ainsi de suite. Et quand tu rencontres un ordinal limite $\lambda$ tu utilises l'hypothèse : comme ta suite $(x_{\alpha})_{\alpha < \lambda}$ est une chaîne, par inductivité tu en déduis l'existence d'un $x_{\lambda}$ qui majore tous ses prédécesseurs.
(A ce propos, dans mon précédent post il faut remplacer tous les $\leq$ par des $<$, sinon la preuve ne tient pas).
Bref. Donc tous tes $x_{\alpha}$ sont deux à deux distincts.
Si la construction sature en un certain $x_{\alpha}$, tu as gagné.
Sinon ça veut dire que tu es capable de construire une injection de la classe des ordinaux dans $E$, et ça ça contredit le schéma de remplacement. (En renversant l'injection tu obtiens une application qui est définie sur un ensemble, et dont l'image est une classe propre).
Re: Ensemble inductif
il y a trois mois
Grillé par Max.

Je savais pertinemment qu'on utilisait AC pour construire les $x_{\alpha}$ mais je ne voulais pas semer le trouble dans la tête de Julia. (Remarque, j'y suis peut-être arrivé quand même, sans le faire exprès, lol).
Par contre je pensais qu'on utilisait aussi AC dans la preuve de ma phrase boîteuse.**
Et là tu as raison : pas de choix, que du remplacement.


** Pourquoi il me souligne "boîteuse" ? Il n'y a pas d'accent circonflexe sur ce truc ?
Re: Ensemble inductif
il y a trois mois
@Julia, je n'ai pas compris exactement ta difficulté? Tu veux une preuve du lemme de Zorn?

Sinon remarque, c'est dans les anneaux unitaires que ça marche grace à $1$. Dans un anneau non unitaire (ce qu'est n'importe quel idéal par exemple), ta chaine croissante peut aboutir à l'anneau entier.

La présence du 1 est absolument essentiel.

@Martial pour Foys, je crois que c'est un truc du genre "tout machin dont l'évaluation se fait uniquement sur les parties finies" à la place de "tout machin inductif". Ca revient au même, mais l'hypothèse est plus naturelle et je crois qu'il en a une preuve intuitionniste.

@Julia, tout dépend où tu veux aller, mais une maitrise de base des ordinaux te permettrait de trouver tout ça trivial et les preuves ne seraient à faire qu'une fois.

Si tu veux éviter COMPLETEMENT les ordinaux, étant donné un ensemble $E$ inductif et une fonction $f$ qui associe à chaque chaine $C$ un majorant strict de tous les éléments de $C$ quand c'est possible (non défini sinon), tu prends l'ensemble $T$ des couples $(A,R)$ où $A$ est une partie de $E$ et $R$ un bon ordre sur $A$ qui vérifie que pour tout $x$ dans $A: x = f(Avant(x))$ où $Avant(x)$ désigne l'ensemble des éléments strictement plus petits que $x$ au sens de $R$.

Tu prouves que la réunion des $A$ pour $(A,R)$ dans $T$ est un ensemble bien ordonné par l'ordre de $E$ qui a un maximum et ce maximum est maximal dans $E$.

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Ensemble inductif
il y a trois mois
Ok, merci beaucoup. Je vois en gros. En utilisant l'axiome du choix, on commence par essayer de trouver un élément maximal dans $E$ en choisissant des éléments de $E$ à chaque fois plus grands si on n'est pas tombé sur un élément maximal. Si cela ne marche pas (on a sans cesse un élément plus grand), qu'à cela ne tienne, on a un majorant dans $E$ de l'ensemble de ces éléments sans cesse plus grands (qui sont donc en nombre infini). Si ce majorant est un élément maximal, c'est terminé. Sinon on s'en sort en considérant les ordinaux qui permettent de faire des "paquets" d'éléments en nombre infini numérotés de manière ordinale (d'après ce que j'ai vu sur Wiki). Bon là, cela devient plus compliqué, il faut étudier le concept, mais on aboutit apparemment à une contradiction en utilisant d'autres axiomes (que celui de l'axiome du choix) de la théorie des ensembles.

Martial, non je ne confonds pas élément maximum (unique s'il existe) et maximal (pas forcément unique s'il existe), maximum => maximal (unique), réciproque fausse, et si l'ordre est total, les deux notions coïncident. Le problème de l'existence d'un élément maximal se pose quand l'ordre n'est pas total, sinon c'est vite vu (existence ou non d'un plus grand élément). Par contre, la borne supérieure quant à elle ne s'envisage que pour une partie de $E$.

Bon je vais m'arrêter là, cela m'entraînerait trop loin pour l'instant, mais je comprends mieux maintenant pourquoi ce résultat (très loin d'être intuitif) est admis. winking smiley

Je n'ai pas vu ton message christophe c., je reviens plus tard.



Edité 4 fois. La dernière correction date de il y a trois mois et a été effectuée par Julia Paule.
Re: Ensemble inductif
il y a trois mois
@Julia : bon, je crois que tu as saisi l'essentiel. Je le répète : pour faire de l'algèbre ou de l'analyse classique tu n'as pas besoin d'en savoir beaucoup plus sur Zorn.

Quand tu l'auras appliqué une dizaine de fois il n'aura plus de mystère pour toi.

Attention toutefois : il y a des cas où on a tendance à "zornifier" pour se simplifier la vie, alors que l'exercice est largement faisable sans l'axiome du choix. Je crois même qu'il y a des petits malins qui s'amusent à utiliser Zorn pour démontrer Cantor-Bernstein. Là, c'est carrément de la méchanceté.***

Je sors du sujet mais il y a un truc qui me fascine, c'est le lemme de rigidité du bon ordre : si on a 2 bons ordres $(A,\leq)$ et $(B, \leq')$, alors soit l'un est isomorphe à un segment initial propre de l'autre, soit ils sont isomorphes (c'est ce qu'on appelle la trichotomie).
Quand tu regardes la preuve de ce théorème, elle ressemble à s'y méprendre à une zornification... Et pourtant, pas l'ombre d'un axiome du choix derrière tout ça... Heureusement d'ailleurs !


*** H.S. on : Si on avait besoin de l'axiome du choix pour démontrer Cantor-Bernstein ça serait un de ces bordels, le monde !
D'ailleurs c'est un beau bordel, le monde !
Je me demande si Cantor-Bernstein ne requiert pas AC, au fond...

Michel, si tu nous regardes...
H.S. off
Re: Ensemble inductif
il y a trois mois
Le lemme dont parle Christophe est le suivant (Tukey-Teichmüller): Soit $E$ un ensemble et $\mathcal F$ un ensemble de parties de $E$ telles que pour tout $D\subseteq E$, $D\in \mathcal F$ si et seulement si tous les sous-ensembles finis de $D$ sont dans $\mathcal F$. Alors $\mathcal F$ possède un élément maximal pour l'inclusion.

Un exemple typique est donné, lorsque $E$ est un espace vectoriel, par l'ensemble des parties libres de $E$ (on retrouve le théorème de la base incomplète).
On peut montrer également avec ce lemme qu'en logique du premier ordre (ou autre puisque dans tous ces systèmes il va de soi qu'un énoncé est conséquence d'un ensemble d'énoncés si et seulement si il est conséquence d'un sous-ensemble fini de cet ensemble), toute théorie consisante est contenue dans une théorie consistante complète (pour récupérer le théorème de complétude il suffit de rajouter des témoins au langage avant: si $E$ est un énoncé à une variable libre, $\Gamma$ un ensemble d'énoncés et $\alpha$ une lettre non libre dans $\Gamma$ ou dans $E$, alors $\Gamma \cup \{\exists x E\Rightarrow E[x:=\alpha]\}$ est une extension conservative de $\Gamma$).

Montrons que cet énoncé entraîne Zorn (la réciproque étant évidente): soit $(E,\leq)$ inductif (au sens où c'est défini dans le premier message du fil, pas avec les bons ordres comme dans Krivine). L'ensemble des parties totalement ordonnées par $\leq$ vérifie les conditions du lemme de Tukey-Teichmüller et donc il existe dans $E$ un sous-ensemble totalement ordonné et maximal. Un majorant d'un tel sous-ensemble est alors nécessairement un élément maximal de $(E,\leq)$.

Ce qui rend le lemme de TT surprenant est que si $E$ est supposé dénombrable, le résultat peut se démontrer non seulement sans axiome du choix, mais en plus en logique intuitionniste (!!!).

L'idée est la suivante: écrivons $E:=\{e_n\mid n \in\N\}$. On pose $F_0=\emptyset$ et $F_{n+1}:= F_n \cup \{x\in E \mid x = e_n \wedge F_n \cup \{x\} \in \mathcal F\}$ (édité). On montre par récurrence que $F_n\in \mathcal F$ pour tout $n\in \N$ puis on vérifie ensuite que $\bigcup_{n\in \N} F_n$ est maximal dans $\mathcal F$ (exo).



Edité 6 fois. La dernière correction date de il y a trois mois et a été effectuée par Foys.
Re: Ensemble inductif
il y a trois mois
Très intéressant Foys, merci.
Re: Ensemble inductif
il y a trois mois
@Foys:

1/ comme tu le remarques toi-même, "pas au sens que tout bon ordre est majoré", mais au sens que "tout ordre total est majoré", ce qui peut te valoir des objections de bonne ou de mauvaise foi.

2/ Je pense que dire "tout ordre partiel contient contient au moins une partie totalement ordonnée maximale" est encore plus simple, plutôt que passer par l'aspect finitude. Je m'explique: en fait ce que tu appelles l'aspect finitude n'est rien d'autre que l'aspect fermé dans la topologie Tychonoff-blabla, du coup, ça peut laisser croire aux gens que c'est topologique au sens habituel des topologies séparées, et donc conséquence de la compacité, alors qu'il n'en est rien. C'est "typiquement" l'axiome du choix, avec sa dimension supplémentaire à l'axiome de l'ultrafiltre.

Pour ma part, je préfère (quitte à supposer l'axiome du choix) des versions "calculable-like", c'est à dire que tu mets un bon ordre sur $E$, en utilisant le plus petit ordinal possible (donc le cardinal de $E$) et tu colories en vert un point quand il majore les précédents verts, sinon tu le colories en rouge. C'est préférable parce que tu atteins ainsi le maximal en un "temps pseudo-fini" (pour pour être plus précis en temps $<card(E)$), le majorant étant le dernier élément à avoir été colorié en vert.

Par contre, il faut avouer que le fait que tout ensemble est bien ordonnable semble nécessiter la machinerie Zornique au moins une fois.

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Ensemble inductif
il y a trois mois
Citation
christophe c
1/ comme tu le remarques toi-même, "pas au sens que tout bon ordre est majoré", mais au sens que "tout ordre total est majoré", ce qui peut te valoir des objections de bonne ou de mauvaise foi.

C'est-à-dire qu'il y a deux lemmes de Zorn: le Zorn "bon ordre" que l'on trouve dans des ouvrages de théorie des ensembles (où il est naturel puisque c'est dans ce genre de travaux qu'on trouve de l'induction ordinale) et un Zorn "ordre total" plus faible qui est celui utilisé partout ailleurs en maths (et qui est celui cité par Julia Paule, d'où le choix que j'ai fait).

Faudrait essayer de trouver TT => Zorn avec bon ordre (une preuve courte je veux dire; je n'y ai pas réfléchi).
Re: Ensemble inductif
il y a trois mois
Citation
Foys
Faudrait essayer de trouver TT => Zorn avec bon ordre

Un bon ordre ce n'est jamais qu'une fonction choix ayant des propriétés de cohérence "finiment descriptibles" (en gros $\forall X,Y: \phi(X\cup Y)\in \{\phi(X);\phi(Y)\})$, et tu demandes que le domaine soit maximal. Mais bon, les gens sont moins habitués.

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Ensemble inductif
il y a trois mois
Foys : dans ta preuve de TT dénombrable, tu es sûr que c'est $x=e_n \implies$ et pas $x=e_n \land$ ? Parce que tel que c'est écrit, $F_{n+1}\supset E\setminus\{e_n\}$ j'ai l'impression

"Mathematics, rightly viewed, possesses not only truth, but supreme beauty"-Russell
Re: Ensemble inductif
il y a trois mois
Citation
christophe c
Par contre, il faut avouer que le fait que tout ensemble est bien ordonnable semble nécessiter la machinerie Zornique au moins une fois.

Si $X$ est un ensemble et $O$ un bon ordre sur $X$, on note ci-dessous pour tout $x\in X$, $S_O(x):=\{y \in X \mid (y,x)\in O, y\neq x\}$ (ensemble des éléments de $X$ strictement inférieurs à $x$ au sens de $O$).
On appelle segment initial de $X$ toute partie de $Y$ de $X$ telle que pour tous $a\in X$ et $b\in Y$, si $(a,b)\in O$ alors $a\in Y$.

Soit $E$ un ensemble et $\varphi: \mathcal P(E)\backslash \{\emptyset\}\to E$ une fonction de choix.

Un couple $(C,R)$ est appelé une chaîne si $C\subseteq E$, $R$ est un bon ordre sur $C$ et, pour tout segment initial $D$ de $(C,R)$, si $D\neq C$ alors $\varphi (E\backslash D) \in C$ et $D$ est l'ensemble des éléments de $C$ inférieurs à $\varphi(E \backslash D)$.

Alors si $(C,R)$ et $(C',R')$ sont des chaînes, l'une est un segment initial de l'autre(*) (on en conclut que la réunion de toutes les chaînes est une chaîne dont le complémentaire est du reste vide sinon on pourrait la prolonger avec $\varphi$).

Preuve de (*): soit $\mathcal A$ l'ensemble des parties $U$ de $E$ qui sont à la fois des segments initiaux pour $(C,R)$ et pour $(C',R')$ et tels que $R|_U = R'_U$. Alors la réunion $B$ de $\mathcal A$ est un segment initial à la fois pour $C$ et pour $C'$. Si $B\neq C$ alors $B = S_R (\varphi (E\backslash B))$ et donc $\varphi (E\backslash B)\in C$. De même si $B \neq C'$, $B = S_{R'} (\varphi(E \backslash B))$ et donc $\varphi(E\backslash B)\in C'$. Mais ceci entraîne que $B \cup \{\varphi (E\backslash B)\}$ est dans $\mathcal A$ ce qui est impossible puisque $B$ est la réunion de $A$ et que $\varphi(E \backslash B)\notin B$.
Donc $B=C$ ou $B=C'$ ce qui conclut.



Edité 2 fois. La dernière correction date de il y a trois mois et a été effectuée par Foys.
Re: Ensemble inductif
il y a trois mois
Tu as écrit exactement ce que j'appelle la machinerie Zornique. J'espère que Julia te remerciera.

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Ensemble inductif
il y a trois mois
Oui Maxtimax, je me suis encore embrouillé, c'est comme avec Diaconescu...
Un lien (spoiler si les gens veulent chercher): [www.les-mathematiques.net]
Re: Ensemble inductif
il y a trois mois
J'ai l'impression que les gens sont trop souvent effrayés par les ordinaux, je montre comment s'en passer sans rien perdre.

On peut le faire de deux façons:

1/ ou bien en supposant l'axiome de fondation

2/ ou bien autrement.

Je choisis (2) exprès, bien que ce serait plus léger avec (1), mais j'économise un axiome.

On note $E<F$ quand $P(E)\subset F$. La notation $P(X)$ voulant dire "ensemble des parties de X"

Soit $A$ un ensemble et $f$ une application de $P(A)$ dans $A$.

On dit que $\phi$ est bonne quand $dom(\phi)$ est transitif** et quand $\forall x\in dom(\phi)$, on a :

$$\phi(x) = f( \{\phi(y) \mid y<x\} )$$

Bin avec ça, t'as tout ce dont tu rêvais, Julia.


Il est facile de prouver deux bonnes fonctions sont du même avis ie $\forall x\in dom(\phi)\cap dom(\sigma) : \phi(x)=\sigma(x)$ d'une part et que d'autre part, tout ensemble $e$ est tel qu'il existe au moins une $\phi$ telle que $e\in dom(\phi)$.

Si ta fonction $f$ envoie chaque $X$ autre que $A$ dans $A\setminus X$, tu obtiens un bon ordre sur $A$, etc.

Flemme ce soir, demain je t'écrirai comment le dire en français de manière douce et simple.

Tout le secret de cette histoire est que $<$ est bien fondée, ie qu'il n'existe pas d'ensemble $E$ non vide tel que $\forall x\in E\exists y\in E: P(y)\subset x$. Je te le laisse en exo.

En fait, les ordinaux n'apparaissent pas, mais ils sont ce qu'on appelle les hauteurs possibles des arbres bien fondés (c'est à dire sans branche). Le seul inconvénient de cette approche qui a l'avantage de ne pas nécessiter de preuve puisque tout est évident c'est que les ordinaux ont "plusieurs noms" pour un même ordinal.

Si j'avais choisie 1, au lieu de $<$, j'aurais juste pris ... $\in$.

** X est transitif abrège [X inclus dans P(X)]

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Ensemble inductif
il y a trois mois
Merci beaucoup. Je ne vous ai pas encore lus, je vais le faire juste après. En revenant à mon niveau de néophyte, je commence à mieux saisir la difficulté.

Prenons des exemples. Si $E$ est fini, il parait assez évident qu'il a des éléments maximaux (au moins un). En effet, on range ses éléments dans des chaînes selon l'ordre, chaque chaîne aboutissant à un élément qui n'en possède pas de plus grand.
Par exemple, on a rangé les lettres de l'alphabet selon l'ordre (inhabituel !) $a<e<i<o<u<y$, $b<d<f<h<j<l<n<p<r<t<w$, et $c<g<k<m<q<s<v<x<z$. En l'état, les éléments maximaux sont $y,w,z$. Mais on peut rajouter les relations $f<u$ et $i<p$, autrement dit il apparait que les chaines qui aboutissent aux éléments maximaux ne sont pas forcément uniques, et que des éléments ($o,h,j,k,l,n$) peuvent ne pas apparaître dans ces chaînes. Si on rajoute $y<w$, $y$ n'est plus maximal.
Bref, il apparait assez intuitif qu'un ensemble fini est inductif, et que dans tous les cas, de(s) élément(s) maximal(aux) existe(nt).

Prenons un exemple avec $E$ infini et inductif, par exemple $[0,1] \times [0,1] \subset \mathbb{R}^2$, avec l'ordre partiel $(x,y) \leq (x',y') \Leftrightarrow x=x', y \leq y'$. Tous les couples $(a,1)$, $a$ fixé, sont maximaux. On peut construire des chaînes croissantes, qui admettent des majorants, mais qui n'aboutissent pas forcément aux éléments maximaux, par exemple la chaîne $(a, \frac{1}{2} - \frac{1}{n}), n \geq 2$. Il faut quelque chose de plus puissant. Si on est arrivé à ordonner des éléments en chaînes les plus longues possibles (pas forcément tous les éléments, et qui peuvent être redondants dans les chaînes, qui d'ailleurs ne sont pas forcément uniques), les majorants (qui existent car $E$ est inductif) de toutes les chaînes sont trivialement des éléments maximaux.
Par contre, dans $\mathbb{R}^2$ non inductif muni du même ordre, il n'y a pas d'élément maximal, car à la base, $\mathbb{R}^2$ n'est pas borné (pas majoré), et il existe des chaînes non majorées.

Remarque : avec le même ensemble $[0,1] \times [0,1] \subset \mathbb{R}^2$ sous-jacent et la relation d'ordre partiel $(x,y) \leq (x',y') \Leftrightarrow x \leq x', y \leq y'$, il n'y a qu'un seul élément maximal $(1,1)$ (la réciproque de : ordre total => un élément maximal au plus est fausse). On y arrive par un nombre infini de chaînes.

Bref, je commence à mieux saisir l'ampleur de la difficulté, et je comprends mieux maintenant pourquoi il faut ordonner les infinis.



Edité 2 fois. La dernière correction date de il y a trois mois et a été effectuée par Julia Paule.
Re: Ensemble inductif
il y a trois mois
Martial, je le répète : tant que je n'ai pas compris d'où sort ce Lemme de Zorn (mais ça y est, maintenant je l'ai compris grâce à ce fil), je ne peux pas le retenir, et pourtant je l'ai déjà vu pas mal de fois. La cerise sur le gâteau est de comprendre les grandes étapes de sa démonstration.



Edité 1 fois. La dernière correction date de il y a trois mois et a été effectuée par Julia Paule.
Re: Ensemble inductif
il y a trois mois
Merci beaucoup Foys et tous, mais je suis encore trop loin de te comprendre. Il est vrai qu'entre fini et infini, il y a dénombrable, et on peut commencer par là. Ce que tu dis, c'est qu'on peut démontrer le lemme de Zorn dans les ensembles dénombrables, sans utiliser l'axiome du choix.
Enfin, grâce à ce fil, j'ai compris d'où sortait le lemme de Zorn, et il m'apparait intuitivement vrai même dans les ensembles infinis inductifs.
Re: Ensemble inductif
il y a trois mois
J'ai trouvé cela : [www.irif.fr]

et : [www.irif.fr]

Merci beaucoup à leurs auteurs !

(vous allez me dire : pourquoi ne pas avoir cherché plus tôt, réponse : pour un néophyte, il n'est pas évident que le lemme de Zorn est loin d'être facilement démontrable)
Re: Ensemble inductif
il y a trois mois
Julia, ces documents disent EXACTEMENT ce qui t'a été dit dans ce fil. Comme quoi les choses sont souvent affaire de psychologie. J'en reviens à te conseiller d'acquérir les ordinaux qui généralisent les entiers et te permettront finalement d'avoir du recul pour beaucoup de chapitres infinitistes (même si ce n'est plus trop la mode)

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Ensemble inductif
il y a trois mois
Merci christophe c. En effet pour comprendre ce qui est dit dans ce fil, il faut commencer par étudier la théorie des ensembles, notamment les ordinaux et l'axiome de remplacement dont parle Maxtimax, où se situe le noeud de la démonstration du lemme.
Re: Ensemble inductif
il y a trois mois
Citation
Julia
notamment les ordinaux et l'axiome de remplacement

C'est la façon la plus "humaine", celle qu'on retient définitivement parce que c'est la même preuve que celle qui consiste à prouver qu'il y a un élément maximal dans tout ensemble fini ordonné.

Mais cet axiome est superflu, si tu lis, par exemple, d'autres posts, par exemple j'imagine celui de Foys (je n'ai pas tout en tête de ce qui a été dit dans le fil) où tu:

0/ prends une $f$ qui à chaque chaine associe un majorant

1/ regardes les parties bien ordonnées $(A\leq)$ de $E$ telle que pour tout $x\in A: x=f(pred(x))$ où $pred(x)$ est l'ensemble des éléments de $A$ tels que $y<x$

2/ prouve qu'elles sont toutes d'accord entre elles sur qui est plus grand que qui

3/ prends la réunion, bien ordonnée, dont le majorant est alors forcément maximal.

Cette preuve a l'avantage que tu ne dépasse pas $P(P(E))$ comme objets existants. Donc est strictement moins dangereuse que celle avec le remplacement.

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Ensemble inductif
il y a trois mois
avatar
Bonjour

Voici un extrait du livre Analyse I de Laurent Schwartz dans lequel l'équivalence entre axiome du choix et lemme de Zorn est démontrée, sans faire appel aux ordinaux. La démonstration du résultat qui nous préoccupe est longue, page 96 du livre.

Il y a quelques résultats fondamentaux qui sont démontrés au moyen de ce lemme.

Titi



Edité 1 fois. La dernière correction date de il y a trois mois et a été effectuée par Thierry Poma.
Pièces jointes:
ouvrir | télécharger - Sur le lemme de Zorn.pdf (2.16 MB)
Re: Ensemble inductif
il y a trois mois
Bonjour,

Merci beaucoup à vous deux.

christophe c., en français, ça va mieux ! (sinon je bute sur des définitions) Le principe est donc en gros de constituer des chaînes (à l'aide de ce que Foys appelle le bon ordre et les segments initiaux) telles que l'ensemble constitué des majorants de ces chaînes admet lui-même un majorant, qui est un élément maximal de $E$.

Sinon je me suis essayée à le démontrer quand $E$ est dénombrable, par contraposée en supposant que $E$ n'admet pas d'élément maximal : on peut construire une chaîne constituée d'éléments sans cesse plus grands : $x_1 < x_2 < ... < x_n < \cdots$, cela ne veut pas dire que cette chaîne n'est pas majorée (par exemple dans $\mathbb{N}$, muni d'un ordre autre que son ordre naturel, et la chaîne des entiers pairs qu'on majorerait par $1$...), donc c'est pas évident non plus.
Mais si cette chaîne est majorée, cela est le début d'une nouvelle chaîne (car $E$ n'a pas d'élément maximal), etc..., qui si elle est majorée elle-même, va produire une nouvelle chaîne, etc ..., il me semble qu'on voit s'esquisser le principe de la démonstration du lemme de Zorn avec des chaînes admettant des majorants, ordonnés entre eux, et la chaîne constituée de ces majorants qui n'est pas majorée.



Edité 1 fois. La dernière correction date de il y a trois mois et a été effectuée par Julia Paule.
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 228, Messages: 1 506 987, Utilisateurs: 27 661.
Notre dernier utilisateur inscrit ibra.


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

 

 
©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