Borel Determinacy

Origin. Martin (1975). Infinite games with Borel winning sets are determined. One player has winning strategy. Beyond Borel: requires large cardinals. Foundation for descriptive set theory.

Models. Two players alternate choosing naturals. Infinite play: sequence in ℕ^ω. Winning condition: Borel set A. Determined: one player has winning strategy.

Formalism.

Gale-Stewart game G(A): Players I and II alternate: a₀, b₀, a₁, b₁, ... Play: x = (a₀, b₀, a₁, b₁, ...) ∈ ℕ^ω Player I wins iff x ∈ A.

Strategy: σ for I: (history) → next move τ for II: (history) → next move σ * τ: unique play when both follow strategies

Winning strategy: σ winning for I in G(A) iff ∀τ. σ * τ ∈ A τ winning for II iff ∀σ. σ * τ ∉ A

Determinacy: G(A) determined iff I or II has winning strategy. Det(Γ): all games with Γ payoff determined.

Borel hierarchy: Σ⁰₁: open, Π⁰₁: closed Σ⁰_α: countable unions of sets drawn from ∪{β<α} Π⁰_β; Π⁰_α: complements of Σ⁰_α Borel: ∪{α<ω₁} Σ⁰_α = ∪_{α<ω₁} Π⁰_α The union runs to ω₁, not to ω. Stopping at the finite levels does not give the Borel sets, because those levels are not jointly closed under countable union: take one set from each of Σ⁰₁, Σ⁰₂, Σ⁰₃, … and their union already sits at Σ⁰_ω. On an uncountable Polish space the hierarchy is strictly increasing at every countable ordinal, so every level below ω₁ is needed and none above is.

Martin's theorem: All Borel games are determined. Det(Borel) provable in ZFC.

Beyond Borel: Analytic (Σ¹₁): projections of Borel. Det(Analytic) requires large cardinals. Projective determinacy: from large cardinals.

Symbols.

Metatheory. ZFC proves Borel determinacy. Large cardinals for projective. Axiom of Determinacy (AD) alternative. Wadge degrees.

Applies to. Descriptive set theory. Set theory foundations. Infinite games. Automata theory. Large cardinals.

Limitations. Infinitary. Borel complexity. Large cardinals for extensions. Abstract mathematics.

© 2026 Lingenic LLC