AFTD Auto-Formalizing Theoretical Domains

is_complete_return_word_prefix

theoremverified

If c is a complete return word to q, then q is a prefix of c.

Statement

theorem is_complete_return_word_prefix {α : Type*} {c q : List α}
    (h : is_complete_return_word c q) : q <+: c
Source
arXiv:2611.13676 Section 2
Verified
13 Nov 2026
Axioms
none — Lean reports it depends on no axioms
Built on 1
  • is_complete_return_wordA word c is a complete return word to a factor q if q is both a prefix and a suffix of c, strictly shorter than c, and q does not occur at…

Read back from the Lean

For any type α and any lists c and q of elements of α, if c and q satisfy is_complete_return_word c q, then q is a prefix of c (q <+: c).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

By definition, a word $c$ is a complete return word to $q$ if it satisfies a four-part conjunction: $q$ is a prefix of $c$, $q$ is a suffix of $c$, $q$ is strictly shorter than $c$, and $q$ does not appear as an internal factor. The theorem follows immediately by projecting the first conjunct from this definition.

  1. $q$ is a prefix of $c$ ($q <+: c$)

    By definition, $c$ being a complete return word to $q$ (`is_complete_return_word c q`) is a conjunction whose very first condition is that $q$ is a prefix of $c$ ($q <+: c$). Extracting the first conjunct (`h.1`) from the hypothesis $h$ directly proves the claim.

    line 4

      exact h.1

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

/-- A complete return word to q has q as a prefix. -/theorem is_complete_return_word_prefix {α : Type*} {c q : List α}    (h : is_complete_return_word c q) : q <+: c := by  exact h.1
See it in the graphDiscuss this resultChallenge it