We present here a short proof of Cantor-Berstein-Schroeder theorem based on a fixed-point argument, probably not known enough; this proof is less explicit that the usual one, but it is worth noticing that it does not depend on the axiom of choice.

As a lemma, we first prove a particular case of Knaster-Tarski fixed point theorem:

Theorem: (Tarski) Let $A$ be a set and $f : \mathfrak{P}(A) \to \mathfrak{P}(A)$ be a nondecreasing function (ie. such that $X \subset Y \Rightarrow f(X) \subset f(Y)$ for all $X,Y \in \mathfrak{P}(A)$). Then $f$ has a fixed point.

Proof. Let $C= \{ X \in \mathfrak{P}(A) \mid X \subset f(X) \}$ and $F= \bigcup\limits_{X \in C} X \in \mathfrak{P}(A)$.

Notice that for all $X \in C$, $X \subset f(X) \subset f(F)$, hence $F \subset f(F) \ (1)$.

Moreover, $(1)$ implies $f(F) \subset f(f(F))$ ie. $f(F) \in C$, so $f(F) \subset F \ (2)$.

We deduce that $F$ is a fixed point of $f$ from $(1)$ and $(2)$, and the theorem follows. $\square$

Theorem: (Cantor-Bernstein-Schroeder) Let $A,B$ be two sets. Suppose that there exist two injections $f : A \hookrightarrow B$ and $g : B \hookrightarrow A$. Then there exists a bijection $A \overset{\sim}{\to} B$.

Proof. First, we define the map

$\Phi : \left\{ \begin{array}{ccc} \mathfrak{P}(A) & \to & \mathfrak{P}(A) \\ X & \mapsto & g( B \backslash f(A \backslash X)) \end{array} \right.$.

Easily, we see that $\Phi$ is nondecreasing, so $\Phi$ has a fixed point $X$ according to Tarski’s theorem. Now notice that

$A = X \coprod (A \backslash X) \ \text{and} \ B= ( B \backslash f(A \backslash X)) \coprod f(A \backslash X)$,

and that $g$ induces a bijection $B \backslash f(A \backslash X) \overset{\sim}{\to} g( B \backslash f(A \backslash X)) = \Phi(X)=X$ and $f$ induces a bijection $A \backslash X \overset{\sim}{\to} f(A \backslash X)$. Therefore, $A$ and $B$ are equipotent. By the way, an explicit bijection from $A$ to $B$ is given by

$x \mapsto \left\{ \begin{array}{cl} f(x) & \text{if} \ x \in X \\ g^{-1}(x) & \text{if} \ x \notin X \end{array} \right. . \hspace{1cm} \square$