AFTD Auto-Formalizing Theoretical Domains

prioritized_borel_fork_all_winning_memoryless

theoremverified

The all-winning fork game has a winning strategy using one memory state.

Statement

theorem prioritized_borel_fork_all_winning_memoryless : HasWinningStrategyInMem prioritized_borel_fork_all_winning_game 1
Source
arXiv:2611.10136, Section 5.3.2; the three-state fork subarena
Verified
12 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 8
  • prioritized_borel_fork_all_winning_gameThe three-state fork arena with every priority branch set equal to the full branch space.
  • prioritized_borel_fork_all_winning_strategyA memoryless strategy choosing the true-direction edge at the p-owned state of the all-winning fork game.
  • prioritized_borel_highest_recurrent_indexEvery infinite sequence of positive natural numbers bounded by s has a positive largest recurrent value I, and all sufficiently late…
  • HasWinningStrategyInMemThe proposition HasWinningStrategyInMem G m_bound asserts that for a prioritized Borel game G with state space Q and k priorities, there…
  • TreeGameEdgeA structure TreeGameEdge (Q : Type*) (k : ℕ) representing an edge in a binary tree game arena with state space Q and k priorities, with…
  • PrioritizedBorelGameA structure PrioritizedBorelGame (Q : Type*) (k : ℕ) representing a prioritized Borel game with state space Q and k priorities, with…
  • BorelGamePlayerThe two players in a prioritized Borel game, Eve and Adam.
  • FiniteMemoryStrategyA structure FiniteMemoryStrategy {Q : Type*} {k : ℕ} (G : PrioritizedBorelGame Q k) (pl : BorelGamePlayer) (M : Type*) representing a…

The proof, explained

The proof shows that Eve has a winning strategy using a single memory state (Unit) in the prioritized Borel fork game. Since all winning sets in this game are universal, Eve wins any play as long as there is a well-defined maximal priority occurring infinitely often. Because edge priorities take values in Fin 3, the finite-range recurrence lemma ensures the existence of a maximal recurring priority, which immediately satisfies Eve's parity winning condition.

  1. The problem reduces to showing that Eve wins any legal play consistent with a 1-state memory strategy.

    We witness Eve as the winning player, Unit as the memory type (which has cardinality 1 ≤ 1, fulfilling the memoryless bound), and the candidate strategy prioritized_borel_fork_all_winning_strategy. We then consider an arbitrary infinite play that conforms to the graph transitions, initial state, and Eve's strategy choices.

    lines 2–3

      refine ⟨BorelGamePlayer.Eve, Unit, inferInstance, by simp, prioritized_borel_fork_all_winning_strategy, ?_⟩
      intro play _ _ _ _
  2. At every step n, the shifted priority (play n).prio + 1 lies in the range {1, 2, 3}.

    Because edge priorities belong to Fin 3, their values are strictly less than 3. Adding 1 ensures that the shifted priority is at least 1 and at most 3.

    lines 4–7

      have hf : ∀ n, 1 ≤ (play n).prio.val + 1 ∧ (play n).prio.val + 1 ≤ 3 := by
        intro n
        have h := (play n).prio.isLt
        omega
  3. There is a maximal recurrent priority p ∈ Fin 3 that appears infinitely often and bounds all subsequent priorities beyond some step N₀.

    Applying prioritized_borel_highest_recurrent_index with bound 3 to the shifted priority sequence yields an index I ∈ {1, 2, 3} that recurs after any point, along with a threshold N₀ past which all terms are at most I. We define the priority p ∈ Fin 3 to have numerical value I - 1.

    lines 8–10

    uses prioritized_borel_highest_recurrent_index

      obtain ⟨I, hpos, hbound, hrec, N0, hmax⟩ :=
        prioritized_borel_highest_recurrent_index 3 (fun n => (play n).prio.val + 1) hf
      let p : Fin 3 := ⟨I - 1, by omega⟩
  4. Choosing p reduces Eve's winning condition to showing that p recurs infinitely often and no strictly higher priority does.

    We provide p as the witness for Eve's priority condition. The third requirement—that the sequence of edge directions belongs to the winning set for p—holds immediately by simplification because the game defines winning sets for all priorities to be the universal set.

    line 11

      refine ⟨p, ?_, ?_, by simp [prioritized_borel_fork_all_winning_game]⟩
  5. Priority p occurs infinitely often along the play.

    Using Filter.frequently_atTop.mpr, for any given threshold N we find an index n ≥ N where the shifted priority equals I. By Fin.ext, the priority of play n equals p because their numerical values both equal I - 1.

    lines 12–18

    uses Filter.frequently_atTop.mpr, Fin.ext

      · apply Filter.frequently_atTop.mpr
        intro N
        obtain ⟨n, hn, heq⟩ := hrec N
        refine ⟨n, hn, ?_⟩
        apply Fin.ext
        dsimp [p]
        omega
  6. No priority strictly greater than p occurs infinitely often.

    Suppose for contradiction that some priority q > p occurs infinitely often. By Filter.frequently_atTop.mp, q must occur at some step n ≥ N₀. Applying Fin.val via congrArg yields that the priority at step n equals q. However, the upper bound at N₀ ensures that this priority is at most I - 1 = p, contradicting p < q.

    lines 19–25

    uses Filter.frequently_atTop.mp, congrArg, Fin.val

      · intro q hq hfreq
        obtain ⟨n, hn, heq⟩ := Filter.frequently_atTop.mp hfreq N0
        have hh := hmax n hn
        have hp : p.val < q.val := hq
        have heqval := congrArg Fin.val heq
        dsimp [p] at hp
        omega
prioritized_borel_highest_recurrent_index
In any sequence taking values in {1, ..., s}, there exists a maximal value I occurring infinitely often, such that I recurs after any point and all sequence terms are eventually at most I.
Filter.frequently_atTop.mpr
A property holds frequently (infinitely often) along ℕ if and only if for every index N, there is an index n ≥ N where the property holds.
Fin.ext
Two elements of Fin n are equal if their underlying natural number values are equal.
Filter.frequently_atTop.mp
If a property holds frequently (infinitely often) along ℕ, then for every threshold N there exists some n ≥ N satisfying the property.
congrArg
Equality is preserved under function application: if a₁ = a₂, then f a₁ = f a₂.
Fin.val
The projection mapping an element of Fin n to its underlying natural number value.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

theorem prioritized_borel_fork_all_winning_memoryless : HasWinningStrategyInMem prioritized_borel_fork_all_winning_game 1 := by  refine ⟨BorelGamePlayer.Eve, Unit, inferInstance, by simp, prioritized_borel_fork_all_winning_strategy, ?_⟩  intro play _ _ _ _  have hf : ∀ n, 1 ≤ (play n).prio.val + 1 ∧ (play n).prio.val + 1 ≤ 3 := by    intro n    have h := (play n).prio.isLt    omega  obtain ⟨I, hpos, hbound, hrec, N0, hmax⟩ :=    prioritized_borel_highest_recurrent_index 3 (fun n => (play n).prio.val + 1) hf  let p : Fin 3 := ⟨I - 1, by omega⟩  refine ⟨p, ?_, ?_, by simp [prioritized_borel_fork_all_winning_game]⟩  · apply Filter.frequently_atTop.mpr    intro N    obtain ⟨n, hn, heq⟩ := hrec N    refine ⟨n, hn, ?_⟩    apply Fin.ext    dsimp [p]    omega  · intro q hq hfreq    obtain ⟨n, hn, heq⟩ := Filter.frequently_atTop.mp hfreq N0    have hh := hmax n hn    have hp : p.val < q.val := hq    have heqval := congrArg Fin.val heq    dsimp [p] at hp    omega
See it in the graphDiscuss this resultChallenge it