AFTD Auto-Formalizing Theoretical Domains

prioritized_borel_reverse_state_histories_unique

theoremverified

If a tree-game edge is reverse-deterministic in the state at each fixed parent node and child direction, then at most one state history reaches any fixed node and final state.

Statement

theorem prioritized_borel_reverse_state_histories_unique {Q : Type} {k : ℕ}
    (G : PrioritizedBorelGame Q k)
    (hback : ∀ e ∈ G.edges, ∀ e' ∈ G.edges,
      e.source_node = e'.source_node → e.dir = e'.dir →
      e.target_state = e'.target_state → e.source_state = e'.source_state)
    (v : List Bool) (q : Q) : (op1385StateHistories G v q).Subsingleton
Source
Structural step related to 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 2

The proof, explained

To show that the set of state histories reaching a given node v and final state q contains at most one element, we assume two valid histories h and h' and show they coincide pointwise. We proceed by backward induction on the distance j from the target node, proving that h(|v| - j) = h'(|v| - j) for all j ≤ |v|. The base case j = 0 holds because both histories end in q, and the induction step follows from the reverse-determinism hypothesis, which forces the predecessor states to match once the target states, source nodes, and directions match. Function extensionality then concludes that h = h'.

  1. To show that the set of state histories is a subsingleton, it suffices to prove that any two valid state histories h and h' are equal.

    We introduce arbitrary state histories h and h' belonging to op1385StateHistories G v q. Subsingleton means that any two elements in the set are identical, reducing the goal to h = h'.

    line 16

      intro h hh h' hh'
  2. In the base case j = 0 of backward induction, both histories agree at the final index: h(|v|) = h'(|v|) = q.

    We formulate a backward induction on the distance j from the end of the path (0 ≤ j ≤ |v|) to show h(|v| - j) = h'(|v| - j). For the base case j = 0, the index |v| - 0 is the final position Fin.last |v|. By the definition of state histories, h(Fin.last |v|) = q and h'(Fin.last |v|) = q, so transitivity immediately yields h(|v|) = h'(|v|).

    lines 17–26

    uses Fin.ext

      have hrev : ∀ j : ℕ, ∀ hj : j ≤ v.length,
          h ⟨v.length - j, by omega⟩ = h' ⟨v.length - j, by omega⟩ := by
        intro j
        induction j with
        | zero =>
          intro hj
          have hz : (⟨v.length - 0, by omega⟩ : Fin (v.length + 1)) = Fin.last v.length := by
            apply Fin.ext
            simp
          simpa only [hz] using hh.2.1.trans hh'.2.1.symm
  3. In the inductive step, if h and h' agree at position |v| - j, then they also agree at position |v| - (j + 1).

    Let i = |v| - (j + 1). By the definition of valid state histories, h and h' each traverse a tree game edge (e and e' respectively) from source node v.take i in direction v[i], with source states h(i) and h'(i) and target states h(i + 1) and h'(i + 1). Since i + 1 = |v| - j, the induction hypothesis applies to show e.target_state = e'.target_state. Because e and e' share the same source node, direction, and target state, the reverse-determinism hypothesis hback implies their source states must coincide: h(i) = e.source_state = e'.source_state = h'(i).

    lines 27–38

    uses Fin.ext

        | succ j ih =>
          intro hj
          let i : Fin v.length := ⟨v.length - (j + 1), by omega⟩
          obtain ⟨e, he, hen, hes, hed, het⟩ := hh.2.2 i
          obtain ⟨e', he', hen', hes', hed', het'⟩ := hh'.2.2 i
          have ht : e.target_state = e'.target_state := by
            rw [het, het']
            have hprev := ih (by omega)
            convert hprev using 1 <;> congr 1 <;> apply Fin.ext <;> simp [i] <;> omega
          have hs := hback e he e' he' (hen.trans hen'.symm) (hed.trans hed'.symm) ht
          rw [hes, hes'] at hs
          exact hs
  4. The state histories h and h' are equal everywhere, so h = h'.

    By function extensionality, h = h' follows once h(i) = h'(i) for every index i. Specializing the backward induction result with j = |v| - i yields h(|v| - (|v| - i)) = h'(|v| - (|v| - i)), which simplifies to h(i) = h'(i) because |v| - (|v| - i) = i.

    lines 39–41

    uses Fin.ext

      funext i
      have h := hrev (v.length - i.val) (by omega)
      convert h using 1 <;> congr 1 <;> apply Fin.ext <;> simp <;> omega
Fin.ext
Two elements of Fin n are equal if and only if their underlying natural numbers are equal.

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

open Setset_option maxHeartbeats 1000000def op1385StateHistories {Q : Type} {k : ℕ} (G : PrioritizedBorelGame Q k)    (v : List Bool) (q : Q) : Set (Fin (v.length + 1) → Q) :=  {h | h 0 = G.init_state ∧ h (Fin.last v.length) = q ∧    ∀ i : Fin v.length, ∃ e ∈ G.edges, e.source_node = v.take i.val ∧      e.source_state = h i.castSucc ∧ e.dir = v.get i ∧ e.target_state = h i.succ}theorem prioritized_borel_reverse_state_histories_unique {Q : Type} {k : ℕ}    (G : PrioritizedBorelGame Q k)    (hback : ∀ e ∈ G.edges, ∀ e' ∈ G.edges,      e.source_node = e'.source_node → e.dir = e'.dir →      e.target_state = e'.target_state → e.source_state = e'.source_state)    (v : List Bool) (q : Q) : (op1385StateHistories G v q).Subsingleton := by  intro h hh h' hh'  have hrev : ∀ j : ℕ, ∀ hj : j ≤ v.length,      h ⟨v.length - j, by omega⟩ = h' ⟨v.length - j, by omega⟩ := by    intro j    induction j with    | zero =>      intro hj      have hz : (⟨v.length - 0, by omega⟩ : Fin (v.length + 1)) = Fin.last v.length := by        apply Fin.ext        simp      simpa only [hz] using hh.2.1.trans hh'.2.1.symm    | succ j ih =>      intro hj      let i : Fin v.length := ⟨v.length - (j + 1), by omega⟩      obtain ⟨e, he, hen, hes, hed, het⟩ := hh.2.2 i      obtain ⟨e', he', hen', hes', hed', het'⟩ := hh'.2.2 i      have ht : e.target_state = e'.target_state := by        rw [het, het']        have hprev := ih (by omega)        convert hprev using 1 <;> congr 1 <;> apply Fin.ext <;> simp [i] <;> omega      have hs := hback e he e' he' (hen.trans hen'.symm) (hed.trans hed'.symm) ht      rw [hes, hes'] at hs      exact hs  funext i  have h := hrev (v.length - i.val) (by omega)  convert h using 1 <;> congr 1 <;> apply Fin.ext <;> simp <;> omega
See it in the graphDiscuss this resultChallenge it