Dénombrable

Imaginez une liste dont les places portent les numéros 0, 1, 2, 3, et ainsi de suite. Un ensemble est dénombrable lorsque chacun de ses éléments peut recevoir une place distincte dans une telle liste. La liste peut ne jamais finir : l'essentiel est que tout élément finisse par apparaître à un rang précis.

Cette idée couvre les ensembles finis et certains ensembles infinis. Les nombres rationnels, malgré leur abondance, peuvent ainsi être rangés sans en oublier. Les nombres réels, eux, échappent à toute liste de ce genre.

Soit un ensemble E. Dire que E est dénombrable signifie ici qu'il existe une bijection entre E et une partie de l'ensemble ℕ des entiers naturels. Une bijection associe chaque élément de E à un entier distinct, et chaque entier de la partie choisie à exactement un élément de E.

Cette définition comprend deux cas. Si E est fini, la partie correspondante de ℕ est finie. Si E est infini, E peut être mis en bijection avec ℕ tout entier : ses éléments forment alors une suite infinie dans laquelle chacun apparaît une fois.

Les entiers, les rationnels et les polynômes à coefficients rationnels sont dénombrables. Les réels ne le sont pas : l'argument diagonal de Cantor construit, à partir de toute liste proposée de réels, un réel absent de cette liste. La propriété concerne donc l'existence d'un rangement par entiers, et non la manière dont les éléments semblent dispersés ou serrés.

On veut ranger les rationnels positifs. Chaque candidat s'écrit comme une fraction p/q, où le numérateur p et le dénominateur q sont des entiers strictement positifs. On parcourt les couples (p, q) par diagonales de somme p + q constante.

1. Pour p + q = 2, on rencontre 1/1.
2. Pour p + q = 3, on rencontre 1/2 puis 2/1.
3. Pour p + q = 4, on rencontre 1/3, 2/2 et 3/1. On écarte 2/2, déjà représenté par 1/1.
4. On poursuit de la même façon en ne gardant que les fractions réduites.

Tout rationnel positif a une écriture réduite a/b. Il apparaît sur la diagonale de somme a + b, donc à une étape finie. Les fractions conservées commencent ainsi par 1/1, 1/2, 2/1, 1/3, 3/1, 1/4, 2/3, 3/2 et 4/1. Pour contrôler le procédé, choisissez une fraction réduite : 2/3 se trouve bien sur la diagonale p + q = 5.

Pour établir qu'un ensemble est dénombrable, on cherche un rangement explicite par entiers. Pour les rationnels positifs, le parcours diagonal des couples numérateur-dénominateur fournit ce rangement ; une simple tentative de les classer par taille n'offre pas le même repère.

Pour prouver qu'un ensemble ne l'est pas, il faut montrer que toute liste échoue. Pour les réels, l'argument diagonal de Cantor produit précisément un élément qui diffère de chaque terme proposé.

En théorie de la mesure, on vérifie si la famille d'ensembles négligeables est dénombrable. Une union dénombrable d'ensembles de mesure nulle reste de mesure nulle ; cette conclusion ne vient pas du seul fait que chaque ensemble est négligeable.

Dénombrable et fini. Un ensemble fini est dénombrable selon la convention de cette fiche, mais l'inverse est faux. L'ensemble ℕ est dénombrable et infini : chaque entier porte déjà son propre rang.

Infini et non dénombrable. Être infini ne tranche pas la question. Les rationnels sont infinis et dénombrables, tandis que les réels sont infinis et non dénombrables. Le critère décisif est l'existence d'une bijection avec une partie de ℕ.

Liste avec répétitions et bijection. Une énumération qui répète 1 sous les formes 1/1 et 2/2 n'est pas encore une bijection. Dans l'exemple des rationnels, réduire les fractions supprime ces doublons.

Une liste partielle ne suffit pas. Donner les premiers termes d'un rangement ne prouve rien si aucun argument ne garantit que tout élément apparaîtra. Pour a/b sous forme réduite, le parcours diagonal fournit ce contrôle : la fraction est atteinte à la diagonale a + b.

Les doublons masquent le comptage. Parcourir tous les couples (p, q) rencontre plusieurs écritures d'un même rationnel. Il faut conserver une seule écriture, par exemple la fraction réduite, avant d'affirmer que l'association est bijective.

Le mot « dénombrable » dépend d'une convention. Dans cette fiche, les ensembles finis sont inclus. Certains textes réservent ce mot aux ensembles en bijection avec ℕ et disent « au plus dénombrable » pour inclure les ensembles finis. Il faut vérifier la définition adoptée.

Une union quelconque n'est pas une union dénombrable. Le résultat de mesure cité suppose que la famille réunie puisse elle-même être indexée par les entiers. Sans cette hypothèse, la conclusion « mesure nulle » n'est pas garantie.

La fiche bijection précise le type de correspondance qui permet de comparer exactement deux ensembles.

La fiche Rationnels approfondit l'ensemble qui sert ici d'exemple conducteur.

L'article La bataille de l’infini replace les différentes tailles d'infini dans un parcours plus large.