prioritized_borel_fork_strategy_fixed_branch
For any history-dependent strategy and finite-memory assignment in the three-state fork arena, there are one infinite visible block sequence and one fixed memory value for which arbitrarily many distinct legal strategy-consistent runs ending at q and that memory value share prefixes of the sequence.
Statement
theorem prioritized_borel_fork_strategy_fixed_branch {M : Type} [Fintype M] (choice : List PrioritizedBorelForkEdge → Bool) (memory : List PrioritizedBorelForkEdge → M) : ∃ f : ℕ → Bool, ∃ m : M, ∀ d, ∃ n, ∃ S : Finset (List Bool), d < S.card ∧ (∀ h ∈ S, prioritized_borel_fork_consistent choice [] (prioritized_borel_fork_expand (List.ofFn (fun i : Fin n => f i)) h) ∧ memory (prioritized_borel_fork_expand (List.ofFn (fun i : Fin n => f i)) h) = m ∧ PrioritizedBorelForkRun 0 (prioritized_borel_fork_expand (List.ofFn (fun i : Fin n => f i)) h) 0 ∧ (prioritized_borel_fork_expand (List.ofFn (fun i : Fin n => f i)) h).map PrioritizedBorelForkEdge.dir = (List.ofFn (fun i : Fin n => f i)).flatMap (fun b => [false, false, b])) ∧ (∀ h ∈ S, ∀ k ∈ S, prioritized_borel_fork_expand (List.ofFn (fun i : Fin n => f i)) h = prioritized_borel_fork_expand (List.ofFn (fun i : Fin n => f i)) k → h = k)
- Source
- arXiv:2611.10136, Section 5.3.2; the three-state fork subarena
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 13
- PrioritizedBorelForkEdgeOne edge of the three-state fork arena, recording source, direction, target, and priority.
- PrioritizedBorelForkRunA finite path in the fork arena whose edges are legal and have matching endpoints.
- prioritized_borel_fork_consistentA finite edge history is consistent with a history-dependent choice function when every p-owned edge uses the direction the function…
- prioritized_borel_fork_decode_expandExpanding equally long visible and hidden block histories and decoding the result recovers the hidden history.
- prioritized_borel_fork_expandExpand equally indexed visible bits and hidden stay-or-excursion choices into three-edge blocks.
- prioritized_borel_fork_expand_directionsExpanding equally long block histories has directions false, false, then the visible bit in each block.
- prioritized_borel_fork_expand_runEvery expanded sequence of paired blocks is a legal run from q back to q.
- prioritized_borel_fork_fixed_branch_memory_fibersFor any finite-memory assignment, one infinite visible sequence and one fixed memory value have arbitrarily large compatible…
- prioritized_borel_fork_hidden_decodeRecover the hidden stay-or-excursion choices from the first edge of each three-edge block.
- prioritized_borel_fork_setupThe first two forced edges of a fork excursion.
- prioritized_borel_fork_valid_consistentEvery valid hidden block history expands to an edge history consistent with the actual history-dependent p-owned choice function.
- prioritized_borel_fork_valid_lengthsIn each compatible block history the visible and hidden histories have equal length.
- PrioritizedBorelForkValidBlockwise histories: every history may stay for an arbitrary visible bit, or take a hidden excursion only when the strategy chooses that…
- Used by 1
- prioritized_borel_fork_game_strategy_fixed_branchFor every finite-memory Eve strategy in the all-winning three-state fork game, one infinite visible block sequence and one fixed memory…
The proof, explained
The proof applies prioritized_borel_fork_fixed_branch_memory_fibers to extract an infinite visible sequence f and a memory state m such that arbitrarily large finite sets of valid hidden sequences share the same prefix of f and end in memory m. Given any threshold d, this provides a prefix length n and a set S of hidden sequences with |S| > d. Each hidden sequence in S expands to a strategy-consistent run from state 0 to state 0 with memory m and the prescribed edge directions. Finally, an explicit decoder (prioritized_borel_fork_hidden_decode) inverts the expansion map, proving that the expanded runs are pairwise distinct.
There exist an infinite visible bit sequence f and a memory state m admitting arbitrarily large finite families of valid hidden sequences.
Applying the fiber lemma prioritized_borel_fork_fixed_branch_memory_fibers to the strategy choice and the memory update function (both evaluated on expanded runs) yields an infinite sequence f : ℕ → Bool and a memory state m ∈ M. These serve as the existential witnesses for the theorem.
uses
prioritized_borel_fork_fixed_branch_memory_fibersobtain ⟨f, m, hf⟩ := prioritized_borel_fork_fixed_branch_memory_fibers (fun u h => choice (prioritized_borel_fork_expand u h ++ prioritized_borel_fork_setup)) (fun u h => memory (prioritized_borel_fork_expand u h)) refine ⟨f, m, ?_⟩
For any size threshold d, we obtain a prefix length n and a finite set S of hidden sequences with |S| > d, reducing the problem to verifying run properties and injectivity.
Fixing an arbitrary threshold d, the fiber hypothesis yields a prefix length n and a finite set S of hidden sequences with |S| > d. Letting u be the length-n prefix of f, we supply n and S as the required witnesses, leaving two obligations: verifying the four run properties for every h ∈ S, and proving that the expansion map is injective on S.
intro d obtain ⟨n, S, hcard, hvalid⟩ := hf d let u : List Bool := List.ofFn (fun i : Fin n => f i) refine ⟨n, S, hcard, ?_, ?_⟩
Every hidden sequence h ∈ S expands to a run that is consistent with the strategy, terminates in memory state m, is a legal run from 0 to 0, and has the required sequence of directions.
For each h ∈ S, the fiber hypothesis guarantees that (u, h) is valid and that the expanded run attains memory m. The lemma prioritized_borel_fork_valid_consistent shows that validity implies consistency with choice. The lemma prioritized_borel_fork_expand_run guarantees that the expanded run is a valid run from state 0 to state 0. Finally, prioritized_borel_fork_valid_lengths ensures that u and h have the same length, which allows prioritized_borel_fork_expand_directions to show that the directions of the run match the expanded visible sequence.
uses
prioritized_borel_fork_valid_consistent,prioritized_borel_fork_expand_run,prioritized_borel_fork_expand_directions,prioritized_borel_fork_valid_lengths· intro h hh obtain ⟨hv, hm⟩ := hvalid h hh exact ⟨prioritized_borel_fork_valid_consistent choice hv, hm, prioritized_borel_fork_expand_run u h, prioritized_borel_fork_expand_directions u h (prioritized_borel_fork_valid_lengths hv)⟩
The expansion map is injective on S: distinct hidden sequences in S produce distinct expanded runs.
Suppose two sequences h, k ∈ S produce identical expanded runs. Since u and h (respectively u and k) have equal lengths by prioritized_borel_fork_valid_lengths, the decoding lemma prioritized_borel_fork_decode_expand proves that applying prioritized_borel_fork_hidden_decode to each expanded run recovers h and k, respectively. Applying prioritized_borel_fork_hidden_decode to both sides of the assumed equality via congrArg and rewriting with these decoding identities establishes h = k.
uses
prioritized_borel_fork_decode_expand,prioritized_borel_fork_valid_lengths,congrArg· intro h hh k hk heq have h1 := prioritized_borel_fork_decode_expand u h (prioritized_borel_fork_valid_lengths (hvalid h hh).1) have h2 := prioritized_borel_fork_decode_expand u k (prioritized_borel_fork_valid_lengths (hvalid k hk).1) change prioritized_borel_fork_expand u h = prioritized_borel_fork_expand u k at heq have he := congrArg prioritized_borel_fork_hidden_decode heq rw [h1, h2] at he exact he
congrArg- Functions respect equality: if a₁ = a₂, then f a₁ = f a₂.
prioritized_borel_fork_decode_expand- If u and h have equal lengths, decoding the expanded run with prioritized_borel_fork_hidden_decode reconstructs the hidden sequence h.
prioritized_borel_fork_expand_directions- When u and h have equal lengths, the sequence of edge directions in the expanded run corresponds to expanding each bit b in u to [false, false, b].
prioritized_borel_fork_expand_run- For any visible sequence u and hidden sequence h, expanding them produces a legal run in the fork arena that starts and ends at state 0.
prioritized_borel_fork_fixed_branch_memory_fibers- For any strategy and finite-memory tracker on block sequences, there exist an infinite visible sequence f and a memory state m such that arbitrarily large finite sets of valid hidden sequences share the same prefix of f and attain memory m.
prioritized_borel_fork_valid_consistent- If a pair of visible and hidden sequences (u, h) is valid for the strategy following the setup prefix, then expanding them produces a run consistent with the strategy starting from the empty history.
prioritized_borel_fork_valid_lengths- Any valid pair of visible and hidden block sequences (u, h) must have equal lengths.
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_strategy_fixed_branch {M : Type} [Fintype M] (choice : List PrioritizedBorelForkEdge → Bool) (memory : List PrioritizedBorelForkEdge → M) : ∃ f : ℕ → Bool, ∃ m : M, ∀ d, ∃ n, ∃ S : Finset (List Bool), d < S.card ∧ (∀ h ∈ S, prioritized_borel_fork_consistent choice [] (prioritized_borel_fork_expand (List.ofFn (fun i : Fin n => f i)) h) ∧ memory (prioritized_borel_fork_expand (List.ofFn (fun i : Fin n => f i)) h) = m ∧ PrioritizedBorelForkRun 0 (prioritized_borel_fork_expand (List.ofFn (fun i : Fin n => f i)) h) 0 ∧ (prioritized_borel_fork_expand (List.ofFn (fun i : Fin n => f i)) h).map PrioritizedBorelForkEdge.dir = (List.ofFn (fun i : Fin n => f i)).flatMap (fun b => [false, false, b])) ∧ (∀ h ∈ S, ∀ k ∈ S, prioritized_borel_fork_expand (List.ofFn (fun i : Fin n => f i)) h = prioritized_borel_fork_expand (List.ofFn (fun i : Fin n => f i)) k → h = k) := by obtain ⟨f, m, hf⟩ := prioritized_borel_fork_fixed_branch_memory_fibers (fun u h => choice (prioritized_borel_fork_expand u h ++ prioritized_borel_fork_setup)) (fun u h => memory (prioritized_borel_fork_expand u h)) refine ⟨f, m, ?_⟩ intro d obtain ⟨n, S, hcard, hvalid⟩ := hf d let u : List Bool := List.ofFn (fun i : Fin n => f i) refine ⟨n, S, hcard, ?_, ?_⟩ · intro h hh obtain ⟨hv, hm⟩ := hvalid h hh exact ⟨prioritized_borel_fork_valid_consistent choice hv, hm, prioritized_borel_fork_expand_run u h, prioritized_borel_fork_expand_directions u h (prioritized_borel_fork_valid_lengths hv)⟩ · intro h hh k hk heq have h1 := prioritized_borel_fork_decode_expand u h (prioritized_borel_fork_valid_lengths (hvalid h hh).1) have h2 := prioritized_borel_fork_decode_expand u k (prioritized_borel_fork_valid_lengths (hvalid k hk).1) change prioritized_borel_fork_expand u h = prioritized_borel_fork_expand u k at heq have he := congrArg prioritized_borel_fork_hidden_decode heq rw [h1, h2] at he exact he