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.
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:Even0). Instead of
"Even.zero has type Even0," we can say that
"Even.zero is a proof of Even0."
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.
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.
The expression Even.succ_succ2(Even.succ_succ0Even.zero) instantiates the
parameterized constructor Even.succ_succ with the specific arguments 2
and 0 plus the corresponding proof objects for its premises Even2 and Even0. 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:
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_proofsectionShowProofopenLeanElabTacticMeta/-- Like `instantiateMVars`, but also substitutes holes
whose assignment Lean delays until they are complete
(e.g., the body under an `intro`). -/partialdefinstantiatePartial(e:Expr):MetaMExpr:=dolete←instantiateMVarsetransforme(pre:=fune=>dolet.mvarm:=e.getAppFn|return.continueletsomed←getDelayedMVarAssignment?m|return.continueletv←instantiatePartial(mkMVard.mvarIdPending)letargs:=e.getAppArgsletn:=d.fvars.sizeletv:=(v.abstractd.fvars).instantiateRevRange0nargsreturn.done(mkAppNvargs[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=>doletroot←getMainGoallets:=seq.raw[0]lettacs:=ifs.getKind==``Parser.Tactic.tacticSeqBracketedthens[1].getSepArgselses[0].getSepArgsletrender:TacticMFormat:=dolete←instantiatePartial(mkMVarroot)withOptions(funo=>(o.setBool`pp.mvarsfalse).setBool`pp.fieldNotationfalse)(ppExpre)letmutout←renderfortintacsdoevalTactictlettac←PrettyPrinter.ppTactic⟨t⟩out:=out++.line++.line++f!"after {tac}:"++.nest2(.line++(←render))logInfom!"{out}"endShowProoftheoremeven_4'':Even4:=⊢ Even4?_
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⊢ Even2⊢ Even0All 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.
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!
What is the proof object corresponding to even_plus4?
We're looking for an expression whose type is ∀(n:Nat),Evenn→Even(n+4) — that is, a function that takes two arguments (one
number and a piece of evidence) and returns a piece of evidence!
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:
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:
defeven_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]_ENote: This linter can be disabled with `set_option linter.unusedVariables false`E:Evenn),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:
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:
theoremeven_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]_hevenNote: This linter can be disabled with `set_option linter.unusedVariables false`heven:Evenn),Even(n+2):=⊢ ∀(n:Nat),Evenn→Even(n+2)n:Nath:Evenn⊢ Even(n+2);n:Nath:Evenn⊢ Evenn;All goals completed! 🐙
And we will also put the names before the :, which saves needing to
use intro:
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:
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."
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!
defadd2: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_proofn:Nat⊢ Natn:Nat⊢ Natn:Nat⊢ NatAll 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)
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.
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 propositionNat→Nattheoremadd2_with_theorem_wrong:Nat→Nat:=⊢ Nat→NatAll goals completed! 🐙
type of theorem `EvenProp.add2_with_theorem_wrong` is not a propositionNat→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 termsorry 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.
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.
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:
rfl: The termrfl is used very often as a full proof instead of
by rfl (which references the tacticrfl of the same name)
and is even preferred in Lean's Mathlib, which writes its
@[simp] definitional lemmas this way.
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!
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.
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.
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(ab:Prop):Propnumber of parameters: 2fields:_root_.And.left : a_root_.And.right : bconstructor:_root_.And.intro{ab:Prop}(left:a)(right:b):a∧b#print_root_.And
structure_root_.And(ab:Prop):Propnumber of parameters: 2fields:_root_.And.left : a_root_.And.right : bconstructor:_root_.And.intro{ab: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.
structureMyProd(αβ:Type):Typenumber of parameters: 2fields:MyProd.fst : αMyProd.snd : βconstructor:MyProd.mk{αβ:Type}(fst:α)(snd:β):MyProdαβ#printMyProd
structureMyProd(αβ:Type):Typenumber of parameters: 2fields: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:
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.
theoreminj_l:∀(PQ:Prop),P→OrPQ:=fun__hp=>Or.inlhptheoreminj_l'(PQ:Prop)(hp:P):OrPQ:=P:PropQ:Prophp:P⊢ OrPQ?_
after left:
Or.inl ?_
after exact hp:
Or.inl hpshow_proofP:PropQ:Prophp:P⊢ PAll goals completed! 🐙
?_
after left:
Or.inl ?_
after exact hp:
Or.inl hp
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,Evenx desugars to an expression
involving Exists:
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 existsw?
False is equally simple — indeed, so simple it may look
syntactically wrong at first glance!
inductiveFalse: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.
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.
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.
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.
The rfl tactic that we have used to prove
equalities of the form x = y up to now is
essentially just shorthand for applyEq.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:
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.
theoremeq_add:∀(n1n2:Nat),n1='n2→(n1+1)='(n2+1):=funn1Variable 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]_n2Note: This linter can be disabled with `set_option linter.unusedVariables false`n2heq=>matchheqwith|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(n1n2:Nat)(heq:n1='n2):(n1+1)='(n2+1):=n1:Natn2:Natheq:n1='n2⊢ n1+1='n2+1n1:Natn2:Natheq:n1='n2⊢ n1+1='n2+1-- doesn't work for _our_ =' relationexample(n1:Nat):(n1+1)='(n1+1):=byn1:Nat⊢ n1+1='n1+1Tactic `rfl` failed: No `[refl]` lemma registered for relationEqHint: Add the `[refl]` attribute to reflexivity lemmas for `Eq` to use this tacticn1:Nat⊢ n1+1='n1+1rfln1:Nat⊢ n1+1='n1+1-- doesn't work for _our_ =' relationtheoremeq_add'(n1n2:Nat)(heq:n1='n2):(n1+1)='(n2+1):=byn1:Natn2:Natheq:n1='n2⊢ n1+1='n2+1casesheqrefln1:Nat⊢ n1+1='n1+1-- n2 replaced by n1 in the goal!applyEq.reflAll goals completed! 🐙
Exercise★★(eq_cons)
Construct the proof object for the following theorem. Use pattern
matching on the equality hypotheses.
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.
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.
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...
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
theoremquiz1:∃x,x+3='4:=Type mismatchEq.refl4has type4='4but is expected to have type∃x,x+3='4Eq.refl4theoremquiz2:∃x,x+3='4:=@Exists.introNat(Unknown identifier `z`z+3='4)1(Eq.refl4)theoremquiz3:∃x,x+3='4:=@Exists.introNat(funz=>z+3='4)1(Eq.refl4)theoremquiz4:∃x,x+3='4:=@Exists.introNat(funz=>z+3='4)1Application type mismatch: The argumentEq.refl1has type1='1but is expected to have type1+3='4in the applicationExists.intro1(Eq.refl1)(Eq.refl1)
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:
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.
definfinite_loop{α:Type}(n:Nat):α:=infinite_loopncannot use specified measure for structural recursion:it is unchanged in the recursive callstermination_bystructuralntheoremfalso:False:=Type mismatchinfinite_loop0has type?m.1of sort `Type` but is expected to have typeFalseof sort `Prop`infinite_loop0
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.
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:defpropositional_extensionality:Prop:=∀(PQ:Prop),(P↔Q)→P=Q-- Lean calls it `propext`:propext{ab:Prop}:(a↔b)→a=b#checkpropext
propext{ab: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.
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:
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:
theoremproof_irrelevance_lean:proof_irrelevance:=fun___=>rfl'EvenProp.proof_irrelevance_lean' does not depend on any axioms#printaxiomsproof_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