1. Modélisation. Un objet Date est entièrement déterminé par un triplet d'entiers : une année, un mois, un jour. L'ensemble des objets possibles est donc une partie de $\mathbb{N}^3$ :

$E = \{\, (a, m, j) \in \mathbb{N}^3 \;:\; 1 \le m \le 12 \;\text{et}\; 1 \le j \le J(m, a) \,\}$

où $J(m, a)$ est le nombre de jours du mois $m$ de l'année $a$ : 31 pour janvier, mars, mai, juillet, août, octobre, décembre ; 30 pour avril, juin, septembre, novembre ; 28 ou 29 pour février selon que l'année est bissextile ou non.

Le point important n'est pas la formule mais la démarche : un objet logiciel se décrit comme un élément d'un produit cartésien de domaines simples, et les contraintes de validité se traduisent en conditions sur les composantes. C'est exactement la façon dont le cours présente les données d'un programme : toute donnée est codée sur une partie finie de $\mathbb{N}$.

2. Cardinal. Il n'y a pas de formule close immédiate : le nombre de jours de février dépend de l'année. On découpe donc $E$ selon l'année, ce qui en donne une partition, et on applique le principe additif (si les $(E_i)$ forment une partition de $E$, alors $|E| = \sum_i |E_i|$).

$|E| = \sum_{a} \sum_{m=1}^{12} J(m, a) = \sum_{a} \big(337 + J(2, a)\big)$

car les onze mois autres que février totalisent toujours $31 \times 7 + 30 \times 4 = 337$ jours.

Avec l'hypothèse usuelle des années 1 à 9999 et de la règle grégorienne (bissextile si divisible par 4, sauf par 100, sauf par 400), le nombre d'années bissextiles vaut

$\left\lfloor \frac{9999}{4} \right\rfloor - \left\lfloor \frac{9999}{100} \right\rfloor + \left\lfloor \frac{9999}{400} \right\rfloor = 2499 - 99 + 24 = 2424$

d'où

$|E| = 9999 \times 365 + 2424 = 3\,649\,635 + 2424 = 3\,652\,059.$

Ce qu'il faut retenir. Le cardinal d'un ensemble de données se calcule en partitionnant selon le paramètre qui complique le comptage (ici l'année), puis en appliquant le principe additif. Toute autre hypothèse de départ (années 1970-2038, par exemple) donne un autre total, mais la méthode reste identique — c'est elle qui est évaluée.

1. $\{0\} \subseteq \emptyset$ est faux : l'élément $0$ appartient à $\{0\}$ mais pas à $\emptyset$, et l'inclusion exige que tout élément du premier soit élément du second. $\{0\} \in B$ est faux : les seuls éléments de $B$ sont $0$ et $1$, et l'ensemble $\{0\}$ n'est ni l'un ni l'autre. $\{0\} \in \mathcal{P}(B)$ est vrai : $\mathcal{P}(B)$ est l'ensemble des parties de $B$, et $\{0\}$ est bien une partie de $B$.

La leçon : appartenance et inclusion sont deux relations différentes. Confondre $\in$ et $\subseteq$ est l'erreur la plus fréquente sur ce chapitre, et elle est fatale dès qu'on parle d'ensembles d'ensembles.

2. $B \subseteq B$ est vrai : l'inclusion est réflexive, tout ensemble est partie de lui-même. C'est aussi le cas de $\emptyset \subseteq \emptyset$.

3. Les parties de $B$ sont l'ensemble vide, les deux singletons et $B$ lui-même :

$\mathcal{P}(B) = \{\, \emptyset,\; \{0\},\; \{1\},\; \{0,1\} \,\}, \qquad |\mathcal{P}(B)| = 4 = 2^{2}.$

4. $\mathcal{P}(\mathcal{P}(B))$ a pour éléments les parties de $\mathcal{P}(B)$, qui compte 4 éléments, donc

$|\mathcal{P}(\mathcal{P}(B))| = 2^{4} = 16.$

Ce sont : $\emptyset$, les quatre singletons $\{\emptyset\}$, $\{\{0\}\}$, $\{\{1\}\}$, $\{\{0,1\}\}$, les six paires $\{\emptyset,\{0\}\}$, $\{\emptyset,\{1\}\}$, $\{\emptyset,\{0,1\}\}$, $\{\{0\},\{1\}\}$, $\{\{0\},\{0,1\}\}$, $\{\{1\},\{0,1\}\}$, les quatre triplets et $\mathcal{P}(B)$ tout entier. Le compte suit la formule $|\mathcal{P}(E)| = 2^{|E|}$ pour $E$ fini.

5. Avec $\emptyset$ à la place de $B$ : $\{0\} \subseteq \emptyset$ reste faux ; $\{0\} \in \emptyset$ est faux (l'ensemble vide n'a aucun élément) et $\{0\} \in \mathcal{P}(\emptyset)$ est faux aussi, car $\mathcal{P}(\emptyset) = \{\emptyset\}$ et $\{0\} \neq \emptyset$. En revanche $\emptyset \subseteq \emptyset$ est vrai, $\emptyset \in \mathcal{P}(\emptyset)$ est vrai, $\mathcal{P}(\emptyset) = \{\emptyset\}$ a pour cardinal $1 = 2^0$, et $\mathcal{P}(\mathcal{P}(\emptyset)) = \{\emptyset, \{\emptyset\}\}$ a pour cardinal $2$.

Le pont avec la représentation. Ces comptages ne sont pas gratuits. Une partie d'un ensemble à $k$ éléments se code exactement par un mot binaire de longueur $k$ : c'est sa fonction caractéristique, qui vaut 1 sur les éléments de la partie et 0 ailleurs. Ainsi $\mathcal{P}(B)$ correspond aux $2^2 = 4$ mots de longueur 2, et $\mathcal{P}(\mathcal{P}(B))$ aux mots de longueur 4. Compter les parties et compter les mots binaires, c'est le même calcul — celui qui donne $2^8 = 256$ valeurs à un octet.

Un octet est un mot de 8 bits. Le nombre de mots de longueur $p$ sur un alphabet de $n$ symboles est $n^{p}$ (arrangement avec répétition : $n$ choix indépendants à chacune des $p$ positions). Ici $n = 2$ et $p = 8$, donc il existe

$2^{8} = 256 \ \text{octets distincts}.$

Chaque type étant codé sur un nombre entier d'octets, il admet $2^{k}$ motifs de bits distincts, où $k$ est le nombre de bits :

Précision sur les types signés. Le nombre de motifs distincts est $2^{k}$ dans tous les cas. Pour un type signé, ces $2^{k}$ motifs se répartissent sur l'intervalle $[-2^{k-1}, 2^{k-1}-1]$ ; pour un type non signé, sur $[0, 2^{k}-1]$. Ce qui compte ici est la taille du réservoir de motifs, car c'est elle qui borne tout ce que le type peut représenter.

La conséquence décisive. Un double ne dispose que de $2^{64} \approx 1{,}8 \times 10^{19}$ motifs, alors que l'intervalle $[0,1]$ contient une infinité non dénombrable de réels (exercice 4). Le principe des tiroirs interdit donc toute correspondance injective entre les réels et les double : deux réels distincts partagent forcément un même motif. C'est la raison mathématique de l'approximation des flottants — celle qui fait que 0.1 + 0.2 ne vaut pas 0.3.

Étape 1 — ce qu'est une donnée machine. Toute donnée stockée est une suite finie de bits, donc un mot sur l'alphabet $B = \{0,1\}$. L'ensemble des données machine est contenu dans $B^{*}$, l'ensemble de tous les mots binaires, qui est dénombrable (exercice 5). En particulier l'ensemble des valeurs d'un double est fini, de cardinal $2^{64}$.

Étape 2 — ce qu'est un codage. Le cours définit un codage de $A$ dans $B$ comme une application injective de $A^{+}$ dans $B^{+}$ : deux objets différents doivent avoir deux codes différents, sinon le décodage est ambigu. Coder les réels, c'est donc chercher une injection de $\mathbb{R}$ vers les données machine.

Étape 3 — le principe des tiroirs. Le cours énonce : si $|E| \gt |F|$, il n'existe pas d'injection de $E$ dans $F$. Or $\mathbb{R}$ n'est pas dénombrable, tandis que les données machine le sont (exercice 5). Il n'existe donc aucune injection de $\mathbb{R}$ vers les données machine.

Le pont entre $\mathbb{R}$ et l'exercice 6. À chaque suite $s = (d_1, d_2, \dots)$ de 0 et de 1, associons le réel $\varphi(s) = \sum_{i \ge 1} d_i\,3^{-i}$ : on lit la suite comme un développement en base 3 n'utilisant que les chiffres 0 et 1. Cette application est injective. En effet, si deux suites distinctes donnaient le même réel, en notant $k$ le premier indice où elles diffèrent (disons $d_k = 1$, $e_k = 0$), on aurait

$\left|\sum_{i \gt k} (e_i - d_i)\,3^{-i}\right| \le \sum_{i \gt k} 3^{-i} = \frac{3^{-k}}{2} \lt 3^{-k},$

inégalité contredisant l'égalité $\sum_{i \gt k}(e_i - d_i)3^{-i} = 3^{-k}$ qu'imposerait le même réel. Si $\mathbb{R}$ était dénombrable, la partie $]0,1[$ le serait aussi, donc $S$ — en bijection avec $\varphi(S) \subseteq \;]0,1[$ — le serait également, ce qui contredit l'exercice 6. $\mathbb{R}$ n'est donc pas dénombrable, comme l'énonce le cours.

Conclusion. Toute représentation des réels sur une machine est nécessairement non injective : il existe toujours deux réels distincts ayant la même représentation. Autrement dit, la représentation est une approximation, jamais une identité. C'est exactement ce qu'on observe avec les flottants IEEE 754 : la mantisse ne retient qu'un nombre fini de bits significatifs, si bien que $0{,}1$ est arrondi au flottant le plus proche, et que

1print(0.1 + 0.2)         # 0.300000000000000042print(0.1 + 0.2 == 0.3)  # False

Conséquence pratique. Ne jamais tester l'égalité de deux flottants : comparer un écart à une tolérance, ou compter en entiers quand l'exactitude est requise. Le défaut n'est pas un bug du langage mais une impossibilité mathématique.

1. Un codage explicite des parties finies. À une partie finie non vide $S = \{n_1 \lt n_2 \lt \dots \lt n_k\}$ de $\mathbb{N}$, associons le mot binaire $w(S)$ de longueur $n_k + 1$ dont les 1 occupent les positions $n_1, n_2, \dots, n_k$ (positions numérotées à partir de 0), et posons $w(\emptyset) = \varepsilon$. Autrement dit, $w(S)$ est la fonction caractéristique de $S$, tronquée juste après son dernier 1.

• $w$ est injective : $S$ se relit sur $w(S)$ comme l'ensemble des positions des 1, et $w(S)$ détermine $S$ sans ambiguïté.
• L'image de $w$ est l'ensemble $W = \{\varepsilon\} \cup \{\text{mots se terminant par } 1\}$, qui est une partie infinie de $B^{*}$.

On obtient donc une bijection explicite entre $F$ et $W$. Pour obtenir une bijection entre $F$ et $B^{*}$ entier, il suffit d'apparier les deux énumérations : on range les mots de $B^{*}$ dans l'ordre hiérarchique (par longueur croissante, puis lexicographique) et les mots de $W$ dans ce même ordre, et on associe le $i$-ème mot de $W$ au $i$-ème mot de $B^{*}$. Deux ensembles infinis dénombrables sont toujours en bijection, et cette construction en exhibe une.

2. $B^{*}$ est dénombrable. On range les mots par longueur croissante, puis par ordre lexicographique à longueur fixe :

$\varepsilon,\; 0,\; 1,\; 00,\; 01,\; 10,\; 11,\; 000,\; 001, \dots$

Ce rangement attribue à chaque mot un rang unique, donc définit une bijection entre $B^{*}$ et $\mathbb{N}$ : c'est la preuve donnée par le cours. Le décompte par longueur est utile à retenir : il y a $2^{L}$ mots de longueur $L$ et $2^{L+1} - 1$ mots de longueur au plus $L$ ; le rang d'un mot de longueur $L$ est donc compris entre $2^{L}$ et $2^{L+1} - 1$.

3. Conclusion. $F$ est en bijection avec $W$, qui est une partie de $B^{*}$. Or toute partie d'un ensemble dénombrable est finie ou dénombrable, et $W$ est infini. Donc $F$ est dénombrable.

Lecture informatique. Ce résultat dit exactement que l'ensemble des données que peut manipuler une machine est dénombrable : un fichier, un graphe fini, un arbre, une liste de rationnels se codent tous par un mot fini sur un alphabet fini. C'est la première moitié de l'argument de l'exercice 4.

1. La fonction caractéristique. À chaque partie $A \subseteq \mathbb{N}$, associons sa fonction caractéristique $\chi_A : \mathbb{N} \to \{0,1\}$, définie par $\chi_A(n) = 1$ si $n \in A$ et $\chi_A(n) = 0$ sinon. La suite infinie $(\chi_A(0), \chi_A(1), \chi_A(2), \dots)$ détermine $A$ et réciproquement : deux parties distinctes diffèrent sur au moins un entier, donc leurs suites diffèrent ; toute suite de 0 et de 1 est la fonction caractéristique de la partie formée des indices où elle vaut 1. C'est donc une bijection entre $\mathcal{P}(\mathbb{N})$ et $S$.

2. La diagonale de Cantor. Supposons, par l'absurde, que $S$ soit dénombrable : on peut alors ranger ses éléments en une liste

1s0 = 1 0 1 1 0 ...2s1 = 0 0 1 0 1 ...3s2 = 1 1 1 0 0 ...4s3 = 0 1 0 0 1 ...5...

Construisons la suite $s^{*}$ dont le $n$-ième terme est l'opposé du $n$-ième terme de $s_n$, c'est-à-dire $1$ si le $n$-ième terme de $s_n$ vaut $0$, et $0$ sinon. Par construction, $s^{*}$ diffère de $s_n$ au moins en position $n$, pour tout entier $n$. Donc $s^{*}$ ne figure nulle part dans la liste, qui est incomplète : contradiction. Aucune liste ne peut épuiser $S$, donc $S$ n'est pas dénombrable.

3. Conclusion. Une bijection conserve le cardinal (principe d'égalité : s'il existe une bijection entre $E$ et $F$, alors $|E| = |F|$). Si $\mathcal{P}(\mathbb{N})$ était dénombrable, $S$ le serait aussi. Comme $S$ ne l'est pas, $\mathcal{P}(\mathbb{N})$ ne l'est pas non plus.

Le résultat général. Pour $E$ fini, $|\mathcal{P}(E)| = 2^{|E|}$. Le cours note que l'analogie se rompt à l'infini : si $E$ est infini dénombrable, $\mathcal{P}(E)$ n'est pas dénombrable. La diagonale de Cantor est l'argument qui traite tous ces cas d'un coup — c'est aussi, au signe près, celui qui prouve que $\mathbb{R}$ n'est pas dénombrable.

Méthode 1 — bijection explicite. Posons

$f(n) = \begin{cases} n & \text{si } n \le 2 \\ n + 1 & \text{si } n \ge 3 \end{cases}$

soit $0 \mapsto 0$, $1 \mapsto 1$, $2 \mapsto 2$, $3 \mapsto 4$, $4 \mapsto 5$, etc. Cette application est injective (deux antécédents distincts ont des images distinctes) et surjective sur $\mathbb{N} \setminus \{3\}$ (tout entier différent de 3 a un antécédent). C'est donc une bijection, et $\mathbb{N} \setminus \{3\}$ est dénombrable.

Méthode 2 — par inclusion. $\mathbb{N} \setminus \{3\}$ est une partie de $\mathbb{N}$. Or toute partie d'un ensemble dénombrable est finie ou dénombrable. Comme $\mathbb{N} \setminus \{3\}$ est infini, il est dénombrable.

Généralisation. Le même argument montre que retirer un nombre fini d'éléments à un ensemble dénombrable le laisse dénombrable. Ce n'est pas vrai pour un retrait infini : retirer une infinité d'entiers peut encore laisser un ensemble dénombrable, mais retirer les rationnels de $\mathbb{R}$ laisse un ensemble qui n'est plus dénombrable, puisque $\mathbb{R}$ lui-même ne l'est pas.

Soit $n$ le nombre de membres du club, et considérons la grandeur « nombre d'adversaires distincts déjà rencontrés ». Comme tous les membres jouent, cette grandeur vaut au moins 1 pour chacun d'eux. Comme on ne joue pas contre soi-même, elle vaut au plus $n - 1$.

Il n'y a donc que $n - 1$ valeurs possibles — $1, 2, \dots, n - 1$ — pour $n$ joueurs. Par le principe des tiroirs ($n$ objets rangés dans $n-1$ tiroirs : au moins un tiroir contient deux objets), deux joueurs au moins partagent le même nombre d'adversaires distincts. $\blacksquare$

Pourquoi l'hypothèse « tous les membres jouent » est utile. Sans elle, la valeur 0 serait possible et il y aurait $n$ valeurs pour $n$ joueurs : plus de collision forcée par ce seul argument. En réalité le résultat tient quand même, mais il faut un argument plus fin : les valeurs $0$ et $n-1$ ne peuvent pas être prises simultanément (si un joueur n'a affronté personne, personne n'a pu l'affronter, donc aucun joueur n'a $n-1$ adversaires). Il reste donc au plus $n-1$ valeurs atteignables pour $n$ joueurs, et la collision est forcée.

Lien avec l'encodage. Le principe des tiroirs est le même outil que dans l'exercice 4 : dès que l'ensemble des états possibles est plus petit que l'ensemble des objets à décrire, deux objets partagent une description. C'est la raison profonde pour laquelle aucune compression sans perte n'est universelle, et pour laquelle les tables de hachage admettent des collisions.

Partitionnons l'ensemble $\{1, 2, \dots, 8\}$ en quatre paires dont la somme vaut 9 :

$\{1, 8\}, \quad \{2, 7\}, \quad \{3, 6\}, \quad \{4, 5\}.$

Choisir 5 entiers distincts dans $\{1, \dots, 8\}$, c'est ranger 5 objets dans ces 4 paires, qui jouent le rôle des tiroirs. Par le principe des tiroirs, deux des entiers choisis appartiennent à la même paire. Comme les entiers choisis sont distincts, ces deux entiers sont les deux éléments différents de cette paire, et leur somme vaut 9 par construction. $\blacksquare$

La méthode, plus que le résultat. Le principe des tiroirs ne s'applique jamais tout seul : il faut fabriquer les tiroirs. Ici, la conclusion porte sur une somme, donc les tiroirs sont les paires de somme 9 ; la partition $\{1,\dots,8\}$ en 4 paires est ce qui rend l'argument possible. Chercher les tiroirs revient à chercher la bonne partition de l'énoncé.

Variante. Pour des nombres entre 1 et 10, il faut en prendre 6 pour être certain d'obtenir deux fois la somme 11 (les tiroirs sont alors les 5 paires $\{1,10\}, \{2,9\}, \{3,8\}, \{4,7\}, \{5,6\}$).

Soient $A$ et $B$ deux ensembles dénombrables. Par définition de la différence ensembliste,

$A \setminus B = \{\, x \in A \;:\; x \notin B \,\} \subseteq A.$

$A \setminus B$ est donc une partie de l'ensemble dénombrable $A$. Or le cours établit que toute partie d'un ensemble dénombrable est finie ou infinie dénombrable — c'est-à-dire, dans sa terminologie où les ensembles finis sont eux aussi dits dénombrables, que toute partie d'un ensemble dénombrable est dénombrable. D'où le résultat. $\blacksquare$

Remarque. L'argument est presque trop court : tout le contenu est dans la propriété « toute partie d'un ensemble dénombrable est dénombrable », qui vient de la définition même (être en bijection avec $\mathbb{N}$ ou avec une partie de $\mathbb{N}$ — une partie d'une partie est une partie). Le réflexe à acquérir : pour montrer qu'un ensemble est dénombrable, il suffit souvent de l'injecter dans un ensemble dénombrable connu.

Décomposition en union. Réécrivons $A + B$ comme une union indexée par $A$ :

$A + B = \bigcup_{a \in A} (a + B), \qquad \text{où } a + B = \{\, a + b \;:\; b \in B \,\}.$

Chaque terme est dénombrable. Pour $a \in A$ fixé, l'application $\tau_a : G \to G$, $x \mapsto a + x$ est une bijection (sa réciproque est la translation par $-a$, qui existe puisque $G$ est un groupe). La restriction de $\tau_a$ à $B$ est donc une bijection de $B$ sur $a + B$, si bien que $|a + B| = |B|$. Or $B \subseteq G$ est une partie d'un ensemble dénombrable, donc $B$ est dénombrable, et $a + B$ aussi.

L'union est dénombrable. $A + B$ est donc une union dénombrable d'ensembles dénombrables : l'ensemble d'indices $A$ est dénombrable, et chacun des $(a+B)$ l'est. Le cours établit que toute union dénombrable d'ensembles dénombrables est dénombrable. D'où $A + B$ dénombrable. $\blacksquare$

Les deux réflexes utilisés. (i) Une bijection transporte le cardinal : pour compter $a+B$, on exhibe la bijection $b \mapsto a+b$. (ii) Pour un objet défini par une somme, on décompose en union indexée par l'un des deux ensembles, puis on applique la stabilité par union dénombrable. Ces deux gestes, avec le principe des tiroirs et la diagonale de Cantor, forment l'outillage complet de ce chapitre.