Skip to content

Induction on lists ​

After finishing this section, you will be able to prove that the reversal function you wrote satisfies "reversing twice is the same as not reversing at all." More importantly, you will experience getting stuck in a proof and learn to see what's missing from where you got stuck.

What you'll be able to do ​

  • Write inductive proofs on lists: the empty list, and "prepend one element"
  • Read the needed auxiliary lemma out of an unfinished goal
  • Prove a lemma first, then use it to finish the main theorem

Step 1: Write a reversal function ​

lean
def rev : List α → List α
  | [] => []
  | x :: xs => rev xs ++ [x]
  • [] is the empty list; reversing it still gives the empty list.
  • x :: xs is "the first element x, followed by the list xs". To reverse it, first reverse the rest, then append x at the end. ++ concatenates two lists.

Try it:

lean
#eval rev [1, 2, 3]
text
[3, 2, 1]
  • My rev can reverse [1, 2, 3]

Step 2: Try proving directly, then get stuck ​

What we want to prove is: for any list, rev (rev xs) = xs.

Induction on lists, like on natural numbers, has two cases: nil is the empty list, cons x xs ih is "x followed by xs", and ih says the proposition holds for xs. Following the pattern from the previous section:

lean
theorem rev_rev_try (xs : List α) : rev (rev xs) = xs := by
  induction xs with
  | nil => rfl
  | cons x xs ih => simp [rev, ih]

You should see: Lean says there are unfinished goals:

text
unsolved goals
case cons
α : Type u_1
x : α
xs : List α
ih : rev (rev xs) = xs
⊢ rev (rev xs ++ [x]) = x :: xs

Don't rush to switch strategies—read this goal. The left side is rev (rev xs ++ [x]), a reversal of a "concatenated list". ih says rev (rev xs), with an extra ++ [x] in the middle, so it doesn't apply.

What's missing is a piece of knowledge: what is the result of reversing a concatenation?

  • I saw unsolved goals, and I can point out where the goal differs from ih

Step 3: Prove a helper first ​

Think of a concrete example: concatenate [1, 2] and [3, 4], then reverse, and you get [4, 3, 2, 1]—that is, "the reversal of the second half" followed by "the reversal of the first half". Write it as a theorem, again using induction:

lean
theorem rev_append (xs ys : List α) : rev (xs ++ ys) = rev ys ++ rev xs := by
  induction xs with
  | nil =>
    simp [rev]
  | cons x xs ih =>
    simp [rev, ih]

A small theorem proved in advance in order to prove the main theorem is called a lemma.

  • rev_append passes

Step 4: Finish the main theorem ​

Hand the lemma to simp:

lean
theorem rev_rev (xs : List α) : rev (rev xs) = xs := by
  induction xs with
  | nil =>
    rfl
  | cons x xs ih =>
    simp [rev, rev_append, ih]

You should see: no errors.

With rev_append, the stuck rev (rev xs ++ [x]) gets rewritten into rev [x] ++ rev (rev xs), at which point ih can be used, and the remaining simp finishes the computation on its own.

  • rev_rev passes

Quiz timeThe proof is stuck and Lean shows unsolved goals. What's the best next step?

Checkpoint ​

  • I can write the two cases of list induction: nil and cons x xs ih
  • I can explain why the first attempt gets stuck
  • I know what a lemma is, and how the lemma in this section was figured out
  • Both rev_append and rev_rev pass

Didn't work? ​

rev_rev reports an error saying it doesn't recognize rev_append. The lemma must be written before the theorem that uses it. Lean reads the file top to bottom.

There is still a goal left after simp. Compare with the code above and check whether rev_append or ih is missing from the square brackets.

Next section ​

You already know how to verify a function. The last section uses the same three steps—define, get stuck and find a lemma, do induction—to prove that a mini compiler is correct.

gaodong.aiAboutPrivacyContact

Independent tutorials, not affiliated with any product mentioned. Product names and trademarks belong to their owners. Check official pages for prices and policies.