prioritized_borel_finite_history_shadow
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
- prioritized_borel_constrained_history_shadowA prefix-closed finite-alphabet history tree has an infinite branch meeting pointwise allowed-value constraints whenever arbitrarily long…
- prioritized_borel_fork_one_infinite_branchFor every history-dependent fork response, one infinite visible block sequence has prefixes with arbitrarily many compatible hidden…
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.
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.
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
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.
uses
Fin.ofFn_take_eq_take_ofFnlet π : {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⟩
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.
uses
Subtype.ext,Fin.take_eq_self,Fin.take_takehave 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
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.
uses
Nat.le_add_right,Set.toFinitehave hfin : ∀ i a, {b : H (i+1) | π (Nat.le_add_right i 1) b = a}.Finite := by intro i a exact Set.toFinite _
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.
uses
exists_seq_forall_proj_of_forall_finiteobtain ⟨seq, hseq⟩ := exists_seq_forall_proj_of_forall_finite π hrefl htrans hfinThe 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).
uses
Nat.lt_succ_self,congrFun,congrArg,Subtype.val,Nat.succ_le_iff.mprlet 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
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).
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.
- Lists of length n are represented formally as functions Fin n → A via List.ofFn, and truncation is handled using Fin.take.
- The theorem is a formalization of König's Infinity Lemma: the tree of valid prefixes is finitely branching because the alphabet A is finite. The formal proof delegates the tree-pruning argument to exists_seq_forall_proj_of_forall_finite, which constructs an infinite thread in an inverse limit system over ℕ.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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