exists_min_factor_coverage_subset
Every factor coverage D ∈ H(w) contains some inclusion-minimal factor coverage C ∈ H_min(w).
Statement
theorem exists_min_factor_coverage_subset {α : Type*} [DecidableEq α] (w : List α) {D : Finset ℕ} (hD : D ∈ word_factor_coverages w) : ∃ C ∈ word_min_factor_coverages w, C ⊆ D
- Source
- Helper for arXiv:2610.10950 (Smallest String Attractors and Minimal Coverage Certificates of Thue–Morse Words), Proposition 3.2 (every member of the finite family H(w) lies above a minimal one).
- Verified
- 12 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- word_min_factor_coveragesH_min(w): the inclusion-minimal members of H(w), the family of factor coverages of w.
- word_factor_coveragesH(w): the family of coverages Cov_w(x) of the nonempty factors x of w.
- Used by 1
- is_string_attractor_iff_forall_min_factor_coverageFor every finite word w and every Γ ⊆ [1, |w|], Γ is a string attractor of w if and only if Γ ∩ C ≠ ∅ for every inclusion-minimal factor…
The proof, explained
We consider the collection of all factor coverages of w that are subsets of D. Because D itself belongs to this collection, it is non-empty, and by the well-foundedness of finite set cardinality, it contains an element C of minimal cardinality. If there were a factor coverage E strictly contained in C, it would also be a subset of D with strictly smaller cardinality, contradicting the choice of C. Hence C is inclusion-minimal and satisfies C ⊆ D.
There exists a factor coverage C ⊆ D of minimal cardinality among all factor coverages contained in D.
The set S = {C ∈ word_factor_coverages w | C ⊆ D} is non-empty because D ∈ word_factor_coverages w and D ⊆ D (by subset_rfl). Since the cardinality of finite sets is a well-founded measure on Finset ℕ, every non-empty collection has an element C of minimal cardinality, so no element in S has strictly smaller cardinality than C.
uses
subset_rflobtain ⟨C, ⟨hCH, hCD⟩, hmin⟩ := (measure Finset.card).wf.has_min {C | C ∈ word_factor_coverages w ∧ C ⊆ D} ⟨D, hD, subset_rfl⟩To show that C is an inclusion-minimal factor coverage contained in D, it suffices to show that every factor coverage E ⊆ C satisfies E = C.
We provide C as the candidate minimal factor coverage. We already know C is a factor coverage and C ⊆ D. By the definition of word_min_factor_coverages, C is inclusion-minimal if every factor coverage E contained in C is equal to C.
refine ⟨C, ⟨hCH, fun E hE hEC => ?_⟩, hCD⟩
Any factor coverage E ⊆ C must equal C.
Suppose for contradiction that E ≠ C (hne). Because E ⊆ C and E ≠ C, E is a strict subset of C (Finset.ssubset_iff_subset_ne.2), which implies |E| < |C| by Finset.card_lt_card. Moreover, E is a factor coverage and E ⊆ D by transitivity (hEC.trans hCD), so E belongs to the collection S. This contradicts the cardinality-minimality of C (hmin).
uses
Finset.card_lt_card,Finset.ssubset_iff_subset_ne.2by_contra hne exact hmin E ⟨hE, hEC.trans hCD⟩ (Finset.card_lt_card (Finset.ssubset_iff_subset_ne.2 ⟨hEC, hne⟩))
subset_rfl- Any set is a subset of itself: a ⊆ a.
Finset.card_lt_card- A strict subset of a finite set has strictly smaller cardinality: if s ⊂ t, then |s| < |t|.
Finset.ssubset_iff_subset_ne.2- If s is a subset of t and s ≠ t, then s is a strict subset of t (s ⊂ t).
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 exists_min_factor_coverage_subset {α : Type*} [DecidableEq α] (w : List α) {D : Finset ℕ} (hD : D ∈ word_factor_coverages w) : ∃ C ∈ word_min_factor_coverages w, C ⊆ D := by obtain ⟨C, ⟨hCH, hCD⟩, hmin⟩ := (measure Finset.card).wf.has_min {C | C ∈ word_factor_coverages w ∧ C ⊆ D} ⟨D, hD, subset_rfl⟩ refine ⟨C, ⟨hCH, fun E hE hEC => ?_⟩, hCD⟩ by_contra hne exact hmin E ⟨hE, hEC.trans hCD⟩ (Finset.card_lt_card (Finset.ssubset_iff_subset_ne.2 ⟨hEC, hne⟩))