longest_common_prefix_nil_left
The longest common prefix of the empty list and any list is empty.
Statement
theorem longest_common_prefix_nil_left {α : Type*} [DecidableEq α] (l : List α) : longest_common_prefix [] l = []
- Source
- arXiv:2611.13676 Lemma 3.1
- Verified
- 13 Nov 2026
- Axioms
propext- Built on 1
- longest_common_prefixThe longest common prefix of two lists is their maximal shared initial segment.
Read back from the Lean
For any type α with decidable equality and for any list l : List α, the longest common prefix of the empty list [] and l is equal to the empty list [].
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
The proof proceeds by case analysis on the list l. In both cases—whether l is empty or of the form head :: tail—the first argument is empty, so longest_common_prefix [] l reduces to [] immediately by definition.
longest_common_prefix [] l = []
We split into cases on whether the list l is empty (nil) or non-empty (cons). In both cases, the first argument is the empty list [], so the definition of longest_common_prefix bypasses the recursive branch and evaluates directly to [] by definition (definitional equality).
cases l <;> rfl
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.
/-- The longest common prefix with an empty list on the left is empty. -/theorem longest_common_prefix_nil_left {α : Type*} [DecidableEq α] (l : List α) : longest_common_prefix [] l = [] := by cases l <;> rfl