prioritized_borel_fork_expand_snoc
Appending a visible bit and hidden decision appends the corresponding three-edge block to the expanded history.
Statement
theorem prioritized_borel_fork_expand_snoc (u h : List Bool) (hlen : u.length = h.length)
(b c : Bool) :
prioritized_borel_fork_expand (u ++ [b]) (h ++ [c]) =
prioritized_borel_fork_expand u h ++ prioritized_borel_fork_three_step_block b c- Source
- arXiv:2611.10136, Section 5.3.2; the three-state fork subarena
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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.
- PrioritizedBorelForkEdgeOne edge of the three-state fork arena, recording source, direction, target, and priority.
- Used by 1
- prioritized_borel_fork_valid_consistentEvery valid hidden block history expands to an edge history consistent with the actual history-dependent p-owned choice function.
The proof, explained
The proof proceeds by induction on the visible bit list u, generalizing over the hidden decision list h. In the base case where u is empty, the length equality forces h to be empty as well, and both sides reduce to the three-step block for (b, c). In the inductive step, the length assumption eliminates the empty list for h and shows that the tails of u and h have equal length; expanding the definition of history expansion on both sides separates the leading block, and the induction hypothesis together with list concatenation associativity finishes the proof.
The identity holds in the base case where u is empty.
We proceed by induction on u, generalizing over h. When u = [], we case split on h. If h = [], expanding the definition of prioritized_borel_fork_expand reduces both sides to prioritized_borel_fork_three_step_block b c. If h is non-empty, the hypothesis |[]| = |h| implies that an empty list has the same length as a non-empty list, which is an immediate contradiction.
induction u generalizing h with | nil => cases h <;> simp_all [prioritized_borel_fork_expand]
In the inductive step with non-empty u, the list h cannot be empty.
For u = a :: u, we case split on h. If h = [], the equal-length hypothesis asserts (a :: u).length = 0, which is impossible because a :: u has length at least 1.
| cons a u ih => cases h with | nil => simp at hlenThe inductive step holds when h is also non-empty.
When h = x :: h, the tails u and h satisfy u.length = h.length since (a :: u).length = (x :: h).length. Unfolding the definition of prioritized_borel_fork_expand on both sides separates the leading block prioritized_borel_fork_three_step_block a x from the expansion of the tails. Rewriting the tail expansion using the induction hypothesis and applying the associativity of list concatenation (List.append_assoc) establishes the equality.
uses
List.append_assoc| cons x h => have hh : u.length = h.length := by simpa using hlen simp [prioritized_borel_fork_expand, ih h hh, List.append_assoc]
List.append_assoc- Concatenation of lists is associative: for any lists as, bs, and cs, (as ++ bs) ++ cs = as ++ (bs ++ cs).
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_snoc (u h : List Bool) (hlen : u.length = h.length) (b c : Bool) : prioritized_borel_fork_expand (u ++ [b]) (h ++ [c]) = prioritized_borel_fork_expand u h ++ prioritized_borel_fork_three_step_block b c := by induction u generalizing h with | nil => cases h <;> simp_all [prioritized_borel_fork_expand] | cons a u ih => cases h with | nil => simp at hlen | cons x h => have hh : u.length = h.length := by simpa using hlen simp [prioritized_borel_fork_expand, ih h hh, List.append_assoc]