AFTD Auto-Formalizing Theoretical Domains

longest_common_prefix_nil_left

theoremverified

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

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.

  1. 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).

    line 4

      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

/-- 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
See it in the graphDiscuss this resultChallenge it