Chapitre 1 : Ensembles, dénombrement, dénombrabilité

1.1 Vocabulaire de la logique

$\exists x$ : il existe $x$.

$\forall x$ : pour tout $x$.

Pour deux propositions $P$ et $Q$:

• $P \land Q$ : $P$ et $Q$.
• $P \lor Q$ : $P$ ou $Q$.
• $\neg P$ : non $P$ / la négation de $P$.
• $P \implies Q$ : $P$ implique $Q$ ; Si $P$, alors $Q$ ; $P$ est une condition suffisante de $Q$ ; $Q$ est une condition nécessaire de $P$.
• $P \iff Q$ : $P$ et $Q$ sont équivalentes ; $P$ si et seulement si (ssi) $Q$ ; $P$ est une condition nécessaire et suffisante (CNS) de $Q$.
• $Q \implies P$ : la réciproque de $P \implies Q$.
• $\neg P \implies \neg Q$ : l'inverse de $P \implies Q$.
• $\neg Q \implies \neg P$ : la contraposée de $P \implies Q$.

Notations (de Bourbaki) :
$\mathbb N$: L'ensemble des entiers naturels. $\mathbb N = \{ 0, 1, 2, \ldots \}, \mathbb N^* = \mathbb N \backslash \{ 0 \}$
$\mathbb Z$: L'ensemble des entiers relatifs. $\mathbb Z = \{ \ldots, -2, -1, 0, 1, 2, \ldots \}$
$\mathbb Q$: L'ensemble des nombres rationnels. $\mathbb Q = \{ \frac{a}{b} : a \in \mathbb Z, b \in \mathbb Z^* \}$
$\mathbb R$: L'ensemble des nombres réels.
$\mathbb C$: L'ensemble des nombres complexes.

1.2 Opérations sur les ensembles

Un ensemble = Une collection d'objets (définition ''naïve'' / non axiomatique)

eux ensembles sont égaux ssi ils contiennent les mêmes éléments.

L'ensemble vide est noté $\varnothing$.

Soit $E$ un ensemble :

• $x \in E$ : $x$ appartient à $E$ ; $x$ est un élément de $E$.
• $A \subset E / A \subseteq E$ : $\forall w \in A$, on a $w \in E$ ; $A$ est inclus dans $E$ ; $A$ est un sous-ensemble de $E$ ; $A$ est une partie de $E$.

Soit $A, B$ deux parties de $E$ :

• $A \cup B := \{ w \in E: w \in A \text{ ou } w \in B \}$. union / réunion de $A$ et $B$.
• $A \cap B := \{ w \in E: w \in A \text{ et } w \in B \}$. intersection de $A$ et $B$.
• $A^C := \{ w \in E: w \notin A \}$. complémentaire de $A$ (par rapport à $E$).
• $A \backslash B := A \cap (B^C)$. différence de $A$ et $B$.
• $A \triangle B := (A \backslash B) \cup (B \backslash A)$. différence symétrique de $A$ et $B$.

Soit $I$ un ensemble d'indices, pour tout $i \in I$, soit $A_i$ un sous-ensemble de $E$ :

• $(A_i)_{i \in I}$: famille de sous-ensembles de $E$.
• $\bigcup\limits_{i \in I} A_i := \{ w \in E: \exists i \in I \text{ tel que } w \in A_i \}$. réunion de la famille $(A_i)_{i \in I}$.
• $\bigcap\limits_{i \in I} A_i := \{ w \in E: \forall i \in I, w \in A_i \}$. intersection de la famille $(A_i)_{i \in I}$.

La famille $(A_i)_{i \in I}$ est disjointe si

$$ \forall i, j \in I \text{ tels que } i \neq j, \text{ on a } A_i \cap A_j = \varnothing. $$

Distributivité entre $\cup, \cap, (\quad)^C$ :

• $\left( \bigcup\limits_{i \in I} A_i \right) \cap B = \bigcup\limits_{i \in I} (A_i \cap B)$
• $\left( \bigcap\limits_{i \in I} A_i \right) \cup B = \bigcap\limits_{i \in I} (A_i \cup B)$
• $\left( \bigcup\limits_{i \in I} A_i \right)^C = \bigcap\limits_{i \in I} (A_i^C)$
• $\left( \bigcap\limits_{i \in I} A_i \right)^C = \bigcup\limits_{i \in I} (A_i^C)$

Produit cartésien :

$$ A \times B := \{ (a, b): a \in A, b \in B \} $$

Pour $n \geq 2$ entier, on écrit $A^n = \underbrace{A \times A \times A \times \cdots \times A}_{n \text{ fois}}$.

$\mathcal{P}(E) := \{ A: A \subseteq E \}$ : l'ensemble des sous-ensembles de $E$.

Remarque : On a toujours $\varnothing \in \mathcal{P}(E)$ et $E \in \mathcal{P}(E)$. $\varnothing$ et $E$ sont appelés sous-ensembles triviaux de $E$.

$\forall A \in \mathcal{P}(E)$, on définit la fonction indicatrice de $A$ par

$$ \mathbb I_A: E \to \mathbb R, \quad\mathbb I_A(x) = \begin{cases} 1, & \text{si } x \in A \\ 0, & \text{si } x \notin A \end{cases} $$

Definition : Une fonction $f: E \to F$ est

• injective, si tout élément de $F$ est l'image d'au plus un élément de $E$. c-à-d $\forall y \in F$, il existe au plus un élément $x \in E$ tel que $y = f(x)$.
• surjective, si tout élément de $F$ est l'image d'au moins un élément de $E$. c-à-d $\forall y \in F, \exists x \in E$ tel que $y = f(x)$.
• bijective, si $f$ est à la fois injective et surjective.

Si $f: E \to F$ est bijective, alors on peut définir son inverse $f^{-1}: F \to E$.

Soit $B \subseteq F$, l'image réciproque de $B$ par $f$ est $f^{-1}(B)$.

Soit $A \subseteq E$, l'image directe de $A$ par $f$ est $f(A)$.

1.2.1 Ensembles finis

Notation : Pour $n \in \mathbb N$, on note $\{1, 2, \ldots, n\} = [\![ 1, n ]\!]$ et par convention si $n = 0, [\![ 1, 0 ]\!] = \varnothing$.

Definition : Un ensemble $E$ est fini s'il existe $n \in \mathbb N$ et une bijection $f: [\![ 1, n ]\!] \to E$.

Lemme : (fondamental) Soient $m, n \in \mathbb N$, s'il existe une injection $f: [\![ 1, n ]\!] \to [\![ 1, m ]\!]$, alors $n \leq m$.

Preuve : On raisonne par récurrence sur $m$.

• (Initialisation) Si $m = 0$, alors $[\![ 1, m ]\!]$ est vide. L'application $f: [\![ 1, n ]\!] \to \varnothing$ peut exister seulement si $[\![ 1, n ]\!] \neq \varnothing$. Donc $n \leq m$ est vrai.
• (Hérédité) Supposons que le résultat est vrai pour $m$. Soit $f: [\![ 1, n ]\!] \to [\![ 1, m + 1 ]\!]$ une injection. Si $n = 0$, alors $n \leq m + 1$ et c'est fini. Supposons $n \geq 1$. Soit $p: [\![ 1, m + 1 ]\!] \to [\![ 1, m + 1 ]\!]$ la permutation qui échange $f(n)$ et $m + 1$. Alors $g = p \circ f$ est une application $g: [\![ 1, n ]\!] \to [\![ 1, m + 1 ]\!]$ telle que $g(n) = m + 1$. De plus, $g$ est injective. La restriction de $g$ sur $[\![ 1, n - 1 ]\!]$ est une injection $[\![ 1, n - 1 ]\!] \to [\![ 1, m ]\!]$. Par l'hypothèse de récurrence, on a $n - 1 \leq m$, donc $n \leq m + 1$.

Donc le lemme est démontré par récurrence.

$\square$

Definition : Pour un ensemble fini $E$. S'il existe une bijection $f: [\![ 1, n ]\!] \to E$ pour l'entier $n$, alors $n$ est appelé le cardinal de $E$, et on écrit $\text{card}(E) = |E| = \#E = n$.

Lemme : Soit $E$ un ensemble fini. L'entier $n$ tel qu'il existe une bijection $[\![ 1, n ]\!] \to E$ est unique.

Preuve : Supposons qu'il existe deux bijections

$$ f: [\![ 1, n ]\!] \to E \quad \text{et} \quad g: [\![ 1, m ]\!] \to E $$

Alors $g^{-1} \circ f$ est une bijection de $[\![ 1, n ]\!]$ dans $[\![ 1, m ]\!]$. En particulier, c'est une injection $[\![ 1, n ]\!] \to [\![ 1, m ]\!]$. Selon le lemme fondamental, on a $n \leq m$. De la même façon, $m \leq n$. Donc $n = m$, d'où l'unicité de la valeur de $n$.

$\square$

Grâce au lemme précédent, la définition du cardinal pour les ensembles finis est bien posée.

Remarque : L'ensemble vide $\varnothing$ est le seul ensemble de cardinal nul.

Si $\text{card}(E) = n$, alors on peut représenter les éléments de $E$ comme une série ordonnée finie $E = \{ a_1, a_2, \ldots, a_n \}$ avec $a_i \neq a_j, \forall i \neq j$.

Definition : Un ensemble infini est un ensemble qui n'est pas fini.

Exemple : $\mathbb N, \mathbb Z, \mathbb Q, \mathbb R, \mathbb C$ sont tous des ensembles infinis.

Théorème : (comparaison) Soient $E, F$ deux ensembles finis.

1. $|E| \leq |F|$ ssi $\exists$ une injection $f: E \to F$
2. $|E| = |F|$ ssi $\exists$ une bijection $f: E \to F$
3. Si $E \neq \varnothing$, $|E| \leq |F|$ ssi $\exists$ une surjection $F \to E$.

Preuve : Soient $n = |E|, m = |F|$ et $u: [\![ 1, n ]\!] \to E, v: [\![ 1, m ]\!] \to F$ deux bijections.

1. Supposons qu'il existe une injection $f: E \to F$. Alors l'application $v^{-1} \circ f \circ u: [\![ 1, n ]\!] \to [\![ 1, m ]\!]$ est injective. Selon le lemme fondamental, on a $n \leq m$, càd $|E| \leq |F|$. Réciproquement, si $n \leq m$, alors l'application $h: [\![ 1, n ]\!] \to [\![ 1, m ]\!], k \mapsto k$ est injective. Donc $v \circ h \circ u^{-1}: E \to F$ est une injection. Donc il existe une injection $E \to F$.
2. Supposons qu'il existe une bijection $f: E \to F$. Puisque $f$ est injective, selon le point 1, on a $|E| \leq |F|$. De même, $f^{-1}: F \to E$ est aussi injective. Donc $|F| \leq |E|$. Donc $|E| = |F|$.
3. Supposons $E \neq \varnothing$, càd $n \geq 1$. Supposons qu'il existe une surjection $g: F \to E$. Alors $q = v \circ g \circ u^{-1}$ est une surjection $[\![ 1, m ]\!] \to [\![ 1, n ]\!]$. Pour chaque $i \in [\![ 1, n ]\!]$, on pose $r(i) =$ le plus petit élément de $q^{-1}(\{i\})$. $r$ est une injection $[\![ 1, n ]\!] \to [\![ 1, m ]\!]$. Donc $n \leq m$. Réciproquement, si $n \leq m$, alors on peut définir la surjection $[\![ 1, m ]\!] \to [\![ 1, n ]\!]$.

$$ s(k) = \begin{cases} k, & \text{si } k \leq n \\ 1, & \text{si } k > n \end{cases} $$

Alors $u \circ s \circ v^{-1}$ est une surjection $F \to E$. $\square$

Corollaire : Soient $E, F$ deux ensembles finis, s'il existe une injection $E \to F$ et une injection $F \to E$, alors $|E| = |F|$.

Corollaire : Soit $E$ un ensemble fini.

• Si $A \subseteq E$, alors $A$ est fini et $|A| \leq |E|$.
• Si $f: E \to F$ est une application, alors $f(E)$ est fini et $|f(E)| \leq |E|$. De plus, $|f(E)|=|E|$ ssi $f$ est injective.
• Si $f: E \to E$, alors $f$ est injective $\iff f$ est surjective $\iff f$ est bijective.

Preuve : Soit $n=|E|$, alors on peut écrire $E=\{a_1, a_2, \dots, a_n\}$.

• Si $A \subseteq E$, alors $A$ s'écrit sous la forme $A=\{a_{i_1}, a_{i_2}, \dots, a_{i_p}\}$ avec $1 \le i_1 < i_2 < \dots < i_p \le n$. Donc $A$ est fini et $|A|=p \leq n$.
• On a $f(E)= \{f(a): a \in E\}=\{f(a_1), f(a_2), \dots, f(a_n)\}$, donc $f(E)$ contient au plus $n$ éléments, d'où $|f(E)| \leq n$. On a $|f(E)|= n$ ssi il n'y a pas de valeurs répétées parmi $f(a_1), f(a_2), \dots, f(a_n)$ càd $f$ est injective.
• Si $f$ est injective, selon le point 2, $|f(E)|=|E|$. Car $f(E) \subseteq E$ et $|f(E)|=|E|$, on a $f(E)=E$, donc $f$ est surjective. Si $f$ est surjective, alors $|f(E)|=|E|$, et selon le point 2, $f$ est injective. Donc $f$ est injective ssi $f$ est surjective.

$\square$

Remarque : L'hypothèse "$E$ est fini" est indispensable dans le corollaire 2. Si $E$ est infini, on a le contre-exemple :

$$\begin{align*} f: \mathbb N &\to \mathbb N \\ n &\mapsto n+1 \end{align*} $$

qui est injective mais non surjective.

Corollaire (Principe des tiroirs) : Si on place $n$ objets dans $m$ tiroirs avec $n > m$, alors au moins un tiroir contient au moins 2 objets.

Preuve : Soit $f: E = \text{l'ensemble des objets} \to F = \text{l'ensemble des tiroirs}$ l'application qui décrit le placement des objets dans les tiroirs. On sait que $|E| > |F|$, alors $f$ n'est pas injective, càd $\exists y \in F, x_1, x_2 \in E$ tels que $x_1 \neq x_2$ mais $f(x_1)=f(x_2)=y$.

$\square$

1.3 Dénombrement

Rappel (principe de bijection) : Pour deux ensembles finis $E, F$, s'il existe une bijection $E \to F$, alors $|E| = |F|$.

Principe d'addition : Soient $A, B$ deux ensembles finis, si $A$ et $B$ sont disjoints (càd $A \cap B = \varnothing$), alors $|A \cup B| = |A| + |B|$.

Démonstration : Soient $n = |A|, m = |B|$, construisons une bijection $f: [\![ 1, m + n ]\!] \to A \cup B$.

Principe de multiplication : Soient $A, B$ deux ensembles finis, alors $|A \times B| = |A| \cdot |B|$.

Démonstration : Construisons une bijection $f: [\![ 1, mn ]\!] \to A \times B$, où $n = |A|, m = |B|$.

Généralisation : Si $E_1, E_2, \ldots, E_k$ sont des ensembles finis, alors $|E_1 \times E_2 \times \cdots \times E_k| = \prod\limits_{j = 1}^k |E_j|$. Pour $n \in \mathbb N^*$, $|E^n| = |E|^n$. En particulier, $| \{ 0, 1 \} |^n = 2^n$.

Corollaire : Si $E, F$ sont deux ensembles finis, alors $| \{ f: E \to F \} (=: \mathcal F) | = |F|^{|E|}$

Preuve : Construisons une bijection $\varphi: [\![ 1, |F|^{|E|} ]\!] \to \mathcal F$.

$\square$

Corollaire : Si $E$ est un ensemble fini, alors $\mathcal P(E)$ est aussi fini, et $|\mathcal P(E)| = 2^{|E|}$.

Preuve : La fonction indicatrice définit une bijection

$$\begin{align*} \mathbb I: \mathcal P(E) &\to \{ f: E \to \{ 0, 1 \} \} \\ A \subseteq E &\mapsto \mathbb I_A \end{align*} $$

Donc $|\mathcal P(E)| = | \{ f: E \to \{ 0, 1 \} \} | = 2^{|E|}$.

$\square$

$p$-arrangement :

Definition : Soient $p \in \mathbb N^*$ et $E$ un ensemble fini. On appelle $p$-arrangement d'éléments de $E$ tout $p$-liste (liste de longueur $p$) d'éléments de $E$ deux-à-deux distincts. On écrit $A^p_n = \text{card}(\{ (x_1, x_2, \ldots, x_p) \in E^p: \forall i \neq j, x_i \neq x_j \})$.

Théorème : Pour $n \in \mathbb N, p \in \mathbb N^*$, on a

$$ A_n^p = \begin{cases} \frac{n!}{(n - p)!}, & \text{si } p \leqslant n \\ 0, & \text{si } p > n \end{cases} $$

Preuve : Si $p > n$, alors il n'existe pas de $p$-liste à éléments deux-à-deux distincts de $E$.

Si $p \leqslant n$, pour construire un $p$-arrangement d'éléments de $E$, $(x_1, x_2, \ldots, x_p)$ :

• On choisit $x_1 \in E \to n$ choix.
• On choisit $x_2 \in E \setminus \{x_1\} \to n - 1$ choix.
• $\cdots$
• On choisit $x_p \in E \setminus \{x_1, x_2, \ldots, x_{p-1}\} \to n - (p - 1)$ choix.

Par le principe de multiplication, $A_n^p = n(n-1)(n-2)\cdots(n-p+1) = \frac{n!}{(n-p)!}$.

$\square$

Corollaire : Soient $E, F$ deux ensembles finis, alors $\text{card}(\{ f: E \to F \mid f \text{ injective} \}) = A_n^p$ où $p = |E|$ et $n = |F|$.

Preuve : Soit $u: [\![ 1, p ]\!] \to E$ une bijection, alors on a la bijection

$$\begin{align*} \varphi: \{ p\text{-arrangements d'éléments de } F \} &\to \{ f: E \to F \text{ injective} \} \\ (x_1, x_2, \cdots, x_p) &\mapsto f(z) = x_{u^{-1}(z)} \end{align*} $$

$\square$

Definition : Une permutation d'un ensemble fini $E$ est une application bijective $E \to E$.

Conséquence : On a vu que quand $E$ est fini, une application $f: E \to E$ est injective ssi elle est bijective. Donc $| \{ \text{permutations de } E \} | = | \{ f: E \to E \mid f \text{ injective} \} | = A_n^n = n!$.

Principe de quotient :

Lemme : Soit $f: E \to F$ une surjection entre deux ensembles finis $E, F$. S'il existe $r \in \mathbb N^*$ tel que $\forall y \in F$, on a $|f^{-1}(\{y\})| = r$, alors $|F| = \frac{|E|}{r}$.

$p$-combinaison : Une $p$-combinaison d'éléments de $E$ est un sous-ensemble (les éléments sont non ordonnés et sans répétition) de $E$ de cardinal $p$.

Théorème : Le nombre de $p$-combinaisons d'un ensemble $E$ de cardinal $n$ est donné par $\frac{A_n^p}{p!}$.

Preuve : Appliquer le principe de quotient.

$\square$

Definition : On écrit $\binom{n}{p} = \frac{A_n^p}{p!} = \frac{n!}{p!(n-p)!}$. $\binom{n}{p}$ est appelé le coefficient binomial.

Convention :

• $0! = 1$.
• $\binom{n}{0} = 1$.
• $\forall p > n, \binom{n}{p} = 0$.

Principe d'inclusion-exclusion : Soient $A_1, A_2, \cdots, A_n$ $n$ ensembles finis (non nécessairement disjoints). On a

$$ |A_1 \cup A_2 \cup \cdots \cup A_n| = \sum\limits_{k = 1}^n (-1)^{k + 1} \sum\limits_{\substack{(r_1, r_2, \ldots, r_k) \in [\![ 1, n ]\!]^k \\ 1 \leqslant r_1 < r_2 < \cdots < r_k \leqslant n}} |A_{r_1} \cap A_{r_2} \cap \cdots \cap A_{r_k}| $$

Par exemple :

• $n = 2$ : $|A \cup B| = |A| + |B| - |A \cap B|$.
• $n = 3$ : $|A \cup B \cup C| = |A| + |B| + |C| - (|A \cap B| + |A \cap C| + |B \cap C|) + |A \cap B \cap C|$.

Théorème (formule du binôme (de Newton)) : Pour $n \in \mathbb N, a, b \in \mathbb C$ (ou n'importe quel anneau commutatif), on a

$$ (a + b)^n = \sum\limits_{k = 0}^n \binom{n}{k} a^k b^{n-k} $$

1.4 Dénombrabilité

Definition : Un ensemble $A$ est dénombrable s'il existe une bijection $\mathbb N \to A$. Il est dit au plus dénombrable s'il est dénombrable ou fini.

Interprétation : Une bijection $\mathbb N \to A$ donne une liste infinie de tous les éléments de $A$ sans répétition, càd $A = \{ a_0, a_1, a_2, \ldots \}$ et $\forall i \neq j, a_i \neq a_j$.

Exemple : $\mathbb Z$ est un ensemble dénombrable. Par exemple,

$$\begin{align*} \varphi: \mathbb N &\to \mathbb Z \\ \forall k \in \mathbb N, 2k &\mapsto k \\ \forall k \in \mathbb N^*, 2k - 1 &\mapsto -k \end{align*} $$

est une bijection.

Théorème (comparaison) : Soit $A$ un ensemble. Les propriétés suivantes sont équivalentes :

1. $A$ est au plus dénombrable.
2. Il existe une injection $A \to \mathbb N$.
3. $A$ est en bijection avec une partie de $\mathbb N$.
4. Il existe une surjection $\mathbb N \to A$.

(2), (3), (4) sont des caractérisations de la propriété "au plus dénombrable".

Preuve :

• $(1) \Rightarrow (2)$ : Si $A$ est fini, alors il existe $p \in \mathbb N$ et une bijection $\varphi: [\![ 1, p ]\!] \to A$. Alors $\varphi^{-1}$ donne une injection $A \to [\![ 1, p ]\!] \subseteq \mathbb N$. Si $A$ est dénombrable, il existe une bijection $\mathbb N \to A$ par déf.
• $(2) \Rightarrow (3)$ : Si $f: A \to \mathbb N$ est une injection alors $f: A \to f(A) \subseteq \mathbb N$ est une bijection vers une partie de $\mathbb N$.
• $(3) \Rightarrow (4)$ : Soit $B \subseteq \mathbb N$ tel que $A$ est en bijection avec $B$. Si $B$ est fini, alors $A$ est fini. Si $B$ est infini, on définit $b_0 = \min B$. $\forall n \geqslant 1, b_n = \min \{ b \in B: b > b_{n - 1} \}$. Alors $n \mapsto b_n$ est une bijection $\mathbb N \to B$. Donc $A$ est dénombrable.
• $(4) \Rightarrow (1)$ : S'il existe une surjection $g: \mathbb N \to A$, alors pour tout $a \in A$, $g^{-1}(\{a\}) \neq \varnothing$. On peut alors définir une injection $h: A \to \mathbb N$ en posant $h(a) = \min g^{-1}(\{a\})$. Donc $A$ est au plus dénombrable.

$\square$

Corollaire : L'image d'un ensemble au plus dénombrable par une application (quelconque) est au plus dénombrable. $f: A \to B$, $A$ au plus dénombrable $\implies f(A)$ est au plus dénombrable.

Exemple : $\mathbb N^2$ est dénombrable. On peut arranger tous les éléments de $\mathbb N^2$ dans la liste suivante :

$$ (0, 0), (0, 1), (1, 0), (0, 2), (1, 1), (2, 0), \ldots $$

Théorème (utile pour le chapitre 2) :

1. Un produit fini d'ensembles au plus dénombrables est au plus dénombrable.
2. Si $(A_i)_{i \in I}$ est une famille d'ensembles au plus dénombrables, indicée par un ensemble $I$ au plus dénombrable, alors $\bigcup\limits_{i \in I} A_i$ est au plus dénombrable.

Preuve :

1. Soient $A, B$ deux ensembles au plus dénombrables. Par le thm de comparaison, il existe deux injections $f: A \to \mathbb N, g: B \to \mathbb N$. Alors

$$\begin{align*} \varphi: A \times B &\to \mathbb N^2 \\ (a, b) &\mapsto (f(a), g(b)) \end{align*} $$

est injective. On sait que $\mathbb N^2$ est en bijection avec $\mathbb N$, donc il existe une injection $A \times B \to \mathbb N$, donc $A \times B$ est au plus dénombrable.

2. Soit $I$ un ensemble au plus dénombrable et $\forall i \in I, A_i$ est un ensemble au plus dénombrable. Alors on peut lister les éléments de $I$ et les $A_i$ :

$$ I = \{ i_0, i_1, i_2, \ldots \} $$

$$ \forall i_k \in I, A_{i_k} = \{ a_{k, 0}, a_{k, 1}, a_{k, 2}, \ldots \} $$

Alors $\bigcup\limits_{i \in I} A_i = \{ a_{k, j} \mid k \in \mathbb N \text{ tel que } i_k \in I, j \in \mathbb N \text{ tel que } a_{k, j} \in A_{i_k} \}$. Cela nous donne une surjection $\mathbb N^2 \to \bigcup\limits_{i \in I} A_i$. Par le thm de comparaison, $\bigcup\limits_{i \in I} A_i$ est au plus dénombrable.

$\square$

Corollaire :

• $\mathbb Q$ est dénombrable.

$$\begin{align*} \mathbb Z \times \mathbb N^* &\to \mathbb Q \\ (p, q) &\mapsto \frac{p}{q} \end{align*} $$

est surjective, et $\mathbb Z \times \mathbb N^*$ est au plus dénombrable.

• $\mathbb Z[x]$ est dénombrable. $\mathbb Z[x] = \bigcup\limits_{n \in \mathbb N} \mathbb Z_n[x]$, et $\forall n \in \mathbb N, \mathbb Z_n[x]$ est en bijection avec $\mathbb N^{n + 1}$.

Question : Y a-t-il des ensembles infinis non dénombrables ? Si oui, exemples ?

Théorème : Soit $E$ un ensemble quelconque, il n'existe pas de bijection entre $E$ et $\mathcal P(E)$.

Preuve (par absurde) : Supposons qu'il existe une bijection $\Phi: E \to \mathcal P(E)$. Alors on peut définir $A = \{ x \in E \mid x \notin \Phi(x) \}$.

• On a $A \in \mathcal P(E)$.
• Mais $\forall x \in E$ on a
  • si $x \in A$, alors $x \notin \Phi(x)$, donc $A \neq \Phi(x)$.
  • si $x \notin A$, alors $x \in \Phi(x)$, donc $A \neq \Phi(x)$.

Donc on a $A \neq \Phi(x)$ pour tout $x \in E$. Càd $A$ est un élément de l'ensemble d'arrivée $\mathcal P(E)$, qui n'a pas d'antécédent.

Donc $\Phi$ n'est pas surjective. C'est absurde. Cela contredit l'hypothèse que $\Phi$ est bijective. Donc il n'existe pas de bijection $E \to \mathcal P(E)$.

$\square$

Corollaire : $\mathcal P(\mathbb N)$ n'est pas dénombrable.

Notation : $\{ 0, 1 \}^{\mathbb N} = \{ f: \mathbb N \to \{ 0, 1 \} \} = \{ (d_0, d_1, d_2, \ldots) \mid \forall i \in \mathbb N, d_i \in \{ 0, 1 \} \}$

Conséquence : On a vu que $\{ 0, 1 \}^{\mathbb N}$ est en bijection avec $\mathcal P(\mathbb N)$. Donc il n'est pas dénombrable.

Théorème : $\mathbb R$ n'est pas dénombrable.

Preuve : On définit

$$\begin{align*} \Phi: \{ 0, 1 \}^{\mathbb N} &\to \mathbb R \\ (d_n)_{n \in \mathbb N} &\mapsto \sum\limits_{n = 0}^\infty \frac{2d_n}{3^{n + 1}} \end{align*} $$

(Exercice : Montrer que $\Phi$ est injective)

Si $\mathbb R$ est dénombrable avec $f: \mathbb R \to \mathbb N$ une bijection, alors $f \circ \Phi: \{ 0, 1 \}^{\mathbb N} \to \mathbb N$ est une injection. Selon le thm de comparaison, cela implique que $\{ 0, 1 \}^{\mathbb N}$ est au plus dénombrable. C'est absurde. Donc $\mathbb R$ n'est pas dénombrable.

$\square$