master lean-101 / Game / Addition.lean
Dylan Cant  ·  2026-10-27
 1import Game.Tutorial
 2
 3/-!
 4# Addition World
 5
 6New tactic: induction. To prove a statement for every `n`, prove it for `0`,
 7then prove that if it holds for `d`, it holds for `succ d`:
 8```
 9induction n with
10| zero => …
11| succ d hd => …
12```
13In the `zero` case the goal is the statement for `0`. In the `succ` case,
14`hd` is the statement for `d` and the goal is the statement for `succ d`.
15The tactics for each case follow its `=>`, on the same line or on the next
16lines, indented further than the `|`.
17
18Each theorem here can be used in the later levels, as can `succ_eq_add_one`
19from Tutorial World.
20-/
21
22namespace MyNat
23
24-- Level 1: induction on `n`. In the `succ` case, rewrite until you can use
25-- `hd`.
26theorem zero_add (n : ℕ) : 0 + n = n := by
27  sorry
28
29-- Level 2: induction on `b`.
30theorem succ_add (a b : ℕ) : succ a + b = succ (a + b) := by
31  sorry
32
33-- Level 3: induction on `b`. Levels 1 and 2 will help.
34theorem add_comm (a b : ℕ) : a + b = b + a := by
35  sorry
36
37-- Level 4: induction on `c`.
38theorem add_assoc (a b c : ℕ) : a + b + c = a + (b + c) := by
39  sorry
40
41-- Level 5: no induction needed. Use `add_assoc`, and `add_comm` with
42-- arguments (`add_comm b c`) so that it swaps the right sum.
43theorem add_right_comm (a b c : ℕ) : a + b + c = a + c + b := by
44  sorry
45
46end MyNat