1 Ensembles (au plus) dénombrables

L’inverse est $h\mapsto h^{-1}\left(\left\{1\right\}\right)$. La vérification que c’est bien un inverse est facile, et laissée en exercice.   □

1. Si $P$ est non-vide et donc, disons, contient $n$, alors $[[0,n]]\cap P$ est aussi non-vide et FINI, donc a clairement un minimum. 2. Il suffit de voir le deuxième cas (en restreignant aux segments initiaux), on le montre par récurrence sur $n$. Si $n=0$ , $f\left(0\right)\in \mathbb{N}$ donc c’est évident. En supposant l’hypothèse vraie au rang $n$, on considère $f:[[0,n+1]]\to \mathbb{N}$, la restriction à $[[0,n]]$ vérifie l’hypothèse de récurrence, donc $f\left(p\right)\ge p$ pour $p\le n$ et $f\left(n+1\right)>f\left(n\right)\ge n$ mais dans $\mathbb{N}$ cela implique $f\left(n+1\right)\ge n+1$ et conclut l’étape d’induction.   □

Les ensembles au plus dénombrables sont par définition en bijection avec les parties de $\mathbb{N}$. Dans le cas infini, il suffit de voir le second point pour obtenir la bijection avec $\mathbb{N}$. On définit par récurrence la bijection $f:{\mathbb{N}}^{\ast }\to P$. Plus précisément, on construit par récurrence sur $n$ une application strictement croissante $f_n:[[1,n]]\to P$ telle que pour tout $x\in Im\left(f_n\right),y\in P-Im\left(f_n\right)$, et ${f_n|}_{[[1,k]]}=f_k$. Comme $P$, infini, il est non-vide donc admet un élément $a_0=\min \left(P\right)$ On pose $f_0\left(0\right)=a_0$ d’où l’initialisation.

On suppose construit $f_n$, et on prend $a_{n+1}=min\left(P-Im\left(f_n\right)\right)$ qui existe car cette partie est infinie de $\mathbb{N}$ donc non vide (si elle n’était pas infinie, P serait finie comme union finie de parties finies). On pose $f_{n+1}\left(k\right)=f_n\left(k\right),k\le n,f_{n+1}\left(n+1\right)=a_{n+1}$ de sorte que par l’hyp de rec sur $f_n,$ $a_{n+1}>f_n\left(k\right),k\le n$ ce qui donne la stricte croissance de $f_{n+1}$ en combinant avec celle de $f_n$. Enfin, si $y\in P-Im\left(f_{n+1}\right)\subset P-Im\left(f_n\right)$ on a par hyp de rec $y>f_n\left(k\right)k\le n$ et $y>a_{n+1}$ car c’est le min donc $\ge$ et on a $y\ne a_{n+1}$ par construction. Donc la relation demandée à l’étape suivante est vérifiée.

On obtient $f$ strictement croissante donc injective en rassemblant les valeurs des $f_n$ qui s’accordent ($f\left(n\right)=f_n\left(n\right)=f_m\left(n\right),m\ge n$).

Pour voir que $f$ bijective, par l’absurde, sinon il existe $b\in P-Im\left(f\right)$ mais par stricte croissance d’entiers $f\left(n\right)\to \mathrm{\infty }$ donc il existe $n$ minimal tel que ce qui impose par minimalité $b>f\left(n-1\right)$ et contredit $f_n\left(n\right)=Min\left(P-Im\left(f_{n-1}\right)\right)$ vu $b\in P-Im\left(f_{n-1}\right)$.

Pour l’unicité, si $g$ est une autre telle bijection $g^{-1}\circ f$ est une bijection strictement croissante de $\mathbb{N}\to \mathbb{N}$ ainsi que sa réciproque et le lemme 1.2 donne donc $g^{-1}\circ f\left(n\right)\ge n,f^{-1}\circ g\left(n\right)\ge n$ et donc, d’où par croissance de $g,f$ appliquée encore à ces relations: $f=g$.   □

Pour l’implication directe, si $P$ est dénombrable, la bijection de la définition convient, si $P$ est fini, en bijection avec $[[0,n-1]]$ alors le reste modulo $n$ donne la surjection $\mathbb{N}\to [[0,n-1]]$ qui composée à la bijection donne la surjection cherchée. Réciproquement, l’ensemble $f^{-1}\left(p\right),p\in P$ est une partie de $\mathbb{N}$ qui a un plus petit element $a_p$: $a:P\to \mathbb{N}$ est l’injection cherchée.   □

1. Soit $a_n=Card\left(X_n\right)$ et $A_n={\displaystyle \sum _{k=0}^n}{a}_k$ ($A_{-1}=0$). On a des bijections $h_n:[[A_{n-1}+1,A_n]]\to [[1,a_n]]\to X_n$ qui induisent une application $h:{\mathbb{N}}^{\ast }\to {\cup }_n{X}_n$ dès qu’un nombre infini de $X_i$ n’est pas vide, ou $h:[[1,A_p]]\to {\cup }_n{X}_n$ qui est par construction surjective. L’injectivité des $h_n$ et le fait que les $X_n$ sont disjoints donne l’injectivité de $h$. 2. Si $X$ est fini on prend la suite constante, sinon, pour une bijection $h:\mathbb{N}\to X$ on prend $X_n=h\left([[0,n]]\right)$ comme suite croissante cherchée. Réciproquement, la suite croissante $X_n$ donne une suite disjointe $X_0$, $X_{n+1}-X_n$ de parties finies, donc 1 donne que l’union est au plus dénombrable.

3. Une récurrence triviale ramène au cas du produit de 2 ensembles $A,B$. Soit $h:\mathbb{N}\to A$, $g:\mathbb{N}\to B$ des surjections données par la proposition 1.4. $f=h\times g:{\mathbb{N}}^2\to A\times B$ est une surjection qui ramène au cas ${\mathbb{N}}^2$ qui admet pour suite exhaustive d’ensembles finis ${[[0,n]]}^2$.   □

On a vu le cas du produit ${\mathbb{N}}^k$ au lemme précédent. $[[-n,n]]$ est une suite exhaustive d’ensemble fini pour $\mathbb{Z}$ qui est donc au plus dénombrable par la proposition précédente, il est infini car il contient $\mathbb{N}$. Enfin $(p,q)\mapsto p/q$ est une surjection de $\mathbb{Z}\times {\mathbb{N}}^{\ast }\to \mathbb{Q}$, donc, par la proposition 1.4, $\mathbb{Q}$ est au plus dénombrable, et infini car il contient $\mathbb{N}$.   □

Soit ${\left(X_n\right)}_{n\ge 0}$ une suite d’ensembles dénombrables (si la suite est finie, on peut la prolonger en une suite infinie.). Soit $f_n:\mathbb{N}\to X_n$ une surjection donnée par la proposition 1.4. Petite subtilité, on a besoin de former une suite ${\left(f_n\right)}_{n\in \mathbb{N}}$, c’est à dire une application de $\mathbb{N}\to {\left({\displaystyle \bigcup _{n\in \mathbb{N}}}{X}_n\right)}^{\mathbb{N}}$, ce qui n’est pas complètement anodin et utilise l’axiome du choix dénombrable). On pose $f:{\mathbb{N}}^2\to {\displaystyle \bigcup _{n\in \mathbb{N}}}{X}_n$ défini par $f(n,p)=f_n\left(p\right)$ et en composant avec une surjection $\mathbb{N}\to {\mathbb{N}}^2$, on obtient le résultat par la réciproque dans la proposition juste citée.   □

En effet une application $h:E\to 𝒫\left(E\right)$ permet de considérer l’ensemble $A=\{x\in E:x\notin h\left(x\right)\}$. Il n’existe pas de $y$ tel que $h\left(y\right)=A$ car par l’absurde, si il existait, soit $y\in A$ et alors $y\notin h\left(y\right)=A$ une contradiction, soit $y\notin A$ et alors $y\in h\left(y\right)=A$ encore une contradiction.   □

On construit une injection $\phi :{\left\{\mathrm{0,1}\right\}}^{\mathbb{N}}\to \left[\mathrm{0,1}\right]$ (le cas $ℝ$ s’en déduit. (l’image de cette injection va être l’ensemble triadique de Cantor). On fixe $a=\left(a_n\right)\in {\left\{\mathrm{0,1}\right\}}^{\mathbb{N}}$ on définit une suite de segments emboîtés, on pose $J_0=\left[\mathrm{0,1}\right]$ et si $J_n=[x_n,y_n]$ alors on découpe l’intervalle en trois en posant $u_n=\left(2x_n+y_n\right)/3$ et $v_n=\left(x_n+2y_n\right)/3.$ Si $a_n=0$, on pose $J_{n+1}=[x_n,u_n]$, et si $a_n=1$, on pose $J_{n+1}=[v_n,y_n].$ On obtient par construction une suite de segments emboîtés, $x_n,y_n$ sont des suites adjacentes et $y_n-x_n\le 1/3^n$ (récurrence facile) donc l’intersection est un singleton ${\cap }_n{J}_n=\left\{\phi \left(a\right)\right\}.$

Pour voir que $\phi$ est injective on note que si $a\ne a^{\prime }$ sont deux suites et $n$ le premier indice avec $a_n\ne a_n^{\prime }$, alors $J_n\cap J_n^{\prime }=\mathrm{\emptyset }$ et les images sont donc distinctes.   □