prioritized_borel_fork_all_winning_memoryless
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.
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.
refine ⟨BorelGamePlayer.Eve, Unit, inferInstance, by simp, prioritized_borel_fork_all_winning_strategy, ?_⟩ intro play _ _ _ _
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.
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
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.
uses
prioritized_borel_highest_recurrent_indexobtain ⟨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⟩
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.
refine ⟨p, ?_, ?_, by simp [prioritized_borel_fork_all_winning_game]⟩
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.
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
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.
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.
- The edge priorities in Fin 3 (taking values in {0, 1, 2}) are shifted by 1 to {1, 2, 3} purely to match the signature of the helper lemma prioritized_borel_highest_recurrent_index, before being shifted back by 1 to define p.
- Eve wins regardless of the sequence of directions chosen along the play because the game defines every priority's winning set to be the universal set.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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