prioritized_borel_reverse_unique_state_trace
If every transition relation has a unique source state for fixed reversed branch prefix, direction and target state, then two traces reaching the same branch and final state have identical state histories.
Statement
theorem prioritized_borel_reverse_unique_state_trace {Q : Type} (init : Q) (R : List Bool → Q → Bool → Q → Prop) (hback : ∀ v q1 q2 d q', R v q1 d q' → R v q2 d q' → q1 = q2) {v q xs} (ht : PrioritizedBorelStateTrace init R v q xs) : ∀ ys, PrioritizedBorelStateTrace init R v q ys → xs = ys
- Source
- arXiv:2611.10136, Section 5.2.4; reverse-unique state history lemma
- Verified
- 12 Nov 2026
- Axioms
- none — Lean reports it depends on no axioms
- Built on 1
- PrioritizedBorelStateTraceA state trace starts at the initial state and extends by a transition; the recorded branch and state sequence are stored in reverse order.
The proof, explained
The proof proceeds by induction on the derivation of the trace ht. In the base case, the branch prefix is empty, forcing any second trace to be the unique root trace [init]. In the inductive step, the backward determinism assumption (hback) implies that both traces transitioned from the exact same predecessor state, allowing the induction hypothesis to conclude that their earlier state histories coincide.
For the initial trace at the root, the state trace is uniquely determined as [init].
We proceed by induction on the derivation of the trace ht. In the base case (root), the branch prefix is empty and the final state is init, with state trace [init]. Given any second trace hy reaching the empty branch and state init, case analysis on hy shows that it must also be formed by the root constructor, giving ys = [init], which holds by definition.
induction ht with | root => intro ys hy cases hy rfl
In the inductive step, any second trace ending at the same branch and state must also arise from a step transition.
In the inductive step, the trace ht extends a predecessor trace xs ending at state q via a transition along direction d to reach state q', resulting in branch d :: v. Given another trace hy reaching d :: v and state q', case analysis on hy shows that it cannot be a root (since the branch is non-empty) and must also be formed by a step transition from some predecessor state with trace qs.
| @step v q xs d q' ht hr ih => intro ys hy cases hy with | step ht' hr' =>The predecessor state in the second trace must equal q.
The hypothesis hback states that the source state of a transition is uniquely determined by the branch prefix, direction, and target state. Applying hback to the transitions of both traces shows that the predecessor state in the second trace equals q. Substituting this equality identifies the two predecessor states.
have heq := hback v q _ d q' hr hr' subst_varsThe full state traces are identical.
Because both traces share the same head state q', congruence reduces the goal to showing that their tails are equal (xs = qs). This equality follows immediately from the induction hypothesis applied to the predecessor trace of hy.
congr 1 exact ih _ ht'
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_reverse_unique_state_trace {Q : Type} (init : Q) (R : List Bool → Q → Bool → Q → Prop) (hback : ∀ v q1 q2 d q', R v q1 d q' → R v q2 d q' → q1 = q2) {v q xs} (ht : PrioritizedBorelStateTrace init R v q xs) : ∀ ys, PrioritizedBorelStateTrace init R v q ys → xs = ys := by induction ht with | root => intro ys hy cases hy rfl | @step v q xs d q' ht hr ih => intro ys hy cases hy with | step ht' hr' => have heq := hback v q _ d q' hr hr' subst_vars congr 1 exact ih _ ht'