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

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 ≡
Example 1.9.4 Show that for all n ∈ ℕ,
If n = 1 this reduces to the statement that

The theorem will be proved if this last expression is less than

which occurs if and only if
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 =

Then y = y − a + a < na + a =
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 x^{2} < 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.
Proof: Let n ∈ ℕ be large enough that

Thus

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 ≡

If r ≥ a then b − pa ≥ a and so b ≥
To verify uniqueness of p and r, suppose p_{i} and r_{i}, i = 1,2, both work and r_{2} > r_{1}. Then a little algebra shows

Thus p_{1} − p_{2} is an integer between 0 and 1, contradicting Theorem 1.9.7. The case that r_{1} > r_{2} cannot occur either by similar reasoning. Thus r_{1} = r_{2} and it follows that p_{1} = p_{2}. ■
This theorem is called the Euclidean algorithm when a and b are integers.