AFTD Auto-Formalizing Theoretical Domains

prioritized_borel_fork_strategy_obstruction

theoremverified

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

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.

  1. 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).

    lines 14–15

    uses prioritized_borel_fork_unbounded_same_memory

      obtain ⟨u, m, S, hc, hv, hinj⟩ := prioritized_borel_fork_unbounded_same_memory
        (fun H => choice (H ++ prioritized_borel_fork_setup)) memory d
  2. 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.

    lines 16–19

    uses prioritized_borel_fork_valid_consistent

      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⟩
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

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⟩
See it in the graphDiscuss this resultChallenge it