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