AFTD Auto-Formalizing Theoretical Domains

prioritized_borel_compact_prefix_isolation_uniform

theoremverified

If a closed set of paths over a compact discrete alphabet has each path determined by some finite prefix, then one common prefix length distinguishes all of its paths.

Statement

theorem prioritized_borel_compact_prefix_isolation_uniform
    (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) :
    ∃ N : ℕ, ∀ f ∈ S, ∀ g ∈ S, (∀ i < N, g i = f i) → g = f
Source
IN-829: compactness route to a uniform choice cutoff.
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1

The proof, explained

By a previous compactness result, any closed set of paths over a compact discrete alphabet whose paths are individually isolated by finite prefixes is finite. Since the set of paths S is finite, we can assign to each path f ∈ S a finite prefix length n(f) that isolates it, and take N to be the maximum of these lengths across S. Any two paths in S that agree on the first N coordinates necessarily agree on the first n(f) coordinates, which forces them to be identical.

  1. The set of paths S is finite, allowing it to be equipped with a finite type structure.

    By prioritized_borel_compact_isolated_paths_finite, since the alphabet A is compact and discrete, S is closed, and every path in S is isolated by a finite prefix, S is finite (hs). This finiteness is registered as a Fintype instance on the subtype S.

    lines 6–8

    uses prioritized_borel_compact_isolated_paths_finite

      classical
      have hs := prioritized_borel_compact_isolated_paths_finite A S hclosed hisolate
      letI : Fintype S := hs.fintype
  2. There exists a candidate uniform prefix length N, defined as the maximum isolating prefix length across all paths in S.

    For each path f ∈ S, let n(f) be an isolating prefix length provided by hisolate. Since S is finite, the set of these lengths is finite, so we define N = sup_{f ∈ S} n(f) using Finset.univ.sup. We propose N as the uniform prefix length witness.

    lines 9–11

      let n : S → ℕ := fun f => Classical.choose (hisolate f f.property)
      let N : ℕ := Finset.univ.sup n
      refine ⟨N, ?_⟩
  3. For any paths f, g ∈ S that agree on the first N coordinates, the isolating prefix length n(f) is at most N.

    Fix paths f, g ∈ S such that g and f agree on all indices i < N. Viewing f as an element of the finite type S, it belongs to the universal finset by Finset.mem_univ, and therefore n(f) ≤ N by Finset.le_sup.

    lines 12–14

    uses Finset.le_sup, Finset.mem_univ

      intro f hf g hg hprefix
      let fs : S := ⟨f,hf⟩
      have hle : n fs ≤ N := Finset.le_sup (Finset.mem_univ fs)
  4. g = f

    By Classical.choose_spec, the choice of n(f) guarantees that g = f provided that g and f agree on all indices i < n(f). Given i < n(f), transitivity (lt_of_lt_of_le) with n(f) ≤ N implies i < N. Since g and f agree on all coordinates up to N by hypothesis, they agree at index i, completing the proof that g = f.

    lines 15–17

    uses Classical.choose_spec, lt_of_lt_of_le

      apply (Classical.choose_spec (hisolate f hf)) g hg
      intro i hi
      exact hprefix i (lt_of_lt_of_le hi hle)
prioritized_borel_compact_isolated_paths_finite
A closed set of paths over a compact discrete space in which every path is isolated by some finite prefix is finite.
Finset.le_sup
An element's value under a function is less than or equal to the supremum of that function over any finite set containing the element.
Finset.mem_univ
Every element of a finite type belongs to the universal finite set of that type.
Classical.choose_spec
The element chosen by Classical.choose satisfies the existential predicate.
lt_of_lt_of_le
In a preorder, if a < b and b ≤ c, then a < c.

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_prefix_isolation_uniform    (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) :    ∃ N : ℕ, ∀ f ∈ S, ∀ g ∈ S, (∀ i < N, g i = f i) → g = f := by  classical  have hs := prioritized_borel_compact_isolated_paths_finite A S hclosed hisolate  letI : Fintype S := hs.fintype  let n : S → ℕ := fun f => Classical.choose (hisolate f f.property)  let N : ℕ := Finset.univ.sup n  refine ⟨N, ?_⟩  intro f hf g hg hprefix  let fs : S := ⟨f,hf⟩  have hle : n fs ≤ N := Finset.le_sup (Finset.mem_univ fs)  apply (Classical.choose_spec (hisolate f hf)) g hg  intro i hi  exact hprefix i (lt_of_lt_of_le hi hle)
See it in the graphDiscuss this resultChallenge it