master lean-101 / Game / MyNat.lean
Dylan Cant  ·  2026-10-27
 1/-!
 2# `MyNat`: the natural numbers of the Natural Number Game
 3
 4A copy of the set-up of NNG4 (https://github.com/leanprover-community/NNG4,
 5`Game/MyNat/`), so the levels can be played in a local editor. As in the game,
 6`+`, `*` and `^` are `opaque` and their defining equations are axioms, so
 7`rfl` cannot evaluate `2 + 2` and every step has to be a rewrite.
 8-/
 9
10/-- Our copy of the natural numbers, with notation `ℕ`. -/
11inductive MyNat where
12  | zero : MyNat
13  | succ : MyNat → MyNat
14
15@[inherit_doc]
16notation (priority := 1000000) "ℕ" => MyNat
17
18attribute [pp_nodot] MyNat.succ
19
20namespace MyNat
21
22instance : Inhabited ℕ := ⟨zero⟩
23
24def ofNat : Nat → ℕ
25  | 0 => zero
26  | n + 1 => succ (ofNat n)
27
28instance instOfNat {n : Nat} : OfNat ℕ n := ⟨ofNat n⟩
29
30theorem zero_eq_0 : zero = 0 := rfl
31
32/-- `induction n with | zero => … | succ d hd => …` shows `0`, not `zero`. -/
33@[elab_as_elim, induction_eliminator]
34def rec' {motive : ℕ → Sort u} (zero : motive 0)
35    (succ : (n : ℕ) → motive n → motive (MyNat.succ n)) : (t : ℕ) → motive t
36  | .zero => zero
37  | .succ n => succ n (rec' zero succ n)
38
39/-- Same for `cases n with | zero => … | succ d => …`. -/
40@[elab_as_elim, cases_eliminator]
41def casesOn' {motive : ℕ → Sort u} (zero : motive 0)
42    (succ : (n : ℕ) → motive (MyNat.succ n)) : (t : ℕ) → motive t
43  | .zero => zero
44  | .succ n => succ n
45
46-- Numerals (Tutorial World, level 3).
47theorem one_eq_succ_zero : (1 : ℕ) = succ 0 := rfl
48theorem two_eq_succ_one : (2 : ℕ) = succ 1 := rfl
49theorem three_eq_succ_two : (3 : ℕ) = succ 2 := rfl
50theorem four_eq_succ_three : (4 : ℕ) = succ 3 := rfl
51
52-- Peano's axioms (Implication World).
53theorem succ_inj (a b : ℕ) (h : succ a = succ b) : a = b := by
54  injection h
55
56theorem zero_ne_succ (a : ℕ) : 0 ≠ succ a := fun h => MyNat.noConfusion h
57
58-- From here on `rfl` cannot unfold numerals either: `1 = succ 0` needs a rewrite.
59attribute [irreducible] ofNat
60
61-- Addition (Tutorial World, levels 5 and 7).
62opaque add : ℕ → ℕ → ℕ
63instance : Add ℕ := ⟨add⟩
64axiom add_zero (a : ℕ) : a + 0 = a
65axiom add_succ (a d : ℕ) : a + succ d = succ (a + d)
66
67-- Multiplication (Multiplication World).
68opaque mul : ℕ → ℕ → ℕ
69instance : Mul ℕ := ⟨mul⟩
70axiom mul_zero (a : ℕ) : a * 0 = 0
71axiom mul_succ (a b : ℕ) : a * succ b = a * b + a
72
73-- Power (Power World).
74opaque pow : ℕ → ℕ → ℕ
75instance : Pow ℕ ℕ := ⟨pow⟩
76-- Without this, the `0` in `m ^ 0` would be elaborated as a `Nat` (as NNG4 does).
77macro_rules | `($x ^ $y) => `(HPow.hPow ($x : MyNat) ($y : MyNat))
78axiom pow_zero (m : ℕ) : m ^ 0 = 1
79axiom pow_succ (m n : ℕ) : m ^ succ n = m ^ n * m
80
81-- Order (≤ World): `a ≤ b` means there is a `c` with `b = a + c`.
82def le (a b : ℕ) := ∃ c : ℕ, b = a + c
83instance : LE ℕ := ⟨le⟩
84
85end MyNat
86