prioritized_borel_compact_prefix_isolation_uniform
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
- prioritized_borel_compact_isolated_paths_finiteA 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…
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.
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.
uses
prioritized_borel_compact_isolated_paths_finiteclassical have hs := prioritized_borel_compact_isolated_paths_finite A S hclosed hisolate letI : Fintype S := hs.fintypeThere 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.
let n : S → ℕ := fun f => Classical.choose (hisolate f f.property) let N : ℕ := Finset.univ.sup n refine ⟨N, ?_⟩
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.
uses
Finset.le_sup,Finset.mem_univintro f hf g hg hprefix let fs : S := ⟨f,hf⟩ have hle : n fs ≤ N := Finset.le_sup (Finset.mem_univ fs)
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.
uses
Classical.choose_spec,lt_of_lt_of_leapply (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
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_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)