import LF.Basics import LF.Induction import LF.SFLCompat -- USING LEAN! -- ## More Powerful Natural Numbers -- Until now, we have been working with our own custom natural numbers, using -- the `Nat` type that we defined in Basics -- in the NatPlayground.Nat namespace. example : 3 * 3 = 9 := by rfl example (n m : Nat) (h : n = m) : n = m := by -- `rfl` will not work here! -- First rewrite the goal with `h`; then the two sides are identical. rewrite [h] rfl -- The same proof can be written more compactly with `rw`. In this example, -- `rw [h]` rewrites with `h` and then closes the resulting reflexive goal. -- Same theorem, written different ways: example (n m : Nat) (h : n = m) : n = m := by rw [h] example (n m : Nat) : n = m → n = m := by intro h rw [h] example : ∀ n m : Nat, n = m → n = m := by intro n m intro h rw [h] example : ∀ n m : Nat, n = m → n = m := by intro n m h rw [h] -- ## Using the Standard Library -- As part of using Lean's standard `Nat` type, we will also begin using -- theorems about `Nat`s from the standard library. Because we did not write -- or prove these theorems ourselves, however, we may not know all the -- available theorems off the top of our heads. -- Lean provides a few ways to search through the standard library to find -- theorems that may be useful during a particular proof. The first such way -- is the `exact?` tactic. This tactic searches the standard library for a -- theorem that can be applied, along with the hypotheses in the context, to -- exactly close the current goal. example (n m : Nat) : n + m = m + n := by exact Nat.add_comm n m -- The `rw?` tactic works like `exact?`, except that it searches for any -- theorems that you could use to rewrite the current goal. example (n m : Nat) : n + m = m + n := by rw [Nat.add_comm] -- Prove the following theorems about `Nat`s. You should not need induction -- for any of these; you can find the theorems you need using `rw?` and -- `exact?`. theorem mul_three (n : Nat) : 3 * n = n + n + n := by rw [Nat.add_one_mul] rw [Nat.two_mul] theorem mul_three_beq (n : Nat) : (3 * n == n + n + n) = true := by rw [mul_three] rw [Nat.beq_eq_true_eq] -- ## Definitional Simplification: `dsimp` -- Often, rather than rewriting by a known equation like -- `n + succ m = succ (n + m)` using `rw [add_succ]`, we just want to simplify -- the function (here `Nat.add`) automatically when we can. -- The `dsimp` tactic ("definitionally simplify") unfolds definitions and -- performs definitional simplifications. You can give it hints in square -- brackets: `dsimp [f]` tells it to unfold the definition of `f`. You can -- also simplify a hypothesis `h` in the context by writing -- `dsimp [...] at h`. `dsimp` will also close goals by `rfl` when possible. def square (n : Nat) : Nat := n * n def triple (n : Nat) : Nat := n + n + n -- When the goal depends on a fact about an unknown value, `rfl` fails. Here, -- `dsimp` makes progress, exposing a goal the fact can close. example (n m : Nat) (h : n + n = m) : triple n = m + n := by -- rfl will not work here! dsimp [triple] -- The goal can now be rewritten by `h`. rw [h] -- As we have seen, `rw` can also unfold definitions. In this example, either -- style is fine: use `dsimp [triple]` when you want to emphasize definitional -- simplification, or `rw [triple, h]` when the proof is just a sequence of -- rewrites. example (n m : Nat) (h : n + n = m) : triple n = m + n := by -- `rw [triple]` unfolds `triple n`. rw [triple, h] -- ### Exercise (2 stars): dsimp1 ⭐⭐ -- Complete this proof, using `dsimp` or `rw` as appropriate. example (n m : Nat) (h : m = n) : triple m = n + (n + n) := by dsimp [triple] rw [h] rw [Nat.add_assoc] -- `dsimp at h` also works on hypotheses, which `rfl` can't touch. example (n : Nat) (h : square n = 16) : n * n = 16 := by dsimp [square] at h exact h -- Like `rw` and `exact`, `dsimp` also has a `?` version that searches for -- functions to simplify by. Many Lean tactics have `?` versions; try it out -- if you are unsure. -- USING LEAN END