AFTD Auto-Formalizing Theoretical Domains

not_is_string_attractor_empty

theoremverified

The empty set is not a string attractor of a nonempty word.

Statement

theorem not_is_string_attractor_empty {α : Type*} [DecidableEq α] {w : List α} (hw : w ≠ []) :
    ¬ is_string_attractor w ∅
Source
Sanity lemma for is_string_attractor (arXiv:2610.10950 (Smallest String Attractors and Minimal Coverage Certificates of Thue–Morse Words), Definition 3.1).
Verified
12 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • is_string_attractorA set Γ ⊆ [1, |w|] of positions is a string attractor of the finite word w if Γ ∩ Cov_w(x) ≠ ∅ for every nonempty factor x of w.
  • word_occurrence_coverageThe coverage Cov_w(x) of a word x in a finite word w: the union of the intervals [p, p+|x|−1] over all (1-based) occurrence starts p of x…
Used by 1

The proof, explained

The proof proceeds by contradiction. If the empty set were a string attractor of a nonempty word $w$, then every nonempty factor of $w$ would have an occurrence intersecting $\emptyset$. But $w$ is a nonempty factor of itself, which would require $\emptyset$ to intersect the coverage of $w$—an impossibility since the empty set contains no elements.

  1. Assume for contradiction that $\emptyset$ is a string attractor of $w$, extracting the condition that every nonempty factor of $w$ intersects $\emptyset$.

    By definition, a set $\Gamma$ is a string attractor of $w$ if $\Gamma \subseteq \{1, \dots, |w|\}$ and every nonempty factor of $w$ has an occurrence intersecting $\Gamma$. Assuming for contradiction that $\emptyset$ is an attractor, we discard the trivial inclusion $\emptyset \subseteq \{1, \dots, |w|\}$ and retain the hypothesis (named $h$) that every nonempty factor of $w$ has an occurrence whose coverage intersects $\emptyset$.

    line 3

      rintro ⟨-, h⟩
  2. Specializing the attractor condition to $w$ itself derives a contradiction.

    Since $w$ is nonempty by hypothesis ($hw$) and is an infix of itself (by `List.infix_refl`), the attractor hypothesis $h$ guarantees that $\emptyset \cap \text{word\_occurrence\_coverage } w\ w$ is nonempty. This yields a witness $x$ belonging to this intersection ($hx$). Simplifying this membership condition immediately produces a contradiction, since no element can belong to the empty set.

    lines 4–5

    uses List.infix_refl

      obtain ⟨x, hx⟩ := h w hw (List.infix_refl w)
      simp at hx
List.infix_refl
Every list is an infix (contiguous sublist) of itself: $l <:+: l$.

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 not_is_string_attractor_empty {α : Type*} [DecidableEq α] {w : List α} (hw : w ≠ []) :    ¬ is_string_attractor w ∅ := by  rintro ⟨-, h⟩  obtain ⟨x, hx⟩ := h w hw (List.infix_refl w)  simp at hx
See it in the graphDiscuss this resultChallenge it