prioritized_borel_fork_strategy_obstruction
For any history-dependent strategy and any finite-memory assignment, arbitrarily many distinct legal strategy-consistent runs return to q on one visible finite branch and one memory value.
Statement
theorem prioritized_borel_fork_strategy_obstruction {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, prioritized_borel_fork_consistent choice [] (prioritized_borel_fork_expand 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 8
- 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_expandExpand equally indexed visible bits and hidden stay-or-excursion choices into three-edge blocks.
- prioritized_borel_fork_setupThe first two forced edges of a fork excursion.
- 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…
- prioritized_borel_fork_valid_consistentEvery valid hidden block history expands to an edge history consistent with the actual history-dependent p-owned choice function.
- PrioritizedBorelForkValidBlockwise histories: every history may stay for an arbitrary visible bit, or take a hidden excursion only when the strategy chooses that…
The proof, explained
The theorem shows that for any history-dependent strategy and finite-memory assignment, there are arbitrarily many distinct strategy-consistent runs that share a single visible branch and produce the same memory state at state 0. The proof applies prioritized_borel_fork_unbounded_same_memory to the strategy shifted by the initial setup prefix, producing a visible branch u, memory value m, and a set of hidden branches S of size exceeding d. It then uses prioritized_borel_fork_valid_consistent to convert the validity of each run under the shifted strategy into consistency with the original strategy starting from the empty history.
There exist a visible sequence u, a memory value m, and a finite set S of hidden sequences with |S| > d whose expansions have memory m, cycle from state 0 to state 0, match the prescribed directions, are pairwise distinct, and are valid under the setup-shifted strategy.
We apply prioritized_borel_fork_unbounded_same_memory with the bound d, the given memory function, and the shifted strategy H ↦ choice (H ++ prioritized_borel_fork_setup). This yields witnesses u, m, and S along with the size bound |S| > d (hc), injectivity of the expansion on S (hinj), and the validity, memory, run, and direction properties for every h ∈ S (hv).
uses
prioritized_borel_fork_unbounded_same_memoryobtain ⟨u, m, S, hc, hv, hinj⟩ := prioritized_borel_fork_unbounded_same_memory (fun H => choice (H ++ prioritized_borel_fork_setup)) memory d
The witnesses u, m, and S satisfy all conditions of the theorem, with each branch expansion consistent with choice from the empty prefix.
We supply u, m, and S as the witnesses for the existential goal. The cardinality bound |S| > d and the injectivity of the expansion map follow immediately from hc and hinj. For any h ∈ S, we unpack its memory value m, its cycle property from 0 to 0, and its direction sequence from hv; we then apply prioritized_borel_fork_valid_consistent to convert the validity hypothesis hvalid under the shifted strategy into consistency with choice starting from the empty prefix.
uses
prioritized_borel_fork_valid_consistentrefine ⟨u, m, S, hc, ?_, hinj⟩ intro h hh obtain ⟨hvalid, hmem, hrun, hdir⟩ := hv h hh exact ⟨prioritized_borel_fork_valid_consistent choice hvalid, hmem, hrun, hdir⟩
prioritized_borel_fork_unbounded_same_memory- Given a strategy, a finite-memory assignment, and a bound d, there exist a visible sequence u, a memory value m, and a finite set S of hidden sequences with |S| > d such that every expansion is valid, yields memory m, forms a cycle at state 0, has directions prescribed by u, and the expansion map is injective on S.
prioritized_borel_fork_valid_consistent- If an expanded run is valid for the strategy shifted by the initial setup prefix, then it is consistent with the original strategy starting from the empty prefix.
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_obstruction {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, prioritized_borel_fork_consistent choice [] (prioritized_borel_fork_expand 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, hc, hv, hinj⟩ := prioritized_borel_fork_unbounded_same_memory (fun H => choice (H ++ prioritized_borel_fork_setup)) memory d refine ⟨u, m, S, hc, ?_, hinj⟩ intro h hh obtain ⟨hvalid, hmem, hrun, hdir⟩ := hv h hh exact ⟨prioritized_borel_fork_valid_consistent choice hvalid, hmem, hrun, hdir⟩