Today, I may well have learned for the first time the proof of Cantor’s theorem, which states that there is no bijection between a set and its power set for any set. Since mapping each element to its singleton set trivially generates an injection. This means that for any set , , where the cardinality operator defined on the universe of sets, with its codomain being the set of cardinal numbers.
Cantor’s theorem (Theorem 1): For any set , there exists no surjection from it to its power set.
Proof: Assume that there is a surjection , and let be defined as , which of course must exist uniquely. One notices that and that more generally . Moreover, if , . Thus, , which is a contradiction.
Afterwards, I was reminded of the Cantor-Schroder-Bernstein theorem, which I had learned before, which I tried to re-prove myself. I’ll talk a bit about the process I took to solve it, having been not able to immediately think of the right approach without a hint.
The statement of the theorem is as follows.
Cantor-Schroder-Bernstein theorem (Theorem 2): If there exists an injection and injection , then there exists a bijection between and or equivalently, .
In attempt to prove this, I thought directly in terms of the injections, noticing also the symmetry with respect to , by which I mean that the theorem’s proposition is invariant with respect to the swap of the two sets.
This is obviously a bijection between and and also and
Immediately, one gets
For any two disjoint sets , we have the cardinalities . It is natural to define on space of cardinals an operator such that . We moreover can reasonably stipulate that if for any such that , then, . This is consistent with the definition of cardinality since one can directly construct a bijection from to off our bijections between and and between and respectively which exist by definition of cardinality. I thus implicitly though of the following proposition.
Proposition 1 If for and , then .
In the case of all finite cardinalities this is obvious, and in fact, we do not even need the hypothesis of . We do of course need it in general. As one can union with two sets of different finite cardinality to obtain two distinct sets both with cardinality equal to .
There is another intuitively true or “obvious” proposition that is much useful though, which I try to prove and failed to, after which I thought of possibly regarding it as an axiom.
Proposition 2 If and , then .
In attempt to prove this, I tried in vain to prove the more general statement that if there exists between two sets both an injective and a surjective function, there must exist a bijection between the two, trying to use Zorn’s lemma in the process.
Of course, before I tried to prove this, I had already noticed that since an injective function on a domain when restricted to any subdomain remains injective, one tells us that . With and , Proposition 2 would give us the desired .
In the process I suspected that it would be pretty must impossible to explicitly construct a bijection. I tried to construct one between and to no success of course.
Though I was mostly still dissatisfied, I did make some non-neglible progress, and I decided to take a sneak peak on one of the first chapters in Folland’s analysis book, from which I had likely first learned of this theorem. I saw in the proof the name of a set with in its subscript as well as the word “terminate”. Then, it immediately occured to me to think in terms of zig-zags between and via and , along with the realization that there a set of points in for which the zig-zag does not cycle with finite period and never terminates. After this, I figured out the proof without difficulty. The details of it will be written below.
Proof (of Cantor-Schroder-Bernstein theorem): One notices that any point in or in , either cycles with finite, even period, or it continues indefinitely, reaching a point never reached after each application of or of . A point not included in the points of the cycle can never reach that cycle, because with being injective in mind, each point in the cycle is already directly reached in one step by another point in the cycle.
One realizes that here, one can move forward one step by applying or , or maybe move backwards by applying or . For any points , (or ) is either the empty set or a singleton set. In points or which belong to finite cycles necessarily even, one can start at an arbitrary in the cycle and associate it with . One return to a point in via and repeats the procedure until all the points in the cycle are traversed. After doing this for all points that are part of a finite cycle, the remaining points are all ones which “never terminate” when the “move forward” algorithm is run on it.
For the remaining points, either running the “move backward” algorithm on it terminates or it doesn’t. There is moreover a subset of those remaining points on which “move backward” cannot be run (the preimage of that point is empty set). For the points for which “move backward” terminates, it either terminates in a point in or it does so in a point in . In the former case, we would associate such point with if it is in or with if it is in . Doing so covers all the points for which the “move backward” algorithm terminates.
Finally, we have points not part of finite cycles which terminate neither under “move forward” nor under “move backward”. In this case, we simply associate every such point in with .
We have partitioned all points in and in into three classes 1) those part of finite cycles 2) those which can never reach a point in a finite cycle for which “move backward” will terminate at a point with empty preimage 3) those which can never reach a point in a finite cycle for which neither “move forward” nor “move backward” terminates. For each of these cases, we have matched together points in with those in such that every point is matched with exactly one point, covering all points. This proves the existence of a bijection between and and thus that .
After figuring this out, I read a bit about the historical background of this theorem on Wikipedia, which I shall summarize based on my possibly imperfect memory. I learned that Cantor, despite stating and publishing it, did so without proof. Then, Schroder gave for it a proof which was wrong. After that, Dedekind, despite his not having his name associated with it, proved it via Proposition 2. Afterwards, Bernstein as a high school or university student helped Cantor prove it fully and rigorously. Following that, Dedekind proved it once again, and it was realized that Schroder’s arguments, which did not fully qualify as a proof, could be patched up without much difficulty. The idea behind the proof that I gave seems to be attributed to Konig, which makes me wonder how Bernstein actually proved the theorem.
Maybe if I have sufficient time and interest, I’ll eventually learn about Zermelo-Fraenkel set theory and transfinite cardinals and all that logic and foundations of mathematics in serious depth, maybe even learning the proofs of Godel’s incompeteness theorems in the process. This stuff is of course extremely interesting; I only hesitate to learn it due to its utter lack of practically, and associated with that, existence of matters of higher priority. I like to say that among pure mathematicians and theoretical physicists, I am almost certainly one of a more pragmatic or realistic mindset. Though I love math and theoretical physics, I don’t quite like the cult-like culture that often exists in these fields in academia.