Ensemble dénombrable - Définition
La liste des auteurs de cet article est disponible ici.
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 où il établit d'une part que l'ensemble des nombres algébriques réels (c'est-à-dire solutions réelles d'une équation polynômiale à coefficients entiers) est dénombrable, 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 …). 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 Poincaré, 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 sens, 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 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.
Parties d'un ensemble dénombrable
Les entiers naturels
On va utiliser la structure 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 inférieurs à un entier 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 tous sous-ensemble non vide de N possède un plus petit élément. En effet, on peut définir par récurrence une suite (an) de la façon suivante :
- a0 est le plus petit élément de A (qui existe forcément car A est non vide) ;
- an+1 est le plus petit élément de A supérieur à an s'il en existe un, est non défini sinon, ou si an n'est pas défini.
Cette suite établit bien une bijection strictement croissante d'un segment initial des entiers dans A.
Par construction, soit cette suite est définie sur tous les entiers naturels, soit il existe un entier N tel qu'elle soit définie pour les N+1 premiers entiers (les entiers de 0 à N) 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 une récurrence immédiate, que si an est défini, alors an ≥ n. On en déduit donc que si la suite est définie sur tout N, alors elle n'est pas bornée.
Montrons maintenant que l'image de cette suite est A. Soit b un élément de A. Il existe un entier p tel que ap est défini, et ap ≥ b : 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 ap est défini, et l'ensemble des éléments de A supérieurs strictement à ap est vide. On peut donc définir, par la propriété de bon ordre, le plus petit entier n tel que an ≥ b. Par définition de la suite, si n=0 c'est que b=a0 le plus petit élément de A. Sinon c'est que n=m+1, et que an est le plus petit élément parmi les éléments de A strictement supérieurs à am, dont b justement fait partie, par définition de n. Donc, par définition de an, an ≤ b, donc b = an.
La suite (an) définit donc une bijection soit entre N et A, auquel cas par définition A est dénombrable, soit entre l'ensemble des N+1 premiers entiers et A, auquel cas A est par définition fini.Par définition d'une part des ensembles finis, d'autre part des ensembles dénombrables, on déduit immédiatement 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 on remarque que, par une récurrence immédiate, une fonction f strictement croissante vérifie que pour tout entier n, f(n) ≥ n. Si A est bornée par N, la bijection strictement croissante donnée par le lemme ne peut donc être définie au-delà de N. Réciproquement, si la bijection est définie sur les N premiers entiers, N ≠ 0, A est bornée par f(N-1) (par n'importe quel entier si N = 0).
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 qu'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).
