AFTD Auto-Formalizing Theoretical Domains

prioritized_borel_prefix_language_isClosed

theoremverified

For any predicate on finite words over a discrete topological alphabet, the set of infinite sequences all of whose finite prefixes satisfy it is closed.

Statement

theorem prioritized_borel_prefix_language_isClosed
    (A : Type*) [TopologicalSpace A] [DiscreteTopology A]
    (P : List A → Prop) :
    IsClosed {f : ℕ → A | ∀ n : ℕ, P (List.ofFn (fun i : Fin n => f i))}
Source
IN-829: compactness route to finite compatible plays.
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

The set of infinite sequences whose prefixes all satisfy P is expressed as the countable intersection over all lengths n ∈ ℕ of the sets of sequences whose length-n prefix satisfies P. Since an arbitrary intersection of closed sets is closed, it suffices to show that each length-n prefix condition defines a closed set. For a fixed n, this set is the preimage of a subset of Fin n → A under the restriction map. Because A is discrete and Fin n is finite, the function space Fin n → A is discrete, making the target subset closed; since the restriction map is continuous, its preimage is closed.

  1. The set of infinite sequences whose prefixes all satisfy P is equal to the intersection ⋂ (n : ℕ), {f : ℕ → A | P (f|_(Fin n))}.

    By function extensionality (`ext f`), an infinite sequence f satisfies the prefix predicate P for all n ∈ ℕ if and only if it belongs to the corresponding set for each individual n, which is the defining condition for membership in the indexed intersection. The simplifier (`simp`) unfolds these set comprehensions and verifies the equivalence.

    lines 5–8

      have he : {f : ℕ → A | ∀ n : ℕ, P (List.ofFn (fun i : Fin n => f i))} =
          ⋂ n : ℕ, {f : ℕ → A | P (List.ofFn (fun i : Fin n => f i))} := by
        ext f
        simp
  2. It suffices to show that for every n ∈ ℕ, the set of sequences whose prefix of length n satisfies P is closed.

    Rewriting the goal with the intersection equality, `isClosed_iInter` reduces the problem of showing that the intersection is closed to showing that each component set is closed. We then introduce an arbitrary index n ∈ ℕ (`intro n`).

    lines 9–11

    uses isClosed_iInter

      rw [he]
      apply isClosed_iInter
      intro n
  3. The set T ⊆ (Fin n → A) of length-n prefixes satisfying P is closed.

    Let T be the set of functions g : Fin n → A whose list representation satisfies P. Since A has the discrete topology and Fin n is finite, the product space Fin n → A is discrete, and therefore every subset of it is closed by `isClosed_discrete`.

    lines 12–13

    uses isClosed_discrete

      let T : Set (Fin n → A) := {f | P (List.ofFn f)}
      have hT : IsClosed T := isClosed_discrete T
  4. The prefix restriction map is continuous, and therefore the set of sequences whose prefix of length n satisfies P is closed.

    The map restricting a sequence f : ℕ → A to its first n elements is continuous because, by `continuous_pi`, a map into a product space is continuous if each coordinate projection is continuous, and each coordinate projection is the evaluation map at i ∈ Fin n, which is continuous by `continuous_apply`. The set of sequences whose prefix satisfies P is the preimage of T under this restriction map; since T is closed and the restriction map is continuous, the preimage is closed.

    lines 14–17

    uses continuous_pi, continuous_apply

      have hc : Continuous (fun f : ℕ → A => fun i : Fin n => f i) := by
        refine continuous_pi (fun i : Fin n => ?_)
        exact continuous_apply (i : ℕ)
      exact hT.preimage hc
isClosed_iInter
An arbitrary (indexed) intersection of closed sets in a topological space is closed.
isClosed_discrete
In a topological space with the discrete topology, every subset is closed.
continuous_pi
A function into a product space is continuous if each of its coordinate projections is continuous.
continuous_apply
For any coordinate index i, the evaluation (projection) map p ↦ p(i) from a product space is continuous.

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_prefix_language_isClosed    (A : Type*) [TopologicalSpace A] [DiscreteTopology A]    (P : List A → Prop) :    IsClosed {f : ℕ → A | ∀ n : ℕ, P (List.ofFn (fun i : Fin n => f i))} := by  have he : {f : ℕ → A | ∀ n : ℕ, P (List.ofFn (fun i : Fin n => f i))} =      ⋂ n : ℕ, {f : ℕ → A | P (List.ofFn (fun i : Fin n => f i))} := by    ext f    simp  rw [he]  apply isClosed_iInter  intro n  let T : Set (Fin n → A) := {f | P (List.ofFn f)}  have hT : IsClosed T := isClosed_discrete T  have hc : Continuous (fun f : ℕ → A => fun i : Fin n => f i) := by    refine continuous_pi (fun i : Fin n => ?_)    exact continuous_apply (i : ℕ)  exact hT.preimage hc
See it in the graphDiscuss this resultChallenge it