master lean-101 / Game / Implication.lean
Dylan Cant  ·  2026-10-27
 1import Game.Power
 2
 3/-!
 4# Implication World
 5
 6Theorems of the form "if P then Q", written `P → Q` (type `\to` for `→`).
 7New tactics:
 8* `exact h` closes a goal that is exactly the hypothesis `h`.
 9* `rw [t] at h` rewrites in the hypothesis `h` instead of the goal.
10* `apply t`: if `t : P → Q` and the goal is `Q`, the goal becomes `P`
11  (arguing backwards: to prove `Q`, it is enough to prove `P`).
12* `intro h`: if the goal is `P → Q`, assumes `h : P` and leaves the goal `Q`.
13* `have h2 := t`: adds the fact `t` as a new hypothesis `h2`.
14* `symm` turns a goal `x = y` into `y = x` (and `x ≠ y` into `y ≠ x`);
15  `symm at h` does the same to `h`.
16* `repeat t` runs the tactic `t` until it fails.
17
18To argue forwards instead: if `t : P → Q` and `h : P`, then `t h` is a
19proof of `Q`. Use it with `exact t h`, or keep it with `have h2 := t h`.
20Theorems with arguments take them first: `succ_inj a b h`, or
21`succ_inj _ _ h` to let Lean work out `a` and `b` from `h`.
22
23New theorems (Peano's axioms, in `MyNat.lean`):
24* `succ_inj a b : succ a = succ b → a = b`
25* `zero_ne_succ a : 0 ≠ succ a`
26
27`a ≠ b` is notation for `a = b → False`, so treat it as an implication.
28-/
29
30namespace MyNat
31
32-- Level 1: `exact`.
33example (x y z : ℕ) (h1 : x + y = 37) (h2 : 3 * x + z = 42) : x + y = 37 := by
34  sorry
35
36-- Level 2: if the goal is not exactly a hypothesis, rewrite until it is
37-- (`rw [zero_add] at h`).
38example (x y : ℕ) (h : 0 + x = 0 + y + 2) : x = y + 2 := by
39  sorry
40
41-- Level 3: the hypothesis `h2` is an implication. Argue backwards with
42-- `apply h2`, or forwards with `exact h2 h1`.
43example (x y : ℕ) (h1 : x = 37) (h2 : x = 37 → y = 42) : y = 42 := by
44  sorry
45
46-- Level 4: `succ_inj`, forwards. Manipulate `h` until it is the goal: make
47-- both sides successors (`four_eq_succ_three`, `succ_eq_add_one`), then
48-- `exact succ_inj _ _ h`.
49example (x : ℕ) (h : x + 1 = 4) : x = 3 := by
50  sorry
51
52-- Level 5: the same, arguing backwards: start with `apply succ_inj` and
53-- manipulate the goal until it is `h`.
54example (x : ℕ) (h : x + 1 = 4) : x = 3 := by
55  sorry
56
57-- Level 6: `intro`. The goal itself is an implication.
58example (x : ℕ) : x = 37 → x = 37 := by
59  sorry
60
61-- Level 7: `intro` practice. `repeat rw [...] at h` rewrites every match.
62example (x y : ℕ) : x + 1 = y + 1 → x = y := by
63  sorry
64
65-- Level 8: `≠`. The goal `False` can only follow from contradictory
66-- hypotheses, and these are: `h2 : x ≠ y` means `x = y → False`.
67example (x y : ℕ) (h1 : x = y) (h2 : x ≠ y) : False := by
68  sorry
69
70-- Level 9: `zero_ne_succ`. After `intro h`, the goal is `False`, and
71-- `zero_ne_succ 0 h` proves it once `h` says `0 = succ 0`:
72-- `rw [one_eq_succ_zero] at h` first.
73theorem zero_ne_one : (0 : ℕ) ≠ 1 := by
74  sorry
75
76-- Level 10: `symm`. Use level 9.
77theorem one_ne_zero : (1 : ℕ) ≠ 0 := by
78  sorry
79
80-- Level 11: 2 + 2 ≠ 5, with the numerals already unfolded. Use `add_succ`,
81-- `succ_inj` and `zero_ne_succ`.
82example : succ (succ 0) + succ (succ 0) ≠ succ (succ (succ (succ (succ 0)))) := by
83  sorry
84
85end MyNat