Cantor-Bernstein-Schröder Theorem/Lemma/Proof 1
Theorem
Let $S$ be a set.
Let $T \subseteq S$.
Suppose that $f: S \to T$ is an injection.
Then there is a bijection $g: S \to T$.
Proof
Recursively define a sequence $\langle C_n \rangle$ in the power set of $S$ as follows:
- $C_0 = S \setminus T$, the difference between $S$ and $T$.
- $C_{n+1} = f \left[{C_n}\right]$, the image of $C_n$ under $f$.
Let $\displaystyle C := \bigcup_{n \mathop \in \N} C_n$.
Define a mapping $h: S \to T$ as follows:
- $\displaystyle h \left({x}\right) = \begin{cases} f \left({x}\right) & : x \in C \\ x & : x \notin C \end{cases}$
$h$ is a mapping from $S$ to $T$
By Law of Excluded Middle, for each $x \in S$:
- $x \in C$
or:
- $x \notin C$
Thus the construction produces a mapping on S.
It remains to be shown that:
- $\forall x \in S: h \left({x}\right) \in T$
Let $x \in C$.
Then:
- $h \left({x}\right) = f \left({x}\right) \in T$
Let $x \notin C$.
Then by Set is Subset of Union:
- $x \notin C_0$
As $x \in S$:
- $x \in S \setminus C_0$
by the definition of set difference.
By Relative Complement of Relative Complement:
- $S \setminus C_0 = T$
Thus $x \in T$ by the definition of subset.
As $h \left({x}\right) = x$ in this case:
- $h \left({x}\right) \in T$
$\Box$
$h$ is injective
Let $x, y \in S$.
Suppose that $h \left({x}\right) = h \left({y}\right)$.
By Law of Excluded Middle for Two Variables:
- $\left({x \in C}\right) \land \left({y \in C}\right)$
or:
- $\left({x \notin C}\right) \land \left({y \notin C}\right)$
or:
- $\left({x \in C}\right) \land \left({y \notin C}\right)$
or:
- $\left({x \notin C}\right) \land \left({y \in C}\right)$
Let $x, y \in C$.
Then $x = y$ because $f$ is injective.
Let $x, y \notin C$.
Then $x = y$ by Identity Mapping is Injection.
Let $x \in C$ and $y \notin C$.
Then $x \in C_n$ for some $n$ by the definition of union.
- $h \left({x}\right) = f \left({x}\right) \in C_{n+1} \subseteq C$
Thus $h \left({x}\right) \in C$.
- $h \left({y}\right) = y$ by the definition of $h$.
Since $y \notin C$, this contradicts the assumption that $h \left({x}\right) = h \left({y}\right)$.
The argument for the case of $x \notin C$ and $y \in C$ is identical to the preceding.
Thus $h \left({x}\right) = h \left({y}\right) \implies x = y$ for all $x, y \in S$, so $h$ is injective.
$\Box$
$h$ is surjective
Let $y \in T$.
- $y \in C$
or:
- $y \notin C$
Let $y \notin C$.
Then:
- $h \left({y}\right) = y$
Let $y \in C$.
Then as $y \notin C_0 = S \setminus T$:
- $\exists n \in \N_{>0}: y \in C_{n+1}$
Thus:
- $\exists x \in C_n: y = f \left({x}\right)$
By the definition of union:
- $x \in C$
Thus:
- $h \left({x}\right) = f \left({x}\right) = y$
Thus:
- $\forall y \in T: \exists x \in S: h \left({x}\right) = y$
Thus by definition, $h$ is surjective.
$\blacksquare$
Sources
This article incorporates material from proof of Schroeder-Bernstein theorem on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.