This post is part of the What is Maths series.
Now that we have introduced addition into the world of number theory, we can introduce multiplication as well.
Notice that this relies on the definition of addition; trying to define this without reusing addition would be rather tricky. This also means that it will take a rather long time to fully unwind this definition for all but the smallest numbers!
As this definition is very similar in spirit to the definition of addition, I won’t discuss this too much further. It turns out, somewhat unsurprisingly, that multiplication is also associative and commutative. I encourage you to think about how this might be proven, but as it’s rather similar to addition, I won’t discuss it here.
I will, however, show a proof of an important fact about how multiplication and addition interact, often called ‘multiplying out brackets’, or ‘distributivity’. The proof consists mostly of the tedious shuffling around of symbols, but it’s worth paying attention to how it relies heavily on the commutativity and associativity of addition. Just try to imagine how unpleasant the proof would be if we hadn’t already proved these facts!
We shall use induction on \( a \).
In the base case, we wish to show \( ( b + c ) \times 0 = ( b \times 0 ) + ( c \times 0 ) \).
This follows from expanding the definitions of addition and multiplication.
In the inductive step, we assume \( ( b + c) \times a = ( b \times a ) + ( c \times a ) \) and wish to show that \( ( b + c ) \times S a = ( b \times S a ) + ( c \times S a ) \).
In the same way we defined multiplication in terms of addition, we can also define exponentiation (also called powers) in terms of multiplication.
\begin{align*} a^0 &= 1 \\ a^{Sb} &= a \times a^b \end{align*}
We won’t discuss exponentiation too much here, and we won’t go any further in this hierarchy. However, there is no fundamental reason why you should stop at exponentiation; in fact, I would encourage you to think about what might come next!
Quite surprisingly, exponentiation is neither commutative nor associative. What’s more, it isn’t too hard to find a counterexample: \( 2^3 = 8 \), but \( 3^2 = 9 \). However, this counterexample does very little to explain anything in a satisfying way. I believe you will gain the most understanding by trying to prove commutativity yourself, even if it is an impossible task. A small hint though: it has a lot to do with the topics we’ll discuss in the next part.
Ordering and Divisibility
At the end of the previous part, I posed the question of what might make a good definition for the statement ‘\( a \) is greater than \( b \)’. Shortly, I will reveal my preferred definition. I say preferred here because there is not necessarily a correct answer to this question—there are in fact multiple definitions that may all look rather different at first, but actually turn out to be equivalent. Despite this, there are some ‘bad’ definitions. For example, I could define ‘\( a \) is greater than \( b \)’ to mean \( a = 0 \) and \( b \neq 0 \). While this is, in the abstract philosophical sense discussed earlier, a legitimate thing to do, it is also rather perverse because it so rudely contradicts our preconceived ideas of what ‘greater than’ should mean.
If this definition is different to yours, can you prove that they’re equivalent? If not, can you find an example where the two definitions disagree?
We will discuss the concept of divisibility more later, but I want to bring it up here to highlight the similarity it has to the definition of ordering. It is quite remarkable that these two concepts, which intuitively feel so distinct, have near identical definitions! Our symbolic form of this definition is \( b \mid a \), which can be read as ‘\( b \) divides \( a \)’.
Armed with this new definition, we should try out some examples. Firstly, because \( 0 + 1 = 1 \), we can say \( 1 \geq 0 \). We also know that \( 1 \neq 0 \) so we can go further and say \( 1 > 0 \). As another example, we know \( 3 + 2 = 5 \) and \( 3 \neq 5 \), so we can say \( 5 > 3 \).
Now let’s try something the other way around, is \( 0 \geq 1 \)? Obviously, we are tempted to say no, but can we prove it? This actually turns out to be quite a bit harder than the examples above. Before, our examples consisted of plucking the difference out of thin air and saying ‘look, it works’! It isn’t always easy to pluck the right thing out of thin air, but, in this case, we have the advantage of a strong intuition. However, proving that 0 is not greater than or equal to 1 actually requires us to show that there is no choice of difference that would work. In other words, we need to show that for all natural numbers \( d \), we have \( 1 + d \neq 0 \).
Thankfully, this proof is quite manageable. By using commutativity, we can say \( 1 + d = d + 1 \). Then recalling the definition of addition, we have that \( d + 1 = S d \). Finally, axiom 4 tells us that \( S d \) is not 0 and so we have proved that 0 is not greater than 1. By extending this logic, we can prove that 0 is not greater than any natural number, although I shall leave the details for you to sort out.
When I suggested proving that 0 is not greater than 1, I expect your intuition immediately jumped in to claim that this must be because \( 1 > 0 \). However, this line of proof relies on a fact that we haven’t yet proven: if \( a \geq b \) and \( b \geq a \), then \( a = b \).
To prove this statement, we will first need an intermediate result. The intermediate result we need is actually so important that is has a name—the Cancellation Lemma. If you haven’t seen the word ‘lemma’ before, it is often used to describe results that are very useful, but not terribly interesting by themselves.
We will now use induction on \( a \).
The base case requires us to show that \( b = c \) given \( b + 0 = c + 0 \).
The desired result follows from the definition of addition.
The inductive step requires us to prove that if \( b + S a = c + S a \) then \( b = c \).
Our inductive hypothesis claims that if \( b + a = c + a \) then \( b = c \).
Now, as we have \( b + S a = c + S a \), the definition of addition tells us that \( S ( b + a ) = S ( c + a ) \).
Axiom 3 then gives us \( b + a = c + a \) so our result now follows from the inductive hypothesis.
This lemma is, I believe, the most obscure use of induction we have seen so far. The first line of the proof makes the observation that the claim is equivalent to saying that if \( b + a = c + a \), then \( b = c \). The latter is much neater to prove as it removes the need to keep using commutativity.
Now, the induction here is of a rather different style than what we have seen up until now. Essentially, all the statements we’ve used induction on previously have just been an equation containing the number on which we are using induction. For example, when we wanted to prove that \( S ( n + a ) = S n + a \), we just used induction over \( a \) on this equation.
In the cancellation lemma however, this is not enough. The statement we use induction on is ‘for any natural numbers \( b \) and \( c \) such that \( b + a = c + a \), it is the case that \( b = c \)’. It goes without saying, but this is a much more complex statement than just an equation. Despite this though, the actual structure of the induction is the same as everything we have seen before. You may have to read the proof a few times before you fully understand it.
A natural result of the cancellation lemma is that if \( a + b = a \), then \( b = 0 \); it is actually this result that we use in the following proof.
Similarly, because \( b \geq a \), there exists some natural number \( d_2 \) such that \( a + d_2 = b \).
Hence, by substituting \( a + d_2 \) into \( b \) in the former equation, we see that \( (a + d_2) + d_1 = a \).
By associativity, we have \( a + (d_2 + d_1) = a \).
Now, the cancellation lemma tells us that \( d_2 + d_1 = 0 \).
By referring to commutativity and the definition of ‘greater than or equal’, we see that \( 0 \geq d_1 \) and \( 0 \geq d_2 \).
Because 0 is greater than or equal to nothing other than 0, we must have \( d_1 = 0 \) and \( d_2 = 0 \).
Returning to our original two equations, this tells us that \( a = b \).
This proof is really quite exciting—we were able to prove something very substantial without using induction at all! This is really a testament to the usefulness of the results we have already proven. It is also worth noting that we didn’t refer to a single axiom or the fundamental \( S \) operation. In some sense, we have achieved a ‘higher level’ view of the natural numbers, not just in our results, but in the proofs as well.
I will now leave you with some facts that will be important to us in the following part, but which I will let you prove:
- If \( a \geq b \) and \( b \geq c \), then \( a \geq c \).
- For all numbers, either \( a \geq b \) or \( b \geq a \) (or both).
- For all numbers, \( a + b \geq a \).
- For all numbers, \( a \times b \geq a \); this statement actually needs an extra condition to be true, can you spot what it is? The previous statement will also serve as a very useful intermediate result here.