AFTD Auto-Formalizing Theoretical Domains

has_winning_strategy_in_mem_mono

theoremverified

In any prioritized Borel game G with k priorities on state space Q, if a player has a winning strategy using at most m1 memory states, and m1 ≤ m2, then the player has a winning strategy using at most m2 memory states.

Statement

theorem has_winning_strategy_in_mem_mono {Q : Type*} {k : ℕ} (G : PrioritizedBorelGame Q k) {m1 m2 : ℕ} (h : m1 ≤ m2) (hw : HasWinningStrategyInMem G m1) : HasWinningStrategyInMem G m2
Source
step towards op_1385_three_priority_borel_finite_memory_determinacy
Verified
11 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • PrioritizedBorelGameA structure PrioritizedBorelGame (Q : Type*) (k : ℕ) representing a prioritized Borel game with state space Q and k priorities, with…
  • 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…
  • 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 proceeds directly by unpacking the winning strategy with memory bound $m_1$ and reusing it for bound $m_2$. Since the memory space $M$ satisfies $|M| \le m_1$ and $m_1 \le m_2$, transitivity of inequality gives $|M| \le m_2$, so the exact same strategy witnesses that a winning strategy exists within memory bound $m_2$.

  1. We obtain a player, a finite memory space $M$ of size at most $m_1$, and a winning strategy on $M$.

    Unpack the hypothesis `hw` (`HasWinningStrategyInMem G m1`), which by definition provides a player `pl`, a finite memory type $M$ satisfying $|M| \le m_1$, and a winning strategy `strat` with memory $M$.

    line 3

      rcases hw with ⟨pl, M, fM, hcard, strat, hwin⟩
  2. The same player, memory space, and strategy satisfy the winning condition with memory bound $m_2$.

    Provide the same player `pl`, memory space $M$, and strategy `strat` as witnesses for `HasWinningStrategyInMem G m2`. The cardinality bound $|M| \le m_2$ holds by transitivity from $|M| \le m_1$ and the hypothesis $m_1 \le m_2$, while the strategy and its winning property are unchanged.

    line 4

      exact ⟨pl, M, fM, hcard.trans h, strat, hwin⟩

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

/-- A winning strategy using at most m1 memory states also uses at most m2 memory states whenever m1 ≤ m2. -/theorem has_winning_strategy_in_mem_mono {Q : Type*} {k : ℕ} (G : PrioritizedBorelGame Q k) {m1 m2 : ℕ} (h : m1 ≤ m2) (hw : HasWinningStrategyInMem G m1) : HasWinningStrategyInMem G m2 := by  rcases hw with ⟨pl, M, fM, hcard, strat, hwin⟩  exact ⟨pl, M, fM, hcard.trans h, strat, hwin⟩
See it in the graphDiscuss this resultChallenge it