prioritized_borel_fork_expand_run
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
- PrioritizedBorelForkRunA finite path in the fork arena whose edges are legal and have matching endpoints.
- prioritized_borel_fork_block_runEach three-edge stay or excursion is a legal run from q back to q.
- prioritized_borel_fork_expandExpand equally indexed visible bits and hidden stay-or-excursion choices into three-edge blocks.
- prioritized_borel_fork_run_appendTwo finite legal fork runs can be concatenated when their intermediate states agree.
- PrioritizedBorelForkEdgeOne edge of the three-state fork arena, recording source, direction, target, and priority.
- prioritized_borel_fork_three_step_blockA three-edge stay or excursion with common output directions false, false, then the supplied bit.
- Used by 2
- prioritized_borel_fork_strategy_fixed_branchFor any history-dependent strategy and finite-memory assignment in the three-state fork arena, there are one infinite visible block…
- prioritized_borel_fork_unbounded_same_memoryFor any history-dependent excursion choice and finite-memory assignment, arbitrarily many distinct legal runs from q to q share their…
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.
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.
uses
PrioritizedBorelForkRun.nilinduction u generalizing h with | nil => simp [prioritized_borel_fork_expand, PrioritizedBorelForkRun.nil]
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.
uses
PrioritizedBorelForkRun.nil| cons b u ih => cases h with | nil => simp [prioritized_borel_fork_expand, PrioritizedBorelForkRun.nil]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.
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
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_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)