prioritized_borel_outgoing_edge_card_bound
At any fixed position in a finite-state game with k priorities there are at most 2k times the number of states legal outgoing edges.
Statement
theorem prioritized_borel_outgoing_edge_card_bound {Q : Type} [Fintype Q] {k : ℕ} (G : PrioritizedBorelGame Q k) (v : List Bool) (q : Q) : Set.ncard {e : TreeGameEdge Q k | e ∈ G.edges ∧ e.source_node = v ∧ e.source_state = q} ≤ 2 * k * Fintype.card Q
- Source
- Finite branching bound for arXiv:2611.10136, Conjecture 19.
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- PrioritizedBorelGameA structure PrioritizedBorelGame (Q : Type*) (k : ℕ) representing a prioritized Borel game with state space Q and k priorities, with…
- 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 1
- 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…
The proof, explained
To bound the number of legal outgoing edges from a fixed tree node v and state q, we encode each edge by the triple of its direction, priority, and target state in Bool × Fin k × Q. Because the source node and source state are fixed to v and q for all edges at this position, this encoding is injective. Therefore, the number of such edges is at most the cardinality of Bool × Fin k × Q, which is 2 * k * |Q|.
Define the set S of outgoing edges from position v and state q, and define an encoding of edges into Bool × Fin k × Q.
We let S be the set of edges e in G with source_node = v and source_state = q. We define the function code mapping an edge e to the triple (e.dir, e.prio, e.target_state).
classical let S : Set (TreeGameEdge Q k) := {e | e ∈ G.edges ∧ e.source_node = v ∧ e.source_state = q} let code : TreeGameEdge Q k → Bool × Fin k × Q := fun e => (e.dir, e.prio, e.target_state)
The encoding map code is injective on S.
Let e and e' be edges in S such that code e = code e'. Because both edges belong to S, their source nodes both equal v and their source states both equal q. Furthermore, because their codes agree, applying congrArg to the components of the triple shows that e and e' share the same direction, priority, and target state. Since all five structural fields of the two edges coincide, the edges e and e' are equal.
uses
congrArg,Prod.fsthave hinj : Set.InjOn code S := by intro e he e' he' hc have hv : e.source_node = e'.source_node := he.2.1.trans he'.2.1.symm have hq : e.source_state = e'.source_state := he.2.2.trans he'.2.2.symm have hd : e.dir = e'.dir := congrArg Prod.fst hc have hp : e.prio = e'.prio := congrArg (fun x => x.2.1) hc have ht : e.target_state = e'.target_state := congrArg (fun x => x.2.2) hc cases e with | mk v1 q1 d1 p1 t1 => cases e' with | mk v2 q2 d2 p2 t2 => simp only at hv hq hd hp ht cases hv; cases hq; cases hd; cases hp; cases ht rfl
The cardinality of S is at most the cardinality of the universal set on Bool × Fin k × Q.
Every edge in S maps into the universal set Set.univ of Bool × Fin k × Q. Since code is injective on S and the codomain type is finite, Set.ncard_le_ncard_of_injOn bounds the cardinality of S by the cardinality of Set.univ.
uses
Set.ncard_le_ncard_of_injOn,Set.mem_univ,Set.toFinitehave hc := Set.ncard_le_ncard_of_injOn code (s := S) (t := Set.univ) (by intro e he; exact Set.mem_univ _) hinj (Set.toFinite _)
The number of outgoing edges from (v, q) is at most 2 * k * |Q|. automation
The cardinality of Set.univ for Bool × Fin k × Q simplifies to |Bool| * |Fin k| * |Q|, which evaluates to 2 * k * |Q| by product cardinality (Fintype.card_prod) and associativity of multiplication (Nat.mul_assoc).
uses
Fintype.card_prod,Nat.mul_assocsimpa [S, code, Fintype.card_prod, Nat.mul_assoc] using hc
congrArg- if two inputs are equal, applying any function to them produces equal outputs
Prod.fst- the first projection of an ordered pair
Set.ncard_le_ncard_of_injOn- if a function is injective from a set s into a finite set t, then the cardinality of s is at most that of t
Set.mem_univ- every element belongs to the universal set
Set.toFinite- a subset of a finite type is finite
Fintype.card_prod- the cardinality of the Cartesian product of two finite types is the product of their cardinalities
Nat.mul_assoc- multiplication of natural numbers is associative: (n * m) * k = n * (m * k)
- The simplifier automatically evaluates the cardinalities of `Bool` (as 2) and `Fin k` (as k).
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_outgoing_edge_card_bound {Q : Type} [Fintype Q] {k : ℕ} (G : PrioritizedBorelGame Q k) (v : List Bool) (q : Q) : Set.ncard {e : TreeGameEdge Q k | e ∈ G.edges ∧ e.source_node = v ∧ e.source_state = q} ≤ 2 * k * Fintype.card Q := by classical let S : Set (TreeGameEdge Q k) := {e | e ∈ G.edges ∧ e.source_node = v ∧ e.source_state = q} let code : TreeGameEdge Q k → Bool × Fin k × Q := fun e => (e.dir, e.prio, e.target_state) have hinj : Set.InjOn code S := by intro e he e' he' hc have hv : e.source_node = e'.source_node := he.2.1.trans he'.2.1.symm have hq : e.source_state = e'.source_state := he.2.2.trans he'.2.2.symm have hd : e.dir = e'.dir := congrArg Prod.fst hc have hp : e.prio = e'.prio := congrArg (fun x => x.2.1) hc have ht : e.target_state = e'.target_state := congrArg (fun x => x.2.2) hc cases e with | mk v1 q1 d1 p1 t1 => cases e' with | mk v2 q2 d2 p2 t2 => simp only at hv hq hd hp ht cases hv; cases hq; cases hd; cases hp; cases ht rfl have hc := Set.ncard_le_ncard_of_injOn code (s := S) (t := Set.univ) (by intro e he; exact Set.mem_univ _) hinj (Set.toFinite _) simpa [S, code, Fintype.card_prod, Nat.mul_assoc] using hc