Ensemble dénombrable

En mathématiques, un ensemble est dit dénombrable, ou infini dénombrable, lorsque ses éléments peuvent être listés sans omission ni répétition dans une suite indexée par les entiers. Certains ensembles infinis, au contraire, contiennent « trop » d'éléments pour être parcourus complètement par l'infinité des entiers et sont donc dits « non dénombrables ».

Il existe deux usages du mot « dénombrable » en mathématiques, suivant que l'on comprend ou non parmi les ensembles dénombrables les ensembles finis, dont les éléments peuvent être numérotés par les entiers positifs inférieurs à une valeur donnée. C'est seulement quand on comprend les ensembles finis parmi les ensembles dénombrables qu'il est utile de préciser infini dénombrable.

Georg Cantor est le premier à faire usage de cette notion, dans un article publié en 1874, qui marque la naissance de la théorie des ensembles. Mais l'importance du dénombrable se manifeste dans de nombreux domaines des mathématiques, notamment en analyse, en théorie de la mesure et en topologie.

Définitions

On trouve en mathématiques deux définitions de « dénombrable » qui ne sont pas équivalentes.

Selon la première, un ensemble E est dit dénombrable quand il existe une bijection entre l'ensemble N des entiers naturels et E (on dit qu'il est équipotent à l'ensemble N des entiers naturels). C'est la définition originale de Cantor.

Selon la seconde, un ensemble E est dit dénombrable quand il est en bijection avec une partie de N, ce qui revient à ajouter aux ensembles en bijection avec N les ensembles finis, tout sous-ensemble de N étant fini ou dénombrable. Un ensemble équipotent à N est alors appelé « ensemble infini dénombrable ».

Le choix est fait dans la suite de l'article d'adopter la première définition, même si on précise parfois « ensembles infinis dénombrables » qui est sans ambiguïté quelle que soit la définition utilisée. Les ensembles en bijection avec une partie de N sont alors appelés « ensembles au plus dénombrables » ou encore « ensembles finis ou dénombrables ». Un ensemble (infini) non dénombrable, est un ensemble infini qui n'est pas équipotent à N. L'argument de la diagonale de Cantor permet de montrer que l'ensemble des réels et l'ensemble des parties de N ne sont pas dénombrables, mais aussi qu'il existe de « nombreux » autres infinis non dénombrables.

Un ensemble qui contient un ensemble infini dénombrable est nécessairement infini, c'est-à-dire qu'il n'est équipotent à aucun ensemble borné d'entiers naturels. Dès que l'on se donne suffisamment d'axiomes en théorie des ensembles, en particulier l'axiome du choix, on montre que l'infini dénombrable est le plus petit infini, au sens où tout ensemble infini contient un ensemble infini dénombrable. La réciproque ne pose pas de difficulté. On peut alors caractériser un ensemble infini comme un ensemble contenant un ensemble dénombrable.

Le cardinal de N, et donc le cardinal de n'importe quel ensemble dénombrable, est noté ℵ₀ (aleph-zéro). Il est le premier de la suite ordinale des alephs, qui représentent tous les cardinaux infinis en présence de l'axiome du choix.

Apparition

La notion fut introduite par Georg Cantor dans un article de 1874, Sur une propriété du système de tous les nombres algébriques réels, article qui marque la naissance de la théorie des ensembles. On dispose de la genèse de cette démonstration, qui n'est pas encore celle bien connue utilisant l'argument diagonal, grâce aux lettres des 7 décembre et 9 décembre 1873 de Georg Cantor à Dedekind, où il établit d'une part que l'ensemble des nombres algébriques réels (c'est-à-dire solutions réelles d'une équation polynomiale à coefficients entiers) est dénombrable, d'autre part que l'ensemble des nombres réels lui ne l'est pas, ce dont il déduit immédiatement l'existence de nombres transcendants (c'est-à-dire non algébriques), retrouvant ainsi un résultat de Liouville.

Son apparition est liée à la conception de l'infini en mathématiques. Jusqu'à Cantor, l'infini est l'infini potentiel, la possibilité de continuer un processus sans s'arrêter. La comparaison d'ensembles infinis suppose l'infini dit achevé, actuel ou encore complet : un ensemble infini vu comme une totalité, ce qu'ont refusé beaucoup de mathématiciens (Gauss, ou à l'époque de Cantor, Kronecker). Pour ceux-ci le fait de considérer une infinité d'objets comme un tout, par exemple tous les entiers naturels, c'est-à-dire la notion même d’ensemble infini, n'a pas de sens. L'infini résulte seulement d'un procédé d'énumération sans répétitions qui ne s'interrompt pas. Seul l'infini dénombrable peut alors avoir à la rigueur un sens ; il est compris par le procédé qui l'engendre, plutôt que par la totalité de ses éléments. L'infini achevé sera encore contesté par Henri Poincaré, contestation qui fonde également l'intuitionnisme de Brouwer, celui-ci en donnant la forme la plus élaborée. Pour ce dernier seul l'infini dénombrable (en tant qu'infini potentiel) existe, « l'ensemble des réels entre 0 et 1 » n'a pas de sens, mais si ses conceptions sont cohérentes, elles induisent une profonde remise en cause des mathématiques. En distinguant, le premier, deux infinis distincts, et en en déduisant de façon simple un résultat mathématique déjà obtenu de façon différente par Joseph Liouville, Cantor donne des arguments pour l'infini complet, qu'aujourd'hui ne songent même plus à discuter la très grande majorité des mathématiciens.

Cantor devait ultérieurement montrer l'équipotence de certains ensembles non dénombrables, puis l'existence de multiples infinis de plus en plus « grands », ce qui devait le conduire au développement de la théorie de la cardinalité, et plus généralement de la théorie des ensembles.

Quelques exemples d'ensembles dénombrables

Sous-ensembles de N

L'ensemble N des entiers naturels est bien sûr dénombrable par définition, mais, comme cela sera démontré ultérieurement, chacun de ses sous-ensembles infinis l'est également. On peut expliciter quelques cas particuliers. La remarque que N pouvait être mis en correspondance avec une partie stricte a été faite à plusieurs reprises dès l'antiquité. On cite par exemple souvent Galilée pour la remarque qu'il y a « autant » de carrés parfaits que d'entiers naturels. De la même façon, on obtient par une énumération explicite :

• l'ensemble N^∗ des entiers naturels non nuls est dénombrable, il est énuméré par la suite (n + 1) ;
• l'ensemble des entiers naturels pairs est dénombrable, car énuméré par la suite (2n).

Dans le cas des nombres premiers on peut utiliser une définition par récurrence :

• l'ensemble des nombres premiers est dénombrable ; on définit par récurrence une suite (p_n) qui énumère les nombres premiers en posant :

p₀ = 2 ;

p_n+1 est le plus petit nombre premier strictement supérieur à p_n.

La démonstration d'Euclide, qui montre que l'ensemble des nombres premiers est infini, permet d'assurer également que p_n+1 est bien défini, puisque l'ensemble des nombres premiers strictement supérieurs à p_n est forcément non vide (en l'occurrence il contient le ou les diviseurs premiers de p₀.p₁ … p_n+1).

La méthode utilisée dans ce dernier cas est suffisamment générale pour s'adapter à tout sous-ensemble infini des entiers naturels.

« Sur-ensembles » de N

On montre que certains ensembles qui ont N, ou une copie évidente de N, pour partie stricte, sont dénombrables.

Les entiers relatifs

L'ensemble Z des entiers relatifs est dénombrable. En effet, la suite ((-1)ⁿ⌈n/2⌉), où ⌈n/2⌉ désigne le plus petit nombre entier supérieur ou égal à n/2, établit bien une bijection des entiers naturels dans les entiers relatifs : les termes d'indices pairs décrivent les entiers naturels, ceux d'indice impair les entiers négatifs non nuls.

Les couples d'entiers naturels

La fonction de couplage de Cantor établit une bijection de N × N dans N.

L'ensemble N × N des couples d'entiers naturels est dénombrable ; on peut énumérer les couples d'entiers naturels diagonale par diagonale, comme indiqué sur le schéma joint : en le suivant on définit facilement par récurrence une suite de couples qui énumère bijectivement tous les couples d'entiers naturels. La réciproque de cette fonction, soit f, qui est donc une bijection de N × N dans N, dite fonction de couplage de Cantor, est un polynôme de degré 2 :

$f(p,q)=q+\sum _{0\leq k<p+q}(k+1)=q+{(p+q)(p+q+1) \over 2}={\frac {(p+q)^{2}+p+3q}{2}}$.

Une autre méthode consiste à utiliser la propriété arithmétique suivante : tout entier $n\geqslant 1$ peut s'écrire d'une façon unique sous la forme du produit d'une puissance de 2 par un nombre impair, soit $n=2^{a}(2b+1)$, où $a,b\in \mathbf {N}$. L'application $f\colon \mathbf {N} ^{2}\longrightarrow \mathbf {N}$ définie par $f(a,b)=2^{a}(2b+1)-1$ est ainsi une bijection.

Les rationnels

Une variante due à Neil Calkin et Herbert Wilf de l'arbre de Stern-Brocot donne une bijection simple à calculer des rationnels positifs ou nuls, plus précisément de leurs représentations par des fractions irréductibles, dans les entiers naturels : la fraction irréductible a/b a pour fils gauche a/(a+b) et pour fils droit (a+b)/b ; ces fractions sont irréductibles. Toute fraction irréductible d'entiers apparait une et une seule fois dans l'arbre (voir l'algorithme d'Euclide par soustraction original). Le chemin de la racine 0/1 au nœud a/b donne la représentation binaire de l'entier image de a/b par la bijection. La bijection réciproque peut se définir par récurrence :
${\ \ }^{x_{0}=0,\ x_{n+1}={1 \over \lfloor x_{n}\rfloor +1-\{x_{n}\}}}$
où ⌊x_n⌋ est la partie entière de x_n et x_n=⌊x_n⌋ + {x_n}.

L'ensemble Q des nombres rationnels est dénombrable. En effet, un rationnel est représenté par une fraction, c'est-à-dire un couple constitué d'un entier relatif et d'un entier naturel non nul. En composant comme il faut les bijections établies précédemment, on obtient une bijection de N dans Z × N^∗. La représentation d'un rationnel par une fraction n'est pas unique, mais, sachant que Q est infini, on en déduit facilement une définition par récurrence d'une bijection de N dans Q (on prend pour image de n le quotient du premier couple dans l'énumération de Z × N^∗ qui fournit un rationnel non encore énuméré). C'est également une conséquence du théorème de Cantor-Bernstein, simple cependant à démontrer dans ce cas particulier.

Autres exemples

Les deux premiers exemples, dénombrabilité de Z, mais surtout dénombrabilité de N × N, utilisent un argument assez générique pour des démonstrations de dénombrabilité : on énumère les éléments de l'ensemble considéré par blocs successifs, de taille constante dans le cas de Z — deux éléments de même valeur absolue, de taille croissante dans le cas N × N — les diagonales, c'est-à-dire les couples de même somme. On a également une façon uniforme d'ordonner, donc d'énumérer, chaque bloc fini.

• Par exemple l'ensemble des mots sur un alphabet fini, c'est-à-dire des suites finies (de longueur arbitrairement grande) d'éléments d'un ensemble fini, est dénombrable. On l'énumère par blocs de mots de taille fixe, d'abord le mot vide, puis les mots de taille 1, puis ceux de taille 2, etc. Chaque bloc peut-être ordonné lexicographiquement, à partir d'un ordre arbitraire sur l'alphabet de départ.
• De la même façon l'ensemble des suites finies d'entiers (cela revient à prendre des mots sur un alphabet dénombrable), est dénombrable. On peut utiliser pour bloc les suites de longueur inférieure ou égale à n d'entiers inférieurs ou égaux à n où n apparait nécessairement si la suite est de longueur strictement inférieure à n-1. Chaque bloc s'ordonne lexicographiquement.
• L'ensemble des polynômes à coefficients entiers naturels peut être vu comme l'ensemble des suites (finies) de ces coefficients. Ce sont toutes les suites finies d'entiers dont le dernier terme est non nul. De façon strictement analogue au cas précédent, cet ensemble est dénombrable. Comme l'ensemble des entiers relatifs Z est dénombrable, par composition, on en déduit que l'ensemble des polynômes à coefficients entiers relatifs est également dénombrable.

• L'ensemble des nombres algébriques (réels ou complexes) est donc également dénombrable : puisque l'on peut énumérer les polynômes à coefficients entiers, et que chacun de ces polynômes a un nombre fini de racines, on peut énumérer les nombres algébriques, polynôme par polynôme, en ne considérant que les racines du polynôme qui ne sont pas déjà apparues dans l'énumération. Comme ni l'ensemble des réels ni l'ensemble des complexes ne sont dénombrables, on en déduit l'existence de nombres (réels ou complexes) transcendants.

On pourra également utiliser pour ces derniers exemples les théorèmes généraux qui seront vus dans la suite.

Ensembles finis et infinis

Un ensemble est fini si, pour un certain entier naturel N, il est en bijection avec l'ensemble des N premiers entiers, soit {0, 1, …, N-1}, les entiers strictement plus petits que N. Par exemple l'ensemble vide (cas N = 0) est (comme attendu) fini. Tout ensemble fini est donc subpotent à N, c'est-à-dire qu'il existe une injection de cet ensemble dans N.

Une propriété essentielle des ensembles finis est qu'une injection d'un ensemble fini dans lui-même est nécessairement bijective (voir les articles ensemble fini et principe des tiroirs), c'est-à-dire qu'un ensemble fini ne peut être en bijection avec une partie propre de lui-même. Un ensemble infini est simplement un ensemble qui n'est pas fini. L'ensemble N, qui est en bijection avec par exemple N^*, est donc infini, et de même tout ensemble dénombrable est infini. On a même :

Proposition — Un ensemble qui contient un ensemble dénombrable est en bijection avec une de ses parties propres (en particulier il est infini).

En effet, soit E un tel ensemble et A une partie dénombrable de E. On a une bijection sur une partie propre de E en prenant l'identité sur E − A, et une bijection de A sur une partie propre de A.

Avec l'axiome du choix on peut démontrer que si un ensemble est infini alors il contient une partie dénombrable (voir la section #Théorie axiomatique ci-dessous).

Parties d'un ensemble dénombrable

Les entiers naturels

On va utiliser la relation d'ordre sur N. Un segment initial de l'ensemble des entiers naturels N est soit N lui-même, soit l'ensemble des entiers naturels strictement inférieurs à un entier naturel donné. En particulier l'ensemble vide est un segment initial de N. On peut montrer que :

Lemme — Pour toute partie A de N, il existe une bijection strictement croissante d'un segment initial de N dans A.

Le cas où A est vide étant évident, on suppose que cet ensemble A est non vide. On va utiliser le fait que N est bien ordonné, c'est-à-dire que tout sous-ensemble non vide de N possède un plus petit élément. En effet, on peut définir par récurrence une suite (a_n) de la façon suivante :

• a₀ est le plus petit élément de A (qui existe forcément car A est non vide) ;
• a_n+1 est le plus petit élément de A supérieur à a_n s'il en existe un, et est non défini sinon ou si a_n n'est pas défini.

Cette suite établit bien une bijection strictement croissante d'un segment initial des entiers dans A.

Démonstration

Par construction, soit cette suite est définie sur tous les entiers naturels, soit il existe un entier p tel qu'elle soit définie pour les p+1 premiers entiers (les entiers de 0 à p) et ceux-là seulement. Également par construction elle est strictement croissante, ce qui assure qu'elle est injective sur son ensemble de définition, et, par récurrence, que si a_n est défini, alors a_n ≥ n. On en déduit donc que si la suite est bornée, alors elle est définie seulement sur les entiers jusqu'à un certain p.

Montrons maintenant que l'image de cette suite est A. Soit b un élément de A. Il existe un entier p tel que a_p est défini, et a_p ≥ b. En effet, soit la suite n'est pas bornée, soit il existe un entier p tel que la suite est définie seulement pour les entiers jusqu'à p compris, ce qui signifie que a_p est défini et qu'aucun élément de A ne lui est strictement supérieur. On peut donc définir, par la propriété de bon ordre, le plus petit entier n tel que a_n ≥ b. Montrons que b = a_n. Par définition de la suite, si n = 0 c'est que b = a₀, le plus petit élément de A. Si n ≠ 0 c'est que n = m+1, et que a_n est le plus petit élément parmi les éléments de A strictement supérieurs à a_m, dont b justement fait partie, par définition de n. Donc, par définition de a_n, a_n ≤ b, donc b = a_n.

La suite (a_n) définit donc une bijection soit entre N et A, auquel cas par définition A est dénombrable, soit entre l'ensemble des p+1 premiers entiers et A, auquel cas A est par définition fini.

Par définition d'une part des ensembles finis, d'autre part des ensembles dénombrables, on déduit du lemme la première partie de la proposition qui suit.

Proposition — Toute partie A de N est finie ou dénombrable. De plus cette partie A est finie si elle est bornée, dénombrable sinon.

Pour la deuxième partie (en excluant à nouveau le cas évident où A est vide donc bornée par n'importe quel entier), on a déjà vu au cours de la démonstration du lemme que si A est bornée alors le segment initial S avec lequel elle est en bijection est de la forme {0,1,…,p} pour un certain entier p (autrement dit : A est finie) et que réciproquement, si S est de la forme {0,1,…,p} alors A est bornée (par a_p).

On a ainsi une caractérisation courante d'un sous-ensemble infini (donc dénombrable) de N. Par exemple une variante de la preuve d'Euclide pour l'existence d'une infinité de nombres premiers est de montrer que pour tout entier n, n! + 1 a au moins un diviseur premier, et ceux-ci sont nécessairement supérieurs à n.

Une conséquence directe de la proposition est :

Corollaire — Si A est subpotent à N, c'est-à-dire s'il existe une injection de A dans N, alors A est fini ou dénombrable.

On peut donc parler d'ensemble au plus dénombrable pour un ensemble fini ou dénombrable. On en déduit également que :

Proposition — S’il existe une surjection de N dans A, alors A est fini ou dénombrable.

En effet, si s est une surjection de N dans A, on peut définir une injection i qui est une réciproque à droite de s, sans faire appel à l'axiome du choix, puisque N, ensemble de départ de la surjection, est bien ordonné : on prend pour i(y), où y dans A, le plus petit antécédent de y par s.

La réciproque du corollaire est évidente par définition des ensembles finis et des ensembles dénombrables. La réciproque de la proposition est évidente dans le cas dénombrable, par définition. S'il existe une bijection d'un ensemble fini F dans un ensemble A, et que A est non vide, soit a ∈ A, alors on peut compléter cette bijection en une surjection de N dans A, en associant a à tout élément de N qui n'est pas dans F. Ces résultats seront rassemblés dans le théorème du paragraphe suivant.

Les ensembles finis ou dénombrables

On généralise directement ce qui précède de N à un ensemble dénombrable quelconque, en composant avec la bijection qui assure l'équipotence.

Théorème — Toute partie d'un ensemble dénombrable est finie ou dénombrable. On a l'équivalence entre les trois propositions suivantes :

• l'ensemble A est fini ou dénombrable ;
• il existe une injection de l'ensemble A dans un ensemble dénombrable ;
• A est vide ou il existe une surjection d'un ensemble dénombrable dans l'ensemble A.

Comme tout ensemble qui contient un ensemble dénombrable est infini (voir ci-dessus), on en déduit :

Corollaire — Les trois propositions suivantes sont équivalentes :

• l'ensemble A est dénombrable ;
• il existe une injection de l'ensemble A dans un ensemble dénombrable et une injection d'un ensemble dénombrable dans A ;
• il existe une surjection d'un ensemble dénombrable dans l'ensemble A et une injection d'un ensemble dénombrable dans A.

Ce corollaire énonce essentiellement le théorème de Cantor-Bernstein dans le cas particulier du dénombrable, dont la démonstration a été facilitée du fait que N est bien ordonné.

On utilise ces caractérisations dans la suite, mais comme premier exemple d'application on peut montrer que pour tout entier n non nul, l'ensemble N × {0, …, n} est dénombrable. En effet cet ensemble s'injecte par inclusion dans N × N, dont on a montré qu'il est dénombrable, et on a une injection de N dans cet ensemble en associant à un entier p le couple (p, 0) (il ne serait cependant pas bien difficile de donner une bijection explicite en utilisant la division euclidienne).

Opérations ensemblistes et dénombrabilité

Produit fini d'ensembles dénombrables

On a vu que N × N est dénombrable (fonction de couplage de Cantor). On en déduit facilement que :

Proposition — Le produit cartésien d'une famille finie non vide d'ensembles dénombrables est dénombrable.

On montre d'abord le résultat pour A et B deux ensembles dénombrables. Il existe une bijection $\varphi$ de A sur N et une bijection $\psi$ de B sur N. Définissons:

$\lambda :{\begin{array}{rcl}A\times B&\longrightarrow &\mathbf {N} \times \mathbf {N} \\(x,y)&\longmapsto &(\varphi (x),\psi (y))\end{array}}$

Cette application est bijective de A × B sur N × N, qui est dénombrable. Donc A × B est dénombrable.

Une famille finie non vide peut être supposée indexée par les entiers de 0 à n pour un certain n, par définition d'ensemble fini. Le résultat se généralise alors à une famille finie non vide quelconque par récurrence, en utilisant, pour l'étape de récurrence, le résultat que l'on vient de démontrer pour deux ensembles.

Corollaire — Le produit cartésien d'une famille finie d'ensembles au plus dénombrables est au plus dénombrable.

On utilise les caractérisations de la section précédente. Si la famille a pour cardinal fini n, on définit comme ci-dessus une injection du produit cartésien dans Nⁿ. Or cet ensemble est dénombrable d'après la proposition précédente (si la famille est vide, le produit est réduit à un élément).

On peut utiliser ces propriétés pour donner une justification rapide de la dénombrabilité de l'ensemble Q des rationnels. En effet Z, ensemble des entiers relatifs, est dénombrable ainsi que N^*, ensemble des entiers strictement positifs, et donc leur produit cartésien Z × N^*. Tout rationnel s'écrit d'au moins une manière sous la forme d'une fraction p/q où p ∈ Z et q ∈ N^*. Ceci permet de définir une surjection de Z × N^* dans Q, qui est donc au plus dénombrable ; étant infini, il est dénombrable.

Réunion finie d'ensembles dénombrables

Proposition — La réunion d'une famille finie d'ensembles au plus dénombrables est au plus dénombrable. Si l'un des ensembles de la famille finie est dénombrable, la réunion est dénombrable.

En effet, supposons la famille de cardinal n + 1 (si la famille est vide la réunion aussi, d'où le résultat), on peut toujours se ramener à une indexation par les entiers de 0 à n. Il s'agit donc de montrer que si les ensembles A₀, …, A_n sont au plus dénombrables, alors leur réunion l'est également. Pour chaque A_i on a f_i une injection de A_i dans N. On définit une injection de A₀ ∪ …∪ A_n dans l'ensemble dénombrable N × {0, …, n}, en associant à a le couple (f(i), i), où i est le plus petit entier tel que a ∈ A_i. Si de plus l'un des A_i est dénombrable, A₀ ∪ …∪ A_n contient un ensemble dénombrable, donc est dénombrable.

Réunion dénombrable d'ensembles dénombrables

On exploite à nouveau la dénombrabilité de N × N, mais les résultats de cette section utilisent l'axiome du choix dénombrable. On montre alors que :

Proposition — La réunion d'une famille dénombrable d'ensembles dénombrables est dénombrable.

Par composition, il est toujours possible de se ramener au cas où la famille est indexée par N. Il s'agit alors de montrer que si (A_i)_{i ∈ N} est une famille d'ensembles dénombrables, alors la réunion de ces ensembles, A = ∪_{i ∈ N} A_i, est un ensemble dénombrable. Les A_i étant dénombrables, il existe pour chaque entier i, une bijection de N sur A_i. En appliquant l'axiome du choix (dénombrable) à la suite (F_i) _{i ∈ N}, où F_i est l'ensemble des bijections de N dans A_i, on obtient une suite de fonctions (f_i)_{i ∈ N}, où f_i est une bijection de N sur A_i. On peut donc définir l'application suivante de N² dans A :

$f:{\begin{array}{rcl}\mathbf {N} \times \mathbf {N} &\longrightarrow &A\\(i,n)&\longmapsto &f_{i}(n)\end{array}}$

L'application f est surjective, du fait que chacune des applications f_i l'est, et que chaque élément de A est élément d'au moins un A_i.

Ainsi, l'ensemble A est au plus dénombrable, comme il contient un ensemble dénombrable, il est dénombrable.

Proposition — Une réunion dénombrable d'ensembles au plus dénombrables est au plus dénombrable.

Dans le cas où certains A_i sont finis, il suffit de reprendre la démonstration précédente, mais avec les f_i surjectives de N dans A_i.

On peut réexaminer certains des exemples du début à la lumière de ces résultats. Par exemple l'ensemble des suites finies d'entiers, qui est la réunion des Nⁿ pour n ∈ N, réunion dénombrable d'ensembles dénombrables, est donc dénombrable d'après la première de ces deux propositions. La preuve est donc devenue très simple. Cependant la première preuve (esquissée) n'utilisait pas l'axiome du choix. En fait on se ramenait à une réunion dénombrable d'ensembles finis, et on utilisait l'ordre lexicographique pour construire directement une fonction de choix. On peut aussi ne pas se soucier de faire appel ou non à l'axiome du choix, d'autant qu'ici il ne s'agit après tout que de l'axiome du choix dénombrable.

On a une preuve utilisant les mêmes arguments pour l'ensemble des nombres algébriques. Cet ensemble est infini puisque les entiers sont évidemment algébriques. L'ensemble des polynômes à coefficients entiers est évidemment infini, et s'injecte dans l'ensemble des suites finies d'entiers (en prenant la suite de ses coefficients), donc est dénombrable. Un polynôme n'a qu'un nombre fini de racines. L'ensemble des nombres algébriques, qui est la réunion des ensembles des racines de tous les polynômes à coefficients entiers, est donc au plus dénombrable en utilisant la proposition précédente ; il est dénombrable.

Ensembles infinis et dénombrabilité

Exemples d'ensembles infinis non dénombrables

La classe des ensembles dénombrables n'est bien sûr pas close sous toutes les opérations ensemblistes. Le théorème de Cantor montre, par l'argument diagonal, que l'ensemble des parties d'un ensemble dénombrable n'est pas dénombrable. On déduit de ce théorème, ou en reprenant l'argument diagonal, que l'ensemble des suites à valeurs entières indexées par les entiers (les fonctions de N dans N) n'est pas non plus dénombrable, ce qui signifie qu'un produit dénombrable d'ensembles dénombrables n'est pas dénombrable.

Comme l'ensemble des parties de N, ou encore l'ensemble des suites de 0 et de 1, que l'on note {0, 1}^N, cet ensemble a la puissance du continu : le cardinal de l'ensemble des réels. Les propriétés des ensembles dénombrables peuvent être exploitées pour démontrer que certains ensembles ont la puissance du continu. Par exemple de l'équipotence entre le produit cartésien N × N et N, on déduit (A^{B × C} est équipotent à (A^B)^C), celle entre ({0,1}^N)^N et {0,1}^N et donc que l'ensemble des suites réelles indexées par les entiers a la puissance du continu.

De par le théorème de Cantor, il existe bien sûr des ensembles qui ne sont ni dénombrables, ni n'ont la puissance du continu. On peut également montrer l'existence d'ensembles non dénombrables sans utiliser le théorème de Cantor, en utilisant toujours un argument diagonal et la notion de bon ordre, ce qui conduit au cardinal aleph-un et plus généralement à la hiérarchie des alephs.

Caractérisations des ensembles infinis non dénombrables

Un ensemble infini non dénombrable est par définition un ensemble qui n'est ni équipotent à un ensemble fini, ni à N, ou dit autrement dont le cardinal n'est ni fini ni dénombrable. C'est donc un ensemble qui n'est pas équipotent à une partie de N (voir la section Parties d'un ensemble dénombrable), c'est-à-dire tel qu'il n'existe pas d'injection de cet ensemble dans N. C'est encore un ensemble non vide qui n'est pas l'image de N par une surjection (même section).

Cependant aucune de ces caractérisations n'est bien commode, et pour en obtenir de plus opératoires, on a besoin de l'axiome du choix (ce qui n'était pas le cas pour les précédentes caractérisations), qui permet de montrer que les ensembles infinis sont les ensembles qui contiennent un ensemble dénombrable,

Fait — En présence de l'axiome du choix, un ensemble infini non dénombrable est un ensemble dont le cardinal est strictement supérieur à celui de N, c'est-à-dire que c'est un ensemble qui contient une partie dénombrable, et tel qu'il n'y a pas d'injection de cet ensemble dans N.

Il faut cependant remarquer que pour beaucoup d'applications (en voir un exemple dans le paragraphe suivant) l'appel à l'axiome du choix n'est pas nécessaire. En effet l'existence d'ensembles qui ne sont pas équipotents à une partie de N, mais qui ne contiennent pas d'ensemble dénombrable, ne peut se démontrer dans la théorie des ensembles ZF, puisque cela contredit l'axiome du choix, or Kurt Gödel a montré la compatibilité de celui-ci avec les axiomes de ZF.

Réunion

On peut aussi exploiter les propriétés des ensembles dénombrables, pour en déduire des propriétés des ensembles qui contiennent un ensemble dénombrable, c'est-à-dire, en présence de l'axiome du choix (AC en abrégé), des ensembles infinis en général. Du fait que la réunion de deux ensembles dénombrables est dénombrable on déduit immédiatement que :

Proposition — Si E est un ensemble infini (qui contient un ensemble dénombrable si on n'a pas supposé AC), alors la réunion de E et d'un ensemble dénombrable est équipotente à E.

En effet, soit A une partie de E dénombrable et B un ensemble dénombrable. On a une bijection entre A et A ∪ (B\E) (la réunion de A et de la différence ensembliste B\E) que l'on prolonge par l'identité sur le complémentaire de A dans E.

On en déduit (en supposant l'axiome du choix):

Corollaire (AC) — On suppose que E est un ensemble infini non dénombrable, et que A est une partie dénombrable de E, alors E\A, le complémentaire de A dans E, est équipotent à E.

Le corollaire n'utilise l'axiome du choix que pour montrer que E\A contient un ensemble dénombrable. Donnons un exemple où on le déduit directement. L'ensemble des suites de 0 et de 1, E = {0,1}^N, n'est pas dénombrable par argument diagonal. L'ensemble A des suites de 0 et de 1 qui n'utilisent 1 qu'un nombre fini de fois, c'est-à-dire se terminent par une infinité de 0, est dénombrable : on a une injection évidente de cet ensemble dans celui des suites finies d'entiers, et il est par ailleurs évidemment infini (par exemple l'ensemble des suites qui utilisent 1 une seule fois est dénombrable). L'ensemble E\A des suites de 0 et de 1 qui utilisent 1 une infinité de fois contient un ensemble dénombrable : par exemple celui des suites qui utilisent 0 une seule fois. On peut donc appliquer le corollaire sans avoir besoin de l'axiome du choix : E = {0,1}^N est équipotent à l'ensemble E\A des suites finies de 0 et de 1 qui ne se terminent pas par une infinité de 0. Ces suites fournissent un unique développement en base 2 pour les réels de ]0,1]. On en déduit que {0,1}^N et donc l'ensemble des parties de N a la puissance du continu.

Théorie axiomatique

Les définitions et les développements autour du dénombrable ont été menés sans faire référence à une axiomatisation précise de la théorie des ensembles, mais on vérifie facilement que tout se formalise dans la théorie de Zermelo-Fraenkel, et même dans la théorie de Zermelo, avec éventuellement l'axiome du choix : plutôt que le schéma d'axiomes de remplacement, le schéma d'axiomes de compréhension suffit. En particulier l'axiome de l'infini permet de montrer l'existence d'un ensemble infini qui a les propriétés attendues de l'ensemble N des entiers naturels, et que l'on prend comme définition de celui-ci.

On a eu besoin de l'axiome du choix, d'une part pour montrer que la réunion d'une famille dénombrable d'ensembles dénombrables est dénombrable, d'autre part pour montrer que si un ensemble n'est pas fini, il contient un ensemble dénombrable. Dans les deux cas on peut montrer que l'axiome du choix dénombrable suffit. C'est évident pour le premier énoncé (voir ci-dessus).

Pour le second, soit E un ensemble infini (c'est-à-dire qui n'est en bijection avec aucun ensemble {0, …, n – 1}, n entier). Il est naturel de construire une suite injective par récurrence en utilisant une fonction de choix sur les sous-ensembles cofinis de E (tous non vides sinon E serait fini). On modifie légèrement cette preuve pour n'utiliser que l'axiome du choix dénombrable. Pour chaque entier n l'ensemble des (n + 1)-uplets d'éléments de E distincts deux à deux (les injections de {0, ..., n} dans E) est non vide. D'après l'axiome du choix dénombrable, il existe une fonction f définie sur N telle que f(n) est un (n + 1)-uplet d'éléments de E distincts deux à deux. On peut alors définir g sur N par récurrence de la façon suivante. En 0, g(0) est le seul élément du 1-uplet f(0). En n + 1, g(n + 1) est l'élément de plus petit indice du (n + 2)-uplet f(n + 1) qui n'apparait pas dans {g(0), …, g(n)} (de cardinal au plus n + 1, donc un tel élément existe). Par construction la fonction g est injective, et son image est donc un sous-ensemble dénombrable de E.

On peut montrer que l'axiome du choix est bien nécessaire pour ces deux résultats. Il existe des modèles de la théorie de Zermelo-Fraenkel, ZF, (sans l'axiome du choix, bien entendu), dans lesquels par exemple l'ensemble des réels R est réunion dénombrable d'ensembles dénombrables. De façon analogue il existe des modèles de ZF dans lesquels existent des ensembles infinis qui ne contiennent pas de sous-ensemble dénombrable. Les démonstrations utilisent des méthodes avancées de théorie des ensembles, elles combinent le forcing de Cohen et la méthode de permutation de Fraenkel-Mostowski.

Quelques exemples d'intervention du dénombrable

Le dénombrable est une notion tellement élémentaire qu'on la retrouve dans à peu près tous les domaines des mathématiques. On préfère par exemple parler de famille (mathématiques) dénombrable plutôt que de suite indexée par les entiers naturels, quand on veut mettre l'accent sur le fait que l'ordre n'est pas important (voir par exemple famille sommable).

Topologie

L'ensemble Q des rationnels est une partie dénombrable dense de l'espace R des réels. Cette propriété se généralise aux Rⁿ et conduit à la notion d'espace topologique séparable. Elle a pour conséquence qu'un ensemble d'ouverts de R non vides disjoints deux à deux est au plus dénombrable. En effet, l'intersection avec Q de la réunion (supposons-la non vide) de ces ouverts est un ensemble dénombrable, et l'application qui à un élément de cet ensemble associe l'unique ouvert auquel il appartient est surjective. On peut montrer que tout ouvert de R est une réunion d'intervalles ouverts non vides disjoints deux à deux (ses composantes connexes), réunion qui est donc au plus dénombrable (voir la décomposition des ouverts de ℝ). Une autre propriété de R, celle d'avoir une base dénombrable d'ouverts (les intervalles ouverts dont les bornes sont rationnelles) conduit à la notion d'espace à base dénombrable.

Une application fondamentale de la dénombrabilité est la théorie de Baire.

Logique mathématique

En algèbre c'est une banalité de remarquer que par exemple un groupe ayant un nombre fini de générateurs est au plus dénombrable. Par exemple deux réflexions du plan engendrent un groupe fini (groupe diédral) ou infini mais dénombrable, suivant que l'angle entre les deux axes de la réflexion est ou non un multiple rationnel de π.

Tout élément de ce groupe est en fait représenté par une suite finie des générateurs du groupe. C'est un cas particulier d'un phénomène plus général. On a vu que l'ensemble des mots d'un langage fini ou dénombrable est dénombrable. Cette propriété a des conséquences importantes en logique. Il est toujours possible de montrer qu'une théorie du premier ordre exprimée dans un langage fini ou dénombrable — et qui est supposée consistante — (comme l'arithmétique de Peano ou la théorie des ensembles) a un modèle fini ou dénombrable. C'est une forme faible du théorème de Löwenheim-Skolem, que l'on déduit directement de la démonstration du théorème de complétude. Dans le cas de la théorie des ensembles c'est ce que l'on a appelé le paradoxe de Skolem, mais c'est une propriété utile, et qui a été utilisée par Paul Cohen pour ses preuves d'indépendance de l'hypothèse du continu et de l'axiome du choix.

Calculabilité

L'informatique ne manipule que le dénombrable. Mais une propriété plus exigeante est utile. Un ensemble est fini ou dénombrable quand il est vide ou l'image d'une fonction définie sur N, donc d'une certaine façon « énumérable » par une fonction définie sur les entiers. Pour qu'un ensemble soit récursivement énumérable on demande que de plus cette fonction soit calculable (au sens calculable par une machine). Il existe des ensembles dénombrables qui ne sont pas récursivement énumérables. Un exemple est l'ensemble des entiers qui codent une machine de Turing qui ne s'arrête pas pour une entrée donnée, cet ensemble ne peut être récursivement énumérable d'après l'indécidabilité du problème de l'arrêt. Un autre exemple est donné par l'ensemble des théorèmes d'une théories récursivement axiomatisable qui n'est pas décidable, comme l'arithmétique de Peano. C'est un ensemble de mots sur un alphabet fini (ou dénombrable), donc dénombrable, mais pas récursivement énumérable.

Voir aussi

Articles connexes

• Codénombrabilité
• Condition de chaîne dénombrable
• Espace de Lindelöf
• Espace dénombrablement engendré
• Axiomes de dénombrabilité (en)

Lien externe

• Traduction en français de l'article de 1874 de Cantor sur la non-dénombrabilité des réels, Sur une propriété du système de tous les nombres algébriques réels, introduction et analyse Patrick Dehornoy, sur le site BibNum.

• Notice dans un dictionnaire ou une encyclopédie généraliste :

  • Den Store Danske Encyklopædi

Bibliographie

• Paul Halmos, Introduction à la théorie des ensembles [détail des éditions].
  Cet ouvrage introductif couvre, sauf références précisées, à peu près tout le contenu de l'article.
• René Cori et Daniel Lascar, Logique mathématique II. Fonctions récursives, théorème de Gödel, théorie des ensembles, théorie des modèles [détail des éditions], chapitre 7.
  Cet ouvrage introductif utilise les ordinaux dès les premiers développements sur la cardinalité.
• (en) Thomas Jech, Set Theory: The Third Millennium Edition, Revised and Expanded, 2003, Springer (ISBN 3-540-44085-2)