# Cantor-Schröder-Bernstein Theorem

## Solved Problems

### Example 1.

Let $$A \subseteq B \subseteq C.$$ Show that if $$\left| A \right| = \left| C \right|,$$ then $$\left| A \right| = \left| B \right|.$$

Solution.

Since $$A$$ is a subset of $$B,$$ there exists an injection $$A \to B,$$ so we have $$\left| A \right| \le \left| B \right|.$$ Likewise, since $$B \subseteq C,$$ we find that $$\left| B \right| \le \left| C \right|.$$ As a result, we obtain the double inequality

$\left| A \right| \le \left| B \right| \le \left| C \right|.$

By condition, $$\left| A \right| = \left| C \right|.$$ Therefore, we have

$\left| A \right| \le \left| B \right| \le \left| A \right|.$

Using the Cantor-Schröder-Bernstein theorem, we get

$\left| A \right| \le \left| B \right| \le \left| A \right|,\;\; \Rightarrow \left\{ {\begin{array}{*{20}{l}} {\left| A \right| \le \left| B \right|}\\ {\left| B \right| \le \left| A \right|} \end{array}} \right.,\;\; \Rightarrow \left| A \right| = \left| B \right|.$

### Example 2.

Show that $$\left| {{\mathbb{N}^{\mathbb{N}}}} \right| = \left| \mathbb{R} \right|,$$ where $$\mathbb{N}^{\mathbb{N}}$$ is the set of all infinite sequences of natural numbers.

Solution.

Since $$\left| \mathbb{R} \right| = \left| {\left( {0,1} \right)} \right|,$$ we compare the cardinalities of $${{\mathbb{N}^{\mathbb{N}}}}$$ and $${\left( {0,1} \right)}.$$

To build an injection $${\mathbb{N}^{\mathbb{N}}} \to \left( {0,1} \right),$$ consider an arbitrary infinite sequence $$\left( {{a_1},{a_2},{a_3}, \ldots } \right) \in {\mathbb{N}^{\mathbb{N}}}$$ where $${a_i} \in \mathbb{N}.$$ This sequence is mapped to a number in the open unit interval:

$\left( {{a_1},{a_2},{a_3}, \ldots } \right) \to 0.\underbrace {0 \cdots 0}_{{a_1}}1\underbrace {0 \cdots 0}_{{a_2}}1\underbrace {0 \cdots 0}_{{a_3}}1 \cdots .$

Clearly, this mapping is injective.

To define $$\left| {\left( {0,1} \right)} \right| = \left| \mathbb{R} \right|,$$ we use the fact that every real number has a unique infinite decimal representation. In this case, a finite decimal is converted into infinite one like

$0.375 = 0.3749999 \cdots .$

Let a real number $$b \in \left( {0,1} \right)$$ be represented as

$b = 0.{b_1}{b_2}{b_3} \cdots.$

We can map the number $$b$$ to the following infinite sequence:

$0.{b_1}{b_2}{b_3} \cdots \to \left( {\underbrace {1, \ldots ,1}_{{b_1}},2,\underbrace {1, \ldots ,1}_{{b_2}},2,\underbrace {1, \ldots ,1}_{{b_3}},2, \ldots } \right) \in {\mathbb{N}^{\mathbb{N}}}.$

This mapping is also injective.

Consequently, by the Cantor-Schröder-Bernstein theorem,

$\left| {{\mathbb{N}^{\mathbb{N}}}} \right| = \left| {\left( {0,1} \right)} \right| = \left| \mathbb{R} \right|.$

### Example 3.

Prove that $$\left| {{\mathbb{R}^{\mathbb{N}}}} \right| = \left| \mathbb{R} \right|,$$ where $${\mathbb{R}^{\mathbb{N}}}$$ is the set of all infinite sequences of real numbers.

Solution.

Since $$\left| \mathbb{R} \right| = \left| {\mathcal{P}\left( \mathbb{N} \right)} \right| = {2^{\left| \mathbb{N} \right|}},$$ we have

$\left| {{\mathbb{R}^{\mathbb{N}}}} \right| = {\left( {{2^{\left| \mathbb{N} \right|}}} \right)^{\left| \mathbb{N} \right|}} = {2^{\left| \mathbb{N} \right| \times \left| \mathbb{N} \right|}} = {2^{\left| {\mathbb{N} \times \mathbb{N}} \right|}}.$

Recall (see Countable and Uncountable Sets) that

$\left| {\mathbb{N} \times \mathbb{N}} \right| = \left| \mathbb{N} \right|.$

Hence,

$\left| {{\mathbb{R}^{\mathbb{N}}}} \right| = {2^{\left| {\mathbb{N} \times \mathbb{N}} \right|}} = {2^{\left| \mathbb{N} \right|}} = \left| \mathbb{R} \right|.$

### Example 4.

Determine the cardinality of the set of all continuous functions of a real variable.

Solution.

According to Heine definition, a real function $$f\left( x \right)$$ is said to be continuous at a point $$x \in \mathbb{R}$$ if for any sequence $$\left\{ {{q_n}} \right\}$$ such that

$\lim\limits_{n \to \infty } {q_n} = x,$

it holds that

$\lim\limits_{n \to \infty } f\left( {{q_n}} \right) = f\left( x \right).$

It is also known that for every $$x \in \mathbb{R},$$ there exists a sequence of rational numbers $${q_n}$$ that converges to $$x.$$ Therefore, any continuous real-valued function $$f$$ is determined by its values on the set of rational numbers $$\mathbb{Q}.$$

We denote the set of all continuous functions $$f:\mathbb{R} \to \mathbb{R}$$ by $$C.$$

By restricting $$f$$ to the rationals, we get a function $$f^{\prime}:\mathbb{Q} \to \mathbb{R}$$ such that $$f\left( q \right) = f^{\prime}\left( q \right)$$ for any $$q \in \mathbb{Q}.$$ The mapping $$f \to f^{\prime}$$ is injective, so

$\left| C \right| \le \left| {{\mathbb{R}^{\mathbb{Q}}}} \right|.$

Since $$\left| {{\mathbb{R}^{\mathbb{Q}}}} \right| = \left| {{\mathbb{R}^{\mathbb{N}}}} \right| = \left|\mathbb{R}\right|$$ (see Example $$3$$), we have

$\left| C \right| \le \left| \mathbb{R} \right|.$

From the other side, there also exists an injection $$\mathbb{R} \to C.$$ For example, we can map any real number $$\alpha \in \mathbb{R}$$ to the constant function $${f_\alpha }: \mathbb{R} \to \mathbb{R}$$ given by

${f_\alpha }\left( x \right) = \alpha.$

All functions $$f_\alpha$$ are continuous. Then, by the Cantor-Schröder-Bernstein theorem,

$\left| C \right| = \left| \mathbb{R} \right|.$