Commit 4611fb3

Dylan Cant  ·  2026-10-27 02:34:50 +0000 UTC
parent 4611fb3
fork of the natural numbers game
19 files changed,  +1350, -0
+2, -0
......@@ -0,0 +1,2 @@
1+/.lake
2+*.pdf
+10, -0
......@@ -0,0 +1,10 @@
1+import Game.MyNat
2+import Game.Tutorial
3+import Game.Addition
4+import Game.Multiplication
5+import Game.Power
6+import Game.Implication
7+import Game.AdvAddition
8+import Game.LessOrEqual
9+import Game.AdvMultiplication
10+import Game.Algorithm
+46, -0
......@@ -0,0 +1,46 @@
1+import Game.Tutorial
2+
3+/-!
4+# Addition World
5+
6+New tactic: induction. To prove a statement for every `n`, prove it for `0`,
7+then prove that if it holds for `d`, it holds for `succ d`:
8+```
9+induction n with
10+| zero => …
11+| succ d hd => …
12+```
13+In the `zero` case the goal is the statement for `0`. In the `succ` case,
14+`hd` is the statement for `d` and the goal is the statement for `succ d`.
15+The tactics for each case follow its `=>`, on the same line or on the next
16+lines, indented further than the `|`.
17+
18+Each theorem here can be used in the later levels, as can `succ_eq_add_one`
19+from Tutorial World.
20+-/
21+
22+namespace MyNat
23+
24+-- Level 1: induction on `n`. In the `succ` case, rewrite until you can use
25+-- `hd`.
26+theorem zero_add (n : ℕ) : 0 + n = n := by
27+ sorry
28+
29+-- Level 2: induction on `b`.
30+theorem succ_add (a b : ℕ) : succ a + b = succ (a + b) := by
31+ sorry
32+
33+-- Level 3: induction on `b`. Levels 1 and 2 will help.
34+theorem add_comm (a b : ℕ) : a + b = b + a := by
35+ sorry
36+
37+-- Level 4: induction on `c`.
38+theorem add_assoc (a b c : ℕ) : a + b + c = a + (b + c) := by
39+ sorry
40+
41+-- Level 5: no induction needed. Use `add_assoc`, and `add_comm` with
42+-- arguments (`add_comm b c`) so that it swaps the right sum.
43+theorem add_right_comm (a b c : ℕ) : a + b + c = a + c + b := by
44+ sorry
45+
46+end MyNat
+54, -0
......@@ -0,0 +1,54 @@
1+import Game.Implication
2+
3+/-!
4+# Advanced Addition World
5+
6+From here on you are mostly on your own. Each level is a theorem that the
7+next ones (and ≤ World) use.
8+
9+One new tactic, in level 5: `cases`. It splits a number into the ways it
10+can be built, `0` or `succ d`, without the inductive hypothesis that
11+`induction` gives:
12+```
13+cases b with
14+| zero => …
15+| succ d => …
16+```
17+And if `h : False`, then `cases h` closes the goal: there are no ways to
18+build a proof of `False`.
19+
20+Tactics from earlier worlds that help here: `intro`, `apply`, `have`,
21+`symm at h`, `repeat`, and arguments to choose what `rw` rewrites.
22+-/
23+
24+namespace MyNat
25+
26+-- Level 1: induction on `n`. In the `succ` case, `intro h` and rewrite `h`
27+-- until `succ_inj` applies to it.
28+theorem add_right_cancel (a b n : ℕ) : a + n = b + n → a = b := by
29+ sorry
30+
31+-- Level 2: induction on `n`, or deduce it from level 1.
32+theorem add_left_cancel (a b n : ℕ) : n + a = n + b → a = b := by
33+ sorry
34+
35+-- Level 3: `y` is `0 + y`. After `intro h`, argue backwards:
36+-- `apply add_right_cancel x 0 y`.
37+theorem add_left_eq_self (x y : ℕ) : x + y = y → x = 0 := by
38+ sorry
39+
40+-- Level 4: two ways spring to mind: mimic level 3, or use it.
41+theorem add_right_eq_self (x y : ℕ) : x + y = x → y = 0 := by
42+ sorry
43+
44+-- Level 5: start with `cases b with`. In the `succ` case, rewrite the
45+-- hypothesis into `0 = succ _`. Then `zero_ne_succ` turns it into a proof of
46+-- `False` (`have f := …`), and `cases f` closes the goal.
47+theorem add_right_eq_zero (a b : ℕ) : a + b = 0 → a = 0 := by
48+ sorry
49+
50+-- Level 6: mimic level 5, or use it.
51+theorem add_left_eq_zero (a b : ℕ) : a + b = 0 → b = 0 := by
52+ sorry
53+
54+end MyNat
+79, -0
......@@ -0,0 +1,79 @@
1+import Game.LessOrEqual
2+
3+/-!
4+# Advanced Multiplication World
5+
6+Advanced 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
9+multiplying 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+
12+New 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+
27+Theorems 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+
32+namespace MyNat
33+
34+-- Level 1: a warm-up; it works even for `t = 0`.
35+theorem 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`.
40+theorem 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.
45+theorem eq_succ_of_ne_zero (a : ℕ) (ha : a ≠ 0) : ∃ n, a = succ n := by
46+ sorry
47+
48+-- Level 4: use the previous level.
49+theorem one_le_of_ne_zero (a : ℕ) (ha : a ≠ 0) : 1 ≤ a := by
50+ sorry
51+
52+-- Level 5: levels 1, 2 and 4.
53+theorem 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`.
58+theorem 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).
62+theorem 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`.
66+theorem 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.
71+theorem 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`.
76+theorem mul_right_eq_self (a b : ℕ) (ha : a ≠ 0) (h : a * b = a) : b = 1 := by
77+ sorry
78+
79+end MyNat
+129, -0
......@@ -0,0 +1,129 @@
1+import Game.AdvMultiplication
2+
3+/-!
4+# Algorithm World
5+
6+Proofs like `2 + 2 = 4` and `a + b + c + d + e = e + d + c + b + a` are
7+tedious by hand. Here the computer does them: `simp only` for rearranging
8+sums (levels 1-4), and `decide` for equalities of numerals (levels 5-9). On
9+the way you prove two of Peano's axioms, `succ_inj` and `succ_ne_zero`, that
10+`MyNat.lean` gave you for free. It's the last world.
11+
12+New tactics:
13+* `simp only [h₁, h₂]` rewrites with `h₁` and `h₂` everywhere, as often as
14+ it can, and closes the goal with `rfl` if it can. Unlike `rw`, it can use
15+ `add_comm` without looping: it only swaps terms into a fixed internal
16+ order. Level 3.
17+* `macro "name" : tactic => …` makes a new tactic out of old ones. Level 4
18+ shows one.
19+* `trivial` closes the goal `True` (level 6).
20+* `decide` runs an algorithm (a `Decidable` instance) that answers the goal
21+ `P` with yes or no, and closes it on a yes. Levels 8-9.
22+
23+Some definitions are made right before the level that uses them, in plain
24+sight: `pred`, `is_zero`, the algorithm `instDecidableEq`, and `ofNat_succ`.
25+-/
26+
27+namespace MyNat
28+
29+-- Level 1: by hand, for the last time:
30+-- `add_assoc` and a targeted `add_comm a b`. Remember that `a + b + c`
31+-- means `(a + b) + c`.
32+theorem add_left_comm (a b c : ℕ) : a + (b + c) = b + (a + c) := by
33+ sorry
34+
35+-- Level 2: forget the brackets and think about the order of the variables.
36+-- `repeat rw [add_assoc]` pushes all the brackets to the right; then
37+-- `add_left_comm b c` swaps `b` and `c`, and `add_comm b d` swaps `b` and `d`.
38+example (a b c d : ℕ) : a + b + (c + d) = a + c + d + b := by
39+ sorry
40+
41+-- Level 3: not one to do by hand. One line: `simp only [add_left_comm, add_comm]`.
42+example (a b c d e f g h : ℕ) :
43+ (d + f) + (h + (a + c)) + (g + e + b) = a + b + c + d + e + f + g + h := by
44+ sorry
45+
46+-- Level 4: your own tactic. This line makes `simp_add` run the `simp only`
47+-- call between the brackets. Solve the level with it.
48+macro "simp_add" : tactic => `(tactic|(
49+ simp only [add_assoc, add_left_comm, add_comm]))
50+
51+example (a b c d e f g h : ℕ) :
52+ (d + f) + (h + (a + c)) + (g + e + b) = a + b + c + d + e + f + g + h := by
53+ sorry
54+
55+-- Level 5: `pred` tries to subtract 1. It can't from `0`, so it returns a
56+-- junk value. Defined by recursion: what it does on `0` and on `succ n`.
57+def pred : ℕ → ℕ
58+ | zero => 37
59+ | succ n => n
60+
61+theorem pred_succ (n : ℕ) : pred (succ n) = n := rfl
62+
63+-- Now prove Peano's `succ_inj`, without `succ_inj` itself or `injection`.
64+-- Start with `rw [← pred_succ a]`.
65+example (a b : ℕ) (h : succ a = succ b) : a = b := by
66+ sorry
67+
68+-- Level 6: `is_zero n` is the statement `True` when `n = 0` and `False`
69+-- otherwise.
70+def is_zero : ℕ → Prop
71+ | zero => True
72+ | succ _ => False
73+
74+theorem is_zero_zero : is_zero 0 = True := by
75+ rw [← zero_eq_0]
76+ rfl
77+
78+theorem is_zero_succ (n : ℕ) : is_zero (succ n) = False := rfl
79+
80+-- Prove Peano's last axiom without `zero_ne_succ`. After `intro h`, the
81+-- goal is `False`: `rw [← is_zero_succ a]` turns it into `is_zero (succ a)`.
82+-- Turn it into `True`, then `trivial`.
83+theorem succ_ne_zero (a : ℕ) : succ a ≠ 0 := by
84+ sorry
85+
86+-- Level 7: an algorithm for "does `a = b`?": if both are `0`, yes; if one is
87+-- `0` and the other a successor, no; for `succ m` and `succ n`, ask whether
88+-- `m = n`. `rfl`, `zero_ne_succ` and `succ_ne_zero` show the first answers
89+-- are right. This level is the last case: if `m ≠ n` then
90+-- `succ m ≠ succ n`. Start with `intro h'`: the goal becomes `False`, and
91+-- `apply h` turns it into `m = n`, with `h' : succ m = succ n` to prove it.
92+theorem succ_ne_succ (m n : ℕ) (h : m ≠ n) : succ m ≠ succ n := by
93+ sorry
94+
95+-- The algorithm, with the proof that each answer is right. `isTrue p` is
96+-- "yes, and `p` proves it"; `isFalse p` is "no, and `p` proves that".
97+-- `rw [zero_eq_0]` because the statements say `0` and the patterns `zero`.
98+instance instDecidableEq : DecidableEq ℕ
99+ | zero, zero => isTrue rfl
100+ | succ m, zero => isFalse (by rw [zero_eq_0]; exact succ_ne_zero m)
101+ | zero, succ n => isFalse (by rw [zero_eq_0]; exact zero_ne_succ n)
102+ | succ m, succ n =>
103+ match instDecidableEq m n with
104+ | isTrue h => isTrue (by rw [h])
105+ | isFalse h => isFalse (succ_ne_succ m n h)
106+
107+-- A numeral is a successor: `(n + 1 : ℕ) = succ n`, for a numeral `n`.
108+-- `MyNat.lean` seals the numerals (`irreducible`) so that `rfl` can't see
109+-- through them; `with_unfolding_all` breaks the seal for this one proof.
110+theorem ofNat_succ (n : Nat) : (OfNat.ofNat (n + 1) : ℕ) = succ (OfNat.ofNat n) := by
111+ with_unfolding_all rfl
112+
113+-- Level 8: `20 + 20 = 40`. `decide` can't run `+` (it's an axiom here, not
114+-- an algorithm), so first unfold everything into `succ`s:
115+-- `simp only [ofNat_succ, add_succ, add_zero]`. On an equation that's
116+-- already the end: both sides become the same 40 `succ`s, and `simp` closes
117+-- the goal with `rfl`.
118+example : (20 : ℕ) + 20 = 40 := by
119+ sorry
120+
121+-- Level 9: `2 + 2 ≠ 5`, a nicer proof than in Implication World. The same
122+-- `simp only` first; `rfl` can't prove a `≠`, so then `decide`. Plain
123+-- `decide` gets stuck at `OfNat.ofNat 0`, the sealed numeral `0`:
124+-- `decide +kernel` checks with Lean's kernel, which ignores seals (or
125+-- `rw [← zero_eq_0]` first, then `decide`).
126+example : (2 : ℕ) + 2 ≠ 5 := by
127+ sorry
128+
129+end MyNat
+85, -0
......@@ -0,0 +1,85 @@
1+import Game.Power
2+
3+/-!
4+# Implication World
5+
6+Theorems of the form "if P then Q", written `P → Q` (type `\to` for `→`).
7+New 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+
18+To argue forwards instead: if `t : P → Q` and `h : P`, then `t h` is a
19+proof of `Q`. Use it with `exact t h`, or keep it with `have h2 := t h`.
20+Theorems 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+
23+New 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+
30+namespace MyNat
31+
32+-- Level 1: `exact`.
33+example (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`).
38+example (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`.
43+example (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`.
49+example (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`.
54+example (x : ℕ) (h : x + 1 = 4) : x = 3 := by
55+ sorry
56+
57+-- Level 6: `intro`. The goal itself is an implication.
58+example (x : ℕ) : x = 37 → x = 37 := by
59+ sorry
60+
61+-- Level 7: `intro` practice. `repeat rw [...] at h` rewrites every match.
62+example (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`.
67+example (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.
73+theorem zero_ne_one : (0 : ℕ) ≠ 1 := by
74+ sorry
75+
76+-- Level 10: `symm`. Use level 9.
77+theorem 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`.
82+example : succ (succ 0) + succ (succ 0) ≠ succ (succ (succ (succ (succ 0)))) := by
83+ sorry
84+
85+end MyNat
+81, -0
......@@ -0,0 +1,81 @@
1+import Game.AdvAddition
2+
3+/-!
4+# ≤ World
5+
6+`a ≤ b` (type `\le`) is defined as `∃ c, b = a + c`: "there exists a `c`
7+such that `b = a + c`" (type `\ex` for `∃`). The definition is `MyNat.le`,
8+in `MyNat.lean`.
9+
10+New 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+
32+namespace MyNat
33+
34+-- Level 1: start with `exists 0`.
35+theorem le_refl (x : ℕ) : x ≤ x := by
36+ sorry
37+
38+-- Level 2: what number will you choose?
39+theorem zero_le (x : ℕ) : 0 ≤ x := by
40+ sorry
41+
42+-- Level 3: `succ_eq_add_one` will help.
43+theorem le_succ_self (x : ℕ) : x ≤ succ x := by
44+ sorry
45+
46+-- Level 4: take both hypotheses apart with `cases` first.
47+theorem 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.
51+theorem 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`.
56+theorem 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.
60+example (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.
66+theorem le_total (x y : ℕ) : x ≤ y ∨ y ≤ x := by
67+ sorry
68+
69+-- Level 9: helpful for the last two levels.
70+theorem 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.
74+theorem 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.
78+theorem le_two (x : ℕ) (hx : x ≤ 2) : x = 0 ∨ x = 1 ∨ x = 2 := by
79+ sorry
80+
81+end MyNat
+57, -0
......@@ -0,0 +1,57 @@
1+import Game.Addition
2+
3+/-!
4+# Multiplication World
5+
6+Multiplication is defined like addition, by what it does to `0` and `succ d`:
7+* `mul_zero a : a * 0 = 0`
8+* `mul_succ a d : a * succ d = a * d + a`
9+
10+Everything else about `*` is proved from these two, by rewriting and
11+induction. The Addition World theorems (`zero_add`, `succ_add`, `add_comm`,
12+`add_assoc`, `add_right_comm`) and the numerals (`one_eq_succ_zero`,
13+`two_eq_succ_one`, …) are all available. `repeat rw [h]` rewrites with `h`
14+until it no longer applies.
15+-/
16+
17+namespace MyNat
18+
19+-- Level 1: a warm-up, no induction needed, because `1` is a successor.
20+theorem mul_one (m : ℕ) : m * 1 = m := by
21+ sorry
22+
23+-- Level 2: the zero case of `mul_comm` will need this.
24+theorem zero_mul (m : ℕ) : 0 * m = 0 := by
25+ sorry
26+
27+-- Level 3: the last level of Addition World might help.
28+theorem succ_mul (a b : ℕ) : succ a * b = a * b + b := by
29+ sorry
30+
31+-- Level 4: the first sub-boss.
32+theorem mul_comm (a b : ℕ) : a * b = b * a := by
33+ sorry
34+
35+-- Level 5: by induction, with `succ_mul`, or with commutativity.
36+-- Which is quickest?
37+theorem one_mul (m : ℕ) : 1 * m = m := by
38+ sorry
39+
40+-- Level 6: more useful than it looks (a later boss needs it).
41+theorem two_mul (m : ℕ) : 2 * m = m + m := by
42+ sorry
43+
44+-- Level 7: left distributivity. Some variables are harder to induct on
45+-- than others.
46+theorem mul_add (a b c : ℕ) : a * (b + c) = a * b + a * c := by
47+ sorry
48+
49+-- Level 8: just as fiddly by induction, but there is a trick that avoids it.
50+theorem add_mul (a b c : ℕ) : (a + b) * c = a * c + b * c := by
51+ sorry
52+
53+-- Level 9: the boss. `a * b * c` means `(a * b) * c`.
54+theorem mul_assoc (a b c : ℕ) : a * b * c = a * (b * c) := by
55+ sorry
56+
57+end MyNat
+86, -0
......@@ -0,0 +1,86 @@
1+/-!
2+# `MyNat`: the natural numbers of the Natural Number Game
3+
4+A 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 `ℕ`. -/
11+inductive MyNat where
12+ | zero : MyNat
13+ | succ : MyNat → MyNat
14+
15+@[inherit_doc]
16+notation (priority := 1000000) "ℕ" => MyNat
17+
18+attribute [pp_nodot] MyNat.succ
19+
20+namespace MyNat
21+
22+instance : Inhabited ℕ := ⟨zero⟩
23+
24+def ofNat : Nat → ℕ
25+ | 0 => zero
26+ | n + 1 => succ (ofNat n)
27+
28+instance instOfNat {n : Nat} : OfNat ℕ n := ⟨ofNat n⟩
29+
30+theorem 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]
34+def 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]
41+def 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).
47+theorem one_eq_succ_zero : (1 : ℕ) = succ 0 := rfl
48+theorem two_eq_succ_one : (2 : ℕ) = succ 1 := rfl
49+theorem three_eq_succ_two : (3 : ℕ) = succ 2 := rfl
50+theorem four_eq_succ_three : (4 : ℕ) = succ 3 := rfl
51+
52+-- Peano's axioms (Implication World).
53+theorem succ_inj (a b : ℕ) (h : succ a = succ b) : a = b := by
54+ injection h
55+
56+theorem 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.
59+attribute [irreducible] ofNat
60+
61+-- Addition (Tutorial World, levels 5 and 7).
62+opaque add : ℕ → ℕ → ℕ
63+instance : Add ℕ := ⟨add⟩
64+axiom add_zero (a : ℕ) : a + 0 = a
65+axiom add_succ (a d : ℕ) : a + succ d = succ (a + d)
66+
67+-- Multiplication (Multiplication World).
68+opaque mul : ℕ → ℕ → ℕ
69+instance : Mul ℕ := ⟨mul⟩
70+axiom mul_zero (a : ℕ) : a * 0 = 0
71+axiom mul_succ (a b : ℕ) : a * succ b = a * b + a
72+
73+-- Power (Power World).
74+opaque pow : ℕ → ℕ → ℕ
75+instance : Pow ℕ ℕ := ⟨pow⟩
76+-- Without this, the `0` in `m ^ 0` would be elaborated as a `Nat` (as NNG4 does).
77+macro_rules | `($x ^ $y) => `(HPow.hPow ($x : MyNat) ($y : MyNat))
78+axiom pow_zero (m : ℕ) : m ^ 0 = 1
79+axiom 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`.
82+def le (a b : ℕ) := ∃ c : ℕ, b = a + c
83+instance : LE ℕ := ⟨le⟩
84+
85+end MyNat
86+
+55, -0
......@@ -0,0 +1,55 @@
1+import Game.Multiplication
2+
3+/-!
4+# Power World
5+
6+Exponentiation is defined by what it does to `0` and `succ b`:
7+* `pow_zero a : a ^ 0 = 1`
8+* `pow_succ a b : a ^ succ b = a ^ b * a`
9+
10+Using only these, and everything from the Addition and Multiplication
11+Worlds (`mul_comm`, `mul_assoc`, `mul_add`, `two_mul`, …), can you get
12+past the final boss?
13+-/
14+
15+namespace MyNat
16+
17+-- Level 1: mathematicians sometimes debate what `0 ^ 0` is. In this game
18+-- it is `1`.
19+theorem zero_pow_zero : (0 : ℕ) ^ 0 = 1 := by
20+ sorry
21+
22+-- Level 2: if `n` is a successor, then `0 ^ n = 0`.
23+theorem zero_pow_succ (m : ℕ) : (0 : ℕ) ^ (succ m) = 0 := by
24+ sorry
25+
26+-- Level 3
27+theorem pow_one (a : ℕ) : a ^ 1 = a := by
28+ sorry
29+
30+-- Level 4
31+theorem one_pow (m : ℕ) : (1 : ℕ) ^ m = 1 := by
32+ sorry
33+
34+-- Level 5: this one will be useful for the final boss.
35+theorem pow_two (a : ℕ) : a ^ 2 = a * a := by
36+ sorry
37+
38+-- Level 6: the approach to the final boss begins.
39+theorem pow_add (a m n : ℕ) : a ^ (m + n) = a ^ m * a ^ n := by
40+ sorry
41+
42+-- Level 7: if `rw [mul_comm]` swaps the wrong multiplication, give it
43+-- arguments (`mul_comm a b`) to say which one.
44+theorem mul_pow (a b n : ℕ) : (a * b) ^ n = a ^ n * b ^ n := by
45+ sorry
46+
47+-- Level 8: a savage sub-boss.
48+theorem pow_pow (a m n : ℕ) : (a ^ m) ^ n = a ^ (m * n) := by
49+ sorry
50+
51+-- Level 9: the final boss. `2 * a * b` means `(2 * a) * b`.
52+theorem add_sq (a b : ℕ) : (a + b) ^ 2 = a ^ 2 + b ^ 2 + 2 * a * b := by
53+ sorry
54+
55+end MyNat
+73, -0
......@@ -0,0 +1,73 @@
1+import Game.MyNat
2+
3+/-!
4+# Tutorial World
5+
6+Each level is a theorem. The line `example (x y : ℕ) (h : y = x + 7) :
7+2 * y = 2 * (x + 7) := by` says: given numbers `x`, `y` and a hypothesis `h`
8+that `y = x + 7`, prove the goal `2 * y = 2 * (x + 7)`. After `by` comes the
9+proof: a list of *tactics*, one per line, each indented by two spaces. Each
10+tactic changes the goal, and the level is done when no goal is left.
11+
12+At first each proof is `sorry`, a keyword that "proves" anything for free.
13+Lean accepts it, with a warning. Replace it with a real proof. Put the cursor
14+in a proof to see the current goal and hypotheses (see the README).
15+
16+Tactics in this world:
17+* `rfl` proves a goal of the form `X = X`, where both sides are identical.
18+* `rw [h]`, where `h : A = B`, replaces every `A` in the goal by `B`.
19+ `rw [← h]` (type `\l` for `←`) goes the other way, `B` to `A`.
20+ After rewriting, `rw` tries `rfl` by itself, so it often finishes the
21+ level. A `rfl` after that fails with "no goals": delete it.
22+* `rw [h₁, h₂]` is `rw [h₁]` followed by `rw [h₂]`.
23+
24+`rw` also takes theorems, such as `add_zero`, which says `a + 0 = a` for
25+every `a`. `rw [add_zero]` rewrites the first `_ + 0` it finds, and every
26+copy of that same sum. To pick another one, say which:
27+`rw [add_zero c]` rewrites `c + 0` only.
28+
29+A level stated as `theorem name …` can be used in all the later levels, like
30+`add_zero`; one stated as `example …` is only an exercise.
31+-/
32+
33+namespace MyNat
34+
35+-- Level 1: both sides are the same, so `rfl` proves it.
36+example (x q : ℕ) : 37 * x + q = 37 * x + q := by
37+ sorry
38+
39+-- Level 2: the goal has a `y`, and `h` says what `y` is: `rw [h]`.
40+example (x y : ℕ) (h : y = x + 7) : 2 * y = 2 * (x + 7) := by
41+ sorry
42+
43+-- Level 3: numerals. `2` is defined as `succ 1`, and `1` as `succ 0`: the
44+-- theorems `two_eq_succ_one : 2 = succ 1` and `one_eq_succ_zero : 1 = succ 0`
45+-- (`three_eq_succ_two` and `four_eq_succ_three` too). Rewrite with them.
46+example : 2 = succ (succ 0) := by
47+ sorry
48+
49+-- Level 4: the same goal, rewriting backwards this time: turn `succ 0` into
50+-- `1` with `rw [← one_eq_succ_zero]`, then `succ 1` into `2`.
51+example : 2 = succ (succ 0) := by
52+ sorry
53+
54+-- Level 5: `add_zero a : a + 0 = a`. Rewrite with it until both sides agree.
55+example (a b c : ℕ) : a + (b + 0) + (c + 0) = a + b + c := by
56+ sorry
57+
58+-- Level 6: the same goal, but now rewrite `c + 0` first, then `b + 0`:
59+-- `rw [add_zero c]`.
60+example (a b c : ℕ) : a + (b + 0) + (c + 0) = a + b + c := by
61+ sorry
62+
63+-- Level 7: `add_succ a d : a + succ d = succ (a + d)`, the definition of
64+-- addition. Write the `1` as `succ 0` first.
65+theorem succ_eq_add_one (n : ℕ) : succ n = n + 1 := by
66+ sorry
67+
68+-- Level 8: unfold both sides into `succ`s (start with the `4`, then the
69+-- `3`, then all the `2`s at once), then use `add_succ` and `add_zero`.
70+example : (2 : ℕ) + 2 = 4 := by
71+ sorry
72+
73+end MyNat
+201, -0
......@@ -0,0 +1,201 @@
1+ Apache License
2+ Version 2.0, January 2004
3+ http://www.apache.org/licenses/
4+
5+ TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION
6+
7+ 1. Definitions.
8+
9+ "License" shall mean the terms and conditions for use, reproduction,
10+ and distribution as defined by Sections 1 through 9 of this document.
11+
12+ "Licensor" shall mean the copyright owner or entity authorized by
13+ the copyright owner that is granting the License.
14+
15+ "Legal Entity" shall mean the union of the acting entity and all
16+ other entities that control, are controlled by, or are under common
17+ control with that entity. For the purposes of this definition,
18+ "control" means (i) the power, direct or indirect, to cause the
19+ direction or management of such entity, whether by contract or
20+ otherwise, or (ii) ownership of fifty percent (50%) or more of the
21+ outstanding shares, or (iii) beneficial ownership of such entity.
22+
23+ "You" (or "Your") shall mean an individual or Legal Entity
24+ exercising permissions granted by this License.
25+
26+ "Source" form shall mean the preferred form for making modifications,
27+ including but not limited to software source code, documentation
28+ source, and configuration files.
29+
30+ "Object" form shall mean any form resulting from mechanical
31+ transformation or translation of a Source form, including but
32+ not limited to compiled object code, generated documentation,
33+ and conversions to other media types.
34+
35+ "Work" shall mean the work of authorship, whether in Source or
36+ Object form, made available under the License, as indicated by a
37+ copyright notice that is included in or attached to the work
38+ (an example is provided in the Appendix below).
39+
40+ "Derivative Works" shall mean any work, whether in Source or Object
41+ form, that is based on (or derived from) the Work and for which the
42+ editorial revisions, annotations, elaborations, or other modifications
43+ represent, as a whole, an original work of authorship. For the purposes
44+ of this License, Derivative Works shall not include works that remain
45+ separable from, or merely link (or bind by name) to the interfaces of,
46+ the Work and Derivative Works thereof.
47+
48+ "Contribution" shall mean any work of authorship, including
49+ the original version of the Work and any modifications or additions
50+ to that Work or Derivative Works thereof, that is intentionally
51+ submitted to Licensor for inclusion in the Work by the copyright owner
52+ or by an individual or Legal Entity authorized to submit on behalf of
53+ the copyright owner. For the purposes of this definition, "submitted"
54+ means any form of electronic, verbal, or written communication sent
55+ to the Licensor or its representatives, including but not limited to
56+ communication on electronic mailing lists, source code control systems,
57+ and issue tracking systems that are managed by, or on behalf of, the
58+ Licensor for the purpose of discussing and improving the Work, but
59+ excluding communication that is conspicuously marked or otherwise
60+ designated in writing by the copyright owner as "Not a Contribution."
61+
62+ "Contributor" shall mean Licensor and any individual or Legal Entity
63+ on behalf of whom a Contribution has been received by Licensor and
64+ subsequently incorporated within the Work.
65+
66+ 2. Grant of Copyright License. Subject to the terms and conditions of
67+ this License, each Contributor hereby grants to You a perpetual,
68+ worldwide, non-exclusive, no-charge, royalty-free, irrevocable
69+ copyright license to reproduce, prepare Derivative Works of,
70+ publicly display, publicly perform, sublicense, and distribute the
71+ Work and such Derivative Works in Source or Object form.
72+
73+ 3. Grant of Patent License. Subject to the terms and conditions of
74+ this License, each Contributor hereby grants to You a perpetual,
75+ worldwide, non-exclusive, no-charge, royalty-free, irrevocable
76+ (except as stated in this section) patent license to make, have made,
77+ use, offer to sell, sell, import, and otherwise transfer the Work,
78+ where such license applies only to those patent claims licensable
79+ by such Contributor that are necessarily infringed by their
80+ Contribution(s) alone or by combination of their Contribution(s)
81+ with the Work to which such Contribution(s) was submitted. If You
82+ institute patent litigation against any entity (including a
83+ cross-claim or counterclaim in a lawsuit) alleging that the Work
84+ or a Contribution incorporated within the Work constitutes direct
85+ or contributory patent infringement, then any patent licenses
86+ granted to You under this License for that Work shall terminate
87+ as of the date such litigation is filed.
88+
89+ 4. Redistribution. You may reproduce and distribute copies of the
90+ Work or Derivative Works thereof in any medium, with or without
91+ modifications, and in Source or Object form, provided that You
92+ meet the following conditions:
93+
94+ (a) You must give any other recipients of the Work or
95+ Derivative Works a copy of this License; and
96+
97+ (b) You must cause any modified files to carry prominent notices
98+ stating that You changed the files; and
99+
100+ (c) You must retain, in the Source form of any Derivative Works
101+ that You distribute, all copyright, patent, trademark, and
102+ attribution notices from the Source form of the Work,
103+ excluding those notices that do not pertain to any part of
104+ the Derivative Works; and
105+
106+ (d) If the Work includes a "NOTICE" text file as part of its
107+ distribution, then any Derivative Works that You distribute must
108+ include a readable copy of the attribution notices contained
109+ within such NOTICE file, excluding those notices that do not
110+ pertain to any part of the Derivative Works, in at least one
111+ of the following places: within a NOTICE text file distributed
112+ as part of the Derivative Works; within the Source form or
113+ documentation, if provided along with the Derivative Works; or,
114+ within a display generated by the Derivative Works, if and
115+ wherever such third-party notices normally appear. The contents
116+ of the NOTICE file are for informational purposes only and
117+ do not modify the License. You may add Your own attribution
118+ notices within Derivative Works that You distribute, alongside
119+ or as an addendum to the NOTICE text from the Work, provided
120+ that such additional attribution notices cannot be construed
121+ as modifying the License.
122+
123+ You may add Your own copyright statement to Your modifications and
124+ may provide additional or different license terms and conditions
125+ for use, reproduction, or distribution of Your modifications, or
126+ for any such Derivative Works as a whole, provided Your use,
127+ reproduction, and distribution of the Work otherwise complies with
128+ the conditions stated in this License.
129+
130+ 5. Submission of Contributions. Unless You explicitly state otherwise,
131+ any Contribution intentionally submitted for inclusion in the Work
132+ by You to the Licensor shall be under the terms and conditions of
133+ this License, without any additional terms or conditions.
134+ Notwithstanding the above, nothing herein shall supersede or modify
135+ the terms of any separate license agreement you may have executed
136+ with Licensor regarding such Contributions.
137+
138+ 6. Trademarks. This License does not grant permission to use the trade
139+ names, trademarks, service marks, or product names of the Licensor,
140+ except as required for reasonable and customary use in describing the
141+ origin of the Work and reproducing the content of the NOTICE file.
142+
143+ 7. Disclaimer of Warranty. Unless required by applicable law or
144+ agreed to in writing, Licensor provides the Work (and each
145+ Contributor provides its Contributions) on an "AS IS" BASIS,
146+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
147+ implied, including, without limitation, any warranties or conditions
148+ of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A
149+ PARTICULAR PURPOSE. You are solely responsible for determining the
150+ appropriateness of using or redistributing the Work and assume any
151+ risks associated with Your exercise of permissions under this License.
152+
153+ 8. Limitation of Liability. In no event and under no legal theory,
154+ whether in tort (including negligence), contract, or otherwise,
155+ unless required by applicable law (such as deliberate and grossly
156+ negligent acts) or agreed to in writing, shall any Contributor be
157+ liable to You for damages, including any direct, indirect, special,
158+ incidental, or consequential damages of any character arising as a
159+ result of this License or out of the use or inability to use the
160+ Work (including but not limited to damages for loss of goodwill,
161+ work stoppage, computer failure or malfunction, or any and all
162+ other commercial damages or losses), even if such Contributor
163+ has been advised of the possibility of such damages.
164+
165+ 9. Accepting Warranty or Additional Liability. While redistributing
166+ the Work or Derivative Works thereof, You may choose to offer,
167+ and charge a fee for, acceptance of support, warranty, indemnity,
168+ or other liability obligations and/or rights consistent with this
169+ License. However, in accepting such obligations, You may act only
170+ on Your own behalf and on Your sole responsibility, not on behalf
171+ of any other Contributor, and only if You agree to indemnify,
172+ defend, and hold each Contributor harmless for any liability
173+ incurred by, or claims asserted against, such Contributor by reason
174+ of your accepting any such warranty or additional liability.
175+
176+ END OF TERMS AND CONDITIONS
177+
178+ APPENDIX: How to apply the Apache License to your work.
179+
180+ To apply the Apache License to your work, attach the following
181+ boilerplate notice, with the fields enclosed by brackets "[]"
182+ replaced with your own identifying information. (Don't include
183+ the brackets!) The text should be enclosed in the appropriate
184+ comment syntax for the file format. We also recommend that a
185+ file or class name and description of purpose be included on the
186+ same "printed page" as the copyright notice for easier
187+ identification within third-party archives.
188+
189+ Copyright [yyyy] [name of copyright owner]
190+
191+ Licensed under the Apache License, Version 2.0 (the "License");
192+ you may not use this file except in compliance with the License.
193+ You may obtain a copy of the License at
194+
195+ http://www.apache.org/licenses/LICENSE-2.0
196+
197+ Unless required by applicable law or agreed to in writing, software
198+ distributed under the License is distributed on an "AS IS" BASIS,
199+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
200+ See the License for the specific language governing permissions and
201+ limitations under the License.
+80, -0
......@@ -0,0 +1,80 @@
1+# lean-101: the Natural Number Game in your own editor
2+
3+The [Natural Number Game](https://adam.math.hhu.de/#/g/leanprover-community/nng4) teaches Lean by building the natural numbers from scratch: addition, multiplication, powers, inequalities, one small theorem at a time. In this repository we copy the levels of this game into ordinary Lean files, so you can play the game locally on your own computer.
4+
5+Each level is a theorem whose proof is `sorry` (`sorry` is a special keyword which lets you "prove" any theorem for free). To beat a level, one should replace the `sorry` with a genuine proof. The project needs nothing but core Lean (i.e., mathlib is not required), so it builds quickly.
6+
7+## Getting started
8+
9+1. **Install Lean.** Lean comes through its version manager, [elan](https://github.com/leanprover/elan):
10+
11+ ```sh
12+ curl https://elan.lean-lang.org/elan-init.sh -sSf | sh
13+ ```
14+
15+ This puts `lean` and `lake` (Lean's build tool) in `~/.elan/bin`. Open a new terminal afterwards so they are on your `PATH`.
16+
17+2. **Clone the git repository and build the levels.**
18+
19+ ```sh
20+ git clone https://a.pseudo.top/lean-101.git
21+ cd lean-101
22+ lake build
23+ ```
24+
25+ The first time you run `lake build`, it will first download Lean; this may take a minute or so. You will also see "sorry" warnings for each level; this is normal.
26+
27+ **Remark.** The goal of the game is to be able to run `lake build` without any warnings.
28+
29+3. **Start playing.** Open `Game/Tutorial.lean` in your editor (see below for Emacs, VS Code or a plain terminal) and begin with level 1.
30+
31+## The worlds
32+
33+Play them in this order. Each world can use everything proved in the worlds before it, so your earlier theorems become tools for the later ones.
34+
35+|File |What you learn |
36+|-----------------------------|------------------------------------------------------------|
37+|`Game/Tutorial.lean` |`rfl`, `rw` |
38+|`Game/Addition.lean` |`induction` |
39+|`Game/Multiplication.lean` |`repeat`, choosing what to induct on |
40+|`Game/Power.lean` |rewriting at a chosen spot (`rw [mul_comm a b]`) |
41+|`Game/Implication.lean` |`exact`, `apply`, `intro`, `have`, `symm` |
42+|`Game/AdvAddition.lean` |`cases` |
43+|`Game/LessOrEqual.lean` |`exists`, `left`, `right` |
44+|`Game/AdvMultiplication.lean`|`contradiction`, `by_cases`, `induction … generalizing` |
45+|`Game/Algorithm.lean` |`simp only`, a home-made tactic, `trivial`, `decide` |
46+
47+Each file starts with an introduction to its new tactics and theorems, and every level comes with a hint in a comment just above it. Stuck? Read the hint again, and look at the goal (below) after each step.
48+
49+## Playing in a terminal
50+
51+Run `bin/watch Game/Tutorial.lean` in one terminal and edit the file in another, with any editor. Each time you save, the file is checked again (after rebuilding any earlier world you changed), and Lean's messages are printed, followed by the number of levels left. To see the goal, type your tactics above the level's `sorry`: watch shows the goal at that `sorry`, just as the game shows it after your last step. The `sorry` of a level you haven't started stays quiet. To see the goal anywhere else, put `trace_state` on a line of its own there. `lake build` checks all the files at once.
52+
53+## Playing in VS Code
54+
55+Install the "Lean 4" extension and open the `lean-101` folder. The goal appears in the Lean Infoview panel as you move the cursor.
56+
57+## Playing in Emacs
58+
59+`emacs/lean.el` sets everything up: [nael](https://codeberg.org/mekeor/nael) (from MELPA) on eglot, a goal window, and indentation that understands Lean. Load it from your `init.el`, after `package-initialize` and with `use-package-always-ensure` (or `:ensure t`):
60+
61+```elisp
62+(load "/path/to/lean-101/emacs/lean.el")
63+```
64+
65+Then open a `.lean` file. Lean starts in the background (the first time takes a few seconds; the mode line shows `[eglot:lean]` when it is ready).
66+
67+- **See the goal:** `C-c C-g` opens the goal window on the right, like the game's right-hand panel. It follows the cursor: at the start of a tactic line it shows the goal before that step, at the end the goal after it. The goal also appears in the echo area as you move.
68+- **Errors** are underlined. `C-c C-n` jumps to the next one, and its message also shows in the goal window.
69+- **Symbols:** type `\l` then space for `←`, `\to` for `→`, `\N` for `ℕ`, `\ne` for `≠`. `C-c C-k` lists them all.
70+- **Completion** pops up by itself after 2 characters and a second's pause (or press `C-M-i`). In the popup, TAB and S-TAB move, RET inserts.
71+- **Indentation:** TAB jumps to the most likely column (2 more after a line ending in `by`, `:=` or `=>`). Press TAB again to cycle through the other sensible columns, and S-TAB to go one level out. RET indents the new line the same way. Lean only accepts spaces, never tab characters, and the setup takes care of that.
72+- **Check everything:** `C-c C-c` builds the whole project.
73+
74+## Credits and licence
75+
76+The levels, their statements and most hints come from [NNG4](https://github.com/leanprover-community/NNG4) (`Game/Levels/`) by Kevin Buzzard, Jon Eugster and the Lean community, under the Apache License 2.0. This repository is under the same licence (`LICENSE`).
77+
78+## Remark on MyNat.lean
79+
80+`Game/MyNat.lean` is not a world: it builds the game's natural numbers (`MyNat`), with `succ`, the numerals, `+`, `*`, `^` and `≤`. Feel free to read it, but don't edit it, since every world depends on it. As in the game, `+`, `*` and `^` are sealed and come with their defining equations (`add_zero`, `add_succ`, `mul_zero`, …) as axioms, so Lean can't simply compute `2 + 2`.
+66, -0
......@@ -0,0 +1,66 @@
1+#!/bin/sh
2+# Usage: bin/watch FILE.lean
3+# Re-checks FILE each time it (or another file in Game/) changes and prints
4+# Lean's messages. Earlier worlds that changed are rebuilt first.
5+#
6+# Goals: a `sorry` after your tactics (on a line of its own, or after `=>`)
7+# shows the goal at that point; the `sorry` of a level you haven't started
8+# stays quiet. Elsewhere, `trace_state` on a line of its own prints the goal.
9+# An unfinished proof shows what is left as an "unsolved goals" error.
10+set -eu
11+[ $# -eq 1 ] || { echo "usage: $0 FILE.lean" >&2; exit 2; }
12+[ -f "$1" ] || { echo "$0: no such file: $1" >&2; exit 2; }
13+# Resolve FILE before moving to the project root.
14+file=$(cd "$(dirname "$1")" && pwd)/$(basename "$1")
15+cd "$(dirname "$0")/.."
16+root=$(pwd)/
17+PATH=$HOME/.elan/bin:$PATH
18+# `lake lean` leaves a file in $TMPDIR each time it runs: give it a private
19+# one, removed on exit.
20+TMPDIR=$(mktemp -d)
21+export TMPDIR
22+trap 'rm -rf "$TMPDIR"' EXIT
23+trap 'exit 130' INT TERM
24+# Lake's log of the imports' build goes to stderr; it matters only when one
25+# of them fails.
26+log=$TMPDIR/log
27+# FILE is checked through a copy where those `sorry`s print the goal first,
28+# on the same line, so line numbers don't change.
29+copy=$TMPDIR/$(basename "$file")
30+rel=${file#"$root"}
31+tidy() { sed -e "s|$copy|$rel|g" -e "s|$root||g"; }
32+last=
33+while :; do
34+ # Compare contents, not times: portable, and no saves are missed. An editor
35+ # that saves by renaming can leave a file missing for a moment: wait.
36+ if now=$(cat "$file" Game/*.lean 2>/dev/null | cksum) &&
37+ [ -f "$file" ] && [ "$now" != "$last" ]; then
38+ last=$now
39+ printf '\033[H\033[2J== %s (%s)\n\n' "$rel" "$(date +%H:%M:%S)"
40+ awk '
41+ function show() {
42+ sub(/sorry[ \t]*$/, "trace \"Goal at line " NR ":\"; trace_state; sorry")
43+ }
44+ /^[ \t]*sorry[ \t]*$/ && prev !~ /by[ \t]*$/ { show() }
45+ /=>[ \t]*sorry[ \t]*$/ { show() }
46+ { print; if ($0 !~ /^[ \t]*$/) prev = $0 }
47+ ' "$file" > "$copy"
48+ # `lake lean` builds the file's imports first, with the project's options.
49+ if out=$(lake -q lean "$copy" 2>"$log"); then
50+ if [ -z "$out" ]; then
51+ echo "No warnings: every level in this file is done."
52+ else
53+ printf '%s\n\n' "$out" | tidy
54+ left=$(printf '%s\n' "$out" | grep -c 'declaration uses `sorry`' || true)
55+ [ "$left" -eq 0 ] || echo "$left level(s) left in this file."
56+ fi
57+ elif [ -n "$out" ]; then
58+ printf '%s\n' "$out" | tidy
59+ else
60+ echo "A file this one imports has an error. Fix it first:"
61+ echo
62+ grep -v -e 'declaration uses `sorry`' -e '^⚠ ' -e '^trace: ' "$log" | tidy
63+ fi
64+ fi
65+ sleep 1
66+done
+232, -0
......@@ -0,0 +1,232 @@
1+;;; lean.el --- Emacs set-up for this project (nael + eglot) -*- lexical-binding: t -*-
2+
3+;; Load it from your init.el with (load "/path/to/lean-101/emacs/lean.el"),
4+;; after `package-initialize'. See README.md, "In Emacs".
5+;;
6+;; Needs: Emacs 30+ (eglot, use-package), `nael' from MELPA, and
7+;; `use-package-always-ensure' (or add `:ensure t' below). Completion popups
8+;; come from corfu with `corfu-auto' (any completion-at-point UI works).
9+
10+;; -----------------------------------------------------------------------------
11+;; Lean 4
12+;; -----------------------------------------------------------------------------
13+;; elan puts lean and lake in ~/.elan/bin. A daemon started before that was on
14+;; $PATH would not find `lake serve', so add it here too.
15+(let ((elan (expand-file-name "~/.elan/bin")))
16+ (when (and (file-directory-p elan) (not (member elan exec-path)))
17+ (add-to-list 'exec-path elan)
18+ (setenv "PATH" (concat elan path-separator (getenv "PATH")))))
19+
20+;; nael has no indentation of its own: TAB fell back to `indent-relative' and
21+;; inserted tab characters, which Lean rejects. Lean's indentation carries
22+;; meaning (as in Python), so this works like python-mode: TAB goes to the most
23+;; likely column and, pressed again, cycles through the other plausible ones;
24+;; indenting a region keeps every line whose indentation is already plausible.
25+(defconst my/lean--command-re
26+ (concat "[ \t]*\\(?:@\\[\\|/--\\|/-!\\|#[a-z]+\\_>\\|"
27+ (regexp-opt '("import" "open" "namespace" "section" "end" "universe"
28+ "variable" "set_option" "theorem" "lemma" "def" "example"
29+ "abbrev" "instance" "axiom" "opaque" "inductive" "structure"
30+ "class" "macro" "macro_rules" "syntax" "notation" "infix"
31+ "infixl" "infixr" "prefix" "postfix" "attribute" "elab"
32+ "noncomputable" "private" "protected" "partial" "unsafe" "public"
33+ "mutual" "where" "termination_by" "decreasing_by" "deriving" "prelude" "module")
34+ 'symbols)
35+ "\\)")
36+ "A top-level command: its line starts in column 0.")
37+
38+(defconst my/lean--decl-re
39+ (concat "[ \t]*\\(?:@\\[[^]\n]*\\][ \t]*\\)?"
40+ "\\(?:\\(?:private\\|protected\\|noncomputable\\|partial\\|unsafe\\)[ \t]+\\)*"
41+ "\\(?:theorem\\|lemma\\|example\\|def\\|instance\\|abbrev\\)\\_>")
42+ "A declaration whose statement may continue on the following lines.")
43+
44+(defconst my/lean--opener-re
45+ "\\(?:\\_<by\\|:=\\|=>\\|\\_<do\\|\\_<where\\|\\_<then\\|\\_<else\\|\\_<calc\\)\\'"
46+ "Code ending like this is followed by a block indented 2 more.")
47+
48+(defun my/lean--code ()
49+ "The code on the line at point, without indentation or a trailing `--' comment."
50+ (let ((s (buffer-substring-no-properties
51+ (progn (back-to-indentation) (point)) (line-end-position))))
52+ (replace-regexp-in-string "[ \t]*\\(?:--.*\\)?\\'" "" s)))
53+
54+(defun my/lean--code-line-p ()
55+ "Non-nil if the line at point has code (not blank, not only a comment)."
56+ (save-excursion
57+ (beginning-of-line)
58+ (and (not (looking-at-p "[ \t]*\\(?:--\\|/-\\|$\\)"))
59+ (not (nth 4 (syntax-ppss))))))
60+
61+(defun my/lean--previous-code-line ()
62+ "Move to the previous line with code; nil if there is none."
63+ (let (found)
64+ (while (and (not found) (zerop (forward-line -1)))
65+ (setq found (my/lean--code-line-p)))
66+ found))
67+
68+(defun my/lean--statement-column ()
69+ "If the line at point is part of a declaration header, the declaration's column.
70+The line at point may end the header (with `:=' or `by'); the lines above may not."
71+ (save-excursion
72+ (let (col done (first t))
73+ (while (not done)
74+ (let ((code (my/lean--code)))
75+ (cond ((and (not first)
76+ (or (string-match-p ":=" code)
77+ (string-match-p my/lean--opener-re code)
78+ (string-prefix-p "|" code)))
79+ (setq done t))
80+ ((save-excursion (beginning-of-line) (looking-at-p my/lean--decl-re))
81+ (setq col (current-indentation) done t))
82+ ((or (zerop (current-indentation))
83+ (not (my/lean--previous-code-line)))
84+ (setq done t))))
85+ (setq first nil))
86+ col)))
87+
88+(defun my/lean--bar-column ()
89+ "Column for a line starting with `|', from the line at point upwards."
90+ (save-excursion
91+ (let (col)
92+ (while (not col)
93+ (let ((code (my/lean--code)) (ind (current-indentation)))
94+ (cond ((string-prefix-p "|" code) (setq col ind))
95+ ((string-match-p "\\_<with\\'" code) (setq col ind))
96+ ((or (string-match-p "\\_<where\\'" code)
97+ (save-excursion (beginning-of-line) (looking-at-p my/lean--decl-re)))
98+ (setq col (+ ind 2)))
99+ ((or (zerop ind) (not (my/lean--previous-code-line)))
100+ (setq col (+ ind 2))))))
101+ col)))
102+
103+(defun my/lean--columns ()
104+ "Return (BEST CYCLE MIN MAX) for the line at point.
105+BEST is the most likely column, CYCLE the columns TAB cycles through, and
106+any column from MIN to MAX is plausible."
107+ (save-excursion
108+ (beginning-of-line)
109+ (let* ((cur (if (my/lean--code-line-p) (my/lean--code) ""))
110+ (command (and (not (string-empty-p cur))
111+ (save-excursion (beginning-of-line)
112+ (looking-at-p my/lean--command-re)))))
113+ (if (not (my/lean--previous-code-line))
114+ (list 0 '(0) 0 0)
115+ (let* ((p (current-indentation))
116+ (code (my/lean--code))
117+ (stmt (my/lean--statement-column))
118+ (opener (string-match-p my/lean--opener-re code))
119+ (best (cond (command 0)
120+ ((string-prefix-p "|" cur) (my/lean--bar-column))
121+ ((string-match-p my/lean--opener-re code)
122+ (+ (or stmt p) 2))
123+ (stmt (+ stmt 4))
124+ ((string-match-p "\\`[·.][ \t]" code) (+ p 2))
125+ (t p)))
126+ (cols (list best 0 p (+ p 2))))
127+ (when stmt (push (+ stmt 2) cols) (push (+ stmt 4) cols))
128+ ;; Every enclosing level above is plausible, and one level inside it.
129+ (let ((ind p))
130+ (while (and (> ind 0) (my/lean--previous-code-line))
131+ (when (< (current-indentation) ind)
132+ (setq ind (current-indentation))
133+ (push ind cols)
134+ (push (+ ind 2) cols))))
135+ (list best (sort (delete-dups cols) #'<)
136+ ;; Plausible range: up to 4 past the line above, and not
137+ ;; column 0 after an opener (a tactic there ends the proof).
138+ (if (and opener (not command)) 1 0)
139+ ;; A line starting with a bracket or an operator (`(', `⟨',
140+ ;; `|>', `_ =', …) continues the one above at any depth.
141+ (if (string-match-p "\\`[^[:word:][:space:]|·]" cur)
142+ most-positive-fixnum
143+ (+ p 4))))))))
144+
145+(defun my/lean-indent-line ()
146+ "Indent the current Lean line.
147+The first TAB goes to the most likely column; TAB again cycles through the
148+other plausible columns, deepest first. Never inserts tab characters."
149+ (let* ((cols (my/lean--columns))
150+ (cur (current-indentation))
151+ (target
152+ (if (and (eq this-command 'indent-for-tab-command)
153+ (eq last-command 'indent-for-tab-command))
154+ ;; Repeated TAB: the next shallower plausible column, wrapping.
155+ (or (car (last (seq-filter (lambda (c) (< c cur)) (nth 1 cols))))
156+ (car (last (nth 1 cols))))
157+ (car cols))))
158+ (if (<= (current-column) cur)
159+ (indent-line-to target)
160+ (save-excursion (indent-line-to target)))))
161+
162+(defun my/lean--plausible-p (col)
163+ "Non-nil if COL is a plausible indentation for the line at point."
164+ (or (> (car (syntax-ppss (line-beginning-position))) 0) ; inside ( [ { ⟨
165+ (pcase-let ((`(,_ ,_ ,lo ,hi) (my/lean--columns)))
166+ (<= lo col hi))))
167+
168+(defun my/lean-indent-region (start end)
169+ "Indent the Lean lines between START and END, conservatively.
170+A line whose indentation is already plausible is kept; only the others move.
171+Tab characters in indentation become spaces. Comments are left alone."
172+ (save-excursion
173+ (goto-char start)
174+ (beginning-of-line)
175+ (let ((end (copy-marker end)))
176+ (while (< (point) end)
177+ (untabify (point) (save-excursion (skip-chars-forward " \t") (point)))
178+ (when (and (my/lean--code-line-p)
179+ (not (my/lean--plausible-p (current-indentation))))
180+ (indent-line-to (car (my/lean--columns))))
181+ (forward-line 1))
182+ (set-marker end nil))))
183+
184+(defun my/lean-dedent ()
185+ "Move the line to the next shallower plausible column."
186+ (interactive)
187+ (let* ((cur (current-indentation))
188+ (c (car (last (seq-filter (lambda (c) (< c cur)) (nth 1 (my/lean--columns)))))))
189+ (when c
190+ (if (<= (current-column) cur)
191+ (indent-line-to c)
192+ (save-excursion (indent-line-to c))))))
193+
194+(defun my/lean-setup ()
195+ ;; Lean rejects tab characters ("tabs are not allowed").
196+ (setq-local indent-tabs-mode nil)
197+ (setq-local indent-line-function #'my/lean-indent-line)
198+ (setq-local indent-region-function #'my/lean-indent-region)
199+ ;; TAB only indents (and cycles); completion pops up by itself (corfu-auto),
200+ ;; or with C-M-i.
201+ (setq-local tab-always-indent t)
202+ ;; RET indents the new line but leaves the one above as typed.
203+ (setq-local electric-indent-inhibit t))
204+
205+;; `nael' is a small Lean 4 mode built on eglot (lean4-mode needs lsp-mode).
206+;; Eglot runs `lake serve'; nael asks it for the proof goal at point and shows
207+;; it through ElDoc. `abbrev-mode' gives the Lean input: \l → ←, \to → →, …
208+;; (C-c C-k lists them).
209+(use-package nael
210+ :hook
211+ (nael-mode . eglot-ensure)
212+ (nael-mode . abbrev-mode)
213+ (nael-mode . my/lean-setup)
214+ :bind (:map nael-mode-map
215+ ("C-c C-g" . my/lean-goals)
216+ ("<backtab>" . my/lean-dedent))
217+ :config
218+ ;; The ElDoc buffer, shown on the right, is the goal view: it follows point.
219+ (add-to-list 'display-buffer-alist
220+ '("\\`\\*eldoc"
221+ (display-buffer-in-side-window)
222+ (side . right)
223+ (window-width . 0.4)))
224+ (defun my/lean-goals ()
225+ "Show the Lean goal at point in a side window that follows point."
226+ (interactive)
227+ (condition-case nil
228+ (eldoc-doc-buffer t)
229+ (user-error
230+ (message "No goal yet: wait for Lean to start, move point into a proof, retry")))))
231+
232+;;; lean.el ends here
+6, -0
......@@ -0,0 +1,6 @@
1+{"version": "1.2.0",
2+ "packagesDir": ".lake/packages",
3+ "packages": [],
4+ "name": "lean101",
5+ "lakeDir": ".lake",
6+ "fixedToolchain": false}
+7, -0
......@@ -0,0 +1,7 @@
1+name = "lean101"
2+defaultTargets = ["Game"]
3+# Some levels have hypotheses on purpose that the proof doesn't need.
4+leanOptions = { linter.unusedVariables = false }
5+
6+[[lean_lib]]
7+name = "Game"
+1, -0
......@@ -0,0 +1 @@
1+leanprover/lean4:v4.34.1