Dylan Cant
·
2026-10-27
1import Game.LessOrEqual
2
3/-!
4# Advanced Multiplication World
5
6Advanced Addition World proved implications about `+` such as
7`x + y = 0 → x = 0`; ≤ World used them. Here are the same kind of facts for
8`*`, such as `x * y = 1 → x = 1`. Many need a hypothesis `a ≠ 0`, because
9multiplying by `0` makes things smaller. Remember that `a ≠ 0` means
10`a = 0 → False`: `intro` it, or feed it a proof of `a = 0`.
11
12New tactics:
13* `contradiction` closes any goal when the hypotheses contradict each other
14 in plain sight: `h1 : a = 0` and `h2 : a ≠ 0`, or `h : a ≠ a`, or
15 `h : False`. It doesn't see through numerals: for `h : 0 = 1`, write
16 `exact absurd h zero_ne_one` (`absurd : P → ¬P → Q`).
17* `by_cases h : P` splits into two goals, one with `h : P` and one with
18 `h : ¬P`. That's how you reason "either `a = 0` or not" (level 8). Prove
19 the first goal, then the second.
20* `have h : P := by` followed by an indented proof of `P`: prove a fact
21 first, then carry on with `h : P` (Implication World's `have`, with the
22 statement written out and a proof by tactics).
23* `induction b generalizing c with` (level 9): the inductive hypothesis then
24 holds *for all* `c`, not just the one in the goal, so `hd _ h` works for
25 any `c`.
26
27Theorems you'll want, from earlier worlds: `add_mul`, `mul_comm`, `one_mul`,
28`mul_one`, `mul_succ`, `one_ne_zero`, `zero_ne_succ`, `add_right_cancel`,
29`add_left_eq_zero`, `le_one`.
30-/
31
32namespace MyNat
33
34-- Level 1: a warm-up; it works even for `t = 0`.
35theorem mul_le_mul_right (a b t : ℕ) (h : a ≤ b) : a * t ≤ b * t := by
36 sorry
37
38-- Level 2: reduce it to a hypothesis `b = 0` and a goal `a * b = 0`:
39-- start with `intro hb`.
40theorem mul_left_ne_zero (a b : ℕ) (h : a * b ≠ 0) : b ≠ 0 := by
41 sorry
42
43-- Level 3: if `a ≠ 0` then `a` is a successor. Start with `cases a with`;
44-- in the case `a = 0`, `ha : 0 ≠ 0` is a contradiction.
45theorem eq_succ_of_ne_zero (a : ℕ) (ha : a ≠ 0) : ∃ n, a = succ n := by
46 sorry
47
48-- Level 4: use the previous level.
49theorem one_le_of_ne_zero (a : ℕ) (ha : a ≠ 0) : 1 ≤ a := by
50 sorry
51
52-- Level 5: levels 1, 2 and 4.
53theorem le_mul_right (a b : ℕ) (h : a * b ≠ 0) : a ≤ a * b := by
54 sorry
55
56-- Level 6: you want `le_mul_right`, but it needs `x * y ≠ 0`, which you
57-- don't have yet: `have h2 : x * y ≠ 0 := by`.
58theorem mul_right_eq_one (x y : ℕ) (h : x * y = 1) : x = 1 := by
59 sorry
60
61-- Level 7: write both `a` and `b` as successors (level 3).
62theorem mul_ne_zero (a b : ℕ) (ha : a ≠ 0) (hb : b ≠ 0) : a * b ≠ 0 := by
63 sorry
64
65-- Level 8: level 7 plus pure logic: `by_cases ha : a = 0`.
66theorem mul_eq_zero (a b : ℕ) (h : a * b = 0) : a = 0 ∨ b = 0 := by
67 sorry
68
69-- Level 9: start with `induction b generalizing c with`; in the `succ` case,
70-- split `c` too.
71theorem mul_left_cancel (a b c : ℕ) (ha : a ≠ 0) (h : a * b = a * c) : b = c := by
72 sorry
73
74-- Level 10: reduce it to level 9, arguing backwards:
75-- `apply mul_left_cancel a b 1 ha`.
76theorem mul_right_eq_self (a b : ℕ) (ha : a ≠ 0) (h : a * b = a) : b = 1 := by
77 sorry
78
79end MyNat