Dénombrabilité

Définition intuitive

Pour un ensemble fini, le cardinal mesure naturellement le « nombre d’éléments ». Mais cette approche atteint sa limite dès qu’on considère un ensemble infini : on ne peut pas « compter » ses éléments un par un, puisque le comptage ne s’arrête jamais.

L’idée clé pour contourner ce problème est de comparer des ensembles sans les compter, uniquement à l’aide d’une bijection : deux ensemble $E$ et $F$ ont le même cardinal si et seulement s’il existe une bijection entre $E$ et $F$. Cette définition redonne bien la notion usuelle dans le cas fini : en particulier, un ensemble est de cardinal $n$ si et seulement s’il est en bijection avec $[\![1,n]\!]$, mais elle a l’avantage de s’étendre sans modification au cas infini, où l’on ne dispose plus d’un entier $n$ précis pour décrire le cardinal.

Parmi tous les ensembles infinis, $\mathbb{N}$ joue un rôle particulier : ses éléments sont énumérables un par un, dans l’ordre naturel: $0,1,2,3,...$ . Dire qu’un ensemble $E$ est en bijection avec $\mathbb{N}$, c’est donc dire qu’on peut associer à chaque élément de $E$ un unique entier naturel, c’est-à-dire numéroter les éléments de $E$, sans en oublier ni en répéter aucun. On peut donc « dénombrer » cet ensemble, intuitivement, même si $E$ est infini, on peut en « faire la liste » : $e_{0},e_{1},e_{2},…$

Définition formelle

On dit qu’un ensemble $E$ est dénombrable si et seulement si il existe une bijection de $\mathbb{N}$ dans $E$.

On dit qu’un ensemble $E$ est au plus dénombrable si et seulement si $E$ est dénombrable ou $E$ est fini.

Exemples (voir exercices)

• $\mathbb{Z}$ est dénombrable ;
• $\mathbb{Q}$ est dénombrable ;
• $\mathbb{R}$ n’est pas dénombrable (diagonale de Cantor).