AFTD Auto-Formalizing Theoretical Domains

prioritized_borel_fork_one_branch_memory_fibers

theoremverified

For any finite-memory assignment, one infinite visible sequence has prefixes with arbitrarily large compatible hidden-history fibers at some memory value.

Statement

theorem prioritized_borel_fork_one_branch_memory_fibers {M : Type} [Fintype M]
    (color : List Bool → List Bool → Bool) (mem : List Bool → List Bool → M) :
    ∃ f : ℕ → Bool, ∀ d, ∃ n, ∃ m : M, ∃ S : Finset (List Bool),
      d < S.card ∧ ∀ h ∈ S,
        PrioritizedBorelForkValid color (List.ofFn (fun i : Fin n => f i)) h ∧
        mem (List.ofFn (fun i : Fin n => f i)) h = m
Source
arXiv:2611.10136, Section 5.3.2; the three-state fork subarena
Verified
12 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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_one_infinite_branchFor every history-dependent fork response, one infinite visible block sequence has prefixes with arbitrarily many compatible hidden…
Used by 1

The proof, explained

The proof applies the pigeonhole principle to an infinite visible sequence obtained from `prioritized_borel_fork_one_infinite_branch`. That sequence has the property that its prefix of any length $n$ admits at least $n + 1$ compatible valid hidden histories. To obtain a fiber of size greater than $d$ for a finite memory type $M$, we choose the prefix length $n = |M| \cdot d$, ensuring at least $|M| \cdot d + 1$ valid hidden histories. By the pigeonhole principle, some memory value $m \in M$ must be attained by more than $d$ of these histories, giving the desired memory fiber.

  1. There exists an infinite binary sequence $f$ whose prefixes have arbitrarily large sets of valid hidden histories.

    Using `prioritized_borel_fork_one_infinite_branch`, we obtain an infinite sequence $f : \mathbb{N} \to \text{Bool}$ such that for every length $n$, there is a finite set of hidden histories of cardinality at least $n + 1$ valid with respect to the prefix of $f$ of length $n$. We choose this $f$ as the candidate branch.

    lines 7–9

    uses prioritized_borel_fork_one_infinite_branch

      classical
      obtain ⟨f, hf⟩ := prioritized_borel_fork_one_infinite_branch color
      refine ⟨f, ?_⟩
  2. For any target fiber size $d$, choosing prefix length $n = |M| \cdot d$ yields a set $T$ of at least $|M| \cdot d + 1$ valid hidden histories compatible with prefix $u$.

    Given $d$, we define the prefix length $n = |M| \cdot d$ and denote by $u$ the length-$n$ prefix of $f$. Evaluating the property of $f$ at $n$ yields a finite set $T$ of hidden histories with $|T| \ge n + 1$ that are all valid with respect to $u$.

    lines 10–13

      intro d
      let n := Fintype.card M * d
      let u : List Bool := List.ofFn (fun i : Fin n => f i)
      obtain ⟨T, hsize, hvalid⟩ := hf n
  3. The cardinality of $T$ strictly exceeds $|\text{Finset.univ}| \cdot d$, where $\text{Finset.univ}$ is the universal set of $M$. automation

    Rewriting $|\text{Finset.univ}|$ to $|M|$ via `Finset.card_univ` and unfolding $n$ in $|T| \ge |M| \cdot d + 1$, the strict inequality $|M| \cdot d < |T|$ is established by linear arithmetic (`omega`).

    lines 14–17

    uses Finset.card_univ

      have hlarge : (Finset.univ : Finset M).card * d < T.card := by
        simp only [Finset.card_univ]
        dsimp [n] at hsize
        omega
  4. There exists a memory state $m \in M$ whose fiber in $T$ under $\text{mem}(u, \cdot)$ has cardinality strictly greater than $d$.

    The memory function maps $T$ into the universal finset of $M$. Because $|T| > |M| \cdot d$, the pigeonhole principle (`Finset.exists_lt_card_fiber_of_mul_lt_card_of_maps_to`) guarantees the existence of a state $m \in M$ such that the fiber $\{h \in T \mid \text{mem}(u, h) = m\}$ has size strictly greater than $d$.

    lines 18–20

    uses Finset.exists_lt_card_fiber_of_mul_lt_card_of_maps_to

      obtain ⟨m, _, hm⟩ := Finset.exists_lt_card_fiber_of_mul_lt_card_of_maps_to
        (s := T) (t := Finset.univ) (f := mem u) (n := d)
        (by simp) hlarge
  5. The prefix length $n$, memory state $m$, and fiber $S = \{h \in T \mid \text{mem}(u, h) = m\}$ satisfy all required properties.

    We provide $n$, $m$, and the fiber $S = \{h \in T \mid \text{mem}(u, h) = m\}$ as witnesses. Its cardinality exceeds $d$ by the pigeonhole step. Decomposing the filter membership via `Finset.mem_filter.mp` shows that every $h \in S$ belongs to $T$ (hence is valid with respect to $u$) and evaluates under $\text{mem}(u, \cdot)$ to $m$.

    lines 21–24

    uses Finset.mem_filter.mp

      refine ⟨n, m, T.filter (fun h => mem u h = m), hm, ?_⟩
      intro h hh
      obtain ⟨hhT, hhm⟩ := Finset.mem_filter.mp hh
      exact ⟨hvalid h hhT, hhm⟩
prioritized_borel_fork_one_infinite_branch
There exists an infinite binary sequence $f$ such that for every prefix length $n$, there are at least $n + 1$ valid hidden histories compatible with the prefix of $f$ of length $n$.
Finset.card_univ
The cardinality of the universal finset `Finset.univ` of a finite type $\alpha$ equals `Fintype.card \alpha`.
Finset.exists_lt_card_fiber_of_mul_lt_card_of_maps_to
If a map from a finite set $s$ into a finite set $t$ satisfies $|s| > |t| \cdot n$, then some element $y \in t$ has a fiber $\{x \in s \mid f(x) = y\}$ of cardinality strictly greater than $n$ (pigeonhole principle).
Finset.mem_filter.mp
An element belongs to the filtered finset $\{x \in s \mid p(x)\}$ if and only if it belongs to $s$ and satisfies $p$.

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_one_branch_memory_fibers {M : Type} [Fintype M]    (color : List Bool → List Bool → Bool) (mem : List Bool → List Bool → M) :    ∃ f : ℕ → Bool, ∀ d, ∃ n, ∃ m : M, ∃ S : Finset (List Bool),      d < S.card ∧ ∀ h ∈ S,        PrioritizedBorelForkValid color (List.ofFn (fun i : Fin n => f i)) h ∧        mem (List.ofFn (fun i : Fin n => f i)) h = m := by  classical  obtain ⟨f, hf⟩ := prioritized_borel_fork_one_infinite_branch color  refine ⟨f, ?_⟩  intro d  let n := Fintype.card M * d  let u : List Bool := List.ofFn (fun i : Fin n => f i)  obtain ⟨T, hsize, hvalid⟩ := hf n  have hlarge : (Finset.univ : Finset M).card * d < T.card := by    simp only [Finset.card_univ]    dsimp [n] at hsize    omega  obtain ⟨m, _, hm⟩ := Finset.exists_lt_card_fiber_of_mul_lt_card_of_maps_to    (s := T) (t := Finset.univ) (f := mem u) (n := d)    (by simp) hlarge  refine ⟨n, m, T.filter (fun h => mem u h = m), hm, ?_⟩  intro h hh  obtain ⟨hhT, hhm⟩ := Finset.mem_filter.mp hh  exact ⟨hvalid h hhT, hhm⟩
See it in the graphDiscuss this resultChallenge it