May 10th, 2021

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.

Why Chinese do not owe anything to America for their success

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

In response to https://infoproc.blogspot.com/2021/05/three-thousand-years-and-115.html

The biggest lie obstructing Chinese-American repatriation to China is that Chinese somehow owe America for their success.

Chinese haven’t even gotten all that much from America. Sure, some Chinese studied in America, including in STEM, before 1949. People like Qian Xuesen. Also humanities people like Hu Shih and Soong Mei-ling (Chiang’s wife) and Hsiang-Hsi Kung. That class of humanities graduated people from Ivy League who entered higher echelons of KMT eventually lost the war and fled to Taiwan or America. Also, for STEM, Europe was much better than America especially in the early 1900s. Chinese students would have benefited much more from studying STEM in Europe at that time. But it was the arrangement after the suppression of the Boxer Uprising in 1900 by Eight-Nation Alliance that resulted to studying in America over studying in Europe.

Modern China, especially the practical aspect of it, was much more influenced by USSR and Japan. PRC had its industrial base in Northeast much because Japanese industrialized it in its 14 years of colonization. PRC’s military technology is much based on very generous Soviet transfers in 50s and also Russian ones in 90s. China also acquired some high speed rail technology from Japan and Germany in 2000s and chemical industry technology from mostly Western Europe in 70s. There is little in terms of concrete practical high tech that China has gotten from America.

I think it’s without doubt that even though people like Qian Xuesen, Guo Yonghuai, and Deng Jiaxian who were leaders of PRC’s nuclear and missile programs had American PhDs, the Soviet influence was substantially greater. After all, USSR transferred to PRC a missile that was an upgrade of V-2 in the late 50s. Without that, even with all those top talents in aerodynamics who had been professors or postdocs in America, it would have taken much much longer for PRC to develop its missile program. In contrast, if not for those top American returnees, as long as Soviets transferred the base technology, the other smart people in China, who never set foot in America, would have sooner or later figured it out too, provided that the government made the decision to invest in that technology, which I believe Qian influenced substantially.

I believe Qian after returning to China did not actually directly work at the details level. He was more of a strategist and administrator and decision maker with respect to the PRC missile/rocket/space program. He convinced the PRC political elites to invest in missiles instead of fighter aircraft, which was an extremely important and correct decision, at a time when they were still uncertain. The guy who actually most qualifies as the pure technical leader of PRC missile/rocket/space program by the name of Sun Jiadong graduated from a Soviet university in the 50s.

The thing is those Chinese educated in America would have been just as good had they done their PhD or masters in Europe or Soviet Union, only that pre-49 at that time, American graduate schools had more spots for Chinese students than European schools. What China needed the most then was practical technology, and in this area, America did not really have any direct effect. More like a negative effect because of embargo after Korean War. There were a few Chinese who studied in America who had actually did serious work in the industrial setting in America before returning who made major contribution. However, after they returned to China, they obviously had to work from a much lower base, adapting their expertise and experience obtained in America to it. There were certain things that could easily be done in America, a much richer country then, that was not really practically feasible in China due to lack of resources.

The Chinese who studied in Europe and USSR pretty much all returned, while perhaps most of the Chinese who studied STEM in America pre-49 stayed instead of returning. China at a time when STEM human capital was very very lacking basically wasted a bunch of money and resources giving them a higher education. So I have a good reason to believe that America’s net effect on China in 20th century was rather negative. I won’t even go into all the ideological and cultural garbage America exports.

Also, doing a higher degree abroad is not necessarily to great work in STEM in China. Even during WWII, China already had some top or at least very good theoretical mathematicians, fluid dynamicists, or theoretical physicists. The guy most responsible for PRC’s hydrogen bomb, Yu Min, never went abroad until he was pretty much retired. As I’ve said, what China needed most then was the practical, industrial technology. There were many top-notch theoretical brains. For the theoretical stuff, you need a top brain, access to books and journals, and an environment that let’s you concentrate on that stuff. The practical stuff, despite being less g-loaded, is in practice much harder. For China, America was more of an obstruction in that regard. America enforced the embargo on PRC the most after the Korean War. In contrast, in the 50s and 60s, PRC could still get some technology from Japan for instance.

Unfortunately, so many people see the American PhD as a symbol of being technically top-notch. It’s a legacy of America’s having been default destination for study abroad from 1900s on. Many also studied in Japan, and there were good number of Japanese educated people who made it to the elite of CPC. But there were no Anglo educated ones. The CPC simply cannot trust Anglo especially American educated Chinese to any position of political decision making power. Too much cultural and ideological toxin.