The Natural Numbers

Every course in this guidebook ends at the same place: a theorem about the shape of three-dimensional space, proved by a flow on curvature. This one starts somewhere that seems absurdly far away: with the question of what the numbers $0, 1, 2, 3, \dots$ actually are.

There are two reasons to start this far back, and neither is pedantry. The first is that the most important proof technique in this guidebook, induction, is not a trick for proving formulas about sums. It is a statement about what the natural numbers are, and you can only see that once the natural numbers have been written down precisely. The second reason is practical. When you prove something, you should know exactly which facts you are using, because the day one of them fails, the proof fails with it. That sounds abstract until you meet a number system where some familiar fact is false. You have used such systems every day of your life: the integers inside every computer are one.

By the end of this chapter you will be able to:

• state the five axioms for the natural numbers, and for each one, name a real system that satisfies the other four but not that one;
• write a proof by induction, and explain why the method is valid;
• define a sequence by recursion, and explain why the definition makes sense;
• prove the laws of arithmetic (commutativity, associativity, cancellation) and of order from the axioms;
• use strong induction and the well-ordering principle, and recognise them in a termination proof.

1.1Why build what everyone already knows

Children learn to count before they can read, and the natural numbers feel like the one part of mathematics that needs no explanation. So it is worth seeing, concretely, what goes wrong when a system that looks like the natural numbers is missing one of their properties.

In each case the machine's numbers behave exactly like the natural numbers for a very long time, and then one property silently fails. For a 32-bit counter, the property "adding one always gives a new number, never one you've seen before" fails after about two billion steps.

So here is the plan for this chapter. Write down a short list of properties of the natural numbers, so short that every other fact about them can be proved from it. Then, for each property on the list, look at a system that has all the others but not that one. That shows what each property is for. It also shows the real moral of the 32-bit counter: a proof is valid for a system only if the system satisfies every property the proof used.

1.2The minimum logic for this chapter

This section collects the handful of logical ideas used in this chapter. Quantifiers and their negations, which matter enormously once limits appear, get a full chapter of their own later (2A.5 Quantifiers and the Shape of a Proof), placed just before the first ε–N arguments.

A statement is a sentence that is either true or false: "$3$ is a natural number", "every natural number is even". Sentences such as "$n$ is even" are not yet statements, because their truth depends on $n$. We call them properties of $n$ and write $P(n)$. Once you plug in a particular $n$, you get a statement $P(3)$, $P(7)$, …, each true or false.

Implication. "If $P$, then $Q$", written $P \implies Q$, is false in exactly one situation: when $P$ is true and $Q$ is false. In every other case it is true. In particular, an implication with a false hypothesis is automatically true ("vacuously true"). That convention may feel odd, but it is the only one that makes statements like "for every natural number $n$, if $n > 5$ then $n > 3$" true, which they obviously should be: for $n = 2$ the hypothesis fails, and the implication must not count as false just because of that.

Contrapositive versus converse. The statement $P \implies Q$ has the same truth value as its contrapositive, $\text{not } Q \implies \text{not } P$, so proving one proves the other. It does not have the same truth value as its converse, $Q \implies P$. "If it rained, the street is wet" is true; its converse "if the street is wet, it rained" is not (a water main may have burst); its contrapositive "if the street is dry, it didn't rain" is true.

For every. "For every natural number $n$, $P(n)$" is true when each of the statements $P(0), P(1), P(2), \dots$ is true. To show it is false, it is enough to find one $n$ for which $P(n)$ is false: a counterexample.

Proof by contradiction. To prove a statement $S$, assume that $S$ is false and deduce something impossible, for instance a statement and its negation. Since a correct argument from a true assumption cannot reach an impossibility, the assumption must have been false, so $S$ is true. Many proofs in this chapter are short arguments by contradiction.

That is all the logic needed now.

1.3Zero and the next number

Here is the idea we want to capture. The natural numbers are what you get by starting at $0$ and repeatedly taking "the next one": $0$, the next one after $0$, the next one after that, and so on. Everything about them should follow from those two ingredients: a starting point, and a way to step forward.

We write $n{+}{+}$ for "the next number after $n$", also called the successor of $n$.11 The notation $n{+}{+}$ is borrowed from programming languages, where it means "increase $n$ by one". It is the notation in Tao's Analysis I, which this book accompanies. Many logic books write $S(n)$ for the successor instead. It is important that $n{+}{+}$ is not defined as $n + 1$. Addition hasn't been defined yet. In fact we'll define addition using the successor, later in this chapter, and only then prove that $n{+}{+} = n + 1$.

These two axioms already produce infinitely many natural numbers: $0$; then $0{+}{+}$; then $(0{+}{+}){+}{+}$; and so on. To talk about them conveniently, we give them names.

With only Axiom 1.1 and Axiom 1.2 we can prove that $3$ is a natural number. By Axiom 1.1, $0$ is a natural number. Applying Axiom 1.2 to it, $1 = 0{+}{+}$ is a natural number. Applying Axiom 1.2 again, $2$ is, and once more, $3$ is.

That is a genuine proof, from the axioms, of something everybody knows. The point of doing it is to notice what we cannot yet prove. We can't prove that $3 \neq 0$, and we can't prove that the chain in Figure 1.2 never loops back on itself. Nothing in the two axioms forbids it.

A checked counter of this kind violates Axiom 1.2, and nothing else on our eventual list. Axiom 1.2 is the axiom that says: there is always a next one. No finite machine can satisfy it, which is one reason mathematics needs the natural numbers as an idealisation.

1.4Two axioms that keep the chain from looping

The 32-bit counter of Figure 1.1 satisfies both axioms so far: it has a $0$, and every value has a successor. So does the clock on a wall, if we call twelve o'clock "$0$". What goes wrong in those systems is that counting forward eventually brings you back to a number you have already met. Two more axioms rule that out. First, the chain can't loop back to its start:

Now we can prove that $3 \neq 0$: since $3 = 2{+}{+}$ is a successor, Axiom 1.3 says it can't equal $0$. But we still can't prove $4 \neq 1$. Nothing stops the chain from looping back to some later point, forming a shape like the letter ρ, with $3{+}{+} = 1$, say. The fourth axiom rules out every such merging:

Now $4 \neq 1$: if $4 = 1$ then $3{+}{+} = 0{+}{+}$, so by Axiom 1.4 $3 = 0$, contradicting what we just proved. The same argument shows that any two numerals with different names are different numbers. That is, $0, 1, 2, 3, \dots$ are all distinct (see Exercise 1.23).

With four axioms we have a chain that starts at $0$, never ends, never loops back to $0$, and never merges into itself. Is that enough? Not yet, and the reason is the most interesting part of the chapter.

1.5Induction: the axiom that says there is nothing else

Here is a system that satisfies all four axioms so far, but is still not the natural numbers. Take the usual numbers $0, 1, 2, 3, \dots$, and add the half-integers $\tfrac12, 1\tfrac12, 2\tfrac12, \dots$, with the successor of $x$ defined to be $x + 1$ in both rows (bottom-right panel of Figure 1.3). There is a $0$ (Axiom 1.1). Everything has a successor (Axiom 1.2). Nothing has $0$ as its successor (Axiom 1.3): the successor of a half-integer is a half-integer, and the successor of a whole number is at least $1$. And different elements have different successors (Axiom 1.4).

The half-integers are intruders. They are never reached by counting from $0$. We need an axiom saying that every natural number can be reached from $0$ by repeatedly taking successors. But "can be reached by repeatedly taking successors" is circular as it stands, because "repeatedly" already involves counting. The way out is to say it indirectly, through properties.

To see why this axiom excludes the intruders, apply it to the property

In the system above, $P(0)$ is true, and the successor of a whole number is a whole number, so $P(x) \implies P(x{+}{+})$. If the system satisfied Axiom 1.5, then every element would be a whole number. But $\tfrac12$ isn't. So the system fails Axiom 1.5.

The same argument works for any intruders. Take $P(x)$ to be "$x$ is one of $0, 0{+}{+}, (0{+}{+}){+}{+}, \dots$". Then $P(0)$ holds and $P$ is passed from each element to its successor, so Axiom 1.5 forces every element to have the property. Induction is exactly the axiom that says: there is nothing in the system except what counting from $0$ produces.

1.5.1What an induction proof looks like

Axiom 1.5 turns into a method of proof. To prove that a property holds for every natural number, you do two things:

1. Base case. Prove $P(0)$.
2. Inductive step. Prove that for every natural number $n$, if $P(n)$ is true then $P(n{+}{+})$ is true. In this step you assume $P(n)$ (the inductive hypothesis) and use it to prove $P(n{+}{+})$.

Then Axiom 1.5 gives $P(n)$ for every $n$.

The inductive step is a single argument that works for an arbitrary $n$, not an infinite list of arguments. That is the whole power of the method: one finite argument settles infinitely many statements.

Here is a first example, a fact so basic it is easy to overlook, proved carefully.

Notice that the inductive step didn't actually use the inductive hypothesis. That's unusual but perfectly legitimate. Notice too what the proposition says about the intruders of Figure 1.3: $\tfrac12$ is neither $0$ nor the successor of anything in that system, so the proposition fails there. This confirms again that the intruders violate induction.

Combining Proposition 1.2 with Axiom 1.4: every nonzero natural number is the successor of exactly one natural number, called its predecessor.

1.5.2Two ways to get induction wrong

Every proof by induction has two parts, and leaving out either one gives nonsense.

Omitting the base case. Consider the property "$n{+}{+} = n$". If it held for some $n$, then applying $++$ to both sides would give $(n{+}{+}){+}{+} = n{+}{+}$, so it would hold for $n{+}{+}$ too: the inductive step goes through. But the property is false for every $n$ (Exercise 1.25). The base case fails, and with it the whole proof. The saturating counter is a telling contrast: there $255{+}{+} = 255$ really does hold, but only because that system breaks Axiom 1.4.

An inductive step that secretly doesn't work for every $n$. The classic example is the "proof" that in any group of horses, all horses have the same colour. The base case is a single horse, which trivially has the same colour as itself. For the "inductive step", take a group of $n{+}{+}$ horses, remove one horse, and by hypothesis the remaining $n$ have the same colour. Put it back, remove a different horse, and again the remaining $n$ share a colour. Since the two groups overlap, all $n{+}{+}$ horses share a colour.

The overlap argument needs the two groups of $n$ horses to have a horse in common. When $n{+}{+} = 2$ the two groups are $\{\text{horse } A\}$ and $\{\text{horse } B\}$, which have no horse in common. The step from $1$ to $2$ fails, and every later step depends on it. The lesson: an inductive step must be valid for every $n$, including the smallest ones, and those are exactly where hidden assumptions break.

1.6Recursion: defining things one step at a time

Induction proves statements about every natural number. Its twin, recursion, defines things for every natural number: give the value at $0$, and give a rule for the value at $n{+}{+}$ in terms of the value at $n$.

It seems obvious that a recursive definition defines something. It is worth seeing that it needs every one of the axioms, because each failure is instructive.

The proof is short, but each axiom is visibly doing work, and each almost-system of Figure 1.3 shows what goes wrong without it.

• Without Axiom 1.3 (the wrap-around counter): try to define "the total number of ticks so far" on a clock face by $a_0 = 0$ and $a_{n{+}{+}} = a_n + 1$. Going round once, $a_{11} = 11$ and then $a_0 = a_{11{+}{+}} = 12$. But $a_0$ was already $0$. The definition contradicts itself. That is why a clock reading alone can't tell you how much time has passed, and why calendars and timestamps count something more.
• Without Axiom 1.4 (the saturating counter): in an 8-bit saturating counter, $255{+}{+} = 255$, so the same rule would require $a_{255} = a_{255} + 1$, which is impossible.
• Without Axiom 1.5 (the intruders): the rule defines $a_n$ for $n = 0, 1, 2, \dots$, but says nothing at $\tfrac12$. The "sequence" is undefined at some elements.

1.7Addition

Now we can define addition. The definition is a recursion in the first argument: adding $0$ does nothing, and adding the successor of $n$ means adding $n$ and then taking one more step.

For each fixed $m$, this is a recursive definition of the sequence $a_n = n + m$, with $a_0 = m$ and $a_{n{+}{+}} = (a_n){+}{+}$, so Proposition 1.3 guarantees it defines $n + m$ for every $n$. Concretely, $n + m$ is what you reach from $m$ after taking $n$ successor steps.

Everything you know about addition must now be proved. That is less tedious than it sounds, and it is the best possible practice in writing induction proofs, because the statements are so simple that all the attention goes to the structure of the argument. The definition treats the two arguments differently ($0 + m = m$ is a definition, but $m + 0 = m$ is not), so even that needs a proof.

As a first payoff: taking $m = 0$ in Lemma 1.6 and using Lemma 1.5, $n + 1 = n + (0{+}{+}) = (n + 0){+}{+} = n{+}{+}$. The successor of $n$ is $n + 1$, now as a theorem rather than an assumption.

The proof is Exercise 1.26: induct on $a$, keeping $b$ and $c$ fixed. Once addition is commutative and associative, brackets and order in a sum can be dropped, and we will do so from now on.

The next fact is where Axiom 1.4 enters arithmetic.

In the saturating counter, cancellation fails: $1 + 255 = 255 = 0 + 255$ there, yet $1 \neq 0$. A saturated sensor reading tells you that the true value was at least the maximum, but not what it was. That is a real problem in measurement, and it is exactly the failure of Proposition 1.9.

1.8Order

Order can be defined in terms of addition: $n$ is at least $m$ when you can get from $m$ to $n$ by adding something.

So $5 \geq 3$ because $5 = 3 + 2$. The basic properties all follow from the facts already proved:

The most important property of order is that any two numbers can be compared. Its proof is a good model of an induction in which the inductive step splits into cases.

1.8.1Strong induction and the well-ordering principle

Sometimes the inductive step needs more than the immediately preceding case. To prove something about $n$ you may want to know it for all smaller numbers. Factorising a number into primes is a typical example: $n$ factors as $a \times b$ with $a, b$ smaller than $n$, and you want to know the result for both $a$ and $b$, not just for $n - 1$.

Strong induction has an equivalent form that is often more convenient. It speaks about sets rather than properties.

The well-ordering principle has a vivid contrapositive form: there is no infinite strictly decreasing sequence of natural numbers. (Its values would form a nonempty set with no least element.) Fermat used this as a method of proof, calling it infinite descent: to show that no example of something exists, show that from any example you could build a strictly smaller one. You will use it in 2A.3 Integers and Rationals to prove that $\sqrt 2$ is irrational.

1.9Multiplication, division and powers

Multiplication is repeated addition, defined by recursion just as addition was repeated succession.

All the familiar laws follow by induction, each proof shaped like the corresponding one for addition. We state them together, prove the distributive law as a model, and leave the rest as exercises.

Part (6) is what allows dividing both sides of an equation by a positive number. It doesn't yet give division as an operation, because $7$ divided by $2$ is not a natural number. What the natural numbers do have is division with remainder.

The numbers $m$ and $r$ are in fact unique (Exercise 1.27); they are the quotient and the remainder.

Exponentiation is defined by one more recursion.

So $2^3 = 2^2 \times 2 = (2^1 \times 2) \times 2 = ((1 \times 2) \times 2) \times 2 = 8$. The usual laws $m^{a + b} = m^a \times m^b$ and $(m^a)^b = m^{a \times b}$ are proved by induction on $b$ (Exercise 1.28). The pattern is now clear: successor builds addition, addition builds multiplication, multiplication builds powers, each by a single recursion, and every law about them is a theorem proved by induction.

1.10Before the axioms: where this came from

1.11Exercises

The exercises are part of the chapter. The first group makes the axioms concrete, the second practises induction, and the last rehearses an argument from much later in the route. Try each one before opening its hint.

Hint

Every pair involving $0$ is handled by Axiom 1.3. For a pair like $4$ and $2$, apply Axiom 1.4 repeatedly to strip off successors until one side is $0$.

Solution

$1, 2, 3, 4$ are successors, so none equals $0$ (Axiom 1.3). If $4 = 2$, then $3{+}{+} = 1{+}{+}$, so $3 = 1$ by Axiom 1.4, so $2 = 0$ by Axiom 1.4 again, contradicting Axiom 1.3. Every pair is handled the same way: if numerals with $k$ and $j$ successor symbols ($k > j$) were equal, removing $j$ successors from both sides with Axiom 1.4 would make a successor equal to $0$.

Solution

In the wrap-around counter $\{0, \dots, 5\}$, suppose $P(0)$ holds and $P(x) \implies P(x{+}{+})$ for all $x$. Then $P(1), \dots, P(5)$ follow one at a time, and those are all the elements. So Axiom 1.5 holds, because every element is reached from $0$; the system merely comes back to $0$ as well. In the saturating counter $\{0, \dots, 3\}$ with $3{+}{+} = 3$, $0$ is not a successor and every element is reached from $0$, but $2{+}{+} = 3{+}{+}$. In the checked counter, $3{+}{+}$ doesn't exist, so Axiom 1.2 fails, while the other conditions hold for every element where they make sense. In the system with intruders, see the discussion after Axiom 1.5.

Solution

Induction on $n$. Base case: $0{+}{+} \neq 0$ by Axiom 1.3. Inductive step: suppose $n{+}{+} \neq n$. If $(n{+}{+}){+}{+} = n{+}{+}$, then by Axiom 1.4 $n{+}{+} = n$, contradicting the hypothesis. The proof uses Axiom 1.3, Axiom 1.4 and Axiom 1.5, and the saturating counter breaks Axiom 1.4.

Hint

Fix $b$ and $c$ and induct on $a$. The definition of addition peels successors off the left argument, so that is the one to induct on.

Solution

Base case: $(0 + b) + c = b + c = 0 + (b + c)$. Inductive step: if $(a + b) + c = a + (b + c)$, then $((a{+}{+}) + b) + c = ((a + b){+}{+}) + c = ((a + b) + c){+}{+} = (a + (b + c)){+}{+} = (a{+}{+}) + (b + c)$, using the definition three times and the hypothesis once.

Hint

If $m q + r = m' q + r'$ with $r, r' < q$ and, say, $m < m'$, then $m' = m + d$ with $d \geq 1$. Show that this forces $r \geq q$.

Hint

Suppose $P(0)$ holds and $P(n) \implies P(n{+}{+})$, but $P$ fails somewhere. Apply well-ordering to the set of numbers where $P$ fails. Its least element can't be $0$, so it is a successor $n{+}{+}$. What do you know about $n$?

Solution

The step fails at $n = 1$. The only ways to write $1 = a + b$ are $0 + 1$ and $1 + 0$, and in each, one of the summands is not smaller than $n$. The sentence "write $n = a + b$ with $a < n$ and $b < n$" is false for $n = 1$. For $n \geq 2$ it is possible ($n = 1 + (n - 1)$), but that is too late: the chain from $0$ to every other number passes through $1$. Like the horses, the flaw sits at the smallest case.

Solution

Base case: $C_0 \leq M = 0!\,M$. Inductive step: if $C_k \leq k!\,M$, then $C_{k{+}{+}} \leq (k+1)\,C_k \leq (k+1)\,k!\,M = (k{+}{+})!\,M$. Without an estimate linking $C_1$ to $C_0$, the chain of inequalities has nowhere to start: the conclusion holds for $k \geq 1$ only if $C_1$ is controlled some other way. The base case of the derivative ladder matters as much as the step. In Shi's estimates the base case is the curvature bound itself, and the step is a maximum-principle argument, which you will meet in 6A.6 Parabolic Regularity.