prioritized_borel_compact_isolated_paths_finite
A closed set of infinite paths over a compact discrete alphabet is finite if each of its paths is uniquely determined within the set by a finite prefix.
Statement
theorem prioritized_borel_compact_isolated_paths_finite (A : Type*) [TopologicalSpace A] [DiscreteTopology A] [CompactSpace A] (S : Set (ℕ → A)) (hclosed : IsClosed S) (hisolate : ∀ f ∈ S, ∃ n : ℕ, ∀ g ∈ S, (∀ i < n, g i = f i) → g = f) : S.Finite
- Source
- IN-829: compactness route to finite compatible plays.
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 2
- prioritized_borel_compact_prefix_isolation_uniformIf a closed set of paths over a compact discrete alphabet has each path determined by some finite prefix, then one common prefix length…
- 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
Since the discrete alphabet A is compact, the infinite product space A^ℕ is compact by Tychonoff's theorem, so the closed subset S is compact. Because any compact discrete space is finite, it suffices to prove that S inherits the discrete topology. For each path f ∈ S, the prefix isolation assumption provides a cylinder set U of paths agreeing with f on a finite initial segment; U is open as a finite intersection of preimages of singletons under continuous projections, and its intersection with S is precisely {f}.
It suffices to show that each path in S is isolated within S by an ambient open neighborhood.
Since the discrete alphabet A is compact, the product space A^ℕ is compact by Tychonoff's theorem. The closed set S is therefore compact. A compact space that is discrete is necessarily finite, so the goal reduces to showing that S has the discrete subspace topology. By isDiscrete_iff_forall_mem_exists_isOpen.mpr, this holds if every f ∈ S has an ambient open neighborhood U such that U ∩ S = {f}.
uses
isDiscrete_iff_forall_mem_exists_isOpen.mprhave hc : IsCompact S := hclosed.isCompact apply hc.finite apply isDiscrete_iff_forall_mem_exists_isOpen.mpr
For a given path f ∈ S, let n be the prefix length isolating f in S, and define the cylinder set U of paths that match f on the first n positions.
Fix f ∈ S. By the isolation hypothesis hisolate, there is an index bound n such that any path in S matching f on all coordinates i < n must equal f. We define the cylinder set U as the set of all paths g : ℕ → A satisfying g i = f i for all i < n.
intro f hf obtain ⟨n, hn⟩ := hisolate f hf let U : Set (ℕ → A) := {g | ∀ i < n, g i = f i}
The cylinder set U is open in the product topology.
The cylinder U is the finite intersection over i < n of the sets {g | g i = f i}. By isOpen_biInter_finset, a finite intersection of open sets is open. For each index i, the set {g | g i = f i} is the preimage of the singleton {f i} under the projection map g ↦ g i. Since A has the discrete topology, {f i} is open by isOpen_discrete; because coordinate projections are continuous by continuous_apply, this preimage is open. Therefore, U is open.
uses
isOpen_biInter_finset,isOpen_discrete,continuous_applyhave hUopen : IsOpen U := by have he : U = ⋂ i ∈ Finset.range n, {g : ℕ → A | g i = f i} := by ext g simp [U] rw [he] apply isOpen_biInter_finset intro i hi change IsOpen ((fun g : ℕ → A => g i) ⁻¹' ({f i} : Set A)) exact (isOpen_discrete ({f i} : Set A)).preimage (continuous_apply i)
The intersection U ∩ S is precisely {f}, completing the proof.
We provide U and its openness as the witness isolating f in S. For the forward inclusion, if g ∈ U ∩ S, then g ∈ S and g agrees with f on the first n coordinates, so g = f by the choice of n. For the reverse inclusion, f ∈ S by assumption and f trivially agrees with itself on the first n coordinates (so f ∈ U), showing {f} ⊆ U ∩ S. Hence U ∩ S = {f}.
refine ⟨U,hUopen,?_⟩ ext g constructor · rintro ⟨hgU,hgS⟩ exact hn g hgS hgU · intro hg have heq : g=f := by simpa using hg subst g exact ⟨by simp [U],hf⟩
isDiscrete_iff_forall_mem_exists_isOpen.mpr- A subset of a topological space is discrete if every point of the subset has an open neighborhood in the ambient space whose intersection with the subset is that singleton.
isOpen_biInter_finset- The intersection of a family of open sets indexed by a finite set is open.
isOpen_discrete- In a space with the discrete topology, every subset is open.
continuous_apply- In a product space, the coordinate projection map is continuous.
- The compactness of the product space A^ℕ is inferred automatically by Lean via Tychonoff's theorem (as a CompactSpace instance on ℕ → A), allowing hclosed.isCompact to be invoked directly without an explicit manual step for Tychonoff's theorem.
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_compact_isolated_paths_finite (A : Type*) [TopologicalSpace A] [DiscreteTopology A] [CompactSpace A] (S : Set (ℕ → A)) (hclosed : IsClosed S) (hisolate : ∀ f ∈ S, ∃ n : ℕ, ∀ g ∈ S, (∀ i < n, g i = f i) → g = f) : S.Finite := by have hc : IsCompact S := hclosed.isCompact apply hc.finite apply isDiscrete_iff_forall_mem_exists_isOpen.mpr intro f hf obtain ⟨n, hn⟩ := hisolate f hf let U : Set (ℕ → A) := {g | ∀ i < n, g i = f i} have hUopen : IsOpen U := by have he : U = ⋂ i ∈ Finset.range n, {g : ℕ → A | g i = f i} := by ext g simp [U] rw [he] apply isOpen_biInter_finset intro i hi change IsOpen ((fun g : ℕ → A => g i) ⁻¹' ({f i} : Set A)) exact (isOpen_discrete ({f i} : Set A)).preimage (continuous_apply i) refine ⟨U,hUopen,?_⟩ ext g constructor · rintro ⟨hgU,hgS⟩ exact hn g hgS hgU · intro hg have heq : g=f := by simpa using hg subst g exact ⟨by simp [U],hf⟩