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