Calculus

Set Theory

Set Theory Logo

Cantor-Schröder-Bernstein Theorem

The Cantor-Schröder-Bernstein theorem (CSB) states that for any two sets A and B, if |A| ≤ |B| and |B| ≤ |A|, then |A| = |B|.

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

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

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 be sets and let and be injective functions. We need to show that there is a bijective function

We will denote the range of the function by and the range of the function by By condition, the functions and are injective, so they may not have inverse functions (unless they are also surjective). However, the function between sets and is bijective, and therefore it has an inverse

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

Successively applying the injections and we get the following fractal-like structures:

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

Let be the complement of after the function is applied for the first time. When we circle back to with the next iteration, we get Each cycle creates a new nested region (shaded in blue) according to the recurrence relation

We will use the symbol to denote the union over all so the entire blue region of the set is given by

The remaining (orange) region in is expressed as

Thus, we partitioned the original set into two subsets that "behave" differently. The first subset maps the blue areas in to the blue areas in under the function The second subset maps the orange areas in to the orange areas in using the function

The resulting function is defined as follows:

To see that is injective, we pick two elements and show that implies Consider three cases:

  1. If then
    because the function is injective.
  2. If then given that is injective, we get
  3. If but then for some This yields:
    This contradicts the assumption that Hence, this case cannot happen.

To see that is surjective, we take an arbitrary element and show that there is a preimage such that There are two cases to consider:

  1. If then
  2. If then for some Here because Using the recurrence relation we can write If we take an element then we have The function is injective. Therefore
    We can choose to have

Thus for any there is an element for which So, the function is surjective. Since is both injective and surjective, it is bijective.

Corollary 1.

We have already found a bijective function between the sets and in Example on the Cardinality of a Set page. Now we solve the problem by using the Cantor-Schröder-Bernstein theorem.

The function is an injection Also, the function is an injection It then follows from the CSB theorem that

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 and the open unit interval

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

To build an injection from to we represent the coordinates of an arbitrary point of the square by their decimal expansions. Let

We assume here that and do not have a repeating sequence of at the end. If there exists such a number, it must be represented as a terminating decimal:

We define the mapping as follows:

If then the two numbers have a different coordinate, and hence, their decimal expansions are also different, that is, This means that the function is injective.

There is a natural injection from to where is any number from the interval For example, if we take then

By the Cantor-Schröder-Bernstein theorem,

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

Corollary 3.

We can map using the function

This mapping is bijective.

Similarly, the mapping is given by the function

that is also bijective.

Then we have

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

Corollary 4.

Notice that the cardinality of is the same as the cardinality of the open unit interval because there exists a bijective function between the sets:

Next, similarly to the Corollary we can easily prove that the open interval and the closed interval have the same cardinality. Hence, we will just need to show that By the Cantor-Schröder-Bernstein theorem, it suffices to find injections and

To define we use the fact that any real can be represented as a binary decimal. Let

Then the mapping function is given by

For example,

The function is injective.

To define we use the similar approach. Let be a subset of The function is given by

where if and if For example,

We also set

It is clear that the function is injective.

By the Cantor-Schröder-Bernstein theorem, and hence

Note that if is an arbitrary set, its power set can be represented as

Indeed, with every subset we can associate the characteristic function defined by

where

Clearly, the total number of subsets of is For the set of natural numbers, we obtain

Then

See solved problems on Page 2.

Page 1 Page 2