Thursday, June 15, 2006

Here's a slick new proof that the reals are uncountable.
Alice and Bob decide to play the following infinite game on the real number line. A subset S of the unit interval [0,1] is fixed, and then Alice and Bob alternate playing real numbers. Alice moves first, choosing any real number a_1 strictly between 0 and 1. Bob then chooses any real number b_1 strictly between a_1 and 1. On each subsequent turn, the players must choose a point strictly between the previous two choices. Equivalently, if we let a_0 = 0 and b_0 = 1, then in round n, for n at least 1, Alice chooses a real number a_n with a_{n-1} < a_n < b_{n-1}, and then Bob chooses a real number b_n with a_n < b_n < b_{n-1}. Since a monotonically increasing sequence of real numbers which is bounded above has a limit (see [8, Theorem 3.14]), the limit alpha of a_1, a_2, a_3,... is a well-defined real number between 0 and 1. Alice wins the game if alpha is in S, and Bob wins if alpha is not in S.
It's pretty easy to check that if S is countable, meaning we can list S as {s_1, s_2, s_3,...}, then there's a strategy for Bob that will guarantee him victory. (Bob plays b_n=s_n whenever it's legal; otherwise he plays randomly.) On the other hand, if S is all of [0, 1], then Alice wins no matter how she and Bob play. Therefore, [0, 1] is uncountable.

1 Comments:

Blogger Vader said...

I'm still having a tough time deciding whether I believe in non-computable numbers.

6/16/2006 4:20 PM  

Post a Comment

<< Home