AFTD Auto-Formalizing Theoretical Domains

prioritized_borel_fork_one_infinite_branch

theoremverified

For every history-dependent fork response, one infinite visible block sequence has prefixes with arbitrarily many compatible hidden histories.

Statement

theorem prioritized_borel_fork_one_infinite_branch (color : List Bool → List Bool → Bool) :
    ∃ f : ℕ → Bool, ∀ n, ∃ S : Finset (List Bool), n+1 ≤ S.card ∧
      ∀ h ∈ S, PrioritizedBorelForkValid color (List.ofFn (fun i : Fin n => f i)) h
Source
arXiv:2611.10136, Section 5.3.2; the three-state fork subarena
Verified
12 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • PrioritizedBorelForkValidBlockwise histories: every history may stay for an arbitrary visible bit, or take a hidden excursion only when the strategy chooses that…
  • prioritized_borel_finite_history_shadowLet P be a prefix-closed predicate on finite lists over a finite alphabet. If P has a list of every finite length, then there is an…
  • prioritized_borel_fork_prefix_chainFor every n, there is a visible n-block word such that every prefix of length k admits at least k+1 compatible hidden histories.
Used by 1

The proof, explained

The theorem is established via a compactness argument (a variant of König's Lemma for sequence spaces). We define a predicate P stating that every prefix of length k has at least k + 1 compatible valid hidden histories, show that P is prefix-closed, and invoke prioritized_borel_fork_prefix_chain to obtain words of arbitrary length satisfying P. Applying prioritized_borel_finite_history_shadow yields an infinite sequence f whose prefixes all satisfy P, which immediately provides the required set of at least n + 1 valid hidden histories for every length n.

  1. Define a predicate P asserting that every prefix has sufficiently many compatible valid hidden histories.

    Working in classical logic, define P(u) for a finite binary word u to mean that for every k ≤ |u|, there exists a finite set S of hidden histories of cardinality at least k + 1 such that every h ∈ S is valid for the prefix u.take(k) under the given coloring.

    lines 4–7

      classical
      let P : List Bool → Prop := fun u =>
        ∀ k ≤ u.length, ∃ S : Finset (List Bool), k+1 ≤ S.card ∧
          ∀ h ∈ S, PrioritizedBorelForkValid color (u.take k) h
  2. The predicate P is closed under taking prefixes.

    Suppose xs ++ ys satisfies P, and consider any k ≤ |xs|. Since k ≤ |xs ++ ys|, the assumption P(xs ++ ys) yields a set S of at least k + 1 valid hidden histories for (xs ++ ys).take(k). By List.take_append_of_le_length, since k ≤ |xs|, (xs ++ ys).take(k) is identical to xs.take(k), so S also witnesses validity for xs.take(k).

    lines 8–13

    uses List.take_append_of_le_length

      have hpref : ∀ xs ys, P (xs ++ ys) → P xs := by
        intro xs ys hx k hk
        obtain ⟨S, hs, hv⟩ := hx k (by simp; omega)
        refine ⟨S, hs, ?_⟩
        have heq : (xs ++ ys).take k = xs.take k := List.take_append_of_le_length hk
        simpa [heq] using hv
  3. For every n, there exists a binary word of length n satisfying P.

    Given n, the lemma prioritized_borel_fork_prefix_chain produces a binary word u of length n whose prefixes of length k ≤ n each admit at least k + 1 valid hidden histories. Because |u| = n, this condition matches the definition of P(u).

    lines 14–17

    uses prioritized_borel_fork_prefix_chain

      have hdepth : ∀ n, ∃ u : List Bool, u.length = n ∧ P u := by
        intro n
        obtain ⟨u, hu, hc⟩ := prioritized_borel_fork_prefix_chain color n
        exact ⟨u, hu, by simpa [P, hu] using hc⟩
  4. There exists an infinite sequence f : ℕ → Bool all of whose prefixes satisfy P.

    Since the alphabet Bool is finite, P is prefix-closed, and words of every length satisfying P exist, König's Lemma (prioritized_borel_finite_history_shadow) provides an infinite sequence f : ℕ → Bool such that the prefix of length n of f satisfies P for all n.

    line 18

    uses prioritized_borel_finite_history_shadow

      obtain ⟨f, hf⟩ := prioritized_borel_finite_history_shadow Bool P hpref hdepth
  5. For each prefix length n, the length-n prefix of f admits a set S of at least n + 1 valid hidden histories.

    Taking f as the candidate infinite sequence, fix n. The length-n prefix of f (as a list) satisfies P. Evaluating P at k = n gives a set S of hidden histories with |S| ≥ n + 1 that are valid for the prefix of length n of that list. Providing S and its cardinality bound reduces the goal to confirming validity.

    lines 19–23

      refine ⟨f, ?_⟩
      intro n
      have h := hf n
      obtain ⟨S, hs, hv⟩ := h n (by simp)
      refine ⟨S, hs, ?_⟩
  6. The histories in S are valid for the length-n prefix of f.

    Because the prefix list has length n (by List.length_ofFn), taking its first n elements returns the full list itself (by List.take_length). Rewriting with this identity confirms that each history in S is valid for the length-n prefix of f.

    lines 24–30

    uses List.length_ofFn, List.take_length

      have htake : (List.ofFn (fun i : Fin n => f i)).take n =
          List.ofFn (fun i : Fin n => f i) := by
        simpa only [List.length_ofFn] using
          (List.take_length : (List.ofFn (fun i : Fin n => f i)).take
            (List.ofFn (fun i : Fin n => f i)).length = List.ofFn (fun i : Fin n => f i))
      rw [htake] at hv
      exact hv
List.take_append_of_le_length
Taking the first i elements of a concatenation l₁ ++ l₂ is equal to taking the first i elements of l₁, provided i ≤ length(l₁).
prioritized_borel_fork_prefix_chain
For every n, there exists a binary word of length n whose prefixes of length k ≤ n all admit at least k + 1 compatible valid hidden histories.
prioritized_borel_finite_history_shadow
König's Lemma for sequence spaces: if a predicate on lists over a finite alphabet is prefix-closed and has witnesses of arbitrarily large length, then there is an infinite sequence all of whose prefixes satisfy the predicate.
List.length_ofFn
The length of a list formed by tabulating a function on Fin n is n.
List.take_length
Taking the first length(l) elements of a list l returns l 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_one_infinite_branch (color : List Bool → List Bool → Bool) :    ∃ f : ℕ → Bool, ∀ n, ∃ S : Finset (List Bool), n+1 ≤ S.card ∧      ∀ h ∈ S, PrioritizedBorelForkValid color (List.ofFn (fun i : Fin n => f i)) h := by  classical  let P : List Bool → Prop := fun u =>    ∀ k ≤ u.length, ∃ S : Finset (List Bool), k+1 ≤ S.card ∧      ∀ h ∈ S, PrioritizedBorelForkValid color (u.take k) h  have hpref : ∀ xs ys, P (xs ++ ys) → P xs := by    intro xs ys hx k hk    obtain ⟨S, hs, hv⟩ := hx k (by simp; omega)    refine ⟨S, hs, ?_⟩    have heq : (xs ++ ys).take k = xs.take k := List.take_append_of_le_length hk    simpa [heq] using hv  have hdepth : ∀ n, ∃ u : List Bool, u.length = n ∧ P u := by    intro n    obtain ⟨u, hu, hc⟩ := prioritized_borel_fork_prefix_chain color n    exact ⟨u, hu, by simpa [P, hu] using hc⟩  obtain ⟨f, hf⟩ := prioritized_borel_finite_history_shadow Bool P hpref hdepth  refine ⟨f, ?_⟩  intro n  have h := hf n  obtain ⟨S, hs, hv⟩ := h n (by simp)  refine ⟨S, hs, ?_⟩  have htake : (List.ofFn (fun i : Fin n => f i)).take n =      List.ofFn (fun i : Fin n => f i) := by    simpa only [List.length_ofFn] using      (List.take_length : (List.ofFn (fun i : Fin n => f i)).take        (List.ofFn (fun i : Fin n => f i)).length = List.ofFn (fun i : Fin n => f i))  rw [htake] at hv  exact hv
See it in the graphDiscuss this resultChallenge it