Rapport dénombrable/indénombrable.

Voici une démonstration plus indirecte du fait que $R$ est indénombrable, mais qui a l'avantage de préciser le rapport entre les 2, à savoir $\R \sim \pa(\N)$, l'ensemble des parties de $\N$.

En voici une (jolie) démonstration par l'absurde.

Supposons qu'il existe une bijection $h: E \to\pa(E)$ Pour tout $x$ dans $E$, $h(x)$ est un sous-ensemble de $E$. Notons $F = \{ x \in E \vert x \text{ n'est pas dans h(x)} \}$. Par construction, $F$ est une partie de $E$, donc $F$ est dans $\pa(E)$. Comme $h$ est une bijection, $F$ a un antécédent dans $E$, ie: il existe $y \in E$ tel que $h(y) = F = \{x \in E \vert x \text{ n'est pas dans }h(x)\}$.

Alors:

• si $y \in F$, par définition de $F$, $y \not\in h(y)=F$. Absurde.
• si $y \not\in F$, par définition de $F$, $y \in h(y)=F$. Absurde aussi.

C'est donc l'hypothèse d'existence de la bijection $h$ qui est fausse. Cqfd.

On constitue donc l'application $p: \pa(\N) \to \R$ de la façon suivante. Soit $E$ dans $\pa(\N)$. $E$ est donc un sous-ensemble (fini ou infini) de $\N$.

On forme un nombre $d$ écrit en base $2$ de la façon suivante:

$$d = 0, d_0 d_1 d_2 d_3 d_4 d_5 \ldots$$

où

$$d_n = \begin{cases} 1 & \text{si } n \in E \ 0 & \text{sinon} \end{cases}$$

On a alors $d \in \lbrack 0,1 \rbrack$ ($d=0$ si $E=\emptyset$, $d=1$ si $E=\N$).^4.2

D'autre part, si on fabrique l'application $q$ comme $p$, mais en considérant que cette fois d est écrit en base 3 (ou 10, ou n>2), alors l'application q est une injection de $\pa({\N})$ dans $R$.^4.3

$\pa(\N)$ se surjecte et s'injecte à la fois dans $R$, donc $\pa(\N) \equiv \R$, ie: $\card \pa(\N) = \card \R$

Par généralisation du cas fini, on écrit:

$$\card \R = \card \pa(\N) = 2^{\card \N} = 2^{\aleph_0}$$

En effet, puisque $\N$ est inclus (donc s'injecte) dans $R$, $\card \N \leq \card \R$. De plus, on vient de montrer que $\card \R = \card \pa(\N)$, et que $\pa(\N)$ n'est pas équipotent à $\N$. Donc $\card \N < \card \R$.