Théorème de Cantor-Bernstein

Soient $f : A \to B$ et $g : B \to A$ injectives. Pour $X \subset A$, posons $$\varphi(X) = A \setminus g\big(B \setminus f(X)\big).$$ L'application $\varphi : {\mathcal P}(A) \to \mathcal P(A)$ respecte l'inclusion : si $X \subset X'$, alors $f(X) \subset f(X')$, donc $B \setminus f(X) \supset B \setminus f(X')$, donc leurs images par $g$ sont dans le même sens, et les complémentaires dans $A$ dans le sens inverse, soit $\varphi(X) \subset \varphi(X')$.

Un point fixe. Soit $\mathcal S = \{X \in \mathcal P(A) : X \subset \varphi(X)\}$ et $X_0 = \bigcup \mathcal S$. Pour $X \in \mathcal S$, on a $X \subset X_0$, donc $X \subset \varphi(X) \subset \varphi(X_0)$ ; ainsi $X_0 \subset \varphi(X_0)$.

Comme $\varphi$ respecte l'inclusion, $\varphi(X_0) \subset \varphi(\varphi(X_0))$, donc $\varphi(X_0) \in \mathcal S$ et $\varphi(X_0) \subset X_0$. D'où $\varphi(X_0) = X_0$, c'est-à-dire $$A \setminus X_0 = g\big(B \setminus f(X_0)\big).$$

La bijection. Posons $h(a) = f(a)$ si $a \in X_0$, et $h(a) =$ l'unique antécédent de $a$ par $g$ si $a \in A \setminus X_0$ ; cet antécédent existe par l'égalité précédente, est unique par injectivité de $g$, et appartient à $B \setminus f(X_0)$.

L'application $h : A \to B$ est injective : elle l'est sur $X_0$ comme $f$, sur $A \setminus X_0$ comme réciproque de $g$, et les deux images $f(X_0)$ et $B \setminus f(X_0)$ sont disjointes.

Elle est surjective : un $b \in f(X_0)$ est atteint sur $X_0$ ; un $b \notin f(X_0)$ vérifie $g(b) \in A \setminus X_0$, et $h(g(b)) = b$.