prioritized_borel_fork_block_run
Each three-edge stay or excursion is a legal run from q back to q.
Statement
theorem prioritized_borel_fork_block_run (b c : Bool) : PrioritizedBorelForkRun 0 (prioritized_borel_fork_three_step_block b c) 0- Source
- arXiv:2611.10136, Section 5.3.2; the three-state fork subarena
- Verified
- 12 Nov 2026
- Axioms
Quot.soundpropext- Built on 4
- PrioritizedBorelForkRunA finite path in the fork arena whose edges are legal and have matching endpoints.
- prioritized_borel_fork_is_legalThe legal edges of the three-state fork subarena, including both q self-loop directions and the q-to-hat-to-p-to-q excursion.
- 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_expand_runEvery expanded sequence of paired blocks is a legal run from q back to q.
The proof, explained
The proof proceeds by exhaustively checking all four boolean combinations of b and c. In each case, the three-step block definition simplifies to an explicit sequence of three edges: either three self-loops at state 0 (a stay) or a cycle visiting states 1 and 2 before returning to 0 (an excursion). We decompose each sequence into a valid run using the inductive constructors for runs, matching intermediate states by reflexivity, and conclude by verifying the legality of all twelve individual transitions via automated evaluation.
In each of the four boolean combinations of b and c, the three-step block simplifies to an explicit list of three edges.
We perform a case split on the boolean variables b and c, yielding four cases. In each case, simplifying the definition of prioritized_borel_fork_three_step_block evaluates the if-then-else conditions (using Bool.false_eq_true to eliminate false = true branches), producing an explicit three-edge path starting and ending at state 0: either three self-loops at state 0 (when c is false) or the excursion 0 → 1 → 2 → 0 (when c is true).
uses
Bool.false_eq_truecases b <;> cases c <;> simp only [prioritized_borel_fork_three_step_block, Bool.false_eq_true, ↓reduceIte] <;>
Each of the four paths forms a valid run from state 0 back to state 0, provided each individual edge is legal.
We decompose each three-edge path into a sequence of run transitions by applying PrioritizedBorelForkRun.cons three times and terminating with PrioritizedBorelForkRun.nil. At each transition, the source of the edge aligns with the current state by reflexivity (rfl), leaving three legality subgoals for each of the four cases (twelve subgoals in total).
uses
PrioritizedBorelForkRun.cons,PrioritizedBorelForkRun.nilrefine PrioritizedBorelForkRun.cons ?_ rfl (PrioritizedBorelForkRun.cons ?_ rfl (PrioritizedBorelForkRun.cons ?_ rfl (PrioritizedBorelForkRun.nil _))) <;>
Every edge transition across the four paths is legal. automation
The norm_num tactic unfolds the definition of prioritized_borel_fork_is_legal and evaluates the equalities on state indices, edge directions, and priority values for each of the twelve edges, verifying that each edge satisfies the definition.
norm_num [prioritized_borel_fork_is_legal]
Bool.false_eq_true- The equality false = true is false: (false = true) = False.
PrioritizedBorelForkRun.cons- Prepending a legal edge e with source q to a valid run from e's destination to s produces a valid run from q to s.
PrioritizedBorelForkRun.nil- The empty sequence of edges forms a valid run from any state q to itself.
- The verification that all twelve individual edges satisfy the legality condition is discharged entirely by norm_num via finite case analysis on the definition.
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_block_run (b c : Bool) : PrioritizedBorelForkRun 0 (prioritized_borel_fork_three_step_block b c) 0 := by cases b <;> cases c <;> simp only [prioritized_borel_fork_three_step_block, Bool.false_eq_true, ↓reduceIte] <;> refine PrioritizedBorelForkRun.cons ?_ rfl (PrioritizedBorelForkRun.cons ?_ rfl (PrioritizedBorelForkRun.cons ?_ rfl (PrioritizedBorelForkRun.nil _))) <;> norm_num [prioritized_borel_fork_is_legal]