prioritized_borel_fork_one_infinite_branch
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
- 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…
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.
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.
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
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).
uses
List.take_append_of_le_lengthhave 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
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).
uses
prioritized_borel_fork_prefix_chainhave 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⟩
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.
uses
prioritized_borel_finite_history_shadowobtain ⟨f, hf⟩ := prioritized_borel_finite_history_shadow Bool P hpref hdepthFor 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.
refine ⟨f, ?_⟩ intro n have h := hf n obtain ⟨S, hs, hv⟩ := h n (by simp) refine ⟨S, hs, ?_⟩
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.
uses
List.length_ofFn,List.take_lengthhave 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.
- The infinite branch is obtained via a compactness argument (a variant of König's Lemma, `prioritized_borel_finite_history_shadow`), which relies on classical choice.
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_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