Friends who have studied set theory should know that, by definition, the most direct way to determine if two sets have the same "cardinality" is to provide a bijection between them. However, such a bijection is often not easy to come up with. For example:
Please provide a bijection from [0, +\infty) to (0, +\infty).
Intuitively, the cardinalities of these two sets must be equal, and there are infinitely many bijections between them. However, most of us find it difficult to construct one. When we see a constructed bijection, our first reaction is often: "How did they think of this proof!?" For instance, one answer to the above problem is:
h(x) = \begin{cases} x^2+1, & x = 0, 1, 2, 5, 26, 677, \dots \\ x, & x \in [0, +\infty) \text{ and } x \neq 0, 1, 2, 5, 26, \dots \end{cases}
In this case, each subsequent term in the sequence 0, 1, 2, 5, 26, 677, \dots is the square of the previous term plus 1. Such a constructed bijection is undoubtedly amazing!
Intuitive Analysis
How can we construct such a bijection? The idea is quite elegant. First, assume that sets A and B have the same cardinality. Although a bijection A \to B might be hard to provide, an injection f: A \to B is usually easy to find (which is a bijection from A to a subset of B). Similarly, we can provide an injection g: B \to A. An "economical" idea is: can we "patch together" a bijection A \to B using f and g^{-1}?
The answer is yes, and this is what we call the "Cantor-Bernstein Theorem"! Below is a simple description of the underlying logic.
Step One: First consider the injection g: B \to A. The range of g is g(B), which means the domain of g^{-1} is at most g(B). Consequently, in the bijection A \to B, the part corresponding to A \setminus g(B) must be defined by f. Let C_0 = A \setminus g(B).
Step Two: If C_0 = \emptyset, then the bijection can be defined solely by g^{-1}. If C_0 \neq \emptyset, then the C_0 part must be defined by f. However, this does not mean the remaining part is simply defined by g^{-1}. This is because the remaining part (i.e., g(B)) maps to the entire set B via g^{-1}, and f also maps C_0 to a portion of B. This would result in a mapping that is not a bijection (it wouldn’t be injective).
Step Three: To resolve the difficulty in Step Two, the only way is to slightly expand the domain of f and slightly shrink the domain of g^{-1}. Since the C_0 part must already be defined by f, we can only increase the domain of f. The image of C_0 in B is f(C_0). We cannot let the image of g^{-1} intersect with it. This means we must remove g(f(C_0)) = C_1 from the domain of g^{-1} (which is g(B)). After this removal, g^{-1}(x) can no longer belong to f(C_0).
Step Four: However, while we have removed the influence of C_0, we have now introduced C_1. We must use the same technique to remove the influence of C_1, which inevitably produces an influence from C_2 = g(f(C_1)), and so on to infinity. After removing these infinite influences, we obtain a valid bijection.
Expressed in mathematical language: h(x) = \begin{cases} f(x), & x \in C \\ g^{-1}(x), & x \in A \setminus C \end{cases} where C = \bigcup_{n=0}^{\infty} C_n and C_{n+1} = g(f(C_n)).
It can be proven that this is indeed a bijection A \to B. The specific proof is not included here; readers may refer to the Wikipedia entry for the Schröder-Bernstein theorem.
Example Demonstration
Now let us see how to provide a bijection from [0, +\infty) to (0, +\infty). Let: \begin{cases} f(x) = x^2+1, & x \in [0, +\infty) \\ g(x) = x, & x \in (0, +\infty) \end{cases} Here f and g are injections from [0, +\infty) \to (0, +\infty) and (0, +\infty) \to [0, +\infty) respectively, and g^{-1}(x) = x. We can calculate: \begin{aligned} C_0 &= [0, +\infty) \setminus (0, +\infty) = \{0\} \\ C_1 &= g(f(C_0)) = \{1\} \\ C_2 &= g(f(C_1)) = \{2\} \\ C_3 &= g(f(C_2)) = \{5\} \\ &\dots \end{aligned} Therefore: C = \bigcup_{n=0}^{\infty} C_n = \{0, 1, 2, 5, 26, 677, \dots\} Thus, we obtain the bijection: h(x) = \begin{cases} x^2+1, & x = 0, 1, 2, 5, 26, 677, \dots \\ x, & x \in [0, +\infty) \text{ and } x \notin \{0, 1, 2, 5, 26, 677, \dots\} \end{cases}
When reposting, please include the original article address: https://kexue.fm/archives/2951
For more detailed reposting matters, please refer to: Scientific Space FAQ