Dénombrabilité

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 ».
On comprend parfois 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. Cependant, il est devenu assez courant de réserver l'adjectif « dénombrable » aux seuls ensembles infinis.

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^[1]. 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

Plus formellement un ensemble E est dit dénombrable quand il est équipotent à l'ensemble des entiers naturels N, c'est-à-dire qu'il existe une bijection de N sur E. Cette définition est parfois élargie aux ensembles finis par certains auteurs, qui définissent un ensemble dénombrable comme un ensemble en bijection avec un sous-ensemble des entiers naturels. Mais cet élargissement sera désigné dans cet article par l'expression « ensemble au plus dénombrable » ou encore « ensemble fini ou dénombrable ». ^[2]. S'il y a risque d'ambiguïté, un ensemble équipotent à N peut toujours être précisé « ensemble infini dénombrable ».

A contrario, 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 l'existence 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, ce qui est assez opératoire en théorie de la cardinalité.

Le cardinal de N, et donc le cardinal de n'importe quel ensemble dénombrable, est noté ℵ₀ (aleph zero). 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^[3] Sur une propriété du système de tous les nombres algébriques réels^[4] où il établit d'une part que l'ensemble des nombres algébriques réels (c'est-à-dire solutions réelles d'une équation polynômiale à coefficients entiers) est dénombrable^[5], 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 …)^[6]. 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 Poincaré^[7], 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^[8], 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^[9] 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é^[10]. 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 est un polynôme de degré 2^[11] :

Les rationnels

Une variante^[12] 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 noeud 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 :
    
où ⌊x_n⌋ est la partie entière de x_n et x_n=⌊x_n⌋ + {x_n}^[13],[14].

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 plus petite ou égale à n d'entiers plus petits 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 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 peut encore généraliser :

Proposition — Tout ensemble qui contient un ensemble dénombrable 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.

La réciproque de cette proposition, de même que la réciproque de la propriété utilisée pour la démontrer, à savoir que si un ensemble est infini alors il est en bijection avec une de ses parties propres, reposent sur l'axiome du choix (voir la section théorie axiomatique ci-dessous).

Parties d'un ensemble dénombrable

Les entiers naturels

On va utiliser la structure 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 inférieurs à un entier 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 tous sous-ensemble non vide de N possède un plus petit élément. En effet, on peut définir par récurrence^[15] 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, 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.

Par définition d'une part des ensembles finis, d'autre part des ensembles dénombrables, on déduit immédiatement 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 on remarque que, par une récurrence immédiate, une fonction f strictement croissante vérifie que pour tout entier n, f(n) ≥ n. Si A est bornée par N, la bijection strictement croissante donnée par le lemme ne peut donc être définie au-delà de N. Réciproquement, si la bijection est définie sur les N premiers entiers, N ≠ 0, A est bornée par f(N-1) (par n'importe quel entier si N = 0).

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 qu'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 de A sur N et une bijection ψ de B sur N. Définissons:

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^*, ensembles 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. D'après l'axiome du choix (dénombrable), on a donc 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 :

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

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) ne sont pas non plus dénombrables, 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-1 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^[16].

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 (la réunion de A et de B) 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, {0,1}^N, n'est pas dénombrable par argument diagonal. L'ensemble des suites de 0 et de 1 qui n'utilisent 1 qu'un nombre fini de fois, et donc 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 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 : {0,1}^N est équipotent à l'ensemble 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 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^[17]. 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 de complémentaire fini de E (tous non vides sinon E serait fini)^[18]. 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.^[19]. 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^[20].

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

On remarque que l'ensemble Q des rationnels est un sous-ensemble dénombrable dense de l’ensemble R des réels. Cette propriété se généralise aux Rⁿ, et elle conduit à la notion d'espace séparable. et elle a pour conséquence qu'un intervalle ouvert de R est déterminé par son intersection avec Q. si cet intervalle est non vide on montre facilement que cette intersection est infinie dénombrable. Une famille d'intervalles ouverts non vides disjoints deux à deux est donc au plus dénombrable, puisque l'on peut définir une surjection de l'intersection de la réunion de cette famille avec Q, qui est donc dénombrable, dans l'ensemble des intervalles de la famille. On peut montrer que tout ouvert de R est réunion dénombrable d'intervalles ouverts, et 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.

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 pi.

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 (comme l'arithmétique de Peano ou la théorie des ensembles) a un modèle 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^[21].

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 : si l'ensemble des propositions démontrables d'une théorie est toujours récursivement énumérable (pour les théories récursivement axiomatisables, celles que l'on rencontre habituellement en mathématiques), l'ensemble des propositions qui ne sont pas démontrables ne l'est pas. Ces deux ensembles, qui sont finalement des ensembles de mots sur un alphabet fini (ou dénombrable) sont pourtant tous les deux dénombrables.

Notes

Voir aussi

• Entier naturel
• Nombre cardinal
• Aleph (nombre)
• Hypothèse du continu
• Georg Cantor

Lien externe

• Version en français de l'article de 1874 de Cantor sur la non-dénombrabilité des réels, en ligne et commentée sur le site BibNum.

Bibliographie

• Paul R. Halmos, Introduction à la théorie des ensembles [détail des éditions] ouvrage introductif, couvre, sauf références précisées, à peu près tout le contenu de l'article.
• René Cori, Daniel Lascar, Logique mathématique (tome II) - Masson - 1994 - ISBN 2-225-84080-6, ch 7, ouvrage introductif, utilise les ordinaux dès les premiers développements sur la cardinalité.
• Jech, Thomas, 2003. Set Theory: The Third Millennium Edition, Revised and Expanded. Springer. ISBN 3-540-44085-2.

• Portail des mathématiques