1549901369-Elements_of_Real_Analysis__Denlinger_

1.3 Natural Numbers 25

*Proof. Suppose p(n) satisfies c~nditions (1) and (2) above. Let q(l) de-

note p(l), and for k ~ 2 let q(k) denote the statement "p(m) is true for all

natural numbers m < k." Then,

(i) q(l) is true;

(ii) Vk EN, q(k)::::} p(m) is true for all natural numbers m < k

::::} p(k) is true by condition (2) above K ~

1. -s 6 7 ::::} p( k) is true for all natural numbers In < k + 1
   ::::} q(k + 1).
   Therefore, by the principle of mathematical induction (1.3.6), Vn E N, q(n)
   is true, from which it follows that Vn E N, p(n) is true. •

The following property is closely related to the principle of mathemati-

cal induction, and is one of the principle characteristics of the set of natural

numbers.

Theorem 1.3.10 (Well-Ordering Property) Every nonempty set of natural

numbers has a smallest element.

*Proof. Let A be a nonempty subset of N. For contradiction, suppose that

A does not have a smallest element. Let

S=N-A.

Then

(1) 1 tJ_ A, since if 1 E A it would be the smallest element of A. So,

1 ES.

(2) Suppose 1, 2, · · · , k E S. Then, 1, 2, · · · , k tJ_ A. Thus, k + 1 tJ_ A,

since if k EA it would be the smallest element of A. Thus, k ES.

By (1), (2) and the alternate principle of mathematical induction, Vn E N,

n E S. Therefore, S = N, and so A = 0. Contradiction. Therefore, A must

have a smallest element. •

The Principle of Mathematical Induction, as presented in Theorem 1.3.6,
establishes the truth of p(n), for all integers n starting with n = 1. However,
there is no reason why we must start with n = 1. We could use any natural
number as a starting point. The following theorem expresses this fact.

Theorem 1.3.11 (Principle of Mathematical Induction For n ;:::: no)

Suppose no EN and V natural numbers n ~no, p(n) is a proposition about

n. If

(1) p(no) is true, and

(2) Vk EN 3 k ~ n 0 , p(k)::::} p(k+ 1),

then Vn ~no in N, p(n) is true.