Cantor-Bernstein-Schröder Theorem/Proof 1

From ProofWiki
Jump to navigation Jump to search

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: S \to T_1$
$g: T \to S_1$


Let:

$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$.

For each natural number $k$, let $S_{k+2} \subseteq S$ be the image of $S_k$ under the mapping $g \circ f$.


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


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


Now we can represent $S$ as:

\(\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\) $(1)$

where $S \setminus S_1$ denotes set difference.


Similarly, we can represent $S_1$ as:

\(\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\) $(2)$


Now let:

\(\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 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 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\)


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

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


Now:

\(\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 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)\)


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$


Source of Name

This entry was named for Georg Cantor, Felix Bernstein and Ernst Schröder.


Sources