Sous-ensembles de $\mathbb N$. Dénombrabilité de $\mathbb Q$.

 Cet article fait suite à :

• Ensemble fini.
• Ensemble dénombrable. Produit fini d'ensembles dénombrables. $\mathbb Z$ et $\mathbb N\times \mathbb N$ sont dénombrables.

Pour la contruction de $\mathbb Q$, on pourra se reporter à cet article.

Nous verrons plus bas quelques propriétés : 

• l'image de $\mathbb N$ par une injection est un ensemble dénombrable
• les sous-ensembles de $\mathbb N$ sont soit finis soit dénombrables

Image de $\mathbb N$ par une injection

Propriété A. S'il existe une injection $\mathbb N \longrightarrow E$, alors $E$ n'est pas un ensemble fini. 

Démonstration. Supposons qu'il existe un $n$ entier tel qu'il existe une bijection $\varphi:E_n \longrightarrow E$. Notons $\alpha:\mathbb N \longrightarrow E$ une injection. 

Alors $\varphi^{-1}\circ \alpha : \mathbb N \longrightarrow N_n$ est une injection. Par injectivité de $\beta=\varphi^{-1}\circ \alpha$,  $\beta(1),\ldots,\beta(n),\beta(n+1)$ sont des éléments de $\mathbb N_n$. D'après le principe des tiroirs, au moins deux de ses éléments sont égaux contredisant l'injectivité de $\beta$.

Il est donc impossible que $E$ soit un ensemble fini.

Propriété B. Soit $f:E\longrightarrow F$ une fonction injective. Alors la fonction $\tilde f:E \longrightarrow f(E)$ définie pour tout $x\in E$ par $\tilde{f}(x)=f(x)$, est une bijection.

Démonstration. Clairement $\tilde f$ est injective. 

Pour la surjectivité, soit $y\in f(E)$. Il existe par définition de $f(E)$ un élément $x\in E$ tel que $f(x)=y$. 

Lemme C1. Si $F$ n'est pas de cardinal fini, et si $x_1,\ldots,x_r$ sont $r$ éléments de $F$, alors l'ensemble 

$$F'=F\setminus\left\{x_1,\ldots,x_r \right\}$$

n'est pas vide et n'est pas de cardinal fini.

Démonstration. On fait une récurrence sur $r$. 

Initialisation. Si $r=1$, $F'=F\setminus\left\{x_1\right\}$. $F'$ n'est pas vide car sinon $F$ serait de cardinal 1. Si $F'$ était de cardinal fini, on aurait $F'=\left\{a_1,\ldots,a_t \right\}$ et $F=\left\{a_1,\ldots,a_t \right\}\cup \left\{x_1\right\}$ contiendrait exactement $t+1$ éléments contredisant le fait que $F$ est fini.

Hérédité. Supposons que si $x_1,\ldots,x_k$ sont $k$ éléments de $F$, alors l'ensemble 

$$F'=F\setminus\left\{x_1,\ldots,x_k \right\}$$

n'est pas vide et n'est pas de cardinal fini.

Soit $x_{k+1}$ un autre élément de $F$. Comme $F'$ est infini, d'après le cas $r=1$, on en déduit que $F''=F'\setminus\left\{x_{k+1} \right\}=F\setminus\left\{x_1,\ldots,x_k,x_{k+1} \right\}$ n'est pas de cardinal fini.

Conclusion. Le lemme est démontré.

Lemme C2. Si une suite d'entier naturel $(n_k)$ est strictement croissante, alors, elle n'est pas majorée.

Preuve. Soit $A$ un nombre réel. Soit $N_A$, le premier entier supérieur ou égal à $A$. 

On montre à l'aide d'une récurrence que $n_{N_A}\geq n_0+N_A\geq N_A \geq A$. Ainsi, $(n_k)$ n'est pas majorée.

Propriété C. Soit $F\subset \mathbb N$ un sous-ensemble qui n'est pas de cardinal fini. 

Alors $F$ est dénombrable.

Autrement dit, un sous-ensemble de $\mathbb N$ est soit fini soit dénombrable. On dit qu'il est au plus dénombrable.

Démonstration. On va construire une fonction bijective $\varphi:F\longrightarrow \mathbb N$.

On note $F_0=F$ et $n_0=\min F_0$ le plus petit élément de $F_0$. 

On pose et $F_1=F\setminus\left\{n_0 \right\}$ et $n_1=\min F_1$. Il n'y a pas de problème car d'après le lemme, $F_1$ n'est pas vide. On a $n_0<n_1$. De plus il n'y a aucun élément de $F$ entre $n_0$ et $n_1$, par minimalité de $n_1$. 

Supposons qu'à l'étape $k$ on a $n_0<n_1<\ldots<n_k$, $k+1$ éléments tels qu'il n'existe aucun élément de $F$ entre deux $n_i$ consécutifs. D'après le lemme $F_{k+1}=F\setminus\left\{n_0,n_1,\ldots,n_k,n_{k+1} \right\}$ est non-vide ; il possède donc un plus petit élément $n_{k+1}$. Par minimalité de $n_k$, $n_k<n_{k+1}$ et par minimalité de $n_{k+1}$, il n'existe pas non-plus d'élément de $F$ entre $n_k$ et $n_{k+1}$.

Par récurrence, on construit donc une suite d'éléments $(n_i)$ de $F$, tels que :

$$n_0<n_1<\ldots<n_k <n_{k+1}<\ldots$$

pour laquelle pour tout entier $k$ il n'y a jamais d'élément de $F$ entre deux $n_k$ et $n_{k+1}$. 

Pour tout $k$, on pose $\varphi(k)=n_k$.

La fonction $\varphi$ est injective car la suite $(n_k)$ est strictement croissante. 

La fonction $\varphi$ est surjective. Soit en effet, $y\in F \mathbb N$. La suite $(n_k)$ n'est pas majorée. En effet, elle répond aux conditions du lemme C2. Donc il existe $n_s$ tel que $n_s\geq y$. Soit $n_r$ le plus petit élément de $(n_k)$ supérieur ou égal à $y$. Par construction de la suite $(n_k)$, $y$ n'est pas compris entre $n_r$ et $n_{r+1}$, donc $y=n_r$. Ainsi $y=\varphi(r)$.   

Propriété D. S'il existe une injection $E \longrightarrow \mathbb N$ est que $E$ n'est pas fini, alors $E$ est dénombrable.

Si $F'\subset F$ avec $F'$ de cardinal non-fini et $F$ dénombrable, alors $F'$ est dénombrable.

Démonstration. Soit $j:E\longrightarrow \mathbb N$ une injection. Alors d'après la propriété B, $\tilde j : E \longrightarrow j(E)$ définit une bijection. $E$ n'étant pas fini, $j(E)$ n'est pas fini. D'après la propriété C, $j(E)$ est donc dénombrable. 

Soit $\psi:\mathbb N \longrightarrow j(E)$ une bijection. Alors $j^{-1}\circ \psi$ établit une bijection entre $\mathbb N$ et $E$. $E$ est donc dénombrable. 

Soit $j:F'\longrightarrow F$ l'inclusion naturelle donnée par $j(x)=x$. C'est une fonction injective. Soit $\varphi:\mathbb N\longrightarrow F$ une bijection. Alors $\varphi^{-1}\circ j : F' \longrightarrow \mathbb N$ est injective comme composée de deux fonctions bijective. On en déduit que $F'$ est dénombrable.

Dénombrabilité de $\mathbb Q$

Propriété. $\mathbb Q$ est dénombrable.

Remarque. Pour la construction de $\mathbb Q$, on pourra se reporter à cet article.

Démonstration. 

On pourra se référer à l'article $\mathbb Z$, produit cartésien d'ensembles dénombrables.

Puisque $\mathbb Z^{\star}\subset \mathbb Z$ et que $\mathbb Z$ est dénombrable, $\mathbb Z^\star$ est dénombrable. (Ainsi $\mathbb Z \times \mathbb Z^\star$ est dénombrable.) 

Soit $E \subset \mathbb Z \times \mathbb Z^\star$ l'ensemble des couples $(a,b)$ tels que $b$ est strictement positif et $a\neq 0$ et $b$ sont premiers entre eux. 

Soit $\varphi : E \longrightarrow Q^\star$ définie par $\varphi(a,b)=\frac a b$. Alors $\varphi$ est surjective car tout rationnel non-nul peut s'écrire sous la forme $\frac a b$ avec $a,b$

premiers entre eux et $b$ strictement positif : c'est la forme irréductible.  $\varphi$ est injective car la forme irréductible avec le dénominateur strictement positif est unique. 

Donc $E$ est en bijection avec $\mathbb Q^\star$. Si on ajoute $(0,0)$ à $E$, et qu'on définit $\varphi(0,0)=0$, on obtient une bijection entre $E'=E\cup\left\{(0,0)\right\}$ et $\mathbb Q$. $\mathbb Q$ contient $\mathbb Z$ donc $\mathbb Q$ n'est pas de cardinal fini, a fortiori $E'$ n'est pas de cardinal fini. Puisque $E'\subset \mathbb Z \times \mathbb Z$, $j:E'\longrightarrow \mathbb Z \times \mathbb Z$ définie par $j(x)=x$ est injective. On en déduit que $E'$ est dénombrable. Ainsi $\mathbb Q$ est dénombrable.

A suivre

Dans de prochains articles, on pourra s'intéresser :

• A la réunion d'ensembles dénombrables
• A des exembles d'ensembles non-dénombrables