La dénombrabilité : Cours et exercices corrigés

Cet article a pour but de présenter la notion de dénombrabilité en la définissant et en proposant quelques exercices corrigés autour de ce thème. Cette notion est accessible dans les études supérieures

Cours

Définition de la dénombrabilité

Un ensemble E est dit dénombrable s’il existe une bijection entre \N et E

Un ensemble E est dit au plus dénombrable s’il existe une bijection entre une partie de \N et E

Et voici une propriété qui peut paraitre parfois surprenante : L’union au plus dénombrable d’ensembles au plus dénombrables est dénombrable

Exemples d’ensembles dénombrables

Voici quelques ensembles dénombrables bien connus :

• \N évidemment !
• \N^*
• \N^2
• \N^r, r \in \N, r \geq 2
• \Z
• \mathbb{Q}
• L’ensemble \mathbb{P} des nombres premiers
• L’ensemble des termes d’une suite est au plus dénombrable

Voici quelques ensembles qui ne sont pas dénombrables

• \R
• \mathbb{C}
• \N^{\N}

Exercices corrigés

Exercice 1

Enoncé : Montrer que \Z est dénombrable.

Corrigé : On peut poser la fonction f: \N \to \Z définie par

f(n) = \left\{
\begin{array}{ll}
\dfrac{-n}{2} & \text{si } n =2k\\
\dfrac{n+1}{2} & \text{si } n =2k+1\\
\end{array}
\right.

D’une part, f est bien injective : si n,m \in \N vérifient f(n) = f(m) alors ils sont nécessairement de même parité :

• Soit ils sont tous les deux pairs et dans ce cas \dfrac{-n}{2}=\dfrac{-m}{2} \iff n=m
• Soit ils sont tous les deux pairs et dans ce cas \dfrac{n+1}{2}=\dfrac{m+1}{2} \iff n=m

D’autre part, f est surjective. En effet :

• Soit k \in \N^*. Alors, f(2k-1) = \dfrac{2k-1+1}{2} = k
• Soit k \in \Z^-. Alors, f(-2k) = \dfrac{-(-2k)}{2} = k

Exercice 2

Enoncé : Montrer que \N^2 est dénombrable.

Corrigé : On pose f : \N^2 \to \N définie par

\forall a,b \in \N, f(a,b) = 2^a(2b+1)-1

La fonction f est injective. En effet,

\begin{array}{ll}
&f(a,b) = f(a',b') \\
\iff & 2^a(2b+1)-1= 2^{a'}(2b'+1)-1\\
\iff & 2^a(2b+1)= 2^{a'}(2b'+1)\\
\iff & \left\{ \begin{array} {l}
2^a  = 2^{a'}\\
2b+1 = 2b'+1
\end{array}\right.\\
\iff & \left\{ \begin{array} {l}
a =a'\\
b = b'
\end{array}\right.
 \end{array}

On a pu séparer les deux termes car d’un côté l’un est une puissance de 2, l’autre est un nombre impair et ne contient pas de puissance de 2. C’est le théorème des nombres premiers qui nous permet de justifier cela.

De plus, la fonction est bien surjective. Là aussi, on utilise le théorème des nombres premiers pour dire qu’il existe une unique combinaison (à une permutation près) de nombres premiers p_1, \ldots, p_k et leurs puissances qui sont des entiers \alpha_1, .., \ldots, \alpha_k . Soit n un entier. n +1 est non nul. On peut alors écrire

n +1  =p_1^{ \alpha_1} \ldots p_k^{\alpha_k}

Si le nombre n+1 est pair alors l’un des p_i vaut 2. On l’isole, le reste des termes est un nombre de nombres impairs et peut donc s’écrire 2b+1 . On a donc

n +1  =2^{r_i}(2b+1) \iff n = 2^a (2b+1)-1

Ce qui est un résultat sous la bonne forme.

Conclusion : \N et \N^2 sont en bijection. Donc \N^2 est dénombrable.

Bonus : En déduire que \mathbb{Q}est dénombrable et que \N^r l’est aussi !

Exercice 3

Enoncé : On dit qu’un réel x est un nombre algébrique s’il est racine d’un polynôme non nul à coefficients entiers :

\exists d \in \N^*, (a_0, \ldots, a_d) \in \Z, a_d \neq 0, \sum_{k=0}^d a_k x^k = 0 

Le plus petit d qui convient s’appelle alors le degré de x.

1. Montrer que l’ensemble des nombres algébriques de d est dénombrable
2. Montrer que l’ensemble des nombres algébriques est dénombrable

Corrigé :

Question 1 :

Soit a = (a_0, \ldots, a_d) \in \Z^d \times \Z^* = A_d

On définit E_a par

D_a  = \{x \in \R , \sum_{k=0}^d a_k x^k = 0 \}

Un polynômes de degré a au plus d racines donc c’est un majorant du cardinal de D_a . L’ensemble des nombres algébriques de degré au plus d est donc défini par :

Al_d = \cup_{a \in A_d} D_a 

qui est donc au plus dénombrable en tant qu’union dénombrable d’ensembles finis. Et elle est bien dénombrable car on a au moins les entiers qui appartiennent à cet ensemble.

Question 2 : Notons Al l’ensemble des entiers algébriques. On a, en reprenant la notation de la question précédente :

Al = \cup_{d \in \N} Al_d

Ce qui nous permet de conclure car c’est une union dénombrable d’ensembles dénombrables.

Ce qui termine ce troisième exercice sur la dénombrabilité.