2025-11-10T02:32:56.375344

Binary Choice Games and Arithmetical Comprehension

Aguilera, Kouptchinsky
We prove that Arithmetical Comprehension is equivalent to the determinacy of all clopen integer games in which each player has at most two moves per turn.
academic

Binary Choice Games and Arithmetical Comprehension

Basic Information

  • Paper ID: 2510.12612
  • Title: Binary Choice Games and Arithmetical Comprehension
  • Authors: J. P. Aguilera, T. Kouptchinsky (Vienna University of Technology)
  • Classification: math.LO (Mathematical Logic)
  • Publication Date: October 15, 2025
  • Paper Link: https://arxiv.org/abs/2510.12612

Abstract

This paper proves that Arithmetical Comprehension is equivalent to the determinacy of all closed integer games where each player has at most two move choices per round.

Research Background and Motivation

Research Questions

The core research question addresses, within the framework of Reverse Mathematics, the equivalence relations between the determinacy of binary choice games and subsystems of second-order arithmetic, particularly the relationship with the Arithmetical Comprehension axiom system ACA₀.

Significance of the Problem

  1. Foundational Questions in Reverse Mathematics: Determining which mathematical theorems require which axiom systems is the central goal of reverse mathematics
  2. Intersection of Game Theory and Logic: Game determinacy theory plays an important role in characterizing the proof-theoretic strength of logical systems
  3. Refinement of Existing Theory: Fills an important gap in the study of binary choice game determinacy

Limitations of Existing Research

  1. Results by Nemoto et al.: Proved that determinacy of all Δ₁⁰ games on {0,1} is equivalent to WKL₀, but limited to binary moves
  2. Results by Simpson: Proved that determinacy of integer move games of length k (k≥3) is equivalent to ACA₀, but without restrictions on the number of moves
  3. Results by Steel: Δ₁⁰-determinacy is equivalent to ATR₀, but with higher complexity

This paper fills the important theoretical gap of "finite move choices but allowing integer moves."

Core Contributions

  1. Main Equivalence Theorem: Proves that over RCA₀, the following four propositions are equivalent:
    • Determinacy of well-founded binary choice game trees
    • Δ₁⁰-determinacy of binary choice game trees
    • (Σ₁⁰)ₖ-determinacy of binary choice game trees
    • The ACA₀ axiom system
  2. New Game Model: Introduces precise mathematical definitions of binary choice game trees, where each player has at most two legal moves per round
  3. Constructive Proofs: Provides explicit methods for constructing special games from trees that violate König's lemma
  4. Theoretical Refinement: Establishes precise correspondence between binary choice game determinacy theory and arithmetical comprehension

Methodology Details

Task Definition

Binary Choice Tree Definition: A finite set T of natural number sequences is a binary choice tree if and only if:

  1. For all τ∈T, all prefixes of τ are also in T
  2. For all τ∈T, there exist at most two n such that τ⌢n∈T

Game Definition: Given a binary choice game tree T and formula φ, in game G(T,φ):

  • Players alternately choose natural numbers
  • The first player to violate the tree structure loses
  • Otherwise, the winner is determined according to φ(x), where x is the complete sequence of moves

Model Architecture

Strategy Definition

The paper defines two types of strategies:

  1. Standard Strategies:
    • Player I's strategy σ: N^even → N
    • Player II's strategy τ: N^odd → N
  2. Restricted Strategies:
    • Must operate within the given tree T
    • Player I chooses the unique move at even positions, all legal moves allowed at odd positions
    • Player II vice versa

Winning Conditions

For game G(T,φ), Player I wins if and only if: ¬μᵢ(x) ∧ (φ(x) ∨ μᵢᵢ(x))

where:

  • μᵢ(x): Player I first violates the tree structure
  • μᵢᵢ(x): Player II first violates the tree structure

Technical Innovations

  1. Tree Structure Encoding: Cleverly embeds arbitrary binary choice trees into standard binary trees {0,1}*, preserving the essential properties of the game
  2. Four-Stage Game Construction: When proving the necessity of ACA₀, designs a complex four-stage game:
    • Stage 1: Player I constructs sequence t∈T
    • Stage 2: Player II selects u₀ such that t⌢u₀∈T
    • Stage 3: Player I constructs sequence v, requiring v(0)≠u₀
    • Stage 4: Player II constructs sequence u' extending t⌢u₀
  3. Inductive Arguments: Uses nested structures of Σ₁⁰ induction and Π₁⁰ induction to prove that violating König's lemma leads to contradiction

Experimental Setup

This paper is pure mathematical theoretical research with no computational experiments. The proof process employs rigorous mathematical logic reasoning.

Proof Strategy

  1. Sufficiency Proof: ACA₀ ⟹ (Σ₁⁰)ₖ-Det
  2. Necessity Proof: Well-founded binary choice game determinacy ⟹ ACA₀
  3. Equivalence Chain: Establishes logical derivation relationships between the four propositions

Key Lemmas

The paper relies on Simpson's classical results on subsystems of second-order arithmetic, particularly that ACA₀ is equivalent to the weak König's lemma for binary choice trees.

Experimental Results

Main Results

Theorem 1.1: For k≥1, the following propositions are equivalent over RCA₀:

  1. Determinacy of well-founded binary choice game trees
  2. Δ₁⁰-determinacy of binary choice game trees
  3. (Σ₁⁰)ₖ-determinacy of binary choice game trees
  4. ACA₀

Proof Highlights

Sufficiency Direction

  • Utilizes ACA₀ to construct embedding ρ: T → 2^N
  • Applies Nemoto et al.'s determinacy results for binary games
  • Pulls winning strategies back to the original game via ρ

Necessity Direction

  • Assumes existence of infinite binary choice tree T violating König's lemma
  • Constructs special four-stage game with well-founded game tree
  • Proves Player I has no winning strategy
  • Constructs branch of T from Player II's winning strategy, yielding contradiction

Technical Details

The key inequality in the proof: |T_{fn+1-j}| ≤ 2^{j+1} - 1, established through Π₁⁰ induction, ultimately leads to |T| being bounded, contradicting the assumption that T is infinite.

Related Work

Major Research Directions

  1. Classical Game Determinacy: Steel's Δ₁⁰-determinacy theory
  2. Finite Games: Simpson's research on fixed-length games
  3. Binary Games: Work by Nemoto-MedSalem-Tanaka on Cantor space games

Uniqueness of This Paper's Contribution

  • First to establish equivalence between binary choice-constrained game determinacy and ACA₀
  • Fills the theoretical gap between WKL₀ (binary moves) and ATR₀ (unrestricted moves)
  • Provides constructive proof methods with strong mathematical insight

Conclusions and Discussion

Main Conclusions

This paper completely characterizes the logical strength of binary choice game determinacy, proving it corresponds exactly to the Arithmetical Comprehension axiom system ACA₀. This provides important new results for game determinacy theory in reverse mathematics.

Limitations

  1. Move Restrictions: Results apply only to cases with at most two moves per round
  2. Tree Structure Requirements: Games must operate within specific binary choice tree structures
  3. Complexity Restrictions: Only considers relatively low-complexity winning condition categories

Future Directions

  1. Generalization to More Moves: Study cases with k moves per round (k>2)
  2. Higher Complexity: Explore relationships with stronger axiom systems (e.g., ATR₀)
  3. Computational Complexity: Investigate algorithmic complexity of related game problems

In-Depth Evaluation

Strengths

  1. Theoretical Completeness: Provides complete characterization of binary choice game determinacy
  2. Proof Techniques: The four-stage game construction demonstrates sophisticated technical skill
  3. Logical Rigor: All proof steps are strictly conducted within the RCA₀ framework
  4. Gap-Filling: Resolves an important open problem in the field

Weaknesses

  1. Limited Applications: As a pure theoretical result, direct application value is limited
  2. Technical Complexity: The proof process is quite complex with high comprehension barriers
  3. Generalizability: Generalization to more general cases is not straightforward

Impact

  1. Theoretical Contribution: Makes important contributions to reverse mathematics and game determinacy theory
  2. Methodological Value: Proof techniques may be applicable to related problems
  3. Completeness: Refines the spectrum of logical strengths for game determinacy

Applicable Scenarios

Primarily applicable to:

  1. Theoretical research in reverse mathematics
  2. Game determinacy theory
  3. Proof-theoretic research on subsystems of second-order arithmetic
  4. Foundational mathematical logic research

References

1 J. P. Aguilera, The Metamathematics of Separated Determinacy, Invent. Math. 240 (2025), 313–457. 2 T. Nemoto, M. O. MedSalem, and K. Tanaka, Infinite Games in the Cantor Space and Subsystems of Second Order Arithmetic, Math. Log. Q. 53 (2007), 226–236. 3 S. Simpson, Subsystems of Second-Order Arithmetic, 1999. 4 J. R. Steel, Determinateness and Subsystems of Analysis, Ph.D. Thesis, 1977.