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 Π⁰ₙ Borel: ∪ₙ Σ⁰ₙ = ∪ₙ Π⁰ₙ

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.

Symbol	Unicode	Name	Meaning
G(A)	—	Game	With payoff A
σ, τ	—	Strategies	Player strategies
Det	—	Determinacy	Game determined
Σ⁰ₙ, Π⁰ₙ	—	Borel	Hierarchy levels

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.