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
def rev : List α → List α
| [] => []
| x :: xs => rev xs ++ [x][]is the empty list; reversing it still gives the empty list.x :: xsis "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:
#eval rev [1, 2, 3][3, 2, 1]- My
revcan 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:
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:
unsolved goals
case cons
α : Type u_1
x : α
xs : List α
ih : rev (rev xs) = xs
⊢ rev (rev xs ++ [x]) = x :: xsDon'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 fromih
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:
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_appendpasses
Step 4: Finish the main theorem
Hand the lemma to simp:
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_revpasses
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:
nilandcons 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_appendandrev_revpass
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.