10 1. The Real Numbers

this set A. Note that (1,x1) is the only element of A which is not in the range of S.

This is because any other such element could be removed from A and the resulting

set would still contain (1,x1) and be closed under S.

To complete the argument, we will show that the set A is the graph of a function

from N to X – that is, it has the form {(n, xn) : n ∈ N} for a certain sequence

{xn} in X. This is the sequence we are seeking. To prove that A is the graph of a

function from N to X, we must show that each n ∈ N is the first element of exactly

one pair (n, x) ∈ A. We prove this by induction.

The element 1 is the first element of the pair (1,x1), which is in A by the

construction of A. If there were another element x ∈ X such that (1,x) ∈ A, then

(1,x) would be an element, not equal to (1,x1), which fails to be in the range of S.

This is due to the fact that 1 is not the successor of any element of N by N3.

Now, for the induction step, suppose for some n we know that there is a unique

element xn ∈ X such that (n, xn) ∈ A. Then S(n, xn) = (s(n),fn(xn)) is in A.

Suppose there is another element (s(n),x) ∈ A with x = fn(xn) and suppose this

element is in the image of S – that is, (s(n),x) = S(m, y) = (s(m),fm(y)) for some

(m, y) ∈ A. Then n = m by N4, and y = xn by the induction assumption. Thus

if (s(n),x) is really different from (s(n),fn(xn)), then it cannot be in the image of

S. Since (1,x1) is the only element of A which is not in the image of S and since

s(n) = 1, we conclude there is no such element (s(n),x). By induction, for each

element of N there is a unique element xn ∈ X such that (n, xn) ∈ A. Thus, A is

the graph of a function n → xn from N to X.

This shows the existence of a sequence with the required properties. We leave

the proof that this sequence is unique to the exercises.

Note that the proof of the above theorem used all of Peano’s axioms, not just

N5.

Using Peano’s Axioms to Develop Properties of N. In this subsection, we

will demonstrate some of the steps involved in developing the arithmetic and order

properties of N using only Peano’s axioms. It is not a complete development, but

just a taste of what is involved. We begin with the definition of addition.

Definition 1.2.4. We fix m ∈ N and define a sequence {m + n}n∈N inductively as

follows:

(1.2.3) m + 1 = s(m),

and

(1.2.4) m + s(n) = s(m + n).

These two conditions determine a unique sequence {m + n}n∈N by Theorem 1.2.3.

Note that (1.2.4) is the recursion relation of the inductive definition. It tells us how

m + s(n) is to be defined assuming that m + n has already been defined.

By (1.2.3) of the above definition, the successor s(n) of n is our newly defined

n + 1. At this point we will begin using n + 1 in place of s(n) in our inductive

arguments and definitions.