AFTD Auto-Formalizing Theoretical Domains

prioritized_borel_fork_prefix_chain

theoremverified

For every n, there is a visible n-block word such that every prefix of length k admits at least k+1 compatible hidden histories.

Statement

theorem prioritized_borel_fork_prefix_chain (color : List Bool → List Bool → Bool) (n : ℕ) :
    ∃ u : List Bool, u.length = n ∧
      ∀ k ≤ n, ∃ S : Finset (List Bool), k + 1 ≤ S.card ∧
        ∀ h ∈ S, PrioritizedBorelForkValid color (u.take k) h
Source
arXiv:2611.10136, Section 5.3.2; the three-state fork subarena
Verified
12 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • PrioritizedBorelForkValidBlockwise histories: every history may stay for an arbitrary visible bit, or take a hidden excursion only when the strategy chooses that…
  • prioritized_borel_fork_majority_growthIf every history has a distinct stay extension and a distinct excursion extension colored by a bit, some common visible bit yields at…
Used by 1

The proof, explained

The theorem is proved by induction on n. In the induction step, given a word u of length n with at least n + 1 compatible histories S at step n, the majority growth lemma (prioritized_borel_fork_majority_growth) selects a continuation bit that expands the valid histories to a set T satisfying 3 |S| ≤ 2 |T|. Linear arithmetic ensures |T| ≥ n + 2, providing enough valid histories for the entire extended word u ++ [bit]. All shorter prefixes k ≤ n retain their valid histories from the induction hypothesis because extending the word does not alter its shorter prefixes.

  1. Appending false and appending true to histories are injective maps with disjoint ranges.

    Appending [false] and appending [true] to a list are both injective by List.append_left_injective. If a ++ [false] = b ++ [true], taking the last element of both lists via congrArg List.getLast? implies some false = some true, an equality of distinct values which simp refutes.

    lines 5–13

    uses List.append_left_injective, congrArg, List.getLast?

      classical
      have hs : Function.Injective (fun h : List Bool => h ++ [false]) :=
        List.append_left_injective [false]
      have he : Function.Injective (fun h : List Bool => h ++ [true]) :=
        List.append_left_injective [true]
      have hdiff : ∀ a b : List Bool, a ++ [false] ≠ b ++ [true] := by
        intro a b h
        have hh := congrArg List.getLast? h
        simp at hh
  2. Base case n = 0: the empty visible word admits a valid history set of size at least 1.

    We induct on n. For n = 0, we choose the empty visible word []. The only prefix length k ≤ 0 is k = 0 (by omega). The singleton set {[]} has size 1 ≥ 0 + 1. By Finset.mem_singleton, the only history in this set is [], which is valid for the empty word by PrioritizedBorelForkValid.root.

    lines 14–24

    uses Finset.mem_singleton, PrioritizedBorelForkValid.root

      induction n with
      | zero =>
          refine ⟨[], rfl, ?_⟩
          intro k hk
          have : k = 0 := by omega
          subst k
          refine ⟨{[]}, by simp, ?_⟩
          intro h hh
          simp only [Finset.mem_singleton] at hh
          subst h
          simpa using (PrioritizedBorelForkValid.root (color := color))
  3. Induction step setup: obtain a word u of length n and a set S of at least n + 1 valid histories for u.

    From the induction hypothesis for n, we obtain a visible word u of length n. Specializing the prefix property to k = n using le_rfl yields a set S of size at least n + 1 such that every history in S is valid for u.take n = u.

    lines 25–29

    uses le_rfl

      | succ n ih =>
          obtain ⟨u, hlen, hchain⟩ := ih
          obtain ⟨S, hsize, hvalid⟩ := hchain n le_rfl
          have hu : u.take n = u := by simp [← hlen]
          rw [hu] at hvalid
  4. A majority bit produces a new history set T with |T| ≥ n + 2.

    Applying prioritized_borel_fork_majority_growth to S with stay map h ↦ h ++ [false], exit map h ↦ h ++ [true], and coloring color(u) produces a bit such that 3 |S| ≤ 2 |T|, where T is the union of the stay image of S and the exit image of elements matching the bit. Because |S| ≥ n + 1, linear integer arithmetic (omega) implies |T| ≥ n + 2.

    lines 30–36

    uses prioritized_borel_fork_majority_growth

          obtain ⟨bit, hb⟩ := prioritized_borel_fork_majority_growth S
            (fun h => h ++ [false]) (fun h => h ++ [true]) hs he hdiff (color u)
          let T := (S.image (fun h => h ++ [false])) ∪
            ((S.filter fun h => color u h = bit).image (fun h => h ++ [true]))
          have ht : n+2 ≤ T.card := by
            have hm : 3 * S.card ≤ 2 * T.card := hb
            omega
  5. Every history in T is valid for the extended visible word u ++ [bit].

    For any h ∈ T, case analysis on the union (Finset.mem_union.mp) shows that h either comes from the stay image (Finset.mem_image.mp), meaning h = a ++ [false] for some a ∈ S, which is valid for u ++ [bit] by PrioritizedBorelForkValid.stay; or h comes from the exit image, meaning h = a ++ [true] for some a ∈ S with color(u, a) = bit (Finset.mem_filter.mp), which is valid for u ++ [bit] by PrioritizedBorelForkValid.exit.

    lines 37–44

    uses Finset.mem_union.mp, Finset.mem_image.mp, PrioritizedBorelForkValid.stay, Finset.mem_filter.mp, PrioritizedBorelForkValid.exit

          have hv : ∀ h ∈ T, PrioritizedBorelForkValid color (u ++ [bit]) h := by
            intro h hh
            rcases Finset.mem_union.mp hh with hs' | he'
            · obtain ⟨a, ha, rfl⟩ := Finset.mem_image.mp hs'
              exact PrioritizedBorelForkValid.stay bit (hvalid a ha)
            · obtain ⟨a, ha, rfl⟩ := Finset.mem_image.mp he'
              obtain ⟨haS, hcolor⟩ := Finset.mem_filter.mp ha
              simpa [hcolor] using (PrioritizedBorelForkValid.exit (hvalid a haS))
  6. The extended word u ++ [bit] of length n + 1 satisfies the prefix condition for all k ≤ n + 1.

    We choose u ++ [bit], which has length n + 1. For any prefix length k ≤ n + 1, we consider whether k ≤ n. If k ≤ n, the prefix of length k coincides with u.take k by List.take_append_of_le_length, so the history set S' provided by the induction hypothesis remains valid. If k = n + 1, the candidate set T satisfies |T| ≥ n + 2 = k + 1, and every history in T is valid for the full word.

    lines 45–58

    uses List.take_append_of_le_length

          refine ⟨u ++ [bit], by simp [hlen], ?_⟩
          intro k hk
          by_cases hkn : k ≤ n
          · obtain ⟨S', hs', hv'⟩ := hchain k hkn
            refine ⟨S', hs', ?_⟩
            have heq : (u ++ [bit]).take k = u.take k := by
              apply List.take_append_of_le_length
              omega
            simpa [heq] using hv'
          · have hk' : k = n+1 := by omega
            subst k
            refine ⟨T, by omega, ?_⟩
            have heq : (u ++ [bit]).take (n+1) = u ++ [bit] := by simp [hlen]
            simpa [heq] using hv
List.append_left_injective
Appending a fixed list to the right of any list is an injective operation.
congrArg
Applying a function to both sides of an equality preserves the equality: if a₁ = a₂, then f(a₁) = f(a₂).
List.getLast?
Returns the last element of a list as an option, or none if the list is empty.
Finset.mem_singleton
An element belongs to the singleton set {a} if and only if it equals a.
PrioritizedBorelForkValid.root
The empty history is valid for the empty visible word.
le_rfl
Every element in a preorder is less than or equal to itself (a ≤ a).
prioritized_borel_fork_majority_growth
For any finite set S, injective maps stay and exit with disjoint ranges, and binary coloring, there exists a bit such that 3 |S| ≤ 2 |stay(S) ∪ exit({a ∈ S | color(a) = bit})|.
Finset.mem_union.mp
If an element belongs to a union A ∪ B, then it belongs to A or to B.
Finset.mem_image.mp
If an element belongs to the image f(S), then it equals f(a) for some a ∈ S.
PrioritizedBorelForkValid.stay
If a history h is valid for visible word u, then h ++ [false] is valid for u ++ [b] for any bit b.
Finset.mem_filter.mp
If an element belongs to the filtered set {a ∈ S | p(a)}, then it belongs to S and satisfies p.
PrioritizedBorelForkValid.exit
If a history h is valid for visible word u, then h ++ [true] is valid for u ++ [color(u, h)].
List.take_append_of_le_length
Taking i elements from l₁ ++ l₂ equals taking i elements from l₁, provided i ≤ length(l₁).

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_prefix_chain (color : List Bool → List Bool → Bool) (n : ℕ) :    ∃ u : List Bool, u.length = n ∧      ∀ k ≤ n, ∃ S : Finset (List Bool), k + 1 ≤ S.card ∧        ∀ h ∈ S, PrioritizedBorelForkValid color (u.take k) h := by  classical  have hs : Function.Injective (fun h : List Bool => h ++ [false]) :=    List.append_left_injective [false]  have he : Function.Injective (fun h : List Bool => h ++ [true]) :=    List.append_left_injective [true]  have hdiff : ∀ a b : List Bool, a ++ [false] ≠ b ++ [true] := by    intro a b h    have hh := congrArg List.getLast? h    simp at hh  induction n with  | zero =>      refine ⟨[], rfl, ?_⟩      intro k hk      have : k = 0 := by omega      subst k      refine ⟨{[]}, by simp, ?_⟩      intro h hh      simp only [Finset.mem_singleton] at hh      subst h      simpa using (PrioritizedBorelForkValid.root (color := color))  | succ n ih =>      obtain ⟨u, hlen, hchain⟩ := ih      obtain ⟨S, hsize, hvalid⟩ := hchain n le_rfl      have hu : u.take n = u := by simp [← hlen]      rw [hu] at hvalid      obtain ⟨bit, hb⟩ := prioritized_borel_fork_majority_growth S        (fun h => h ++ [false]) (fun h => h ++ [true]) hs he hdiff (color u)      let T := (S.image (fun h => h ++ [false])) ∪        ((S.filter fun h => color u h = bit).image (fun h => h ++ [true]))      have ht : n+2 ≤ T.card := by        have hm : 3 * S.card ≤ 2 * T.card := hb        omega      have hv : ∀ h ∈ T, PrioritizedBorelForkValid color (u ++ [bit]) h := by        intro h hh        rcases Finset.mem_union.mp hh with hs' | he'        · obtain ⟨a, ha, rfl⟩ := Finset.mem_image.mp hs'          exact PrioritizedBorelForkValid.stay bit (hvalid a ha)        · obtain ⟨a, ha, rfl⟩ := Finset.mem_image.mp he'          obtain ⟨haS, hcolor⟩ := Finset.mem_filter.mp ha          simpa [hcolor] using (PrioritizedBorelForkValid.exit (hvalid a haS))      refine ⟨u ++ [bit], by simp [hlen], ?_⟩      intro k hk      by_cases hkn : k ≤ n      · obtain ⟨S', hs', hv'⟩ := hchain k hkn        refine ⟨S', hs', ?_⟩        have heq : (u ++ [bit]).take k = u.take k := by          apply List.take_append_of_le_length          omega        simpa [heq] using hv'      · have hk' : k = n+1 := by omega        subst k        refine ⟨T, by omega, ?_⟩        have heq : (u ++ [bit]).take (n+1) = u ++ [bit] := by simp [hlen]        simpa [heq] using hv
See it in the graphDiscuss this resultChallenge it