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 a₁ in the open interval (0, 1): 0 < a₁ < 1. Bob then chooses b₁ strictly between a₁ and 1: a₁ < b₁ < 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 a₀ = 0 and b₀ = 1, the inequalities apply to n ≥ 1.

Since a monotone increasing sequence {a_n} is bounded from above, it has a limit α = lim_n→∞a_n. α 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 x₁, x₂, ..., 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 = {s₁, ..., s_k, ...}. The winning strategy for Bob is as follows. For n ≥ 1, he chooses b_n = s_n, if possible. Otherwise, he chooses any legal b_n randomly. Due to this strategy, for each n, either s_n ≤ a_n, or s_n ≥ b_n. Since, for all n, a_n < α < b_n, 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

• Irrational Numbers: Diagonal Argument with Decimals
• The Diagonal Argument
• Uncountability of the Reals - via a Game
• Cantor's First Uncountability Proof
• The set of all subsets of a given set

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

Copyright © 1996-2018 Alexander Bogomolny