Montrer qu'un ensemble est dénombrable : méthodes

Un ensemble $E$ est dit dénombrable s'il est en bijection avec $\mathbb{N}$ (ou fini, selon la convention). Voici les principales techniques pour le démontrer.

Définition

Un ensemble $E$ est dénombrable s'il existe une bijection $f : \mathbb{N} \to E$. Autrement dit, on peut numéroter tous ses éléments : $e_0, e_1, e_2, \dots$

Convention : certains auteurs distinguent « dénombrable » (bijection avec $\mathbb{N}$, i.e. infini dénombrable) et « au plus dénombrable » (fini ou dénombrable). Nous utilisons ici « dénombrable » au sens large.

Méthode 1 : bijection explicite

Construire une bijection $f : \mathbb{N} \to E$. Exemple classique : $\mathbb{Z}$ est dénombrable via $f(n) = (-1)^n \lfloor n/2 \rfloor$ qui donne la suite $0, -1, 1, -2, 2, -3, \dots$

C'est la méthode la plus directe mais parfois laborieuse.

Méthode 2 : injection dans N

S'il existe une injection $g : E \hookrightarrow \mathbb{N}$, alors $E$ est au plus dénombrable. En effet $g$ est une bijection de $E$ vers $g(E) \subseteq \mathbb{N}$.

Exemple : l'ensemble des nombres premiers est dénombrable (c'est un sous-ensemble de $\mathbb{N}$, donc il suffit de l'identité).

Méthode 3 : union dénombrable

Une union dénombrable d'ensembles dénombrables est dénombrable : $\bigcup_{n \in \mathbb{N}} E_n$ est dénombrable si chaque $E_n$ l'est.

Application : $\mathbb{Q}$ est dénombrable. On écrit $\mathbb{Q} = \bigcup_{n \geq 1} \{p/n \mid p \in \mathbb{Z}\}$. Chaque ensemble $\{p/n\}_{p \in \mathbb{Z}}$ est en bijection avec $\mathbb{Z}$, donc dénombrable.

Méthode 4 : argument diagonal de Cantor (N×N)

$\mathbb{N} \times \mathbb{N}$ est dénombrable. On parcourt les diagonales : $(0,0), (1,0), (0,1), (2,0), (1,1), (0,2), \dots$ La bijection est $f(i,j) = \frac{(i+j)(i+j+1)}{2} + j$.

Cela permet de montrer que tout produit fini d'ensembles dénombrables est dénombrable.

Une question ou une suggestion ? Écrivez-nous.