This post is part of the What is Maths series.
Now that we are armed with induction, recursion, and our fundamental axioms, we are finally ready to tackle something more complicated: addition! As I’m sure you’re already familiar with the concept of addition, let’s start by defining it in the context of our number theory.
In contrast to the definition of \( D \) we discussed previously, addition is an operation that requires two numbers as input.
If \( a \) and \( b \) are natural numbers, we will write \( a + b \) to represent the result of adding \( a \) and \( b \). We will then define addition recursively in the right hand number.
\begin{align*} a + 0 &= a \\ a + Sb &= S ( a + b ) \end{align*}It is worth noting that we must, at this stage, be far more careful about how we treat addition then we may be used to. Firstly, it is not at all obvious, from our definition, that \( a + b \) is the same as \( b + a \). Secondly, something like \( a + b + c \) is not covered at all by our definition, so we shouldn’t write this. We can instead write \( ( a + b ) + c \) or \( a + ( b + c ) \) but it is not clear that these are the same either, so it is important to make the brackets explicit. Despite these warnings, if our definition is ‘good’, we will eventually be able to prove that these familiar facts hold.
Now for an example:
\begin{align*} 3 + 2 &= S S S 0 + S S 0 & \text{by the definitions of 2 and 3} \\ &= S ( S S S 0 + S 0 ) & \text{by the definition of +} \\ &= S S ( S S S 0 + 0 ) & \text{by the definition of +} \\ &= S S ( S S S 0 ) & \text{by the definition of +} \\ &= S S S S S 0 & \text{just moving brackets for clarity} \\ &= 5 & \text{by the definition of 5} \end{align*}
This example has worked out exactly as we would have wanted! Another example worth looking at is \( n + 1 \), where \( n \) is an arbitrary natural number. It turns out that \( n + 1 = S n \), which justifies that intuitive description of \( S \) as being addition by 1. In fact, we can go one step further and provide a whole list of similar examples, all of which can be easily obtained by unwrapping the definition a few times.
\begin{align*} n + 0 &= n \\ n + 1 &= S n \\ n + 2 &= S S n \\ n + 3 &= S S S n \\ &\cdots \end{align*}
However, if we tried a ‘reversed’ list of examples, starting at \( 0 + n \), we would run into trouble right away. We cannot unwrap the definition at all here without first knowing whether \( n \) is either 0 or the successor of another natural number. Crucially, this is not a problem with the definition—this problem arises because we don’t know enough about \( n \).
You may have noticed another approach; if we substitute 0 into \( n \) in our first list of examples, you will see that the resulting infinite list of results corresponds exactly to saying \( 0 + n = n \). This idea of collapsing an infinite list of similar statements into a single claim is exactly what induction allows us to do. We can now start to write a formal proof.
In the base case, we have, directly from the definition of addition, \( 0 + 0 = 0 \) as required.
In the inductive step, we assume \( 0 + n = n \) for some \( n \) and wish to prove \( 0 + S n = S n \).
By applying the definition of addition, we get that \( S ( 0 + n ) = 0 + S n \).
Hence, our inductive hypothesis gives us \( S n = 0 + S n \) as required.
In the proof above, I have left out the tedious details of proving everything that needs to be a natural number is, in fact, a natural number. This makes the proof much clearer and easier to read. Furthermore, it is, in my opinion, clear enough in every case except for one which I shall leave for you to prove—is \( a + b \) a natural number whenever \( a \) and \( b \) are?
Leaving out these details also makes it clear just how intimately induction and recursion are linked; our inductive step involves little more than simply unwrapping a single level of the recursive definition.
Flipping Addition
We will now try to prove another key fact about addition: \( a + b = b + a \). In case I haven’t already introduced enough obscure maths words, this property is called commutativity. You may find it interesting to attempt to prove this yourself before reading ahead. However, it is harder than any of the proofs we have seen up until now!
The first thing we must be careful of is that induction only lets us ‘decompose’ one number at a time. In situations like this though, there are two numbers we might want to perform induction on and so we must take extra care not to misuse the inductive axiom. My preferred method for making sure I keep things in order is to only use induction on a single number in any given proof. By instead referring to intermediate results that are proved separately, we can more clearly see that everything is in order.
If you tried proving this claim yourself using induction, you will have found that the base case is a very similar statement to what we just proved. This is our first example of using an intermediate result. Instead of trying to copy the proof that \( 0 + a = a \) into our proof of \( a + b = b + a \), we can simply say that it’s already been proved. In addition to referencing our above proof, all that is needed is to reference the definition of addition: \( a + 0 = a \).
The inductive step, however, poses a little more difficulty; this is not at all unusual with induction. In the proof I provide below, we attempt to prove \( a + S n = S n + a \) using the inductive hypothesis \( a + n = n + a \). The only thing I can see that we’re allowed to do here is to unwrap the definition of addition in \( a + S n \), transforming it to \( S ( a + n ) \). This now leaves us with the option to apply the inductive hypothesis, transforming our formula further to \( S ( n + a ) \).
Unfortunately, however, this is where we get stuck. It is not at all obvious that \( S ( n + a ) = S n + a \). This is where we return to the idea of intermediate results, and the proof of this statement is below.
We will use induction on \( a \).
Our base case requires us to show \( S ( n + 0 ) = S n + 0 \).
This follows from unwrapping the definition of +.
In the inductive step, we assume \( S ( n + a ) = S n + a \) for some \( a \) and wish to prove \( S ( n + S a ) = S n + S a \).
You will notice that we are now using induction on the other number. By using induction in this way, we achieve a radical transformation of the problem we’re trying to solve. Instead of the awkward \( S ( n + a ) = S n + a \) which leaves us little room to move, we get to look at \( S ( n + S a ) = S n + S a \) and have an inductive hypothesis to boot. All these extra \( S \)s open up our ability to unwind the addition and the inductive hypothesis is, as usual, an incredibly powerful tool.
In fact, in this particular proof, the inductive hypothesis continues to do all the work. The only other steps we need are unwrapping and rewrapping addition, which are really doing nothing more than massaging the expressions into the shape that allows the inductive hypothesis to be used.
Before we continue on to finish our proof, it is worth noticing something interesting about the last two theorems we have proved: \( 0 + a = a \) is the same as the first line in the definition of addition, but flipped, and \( S n + a = S ( n + a ) \) is the same as the second line, but flipped. After noticing this, commutativity feels inevitable.
Now that we are armed with this intermediate result, the proof of addition’s commutativity falls into place.
We will use induction on \( n \).
Our base case requires us to show \( a + 0 = 0 + a \).
From an above theorem, we have \( 0 + a = a \) and from the definition of addition we have \( a = a + 0 \).
Therefore, \( a + 0 = 0 + a \) as required.
In the inductive step, we assume \( a + n = n + a \) for some \( n \) and wish to prove \( a + S n = S n + a \).
In case that wasn’t enough for you, try proving what is called the associative property: \( ( a + b ) + c = a + ( b + c ) \). As we have already proved the commutative property, you may now use that freely, in the same way that we used \( S ( n + a ) = S n + a \) and \( 0 + a = a \) in our proof of the commutative property. Be warned though: this is a much more challenging proof and you are likely to need several intermediate results!
Another exercise to consider is how we might define the statement ‘\( a \) is greater than \( b \)’ in the language of number theory. There are multiple equivalent ways to do this, but my favourite makes uses of addition in a rather elegant way.