Skip to content

First proofs: rfl, omega, induction

3 February 2025

The surprise of the first week: a proof is just another term, and by switches into tactic mode, where each line transforms the goal and the infoview shows what's left.

Some facts hold by computation. Lean evaluates both sides and compares them:

example : 2 + 2 = 4 := rfl

def double (n : Nat) : Nat := n + n

example : double 21 = 42 := rfl

Others need arithmetic. omega decides linear arithmetic over Nat and Int, once the definitions are out of its way:

theorem double_add (a b : Nat) : double (a + b) = double a + double b := by
  unfold double
  omega

Anything about a recursive definition wants induction, in the same shape as the definition:

def countdown : Nat → List Nat
  | 0 => [0]
  | n + 1 => (n + 1) :: countdown n

theorem countdown_length (n : Nat) : (countdown n).length = n + 1 := by
  induction n with
  | zero => rfl
  | succ n ih => simp [countdown, ih]

In the succ case the infoview shows ih : (countdown n).length = n + 1 and the goal (countdown (n + 1)).length = n + 1 + 1. simp unfolds one step of countdown, rewrites the length of a cons, and finishes with ih.