Logical Foundations

10. ProofObjects: The Curry-Howard Correspondence🔗

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

We have seen that Lean has mechanisms both for programming, using inductive data types like Nat or List and functions over these types, and for proving properties of these programs, using inductive propositions (like Even), implication, universal quantification, and the like. So far, we have mostly treated these mechanisms as if they were quite separate, and for many purposes this is a good way to think. But we have also seen hints that Lean's programming and proving facilities are closely related. For example, the keyword inductive is used to declare both data types and propositions, and → is used both to describe the type of functions on data and logical implication. This is not just a syntactic accident! In fact, programs and proofs in Lean are almost the same thing. In this chapter we will study this connection in more detail.

We have already seen the fundamental idea: provability in Lean is always witnessed by evidence. When we construct the proof of a basic proposition, we are actually building a tree of evidence, which can be thought of as a concrete data structure.

If the proposition is an implication like A → B, then its proof is an evidence transformer: a recipe for converting evidence for A into evidence for B. So at a fundamental level, proofs are simply programs that manipulate evidence.

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)

The expression Even.succ_succ 2 (Even.succ_succ 0 Even.zero) instantiates the parameterized constructor Even.succ_succ with the specific arguments 2 and 0 plus the corresponding proof objects for its premises Even 2 and Even 0. Alternatively, we can think of Even.succ_succ as a primitive "evidence constructor" that, when applied to a particular number, wants to be further applied to evidence that this number is even; its type,

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

expresses this functionality, in the same way that the polymorphic type {α : Type} → List α expresses the fact that the constructor List.nil can be thought of as a function from types to empty lists with elements of that type.

The fact that some arguments are implicit, like {α} of List and {n} of the real Even.succ_succ, actually doesn't make a difference at all: List is still taking one argument, and Even.succ_succ is still taking two. Implicit arguments are just a usability feature that tells Lean to figure some arguments out when we apply a definition (like Even.succ_succ) to an explicit argument (like a proof of Even n). In this case, since Even n contains n, we don't need to pass n in to begin with, and can mark it as implicit with the curly braces as {n}.

We saw in the Logic chapter that we can use function application syntax to instantiate universally quantified variables in lemmas, as well as to supply evidence for assumptions that these lemmas impose. For instance:

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

10.1. Proof Scripts🔗

The proof objects we've been discussing lie at the core of how Lean operates. When Lean is following a proof script, what is happening internally is that it is gradually constructing a proof object — a term whose type is the proposition being proved. All the tactics following by tell it how to build up a term of the required type. To see this process in action, we provide a show_proof tactic to display the current state of the proof tree at various points in the following tactic proof.

show_proof wraps a tactic script and prints the partial proof term — a term with holes where the remaining proof obligations are — before and after each step. A term's holes are shown as ?_.

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)

At any given moment, Lean has constructed a term with a "hole" (indicated by ?_ here, and so on), and it knows what type of evidence is needed to fill this hole.

Each hole corresponds to a subgoal, and the proof is finished when there are no more subgoals. At this point, the evidence we've built is stored in the global context (i.e. Lean's environment that it uses for type-checking) under the name given in the theorem command.

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)

All these different ways of building the proof lead to exactly the same evidence being saved in the global environment.

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)#print even_4' 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)#print even_4'''
theorem EvenProp.even_4 : Even 4 :=
Even.succ_succ 2 (Even.succ_succ 0 Even.zero)
theorem EvenProp.even_4' : Even 4 :=
Even.succ_succ 2 (Even.succ_succ 0 Even.zero)
theorem EvenProp.even_4'' : Even 4 :=
Even.succ_succ 2 (Even.succ_succ 0 Even.zero)
theorem EvenProp.even_4''' : Even 4 :=
Even.succ_succ 2 (Even.succ_succ 0 Even.zero)
Exercise★★(eight_is_even)

Give a tactic proof and a proof object showing that Even 8.

theorem even_8_tactics : Even 8 := ⊢ Even 8 solution! ⊢ Even 6 ⊢ Even 4 All goals completed! 🐙 theorem even_8_term : Even 8 := solution!(Even.succ_succ 6 (Even.succ_succ 4 even_4))

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)

Recall that fun n => blah means "the function that, given n, yields blah," and that Lean treats n + 4 and n + 2 + 2 as synonyms. Another equivalent way to write this definition is:

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

For example, consider this proposition:

def even_plus2 : Prop := ∀ (n : Nat), ∀ (Variable name `E` is not explicitly referenced. Hint: The binding can be removed (if unused) or named `_` (if used implicitly). Alternatively, prefix the name with `_` to silence this warning: [apply] _E Note: This linter can be disabled with `set_option linter.unusedVariables false`E : Even n), Even (n + 2)

A proof term inhabiting this proposition would be a function with two arguments: a number n and some evidence E that n is even. But the name E for this evidence is not used in the rest of the statement of even_plus2, so it's a bit silly to bother making up a name for it. We could write it like this instead, using the dummy identifier _ in place of a real name:

def even_plus2' : Prop := ∀ (n : Nat), ∀ (_ : Even n), Even (n + 2)

Or, equivalently, we can write it in a different, familiar way:

def even_plus2'' : Prop := ∀ (n : Nat), Even n → Even (n + 2)

In general, "P → Q" is just syntactic sugar for "∀ (_ : P), Q".

When we write theorem statements in Lean, we often will name the quantified evidence with a name often beginning with h:

theorem even_plus2_thm : ∀ (n : Nat) (Variable name `heven` is not explicitly referenced. Hint: The binding can be removed (if unused) or named `_` (if used implicitly). Alternatively, prefix the name with `_` to silence this warning: [apply] _heven Note: This linter can be disabled with `set_option linter.unusedVariables false`heven : Even n), Even (n + 2) := ⊢ ∀ (n : Nat), Even n → Even (n + 2) n:Nath:Even n⊢ Even (n + 2); n:Nath:Even n⊢ Even n; All goals completed! 🐙

And we will also put the names before the :, which saves needing to use intro:

theorem even_plus2_thm' (n : Nat) (heven : Even n) : Even (n + 2) := n:Natheven:Even n⊢ Even (n + 2) n:Natheven:Even n⊢ Even n; All goals completed! 🐙

All of these theorem statements are equivalent! When we write def, we are just writing down the statement — the type. When we write theorem, we are stating the type and then providing a witness after the := (either with by and tactics or directly with a term). We can even show the two definitions are equivalent in Lean itself:

theorem even_plus2_defs_same : even_plus2 = even_plus2'' := ⊢ even_plus2 = even_plus2'' All goals completed! 🐙

Remember that theorem statements are just types, so rfl here is just comparing two types.

What about the two theorems? Here, we are asking if two proofs — which we now know are both functions — are equal. Then, do we need to use funext?

theorem even_plus2_theorems_same : even_plus2_thm = even_plus2_thm' := ⊢ even_plus2_thm = even_plus2_thm' All goals completed! 🐙

Surprisingly, we don't. This is because Lean has a special feature called definitional proof irrelevance. It says that any two proofs of the same proposition are definitionally equal. So we could write the same proof again however we wanted — with different tactics, using terms instead of tactics, etc. — and we would still have "the same theorem."

theorem even_plus2_thm'' (n : Nat) (heven : Even n) : Even (n + 2) := n:Natheven:Even n⊢ Even (n + 2) All goals completed! 🐙 theorem even_plus2_theorems_still_same : even_plus2_thm = even_plus2_thm'' := ⊢ even_plus2_thm = even_plus2_thm'' All goals completed! 🐙
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🔗

If we can build proofs by giving explicit terms rather than executing tactic scripts, you may wonder whether we can build programs using tactics rather than by writing down explicit terms.

Naturally, the answer is yes!

def add2 : Nat → Nat := ⊢ Nat → Nat ?_ after intro n: fun n => ?_ after apply Nat.succ: fun n => Nat.succ ?_ after apply Nat.succ: fun n => Nat.succ (Nat.succ ?_) after exact n: fun n => Nat.succ (Nat.succ n)show_proof n:Nat⊢ Nat n:Nat⊢ Nat n:Nat⊢ Nat All goals completed! 🐙
?_

after intro n:
  fun n => ?_

after apply Nat.succ:
  fun n => Nat.succ ?_

after apply Nat.succ:
  fun n => Nat.succ (Nat.succ ?_)

after exact n:
  fun n => Nat.succ (Nat.succ n)
def EvenProp.add2 : Nat → Nat := fun n => n.succ.succ#print add2
def EvenProp.add2 : Nat → Nat :=
fun n => n.succ.succ
4#eval add2 2
4

Notice that we followed def … := with by rather than with a term. This tells Lean to enter proof scripting mode to build an object of type Nat → Nat.

This feature is mainly useful for writing functions with dependent types, which we won't explore much further in this book. But it does illustrate the uniformity and orthogonality of the basic ideas in Lean.

Note to developers (Michael Hicks @mwhicks1)

This statement is a bit mysterious. Why are dependent types special? I think the answer is that they allow for more explicit specifications -- normal types are just not strong enough to say much about a function you might ask tactics to synthesize. There are lots of Nat -> Nat functions, but far fewer that ... insert dependent type here.

Since def and theorem can both use terms or by, is there any difference between the two? There is one: a theorem must have a Prop type.

type of theorem `EvenProp.add2_with_theorem_wrong` is not a proposition Nat → Nattheorem add2_with_theorem_wrong : Nat → Nat := ⊢ Nat → Nat All goals completed! 🐙
type of theorem `EvenProp.add2_with_theorem_wrong` is not a proposition
  Nat → Nat

10.4. Building Proof Objects Incrementally (Optional)🔗

As you probably noticed while solving the exercises earlier in the chapter, constructing proof objects is more involved than constructing the corresponding tactic proofs. Fortunately, there's a simple trick to help in the construction: we can use the term sorry as a placeholder of any type we like.

As an example, let's walk through the process of constructing a proof object demonstrating the evenness of 8.

theorem even_8_atmpt_1 : Even 8 := sorry

Maybe we can use Even.succ_succ to construct a term of type Even 8? Recall that Even.succ_succ is of type

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

If we can demonstrate that 6 is even, we should be done.

theorem even_8_atmpt_2 : Even 8 := Even.succ_succ 6 sorry

In the attempt above, we've omitted the proof that 6 is even, but it can easily be constructed following the same procedure:

theorem even_8_atmpt_3 : Even 8 := Even.succ_succ 6 (Even.succ_succ 4 sorry) theorem even_8_atmpt_4 : Even 8 := Even.succ_succ 6 (Even.succ_succ 4 (Even.succ_succ 2 sorry)) theorem even_8_atmpt_5 : Even 8 := Even.succ_succ 6 (Even.succ_succ 4 (Even.succ_succ 2 (Even.succ_succ 0 Even.zero)))

To recap, we've been guided by an informal proof that we have in our minds, and we check the high-level details before completing the intricacies of the proof. The sorry term allows us to do this.

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🔗

We have now seen that tactics are not "special" in Lean: they are just manipulators of terms. Recall that Lean's logical connectives are also not "special": only universal quantification (with implication as a special case) is built into Lean; all the other connectives are defined inductively. Now that we know more about the relationship between terms and tactics, we can delve into advanced ways to work with logical connectives.

10.6.1. Conjunction🔗

To prove that P ∧ Q holds, we must present evidence for both P and Q. Thus, it makes sense to define a proof object for P ∧ Q to consist of a pair of proofs: one for P and another for Q. This leads to the following definition.

structure And (P Q : Prop) : Prop where intro :: left : P right : Q

Now that we have pulled back the covers a bit further, we can reveal another fact: a structure is just an inductive type with one constructor whose parameters are named. By default, the constructor is called mk, which we can rename to <name> using <name> ::, as in the example.

We can also see that this definition of And matches core And exactly: a structure with constructor intro and fields left/right (except that core uses a and b instead of P and Q).

structure _root_.And (a b : Prop) : Prop number of parameters: 2 fields: _root_.And.left : a _root_.And.right : b constructor: _root_.And.intro {a b : Prop} (left : a) (right : b) : a ∧ b#print _root_.And
structure _root_.And (a b : Prop) : Prop
number of parameters: 2
fields:
  _root_.And.left : a
  _root_.And.right : b
constructor:
  _root_.And.intro {a b : Prop} (left : a) (right : b) : a ∧ b

Notice the similarity with the definition of the MyProd type, given in chapter Poly; the only difference is that MyProd takes Type arguments, whereas And takes Prop arguments.

structure MyProd (α β : Type) : Type number of parameters: 2 fields: MyProd.fst : α MyProd.snd : β constructor: MyProd.mk {α β : Type} (fst : α) (snd : β) : MyProd α β#print MyProd
structure MyProd (α β : Type) : Type
number of parameters: 2
fields:
  MyProd.fst : α
  MyProd.snd : β
constructor:
  MyProd.mk {α β : Type} (fst : α) (snd : β) : MyProd α β

This similarity should clarify why cases, obtain ⟨hp, hq⟩, and intro ⟨hp, hq⟩ patterns can be used on a conjunctive hypothesis. Case analysis allows us to consider all possible ways in which P ∧ Q was proved. For And there is just one — the And.intro constructor:

theorem proj1' (P Q : Prop) (hpq : And P Q) : P := P:PropQ:Prophpq:And P Q⊢ P cases hpq with P:PropQ:Prophp:Pright✝:Q⊢ P All goals completed! 🐙

Here is a use of obtain:

theorem and_comm (P Q : Prop) : And P Q ↔ And Q P := P:PropQ:Prop⊢ And P Q ↔ And Q P P:PropQ:Prop⊢ And P Q → And Q PP:PropQ:Prop⊢ And Q P → And P Q P:PropQ:Prop⊢ And P Q → And Q P P:PropQ:Proph:And P Q⊢ And Q P P:PropQ:Prophp:Phq:Q⊢ And Q P P:PropQ:Prophp:Phq:Q⊢ QP:PropQ:Prophp:Phq:Q⊢ P P:PropQ:Prophp:Phq:Q⊢ Q All goals completed! 🐙 P:PropQ:Prophp:Phq:Q⊢ P All goals completed! 🐙 P:PropQ:Prop⊢ And Q P → And P Q P:PropQ:Proph:And Q P⊢ And P Q P:PropQ:Prophq:Qhp:P⊢ And P Q P:PropQ:Prophq:Qhp:P⊢ PP:PropQ:Prophq:Qhp:P⊢ Q P:PropQ:Prophq:Qhp:P⊢ P All goals completed! 🐙 P:PropQ:Prophq:Qhp:P⊢ Q All goals completed! 🐙

Just as the inductive (structure) definition of And can be manipulated by tactics, we can also use it to build proofs directly.

theorem proj1'' (P Q : Prop) (hpq : P ∧ Q) : P := match hpq with | And.intro hp _ => hp theorem and_comm'_aux (P Q : Prop) (h : P ∧ Q) : Q ∧ P := match h with | And.intro hp hq => And.intro hq hp theorem and_comm' (P Q : Prop) : P ∧ Q ↔ Q ∧ P := Iff.intro (and_comm'_aux P Q) (and_comm'_aux Q P)

Here, Iff.intro is doing the same thing as And.intro: it builds the Iff structure with its two arguments.

Exercise★★(conj_fact)

Construct a proof object for the following proposition.

theorem conj_fact : ∀ (P Q R : Prop), P ∧ Q → Q ∧ R → P ∧ R := solution!(fun _ _ _ hpq hqr => match hpq, hqr with | And.intro hp _, And.intro _ hr => And.intro hp hr)
Quiz

What is the type of this expression?

fun P Q R (h1 : And P Q) (h2 : And Q R) =>
  match h1, h2 with
  | And.intro hp _, And.intro _ hr => And.intro hp hr

(A) ∀ (P Q R : Prop), P ∧ Q → Q ∧ R → P ∧ R

(B) ∀ (P Q R : Prop), Q ∧ P → R ∧ Q → P ∧ R

(C) ∀ (P Q R : Prop), P ∧ R

(D) ∀ (P Q R : Prop), P ∨ Q → Q ∨ R → P ∨ R

(E) Not typeable

Show solution

(A)

fun P Q R h1 h2 => match h1, h2 with | ⟨hp, right⟩, ⟨left, hr⟩ => ⟨hp, hr⟩ : ∀ (P Q R : Prop), P ∧ Q → Q ∧ R → P ∧ R#check (fun P Q R (h1 : And P Q) (h2 : And Q R) => match h1, h2 with | And.intro hp _, And.intro _ hr => And.intro hp hr : ∀ (P Q R : Prop), P ∧ Q → Q ∧ R → P ∧ R)

10.6.2. Disjunction🔗

The inductive definition of disjunction uses two constructors, one for each side of the disjunction:

inductive Or (P Q : Prop) : Prop where | inl : P → Or P Q | inr : Q → Or P Q

This declaration explains the behavior of the cases tactic on a disjunctive hypothesis, since the generated subgoals match the shape of the Or.inl and Or.inr constructors.

Once again, we can also directly write proof objects for theorems involving Or, without resorting to tactics.

theorem inj_l : ∀ (P Q : Prop), P → Or P Q := fun _ _ hp => Or.inl hp theorem inj_l' (P Q : Prop) (hp : P) : Or P Q := P:PropQ:Prophp:P⊢ Or P Q ?_ after left: Or.inl ?_ after exact hp: Or.inl hpshow_proof P:PropQ:Prophp:P⊢ P All goals completed! 🐙
?_

after left:
  Or.inl ?_

after exact hp:
  Or.inl hp
theorem or_elim : ∀ (P Q R : Prop), Or P Q → (P → R) → (Q → R) → R := fun _ _ _ hpq hpr hqr => match hpq with | Or.inl hp => hpr hp | Or.inr hq => hqr hq theorem or_elim' (P Q R : Prop) (hpq : Or P Q) (hpr : P → R) (hqr : Q → R) : R := P:PropQ:PropR:Prophpq:Or P Qhpr:P → Rhqr:Q → R⊢ R cases hpq with P:PropQ:PropR:Prophpr:P → Rhqr:Q → Rhp:P⊢ R P:PropQ:PropR:Prophpr:P → Rhqr:Q → Rhp:P⊢ P All goals completed! 🐙 P:PropQ:PropR:Prophpr:P → Rhqr:Q → Rhq:Q⊢ R P:PropQ:PropR:Prophpr:P → Rhqr:Q → Rhq:Q⊢ Q All goals completed! 🐙
Note to developers (Mike Hicks @mwhicks1)

It is confusing that we don't use show_proof here, but if we did, it doesn't show the proof in the first example; it looks more like the second example directly. Should we change the example? Maybe use the non-sameness to explain how proofs can differ?

Exercise★★(or_commut')

Construct a proof object for the following proposition.

theorem or_commut' : ∀ (P Q : Prop), P ∨ Q → Q ∨ P := solution!(fun (P Q : Prop) (h : P ∨ Q) => match h with | Or.inl hp => Or.inr hp | Or.inr hq => Or.inl hq)
Quiz

What is the type of this expression?

fun P Q h =>
  match h with
  | Or.inl hp => @Or.inr Q P hp
  | Or.inr hq => @Or.inl Q P hq

(A) ∀ P Q H, Q ∨ P ∨ H

(B) ∀ (P Q : Prop), P ∨ Q → Q ∨ P

(C) ∀ P Q H, P ∨ Q → Q ∨ P → H

(D) ∀ (P Q : Prop), P ∨ Q → P ∨ Q

(E) Not typeable

Show solution

(B)

fun P Q h => match h with | Or.inl hp => Or.inr hp | Or.inr hq => Or.inl hq : ∀ (P Q : Prop), P ∨ Q → Q ∨ P#check (fun P Q h => match h with | Or.inl hp => @Or.inr Q P hp | Or.inr hq => @Or.inl Q P hq : ∀ (P Q : Prop), P ∨ Q → Q ∨ P)

10.6.3. Existential Quantification🔗

To give evidence for an existentially quantified proposition P, we package a witness x together with a proof of P x, i.e., that x satisfies P:

inductive Exists {α : Type} (P : α → Prop) : Prop where | intro : ∀ (w : α), P w → Exists P

This definition may need a little unpacking. Exists can be used to build propositions of the form Exists P, where P is a predicate, i.e., a function from witness values of type α to Prop. The Exists.intro constructor then offers a way of constructing evidence for Exists P, given a witness w and a proof of P w.

The more familiar form ∃ x, Even x desugars to an expression involving Exists:

∃ n, Even n : Prop#check (Exists (fun n => Even n) : Prop)
∃ n, Even n : Prop

Here's how to define an explicit proof object involving Exists:

theorem some_nat_is_even : ∃ n, Even n := Exists.intro 4 (Even.succ_succ 2 (Even.succ_succ 0 Even.zero))

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

Which of the following propositions is proved by providing an explicit witness w using exists w?

(A) ∀ (x : Nat), (∃ n, x = n + 1) → x ≠ 0

(B) ∀ (x : Nat), x ≠ 0 → (∃ n, x = n + 1)

(C) ∀ (x : Nat), x = 0 → ¬(∃ n, x = n + 1)

(D) ∀ (x : Nat), x = 4 → x ≠ 0

(E) none of the above

Show solution

(B)

example : ∀ (x : Nat), x ≠ 0 → (∃ n, x = n + 1) := ⊢ ∀ (x : Nat), x ≠ 0 → ∃ n, x = n + 1 x:Nath:x ≠ 0⊢ ∃ n, x = n + 1 cases x with h:0 ≠ 0⊢ ∃ n, 0 = n + 1 h:0 ≠ 0⊢ False h:0 ≠ 0⊢ 0 = 0 All goals completed! 🐙 x':Nath:x' + 1 ≠ 0⊢ ∃ n, x' + 1 = n + 1 All goals completed! 🐙
Exercise★★(ex_even_Sn)

Construct a proof object for the following proposition.

theorem ex_even_Sn : Exists (fun n => Even (n + 1)) := solution!(Exists.intro 1 (Even.succ_succ 0 Even.zero))

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)
Exercise★★(ex_match)

Construct a proof object for the following proposition:

theorem ex_match : ∀ (A : Type) (P Q : A → Prop), (∀ (x : A), P x → Q x) → (∃ x, P x) → (∃ x, Q x) := solution!(fun _ _ _ hpq hp => match hp with | Exists.intro x hpx => Exists.intro x (hpq x hpx))

10.6.4. True and False🔗

The inductive definition of the True proposition is simple:

inductive True : Prop where | intro : True

It has one constructor: there is one definitional way to build True. (But there are lots of ways to state and prove true things!)

Exercise★(p_implies_true)

Construct a proof object for the following proposition.

theorem p_implies_true : ∀ (P : Prop), P → True := solution!(fun _ _ => True.intro)

False is equally simple — indeed, so simple it may look syntactically wrong at first glance!

inductive False : Prop

That is, False is an inductive type with no constructors, i.e., no way to build evidence for it. Thus, there is no way to complete the following definition (replacing sorry) such that it succeeds.

theorem declaration uses `sorry`contra : False := sorry

But it is possible to destruct False by pattern matching. There can be no patterns that match it, since it has no constructors. To handle this, Lean uses the nomatch construct.

theorem false_implies_zero_eq_one : False → 0 = 1 := fun contra => nomatch contra

Since there are no branches to evaluate, the nomatch expression can be given any type we want, including 0 = 1. Fortunately, it's impossible to ever cause the nomatch to be evaluated, because we can never construct a value of type False to pass to the function.

Exercise★(ex_falso_quodlibet')

Construct a proof object for the following proposition.

theorem ex_falso_quodlibet' : ∀ (P : Prop), False → P := solution!(fun _ contra => nomatch contra)

10.7. Equality🔗

Even Lean's equality relation is not built in. We can define it ourselves:

inductive Eq {α : Type} : α → α → Prop where | refl : ∀ (x : α), Eq x x scoped infix:50 " =' " => Eq

The Eq definition relates pairs of elements of type α. The only way to prove Eq a b for a pair of elements a and b is via the Eq.refl constructor, which by requiring Eq x x for all x forces a and b to be the same.

This means we can use Eq.refl to construct evidence that, for example, 2 = 2. Can we also use it to construct evidence that 1 + 1 = 2? Perhaps surprisingly: Yes, we can!

The reason is that Lean treats as "the same" any two terms that are convertible according to a simple set of computation rules. These rules, which are similar to those used by #eval, include evaluation of function application, inlining of definitions, and simplification of match expressions.

theorem four : 2 + 2 =' 1 + 3 := ⊢ 2 + 2 =' 1 + 3 All goals completed! 🐙

The rfl tactic that we have used to prove equalities of the form x = y up to now is essentially just shorthand for apply Eq.refl.

In tactic-based proofs of equality, the conversion rules operate invisibly: whenever Lean checks two terms for definitional equality — as rfl does when closing a goal x = y, or as exact and apply do when unifying a term against an expected type — it reduces both sides by these computation rules before comparing them. You can see what's going on by enabling the Lean option trace.Meta.isDefEq:

set_option trace.Meta.isDefEq true in example :
[Meta.isDefEq] ✅️ ?m.9 =?= ?m.11
  • [Meta.isDefEq] ?m.9 [assignable] =?= ?m.11 [assignable]
  • [Meta.isDefEq] ✅️ Type ?u.3 =?= Sort ?u.2
[Meta.isDefEq] ✅️ ?m.11 =?= ?m.11[Meta.isDefEq] ✅️ Sort ?u.1 =?= Prop
[Meta.isDefEq] ✅️ ?m.1 =?= ?m.7
  • [Meta.isDefEq] ?m.1 [assignable] =?= ?m.7 [assignable]
  • [Meta.isDefEq] ✅️ Type ?u.7 =?= Type ?u.5
[Meta.isDefEq] ✅️ ?m.3 =?= ?m.8
  • [Meta.isDefEq] ?m.3 [assignable] =?= ?m.8 [assignable]
  • [Meta.isDefEq] ✅️ Type ?u.9 =?= Type ?u.4
[Meta.isDefEq] 💥️ HAdd ?m.7 ?m.8 ?m.11 =?= HAdd Std.Time.WallTime Std.Time.Week.Offset Std.Time.WallTime
  • [Meta.isDefEq] 💥️ ?m.7 =?= Std.Time.WallTime
    • [Meta.isDefEq] ?m.7 [nonassignable] =?= Std.Time.WallTime [nonassignable]
[Meta.isDefEq] 💥️ HAdd ?m.7 ?m.8 ?m.12 =?= HAdd Std.Time.WallTime Std.Time.Week.Offset Std.Time.WallTime
  • [Meta.isDefEq] 💥️ ?m.7 =?= Std.Time.WallTime
    • [Meta.isDefEq] ?m.7 [nonassignable] =?= Std.Time.WallTime [nonassignable]
[Meta.isDefEq] 💥️ HAdd ?m.7 ?m.8 ?m.12 =?= HAdd Std.Time.WallTime Std.Time.Week.Offset Std.Time.WallTime
  • [Meta.isDefEq] 💥️ ?m.7 =?= Std.Time.WallTime
    • [Meta.isDefEq] ?m.7 [nonassignable] =?= Std.Time.WallTime [nonassignable]
[Meta.isDefEq] 💥️ HAdd ?m.7 ?m.8 ?m.12 =?= HAdd Std.Time.WallTime Std.Time.Week.Offset Std.Time.WallTime
  • [Meta.isDefEq] 💥️ ?m.7 =?= Std.Time.WallTime
    • [Meta.isDefEq] ?m.7 [nonassignable] =?= Std.Time.WallTime [nonassignable]
[Meta.isDefEq] ✅️ ?m.10 =?= instHAdd
  • [Meta.isDefEq] ?m.10 [assignable] =?= instHAdd [nonassignable]
  • [Meta.isDefEq] ✅️ HAdd ?m.7 ?m.8 ?m.11 =?= HAdd ?α ?α ?α
    • [Meta.isDefEq] ✅️ ?m.7 =?= ?α
      • [Meta.isDefEq] ?m.7 [assignable] =?= ?α [assignable]
      • [Meta.isDefEq] ✅️ Type ?u.5 =?= Type ?u.12
    • [Meta.isDefEq] ✅️ ?m.8 =?= ?α
      • [Meta.isDefEq] ?m.8 [assignable] =?= ?α [assignable]
      • [Meta.isDefEq] ✅️ Type ?u.4 =?= Type ?u.12
    • [Meta.isDefEq] ✅️ ?m.11 =?= ?α
      • [Meta.isDefEq] ?m.11 [assignable] =?= ?α [assignable]
      • [Meta.isDefEq] ✅️ Type ?u.3 =?= Type ?u.12
[Meta.isDefEq] 💥️ Add ?α =?= Add (Lean.Grind.Ring.OfSemiring.Q ?m.15)
  • [Meta.isDefEq] 💥️ ?α =?= Lean.Grind.Ring.OfSemiring.Q ?m.15
    • [Meta.isDefEq] ?α [nonassignable] =?= Lean.Grind.Ring.OfSemiring.Q ?m.15 [nonassignable]
[Meta.isDefEq] 💥️ HAdd Nat ?m.8 ?m.13 =?= HAdd ?m.15 ?m.15 ?m.15
  • [Meta.isDefEq] ✅️ Nat =?= ?m.15
    • [Meta.isDefEq] Nat [nonassignable] =?= ?m.15 [assignable]
    • [Meta.isDefEq.transparency] raising transparency instances → implicit
    • [Meta.isDefEq] ✅️ Type ?u.13 =?= Type
  • [Meta.isDefEq] 💥️ ?m.8 =?= Nat
    • [Meta.isDefEq] ?m.8 [nonassignable] =?= Nat [nonassignable]
[Meta.isDefEq] 💥️ HAdd Nat ?m.8 ?m.13 =?= HAdd ?m.15 ?m.15 ?m.15
  • [Meta.isDefEq] ✅️ Nat =?= ?m.15
    • [Meta.isDefEq] Nat [nonassignable] =?= ?m.15 [assignable]
    • [Meta.isDefEq.transparency] raising transparency instances → implicit
    • [Meta.isDefEq] ✅️ Type ?u.13 =?= Type
  • [Meta.isDefEq] 💥️ ?m.8 =?= Nat
    • [Meta.isDefEq] ?m.8 [nonassignable] =?= Nat [nonassignable]
[Meta.isDefEq] ✅️ ?m.10 =?= instHAdd
  • [Meta.isDefEq] ?m.10 [assignable] =?= instHAdd [nonassignable]
  • [Meta.isDefEq] ✅️ HAdd Nat ?m.8 ?m.11 =?= HAdd ?α ?α ?α
    • [Meta.isDefEq] ✅️ Nat =?= ?α
      • [Meta.isDefEq] Nat [nonassignable] =?= ?α [assignable]
      • [Meta.isDefEq] ✅️ Type ?u.12 =?= Type
    • [Meta.isDefEq] ✅️ ?m.8 =?= Nat
      • [Meta.isDefEq] ?m.8 [assignable] =?= Nat [nonassignable]
      • [Meta.isDefEq] ✅️ Type ?u.4 =?= Type
    • [Meta.isDefEq] ✅️ ?m.11 =?= Nat
      • [Meta.isDefEq] ?m.11 [assignable] =?= Nat [nonassignable]
      • [Meta.isDefEq] ✅️ Type ?u.3 =?= Type
[Meta.isDefEq] ✅️ Add Nat =?= Add Nat[Meta.isDefEq] ✅️ Add Nat =?= Add Nat
[Meta.isDefEq] ✅️ ?inst✝ =?= instAddNat
  • [Meta.isDefEq] ?inst✝ [assignable] =?= instAddNat [nonassignable]
  • [Meta.isDefEq] ✅️ Add Nat =?= Add Nat
    • [Meta.isDefEq] ✅️ Nat =?= Nat
[Meta.isDefEq] 💥️ OfNat ?m.1 1 =?= OfNat (Lean.Grind.Ring.OfSemiring.Q ?m.4) ?m.6
  • [Meta.isDefEq] 💥️ ?m.1 =?= Lean.Grind.Ring.OfSemiring.Q ?m.4
    • [Meta.isDefEq] ?m.1 [nonassignable] =?= Lean.Grind.Ring.OfSemiring.Q ?m.4 [nonassignable]
[Meta.isDefEq] 💥️ OfNat ?m.1 1 =?= OfNat (Lean.Grind.Ring.OfSemiring.Q ?m.6) ?m.8
  • [Meta.isDefEq] 💥️ ?m.1 =?= Lean.Grind.Ring.OfSemiring.Q ?m.6
    • [Meta.isDefEq] ?m.1 [nonassignable] =?= Lean.Grind.Ring.OfSemiring.Q ?m.6 [nonassignable]
[Meta.isDefEq] 💥️ OfNat ?m.1 1 =?= OfNat (Lean.Grind.Ring.OfSemiring.Q ?m.8) ?m.10
  • [Meta.isDefEq] 💥️ ?m.1 =?= Lean.Grind.Ring.OfSemiring.Q ?m.8
    • [Meta.isDefEq] ?m.1 [nonassignable] =?= Lean.Grind.Ring.OfSemiring.Q ?m.8 [nonassignable]
[Meta.isDefEq] 💥️ OfNat ?m.7 1 =?= OfNat (Lean.Grind.Ring.OfSemiring.Q ?m.13) ?m.15
  • [Meta.isDefEq] 💥️ ?m.7 =?= Lean.Grind.Ring.OfSemiring.Q ?m.13
    • [Meta.isDefEq] ?m.7 [nonassignable] =?= Lean.Grind.Ring.OfSemiring.Q ?m.13 [nonassignable]
[Meta.isDefEq] 💥️ OfNat ?m.7 1 =?= OfNat (Lean.Grind.Ring.OfSemiring.Q ?m.13) ?m.15
  • [Meta.isDefEq] 💥️ ?m.7 =?= Lean.Grind.Ring.OfSemiring.Q ?m.13
    • [Meta.isDefEq] ?m.7 [nonassignable] =?= Lean.Grind.Ring.OfSemiring.Q ?m.13 [nonassignable]
[Meta.isDefEq] 💥️ OfNat ?m.7 1 =?= OfNat (Lean.Grind.Ring.OfSemiring.Q ?m.13) ?m.15
  • [Meta.isDefEq] 💥️ ?m.7 =?= Lean.Grind.Ring.OfSemiring.Q ?m.13
    • [Meta.isDefEq] ?m.7 [nonassignable] =?= Lean.Grind.Ring.OfSemiring.Q ?m.13 [nonassignable]
[Meta.isDefEq] ✅️ ?m.2 =?= instOfNatNat ?n
  • [Meta.isDefEq] ?m.2 [assignable] =?= instOfNatNat ?n [nonassignable]
  • [Meta.isDefEq] ✅️ OfNat ?m.7 1 =?= OfNat Nat ?n
    • [Meta.isDefEq] ✅️ ?m.7 =?= Nat
      • [Meta.isDefEq] ?m.7 [assignable] =?= Nat [nonassignable]
      • [Meta.isDefEq] ✅️ Type ?u.5 =?= Type
    • [Meta.isDefEq] ✅️ 1 =?= ?n
      • [Meta.isDefEq] 1 [nonassignable] =?= ?n [assignable]
      • [Meta.isDefEq] ✅️ Nat =?= Nat
1
+
[Meta.isDefEq] 💥️ OfNat ?m.3 1 =?= OfNat (Lean.Grind.Ring.OfSemiring.Q ?m.6) ?m.8
  • [Meta.isDefEq] 💥️ ?m.3 =?= Lean.Grind.Ring.OfSemiring.Q ?m.6
    • [Meta.isDefEq] ?m.3 [nonassignable] =?= Lean.Grind.Ring.OfSemiring.Q ?m.6 [nonassignable]
[Meta.isDefEq] 💥️ OfNat ?m.3 1 =?= OfNat (Lean.Grind.Ring.OfSemiring.Q ?m.6) ?m.8
  • [Meta.isDefEq] 💥️ ?m.3 =?= Lean.Grind.Ring.OfSemiring.Q ?m.6
    • [Meta.isDefEq] ?m.3 [nonassignable] =?= Lean.Grind.Ring.OfSemiring.Q ?m.6 [nonassignable]
[Meta.isDefEq] 💥️ OfNat ?m.3 1 =?= OfNat (Lean.Grind.Ring.OfSemiring.Q ?m.8) ?m.10
  • [Meta.isDefEq] 💥️ ?m.3 =?= Lean.Grind.Ring.OfSemiring.Q ?m.8
    • [Meta.isDefEq] ?m.3 [nonassignable] =?= Lean.Grind.Ring.OfSemiring.Q ?m.8 [nonassignable]
[Meta.isDefEq] 💥️ OfNat ?m.8 1 =?= OfNat (Lean.Grind.Ring.OfSemiring.Q ?m.13) ?m.15
  • [Meta.isDefEq] 💥️ ?m.8 =?= Lean.Grind.Ring.OfSemiring.Q ?m.13
    • [Meta.isDefEq] ?m.8 [nonassignable] =?= Lean.Grind.Ring.OfSemiring.Q ?m.13 [nonassignable]
[Meta.isDefEq] 💥️ OfNat ?m.8 1 =?= OfNat (Lean.Grind.Ring.OfSemiring.Q ?m.13) ?m.15
  • [Meta.isDefEq] 💥️ ?m.8 =?= Lean.Grind.Ring.OfSemiring.Q ?m.13
    • [Meta.isDefEq] ?m.8 [nonassignable] =?= Lean.Grind.Ring.OfSemiring.Q ?m.13 [nonassignable]
[Meta.isDefEq] 💥️ OfNat ?m.8 1 =?= OfNat (Lean.Grind.Ring.OfSemiring.Q ?m.13) ?m.15
  • [Meta.isDefEq] 💥️ ?m.8 =?= Lean.Grind.Ring.OfSemiring.Q ?m.13
    • [Meta.isDefEq] ?m.8 [nonassignable] =?= Lean.Grind.Ring.OfSemiring.Q ?m.13 [nonassignable]
[Meta.isDefEq] 💥️ OfNat ?m.8 1 =?= OfNat (Lean.Grind.Ring.OfSemiring.Q ?m.14) ?m.16
  • [Meta.isDefEq] 💥️ ?m.8 =?= Lean.Grind.Ring.OfSemiring.Q ?m.14
    • [Meta.isDefEq] ?m.8 [nonassignable] =?= Lean.Grind.Ring.OfSemiring.Q ?m.14 [nonassignable]
[Meta.isDefEq] 💥️ OfNat ?m.8 1 =?= OfNat (Lean.Grind.Ring.OfSemiring.Q ?m.14) ?m.16
  • [Meta.isDefEq] 💥️ ?m.8 =?= Lean.Grind.Ring.OfSemiring.Q ?m.14
    • [Meta.isDefEq] ?m.8 [nonassignable] =?= Lean.Grind.Ring.OfSemiring.Q ?m.14 [nonassignable]
[Meta.isDefEq] ✅️ OfNat Nat 1 =?= OfNat Nat ?m.16
  • [Meta.isDefEq] ✅️ Nat =?= Nat
  • [Meta.isDefEq] ✅️ 1 =?= ?m.16
    • [Meta.isDefEq] 1 [nonassignable] =?= ?m.16 [assignable]
    • [Meta.isDefEq.transparency] raising transparency instances → implicit
    • [Meta.isDefEq] ✅️ Nat =?= Nat
[Meta.isDefEq] ✅️ OfNat Nat 1 =?= OfNat Nat 1
[Meta.isDefEq] ✅️ ?m.4 =?= instOfNatNat 1
  • [Meta.isDefEq] ?m.4 [assignable] =?= instOfNatNat 1 [nonassignable]
  • [Meta.isDefEq] ✅️ OfNat Nat 1 =?= OfNat Nat 1
    • [Meta.isDefEq] ✅️ Nat =?= Nat
    • [Meta.isDefEq] ✅️ 1 =?= 1
1
=
[Meta.isDefEq] 💥️ OfNat ?m.5 2 =?= OfNat (Lean.Grind.Ring.OfSemiring.Q ?m.8) ?m.10
  • [Meta.isDefEq] 💥️ ?m.5 =?= Lean.Grind.Ring.OfSemiring.Q ?m.8
    • [Meta.isDefEq] ?m.5 [nonassignable] =?= Lean.Grind.Ring.OfSemiring.Q ?m.8 [nonassignable]
[Meta.isDefEq] 💥️ OfNat ?m.5 2 =?= OfNat (Lean.Grind.Ring.OfSemiring.Q ?m.8) ?m.10
  • [Meta.isDefEq] 💥️ ?m.5 =?= Lean.Grind.Ring.OfSemiring.Q ?m.8
    • [Meta.isDefEq] ?m.5 [nonassignable] =?= Lean.Grind.Ring.OfSemiring.Q ?m.8 [nonassignable]
[Meta.isDefEq] ✅️ ?m.5 =?= ?m.9
  • [Meta.isDefEq] ?m.5 [assignable] =?= ?m.9 [assignable]
  • [Meta.isDefEq] ✅️ Type ?u.11 =?= Type ?u.3
[Meta.isDefEq] 💥️ OfNat ?m.11 2 =?= OfNat (Lean.Grind.Ring.OfSemiring.Q ?m.13) ?m.15
  • [Meta.isDefEq] 💥️ ?m.11 =?= Lean.Grind.Ring.OfSemiring.Q ?m.13
    • [Meta.isDefEq] ?m.11 [nonassignable] =?= Lean.Grind.Ring.OfSemiring.Q ?m.13 [nonassignable]
[Meta.isDefEq] 💥️ OfNat ?m.11 2 =?= OfNat (Lean.Grind.Ring.OfSemiring.Q ?m.13) ?m.15
  • [Meta.isDefEq] 💥️ ?m.11 =?= Lean.Grind.Ring.OfSemiring.Q ?m.13
    • [Meta.isDefEq] ?m.11 [nonassignable] =?= Lean.Grind.Ring.OfSemiring.Q ?m.13 [nonassignable]
[Meta.isDefEq] 💥️ OfNat ?m.11 2 =?= OfNat (Lean.Grind.Ring.OfSemiring.Q ?m.13) ?m.15
  • [Meta.isDefEq] 💥️ ?m.11 =?= Lean.Grind.Ring.OfSemiring.Q ?m.13
    • [Meta.isDefEq] ?m.11 [nonassignable] =?= Lean.Grind.Ring.OfSemiring.Q ?m.13 [nonassignable]
[Meta.isDefEq] 💥️ OfNat ?m.11 2 =?= OfNat (Lean.Grind.Ring.OfSemiring.Q ?m.14) ?m.16
  • [Meta.isDefEq] 💥️ ?m.11 =?= Lean.Grind.Ring.OfSemiring.Q ?m.14
    • [Meta.isDefEq] ?m.11 [nonassignable] =?= Lean.Grind.Ring.OfSemiring.Q ?m.14 [nonassignable]
[Meta.isDefEq] 💥️ OfNat ?m.11 2 =?= OfNat (Lean.Grind.Ring.OfSemiring.Q ?m.14) ?m.16
  • [Meta.isDefEq] 💥️ ?m.11 =?= Lean.Grind.Ring.OfSemiring.Q ?m.14
    • [Meta.isDefEq] ?m.11 [nonassignable] =?= Lean.Grind.Ring.OfSemiring.Q ?m.14 [nonassignable]
[Meta.isDefEq] ✅️ OfNat Nat 2 =?= OfNat Nat ?m.16
  • [Meta.isDefEq] ✅️ Nat =?= Nat
  • [Meta.isDefEq] ✅️ 2 =?= ?m.16
    • [Meta.isDefEq] 2 [nonassignable] =?= ?m.16 [assignable]
    • [Meta.isDefEq.transparency] raising transparency instances → implicit
    • [Meta.isDefEq] ✅️ Nat =?= Nat
[Meta.isDefEq] ✅️ OfNat Nat 2 =?= OfNat Nat 2
[Meta.isDefEq] ✅️ ?m.6 =?= instOfNatNat 2
  • [Meta.isDefEq] ?m.6 [assignable] =?= instOfNatNat 2 [nonassignable]
  • [Meta.isDefEq] ✅️ OfNat Nat 2 =?= OfNat Nat 2
    • [Meta.isDefEq] ✅️ Nat =?= Nat
    • [Meta.isDefEq] ✅️ 2 =?= 2
2
:=
[Meta.isDefEq] ✅️ 1 + 1 = 2 =?= ?m.16 = ?m.16
  • [Meta.isDefEq] ✅️ Nat =?= ?m.15
    • [Meta.isDefEq] Nat [nonassignable] =?= ?m.15 [assignable]
    • [Meta.isDefEq] ✅️ Sort ?u.13 =?= Type
  • [Meta.isDefEq] ✅️ 1 + 1 =?= ?m.16
    • [Meta.isDefEq] 1 + 1 [nonassignable] =?= ?m.16 [assignable]
    • [Meta.isDefEq] ✅️ Nat =?= Nat
  • [Meta.isDefEq] ✅️ 2 =?= 1 + 1
    • [Meta.isDefEq] ✅️ 2 =?= 1 + 1
      • [Meta.isDefEq] ✅️ instHAdd =?= instHAdd
      • [Meta.isDefEq] ✅️ Nat =?= Nat
      • [Meta.isDefEq] ✅️ 1 =?= 1
[Meta.isDefEq] ✅️ 1 + 1 = 1 + 1 =?= 1 + 1 = 2
  • [Meta.isDefEq] ✅️ 1 + 1 =?= 1 + 1
  • [Meta.isDefEq] ✅️ 1 + 1 =?= 2
    • [Meta.isDefEq] ✅️ instHAdd =?= instHAdd
    • [Meta.isDefEq] ✅️ Nat =?= Nat
    • [Meta.isDefEq] ✅️ 1 =?= 1
  • [Meta.isDefEq] ✅️ Nat =?= Nat
rfl

In explicit proofs of equality, the conversion rules still operate invisibly, but their result is made manifest as an argument to Eq.refl in the proof term.

theorem four' : 2 + 2 =' 1 + 3 := Eq.refl 4 theorem singleton : ∀ (α : Type) (x : α), [] ++ [x] =' x :: [] := fun (α : Type) (x : α) => Eq.refl [x]

We can also pattern-match on an equality proof:

theorem eq_add : ∀ (n1 n2 : Nat), n1 =' n2 → (n1 + 1) =' (n2 + 1) := fun n1 Variable name `n2` is not explicitly referenced. Hint: The binding can be removed (if unused) or named `_` (if used implicitly). Alternatively, prefix the name with `_` to silence this warning: [apply] _n2 Note: This linter can be disabled with `set_option linter.unusedVariables false`n2 heq => match heq with | Eq.refl _ => Eq.refl (n1 + 1)

By pattern-matching against n1 =' n2, we replace n2 with n1 in the type we have to produce, so instead of (n1 + 1) =' (n2 + 1), we now have to produce something of type (n1 + 1) =' (n1 + 1), which we establish by Eq.refl (n1 + 1).

A tactic-based proof runs into some difficulties if we try to use our usual repertoire of tactics, such as rw and rfl. Those work with relations that Lean knows about, such as =, but not with our ='. We could teach Lean about =' (by registering a reflexivity lemma for rfl, or by working in a quotient type where =' becomes =, for rw), but a simpler way is to use cases and apply instead.

example (n1 n2 : Nat) (heq : n1 =' n2) : (n1 + 1) =' (n2 + 1) := n1:Natn2:Natheq:n1 =' n2⊢ n1 + 1 =' n2 + 1 n1:Natn2:Natheq:n1 =' n2⊢ n1 + 1 =' n2 + 1 -- doesn't work for _our_ =' relation example (n1 : Nat) : (n1 + 1) =' (n1 + 1) := n1:Nat⊢ n1 + 1 =' n1 + 1 Tactic `rfl` failed: No `[refl]` lemma registered for relation Eq Hint: Add the `[refl]` attribute to reflexivity lemmas for `Eq` to use this tactic n1:Nat⊢ n1 + 1 =' n1 + 1n1:Nat⊢ n1 + 1 =' n1 + 1 -- doesn't work for _our_ =' relation theorem eq_add' (n1 n2 : Nat) (heq : n1 =' n2) : (n1 + 1) =' (n2 + 1) := n1:Natn2:Natheq:n1 =' n2⊢ n1 + 1 =' n2 + 1 n1:Nat⊢ n1 + 1 =' n1 + 1 -- n2 replaced by n1 in the goal! All goals completed! 🐙
Exercise★★(eq_cons)

Construct the proof object for the following theorem. Use pattern matching on the equality hypotheses.

theorem eq_cons : ∀ (α : Type) (h1 h2 : α) (t1 t2 : List α), h1 =' h2 → t1 =' t2 → h1 :: t1 =' h2 :: t2 := solution!(fun _ h1 _ t1 _ heq teq => match heq, teq with | Eq.refl _, Eq.refl _ => Eq.refl (h1 :: t1))
Exercise★★(equality__leibniz_equality)

The inductive definition of equality implies Leibniz equality: what we mean when we say "x and y are equal" is that every property P that is true of x is also true of y. Prove that.

theorem equality__leibniz_equality : ∀ (α : Type) (x y : α), x =' y → ∀ (P : α → Prop), P x → P y := ⊢ ∀ (α : Type) (x y : α), x =' y → ∀ (P : α → Prop), P x → P y solution! α:Typex:αy:αheq:x =' yP:α → Prophpx:P x⊢ P y α:Typex:αP:α → Prophpx:P x⊢ P x All goals completed! 🐙
Exercise★★(equality__leibniz_equality_term)

Construct the proof object for the previous exercise. All it requires is anonymous functions and pattern-matching; the large proof term constructed by tactics in the previous exercise is needessly complicated. Hint: pattern-match as soon as possible.

theorem equality__leibniz_equality_term : ∀ (α : Type) (x y : α), x =' y → ∀ (P : α → Prop), P x → P y := solution!(fun _ _ _ heq => match heq with | Eq.refl _ => fun _ hp => hp)
Exercise★★(leibniz_equality__equality) (Optional)

Show that, in fact, the inductive definition of equality is equivalent to Leibniz equality. Hint: the proof is quite short. You can write it by inventing a clever property P to instantiate the antecedent, or you can let Lean figure it out...

theorem leibniz_equality__equality : ∀ (α : Type) (x y : α), (∀ (P : α → Prop), P x → P y) → x =' y := ⊢ ∀ (α : Type) (x y : α), (∀ (P : α → Prop), P x → P y) → x =' y solution! α:Typex:αy:αh:∀ (P : α → Prop), P x → P y⊢ x =' y α:Typex:αy:αh:∀ (P : α → Prop), P x → P y⊢ x =' x -- `apply h` also works; Lean will provide `P`. All goals completed! 🐙
Quiz

Which of the following is a correct proof object for the proposition

∃ x, x + 3 =' 4

?

(A) Eq.refl 4

(B) @Exists.intro Nat (z + 3 =' 4) 1 (Eq.refl 4)

(C) @Exists.intro Nat (fun z => z + 3 =' 4) 1 (Eq.refl 4)

(D) @Exists.intro Nat (fun z => z + 3 =' 4) 1 (Eq.refl 1)

(E) none of the above

Show solution
theorem quiz1 : ∃ x, x + 3 =' 4 := Type mismatch Eq.refl 4 has type 4 =' 4 but is expected to have type ∃ x, x + 3 =' 4Eq.refl 4 theorem quiz2 : ∃ x, x + 3 =' 4 := @Exists.intro Nat (Unknown identifier `z`z + 3 =' 4) 1 (Eq.refl 4) theorem quiz3 : ∃ x, x + 3 =' 4 := @Exists.intro Nat (fun z => z + 3 =' 4) 1 (Eq.refl 4) theorem quiz4 : ∃ x, x + 3 =' 4 := @Exists.intro Nat (fun z => z + 3 =' 4) 1 Application type mismatch: The argument Eq.refl 1 has type 1 =' 1 but is expected to have type 1 + 3 =' 4 in the application Exists.intro 1 (Eq.refl 1)(Eq.refl 1)
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.

One question that arises with any automated proof assistant is "why should we trust it?" — i.e., what if there is a bug in the implementation that renders all its reasoning suspect?

While it is impossible to allay such concerns completely, the fact that Lean is based on the Curry-Howard correspondence gives it a strong foundation. Because propositions are just types and proofs are just terms, checking that an alleged proof of a proposition is valid just amounts to type-checking the term. Type checkers are relatively small and straightforward programs, so the "trusted computing base" for Lean — the part of the code that we have to believe is operating correctly — is small too.

How, then, does Lean relegate its large set of complex behaviors to a small codebase?

Lean is organized in two layers. The elaborator is large and complicated: it handles notation, implicit arguments, match, recursion, and tactics. Its output is a plain term in Lean's core type theory, which it hands to the kernel. Only the kernel is trusted. It is small, and its job is just to type-check that term, computing as needed to decide whether two types are the same.

This division means that a bug in the elaborator, or in a tactic, cannot lead Lean to accept a false theorem: at worst, it produces a term that the kernel then rejects. Every declaration, whether written as a term or built by tactics, is checked by the kernel when it is added to the environment.

Two checks you might expect a typechecker to perform, exhaustiveness of match and termination of recursive functions, happen in the elaborator, because the kernel's language actually has no match and no recursion at all. The kernel's language for destructuring values only has the notion of a recursor: a primitive function that is exhaustive and terminating by construction. If the elaborator cannot express a definition in terms of the recursors generated by the kernel, it rejects the definition.

There are some mild exceptions to this, like partial def, but those exceptions have strict rules imposed upon them to prevent a proof of False, and in general it is the translation to recursors that catches such bugs.

We can see the elaborator refuse definitions that would otherwise let us prove False:

theorem or_bogus : ∀ (P Q : Prop), P ∨ Q → P := fun (P Q : Prop) (A : P ∨ Q) => Missing cases: (Or.inr _)match A with | Or.inl h => h

All the types here match correctly, but the match only considers one of the possible constructors for Or. Lean's exhaustiveness check will reject this definition.

def infinite_loop {α : Type} (n : Nat) : α := infinite_loop n cannot use specified measure for structural recursion: it is unchanged in the recursive callstermination_by structural n theorem falso : False := Type mismatch infinite_loop 0 has type ?m.1 of sort `Type` but is expected to have type False of sort `Prop`infinite_loop 0

Recursive function infinite_loop purports to return a value of any type α that you would like. (The termination_by structural n annotation tells Lean that it recurses on argument n, not α.) Were Lean to allow infinite_loop, then falso would be definable, thus giving evidence for False. So Lean rejects infinite_loop.

Besides the kernel, we also trust the handful of axioms Lean assumes, such as propext. The command #print axioms shows which axioms a theorem depends on. The tactic native_decide goes further, trusting Lean's compiler too, which is why careful developments avoid it.

10.9. More Exercises🔗

Most of the following theorems were already proved with tactics in Logic. Now construct the proof objects for them directly.

Exercise★★(and_assoc)
theorem and_assoc : ∀ (P Q R : Prop), P ∧ (Q ∧ R) → (P ∧ Q) ∧ R := solution!(fun _ _ _ h => match h with | And.intro hp (And.intro hq hr) => And.intro (And.intro hp hq) hr)
Exercise★★★(or_distributes_over_and)
theorem or_distributes_over_and : ∀ (P Q R : Prop), P ∨ (Q ∧ R) ↔ (P ∨ Q) ∧ (P ∨ R) := solution!(fun _ _ _ => Iff.intro (fun h => match h with | Or.inl hp => And.intro (Or.inl hp) (Or.inl hp) | Or.inr (And.intro hq hr) => And.intro (Or.inr hq) (Or.inr hr)) (fun h => match h with | And.intro hpq hpr => match hpq, hpr with | Or.inl hp, _ | _, Or.inl hp => Or.inl hp | Or.inr hq, Or.inr hr => Or.inr (And.intro hq hr)))
Exercise★★★(negations)
theorem double_neg : ∀ (P : Prop), P → ¬¬P := solution!(fun _ hp hnp => hnp hp) theorem contradiction_implies_anything : ∀ (P Q : Prop), (P ∧ ¬P) → Q := solution!(fun _ _ h => match h with | And.intro hp hnp => nomatch hnp hp) theorem de_morgan_not_or : ∀ (P Q : Prop), ¬(P ∨ Q) → ¬P ∧ ¬Q := solution!(fun _ _ h => And.intro (fun hp => h (Or.inl hp)) (fun hq => h (Or.inr hq)))
Exercise★★(currying)
theorem curry : ∀ (P Q R : Prop), ((P ∧ Q) → R) → (P → (Q → R)) := solution!(fun _ _ _ h hp hq => h (And.intro hp hq)) theorem uncurry : ∀ (P Q R : Prop), (P → (Q → R)) → ((P ∧ Q) → R) := solution!(fun _ _ _ h hpq => match hpq with | And.intro hp hq => h hp hq)

10.10. Working with Proof Irrelevance🔗

In Logic we saw that functional extensionality (funext) is a core property of Lean. A similar notion about propositions also exists in Lean, this time as a core axiom of propositional extensionality:

-- Written out, propositional extensionality looks like this: def propositional_extensionality : Prop := ∀ (P Q : Prop), (P ↔ Q) → P = Q -- Lean calls it `propext`: propext {a b : Prop} : (a ↔ b) → a = b#check propext
propext {a b : Prop} : (a ↔ b) → a = b

Propositional extensionality asserts that if two propositions are equivalent — i.e., each implies the other — then they are in fact equal. The proof objects for the propositions might be syntactically different terms. But propositional extensionality overlooks that, just as functional extensionality overlooks the syntactic differences between functions.

Exercise★(pe_implies_or_eq) (Advanced)

Prove the following consequence of propositional extensionality.

theorem pe_implies_or_eq : propositional_extensionality → ∀ (P Q : Prop), (P ∨ Q) = (Q ∨ P) := ⊢ propositional_extensionality → ∀ (P Q : Prop), (P ∨ Q) = (Q ∨ P) solution! ⊢ (∀ (P Q : Prop), (P ↔ Q) → P = Q) → ∀ (P Q : Prop), (P ∨ Q) = (Q ∨ P) PE:∀ (P Q : Prop), (P ↔ Q) → P = QP:PropQ:Prop⊢ (P ∨ Q) = (Q ∨ P) PE:∀ (P Q : Prop), (P ↔ Q) → P = QP:PropQ:Prop⊢ P ∨ Q ↔ Q ∨ P All goals completed! 🐙
Exercise★(pe_implies_true_eq) (Advanced)

Prove that if a proposition P is provable, then it is equal to True — as a consequence of propositional extensionality.

theorem pe_implies_true_eq : propositional_extensionality → ∀ (P : Prop), P → True = P := ⊢ propositional_extensionality → ∀ (P : Prop), P → True = P solution! ⊢ (∀ (P Q : Prop), (P ↔ Q) → P = Q) → ∀ (P : Prop), P → True = P PE:∀ (P Q : Prop), (P ↔ Q) → P = QP:Propp:P⊢ True = P PE:∀ (P Q : Prop), (P ↔ Q) → P = QP:Propp:P⊢ True ↔ P PE:∀ (P Q : Prop), (P ↔ Q) → P = QP:Propp:P⊢ True → PPE:∀ (P Q : Prop), (P ↔ Q) → P = QP:Propp:P⊢ P → True PE:∀ (P Q : Prop), (P ↔ Q) → P = QP:Propp:P⊢ True → P PE:∀ (P Q : Prop), (P ↔ Q) → P = QP:Propp:Pa✝:True⊢ P All goals completed! 🐙 PE:∀ (P Q : Prop), (P ↔ Q) → P = QP:Propp:P⊢ P → True PE:∀ (P Q : Prop), (P ↔ Q) → P = QP:Propp:Pa✝:P⊢ True All goals completed! 🐙

Propositional extensionality is about equating two different propositions that happen to be equivalent. A related but distinct notion, proof irrelevance, is instead about equating two different proofs of the same proposition:

def proof_irrelevance : Prop := ∀ (P : Prop) (pf1 pf2 : P), pf1 = pf2

In many proof assistants, proving this fact outright requires an assumption like propositional extensionality: without some axiom to fall back on, two proofs of the same proposition are just two terms, and nothing forces them to be equal. But recall the Dependency, Equivalence, and Proof Irrelevance section earlier in this chapter: Lean's Prop already builds proof irrelevance into its type theory, so that any two proofs of the same proposition are automatically definitionally equal. So proof_irrelevance holds outright here, with no axioms needed at all:

theorem proof_irrelevance_lean : proof_irrelevance := fun _ _ _ => rfl 'EvenProp.proof_irrelevance_lean' does not depend on any axioms#print axioms proof_irrelevance_lean
'EvenProp.proof_irrelevance_lean' does not depend on any axioms

This is one of the ways Lean's type theory is unusual: most other proof assistants either don't have this property by default, or offer it only for a separate, special-purpose kind of proposition that you have to opt into.

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