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.