Happy St. Patrick Day—Again
A proof of the famous Cantor Theorem
Neil L. is not a computer scientist–he is a Leprechaun. Since today is St. Patrick’s Day it seems right to talk about him again. As long as you look at him he cannot escape, but the moment you look away, he vanishes.
Magic.
I want to present a proof of Cantor’s famous Theorem: the set of all infinite sequences of 
be a sequence of infinite sequences. Each 
could be 
The plan is to use the probabilistic method. Let 
Then, the expectation ![{E[Y_{i}]}](https://s0.wp.com/latex.php?latex=%7BE%5BY_%7Bi%7D%5D%7D&bg=ffffff&fg=228b22&s=0 "{E[Y_{i}]}")
By linearity of expectation it follows that
![\displaystyle E[A] = 1/4 + 1/8 + \dots = 1/2.](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle++E%5BA%5D+%3D+1%2F4+%2B+1%2F8+%2B+%5Cdots+%3D+1%2F2.+&bg=ffffff&fg=228b22&s=0 "\displaystyle E[A] = 1/4 + 1/8 + \dots = 1/2.")
Thus, there is a sample point so that all the 
Open Problems
Have a happy St. Patrick’s Day. By the way is this proof correct or has Neil tricked us?
Did you forget to show that the Yi are independent?
Nemo,
Love pic. No. They are not independent. But E[A+B] = E[A] + E[B] whether independent or not. That is the beauty of expectation.
Whoops; never mind. Linearity of expectation holds for non-independent events.
But something is still bothering me about that infinite sum. For some X, it diverges…
Impressive post this emerald day.
I’m not sure I would be convinced by this argument if I didn’t already know Cantor’s Theorem.
The problem is that you don’t reprove all the theorems of probability theory that you use. Without that, how do I know that none of the proofs depend on the uncountably of the reals?
Using probability theory to prove Cantor’s Theorem is like turning wine into water. It may be an interesting trick, but didn’t you need water to grow the grapes?
I’m mostly with Ralph Hartley, but to me the issues are more of “Reverse Mathematics”—any followers of Harvey Friedman at the ASL meeting? The question is whether the deduction of a sample point such that all Y_i’s are 0 depends on infinitistic facts about Lebesgue measure, which in turn depend on Cantor. The argument is based on the binary tree of sequences rather than the reals, so the basic open sets (corresponding to each node) are truly finitistic. The question IMHO is whether that’s enough of a foundation for proving that the leprechaun cannot have led us into a “Tarski World” of non-measurable sets that can make a part seem to equal the whole.
I will try and check this out.
I reprove the unusual use of the word reprove.