prioritized_borel_fork_unbounded_same_memory
For any history-dependent excursion choice and finite-memory assignment, arbitrarily many distinct legal runs from q to q share their visible directions and memory value, and each excursion follows the choice function.
Statement
theorem prioritized_borel_fork_unbounded_same_memory {M : Type} [Fintype M] (choice : List PrioritizedBorelForkEdge → Bool) (memory : List PrioritizedBorelForkEdge → M) (d : ℕ) : ∃ u : List Bool, ∃ m : M, ∃ S : Finset (List Bool), d < S.card ∧ (∀ h ∈ S, PrioritizedBorelForkValid (fun v k => choice (prioritized_borel_fork_expand v k)) u h ∧ memory (prioritized_borel_fork_expand u h) = m ∧ PrioritizedBorelForkRun 0 (prioritized_borel_fork_expand u h) 0 ∧ (prioritized_borel_fork_expand u h).map PrioritizedBorelForkEdge.dir = u.flatMap (fun b => [false, false, b])) ∧ (∀ h ∈ S, ∀ k ∈ S, prioritized_borel_fork_expand u h = prioritized_borel_fork_expand u 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 10
- 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.
- 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_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_hidden_decodeRecover the hidden stay-or-excursion choices from the first edge of each three-edge block.
- prioritized_borel_fork_memory_fiber_unboundedFor every history-dependent response and every finite-memory assignment, arbitrarily many compatible hidden histories can reach one common…
- prioritized_borel_fork_valid_lengthsIn each compatible block history the visible and hidden histories have equal length.
- Used by 1
- prioritized_borel_fork_strategy_obstructionFor any history-dependent strategy and any finite-memory assignment, arbitrarily many distinct legal strategy-consistent runs return to q…
The proof, explained
We instantiate the existential claim using prioritized_borel_fork_memory_fiber_unbounded, obtaining a visible sequence u, a memory value m, and a set S of hidden paths of cardinality greater than d whose expansions achieve memory value m and follow the choice function. Each such expansion constitutes a legal run from state 0 to state 0 whose edge directions are obtained by expanding each bit b of u into [false, false, b]. Finally, these expanded runs are all distinct because the hidden sequence h can be uniquely decoded from the expansion.
There exist a visible sequence u, a memory value m, and a finite set S of hidden sequences with |S| > d whose elements all reach memory value m under the choice function, reducing the theorem to checking the execution properties and injectivity.
Applying prioritized_borel_fork_memory_fiber_unbounded to the choice and memory functions composed with expansion produces a visible sequence u, a memory state m, and a set S of hidden sequences with |S| > d such that every h ∈ S is valid under the choice function and attains memory state m. Providing u, m, and S as witnesses leaves two obligations: verifying the run properties for each element of S, and establishing that the expansion map is injective on S.
uses
prioritized_borel_fork_memory_fiber_unboundedobtain ⟨u, m, S, hcard, hvalid⟩ := prioritized_borel_fork_memory_fiber_unbounded (fun v k => choice (prioritized_borel_fork_expand v k)) (fun v k => memory (prioritized_borel_fork_expand v k)) d refine ⟨u, m, S, hcard, ?_, ?_⟩
For every hidden sequence h ∈ S, the expansion expand(u, h) is valid, attains memory state m, forms a legal run from state 0 to state 0, and has the prescribed visible directions.
Validity under the choice function and the memory value m are inherited directly from the set S. Lemma prioritized_borel_fork_expand_run shows that the expansion forms a legal run from state 0 to state 0. By prioritized_borel_fork_valid_lengths, validity implies that u and h have the same length, which allows prioritized_borel_fork_expand_directions to establish that projecting the directions of the expanded edges yields the concatenation of [false, false, b] for each bit b in u.
uses
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 ⟨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 h ↦ expand(u, h) is injective on S.
Suppose h, k ∈ S satisfy expand(u, h) = expand(u, k). Applying the decoding function prioritized_borel_fork_hidden_decode to both sides via congrArg equates their decoded outputs. Since u and h (as well as u and k) share the same length by prioritized_borel_fork_valid_lengths, prioritized_borel_fork_decode_expand simplifies the two decoded expressions back to h and k, proving 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) have he := congrArg prioritized_borel_fork_hidden_decode heq simpa [h1, h2] using he
prioritized_borel_fork_memory_fiber_unbounded- For any finite memory type M, excursion choice function, memory function, and bound d, there exists a visible sequence u, a memory value m, and a finite set S of hidden paths of size greater than d such that each h in S is valid with respect to u and results in memory state m.
prioritized_borel_fork_expand_run- For any sequences u and h, the expanded sequence of edges is a legal automaton run starting and ending at state 0.
prioritized_borel_fork_expand_directions- When sequences u and h have equal length, the sequence of edge directions in their expansion is obtained by replacing each bit b of u with [false, false, b].
prioritized_borel_fork_valid_lengths- If a hidden path h is valid with respect to a visible sequence u, then u and h have the same length.
prioritized_borel_fork_decode_expand- Decoding an expanded sequence of edges using prioritized_borel_fork_hidden_decode recovers the hidden sequence h, provided u and h have equal length.
congrArg- Applying a function f to both sides of an equality a₁ = a₂ yields f(a₁) = f(a₂).
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_unbounded_same_memory {M : Type} [Fintype M] (choice : List PrioritizedBorelForkEdge → Bool) (memory : List PrioritizedBorelForkEdge → M) (d : ℕ) : ∃ u : List Bool, ∃ m : M, ∃ S : Finset (List Bool), d < S.card ∧ (∀ h ∈ S, PrioritizedBorelForkValid (fun v k => choice (prioritized_borel_fork_expand v k)) u h ∧ memory (prioritized_borel_fork_expand u h) = m ∧ PrioritizedBorelForkRun 0 (prioritized_borel_fork_expand u h) 0 ∧ (prioritized_borel_fork_expand u h).map PrioritizedBorelForkEdge.dir = u.flatMap (fun b => [false, false, b])) ∧ (∀ h ∈ S, ∀ k ∈ S, prioritized_borel_fork_expand u h = prioritized_borel_fork_expand u k → h = k) := by obtain ⟨u, m, S, hcard, hvalid⟩ := prioritized_borel_fork_memory_fiber_unbounded (fun v k => choice (prioritized_borel_fork_expand v k)) (fun v k => memory (prioritized_borel_fork_expand v k)) d refine ⟨u, m, S, hcard, ?_, ?_⟩ · intro h hh obtain ⟨hv, hm⟩ := hvalid h hh exact ⟨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) have he := congrArg prioritized_borel_fork_hidden_decode heq simpa [h1, h2] using he