AFTD Auto-Formalizing Theoretical Domains

prioritized_borel_fork_expand_snoc

theoremverified

Appending a visible bit and hidden decision appends the corresponding three-edge block to the expanded history.

Statement

theorem prioritized_borel_fork_expand_snoc (u h : List Bool) (hlen : u.length = h.length)
    (b c : Bool) :
    prioritized_borel_fork_expand (u ++ [b]) (h ++ [c]) =
      prioritized_borel_fork_expand u h ++ prioritized_borel_fork_three_step_block b c
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 1

The proof, explained

The proof proceeds by induction on the visible bit list u, generalizing over the hidden decision list h. In the base case where u is empty, the length equality forces h to be empty as well, and both sides reduce to the three-step block for (b, c). In the inductive step, the length assumption eliminates the empty list for h and shows that the tails of u and h have equal length; expanding the definition of history expansion on both sides separates the leading block, and the induction hypothesis together with list concatenation associativity finishes the proof.

  1. The identity holds in the base case where u is empty.

    We proceed by induction on u, generalizing over h. When u = [], we case split on h. If h = [], expanding the definition of prioritized_borel_fork_expand reduces both sides to prioritized_borel_fork_three_step_block b c. If h is non-empty, the hypothesis |[]| = |h| implies that an empty list has the same length as a non-empty list, which is an immediate contradiction.

    lines 5–6

      induction u generalizing h with
      | nil => cases h <;> simp_all [prioritized_borel_fork_expand]
  2. In the inductive step with non-empty u, the list h cannot be empty.

    For u = a :: u, we case split on h. If h = [], the equal-length hypothesis asserts (a :: u).length = 0, which is impossible because a :: u has length at least 1.

    lines 7–9

      | cons a u ih =>
          cases h with
          | nil => simp at hlen
  3. The inductive step holds when h is also non-empty.

    When h = x :: h, the tails u and h satisfy u.length = h.length since (a :: u).length = (x :: h).length. Unfolding the definition of prioritized_borel_fork_expand on both sides separates the leading block prioritized_borel_fork_three_step_block a x from the expansion of the tails. Rewriting the tail expansion using the induction hypothesis and applying the associativity of list concatenation (List.append_assoc) establishes the equality.

    lines 10–12

    uses List.append_assoc

          | cons x h =>
              have hh : u.length = h.length := by simpa using hlen
              simp [prioritized_borel_fork_expand, ih h hh, List.append_assoc]
List.append_assoc
Concatenation of lists is associative: for any lists as, bs, and cs, (as ++ bs) ++ cs = as ++ (bs ++ cs).

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