Sheng Li (gmachine1729) wrote,
Sheng Li

My partially successful attempt at proving the Cantor-Schroder-Bernstein theorem

Originally published at 狗和留美者不得入内. You can comment here or there.

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

[公式]which implies

[公式] 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.

Tags: uncategorized

  • 中国少数民族的语系分类

    汉藏语系 汉族:汉语族,12.2 亿 壮族:壮侗语族,1690 万,主要在广西 彝族:彝语支,870 万,主要在西南 土家族:840 万,主要在湖南,湖北,贵州 藏族:藏缅语族,630 万,主要在西藏 侗族 布衣族 白族 哈尼族 黎族 傣族…

  • 中国那帮英语培训机构基本都是垃圾,他们的创办人及工作者应当被处置

    刚跟朋友说了国庆放假,我在健身房,碰到了一个俄罗斯姑娘和个三十出头的中国女人一起。我跟她用俄语稍微聊了几句,也加了她和她的中国同事微信。然后,我得知她们是在培训班教小学生英语的。俄罗斯姑娘跟我说她在俄罗斯的 Перм 上大学,专业是德语,现在在中国已经待了一年了。…

  • 拼音英语字符比对服务

    我和朋友做了一个汉字转拼音的服务。什么给了我这个启发?是他有一次想让我在微信上用英语,可是我不想,因为觉得中文更快。然后自己做了个 小试验。 >>>…

  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened