Ensembles, fonctions et cardinalité

Supposons le principe de compréhension non restreinte valide. Appliqué à la propriété « $x$ n'est pas élément de lui-même », il fournit un ensemble

Par la définition 1.1, pour tout objet $a$ : $a \in R$ lorsque $a \notin a$, et $a \notin R$ lorsque $a \in a$. L'objet $R$ étant lui-même un ensemble, on peut prendre $a := R$, et l'on distingue deux cas.

Premier cas : $R \in R$. Alors, par la caractérisation ci-dessus appliquée à $a := R$, la propriété définissant $R$ est vraie de $R$, c'est-à-dire $R \notin R$ : contradiction avec l'hypothèse du cas.

Second cas : $R \notin R$. Alors la propriété définissant $R$ est vraie de $R$, donc $R$ appartient à $R$, c'est-à-dire $R \in R$ : contradiction avec l'hypothèse du cas.

Les deux cas sont exhaustifs et chacun conduit à une contradiction. L'hypothèse absurde posée au départ — la validité du principe de compréhension non restreinte — est donc réfutée.

$\blacksquare$

Première égalité, inclusion directe. Soit $x \in \complement_{E} \big( \bigcup_{i \in I} A_i \big)$. Par la définition 1.8, $x \in E$ et $x$ n'appartient à aucun $A_i$. Soit $i \in I$ quelconque : de $x \in E$ et $x \notin A_i$ on tire $x \in \complement_{E} A_i$. Ceci valant pour tout $i \in I$, on a $x \in \bigcap_{i \in I} \complement_{E} A_i$.

Première égalité, inclusion réciproque. Soit $x \in \bigcap_{i \in I} \complement_{E} A_i$. Comme $I$ est non vide, choisissons $i_0 \in I$ ; de $x \in \complement_{E} A_{i_0}$ on tire $x \in E$. Par ailleurs, pour tout $i \in I$, $x \in \complement_{E} A_i$, donc $x \notin A_i$ ; ainsi $x$ n'appartient à aucun $A_i$, c'est-à-dire $x \notin \bigcup_{i \in I} A_i$. De $x \in E$ et $x \notin \bigcup_{i \in I} A_i$ on conclut $x \in \complement_{E} \big( \bigcup_{i \in I} A_i \big)$.

Seconde égalité, inclusion directe. Soit $x \in \complement_{E} \big( \bigcap_{i \in I} A_i \big)$, donc $x \in E$ et $x \notin \bigcap_{i \in I} A_i$. Il existe donc $j \in I$ tel que $x \notin A_j$ ; alors $x \in \complement_{E} A_j$, donc $x \in \bigcup_{i \in I} \complement_{E} A_i$.

Seconde égalité, inclusion réciproque. Soit $x \in \bigcup_{i \in I} \complement_{E} A_i$ : il existe $j \in I$ tel que $x \in \complement_{E} A_j$, d'où $x \in E$ et $x \notin A_j$. De $x \notin A_j$ on tire $x \notin \bigcap_{i \in I} A_i$, et donc $x \in \complement_{E} \big( \bigcap_{i \in I} A_i \big)$.

$\blacksquare$

Sens réciproque. Si $a = c$ et $b = d$, les deux couples sont le même objet par substitution, donc $(a,b) = (c,d)$.

Sens direct. Supposons $\{ \{a\}, \{a,b\} \} = \{ \{c\}, \{c,d\} \}$.

Cas 1 : $a = b$. Alors $\{a,b\} = \{a\}$, donc $(a,b) = \{ \{a\} \}$ : ce couple a un unique élément. Par extensionnalité (définition 1.6), $\{ \{c\}, \{c,d\} \}$ a donc lui aussi $\{a\}$ pour unique élément, d'où $\{c\} = \{a\}$ et $\{c,d\} = \{a\}$. De $\{c\} = \{a\}$ on tire $c = a$ ; de $\{c,d\} = \{a\}$ on tire $d = a$, et comme $b = a$ par l'hypothèse du cas, $d = b$. Les deux égalités voulues sont établies.

Cas 2 : $a \neq b$. Comme $\{a\}$ est élément du membre de gauche, il est élément du membre de droite : ou bien $\{a\} = \{c\}$, ou bien $\{a\} = \{c,d\}$. De même, $\{a,b\}$ est égal à $\{c\}$ ou à $\{c,d\}$.

Écartons d'abord $\{a,b\} = \{c\}$ : cette égalité donnerait $a = c$ et $b = c$, donc $a = b$, ce qui contredit l'hypothèse du cas. Donc $\{a,b\} = \{c,d\}$.

Écartons ensuite $\{a\} = \{c,d\}$ : cette égalité donnerait $c = a$ et $d = a$, donc $\{c,d\} = \{a\}$ ; joint à $\{a,b\} = \{c,d\}$, cela donnerait $\{a,b\} = \{a\}$, donc $b = a$, ce qui contredit encore l'hypothèse du cas. Donc $\{a\} = \{c\}$, c'est-à-dire $a = c$.

Il reste à établir $b = d$. De $\{a,b\} = \{c,d\}$ et $a = c$ on tire $\{a,b\} = \{a,d\}$. Comme $b \in \{a,b\}$, on a $b \in \{a,d\}$, donc $b = a$ ou $b = d$ ; le premier membre de l'alternative est exclu par l'hypothèse du cas, donc $b = d$.

$\blacksquare$

Point 1. Soit $x \in E$. Par réflexivité de $R$ (définition 1.17), $x \mathbin{R} x$, donc $x \in [x]_{R}$ par définition de la classe. Toute classe contient donc au moins l'élément dont elle est la classe, et tout $x \in E$ appartient à la classe $[x]_{R}$, laquelle est élément de $E/R$.

Point 2, sens direct. Supposons $x \mathbin{R} y$. Soit $z \in [x]_{R}$, c'est-à-dire $x \mathbin{R} z$. Par symétrie, $y \mathbin{R} x$ ; par transitivité appliquée à $y \mathbin{R} x$ et $x \mathbin{R} z$, on obtient $y \mathbin{R} z$, donc $z \in [y]_{R}$ : ainsi $[x]_{R} \subseteq [y]_{R}$. L'inclusion inverse s'obtient de même en partant de $z \in [y]_{R}$, c'est-à-dire $y \mathbin{R} z$, et en appliquant la transitivité à $x \mathbin{R} y$ et $y \mathbin{R} z$. Par double inclusion, $[x]_{R} = [y]_{R}$.

Point 2, sens réciproque. Supposons $[x]_{R} = [y]_{R}$. Par le point 1, $y \in [y]_{R}$, donc $y \in [x]_{R}$, c'est-à-dire $x \mathbin{R} y$.

Point 3. Soient $x, y \in E$. Si $[x]_{R} \cap [y]_{R} = \varnothing$, la conclusion est acquise. Sinon, il existe $z \in [x]_{R} \cap [y]_{R}$, donc $x \mathbin{R} z$ et $y \mathbin{R} z$. Par symétrie, $z \mathbin{R} y$ ; par transitivité appliquée à $x \mathbin{R} z$ et $z \mathbin{R} y$, on obtient $x \mathbin{R} y$, d'où $[x]_{R} = [y]_{R}$ par le point 2.

$\blacksquare$

Point 1, sens direct. Supposons $f$ injective et $E \neq \varnothing$ ; fixons $e_0 \in E$. Pour $y \in F$, deux cas se présentent. Si $y \in \mathrm{im}(f)$, il existe $x \in E$ tel que $f(x) = y$, et cet $x$ est unique par injectivité de $f$ ; on pose $g(y) := x$. Sinon, on pose $g(y) := e_0$. La fonction $g : F \to E$ ainsi définie est totale et, pour tout $x \in E$, $f(x) \in \mathrm{im}(f)$ et l'unique antécédent de $f(x)$ est $x$, donc $g(f(x)) = x$ : ainsi $g \circ f = \mathrm{id}_{E}$.

Point 1, sens réciproque. Supposons qu'il existe $g$ telle que $g \circ f = \mathrm{id}_{E}$, et soient $x, y \in E$ avec $f(x) = f(y)$. En appliquant $g$ : $x = g(f(x)) = g(f(y)) = y$. Donc $f$ est injective.

Point 2, sens direct. Supposons $f$ bijective. Pour $y \in F$, la surjectivité fournit un $x \in E$ tel que $f(x) = y$, et l'injectivité assure son unicité ; on pose $g(y) := x$. La fonction $g : F \to E$ est totale. Pour $y \in F$, $f(g(y)) = y$ par construction, donc $f \circ g = \mathrm{id}_{F}$ ; pour $x \in E$, $g(f(x))$ est l'unique antécédent de $f(x)$, à savoir $x$, donc $g \circ f = \mathrm{id}_{E}$.

Point 2, sens réciproque. Supposons $g \circ f = \mathrm{id}_{E}$ et $f \circ g = \mathrm{id}_{F}$. La première égalité donne l'injectivité de $f$ par le point 1 (sens réciproque, dont la preuve n'utilise pas $E \neq \varnothing$). La seconde donne la surjectivité : pour $y \in F$, $y = f(g(y))$ est dans $\mathrm{im}(f)$.

Point 2, unicité. Soient $g$ et $g'$ vérifiant toutes deux les deux égalités. Pour $y \in F$ : $g(y) = g(f(g'(y)))$, car $f \circ g' = \mathrm{id}_{F}$, et $g(f(g'(y))) = g'(y)$, car $g \circ f = \mathrm{id}_{E}$. Donc $g = g'$. Enfin $f^{-1}$ est bijective, car $f$ elle-même joue pour $f^{-1}$ le rôle que $f^{-1}$ joue pour $f$ dans les deux égalités, ce qui permet d'appliquer le sens réciproque du point 2 à $f^{-1}$.

Point 3. Supposons $f \circ s = \mathrm{id}_{F}$ et soit $y \in F$. Alors $y = f(s(y))$, donc $y \in \mathrm{im}(f)$. Ceci valant pour tout $y \in F$, $f$ est surjective.

$\blacksquare$

Réflexivité. La fonction $\mathrm{id}_{E}$ est injective (si $x = y$ alors $x = y$) et surjective (tout $x \in E$ est l'image de $x$), donc bijective, donc $E \approx E$.

Symétrie. Soit $f : E \to F$ une bijection. Par la proposition 1.22, point 2, la fonction $f^{-1} : F \to E$ existe et est bijective, donc $F \approx E$.

Transitivité. Soient $f : E \to F$ et $g : F \to G$ bijectives. La composée $g \circ f$ est injective : si $g(f(x)) = g(f(y))$, l'injectivité de $g$ donne $f(x) = f(y)$, puis celle de $f$ donne $x = y$. Elle est surjective : pour $z \in G$, la surjectivité de $g$ fournit $y \in F$ tel que $g(y) = z$, puis celle de $f$ fournit $x \in E$ tel que $f(x) = y$, d'où $g(f(x)) = z$. Donc $g \circ f$ est bijective et $E \approx G$.

$\blacksquare$

(i) $\mathrm{id}_{E}$ est injective, comme vu dans la preuve de la proposition 1.27.

(ii) Soient $f : E \to F$ et $g : F \to G$ injectives. La composée $g \circ f$ est injective, par l'argument déjà donné dans la preuve de la transitivité à la proposition 1.27.

(iii) Si $E \subseteq F$, la fonction $j : E \to F$, $x \mapsto x$, est totale et injective.

(iv) Si $f : E \to F$ est bijective, elle est en particulier injective, donc $E \preccurlyeq F$ ; et $f^{-1} : F \to E$ est bijective par la proposition 1.22, point 2, donc injective, d'où $F \preccurlyeq E$.

$\blacksquare$

Soient $f : A \to B$ et $g : B \to A$ injectives. Définissons par récurrence sur $n \in \mathbb{N}$ (prérequis 2) la suite de parties de $A$ :

Définissons ensuite $h : A \to B$ en posant, pour $x \in A$ :

La fonction $h$ est bien définie et totale. Le seul point à vérifier concerne le second cas. Soit $x \notin C$. Comme $C_{0} \subseteq C$, on a $x \notin C_{0}$, c'est-à-dire $x \notin A \setminus g[B]$ ; or $x \in A$, donc $x \in g[B]$ : il existe $b \in B$ tel que $g(b) = x$. Cet élément $b$ est unique par injectivité de $g$ ; on le note $g^{-1}(x)$. La disjonction des deux cas est exclusive et exhaustive, donc $h$ est une fonction totale de $A$ dans $B$.

La fonction $h$ est injective. Soient $x, y \in A$ avec $h(x) = h(y)$. Trois configurations sont possibles.

Si $x \in C$ et $y \in C$, alors $f(x) = f(y)$, d'où $x = y$ par injectivité de $f$.

Si $x \notin C$ et $y \notin C$, alors $g^{-1}(x) = g^{-1}(y)$ ; en appliquant $g$ aux deux membres et en utilisant $g(g^{-1}(x)) = x$ et $g(g^{-1}(y)) = y$, on obtient $x = y$.

Si l'un est dans $C$ et l'autre non, on peut supposer $x \in C$ et $y \notin C$ (le cas symétrique s'obtient en échangeant les noms de $x$ et $y$). Alors $f(x) = g^{-1}(y)$, donc, en appliquant $g$, $y = g(f(x))$. Comme $x \in C$, il existe $n \in \mathbb{N}$ tel que $x \in C_{n}$ ; alors $f(x) \in f[C_{n}]$, donc $y = g(f(x)) \in g[f[C_{n}]] = C_{n+1} \subseteq C$, ce qui contredit $y \notin C$. Cette configuration est donc impossible.

La fonction $h$ est surjective. Soit $b \in B$, et posons $a := g(b) \in A$. Deux cas.

Si $a \notin C$, alors $h(a) = g^{-1}(a) = g^{-1}(g(b)) = b$ par injectivité de $g$, donc $b \in \mathrm{im}(h)$.

Si $a \in C$, il existe $n \in \mathbb{N}$ tel que $a \in C_{n}$. On a $n \neq 0$ : en effet $a = g(b) \in g[B]$, alors que $C_{0} = A \setminus g[B]$ ne contient aucun élément de $g[B]$. Donc $n = m+1$ pour un $m \in \mathbb{N}$, et $a \in C_{m+1} = g[f[C_{m}]]$ : il existe $x \in C_{m}$ tel que $a = g(f(x))$. De $g(b) = a = g(f(x))$ et de l'injectivité de $g$ on tire $b = f(x)$. Comme $x \in C_{m} \subseteq C$, on a $h(x) = f(x) = b$, donc $b \in \mathrm{im}(h)$.

Dans les deux cas $b \in \mathrm{im}(h)$, donc $h$ est surjective. Étant injective et surjective, $h$ est bijective, et $A \approx B$.

$\blacksquare$

De $B \subseteq C$ et de la proposition 1.29 (iii) on tire $B \preccurlyeq C$. Par hypothèse il existe une bijection $u : C \to A$ ; elle est injective, et la fonction $j : A \to B$, $x \mapsto x$, est injective par la proposition 1.29 (iii) puisque $A \subseteq B$. Donc $j \circ u : C \to B$ est injective par la proposition 1.29 (ii), c'est-à-dire $C \preccurlyeq B$. Le théorème 1.30 appliqué à $B$ et $C$ donne $B \approx C$. Enfin $A \approx C$ et $C \approx B$ donnent $A \approx B$ par symétrie et transitivité (proposition 1.27).

$\blacksquare$

L'inclusion $[0,1] \subseteq \mathbb{R}$ donne $[0,1] \preccurlyeq \mathbb{R}$ par la proposition 1.29 (iii).

Réciproquement, posons $u : \mathbb{R} \to \mathbb{R}$, $x \mapsto \dfrac{x}{1 + \lvert x \rvert}$, puis $v : \mathbb{R} \to \mathbb{R}$, $x \mapsto \dfrac{1}{2} + \dfrac{u(x)}{2}$. Le dénominateur $1 + \lvert x \rvert$ est strictement positif, donc $u$ est bien définie et totale, et $v$ aussi.

Les valeurs de $v$ sont dans $[0,1]$. Pour tout $x$, $\lvert u(x) \rvert = \dfrac{\lvert x \rvert}{1 + \lvert x \rvert} < 1$, car $\lvert x \rvert < 1 + \lvert x \rvert$. Donc $-1 < u(x) < 1$, d'où $0 < v(x) < 1$ et en particulier $v(x) \in [0,1]$.

La fonction $v$ est injective. Il suffit de le démontrer pour $u$, puisque $v(x) = v(y)$ entraîne $u(x) = u(y)$. Or, pour tout $x$, on a $\lvert u(x) \rvert = \dfrac{\lvert x \rvert}{1+\lvert x \rvert}$, donc

quantité strictement positive, et par conséquent

Ainsi $x$ se récupère à partir de $u(x)$ par une expression ne dépendant que de $u(x)$ : si $u(x) = u(y)$, alors $x = \dfrac{u(x)}{1 - \lvert u(x) \rvert} = \dfrac{u(y)}{1 - \lvert u(y) \rvert} = y$. Donc $u$, puis $v$, sont injectives.

La fonction $v$, vue comme fonction de $\mathbb{R}$ dans $[0,1]$, est donc une injection totale, d'où $\mathbb{R} \preccurlyeq [0,1]$. Le théorème 1.30 conclut : $\mathbb{R} \approx [0,1]$.

$\blacksquare$

Supposons qu'il existe une surjection $f : E \to \mathcal{P}(E)$. Comme $f(x)$ est, pour chaque $x \in E$, une partie de $E$, on peut poser, par compréhension restreinte (notation 1.7) :

C'est une partie de $E$, donc $D \in \mathcal{P}(E)$. Par surjectivité de $f$, il existe $a \in E$ tel que $f(a) = D$. Distinguons deux cas.

Premier cas : $a \in D$. Par définition de $D$, cela signifie $a \notin f(a)$ ; or $f(a) = D$, donc $a \notin D$ : contradiction avec l'hypothèse du cas.

Second cas : $a \notin D$. Comme $a \in E$, la définition de $D$ impose que la propriété « $a \notin f(a)$ » soit fausse, c'est-à-dire $a \in f(a)$ ; or $f(a) = D$, donc $a \in D$ : contradiction avec l'hypothèse du cas.

Les deux cas sont exhaustifs et chacun conduit à une contradiction. L'hypothèse absurde — l'existence d'une surjection de $E$ sur $\mathcal{P}(E)$ — est donc réfutée.

$\blacksquare$

Première assertion. La fonction $s : E \to \mathcal{P}(E)$, $x \mapsto \{x\}$, est totale et injective : si $\{x\} = \{y\}$, alors $x \in \{y\}$, donc $x = y$. Donc $E \preccurlyeq \mathcal{P}(E)$.

Seconde assertion. Supposons qu'il existe une injection totale $j : \mathcal{P}(E) \to E$. Construisons $f : E \to \mathcal{P}(E)$ ainsi : pour $x \in E$, si $x \in \mathrm{im}(j)$, il existe un unique $A \in \mathcal{P}(E)$ tel que $j(A) = x$ (unicité par injectivité de $j$) et l'on pose $f(x) := A$ ; sinon on pose $f(x) := \varnothing$, ce qui est licite puisque $\varnothing \in \mathcal{P}(E)$. Alors $f$ est surjective : pour $A \in \mathcal{P}(E)$, l'élément $x := j(A)$ vérifie $f(x) = A$. L'existence d'une telle surjection contredit le théorème 1.35. Donc $\mathcal{P}(E) \not\preccurlyeq E$.

Conséquence. Si l'on avait $E \approx \mathcal{P}(E)$, la proposition 1.29 (iv) donnerait $\mathcal{P}(E) \preccurlyeq E$, ce qui vient d'être exclu.

$\blacksquare$

Comme $A$ est infini, il est en particulier non vide, et aucune partie finie de $A$ n'épuise $A$ : pour toute partie finie $S$, l'ensemble $A \setminus S$ est non vide, faute de quoi $A \subseteq S$ serait fini (prérequis 4). Le principe du bon ordre (prérequis 1) permet donc de définir par récurrence (prérequis 2) la suite

chaque minimum portant sur une partie non vide de $\mathbb{N}$ par la remarque précédente.

Assertion auxiliaire. Pour tout $n \in \mathbb{N}$, on a $e(0) < e(1) < \cdots < e(n)$ et

La fonction $e : \mathbb{N} \to A$ est injective. Soient $m \neq n$, par exemple $m < n$ ; la stricte croissance établie par l'assertion auxiliaire donne $e(m) < e(n)$, donc $e(m) \neq e(n)$.

La fonction $e$ est surjective. La stricte croissance entraîne $e(n) \geq n$ pour tout $n$, comme on le voit par récurrence immédiate : $e(0) \geq 0$, et $e(n+1) > e(n) \geq n$ donne $e(n+1) \geq n+1$. Soit $a \in A$. Alors $e(a) \geq a$, donc l'ensemble $\{\, n \in \mathbb{N} \mid e(n) \geq a \,\}$ est non vide ; soit $n_0$ son plus petit élément (prérequis 1). On a $a \leq e(n_0)$ et $a \in A$, donc, par l'assertion auxiliaire, $a \in \{ e(0), \dots, e(n_0) \}$ : $a$ est bien dans $\mathrm{im}(e)$.

Ainsi $e$ est une bijection de $\mathbb{N}$ sur $A$, donc $A \approx \mathbb{N}$ par la proposition 1.27 (symétrie), c'est-à-dire $A$ est dénombrable.

$\blacksquare$

Sens direct. Si $E$ est fini, il existe $n$ et une bijection $b : E \to [n]$ ; comme $[n] \subseteq \mathbb{N}$, la proposition 1.29 (iii) et (ii) donnent $E \preccurlyeq \mathbb{N}$. Si $E$ est dénombrable, $E \approx \mathbb{N}$ donne $E \preccurlyeq \mathbb{N}$ par la proposition 1.29 (iv).

Sens réciproque. Soit $j : E \to \mathbb{N}$ injective et $A := \mathrm{im}(j) \subseteq \mathbb{N}$. La fonction $j$, vue comme fonction de $E$ dans $A$, est bijective : elle est injective par hypothèse et surjective sur son image par définition de $A$. Donc $E \approx A$. Deux cas. Si $A$ est fini, il existe $n$ tel que $A \approx [n]$, donc $E \approx [n]$ par transitivité (proposition 1.27) et $E$ est fini. Si $A$ est infini, le lemme 1.41 donne $A \approx \mathbb{N}$, donc $E \approx \mathbb{N}$ par transitivité et $E$ est dénombrable. Dans les deux cas $E$ est au plus dénombrable.

$\blacksquare$

Pour $k \in \mathbb{N}$, posons $T_{k} := \dfrac{k(k+1)}{2}$. Comme $k$ et $k+1$ sont deux entiers consécutifs, l'un des deux est pair, donc $T_{k} \in \mathbb{N}$. On a $T_{0} = 0$ et, pour tout $k$,

donc la suite $(T_{k})$ est strictement croissante ; une récurrence immédiate donne alors $T_{k} \geq k$, si bien que $(T_{k})$ n'est pas majorée. Avec ces notations, en posant $s := m+n$ :

Assertion auxiliaire. Pour tout $N \in \mathbb{N}$, il existe un unique $s \in \mathbb{N}$ tel que $T_{s} \leq N < T_{s+1}$.

Surjectivité. Soit $N \in \mathbb{N}$ et soit $s$ l'unique entier fourni par l'assertion auxiliaire. Posons $n := N - T_{s}$, qui est un entier naturel puisque $T_{s} \leq N$. De $N < T_{s+1} = T_{s} + s + 1$ on tire $n < s+1$, donc $0 \leq n \leq s$. Posons $m := s - n$, entier naturel. Alors $m + n = s$ et $\langle m, n \rangle = T_{s} + n = N$.

Injectivité. Soient $(m,n)$ et $(m',n')$ tels que $\langle m,n \rangle = \langle m',n' \rangle =: N$. Posons $s := m+n$ et $s' := m'+n'$. Comme $0 \leq n \leq s$, on a $T_{s} \leq T_{s} + n = N$ et $N = T_{s} + n \leq T_{s} + s < T_{s} + s + 1 = T_{s+1}$, donc $T_{s} \leq N < T_{s+1}$ ; le même calcul donne $T_{s'} \leq N < T_{s'+1}$. L'unicité de l'assertion auxiliaire impose $s = s'$. Alors $n = N - T_{s} = N - T_{s'} = n'$, puis $m = s - n = s' - n' = m'$. Donc $(m,n) = (m',n')$ par le lemme 1.13.

$\blacksquare$

Cas de base $k = 1$. $\mathbb{N}^{1} = \mathbb{N}$ et $\mathrm{id}_{\mathbb{N}}$ est bijective.

Hérédité. Supposons $\mathbb{N}^{k} \approx \mathbb{N}$, au moyen d'une bijection $b : \mathbb{N}^{k} \to \mathbb{N}$. La fonction

est bijective. Elle est injective : si $c(\vec{a}) = c(\vec{a}')$, la proposition 1.44 donne $b(a_{1},\dots,a_{k}) = b(a'_{1},\dots,a'_{k})$ et $a_{k+1} = a'_{k+1}$, puis l'injectivité de $b$ donne $(a_{1},\dots,a_{k}) = (a'_{1},\dots,a'_{k})$, d'où l'égalité des deux $(k+1)$-uplets par le lemme 1.13. Elle est surjective : pour $N \in \mathbb{N}$, la proposition 1.44 fournit $(u,v)$ tel que $\langle u,v \rangle = N$, puis la surjectivité de $b$ fournit $(a_{1},\dots,a_{k})$ tel que $b(a_{1},\dots,a_{k}) = u$, et $c(a_{1},\dots,a_{k},v) = N$.

$\blacksquare$

Si $I = \varnothing$, la réunion est vide, donc finie, donc au plus dénombrable. Supposons $I$ non vide et posons $U := \bigcup_{i \in I} A_{i}$. Soit $x \in U$. L'ensemble $M_{x} := \{\, u(i) \mid i \in I \text{ et } x \in A_{i} \,\}$ est une partie non vide de $\mathbb{N}$ ; soit $m(x) := \min M_{x}$ (prérequis 1). Il existe un unique $i \in I$ tel que $u(i) = m(x)$, par injectivité de $u$ ; notons-le $i(x)$. On a $x \in A_{i(x)}$ par construction de $M_{x}$. On pose

Cette définition ne fait intervenir aucune sélection arbitraire : $m(x)$ est un minimum, $i(x)$ est unique, et $g_{i(x)}$ est un membre de la famille donnée.

Injectivité de $h$. Soient $x, y \in U$ avec $h(x) = h(y)$. Par injectivité de $\langle \cdot,\cdot \rangle$ (proposition 1.44), $m(x) = m(y)$ et $g_{i(x)}(x) = g_{i(y)}(y)$. De $m(x) = m(y)$ et de l'injectivité de $u$ on tire $i(x) = i(y) =: i$. Alors $g_{i}(x) = g_{i}(y)$, donc $x = y$ par injectivité de $g_{i}$.

Ainsi $U \preccurlyeq \mathbb{N}$, et le corollaire 1.42 conclut.

$\blacksquare$

Par le corollaire 1.42, il existe une injection $g : E \to \mathbb{N}$. Définissons par récurrence sur $n \in \mathbb{N}$ (prérequis 2) une fonction $j_{n} : E^{n} \to \mathbb{N}$ :

Chaque $j_{n}$ est injective. Par récurrence sur $n$. Pour $n = 0$, $E^{0} = \{\varepsilon\}$ n'a qu'un élément, donc toute fonction de source $E^{0}$ est injective. Supposons $j_{n}$ injective et soient deux éléments de $E^{n+1}$ ayant même image par $j_{n+1}$. Par injectivité de $\langle \cdot,\cdot \rangle$ (proposition 1.44), leurs préfixes de longueur $n$ ont même image par $j_{n}$ et leurs dernières lettres ont même image par $g$ ; l'hypothèse de récurrence donne l'égalité des préfixes, l'injectivité de $g$ celle des dernières lettres, et le lemme 1.13 conclut à l'égalité des deux mots.

Codage global. Tout $w \in E^{*}$ appartient à $E^{n}$ pour un unique $n$, sa longueur ; on pose $h(w) := \langle n, j_{n}(w) \rangle$. Si $h(w) = h(w')$, la proposition 1.44 donne d'abord l'égalité des longueurs, $n = n'$, puis $j_{n}(w) = j_{n}(w')$, d'où $w = w'$ par injectivité de $j_{n}$. Donc $h$ est une injection de $E^{*}$ dans $\mathbb{N}$, et le corollaire 1.42 conclut.

$\blacksquare$

Cas de $\mathbb{Z}$. La fonction $\zeta : \mathbb{Z} \to \mathbb{N}$ définie par $\zeta(n) := 2n$ si $n \geq 0$ et $\zeta(n) := -2n - 1$ si $n < 0$ est totale et injective : les valeurs prises sur les entiers positifs ou nuls sont paires, celles prises sur les entiers strictement négatifs sont impaires, donc deux entiers de signes distincts ont des images distinctes ; et sur chacun des deux domaines, $\zeta$ est injective car $n \mapsto 2n$ et $n \mapsto -2n-1$ le sont. Donc $\mathbb{Z} \preccurlyeq \mathbb{N}$.

Cas de $\mathbb{Q}$. Tout $q \in \mathbb{Q}$ s'écrit de manière unique $q = p/d$ avec $p \in \mathbb{Z}$, $d \in \mathbb{N}^{*}$ et $p$, $d$ premiers entre eux (prérequis 3). La fonction $\rho : \mathbb{Q} \to \mathbb{N}$, $q \mapsto \langle \zeta(p), d \rangle$, où $p/d$ est l'écriture irréductible de $q$, est donc bien définie et totale ; elle est injective, car $\rho(q) = \rho(q')$ donne, par injectivité de $\langle \cdot,\cdot \rangle$ (proposition 1.44), $\zeta(p) = \zeta(p')$ et $d = d'$, donc $p = p'$ par injectivité de $\zeta$, donc $q = p/d = p'/d' = q'$. Donc $\mathbb{Q} \preccurlyeq \mathbb{N}$.

Ces ensembles sont infinis. La fonction $\mathbb{N} \to \mathbb{Z}$, $n \mapsto n$, est injective, donc $\mathbb{N} \preccurlyeq \mathbb{Z}$ et de même $\mathbb{N} \preccurlyeq \mathbb{Q}$. Par le théorème 1.30 appliqué à chacun de ces deux ensembles et à $\mathbb{N}$, on obtient $\mathbb{Z} \approx \mathbb{N}$ et $\mathbb{Q} \approx \mathbb{N}$ : ces ensembles sont dénombrables au sens de la définition 1.40.

$\blacksquare$

Première assertion. Supposons $\mathcal{P}(\mathbb{N})$ au plus dénombrable. Par le corollaire 1.42, $\mathcal{P}(\mathbb{N}) \preccurlyeq \mathbb{N}$, ce qui contredit le corollaire 1.36 appliqué à $E := \mathbb{N}$. La contradiction est obtenue sur l'existence d'une injection de $\mathcal{P}(\mathbb{N})$ dans $\mathbb{N}$.

Seconde assertion. Notons $\Phi : A \mapsto \chi_{A}$. Elle est injective : si $\chi_{A} = \chi_{B}$, alors pour tout $x \in E$, $x \in A$ exactement lorsque $\chi_{A}(x) = 1$, c'est-à-dire lorsque $\chi_{B}(x) = 1$, c'est-à-dire lorsque $x \in B$ ; par extensionnalité (définition 1.6), $A = B$. Elle est surjective : soit $\theta : E \to \{0,1\}$ totale, et posons $A := \theta^{-1}[\{1\}] = \{\, x \in E \mid \theta(x) = 1 \,\}$, qui est une partie de $E$. Pour $x \in E$, si $\theta(x) = 1$ alors $x \in A$ donc $\chi_{A}(x) = 1$ ; si $\theta(x) = 0$ alors $x \notin A$ donc $\chi_{A}(x) = 0$. Dans les deux cas $\chi_{A}(x) = \theta(x)$, donc $\chi_{A} = \theta$ et $\theta \in \mathrm{im}(\Phi)$.

$\blacksquare$