Fact-checked by Grok 2 weeks ago

Determinacy

In , particularly in the context of descriptive set theory and of mathematics, (AD) asserts that every subset of the \omega^\omega (the space of infinite sequences of natural numbers) defines a determined two-player game of , meaning that for any such payoff set A \subseteq \omega^\omega, one of the players—either player I or player II—possesses a winning strategy in the associated Gale-Stewart game, regardless of the opponent's moves. Proposed in 1962 by mathematicians Jan Mycielski and Hugo Steinhaus, AD emerged as a response to pathological phenomena arising from the (), such as the existence of non-measurable sets of reals and sets without the property of Baire. Unlike , which allows for arbitrary selections from families of sets, AD imposes a form of regularity on infinite games and is inconsistent with within the framework of Zermelo-Fraenkel with choice (ZFC); however, AD is consistent with Zermelo-Fraenkel without choice (ZF). Early work by Mycielski and others demonstrated that AD yields constructive alternatives to AC-dependent results, particularly in and . One of the most significant implications of AD is that it resolves longstanding problems in by ensuring that all subsets of the real numbers exhibit classical regularity properties: every set of reals is Lebesgue measurable, has the property of Baire, satisfies the perfect set theorem (i.e., is either countable or contains a perfect subset), and admits a uniformization. These consequences extend to projective determinacy (), a weaker axiom asserting determinacy for projective sets, which follows from the existence of large cardinals and has been pivotal in advancing the structural theory of the projective hierarchy. In modern set theory, AD occupies a central position in the study of inner models and forcing axioms, with its consistency relative to ZF established through connections to large cardinal hypotheses, such as the existence of infinitely many Woodin cardinals, which imply AD in the inner model L(\mathbb{R}) (the smallest inner model containing all reals and ordinals). Key results by Donald A. Martin and John R. Steel in the 1980s and 1990s linked AD to measurable cardinals and hod mice, providing a robust framework for understanding determinacy's role in the universe of sets beyond ZFC.

Basic Concepts in Infinite Games

Gale-Stewart Games

Gale-Stewart games are infinite two-player games of played on sequences from a nonempty set A, typically the natural numbers \omega. In such a game, denoted G(A, E) where E \subseteq A^\omega is the payoff set, Player I and Player II alternate making moves by selecting elements from A, starting with Player I. The sequence of moves produces an infinite play x = (x_0, x_1, x_2, \dots) \in A^\omega, known as the when A = \omega. Player I wins if the resulting x \in E, while Player II wins if x \notin E. These games are of length \omega, meaning they continue for countably infinitely many turns without a predetermined end. Each player has , as every move is public and all previous choices are known to both players before their next turn. This setup ensures that the game tree is a full of \omega when A is countable, with no hidden actions or chance elements. The framework captures the essence of strategic decision-making over infinite horizons, central to the study of determinacy in . Gale-Stewart games were introduced by David Gale and F. M. Stewart in their 1953 paper, which formalized infinite games of and proved determinacy for payoff sets that are open or closed in the . This foundational work established the model for analyzing determinacy, where the question is whether one player has a winning strategy regardless of the opponent's play.

Strategies and Determinacy

In the context of Gale-Stewart games, players employ strategies to dictate their moves based on the game's history. A strategy for Player I is a function \sigma: \bigcup_{n<\omega} \omega^{2n} \to \omega, where for any finite history y \in \omega^{2n} consisting of the previous n moves by each player, \sigma(y) specifies Player I's next move in \omega. Similarly, a strategy for Player II is a function \tau: \bigcup_{n<\omega} \omega^{2n+1} \to \omega, defined on histories of odd length, where \tau(y) determines Player II's response to the sequence of moves up to that point. A winning strategy for Player I in a game with payoff set A \subseteq \omega^\omega is a strategy \sigma such that every infinite run x \in \omega^\omega consistent with \sigma—meaning x interleaves moves dictated by \sigma and arbitrary opponent responses—belongs to A. For Player II, a winning strategy \tau ensures that every run consistent with \tau lies in the complement of A. These strategies formalize optimal play, guaranteeing a win irrespective of the opponent's choices. A Gale-Stewart game is determined if either Player I or Player II possesses a winning strategy; notably, both cannot simultaneously have winning strategies, analogous to Zermelo's theorem for finite games of . In contrast, undetermined games exist where neither player has a winning strategy, and their construction relies on the to select payoff sets A that evade determinacy for both players.

Examples of Determined and Undetermined Games

In Gale-Stewart games of length \omega on the natural numbers, where Player I wins if the resulting infinite sequence belongs to a given payoff set A \subseteq \omega^\omega, open payoff sets are always determined. The proof proceeds by on the game tree, classifying each position as a winning position for one player or the other based on the openness of the set. Dually, closed payoff sets are also determined, with the proof following similarly by considering the structure of closed sets in the . The Banach-Mazur game provides another concrete example of determinacy in a topological setting. Played on a X, the two players alternately choose nonempty s with diameters tending to zero, and Player II wins if the of these sets lies in a target set B \subseteq X. If B is comeager (, i.e., its complement is meager), Player II has a winning strategy, which exploits the of B to always select a basic intersecting B non-meagerly. The () implies the existence of undetermined games, demonstrating that determinacy does not hold for all payoff sets in ZFC. Using to well-order the reals (or \omega^\omega), one enumerates all possible strategies for both players in type and constructs a payoff set A by : for each strategy \sigma of Player I (in order), ensure some play following \sigma lands outside A; similarly for Player II's strategies, ensuring some play following it lands in A. This A admits no winning strategy for either player, as every strategy is defeated by the construction.

Proofs of Determinacy in ZFC

Borel Determinacy

Borel sets form a fundamental class in descriptive set theory, consisting of the smallest on a , such as the \omega^\omega, that contains all open sets. The classifies these sets by complexity levels: the class \Sigma^0_1 comprises the open sets, while \Pi^0_1 consists of the closed sets; for n \geq 2, \Sigma^0_n is the collection of countable unions of sets from \Pi^0_{n-1}, \Pi^0_n is the class of complements of \Sigma^0_n sets, and \Delta^0_n = \Sigma^0_n \cap \Pi^0_n. The entire Borel is the union of all \Delta^0_n over finite n, though more refined hierarchies extend to countable ordinals \alpha, with \Sigma^0_\alpha, \Pi^0_\alpha, and \Delta^0_\alpha defined analogously via . In 1975, Donald A. Martin established the Borel determinacy theorem, proving that every Gale-Stewart game on \omega^\omega with a Borel payoff set A is determined, meaning one of the two players has a in . This result marked the first non-trivial extension of determinacy beyond the open and closed games, whose determinacy had been shown earlier by Gale and Stewart using a argument on the game tree. Martin's theorem applies uniformly to all Borel sets, regardless of their position in the hierarchy, demonstrating that the complexity level does not affect the existence of a . The proof relies on an inductive construction over the , unraveling the game tree into a of strategy trees where a contraction mapping principle—invoking the —guarantees the existence of a fixed point corresponding to a winning strategy. Specifically, for a Borel payoff set of \alpha, Martin builds a space of partial strategies as a , defines a that contracts distances between strategies based on the Borel , and applies the to yield a non-losing strategy for one player, which can then be refined to a winning one. This approach leverages the of the game to simulate higher Borel levels through iterative refinements, ensuring determinacy propagates from the base case of clopen sets upward through the hierarchy. The result's significance lies in its ZFC-provability, contrasting with higher-complexity determinacy results that require additional axioms.

Analytic and Coanalytic Determinacy

Analytic sets, also known as \Sigma^1_1 sets, are the continuous images of Borel sets or, equivalently, the existential projections of Borel subsets of \omega \times \omega. Coanalytic sets, or \Pi^1_1 sets, are the complements of analytic sets. Unlike Borel determinacy, analytic determinacy is not provable in ZFC alone but follows from the of a , a large cardinal hypothesis consistent with ZFC. In 1970, Donald A. Martin proved that the existence of a implies the determinacy of all analytic . The proof relies on representing the analytic payoff set as the of a in a space involving the measurable cardinal \kappa. Specifically, the game is unfolded into an auxiliary of length \omega + 1 on \omega^\omega \times \kappa, where player II chooses elements from \kappa to "witness" membership in the tree. Using the non-principal ultrafilter on \kappa, Martin constructs a winning strategy for one player in the original game by integrating (averaging) strategies over the ultrafilter, ensuring that the measure of winning plays is 1. This reduction leverages the determinacy of , established earlier by Gale and Stewart. Coanalytic determinacy follows immediately from analytic determinacy by duality: if A is coanalytic, then its complement \mathbb{R} \setminus A is analytic, and a winning strategy for the game G(A) is simply a winning strategy for G(\mathbb{R} \setminus A) with the players' roles interchanged. This result establishes determinacy at the base of the projective hierarchy, providing regularity properties such as the perfect set property and measurability for analytic and coanalytic sets of reals, though it falls short of full projective determinacy.

Determinacy and Large Cardinals

Measurable Cardinals

A measurable cardinal is an uncountable \kappa for which there exists a non-principal ultrafilter U on the power set \mathcal{P}(\kappa) that is \kappa-complete (closed under intersections of fewer than \kappa many sets from U) and \kappa-additive. This ultrafilter induces an elementary embedding j: V \to M with critical point \kappa, where M is a transitive inner model containing all ordinals, and [ \kappa ]^U \in M. The existence of a measurable cardinal has profound implications for the determinacy of infinite games of length \omega played over the natural numbers, particularly for games whose payoff sets belong to certain classes in the projective hierarchy. Specifically, assuming ZFC together with the existence of a measurable cardinal, all games with payoff sets in the class \mathbf{\Delta}^1_1 are determined, meaning that one of the two players has a winning strategy. This seminal result is due to Donald A. Martin (). More precisely, Martin's argument establishes \mathbf{\Pi}^1_1-determinacy, from which \mathbf{\Sigma}^1_1-determinacy follows by complementation (switching players), yielding the full \mathbf{\Delta}^1_1-result. The proof relies on the ultrafilter derived from the measurable cardinal to construct a countably complete measure on the space of well-founded trees or codes for coanalytic sets. This measure allows for the definition of a winning strategy by ensuring that certain "good" plays cover the possible opponent responses in the game tree, proving determinacy for coanalytic payoff sets. However, these results are limited to the first level of the projective hierarchy. The existence of a measurable cardinal does not suffice to establish determinacy for all projective sets (\mathbf{[PD](/page/PD)}), which requires stronger assumptions such as the existence of Woodin cardinals.

Woodin Cardinals and Projective Determinacy

A is a notion introduced by , defined as follows: a cardinal κ is Woodin if for every set A ⊆ κ, there exists δ < κ such that for every B ⊆ δ, the set of α < δ for which there exists a B-generic elementary embedding j : (V_α, A ∩ V_α) ≺ (V_δ, A ∩ V_δ) is in δ. This concept strengthens the role of measurable cardinals in proving determinacy for higher levels of the projective hierarchy. Specifically, Donald A. Martin's theorem states that the existence of n Woodin cardinals, together with a measurable cardinal above them, implies the determinacy of all Π¹_{n+1} sets of reals. For finite n, this establishes determinacy step-by-step through the projective levels, building on earlier results for Borel and analytic sets. The full projective determinacy (PD), which asserts that every projective set of reals is determined, follows from the assumption of infinitely many Woodin cardinals with a measurable cardinal above them all. This seminal result, announced in 1988 by Martin and John R. Steel using Woodin's insights, marks a breakthrough in descriptive set theory by linking PD to inner model theory. The proof relies on constructing winning strategies for projective games via iterated ultrapowers and fine-structural mice. Starting from a mouse model containing the Woodin cardinals, one builds iteration trees using extender sequences, where each step applies ultrapower constructions to compare models and ensure iterability. The comparison process yields a well-founded model in which a strategy for the game can be defined, exploiting the genericity and elementarity of the embeddings to cover all possible opponent moves. The of ZFC + PD is established relative to ZFC + I0, where I0 is Woodin's axiom asserting the of a certain iterable inner model with two measurable cardinals; this relative was advanced through Woodin's work in the , confirming PD's viability within ZFC frameworks without post-2023 breakthroughs altering the landscape.

Axiom of Determinacy

The (AD) is a statement in asserting that every two-player game of , played over countably many moves where each alternately chooses natural numbers, and with a payoff set belonging to the power set of the \omega^\omega, is determined: one of the two players has a winning . Formally, for every subset A \subseteq \omega^\omega, the associated Gale-Stewart game G(A) admits a winning strategy for either I or II. Introduced by Mycielski and Steinhaus, AD provides a global assumption contrasting with the by emphasizing regularity in infinite games on the reals. AD is incompatible with the () within ZF , as AC permits the construction of a well-ordering of the reals, from which a non-determined payoff set can be diagonalized. Consequently, AD implies the failure of AC and, in particular, the non-existence of any well-ordering of the . Moreover, AD is consistent with the weaker Axiom of Dependent Choice (), which suffices for many foundational results in descriptive set theory. The consistency of \mathsf{AD}_{L(\mathbb{R})} (determinacy for sets in the inner model L(\mathbb{R})) is established relative to ZF together with the existence of infinitely many Woodin cardinals below the first . Full AD in V requires stronger hypotheses ensuring all sets of reals are in L(\mathbb{R}), with consistency strength equivalent to the existence of a remarkable cardinal. In scope, AD subsumes determinacy for all sets of reals, rendering it strictly stronger than projective determinacy, which applies only to the projective hierarchy.

Consequences of Determinacy

Regularity Properties for Sets of Reals

One of the most significant implications of the axiom of determinacy (AD) is that every set of real numbers exhibits strong regularity properties in measure theory and topology, resolving long-standing questions about the existence of pathological sets under the axiom of choice. Specifically, AD ensures that all subsets of the reals are Lebesgue measurable, meaning that for any set A \subseteq \mathbb{R}, there exists a Borel set B such that the symmetric difference A \Delta B has Lebesgue measure zero. This result, first established in the early 1960s, contrasts sharply with ZFC, where non-measurable sets like the Vitali set exist. AD also guarantees that every set of reals has the property of Baire, which states that for any set A \subseteq \mathbb{R}, there is a nonempty open set U \subseteq \mathbb{R} such that either A is comeager (residual) in U or its complement is comeager in U. This property captures a form of topological "largeness" or "smallness," avoiding the meager sets that can arise under choice. The proof relies on the determinacy of Banach-Mazur games associated with sets of reals, which directly yields this outcome for all subsets. Furthermore, under , every nonempty set of reals has the perfect set property: it either is countable or contains a , where a is a nonempty with no isolated points (hence uncountable and homeomorphic to the ). This eliminates the possibility of uncountable sets without perfect subsets, such as those constructed via well-ordering in ZFC. The argument involves a game where one player attempts to build a perfect tree within the set, with determinacy ensuring success unless the set is countable. For projective sets, which form a key definable hierarchy in descriptive set theory, the axiom of projective determinacy (PD) implies analogous regularity through the existence of scales. A scale on a projective set A is a sequence of functions from reals to ordinals that "norms" the set in a well-ordered way, allowing projections to preserve well-foundedness and yielding Lebesgue measurability, the Baire property, and the perfect set property for all projective levels. These scales are constructed using winning strategies in determined games on projective payoff sets, providing a uniform method to derive regularity without relying on choice principles. PD additionally ensures uniformization for projective sets: for any projective R \subseteq \mathbb{R} \times \mathbb{R} whose projection onto the first coordinate is the entire real line, there exists a projective uniformizing set U \subseteq R such that for every x \in \mathbb{R}, there is exactly one y \in \mathbb{R} with (x, y) \in U. This property facilitates selective choice within definable contexts and follows from constructions that select witnesses via game-theoretic strategies.

Periodicity Theorems

Under the axiom of determinacy (AD), boldface pointclasses of sets of reals exhibit periodicity in their structural properties, meaning that closure under countable unions and intersections alternates between consecutive levels of the hierarchy. Specifically, for a non-self-dual boldface pointclass Γ closed under existential quantification over the reals (∃^ℝ), if Γ is closed under countable unions, then its dual class ˇΓ (the complements of sets in Γ) is closed under countable intersections, and vice versa, leading to a periodic pattern every two levels. This alternation ensures that regularity properties propagate through the hierarchy in a predictable manner. The first periodicity theorem, established independently by Martin and by Addison and Moschovakis, formalizes this propagation for the prewellordering property under definable determinacy assumptions. Assuming that a pointclass Γ has the prewellordering property (meaning there exists a prewellordering on the reals whose kernel is exactly the sets in Γ) and that games in the envelope of Γ (the smallest class containing Γ and closed under certain operations) are determined, then the dual class ˇΓ inherits the property after projection through the reals. This result implies that under projective determinacy (PD), the lightface projective pointclasses Σ¹_{2n+1} and Π¹_{2n+1} alternately possess key structural features like scales and uniformization. Martin's theorem extends this periodicity to scales in the projective hierarchy under PD, showing that the scale property—wherein every set in the pointclass admits a scale (a sequence of norms wellfounded on the complement)—holds periodically for Σ¹_{2n+1} and Π¹_{2n+2}, with the lengths of these scales related to mouse constructions and inner model theory. These scales provide a normed basis for the pointclasses, enabling uniformization and reduction, and the periodicity ensures the hierarchy does not collapse but maintains alternating duality. For example, under PD, Π¹_1 sets have scales of length ω₁, while the pattern repeats with increasing complexity at higher levels tied to large cardinals like measurable cardinals. In determined Gale-Stewart games, periodicity manifests as a duality between the strategies of the two players: if Player I has a winning in a game with payoff set A, then Player II has a winning in the complementary game with payoff set ¬A, reflecting the symmetric nature of open and closed sets under the Gale-Stewart theorem. This duality underpins the periodic alternation in pointclass properties, as determinacy ensures that strategic advantages flip predictably across dual classes. Under , every set of reals is Ramsey, meaning for any such set A, there exists an X ⊆ ω such that either [X]^ω ⊆ A or [X]^ω ∩ A = ∅ relative to the Mathias topology on the reals; moreover, these sets admit periodic scales that alternate in their norming properties across the boldface hierarchy. This Ramsey property, combined with the scale periodicity, implies that all sets of reals satisfy strong regularity features without , contrasting with ZFC where pathological sets exist. The full periodicity of pointclasses under , including the uniform alternation of all major structural properties (such as reduction, scales, and envelopes) across boldface levels, was established by Harrington, Kechris, and Louveau, building on earlier work to show that induces a complete periodic structure on the power set of the reals. This result unifies the combinatorial theory of reals under determinacy, revealing a rigid, alternating framework for all subsets.

Applications to Descriptive Set Theory and Logic

Projective determinacy (PD) establishes that the projective hierarchy of sets of reals is well-defined, with each level \Sigma_n^1 properly containing the previous ones for all finite n, resolving long-standing questions about the complexity and separation of these classes. This , built by successive projections and complements starting from s, benefits from PD through the existence of scales—good winning strategies in associated games—that enable proofs of regularity properties like the perfect set theorem and uniformization at every projective level. In particular, PD implies basis theorems for projective sets, asserting that every non-empty set in \Sigma_n^1 admits a uniform basis, either a Borel set or a simpler projective set from which it can be projected, facilitating constructive descriptions and classifications in descriptive set theory. PD also yields significant results in logic, particularly regarding definability. It provides a projective truth definition for sentences in second-order arithmetic (Z_2), using scales for projective sets to define satisfaction within the projective hierarchy. However, this truth predicate is not recursively decidable. Similarly, fragments of set theory restricted to projective definitions become projectively definable under PD, as game-theoretic strategies resolve the satisfaction of projective formulas over the reals. Harrington's theorem further connects this to analytic sets: analytic determinacy (implied by PD) is equivalent to the existence of $0^\sharp, which yields a recursive enumeration of true \Pi^1_1 sentences. The (AD) has profound implications for principles in descriptive . AD contradicts the by implying the failure of global choice on the power set of the naturals, as all sets of reals become Lebesgue measurable and have the property, precluding pathological sets like Vitali sets that rely on choice. However, AD restores choice-like functionality through uniformization: every relation on the reals whose vertical sections are sets of reals admits a uniformizing selecting one from each non-empty section, providing a selective without full choice. Links to inner underscore these applications, where determinacy axioms guide the construction of canonical inner models containing all reals and satisfying properties consistent with PD and AD. Recent work, including a 2025 construction of a model of AD in which every set of reals is universally Baire (Larson, Sargsyan, and ), continues to refine these models with Woodin cardinals, advancing the understanding of consistency strength and definability.

Wadge Degrees and Hierarchy

In descriptive , Wadge reducibility provides a way to compare the descriptive complexity of subsets of the \omega^\omega. For sets E, F \subseteq \omega^\omega, E \leq_W F if there exists a f: \omega^\omega \to \omega^\omega such that E = f^{-1}(F). This relation is reflexive and transitive, forming a quasi-order on the power set of \omega^\omega. The E \equiv_W F holds if E \leq_W F and F \leq_W E, and the Wadge degree of E is the [E]_W = \{ G \subseteq \omega^\omega \mid G \equiv_W E \}. These degrees order the sets by continuous reducibility, capturing fine-grained differences in complexity beyond traditional Borel or projective hierarchies. Under the (AD), the Wadge degrees form a well-founded semi-linear order. Specifically, Wadge's lemma states that for any A, B \subseteq \omega^\omega, either A \leq_W B or B \leq_W \neg A, ensuring comparability up to complements with no infinite descending chains. The entire hierarchy is well-ordered with ordinal length \Theta, where \Theta is the least ordinal that cannot be injected into \omega^\omega via an ordinal definable function from the reals. This structure arises because AD implies the determinacy of all Wadge games, games where Player I wins if the outcome is in A and Player II if in \neg A, via continuous reductions. (PD), a consequence of large cardinals like Woodin cardinals, restricts this to projective sets: the projective Wadge degrees are well-ordered with length given by the projective ordinals \delta^1_n. The Wadge hierarchy embeds into the class of ordinals through the Wadge rank \|A\|_W, the ordinal height assigned to the degree [A]_W in this well-ordering. Self-dual degrees (where [A]_W = [\neg A]_W) alternate with non-self-dual pairs ([B]_W, [\neg B]_W), reflecting the semi-linearity. A related structure is the Lipschitz degrees, defined using 1-Lipschitz (non-expansive) continuous functions for reductions; under AD, the Lipschitz hierarchy has the same length \Theta and is equivalent in strength to the full Wadge hierarchy, as Wadge determinacy implies Lipschitz determinacy and vice versa. This equivalence highlights how continuous reductions suffice to capture the full ordering without needing stricter uniformity.

Generalizations of Determinacy

Games Beyond Natural Numbers

In the standard Gale-Stewart framework, infinite games of perfect information can be generalized to settings where players alternate moves from an arbitrary Polish space X rather than the natural numbers \omega, producing runs in the space X^\omega equipped with the product topology, which is itself Polish. The payoff set is then a subset A \subseteq X^\omega, and the game G(A) is determined if one player has a winning strategy. A key result in ZFC is that Borel determinacy holds for such games on any X. This generalizes Martin's original theorem for the \omega^\omega, relying on the topological structure of Polish spaces to construct winning strategies via unfolding and measure-theoretic arguments. For instance, in the $2^\omega, Borel payoffs yield determined games, mirroring the countable case but leveraging the complete metric to ensure strategy existence without choice principles beyond ZFC. Variants of the axiom of determinacy extend to these broader move sets. The axiom \mathsf{AD}_\mathbb{R} asserts determinacy for all games of length \omega where players move reals from the Polish space \mathbb{R}, with payoffs in \mathbb{R}^\omega. This implies the same regularity properties for sets of reals as \mathsf{AD} (e.g., Lebesgue measurability, Baire property, perfect set property), and is equivalent to \mathsf{AD} holding in L(\mathbb{R}). Large cardinals, such as a measurable cardinal above infinitely many Woodin cardinals, suffice to prove \mathsf{AD}_\mathbb{R} consistent relative to ZFC. For games of length \kappa where \kappa is an uncountable and moves are from \{0,1\} (yielding runs in $2^\kappa), determinacy relates closely to combinatorial principles involving sets on \kappa. Under \mathsf{AD}, \omega_1 becomes measurable, implying that every subset of \omega_1 is "thick" in the sense of intersecting all club sets in a uniform way, which contrasts with ZFC where and co-stationary sets partition \omega_1. Determinacy for definable payoffs in such transfinite games of length \omega_1 or \omega_2 follows from \mathsf{AD}_\mathbb{R} or stronger assumptions like the existence of 0^\sharp, ensuring strategies exist without relying on the . Specific examples illustrate reductions to the standard case. Games where players move integers from \mathbb{Z} can be coded bijectively into \omega via a , preserving determinacy status since \mathbb{Z}^\omega is homeomorphic to \omega^\omega. Similarly, for rational moves in \mathbb{Q}^\omega, the dense countable structure allows continuous coding into the , so Borel determinacy holds in ZFC, and full determinacy follows under \mathsf{AD}_\mathbb{R}. These reductions highlight how completeness facilitates equivalence across countable move sets.

Long Games and Games on Trees

Long games generalize the standard Gale-Stewart games of length \omega by allowing plays of arbitrary ordinal length \alpha, where players alternate moves from \omega to construct a sequence of length \alpha. For \alpha = \omega_1, determinacy of open games of this length—where the winning condition depends on whether some initial segment belongs to a given set—holds assuming the existence of an iterable inner model containing a proper class of indiscernible Woodin cardinals. Such assumptions also yield determinacy for stronger classes of \omega_1-length games involving payoff sets defined over the club filter on \omega_1 and sequences of stationary subsets. Determinacy for \omega_1-length games further arises from combinatorial principles tied to large cardinals, such as . For instance, simultaneous reflection of stationary subsets of \omega_2 (denoted WRP(2)(\omega_2)) combined with the of the nonstationary ideal on \omega_1 implies the in L(\mathbb{R}), extending to determinacy in models incorporating long games via core model induction and mouse principles. Club guessing principles, which posit the existence of sequences that anticipate closed unbounded subsets of \omega_1 by tail segments, are consequences of \omega_1-strong cardinals and facilitate proofs of determinacy for certain \omega_1-games by providing combinatorial control over sets in inner models. Tree games involve players collaboratively constructing branches through a tree T \subseteq \omega^{<\omega}, with the payoff determined by whether the resulting infinite path satisfies a given condition. These games connect to the structure of trees in , particularly Suslin trees, which are \omega_1-trees without uncountable branches or antichains; under determinacy, models like L(\mathbb{R}) satisfy the Suslin hypothesis, implying no such trees exist and thus restricting possible payoff sets in tree games. Determinacy for tree games often follows from broader results on infinitely long , where the game tree encodes legal moves, and winning strategies are analyzed via iteration along branches. The (AD) implies determinacy for all games of length less than \Theta in L(\mathbb{R}), where \Theta is the supremum of ordinals surjectively onto which the reals map; this follows from the uniformization properties and scale arguments inherent to AD, ensuring strategies exist for payoffs definable in L(\mathbb{R}). Such results extend the scope of determinacy beyond countable lengths, capturing games up to the "height" of the reals under AD. Applications of and tree game determinacy include advancements in forcing techniques and inner model theory. Stationary tower forcing, a generalized forcing iteration over models with Woodin cardinals, uses determinacy for s to establish absoluteness results and construct inner models satisfying , such as extensions where the nonstationary ideal remains saturated. These tools calibrate the consistency strength of determinacy axioms and yield canonical inner models incorporating tree properties, like the absence of Suslin trees, to analyze regularity of sets of reals.

Imperfect Information Games

In the study of determinacy, imperfect information games extend classical Gale-Stewart games by introducing asymmetry in players' knowledge of the game history or opponent's actions, necessitating the use of mixed strategies for achieving optimal outcomes. These games model scenarios where players receive partial signals or observations, contrasting with games where full history is available to both. Determinacy in this setting typically means the existence of a value—a representing the game's worth under optimal mixed strategies—rather than a pure winning strategy for one player. A foundational class of such games is Blackwell games, introduced by in 1969, where two players alternately choose natural numbers simultaneously without observing the opponent's exact move, instead receiving a signal (often the sum modulo some fixed number), and the payoff depends on the limiting frequency of visits to certain states. Blackwell initially proved determinacy for games with open or G_\delta payoff sets using epsilon-optimal strategies. In 1998, Donald A. Martin established that all Borel Blackwell games are determined, showing that their value equals that of an associated perfect-information Borel game, thereby leveraging Martin's 1975 Borel determinacy theorem. Under the (AD), every Blackwell game on the reals has a value, as AD implies the pointclass of all sets of reals is determined, extending Martin's reduction. Stochastic games generalize Blackwell games by incorporating probabilistic transitions between states, where players' randomized moves influence the evolution, and payoffs are defined via limiting averages or discounted sums. In information variants, players act based on private signals, and determinacy manifests as the existence of a value under optimal behavioral strategies. and Sudderth (1998) proved that Borel stochastic games with finitely additive measures are determined, adapting Martin's techniques to handle the probabilistic structure while preserving the value from associated perfect-information games. These results hold under AD for more complex objectives, ensuring values for all such games on reals. More broadly, imperfect information games with partial observations—where players see only subsets of the play history—connect to through reductions to games on product constructions of the original and observation automata. In contexts, determinacy for \omega-regular objectives (e.g., parity or Büchi conditions) under partial observations is established by solving equivalent perfect-information games on expanded state spaces, yielding decidable values for finite-state arenas. Projective determinacy (PD) implies determinacy for projective imperfect-information games, including those with Borel or projective partial-observation structures, by extending the determinacy of projective perfect-information games via similar value-preserving reductions.

Quasideterminacy Concepts

A quasistrategy in a two-player game of is a of a that, at each position, specifies a non-empty set of acceptable moves rather than a single move, such that every complete play consistent with choices from these sets results in a win for the employing the quasistrategy. Formally, for Player II in a game on reals with payoff set A \subseteq \mathbb{R}^\omega, a quasistrategy \Sigma: \bigcup_{n \in \mathbb{N}} \mathbb{R}^n \to \mathcal{P}(\mathbb{R}) \setminus \{\emptyset\} is winning if for every play x with x(2n) \in \Sigma(x \restriction 2n) for all n, the run x \in A. Quasideterminacy extends the notion of determinacy by requiring that at least one possesses such a winning quasistrategy, rather than a precise winning . In the context of infinite games on natural numbers, quasideterminacy can be defined with respect to or measure: a quasistrategy wins on a comeager set of opponent plays (i.e., all but a meager set) or on a set of full . This weakening allows for broader applicability, particularly in analyzing games where payoffs are "small" in the Baire sense, such as meager sets. ZFC proves quasideterminacy for all games with Borel payoff sets, as quasistrategies can be constructed level-by-level through the using inductive definitions and absoluteness arguments. The proof leverages the structure of Borel sets and the wellorderability of the natural numbers as the move set, ensuring that a winning quasistrategy implies a genuine winning strategy via the ; this aligns with Martin's full Borel determinacy theorem but highlights the category-theoretic underpinnings, as quasistrategies often correspond to dense open sets in the game tree via the . Under the (AD), quasideterminacy coincides with full determinacy for games on reals. AD implies that every set of reals has the property of Baire, rendering meager sets "avoidable" in a strong sense, so any quasistrategy winning on a comeager set can be refined to a precise using the regularity properties ensured by AD. Specifically, Lemma 15 in descriptive inner model theory shows that if a pointclass is closed under continuous images, over reals, complements, and finite unions, then quasi-determinacy for that class implies full determinacy. Quasideterminacy concepts find applications in generic absoluteness and forcing techniques. In inner models like L(\mathbb{R},\mu), where \mu is a measure on \kappa, quasideterminacy preserves determinacy properties across forcing extensions, ensuring that Borel-level games remain quasi-determined in generic extensions without collapsing cardinals. This is crucial for constructing models where holds, such as those arising from Woodin cardinals, facilitating the study of absoluteness for \Sigma^1_2 statements under forcing that adds no new reals.