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é^[16]. 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 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^[17] :

${\displaystyle 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 ${\displaystyle 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 ${\displaystyle n=2^{a}(2b+1)}$, où ${\displaystyle a,b\in \mathbf {N} }$. L'application ${\displaystyle f\colon \mathbf {N} ^{2}\longrightarrow \mathbf {N} }$ définie par ${\displaystyle f(a,b)=2^{a}(2b+1)-1}$ est ainsi une bijection.

Les rationnels

Une variante due à Neil Calkin et Herbert Wilf^[18] 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 :
${\displaystyle {\ \ }^{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}^[19],[20].

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.

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

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

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 ${\displaystyle \varphi }$ de A sur N et une bijection ${\displaystyle \psi }$ de B sur N. Définissons:

${\displaystyle \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 :

${\displaystyle 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.

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

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.

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

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^[29]. C'est un ensemble de mots sur un alphabet fini (ou dénombrable), donc dénombrable, mais pas récursivement énumérable.

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.

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)