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.
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
Have a happy St. Patrick’s Day. By the way is this proof correct or has Neil tricked us?