Skip to content

Happy St. Patrick Day—Again

March 17, 2010

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 {0}{1}‘s is not countable. Let

\displaystyle  s^{1}, s^{2}, \dots, s^{n}, \dots

be a sequence of infinite sequences. Each {s^{i}} is an infinite sequence; for example,

\displaystyle  00000 \dots 0000 \dots

could be {s^{1}}.

The plan is to use the probabilistic method. Let {X_{1},X_{2},\dots} be an infinite sequence of independent indicator random variables that are {1} with probability {1/2}. Define another sequence of indicator random variables {Y_{1},Y_{2},\dots} as follows: {Y_{i}} is {1} if and only if

\displaystyle  X_{1},\dots,X_{i+1} = s^{i}(1),\dots,s^{i}(i+1).

Then, the expectation {E[Y_{i}]} is equal to {2^{-(i+1)}}. Consider next the infinite sum,

\displaystyle  A = \sum_{i=1}^{\infty} Y_{i}.

By linearity of expectation it follows that

\displaystyle  E[A] = 1/4 + 1/8 + \dots = 1/2.

Thus, there is a sample point so that all the {Y_{i}}‘s are {0}. But, this point must be different from each sequence {s^{i}(1),s^{i}(2),\dots} For suppose that {x_{1},x_{2},\dots} is the sample point. Then, since all {Y_{i}=0} it must follow that

\displaystyle  x_{1},\dots,x_{i+1} \neq s^{i}(1),\dots,s^{i}(i+1).

Open Problems

Have a happy St. Patrick’s Day. By the way is this proof correct or has Neil tricked us?

9 Comments leave one →
  1. March 17, 2010 9:40 am

    Did you forget to show that the Yi are independent?

    • March 17, 2010 11:51 am


      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.

    • March 17, 2010 12:03 pm

      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…

  2. March 17, 2010 10:57 am

    Impressive post this emerald day.

  3. Ralph Hartley permalink
    March 17, 2010 11:45 am

    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?

  4. March 17, 2010 12:32 pm

    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.

    • rjlipton permalink*
      March 17, 2010 8:29 pm

      I will try and check this out.

  5. Picknitter permalink
    March 19, 2010 11:38 pm

    I reprove the unusual use of the word reprove.


  1. Leprechauns Go Universal | Gödel's Lost Letter and P=NP

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s