Ensemble dénombrable - Définition

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 de A sur N et une bijection ψ de B sur N. Définissons:

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 fini n, on définit comme ci-dessus une injection du produit cartésien dans Nⁿ. 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 rationnels. En effet Z, ensemble des entiers relatifs, est dénombrable ainsi que N^*, ensembles des entiers strictement positifs, et donc leur produit cartésien Z × N^*. Tout rationnel s'écrit d'au moins une manière sous la forme d'une fraction p/q où p ∈ Z et q ∈ N^*. Ceci permet de définir une surjection de Z × N^* dans Q, qui est donc au plus dénombrable ; étant infini, il est dénombrable.

Réunion finie d'ensembles dénombrables

Proposition — La 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₀, …, A_n sont au plus dénombrables, alors leur réunion l'est également. Pour chaque A_i on a f_i une injection de A_i dans N. On définit une injection de A₀ ∪ …∪ A_n 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_i. Si de plus l'un des A_i est dénombrable, A₀ ∪ …∪ A_n 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 N. Il s'agit alors de montrer que si (A_i)_{i ∈ N} est une famille d'ensembles dénombrables, alors la réunion de ces ensembles, A = ∪_{i ∈ N} A_i, est un ensemble dénombrable. Les A_i étant dénombrables, il existe pour chaque entier i, une bijection de N sur A_i. D'après l'axiome du choix (dénombrable), on a donc une suite de fonctions (f_i)_{i ∈ N}, où f_i est une bijection de N sur A_i. On peut donc définir l'application suivante de N² dans A :

L'application f est surjective, du fait que chacune des applications f_i l'est : chaque élément de A est élément d'au moins un A_i, il est donc atteint par f_i, donc par f.

Ainsi, l'ensemble 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 A_i sont finis, il suffit de reprendre la démonstration précédente, mais avec les f_i surjectives de N dans A_i.

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 Nⁿ pour 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.