Bridge to Abstract Mathematics: Mathematical Proof and Structures

336 CONSTRUCTION OF NUMBER SYSTEMS Chapter 10

T H E 0 RE M 4 (Principle of Inductive Definition)

Let f: N -, N be an arbitrary mapping and let a E N be given. Then there exists

a mapping cp of N into N, uniquely determined by f and a, such that:

(i) q(l) = a, and

(ii) cp(a(n)) = f(rp(n)) for all n E N

A function cp, defined as in Theorem 4, is said to have been defined by
induction or recursively. As we suggested just before stating Theorem 4, the
"sum to m" function s, was defined by induction. In that case, for a given
m E N, we had a = dm) and f (p) = a(p) for each p E N. Other familiar
functions with domain N may be defined formally in a recursive manner,
among these factorial, nth power, and the nth Fibonacci number (see Exercise
1). The inductive definition of "product with m," denoted p,,,, is most ger-
mane to our current considerations.

DEFINITION 2

For a fixed m E N, we defined the function "product with m, "denoted p,, in-

ductively by the rules p,(l) = m and p,(a(n)) = p,(n) + m, for any n E N. Given

two positive integers m and n, we define their product p(m, n) (usually denoted

m - n or simply mn) by the rule p(m, n) = p,(n).

Note that multiplication by m is defined by applying Theorem 4 with a =

m and f(p) = p + m. You should formulate closure and well-definedness

statements for the product, analogous to those stated for the sum in the

corollary to Theorem 3.

With addition and multiplication now defined, we turn to properties of

these operations. As we work toward these properties, it will prove useful to

have at our disposal translations of the defining properties from functional

to operational notation. For this purpose, we note that the addition and

multiplication operations are defined by the equations (for all m, n E N):

m+l=a(m)

m+(n+ l)=(m+n)+ 1

m.l=m

m.(n + 1) = mn + m

THEOREM 5

Let n, p, 9 E N. Then:

(a) (n + P) + 9 = n + (P + 9)

(b) n+p=p+n

(c) n+p+n

(d) If n + q = p + q, then n = p

(addition is associative)

(addition is commutative)

(there is no additive identity in N)

(additive cancellation)