prioritized_borel_fork_valid_consistent
Every valid hidden block history expands to an edge history consistent with the actual history-dependent p-owned choice function.
Statement
theorem prioritized_borel_fork_valid_consistent (choice : List PrioritizedBorelForkEdge → Bool) {u h : List Bool} (hv : PrioritizedBorelForkValid (fun v k => choice (prioritized_borel_fork_expand v k ++ prioritized_borel_fork_setup)) u h) : prioritized_borel_fork_consistent choice [] (prioritized_borel_fork_expand u h)
- Source
- arXiv:2611.10136, Section 5.3.2; the three-state fork subarena
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 11
- PrioritizedBorelForkEdgeOne edge of the three-state fork arena, recording source, direction, target, and priority.
- PrioritizedBorelForkValidBlockwise histories: every history may stay for an arbitrary visible bit, or take a hidden excursion only when the strategy chooses that…
- prioritized_borel_fork_consistentA finite edge history is consistent with a history-dependent choice function when every p-owned edge uses the direction the function…
- prioritized_borel_fork_consistent_appendConsistency of concatenated histories splits into consistency before and after the cut, with the preceding history passed to the second…
- prioritized_borel_fork_exit_consistentAn excursion block is consistent when its last direction is the function's choice after the first two edges.
- prioritized_borel_fork_expandExpand equally indexed visible bits and hidden stay-or-excursion choices into three-edge blocks.
- prioritized_borel_fork_expand_snocAppending a visible bit and hidden decision appends the corresponding three-edge block to the expanded history.
- prioritized_borel_fork_setupThe first two forced edges of a fork excursion.
- prioritized_borel_fork_stay_consistentA stay block is consistent with every p-owned choice function.
- prioritized_borel_fork_valid_lengthsIn each compatible block history the visible and hidden histories have equal length.
- 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_strategy_obstructionFor any history-dependent strategy and any finite-memory assignment, arbitrarily many distinct legal strategy-consistent runs return to q…
The proof, explained
The theorem is proved by induction on the validity hypothesis for the block histories. The base case of empty histories expands to the empty edge sequence, which is vacuously consistent. In each inductive step, expanding the snoc-extended histories yields the prefix expansion followed by a three-step block; consistency decomposes across this concatenation, where the prefix is consistent by the induction hypothesis, and the block is consistent either vacuously (in the stay case) or by matching the choice function at vertex 2 (in the exit case).
The expanded history is consistent in the base case where both block histories are empty.
The proof proceeds by induction on the derivation of validity `hv`. In the base case `root`, both block histories `u` and `h` are empty lists. Unfolding `prioritized_borel_fork_expand` on empty lists produces the empty edge list, which is vacuously consistent with `choice` by definition of `prioritized_borel_fork_consistent`.
induction hv with | root => simp [prioritized_borel_fork_expand, prioritized_borel_fork_consistent]
Consistency is preserved when extending valid histories with a stay block.
In the `stay` case, the histories are extended to `u ++ [bit]` and `h ++ [false]`. Since valid histories have equal lengths by `prioritized_borel_fork_valid_lengths`, `prioritized_borel_fork_expand_snoc` expands this into the previous expansion followed by a three-step stay block. By `prioritized_borel_fork_consistent_append`, consistency of the concatenated history reduces to consistency of the prefix and consistency of the stay block after simplifying the empty initial prefix with `List.nil_append`. The prefix is consistent by the induction hypothesis `ih`, and the stay block is consistent by `prioritized_borel_fork_stay_consistent` since it never visits vertex 2.
uses
prioritized_borel_fork_expand_snoc,prioritized_borel_fork_valid_lengths,prioritized_borel_fork_consistent_append,List.nil_append,prioritized_borel_fork_stay_consistent| @stay u h bit hv ih => rw [prioritized_borel_fork_expand_snoc u h (prioritized_borel_fork_valid_lengths hv), prioritized_borel_fork_consistent_append] simp only [List.nil_append] exact ⟨ih, prioritized_borel_fork_stay_consistent choice _ bit⟩Consistency is preserved when extending valid histories with an exit block.
In the `exit` case, the histories are extended to `u ++ [color u h]` and `h ++ [true]`, where `color u h` is defined as `choice` applied to the expansion of `(u, h)` followed by the setup edges. Using `prioritized_borel_fork_valid_lengths` and `prioritized_borel_fork_expand_snoc`, the expansion decomposes into the expansion of the prefix followed by a three-step exit block. Decomposing consistency with `prioritized_borel_fork_consistent_append` and simplifying the prefix with `List.nil_append`, the prefix is consistent by `ih`, and the exit block is consistent by `prioritized_borel_fork_exit_consistent` because its direction at vertex 2 is exactly what the choice function requires.
uses
prioritized_borel_fork_expand_snoc,prioritized_borel_fork_valid_lengths,prioritized_borel_fork_consistent_append,List.nil_append,prioritized_borel_fork_exit_consistent| @exit u h hv ih => rw [prioritized_borel_fork_expand_snoc u h (prioritized_borel_fork_valid_lengths hv), prioritized_borel_fork_consistent_append] simp only [List.nil_append] exact ⟨ih, prioritized_borel_fork_exit_consistent choice _⟩
prioritized_borel_fork_expand_snoc- Appending elements to equal-length block histories expands to the expansion of the prefixes concatenated with the three-step block corresponding to the new elements.
prioritized_borel_fork_valid_lengths- Any valid pair of block histories has equal lengths.
prioritized_borel_fork_consistent_append- A sequence of edges is consistent after a given prefix if and only if its first part is consistent after the prefix and its second part is consistent after the prefix extended by the first part.
List.nil_append- Prepending an empty list to any list leaves the list unchanged.
prioritized_borel_fork_stay_consistent- A three-step stay block is consistent after any prefix, because none of its edges originate at vertex 2.
prioritized_borel_fork_exit_consistent- A three-step exit block is consistent when its decision bit at vertex 2 matches the value of the choice function on the prefix extended by the setup edges.
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_consistent (choice : List PrioritizedBorelForkEdge → Bool) {u h : List Bool} (hv : PrioritizedBorelForkValid (fun v k => choice (prioritized_borel_fork_expand v k ++ prioritized_borel_fork_setup)) u h) : prioritized_borel_fork_consistent choice [] (prioritized_borel_fork_expand u h) := by induction hv with | root => simp [prioritized_borel_fork_expand, prioritized_borel_fork_consistent] | @stay u h bit hv ih => rw [prioritized_borel_fork_expand_snoc u h (prioritized_borel_fork_valid_lengths hv), prioritized_borel_fork_consistent_append] simp only [List.nil_append] exact ⟨ih, prioritized_borel_fork_stay_consistent choice _ bit⟩ | @exit u h hv ih => rw [prioritized_borel_fork_expand_snoc u h (prioritized_borel_fork_valid_lengths hv), prioritized_borel_fork_consistent_append] simp only [List.nil_append] exact ⟨ih, prioritized_borel_fork_exit_consistent choice _⟩