prioritized_borel_fork_memory_fiber_unbounded
For every history-dependent response and every finite-memory assignment, arbitrarily many compatible hidden histories can reach one common visible node and one memory value.
Statement
theorem prioritized_borel_fork_memory_fiber_unbounded {M : Type} [Fintype M] (color : List Bool → List Bool → Bool) (mem : List Bool → List Bool → M) (d : ℕ) : ∃ u : List Bool, ∃ m : M, ∃ S : Finset (List Bool), d < S.card ∧ ∀ h ∈ S, PrioritizedBorelForkValid color u h ∧ mem u h = m
- Source
- arXiv:2611.10136, Section 5.3.2, smallest lower-bound arena; three-move fork obstruction
- 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_exponential_historiesFor every history-dependent excursion response and every n, some common n-block output has at least (3/2)^n compatible hidden histories.
- Used by 1
- prioritized_borel_fork_unbounded_same_memoryFor any history-dependent excursion choice and finite-memory assignment, arbitrarily many distinct legal runs from q to q share their…
The proof, explained
To find more than d valid hidden histories sharing the same visible sequence and finite-memory value, we set n = |M| * d and invoke prioritized_borel_fork_exponential_histories to obtain a visible sequence u and a set T of valid hidden histories of size at least |M| * d + 1. By the pigeonhole principle applied to the memory mapping from T into M, at least one memory value m has a fiber in T of size strictly greater than d. Filtering T to this fiber provides the required witnesses.
There exist a visible sequence u and a finite set T of at least |M| * d + 1 valid hidden histories compatible with u.
Setting n = |M| * d, theorem prioritized_borel_fork_exponential_histories supplies a visible sequence u of length n and a finite set T of hidden histories such that |T| ≥ n + 1 = |M| * d + 1, and every history h in T is valid for u under the response rule color.
uses
prioritized_borel_fork_exponential_historiesclassical let n := Fintype.card M * d obtain ⟨u, T, _, hsize, _, hvalid⟩ := prioritized_borel_fork_exponential_histories color n
The cardinality of T is strictly greater than |M| * d.
By Finset.card_univ, the universe of M has size |M|. Since |T| ≥ |M| * d + 1, linear arithmetic (omega) confirms that |M| * d < |T|.
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 under mem(u, ·) in T contains strictly more than d histories.
Applying the pigeonhole principle (Finset.exists_lt_card_fiber_of_mul_lt_card_of_maps_to) to the memory function h ↦ mem(u, h) from T into M, the inequality |M| * d < |T| guarantees that some memory state m in M has more than d preimages in T.
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 fiber S = {h ∈ T | mem(u, h) = m} satisfies all required conditions.
We instantiate the existential witnesses with u, m, and the fiber S. Its size exceeds d by the pigeonhole step. For each h ∈ S, Finset.mem_filter.mp shows that h ∈ T (hence h is valid for u) and mem(u, h) = m, which completes the proof.
uses
Finset.mem_filter.mprefine ⟨u, 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_exponential_histories- For any coloring function and any natural number n, there exist a visible sequence u of length n and a finite set of hidden histories of size at least n + 1, all of which are valid responses compatible with u.
Finset.card_univ- The cardinality of the universal finset of a finite type equals the cardinality of the type.
Finset.exists_lt_card_fiber_of_mul_lt_card_of_maps_to- If a map from a finite set s to a finite set t satisfies |t| * n < |s|, then there exists an element y in t whose fiber has size strictly greater than n (the pigeonhole principle).
Finset.mem_filter.mp- An element belongs to a filtered finset if and only if it belongs to the original finset and satisfies the filtering predicate.
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_memory_fiber_unbounded {M : Type} [Fintype M] (color : List Bool → List Bool → Bool) (mem : List Bool → List Bool → M) (d : ℕ) : ∃ u : List Bool, ∃ m : M, ∃ S : Finset (List Bool), d < S.card ∧ ∀ h ∈ S, PrioritizedBorelForkValid color u h ∧ mem u h = m := by classical let n := Fintype.card M * d obtain ⟨u, T, _, hsize, _, hvalid⟩ := prioritized_borel_fork_exponential_histories color 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 ⟨u, 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⟩