Let Lean do the calculating for you
After finishing this section, you will be able to use four effort-saving tactics and know which one to try first.
| Tactic | What it does | When to think of it |
|---|---|---|
rw [h] | Uses an equality h to replace the left side with the right side in the goal | You have an equality in hand, and its left side happens to appear in the goal |
simp | Repeatedly rewrites using a set of known simplification rules | The goal looks "obvious" and is just wordy |
omega | Proves addition, subtraction, and comparisons over natural numbers and integers | The goal is arithmetic involving +, <, ≤ |
decide | Directly computes the truth value of a concrete proposition | The goal contains only concrete numbers, with no variables |
What you'll be able to do after this section
- Perform an equality substitution with
rw - Use
#checkto look up what an existing theorem says - Decide whether a goal should go to
simp,omega, ordecide
Step 1: rw, rewriting with equalities
You have h : a = b in hand, and a appears in the goal. rw [h] replaces every a in the goal with b:
example (a b : Nat) (h : a = b) : a + 1 = b + 1 := by
rw [h]After the rewrite, the goal becomes b + 1 = b + 1; both sides are the same, and rw finishes the proof right away.
rw can also use existing theorems. Lean ships with many; first use #check to see what one says:
#check Nat.add_commYou should see:
Nat.add_comm (n m : Nat) : n + m = m + nAddition is commutative. Use it to rewrite:
example (a b : Nat) : a + b = b + a := by
rw [Nat.add_comm]- I know
rw [h]replaces the left side ofhwith the right side
Step 2: simp, automatic simplification
Many facts are already marked as simplification rules, such as "appending an empty list to a list gives back the same list." simp will find and use them on its own:
example (xs : List Nat) : (xs ++ []).length = xs.length := by
simpTo make it use a few extra rules or definitions, put them inside square brackets: simp [某个定义, 某条定理]. The following sections will keep using it this way.
- I know to try
simpfirst when the goal is "obvious but wordy"
Step 3: omega, linear arithmetic
Hand addition, subtraction, and size comparisons involving variables to omega:
example (a b : Nat) (h : a < b) : a + 1 ≤ b := by
omegaIt will use the hypotheses you have in hand, such as h. But it only understands addition, subtraction, and comparisons—multiplying two variables is out of its jurisdiction.
- I know
omegahandles addition, subtraction, and comparisons over natural numbers and integers
Step 4: decide, direct computation
When the proposition contains only concrete numbers, let Lean compute the truth value:
example : 17 * 3 = 51 := by
decideIt won't work with variables—Lean cannot check "all n" one by one. That is exactly what induction, the topic of the next chapter, is meant to solve.
- I know
decideis only suitable for concrete propositions without variables
Quiz timeGoal是 x + 2 > x, where x is an arbitrary natural number. Which tactic do you try first?
Checkpoint
- I can say what each of the four tactics is good at
- I can use
#checkto look up the content of a theorem - I know the direction of
rw [h]is left to right - I know the division of labor between
decideandomega: no variables vs. variables
Didn't work?
**rw reports it can't find anything to rewrite. ** The left side of the equality doesn't appear in the goal. Check the direction of the equality; to use it the other way around, write rw [← h], typing the arrow with \l.
**simp didn't finish the proof. ** It only simplifies; whatever remains of the goal is left to you. Take a look at what's left, then decide on the next step.
Next section
These tactics only handle cases that "can be seen at a glance." To prove that something holds for all natural numbers, you need induction.