Ensemble dénombrable - Définition

Ensembles finis et infinis

Un ensemble est fini si, pour un certain entier 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 de cet ensemble dans N.

Une propriété essentielle des 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^*, est donc infini, et de même tout ensemble dénombrable est infini. On peut encore généraliser :

Proposition — Tout ensemble qui contient un ensemble dénombrable 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.

La réciproque de cette proposition, de même que la réciproque de la propriété utilisée pour la démontrer, à savoir que si un ensemble est infini alors il est en bijection avec une de ses parties propres, reposent sur l'axiome du choix (voir la section théorie axiomatique ci-dessous).

Ensembles infinis et dénombrabilité

Exemples d'ensembles infinis non dénombrables

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 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) ne sont pas non plus dénombrables, 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}^N, 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 (A^{B × C} est équipotent à (A^B)^C), celle entre ({0,1}^N)^N et {0,1}^N 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 diagonal et la notion de bon ordre, ce qui conduit au cardinal aleph-1 et plus généralement à la hiérarchie des 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 ), 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 ().

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.

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 (la réunion de A et de B) que l'on prolonge par l'identité sur le 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, {0,1}^N, n'est pas dénombrable par argument diagonal. L'ensemble des suites de 0 et de 1 qui n'utilisent 1 qu'un nombre fini de fois, et donc 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 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 : {0,1}^N est équipotent à l'ensemble 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 pour les réels de ]0,1]. On en déduit que {0,1}^N et donc l'ensemble des parties de N a la puissance du continu.