prioritized_borel_fork_fixed_branch_memory_fibers
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
- 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_one_branch_memory_fibersFor any finite-memory assignment, one infinite visible sequence has prefixes with arbitrarily large compatible hidden-history fibers at…
- Used by 1
- prioritized_borel_fork_strategy_fixed_branchFor any history-dependent strategy and finite-memory assignment in the three-state fork arena, there are one infinite visible block…
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₀.
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).
uses
prioritized_borel_fork_one_branch_memory_fibersclassical obtain ⟨f, hf⟩ := prioritized_borel_fork_one_branch_memory_fibers color mem choose n m S hsize hvalid using hfThere 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.
uses
Filter.Eventually.of_forall,Filter.frequently_exists.mphave 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
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).
uses
Filter.frequently_atTop.mp,lt_of_le_of_ltrefine ⟨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), ?_⟩
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₀.
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.
- The proof formalises the infinite pigeonhole principle using filters: since the memory type M is finite, a predicate that holds frequently along Filter.atTop must have a single witness in M that holds frequently along Filter.atTop.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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⟩