master lean-101 / Game / Power.lean
Dylan Cant  ·  2026-10-27
 1import Game.Multiplication
 2
 3/-!
 4# Power World
 5
 6Exponentiation 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
10Using only these, and everything from the Addition and Multiplication
11Worlds (`mul_comm`, `mul_assoc`, `mul_add`, `two_mul`, …), can you get
12past the final boss?
13-/
14
15namespace MyNat
16
17-- Level 1: mathematicians sometimes debate what `0 ^ 0` is. In this game
18-- it is `1`.
19theorem zero_pow_zero : (0 : ℕ) ^ 0 = 1 := by
20  sorry
21
22-- Level 2: if `n` is a successor, then `0 ^ n = 0`.
23theorem zero_pow_succ (m : ℕ) : (0 : ℕ) ^ (succ m) = 0 := by
24  sorry
25
26-- Level 3
27theorem pow_one (a : ℕ) : a ^ 1 = a := by
28  sorry
29
30-- Level 4
31theorem one_pow (m : ℕ) : (1 : ℕ) ^ m = 1 := by
32  sorry
33
34-- Level 5: this one will be useful for the final boss.
35theorem pow_two (a : ℕ) : a ^ 2 = a * a := by
36  sorry
37
38-- Level 6: the approach to the final boss begins.
39theorem 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.
44theorem mul_pow (a b n : ℕ) : (a * b) ^ n = a ^ n * b ^ n := by
45  sorry
46
47-- Level 8: a savage sub-boss.
48theorem 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`.
52theorem add_sq (a b : ℕ) : (a + b) ^ 2 = a ^ 2 + b ^ 2 + 2 * a * b := by
53  sorry
54
55end MyNat