AFTD Auto-Formalizing Theoretical Domains

thue_morse_min_factor_coverages_finset_mem

theoremverified

For 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 t_n.

Statement

theorem thue_morse_min_factor_coverages_finset_mem (n : ℕ) (C : Finset ℕ) :
    C ∈ thue_morse_min_factor_coverages_finset n ↔ C ∈ word_min_factor_coverages (thue_morse_word n)
Source
step towards thue_morse_random_attractor_lattice_gumbel
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
Used by 1

The proof, explained

The finite set `thue_morse_min_factor_coverages_finset n` is defined by filtering the powerset of the index set $\{1, \dots, |t_n|\}$ by the decidability of being an inclusion-minimal factor coverage of the $n$-th Thue-Morse word $t_n$. Unfolding this definition reduces the equivalence to showing that any minimal factor coverage $C$ is automatically contained in $\{1, \dots, |t_n|\}$. This inclusion holds because minimal factor coverages are factor coverages (the coverages of occurrences of some factor), and all occurrence coverages in $t_n$ are bounded by the length of $t_n$.

  1. Membership in `thue_morse_min_factor_coverages_finset n` is equivalent to $C \subseteq \{1, \dots, |t_n|\} \wedge C \in \text{word\_min\_factor\_coverages}(t_n)$, where $t_n$ is the $n$-th Thue-Morse word.

    Unfolding the definition of `thue_morse_min_factor_coverages_finset` shows it is defined by filtering the powerset of $\{1, \dots, |t_n|\}$. Rewriting with `Finset.mem_filter` and `Finset.mem_powerset` turns membership in this filtered powerset into the subset condition $C \subseteq \{1, \dots, |t_n|\}$ paired with the boolean condition $\text{decide}(C \in \text{word\_min\_factor\_coverages}(t_n)) = \text{true}$. Simplifying with `decide_eq_true_eq` reduces the boolean check directly to the proposition $C \in \text{word\_min\_factor\_coverages}(t_n)$.

    lines 4–6

    uses Finset.mem_filter, Finset.mem_powerset, decide_eq_true_eq

      dsimp [thue_morse_min_factor_coverages_finset]
      rw [Finset.mem_filter, Finset.mem_powerset]
      simp only [decide_eq_true_eq]
  2. If $C \subseteq \{1, \dots, |t_n|\}$ and $C \in \text{word\_min\_factor\_coverages}(t_n)$, then $C \in \text{word\_min\_factor\_coverages}(t_n)$.

    We split the equivalence into both directions. For the forward direction, assuming the conjunction $C \subseteq \{1, \dots, |t_n|\} \wedge C \in \text{word\_min\_factor\_coverages}(t_n)$, the desired conclusion is simply the second conjunct.

    lines 7–9

      constructor
      · intro h
        exact h.2
  3. If $C \in \text{word\_min\_factor\_coverages}(t_n)$, then $C \subseteq \{1, \dots, |t_n|\}$ and $C \in \text{word\_min\_factor\_coverages}(t_n)$.

    For the reverse direction, we assume $C \in \text{word\_min\_factor\_coverages}(t_n)$. Supplying this assumption discharges the second conjunct, leaving the goal to show $C \subseteq \{1, \dots, |t_n|\}$. By `word_min_factor_coverages_subset`, any minimal factor coverage is in particular a factor coverage. Unpacking the definition of factor coverage, $C$ must be the occurrence coverage of some nonempty factor $x$ of $t_n$. Finally, `word_occurrence_coverage_subset` guarantees that the occurrence coverage of any factor in $t_n$ is contained in the index range $\{1, \dots, |t_n|\}$.

    lines 10–14

    uses word_min_factor_coverages_subset, word_occurrence_coverage_subset

      · intro h
        refine ⟨?_, h⟩
        have hC := word_min_factor_coverages_subset (thue_morse_word n) h
        rcases hC with ⟨x, _, _, rfl⟩
        exact word_occurrence_coverage_subset (thue_morse_word n) x
Finset.mem_filter
An element belongs to the filter of a finite set by a predicate if and only if it belongs to the base set and satisfies the predicate.
Finset.mem_powerset
A finite set belongs to the powerset of another finite set if and only if it is a subset of that set.
decide_eq_true_eq
The decidable boolean evaluation `decide p` equals `true` if and only if the proposition `p` holds.
word_min_factor_coverages_subset
Every minimal factor coverage of a word is also a factor coverage of that word.
word_occurrence_coverage_subset
The occurrence coverage of any factor in a word is contained in the index range from 1 to the length of the word.

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

/-- Membership in the Finset realization of H_min(t_n) is exactly membership in the set H_min(t_n). -/theorem thue_morse_min_factor_coverages_finset_mem (n : ℕ) (C : Finset ℕ) :    C ∈ thue_morse_min_factor_coverages_finset n ↔ C ∈ word_min_factor_coverages (thue_morse_word n) := by  dsimp [thue_morse_min_factor_coverages_finset]  rw [Finset.mem_filter, Finset.mem_powerset]  simp only [decide_eq_true_eq]  constructor  · intro h    exact h.2  · intro h    refine ⟨?_, h⟩    have hC := word_min_factor_coverages_subset (thue_morse_word n) h    rcases hC with ⟨x, _, _, rfl⟩    exact word_occurrence_coverage_subset (thue_morse_word n) x
See it in the graphDiscuss this resultChallenge it