Ensembles finis, construction de von Neumann

Julia Paule

Bonjour,

Je bute sur un élément de démonstration dans mon livre. Suite à la construction des entiers naturels par la méthode de von Neumann, on a montré que $n$ entier naturel n'est pas équivalent (i.e. en bijection) à un sous-ensemble propre de $n$.

Alors, un ensemble $E$ est appelé fini s'il est équivalent à un certain entier naturel, sinon il est appelé infini.

On montre qu'un ensemble ne peut être équivalent qu'à au plus un entier naturel (en effet, si deux entiers naturels sont distincts, alors l'un est élément de l'autre, donc un sous-ensemble propre de l'autre, donc ils ne peuvent pas être équivalents).

Ensuite on en déduit qu'un ensemble fini n'est jamais équivalent à un sous-ensemble propre (affirmé sans démonstration dans mon livre). C'est là que je bute.

Soit $F \subset E$, $E$ fini, équivalent à $n$. Déjà il n'est pas difficile de montrer que $F$ est fini : il existe une injection de $F$ dans $E$, donc une bijection de $F$ dans un sous-ensemble de $n$, donc $F$ est équivalent à un entier naturel $m$ inclus dans $n$, i.e. égal à $n$ ou appartenant à $n$. Donc $F$ est fini.

Il s'agit de montrer que si $F \subsetneq E$, alors $m=n$ est impossible. Autrement dit, si $m=n$, alors $E=F$.
Si $m=n$, alors l'injection de $F$ dans $E$ est une bijection, mais je ne vois pas en l'état (c'est-à-dire sans utiliser des théorèmes connus par ailleurs), ce qui permet d'affirmer que $E=F$.

Merci d'avance (si vous avez eu le courage de me lire jusque là).

Merci de déplacer ce message s'il a mieux sa place dans le forum Algèbre.

Julia Paule

Ce qui est gênant, c'est qu'au vu de cette définition du cardinal d'un ensemble fini, je ne vois pas comment on pourrait s'en sortir en rattachant cette idée de cardinal au "nombre" d'éléments de $E$, par exemple, comment on pourrait dire que si $E$ est équivalent à $1$ et $F$ strictement inclus dans $E$ (donc par définition il existe un élément dans $E$ qui n'est pas dans $F$), alors $F$ est vide, équivalent à $0$.

Maxtimax

Déjà ta démonstration que $F$ est fini n'est pas complète: il faut montrer l'analogue pour les entiers naturels $n$ (à savoir que $F\subset n$ est nécessairement fini). Ce n'est pas compliqué, mais il faut le prouver, et je ne pense pas savoir le faire autrement que par récurrence.

Pour le reste c'est pareil: il suffit de montrer que si $F$ est un sous-ensemble propre de $n$, alors $F$ n'est pas équivalent à $n$. On peut à nouveau faire ça par récurrence (ce n'est pas compliqué) ou prouver un résultat plus fort que le précédent par récurrence à savoir :

Proposition : soit $F\subset n$ un sous-ensemble. Alors il existe un entier $m\subset n$ et une permutation $\sigma$ de $n$ telle que $\sigma (F) = m$ (image directe - je précise parce que si $F$ s'avère être un entier $\in n$, $\sigma (F)$ pourrait avoir une autre signification).

Cela permet de montrer à la fois le premier point, et le second en remarquant que si $F$ est strictement inclus dans $n$, alors $m<n$ ne peut pas être équivalent à $n$.

Il faudra "de toute façon" une récurrence à un moment puisque le résultat est faux pour des cardinaux infinis.

Julia Paule

Ah $1 = \{0 \}$, donc si $E$ est en bijection avec $1$, il possède un seul élément (au sens où on l'entend habituellement), i.e. $E= \{x \}$ (il faut le montrer). Il faut alors montrer que $E \setminus \{x \} = \emptyset$ (tel qu'il est défini dans cette théorie), etc ..., puis peut-être ensuite par induction ...

Pas vu ton message Maxtimax, je reviens.

Julia Paule

Maxtimax,

Si $F \subset n$, alors ce qui est valable pour $E \sim n$ est valable pour $n$ directement ?

Sinon dans le cours, on a ce résultat qui précède : tout sous-ensemble propre d'un entier naturel $n$ est équivalent à un entier naturel $m$ plus petit (i.e. à un élément de $n$).

Donc si $F \subsetneq n$, alors $F$ est équivalent à $m <n$, donc $F$ n'est pas équivalent à $n$.

Mais si $F \subsetneq E$, avec $E \sim n$, je ne vois pas comment on peut utiliser ce résultat. On a seulement une injection de $F$ dans $n$ (on bute à montrer que cette injection ne peut pas être une bijection, il faudrait montrer qu'il ne peut pas y avoir de bijection entre $F$ et $E$, or c'est ce qu'on veut montrer), puis par cette injection l'image de $F$ est équivalente à un sous-ensemble de $n$, mais rien ne dit que ce sous-ensemble est propre (i.e. que l'injection $F \hookrightarrow E$ ne peut pas être une bijection). Bref on tourne en rond.

En effet, c'est faux pour des ensembles infinis (un ensemble infini peut être équivalent à un sous-ensemble propre).

Je crois en effet qu'on ne peut s'en sortir qu'avec une induction, à l'instar de la démo habituelle que je viens de voir dans un cours de MPSI (mais rien de simple).

Maxtimax

Beh tu composes la bijection $E\to n$ avec l'injection $F\to E$. La seconde est injective, donc si la première n'est pas surjective (i.e. $F$ est propre) la composée ne l'est pas non plus !

Julia Paule

Tout est là. $F$ propre $\Rightarrow$ l'injection $F \hookrightarrow E$ n'est pas surjective, donc la composée n'est pas surjective. Alors si $F \sim n$, il existe une injection non surjective $n \hookrightarrow n$, donc il existe une bijection entre $n$ et un sous-ensemble propre $m$ de $n$, donc on a à la fois $m \sim n$, ce qui implique que $m=n$, et $m<n$, i.e. $m \in n$, les deux sont incompatibles. Donc $F$ n'est pas équivalent à $n$, donc $E$ n'est pas équivalent à $F$.

Merci beaucoup Maxtimax.

Ce qui m'embrouille, c'est que $n$ désigne à la fois un élément et une partie du même ensemble ($n^+=n \cup \{n \}$), donc on ne sait pas a priori ce que $n$ désigne, mais en fait c'est la même chose, il faut s'y faire.

Chaurien

De quel livre s'agit-il ?

Julia Paule

C'est l'Introduction à la théorie des ensembles de Paul R. Halmos.

Thierry Poma

Lire : on a montré que $n$ entier naturel n'est pas équipotent (i.e. en bijection) à un sous-ensemble propre de $n$.

Julia Paule

Oui j'ai dû le voir passer, mais n'en suis pas sûre.

Le livre utilise "équivalent" pour "équipotent", et "nombre naturel" pour "entier naturel", mais pour ce dernier, j'ai fait la traduction.

Thierry Poma

@Julia : Halmos emploie l'adjectif "equivalent" en anglais. De nos jours, l'on dit "équipotent". Enfin, moi, ça me choque.

Julia Paule

C'est la traduction française, où "équivalent" a été conservé. Cela ne me gêne pas.

christophe c

Pour faire un post court, soit $p:=n+1$ avec $n>0$ un entier et $f$ une injection de $p\to p$. Soit $a\in p$ sans antécédent par $f$.

En composant à gauche $f$ avec une transposition, on peut supposer en plus que $a=n$, de sorte que $f$ est à valeurs dans $n$ et pas seulement dans $n+1$.

En composant à droite $f$ par ce qu'il faut, $f(n)=n-1$ de sorte que $f_{|n}$ injecte $n$ dans $n-1$ et n'est donc elle-même pas surjective.

"toute injection est surjective" vérifie donc ce qu'il faut pour que l'axiome (ou propriété) de récurrence donne cette propriété à tout entier.