## 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 Copyright © 1996-2018 Alexander Bogomolny

68265244