prioritized_borel_fork_prefix_chain
For every n, there is a visible n-block word such that every prefix of length k admits at least k+1 compatible hidden histories.
Statement
theorem prioritized_borel_fork_prefix_chain (color : List Bool → List Bool → Bool) (n : ℕ) :
∃ u : List Bool, u.length = n ∧
∀ k ≤ n, ∃ S : Finset (List Bool), k + 1 ≤ S.card ∧
∀ h ∈ S, PrioritizedBorelForkValid color (u.take k) h- 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_majority_growthIf every history has a distinct stay extension and a distinct excursion extension colored by a bit, some common visible bit yields at…
- Used by 1
- prioritized_borel_fork_one_infinite_branchFor every history-dependent fork response, one infinite visible block sequence has prefixes with arbitrarily many compatible hidden…
The proof, explained
The theorem is proved by induction on n. In the induction step, given a word u of length n with at least n + 1 compatible histories S at step n, the majority growth lemma (prioritized_borel_fork_majority_growth) selects a continuation bit that expands the valid histories to a set T satisfying 3 |S| ≤ 2 |T|. Linear arithmetic ensures |T| ≥ n + 2, providing enough valid histories for the entire extended word u ++ [bit]. All shorter prefixes k ≤ n retain their valid histories from the induction hypothesis because extending the word does not alter its shorter prefixes.
Appending false and appending true to histories are injective maps with disjoint ranges.
Appending [false] and appending [true] to a list are both injective by List.append_left_injective. If a ++ [false] = b ++ [true], taking the last element of both lists via congrArg List.getLast? implies some false = some true, an equality of distinct values which simp refutes.
uses
List.append_left_injective,congrArg,List.getLast?classical have hs : Function.Injective (fun h : List Bool => h ++ [false]) := List.append_left_injective [false] have he : Function.Injective (fun h : List Bool => h ++ [true]) := List.append_left_injective [true] have hdiff : ∀ a b : List Bool, a ++ [false] ≠ b ++ [true] := by intro a b h have hh := congrArg List.getLast? h simp at hh
Base case n = 0: the empty visible word admits a valid history set of size at least 1.
We induct on n. For n = 0, we choose the empty visible word []. The only prefix length k ≤ 0 is k = 0 (by omega). The singleton set {[]} has size 1 ≥ 0 + 1. By Finset.mem_singleton, the only history in this set is [], which is valid for the empty word by PrioritizedBorelForkValid.root.
uses
Finset.mem_singleton,PrioritizedBorelForkValid.rootinduction n with | zero => refine ⟨[], rfl, ?_⟩ intro k hk have : k = 0 := by omega subst k refine ⟨{[]}, by simp, ?_⟩ intro h hh simp only [Finset.mem_singleton] at hh subst h simpa using (PrioritizedBorelForkValid.root (color := color))
Induction step setup: obtain a word u of length n and a set S of at least n + 1 valid histories for u.
From the induction hypothesis for n, we obtain a visible word u of length n. Specializing the prefix property to k = n using le_rfl yields a set S of size at least n + 1 such that every history in S is valid for u.take n = u.
uses
le_rfl| succ n ih => obtain ⟨u, hlen, hchain⟩ := ih obtain ⟨S, hsize, hvalid⟩ := hchain n le_rfl have hu : u.take n = u := by simp [← hlen] rw [hu] at hvalidA majority bit produces a new history set T with |T| ≥ n + 2.
Applying prioritized_borel_fork_majority_growth to S with stay map h ↦ h ++ [false], exit map h ↦ h ++ [true], and coloring color(u) produces a bit such that 3 |S| ≤ 2 |T|, where T is the union of the stay image of S and the exit image of elements matching the bit. Because |S| ≥ n + 1, linear integer arithmetic (omega) implies |T| ≥ n + 2.
uses
prioritized_borel_fork_majority_growthobtain ⟨bit, hb⟩ := prioritized_borel_fork_majority_growth S (fun h => h ++ [false]) (fun h => h ++ [true]) hs he hdiff (color u) let T := (S.image (fun h => h ++ [false])) ∪ ((S.filter fun h => color u h = bit).image (fun h => h ++ [true])) have ht : n+2 ≤ T.card := by have hm : 3 * S.card ≤ 2 * T.card := hb omega
Every history in T is valid for the extended visible word u ++ [bit].
For any h ∈ T, case analysis on the union (Finset.mem_union.mp) shows that h either comes from the stay image (Finset.mem_image.mp), meaning h = a ++ [false] for some a ∈ S, which is valid for u ++ [bit] by PrioritizedBorelForkValid.stay; or h comes from the exit image, meaning h = a ++ [true] for some a ∈ S with color(u, a) = bit (Finset.mem_filter.mp), which is valid for u ++ [bit] by PrioritizedBorelForkValid.exit.
uses
Finset.mem_union.mp,Finset.mem_image.mp,PrioritizedBorelForkValid.stay,Finset.mem_filter.mp,PrioritizedBorelForkValid.exithave hv : ∀ h ∈ T, PrioritizedBorelForkValid color (u ++ [bit]) h := by intro h hh rcases Finset.mem_union.mp hh with hs' | he' · obtain ⟨a, ha, rfl⟩ := Finset.mem_image.mp hs' exact PrioritizedBorelForkValid.stay bit (hvalid a ha) · obtain ⟨a, ha, rfl⟩ := Finset.mem_image.mp he' obtain ⟨haS, hcolor⟩ := Finset.mem_filter.mp ha simpa [hcolor] using (PrioritizedBorelForkValid.exit (hvalid a haS))
The extended word u ++ [bit] of length n + 1 satisfies the prefix condition for all k ≤ n + 1.
We choose u ++ [bit], which has length n + 1. For any prefix length k ≤ n + 1, we consider whether k ≤ n. If k ≤ n, the prefix of length k coincides with u.take k by List.take_append_of_le_length, so the history set S' provided by the induction hypothesis remains valid. If k = n + 1, the candidate set T satisfies |T| ≥ n + 2 = k + 1, and every history in T is valid for the full word.
uses
List.take_append_of_le_lengthrefine ⟨u ++ [bit], by simp [hlen], ?_⟩ intro k hk by_cases hkn : k ≤ n · obtain ⟨S', hs', hv'⟩ := hchain k hkn refine ⟨S', hs', ?_⟩ have heq : (u ++ [bit]).take k = u.take k := by apply List.take_append_of_le_length omega simpa [heq] using hv' · have hk' : k = n+1 := by omega subst k refine ⟨T, by omega, ?_⟩ have heq : (u ++ [bit]).take (n+1) = u ++ [bit] := by simp [hlen] simpa [heq] using hv
List.append_left_injective- Appending a fixed list to the right of any list is an injective operation.
congrArg- Applying a function to both sides of an equality preserves the equality: if a₁ = a₂, then f(a₁) = f(a₂).
List.getLast?- Returns the last element of a list as an option, or none if the list is empty.
Finset.mem_singleton- An element belongs to the singleton set {a} if and only if it equals a.
PrioritizedBorelForkValid.root- The empty history is valid for the empty visible word.
le_rfl- Every element in a preorder is less than or equal to itself (a ≤ a).
prioritized_borel_fork_majority_growth- For any finite set S, injective maps stay and exit with disjoint ranges, and binary coloring, there exists a bit such that 3 |S| ≤ 2 |stay(S) ∪ exit({a ∈ S | color(a) = bit})|.
Finset.mem_union.mp- If an element belongs to a union A ∪ B, then it belongs to A or to B.
Finset.mem_image.mp- If an element belongs to the image f(S), then it equals f(a) for some a ∈ S.
PrioritizedBorelForkValid.stay- If a history h is valid for visible word u, then h ++ [false] is valid for u ++ [b] for any bit b.
Finset.mem_filter.mp- If an element belongs to the filtered set {a ∈ S | p(a)}, then it belongs to S and satisfies p.
PrioritizedBorelForkValid.exit- If a history h is valid for visible word u, then h ++ [true] is valid for u ++ [color(u, h)].
List.take_append_of_le_length- Taking i elements from l₁ ++ l₂ equals taking i elements from l₁, provided i ≤ length(l₁).
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_prefix_chain (color : List Bool → List Bool → Bool) (n : ℕ) : ∃ u : List Bool, u.length = n ∧ ∀ k ≤ n, ∃ S : Finset (List Bool), k + 1 ≤ S.card ∧ ∀ h ∈ S, PrioritizedBorelForkValid color (u.take k) h := by classical have hs : Function.Injective (fun h : List Bool => h ++ [false]) := List.append_left_injective [false] have he : Function.Injective (fun h : List Bool => h ++ [true]) := List.append_left_injective [true] have hdiff : ∀ a b : List Bool, a ++ [false] ≠ b ++ [true] := by intro a b h have hh := congrArg List.getLast? h simp at hh induction n with | zero => refine ⟨[], rfl, ?_⟩ intro k hk have : k = 0 := by omega subst k refine ⟨{[]}, by simp, ?_⟩ intro h hh simp only [Finset.mem_singleton] at hh subst h simpa using (PrioritizedBorelForkValid.root (color := color)) | succ n ih => obtain ⟨u, hlen, hchain⟩ := ih obtain ⟨S, hsize, hvalid⟩ := hchain n le_rfl have hu : u.take n = u := by simp [← hlen] rw [hu] at hvalid obtain ⟨bit, hb⟩ := prioritized_borel_fork_majority_growth S (fun h => h ++ [false]) (fun h => h ++ [true]) hs he hdiff (color u) let T := (S.image (fun h => h ++ [false])) ∪ ((S.filter fun h => color u h = bit).image (fun h => h ++ [true])) have ht : n+2 ≤ T.card := by have hm : 3 * S.card ≤ 2 * T.card := hb omega have hv : ∀ h ∈ T, PrioritizedBorelForkValid color (u ++ [bit]) h := by intro h hh rcases Finset.mem_union.mp hh with hs' | he' · obtain ⟨a, ha, rfl⟩ := Finset.mem_image.mp hs' exact PrioritizedBorelForkValid.stay bit (hvalid a ha) · obtain ⟨a, ha, rfl⟩ := Finset.mem_image.mp he' obtain ⟨haS, hcolor⟩ := Finset.mem_filter.mp ha simpa [hcolor] using (PrioritizedBorelForkValid.exit (hvalid a haS)) refine ⟨u ++ [bit], by simp [hlen], ?_⟩ intro k hk by_cases hkn : k ≤ n · obtain ⟨S', hs', hv'⟩ := hchain k hkn refine ⟨S', hs', ?_⟩ have heq : (u ++ [bit]).take k = u.take k := by apply List.take_append_of_le_length omega simpa [heq] using hv' · have hk' : k = n+1 := by omega subst k refine ⟨T, by omega, ?_⟩ have heq : (u ++ [bit]).take (n+1) = u ++ [bit] := by simp [hlen] simpa [heq] using hv