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 (En théorie des ensembles, un ensemble désigne intuitivement une collection...) 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 (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou...) ensemble équipotent à un ensemble dénombrable (En mathématiques, un ensemble est dit dénombrable, ou infini dénombrable, lorsque...) est lui-même dénombrable.
Un ensemble dénombrable est infini (Le mot « infini » (-e, -s ; du latin finitus,...), car équipotent à , qui est infini. Mais la réciproque est fausse : il existe des ensembles infinis non dénombrables. Le mathématicien (Un mathématicien est au sens restreint un chercheur en mathématiques, par extension toute...) Cantor, qui introduisit la notion de dénombrabilité, démontra que l'ensemble des nombres réels, noté , n'est pas dénombrable.
L'expression ensemble dénombrable a deux définitions :
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 ( Seconde est le féminin de l'adjectif second, qui vient immédiatement après le premier ou qui...) acception qui sera utilisée.
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 a0.
Soit . On suppose avoir prouvé l'existence d'éléments de A notés tels que :
L'ensemble n'est pas vide car A est infini, donc A' admet un plus petit élément que l'on note an + 1. On a alors :
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 (En mathématiques, l'inverse d'un élément x d'un ensemble muni d'une loi de...). 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.
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.
Tout produit cartésien (En mathématiques, le produit cartésien de deux ensembles X et Y, appelé...) d'une famille finie (En mathématiques, la notion de famille est une généralisation de celle de suite, suite finie ou...) 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.
Soient E et F deux ensembles non vides, et f une application de E dans F.
f étant injective, elle induit (L'induit est un organe généralement électromagnétique utilisé en électrotechnique chargé de...) 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.
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 (Un axiome (du grec ancien αξιωμα/axioma,...) 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 (En mathématiques, un ensemble A est un sous-ensemble ou une partie d’un ensemble B, ou...) non vide de E. On définit alors :
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 (Un théorème est une proposition qui peut être mathématiquement démontrée, c'est-à-dire une...) : les trois propositions suivantes sont équivalentes :
La réunion (La Réunion est une île française du sud-ouest de l'océan Indien située...) 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, Ai étant dénombrable, il existe une bijection λi de sur Ai. 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 Ai, 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 Ai sont finis, il suffit de reprendre la démonstration précédente, mais avec λi surjective de sur Ai.
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 :
Voici les premières valeurs de la suite :