AFTD Auto-Formalizing Theoretical Domains

prioritized_borel_constrained_history_shadow

theoremverified

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

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.

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

    lines 8–10

      classical
      let Q : List A → Prop := fun xs => P xs ∧
        ∀ (i : ℕ) (hi : i < xs.length), allowed i xs[i]
  2. 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.

    lines 11–17

    uses List.getElem_append_left

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

    lines 18–21

      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⟩
  4. 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.

    line 22

    uses prioritized_borel_finite_history_shadow

      obtain ⟨f, hf⟩ := prioritized_borel_finite_history_shadow A Q hQprefix hQdepth
  5. The 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).

    lines 23–26

    uses List.getElem_ofFn

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

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