AFTD Auto-Formalizing Theoretical Domains

prioritized_borel_compact_isolated_paths_finite

theoremverified

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

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

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

    lines 6–8

    uses isDiscrete_iff_forall_mem_exists_isOpen.mpr

      have hc : IsCompact S := hclosed.isCompact
      apply hc.finite
      apply isDiscrete_iff_forall_mem_exists_isOpen.mpr
  2. 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.

    lines 9–11

      intro f hf
      obtain ⟨n, hn⟩ := hisolate f hf
      let U : Set (ℕ → A) := {g | ∀ i < n, g i = f i}
  3. 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.

    lines 12–20

    uses isOpen_biInter_finset, isOpen_discrete, continuous_apply

      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)
  4. 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}.

    lines 21–29

      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.

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