prioritized_borel_reverse_state_histories_unique
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
- 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_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…
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'.
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'.
intro h hh h' hh'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|).
uses
Fin.exthave 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
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).
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 hsThe 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.
uses
Fin.extfunext 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.
- In Lean, positions in a path of length |v| are represented by elements of the subtype Fin (|v| + 1). Arithmetic adjustments such as (|v| - (j + 1)) + 1 = |v| - j and |v| - (|v| - i) = i are handled formally by omega, simp, and Fin.ext, but are treated as implicit in informal proofs.
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.
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