1.9 Well Ordering And Archimedean Property
Definition 1.9.1 A set is well ordered if every nonempty subset S, contains a smallest
element 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
is well ordered.
The above axiom implies the principle of mathematical induction.
Theorem 1.9.3 (Mathematical induction) A set S ⊆ ℤ, having the property that a ∈ S
and n + 1 ∈ S whenever n ∈ S contains all integers x ∈ ℤ such that x ≥ a.
Proof: Let T ≡
. Thus T
consists of all integers larger than or equal to
which are not in S.
The theorem will be proved if T
then by the well
ordering principle, there would have to exist a smallest element of T,
denoted as b.
must be the case that b > a
since by definition, a
Then the integer, b −
1 ≥ a
because if b −
1 ∈ S,
then b −
1 + 1 = b ∈ S
by the assumed property of S.
Therefore, b −
which contradicts the choice of b
as the smallest
element of T.
1 is smaller.) Since a contradiction is obtained by assuming T≠∅,
must be the case that T
and this says that everything in [a,∞
) ∩ ℤ
is also in S
Example 1.9.4 Show that for all n ∈ ℕ,
If n = 1 this reduces to the statement that
which is obviously true. Suppose then that
the inequality holds for
The theorem will be proved if this last expression is less than
This happens if and only
which occurs if and only if
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 ∈ ℝ, and a > 0, there
exists n ∈ ℕ such that na > x.
Proposition 1.9.6 ℝ has the Archimedean property.
Proof: Suppose it is not true. Then there exists x ∈ ℝ and a > 0 such that na ≤ x
for all n ∈ ℕ. Let S =
By assumption, this is bounded above by x
completeness, it has a least upper bound y
. By Proposition 1.8.3
there exists n ∈ ℕ
Then y = y − a + a < na + a =
a ≤ y,
a contradiction. ■
Theorem 1.9.7 Suppose x < y and y − x > 1. Then there exists an integer l ∈ ℤ, such
that x < l < y. If x is an integer, there is no integer y satisfying x < y < x + 1.
Proof: Let x be the smallest positive integer. Not surprisingly, x = 1 but this can be proved. If
x < 1 then x2 < x contradicting the assertion that x is the smallest natural number. Therefore, 1
is the smallest natural number. This shows there is no integer, y, satisfying x < y < x + 1
since otherwise, you could subtract x and conclude 0 < y − x < 1 for some integer
y − x.
Now suppose y − x > 1 and let
The set S is nonempty by the Archimedean property. Let k be the smallest element of S.
Therefore, k − 1 < y. Either k − 1 ≤ x or k − 1 > x. If k − 1 ≤ x, then
contrary to the assumption that y − x > 1. Therefore, x < k − 1 < y. Let l = k − 1.
It is the next theorem which gives the density of the rational numbers. This means that for any
real number, there exists a rational number arbitrarily close to it.
Theorem 1.9.8 If x < y then there exists a rational number r such that x < r < y.
Proof: Let n ∈ ℕ be large enough that
added to itself
times is larger than 1. Therefore,
It follows from Theorem 1.9.7 there exists m ∈ ℤ such that
and so take r = m∕n. ■
Definition 1.9.9 A set S ⊆ ℝ is dense in ℝ if whenever a < b, S ∩
Thus the above theorem says ℚ is “dense” in ℝ.
Theorem 1.9.10 Suppose 0 < a and let b ≥ 0. Then there exists a unique integer p and
real number r such that 0 ≤ r < a and b = pa + r.
Proof: Let S ≡
By the Archimedean property this set is nonempty. Let
+ 1 be the smallest element of S.
Then pa ≤ b
+ 1 is the smallest in S.
If r ≥ a then b − pa ≥ a and so b ≥
+ 1 ∈ S.
Therefore, r < a
To verify uniqueness of p and r, suppose pi and ri, i = 1,2, both work and r2 > r1. Then a
little algebra shows
Thus p1 − p2 is an integer between 0 and 1, contradicting Theorem 1.9.7. The case that r1 > r2
cannot occur either by similar reasoning. Thus r1 = r2 and it follows that p1 = p2.
This theorem is called the Euclidean algorithm when a and b are integers.