Skip to content
LumenaryAcademy
Professional 65 min

Propositions as types, and writing proofs

In Lean a statement is a type and a proof is a program of that type. Proofs written as terms, proofs built step by step with tactics, and the automation that does the routine work.

Code tested · 4AI-draftedAwaiting review by a computer scientist
MotivationH

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.

DefinitionsH

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:

StatementRead asA proof of it is
p → qif p then qa function turning a proof of p into a proof of q
p ∧ qp and qa pair ⟨hp, hq⟩
p ∨ qp or qOr.inl hp or Or.inr hq, saying which side holds
¬ pnot pa function from proofs of p to False
∀ x, P xfor every xa function taking any x to a proof of P x
∃ x, P xfor some xa pair ⟨w, h⟩ of a witness w and a proof h : P w
a = ba equals brfl when both sides compute to the same value; otherwise a proof by rewriting
Falseabsurditynothing: it has no proofs at all

Here are proofs written directly as values, which is called term mode:

lean
-- 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_nil
text
chain (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 ++ [] = as

Read 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.

Worked examplesH

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.

lean
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
    simp
text
p 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).length

The core tactics, in the order you will need them:

  • intro h: when the goal is p → q (or ∀ x, …), assume p and call the assumption h; the goal becomes q. In and_to_or, the first trace shows h : p ∧ q above the line.
  • exact e: close the goal with the term e, whose type must match the goal exactly.
  • apply f: when f proves something of the form … → goal, use it and leave its premises as new goals. In chain, apply hqr turns the goal r into q, as the second trace shows, because hqr can produce r from a proof of q.
  • rfl: close a goal a = a, or a = b where both sides compute to the same value.
  • constructor: split a goal built by a constructor, such as p ∧ q, into one goal per field.
  • cases h and obtain ⟨a, b⟩ := h: take apart a hypothesis built from constructors, such as a pair, an Or (one goal per side) or a list (one goal for [], one for x :: rest). In length_pos, the nil case contradicts the hypothesis h : [] ≠ [], which the contradiction tactic notices, and in the cons case the goal mentions x :: rest, whose length simp knows 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 equation h : a = b, replacing a by b everywhere.

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:

lean
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
  omega
text
case 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 * c

induction 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.

ComputationC

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.

lean
-- 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_comm
text
true
true
'Nat.add_comm' does not depend on any axioms
  • decide proves a proposition that can be decided by computation (a Decidable instance): equalities of concrete values, Boolean facts, statements over finite types such as Bool and Fin n, and quantifiers bounded by a number. It cannot prove ∀ n : Nat, n + 0 = n, which is about infinitely many numbers. #eval decide p runs the same decision procedure as a program, which is the bridge between Prop and Bool.
  • omega is a decision procedure for linear arithmetic over Nat and Int: 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.
  • simp rewrites the goal with a large database of lemmas marked @[simp] (such as "the length of xs ++ ys is 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 in sumTo_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:

text
two.lean:1:26: error: Tactic `decide` proved that the proposition
  2 + 2 = 5
is false
ExplanationH

What 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:

  • sorry is a placeholder that "proves" anything. It is indispensable while working (state a lemma, sorry its proof, check that the main argument works, then come back), and Lean prints the warning declaration 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 no sorry remains; 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) and Classical.choice (the axiom of choice, from which the law of the excluded middle follows). #print axioms name lists the axioms a theorem depends on. The output above shows that Nat.add_comm uses none at all; many proofs that use simp or grind depend on the standard three, which mathematicians and computer scientists alike accept. An unexpected axiom, such as sorryAx, the axiom behind sorry, 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 misconceptionsH

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

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-upHuman

In Lean, what is a proof of p → q?

Choose one

2. Propositions as types, and writing proofs

Warm-upComputational

Which number completes this proof?

example : ∃ n : Nat, n + n = 14 := ⟨?, rfl⟩

3. Propositions as types, and writing proofs

CoreHuman

The goal is ⊢ p ∧ q → q ∨ p. After intro h, what is the new goal (the part after ⊢)?

4. Propositions as types, and writing proofs

CoreHuman

The 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

CoreHuman

Which tactic is designed for this goal?

example (i n : Nat) (h₁ : i < n) (h₂ : n ≤ 100) : i + 1 ≤ 100 := by ?
Choose one

6. Propositions as types, and writing proofs

StretchHuman

Which 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

Write elements separated by commas. Order and repeats don’t matter — just like in a set!

7. Propositions as types, and writing proofs

CoreHuman

A colleague's file compiles, and #print axioms main_theorem lists sorryAx among the axioms. What does this tell you?

Choose one

Further reading and resources