Peano!

You might recall our previous discussions of fields. We eventually got as far as being able to define a complete, ordered field and show that the real numbers are an example of it. That was in a sense, a top-down approach. We started with a complicated set of axioms that define the behavior we want. Starting today, we’re going to go bottom-up: we’ll start with a system that obeys very simple axioms, and gradually construct one with the desired complex behavior.

The system we’re starting with is called Peano arithmetic, and it describes a system very much like the natural numbers, which consist of 0, 1, 2, .etc. [1] It has a very simple language:

There are only three axioms:

Let’s do a simple example to explore axiom 3. Suppose we define U as the set of numbers that either equal 0 or have a predecessor. Does the axiom apply?

Thus, by Axiom 3, all numbers x are members of U.


If we think of

0, S(0), S(S(0[/efn_note], S(S(S(0[/efn_note]), …

as a line, we can picture its shape. Because of axiom 1, it never loops back to the beginning. Because of axiom 2, it never loops back at any other point either. And because of axiom 3, since 0 is on the line and all the successors are on the line, every number is on this one line. [2] So it looks a lot like our familiar number line that starts at 0 and goes infinitely to the right.

Of course, the fact that we’re calling them numbers and in particular calling the first one “0” doesn’t mean that they act anything like the numbers we’re used to: we need to prove that. For instance, we should be able to add and subtract and multiply and divide them. Let’s start out simply, by defining addition:


Addition:

Since, as we proved above, every number either is 0 or has a predecessor, we have just defined addition for all numbers. Now we’d like to prove that addition behaves as it should, for instance, that it’s commutative. This is a bit tedious, because we have so little machinery to work with. First, we prove it when one number is 0:


Define the set U as the numbers that commute additively with 0.
From the definition of addition, 0 + 0 = 0. 0 is a member of U.
Now, suppose that for some a, 0 + a = a. We know that 0 + S(a) = S(0 + a) = S(a + 0) = S(a) = S(a) + 0
That is if a is a member of U, so is S(a).
Thus, by Axiom 3, it's true for all n that n + 0 = 0 + n.


Now we’ll prove that when we’re adding two numbers, we can move the S() operator between them:


Define the set V as the numbers v for which S(m) + v = m + S(v) for any m.
Let v be 0. Then S(m) + 0 = S(m) = S(m + 0) = m + S(0). So 0 is a member of V.
Suppose v is in V, that is S(m) + v = m + S(v) for any m.
Then S(m) + S(v) = S(S(m) + v) = S(m + S(v[/efn_note] = m + S(S(v[/efn_note]
So S(v) is in V, and it's true for all m and n that m + S(n) = S(m) + n


Now we have what we need to prove that addition commutes for all numbers.


Define U as the set of numbers u for which u + n = n + u for any n.
We showed above that 0 is a member of U.
Suppose u is in U, that is u + m = m + u for any m.
Then n + S(u) = S(n + u) = S(u + n) = u + S(n) = S(u) + n, and S(u) is in U.
Thus all numbers are in U, and addition is commutative.


We can use the same kind of induction to prove that addition is associative ( (a + b) + c = a + (b + c) ). If we define multiplication is the obvious way:

• for all numbers n, n * 0 = 0
• for all numbers m and n, m * S(n) = (m * n) + m

then we can use induction to prove that it has the properties we expect (commutative, associative, distributes over addition.) As a taste, here’s the proof that 0 * n = 0:


Let I be the set of numbers for which 0 * n = 0.
Obviously 0 is in I, since 0 * 0 = 0.
If i is in I, then 0 * S(i) = (0 * i) + 0 = 0 + 0 = 0
This all numbers are in I, and for all n, 0 * n = 0.


and the proof that S(0) (also known as 1) is the multiplicative identity.


For all m, m * S(0) = (m * 0) + m = 0 + m = m. So S(0) is a right identity.
Now consider the set Q for which S(0) is a left identity, that is for which S(0) * q = q.
Clearly 0 is in Q, since S(0) * 0 = 0 = 0 * S(0)
For any q in Q, S(0) * S(q) = (S(0) * q) + S(0) = q + S(0) = S(q).
So S(0) is a left identity too, and n = S(0) * n = n * s(0) for all n.


The Peano numbers don’t form a field or even a group (the absence of negative numbers means no additive inverses), but they do have the following properties, which show that we’re headed in the right direction:


A1: Addition is commutative: for all x and y, x + y = y + x
A2: Addition is associative: for all x and y, (x + y) + z = x + (y + z)
A3: The field contains an additive identity: there exists a member 0 such that for all x, x + 0 = x
M1: Multiplication is commutative: for all x and y, x * y = y * x
M2: Multiplication is associative: for all x and y, (x * y) * z = x * (y * z)
M3: The field contains an multiplicative identity not equal to the additive identity: there exists a member 1 ≠ 0 such that for all x, x * 1 = x. (Recall that 1 is another name for S(0). We know that 1 ≠ 0 because 1 has a predecessor and 0 does not.)
D1: Multiplication distributes over addition: for all x, x, and z, x * (y + z) = (x * y) + (x * z)


Next time, we’ll see how to construct negative numbers.

[1]Of course, Peano arithmetic only lets you count up to 88.
[2]There are some complicated reasons why that last sentence might not be true, but for our purposes we can ignore them.