III.2 The Axiom of Determinacy
Consider the following “infinite game.” Two players, A and B, take turns to name natural numbers, with A going first, say. By doing this, they generate an infinite sequence. A wins the game if this sequence is “eventually periodic,” and B wins if it is not. (An eventually periodic sequence is one like 1, 56, 4, 5, 8, 3, 5, 8, 3, 5, 8, 3, 5, 8, 3, . . .: that is, one that settles down after a while to a recurring pattern.) It is not hard to see that B has a winning strategy for this game, since eventually periodic sequences are rather special. However, at any stage of the game it is always possible that A will win (if B plays sufficiently badly), since every finite sequence is the beginning of many eventually periodic sequences.
More generally, any collection S of infinite sequences of natural numbers gives rise to an infinite game: A’s object is now to ensure that the sequence produced is one of the sequences in S, and B’s object is to ensure the reverse. The resulting game is called determined if one of the two players has a winning strategy. As we have seen, the game is certainly determined when S is the set of eventually periodic sequences, and indeed for just about any set S that one writes down it is easy to see that the corresponding game is determined. Nevertheless, it turns out that there are games that are not determined. (It is an instructive exercise to see where the plausible-seeming argument, “If A does not have a winning strategy, then A cannot force a win, so B must have a winning strategy,” breaks down.)
It is not too hard to construct nondetermined games, but the constructions use THE AXIOM OF CHOICE [III.1]: roughly speaking, one can well-order all possible strategies so that each one has fewer predecessors than there are infinite sequences, and select sequences to belong to S or its complement in a way that stops each strategy in turn from being a winning strategy for either player.
The axiom of determinacy states that all games are determined. It contradicts the axiom of choice, but it is a rather interesting axiom when it is added to THE ZERMELO-FRAENKEL AXIOMS [III.99] without choice. It turns out, for example, to imply that many sets of reals have surprisingly good properties, such as being Lebesgue measurable. Variants of the axiom of determinacy are closely connected with the theory of large cardinals. For more details, see SET THEORY [IV.22].