Ensemble dénombrable. $\mathbb Z$ et $\mathbb N \times \mathbb N$ sont dénombrables.

Un ensemble est dénombrable s'il est en bijection avec $\mathbb N$, l'ensemble des entiers naturels. 

Si un ensemble $F$ est en bijection avec un ensemble $E$ dénombrable, alors $F$ est dénombrable. En effet, si $\varphi$ réalise une bijection $E\longrightarrow F$, et si $\alpha : \mathbb N \longrightarrow E$, alors $\varphi \circ \alpha$ est une bijection $F\longrightarrow \mathbb N$.

Réciproquement, si $E$ et $F$ sont des ensembles dénombrables, alors ils sont en bijection.

Dans cet article, je donnerai plusieurs exemples d'ensembles dénombrables et plusieurs propriétés permettant de construire des ensembles dénombrables. Enfin, je citerai quelques ensembles non dénombrables.

Dénombrabilité de $\mathbb Z$

Propriété 1. $\mathbb Z$ est dénombrable.

Preuve. On construit la fonction 

$$\varphi : \mathbb N \longrightarrow \mathbb Z$$ définie par 

$$\varphi(n)=\left\{\begin{array}{ccc}\frac{n}{2} & \textrm{si} & n \textrm{ est pair}\\ -\frac{n+1}{2} &\textrm{si}  & n \textrm{ est impair} \end{array}  \right.$$

$\varphi$ est injective. En effet deux nombres pairs ne peuvent  avoir la même image que s'ils sont égaux. De même deux nombres impairs ne peuvent avoir la même image que s'ils sont égaux. Si deux nombres non-nuls n'ont pas la même parité, leurs images sont de signes strictement opposés. Enfin seul zéro a pour image zéro.

$\varphi$ est surjective. Soit $m\in\mathbb Z$. Si $m\geq 0$, alors $\varphi(2m)=m$. Si $m<0$, alors $\varphi\left(-1-2m \right)=m$.  

$\mathbb N \times N$ est dénombrable

Propriété 2. 

a) $\mathbb N \times \mathbb N$ est en bijection avec $\mathbb N$. Autrement dit $\mathbb N^2=\mathbb N \times \mathbb N$ est dénombrable.

b) Si $E$ et $F$ sont dénombrables, alors $E\times F$ est dénombrable.

Preuve. 

a) Construisons une bijection $\alpha : \mathbb N \longrightarrow \mathbb N \times \mathbb N$.

Soit $\alpha:\mathbb N\longrightarrow \mathbb N\times \mathbb N$ définie par récurrence comme expliquée ci-dessous :

• $\alpha(0)=(0,0)$
• $\alpha(1)=(0,1)$, $\alpha(2)=(1,0)$
• $\alpha(3)=(2,0)$, $\alpha(4)=(1,1)$, $\alpha(5)=(0,2)$

On note pour tout entier naturel $n\geq 1$, $s_n=1+2+\ldots+n=\frac{n(n+1)}{2}$ (voir l'article sur les suites arithmétiques). On pose $s_0=0$ (la "somme vide").

On a $s_0=0$, $s_1=1$, $s_2=3$, etc. On a $s_0<s_1<s_2<\ldots$ avec $\lim_n s_n=+\infty$. On remarque au passage que pour tout entier naturel $p$, il existe un entier $q$ tel que $s_q\leq p < s_{q+1}$.

Faisons maintenant la remarque suivante. Pour tout entier naturel $k$, il existe $k+1$ décompositions de $k$ sous la forme $k=i+j$, avec $i,j$ entiers naturels. En effet $i$ peut prendre les valeurs de $0$ à $k$, auxquels correspondent les valeurs $j=k-i$.

Pour passer de l'étape $k$ à l'étape $k+1$, on suppose que l'on a défini : 

$\alpha(0),\alpha(1),\ldots,\alpha(s_k),\alpha(s_k+1),\ldots,\alpha(s_k+k)$, avec pour tout entier naturel $\ell\leq k$ : $\alpha(s_\ell+i)=(i,\ell-i)$.

Autrement dit pour tout entier naturel $\ell\leq k$ et pour tous $i,j$ entiers naturels tels que $\ell=i+j$, on a $\alpha(s_{i+j}+i)=(i,j)$.

A l'étape suivante, l'étape $k+1$, on pourra ainsi définir $k+1$ nouvelles valeurs de $\alpha$ : $\alpha(s_k+k+1),\ldots,\alpha(s_k+k+1+k+1)$. En effet cela correspond aux $k+1$ façons de décomposer $k+1$ sous la forme $i+j$ avec $i,j$ entiers naturels. 

Par ailleurs, comme $s_k+k+1=1+\ldots+k+(k+1)=s_{k+1}$, on définit pour tout entier $i$ tel que $0\leq i \leq k+1$ : $\alpha(s_{k+1}+i)=(i,k+1-i)$.

Ainsi on définit pour tout entier naturel $n$, $\alpha(n)$. 

La fonction $\alpha$ est surjective car si $i,j$ sont deux entiers naturels on peut trouver un antécédent de $(\varphi(i),\psi(j))$ par $\alpha$. Pour cela posons $k=i+j$, et prenons $n=s_k+i$. On a par construction de $\alpha$, $\alpha(n)=(i,k-i)=(i,j)$. 

Par construction la fonction $\alpha$ est injective. Pour le montrer supposons que $\alpha(p_1)=\alpha(p_2)=(q,i)$. 

Alors il existe $q_1$ tel que $s_{q_1}\leq p_1<s_{q_1+1}$. De même, il existe $q_2$ tel que $s_{q_2}\leq p_2<s_{q_2+1}$. 

On pose $p_1=q_1+i_1$ et $p_2=q_2+i_2$.

On a donc $q_1=q=q_2$ et $i_1=i=i_2$. Donc $p_1=p_2$.

b) Soit $\varphi : \mathbb N \longrightarrow E$ et $\psi : \mathbb N \longrightarrow F$ deux bijections. 

Soit $\alpha:\mathbb N\longrightarrow \mathbb N \times\mathbb N$ définie précédemment. 

On définit $p_1:\mathbb N \times \mathbb N \longrightarrow \mathbb N$ et $p_2:\mathbb N \times \mathbb N \longrightarrow \mathbb N$ par $p_1(x,y)=x$ et $p_2(x,y)=y$. Ainsi on a 

$$(\ast) \ \ \ \ \ (x,y)=(p_1(x,y),p_2(x,y))$$

On définit $\theta:\mathbb N \longrightarrow E\times F$ par $n\longrightarrow (\varphi(p_1(\alpha(n))),\psi(p_2(\alpha(n))))$. 

$\theta$ est une bijection. Elle est injective car $\theta(n)=\theta(m)$ implique $\varphi(p_1(\alpha(n)))=\varphi(p_1(\alpha(m)))$ et $\psi(p_2(\alpha(n)))=\psi(p_2(\alpha(m)))$ d'où par injectivié de $\phi$ et $\psi$ : $p_1(\alpha(n))=p_1(\alpha(m))$ et $p_2(\alpha(n))=p_2(\alpha(m))$. D'après $(\ast)$, on a donc 

$$(\alpha(n),\alpha(n))=(p_1(\alpha(n)),p_2(\alpha(n)))=(p_1(\alpha(m)),p_2(\alpha(m)))=(\alpha(m),\alpha(m))$$

D'où l'on déduit que $\alpha(n)=\alpha(m)$. $\alpha$ étant bijective $n=m$. 

$\theta$ est aussi surjective. En effet, soit $(a,b)\in E\times F$. On pose $(x,y)=\left(\varphi^{-1}(a),\psi^{-1}(b)\right)$, $(x,y)\in \mathbb N \times \mathbb N$. On pose 

$$n=\alpha^{-1}(x,y)=\alpha^{-1}\left(\varphi^{-1}(a),\psi^{-1}(b)\right)$$

On a $p_1(\alpha(n))=p_1(x,y)=x$ et de même $p_2(\alpha(n))=y$. Donc 

$\theta(n)=(\varphi(x),\psi(y))=(a,b)$. D'où la surjectivité.

On a donc montré que $\theta$ est bijective. 

Remarque. 

Définissons $\pi_1:E \times F \longrightarrow E$ et $\pi_2: E \times F \longrightarrow F$ par $\pi_1(a,b)=a$ et $\pi_2(a,b)=b$. Ainsi on a 

$$(\ast \ast) \ \ \ \ \ (a,b)=(\pi_1(a,b),\pi_2(a,b))$$

Ainsi $\theta^{-1}(a,b)=\alpha^{-1}\left(\varphi^{-1}(\pi_1(a,b)),\psi^{-1}(\pi_2(a,b))\right)$.

Produit cartésien d'ensembles dénombrables

Propriété 3. Si $E_1,E_2,\ldots,E_n$ sont $n$ ensembles dénombrables, alors $E_1\times E_2\times \ldots \times E_n$ est dénombrable.

En particulier si $E$ est dénombrable et si $n\geq 1$ est un entier, alors $\mathbb N^n$ est dénombrable.

Preuve. Dans cette démonstration, chaque $E_i$ réprésente un ensemble dénombrable. On utilise le théorème de récurrence. 

Si $n=1$, il n'y a rien à démontré.

Supposons que pour un certain entier $k\geq 1$, le produit cartésien $E_1\times \ldots\times E_k$ est dénombrable. Alors $\left(E_1\times \ldots\times E_k \right)\times E_{k+1}$ est dénombrable. 

Or $\left(E_1\times \ldots\times E_k \right)\times E_{k+1}$ est en bijection avec $E_1\times\ldots \times E_k\times E_{k+1}$ via la fonction $\phi\left((x_1,\ldots,x_k),x_{k+1}\right)=(x_1,\ldots,x_k,x_{k+1})$. 

On en déduit que $E_1\times\ldots E_k\times E_{k+1}$ est dénombrable.

La propriété est donc démontrée.

Autres exemples d'ensembles dénombrables

Dans un article ultérieur, nous pourrons voir que $\mathbb Q$ est un ensemble dénombrable.