Cantor-Bernstein-Schroeder Theorem/Proof 3

Theorem

Let $S$ and $T$ be sets, such that:

• $\exists f: S \to T$ such that $f$ is an injection;
• $\exists g: T \to S$ such that $g$ is an injection.

Then there exists a bijection from $S$ to $T$.

Proof

Let $S, T$ be sets, and let $\mathcal P \left({S}\right), \mathcal P \left({T}\right)$ be their power sets.

Let $f: S \to T$ and $g: T \to S$ be injections that we know to exist between $S$ and $T$.

Consider the relative complements of elements of $\mathcal P \left({S}\right)$ and $\mathcal P \left({T}\right)$ as mappings:

• $\complement_S: \mathcal P \left({S}\right) \to \mathcal P \left({S}\right): \forall X \in \mathcal P \left({S}\right): \complement_S \left({X}\right) = S \setminus X$
• $\complement_T: \mathcal P \left({T}\right) \to \mathcal P \left({T}\right): \forall Y \in \mathcal P \left({T}\right): \complement_T \left({Y}\right) = T \setminus Y$

which follow directly from the definition of relative complement.

Consider the mapping $z: \mathcal P \left({S}\right) \to \mathcal P \left({S}\right)$ defined by:

$z = \complement_S \circ \left({g \circ \complement_T \circ f}\right)$

Consider $A \subseteq B \subseteq S$, so $A, B \in \mathcal P \left({S}\right)$.

We have:

	\(\displaystyle \)	\(\displaystyle A \subseteq B\)	\(\implies\)	\(\displaystyle f \left({A}\right) \subseteq f \left({B}\right)\)	\(\displaystyle \)	from Subset of Image
	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle \complement_T \left({f \left({B}\right)}\right) \subseteq \complement_T \left({f \left({A}\right)}\right)\)	\(\displaystyle \)	from Complements Invert Subsets
	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle f \left({\complement_T \left({f \left({B}\right)}\right)}\right) \subseteq g \left({\complement_T \left({f \left({A}\right)}\right)}\right)\)	\(\displaystyle \)	from Subset of Image
	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle \complement_S \left({g \left({\complement_T \left({f \left({A}\right)}\right)}\right)}\right) \subseteq \complement_S \left({g \left({\complement_T \left({f \left({B}\right)}\right)}\right)}\right)\)	\(\displaystyle \)	from Complements Invert Subsets
	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle z \left({A}\right) \subseteq z \left({B}\right)\)	\(\displaystyle \)	by definition of $z$

Now consider the collection:

$\mathbb F = \left\{{X \in \mathcal P \left({S}\right): X \subseteq z \left({X}\right)}\right\}$

As Empty Set Subset of All, we note that $\varnothing \in \mathbb F$, so $\mathbb F \ne \varnothing$.

Now consider the union of all the sets in $\mathbb F$:

$\displaystyle \mathbb G = \bigcup \left\{{X: X \in \mathbb F}\right\}$

Don't lose sight of the fact that:

$\mathbb F \subseteq \mathcal P \left({S}\right)$;

$\mathbb G \subseteq S$.

From Subset of Union: General Result, we have that $X \in \mathbb F \implies X \subseteq \mathbb G$.

Thus:

$X \subseteq z \left({X}\right) \subseteq z \left({\mathbb G}\right)$

From Union Smallest: General Result, it follows that:

$\mathbb G \subseteq z \left({\mathbb G}\right)$

and so from above:

$z \left({\mathbb G}\right) \subseteq z \left({z \left({\mathbb G}\right)}\right)$

So $z \left({\mathbb G}\right) \in \mathbb F$ and so $z \left({\mathbb G}\right) \subseteq \mathbb G$.

So from:

$z \left({\mathbb G}\right) \subseteq \mathbb G$

and:

$\mathbb G \subseteq z \left({\mathbb G}\right)$

we have from Equality of Sets:

$z \left({\mathbb G}\right) = \mathbb G$

From Relative Complement of Relative Complement we have that $\complement_S \circ \complement_S$ is the identity mapping on $\mathcal P \left({S}\right)$.

Thus we obtain:

	\(\displaystyle \)	\(\displaystyle \complement_S \left({\mathbb G}\right)\)	\(=\)	\(\displaystyle \left({\complement_S \circ z}\right) \left({\mathbb G}\right)\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left({\complement_S \circ \complement_S \circ g \circ \complement_T \circ f}\right) \left({\mathbb G}\right)\)	\(\displaystyle \)	by definition of $z$
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left({g \circ \complement_T \circ f}\right) \left({\mathbb G}\right)\)	\(\displaystyle \)	as $\complement_S \circ \complement_S = I_{\mathcal P \left({S}\right)}$

At this stage a diagram can be helpful:

Now consider the sets $S$ and $T$ in light of the fact that the relative complement forms a partition.

We have that:

• $\left\{{\mathbb G, \complement_S \left({\mathbb G}\right)}\right\}$ forms a partition of $S$;
• $\left\{{f \left({\mathbb G}\right), \complement_T \left({f \left({\mathbb G}\right)}\right)}\right\}$ forms a partition of $T$.

Thus we see that we can set up the mapping $h: S \to T$ defined as:

$\forall x \in S: h \left({x}\right) = \begin{cases} f \left({x}\right) & : x \in \mathbb G \\ g^{-1} \left({x}\right) & : x \in \complement_S \left({\mathbb G}\right) \end{cases}$

As $g$ is an injection, it follows that $g^{-1} \left({x}\right)$ is a singleton.

So $h$ is a bijection by dint of the injective nature of both $f$ and $g^{-1}$.

$\blacksquare$

Sources

• T.S. Blyth: Set Theory and Abstract Algebra (1975): $\S 8$: Theorem $8.2$