prioritized_borel_constrained_history_shadow
A prefix-closed finite-alphabet history tree has an infinite branch meeting pointwise allowed-value constraints whenever arbitrarily long constrained histories exist.
Statement
theorem prioritized_borel_constrained_history_shadow (A : Type) [Fintype A] (P : List A → Prop) (allowed : ℕ → A → Prop) (hprefix : ∀ xs ys, P (xs ++ ys) → P xs) (hdepth : ∀ n, ∃ xs : List A, xs.length = n ∧ P xs ∧ ∀ (i : ℕ) (hi : i < xs.length), allowed i xs[i]) : ∃ f : ℕ → A, (∀ n, P (List.ofFn (fun i : Fin n => f i))) ∧ ∀ i, allowed i (f i)
- Source
- Filed by the prover as a step towards another result
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- prioritized_borel_finite_history_shadowLet 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…
The proof, explained
The proof reduces the constrained branch existence problem to the unconstrained branch theorem prioritized_borel_finite_history_shadow. We define a predicate Q on lists that packages the history property P together with the pointwise constraint allowed on each entry. Because P is prefix-closed and list concatenation preserves initial entries, Q is also prefix-closed and contains lists of arbitrary length. Applying the unconstrained theorem to Q produces an infinite sequence whose prefixes satisfy Q, immediately guaranteeing both P at all finite prefixes and allowed at every position.
Define a combined predicate Q incorporating both the tree property P and the pointwise validity constraints.
Using classical logic, we introduce Q(xs) on lists xs as the conjunction of P(xs) and the requirement that for every index i < xs.length, the value xs[i] satisfies allowed i xs[i].
classical let Q : List A → Prop := fun xs => P xs ∧ ∀ (i : ℕ) (hi : i < xs.length), allowed i xs[i]
The combined predicate Q is prefix-closed.
Given Q(xs ++ ys), its first component implies P(xs ++ ys), so P(xs) holds by the prefix-closedness of P. For any index i < xs.length, i is also strictly less than (xs ++ ys).length, so (xs ++ ys)[i] is allowed; by List.getElem_append_left, (xs ++ ys)[i] = xs[i], meaning every element of xs is allowed.
uses
List.getElem_append_lefthave hQprefix : ∀ xs ys, Q (xs ++ ys) → Q xs := by intro xs ys h refine ⟨hprefix xs ys h.1, ?_⟩ intro i hi have hh := h.2 i (by simp; omega) rw [List.getElem_append_left hi] at hh exact hh
The predicate Q admits histories of arbitrary length.
For any n, the hypothesis hdepth directly supplies a list xs of length n such that P(xs) holds and all its elements satisfy allowed. By definition of Q, this list satisfies Q(xs).
have hQdepth : ∀ n, ∃ xs : List A, xs.length = n ∧ Q xs := by intro n obtain ⟨xs, hlen, hp, ha⟩ := hdepth n exact ⟨xs, hlen, hp, ha⟩
There exists an infinite sequence f whose initial segments all satisfy Q.
Because the alphabet A is finite and Q is a prefix-closed predicate with histories of every finite length, prioritized_borel_finite_history_shadow yields a sequence f : ℕ → A such that each prefix of length n satisfies Q.
uses
prioritized_borel_finite_history_shadowobtain ⟨f, hf⟩ := prioritized_borel_finite_history_shadow A Q hQprefix hQdepthThe sequence f satisfies P on every initial segment and satisfies the constraint allowed at every position.
For every n, the prefix of length n satisfies P because it satisfies Q. Furthermore, for any index i, inspecting the prefix of length i + 1 shows its i-th entry is allowed; by List.getElem_ofFn, that i-th entry is exactly f(i), establishing allowed i (f i).
uses
List.getElem_ofFnrefine ⟨f, fun n => (hf n).1, ?_⟩ intro i have hh := (hf (i+1)).2 i (by simp) simpa only [List.getElem_ofFn] using hh
List.getElem_append_left- For any list concatenation as ++ bs, an element at index i with i < as.length is equal to as[i].
List.getElem_ofFn- In a list constructed by List.ofFn f, the element at index i is f(i).
prioritized_borel_finite_history_shadow- For a finite alphabet A, any prefix-closed predicate P on lists admitting paths of arbitrary length has an infinite sequence f whose initial segments all satisfy 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
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_constrained_history_shadow (A : Type) [Fintype A] (P : List A → Prop) (allowed : ℕ → A → Prop) (hprefix : ∀ xs ys, P (xs ++ ys) → P xs) (hdepth : ∀ n, ∃ xs : List A, xs.length = n ∧ P xs ∧ ∀ (i : ℕ) (hi : i < xs.length), allowed i xs[i]) : ∃ f : ℕ → A, (∀ n, P (List.ofFn (fun i : Fin n => f i))) ∧ ∀ i, allowed i (f i) := by classical let Q : List A → Prop := fun xs => P xs ∧ ∀ (i : ℕ) (hi : i < xs.length), allowed i xs[i] have hQprefix : ∀ xs ys, Q (xs ++ ys) → Q xs := by intro xs ys h refine ⟨hprefix xs ys h.1, ?_⟩ intro i hi have hh := h.2 i (by simp; omega) rw [List.getElem_append_left hi] at hh exact hh have hQdepth : ∀ n, ∃ xs : List A, xs.length = n ∧ Q xs := by intro n obtain ⟨xs, hlen, hp, ha⟩ := hdepth n exact ⟨xs, hlen, hp, ha⟩ obtain ⟨f, hf⟩ := prioritized_borel_finite_history_shadow A Q hQprefix hQdepth refine ⟨f, fun n => (hf n).1, ?_⟩ intro i have hh := (hf (i+1)).2 i (by simp) simpa only [List.getElem_ofFn] using hh