AFTD Auto-Formalizing Theoretical Domains

prioritized_borel_fork_block_run

theoremverified

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
Used by 1

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.

  1. 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).

    lines 2–3

    uses Bool.false_eq_true

      cases b <;> cases c <;>
        simp only [prioritized_borel_fork_three_step_block, Bool.false_eq_true, ↓reduceIte] <;>
  2. 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).

    lines 4–5

    uses PrioritizedBorelForkRun.cons, PrioritizedBorelForkRun.nil

        refine PrioritizedBorelForkRun.cons ?_ rfl (PrioritizedBorelForkRun.cons ?_ rfl
          (PrioritizedBorelForkRun.cons ?_ rfl (PrioritizedBorelForkRun.nil _))) <;>
  3. 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.

    line 6

        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.

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

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]
See it in the graphDiscuss this resultChallenge it