prioritized_borel_fork_run_append
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
- PrioritizedBorelForkEdgeOne edge of the three-state fork arena, recording source, direction, target, and priority.
- PrioritizedBorelForkRunA finite path in the fork arena whose edges are legal and have matching endpoints.
- prioritized_borel_fork_is_legalThe legal edges of the three-state fork subarena, including both q self-loop directions and the q-to-hat-to-p-to-q excursion.
- Used by 1
- prioritized_borel_fork_expand_runEvery expanded sequence of paired blocks is a legal run from q back to q.
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`.
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`.
induction h with | nil => simpa using h'
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`.
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
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_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')