prioritized_borel_prefix_language_isClosed
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
- prioritized_borel_prefix_isolated_language_finiteFor a compact discrete alphabet, the infinite sequences all of whose finite prefixes satisfy a given predicate form a finite set if each…
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.
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.
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
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`).
uses
isClosed_iInterrw [he] apply isClosed_iInter intro n
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`.
uses
isClosed_discretelet T : Set (Fin n → A) := {f | P (List.ofFn f)} have hT : IsClosed T := isClosed_discrete T
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.
uses
continuous_pi,continuous_applyhave 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.
- Lean's typeclass inference automatically supplies the instance that the finite product space `Fin n → A` has the discrete topology, which is required by `isClosed_discrete`.
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_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