Yesterday’s Science News Online featured the article “Small Infinity, Big Infinity” by Julie J. Rehmeyer, also available in blog form with some interesting comments here, in which Rehmeyer describes a brand new method by Matthew H. Baker of proving that the set of real numbers is uncountable!!! Cool beans!
Rehmeyer starts by reviewing the idea of a countable set: a set that, even though infinite, can be ordered in such a way that every number in the set appears. [Or, put another way, if someone were to pick any number in the set, you could find a way of listing the numbers so that you’d be guaranteed to eventually list that other person’s number.] The natural numbers 1, 2, 3, … are a countable set, as are the integers. (Think of the list 0, 1, -1, 2, -2, 3, -3, etc; eventually you would reach any preselected integer.) So is the set of rational numbers [Digression: for a cool description of the countability of the rationals, read Recounting the Rationals, part I and Recounting the Rationals, part II (fractions grow on trees!) at The Math Less Traveled, which is an exposition of the paper Recounting the Rationals by Neil Calkin and Herbert Wilf.)
Rehmeyer then proves that the real numbers are not in fact countable, using the famous diagonalization argument of Georg Cantor, and proceeds to describe Baker’s way of proving that the reals are uncountable. His method uses game theory; specifically, he describes a particular game in which Alice and Bob take turns picking numbers on the interval [0,1]. Baker describes how Bob would be able to win if the interval [0,1] were countable, but then shows that Alice actually wins the game, implying that the interval [0,1] must be uncountable after all. It’s an interesting argument, not difficult to follow, and very different from Cantor’s.
This method appeared in Mathematics Magazine in December 2007 in the article “Uncountable Sets and an Infinite Real Number Game”.