AFTD Auto-Formalizing Theoretical Domains

prioritized_borel_fork_valid_lengths

theoremverified

In each compatible block history the visible and hidden histories have equal length.

Statement

theorem prioritized_borel_fork_valid_lengths {color : List Bool → List Bool → Bool} {u h : List Bool}
    (hv : PrioritizedBorelForkValid color u h) : u.length = h.length
Source
arXiv:2611.10136, Section 5.3.2, smallest lower-bound arena; three-move fork obstruction
Verified
12 Nov 2026
Axioms
propext
Built on 1
  • PrioritizedBorelForkValidBlockwise histories: every history may stay for an arbitrary visible bit, or take a hidden excursion only when the strategy chooses that…
Used by 3

The proof, explained

The theorem is proved by induction on the derivation of `PrioritizedBorelForkValid color u h`. In the base case (`root`), both histories are empty, so both lengths are trivially zero. In both inductive steps (`stay` and `exit`), exactly one boolean value is appended to each history, increasing both lengths by one and preserving their equality by the induction hypothesis.

  1. In the base case, the visible and hidden histories are empty, so their lengths are equal.

    We proceed by induction on the validity derivation of `PrioritizedBorelForkValid color u h`. In the base case (`root`), both the visible history `u` and the hidden history `h` are the empty list `[]`. Both have length 0, so the equality `[].length = [].length` holds by definition.

    lines 3–4

      induction hv with
      | root => rfl
  2. The length equality is preserved when extending histories via the `stay` constructor.

    In the `stay` case, the visible history is extended by a boolean `bit` to `u ++ [bit]`, and the hidden history is extended by `false` to `h ++ [false]`. Appending one element increases the length of each list by 1. By the induction hypothesis `ih` (`u.length = h.length`), the new lengths `u.length + 1` and `h.length + 1` are equal.

    line 5

      | stay bit hv ih => simp [ih]
  3. The length equality is preserved when extending histories via the `exit` constructor.

    In the `exit` case, the visible history is extended by `color u h` to `u ++ [color u h]`, and the hidden history is extended by `true` to `h ++ [true]`. As in the `stay` case, exactly one element is appended to each list, so both lengths increase by 1, and equality follows immediately from the induction hypothesis `ih`.

    line 6

      | exit hv ih => simp [ih]

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_valid_lengths {color : List Bool → List Bool → Bool} {u h : List Bool}    (hv : PrioritizedBorelForkValid color u h) : u.length = h.length := by  induction hv with  | root => rfl  | stay bit hv ih => simp [ih]  | exit hv ih => simp [ih]
See it in the graphDiscuss this resultChallenge it