AFTD Auto-Formalizing Theoretical Domains

prioritized_borel_outgoing_edge_card_bound

theoremverified

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

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|.

  1. 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).

    lines 5–8

      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)
  2. 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.

    lines 9–22

    uses congrArg, Prod.fst

      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
  3. 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.

    lines 23–24

    uses Set.ncard_le_ncard_of_injOn, Set.mem_univ, Set.toFinite

      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 _)
  4. 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).

    line 25

    uses Fintype.card_prod, Nat.mul_assoc

      simpa [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)

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_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
See it in the graphDiscuss this resultChallenge it