AFTD Auto-Formalizing Theoretical Domains

prioritized_borel_fork_run_append

theoremverified

Two finite legal fork runs can be concatenated when their intermediate states agree.

Statement

theorem prioritized_borel_fork_run_append {q r s : Fin 3} {xs ys : List PrioritizedBorelForkEdge}
    (h : PrioritizedBorelForkRun q xs r) (h' : PrioritizedBorelForkRun r ys s) :
    PrioritizedBorelForkRun q (xs ++ ys) s
Source
arXiv:2611.10136, Section 5.3.2; the three-state fork subarena
Verified
12 Nov 2026
Axioms
propext
Built on 3
Used by 1

The proof, explained

The theorem is proved by induction on the first run `h`. In the base case, the first run is empty, so its start and intermediate states coincide and the concatenated edge list simplifies directly to the second run `h'`. In the inductive step, the first run begins with a legal edge `e` followed by a tail run; rewriting list concatenation exposes `e` at the head, and applying the induction hypothesis to `h'` allows the run to be extended by `e`.

  1. The base case holds: concatenating an empty run with `h'` yields `h'`.

    We induct on the derivation of the first run `h`. In the base case (`nil`), the edge list is empty (`xs = []`), so the intermediate state equals the initial state (`q = r`). Because `[] ++ ys` simplifies to `ys`, the second run `h'` directly witnesses the required run from `q` to `s`.

    lines 4–5

      induction h with
      | nil => simpa using h'
  2. The inductive step holds: prepending the initial edge to the concatenated remaining runs produces a valid run from `q` to `s`.

    In the inductive step (`cons`), the first run begins with a legal edge `e` starting at `q`, followed by a run along `es` from `e.dst` to `r`. Rewriting with `List.cons_append` transforms `(e :: es) ++ ys` into `e :: (es ++ ys)`. Applying the induction hypothesis to `h'` gives a valid run along `es ++ ys` from `e.dst` to `s`. Finally, prepending `e` via `PrioritizedBorelForkRun.cons` completes the run from `q` to `s`.

    lines 6–8

    uses List.cons_append, PrioritizedBorelForkRun.cons

      | cons hlegal hsrc hrun ih =>
          simp only [List.cons_append]
          exact PrioritizedBorelForkRun.cons hlegal hsrc (ih h')
List.cons_append
Appending a list to a non-empty list satisfies `(a :: as) ++ bs = a :: (as ++ bs)`.
PrioritizedBorelForkRun.cons
If edge `e` is legal, has source `q`, and there is a valid run along `es` from `e.dst` to `s`, then `e :: es` is a valid run from `q` to `s`.

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_fork_run_append {q r s : Fin 3} {xs ys : List PrioritizedBorelForkEdge}    (h : PrioritizedBorelForkRun q xs r) (h' : PrioritizedBorelForkRun r ys s) :    PrioritizedBorelForkRun q (xs ++ ys) s := by  induction h with  | nil => simpa using h'  | cons hlegal hsrc hrun ih =>      simp only [List.cons_append]      exact PrioritizedBorelForkRun.cons hlegal hsrc (ih h')
See it in the graphDiscuss this resultChallenge it