Voir la source de Ensemble dénombrable

{{Confusion|texte=Ne pas confondre avec la notion d'[[espace à base dénombrable]].}}
{{redirect homophones|Non dénombrable|Nom 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 (mathématiques)|suite]] indexée par les [[entier naturel|entiers]]. Certains [[Ensemble infini|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 [[Ensemble fini|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 (mathématiques)|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 [[entier naturel|entiers naturels]] et ''E''<ref>{{harvsp|texte=Cori-Lascar tome II, chap 7|id=Cori-Lascar_II}}.</ref>{{,}}<ref>{{Ouvrage|auteur1=André Delessert|titre=Gödel : une révolution en mathématiques|sous-titre=Essai sur les conséquences scientifiques et philosophiques des théorèmes gödeliens|éditeur=[[Presses polytechniques et universitaires romandes|PPUR]]|année=2000|passage=121|isbn=|lire en ligne={{Google Livres|7Z2WoM4laU8C|page=121}}}}.</ref> (on dit qu'il est [[Équipotence|équipotent]] à l'ensemble '''N''' des entiers naturels). C'est la définition originale de [[Georg Cantor|Cantor]]<ref>La 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 ({{de}}''abzählbar'') comme équipotent à l'ensemble des entiers naturels dans l'article paru en 1883, ''Über unendliche lineare Punktmannigfaltigkeiten, 3'', {{p.|152}} de l'[http://resolver.sub.uni-goettingen.de/purl?PPN237853094 é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'', {{p.|365}}, [https://gallica.bnf.fr/ark:/12148/bpt6k86243w accessible sur Gallica]. La même définition est reprise dans {{Ouvrage|auteur1=[[Émile Borel]]|titre=Leçons sur la théorie des fonctions|éditeur=Gautier-Villars|année=1898|passage=6}}, un ouvrage pionnier sur la théorie des ensembles en France.</ref>.

Selon la seconde, un [[ensemble]] ''E'' est dit ''dénombrable'' quand il est en bijection avec une [[Sous-ensemble|partie]] de '''N'''<ref>{{harvsp|Halmos|p=112}} ({{2de}} édition, trad. française).</ref>{{,}}<ref>{{Krivine98}}, {{p.|36}}.</ref>, ce qui revient à ajouter aux ensembles en bijection avec '''N''' les ensembles finis<ref>{{Ouvrage|auteur1=[[Pierre Colmez]]|titre=Éléments d'analyse et d'algèbre (et de théorie des nombres)|éditeur=Éditions École Polytechnique|année=2009|passage=9|isbn=|lire en ligne={{Google Livres|hMUiEhsa9WUC|page=9}}}}.</ref>, tout [[sous-ensemble]] de '''N''' étant fini ou dénombrable<ref>Voir la section « [[#Les ensembles finis ou dénombrables|Les ensembles finis ou dénombrables]] » qui suit.</ref>. 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 ».
{{ancre|Non dénombrable}}
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 [[Nombre réel|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.
{{Article détaillé|Théorème de Cantor}}

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 [[Cardinalité (mathématiques)|cardinal]] de '''N''', et donc le cardinal de n'importe quel ensemble dénombrable, est noté ℵ<sub>0</sub> ([[aleph-zéro]]). Il est le premier de la suite [[nombre ordinal|ordinale]] des [[aleph (nombre)|alephs]], qui représentent tous les cardinaux infinis en présence de l'axiome du choix.
{{article détaillé|Aleph (nombre)}}

== 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''<ref>{{de}} Cantor, « Über eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen », ''[[Journal für die reine und angewandte Mathematik]]'', vol. 77, 1874, {{p.|258-262}} (voir sur le [[Göttinger Digitalisierungszentrum|centre de numérisation de Göttingen]] [http://gdz.sub.uni-goettingen.de/no_cache/dms/load/img/?IDDOC=49464], et une traduction en français, « Sur une propriété du système de tous les nombres algébriques réels », ''[[Acta Mathematica|Acta Math.]]'', vol. 2, 1883, {{p.|305-310}}, sur [[Gallica]], [https://gallica.bnf.fr/ark:/12148/bpt6k86243w.item]).</ref>, article qui marque la naissance de la [[théorie des ensembles]]<ref>{{en}} [[Thomas Jech]], « [http://plato.stanford.edu/archives/win2010/entries/set-theory/ Set Theory] », ''[[Stanford Encyclopedia of Philosophy]]'' (édition hiver 2011), [[Edward N. Zalta]] (ed.).</ref>. 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 {{date|7 décembre}} et {{date|9 décembre 1873}} de Georg Cantor à [[Richard Dedekind|Dedekind]]<ref>Lettres traduites in [[Jean Cavaillès]], ''Philosophie mathématique'', annexe « Correspondance Cantor-Dedekind », éd. Hermann, Paris. {{p.|189-251}} de l'édition de 1962.</ref>, où il établit d'une part que l'ensemble des [[nombre algébrique|nombres algébriques]] réels (c'est-à-dire solutions réelles d'une [[équation polynomiale]] à coefficients entiers) est dénombrable<ref>Démonstration due à Dedekind, selon leur correspondance.</ref>, 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 [[nombre transcendant|nombres transcendants]] (c'est-à-dire non algébriques), retrouvant ainsi un [[nombre de Liouville|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 ([[Carl Friedrich Gauss|Gauss]], ou à l'époque de Cantor, [[Leopold Kronecker|Kronecker]])<ref>Voir par exemple {{Ouvrage|langue=en|auteur1=[[William Kneale]]|auteur2=[[Martha Kneale]]|titre=The Development of Logic|éditeur=[[Oxford University Press|Clarendon Press]]|année=1962|passage=673|id=Kneale et Kneale 1962}}.</ref>. 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é]]<ref>Par exemple ''[[Science et Méthode]]'', chap III ''Les mathématiques et la logique'', accessible en ligne [http://www.ac-nancy-metz.fr/enseign/philo/textesph/Scienceetmethode.pdf]</ref>, contestation qui fonde également l'intuitionnisme de [[Luitzen Egbertus Jan Brouwer|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<ref>Brouwer ''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 {{p.|81-96}}, d'après {{Harvsp|Kneale et Kneale 1962|p=673-674}}.</ref>, 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<ref>Richard 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é, {{p.|194}}.</ref> 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é (mathématiques)|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é<ref>Voir {{Harvsp|Kneale et Kneale 1962|p=440}}.</ref>. On cite par exemple souvent [[Galilée (savant)|Galilée]] pour la remarque qu'il y a « autant » de [[carré parfait|carrés parfaits]] que d'entiers naturels. De la même façon, on obtient par une énumération explicite :
* l'ensemble '''N'''<sup>∗</sup> 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 (2''n'').
Dans le cas des nombres premiers on peut utiliser une [[définition par récurrence]] :
* l'ensemble des [[nombre premier|nombres premiers]] est dénombrable ; on définit par récurrence une suite (''p''<sub>''n''</sub>) qui énumère les nombres premiers en posant :
::''p''<sub>0</sub> = 2 ;
::''p''<sub>''n''+1</sub> est le plus petit nombre premier strictement supérieur à ''p''<sub>''n''</sub>.
La démonstration d'[[Euclide]], qui montre que l'ensemble des nombres premiers est infini, permet d'assurer également que ''p''<sub>''n''+1</sub> est bien défini, puisque l'ensemble des nombres premiers strictement supérieurs à ''p''<sub>''n''</sub> est forcément non vide (en l'occurrence il contient le ou les diviseurs premiers de ''p''<sub>0</sub>.''p''<sub>1</sub> … ''p''<sub>''n''</sub>+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 [[Entier relatif|entiers relatifs]] est dénombrable. En effet, la suite ((-1)<sup>''n''</sup>⌈''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 ====
{{Article détaillé|contenu=Article détaillé : [[Théorème de Fueter-Pólya]].}}
[[Image:Pairing natural.svg|vignette|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<ref>Selon 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é.</ref> :
{{Centrer|1=<math>f(p,q)=q+\sum_{0\le k<p+q}(k+1)=q+{(p+q)(p+q+1)\over 2}=\frac{(p+q)^2+p+3q}2</math>.}}
<br>

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

==== Les rationnels ====
[[Image:calkinWilf.svg|gauche|vignette|324px|Une variante due à [[Neil Calkin]] et Herbert Wilf<ref> Neil Calkin et Herbert Wilf (2000), « Recounting the rationals », ''[[The American Mathematical Monthly|American Mathematical Monthly]]'', vol. 107, {{n°|4}}, 2000, {{p.|360–363}} [http://www.math.upenn.edu/~wilf/website/recounting.pdf].</ref> de l'[[arbre de Stern-Brocot]] donne une bijection simple à calculer des [[nombre rationnel|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 :
<br />
<math>{\ \ }^{x_0=0,\ x_{n+1}={1\over \lfloor x_n\rfloor + 1 -\{x_n\}}}</math>
<br />

où ⌊''x''<sub>''n''</sub>⌋ est la partie entière de ''x''<sub>''n''</sub> et ''x''<sub>''n''</sub>=⌊''x''<sub>''n''</sub>⌋ + {x<sub>''n''</sub>}<ref>Caractérisation par récurrence due à Moshe Newman selon ''Recounting the Rationals, Continued'' 2003, Donald E. Knuth, C. P. Rupert, Alex Smith, Richard Stong, ''The American Mathematical Monthly'', vol. 110, {{n°|7}}, 2003, {{p.|642-643}} {{DOI|10.2307/3647762}}.</ref>{{,}}<ref>Voir également : [[Martin Aigner]] et [[Günter M. Ziegler]] (2004), ''[[Proofs from THE BOOK]]'', {{3e}} éd., Springer, {{p.|94-97}}.</ref>.]]

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'''<sup>∗</sup>. 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'''<sup>∗</sup> 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 [[ordre lexicographique|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ôme formel|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 [[Nombre algébrique|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) [[Nombre transcendant|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 (mathématiques)|injection]] de cet ensemble dans '''N'''.

Une propriété essentielle des [[ensemble fini|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'''<sup>*</sup>, 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 [[Suite (mathématiques)#Suites monotones|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 [[bon ordre|bien ordonné]], c'est-à-dire que tout sous-ensemble non vide de '''N''' possède un [[Extremum|plus petit élément]]. En effet, on peut [[définition par récurrence|définir par récurrence]]<ref>L'existence et l'unicité d'une suite définie par récurrence sur les entiers naturels se démontre en [[théorie des ensembles]].</ref> une suite (''a''<sub>''n''</sub>) de la façon suivante :
* ''a''<sub>0</sub> est le plus petit élément de ''A'' (qui existe forcément car ''A'' est non vide) ;
* ''a''<sub>''n''+1</sub> est le plus petit élément de ''A'' supérieur à ''a<sub>n</sub>'' s'il en existe un, et est non défini sinon ou si ''a<sub>n</sub>'' n'est pas défini.
Cette suite établit bien une bijection strictement croissante d'un segment initial des entiers dans ''A''.
{{Démonstration|contenu=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 [[Raisonnement par récurrence#Récurrence simple sur les entiers|récurrence]]<ref group=rec>''a''<sub>0</sub> est un entier naturel, donc ''a''<sub>0</sub> ≥ 0 ; si ''a''<sub>''n''+1</sub> est défini et si ''a<sub>n</sub> ≥ n'', on a (par croissance stricte) ''a''<sub>''n''+1</sub> > ''n'' donc ''a''<sub>''n''+1</sub> ≥ ''n''+1.</ref>, que si  ''a<sub>n</sub>'' est défini, alors ''a<sub>n</sub>'' ≥ ''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<sub>p</sub>'' est défini, et ''a<sub>p</sub> ≥ 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<sub>p</sub>'' 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<sub>n</sub> ≥ b''. Montrons que ''b = a<sub>n</sub>''. Par définition de la suite, si ''n'' = 0 c'est que ''b = a''<sub>0</sub>, le plus petit élément de ''A''. Si ''n'' ≠ 0 c'est que ''n = m''+1, et que ''a<sub>n</sub>'' est le plus petit élément parmi les éléments de ''A'' strictement supérieurs à ''a<sub>m</sub>'', dont ''b'' justement fait partie, par définition de ''n''. Donc, par définition de ''a<sub>n</sub>'', ''a<sub>n</sub> ≤ b'', donc ''b = a<sub>n</sub>''. 

La suite (''a<sub>n</sub>'') 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.
<references group=rec/>
}}

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<sub>p</sub>'').

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'', [[Factorielle|''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 (mathématiques)|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 [[application réciproque|réciproque]] à droite de ''s'', sans faire appel à l'[[axiome du choix]], puisque '''N''', ensemble de départ de la surjection, est [[bon ordre|bien ordonné]] : on prend pour ''i''(''y''), où ''y'' dans ''A'', le plus petit [[antécédent (mathématiques)|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 <math>\varphi</math> de ''A'' sur '''N''' et une bijection <math>\psi</math> de ''B'' sur '''N'''. Définissons:
{{Centrer|1=<math>\lambda : \begin{array}[t]{rcl}A\times B & \longrightarrow & \mathbf{N}\times\mathbf{N} \\ (x, y) & \longmapsto & (\varphi(x), \psi(y))\end{array}</math>}}
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 d'un ensemble fini|cardinal]] fini ''n'', on définit comme ci-dessus une injection du [[produit cartésien]] dans '''N'''<sup>''n''</sup>. 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 [[Nombre rationnel|rationnels]]. En effet '''Z''', ensemble des entiers relatifs, est dénombrable ainsi que '''N'''<sup>*</sup>, ensemble des entiers strictement positifs, et donc leur produit cartésien '''Z''' × '''N'''<sup>*</sup>. Tout rationnel s'écrit d'au moins une manière sous la forme d'une fraction ''p''/''q'' où ''p'' ∈ '''Z''' et ''q'' ∈ '''N'''<sup>*</sup>. Ceci permet de définir une surjection de '''Z''' × '''N'''<sup>*</sup> dans '''Q''', qui est donc au plus dénombrable ; étant infini, il est dénombrable.

=== Réunion finie d'ensembles dénombrables ===
'''Proposition''' — ''La [[Union (mathématiques)#Union d'une famille d'ensembles|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''<sub>0</sub>, …, ''A''<sub>''n''</sub> sont au plus dénombrables, alors leur réunion l'est également. Pour chaque ''A''<sub>i</sub> on a ''f''<sub>''i''</sub> une injection de ''A''<sub>''i''</sub> dans ''N''. On définit une injection de ''A''<sub>0</sub> ∪ …∪ ''A''<sub>''n''</sub> 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''<sub>''i''</sub>. Si de plus l'un des ''A''<sub>''i''</sub> est dénombrable, ''A''<sub>0</sub> ∪ …∪ ''A''<sub>''n''</sub> 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 {{math|'''N'''}}. Il s'agit alors de montrer que si {{math|(''A''<sub>''i''</sub>)<sub>''i'' ∈ '''N'''</sub>}} est une famille d'ensembles dénombrables, alors la réunion de ces ensembles, {{math|§=''A'' = ∪<sub>''i'' ∈ '''N'''</sub> ''A''<sub>''i''</sub>}}, est un ensemble dénombrable. Les {{math|''A''<sub>''i''</sub>}} étant dénombrables, il existe pour chaque entier {{math|''i''}}, une bijection de {{math|'''N'''}} sur {{math|''A''<sub>''i''</sub>}}. En appliquant l'axiome du choix (dénombrable) à la suite {{math|(''F''<sub>''i''</sub>)<sub> ''i'' ∈ '''N'''</sub>}}, où {{math|''F''<sub>''i''</sub>}} est l'ensemble des bijections de {{math|'''N'''}} dans {{math|''A''<sub>''i''</sub>}}, on obtient une suite de fonctions {{math|(''f''<sub>''i''</sub>)<sub>''i'' ∈ '''N'''</sub>}}, où {{math|''f''<sub>''i''</sub>}} est une bijection de {{math|'''N'''}} sur {{math|''A''<sub>''i''</sub>}}. On peut donc définir l'application suivante de {{math|'''N'''<sup>2</sup>}} dans {{math|''A''}} :
{{Centrer|1=<math>f : \begin{array}[t]{rcl} \mathbf{N}\times\mathbf{N} & \longrightarrow & A \\ (i,n) & \longmapsto & f_{i}(n) \end{array}</math>}}
L'application {{math|''f''}} est surjective, du fait que chacune des applications {{math|''f''<sub>''i''</sub>}} l'est, et que  chaque élément de {{math|''A''}} est élément d'au moins un {{math|''A''<sub>''i''</sub>}}.

Ainsi, l'ensemble {{math|''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 {{math|''A''<sub>''i''</sub>}} sont finis, il suffit de reprendre la démonstration précédente, mais avec les {{math|''f''<sub>''i''</sub>}} surjectives de {{math|'''N'''}} dans {{math|''A''<sub>''i''</sub>}}.

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 {{math|'''N'''<sup>''n''</sup>}} pour {{math|''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 ===
{{article détaillé|Ensemble infini non dénombrable}}

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 de la diagonale de Cantor|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}<sup>'''N'''</sup>, 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 ({{nobr|''A''<sup>''B''  × ''C''</sup>}} est équipotent à (''A''<sup>''B''</sup>)<sup><sup>''C''</sup></sup>), celle entre ({0,1}<sup>'''N'''</sup>)<sup><sup>'''N'''</sup></sup> et {0,1}<sup>'''N'''</sup> 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 de la diagonale de Cantor|argument diagonal]] et la notion de [[bon ordre]], ce qui conduit au cardinal [[aleph-un]] et plus généralement à la hiérarchie des [[aleph (nombre)|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|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 ([[#Parties d'un ensemble dénombrable|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<ref>{{Ouvrage|langue=en|auteur1=[[Kurt Gödel]]|titre=The consistency of the axiom of choice and of the generalized continuum-hypothesis with the axioms of set theory|lieu=Princeton, London|éditeur=Princeton University Press H. Milford, Oxford University Press|collection=Annals of mathematics studies|numéro dans collection=3|année=1940|pages totales=66|isbn=978-0-691-07927-1|isbn2=0-691-07927-7|oclc=3316304|lire en ligne=http://www.worldcat.org/title/consistency-of-the-axiom-of-choice-and-of-the-generalized-continuum-hypothesis-with-the-axioms-of-set-theory/oclc/3316304/viewport}}.</ref>.

=== 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 (théorie des ensembles)|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}<sup>'''N'''</sup>, n'est pas dénombrable par [[argument de la diagonale de Cantor|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}<sup>'''N'''</sup> 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}<sup>'''N'''</sup> et donc [[Puissance du continu#La puissance du continu est la cardinalité de l'ensemble des parties de ℕ|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 [[ZFC|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<ref>Voir par exemple {{harvsp|Halmos|texte=l'ouvrage cité de Halmos}}, où les premiers développements sur la cardinalité se font avant d'introduire le remplacement.</ref>. 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-ensemble cofini|sous-ensembles cofinis]] de ''E'' (tous non vides sinon ''E'' serait fini)<ref>On utilise en fait une autre version faible de l'axiome du choix, l'axiome du choix dépendant, qui est cependant plus forte que l'axiome du choix dénombrable, voir les ouvrages cités dans les notes suivantes.</ref>. 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''' [[définition par récurrence|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<ref>Un tel modèle est dû à [[Azriel Lévy]] et [[Solomon Feferman]], mentionné dans {{Ouvrage|langue=en|prénom1=Horst|nom1=Herrlich|titre=Axiom of Choice|éditeur=[[Springer Science+Business Media|Springer-Verlag]]|collection=Lecture Notes in Mathematics|numéro dans collection=1876|année=2006|isbn=}}, ISSN print edition 0075-8434, ISSN electronic edition: 1617-9692 {{p.|23}}.</ref>. 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 [[Paul Cohen|Cohen]] et la méthode de permutation de [[Abraham Adolf Fraenkel|Fraenkel]]-[[Andrzej Mostowski|Mostowski]]<ref name="choice">Voir {{Harvsp|Herrlich|2006}} ; Thomas J. Jech, ''The Axiom of Choice'', Elsevier Science 1973 et l'ouvrage cité en bibliographie.</ref>.

== 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 [[#Les rationnels|rationnels]] est une partie dénombrable [[Partie dense#Exemples|dense]] de l'[[Topologie de la droite réelle|espace '''R''' des réels]]. Cette propriété se généralise aux [[Espace euclidien|'''R'''<sup>''n''</sup>]] et conduit à la notion d'[[espace topologique]] [[Espace séparable|séparable]]. Elle a pour conséquence qu'un ensemble d'[[Ouvert (topologie)|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<ref>Cf. premier théorème de la section [[#Les ensembles finis ou dénombrables|Les ensembles finis ou dénombrables]].</ref>. 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 [[Intervalle (mathématiques)#Décomposition des ouverts de ℝ|décomposition des ouverts de ℝ]]). Une autre propriété de '''R''', celle d'avoir une [[base (topologie)|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éorème de Baire|théorie de Baire]].

=== Logique mathématique ===
En [[algèbre]] c'est une banalité de remarquer que par exemple un [[Groupe (mathématiques)|groupe]] ayant un nombre fini de [[Partie génératrice d'un groupe|générateurs]] est au plus dénombrable. Par exemple deux [[Réflexion (mathématiques)|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 mathématique|logique]]. Il est toujours possible de montrer qu'une [[calcul des prédicats|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]]<ref>Voir {{krivine98}}, chap. 10.</ref>.

=== 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 (mathématiques)|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 ''[[fonction calculable|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éorie axiomatique|théories récursivement axiomatisable]] qui n'est pas [[décidabilité|décidable]], comme l'[[arithmétique de Peano]]<ref>Voir [[problème de la décision|théorème de Church]]</ref>. C'est un ensemble de mots sur un alphabet fini (ou dénombrable), donc dénombrable, mais pas récursivement énumérable.

== Notes et références ==
{{Références}}

== Voir aussi ==
=== Articles connexes ===
* [[Codénombrabilité]]
* [[Condition de chaîne dénombrable]]
* [[Espace de Lindelöf]]
* [[Espace dénombrablement engendré]]
*{{Lien|trad=axioms of countability|Axiomes de dénombrabilité}}

=== Lien externe ===
*[http://www.bibnum.education.fr/mathematiques/theorie-des-nombres/cantor-et-les-infinis 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]].
{{liens}}

=== Bibliographie ===
* {{Halmos65}}.{{Commentaire biblio|Cet ouvrage introductif couvre, sauf références précisées, à peu près tout le contenu de l'article.}}
* {{Cori-Lascar II}}, chapitre 7.{{Commentaire biblio|Cet ouvrage introductif utilise les [[nombre ordinal|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}}

{{Portail|mathématiques}}

[[Catégorie:Théorie des ensembles]]
[[Catégorie:Infini]]