AFTD Auto-Formalizing Theoretical Domains

exists_min_factor_coverage_subset

theoremverified

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

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.

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

    lines 4–5

    uses subset_rfl

      obtain ⟨C, ⟨hCH, hCD⟩, hmin⟩ := (measure Finset.card).wf.has_min
        {C | C ∈ word_factor_coverages w ∧ C ⊆ D} ⟨D, hD, subset_rfl⟩
  2. 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.

    line 6

      refine ⟨C, ⟨hCH, fun E hE hEC => ?_⟩, hCD⟩
  3. 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).

    lines 7–8

    uses Finset.card_lt_card, Finset.ssubset_iff_subset_ne.2

      by_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

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