not_is_string_attractor_empty
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
- thue_morse_random_attractor_prob_zeroFor every natural number n, thue_morse_random_attractor_prob n 0 = 0.
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.
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$.
rintro ⟨-, h⟩
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.
uses
List.infix_reflobtain ⟨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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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