Bridge to Abstract Mathematics: Mathematical Proof and Structures

10.1 AN AXlOMATlZATlON FOR THE SYSTEM OF POSITIVE INTEGERS 333

and called "addition to m." Intuitively, our goal is that s,(n) should equal
m + n for any n E N, but, of course, + is exactly what we're trying to define.
We have no tools at our disposal by which to define s,(n) explicitly. What
we have is a successor function and an induction property; the proposed
solution is to define s,(n) inductively (or recursively). What this means is
that we define s,(n) explicitly for n = 1; then, assuming that s,(n) has been
defined for an arbitrary n E N, we define s,(o(n)) in terms of s,(n). We must
do two things to carry out this program successfully: (1) come up with rea-
sonable definitions of s,(l) and s,(a(n)), the latter assuming that s,(n) has
been defined and (2) prove existence and uniqueness of a mapping satisfying
the properties specified in our definition. Let us deal with the first problem
immediately. Experience tells us that we want s,(l) to equal m + 1. For-
tunately, we can formulate this idea in language available to us, namely,
s,(l) = o(m). Now suppose that s,(n) has been defined; for familiarity sake,
let us denote its value by m + n. How then should we define s,(a(n))? That
is, what is the value of m + (n + I)? Why not (m + n) + l? That is, s,(o(n)) =
o(s,(n)). These definitions are used in the following important theorem.

THEOREM 3

If m E N, then there exists a unique mapping s,: N -+ N satisfying

(i) sm(l) = a(m), and

(ii) sm(a(n)) = a(s,(n)) for each n E N.

Proof (Existence) The proof is quite abstract and makes use, at several

stages, of the induction postulate. Let m be an arbitrary positive inte-

ger. We begin by considering the collection of all subsets r, of N x N

satisfying the properties (i)' (1, a(m)) E r,, and (ii)' (n, p) E r, implies

(o(n), o(p)) E r, for each n, p E N. Note that (i)' and (ii)' are simply (i)

and (ii), with functional notation replaced by the more general ordered

pair notation, appropriate for a relation that may not be a function.

Note also that this collection is nonempty, since N x N itself satisfies

(i)' and (ii)'. Let s, equal the set theoretic intersection of all relations on

N satisfying (i)' and (ii)'. It is easy to show [with verification left to you

in Exercise 2(a)] that s, satisfies (i)' and (ii)', and furthermore, is a subset

of any relation on N satisfying (i)' and (ii)'. For the latter reason, we

say that s, is the smallest relation on N satisfying (i)' and (ii)'; this prop-

erty of s, will be a key later in the proof. We claim now that this s, is

the desired mapping of N into N. Since s, is known to satisfy (i)' and

(ii)', we need only verify that s, actually is a mapping on N. In other

words, we must verify:

dom (s,) = N; that is, for any n E N, there exists p E N such that

(n, p) E S,, and

s, is a function; that is, if n, p, q E N with (n, p) E S, and (n, q) E s,,

then p = q.