AFTD Auto-Formalizing Theoretical Domains

prioritized_borel_fork_expand_run

theoremverified

Every expanded sequence of paired blocks is a legal run from q back to q.

Statement

theorem prioritized_borel_fork_expand_run (u h : List Bool) :
    PrioritizedBorelForkRun 0 (prioritized_borel_fork_expand u h) 0
Source
arXiv:2611.10136, Section 5.3.2; the three-state fork subarena
Verified
12 Nov 2026
Axioms
Quot.soundpropext
Built on 6
Used by 2

The proof, explained

The theorem is proved by induction on the list u, generalizing over h. If either u or h is empty, the expansion produces an empty list of edges, which is a trivial run from state 0 to state 0. When both lists are non-empty, the expanded list is the concatenation of a three-step block and the recursive expansion of their tails. Since each three-step block is a legal run from state 0 to state 0 and the recursive call is also a run from state 0 to state 0 by the induction hypothesis, concatenating them yields a legal run from state 0 to state 0.

  1. The empty list expansion prioritized_borel_fork_expand [] h is a legal run from state 0 to state 0.

    We induct on the list u, generalizing over h. In the base case where u = [], the function prioritized_borel_fork_expand [] h evaluates by definition to the empty list [], which is a legal run from state 0 to state 0 by PrioritizedBorelForkRun.nil.

    lines 3–4

    uses PrioritizedBorelForkRun.nil

      induction u generalizing h with
      | nil => simp [prioritized_borel_fork_expand, PrioritizedBorelForkRun.nil]
  2. In the inductive step where u = b :: u', the claim holds when h is the empty list.

    Assuming the induction hypothesis for u', we perform case analysis on h. When h = [], prioritized_borel_fork_expand (b :: u') [] simplifies by definition to [], which is again a legal run from state 0 to state 0 by PrioritizedBorelForkRun.nil.

    lines 5–7

    uses PrioritizedBorelForkRun.nil

      | cons b u ih =>
          cases h with
          | nil => simp [prioritized_borel_fork_expand, PrioritizedBorelForkRun.nil]
  3. In the inductive step where u = b :: u', the claim holds when h = c :: h'.

    When h = c :: h', prioritized_borel_fork_expand (b :: u') (c :: h') unfolds by definition into the concatenation of the three-step block prioritized_borel_fork_three_step_block b c and the recursively expanded tail prioritized_borel_fork_expand u' h'. The block is a legal run from state 0 to state 0 by prioritized_borel_fork_block_run, and the tail is a legal run from state 0 to state 0 by the induction hypothesis on h'. Concatenating these two runs via prioritized_borel_fork_run_append completes the inductive step.

    lines 8–10

    uses prioritized_borel_fork_run_append, prioritized_borel_fork_block_run

          | cons c h =>
              simp only [prioritized_borel_fork_expand]
              exact prioritized_borel_fork_run_append (prioritized_borel_fork_block_run b c) (ih h)
PrioritizedBorelForkRun.nil
For any state q, the empty list of edges is a legal run from q to q.
prioritized_borel_fork_block_run
For any booleans b and c, the three-step block defined by prioritized_borel_fork_three_step_block b c is a legal run from state 0 to state 0.
prioritized_borel_fork_run_append
If xs is a legal run from q to r and ys is a legal run from r to s, then their concatenation xs ++ ys is a legal 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_expand_run (u h : List Bool) :    PrioritizedBorelForkRun 0 (prioritized_borel_fork_expand u h) 0 := by  induction u generalizing h with  | nil => simp [prioritized_borel_fork_expand, PrioritizedBorelForkRun.nil]  | cons b u ih =>      cases h with      | nil => simp [prioritized_borel_fork_expand, PrioritizedBorelForkRun.nil]      | cons c h =>          simp only [prioritized_borel_fork_expand]          exact prioritized_borel_fork_run_append (prioritized_borel_fork_block_run b c) (ih h)
See it in the graphDiscuss this resultChallenge it