Un ensemble E est dit dénombrable s'il est équipotent à l'ensemble des entiers naturels , c'est-à-dire s'il existe une bijection de E sur  ; cela équivaut à l'existence d'une bijection de sur E.

Naïvement, dire qu'un ensemble E est dénombrable signifie qu'il est possible de compter un à un chacun de ses éléments, et de leur attribuer un rang : on peut numéroter les éléments de E sans omission ni répétition, en utilisant tous les entiers naturels.

L'ensemble des entiers naturels est dénombrable, car un ensemble est toujours équipotent à lui-même, et tout ensemble équipotent à un ensemble dénombrable est lui-même dénombrable.

Un ensemble dénombrable est infini, car équipotent à , qui est infini. Mais la réciproque est fausse : il existe des ensembles infinis non dénombrables. Le mathématicien Cantor, qui introduisit la notion de dénombrabilité, démontra que l'ensemble des nombres réels, noté , n'est pas dénombrable.

Vocabulaire

L'expression ensemble dénombrable a deux définitions :

• Certaines publications emploient cette expression non seulement dans le sens vu ci-dessus mais aussi pour désigner un ensemble fini
• D'autres utilisent cette expression uniquement pour les ensembles satisfaisant la définition, et préfèrent employer l'expression ensemble au plus dénombrable pour désigner un ensemble soit fini, soit dénombrable.

Il faut donc prendre garde à la convention utilisée lors de la lecture d'une publication sur le sujet. Dans cet article, c'est la seconde acception qui sera utilisée.

Ensembles usuels et dénombrabilité

• Par définition, l'ensemble des entiers naturels est dénombrable.

• L'ensemble des entiers naturels non nuls est dénombrable. En effet, l'application est bijective.

• L'ensemble des entiers naturels pairs, noté , est dénombrable. En effet, l'application est bijective.

• L'ensemble des carrés parfaits, noté ici , est dénombrable. En effet, l'application est bijective.
  On doit à Galilée la remarque qu'il y a " autant " de carrés parfaits que d'entiers naturels, mettant ainsi en défaut l'affirmation classique (qu'on trouve dans les Éléments d'Euclide): " Le tout est plus grand que la partie. "

• L'ensemble des entiers relatifs est dénombrable. En effet, l'application est bijective.

• L'ensemble des couples d'entiers naturels est dénombrable, car l'application est bijective (tout entier naturel strictement positif se factorise de manière unique sous forme du produit d'une puissance de 2, et d'un entier impair).

• L'ensemble des nombres rationnels est dénombrable (voir plus loin une démonstration de cette affirmation).

• L'ensemble des nombres algébriques (réels ou complexes) est dénombrable. Comme aucun des deux ensembles et n'est dénombrable, on en déduit l'existence de nombres (réels ou complexes) transcendants.

Quelques propriétés

Partie d'un ensemble dénombrable

Toute partie A de est au plus dénombrable.

En effet, si A est fini, alors a fortiori A est au plus dénombrable.

Supposons maintenant A infini. Étant une partie non-vide de , A admet donc un plus petit élément. Notons le a₀.

Soit . On suppose avoir prouvé l'existence d'éléments de A notés tels que :

(i)

(ii)

L'ensemble n'est pas vide car A est infini, donc A' admet un plus petit élément que l'on note a_{n + 1}. On a alors :

donc a_n < a_{n + 1}

On a ainsi montré par récurrence l'existence d'une suite strictement croissante. Posons . B est dénombrable et inclus dans A. Montrons l'inclusion inverse. Soit n élément de A. La suite étant strictement croissante, on a , donc d'après (ii) , donc et donc .

On a ainsi prouvé que A = B, et donc que A est dénombrable.

Dans tous les cas, A est donc au plus dénombrable.

Toute partie d'un ensemble au plus dénombrable est au plus dénombrable.

Soit E un ensemble au plus dénombrable et F une partie de E. Soit une bijection de E sur une partie de . La restriction de à F est une bijection de F sur qui est une partie de , donc au plus dénombrable d'après la propriété ci-dessus. F étant équipotent à est elle-même au plus dénombrable.

Produit d'ensembles dénombrables

Tout produit cartésien d'une famille finie d'ensembles dénombrables est dénombrable.

Soient A et B deux ensembles dénombrables. Il existe une bijection de A sur et une bijection ψ de B sur . Définissons:

Cette application est bijective de sur qui est dénombrable. Donc est dénombrable.

Une récurrence permet d'étendre ce résultat au produit cartésien de toute famille finie d'ensembles dénombrables.

Image et image réciproque d'ensembles dénombrables

Soient E et F deux ensembles non vides, et f une application de E dans F.

1. Si f est injective et si F est au plus dénombrable, alors E est au plus dénombrable.

f étant injective, elle induit une bijection de E sur f(E). Or, f(E) est une partie de F et est donc au plus dénombrable. E est donc au plus dénombrable.

2. Si f est surjective et si E est au plus dénombrable, alors F est au plus dénombrable.

E étant au plus dénombrable, il existe bijective, avec . Or est bien ordonné, donc E peut être muni d'un bon ordre (défini ici explicitement, sans le recours habituel à l'axiome du choix), en posant :

 ;

dès lors, toute partie non vide de E possède un minimum.

Soit ; comme f est surjective, f ^{− 1}({y}) est un sous-ensemble non vide de E. On définit alors :

( est le plus petit antécédent de y par f)

Par construction, pour tout , donc l'application g est injective. L'ensemble E étant au plus dénombrable, il résulte de 1. que F est au plus dénombrable.

Corollaire : les trois propositions suivantes sont équivalentes :

• L'ensemble E est au plus dénombrable.
• Il existe une injection de E vers .
• Il existe une surjection de vers E.

Réunion d'ensembles dénombrables

La réunion de toute famille dénombrable d'ensembles dénombrables est dénombrable

Plus formellement, si I est un ensemble dénombrable et si est une famille d'ensembles dénombrables, alors est un ensemble dénombrable. I étant dénombrable, il existe une bijection f de sur I, et pour tout i de I, A_i étant dénombrable, il existe une bijection λ_i de sur A_i. On pose alors :

.

est bien une application dont l'ensemble d'arrivée est A puisque , donc .

Montrons que est surjective. Soit . Il existe i tel que . Soit tel que i = f(a). et λ_i est une bijection de dans A_i, donc , ce qui donne bien

Ainsi, est surjective et est dénombrable, donc A est dénombrable.

Toute réunion finie d'ensembles dénombrables est dénombrable

Dans le cas où I est fini, il suffit de reprendre la démonstration précédente, mais avec f surjective de sur I.

Toute réunion au plus 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 λ_i surjective de sur A_i.

Dénombrabilité de l'ensemble des rationnels

On justifie ici, à l'aide de certaines des propriétés précédemment établies, la dénombrabilité de l'ensemble des rationnels.

L'application est surjective, car tout rationnel s'écrit d'au moins une manière sous la forme , où et  ; de plus, est dénombrable (produit cartésien de deux ensembles dénombrables).

L'existence de cette surjection implique alors que est au plus dénombrable ; étant infini, il est donc dénombrable.

On peut aussi montrer que la suite définie ci-dessous donne une bijection entre et l'ensemble des rationnels positifs ou nuls :

x₀ = 0

avec , où E(x) désigne la partie entière de x.

Voici les premières valeurs de la suite :