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

Advertisements