Definition 1.7.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.7.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.7.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 ≡
Mathematical induction is a very useful device for proving theorems about the integers.
Example 1.7.4 Prove by induction that ∑ _{k=1}^{n}k^{2} =
By inspection, if n = 1 then the formula is true. The sum yields 1 and so does the formula on the right. Suppose this formula is valid for some n ≥ 1 where n is an integer. Then
∑ _{k=1}^{n+1}k^{2}  = ∑
_{k=1}^{n}k^{2} + ^{2}

= +
^{2}
. 
The step going from the first to the second line is based on the assumption that the formula is true for n. This is called the induction hypothesis. Now simplify the expression in the second line,

This equals

and
+
 = 
= 
Therefore,
∑ _{k=1}^{n+1}k^{2}  = 
=
, 
showing the formula holds for n + 1 whenever it holds for n. This proves the formula by mathematical induction.
Example 1.7.5 Show that for all n ∈ ℕ,
If n = 1 this reduces to the statement that

which occurs if and only if
Lets review the process just used. If S is the set of integers at least as large as 1 for which the formula holds, the first step was to show 1 ∈ S and then that whenever n ∈ S, it follows n + 1 ∈ S. Therefore, by the principle of mathematical induction, S contains [1,∞) ∩ ℤ, all positive integers. In doing an inductive proof of this sort, the set, S is normally not mentioned. One just verifies the steps above. First show the thing is true for some a ∈ ℤ and then verify that whenever it is true for m it follows it is also true for m + 1. When this has been done, the theorem has been proved for all m ≥ a.
Definition 1.7.6 The Archimedean property states that whenever x ∈ ℝ, and a > 0, there exists n ∈ ℕ such that na > x.
This is not hard to believe. Just look at the number line. Imagine the intervals [0,a),[a,2a),[2a,3a),
Axiom 1.7.7 ℝ has the Archimedean property.
Theorem 1.7.8 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 and this proves the theorem with 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.7.8 there exists m ∈ ℤ such that

and so take r = m∕n. ■
Definition 1.7.10 A set, S ⊆ ℝ is dense in ℝ if whenever a < b, S ∩
Thus the above theorem says ℚ is “dense” in ℝ.
You probably saw the process of division in elementary school. Even though you saw it at a young age it is very profound and quite difficult to understand. Suppose you want to do the following problem

This meant

You were given two numbers, 79 and 22 and you wrote the first as some multiple of the second added to a third number which was smaller than the second number. Can this always be done? The answer is in the next theorem and depends here on the Archimedean property of the real numbers.
Theorem 1.7.11 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.7.8. 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. In this case, you would have r is an integer because it equals an integer.