AFTD Auto-Formalizing Theoretical Domains

prioritized_borel_fork_strategy_fixed_branch

theoremverified

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
Used by 1

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.

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

    lines 15–18

    uses prioritized_borel_fork_fixed_branch_memory_fibers

      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, ?_⟩
  2. 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.

    lines 19–22

      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, ?_, ?_⟩
  3. 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.

    lines 23–26

    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)⟩
  4. 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.

    lines 27–33

    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

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