Comparaison des ensembles, préordre total?
Bonjour
Je m'intéresse à un problème probablement ultra-classique, pourtant, je n'arrive pas à trouver une référence claire ou une démonstration, et je n'arrive pas à la produire moi-même, je pose le problème.
On s'intéresse à la relation de préordre à l'origine de la notion de cardinal. On note $a\leq b$ pour dire il existe une injection de $a$ dans $b$.
Je veux montrer que $\leq$ est une relation de préordre totale (i.e $\forall a,b ( a\leq b \lor b\leq a )$ ).
J'utilise ZFC, aucun problème pour montrer que c'est un préordre (transitivité et réflexivité).
Mais pour montrer que c'est total, je suis un peu paumé et même inquiet, parce que la seule phrase que j'ai pu trouver faisant explicitement référence à ce problème est celle-ci :
"La comparaison des ensembles via leurs cardinaux est un préordre (total si on admet qu’il existe une injection entre deux ensembles)" (sur ce lien : http://www.lsv.fr/~leroux/To_be_downloaded/Teaching/Discrete_maths/ch3_relations.pdf ).
Même si ça ne donne rien je vous communique ci-dessous le raisonnement que j'ai tenu pour le moment pour essayer de démontrer la propriété.
- Je suppose $\neg (a \leq b)$, j'essaie de montrer qu'il existe une surjection de $a$ dans $b$ (équivalent à l'existence d'une injection de $b$ dans $a$ par ZFC, en gras le "C").
- Ne parvenant à rien de cette manière, je me préoccupe alors des propriétés d'un ensemble que j'appelle $X$ et que je définis ainsi : $X=\{ x \mid x\in \mathcal{P}(b) \wedge x\leq a \}$, je sais qu'il n'est pas vide (il contient au moins l'ensemble vide). Mais finalement ça ne me sert pas à grand chose, la formule que j'ai crue la plus intéressante que j'ai pu trouver sur $X$ est celle-ci (je rappelle qu'on suppose $\neg (a \leq b)$) : $\forall x \left[ (x\in X \wedge x\neq b) \rightarrow \exists y (y\in X\wedge x\subset y \wedge x\neq y) \right]$, finalement, ça ne m'a pas l'air très pertinent dans le cas général (mon but étant de prouver $b\in X$).
Quelqu'un a une référence sur une démonstration (ou sur l'inexistence de la démonstration, mais j'en serais fort triste) ou une idée permettant de se dépatouiller ?
Merci d'avance !
Je m'intéresse à un problème probablement ultra-classique, pourtant, je n'arrive pas à trouver une référence claire ou une démonstration, et je n'arrive pas à la produire moi-même, je pose le problème.
On s'intéresse à la relation de préordre à l'origine de la notion de cardinal. On note $a\leq b$ pour dire il existe une injection de $a$ dans $b$.
Je veux montrer que $\leq$ est une relation de préordre totale (i.e $\forall a,b ( a\leq b \lor b\leq a )$ ).
J'utilise ZFC, aucun problème pour montrer que c'est un préordre (transitivité et réflexivité).
Mais pour montrer que c'est total, je suis un peu paumé et même inquiet, parce que la seule phrase que j'ai pu trouver faisant explicitement référence à ce problème est celle-ci :
"La comparaison des ensembles via leurs cardinaux est un préordre (total si on admet qu’il existe une injection entre deux ensembles)" (sur ce lien : http://www.lsv.fr/~leroux/To_be_downloaded/Teaching/Discrete_maths/ch3_relations.pdf ).
Même si ça ne donne rien je vous communique ci-dessous le raisonnement que j'ai tenu pour le moment pour essayer de démontrer la propriété.
- Je suppose $\neg (a \leq b)$, j'essaie de montrer qu'il existe une surjection de $a$ dans $b$ (équivalent à l'existence d'une injection de $b$ dans $a$ par ZFC, en gras le "C").
- Ne parvenant à rien de cette manière, je me préoccupe alors des propriétés d'un ensemble que j'appelle $X$ et que je définis ainsi : $X=\{ x \mid x\in \mathcal{P}(b) \wedge x\leq a \}$, je sais qu'il n'est pas vide (il contient au moins l'ensemble vide). Mais finalement ça ne me sert pas à grand chose, la formule que j'ai crue la plus intéressante que j'ai pu trouver sur $X$ est celle-ci (je rappelle qu'on suppose $\neg (a \leq b)$) : $\forall x \left[ (x\in X \wedge x\neq b) \rightarrow \exists y (y\in X\wedge x\subset y \wedge x\neq y) \right]$, finalement, ça ne m'a pas l'air très pertinent dans le cas général (mon but étant de prouver $b\in X$).
Quelqu'un a une référence sur une démonstration (ou sur l'inexistence de la démonstration, mais j'en serais fort triste) ou une idée permettant de se dépatouiller ?
Merci d'avance !
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Tout d'abords merci beaucoup! Déjà pour avoir commencé par le "petit coup de Zorn", je ne connaissais pas le lemme de Zorn (plusieurs fois lu son nom dans des paragraphes parlant de la généralisation de telle ou telle propriété ou dans des bas de pages, mais je ne m'y était jamais atteler).
Du coup, je me suis fait un gros début d'après-midi d'étude, à l'aide des sections 1 et 2 de ce document-là: https://www.normalesup.org/~rpeyre/pro/popul/zorn.pdf (et il y avait beaucoup de vocabulaire nouveau, j'ai bien galéré avant de l'intégrer suffisamment pour comprendre la démonstration). J'ai perdu un peu de temps à tenter d'éviter l'ensemble des injections partielles , mais j'ai fini par me rendre compte que ce n'était pas parce que $c\subset d$ et qu'il y avait une injection $f$ de $c$ dans $b$ et une autre de $d$ dans $b$ que je pouvais faire un prolongement de $f$ sur $d$ qui soit aussi injectif dans $b$ (je ne sais pas si la phrase est claire, mais si c'est le cas, tant mieux! Ça soulignera le fait que je me suis un peu embrouillé). Du coup, je vois à présent mieux l'intérêt de se préoccuper d'ensembles "plus grands" (on se préoccupe moins de l'existence de certaines choses qu'on a pas vraiment besoin de construire).
En conséquence, j'ai fait comme vous avez dit, pas eu de mal à montrer que si la famille $(a_i, f_i)_{i\in I}$ est une chaine d'injection partielle, le majorant $(\cup_{i\in I} a_i, \cup_{i\in I} f_i )$ est aussi une injection partielle et je sais quoi faire des éléments maximaux.
Ça m'a fait apprendre pas mal de choses. C'est le genre d'épisode qui fait qu'on ne regrette pas une tentative d'initiation à la logique. Merci encore!
Pour info dépêche toi surtout d'etudier les ordinaux. C'est un bon preordre il n'est pas seulement total.
J'ai relu plusieurs fois, il est possible que je n'ai pas été assez explicite, auquel cas désolé, mais j'avoue que je ne comprends pas très bien la critique:
D'une part, même si ZFC et les conventions qui lui sont associées sont assez nouvelles pour moi, j'ai assez explicitement fait référence à la définition d'une application dans ce cadre notamment par dans cet extrait:
"... pas eu de mal à montrer que si la famille $(a_i,f_i)_{i\in I}$ est une chaine d'injection partielle, le majorant $(\bigcup_{i \in I}a_i,\bigcup_{i \in I} f_i)$ est aussi une injection partielle" (phrase qui prouve aussi que je fais très attention aux conditions d'utilisation de mon nouveau copain, le lemme de Zorn).
Du coup, pas de problème en ce qui me concerne avec ces histoires d'inclusion et de prolongement (mais je ne me rappelle pas avoir utiliser un terme tel que "prolongation" (qui serait, il est vrai assez mal venu), si j'ai fait l'erreur et qu'on l'a corrigé, pardon.
On est d'accords qu'un élément maximal suffit. Mais: le but était de montrer que la relation "il existe une injection de tel ensemble dans tel autre" est total. Si je suppose qu'il existe une injection de a dans b et que là-dessus je montre qu'il y a des éléments maximaux de l'ensemble des injections partielles de a dans b, je serais pas bien avancé (on notera que si il n'existe pas d'injection de b dans a, tous les éléments maximaux seront des injections de a dans b).
Donc je considère le cas où il n'existe pas d'injection de $a$ dans $b$ et il est bien évident que le très pédagogique conseil de GaBuZoMeu avait pour but de pousser à montrer que dans ce cas il existe des parties de $a$ qui sont en bijection avec $b$ ( d'où ma réponse: "je sais quoi faire des éléments maximaux", on notera que si on ne suppose pas qu'il n'existe pas d'injection de $a$ dans $b$, on ne peux pas déduire l'existence de "bijection partielle" sur ces seules bases, puisqu'un élément maximal peut très bien n'être qu'une injection de $a$ dans $b$).
Bon voilà, désolé d'avoir été aussi sec, d'autant plus qu'il est possible que j'ai aussi mal interprété votre commentaire, mais je préfère écrire un truc comme ça que de faire mon malpoli et vous laisser sans réponse.
En ce qui concerne les ordinaux, je n'en connais guère plus que la définition et quelques exercices que j'ai fait en lien avec l'arithmétique depuis ma précédente question. Le but de cette visite dans la logique n'est pas de devenir un spécialiste, juste de consolider mes bases dans le reste des mathématiques. Mais merci du conseil, d'après ce que j'ai lu, il n'est pas impossible que j'y retourne quand je me remettrai à la topologie (ce qui ne saurait tarder).
Bon ben là-dessus bonne soirée, et désolé d'écrire des pavés, c'est vrai qu'on peut s'y perdre.
Les ordinaux sont une base et non un truc de spécialistes. Donc ne t'inquiète pas ça ne te ferait pas bosser des mois.
Je voulais juste te signaler que, en notant sp(u,v) l'ensemble {u;v} une bijection est un ensemble de couples ayant 2 à 2 des sp disjoints. Et une bijection maximale incluse dans A croix B te donne "qui edt le plus grand". La zornitude étant évidente.
Je ne doutais pas que ton intuition intime avait compris. Mais étant donné le marronnier qu'est de mettre ou non départ et arrivée (Bourbaki+Catories VS TDE) je saisissais ton désir au vol pour cette "remarque typo"
1/ En présence de l'axiome du choix, tu as le lemme de Zorn
2/ Avec Zorn tu as un nombre incroyable de choses. Le problème est que Zorn peut difficilement être rajouté comme un axiome ad hoc (sinon, pourquoi pas la RH, l'inexistence d'entier parfaits impairs, etc)
3/ Zorn te donne en 3 lignes*** que le préordre est un bon préordre (et pas seulement un préordre total), mais question: peut-on prouver AC=>Zorn en peu de lignes. A ma connaissance, ça n'a pas été fait officiellement, il faut au moins 20 lignes.
4/ Comme le fondement derrière tout ça, ce sont les ordinaux (En admettant connu l'outil "ordinal", Zorn n'est qu'un "petit cas particulier"), je me sens légitime à te conseiller leur acquisition.
Voilà, rien de plus.
*** c'est entre autre la raison de l'indication que je t'ai donnée à la suite de GBZM, puisque "l'usine à gaz" qui sacralise la notion de fonction en y ajoutant départ et arrivée, et, j'insiste bien que je ne conteste pas l'utilité de cette convention dans d'autres spécialités, cache complètement ça. D'ailleurs, je me reprends et te le mets en blanc sur blanc pour que tu aies la possibilité de chercher et que ne te soit pas imposé de solution. Voir ci-dessous si tu veux la solution, tu sélectionnes la zone blanche avec ta souris. Mais je pense que tu aurais tort d'aller la lire, cherche, tu en tireras plus de choses.
Si tu as $n\mapsto E_n$ une suite d'ensembles, et que tu appelles GENBIJ toute partie de leur produit qui contient des suites deux à deux disjointes, toute GENBIJ maximal (elle est de manière évidente zornante) te donne un entier $n$ et une injection, pour chaque $p$ de E_n$ dans $E_p$.
Soit $(E,\leq)$ un ordre vérifiant l'hypothèse du théorème de Zorn et $f: P(E)\to E$ telle que pour toute partie $A$ totalement ordonnée de $E$, $f(A)$ majore $A$. Supposant qu'il n'y ait pas d'élément maximal, soit $g:E\to E$ telle que $\forall x\in E: g(x)>x$.
Soit $L$ l'ensemble des parties $A$ de $E$ qui sont bien ordonnées par $\leq$ et telles que pour tout $x\in A$:
1/ si $x$ a un prédécesseur $y$ dans $A$ alors $x=g(y)$
2/ sinon $x=f(\{y\in A \mid y<x\})$
Exercice1: prouve que la réunion des éléments de $L$ est un élément de $L$, puis aboutis à une contradiction.
Exercice2: En admettant Zorn, prouve en une seule "Big-étape" que si $X$ est un ensemble quelconque non vide alors il existe $A\in X$ tel que pour tout $B\in X$ il existe une injection de $A$ dans $B$.