Cantor-Bernstein-Schröder Theorem/Lemma

From ProofWiki
Jump to navigation Jump to search

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 1

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.


By Set is Subset 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$.

By Law of Excluded Middle:

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


Proof 2

Define a mapping $E: \mathcal P \left({S}\right) \to \mathcal P \left({S}\right)$ as:

$E \left({K}\right) = S \setminus \left({T \setminus f \left[{K}\right]}\right)$

where $f \left[{K}\right]$ is the image of $K$ under $f$.

Then:

$E \left({K}\right) = \left({S \setminus T}\right) \cup f \left[{K}\right]$

By Image of Subset under Relation is Subset of Image and the corollary to Set Union Preserves Subsets, $E$ is increasing.


Thus by Knaster-Tarski Lemma: Power Set, $E$ has a fixed point $X$.

Then by the definition of fixed point:

$E \left({X}\right) = X$

That is:

$\left({S \setminus \left({T \setminus f \left[{X}\right]}\right)}\right) = X$

Taking the set difference from $S$:

$T \setminus f \left[{X}\right] = S \setminus X$

Let $f'$ be the restriction of $f$ to $X \times f \left[{X}\right]$.

By Injection to Image is Bijection, $f'$ is a bijection.

By Identity Mapping is Bijection, the identity mapping $I_{S \mathop \setminus X}$ from $S \setminus X$ to $T \setminus f \left[{X}\right]$ is a bijection.

Thus by Union of Bijections with Disjoint Domains and Codomains is Bijection, $g = f' \cup i$ is the bijection we seek.

$\blacksquare$