Dylan Cant
·
2026-10-27
1import Game.AdvAddition
2
3/-!
4# ≤ World
5
6`a ≤ b` (type `\le`) is defined as `∃ c, b = a + c`: "there exists a `c`
7such that `b = a + c`" (type `\ex` for `∃`). The definition is `MyNat.le`,
8in `MyNat.lean`.
9
10New tactics:
11* `exists c`: if the goal is `∃ x, P x` (or `a ≤ b`), turns it into `P c`,
12 and closes that if it is trivial. Choose `c` well: the wrong one leaves a
13 goal you can't prove.
14* `cases h` takes apart a hypothesis `h : a ≤ b`:
15 ```
16 cases h with
17 | intro c hc => …
18 ```
19 gives `c : ℕ` and `hc : b = a + c`.
20* `left` and `right` turn a goal `P ∨ Q` (type `\or`) into `P`, or into `Q`.
21* `cases h` on `h : P ∨ Q` makes two goals, one with each:
22 ```
23 cases h with
24 | inl hp => …
25 | inr hq => …
26 ```
27
28`∨` is right associative: `P ∨ Q ∨ R` means `P ∨ (Q ∨ R)` (level 11).
29`rw [h] at hx ⊢` rewrites in `hx` and in the goal at once (level 10).
30-/
31
32namespace MyNat
33
34-- Level 1: start with `exists 0`.
35theorem le_refl (x : ℕ) : x ≤ x := by
36 sorry
37
38-- Level 2: what number will you choose?
39theorem zero_le (x : ℕ) : 0 ≤ x := by
40 sorry
41
42-- Level 3: `succ_eq_add_one` will help.
43theorem le_succ_self (x : ℕ) : x ≤ succ x := by
44 sorry
45
46-- Level 4: take both hypotheses apart with `cases` first.
47theorem le_trans (x y z : ℕ) (hxy : x ≤ y) (hyz : y ≤ z) : x ≤ z := by
48 sorry
49
50-- Level 5: you'll need a result from Advanced Addition World.
51theorem le_zero (x : ℕ) (hx : x ≤ 0) : x = 0 := by
52 sorry
53
54-- Level 6: the trickiest one so far. Take both hypotheses apart; the
55-- results of Advanced Addition World show that one of the `c`s is `0`.
56theorem le_antisymm (x y : ℕ) (hxy : x ≤ y) (hyx : y ≤ x) : x = y := by
57 sorry
58
59-- Level 7: dealing with `or`. Don't go left or right until you know which.
60example (x y : ℕ) (h : x = 37 ∨ y = 42) : y = 42 ∨ x = 37 := by
61 sorry
62
63-- Level 8 (boss): the toughest level yet. Induction on `y`. If `a` is a
64-- number, `cases a with` splits into `a = 0` and `a = succ b`. Don't go left
65-- or right until your hypotheses tell you which way.
66theorem le_total (x y : ℕ) : x ≤ y ∨ y ≤ x := by
67 sorry
68
69-- Level 9: helpful for the last two levels.
70theorem succ_le_succ (x y : ℕ) (hx : succ x ≤ succ y) : x ≤ y := by
71 sorry
72
73-- Level 10: `cases x with`; in the `succ` case, level 9 and level 5.
74theorem le_one (x : ℕ) (hx : x ≤ 1) : x = 0 ∨ x = 1 := by
75 sorry
76
77-- Level 11: the same idea as level 10, one step further.
78theorem le_two (x : ℕ) (hx : x ≤ 2) : x = 0 ∨ x = 1 ∨ x = 2 := by
79 sorry
80
81end MyNat