AFTD Auto-Formalizing Theoretical Domains

word_min_factor_coverages_subset

theoremverified

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
Used by 2

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.

  1. 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.

    line 3

      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
See it in the graphDiscuss this resultChallenge it