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
Previous Page Next Page