If... then...
After finishing this section, you will be able to prove propositions like "if p then r" and understand the goal state Lean shows you at every step.
Using only three tactics: intro, apply, exact.
What you'll be able to do after this section
- Read the goal state: what's above the line is what you have, and what follows
⊢is what you need to prove - Use
exactto hand over a ready-made proof - Work backward with
apply, take in a hypothesis withintro
First, learn to read the goal state
While writing a proof, Lean tells you your current situation at all times. For example:
p q : Prop
hp : p
hpq : p → q
⊢ qp q : Prop: p and q are two propositions, which can be any statement.hp : p: you have in hand a proof that p holds, namedhp.hpq : p → q: you have in hand a proof of "if p then q", namedhpq.⊢ q: what needs to be proved is q.
Everything above ⊢ is available for you to use; it's called a hypothesis. What comes after ⊢ is the goal. In VS Code, place the cursor on a line of the proof, and the Lean Infoview panel on the right shows the state before that line.
Step 1: exact, when you already have it in hand
The goal is p, and you happen to have a proof of p in hand—just hand it over:
example (p : Prop) (hp : p) : p := by
exact hpYou should see: no errors.
What happens if you hand over the wrong thing? You have p in hand, but the goal is q:
example (p q : Prop) (hp : p) : q := by
exact hpYou should see:
Type mismatch
hp
has type
p
but is expected to have type
qThis is the error you'll see most often going forward. It says: you provided a proof of p, but a proof of q is required here.
- I know that
exactrequires what I give to match the goal exactly
Step 2: apply, working backward
The goal is q, and you have hpq : p → q in hand. It says "if we have p, then we have q". So it suffices to prove p:
example (p q : Prop) (hp : p) (hpq : p → q) : q := by
apply hpq
exact hpAfter apply hpq, the goal changes from q to p. This is working backward: I want q—who can give me q? hpq can, but it first needs to obtain p. So the problem becomes proving p.
- I know that
applyreplaces the goal with "what's still needed to use this rule"
Step 3: intro, taking in the "if"
When the goal itself is "if p then q", first assume p holds, then prove q. That's exactly what intro does:
example (p : Prop) : p → p := by
intro hp
exact hpintro hp moves the first half of the goal p → p up above the line, turning it into the hypothesis hp : p, leaving only the second half, p, as the goal. The name hp is chosen by you.
- I know that when the goal is
A → B, the first step is usuallyintro
Hands-on: chaining two rules together
Use all three tactics together once. Given "if we have p, then we have q" and "if we have q, then we have r", prove "if we have p, then we have r".
theorem imp_chain (p q r : Prop) (hpq : p → q) (hqr : q → r) : p → r := by
intro hp
apply hqr
apply hpq
exact hp
The proof from the exercise, written as code, looks like this:
theorem imp_chain (p q r : Prop) (hpq : p → q) (hqr : q → r) : p → r := by
intro hp
apply hqr
apply hpq
exact hpNote the order: first apply hqr, then apply hpq. Because we're working backward—the goal is r, and the rule closest to r is hqr.
Checkpoint
- Given a goal state, I can point out which items are hypotheses and which one is the goal
- I can explain when to use
exact,apply, andintrorespectively - I completed
imp_chainin the exercise - I can understand what the
Type mismatcherror is saying
Didn't work?
After apply, the goal didn't turn into what I expected. apply only checks whether the last part of the rule matches the goal. hpq : p → q can only be used when the goal is q.
intro reports an error. When the goal isn't in the shape of "if... then...", there's nothing to take in. First take a look at what follows ⊢.
Next section
Propositions aren't just "if... then..."—there are also "and" and "or". In the next section you'll learn how to take them apart and how to build them.