Plus petit ensemble infini

@jacuzzi : en fait on peut être un peu plus précis, comme dit Maxtimax.
Deux choses :
1) L'énoncé "de 2 ensembles infinis il y en a toujours au moins un qui peut s'injecter dans l'autre" est EQUIVALENT à l'axiome du choix. C'est une propriété assez méconnue mais pas trop difficile à prouver (bon, enfin, il faut quand même connaître un peu les ordinaux).
2) La preuve de l'énoncé "$\N$ s'injecte dans tout ensemble infini" ne requiert que l'axiome du choix dénombrable, i.e. tout ensemble dénombrable d'ensembles non vides admet une fonction de choix, ou bien, ce qui revient au même, tout produit dénombrable d'ensembles non vides est non vide.
Par contre dans ce dernier cas je ne sais pas s'il y a équivalence, c'est-à-dire si la possibilité de plonger $\N$ dans tout ensemble infini entraîne $AC_{\omega}$.
Max, tu en penses quoi ?

Maxtimax : je n'ai pas bien compris le sens de ta dernière ligne.
Tu veux dire que si on appelle ensemble infini tout ensemble $X$ pour lequel il existe une injection non surjective de $X$ dans $X$, alors on peut démontrer dans ZF que $\N$ s'injecte dans tout ensemble infini ?
Si c'est ça, peux-tu m'expliquer pourquoi ?

Oui c'est effectivement très simple.
Tellement simple que je n'y aurais sans doute pas pensé, je cherchais un truc plus sophistiqué.
En tous cas, merci.

@Christophe : tu me fais un grand honneur. C'est bien la première fois que je pose une question qui ressemble à un problème ouvert, lol.
Si ça te fait plaisir tu peux aussi rajouter la question 1083, que j'ai posée il y a quelques semaines :
L'axiome de la réunion est-il redondant avec les autres axiomes de ZF(C) ?

Ta proposition n'est pas vraie, pour une raison idiote :-D En effet, si $E=G=\emptyset$ et $F$ est non vide, alors pas de surjection $F\to G$. Et en fait cette raison idiote te fait voir comment régler la preuve, et ne pas avoir besoin de l'axiome du choix. Je t'expliquerai juste en dessous comment "faire la différence".

Bon, on sait qu'on va devoir avoir que $G$ est non vide. Je rajoute cette condition à ton énoncé : $\exists x, x\in G$. Ah ! Mais ce que cette hypothèse me dit c'est qu'on me fournit [qui est ce "on"? peu importe, et je m'en fiche] un $x\in G$, je le prends avec joie.
Maintenant $g:E\to G$ est surjective : $\forall y\in G, \exists z\in E, g(z) = y$. J'applique ça avec $y=x$; à nouveau on me fournit un $z$ avec $g(z) = x$. Ah ! maintenant j'ai un $z\in E$, et ça c'est très pratique.
En effet je peux alors définir $r : F\to E$ par $r(a) = z$ si $a$ n'est pas dans l'image de $f$, et $b$ si $f(b) = a$. En termes de graphe, $r= \{(a,b) \mid f(b) = a \lor (a\notin \mathrm{im}(f) \land b= z )\}$ (on prouve aisément qu'il s'agit bien d'une fonction, car $f$ est injective).
On vérifie facilement que $r\circ f = id_E$. En particulier, $r$ est surjective, de sorte que $g\circ r : F\to G$ l'est aussi (en tant que composition de fonctions surjectives)

Bon, observons comment on a utilisé $\exists$ : on nous a dit $\exists z$, et on a utilisé $z$, pas de souci.
Maintenant supposons que tu aies un $\forall i\in I, \exists x, x\in X_i$ (la situation classique pour l'axiome du choix). Qu'as-tu le droit de faire avec ça ? Beh de prendre un $i\in I$ et de lui appliquer le reste. Donc si tu me donnes un $i$, et tu auras le droit de prétendre qu'on t'a fourni un $x$. Mais c'est "local" : tu ne peux pas dire "je me donne un $x$ pour chaque $i$", c'est simplement que si tu as un $i$, tu peux aussi avoir un $x$.
L'axiome du choix te dit : "ah bah en fait, ce n'est pas "local", tu aurais vraiment pu te fournir un $x$ pour chaque $i$" i.e. "tu peux carrément te prendre une fonction $x$ définie sur $I$ telle que $x_i \in X_i$".

Est-ce que la différence est un peu plus claire ? (je crains que pour la comprendre complètement il ne faille faire de la logique formelle pour comprendre véritablement ce qu'on a le droit de faire avec un $\exists$ ou avec un $\forall$)

(note : Bourbaki, dans sa théorie des ensembles, ne s'embarrasse pas de ça : il y a un opérateur $\tau$ qui répond à la question "qui est ce 'on' ?" que j'ai posée plus haut : le 'on', c'est $\tau$, et puisque c'est $\tau$, il peut te le fournir uniformément. En particulier la théorie des ensembles bourbakiste a l'axiome du choix directement codé dedans ! C'est un avantage en un certain sens (disons un avantage technique pour les gens qui ne veulent pas faire de logique), mais aussi un désavantage en d'autres sens (pour des sémantiques plus subtiles/élaborées) )

PS: si ça peut te rassurer, tu n'es pas le seul à avoir eu peur du $\exists$ après l'axiome du choix :-D au début moi aussi je le voyais partout, je me souviens avoir écrit quelque chose comme "il existe $x,y \in E$ distincts, donc par l'axiome du choix je choisis $x_0, x_1\in E$ distincts" : peut-être avec cet exemple vois-tu de plus près le ridicule ? on t'a dit qu'ils existaient, alors prends-les !

Oui, mais il faut le prouver ! Tu peux prouver par récurrence le résultat suivant : "si $I$ est fini, alors pour toute famille $(X_i)_{i\in I}$ d'ensembles non vides, il existe $(x_i)_{i\in I}$ avec pour tout $i\in I, x_i \in X_i$".
C'est assez facile, mais ça n'est pas un axiome, ni une évidence absolue. Si c'était une évidence absolue, on pourrait sûrement le prouver sans hypothèse sur $I$, et alors ça devient l'énoncé de l'axiome du choix.
Ce que tu écris en dessous est vrai, mais n'a pas grand chose à voir avec l'axiome du choix.

@Max : pour le côté "difficile", AC est certes "pratique", mais de plus nécessaire.
En effet, l'énoncé : "pour tous ensembles A et B, s'il existe une surj de A sur B, alors il existe une inj de B dans A" entraîne l'axiome du choix.

(Voir le bas de la page 18 de mon Chap 10)

Max : ce n'est pas moi qui l'ai inventé (comme tu t'en doutais), j'ai juste adapté la preuve à partir du livre de Patrick Dehornoy.