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 –
‘s is not countable. Let
be a sequence of infinite sequences. Each is an infinite sequence; for example,
could be .
The plan is to use the probabilistic method. Let be an infinite sequence of independent indicator random variables that are
with probability
. Define another sequence of indicator random variables
as follows:
is
if and only if
Then, the expectation is equal to
. Consider next the infinite sum,
By linearity of expectation it follows that
Thus, there is a sample point so that all the ‘s are
. But, this point must be different from each sequence
For suppose that
is the sample point. Then, since all
it must follow that
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.