prioritized_borel_fork_consistent_append
Consistency of concatenated histories splits into consistency before and after the cut, with the preceding history passed to the second part.
Statement
theorem prioritized_borel_fork_consistent_append (choice : List PrioritizedBorelForkEdge → Bool)
(pre xs ys : List PrioritizedBorelForkEdge) :
prioritized_borel_fork_consistent choice pre (xs ++ ys) ↔
prioritized_borel_fork_consistent choice pre xs ∧
prioritized_borel_fork_consistent choice (pre ++ xs) ys- Source
- arXiv:2611.10136, Section 5.3.2; the three-state fork subarena
- Verified
- 12 Nov 2026
- Axioms
propext- Built on 2
- PrioritizedBorelForkEdgeOne edge of the three-state fork arena, recording source, direction, target, and priority.
- 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…
- 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 theorem is proved by structural induction on the list xs, generalizing over the prefix history pre. In the base case where xs is empty, list concatenation and consistency simplify immediately to the consistency of ys. In the inductive step where xs = e :: es, unfolding consistency isolates the choice condition on the head edge e, after which applying the induction hypothesis with prefix pre ++ [e] and using the associativity of list concatenation and logical conjunction equates both sides.
The equivalence holds in the base case where xs is the empty list [].
We proceed by structural induction on the list xs, generalizing over the prefix history pre. When xs = [], the concatenation [] ++ ys evaluates to ys, and pre ++ [] evaluates to pre. By definition, consistency of the empty list is True, so both sides simplify to the consistency of ys with prefix pre, completing the base case.
uses
prioritized_borel_fork_consistentinduction xs generalizing pre with | nil => simp [prioritized_borel_fork_consistent]
The equivalence holds in the inductive step where xs is of the form e :: es.
In the inductive step, the induction hypothesis ih states that the equivalence holds for es under any prefix history. Unfolding the definition of prioritized_borel_fork_consistent on both sides extracts the consistency requirement on the head edge e (that if e.src = 2, then e.dir = choice pre). Applying the induction hypothesis specialized to the extended prefix pre ++ [e] decomposes the remainder into consistency of es and consistency of ys. Finally, associativity of list concatenation (List.append_assoc) rewrites (pre ++ [e]) ++ es to pre ++ (e :: es), and associativity of conjunction (and_assoc) equates both sides.
uses
prioritized_borel_fork_consistent,List.append_assoc,and_assoc| cons e es ih => simp [prioritized_borel_fork_consistent, ih, List.append_assoc, and_assoc]
prioritized_borel_fork_consistent- An edge history is consistent with a choice function starting from a prefix history if it is empty, or if its head edge agrees with the choice function whenever its source vertex is 2 and its tail is recursively consistent with the prefix extended by the head.
List.append_assoc- List concatenation is associative: (as ++ bs) ++ cs = as ++ (bs ++ cs).
and_assoc- Logical conjunction is associative: (a ∧ b) ∧ c ↔ a ∧ (b ∧ c).
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_consistent_append (choice : List PrioritizedBorelForkEdge → Bool) (pre xs ys : List PrioritizedBorelForkEdge) : prioritized_borel_fork_consistent choice pre (xs ++ ys) ↔ prioritized_borel_fork_consistent choice pre xs ∧ prioritized_borel_fork_consistent choice (pre ++ xs) ys := by induction xs generalizing pre with | nil => simp [prioritized_borel_fork_consistent] | cons e es ih => simp [prioritized_borel_fork_consistent, ih, List.append_assoc, and_assoc]