Georg Cantor

In this post I’d like to illustrate how one can use infinite games to prove theorems about the real numbers.  I’ll begin with a game-theoretic proof that the set of real numbers is uncountable, following the exposition in this paper of mine.  This will lead us somewhat unexpectedly into the realm of descriptive set theory, where we will discuss how games are used in cutting-edge explorations of the Axiom of Choice, the Continuum Hypothesis, and the foundations of second-order arithmetic.   In a sequel post I will discuss how infinite games can be used to study Diophantine approximation, with applications to complex dynamics.

Countable versus uncountable infinities

When my daughter was 5 years old, she asked me if there is just one infinity.  I proudly kissed her on the forehead and told her what an excellent question that was.  I told her no, infinity comes in many different flavors.  I pretty much left it at that, but since she’s 10 now, here are some more details for her.  (The reader familiar with the basics of set theory can move on to the next section.)

Georg Cantor proposed the following fundamental definition:

Two sets and are said to have the same cardinality if it is possible to find a one-to-one correspondence between elements of and elements of .

A one-to-one correspondence

For finite sets, this just means that and have the same number of elements.  However, for infinite sets the notion of cardinality is much harder to grasp.  For example, the set of natural numbers and the set of even natural numbers have the same cardinality, even though the latter is a proper subset of the former!  Indeed, the association gives a one-to-one correspondence between and .  To get a feeling for the “paradoxical” nature of this, consider the Hotel Cantor, which has an infinite number of rooms labeled   Due to a large convention of lawyers, the hotel is completely booked.  Suddenly, a similarly large group of doctors arrives.  The manager, a mathematician, figures out a way to accommodate everyone.  He moves the lawyer in room 1 to room 2, room 2 to room 4, room 3 to room 6, etc. and then fills in the odd-numbered hotel rooms with the doctors.  (Insert your favorite joke here.)

A set is called countable if it has the same cardinality as .  In other words, the elements of can be “counted” 1,2,3, etc.  An infinite set which is not countable is called uncountable.  It is not at all obvious that uncountable sets exist — but they do.  In fact, as Cantor showed, the set of real numbers is uncountable.  What follows is a proof of this fact which — while not suitable for most 5-year-olds — is nevertheless quite simple and (in my opinion) enlightening.

The Cantor game

Alice and Bob decide to play the following game (invented by Grossman and Turett) on the real number line.  A subset of the unit interval is fixed, and then Alice and Bob alternate playing real numbers.  Alice moves first, choosing any real number strictly between 0 and 1.  Bob then chooses any real number strictly between and 1.  On each subsequent turn, the players choose a real number strictly between the previous two choices.  Let (which exists since the sequence is monotonically increasing and bounded above).  Alice wins the game if , and Bob wins if .

If is finite, a moment’s thought shows that Bob has a winning strategy.  We claim that if is countably infinite, then Bob still has a winning strategy.  To see this, enumerate the elements of as   Consider the following strategy for Bob.  On his move, he chooses if this is a legal move (i.e., if ), and otherwise he chooses any allowable number for .  So for each , either or .  We conclude that , and hence Bob wins.

On the other hand, if then clearly Alice wins no matter what either player does.  It follows that (and hence the set of real numbers) is not countable.

A generalization to perfect sets

There is a generalization of this result, and method of proof, to perfect sets.  A subset of is called perfect if it is non-empty and equal to its set of limit points.  In the paper referenced above, I show that if is perfect then Alice has a winning strategy.  The proof is based on the following definition: for a subset of , let denote the set of right limit points of , i.e., those points such that for every , the interval contains an element of .

Exercise 1: If is perfect, show that the infimum (greatest lower bound) of belongs to .

Exercise 2: If is perfect and , then for every the interval contains an element of .

It follows easily from these two facts that if is perfect then Alice can always choose regardless of what Bob does.  Since is closed, and thus Alice has a winning strategy.  We therefore get a game-theoretic proof of the following well-known result in point-set topology:

Every perfect set is uncountable.

An open question

Does one of the two players always have a winning strategy, regardless of which subset of [0,1] we start with?  I don’t know the answer.  However, I suspect that the answer depends on which model of set theory we work with.  This might seem like a bizarre statement to make, but in fact such dependencies abound in modern set theory.  Two prototypes are the Continuum Hypothesis (CH), which asserts that every infinite subset of is either countable or has the cardinality of the reals, and the Axiom of Choice.  Thanks to work of Kurt Gödel and Paul Cohen, we know that there are models of set theory in which these assertions are true, and models in which they are false.

Going back to the Cantor game, it is well-known that Borel subsets of have the perfect set property, meaning that every subset is either countable or contains a perfect set.  (The perfect set property can be thought of as a weak version of the Continuum Hypothesis.)  It follows that the Cantor game is determined (i.e., one of the two players has a winning strategy) whenever is Borel.  On the other hand, it is also known that if we assume the Axiom of Choice then there exist non-Borel subsets of which do not have the perfect set property.  My guess — maybe one of the readers of this blog can prove it — is that if we assume AC then there exist subsets of for which the Cantor game is not determined.  On the other hand, if we assume the Axiom of Determinacy (see the next section) instead of the Axiom of Choice, then I would guess that the game is determined for all subsets of .

Philosophical interlude

One of the primary motivating questions in mathematical logic, ever since the work of Gödel and Cohen, is: “If a statement is neither provable nor refutable under ordinary mathematical assumptions, how do we decide if it is true?”  Perhaps the notion of truth is too elusive and we should not try to settle such questions at all?  But as mathematicians we somehow feel committed to deciding truth.  Perhaps what we really need to decide, then, is which new assumptions are most reasonable.

The Axiom of Choice is accepted as true by most working mathematicians, but it has some severely counterintuituive consequences like the Banach-Tarski paradox (which is related to the existence of sets of reals which are not Lebesgue measurable).  If we don’t like some of the consequences of the Axiom of Choice, why do we assume it?  The main reason is that mathematics loses much structure if we don’t — the Axiom of Choice is used to prove that every vector space has a basis, or that every proper ideal in a commutative ring with identity is contained in a maximal ideal.  And we would like to believe that the “pathologies” which show up in the Banach-Tarski paradox are not relevant in everyday mathematics.  But how to make this precise?

In 1905, Lebesgue asked “Can one name a non-measurable set”?  This led the mathematician Luzin to lay the foundations of what is now called descriptive set theory.  What sets should be considered describable?   A reasonable candidate are those sets of reals which can be built up from intervals using the basic tools of analysis: countable unions, countable intersections, and projections.  More formally, a subset of is called projective if it can be obtained in finitely many steps from a Borel subset of some by applying the basic operations of taking complements and projections (i.e., forgetting certain coordinates).  Every Borel set is projective, but the class of projective sets is much larger.  The projective sets are exactly the sets which are definable (i.e., expressible by a formula) in second-order arithmetic (which unlike first-order arithmetic allows quantification over sets of natural numbers, not just over numbers themselves.)   Thus one can, in a precise sense, think of projective sets as the ones which are “describable”.

Luzin pronounced in 1925 that “one does not know and one will never know” the answer to Lebesgue’s question.  This turned out to be prophetic.  In the 1930’s, Gödel showed that it is consistent with ZFC that there are projective sets which are not Lebesgue measurable.  And in the 1960’s, Solovay used Cohen’s forcing method to show that it is consistent with ZFC that every projective set of reals is Lebesgue measurable.  So in a precise sense, the statements “every describable set of reals is Lebesgue measurable” and “the Continuum Hypothesis is true” are independent of the standard axioms of set theory.  But this does not signal the end of the story.  Modern set theory attempts to resolve such ambiguities by introducing new axioms.  Gödel wrote in 1947 that “[the Continuum Hypothesis] must be either true or false, and its undecidability from the axioms as known today can only mean that these axioms do not contain a complete description of reality.”  He went on to write:

…even disregarding the intrinsic necessity of some new axiom, and even in case it had no intrinsic necessity at all, a decision about its truth is possible in another way, namely, …by studying its “success”… There might exist axioms so abundant in their verifiable consequences, shedding so much light upon a whole discipline, and furnishing such powerful methods for solving given problems… that quite irrespective of their intrinsic necessity they would have to be assumed at least in the same sense as any well established scientific theory.

Determinacy games

Infinite games play a prominent role in modern set theory, in the form of various determinacy axioms.  Fix a subset of , and consider the following infinite game (due to Mycielski and Steinhaus) between Alice and Bob.  Alice begins by playing a binary digit , then Bob plays a binary digit , then Alice plays a binary digit , and so on.  The resulting sequence of moves determines the binary expansion of a real number .   Alice wins if , and Bob wins otherwise.  A famous and difficult theorem of Donald Martin asserts that the game is determined whenever is a Borel set (see this post by Tim Gowers for a detailed discussion of Martin’s theorem).  The Axiom of Determinacy (AD) states that this game is determined for every choice of .

A diagonalization argument shows that the Axiom of Determinacy is inconsistent with the Axiom of Choice.  On the other hand, using AD one can prove many non-trivial theorems about the real numbers which are known to be false assuming the Axiom of Choice, including:

• Every subset of is Lebesgue measurable.
• Every subset of has the perfect set property.

Hugh Woodin

Because AD is inconsistent with AC, and for various other reasons, AD is not usually considered a “reasonable” axiom to take as part of the foundations of mathematics.  However, certain variants of AD are taken quite seriously by logicians.  The most prominent of these is the axiom of projective determinacy (PD), which asserts that our game is determined whenever is a projective set.  The projective determinacy axiom, unlike AD, is not known to be inconsistent with the Axiom of Choice.  Many natural propositions expressible in the language of second order arithmetic are independent of ZFC but are provable from projective determinacy, and it is difficult to find natural statements in second-order arithmetic which are independent of PD.  Moreover, projective determinacy is known to follow from certain large cardinal axioms, such as the existence of infinitely many Woodin cardinals.  For these reasons and others, logicians such as Hugh Woodin believe that the Peano axioms plus PD is the proper foundation for second-order arithmetic.   As Woodin writes in this paper:

Projective Determinacy is the correct axiom for the projective sets; the ZFC axioms are obviously incomplete and, moreover, incomplete in a fundamental way.  Assuming Projective Determinacy, there are no essential uses of the Axiom of Choice in the analysis of [the structure of second-order arithmetic].  The only known examples of unsolvable problems about the projective sets, in the context of Projective Determinacy, are analogous to the known examples of unsolvable problems in number theory: Gödel sentences and consistency statements.

There is a lively debate going on about such things, which the reader can learn more about in this excellent article from Quanta magazine.  It describes how, during a recent meeting at Harvard, scholars largely agreed upon two main contenders for additions to ZFC: forcing axioms and the inner-model axiom “V=ultimate L.”  According to Peter Koellner of Harvard: ““If forcing axioms are right, then the continuum hypothesis is false.  And if the inner-model axiom is right, then the continuum hypothesis is true.”   This is above my pay grade so I will not attempt to say anything intelligent about this debate myself.  But I welcome comments from readers of this blog!

Concluding remarks

1. The infinite game which we used to prove the uncountability of the reals comes from a problem posed by Jerrold Grossman and Barry Turett in the February 1998 Mathematics Magazine.  I came up with the results mentioned above as part of a homework assignment for the students in my Math 25 class at Harvard in Fall 2000.  I published these observations as a short paper in Mathematics Magazine; it was reprinted in the book Mathematical Wizardry for a Gardner.  In the paper, I wrote “This argument is in many ways much simpler than Cantor’s original proof.”  What I had in mind was Georg Cantor‘s famous diagonal argument, but I have since learned that this was not Cantor’s original proof!  An exposition of Cantor’s first proof, which in fact shares much in common with the above argument, can be found in this paper by Knapp and Silva.  Inspired by my game theory proof, they also discuss a different game which ‘encodes’ Cantor’s diagonalization argument.  An alternate exposition of my proof can be found in this blog post.

2. In my discussion of the foundations of set theory, I benefited greatly from Woodin’s paper referenced above as well as from some old notes by Dan Seabold, a former classmate at Berkeley.