This post is part of the What is Maths series.
I think it’s now time that we discuss the fifth axiom. It is special, subtle, and much less obvious than the first four axioms. It is, in fact, special enough to get a proper name—the inductive axiom—and the process of using it also has a name—induction.
As discussed in the previous section, we know that \( \{ 0, 1, 2, 3, \ldots \} \) are all natural numbers, but are they all the natural numbers or are we missing some?
Imagine, for a moment, that we have an extra object \( \infty \) such that \( S \infty = \infty \) and we want to know whether it is a natural number. The first axiom obviously does not apply immediately. The second axiom can be applied, but, rather unhelpfully, only tells us that if \( \infty \) is a natural number, then \( \infty \) is a natural number. The third axiom tells us only that there is no natural number \( n \) other than \( \infty \) such that \( S n = \infty \). The fourth axiom is equally unhelpful.
Crucially, it turns out that the first four axioms are not capable of proving whether or not \( \infty \) is a natural number! In order to resolve this problem, we require the inductive axiom. To apply the inductive axiom, we first need to select a statement we wish to prove for all natural numbers \( n \). In this example, we shall use the statement \( n \neq \infty \). We then need to prove two things: that our statement is true about 0 (we call this the base case), and that we can do a ‘logical step’ (we call this the inductive case).
It is clear that \( 0 \neq \infty \) so our statement is true about 0. Now, our logical step starts by assuming we have some natural number \( n \) about which our statement is true—in this case, \( n \neq \infty \). To complete our logical step, we must prove that the statement is also true about \( S n \)—in this particular case, that is \( S n \neq \infty \). We actually already noticed that this step follows immediately from specialising the third axiom: \( n = \infty \) if and only if \( S n = S \infty \). Or, because \( S \infty = \infty \), we can write this equivalently as \( n = \infty \) if and only if \( S n = \infty \). As we are supposing \( n \neq \infty \), it follows that \( S n \neq \infty \) also. We can now apply the inductive axiom, which tells us that \( n \neq \infty \) for all natural numbers \( n \); in particular, \( \infty \) is not a natural number!
We can think of this induction as doing the following:
- We start by knowing \( 0 \neq \infty \).
- Our ‘logical step’ allows us to go from 0 to 1, so we now know \( 1 \neq \infty \).
- Our ‘logical step’ allows us to go from 1 to 2, so we now know \( 2 \neq \infty \).
- …
The inductive axiom tells us that this infinite process will eventually capture all natural numbers, and so this proof method is legitimate.
Now, let's look at another example of using induction.
First, we look at the base case.
By substituting 0 into axiom 4, we see that \( S 0 \neq 0 \).
Now, for the inductive step, we assume that \( S n \neq n \) (we call this the inductive hypothesis) and want to show that \( S S n \neq S n \).
By substituting \( S n \) and \( n \) into axiom 3, we have that \( S n = n \) if and only if \( S S n = S n \).
As the inductive hypothesis tells us that \( S n \neq n \), we must also have \( S S n \neq S n \).
Therefore, by induction, we have that \( S n \neq n \) for all natural numbers \( n \).
As a side note, I would like to point out that we have not proven \( \infty \) is not something that can reasonably be discussed; only that it is not within the framework of number theory. Considering strange objects such as this and trying to extend the current system to include them has turned out to be a very useful method of discovering new maths!
Recursion
Recursion and induction are rather similar concepts, but where induction applies to proofs, recursion applies to definitions. Let's look at an example: defining a function \( D ( n ) \) that, informally, we will think of as doubling a number.
The first line of this definition is totally straightforward and we can consider it as being similar to the base case of induction. The second line, at first glance, appears more suspect. Apparently we need to know what \( D \) is before we can know what \( D \) is; a mathematical chicken and egg!
However, from another perspective, the second line can be interpreted as saying we need to know what \( D ( n ) \) is before we can know what \( D ( S n ) \) is. This line of thinking is much less troubling, especially as \( n \) is ‘smaller’ than \( S n \)—even if, strictly speaking, we haven't actually defined what ‘smaller’ means in the context of natural numbers. In fact, if we try to compute \( D ( 2 ) \), we will find that this second perspective is far more helpful.
\begin{align*} D ( 2 ) &= D ( S S 0 ) & \text{by the definition of 2} \\ &= S S D ( S 0 ) & \text{by the definition of \( D \)} \\ &= S S S S D ( 0 ) & \text{the definition of \( D \) again} \\ &= S S S S 0 & \text{the definition of \( D \), yet again} \\ &= 4 & \text{by the definition of 4} \end{align*}
Whilst expanding out this recursive definition is painfully slow, we do eventually get ourselves an answer, and it's exactly what we might have hoped for! Our definition works because of two key facts about the natural numbers; I won’t provide proofs here so feel free to test your knowledge of induction by attempting to prove them yourself. Firstly, every natural number is either 0 or the successor of another natural number, but not both. This fact means that there is exactly one line of our definition that applies—having no lines or multiple lines applying to a number would be a problem. Secondly, every natural number can be written as a finite number of \( S \)s followed by a 0. This second fact essentially guarantees that our process of repeatedly applying the definition will eventually stop.
Another question you may wish to consider is whether \( D ( n ) \) is always a natural number. If you think you know, try and prove it!