## Uncountability of the Reals

via a Game

The proverbial Alice and Bob play a game. A subset S of the closed unit interval,

Alice moves first, choosing any real a_{1} in the open interval _{1} < 1._{1} strictly between a_{1} and 1: _{1} < b_{1} < 1.

a_{n-1} < a_{n} < b_{n-1}, | |

a_{n} < b_{n} < b_{n-1}, |

n > 0. Letting a_{0} = 0 and b_{0} = 1, the inequalities apply to n ≥ 1.

Since a monotone increasing sequence {a_{n}} is bounded from above, it has a limit _{n→∞}a_{n}.

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 x_{1}, x_{2}, ..., 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 _{1}, ..., s_{k}, ...}._{n} = s_{n},_{n} randomly. Due to this strategy, for each n, either _{n} ≤ a_{n},_{n} ≥ b_{n}._{n} < α < b_{n},

### 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

- 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.

|Contact| |Front page| |Contents| |Algebra| |Geometry| |Up|

Copyright © 1996-2018 Alexander Bogomolny