prioritized_borel_fork_valid_lengths
In each compatible block history the visible and hidden histories have equal length.
Statement
theorem prioritized_borel_fork_valid_lengths {color : List Bool → List Bool → Bool} {u h : List Bool}
(hv : PrioritizedBorelForkValid color u h) : u.length = h.length- Source
- arXiv:2611.10136, Section 5.3.2, smallest lower-bound arena; three-move fork obstruction
- Verified
- 12 Nov 2026
- Axioms
propext- Built on 1
- PrioritizedBorelForkValidBlockwise histories: every history may stay for an arbitrary visible bit, or take a hidden excursion only when the strategy chooses that…
- Used by 3
- 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_valid_consistentEvery valid hidden block history expands to an edge history consistent with the actual history-dependent p-owned choice function.
- 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 derivation of `PrioritizedBorelForkValid color u h`. In the base case (`root`), both histories are empty, so both lengths are trivially zero. In both inductive steps (`stay` and `exit`), exactly one boolean value is appended to each history, increasing both lengths by one and preserving their equality by the induction hypothesis.
In the base case, the visible and hidden histories are empty, so their lengths are equal.
We proceed by induction on the validity derivation of `PrioritizedBorelForkValid color u h`. In the base case (`root`), both the visible history `u` and the hidden history `h` are the empty list `[]`. Both have length 0, so the equality `[].length = [].length` holds by definition.
induction hv with | root => rfl
The length equality is preserved when extending histories via the `stay` constructor.
In the `stay` case, the visible history is extended by a boolean `bit` to `u ++ [bit]`, and the hidden history is extended by `false` to `h ++ [false]`. Appending one element increases the length of each list by 1. By the induction hypothesis `ih` (`u.length = h.length`), the new lengths `u.length + 1` and `h.length + 1` are equal.
| stay bit hv ih => simp [ih]The length equality is preserved when extending histories via the `exit` constructor.
In the `exit` case, the visible history is extended by `color u h` to `u ++ [color u h]`, and the hidden history is extended by `true` to `h ++ [true]`. As in the `stay` case, exactly one element is appended to each list, so both lengths increase by 1, and equality follows immediately from the induction hypothesis `ih`.
| exit hv ih => simp [ih]
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_valid_lengths {color : List Bool → List Bool → Bool} {u h : List Bool} (hv : PrioritizedBorelForkValid color u h) : u.length = h.length := by induction hv with | root => rfl | stay bit hv ih => simp [ih] | exit hv ih => simp [ih]