prioritized_borel_fork_one_branch_memory_fibers
For any finite-memory assignment, one infinite visible sequence has prefixes with arbitrarily large compatible hidden-history fibers at some memory value.
Statement
theorem prioritized_borel_fork_one_branch_memory_fibers {M : Type} [Fintype M] (color : List Bool → List Bool → Bool) (mem : List Bool → List Bool → M) : ∃ f : ℕ → Bool, ∀ d, ∃ n, ∃ m : M, ∃ 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_infinite_branchFor every history-dependent fork response, one infinite visible block sequence has prefixes with arbitrarily many compatible hidden…
- Used by 1
- prioritized_borel_fork_fixed_branch_memory_fibersFor any finite-memory assignment, one infinite visible sequence and one fixed memory value have arbitrarily large compatible…
The proof, explained
The proof applies the pigeonhole principle to an infinite visible sequence obtained from `prioritized_borel_fork_one_infinite_branch`. That sequence has the property that its prefix of any length $n$ admits at least $n + 1$ compatible valid hidden histories. To obtain a fiber of size greater than $d$ for a finite memory type $M$, we choose the prefix length $n = |M| \cdot d$, ensuring at least $|M| \cdot d + 1$ valid hidden histories. By the pigeonhole principle, some memory value $m \in M$ must be attained by more than $d$ of these histories, giving the desired memory fiber.
There exists an infinite binary sequence $f$ whose prefixes have arbitrarily large sets of valid hidden histories.
Using `prioritized_borel_fork_one_infinite_branch`, we obtain an infinite sequence $f : \mathbb{N} \to \text{Bool}$ such that for every length $n$, there is a finite set of hidden histories of cardinality at least $n + 1$ valid with respect to the prefix of $f$ of length $n$. We choose this $f$ as the candidate branch.
uses
prioritized_borel_fork_one_infinite_branchclassical obtain ⟨f, hf⟩ := prioritized_borel_fork_one_infinite_branch color refine ⟨f, ?_⟩
For any target fiber size $d$, choosing prefix length $n = |M| \cdot d$ yields a set $T$ of at least $|M| \cdot d + 1$ valid hidden histories compatible with prefix $u$.
Given $d$, we define the prefix length $n = |M| \cdot d$ and denote by $u$ the length-$n$ prefix of $f$. Evaluating the property of $f$ at $n$ yields a finite set $T$ of hidden histories with $|T| \ge n + 1$ that are all valid with respect to $u$.
intro d let n := Fintype.card M * d let u : List Bool := List.ofFn (fun i : Fin n => f i) obtain ⟨T, hsize, hvalid⟩ := hf n
The cardinality of $T$ strictly exceeds $|\text{Finset.univ}| \cdot d$, where $\text{Finset.univ}$ is the universal set of $M$. automation
Rewriting $|\text{Finset.univ}|$ to $|M|$ via `Finset.card_univ` and unfolding $n$ in $|T| \ge |M| \cdot d + 1$, the strict inequality $|M| \cdot d < |T|$ is established by linear arithmetic (`omega`).
uses
Finset.card_univhave hlarge : (Finset.univ : Finset M).card * d < T.card := by simp only [Finset.card_univ] dsimp [n] at hsize omega
There exists a memory state $m \in M$ whose fiber in $T$ under $\text{mem}(u, \cdot)$ has cardinality strictly greater than $d$.
The memory function maps $T$ into the universal finset of $M$. Because $|T| > |M| \cdot d$, the pigeonhole principle (`Finset.exists_lt_card_fiber_of_mul_lt_card_of_maps_to`) guarantees the existence of a state $m \in M$ such that the fiber $\{h \in T \mid \text{mem}(u, h) = m\}$ has size strictly greater than $d$.
uses
Finset.exists_lt_card_fiber_of_mul_lt_card_of_maps_toobtain ⟨m, _, hm⟩ := Finset.exists_lt_card_fiber_of_mul_lt_card_of_maps_to (s := T) (t := Finset.univ) (f := mem u) (n := d) (by simp) hlarge
The prefix length $n$, memory state $m$, and fiber $S = \{h \in T \mid \text{mem}(u, h) = m\}$ satisfy all required properties.
We provide $n$, $m$, and the fiber $S = \{h \in T \mid \text{mem}(u, h) = m\}$ as witnesses. Its cardinality exceeds $d$ by the pigeonhole step. Decomposing the filter membership via `Finset.mem_filter.mp` shows that every $h \in S$ belongs to $T$ (hence is valid with respect to $u$) and evaluates under $\text{mem}(u, \cdot)$ to $m$.
uses
Finset.mem_filter.mprefine ⟨n, m, T.filter (fun h => mem u h = m), hm, ?_⟩ intro h hh obtain ⟨hhT, hhm⟩ := Finset.mem_filter.mp hh exact ⟨hvalid h hhT, hhm⟩
prioritized_borel_fork_one_infinite_branch- There exists an infinite binary sequence $f$ such that for every prefix length $n$, there are at least $n + 1$ valid hidden histories compatible with the prefix of $f$ of length $n$.
Finset.card_univ- The cardinality of the universal finset `Finset.univ` of a finite type $\alpha$ equals `Fintype.card \alpha`.
Finset.exists_lt_card_fiber_of_mul_lt_card_of_maps_to- If a map from a finite set $s$ into a finite set $t$ satisfies $|s| > |t| \cdot n$, then some element $y \in t$ has a fiber $\{x \in s \mid f(x) = y\}$ of cardinality strictly greater than $n$ (pigeonhole principle).
Finset.mem_filter.mp- An element belongs to the filtered finset $\{x \in s \mid p(x)\}$ if and only if it belongs to $s$ and satisfies $p$.
- The proof begins with `classical` to provide decidable equality for all types, which is needed to define the fiber by filtering `T`.
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_one_branch_memory_fibers {M : Type} [Fintype M] (color : List Bool → List Bool → Bool) (mem : List Bool → List Bool → M) : ∃ f : ℕ → Bool, ∀ d, ∃ n, ∃ m : M, ∃ 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_infinite_branch color refine ⟨f, ?_⟩ intro d let n := Fintype.card M * d let u : List Bool := List.ofFn (fun i : Fin n => f i) obtain ⟨T, hsize, hvalid⟩ := hf n have hlarge : (Finset.univ : Finset M).card * d < T.card := by simp only [Finset.card_univ] dsimp [n] at hsize omega obtain ⟨m, _, hm⟩ := Finset.exists_lt_card_fiber_of_mul_lt_card_of_maps_to (s := T) (t := Finset.univ) (f := mem u) (n := d) (by simp) hlarge refine ⟨n, m, T.filter (fun h => mem u h = m), hm, ?_⟩ intro h hh obtain ⟨hhT, hhm⟩ := Finset.mem_filter.mp hh exact ⟨hvalid h hhT, hhm⟩