Next: 3.2 Integers and Rationals. Up: 3. Induction and Integers Previous: 3. Induction and Integers   Index

# 3.1 Natural Numbers and Induction

3.1   Definition (Inductive set.) Let be a field. A subset of is inductive if it satisfies the two conditions:
i)
.
ii)
for all , .

3.2   Examples. and are inductive sets in . Every field is an inductive subset of itself.

If is an inductive subset of , then

etc. Hence every inductive set contains

If is an inductive subset of , then

so the only inductive subset of is itself. The set

is an inductive subset in .

3.3   Exercise. Which of the following subsets of are inductive?

3.4   Exercise.
a)
Find an inductive subset of , such that and .
b)
Find an inductive subset of , such that and .

3.5   Definition (Natural numbers in .) Let be a field, and let . Then is a natural number in if is in every inductive subset of . The set of all natural numbers in will be denoted by .

3.6   Example. By the first example in 3.2, for every field

If , .

3.7   Remark. By the definition of , is a subset of every inductive subset of , i.e.,

3.8   Theorem. Let be a field. Then the set of natural numbers in is an inductive set.

Proof: Since is in every inductive set, . Let be an inductive subset of . Then for all ,

Hence

Hence is inductive.

3.9   Remark. We summarize the previous theorem and remark by saying  is the smallest inductive subset of ." is an inductive set, and it's a subset of every other inductive set. You should expect that

(whatever " might mean).

3.10   Theorem (Induction theorem.) Let be a field, and let be a proposition form on . Suppose that
 (3.11) (3.12)

Then is true for all .

Proof: Let be a proposition form on satisfying (3.11) and (3.12). Let

I want to show that is inductive. Well, , by (3.11). Let be any element in .
Case 1.

Case 2.

If , then is false, so is true.

Thus for all ,

This shows that is inductive. Since every inductive set contains , ; i.e., for all , is true.

3.13   Theorem. Let be a field, and let be natural numbers in . Then and are in .

Proof: Let be the proposition form on defined by

Then says  " which is true. For all ,

By the induction theorem, is true for all ; i.e.,

Now define a proposition form on by

Then says  " which is true. For all ,

By the induction theorem, is true for all ; i.e.,

3.14   Theorem. Let be an ordered field. Then for all , we have

Proof: Define a proposition form on by

Clearly is true. let . To show that , I'll show that and that . Well

and

Hence , and by induction is true for all .

3.15   Corollary. Let be an ordered field. Then there is no element such that

3.16   Lemma. Let be an ordered field. Then
 (3.17)

Proof: Define a proposition form on by

 (3.18)

Then is true. Let . To show that , I'll show that and that ( . Well,

and

Hence , and by induction, is true for all .

3.19   Theorem. Let be an ordered field and let . Then

Proof: For each define a proposition form on by

I'll show that for each , is true for all . Now says  or " which is true, since . Now let . To show that , I'll show that

and that

By the previous lemma

Also

This completes the proof that , so by induction is true for all .

3.20   Corollary. Let be an ordered field, and let . If , then .

3.21   Theorem. Let be an ordered field and let . Then there is no natural number such that . In other words,

Proof: Suppose

 (3.22)

Then

Since , the previous theorem says . This contradicts corollary 3.15, so (3.22) is false.

3.23   Theorem (Least Element Principle.) Let be an ordered field. Then every non-empty subset of contains a least element, i.e. if , then there is some element such that for all .

Proof: I will show that if is a subset of having no least element, then .

Let be a subset of having no least element. For each define a proposition by

Now , since if were in it would be a least element for . Hence all elements in are greater than , and is true. Now let be a generic element of . Then

since if were in , it would be a least element for . Thus

and by induction, is true for all . It follows that , since if contained an element , then would say that .

3.24   Exercise. A Let be an ordered field. Show that there is a non-empty subset of that has no smallest element, i.e. there is a set such that

3.25   Example. Let be an ordered field. Let be the proposition form on defined by
 (3.26)

Then for all

Hence for all . Now note:

Since is false, I cannot apply the induction theorem. Notice that when I prove I do not assume that is true. (Although I might as well, since I know is true if is false.)

3.27   Theorem (Induction theorem generalization.) Let be an ordered field. Let and let be a proposition form defined on
. Suppose

 (3.28) (3.29)

Then is true for all .

Proof: Let be the proposition form on defined by

(observe that so is defined). Then , so is true by (3.28). For all ,

so

By the induction theorem, is true for all ; i.e., is true for all . To complete the proof, I need to show that

It is clear that

To show the opposite inclusion, observe that if and , then , and by theorem 3.19, .

3.30   Example. Let be an ordered field, and let be the proposition form on defined by

In example 3.25, we showed that for all and that is true. Hence, by our generalized induction theorem we can conclude that is true for all with .

3.31   Exercise. Let be a field and let . We say is even if for some , and we say is odd if for some .
a)
What are the even numbers in ?
b)
What are the odd numbers in ?

3.32   Exercise. A
a)
Let be a field. Prove that every element in is either even or odd. HINT: Let is even or is odd".
b)
Let be an ordered field. Prove that no element of is both even and odd. Why doesn't this contradict the result of exercise 3.31?

3.33   Note. The question of whether to consider to be a natural number is not settled. Some authors start the natural numbers at , other authors start them at . It is interesting to note that Aristotle did not consider to be a number.
for one" signifies a measure of some plurality, and  a number" signifies a measured plurality or a plurality of measures. Therefore, it is also with good reason that unity is not a number; for neither is a measure measures, but a measure is a principle, and so is unity . [5, page 237, N, 1, 1088a5]

Zero was first recognized to be a number around the ninth century. According to [31, page 185] Mahavira (ninth century) noted that any number multiplied by zero produces zero, and any number divided by zero remains unchanged! Bhaskara (1114-1185) said that a number divided by is called an infinite quantity.

Although arguments that are essentially arguments by induction appear in Euclid, the first clear statement of the induction principle is usually credited to Blaise Pascal. (1623-1662) who used induction to prove properties of Pascal's Triangle.[36, page 73]

I believe that the idea of defining the natural numbers to be things that are in every inductive set should be credited to Giuseppe Peano [37, page 94, Axiom 9]. In. 1889, Peano gave a set of axioms for natural numbers (starting with ), one of which can be paraphrased as: If is any set, such that and for all , , then .

Next: 3.2 Integers and Rationals. Up: 3. Induction and Integers Previous: 3. Induction and Integers   Index