📂Set Theory

Proof of the Cantor-Bernstein Theorem

Theorem ¹

A set $A$, $B$ is equivalent to a subset of $B$ being equivalent to a subset of $A$ if and only if $A$ and $B$ are equivalent.

---

• Two sets are equivalent if and only if there exists a bijective function between them.

Proof

Strategy: We attempt to express taking function $f$ on $x$ $k$ times as $f^{k}(x)$. For all $k \in \mathbb{N}$, it should be representable as $f^{k}(x) = f \left( f^{k-1}(x) \right)$. From this perspective, $f^{0}$ can be considered an identity function, which is a function that has not taken $f$ at all.

First, for the subset $B$ of set $A$, we want to show that if there exists an injection $f: A \to B$, then there is also a bijection $h : A \to B$. If $B=A$, any injection $f$ would have an identity function $h:=f^{0}$, hence there’s nothing more to prove, so we only consider when $B \subsetneq A$.

---

Part 1. If $n \ne m$, then $f^{n}(A \setminus B) \cap f^{m}(A \setminus B) = \emptyset$

Assume for $m < n$, $f^{n}(A \setminus B) \cap f^{m}(A \setminus B) \ne \emptyset$ holds. This implies the existence of some $x_{1}, x_{2} \in (A \setminus B)$ satisfying $f^{n}(x_{1}) = f^{m}(x_{2})$. Hence, $$\begin{align*} f^{n-m}(x_{1}) =& f^{m-m}(x_{2}) \\ =& f^{0}(x_{2}) \\ =& x_{2} \end{align*}$$ Where $f^{0}(x_{2}) \in B$ means $x_{2} \in B$. However, this contradicts $x_{2} \in (A \setminus B)$. Similarly, it can be shown that when $m > n$, $f^{n}(A \setminus B) \cap f^{m}(A \setminus B) \ne \emptyset$ holds.

---

Part 2. $h(A) = B$

Define set $C$ as follows. $$\begin{align*} C:=& \bigcup_{n \ge 0} f^{n} (A \setminus B) \\ h(z):=& \begin{cases} f(z) & , z \in C \\ z &,z \in A\setminus C\end{cases} \end{align*}$$ Defining function $h$ for $C$ and $z \in A$ as above, we find $A \setminus B \subset C$ and, $f (C) \subset C$. By the property of the image of a function over a union, $$\begin{align*} h(A) =& (A\setminus C) \cup f (C) \\ =& \left[ A \setminus \bigcup_{n \ge 0} f^{n} (A \setminus B) \right] \cup f \left( \bigcup_{n \ge 0} f^{n} (A \setminus B) \right) \\ =& \left[ A \cap \left( \bigcup_{n \ge 0} f^{n} (A \setminus B) \right)^{c} \right] \cup \bigcup_{n \ge 1} f^{n} (A \setminus B) \\ =& \left[ A \cup \bigcup_{n \ge 1} f^{n} (A \setminus B) \right] \cap \left[ \left( \bigcup_{n \ge 0} f^{n} (A \setminus B) \right)^{c} \cup \bigcup_{n \ge 1} f^{n} (A \setminus B) \right] \\ =& A \cap \left[ \bigcup_{n \ge 0} f^{n} (A \setminus B) \cap \left( \bigcup_{n \ge 1} f^{n} (A \setminus B) \right)^{c} \right]^{c} \\ =& A \cap \left[ f^{0}(A \setminus B) \right]^{c} \\ =& A \cap ( A \setminus B)^{c} \\ =& A \setminus (A \setminus B) \\ =& B \end{align*}$$ That is, $h(A) = B$, and $h$ is onto. Since $f$ is an injection, $h$ is also an injection, thus it’s bijective.

---

Part 3. $h$ is bijective

$$A_{0} \subset A \\ B_{0} \subset B$$ According to the theorem’s assumptions, if there are two bijective functions $f_{0} : A \to B_{0}$ and $g_{0} : B \to A_{0}$, then the function $f$ defined as per $f(x) = g_{0} \left( f_{0} (x) \right)$ is an injection. According to Part 1 and 2, there is a bijective function $h : A \to A_{0}$. Therefore, $g_{0}^{-1} \circ h : A \to B$ is bijective. Hence, $A$ and $B$ are equivalent.

■