master lean-101 / Game / AdvAddition.lean
Dylan Cant  ·  2026-10-27
 1import Game.Implication
 2
 3/-!
 4# Advanced Addition World
 5
 6From here on you are mostly on your own. Each level is a theorem that the
 7next ones (and ≤ World) use.
 8
 9One new tactic, in level 5: `cases`. It splits a number into the ways it
10can be built, `0` or `succ d`, without the inductive hypothesis that
11`induction` gives:
12```
13cases b with
14| zero => …
15| succ d => …
16```
17And if `h : False`, then `cases h` closes the goal: there are no ways to
18build a proof of `False`.
19
20Tactics from earlier worlds that help here: `intro`, `apply`, `have`,
21`symm at h`, `repeat`, and arguments to choose what `rw` rewrites.
22-/
23
24namespace MyNat
25
26-- Level 1: induction on `n`. In the `succ` case, `intro h` and rewrite `h`
27-- until `succ_inj` applies to it.
28theorem add_right_cancel (a b n : ℕ) : a + n = b + n → a = b := by
29  sorry
30
31-- Level 2: induction on `n`, or deduce it from level 1.
32theorem add_left_cancel (a b n : ℕ) : n + a = n + b → a = b := by
33  sorry
34
35-- Level 3: `y` is `0 + y`. After `intro h`, argue backwards:
36-- `apply add_right_cancel x 0 y`.
37theorem add_left_eq_self (x y : ℕ) : x + y = y → x = 0 := by
38  sorry
39
40-- Level 4: two ways spring to mind: mimic level 3, or use it.
41theorem add_right_eq_self (x y : ℕ) : x + y = x → y = 0 := by
42  sorry
43
44-- Level 5: start with `cases b with`. In the `succ` case, rewrite the
45-- hypothesis into `0 = succ _`. Then `zero_ne_succ` turns it into a proof of
46-- `False` (`have f := …`), and `cases f` closes the goal.
47theorem add_right_eq_zero (a b : ℕ) : a + b = 0 → a = 0 := by
48  sorry
49
50-- Level 6: mimic level 5, or use it.
51theorem add_left_eq_zero (a b : ℕ) : a + b = 0 → b = 0 := by
52  sorry
53
54end MyNat