10.1 AN AXlOMATlZATlON FOR THE SYSTEM OF POSITIVE INTEGERS 341prove this fact and, for good measure, introduce another form of the in-
duction postulate in the next theorem.
THEOREM 11
The following three statements about the set N are equivalent:
(a) The induction postulate (IP)
(b) The well-ordering principle (WOP)
(c) The second induction principle (IP2). Any set S of positive integers satis-
fying (i) 1 E S and (ii) for any m E N, k E S for each k E (1, 2,... , m) implies
m + 1 E S, equals N.Proof (a) =. (b) If (b) is false, then there is a nonempty subset S of N having
no smallest element. Hence if a positive integer m has the property that
m < s for all s E S, we must have m q! S. Let M be the set of all such
positive integers (i.e., M = (m E N 1 m < s V s E S}); clearly M n S = 0.
We claim that M = N. In support of this claim, note first that 1 E M.
Since 1 is the smallest element of N and 1 4 S (otherwise 1 would be the
smallest element of S), then surely 1 < s for all s E S. Second, suppose
m E M, so that m < s for all s E S. Then m + 1 < s for all s E S, by
Exercise 7(f). If m + 1 E S, then m + 1 would be the smallest element of
S. Hence m + 1 q! S and we may assert m + 1 < s for all s E S. Hence
m + 1 E M, so that we may conclude M = N. Since M n S = /21 and
M = N, S must be empty, contradicting the initial assumption that S is
nonempty.
(b) (c) Assume S satisfies (i) and (ii) of (c). If S # N, then N - S
is nonempty. By WOP, N - S has a smallest element , call it so. Note
that so # 1, by (i). For all positive integers k such that k I so - 1, we
have k E S. Hence so E S, by (ii), contradicting the fact that so E N - S.
Hence N - S is empty and S = N, as desired.
(c) * (a) Let S be a subset of N satisfying the properties 1 E S and
m E S implies m + 1 E S for all m E N. We must prove S = N. Now
suppose that for each k E N such that k 5 m, we have k E S. Then
surely m E S so that, by our assumption, m + 1 E S. Hence S satisfies (ii)
of (c). Since S satisfies (i) of (c), by our assumption, we may conclude,
by (c), that S = N. 0
Note that the induction postulate [(a) in Theorem 11 and (b) of Axiom
11 is the same as the principle of mathematical induction we used exten-
sively in Article 5.4. (We, now know that a(m) and m + 1 are synonymous.)
Our approach in this article has been to assume this property as one of the
axioms defining N. Theorem 11 shows, among other things, that the well-
ordering principle could just as well be assumed as an axiom for N, in which
case IP could be proved as a theorem. Many texts adopt this approach;
in Exercise 8, you are asked to write a proof deriving IP directly from WOP.