20 CHAPTER 1. PRELIMINARIES

1.9 Well Ordering and Archimedean Property

Definition 1.9.1 A set is well ordered if every nonempty subset S, contains a smallestelement z having the property that z ≤ x for all x ∈ S.

Axiom 1.9.2 Any set of integers larger than a given number is well ordered.

In particular, the natural numbers defined as

N ≡{1, 2, · · · }

is well ordered.The above axiom implies the principle of mathematical induction.

Theorem 1.9.3 (Mathematical induction) A set S ⊆ Z, having the property that a ∈ Sand n+ 1 ∈ S whenever n ∈ S contains all integers x ∈ Z such that x ≥ a.

Proof: Let T ≡ ([a,∞) ∩ Z) \ S. Thus T consists of all integers larger than or equalto a which are not in S. The theorem will be proved if T = ∅. If T ̸= ∅ then by the wellordering principle, there would have to exist a smallest element of T, denoted as b. It mustbe the case that b > a since by definition, a /∈ T. Then the integer, b− 1 ≥ a and b− 1 /∈ Sbecause if b − 1 ∈ S, then b − 1 + 1 = b ∈ S by the assumed property of S. Therefore,b− 1 ∈ ([a,∞) ∩ Z) \ S = T which contradicts the choice of b as the smallest element of T.(b− 1 is smaller.) Since a contradiction is obtained by assuming T ̸= ∅, it must be the casethat T = ∅ and this says that everything in [a,∞) ∩ Z is also in S. ■

Example 1.9.4 Show that for all n ∈ N, 12 · 3

4 · · ·2n−12n < 1√

2n+1.

If n = 1 this reduces to the statement that 12 <

1√3which is obviously true. Suppose

then that the inequality holds for n. Then

1

2· 34· · · 2n− 1

2n· 2n+ 1

2n+ 2<

1√2n+ 1

2n+ 1

2n+ 2=

√2n+ 1

2n+ 2.

The theorem will be proved if this last expression is less than 1√2n+3

. This happens if and

only if (1√

2n+ 3

)2

=1

2n+ 3>

2n+ 1

(2n+ 2)2

which occurs if and only if (2n+ 2)2> (2n+ 3) (2n+ 1) and this is clearly true which may

be seen from expanding both sides. This proves the inequality.

Definition 1.9.5 The Archimedean property states that whenever x ∈ R, and a > 0, thereexists n ∈ N such that na > x.

Proposition 1.9.6 R has the Archimedean property.

Proof: Suppose it is not true. Then there exists x ∈ R and a > 0 such that na ≤ xfor all n ∈ N. Let S = {na : n ∈ N} . By assumption, this is bounded above by x. Bycompleteness, it has a least upper bound y. By Proposition 1.8.3 there exists n ∈ N suchthat

y − a < na ≤ y.

Then y = y − a+ a < na+ a = (n+ 1) a ≤ y, a contradiction. ■