Uncountability of the Reals via a Game

The proverbial Alice and Bob play a game. A subset S of the closed unit interval, S⊂[0, 1], plays an important role in the game. So let such a subset be fixed.

Alice moves first, choosing any real a1 in the open interval (0, 1): 0 < a1 < 1. Bob then chooses b1 strictly between a1 and 1: a1 < b1 < 1. On subsequent moves, the players must choose a point strictly between the two most recent choices:

 an-1 < an < bn-1, an < bn < bn-1,

n > 0. Letting a0 = 0 and b0 = 1, the inequalities apply to n ≥ 1.

Since a monotone increasing sequence {an} is bounded from above, it has a limit α = limn→∞an. α is a well defined real number between 0 and 1. Alice wins the game if α ∈ S. Bob wins if α ∉ S.

A set X is countable if there is a mapping from the set of natural numbers onto X. In other words, X is countable if its elements can be sequenced x1, x2, ..., wherein the sequence may or may not be finite. Usually the empty set ø is also considered countable.

Proposition

 If S is countable, Bob has a winning strategy.

Proof

If S = ø, the conclusion is immediate. Otherwise, assuming S countable, let S = {s1, ..., sk, ...}. The winning strategy for Bob is as follows. For n ≥ 1, he chooses bn = sn, if possible. Otherwise, he chooses any legal bn randomly. Due to this strategy, for each n, either sn ≤ an, or sn ≥ bn. Since, for all n, an < α < bn, it follows that α ∉ S, confirming that the strategy is indeed winning for Bob.

Corollary

 The unit interval [0, 1] is uncountable.

Proof

For S = [0, 1], Alice always wins!

(This is quite different from the more common Diagonal Agument, is not it? But why is it called "diagonal"?)

Reference

1. M. H. Baker, Uncountable Sets and Infinite Real Number Game, in Mathematical Wizardry for a Gardner, A K Peters, 2009, see also the free online version. Uncountability of Real Numbers 