master lean-101 / Game / LessOrEqual.lean
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