prioritized_borel_fork_expand_directions
Expanding equally long block histories has directions false, false, then the visible bit in each block.
Statement
theorem prioritized_borel_fork_expand_directions (u h : List Bool) (hlen : u.length = h.length) : (prioritized_borel_fork_expand u h).map PrioritizedBorelForkEdge.dir = u.flatMap (fun b => [false, false, b])
- Source
- arXiv:2611.10136, Section 5.3.2; the three-state fork subarena
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- PrioritizedBorelForkEdgeOne edge of the three-state fork arena, recording source, direction, target, and priority.
- prioritized_borel_fork_expandExpand equally indexed visible bits and hidden stay-or-excursion choices into three-edge blocks.
- 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 proof proceeds by induction on the list $u$ while generalizing over the history $h$. In the base case where $u$ is empty, the length equality forces $h$ to be empty as well, so both sides evaluate to the empty list. In the inductive step with $u = b :: u'$, the length equality similarly requires $h = c :: h'$ with $|u'| = |h'|$. A case split on the boolean control bit $c$ confirms that in both branches the three-step block yields directions false, false, and $b$, allowing the induction hypothesis on the tails to complete the equality.
The claim holds when $u$ is the empty list.
We proceed by induction on $u$, generalizing over $h$. In the base case $u = []$, we inspect the list $h$. If $h = []$, expanding both empty lists produces an empty list of edges, so both sides evaluate to the empty list. If $h$ is non-empty, the length hypothesis $0 = |h|$ is a contradiction.
uses
prioritized_borel_fork_expandinduction u generalizing h with | nil => cases h <;> simp_all [prioritized_borel_fork_expand]
In the inductive step where $u = b :: u'$, the list $h$ cannot be empty.
Assuming the induction hypothesis holds for $u'$, we consider $u = b :: u'$ and case-split on $h$. If $h = []$, the length equality $|b :: u'| = |[]|$ asserts $|u'| + 1 = 0$, which is impossible.
| cons b u ih => cases h with | nil => simp at hlenWhen $h = c :: h'$, the tails $u'$ and $h'$ have equal length.
When $h$ has head $c$ and tail $h'$, simplifying the length equality $|b :: u'| = |c :: h'|$ by cancelling the head elements gives $|u'| = |h'|$, providing the premise needed to apply the induction hypothesis to the tails.
| cons c h => have hh : u.length = h.length := by simpa using hlenThe direction map identity holds for the prepended lists $b :: u'$ and $c :: h'$.
We split into cases on whether the boolean exit flag $c$ is false or true. In both cases, the three edges created by `prioritized_borel_fork_three_step_block b c` have directions false, false, and $b$. Unfolding `prioritized_borel_fork_expand`, mapping the direction projection over the three-step block, and applying the induction hypothesis to the tails shows that the resulting list of directions is $[\text{false}, \text{false}, b] ++ u'.\text{flatMap}(\dots) = (b :: u').\text{flatMap}(\dots)$.
uses
prioritized_borel_fork_expand,prioritized_borel_fork_three_step_blockcases c <;> simp [prioritized_borel_fork_expand, prioritized_borel_fork_three_step_block, ih h hh]
prioritized_borel_fork_expand- Recursively constructs a list of prioritized Borel fork edges from a list of visible bits and a list of exit flags by producing a three-step block for each pair of elements.
prioritized_borel_fork_three_step_block- Constructs a sequence of three prioritized Borel fork edges given a visible bit and an exit flag; the directions of the three edges are false, false, and the visible bit.
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_directions (u h : List Bool) (hlen : u.length = h.length) : (prioritized_borel_fork_expand u h).map PrioritizedBorelForkEdge.dir = u.flatMap (fun b => [false, false, b]) := by induction u generalizing h with | nil => cases h <;> simp_all [prioritized_borel_fork_expand] | cons b u ih => cases h with | nil => simp at hlen | cons c h => have hh : u.length = h.length := by simpa using hlen cases c <;> simp [prioritized_borel_fork_expand, prioritized_borel_fork_three_step_block, ih h hh]