Cantor-Bernstein-Schroeder Theorem/Proof 1

Theorem

If a subset of one set is equivalent to the other, and a subset of the other is equivalent to the first, then the two sets are themselves equivalent:

$\forall S, T: T \sim S_1 \subseteq S \land S \sim T_1 \subseteq T \implies S \sim T$

Proof

From the facts that $T \sim S_1$ and $S \sim T_1$, we can set up the two bijections:

• $f \left({S}\right) = T_1 \subseteq T$
• $g \left({T}\right) = S_1 \subseteq S$

Thus:

$S_2 = g \left({f \left({S}\right)}\right) = g \left({T_1}\right) \subseteq S_1$

and:

$T_2 = f \left({g \left({T}\right)}\right) = f \left({S_1}\right) \subseteq T_1$

So $S_2 \subseteq S_1$, and $S_2 \sim S$, while $T_2 \subseteq T_1$, and $T_2 \sim T$.

Let $S_3 \subseteq S$ be the image of $S_1$ under the mapping $g \circ f$,

and let $S_4 \subseteq S$ be the image of $S_2$ under the mapping $g \circ f$.

We can generalise this to:

Let $S_{k+2} \subseteq S$ be the image of $S_k$ under the mapping $g \circ f$, where $k \in \N$.

Then $S \supseteq S_1 \supseteq S_2 \supseteq \ldots \supseteq S_k \supseteq S_{k+1} \ldots$.

Set $\displaystyle D = \bigcap_{k=1}^\infty {S_k}$.

Now we can represent $S$ as:

\(\displaystyle \)

\(\displaystyle S\)

\(=\)

\(\displaystyle \left({S \setminus S_1}\right) \cup \left({S_1 \setminus S_2}\right) \cup \ldots \cup \left({S_k \setminus S_{k+1} }\right) \cup \ldots \cup D\)

\(\displaystyle \)

$(1)$

where $S \setminus S_1$ denotes set difference.

Similarly, we can represent $S_1$ as:

\(\displaystyle \)

\(\displaystyle S_1\)

\(=\)

\(\displaystyle \left({S_1 \setminus S_2}\right) \cup \left({S_2 \setminus S_3}\right) \cup \ldots \cup \left({S_k \setminus S_{k+1} }\right) \cup \ldots \cup D\)

\(\displaystyle \)

$(2)$

Now let:

	\(\displaystyle \)	\(\displaystyle M\)	\(=\)	\(\displaystyle \left({S_1 \setminus S_2}\right) \cup \left({S_3 \setminus S_4}\right) \cup \left({S_5 \setminus S_6}\right) \cup \ldots\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle N\)	\(=\)	\(\displaystyle \left({S \setminus S_1}\right) \cup \left({S_2 \setminus S_3}\right) \cup \left({S_4 \setminus S_5}\right) \cup \ldots\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle N_1\)	\(=\)	\(\displaystyle \left({S_2 \setminus S_3}\right) \cup \left({S_4 \setminus S_5}\right) \cup \left({S_6 \setminus S_7}\right) \cup \ldots\)	\(\displaystyle \)

... and rewrite $(1)$ and $(2)$ as:

	\(\displaystyle \)	\(\displaystyle S\)	\(=\)	\(\displaystyle D \cup M \cup N\)	\(\displaystyle \)	$(3)$
	\(\displaystyle \)	\(\displaystyle S_1\)	\(=\)	\(\displaystyle D \cup M \cup N_1\)	\(\displaystyle \)	$(4)$

Now:

	\(\displaystyle \)	\(\displaystyle g \circ f \left({S \setminus S_1}\right) = \left({S_2 \setminus S_3}\right)\)	\(\implies\)	\(\displaystyle \left({S \setminus S_1}\right) \sim \left({S_2 \setminus S_3}\right)\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle g \circ f \left({S_2 \setminus S_3}\right) = \left({S_4 \setminus S_5}\right)\)	\(\implies\)	\(\displaystyle \left({S_2 \setminus S_3}\right) \sim \left({S_4 \setminus S_5}\right)\)	\(\displaystyle \)

and so on.

So $N \sim N_1$.

It follows from $(3)$ and $(4)$ that a bijection can be set up between $S$ and $S_1$.

But $S_1 \sim T$.

Therefore $S \sim T$.

$\blacksquare$

Sources

• A.N. Kolmogorov and S.V. Fomin‎: Introductory Real Analysis (1968): $\S 2.6$: Theorem $7$