AFTD Auto-Formalizing Theoretical Domains

prioritized_borel_fork_fixed_branch_memory_fibers

theoremverified

For any finite-memory assignment, one infinite visible sequence and one fixed memory value have arbitrarily large compatible hidden-history fibers along its prefixes.

Statement

theorem prioritized_borel_fork_fixed_branch_memory_fibers {M : Type} [Fintype M]
    (color : List Bool → List Bool → Bool) (mem : List Bool → List Bool → M) :
    ∃ f : ℕ → Bool, ∃ m : M, ∀ d, ∃ n, ∃ S : Finset (List Bool),
      d < S.card ∧ ∀ h ∈ S,
        PrioritizedBorelForkValid color (List.ofFn (fun i : Fin n => f i)) h ∧
        mem (List.ofFn (fun i : Fin n => f i)) h = m
Source
arXiv:2611.10136, Section 5.3.2; the three-state fork subarena
Verified
12 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 1

The proof, explained

The proof starts from prioritized_borel_fork_one_branch_memory_fibers, which provides an infinite visible sequence f having arbitrarily large fibers of compatible hidden histories with constant memory, though the memory state may vary with the threshold d. Because the memory state space M is finite, the pigeonhole principle along the atTop filter ensures that at least one fixed memory state m₀ must be attained for arbitrarily large d. For any desired fiber size d, choosing an index j ≥ d where m(j) = m₀ yields a valid fiber of size exceeding j ≥ d with the fixed memory value m₀.

  1. There exist an infinite sequence f and functions assigning to each bound d a prefix length n(d), a memory state m(d), and a finite set of hidden histories S(d) of size greater than d, valid with the prefix and yielding memory m(d).

    By prioritized_borel_fork_one_branch_memory_fibers, there is an infinite visible sequence f such that for any size threshold d, some prefix length, memory value, and finite set of hidden histories exist with size exceeding d, valid for the prefix and sharing that memory value. The axiom of choice (choose) extracts these witnesses as functions n(d), m(d), and S(d).

    lines 7–9

    uses prioritized_borel_fork_one_branch_memory_fibers

      classical
      obtain ⟨f, hf⟩ := prioritized_borel_fork_one_branch_memory_fibers color mem
      choose n m S hsize hvalid using hf
  2. There exists a fixed memory state m₀ ∈ M that is attained by m(d) for arbitrarily large values of d.

    For every d, m(d) = m(d) trivially holds, so the statement that m(d) equals some element of M holds universally, and thus eventually and frequently along Filter.atTop via Filter.Eventually.of_forall. Because M is finite, the pigeonhole principle for filters (Filter.frequently_exists.mp) allows the existential quantifier to be pulled outside, yielding a single state m₀ ∈ M such that m(d) = m₀ holds frequently along Filter.atTop.

    lines 10–12

    uses Filter.Eventually.of_forall, Filter.frequently_exists.mp

      have hall : ∃ᶠ d : ℕ in Filter.atTop, ∃ x : M, m d = x := by
        exact (Filter.Eventually.of_forall fun d => ⟨m d, rfl⟩).frequently
      obtain ⟨m0, hm0⟩ := Filter.frequently_exists.mp hall
  3. With witness sequence f and fixed memory state m₀, for any given lower bound d there exist a prefix length and a set of hidden histories of cardinality strictly greater than d.

    We fix the infinite sequence f and memory value m₀. For any threshold d, since m(j) = m₀ frequently along Filter.atTop, Filter.frequently_atTop.mp supplies an index j ≥ d with m(j) = m₀. Choosing prefix length n(j) and history set S(j), the size inequality |S(j)| > j ≥ d implies |S(j)| > d by transitivity of inequality (lt_of_le_of_lt).

    lines 13–16

    uses Filter.frequently_atTop.mp, lt_of_le_of_lt

      refine ⟨f, m0, ?_⟩
      intro d
      obtain ⟨j, hj, hjm⟩ := Filter.frequently_atTop.mp hm0 d
      refine ⟨n j, S j, lt_of_le_of_lt hj (hsize j), ?_⟩
  4. Every history in S(j) is valid with the prefix of length n(j) of f and evaluates to the fixed memory state m₀.

    For any history h ∈ S(j), validity and the equality mem(..., h) = m(j) hold by construction of S(j). Since m(j) = m₀, transitivity of equality concludes that the memory value is indeed m₀.

    lines 17–19

      intro h hh
      obtain ⟨hv, hmem⟩ := hvalid j h hh
      exact ⟨hv, hmem.trans hjm⟩
prioritized_borel_fork_one_branch_memory_fibers
For any finite-memory function, there is an infinite visible sequence whose prefixes admit arbitrarily large sets of valid hidden histories having the same memory value (which may depend on the size threshold).
Filter.Eventually.of_forall
If a predicate holds for every point in a space, then it holds eventually along any filter on that space.
Filter.frequently_exists.mp
If an existential statement over a finite type holds frequently along a filter, then some fixed witness makes the predicate hold frequently along that filter.
Filter.frequently_atTop.mp
If a property of natural numbers holds frequently along Filter.atTop, then for every bound d there exists some j ≥ d satisfying the property.
lt_of_le_of_lt
In a preorder, if a ≤ b and b < c, then a < c.

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_fixed_branch_memory_fibers {M : Type} [Fintype M]    (color : List Bool → List Bool → Bool) (mem : List Bool → List Bool → M) :    ∃ f : ℕ → Bool, ∃ m : M, ∀ d, ∃ n, ∃ S : Finset (List Bool),      d < S.card ∧ ∀ h ∈ S,        PrioritizedBorelForkValid color (List.ofFn (fun i : Fin n => f i)) h ∧        mem (List.ofFn (fun i : Fin n => f i)) h = m := by  classical  obtain ⟨f, hf⟩ := prioritized_borel_fork_one_branch_memory_fibers color mem  choose n m S hsize hvalid using hf  have hall : ∃ᶠ d : ℕ in Filter.atTop, ∃ x : M, m d = x := by    exact (Filter.Eventually.of_forall fun d => ⟨m d, rfl⟩).frequently  obtain ⟨m0, hm0⟩ := Filter.frequently_exists.mp hall  refine ⟨f, m0, ?_⟩  intro d  obtain ⟨j, hj, hjm⟩ := Filter.frequently_atTop.mp hm0 d  refine ⟨n j, S j, lt_of_le_of_lt hj (hsize j), ?_⟩  intro h hh  obtain ⟨hv, hmem⟩ := hvalid j h hh  exact ⟨hv, hmem.trans hjm⟩
See it in the graphDiscuss this resultChallenge it