AFTD Auto-Formalizing Theoretical Domains

prioritized_borel_fork_expand_directions

theoremverified

Expanding equally long block histories has directions false, false, then the visible bit in each block.

Statement

theorem prioritized_borel_fork_expand_directions (u h : List Bool) (hlen : u.length = h.length) :
    (prioritized_borel_fork_expand u h).map PrioritizedBorelForkEdge.dir =
      u.flatMap (fun b => [false, false, b])
Source
arXiv:2611.10136, Section 5.3.2; the three-state fork subarena
Verified
12 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
Used by 2

The proof, explained

The proof proceeds by induction on the list $u$ while generalizing over the history $h$. In the base case where $u$ is empty, the length equality forces $h$ to be empty as well, so both sides evaluate to the empty list. In the inductive step with $u = b :: u'$, the length equality similarly requires $h = c :: h'$ with $|u'| = |h'|$. A case split on the boolean control bit $c$ confirms that in both branches the three-step block yields directions false, false, and $b$, allowing the induction hypothesis on the tails to complete the equality.

  1. The claim holds when $u$ is the empty list.

    We proceed by induction on $u$, generalizing over $h$. In the base case $u = []$, we inspect the list $h$. If $h = []$, expanding both empty lists produces an empty list of edges, so both sides evaluate to the empty list. If $h$ is non-empty, the length hypothesis $0 = |h|$ is a contradiction.

    lines 4–5

    uses prioritized_borel_fork_expand

      induction u generalizing h with
      | nil => cases h <;> simp_all [prioritized_borel_fork_expand]
  2. In the inductive step where $u = b :: u'$, the list $h$ cannot be empty.

    Assuming the induction hypothesis holds for $u'$, we consider $u = b :: u'$ and case-split on $h$. If $h = []$, the length equality $|b :: u'| = |[]|$ asserts $|u'| + 1 = 0$, which is impossible.

    lines 6–8

      | cons b u ih =>
          cases h with
          | nil => simp at hlen
  3. When $h = c :: h'$, the tails $u'$ and $h'$ have equal length.

    When $h$ has head $c$ and tail $h'$, simplifying the length equality $|b :: u'| = |c :: h'|$ by cancelling the head elements gives $|u'| = |h'|$, providing the premise needed to apply the induction hypothesis to the tails.

    lines 9–10

          | cons c h =>
              have hh : u.length = h.length := by simpa using hlen
  4. The direction map identity holds for the prepended lists $b :: u'$ and $c :: h'$.

    We split into cases on whether the boolean exit flag $c$ is false or true. In both cases, the three edges created by `prioritized_borel_fork_three_step_block b c` have directions false, false, and $b$. Unfolding `prioritized_borel_fork_expand`, mapping the direction projection over the three-step block, and applying the induction hypothesis to the tails shows that the resulting list of directions is $[\text{false}, \text{false}, b] ++ u'.\text{flatMap}(\dots) = (b :: u').\text{flatMap}(\dots)$.

    line 11

    uses prioritized_borel_fork_expand, prioritized_borel_fork_three_step_block

              cases c <;> simp [prioritized_borel_fork_expand, prioritized_borel_fork_three_step_block, ih h hh]
prioritized_borel_fork_expand
Recursively constructs a list of prioritized Borel fork edges from a list of visible bits and a list of exit flags by producing a three-step block for each pair of elements.
prioritized_borel_fork_three_step_block
Constructs a sequence of three prioritized Borel fork edges given a visible bit and an exit flag; the directions of the three edges are false, false, and the visible bit.

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_expand_directions (u h : List Bool) (hlen : u.length = h.length) :    (prioritized_borel_fork_expand u h).map PrioritizedBorelForkEdge.dir =      u.flatMap (fun b => [false, false, b]) := by  induction u generalizing h with  | nil => cases h <;> simp_all [prioritized_borel_fork_expand]  | cons b u ih =>      cases h with      | nil => simp at hlen      | cons c h =>          have hh : u.length = h.length := by simpa using hlen          cases c <;> simp [prioritized_borel_fork_expand, prioritized_borel_fork_three_step_block, ih h hh]
See it in the graphDiscuss this resultChallenge it