TSR Wiki > Study Help > Subjects and Revision > Revision Notes > Mathematics > Natural Numbers, Induction and Counting

This page should be treated as a follow-on to the page on Foundations. It builds on the idea of sets, relations and functions to define what we mean by a number, and the natural numbers in particular. These notes are partly based on a course by Tim Gowers that I took in my first year of studying mathematics at Cambridge, partly based on the book An Introduction To Mathematical Philosophy by Bertrand Russell, and partly from my own mind.

The Natural Numbers

The Peano axioms

Guiseppe Peano was an Italian mathematican in the late 19th and early 20th centuries. In 1889 he published a paper which gave five rules from which you were supposed to be able to deduce any fact about the natural numbers. These rules were so succesful that they came to be named in honour of him, as the Peano axioms.

To specify what we mean by the natural numbers , Peano says that we only need to know what three things are. Loosely speaking, we need to know what we mean by the number 0, we need to know what we mean by a number, and we need to know how to add 1 to a number. The first one is quite easy -- we all have an inutitive grasp of what zero is. For the second one, we just say that a number is a member of . We have to be a little bit more specific with the last one. We haven't decided what we mean by addition yet, so we can't just say we 'add 1' to get to the next number. Instead we work with a function σ from to , which we call the successor function. Intuitively we think of this as taking each number to the next one, although we don't need to know this to work with the Peano axioms.

The Peano axioms say that is a set with a function σ : , satisfying:

(1) 0 ∈ ,

(2) If n ∈ , then σ(n) ∈ ,

(3) For all m,n ∈ , if σ(m) = σ(n), then m = n,

(4) There is no n ∈ such that σ(n) = 0, and

(5) If S is a subset of such that 0 ∈ S, and if n ∈ S σ(n) ∈ S, then S = .

Rule (5) is called the inductive rule, and it is this which lets us use mathematical induction to prove things. It basically says that if σ(n) has a property whenever n has that property, and if 0 has that property, then every natural number has that property.

Let's spend a little time thinking about how the theory of the natural numbers comes from these five rules. Firstly, it is clear that we can carry on counting forever. We define 1 as the successor of 0, 2 as the successor of 1 etc. Because of rule (2), we can always go to the next number. Because of rule (3) this can't be any of the numbers that we've reached already, because if it were then two numbers would have the same successor. Because of rule (4), we never get back to 0. Therefore we get an endless series of new numbers.

It is also clear that if we keep counting for long enough, we can reach any natural number. By rule (1), 0 is a number. If n is a number then σ(n) is a number, by rule (2). But then by rule (5), every n belongs to the series that we get by taking successive successors, and so every n is a number.

Arithmetic with the Peano axioms

Now that we have defined the natural numbers using the Peano axioms, we can begin to think about how we do arithmetic with them. The first thing that we'd like to know how to do is add two numbers together. One of the most important properties of the natural numbers is property (5), the inductive property. This suggests that to get a useful idea of addition, we might have to define it inductively, using the successor function.

We can define addition as follows:

• Define m + 0 = m for every m ∈ .
• Define m + σ(n) = σ(m + n) for every m,n ∈ .

Because of property (5), this gives a definition of m + n for any pair of natural numbers m and n. We could define multiplication in a similar way:

• Define m 0 = 0 for every m ∈ .
• Define m σ(n) = m + (m n) for every m,n ∈ .

Because of property (5), this gives a definition of m n for any pair or natural numbers m and n. From these definitions we can prove all kinds of arithmetical facts. For example, suppose that we want to prove that m + n = n + m, i.e. that addition is commutative.

Theorem: Addition is commutative.

Proof: We do this in three steps:

  1. We show that 1 + m = m + 1. If m = 1 then this is obviously true. If it is true for m, then 1 + σ(m) = σ(1 + m) = σ(m + 1) = σ(σ(m)) = σ(m) + 1. Therefore it is true for σ(m). Thus by property (5) it is true for all m.

  2. We show that m + σ(n) = σ(m) + n. If n = 1 then σ(m) + 1 = σ(σ(m)) = σ(m+1) = m + σ(1), so it is true. If it is true for n, then σ(m) + σ(n) = σ(σ(m) + n) = σ(m + σ(n)) = m + σ(σ(n)), so it is true for σ(n). Thus by property (5) it is true for all n.

  3. We show that m + n = n + m. If n = 1 then it is true, as we showed in part 1. If it is true for n, then m + σ(n) = σ(m + n) = σ(n + m) = n + σ(m) = σ(n) + m, so it is true for σ(n). Thus it is true for all n, by property (5). Thus addition is commutative.

Peano proved a whole host of other facts about arithmetic, including:

• Addition is commutative and associative.
• Multiplication is commutative and associative.
• 0 is an identity for addition.
• 1 is an identity for multiplication.
• Multiplication is distributive over addition, i.e. a(b + c) = ab + ac.
• Cancellation laws, a + c = b + c a = b, and ac = bc either c = 0 or a = b.

The proofs of these shouldn't be too hard, but the precise details aren't that important so we'll skip over them. What's important is that with just three ideas and five rules, we can prove lots of statements about arithmetic.

As a final point, notice that we can define an order relation on the natural numbers, by saying that m < n if these is a natural number a, which is not 0, such that m + a = n. You can check that this is transitive, antisymmetric and total.

Problems with the Peano axioms

We would like the Peano axioms to specify a unique set which we can then call the natural numbers, and use to do counting. Unfortunately this isn't the case, and it is one of the biggest problems with Peano arithmetic. For example, if we take "0" to be the number one (bear with me, this will make sense...), take our definition of "number" to be the set 1, 1/2, 1/4, 1/8, 1/16, ... and our successor function to be "divide by two" then this new set satisfies all of the Peano axioms. You might think that it doesn't satisfy rule (4), since 1 is the successor of 2 (since half of two is one). However, the number two is not a "number" in the sense that we have defined it here, and so 1 is not the successor of any number.

As another example, we could take "0" to be the number 0 as before, take our definition of "number" to be a member of the set of even numbers, and take our successor function to be "add two". Then the new set that we get is 0, 2, 4, 6, 8, ... and this still satisfies all of Peano's five axioms.

The point is that our interpretation of what we mean by "0", "number" and "successor" is not defined by any of Peano's five axioms, and so the axioms are capable of any number of interpretations. This is problematic! We want our system of counting to actually correspond to what we know about the world, and not just to satisfy an abstract set of mathematical formula. For example, we want our system of numbers to say that we have two eyes and two ears, and that there are three mugs of cold coffee sitting on my desk. The set 1, 1/2, 1/4, 1/8, ... satisfies Peano's five rules, but it is no good to do counting with.

We can say that we "just know" what we mean by the number 0, and in fact it is perfectly fine to do this and just get on with our everyday lives. However, the point of studying the foundations of mathematics is to put off saying this as long as possible. So can we express what we mean by "0", "number" and "successor" in terms of even simpler ideas?