1.2. The Natural Numbers 9

The following theorem states the mathematical induction principle as it applies

to proving propositions.

Theorem 1.2.1. Suppose {Pn} is a sequence of statements, one for each n ∈ N.

These statements are all true provided

(1) P1 is true (the base case is true); and

(2) whenever Pn is true for some n ∈ N, then Ps(n) is also true (the induction

step can be carried out).

Proof. Let A be the subset of N consisting of those n for which Pn is true. Then

hypothesis (1) of the theorem implies that 1 ∈ A, while hypothesis (2) implies that

s(n) ∈ A whenever n ∈ A. By axiom N5, A = N, and so Pn is true for every n.

Example 1.2.2. Prove that each n ∈ N is either 1 or is the successor of some

element of N.

Solution: If n is 1, then the statement is obviously true. Thus, the base case

is true. If the statement is true of n, then it is certainly true of s(n), because it is

true of any element which is the successor of something in N. Thus, by induction,

the statement is true for every n ∈ N.

Another way to say what was proved in this example is that every natural

number except 1 has a predecessor. This statement doesn’t seem obvious at this

stage of development of N, but its proof was a rather trivial application of induction.

Inductive Definitions. Inductive definitions are used to define sequences. The

sequence {xn} to be defined is a sequence of elements of some set X, which may or

may not be a set of numbers. We wish to define the sequence in such a way that

x1 is a specified element of X and, for each n ∈ N, xs(n) is a certain function of xn.

That is, we are given an element x1 ∈ X and a sequence of functions fn : X → X

and we wish to construct a sequence {xn}, beginning with x1, such that

(1.2.1) xs(n) = fn(xn) for all n ∈ N.

This equation, defining xs(n) in terms of xn, is called a recursion relation. Se-

quences defined in this way occur very often in mathematics. Newton’s method

from calculus and Euler’s method for numerically solving differential equations are

two important examples.

Theorem 1.2.3. Given a set X, an element x1 ∈ X, and a sequence {fn} of

functions from X to X, there is a unique sequence {xn} in X, beginning with x1,

which satisfies xs(n) = fn(xn) for all n ∈ N.

Proof. Consider the Cartesian product N×X – that is, the set of all ordered pairs

(n, x) with n ∈ N and x ∈ X. We define a function S : N × X → N × X by

(1.2.2) S(n, x) = (s(n),fn(x)).

We say that a subset E of N × X is closed under S if S sends elements of E to

elements of E. Clearly the intersection of all subsets of N × X that are closed

under S and contain (1,x1) is also closed under S and contains (1,x1). This is the

smallest subset of N × X that is closed under S and contains (1,x1). We will call