master lean-101 / Game / Multiplication.lean
Dylan Cant  ·  2026-10-27
 1import Game.Addition
 2
 3/-!
 4# Multiplication World
 5
 6Multiplication is defined like addition, by what it does to `0` and `succ d`:
 7* `mul_zero a : a * 0 = 0`
 8* `mul_succ a d : a * succ d = a * d + a`
 9
10Everything else about `*` is proved from these two, by rewriting and
11induction. The Addition World theorems (`zero_add`, `succ_add`, `add_comm`,
12`add_assoc`, `add_right_comm`) and the numerals (`one_eq_succ_zero`,
13`two_eq_succ_one`, …) are all available. `repeat rw [h]` rewrites with `h`
14until it no longer applies.
15-/
16
17namespace MyNat
18
19-- Level 1: a warm-up, no induction needed, because `1` is a successor.
20theorem mul_one (m : ℕ) : m * 1 = m := by
21  sorry
22
23-- Level 2: the zero case of `mul_comm` will need this.
24theorem zero_mul (m : ℕ) : 0 * m = 0 := by
25  sorry
26
27-- Level 3: the last level of Addition World might help.
28theorem succ_mul (a b : ℕ) : succ a * b = a * b + b := by
29  sorry
30
31-- Level 4: the first sub-boss.
32theorem mul_comm (a b : ℕ) : a * b = b * a := by
33  sorry
34
35-- Level 5: by induction, with `succ_mul`, or with commutativity.
36-- Which is quickest?
37theorem one_mul (m : ℕ) : 1 * m = m := by
38  sorry
39
40-- Level 6: more useful than it looks (a later boss needs it).
41theorem two_mul (m : ℕ) : 2 * m = m + m := by
42  sorry
43
44-- Level 7: left distributivity. Some variables are harder to induct on
45-- than others.
46theorem mul_add (a b c : ℕ) : a * (b + c) = a * b + a * c := by
47  sorry
48
49-- Level 8: just as fiddly by induction, but there is a trick that avoids it.
50theorem add_mul (a b c : ℕ) : (a + b) * c = a * c + b * c := by
51  sorry
52
53-- Level 9: the boss. `a * b * c` means `(a * b) * c`.
54theorem mul_assoc (a b c : ℕ) : a * b * c = a * (b * c) := by
55  sorry
56
57end MyNat