human
Prouvez que l'union de plusieurs ensembles dénombrables est dénombrable
gpt
Commençons par une brève revue de ce qu'est un ensemble "dénombrable". Un ensemble est dénombrable s'il existe une correspondance bijective entre l'ensemble et les nombres naturels. Par exemple, prenons $\mathbb{Z}$, qui est composé de tous les entiers. Est-ce que $\mathbb{Z}$ est dénombrable ?

Il peut sembler non dénombrable si l'on choisit une correspondance naïve, par exemple $1 \mapsto 1$, $2 \mapsto 2 ...$, qui laisse tous les nombres négatifs sans correspondance. Mais si nous organisons les entiers de cette manière :
$$0$$
$$1, -1$$
$$2, -2$$
$$3, -3$$
$$...$$

Nous voyons rapidement qu'il existe une correspondance qui fonctionne. On fait correspondre 1 à 0, 2 à 1, 3 à -1, 4 à 2, 5 à -2, etc. Ainsi, pour un élément $x$ dans $\mathbb{Z}$, soit $1 \mapsto x$ si $x=0$, soit $2x \mapsto x$ si $x > 0$, soit $2|x|+1 \mapsto x$ si $x < 0$. Les entiers sont donc dénombrables.

Nous avons prouvé cela en trouvant une correspondance entre les entiers et les nombres naturels. Donc, pour montrer que l'union de plusieurs ensembles dénombrables est dénombrable, nous devons trouver une correspondance similaire. Tout d'abord, décomposons "l'union de plusieurs ensembles dénombrables est dénombrable" :
1. "ensembles dénombrables" est assez simple. Si $S$ est dans notre ensemble d'ensembles, il existe une correspondance bijective entre les éléments de $S$ et $\mathbb{N}$.
2. "plusieurs ensembles dénombrables" nous avons une correspondance bijective entre $\mathbb{N}$ et les ensembles eux-mêmes. En d'autres termes, nous pouvons écrire les ensembles comme $S_1$, $S_2$, $S_3$... Appelons l'ensemble d'ensembles $\{S_n\}, n \in \mathbb{N}$.
3. "l'union de plusieurs ensembles dénombrables est dénombrable". Il existe une correspondance bijective entre les éléments de $\mathbb{N}$ et les éléments de $S_1 \cup S_2 \cup S_3 ...$

Comment prouver cela ? Nous devons trouver une correspondance, bien sûr. Heureusement, il y a une manière simple de le faire. Soit $s_{nm}$ le $m$-ème élément de $S_n$. Nous pouvons le faire car $S_n$ est, par définition du problème, dénombrable. Nous pouvons écrire les éléments de TOUS les ensembles de cette manière :
$$s_{11}, s_{12}, s_{13} ...$$
$$s_{21}, s_{22}, s_{23} ...$$
$$s_{31}, s_{32}, s_{33} ...$$
$$...$$
Maintenant, faisons correspondre $1 \mapsto s_{11}$, $2 \mapsto s_{12}$, $3 \mapsto s_{21}$, $4 \mapsto s_{13}$, etc. Vous remarquerez que si nous barrons chaque élément que nous avons mis en correspondance, nous les barrons en diagonales. Avec $1$, nous barrons la première diagonale, avec $2-3$ nous barrons la deuxième diagonale, avec $4-6$ la troisième diagonale, avec $7-10$ la quatrième diagonale, etc. La $n$-ème diagonale nécessite que nous mettions en correspondance $n$ éléments pour la barrer. Comme nous ne "manquons jamais" d'éléments dans $\mathbb{N}$, nous finirons par créer une correspondance avec chaque élément de chaque diagonale. Puisque évidemment chaque élément de $S_1 \cup S_2 \cup S_3 ...$ se trouve dans l'une des diagonales, nous avons créé une correspondance bijective entre $\mathbb{N}$ et l'ensembl