word_min_factor_coverages_subset
Every inclusion-minimal factor coverage is a factor coverage: H_min(w) ⊆ H(w).
Statement
theorem word_min_factor_coverages_subset {α : Type*} [DecidableEq α] (w : List α) : word_min_factor_coverages w ⊆ word_factor_coverages w
- Source
- Sanity lemma for word_min_factor_coverages (arXiv:2610.10950 (Smallest String Attractors and Minimal Coverage Certificates of Thue–Morse Words), Sec. 3.2).
- 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 2
- thue_morse_unhit_mean_nonnegFor all n and k, 0 ≤ thue_morse_unhit_mean n k.
- thue_morse_min_factor_coverages_finset_memFor every n and every C, C belongs to thue_morse_min_factor_coverages_finset n if and only if C is an inclusion-minimal factor coverage of…
The proof, explained
By definition, an inclusion-minimal factor coverage of a word w is a factor coverage satisfying an additional minimality condition. To show that the set of minimal factor coverages is a subset of the set of all factor coverages, the proof takes an arbitrary element of the former and projects out the first conjunct of its defining property.
Every element of word_min_factor_coverages w belongs to word_factor_coverages w.
To prove the subset relation, let C be an arbitrary element of word_min_factor_coverages w with membership hypothesis hC. By definition, word_min_factor_coverages w consists of those sets C that belong to word_factor_coverages w and are minimal with respect to inclusion. The hypothesis hC is therefore a conjunction whose first conjunct (hC.1) is precisely the statement that C ∈ word_factor_coverages w.
fun _ hC => hC.1
Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
theorem word_min_factor_coverages_subset {α : Type*} [DecidableEq α] (w : List α) : word_min_factor_coverages w ⊆ word_factor_coverages w := fun _ hC => hC.1