Logical Foundations

10. ProofObjects: The Curry-Howard Correspondence🔗

"Algorithms are the computational content of proofs." (Robert Harper)

Programming and proving in Lean are two sides of the same coin. Proofs manipulate evidence much as programs manipulate data.

Question: If evidence is data, what are propositions themselves?

Answer: They are types!

Look again at the formal definition of the Even property. For illustrative purposes, we've made the implicit argument {n : Nat} to Even.succ_succ explicit.

namespace EvenProp inductive Even : Nat → Prop where | zero : Even 0 | succ_succ (n : Nat) (h : Even n) : Even (n + 2)

We can pronounce the ":" here as either "has type" or "is a proof of." For example, the second line in the definition of Even declares that (Even.zero : Even 0). Instead of "Even.zero has type Even 0," we can say that "Even.zero is a proof of Even 0."

This pun between types and propositions — between : as "has type" and : as "is a proof of" or "is evidence for" — is called the Curry-Howard correspondence. It proposes a deep connection between the world of logic and the world of computation:

propositions  ~  types
proofs        ~  programs

See Wadler (2015)Philip Wadler (2015). “Propositions as Types”. Communications of the ACM. 58(12), pp. 75–84. for a brief history and modern exposition.

Many useful insights follow from this connection. To begin with, it gives us a natural interpretation of the type of the Even.succ_succ constructor.

The type of Even.succ_succ says that it is a function (better: a data constructor) taking two arguments (one number n plus evidence for Even n) and returning evidence that n + 2 is even.

Even.succ_succ : ∀ (n : Nat), Even n → Even (n + 2)#check @Even.succ_succ
Even.succ_succ : ∀ (n : Nat), Even n → Even (n + 2)

This can be read "Even.succ_succ is a constructor that takes two arguments — a number n and evidence for the proposition Even n — and yields evidence for the proposition Even (n + 2)."

Now let's look again at an earlier proof involving Even.

theorem even_4 : Even 4 := ⊢ Even 4 ⊢ Even 2 ⊢ Even 0 All goals completed! 🐙

Just as with ordinary data values and functions, we can use the #print command to see the proof object that results from this proof script.

theorem EvenProp.even_4 : Even 4 := Even.succ_succ 2 (Even.succ_succ 0 Even.zero)#print even_4
theorem EvenProp.even_4 : Even 4 :=
Even.succ_succ 2 (Even.succ_succ 0 Even.zero)

Indeed, we can also write down this proof object directly, with no need for a proof script at all:

Even.succ_succ 2 (Even.succ_succ 0 Even.zero) : Even (2 + 2)#check (Even.succ_succ 2 (Even.succ_succ 0 Even.zero) : Even (2 + 2))
Even.succ_succ 2 (Even.succ_succ 0 Even.zero) : Even (2 + 2)

Similarly, as we've seen, we can directly apply theorems to arguments in proof scripts:

theorem even_4' : Even 4 := ⊢ Even 4 All goals completed! 🐙

10.1. Proof Scripts🔗

When we write a proof using tactics, what we are doing is instructing Lean to build a proof object under the hood. We can see this using the custom tactic show_proof:

Tactic: show_proofsection ShowProof open Lean Elab Tactic Meta /-- Like `instantiateMVars`, but also substitutes holes whose assignment Lean delays until they are complete (e.g., the body under an `intro`). -/ partial def instantiatePartial (e : Expr) : MetaM Expr := do let e ← instantiateMVars e transform e (pre := fun e => do let .mvar m := e.getAppFn | return .continue let some d ← getDelayedMVarAssignment? m | return .continue let v ← instantiatePartial (mkMVar d.mvarIdPending) let args := e.getAppArgs let n := d.fvars.size let v := (v.abstract d.fvars).instantiateRevRange 0 n args return .done (mkAppN v args[n:])) /-- `show_proof tac₁ … tacₙ` runs the tactics in order, printing the partial proof term (with `?_` for unfilled holes) before the first tactic and after each one. -/ elab "show_proof" seq:tacticSeq : tactic => do let root ← getMainGoal let s := seq.raw[0] let tacs := if s.getKind == ``Parser.Tactic.tacticSeqBracketed then s[1].getSepArgs else s[0].getSepArgs let render : TacticM Format := do let e ← instantiatePartial (mkMVar root) withOptions (fun o => (o.setBool `pp.mvars false).setBool `pp.fieldNotation false) (ppExpr e) let mut out ← render for t in tacs do evalTactic t let tac ← PrettyPrinter.ppTactic ⟨t⟩ out := out ++ .line ++ .line ++ f!"after {tac}:" ++ .nest 2 (.line ++ (← render)) logInfo m!"{out}" end ShowProof
theorem even_4'' : Even 4 := ⊢ Even 4 ?_ after apply Even.succ_succ: Even.succ_succ 2 ?_ after apply Even.succ_succ: Even.succ_succ 2 (Even.succ_succ 0 ?_) after apply Even.zero: Even.succ_succ 2 (Even.succ_succ 0 Even.zero)show_proof ⊢ Even 2 ⊢ Even 0 All goals completed! 🐙
?_

after apply Even.succ_succ:
  Even.succ_succ 2 ?_

after apply Even.succ_succ:
  Even.succ_succ 2 (Even.succ_succ 0 ?_)

after apply Even.zero:
  Even.succ_succ 2 (Even.succ_succ 0 Even.zero)

Tactic proofs are convenient, but they are not essential in Lean: in principle, we can always just construct the required evidence by hand. Then we can write a proof term directly following a := (instead of writing by and then tactics) to introduce a global name for this evidence.

theorem even_4''' : Even 4 := Even.succ_succ 2 (Even.succ_succ 0 Even.zero)

10.2. Quantifiers, Implications, Functions🔗

In Lean's computational universe (where data structures and programs live), there are two sorts of values that have arrows in their types: constructors introduced by inductively defined data types, and functions.

Similarly, in Lean's logical universe (where we carry out proofs), there are two ways of giving evidence for an implication: constructors introduced by inductively defined propositions, and... functions!

For example, consider this statement:

theorem even_plus4 (n : Nat) (h : Even n) : Even (n + 4) := n:Nath:Even n⊢ Even (n + 4) n:Nath:Even n⊢ Even (n + 2) n:Nath:Even n⊢ Even n All goals completed! 🐙

What is the proof object corresponding to even_plus4?

We're looking for an expression whose type is ∀ (n : Nat), Even n → Even (n + 4) — that is, a function that takes two arguments (one number and a piece of evidence) and returns a piece of evidence!

Here it is:

theorem even_plus4' : ∀ (n : Nat), Even n → Even (n + 4) := fun (n : Nat) => fun (h : Even n) => Even.succ_succ (n + 2) (Even.succ_succ n h)

Or equivalently:

theorem even_plus4'' (n : Nat) (h : Even n) : Even (n + 4) := Even.succ_succ (n + 2) (Even.succ_succ n h) even_plus4'' : ∀ (n : Nat), Even n → Even (n + 4)#check (even_plus4'' : ∀ (n : Nat), Even n → Even (n + 4))

10.2.1. Dependency, Equivalence, and Proof Irrelevance🔗

When we view the proposition being proved by even_plus4 as a function type, one interesting point becomes apparent: The second argument's type, Even n, mentions the value of the first argument, n.

While such dependent types are not found in most mainstream programming languages, they can be quite useful in programming too, as the flurry of activity in the functional programming community over the past couple of decades (and recently, most notably Lean!) demonstrates. Dependent types sit at the "highest corner" of the Lambda Cube (see the Stlc chapter of Type Systems): types can depend on values in addition to other types.

Notice that both implication (→) and quantification (∀) correspond to functions on evidence. In fact, they are really the same thing: → is just a shorthand for a degenerate use of ∀ where there is no dependency, i.e., no need to give a name to the type on the left-hand side of the arrow:

   ∀ (x : Nat), Nat
=  ∀ (_ : Nat), Nat
=  Nat        → Nat
Quiz

Recall the definition of Even:

inductive Even : Nat → Prop where
  | zero : Even 0
  | succ_succ (n : Nat) (h : Even n) : Even (n + 2)

What is the type of this expression?

fun (n : Nat) =>
  fun (h : Even n) =>
     Even.succ_succ (n + 2) (Even.succ_succ n h)

(A) ∀ (n : Nat), Even n

(B) ∀ (n : Nat), Even (n + 2)

(C) ∀ (n : Nat), Even n → Even n

(D) ∀ (n : Nat), Even n → Even (n + 2)

(E) ∀ (n : Nat), Even n → Even (n + 4)

(F) Not typeable

Show solution

(E)

fun n h => Even.succ_succ (n + 2) (Even.succ_succ n h) : ∀ (n : Nat), Even n → Even (n + 2 + 2)#check (fun (n : Nat) => fun (h : Even n) => Even.succ_succ (n + 2) (Even.succ_succ n h) : ∀ (n : Nat), Even n → Even (n + 4))

10.3. Programming with Tactics🔗

10.4. Building Proof Objects Incrementally (Optional)🔗

10.5. Practical Uses of Terms in Proofs🔗

In the Even examples, we show how to build proofs using terms to illustrate that they are one and the same. But in the most recent example, doing so is impractical: the proof terms are verbose and arguably harder to write and follow than a tactic proof. So the question naturally arises — would we ever use terms in real Lean proofs? The answer is yes, and we show some examples where such use is helpful, and indeed actively encouraged in real Lean developments.

Here are some of the places where terms most often appear in Lean proofs:

  1. rfl: The term rfl is used very often as a full proof instead of by rfl (which references the tactic rfl of the same name) and is even preferred in Lean's Mathlib, which writes its @[simp] definitional lemmas this way.

theorem two_add_two : 2 + 2 = 4 := rfl @[simp] theorem length_cons {α : Type} (x : α) (xs : List α) : (x :: xs).length = xs.length + 1 := rfl
  1. To succinctly apply an existing lemma, possibly via dot notation on proofs

theorem add_comm_flip (a b : Nat) : b + a = a + b := Nat.add_comm b a theorem le_chain {a b c : Nat} (h₁ : a ≤ b) (h₂ : b ≤ c) : a ≤ c := Nat.le_trans h₁ h₂
  1. Within anonymous constructors and projections for And (∧), Iff (↔), and Exists (∃)

theorem and_swap {P Q : Prop} (h : P ∧ Q) : Q ∧ P := ⟨h.2, h.1⟩ theorem iff_swap {P Q : Prop} (h : P ↔ Q) : Q ↔ P := ⟨h.2, h.1⟩ theorem exists_double : ∃ n, n + n = 4 := ⟨2, rfl⟩
  1. fun for implications (as in even_plus4')

theorem imp_trans {P Q R : Prop} (hpq : P → Q) (hqr : Q → R) : P → R := fun hp => hqr (hpq hp)
  1. Proof fields of structures/instances (as in Typeclasses' Monoid laws)

structure PosNat where val : Nat pos : 0 < val def three : PosNat where val := 3 pos := Nat.succ_pos 2

Using terms in proofs can be more succinct and more useful than writing out tactics. Try out using terms like rfl directly in your proofs in this book and see what you discover!

10.6. Logical Connectives as Inductive Types🔗

10.6.1. Conjunction🔗

Quiz

10.6.2. Disjunction🔗

Quiz

10.6.3. Existential Quantification🔗

The notation in the standard library is a slight extension of the above, enabling syntactic forms such as ∃ x y, P x y. The standard library's Exists also takes P implicitly.

Quiz

To destruct existentials in a proof term, we simply use match:

theorem dist_exists_or_term (α : Type) (P Q : α → Prop) : (∃ x, P x ∨ Q x) → (∃ x, P x) ∨ (∃ x, Q x) := fun h => match h with | Exists.intro x hx => match hx with | Or.inl hpx => Or.inl (Exists.intro x hpx) | Or.inr hqx => Or.inr (Exists.intro x hqx)

10.6.4. True and False🔗

10.7. Equality🔗

Quiz
Note to developers

-- ## Inversion, Again

-- :::suppressPreviousHeaderWhenTerse -- :::

HIDE: PR: This section may be repetitive given the increased attention paid to inversion, and it may be ineffective since this chapter is no longer on the recommended path. We need to think about whether this kind of reinforcement of the tactic is needed, and if so, where to place it for best impact.

BCP 11/18: I agree — this material is a bit redundant. On the other hand, the examples at the end may be helpful, so maybe it's fine to leave it.

10.8. Lean's Trusted Computing Base🔗

Note to developers (Mike Hicks @mwhicks1)

There is some overlap here and with the discussion of the TCB in Logic.lean. For that matter, much of the discussion of logical connective proofs here overlaps with the presentation in Logic.lean. This split feels non-optimal to me. I wonder if we can consider some sort of merge of these two chapters.

10.9. More Exercises🔗

10.10. Working with Proof Irrelevance🔗

Source revision: 0519b34, committed 2026-11-20 16:53 UTC