AFTD Auto-Formalizing Theoretical Domains

prioritized_borel_reverse_unique_state_trace

theoremverified

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.

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

    lines 6–10

      induction ht with
      | root =>
          intro ys hy
          cases hy
          rfl
  2. 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.

    lines 11–14

      | @step v q xs d q' ht hr ih =>
          intro ys hy
          cases hy with
          | step ht' hr' =>
  3. 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.

    lines 15–16

              have heq := hback v q _ d q' hr hr'
              subst_vars
  4. The 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.

    lines 17–18

              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

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