Calculus

Set Theory

Set Theory Logo

Cantor-Schröder-Bernstein Theorem

The Cantor-Schröder-Bernstein theorem \(\left( {\text{CSB}} \right)\) states that for any two sets \(A\) and \(B,\) if \(\left| A \right| \le \left| B \right|\) and \(\left| B \right| \le \left| A \right|,\) then \(\left| A \right| = \left| B \right|.\)

In terms of functions, the Cantor-Schröder-Bernstein theorem states that if \(A\) and \(B\) are sets and there are injective functions \(f : A \to B\) and \(g : B \to A,\) then there exists a bijective function \(h : A \to B.\)

In terms of relation properties, the Cantor-Schröder-Bernstein theorem shows that the order relation on cardinalities of sets is antisymmetric.

\( {\text{CSB}} \) is a fundamental theorem of set theory. It is a convenient tool for comparing cardinalities of infinite sets.

Proof

There are many different proofs of this theorem. We present here a direct proof by using the definitions of injective and surjective function.

Let \(A, B\) be sets and let \(f: A \to B\) and \(g : B \to A\) be injective functions. We need to show that there is a bijective function \(h : A \to B.\)

We will denote the range of the function \(f\) by \(f\left( A \right)\) and the range of the function \(g\) by \(g\left( B \right).\) By condition, the functions \(f: A \to B\) and \(g : B \to A\) are injective, so they may not have inverse functions (unless they are also surjective). However, the function \(g : B \to g\left( B \right)\) between sets \(B\) and \(g\left( B \right)\) is bijective, and therefore it has an inverse \(g^{-1} : g\left( B \right) \to B.\)

Two injections in the Cantor-Schroeder-Bernstein theorem.
Figure 1.

Successively applying the injections \(g\) and \(f,\) we get the following fractal-like structures:

Bijective function in the Cantor-Schroeder-Bernstein theorem.
Figure 2.

Let \({A_0} = A\backslash g\left( B \right)\) be the complement of \(g\left( B \right)\) after the function \(g\) is applied for the first time. When we circle back to \(A\) with the next iteration, we get \({A_1} = \left( {g \circ f} \right)\left( {{A_0}} \right).\) Each cycle creates a new nested region \(A_1, A_2, \ldots, A_n, A_{n+1},\ldots\) (shaded in blue) according to the recurrence relation

\[{A_{n + 1}} = \left( {g \circ f} \right)\left( {{A_n}} \right).\]

Assuming the process is infinite, the entire blue region of the set \(A\) is given by

\[{{A_\infty } = \bigcup\limits_{n = 0}^\infty {{A_n}} }={ \bigcup\limits_{n = 0}^\infty {{{\left( {g \circ f} \right)}^n}\left( {A\backslash g\left( B \right)} \right)} .}\]

The remaining (orange) region in \(A\) is expressed as \(A \backslash A_{\infty}.\)

Thus, we partitioned the original set \(A\) into two subsets that “behave” differently. The first subset \(A_{\infty}\) maps the blue areas in \(A\) to the blue areas in \(B\) under the function \(f.\) The second subset \(A \backslash A_{\infty}\) maps the orange areas in \(A\) to the orange areas in \(B\) using the function \(g^{-1}.\)

The resulting function \(h : A \to B\) is defined as follows:

\[h\left( x \right) = \left\{ {\begin{array}{*{20}{l}} {f\left( x \right)} &{\text{if }x \in {A_\infty }}\\ {{g^{ – 1}}\left( x \right)} &{\text{otherwise}} \end{array}} \right..\]

To see that \(h\) is injective, we pick two elements \(x,y \in A\) and show that \(h\left( x \right) = h\left( y \right)\) implies \(x = y.\) Consider three cases:

  1. If \(x,y \in A_{\infty},\) then \[{h\left( x \right) = h\left( y \right),}\;\; \Rightarrow {f\left( x \right) = f\left( y \right),}\;\; \Rightarrow {x = y,}\] because the function \(f\) is injective.
  2. If \(x,y \not\in A_{\infty},\) then given that \(g\) is injective, we get \[{h\left( x \right) = h\left( y \right),}\;\; \Rightarrow {{g^{ – 1}}\left( x \right) = {g^{ – 1}}\left( y \right),}\;\; \Rightarrow {\left( {g \circ {g^{ – 1}}} \right)\left( x \right) = \left( {g \circ {g^{ – 1}}} \right)\left( y \right),}\;\; \Rightarrow {x = y.}\]
  3. If \(x \in A_{\infty}\) but \(y \not\in A_{\infty},\) then \(x \in A_n\) for some \(n.\) This yields: \[{h\left( x \right) = h\left( y \right),}\;\; \Rightarrow {f\left( x \right) = {g^{ – 1}}\left( y \right),}\;\; \Rightarrow {\left( {g \circ f} \right)\left( x \right) = \left( {g \circ {g^{ – 1}}} \right)\left( y \right),}\;\; \Rightarrow {y = \left( {g \circ f} \right)\left( x \right) }\in{ \left( {g \circ f} \right)\left( {{A_n}} \right) }={ {A_{n + 1}}.}\] This contradicts the assumption that \(y \not\in A_{\infty}.\) Hence, this case cannot happen.

To see that \(h\) is surjective, we take an arbitrary element \(b \in B\) and show that there is a preimage \(x \in A\) such that \(h\left( x \right) = b.\) There are two cases to consider:

  1. If \(x = g\left( b \right) \not\in A_{\infty},\) then \[{h\left( x \right) = {g^{ – 1}}\left( x \right) }={ {g^{ – 1}}\left( {g\left( b \right)} \right) }={ \left( {{g^{ – 1}} \circ g} \right)\left( b \right) }={ b.}\]
  2. If \(x = g\left( b \right) \in A_{\infty},\) then \(x \in A_n\) for some \(n.\) Here \(n \gt 0\) because \(x \in g\left( B \right).\) Using the recurrence relation \({A_{n}} = \left( {g \circ f} \right)\left( {{A_{n-1}}} \right),\) we can write \(x \in \left( {g \circ f} \right)\left( {{A_{n-1}}} \right).\) If we take an element \(z \in A_{n-1},\) then we have \(x = \left( {g \circ f} \right)\left( z \right) = g\left( {f\left( z \right)} \right).\) The function \(g\) is injective. Therefore \[\left\{ \begin{array}{l} x = g\left( b \right)\\ x = g\left( {f\left( z \right)} \right) \end{array} \right., \Rightarrow b = f\left( z \right).\] We can choose \(x = z\) to have \[{h\left( x \right) = f\left( x \right) }={ f\left( z \right) }={ b.}\]

Thus for any \(b \in B,\) there is an element \(x \in A\) for which \(h\left( x \right) = b.\) So, the function \(h\) is surjective. Since \(h\) is both injective and surjective, it is bijective.

Corollary \(1.\) \(\left| {\left( {0,1} \right]} \right| = \left| {\left( {0,1} \right)} \right|\)

We have already found a bijective function between the sets \({\left( {0,1} \right]}\) and \({\left( {0,1} \right)}\) in Example \(3\) on the Cardinality of a Set page. Now we solve the problem by using the Cantor-Schröder-Bernstein theorem.

The function \(f\left( x \right) = \frac{x}{2} + \frac{1}{4}\) is an injection \(\left( {0,1} \right] \to \left( {0,1} \right).\) Also, the function \(g\left( x \right) = x\) is an injection \(\left( {0,1} \right) \to \left( {0,1} \right].\) It then follows from the CSB theorem that

\[\left| {\left( {0,1} \right]} \right| = \left| {\left( {0,1} \right)} \right|.\]

Thus, in order to prove that two sets have the same cardinality, we can just look for injections both ways instead of looking for a bijection.

Corollary \(2.\) Equal Cardinalities of Unit Square and Unit Interval

Consider the open unit square \(I \times I = \left( {0,1} \right) \times \left( {0,1} \right)\) and the open unit interval \(I = \left( {0,1} \right).\)

Unit square and unit interval have the same cardinality.
Figure 3.

To build an injection from \(I \times I\) to \(I,\) we represent the coordinates \(\left( {x,y} \right)\) of an arbitrary point of the square by their decimal expansions. Let

\[{x = 0.{x_1}{x_2}{x_3} \ldots ,\;\;}\kern0pt{y = 0.{y_1}{y_2}{y_3} \ldots }\]

We assume here that \(x\) and \(y\) do not have a repeating sequence of \(9’\text{s}\) at the end. If there exists such a number, it must be represented as a terminating decimal:

\[0.73699999 \ldots = 0.737\]

We define the mapping \(f:I \times I \to I\) as follows:

\[{f\left( {\left( {x,y} \right)} \right) = z }={ 0.{x_1}{y_1}{x_2}{y_2}{x_3}{y_3} \ldots }\]

If \(\left( {{x},{y}} \right) \ne \left( {{x^\prime},{y^\prime}} \right),\) then the two numbers have a different coordinate, and hence, their decimal expansions are also different, that is, \({z_1} \ne {z_2}.\) This means that the function \(f\) is injective.

There is a natural injection from \(I\) to \(I \times I:\) \(g\left( z \right) = \left( {a,z} \right),\) where \(a\) is any number from the interval \(\left( {0,1} \right).\) For example, if we take \(a = \large{\frac{1}{2}}\normalsize,\) then \(g\left( z \right) = \left( {\large{\frac{1}{2}}\normalsize, z} \right).\)

By the Cantor-Schröder-Bernstein theorem,

\[\left| {\left( {0,1} \right) \times \left( {0,1} \right)} \right| = \left| {\left( {0,1} \right)} \right|.\]

Thus, the open unit square and the open unit interval have the same cardinality, which is an amazing result!

Corollary \(3.\) \(\left| \mathbb{R} \right| = \left| {\mathbb{R} \times \mathbb{R}} \right|\)

We can map \(I \to \mathbb{R}\) using the function

\[f\left( x \right) = \tan \left( {\pi x – \frac{\pi }{2}} \right).\]

This mapping is bijective.

Similarly, the mapping \(I \times I \to \mathbb{R} \times \mathbb{R}\) is given by the function

\[{g\left( {x,y} \right) \text{ = }}\kern0pt{ \left( {\tan \left( {\pi x – \frac{\pi }{2}} \right),\tan \left( {\pi y – \frac{\pi }{2}} \right)} \right)}\]

that is also bijective.

Then we have

\[{\left| {\mathbb{R} \times \mathbb{R}} \right| = \left| {\left( {0,1} \right) \times \left( {0,1} \right)} \right| }={ \left| {\left( {0,1} \right)} \right| }={ \left| \mathbb{R} \right|,}\]

that is, the set of points of a plane and the set of points of a number line have the same cardinality.

Corollary \(4.\) \(\left| \mathbb{R} \right| = \left| {\mathcal{P}\left( \mathbb{N} \right)} \right|\)

Notice that the cardinality of \(\mathbb{R}\) is the same as the cardinality of the open unit interval \(I = \left( {0,1} \right)\) because there exists a bijective function \(f: I \to \mathbb{R}\) between the sets:

\[f\left( x \right) = \tan \left( {\pi x – \frac{\pi }{2}} \right).\]

Next, similarly to the Corollary \(1,\) we can easily prove that the open interval \({\left( {0,1} \right)}\) and the closed interval \({\left[ {0,1} \right]}\) have the same cardinality. Hence, we will just need to show that \(\left| {\left[ {0,1} \right]} \right| = \left| {\mathcal{P}\left( \mathbb{N} \right)} \right|.\) By the Cantor-Schröder-Bernstein theorem, it suffices to find injections \(\left[ {0,1} \right] \to \mathcal{P}\left( \mathbb{N} \right)\) and \(\mathcal{P}\left( \mathbb{N} \right) \to \left[ {0,1} \right].\)

To define \(\left[ {0,1} \right] \to \mathcal{P}\left( \mathbb{N} \right),\) we use the fact that any real can be represented as a binary decimal. Let

\[{x = 0.{b_1}{b_2}{b_3}{b_4} \ldots \in \left[ {0,1} \right], \;}\kern0pt{\text{where }\;{b_i} \in \left\{ {0,1} \right\}.}\]

Then the mapping function is given by

\[f\left( x \right) = \left\{ {i \in \mathbb{N} \mid {b_i} = 1} \right\}.\]

For example,

\[{f\left( {0.110001 \cdots } \right) = \left\{ {1,2,6, \ldots } \right\},\;\;}\kern0pt{f\left( {0.00111010 \cdots } \right) = \left\{ {3,4,5,7, \ldots } \right\}.}\]

The function \(f\) is injective.

To define \(\mathcal{P}\left( \mathbb{N} \right) \to \left[ {0,1} \right],\) we use the similar approach. Let \(S\) be a subset of \(\mathbb{N}.\) The function \(g\left( S \right)\) is given by

\[g\left( S \right) = 0.{b_1}{b_2}{b_3}{b_4} \ldots ,\]

where \(b_i = 1\) if \(i \in S\) and \(b_i = 0\) if \(i \not\in S.\) For example,

\[{g\left( {\left\{ {1,2,7,8, \ldots } \right\}} \right) = 0,11000011 \cdots,\;\;}\kern0pt{g\left( {\left\{ {4,5,6, \ldots } \right\}} \right) = 0,000111 \cdots .}\]

We also set

\[\require{AMSsymbols}{g\left( \varnothing \right) = 0,\;\;}\kern0pt{g\left( N \right) = 0.11111 \cdots .}\]

It is clear that the function \(g\) is injective.

By the Cantor-Schröder-Bernstein theorem, \(\left| \left[ {0,1} \right]\right| = \left| {\mathcal{P}\left( \mathbb{N} \right)} \right|\) and hence

\[\left| \mathbb{R} \right| = \left| {\mathcal{P}\left( \mathbb{N} \right)} \right|.\]

Note that if \(A\) is an arbitrary set, its power set \(\mathcal{P}\left( A \right)\) can be represented as

\[\left| {P\left( A \right)} \right| = {2^{\left| A \right|}}.\]

Indeed, with every subset \(B \subseteq A,\) we can associate the characteristic function \({\chi _B}:A \to \left\{ {0,1} \right\}\) defined by

\[{\chi _B}\left( a \right) = \left\{ {\begin{array}{*{20}{l}} {1} &{\text{if}\;\;a \in B}\\ {0} &{\text{if}\;\;a \not\in B} \end{array}} \right.,\]

where \(a \in A.\)

Clearly, the total number of subsets of \(A\) is \(2^{\left| A \right|}.\) For the set of natural numbers, we obtain

\[\left| {\mathcal{P}\left( \mathbb{N} \right)} \right| = {2^{\left| \mathbb{N} \right|}}.\]

Then

\[\left| \mathbb{R} \right| = \left| {\mathcal{P}\left( \mathbb{N} \right)} \right| = {2^{\left| \mathbb{N} \right|}}.\]


Solved Problems

Click or tap a problem to see the solution.

Example 1

Let \(A \subseteq B \subseteq C.\) Show that if \(\left| A \right| = \left| C \right|,\) then \(\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.

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.

Example 4

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

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}\kern0pt{ 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}\kern0pt{ \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|.\]