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 functionsf : A → B and g : B → A, then there exists a bijective functionh : A → B.
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
Figure 1.
Successively applying the injections and we get the following fractal-like structures:
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:
If then
because the function is injective.
If then given that is injective, we get
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:
If then
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
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