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 \sqbrk {f \sqbrk S} = g \sqbrk {T_1} \subseteq S_1$

and:

$T_2 = f \sqbrk {g \sqbrk T} = f \sqbrk {S_1} \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 \mathop = 1}^\infty S_k$.


Now we can represent $S$ as:

\(\text {(1)}: \quad\) \(\ds S\) \(=\) \(\ds \paren {S \setminus S_1} \cup \paren {S_1 \setminus S_2} \cup \ldots \cup \paren {S_k \setminus S_{k + 1} } \cup \ldots \cup D\)

where $S \setminus S_1$ denotes set difference.


Similarly, we can represent $S_1$ as:

\(\text {(2)}: \quad\) \(\ds S_1\) \(=\) \(\ds \paren {S_1 \setminus S_2} \cup \paren {S_2 \setminus S_3} \cup \ldots \cup \paren {S_k \setminus S_{k + 1} } \cup \ldots \cup D\)


Now let:

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


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

\(\text {(3)}: \quad\) \(\ds S\) \(=\) \(\ds D \cup M \cup N\)
\(\text {(4)}: \quad\) \(\ds S_1\) \(=\) \(\ds D \cup M \cup N_1\)


Now:

\(\ds g \circ f \sqbrk {S \setminus S_1} = \paren {S_2 \setminus S_3}\) \(\leadsto\) \(\ds \paren {S \setminus S_1} \sim \paren {S_2 \setminus S_3}\)
\(\ds g \circ f \sqbrk {S_2 \setminus S_3} = \paren {S_4 \setminus S_5}\) \(\leadsto\) \(\ds \paren {S_2 \setminus S_3} \sim \paren {S_4 \setminus S_5}\)


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 CantorFelix Bernstein and Friedrich Wilhelm Karl Ernst Schröder.


Sources