PrioritizedBorelGame
A structure PrioritizedBorelGame (Q : Type*) (k : ℕ) representing a prioritized Borel game with state space Q and k priorities, with fields: owner : List Bool × Q → BorelGamePlayer, init_state : Q, edges : Set (TreeGameEdge Q k), edges_outgoing asserting that every position (v, q) has an outgoing edge in edges with source_node v and source_state q, winning_sets : Fin k → Set (ℕ → Bool), and winning_measurable asserting that each winning set is Borel (MeasurableSet).
Statement
structure PrioritizedBorelGame (Q : Type*) (k : ℕ)
- Defined in
- arXiv:2611.10136, Def. 18
- Verified
- 10 Nov 2026
- Axioms
- none listed
- Built on 2
- BorelGamePlayerThe two players in a prioritized Borel game, Eve and Adam.
- TreeGameEdgeA structure TreeGameEdge (Q : Type*) (k : ℕ) representing an edge in a binary tree game arena with state space Q and k priorities, with…
- Used by 19
- PrioritizedBorelStrategyHistoryAn encoded finite history follows legal edges from the initial position and agrees with the chosen strategy at its player's positions.…
- 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_reverse_state_histories_uniqueIf a tree-game edge is reverse-deterministic in the state at each fixed parent node and child direction, then at most one state history…
- prioritized_borel_eventually_visible_determined_positionalA determined prioritized tree game has a memoryless winner if, along every legal play, all but finitely many moves are uniquely determined…
- prioritized_borel_outgoing_edge_card_boundAt any fixed position in a finite-state game with k priorities there are at most 2k times the number of states legal outgoing edges.
- prioritized_borel_fork_all_winning_memorylessThe all-winning fork game has a winning strategy using one memory state.
- FiniteMemoryStrategyA structure FiniteMemoryStrategy {Q : Type*} {k : ℕ} (G : PrioritizedBorelGame Q k) (pl : BorelGamePlayer) (M : Type*) representing a…
- prioritized_borel_fork_all_winning_gameThe three-state fork arena with every priority branch set equal to the full branch space.
- has_winning_strategy_in_mem_monoIn 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…
- prioritized_borel_payoff_tail_congrTwo prioritized-game plays have the same payoff when their directions agree everywhere and their priorities agree eventually.
- prioritized_borel_dual_gameThe dual game exchanges the owners of every position and complements each winning branch set while leaving states, edges, and priorities…
- prioritized_borel_deterministic_opponent_memorylessIf every position controlled by Adam in a prioritized Borel game has at most one legal outgoing edge, then one of the players has a…
- HasWinningStrategyInMemThe proposition HasWinningStrategyInMem G m_bound asserts that for a prioritized Borel game G with state space Q and k priorities, there…
- prioritized_borel_reverse_edge_deterministic_positionalIf the current node and target state uniquely determine the previous state, and the node, source state, direction and target state…
- prioritized_borel_fork_game_strategy_fixed_branchFor every finite-memory Eve strategy in the all-winning three-state fork game, one infinite visible block sequence and one fixed memory…
- prioritized_borel_finite_hidden_opponent_choices_positionalFix a winning strategy in a prioritized tree game, with an arbitrary state type. Suppose that on every legal play, all but finitely many…
- PrioritizedBorelStrategyWinsA strategy wins for its player if every legal play from the initial position consistent with its memory update and choices is won by that…
- prioritized_borel_reverse_deterministic_finite_hidden_priorities_positionalConsider a prioritized tree game. Assume that any two legal edges at the same source node with the same direction and target state have…
- prioritized_borel_bounded_opponent_branching_compressionFix a winning strategy, possibly using infinite memory, in a finite-state prioritized tree game with k priorities. If along every legal…
Read back from the Lean
A structure PrioritizedBorelGame parameterized by a type Q and a natural number k, containing:
1. owner: a function mapping each pair (v, q) : List Bool × Q to a player in BorelGamePlayer (Eve or Adam);
2. init_state: an initial state in Q;
3. edges: a set of edges of type TreeGameEdge Q k;
4. edges_outgoing: a hypothesis that for every node v : List Bool and every state q : Q, there exists an edge e ∈ edges such that e.source_node = v and e.source_state = q;
5. winning_sets: a family of sets of infinite binary sequences winning_sets i ⊆ (ℕ → Bool) indexed by i : Fin k;
6. winning_measurable: a hypothesis that for every i : Fin k, the set winning_sets i is measurable (with respect to the standard measurable space on ℕ → Bool).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- A prioritized Borel game on the binary tree with state space Q and k priorities. -/ structure PrioritizedBorelGame (Q : Type*) (k : ℕ) where owner : List Bool × Q → BorelGamePlayer init_state : Q edges : Set (TreeGameEdge Q k) edges_outgoing : ∀ (v : List Bool) (q : Q), ∃ e ∈ edges, e.source_node = v ∧ e.source_state = q winning_sets : Fin k → Set (ℕ → Bool) winning_measurable : ∀ i, MeasurableSet (winning_sets i)