AFTD Auto-Formalizing Theoretical Domains

prioritized_borel_fork_unbounded_same_memory

theoremverified

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

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.

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

    lines 14–17

    uses prioritized_borel_fork_memory_fiber_unbounded

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

    lines 18–21

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

    lines 22–26

    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

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