From some inputs to all inputs
A test checks a program on the inputs you thought of. #eval sumTo 10 shows 55, and the formula n * (n + 1) / 2 gives 55 too, so we feel confident that sumTo adds up the numbers from 1 to n. But a test of ten values, or ten million, says nothing about the next one. A proof covers every input at once, and Lean checks that it is correct.
Lesson 2 drew a line between Bool, a value a program computes, and Prop, a statement. 3 == 4 is a Bool, false. 3 = 4 is a Prop: a statement that happens to be false. ∀ n : Nat, 2 * sumTo n = n * (n + 1) is a Prop too, and no program can decide it by trying every n. To establish it, we need a proof. This lesson is about what a proof is in Lean, how to write one, and how to let Lean's automation do most of the routine work. It stays close to statements about programs, which is where we are heading; Lumenary Math's First steps in Lean covers the same tools from the mathematician's side, with more logic and more about natural numbers, and is a good companion to this lesson.
Propositions are types, proofs are values
The central idea of Lean's logic fits in one sentence: a proposition is a type, and a proof of it is a value of that type. To prove a statement is to construct a value of the corresponding type; to check a proof is to type-check that value, which is something Lean is already good at. The idea is known as the Curry–Howard correspondence, after the logicians Haskell Curry and William Howard who noticed it, and Type theory and propositions as types tells its history.
Definition— Prop
Prop is the universe of propositions. If p : Prop, then a value h : p is a proof of p. A theorem is a definition whose type is a proposition: theorem name : statement := proof. An example is a theorem without a name.
Each logical connective is a type former, and its proofs are built and used in a specific way:
| Statement | Read as | A proof of it is |
|---|---|---|
p → q | if p then q | a function turning a proof of p into a proof of q |
p ∧ q | p and q | a pair ⟨hp, hq⟩ |
p ∨ q | p or q | Or.inl hp or Or.inr hq, saying which side holds |
¬ p | not p | a function from proofs of p to False |
∀ x, P x | for every x | a function taking any x to a proof of P x |
∃ x, P x | for some x | a pair ⟨w, h⟩ of a witness w and a proof h : P w |
a = b | a equals b | rfl when both sides compute to the same value; otherwise a proof by rewriting |
False | absurdity | nothing: it has no proofs at all |
Here are proofs written directly as values, which is called term mode:
-- A proof of `p → q` is a function from proofs of `p` to proofs of `q`.
theorem chain (p q r : Prop) (hpq : p → q) (hqr : q → r) : p → r :=
fun hp => hqr (hpq hp)
-- A proof of `p ∧ q` is a pair of proofs; a proof of `q ∨ p` picks a side.
theorem and_to_or (p q : Prop) : p ∧ q → q ∨ p :=
fun ⟨_, hq⟩ => Or.inl hq
-- `¬ p` means `p → False`: a function that turns a proof of `p` into absurdity.
theorem no_contradiction (p : Prop) : ¬ (p ∧ ¬ p) :=
fun ⟨hp, hnp⟩ => hnp hp
-- An existential statement is proved by a witness and a proof about the witness.
theorem perfect_square : ∃ n : Nat, n * n = 144 := ⟨12, rfl⟩
-- A universal statement is proved by a function that works for any `n`.
theorem add_zero_any : ∀ n : Nat, n + 0 = n := fun _ => rfl
-- Library theorems are values too, and can be applied like functions.
theorem append_empty (xs : List String) : xs ++ [] = xs := List.append_nil xs
#check chain
#check @Or.inl
#check perfect_square
#check List.append_nilchain (p q r : Prop) (hpq : p → q) (hqr : q → r) : p → r
@Or.inl : ∀ {a b : Prop}, a → a ∨ b
perfect_square : ∃ n, n * n = 144
List.append_nil.{u} {α : Type u} (as : List α) : as ++ [] = asRead chain as a program: given a proof hp of p, feed it to hpq to get a proof of q, and feed that to hqr to get a proof of r. It is function composition, and that is exactly what "if p implies q and q implies r, then p implies r" means. no_contradiction takes the pair apart and applies the proof of ¬ p to the proof of p, producing False. perfect_square supplies the witness 12, and rfl proves 12 * 12 = 144 by computing both sides. add_zero_any works because n + 0 reduces to n by the definition of addition, which recurses on its second argument (0 + n = n is also true, but needs a proof by induction, since 0 + n does not reduce when n is unknown).
The last #check shows the type of a library theorem, List.append_nil: for every list as, as ++ [] = as. Using a theorem is calling a function, and its explicit arguments say what it is about.
Tactic mode: building a proof step by step
Term-mode proofs are elegant for short arguments, but long ones become unreadable. Tactic mode, entered with by, lets you build the proof interactively. At each point there is a goal: the hypotheses you have, above a ⊢, and the statement you must prove, below it. Each tactic transforms the goal, and the proof is finished when no goals remain. In the editor, the infoview shows the goal wherever the cursor is; here we use the trace_state tactic, which prints the goal as a message, to show you exactly what the infoview would.
theorem and_to_or (p q : Prop) : p ∧ q → q ∨ p := by
intro h
trace_state
obtain ⟨_, hq⟩ := h
exact Or.inl hq
theorem chain (p q r : Prop) (hpq : p → q) (hqr : q → r) (hp : p) : r := by
apply hqr
trace_state
apply hpq
exact hp
theorem length_pos (xs : List Nat) (h : xs ≠ []) : 0 < xs.length := by
cases xs with
| nil => contradiction
| cons x rest =>
trace_state
simpp q : Prop
h : p ∧ q
⊢ q ∨ p
p q r : Prop
hpq : p → q
hqr : q → r
hp : p
⊢ q
case cons
x : Nat
rest : List Nat
h : x :: rest ≠ []
⊢ 0 < (x :: rest).lengthThe core tactics, in the order you will need them:
intro h: when the goal isp → q(or∀ x, …), assumepand call the assumptionh; the goal becomesq. Inand_to_or, the first trace showsh : p ∧ qabove the line.exact e: close the goal with the terme, whose type must match the goal exactly.apply f: whenfproves something of the form… → goal, use it and leave its premises as new goals. Inchain,apply hqrturns the goalrintoq, as the second trace shows, becausehqrcan producerfrom a proof ofq.rfl: close a goala = a, ora = bwhere both sides compute to the same value.constructor: split a goal built by a constructor, such asp ∧ q, into one goal per field.cases handobtain ⟨a, b⟩ := h: take apart a hypothesis built from constructors, such as a pair, anOr(one goal per side) or a list (one goal for[], one forx :: rest). Inlength_pos, thenilcase contradicts the hypothesish : [] ≠ [], which thecontradictiontactic notices, and in theconscase the goal mentionsx :: rest, whose lengthsimpknows to be positive.induction n: prove a statement for every natural number, list or tree by proving it for each constructor, with an induction hypothesis for the smaller pieces.rw [h]: rewrite the goal using an equationh : a = b, replacingabybeverywhere.
The tactics write a term for you. #print and_to_or would show you the term the tactic proof produced, and the kernel checks that term, not the tactics.
Induction on your own function
Here is the proof that motivated the lesson, about a function we wrote ourselves:
def sumTo : Nat → Nat
| 0 => 0
| n + 1 => sumTo n + (n + 1)
theorem sumTo_formula (n : Nat) : 2 * sumTo n = n * (n + 1) := by
induction n with
| zero => rfl
| succ k ih =>
simp only [sumTo]
trace_state
grind
theorem rewrite_example (a b c : Nat) (h₁ : a = b) (h₂ : b = 2 * c) : a + a = 4 * c := by
rw [h₁, h₂]
trace_state
omegacase succ
k : Nat
ih : 2 * sumTo k = k * (k + 1)
⊢ 2 * (sumTo k + (k + 1)) = (k + 1) * (k + 1 + 1)
a b c : Nat
h₁ : a = b
h₂ : b = 2 * c
⊢ 2 * c + 2 * c = 4 * cinduction n with produces two goals, named after Nat's constructors. For zero, both sides compute to 0, so rfl closes it. For succ k, we must prove the formula for k + 1 and may assume it for k: that assumption is ih. simp only [sumTo] unfolds one step of the definition, and the trace shows the goal: an equation between polynomials in k that follows from ih by algebra. grind finishes it; it combines equational reasoning with arithmetic, including the multiplication of variables that omega cannot handle. In rewrite_example, rw [h₁, h₂] replaces a by b and then b by 2 * c, and omega does the remaining linear arithmetic.
Notice the shape of the induction: it follows the shape of sumTo's recursion exactly, one case for 0 and one for n + 1. That is no accident, and the next lesson builds on it.
Automation: decide, simp, omega and grind
Most of the steps in real proofs are routine, and Lean's automation handles them. Knowing which tool does what saves a great deal of time.
-- Finite, computable facts: `decide` evaluates them.
example : 2 ^ 10 = 1024 := by decide
example : ∀ b : Bool, (b && !b) = false := by decide
-- Linear arithmetic over Nat and Int: `omega`.
example (a b : Nat) (h₁ : a < b) (h₂ : b ≤ 10) : a + 1 ≤ 10 := by omega
example (x : Int) (h : 3 * x + 1 = 10) : x = 3 := by omega
-- Simplification with the library's rewrite rules: `simp`.
example (xs ys : List Nat) : (xs ++ ys).length = ys.length + xs.length := by
simp [Nat.add_comm]
example (f : Nat → Nat) (xs : List Nat) : (xs.map f).length = xs.length := by simp
-- A general-purpose automated prover: `grind`.
example (a b : Nat) (h : a * b = 6) (ha : a = 2) : b = 3 := by grind
-- A `Prop` that is decidable can be turned into a `Bool` and computed.
#eval decide (2 ^ 10 = 1024)
#eval decide (∀ n, n < 5 → n * n < 20)
#print axioms Nat.add_commtrue
true
'Nat.add_comm' does not depend on any axiomsdecideproves a proposition that can be decided by computation (aDecidableinstance): equalities of concrete values, Boolean facts, statements over finite types such asBoolandFin n, and quantifiers bounded by a number. It cannot prove∀ n : Nat, n + 0 = n, which is about infinitely many numbers.#eval decide pruns the same decision procedure as a program, which is the bridge betweenPropandBool.omegais a decision procedure for linear arithmetic overNatandInt: sums, differences, multiplication by constants,/and%by constants, and comparisons, under hypotheses of the same kind. It is the tactic you will use most often in proofs about programs, since index bounds and loop counters are linear.simprewrites the goal with a large database of lemmas marked@[simp](such as "the length ofxs ++ ysis the sum of the lengths"), plus any you list in brackets, until nothing more applies.simp only [lemmas]uses only the ones you name, which makes proofs faster and more robust to library changes.grind, a newer addition to core Lean (2025), combines congruence closure, case splitting, linear arithmetic and algebraic normalisation. It closes many goals that would otherwise need several steps, as insumTo_formula.
Each example in the program is a check that the file passes only if the proof is right. When a claim is false, automation says so; example : 2 + 2 = 5 := by decide, in a file two.lean, fails with:
two.lean:1:26: error: Tactic `decide` proved that the proposition
2 + 2 = 5
is falseWhat Lean actually checks, and what you trust
Every proof, whether written as a term or produced by tactics, is finally a term checked by Lean's kernel, a small program whose only job is type checking. Tactics, simp, omega and grind are large and complicated, but they are not trusted: if one of them had a bug and produced a wrong proof term, the kernel would reject it. This design, in which a small trusted checker validates the output of untrusted automation, is known as the de Bruijn criterion, and it is why a Lean proof can be believed without believing in the tools that found it. The kernel has also been reimplemented independently, and those checkers can recheck exported proofs.
Two things can weaken a proof, and Lean tells you about both:
sorryis a placeholder that "proves" anything. It is indispensable while working (state a lemma,sorryits proof, check that the main argument works, then come back), and Lean prints the warningdeclaration uses `sorry`at every declaration that contains one. Declarations that merely use such a lemma get no warning of their own, which is why#print axioms(below) matters. A project is finished only when nosorryremains; Lumenary's tests reject any program that contains one.- Axioms are statements accepted without proof. Lean's logic uses three standard ones:
propext(equivalent propositions are equal),Quot.sound(for quotient types) andClassical.choice(the axiom of choice, from which the law of the excluded middle follows).#print axioms namelists the axioms a theorem depends on. The output above shows thatNat.add_commuses none at all; many proofs that usesimporgrinddepend on the standard three, which mathematicians and computer scientists alike accept. An unexpected axiom, such assorryAx, the axiom behindsorry, is a red flag.
And one thing Lean cannot check: whether the statement says what you meant. A correct proof of the wrong theorem is still the wrong theorem. Reading statements critically is the human half of formal verification, and the next lesson is largely about it.
Common misconceptions
Misconception
"= and == are interchangeable in theorems." A theorem states a Prop, so it uses =. A statement like (xs ++ []) == xs is a Bool, and a theorem about it would be the proposition ((xs ++ []) == xs) = true, which is awkward to work with and needs lawful BEq instances to connect it to real equality. State theorems with =, and use == in programs.
Misconception
"Tactic proofs and term proofs are different kinds of proof." Tactics are a way of writing a term. Both end in the same kind of value, checked by the same kernel. Experienced users mix them freely: exact ⟨hq, hp⟩ inside a tactic proof, by omega inside a term.
Misconception
"If simp fails, the statement is false." simp only rewrites with the lemmas it knows; failure means it got stuck, not that the goal is false. Look at what it left (simp? suggests the lemmas it used, and the infoview shows the remaining goal), then add a lemma, unfold a definition, or switch to omega or grind.
Misconception
"decide can prove anything that is true and simple." It proves only what can be settled by finite computation. ∀ n : Nat, n + 0 = n is simple and true, but it is about infinitely many numbers, and needs intro n; rfl, simp or omega instead.
Exercises
Try each one in your editor or the playground, watching the goal in the infoview as you go.
1. Propositions as types, and writing proofs
Warm-upHumanIn Lean, what is a proof of p → q?
2. Propositions as types, and writing proofs
Warm-upComputationalWhich number completes this proof?
example : ∃ n : Nat, n + n = 14 := ⟨?, rfl⟩
3. Propositions as types, and writing proofs
CoreHumanThe goal is ⊢ p ∧ q → q ∨ p. After intro h, what is the new goal (the part after ⊢)?
4. Propositions as types, and writing proofs
CoreHumanThe goal is ⊢ p ∧ q ∧ r (which Lean reads as p ∧ (q ∧ r)). How many goals are there right after one constructor?
5. Propositions as types, and writing proofs
CoreHumanWhich tactic is designed for this goal?
example (i n : Nat) (h₁ : i < n) (h₂ : n ≤ 100) : i + 1 ≤ 100 := by ?
6. Propositions as types, and writing proofs
StretchHumanWhich of these goals can by decide prove? List their letters.
- A:
2 ^ 8 = 256 - B:
∀ b : Bool, (b || !b) = true - C:
∀ n : Nat, n + 0 = n - D:
∀ n, n < 10 → n * n < 100 - E:
∃ n : Nat, n * n = 144
7. Propositions as types, and writing proofs
CoreHumanA colleague's file compiles, and #print axioms main_theorem lists sorryAx among the axioms. What does this tell you?
Further reading and resources
- Theorem Proving in Lean 4The official book on Lean's logic, from propositions and proofs to tactics, induction and type classes.
- The Lean Language Reference: tacticsThe reference's tactic chapter documents every tactic in core Lean, including simp, omega and grind.
- The Natural Number GameA browser game that teaches tactic proofs by building the arithmetic of the natural numbers, one level at a time.