Exercice 47

1. Les singletons conviennent : $\{n\} \subset \{m\}$ signifie $n \in \{m\}$, c'est-à-dire $n = m$. $$\boxed{A_{n} = \{n\}}$$

2. Supposons $B_{X} \subset B_{Y}$. Les entiers pairs de $B_{Y}$ sont les $2k$ avec $k \in Y$, et ses entiers impairs les $2k + 1$ avec $k \notin Y$.

• Si $k \in X$, l'entier pair $2k$ appartient à $B_{X}$, donc à $B_{Y}$ : ainsi $k \in Y$, et $X \subset Y$.

• Si $k \notin X$, l'entier impair $2k + 1$ appartient à $B_{X}$, donc à $B_{Y}$ : ainsi $k \notin Y$. On a donc $\mathbb{N} \setminus X \subset \mathbb{N} \setminus Y$, c'est-à-dire $Y \subset X$.

$$\boxed{B_{X} \subset B_{Y} \Longrightarrow X = Y}$$ En particulier, $B_{X} = B_{Y}$ entraîne $X = Y$ : les parties $B_{X}$ sont deux à deux distinctes. Et si $X \neq Y$, aucune des inclusions $B_{X} \subset B_{Y}$ et $B_{Y} \subset B_{X}$ n'a lieu : les parties $B_{X}$ sont deux à deux incomparables.

Le codage explique ce phénomène : les entiers pairs disent ce que $X$ contient, les impairs ce qu'il ne contient pas. Agrandir $X$ ajoute des pairs, mais retire autant d'impairs, si bien qu'aucune partie $B_{X}$ ne peut en contenir une autre. On obtient ainsi, dans l'ensemble ordonné $(\mathcal{P}(\mathbb{N}), \subset)$, une famille d'éléments deux à deux incomparables qui est indexée par $\mathcal{P}(\mathbb{N})$ tout entier.

3. Chaque $D_{i}$ est une partie non vide de $\mathbb{N}$ ; elle possède un plus petit élément, ce qui définit l'application $i \mapsto \min D_{i}$. Si $\min D_{i} = \min D_{j} = k$, alors $k \in D_{i} \cap D_{j}$ : cette intersection n'est pas vide, et la disjonction des parties d'indices distincts impose $i = j$. $$\boxed{i \mapsto \min D_{i} \text{ est injective.}}$$ Supposons maintenant $I = \mathcal{P}(\mathbb{N})$, et notons $\iota : \mathcal{P}(\mathbb{N}) \to \mathbb{N}$ l'injection obtenue. On définit $s : \mathbb{N} \to \mathcal{P}(\mathbb{N})$ en posant $s(n) = X$ si $n = \iota(X)$, la partie $X$ étant unique par injectivité, et $s(n) = \varnothing$ si $n$ n'est pas dans l'image de $\iota$. Alors $s\big(\iota(X)\big) = X$ pour toute partie $X$ : l'application $s$ est une surjection de $\mathbb{N}$ sur $\mathcal{P}(\mathbb{N})$, ce que le théorème 3 du cours (Cantor) interdit. $$\boxed{\text{Aucune famille de parties non vides de } \mathbb{N} \text{ deux à deux disjointes n'est indexée par } \mathcal{P}(\mathbb{N}).}$$

4. (a) L'entier $c(P)$ est bien défini : $P$ figure dans la suite $(F_{j})$, donc l'ensemble des $j$ tels que $F_{j} = P$ est une partie non vide de $\mathbb{N}$, qui a un plus petit élément. Si $c(P) = c(Q) = j$, alors $P = F_{j} = Q$ : l'application $c$ est injective.

Les éléments pairs de $T_{n}(X)$ sont inférieurs ou égaux à $2n$, donc le plus grand élément de $T_{n}(X)$ est $2n + 1$. Deux entiers $n \neq n'$ donnent donc des parties $T_{n}(X) \neq T_{n'}(X)$, et, $c$ étant injective, l'application $n \mapsto c\big(T_{n}(X)\big)$ est une injection de $\mathbb{N}$ dans $C_{X}$. Si $C_{X}$ était finie, à $p$ éléments, la restriction de cette injection à $[\![0\,;p]\!]$, qui a $p + 1$ éléments, serait une injection d'un ensemble à $p + 1$ éléments dans un ensemble à $p$ éléments, ce que le théorème 2 du cours interdit. $$\boxed{c \text{ est injective, et } C_{X} \text{ est infinie.}}$$

(b) Par définition de $m$, les parties $X$ et $Y$ ont les mêmes éléments strictement inférieurs à $m$, et $m$ appartient à l'une sans appartenir à l'autre ; quitte à les échanger, on suppose $m \in X$ et $m \notin Y$.

• Si $n < m$, alors $X \cap [\![0\,;n]\!] = Y \cap [\![0\,;n]\!]$, donc $T_{n}(X) = T_{n}(Y)$, et l'entier $c\big(T_{n}(X)\big)$ appartient à $C_{X} \cap C_{Y}$.

• Réciproquement, soit $z \in C_{X} \cap C_{Y}$, de la forme $z = c\big(T_{n}(X)\big) = c\big(T_{n'}(Y)\big)$. L'injectivité de $c$ donne $T_{n}(X) = T_{n'}(Y)$, et la comparaison des plus grands éléments donne $n = n'$. Si l'on avait $n \geqslant m$, l'entier $2m$ appartiendrait à $T_{n}(X)$, puisque $m \in X$, donc à $T_{n}(Y)$, et l'on aurait $m \in Y$ : c'est exclu. Donc $n < m$.

Ainsi $C_{X} \cap C_{Y} = \big\{c\big(T_{n}(X)\big) \mid n \in [\![0\,;m - 1]\!]\big\}$ est l'image de $[\![0\,;m - 1]\!]$ par l'injection de la question (a) : elle est en bijection avec cet intervalle. $$\boxed{\mathrm{card}(C_{X} \cap C_{Y}) = m}$$

(c) On raisonne par contraposée : soit $X \neq Y$. La partie $C_{X}$ est la réunion disjointe de $C_{X} \setminus C_{Y}$ et de $C_{X} \cap C_{Y}$, qui est finie d'après (b). Si $C_{X} \setminus C_{Y}$ était finie, $C_{X}$ le serait aussi, d'après le lemme 4 du cours, ce qui contredit (a). La partie $C_{X} \setminus C_{Y}$ est donc infinie, et $C_{X} \,\Delta\, C_{Y}$, qui la contient, l'est aussi, d'après le lemme 3. $$\boxed{C_{X} \,\Delta\, C_{Y} \text{ finie} \Longrightarrow X = Y}$$

(d) Les parties $C_{X}$, pour $X \in \mathcal{P}(\mathbb{N})$, sont infinies, deux à deux distinctes d'après (c), et deux à deux presque disjointes d'après (b). La question 3 interdisait une telle famille de parties deux à deux disjointes ; il suffit d'autoriser des intersections finies pour qu'elle existe. $$\boxed{(C_{X})_{X \in \mathcal{P}(\mathbb{N})} \text{ est une famille de parties infinies de } \mathbb{N} \text{, deux à deux presque disjointes.}}$$

On lit la construction sur cet arbre. Le nœud de profondeur $n$ atteint en descendant à droite au niveau $k$ si $k \in X$, et à gauche sinon, représente la partie $X \cap [\![0\,;n]\!]$, codée par l'entier $c\big(T_{n}(X)\big)$ ; la partie $C_{X}$ est l'ensemble des codes des nœuds de la branche de $X$. Ici $X$ et $Y$ contiennent $0$, ne contiennent pas $1$, puis se séparent en $m = 2$ : leurs branches n'ont en commun que les deux nœuds du tronc, en bleu pétrole, et $C_{X} \cap C_{Y}$ a deux éléments.

À retenir : l'intuition selon laquelle des parties infinies d'intersections finies seraient « presque » disjointes, donc pas plus nombreuses que des parties disjointes, est fausse. Des parties disjointes s'injectent dans $\mathbb{N}$ par leurs plus petits éléments, alors que les branches d'un arbre binaire, qui partagent deux à deux un tronc fini, sont en bijection avec les parties de $\mathbb{N}$ et ne peuvent donc pas, d'après le théorème de Cantor, être numérotées par les entiers.