# 9.4 Determinacy Principles Determinacy principles study infinite games between two players, and they assert that for certain classes of games one of the two players has a winning strategy. These principles are important in set theory because they give strong regularity properties for definable sets of reals and provide a deep alternative perspective to the axiom of choice. ### Infinite Games We begin with games of perfect information played by two players, usually called Player I and Player II. A typical game proceeds in infinitely many rounds. At round $0$, Player I chooses a natural number. At round $1$, Player II chooses a natural number. The players continue alternating choices forever. The result is an infinite sequence: $$ x = (x_0,x_1,x_2,\dots) $$ where: $$ x \in \omega^\omega $$ Player I chooses the entries with even indices, and Player II chooses the entries with odd indices. A set: $$ A \subseteq \omega^\omega $$ is fixed in advance. Player I wins the play if: $$ x \in A $$ Player II wins the play if: $$ x \notin A $$ Thus the set $A$ is called the payoff set of the game. ### Definition 9.66 (Game on Natural Numbers) Let: $$ A \subseteq \omega^\omega $$ The game $G_A$ is the infinite two player game in which Player I and Player II alternately choose natural numbers: $$ x_0,x_1,x_2,\dots $$ The resulting sequence is: $$ x \in \omega^\omega $$ Player I wins if: $$ x \in A $$ Player II wins if: $$ x \notin A $$ The game is completely determined by its payoff set $A$. ### Definition 9.67 (Strategy) A strategy for Player I is a function: $$ \sigma : \omega^{<\omega}_{\mathrm{even}} \to \omega $$ which assigns a move to each finite position at which Player I is to move. A strategy for Player II is a function: $$ \tau : \omega^{<\omega}_{\mathrm{odd}} \to \omega $$ which assigns a move to each finite position at which Player II is to move. Here $\omega^{<\omega}$ denotes the set of all finite sequences of natural numbers, and the subscripts indicate positions of even or odd length depending on whose turn it is. A strategy is a complete rule for playing the game. It tells a player what to do after every possible finite history of play. ### Definition 9.68 (Winning Strategy) A strategy $\sigma$ for Player I is winning in $G_A$ if every play following $\sigma$ produces a sequence: $$ x \in A $$ A strategy $\tau$ for Player II is winning in $G_A$ if every play following $\tau$ produces a sequence: $$ x \notin A $$ Thus a winning strategy guarantees victory no matter how the other player responds. ### Definition 9.69 (Determined Game) The game $G_A$ is determined if either Player I has a winning strategy or Player II has a winning strategy. The set $A$ is called determined if the corresponding game $G_A$ is determined. Determinacy is a strong assertion because it says that every game in a given class has a completely winning plan for one of the two players. ### Example 9.70 Let: $$ A = \omega^\omega $$ Then Player I wins every play, because every resulting sequence belongs to $A$. Therefore any strategy for Player I is a winning strategy. Let: $$ A = \varnothing $$ Then Player II wins every play, because no resulting sequence belongs to $A$. Therefore any strategy for Player II is a winning strategy. ### Example 9.71 Let: $$ A = \{x \in \omega^\omega : x_0 = 0\} $$ This is the set of sequences whose first entry is $0$. Player I has a winning strategy. On the first move, Player I plays: $$ 0 $$ After that, the rest of the play does not matter, because membership in $A$ is already decided by the first move. Thus $G_A$ is determined. ### Example 9.72 Let: $$ A = \{x \in \omega^\omega : x_1 = 0\} $$ This is the set of sequences whose second entry is $0$. Player II controls the second entry. If Player II plays: $$ 0 $$ on the first response, then the resulting sequence belongs to $A$. Since Player I wins when the sequence belongs to $A$, this means Player II should avoid playing $0$. Player II can instead always play: $$ 1 $$ on the first response. Then: $$ x_1 \neq 0 $$ so: $$ x \notin A $$ Thus Player II has a winning strategy. ### Open Games A set: $$ A \subseteq \omega^\omega $$ is open if membership in $A$ can be verified after seeing only a finite initial segment of the sequence. Equivalently, $A$ is open if whenever $x \in A$, there is a finite initial segment: $$ s = x{\upharpoonright}n $$ such that every sequence extending $s$ also belongs to $A$. For games, this means that if Player I wins, then there is some finite stage at which the win has already become inevitable. ### Theorem 9.73 (Gale Stewart Theorem for Open Games) If: $$ A \subseteq \omega^\omega $$ is open, then the game $G_A$ is determined. Proof We prove that either Player I can force the play into $A$, or Player II can avoid $A$ forever. Call a finite position $s \in \omega^{<\omega}$ winning for Player I if Player I has a strategy from position $s$ that guarantees that the final infinite sequence belongs to $A$. If the empty position is winning for Player I, then Player I has a winning strategy in the original game, and the proof is complete. Suppose instead that the empty position is not winning for Player I. We show that Player II has a winning strategy. At any position where Player II is to move, Player II chooses a move that keeps the position not winning for Player I. Such a move must exist. If every possible move by Player II led to a position winning for Player I, then Player I would already have a winning strategy from the previous position, because no matter how Player II moved, Player I could then follow the corresponding winning strategy. This would contradict the assumption that the previous position was not winning for Player I. Thus Player II can maintain the invariant that after each of Player II's moves, the current finite position is not winning for Player I. Now consider any infinite play following this strategy for Player II. Suppose, toward a contradiction, that the resulting sequence: $$ x $$ belongs to $A$. Since $A$ is open, there is some finite initial segment: $$ x{\upharpoonright}n $$ such that every extension of this segment belongs to $A$. From this finite position, Player I trivially has a winning strategy, because the play is already forced into $A$ no matter what happens later. Thus: $$ x{\upharpoonright}n $$ is winning for Player I. But this contradicts the way Player II maintained positions from which Player I is not winning. Therefore the resulting sequence is not in $A$, and Player II wins. Hence $G_A$ is determined. ### Closed Games A set: $$ A \subseteq \omega^\omega $$ is closed if its complement is open. In the game $G_A$, if $A$ is closed, then Player II's winning condition is open, because Player II wins when the play is outside $A$. Therefore the theorem for open games also gives determinacy for closed games. ### Corollary 9.74 (Closed Determinacy) If: $$ A \subseteq \omega^\omega $$ is closed, then $G_A$ is determined. Proof If $A$ is closed, then: $$ \omega^\omega \setminus A $$ is open. The game $G_A$ gives Player II the payoff: $$ \omega^\omega \setminus A $$ By Theorem 9.73, the open payoff game for Player II is determined. Therefore either Player I can force the play into $A$, or Player II can force the play into its complement. Hence $G_A$ is determined. ### Borel Determinacy The open and closed cases are the first steps in a much stronger theorem. Borel determinacy says that every game whose payoff set is Borel is determined. This is a deep theorem because Borel sets are built from open sets by iterating complements and countable unions through countable stages, and the proof must show that determinacy survives this full construction. ### Theorem 9.75 (Martin's Borel Determinacy Theorem) If: $$ A \subseteq \omega^\omega $$ is Borel, then the game $G_A$ is determined. Proof We give the main structure of the proof rather than all technical details, since the full proof requires a careful induction through the Borel hierarchy. The proof proceeds by induction on the Borel rank of the payoff set. For open sets, determinacy is Theorem 9.73. For closed sets, determinacy follows from open determinacy by taking complements. For higher Borel sets, one analyzes how a payoff set is built from simpler payoff sets using countable unions and complements. The main difficulty is countable union. Suppose: $$ A = \bigcup_{n<\omega} A_n $$ where each $A_n$ has lower Borel rank. Player I wins if the resulting play belongs to at least one $A_n$. The proof introduces auxiliary games in which a player must not only play the original game but also provide information about which component $A_n$ is being targeted. These auxiliary games reduce determinacy of the union to determinacy of lower rank sets. The complement step swaps the roles of the players, because if Player I wins for $A$, then Player II wins for the complement, and conversely. By carrying this induction through all countable Borel ranks, one obtains determinacy for every Borel payoff set. Thus every Borel game is determined. ### Axiom of Determinacy The axiom of determinacy extends the conclusion of Borel determinacy from Borel payoff sets to all subsets of Baire space. ### Definition 9.76 (Axiom of Determinacy) The axiom of determinacy, abbreviated: $$ \mathrm{AD} $$ is the statement that for every set: $$ A \subseteq \omega^\omega $$ the game $G_A$ is determined. Equivalently, every infinite game of perfect information on natural numbers has a winning strategy for one of the two players. ### Conflict with the Axiom of Choice The axiom of determinacy is incompatible with the full axiom of choice. The reason is that choice allows the construction of highly nondefinable sets of reals whose associated games are not determined. Thus: $$ \mathrm{AD} $$ cannot be added to ZFC. Instead, determinacy is usually studied in theories such as: $$ \mathrm{ZF} + \mathrm{AD} $$ or in restricted forms compatible with ZFC, such as projective determinacy. ### Theorem 9.77 The axiom of determinacy implies that every set of reals has the perfect set property, the Baire property, and is Lebesgue measurable. Proof We explain the main ideas for each regularity property. For the perfect set property, one associates to a set of reals $A$ a game in which the players build a real number. The strategies for the players determine whether $A$ is countable or whether one can build a perfect tree of distinct elements of $A$. If Player I has enough control, one obtains a perfect subset of $A$. If Player II has the corresponding control, one shows that $A$ is countable or otherwise small in the required sense. For the Baire property, one uses a game in which players choose smaller and smaller basic open neighborhoods. Determinacy implies that one player has a winning strategy, and this strategy provides an open set approximating $A$ modulo a meager error. For Lebesgue measurability, one uses measure theoretic games where players choose intervals or finite approximations to real numbers. A winning strategy prevents the existence of nonmeasurable behavior, and the resulting argument shows that $A$ satisfies the Caratheodory criterion for measurability. The common idea is that a winning strategy gives definable control over the set, and this control rules out the pathological sets that choice can produce. ### Projective Determinacy Since full determinacy contradicts the axiom of choice, set theorists often study restricted determinacy principles. The most important restricted principle is projective determinacy. ### Definition 9.78 (Projective Determinacy) Projective determinacy, abbreviated: $$ \mathrm{PD} $$ is the statement that every projective subset of: $$ \omega^\omega $$ is determined. That is, if $A$ belongs to the projective hierarchy, then the game $G_A$ is determined. Projective determinacy is compatible with ZFC relative to large cardinal assumptions, and it has strong consequences for definable sets of reals. ### Theorem 9.79 Projective determinacy implies that every projective set of reals has the perfect set property, the Baire property, and is Lebesgue measurable. Proof This follows by applying the regularity arguments from determinacy only to projective payoff sets. If $A$ is projective, then the games used to analyze the perfect set property, the Baire property, and Lebesgue measurability can be arranged to have projective payoff sets. By projective determinacy, those games are determined. The winning strategies then yield the same regularity conclusions as in the proof under full determinacy. Thus every projective set has the regularity properties. ### Analytic Determinacy Analytic determinacy is the statement that every analytic game is determined. This principle is stronger than Borel determinacy because analytic sets may fail to be Borel. ### Theorem 9.80 (Martin) If there exists a measurable cardinal, then every analytic game is determined. Proof We give the central idea. Let: $$ A \subseteq \omega^\omega $$ be analytic. Then there is a tree: $$ T $$ such that: $$ x \in A $$ if and only if there exists an infinite branch through a tree determined by $x$ and $T$. The existence of a measurable cardinal provides a countably complete ultrafilter, and this ultrafilter can be used to compare possible ranks and strategies associated with attempts to avoid or enter the analytic set. The proof converts the analytic payoff into a well founded or ill founded tree problem and then uses the measure to choose coherent information through many possible branches. This produces a winning strategy for one of the players. Thus measurable cardinals imply analytic determinacy. ### Determinacy and Large Cardinals Determinacy principles and large cardinal axioms are closely connected. Borel determinacy is provable in ZFC. Analytic determinacy follows from a measurable cardinal. Projective determinacy follows from stronger large cardinal assumptions, such as the existence of sufficiently many Woodin cardinals. In one direction, large cardinals provide the consistency strength needed to prove determinacy for increasingly complex definable sets. In the other direction, determinacy principles imply strong structural consequences for inner models and definable sets of reals. ### Games and Definability The importance of determinacy comes from the fact that many mathematical properties can be coded as games. A set of reals often represents a classification problem, a definability condition, or a collection of mathematical structures. If the associated game is determined, then one player has a strategy that explains the structure of the set. Thus determinacy transforms questions about arbitrary membership in a set into questions about strategies, and strategies are often more structured and more analyzable than arbitrary sets. ### Comparison with Choice The axiom of choice says that arbitrary selections can be made from arbitrary families of nonempty sets. Determinacy says that arbitrary infinite games have winning strategies. These principles pull in opposite directions. Choice permits the construction of pathological sets of reals. Determinacy prevents such pathology by forcing every set of reals to have regular behavior. For this reason, determinacy is not used as a replacement for ZFC in ordinary mathematics, but it is a powerful alternative principle for studying definable sets of reals and the structure of the continuum.