Natural Number Game in Verso

3.Β Multiplication WorldπŸ”—

How should we define 37 * x? Just like addition, we need to give definitions when x=0 and when x is a successor.

The zero case is easy: we define 37 * 0 to be 0. Now say we know 37 * d. What should 37 * succ d be? Well, that's (d+1) $37$s, so it should be 37 * d + 37.

Here are the definitions in Lean.

  • mul_zero a : a * 0 = 0

  • mul_succ a d : a * succ d = a * d + a

In this world, we must not only prove facts about multiplication like a * b = b * a, we must also prove facts about how multiplication interacts with addition, like a * (b + c) = a * b + a * c. Let's get started.

3.1.Β Level 1: mul_oneπŸ”—

See the new "*" tab in your lemmas, containing mul_zero and mul_succ. Right now these are the only facts we know about multiplication. Let's prove nine more.

Let's start with a warm-up: no induction needed for this one, because we know 1 is a successor.

For any natural number m, we have m \times 1 = m.

New: mul_succ

mul_succ a b is the proof that a * succ b = a * b + a.

New: mul_zero

mul_zero m is the proof that m * 0 = 0.

New: *

Mul a b, with notation a * b, is the usual product of natural numbers. Internally it is via two axioms:

  • mul_zero a : a * 0 = 0

  • mul_succ a b : a * succ b = a * b + a

Other theorems about naturals, such as zero_mul, are proved by induction from these two basic theorems.

theorem mul_one (m : β„•) : m * 1 = m
Tactics
Theorems
Symbols

3.2.Β Level 2: zero_mulπŸ”—

Our first challenge is mul_comm x y : x * y = y * x, and we want to prove it by induction. The zero case will need mul_zero (which we have) and zero_mul (which we don't), so let's start with this.

For all natural numbers m, we have 0 \times m = 0.

theorem zero_mul (m : β„•) : 0 * m = 0
Tactics
Theorems
Symbols

3.3.Β Level 3: succ_mulπŸ”—

Similarly we have mul_succ but we're going to need succ_mul (guess what it says -- maybe you are getting the hang of Lean's naming conventions).

The last level from addition world might help you in this level. If you can't remember what it is, you can go back to the home screen by clicking the house icon and then taking a look. You won't lose any progress.

For all natural numbers a and b, we have (\operatorname{succ}\ a) \times b = a\times b + b.

theorem succ_mul (a b : β„•) : succ a * b = a * b + b
Tactics
Theorems
Symbols

3.4.Β Level 4: mul_commπŸ”—

The first sub-boss of Multiplication World is mul_comm x y : x * y = y * x.

When you've proved this theorem we will have "spare" proofs such as zero_mul, which is now easily deducible from mul_zero. But we'll keep hold of these proofs anyway, because it's convenient to have exactly the right tool for a job.

Multiplication is commutative.

theorem mul_comm (a b : β„•) : a * b = b * a
Tactics
Theorems
Symbols

3.5.Β Level 5: one_mulπŸ”—

You can prove 1\times m=m in at least three ways. Either by induction, or by using succ_mul, or by using commutativity. Which do you think is quickest?

For any natural number m, we have 1 \times m = m.

theorem one_mul (m : β„•): 1 * m = m
Tactics
Theorems
Symbols

3.6.Β Level 6: two_mulπŸ”—

This level is more important than you think; it plays a useful role when battling a big boss later on.

For any natural number m, we have 2 \times m = m+m.

theorem two_mul (m : β„•): 2 * m = m + m
Tactics
Theorems
Symbols

3.7.Β Level 7: mul_addπŸ”—

Our next goal is "left and right distributivity", meaning a(b+c)=ab+ac and (b+c)a=ba+ca. Rather than these slightly pompous names, the name of the proofs in Lean are descriptive. Let's start with mul_add a b c, the proof of a * (b + c) = a * b + a * c. Note that the left hand side contains a multiplication and then an addition.

Multiplication is distributive over addition on the left. In other words, for all natural numbers a, b and c, we have a(b + c) = ab + ac.

theorem mul_add (a b c : β„•) : a * (b + c) = a * b + a * c
Tactics
Theorems
Symbols

3.8.Β Level 8: add_mulπŸ”—

add_mul is just as fiddly to prove by induction; but there's a trick which avoids it. Can you spot it?

Multiplication is distributive over addition. In other words, for all natural numbers a, b and c, we have (a + b) \times c = ac + bc.

theorem add_mul (a b c : β„•) : (a + b) * c = a * c + b * c
Tactics
Theorems
Symbols

3.9.Β Level 9: mul_assocπŸ”—

We now have enough to prove that multiplication is associative, the boss level of multiplication world. Good luck!

Multiplication is associative. In other words, for all natural numbers a, b and c, we have (ab)c = a(bc).

theorem mul_assoc (a b c : β„•) : (a * b) * c = a * (b * c)
Tactics
Theorems
Symbols