AFTD Auto-Formalizing Theoretical Domains

prioritized_borel_finite_history_shadow

theoremverified

Let P be a prefix-closed predicate on finite lists over a finite alphabet. If P has a list of every finite length, then there is an infinite sequence all of whose finite prefixes satisfy P.

Statement

theorem prioritized_borel_finite_history_shadow (A : Type) [Fintype A] (P : List A → Prop) (hprefix : ∀ xs ys, P (xs ++ ys) → P xs) (hdepth : ∀ n, ∃ xs : List A, xs.length = n ∧ P xs) : ∃ f : ℕ → A, ∀ n, P (List.ofFn (fun i : Fin n => f i))
Source
arXiv:2611.10136, Sections 5.2.1-5.2.4; finite-history shadowing along a fixed branch
Verified
12 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 2

The proof, explained

The theorem is an instance of König's Infinity Lemma. For each length n, the collection H(n) of valid prefixes of length n is nonempty and finite because the alphabet A is finite. Truncation defines a compatible system of projections between these sets whose fibers are finite, allowing exists_seq_forall_proj_of_forall_finite to extract a consistent sequence of prefixes of all lengths. The infinite sequence f is then obtained by reading off the n-th symbol from the prefix of length n+1, ensuring that every finite prefix of f satisfies P.

  1. For each n, the type H(n) of valid prefixes of length n is nonempty.

    We define H(n) as the subtype of functions Fin n → A whose corresponding list satisfies P. By assumption hdepth, there is a list xs of length n satisfying P. Indexing xs via xs.get produces a function Fin n → A that satisfies P, showing each H(n) is nonempty. This fact is registered for typeclass synthesis.

    lines 2–9

      classical
      let H (n : ℕ) := { f : Fin n → A // P (List.ofFn f) }
      have hn : ∀ n, Nonempty (H n) := by
        intro n
        obtain ⟨xs, hlen, hp⟩ := hdepth n
        subst n
        exact ⟨⟨xs.get, by simpa using hp⟩⟩
      letI : ∀ n, Nonempty (H n) := hn
  2. Truncation defines a projection map π : H(j) → H(i) whenever i ≤ j.

    Given i ≤ j and x ∈ H(j), we truncate x to its first i elements using Fin.take. By Fin.ofFn_take_eq_take_ofFn, the list corresponding to this truncation is the initial segment of length i of the list for x. Since P is prefix-closed (hprefix) and the original list satisfies P, the truncated list also satisfies P.

    lines 10–14

    uses Fin.ofFn_take_eq_take_ofFn

      let π : {i j : ℕ} → i ≤ j → H j → H i := fun {i j} hij x =>
        ⟨Fin.take i hij x.1, by
          rw [Fin.ofFn_take_eq_take_ofFn]
          apply hprefix _ ((List.ofFn x.1).drop i)
          simpa using x.2⟩
  3. The projection maps π satisfy the identity and transitivity laws of an inverse system.

    By Subtype.ext, equality in H(i) reduces to equality of underlying functions. At length i, truncating a function on Fin i to length i is the identity by Fin.take_eq_self. For i ≤ j ≤ k, truncating from k to j and then to i agrees with truncating directly from k to i by Fin.take_take.

    lines 15–23

    uses Subtype.ext, Fin.take_eq_self, Fin.take_take

      have hrefl : ∀ ⦃i⦄ (a : H i), π rfl.le a = a := by
        intro i a
        apply Subtype.ext
        exact Fin.take_eq_self a.1
      have htrans : ∀ ⦃i j k⦄ (hij : i ≤ j) (hjk : j ≤ k) a,
          π hij (π hjk a) = π (hij.trans hjk) a := by
        intro i j k hij hjk a
        apply Subtype.ext
        exact Fin.take_take hij hjk a.1
  4. For each i and each prefix a ∈ H(i), the fiber of extensions in H(i+1) projecting to a is finite.

    The fiber of a under the one-step projection (with i ≤ i + 1 by Nat.le_add_right) is a subset of H(i+1). Because the alphabet A is finite, the function space Fin (i+1) → A is finite, and so any subset of it is finite by Set.toFinite.

    lines 24–26

    uses Nat.le_add_right, Set.toFinite

      have hfin : ∀ i a, {b : H (i+1) | π (Nat.le_add_right i 1) b = a}.Finite := by
        intro i a
        exact Set.toFinite _
  5. There exists a compatible sequence of prefixes seq of every length.

    By König's Lemma for inverse systems (exists_seq_forall_proj_of_forall_finite), since H(0) is finite, each H(n) is nonempty, and every step has finite fibers, there exists a sequence seq assigning to each n an element of H(n) compatible with all projections: π(seq j) = seq i whenever i ≤ j.

    line 27

    uses exists_seq_forall_proj_of_forall_finite

      obtain ⟨seq, hseq⟩ := exists_seq_forall_proj_of_forall_finite π hrefl htrans hfin
  6. The infinite sequence f defined by f(n) = (seq(n+1))(n) has the property that its prefix of length n coincides with seq(n).

    We define f(n) by taking the n-th symbol of seq(n+1), which is valid since n < n + 1 by Nat.lt_succ_self. To show that the restriction of f to Fin n equals seq(n), we test an arbitrary index i < n. Since i < n implies i + 1 ≤ n by Nat.succ_le_iff.mpr, compatibility of the thread (hseq) implies that projecting seq(n) to length i + 1 yields seq(i+1). Evaluating underlying values (Subtype.val) at index i using congrArg and congrFun gives (seq n)(i) = (seq (i+1))(i) = f(i).

    lines 28–35

    uses Nat.lt_succ_self, congrFun, congrArg, Subtype.val, Nat.succ_le_iff.mpr

      let f : ℕ → A := fun n => (seq (n+1)).1 ⟨n, Nat.lt_succ_self n⟩
      refine ⟨f, ?_⟩
      intro n
      have heq : (fun i : Fin n => f i) = (seq n).1 := by
        funext i
        have h := congrFun (congrArg Subtype.val (hseq (Nat.succ_le_iff.mpr i.isLt)))
          (⟨i.val, Nat.lt_succ_self i.val⟩ : Fin (i.val+1))
        simpa [f, π, Fin.take] using h.symm
  7. Every finite prefix of f satisfies P.

    Rewriting the prefix of length n with seq(n) using the equality just proved, the condition P (List.ofFn (f|_n)) reduces to P (List.ofFn (seq n).1), which holds by definition of the subtype H(n).

    lines 36–37

      rw [heq]
      exact (seq n).2
Fin.ofFn_take_eq_take_ofFn
Converting a truncated function Fin.take m h v to a list equals taking the first m elements of List.ofFn v.
Subtype.ext
Two elements of a subtype are equal if and only if their underlying values are equal.
Fin.take_eq_self
Truncating a function on Fin n to length n yields the original function.
Fin.take_take
Truncating a function first to length n' and then to length m is identical to truncating directly to length m.
Nat.le_add_right
For any natural numbers n and k, n ≤ n + k.
Set.toFinite
Any set on a finite type is finite.
exists_seq_forall_proj_of_forall_finite
An inverse system over ℕ with nonempty levels, finite initial level, and finite fibers between successive levels admits a compatible thread.
Nat.lt_succ_self
For any natural number n, n < n + 1.
congrFun
Equal functions take equal values at any argument.
congrArg
A function applied to equal arguments yields equal values.
Subtype.val
The projection from a subtype element to its underlying value.
Nat.succ_le_iff.mpr
If m < n, then m + 1 ≤ n.

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_finite_history_shadow (A : Type) [Fintype A] (P : List A → Prop) (hprefix : ∀ xs ys, P (xs ++ ys) → P xs) (hdepth : ∀ n, ∃ xs : List A, xs.length = n ∧ P xs) : ∃ f : ℕ → A, ∀ n, P (List.ofFn (fun i : Fin n => f i)) := by  classical  let H (n : ℕ) := { f : Fin n → A // P (List.ofFn f) }  have hn : ∀ n, Nonempty (H n) := by    intro n    obtain ⟨xs, hlen, hp⟩ := hdepth n    subst n    exact ⟨⟨xs.get, by simpa using hp⟩⟩  letI : ∀ n, Nonempty (H n) := hn  let π : {i j : ℕ} → i ≤ j → H j → H i := fun {i j} hij x =>    ⟨Fin.take i hij x.1, by      rw [Fin.ofFn_take_eq_take_ofFn]      apply hprefix _ ((List.ofFn x.1).drop i)      simpa using x.2⟩  have hrefl : ∀ ⦃i⦄ (a : H i), π rfl.le a = a := by    intro i a    apply Subtype.ext    exact Fin.take_eq_self a.1  have htrans : ∀ ⦃i j k⦄ (hij : i ≤ j) (hjk : j ≤ k) a,      π hij (π hjk a) = π (hij.trans hjk) a := by    intro i j k hij hjk a    apply Subtype.ext    exact Fin.take_take hij hjk a.1  have hfin : ∀ i a, {b : H (i+1) | π (Nat.le_add_right i 1) b = a}.Finite := by    intro i a    exact Set.toFinite _  obtain ⟨seq, hseq⟩ := exists_seq_forall_proj_of_forall_finite π hrefl htrans hfin  let f : ℕ → A := fun n => (seq (n+1)).1 ⟨n, Nat.lt_succ_self n⟩  refine ⟨f, ?_⟩  intro n  have heq : (fun i : Fin n => f i) = (seq n).1 := by    funext i    have h := congrFun (congrArg Subtype.val (hseq (Nat.succ_le_iff.mpr i.isLt)))      (⟨i.val, Nat.lt_succ_self i.val⟩ : Fin (i.val+1))    simpa [f, π, Fin.take] using h.symm  rw [heq]  exact (seq n).2
See it in the graphDiscuss this resultChallenge it