Cantor-Bernstein-Schröder Theorem/Lemma/Proof 2
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
Define a mapping $E: \powerset S \to \powerset S$ as:
- $\map E K = S \setminus \paren {T \setminus f \sqbrk K}$
where $f \sqbrk K$ is the image of $K$ under $f$.
Then:
- $\map E K = \paren {S \setminus T} \cup f \sqbrk K$
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 definition of fixed point:
- $\map E X = X$
That is:
- $\paren {S \setminus \paren {T \setminus f \sqbrk X} } = X$
Taking the set difference from $S$:
- $T \setminus f \sqbrk X = S \setminus X$
Let $f'$ be the restriction of $f$ to $X \times f \sqbrk X$.
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 \sqbrk X$ 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$