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 CantorLa notion dans l'article de 1874 où elle apparaît pour la première fois (cf. partie historique), ne porte pas de nom. On trouve la définition de dénombrable (abzählbar) comme équipotent à l'ensemble des entiers naturels dans l'article paru en 1883, Über unendliche lineare Punktmannigfaltigkeiten, 3, de l'édition des œuvres complètes de 1932 par Ernst Zermelo, traduction en français de 1889 dans Sur les ensembles infinis et linéaires de points, , accessible sur Gallica. La même définition est reprise dans , un ouvrage pionnier sur la théorie des ensembles en France..
Selon la seconde, un ensemble E est dit dénombrable quand il est en bijection avec une partie de N ( édition, trad. française)., , ce qui revient à ajouter aux ensembles en bijection avec N les ensembles finis., tout sous-ensemble de N étant fini ou dénombrableVoir la section « Les ensembles finis ou dénombrables » qui suit.. 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é ℵ0 (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 Cantor, « Über eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen », Journal für die reine und angewandte Mathematik, vol. 77, 1874, (voir sur le centre de numérisation de Göttingen , et une traduction en français, « Sur une propriété du système de tous les nombres algébriques réels », Acta Math., vol. 2, 1883, , sur Gallica, )., article qui marque la naissance de la théorie des ensembles Thomas Jech, « Set Theory », Stanford Encyclopedia of Philosophy (édition hiver 2011), Edward N. Zalta (ed.).. 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 et de Georg Cantor à DedekindLettres traduites in Jean Cavaillès, Philosophie mathématique, annexe « Correspondance Cantor-Dedekind », éd. Hermann, Paris. de l'édition de 1962., 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énombrableDémonstration due à Dedekind, selon leur correspondance., 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)Voir par exemple .. 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éPar exemple Science et Méthode, chap III Les mathématiques et la logique, accessible en ligne , 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 sensBrouwer Intuitionism and Formalism, Inaugural Address at the University of Amsterdam 1912, traduit en anglais dans 'The Bulletin of the American Mathematical Society, vol XX 1913 , d'après ., 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 argumentsRichard Dedekind, notes sur les lettres de 1873 L'opinion formulée par moi que la première question [la non dénombrabilité des réels] [...] n'avait aucun intérêt pratique particulier a été réfutée de façon flagrante avec la démonstration qu'a donnée Cantor de l'existence de nombres transcendants, note traduite dans l'annexe de Philosophie mathématique, ouvrage cité, . 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éVoir .. 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 (pn) qui énumère les nombres premiers en posant : p0 = 2 ; pn+1 est le plus petit nombre premier strictement supérieur à pn. La démonstration d'Euclide, qui montre que l'ensemble des nombres premiers est infini, permet d'assurer également que pn+1 est bien défini, puisque l'ensemble des nombres premiers strictement supérieurs à pn est forcément non vide (en l'occurrence il contient le ou les diviseurs premiers de p0.p1 … pn+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⌈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
L'ensemble 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 dans , dite fonction de couplage de Cantor, est un polynôme de degré 2Selon un théorème de Rudolf Fueter et George Pólya, c'est, avec la fonction symétrique, la seule bijection quadratique de N × N dans N : voir l'article détaillé. :
Une autre méthode consiste à utiliser la propriété arithmétique suivante : tout entier peut s'écrire d'une façon unique sous la forme du produit d'une puissance de 2 par un nombre impair, soit , où . L'application définie par est ainsi une bijection.
Les rationnels
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.