AFTD Auto-Formalizing Theoretical Domains

prioritized_borel_prefix_isolated_language_finite

theoremverified

For a compact discrete alphabet, the infinite sequences all of whose finite prefixes satisfy a given predicate form a finite set if each such sequence is uniquely determined by a finite prefix.

Statement

theorem prioritized_borel_prefix_isolated_language_finite
    (A : Type*) [TopologicalSpace A] [DiscreteTopology A] [CompactSpace A]
    (P : List A → Prop)
    (hisolate : ∀ f : ℕ → A, (∀ n, P (List.ofFn (fun i : Fin n => f i))) →
      ∃ n : ℕ, ∀ g : ℕ → A, (∀ m, P (List.ofFn (fun i : Fin m => g i))) →
        (∀ i < n, g i = f i) → g = f) :
    {f : ℕ → A | ∀ n : ℕ, P (List.ofFn (fun i : Fin n => f i))}.Finite
Source
IN-829: compactness route to finite compatible plays.
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2

The proof, explained

The set of sequences whose finite prefixes all satisfy P forms a closed subset of the product space A^ℕ. Because the alphabet A is compact and discrete, any closed subset of A^ℕ whose elements are each isolated by a finite prefix must be finite. Applying this general fact reduces the claim to the isolation property, which is provided directly by the theorem's hypothesis.

  1. It suffices to verify that each sequence in the set is uniquely determined within the set by some finite prefix.

    By prioritized_borel_compact_isolated_paths_finite, a closed subset of the sequence space A^ℕ over a compact discrete alphabet A is finite if each point is isolated by a finite prefix. The set of sequences whose prefixes all satisfy P is closed by prioritized_borel_prefix_language_isClosed, so the goal reduces to establishing the prefix-isolation property for this set.

    line 8

    uses prioritized_borel_compact_isolated_paths_finite, prioritized_borel_prefix_language_isClosed

      apply prioritized_borel_compact_isolated_paths_finite A _ (prioritized_borel_prefix_language_isClosed A P)
  2. The prefix-isolation condition holds for every sequence in the set.

    This is precisely the assumed hypothesis hisolate, which asserts that any sequence whose prefixes satisfy P is uniquely determined among all such sequences by an initial prefix of some length n.

    line 9

      exact hisolate
prioritized_borel_compact_isolated_paths_finite
In the sequence space over a compact discrete space, any closed set whose elements are each uniquely determined within the set by a finite prefix is finite.
prioritized_borel_prefix_language_isClosed
In the sequence space over a discrete space, the set of sequences whose finite prefixes all satisfy a given predicate is closed.

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_isolated_language_finite    (A : Type*) [TopologicalSpace A] [DiscreteTopology A] [CompactSpace A]    (P : List A → Prop)    (hisolate : ∀ f : ℕ → A, (∀ n, P (List.ofFn (fun i : Fin n => f i))) →      ∃ n : ℕ, ∀ g : ℕ → A, (∀ m, P (List.ofFn (fun i : Fin m => g i))) →        (∀ i < n, g i = f i) → g = f) :    {f : ℕ → A | ∀ n : ℕ, P (List.ofFn (fun i : Fin n => f i))}.Finite := by  apply prioritized_borel_compact_isolated_paths_finite A _ (prioritized_borel_prefix_language_isClosed A P)  exact hisolate
See it in the graphDiscuss this resultChallenge it