The Cantor-Schröder-Bernstein theorem

Naive set theory: Size of a set

The Cantor-Schröder-Bernstein theorem

For two sets $X$ and $Y$ , we say that the cardinality of $X$ is less than or equal to the cardinality of $Y$ , or that the equipotency of $X$ is less than or equal to the equipotency of $Y$ , or that $Y$ is at least as large as $X$ , or that $X$ is not larger than $Y$ , if there exists an injective function from $X$ to $Y$ . We write: $X\preccurlyeq Y$ .

We say that the cardinality of $X$ is less than the cardinality of $Y$ , or that the equipotency of $X$ is less than the equipotency of $Y$ , or that $Y$ is greater than $X$ , or that $X$ is less than $Y$ , if there exists an injective function from $X$ to $Y$ but no bijection from $X$ to $Y$ . In other words, $X\preccurlyeq Y$ , but $X\ncong Y$ . We write: $X\prec Y$ .

With the above definitions, we can also say that a set $X$ is countable if $X\preccurlyeq \mathbb{N}$ and uncountable if $\mathbb{N}\prec X$ .

$X\prec{\Large\wp}(\mathbb{X})$ for every set $X$ .

The function $f:\; X\rightarrow {\Large\wp}(\mathbb{X}),\quad f(x)=\{x\}$ is an injective function, because if $x\neq y$ , then $\{x\}\neq\{y\}$ and thus $f(x)\neq f(y)$ .

Now suppose that there exists a bijection $g\; X\rightarrow {\Large\wp}(\mathbb{X})$ . Define $D=\bigl\{x\in X\mid x\notin g(z)\bigl\}$ . Because $g$ is surjective, there exists a $d\in X$ such that $g(d)=D$ . But then we have:

$\begin{aligned}d\in g(d)& \text{ if and only if }d\in D&(\text{because }g(d)=D)\\ &\text{ if and only if }d\notin g(d)&(\text{due to the definition of }D)\end{aligned}$ This is a contradiction, so a bijection $g$ cannot exist.

The following Cantor-Schröder-Bernstein theorem provides a convenient way to demonstrate the equipotency of sets, because one no longer needs to find a bijective function between two sets, but it suffices to find two injective functions from one set to the other and vice versa.

Let $X$ and $Y$ be two sets. If there exists an injective function from $X$ to $Y$ and there exists an injective function from $Y$ to $X$ , then there exists a bijective function from $X$ to $Y$ and the two sets are thus equipotent. In formula language:

For two sets $X$ and $Y$ : $\text{If }X\preccurlyeq Y\text{ and }Y\preccurlyeq X\text{ then } X\cong Y$ .

Assume $X\preccurlyeq Y$ and $Y\preccurlyeq X$ . Then there are two injective functions $f:\;X\rightarrow Y$ and $g\;Y\rightarrow X$ . Note that $Y\cong \mathrm{im}(g)$ . To prove that $Y\cong X$ , it is therefore sufficient to prove that $\mathrm{im}(g)\cong X$ . Now, $\mathrm{im}(g)\subset X$ and the composition $g\circ f$ is an injective function from $X$ to $\mathrm{im}(g)$ . It is therefore sufficient to prove the following lemma:

Lemma If $U\subset X$ and $U\preccurlyeq X$ , then $U\cong X$ .

The proof of this lemma is quite technical and we will omit it.

The open and closed intervals $(0,1)$ and $[0,1]$ in $\mathbb{R}$ are equipotent. In formula form: $(0,1)\cong [0,1]$ .

The function $\mathrm{id}:\;(0,1)\rightarrow [0,1]$ is injective. Define the function $\mathrm{id}:\;[0,1]\rightarrow (0,1)$ by $f(x)=\tfrac{1}{3}(x+1)$ . The function $f$ is also injective. According to the Cantor-Schröder-Bernstein theorem, the two intervals are then equipotent.

$\mathbb{R}\times \mathbb{R} \cong \mathbb{R}$ .

We already know $\mathbb{R}\cong (0,1)$ . Thus, i suffices to show: $(0,1)\times (0,1) \cong (0,1)$ . Each element $(x,y)\in (0,1)\times (0,1)$ can be written in decimal form as

$(x,y)=(0.\xi_1\xi_2\xi_3\cdots, 0.\eta_1\eta_2\eta_23\cdots)$ where each decimal expansion contains an infinite number of nonzero digits (write, for example, $1/2=0.4999\cdots$ ). The function

$f:\; (0,1)\times (0,1)\rightarrow (0,1),\quad f(x,y)=0.\xi_1\eta_1\xi_2\eta_2\xi_3\eta_3\cdots$ is injective. The function

$g:\;(0,1)\rightarrow (0,1)\times (0,1),\quad g(x)=(x,\tfrac{1}{2})$ is also injective. Thus, accoding to the Cantor-Schröder-Bernstein theorem: $(0,1)\times (0,1) \cong (0,1)$ .