master lean-101 / Game / Algorithm.lean
Dylan Cant  ·  2026-10-27
  1import Game.AdvMultiplication
  2
  3/-!
  4# Algorithm World
  5
  6Proofs like `2 + 2 = 4` and `a + b + c + d + e = e + d + c + b + a` are
  7tedious by hand. Here the computer does them: `simp only` for rearranging
  8sums (levels 1-4), and `decide` for equalities of numerals (levels 5-9). On
  9the way you prove two of Peano's axioms, `succ_inj` and `succ_ne_zero`, that
 10`MyNat.lean` gave you for free. It's the last world.
 11
 12New tactics:
 13* `simp only [h₁, h₂]` rewrites with `h₁` and `h₂` everywhere, as often as
 14  it can, and closes the goal with `rfl` if it can. Unlike `rw`, it can use
 15  `add_comm` without looping: it only swaps terms into a fixed internal
 16  order. Level 3.
 17* `macro "name" : tactic => …` makes a new tactic out of old ones. Level 4
 18  shows one.
 19* `trivial` closes the goal `True` (level 6).
 20* `decide` runs an algorithm (a `Decidable` instance) that answers the goal
 21  `P` with yes or no, and closes it on a yes. Levels 8-9.
 22
 23Some definitions are made right before the level that uses them, in plain
 24sight: `pred`, `is_zero`, the algorithm `instDecidableEq`, and `ofNat_succ`.
 25-/
 26
 27namespace MyNat
 28
 29-- Level 1: by hand, for the last time:
 30-- `add_assoc` and a targeted `add_comm a b`. Remember that `a + b + c`
 31-- means `(a + b) + c`.
 32theorem add_left_comm (a b c : ℕ) : a + (b + c) = b + (a + c) := by
 33  sorry
 34
 35-- Level 2: forget the brackets and think about the order of the variables.
 36-- `repeat rw [add_assoc]` pushes all the brackets to the right; then
 37-- `add_left_comm b c` swaps `b` and `c`, and `add_comm b d` swaps `b` and `d`.
 38example (a b c d : ℕ) : a + b + (c + d) = a + c + d + b := by
 39  sorry
 40
 41-- Level 3: not one to do by hand. One line: `simp only [add_left_comm, add_comm]`.
 42example (a b c d e f g h : ℕ) :
 43    (d + f) + (h + (a + c)) + (g + e + b) = a + b + c + d + e + f + g + h := by
 44  sorry
 45
 46-- Level 4: your own tactic. This line makes `simp_add` run the `simp only`
 47-- call between the brackets. Solve the level with it.
 48macro "simp_add" : tactic => `(tactic|(
 49  simp only [add_assoc, add_left_comm, add_comm]))
 50
 51example (a b c d e f g h : ℕ) :
 52    (d + f) + (h + (a + c)) + (g + e + b) = a + b + c + d + e + f + g + h := by
 53  sorry
 54
 55-- Level 5: `pred` tries to subtract 1. It can't from `0`, so it returns a
 56-- junk value. Defined by recursion: what it does on `0` and on `succ n`.
 57def pred : ℕ → ℕ
 58  | zero => 37
 59  | succ n => n
 60
 61theorem pred_succ (n : ℕ) : pred (succ n) = n := rfl
 62
 63-- Now prove Peano's `succ_inj`, without `succ_inj` itself or `injection`.
 64-- Start with `rw [← pred_succ a]`.
 65example (a b : ℕ) (h : succ a = succ b) : a = b := by
 66  sorry
 67
 68-- Level 6: `is_zero n` is the statement `True` when `n = 0` and `False`
 69-- otherwise.
 70def is_zero : ℕ → Prop
 71  | zero => True
 72  | succ _ => False
 73
 74theorem is_zero_zero : is_zero 0 = True := by
 75  rw [← zero_eq_0]
 76  rfl
 77
 78theorem is_zero_succ (n : ℕ) : is_zero (succ n) = False := rfl
 79
 80-- Prove Peano's last axiom without `zero_ne_succ`. After `intro h`, the
 81-- goal is `False`: `rw [← is_zero_succ a]` turns it into `is_zero (succ a)`.
 82-- Turn it into `True`, then `trivial`.
 83theorem succ_ne_zero (a : ℕ) : succ a ≠ 0 := by
 84  sorry
 85
 86-- Level 7: an algorithm for "does `a = b`?": if both are `0`, yes; if one is
 87-- `0` and the other a successor, no; for `succ m` and `succ n`, ask whether
 88-- `m = n`. `rfl`, `zero_ne_succ` and `succ_ne_zero` show the first answers
 89-- are right. This level is the last case: if `m ≠ n` then
 90-- `succ m ≠ succ n`. Start with `intro h'`: the goal becomes `False`, and
 91-- `apply h` turns it into `m = n`, with `h' : succ m = succ n` to prove it.
 92theorem succ_ne_succ (m n : ℕ) (h : m ≠ n) : succ m ≠ succ n := by
 93  sorry
 94
 95-- The algorithm, with the proof that each answer is right. `isTrue p` is
 96-- "yes, and `p` proves it"; `isFalse p` is "no, and `p` proves that".
 97-- `rw [zero_eq_0]` because the statements say `0` and the patterns `zero`.
 98instance instDecidableEq : DecidableEq ℕ
 99  | zero, zero => isTrue rfl
100  | succ m, zero => isFalse (by rw [zero_eq_0]; exact succ_ne_zero m)
101  | zero, succ n => isFalse (by rw [zero_eq_0]; exact zero_ne_succ n)
102  | succ m, succ n =>
103    match instDecidableEq m n with
104    | isTrue h => isTrue (by rw [h])
105    | isFalse h => isFalse (succ_ne_succ m n h)
106
107-- A numeral is a successor: `(n + 1 : ℕ) = succ n`, for a numeral `n`.
108-- `MyNat.lean` seals the numerals (`irreducible`) so that `rfl` can't see
109-- through them; `with_unfolding_all` breaks the seal for this one proof.
110theorem ofNat_succ (n : Nat) : (OfNat.ofNat (n + 1) : ℕ) = succ (OfNat.ofNat n) := by
111  with_unfolding_all rfl
112
113-- Level 8: `20 + 20 = 40`. `decide` can't run `+` (it's an axiom here, not
114-- an algorithm), so first unfold everything into `succ`s:
115-- `simp only [ofNat_succ, add_succ, add_zero]`. On an equation that's
116-- already the end: both sides become the same 40 `succ`s, and `simp` closes
117-- the goal with `rfl`.
118example : (20 : ℕ) + 20 = 40 := by
119  sorry
120
121-- Level 9: `2 + 2 ≠ 5`, a nicer proof than in Implication World. The same
122-- `simp only` first; `rfl` can't prove a `≠`, so then `decide`. Plain
123-- `decide` gets stuck at `OfNat.ofNat 0`, the sealed numeral `0`:
124-- `decide +kernel` checks with Lean's kernel, which ignores seals (or
125-- `rw [← zero_eq_0]` first, then `decide`).
126example : (2 : ℕ) + 2 ≠ 5 := by
127  sorry
128
129end MyNat