4 The Natural Numbers

4
The Natural Numbers

In this chapter, it shall be shown that number theory can be embedded within set theory. One consequence of this embedding is that all of the theorems in number theory can be proven from the axioms of set theory.

In order to show that number theory is, in fact, a special branch of set theory, we must first represent each natural number as a set. How can one define the natural numbers in set theory? To answer this question, we next consider a set theoretic construction that makes sense for any set.

Definition 4.0.1. For each set $\text{[math]}$ , the successor $\text{[math]}$ is the set that is obtained by adjoining $\text{[math]}$ to the elements of $\text{[math]}$ , namely, $\text{[math]}$ .

We note the following three properties concerning the successor of a set $\text{[math]}$ :

1. $\text{[math]}$ .

2. $\text{[math]}$ .

3. $\text{[math]}$ .

Using the successor operation, we can now construct, in set theory, the first few natural numbers as follows:

$\text{[math]}$ .
$\text{[math]}$ .
$\text{[math]}$ .
$\text{[math]}$ .
$\text{[math]}$ .

We note some interesting properties that these “natural numbers” possess (see the above bulleted list):

1. $\text{[math]}$ .

2. $\text{[math]}$ .

4.1 Inductive Sets

The existence of an infinite set is crucial in modern set theory and mathematics. Zermelo realized that one cannot prove that an infinite set exists and thus found a fairly simple way to assert the existence of an infinite set.

Infinity Axiom. There is a set $\text{[math]}$ that contains the empty set as an element and whenever $\text{[math]}$ , then $\text{[math]}$ .

Using the infinity axiom, we shall prove that there is a set consisting of only the natural numbers; this set is denoted by $\text{[math]}$ . First, we define a property of a set that will ensure that each natural number belongs to such a set. A set that satisfies this property will contain the empty set and will be closed under the successor operation.

Definition 4.1.1. A set $\text{[math]}$ is said to be inductive if and only if

1. $\text{[math]}$ ,

2. $\text{[math]}$ , that is, $\text{[math]}$ is “closed under successor.”

An inductive set contains $\text{[math]}$ and also contains the successor of each one of its elements. Hence, an inductive set must contain all of the “natural numbers.” Clearly, the infinity axiom declares that there is an inductive set.

Definition 4.1.2. A natural number is a set that belongs, as an element, to every inductive set.

Therefore, $\text{[math]}$ is a natural number if and only if $\text{[math]}$ is in every inductive set. We now want to prove that there is a set consisting of just the natural numbers. To do this, we need to prove that the class

: (4.1)

is a set. By the infinity axiom, we know that there is an inductive set $\text{[math]}$ . Hence, for each $\text{[math]}$ , if $\text{[math]}$ is in every inductive set, then $\text{[math]}$ . Theorem 2.1.3 therefore implies that (4.1) defines a set, and this set consists of the natural numbers.

Definition 4.1.3. The set consisting of the natural numbers is denoted by $\text{[math]}$ .

Of course, $\text{[math]}$ is the set $\text{[math]}$ , but we will identify $\text{[math]}$ as the set that satisfies

: (4.2)

Theorem 4.1.4. The set $\text{[math]}$ is inductive and $\text{[math]}$ is a subset of every inductive set. Thus, $\text{[math]}$ is the smallest inductive set.

Proof. We first prove that $\text{[math]}$ is an inductive set; that is, we shall prove that

(1) $\text{[math]}$ ,

(2) $\text{[math]}$ .

Since $\text{[math]}$ is in every inductive set, (4.2) implies that $\text{[math]}$ . To prove (2), let $\text{[math]}$ . We thus conclude that $\text{[math]}$ is in every inductive set. So $\text{[math]}$ is also in every inductive set. Hence, $\text{[math]}$ and (2) holds. Now let $\text{[math]}$ be an inductive set and let $\text{[math]}$ . The above (4.2) implies that $\text{[math]}$ is in every inductive set. Therefore, $\text{[math]}$ and thus, $\text{[math]}$ . ☐

We now prove the following simple corollary.

Corollary 4.1.5. Let $\text{[math]}$ be an inductive set. Then $\text{[math]}$ .

Proof. Let $\text{[math]}$ be an inductive set such that $\text{[math]}$ . Since $\text{[math]}$ is an inductive set, Theorem 4.1.4 implies that $\text{[math]}$ . Hence, $\text{[math]}$ . ☐

Corollary 4.1.5 is, in fact, a restatement of the principle of mathematical induction. Suppose that $\text{[math]}$ is some property. To prove by induction that

is true, let $\text{[math]}$ and so, $\text{[math]}$ . If we can prove that

(1) $\text{[math]}$ ,

(2) $\text{[math]}$ ,

then $\text{[math]}$ is inductive and thus, $\text{[math]}$ by Corollary 4.1.5. Therefore, $\text{[math]}$ holds. Item (1) is often called the base step, and (2) is commonly refereed to as the inductive step. We apply this method of proof to establish our next theorem.

Theorem 4.1.6. For every $\text{[math]}$ , either $\text{[math]}$ or $\text{[math]}$ for some $\text{[math]}$ .

Proof. Let $\text{[math]}$ . Clearly, $\text{[math]}$ . Let $\text{[math]}$ . So either $\text{[math]}$ or $\text{[math]}$ for some $\text{[math]}$ . Therefore, $\text{[math]}$ or $\text{[math]}$ where $\text{[math]}$ . Thus, $\text{[math]}$ . Hence, by Corollary 4.1.5, $\text{[math]}$ . ☐

Definition 4.1.7. A set $\text{[math]}$ is said to be a transitive set if $\text{[math]}$ ; that is, every member of $\text{[math]}$ is also a subset of $\text{[math]}$ .

Therefore, for any set $\text{[math]}$ we have that

Example 1. The empty set $\text{[math]}$ is, vacuously, transitive. Each of the following sets is also transitive:

$\text{[math]}$ ,
$\text{[math]}$ ,
$\text{[math]}$ ,
$\text{[math]}$ ,
$\text{[math]}$ .

On the other hand, the set $\text{[math]}$ is not transitive because $\text{[math]}$ and yet $\text{[math]}$ . Similarly, the set $\text{[math]}$ is not transitive.

Remark 4.1.8. Regrettably, we are now using the word “transitive” to refer to two different concepts. A relation $\text{[math]}$ on a set $\text{[math]}$ is transitive provided that for all $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ in $\text{[math]}$ , if $\text{[math]}$ and $\text{[math]}$ , then $\text{[math]}$ (see Definition 3.2.11). A set $\text{[math]}$ is transitive, if whenever $\text{[math]}$ , then $\text{[math]}$ . If a set $\text{[math]}$ is transitive, then one cannot infer that the membership relation $\text{[math]}$ on $\text{[math]}$ is a transitive relation; that is, one cannot always conclude that if $\text{[math]}$ and $\text{[math]}$ , then $\text{[math]}$ , for all $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ in $\text{[math]}$ .

Proposition 4.1.9. Let $\text{[math]}$ and $\text{[math]}$ be sets. Then $\text{[math]}$ .

Theorem 4.1.10. Let $\text{[math]}$ be a transitive set. Then $\text{[math]}$ .

Proof. Suppose that $\text{[math]}$ is a transitive set. Then

Therefore, $\text{[math]}$ . ☐

Theorem 4.1.11. Every natural number is a transitive set.

Proof. We prove that $\text{[math]}$ by induction. Let

Clearly, $\text{[math]}$ , as $\text{[math]}$ is a transitive set. Let $\text{[math]}$ . So $\text{[math]}$ is transitive. To prove that $\text{[math]}$ is transitive, we will show that $\text{[math]}$ (see 4.4). By Theorem 4.1.10, $\text{[math]}$ . Since $\text{[math]}$ (see item 3 on page 83), we conclude that $\text{[math]}$ . Hence, $\text{[math]}$ is a transitive set and thus, $\text{[math]}$ . By Corollary 4.1.5, we conclude that $\text{[math]}$ , and this completes the proof. ☐

Theorem 4.1.11 implies that if $\text{[math]}$ and $\text{[math]}$ , then $\text{[math]}$ , whenever $\text{[math]}$ is a natural number. We now prove that the successor function on $\text{[math]}$ is one-to-one.

Theorem 4.1.12. For all $\text{[math]}$ and $\text{[math]}$ in $\text{[math]}$ , if $\text{[math]}$ , then $\text{[math]}$ .

Proof. Let $\text{[math]}$ and $\text{[math]}$ . It follows from Theorem 4.1.11 that $\text{[math]}$ and $\text{[math]}$ are transitive sets. Assume that $\text{[math]}$ . Thus, $\text{[math]}$ . Therefore, $\text{[math]}$ by Theorem 4.1.10. ☐

Theorem 4.1.13. The set $\text{[math]}$ is a transitive set.

Proof. We shall prove that $\text{[math]}$ by mathematical induction. Let $\text{[math]}$ . Clearly, $\text{[math]}$ , because $\text{[math]}$ and $\text{[math]}$ . Let $\text{[math]}$ . So (IH)¹ $\text{[math]}$ . We shall prove that $\text{[math]}$ . To do this, let $\text{[math]}$ . We must prove that $\text{[math]}$ . Since $\text{[math]}$ , we conclude that $\text{[math]}$ or $\text{[math]}$ . If $\text{[math]}$ , then $\text{[math]}$ by (IH). If $\text{[math]}$ , then $\text{[math]}$ because $\text{[math]}$ . Hence, $\text{[math]}$ . Therefore, $\text{[math]}$ . ☐

Exercises 4.1

1. Let $\text{[math]}$ and $\text{[math]}$ be inductive sets. Prove that $\text{[math]}$ is also inductive.

2. Prove that if $\text{[math]}$ is a transitive set, then $\text{[math]}$ is also a transitive set.

3. Prove that $\text{[math]}$ is a transitive set if and only if $\text{[math]}$ .

4. Prove that if $\text{[math]}$ is a transitive set, then $\text{[math]}$ is a transitive set.

5. Let $\text{[math]}$ be a nonempty set such that $\text{[math]}$ is a transitive set, for all $\text{[math]}$ . Prove that $\text{[math]}$ and $\text{[math]}$ are transitive sets.

6. Prove Proposition 4.1.9.

7. Prove that $\text{[math]}$ for all $\text{[math]}$ .

8. Conclude from Exercise 7 that $\text{[math]}$ for all $\text{[math]}$ .

9. Prove that for all $\text{[math]}$ and all $\text{[math]}$ , if $\text{[math]}$ , then $\text{[math]}$ .

10. Conclude from Exercise 9 that $\text{[math]}$ for all $\text{[math]}$ .

11. Let $\text{[math]}$ be a set and suppose that $\text{[math]}$ . Prove that $\text{[math]}$ is transitive and for all $\text{[math]}$ , there is a $\text{[math]}$ such that $\text{[math]}$ .

Exercise Notes: For Exercise 7, apply Theorem 4.1.12 for the inductive step. For Exercise 9, let $\text{[math]}$ and let $\text{[math]}$ . Prove that $\text{[math]}$ is inductive. Assume $\text{[math]}$ . To prove $\text{[math]}$ , let $\text{[math]}$ . So $\text{[math]}$ or $\text{[math]}$ . If $\text{[math]}$ , then $\text{[math]}$ implies that $\text{[math]}$ and thus, $\text{[math]}$ . If $\text{[math]}$ , then $\text{[math]}$ by Exercise 8.

4.2 The Recursion Theorem on $\text{[math]}$

Induction is frequently applied in mathematical proofs. Moreover, one often defines a function by induction (recursion). A recursively defined function is one that is defined in terms of “previously evaluated values of the function.” A function $\text{[math]}$ on $\text{[math]}$ is defined recursively if its value at $\text{[math]}$ is first specified and all of the remaining values are then defined using an earlier value, together with a given function. For example, let $\text{[math]}$ be a function. Suppose that the initial value of a function $\text{[math]}$ is given to be $\text{[math]}$ for a fixed $\text{[math]}$ , and to get the next value $\text{[math]}$ we use the initial value to obtain $\text{[math]}$ . Similarly, to get the next value $\text{[math]}$ we must evaluate $\text{[math]}$ . By continuing in this manner, we can evaluate more and more values of the function $\text{[math]}$ . A more succinct way of describing this function $\text{[math]}$ is to first define (i) $\text{[math]}$ and then define the remaining values by (ii) $\text{[math]}$ . Thus, one can evaluate $\text{[math]}$ , $\text{[math]}$ , …, $\text{[math]}$ . Just because we can evaluate a finite number of values, do we really know that there is such a function $\text{[math]}$ with domain $\text{[math]}$ ? The existence of such a function seems quite reasonable. In mathematics, however, the acceptance of an existential statement requires a valid argument, that is, a proof. The proof of our next theorem shows that such a function does exist and that it is unique.

Recursion Theorem 4.2.1. Let $\text{[math]}$ be a set and $\text{[math]}$ . Suppose that $\text{[math]}$ is a function. Then there exists a unique function $\text{[math]}$ such that

(1) $\text{[math]}$ ,

(2) $\text{[math]}$ , for all $\text{[math]}$ .

The function $\text{[math]}$ in the recursion theorem, satisfying (1) and (2), is said to be defined by recursion. If a function has been defined by recursion, then proofs of statements about this function often use “proof by induction.” Before we prove the recursion theorem, we make an observation. First, let us assume that the function $\text{[math]}$ exists. When viewing $\text{[math]}$ as a set of ordered pairs, conditions (1) and (2) imply that

$\text{[math]}$ , and
if $\text{[math]}$ , then $\text{[math]}$ , for all $\text{[math]}$ .

In our proof, we will show that there exists a function $\text{[math]}$ that satisfies the above bulleted conditions.

Proof. Let $\text{[math]}$ be a set, $\text{[math]}$ , and let $\text{[math]}$ be a function. Let us call a relation $\text{[math]}$ suitable if the following two conditions hold:

(i) $\text{[math]}$ .

(ii) If $\text{[math]}$ , then $\text{[math]}$ .

Our goal is to construct a suitable relation that is also a function.

Since every suitable relation is a subset of $\text{[math]}$ , Theorem 2.1.3 implies that the class $\text{[math]}$ is, in fact, a set. Because $\text{[math]}$ is a suitable relation, $\text{[math]}$ is nonempty. Let $\text{[math]}$ . Clearly, $\text{[math]}$ , and so $\text{[math]}$ is a relation. We now prove that $\text{[math]}$ is suitable and that it is a function.

Claim 1. $\text{[math]}$ is suitable.

Proof. We need to show that $\text{[math]}$ satisfies items (i) and (ii). Every relation in $\text{[math]}$ is suitable. So $\text{[math]}$ is an element in every relation in $\text{[math]}$ . Thus, $\text{[math]}$ ; that is, $\text{[math]}$ . To prove (ii), assume that $\text{[math]}$ . As $\text{[math]}$ , it follows that $\text{[math]}$ belongs to every relation in $\text{[math]}$ . Let $\text{[math]}$ . Since $\text{[math]}$ and $\text{[math]}$ is suitable, item (ii) implies that $\text{[math]}$ . So $\text{[math]}$ belongs to every relation in $\text{[math]}$ , and hence, $\text{[math]}$ . Thus, $\text{[math]}$ is suitable. (Claim 1) ☐

We now must prove that $\text{[math]}$ is a function from $\text{[math]}$ to $\text{[math]}$ .

Claim 2. $\text{[math]}$ is a function from $\text{[math]}$ to $\text{[math]}$ .

Proof. To prove that $\text{[math]}$ is a function from $\text{[math]}$ to $\text{[math]}$ , we must show that for each $\text{[math]}$ , there is exactly one $\text{[math]}$ such that $\text{[math]}$ . Let $\text{[math]}$ be defined by

We now prove that $\text{[math]}$ is an inductive set. To do this, we must first prove that $\text{[math]}$ . We know that $\text{[math]}$ . To prove that $\text{[math]}$ , we need to show there is no $\text{[math]}$ where $\text{[math]}$ . Suppose, for a contradiction, that $\text{[math]}$ where $\text{[math]}$ . Consider the relation

Clearly, ( $\text{[math]}$ ) $\text{[math]}$ . As $\text{[math]}$ is suitable, it easily follows that $\text{[math]}$ is also suitable (because $\text{[math]}$ for all $\text{[math]}$ ). Hence, $\text{[math]}$ . Since $\text{[math]}$ , we conclude that $\text{[math]}$ , and thus, $\text{[math]}$ , which contradicts ( $\text{[math]}$ ). Consequently, $\text{[math]}$ is the only element in $\text{[math]}$ such that $\text{[math]}$ . Therefore, $\text{[math]}$ .

Let $\text{[math]}$ ; that is, assume that (IH) there is a unique $\text{[math]}$ such that $\text{[math]}$ . Because $\text{[math]}$ is suitable, we conclude that $\text{[math]}$ . To show that $\text{[math]}$ , we must show there is no $\text{[math]}$ where $\text{[math]}$ . Assume, for a contradiction, that $\text{[math]}$ where $\text{[math]}$ . Consider the relation

Clearly, ( $\text{[math]}$ ) $\text{[math]}$ . We now show that $\text{[math]}$ is suitable. Since $\text{[math]}$ is suitable and $\text{[math]}$ , we have only to show that if $\text{[math]}$ , then $\text{[math]}$ . To do this, assume that $\text{[math]}$ . Thus, $\text{[math]}$ , and so $\text{[math]}$ . Since $\text{[math]}$ , $\text{[math]}$ , and $\text{[math]}$ , we conclude from (IH) that $\text{[math]}$ , and thus, $\text{[math]}$ . Because $\text{[math]}$ and $\text{[math]}$ , we infer that $\text{[math]}$ . So $\text{[math]}$ is suitable. Hence, $\text{[math]}$ . Since $\text{[math]}$ , we conclude that $\text{[math]}$ , and thus, $\text{[math]}$ , which contradicts ( $\text{[math]}$ ). Therefore, $\text{[math]}$ is the only element in $\text{[math]}$ such that $\text{[math]}$ . So $\text{[math]}$ , and thus, $\text{[math]}$ is inductive. Corollary 4.1.5 implies that $\text{[math]}$ , and as a result, $\text{[math]}$ is a function from $\text{[math]}$ to $\text{[math]}$ . (Claim 2) ☐

Because the function $\text{[math]}$ is suitable, it satisfies conditions (1) and (2) given in the statement of the theorem. To prove that $\text{[math]}$ is unique, suppose that $\text{[math]}$ also satisfies properties (1) and (2). Thus, $\text{[math]}$ is a suitable relation, and hence, $\text{[math]}$ . Since $\text{[math]}$ , we have that $\text{[math]}$ . Exercise 10 on page 68 implies that $\text{[math]}$ . Therefore, $\text{[math]}$ is unique. (Theorem) ☐

Example 1. Let $\text{[math]}$ and let $\text{[math]}$ . Theorem 4.2.1 implies that there is a function $\text{[math]}$ such that $\text{[math]}$ and $\text{[math]}$ , for all $\text{[math]}$ .

When can we be assured that the function $\text{[math]}$ in Theorem 4.2.1 is one-to-one? Our next theorem provides an answer.

Theorem 4.2.2. Let $\text{[math]}$ be a set, $\text{[math]}$ , $\text{[math]}$ , and $\text{[math]}$ be a function. Suppose that $\text{[math]}$ satisfies

(1) $\text{[math]}$ ,

(2) $\text{[math]}$ , for all $\text{[math]}$ .

If $\text{[math]}$ is one-to-one, then $\text{[math]}$ is also one-to-one.

Proof. Let $\text{[math]}$ be one-to-one, $\text{[math]}$ , $\text{[math]}$ , and let $\text{[math]}$ satisfy (1) and (2). We prove that for all $\text{[math]}$ and all $\text{[math]}$ , if $\text{[math]}$ , then $\text{[math]}$ . Let $\text{[math]}$ be defined by

We shall show that $\text{[math]}$ is an inductive set. To prove that $\text{[math]}$ , we must show that

: (4.5)

So let $\text{[math]}$ and assume that $\text{[math]}$ . By (1), we have $\text{[math]}$ . Hence, $\text{[math]}$ . Suppose that $\text{[math]}$ . Then $\text{[math]}$ for some $\text{[math]}$ by Theorem 4.1.6. Since $\text{[math]}$ , we conclude that $\text{[math]}$ . The above item (2) now implies that $\text{[math]}$ . Thus, $\text{[math]}$ , which contradicts the fact that $\text{[math]}$ . Hence, $\text{[math]}$ . Therefore, (4.5) holds, and so $\text{[math]}$ .

Let $\text{[math]}$ . In other words, assume the induction hypothesis

We shall prove that $\text{[math]}$ ; that is, we will prove that

Let $\text{[math]}$ and suppose that ( $\text{[math]}$ ) $\text{[math]}$ . Because $\text{[math]}$ , the above (4.5) and ( $\text{[math]}$ ) imply that $\text{[math]}$ . So $\text{[math]}$ for some $\text{[math]}$ . Hence, $\text{[math]}$ . Item (2) implies that $\text{[math]}$ . Since $\text{[math]}$ is one-to-one, we conclude that $\text{[math]}$ . Our induction hypothesis (IH) implies that $\text{[math]}$ , and thus, $\text{[math]}$ ; that is, $\text{[math]}$ . Hence, $\text{[math]}$ , and so $\text{[math]}$ is an inductive set. Therefore, $\text{[math]}$ and $\text{[math]}$ is a one-to-one function. ☐

4.2.1 The Peano Postulates ²

The Peano postulates offer an axiomatic foundation for the natural numbers. These postulates were first presented by the nineteenth-century Italian mathematician Giuseppe Peano. In 1888, Richard Dedekind proposed a set of axioms about the natural numbers. Peano then published a more precisely formulated version of these axioms in his 1889 book The principles of arithmetic presented by a new method [13]. The essence of the Peano postulates shall be summarized by means of the following two definitions.

Definition 4.2.3. Let $\text{[math]}$ and let $\text{[math]}$ . Then $\text{[math]}$ is said to be closed under $\text{[math]}$ if for all $\text{[math]}$ , if $\text{[math]}$ , then $\text{[math]}$ .

Let $\text{[math]}$ denote an ordered triple, that is, $\text{[math]}$ .

Definition 4.2.4. Let $\text{[math]}$ be an ordered triple that consists of a set $\text{[math]}$ , a function $\text{[math]}$ , and a particular element $\text{[math]}$ . Then $\text{[math]}$ is a Peano system if the following three conditions hold:

(1) $\text{[math]}$ .

(2) $\text{[math]}$ is one-to-one.

(3) For all $\text{[math]}$ , if $\text{[math]}$ and $\text{[math]}$ is closed under $\text{[math]}$ , then $\text{[math]}$ .

The above condition (3) is referred to as the induction postulate. Figure 4.1 illustrates a Peano system.

Figure 4.1. A Peano system $\text{[math]}$

Theorem 4.1.4 shows that $\text{[math]}$ is inductive. Thus, we can define the function $\text{[math]}$ by $\text{[math]}$ for all $\text{[math]}$ . We can now prove that a Peano system exists.

Theorem 4.2.5. The triple $\text{[math]}$ is a Peano system.

Proof. Since $\text{[math]}$ is inductive, we have that $\text{[math]}$ and that $\text{[math]}$ for all $\text{[math]}$ . Clearly, $\text{[math]}$ for all $\text{[math]}$ , as $\text{[math]}$ and $\text{[math]}$ . Thus, $\text{[math]}$ . Theorem 4.1.12 shows that $\text{[math]}$ is one-to-one. Finally, we need to show that $\text{[math]}$ satisfies the induction postulate. Let $\text{[math]}$ be such that $\text{[math]}$ and $\text{[math]}$ is closed under $\text{[math]}$ . So $\text{[math]}$ is inductive. Corollary 4.1.5 implies that $\text{[math]}$ . Therefore, $\text{[math]}$ is a Peano system because it satisfies conditions (1)–(3) of Definition 4.2.4. ☐

Definition 4.2.6. Let $\text{[math]}$ and $\text{[math]}$ be Peano systems. Then $\text{[math]}$ is isomorphic to $\text{[math]}$ when there is a bijection $\text{[math]}$ such that

(1) $\text{[math]}$ , and

(2) $\text{[math]}$ for all $\text{[math]}$ .

The function $\text{[math]}$ is said to be an isomorphism from $\text{[math]}$ onto $\text{[math]}$ .

Two Peano systems are isomorphic if they are essentially the same structure. We now prove that $\text{[math]}$ is isomorphic to any Peano system. Thus, the set of natural numbers $\text{[math]}$ is “the same” as the set $\text{[math]}$ that is used in calculus.

Theorem 4.2.7. Let $\text{[math]}$ be a Peano system. Then $\text{[math]}$ is isomorphic to $\text{[math]}$ .

Proof. Let $\text{[math]}$ be a Peano system. So $\text{[math]}$ is one-to-one, $\text{[math]}$ , and $\text{[math]}$ . Since $\text{[math]}$ , Theorem 4.2.1 implies that there is a function $\text{[math]}$ such that

(1) $\text{[math]}$ ,

(2) $\text{[math]}$ , for all $\text{[math]}$ .

As $\text{[math]}$ and $\text{[math]}$ is one-to-one, Theorem 4.2.2 implies that $\text{[math]}$ is one-to-one. To show that $\text{[math]}$ is onto $\text{[math]}$ , we use the induction postulate (Definition 4.2.4(3)). Clearly, $\text{[math]}$ . Since $\text{[math]}$ , we see that $\text{[math]}$ . Let $\text{[math]}$ . Thus, $\text{[math]}$ for some $\text{[math]}$ . Hence, $\text{[math]}$ . By (2), we conclude that $\text{[math]}$ . So $\text{[math]}$ , and $\text{[math]}$ is thereby closed under $\text{[math]}$ . The induction postulate implies that $\text{[math]}$ , that is, $\text{[math]}$ is onto $\text{[math]}$ . Therefore, $\text{[math]}$ is an isomorphism from $\text{[math]}$ onto $\text{[math]}$ . ☐

Theorem 4.2.7 implies that the Peano postulates characterize the system of natural numbers (up to isomorphism). Theorem 4.2.7 also implies that any two Peano systems are isomorphic to each other (see Exercises 7–8).

Exercises 4.2

1. How would one modify the proof of Theorem 4.2.1 in order to establish the following:

Theorem. Let $\text{[math]}$ be a set and let $\text{[math]}$ . Suppose that $\text{[math]}$ is a function. Then there exists a unique function $\text{[math]}$ such that

(1) $\text{[math]}$ ,

(2) $\text{[math]}$ , for all $\text{[math]}$ .

2. Let $\text{[math]}$ and $\text{[math]}$ be a function such that $\text{[math]}$ . Suppose that $\text{[math]}$ satisfies

(1) $\text{[math]}$ ,

(2) $\text{[math]}$ , for all $\text{[math]}$ .

Assume that $\text{[math]}$ is one-to-one and onto $\text{[math]}$ . Prove that $\text{[math]}$ is one-to-one.

3. Let $\text{[math]}$ be a set and let $\text{[math]}$ . Suppose that $\text{[math]}$ satisfies

(a) $\text{[math]}$ ,

(b) if $\text{[math]}$ then $\text{[math]}$ , for all $\text{[math]}$ and $\text{[math]}$ in $\text{[math]}$ .

Let $\text{[math]}$ be as stated in Theorem 4.2.1. Prove that $\text{[math]}$ for all $\text{[math]}$ .

4. Let $\text{[math]}$ be a function and let $\text{[math]}$ .

(a) Prove that the class $\text{[math]}$ is a set.

(b) Show that $\text{[math]}$ is nonempty.

(d) Prove that for all $\text{[math]}$ , if $\text{[math]}$ and $\text{[math]}$ , then $\text{[math]}$ .

(e) Prove that $\text{[math]}$ if and only if $\text{[math]}$ .

5. Let $\text{[math]}$ be a function and let $\text{[math]}$ .

(a) Prove that the class $\text{[math]}$ is a set.

(b) Show that $\text{[math]}$ is nonempty.

(d) Prove that for all $\text{[math]}$ , if $\text{[math]}$ and $\text{[math]}$ , then $\text{[math]}$ .

(e) Prove that $\text{[math]}$ if and only if $\text{[math]}$ .

6. Let $\text{[math]}$ be a function and let $\text{[math]}$ . The recursion theorem implies the existence of the function $\text{[math]}$ that satisfies:

(1) $\text{[math]}$ ,

(2) $\text{[math]}$ , for all $\text{[math]}$ .

Now address the following:

(a) Let $\text{[math]}$ and $\text{[math]}$ . Prove by induction that $\text{[math]}$ for all $\text{[math]}$ .

(b) Let $\text{[math]}$ . Prove that $\text{[math]}$ and $\text{[math]}$ .

(d) Let $\text{[math]}$ be as in the previous Exercise 5. Prove that $\text{[math]}$ .

7. Let $\text{[math]}$ and $\text{[math]}$ be Peano systems. Let $\text{[math]}$ be an isomorphism from $\text{[math]}$ onto $\text{[math]}$ . Prove that $\text{[math]}$ is thus an isomorphism from $\text{[math]}$ onto $\text{[math]}$ .

8. Let $\text{[math]}$ and $\text{[math]}$ be Peano systems. Let $\text{[math]}$ be an isomorphism from $\text{[math]}$ onto $\text{[math]}$ , and let $\text{[math]}$ be an isomorphism from $\text{[math]}$ onto $\text{[math]}$ . Show that the composition $\text{[math]}$ is an isomorphism from $\text{[math]}$ onto $\text{[math]}$ .

Exercise Notes: Exercises 4–5 do not involve Theorem 4.2.1, but they do apply some of the ideas in its proof. For Exercise 4(e) and for Exercise 5(e), in the direction ( $\text{[math]}$ ), prove that $\text{[math]}$ . For Exercise 6, item (a) implies (c); to prove (d), use (b) and (c) together with the results of Exercise 5(c)(d) to show that $\text{[math]}$ and $\text{[math]}$ .

4.3 Arithmetic on $\text{[math]}$

In this section, the recursion theorem will be used to define the operations of addition, multiplication, and exponentiation on the natural numbers. We will also prove the properties of arithmetic that we were taught as children. We first establish the following result.

Theorem 4.3.1. Let $\text{[math]}$ and $\text{[math]}$ be functions. Then there is a unique function $\text{[math]}$ such that for each $\text{[math]}$ ,

(1) $\text{[math]}$ ,

(2) $\text{[math]}$ , for all $\text{[math]}$ .

Proof. For each $\text{[math]}$ , by the recursion theorem (viewing $\text{[math]}$ as a constant), there is a unique function $\text{[math]}$ such that

(a) $\text{[math]}$ ,

(b) $\text{[math]}$ , for all $\text{[math]}$ .

Since $\text{[math]}$ is unique for each $\text{[math]}$ , the connection $\text{[math]}$ thus produces a function with domain $\text{[math]}$ . We can now define the function $\text{[math]}$ by $\text{[math]}$ . The function $\text{[math]}$ easily satisfies conditions (1) and (2) for all $\text{[math]}$ , and it is unique. ☐

The function $\text{[math]}$ in Theorem 4.3.1 is defined in terms of two known functions. Thus, before one can apply Theorem 4.3.1, one must first introduce the two relevant functions $\text{[math]}$ and $\text{[math]}$ .

Recalling Definition 3.5.3, a function of the form $\text{[math]}$ is called a binary operation on $\text{[math]}$ . Our next definition is an application of Theorem 4.3.1; that is, using the functions $\text{[math]}$ and $\text{[math]}$ , we define addition on the natural numbers.

Definition 4.3.2. Let $\text{[math]}$ be the unique function satisfying

(1) $\text{[math]}$ ,

(2) $\text{[math]}$

for all natural numbers $\text{[math]}$ and $\text{[math]}$ . The function $\text{[math]}$ shall be referred to as addition, and we define the binary operation $\text{[math]}$ on $\text{[math]}$ to be

for all $\text{[math]}$ and $\text{[math]}$ in $\text{[math]}$ .

Theorem 4.3.3. For all natural numbers $\text{[math]}$ and $\text{[math]}$ ,

(A1) $\text{[math]}$ ,

(A2) $\text{[math]}$ .

Proof. Let $\text{[math]}$ and $\text{[math]}$ be elements in $\text{[math]}$ . Recalling that $\text{[math]}$ , we see that (1) and (2) in Definition 4.3.2 immediately produce (A1) and (A2). ☐

The next proposition shows that $\text{[math]}$ is equal to $\text{[math]}$ , the successor of $\text{[math]}$ . After we prove this proposition, we will show that $\text{[math]}$ .

Proposition 4.3.4. For all $\text{[math]}$ , $\text{[math]}$ .

Proof. Let $\text{[math]}$ . Since $\text{[math]}$ , we obtain

and thus, $\text{[math]}$ . ☐

We can now prove that $\text{[math]}$ as follows:

Now that we have the operation $\text{[math]}$ of addition, we can apply Theorem 4.3.1 to define multiplication on the natural numbers using the functions $\text{[math]}$ and $\text{[math]}$ .

Definition 4.3.5. Let $\text{[math]}$ be the unique function satisfying

(1) $\text{[math]}$ ,

(2) $\text{[math]}$

for all natural numbers $\text{[math]}$ and $\text{[math]}$ . The function $\text{[math]}$ is called multiplication, and we define the binary operation $\text{[math]}$ on $\text{[math]}$ to be

for all $\text{[math]}$ and $\text{[math]}$ in $\text{[math]}$ .

Theorem 4.3.6. For all natural numbers $\text{[math]}$ and $\text{[math]}$ ,

(M1) $\text{[math]}$

(M2) $\text{[math]}$ .

Proof. Let $\text{[math]}$ and $\text{[math]}$ be elements in $\text{[math]}$ . Recalling that $\text{[math]}$ , we see that (1) and (2) in Definition 4.3.5 yields (M1) and (M2). ☐

Having presented the set-theoretic definitions of addition and multiplication, we will now show that some of the familiar laws of arithmetic are provable within set theory. Afterwards, we shall define exponentiation.

Theorem 4.3.7 (Associative Law for Addition). For all $\text{[math]}$ , $\text{[math]}$ , and $\text{[math]}$ in $\text{[math]}$ ,

Proof. Let $\text{[math]}$ and $\text{[math]}$ be elements in $\text{[math]}$ , and let

We shall show that $\text{[math]}$ is an inductive set. To show that $\text{[math]}$ , observe that

and thus, $\text{[math]}$ , and so $\text{[math]}$ . Assume that $\text{[math]}$ . Then

Therefore, $\text{[math]}$ , and hence, $\text{[math]}$ . ☐

For $\text{[math]}$ , we know that $\text{[math]}$ by (A1). Since we have not proven that addition is commutative, we cannot immediately infer that $\text{[math]}$ , and thus, we must prove that this latter equation holds for all $\text{[math]}$ .

Lemma 4.3.8. For all $\text{[math]}$ , we have $\text{[math]}$ .

Proof. We prove that $\text{[math]}$ by induction. Let

We prove that $\text{[math]}$ is inductive. Since (A1) implies that $\text{[math]}$ , we have that $\text{[math]}$ . Let $\text{[math]}$ . So $\text{[math]}$ . We prove that $\text{[math]}$ as follows:

Therefore, $\text{[math]}$ , and this completes the proof. ☐

Item (A2) states that $\text{[math]}$ for natural numbers $\text{[math]}$ and $\text{[math]}$ . We will now prove that we also have that $\text{[math]}$ . Then we will be able to prove that addition is commutative.

Lemma 4.3.9. For all $\text{[math]}$ and $\text{[math]}$ , we have $\text{[math]}$ .

Proof. Let $\text{[math]}$ be arbitrary. We prove that $\text{[math]}$ by induction. Let

To prove the lemma, we just need to show that $\text{[math]}$ is inductive. First, we verify that $\text{[math]}$ by showing that $\text{[math]}$ as follows:

Thus, $\text{[math]}$ . Suppose that $\text{[math]}$ . Then

and hence, $\text{[math]}$ . Therefore, $\text{[math]}$ and $\text{[math]}$ is inductive. ☐

Lemmas 4.3.8 and 4.3.9 will be used to prove that addition is commutative.

Theorem 4.3.10 (Commutative Law for Addition). For all $\text{[math]}$ and $\text{[math]}$ in $\text{[math]}$ ,

Proof. Let $\text{[math]}$ be any element in $\text{[math]}$ and let

We prove that $\text{[math]}$ is an inductive set. Observe that $\text{[math]}$ by Lemma 4.3.8 and (A1). So $\text{[math]}$ . Assume that $\text{[math]}$ . Then

Hence, $\text{[math]}$ , and therefore, $\text{[math]}$ . ☐

Using proof by induction, we will now show that the familiar distributive law of arithmetic holds. We will thus have additional evidence to support the assertion “Mathematics can be embedded in set theory.”

Theorem 4.3.11 (Distributive Law). For all natural numbers $\text{[math]}$ , $\text{[math]}$ , and $\text{[math]}$ ,

Proof. Let $\text{[math]}$ and $\text{[math]}$ be in $\text{[math]}$ . Now let

We will show that $\text{[math]}$ is an inductive set. To verify that $\text{[math]}$ , we have

Thus, $\text{[math]}$ , and so $\text{[math]}$ . Now, suppose that $\text{[math]}$ . Then

Hence, $\text{[math]}$ , and thus, $\text{[math]}$ . ☐

Our next two theorems verify two fundamental properties of multiplication.

Theorem 4.3.12 (Associative Law for Multiplication). For all $\text{[math]}$ , $\text{[math]}$ , and $\text{[math]}$ in $\text{[math]}$ ,

Proof. Let $\text{[math]}$ and $\text{[math]}$ be elements in $\text{[math]}$ and let

We shall show that $\text{[math]}$ is an inductive set. To show that $\text{[math]}$ , observe that

and thus, $\text{[math]}$ , and so $\text{[math]}$ . Assume that $\text{[math]}$ . Then

Therefore, $\text{[math]}$ , and hence, $\text{[math]}$ . ☐

Theorem 4.3.13 (Commutative Law for Multiplication). For all $\text{[math]}$ and $\text{[math]}$ in $\text{[math]}$ ,

Proof. See Exercise 6. ☐

We will now apply Theorem 4.3.1 to define exponentiation on the natural numbers, using the functions $\text{[math]}$ and $\text{[math]}$ .

Definition 4.3.14. Let $\text{[math]}$ be the unique function satisfying

(1) $\text{[math]}$ ,

(2) $\text{[math]}$

for all natural numbers $\text{[math]}$ and $\text{[math]}$ . The function $\text{[math]}$ is called exponentiation. We define the binary operation, denoted by $\text{[math]}$ , to be

for all $\text{[math]}$ and $\text{[math]}$ in $\text{[math]}$ .

Theorem 4.3.15. For all natural numbers $\text{[math]}$ and $\text{[math]}$ ,

(E1) $\text{[math]}$ ,

(E2) $\text{[math]}$ .

Exercises 4.3

1. Let $\text{[math]}$ and $\text{[math]}$ . Suppose $\text{[math]}$ . Prove that $\text{[math]}$ .

2. Let $\text{[math]}$ and $\text{[math]}$ . Show that if $\text{[math]}$ , then $\text{[math]}$ or $\text{[math]}$ .

3. Let $\text{[math]}$ and $\text{[math]}$ . Prove that for all $\text{[math]}$ , if $\text{[math]}$ , then $\text{[math]}$ .

4. Prove that for all $\text{[math]}$ , the equality $\text{[math]}$ holds.

5. Prove for all $\text{[math]}$ and $\text{[math]}$ , we have that $\text{[math]}$ .

6. Let $\text{[math]}$ . Using the previous two exercises, prove Theorem 4.3.13 by showing that the set $\text{[math]}$ is inductive.

7. A natural number $\text{[math]}$ is even if $\text{[math]}$ for some $\text{[math]}$ . If $\text{[math]}$ for some $\text{[math]}$ , then $\text{[math]}$ is odd. Prove that for all $\text{[math]}$ , either $\text{[math]}$ is even or $\text{[math]}$ is odd.

8. Let $\text{[math]}$ . Prove that $\text{[math]}$ is an inductive set. Conclude that no natural number is both even and odd.

9. Prove for all $\text{[math]}$ , $\text{[math]}$ , and $\text{[math]}$ in $\text{[math]}$ , that $\text{[math]}$ .

10. Prove for all $\text{[math]}$ , $\text{[math]}$ , and $\text{[math]}$ in $\text{[math]}$ , that $\text{[math]}$ .

11. Prove for all $\text{[math]}$ , $\text{[math]}$ , and $\text{[math]}$ in $\text{[math]}$ , that $\text{[math]}$ .

Exercise Notes: For Exercise 1, suppose $\text{[math]}$ and then use Theorem 4.1.6. For Exercise 2, assume that $\text{[math]}$ and use Exercise 1 to prove that $\text{[math]}$ . For Exercise 3, Theorem 4.1.12 can be used in the inductive step.

4.4 Order on $\text{[math]}$

We now want to develop a theory of order on the natural numbers. First, we define the “less than” relation on the natural numbers. Then we prove that this relation satisfies the trichotomy law (see Theorem 4.4.9) as well as the standard connections with addition and multiplication. How can we get such a relation in set theory?

Recall that for each $\text{[math]}$ , we defined the successor of $\text{[math]}$ to be the natural number $\text{[math]}$ , and thus, $\text{[math]}$ . As a result, we have the following infinite membership list:

which is very much like the usual relation $\text{[math]}$ on the natural numbers; that is,

It turns out that the order relation that we need is just “ $\text{[math]}$ ,” and, in fact, we will prove that this is the “less than” relation that we were looking for.

Definition 4.4.1. We say that $\text{[math]}$ is less than $\text{[math]}$ if and only if $\text{[math]}$ , whenever $\text{[math]}$ and $\text{[math]}$ are in $\text{[math]}$ .

In this section, we will view “ $\text{[math]}$ ” as the “less than” relation on the natural numbers, and we shall no longer use the symbol $\text{[math]}$ in our initial discussion of ordering on $\text{[math]}$ . We will show that the relation $\text{[math]}$ on $\text{[math]}$ satisfies the trichotomy law, and we will show that $\text{[math]}$ is preserved under the operations of addition and nonzero multiplication.

Theorem 4.1.11 and Theorem 4.1.13 assert, respectively, that each natural number $\text{[math]}$ is a transitive set and that $\text{[math]}$ is a transitive set. Hence, we have the following result.

Proposition 4.4.2. Let $\text{[math]}$ be a natural number. Then

(1) if $\text{[math]}$ , then $\text{[math]}$ ;

(2) if $\text{[math]}$ and $\text{[math]}$ , then $\text{[math]}$ ;

(3) if $\text{[math]}$ , then $\text{[math]}$ ;

(4) if $\text{[math]}$ and $\text{[math]}$ , then $\text{[math]}$ .

Item (2) proclaims that $\text{[math]}$ is a transitive relation on $\text{[math]}$ . One can also prove, without using the regularity axiom, that no natural number is “less than” itself.

Lemma 4.4.3. Let $\text{[math]}$ . Then $\text{[math]}$ .

Proof. See Exercise 10 on page 88. ☐

Using Definition 4.4.1, we can now easily define the “less than or equal” relation on the natural numbers.

Definition 4.4.4. We write $\text{[math]}$ if and only if $\text{[math]}$ or $\text{[math]}$ , whenever $\text{[math]}$ and $\text{[math]}$ are in $\text{[math]}$ .

Since $\text{[math]}$ is a transitive relation on $\text{[math]}$ , it thus follows that $\text{[math]}$ is also a transitive relation on $\text{[math]}$ . Clearly, $\text{[math]}$ is reflexive. We will now show that it is antisymmetric (see Definition 3.4.1).

Lemma 4.4.5. Let $\text{[math]}$ and $\text{[math]}$ . If $\text{[math]}$ and $\text{[math]}$ , then $\text{[math]}$ .

Proof. Let $\text{[math]}$ and $\text{[math]}$ satisfy $\text{[math]}$ and $\text{[math]}$ . Thus, $\text{[math]}$ and $\text{[math]}$ by Proposition 4.4.2(1). Therefore, $\text{[math]}$ . ☐

Hence, $\text{[math]}$ is a partial order on $\text{[math]}$ . Is the relation $\text{[math]}$ a total order on $\text{[math]}$ ? To show that it is, we shall prove that the relation $\text{[math]}$ satisfies the trichotomy law on $\text{[math]}$ . First, we establish two lemmas.

Lemma 4.4.6. For all $\text{[math]}$ , we have that $\text{[math]}$ .

Proof. We shall prove that the set

is inductive. Clearly, $\text{[math]}$ . Assume $\text{[math]}$ . Hence, $\text{[math]}$ . So either $\text{[math]}$ or $\text{[math]}$ . If $\text{[math]}$ , then, as $\text{[math]}$ , we see that $\text{[math]}$ . If $\text{[math]}$ , then we have $\text{[math]}$ and $\text{[math]}$ . By transitivity (see Proposition 4.4.2(2)), we conclude that $\text{[math]}$ . Thus, in either case, $\text{[math]}$ and so, $\text{[math]}$ . Therefore, $\text{[math]}$ is inductive and $\text{[math]}$ . ☐

Lemma 4.4.7. For all natural numbers $\text{[math]}$ and $\text{[math]}$ , if $\text{[math]}$ , then $\text{[math]}$ .

Proof. Let $\text{[math]}$ . We prove that $\text{[math]}$ by induction. Let

Clearly, $\text{[math]}$ as $\text{[math]}$ is true vacuously. Let $\text{[math]}$ . To prove that $\text{[math]}$ , assume that $\text{[math]}$ . We shall show that $\text{[math]}$ . Observe that ( $\text{[math]}$ ) $\text{[math]}$ . Because $\text{[math]}$ , either $\text{[math]}$ or $\text{[math]}$ . If $\text{[math]}$ , then $\text{[math]}$ as $\text{[math]}$ . Since $\text{[math]}$ , we see that ( $\text{[math]}$ ) and transitivity imply that $\text{[math]}$ . If $\text{[math]}$ , then $\text{[math]}$ . Thus, ( $\text{[math]}$ ) implies that $\text{[math]}$ . Therefore, $\text{[math]}$ . ☐

Corollary 4.4.8. If $\text{[math]}$ and $\text{[math]}$ are in $\text{[math]}$ , then $\text{[math]}$ if and only if $\text{[math]}$ .

Proof. Assume that $\text{[math]}$ and $\text{[math]}$ . By Lemma 4.4.7, we just need to prove if $\text{[math]}$ , then $\text{[math]}$ . So let $\text{[math]}$ . Recall that ( $\text{[math]}$ ) $\text{[math]}$ . Since $\text{[math]}$ , we have either $\text{[math]}$ or $\text{[math]}$ . If $\text{[math]}$ , then $\text{[math]}$ by ( $\text{[math]}$ ) and transitivity. Also, if $\text{[math]}$ , then ( $\text{[math]}$ ) implies that $\text{[math]}$ . ☐

The following theorem shows that $\text{[math]}$ is a total order on $\text{[math]}$ ; that is, for all $\text{[math]}$ and $\text{[math]}$ in $\text{[math]}$ , either $\text{[math]}$ or $\text{[math]}$ .

Theorem 4.4.9 (Trichotomy Law on $\text{[math]}$ ). For all $\text{[math]}$ and $\text{[math]}$ in $\text{[math]}$ , exactly one of the three relationships $\text{[math]}$ holds.

Proof. First, we show that any two of the relations $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ cannot hold at the same time, whenever $\text{[math]}$ and $\text{[math]}$ are natural numbers. To do this, we just have to show that the following two conjunctions do not hold:

when $\text{[math]}$ and $\text{[math]}$ . Conjunction (a) implies that $\text{[math]}$ , which contradicts Lemma 4.4.3. Conjunction (b), by transitivity, also implies that $\text{[math]}$ . Hence, both (a) and (b) do not hold.

We now prove that $\text{[math]}$ . To prove this statement, let $\text{[math]}$ and let

We will show that $\text{[math]}$ is inductive. Lemma 4.4.6 implies that $\text{[math]}$ . Let $\text{[math]}$ , that is, assume that

We must show that

: (4.6)

To do this, we consider each of the three cases in (IH) separately. If $\text{[math]}$ , then $\text{[math]}$ by the fact that $\text{[math]}$ and transitivity. If $\text{[math]}$ , then $\text{[math]}$ since $\text{[math]}$ . If $\text{[math]}$ , then Lemma 4.4.7 implies that $\text{[math]}$ . Thus, either $\text{[math]}$ or $\text{[math]}$ . So in each of these three cases in (IH), we obtain one of the conjuncts in (4.6). Therefore, $\text{[math]}$ , and the proof is complete. ☐

The trichotomy law will now allow us to do the following:

(1) identify an interesting connection between the relations $\text{[math]}$ and $\text{[math]}$ on the natural numbers;

(2) prove that addition and multiplication on the natural numbers preserve the “less than” relation;

(3) prove that $\text{[math]}$ , the set of natural numbers, satisfies the crucial well-ordering principle.

Corollary 4.4.10. If $\text{[math]}$ and $\text{[math]}$ are in $\text{[math]}$ , then $\text{[math]}$ if and only if $\text{[math]}$ .

Proof. Let $\text{[math]}$ and $\text{[math]}$ . Assume that $\text{[math]}$ . Because $\text{[math]}$ is transitive, we have that $\text{[math]}$ . Since $\text{[math]}$ , Theorem 4.4.9 implies that $\text{[math]}$ . So $\text{[math]}$ . To prove the converse, assume $\text{[math]}$ . Thus, $\text{[math]}$ . From Theorem 4.4.9, we have either $\text{[math]}$ or $\text{[math]}$ . If $\text{[math]}$ , then we would have that $\text{[math]}$ , as $\text{[math]}$ . This contradicts Theorem 4.4.3. Thus, $\text{[math]}$ . ☐

Corollary 4.4.10 implies that for all natural numbers $\text{[math]}$ and $\text{[math]}$ ,

When $\text{[math]}$ and $\text{[math]}$ are natural numbers, we can now define $\text{[math]}$ , which is the larger of the two natural numbers $\text{[math]}$ and $\text{[math]}$ (see Exercise 5).

Our next theorem shows that the expected properties of “inequality” hold for the natural numbers.

Theorem 4.4.11 (Properties of Inequality). For all natural numbers $\text{[math]}$ , $\text{[math]}$ , and $\text{[math]}$ , the following hold:

(1) $\text{[math]}$ if and only if $\text{[math]}$ .

(2) If $\text{[math]}$ , then $\text{[math]}$ if and only if $\text{[math]}$ .

Proof. Item (1) follows from Exercises 6 and 7 of this section. Similarly, (2) is established via Exercises 8 and 9. ☐

Corollary 4.4.12 (Cancellation Laws). For all natural numbers $\text{[math]}$ , $\text{[math]}$ , and $\text{[math]}$ , the following hold:

(1) If $\text{[math]}$ , then $\text{[math]}$ .

(2) If $\text{[math]}$ , then $\text{[math]}$ implies $\text{[math]}$ .

Proof. See Exercise 10. ☐

Corollary 4.1.5 (page 85) confirms the fact that the principle of mathematical induction is provable from the first seven axioms of Zermelo–Fraenkel (ZF) set theory. Virtually every undergraduate text in mathematics (e.g., number theory, real analysis, and abstract algebra) just cites this principle and does not attempt to prove it directly. Our next theorem shows that these seven axioms also imply the well-ordering principle: Every nonempty subset of $\text{[math]}$ has a least element.

Theorem 4.4.13 (Well-Ordering Principle). Let $\text{[math]}$ be a nonempty subset of $\text{[math]}$ . Then $\text{[math]}$ has a least element; that is, there is an $\text{[math]}$ such that $\text{[math]}$ for all $\text{[math]}$ .

Proof. Let $\text{[math]}$ be a nonempty subset of $\text{[math]}$ . Suppose, for a contradiction, that $\text{[math]}$ has no least element. Let $\text{[math]}$ . So $\text{[math]}$ is the set of $\text{[math]}$ that are less than or equal to every element in $\text{[math]}$ . Note that ( $\text{[math]}$ ) $\text{[math]}$ because if $\text{[math]}$ , then $\text{[math]}$ and $\text{[math]}$ would be a least element in $\text{[math]}$ .

We will now show that $\text{[math]}$ is inductive. Clearly, $\text{[math]}$ , by Lemma 4.4.6. Let $\text{[math]}$ ; that is, suppose that $\text{[math]}$ for all $\text{[math]}$ . Since $\text{[math]}$ has no least element, it follows that $\text{[math]}$ . Therefore, $\text{[math]}$ for all $\text{[math]}$ . Hence, $\text{[math]}$ for all $\text{[math]}$ by Exercise 3. So $\text{[math]}$ and $\text{[math]}$ is inductive. Thus, $\text{[math]}$ and ( $\text{[math]}$ ) now implies that $\text{[math]}$ . Nevertheless, because $\text{[math]}$ and $\text{[math]}$ is nonempty, we also conclude that $\text{[math]}$ . This contradiction completes the proof. ☐

We end this section with a proof of the strong induction principle on $\text{[math]}$ .

Theorem 4.4.14 (Strong Induction Principle on $\text{[math]}$ ). Let $\text{[math]}$ be a subset of $\text{[math]}$ and suppose that

: (4.7)

Then $\text{[math]}$ .

Proof. Let $\text{[math]}$ satisfy (4.7). Suppose, to the contrary, that there is a natural number that is not in $\text{[math]}$ . Thus, the set $\text{[math]}$ is nonempty. Theorem 4.4.13 now implies that $\text{[math]}$ has a least element $\text{[math]}$ . Hence, $\text{[math]}$ and if $\text{[math]}$ , then $\text{[math]}$ . Therefore, $\text{[math]}$ . As $\text{[math]}$ satisfies (4.7), we infer that $\text{[math]}$ , a contradiction. ☐

We can now define a special relation symbol with which we are all familiar. Let $\text{[math]}$ and $\text{[math]}$ be in $\text{[math]}$ . We define $\text{[math]}$ if and only if $\text{[math]}$ , and define $\text{[math]}$ if and only if $\text{[math]}$ . So in the future there may times when we shall use the symbols $\text{[math]}$ and $\text{[math]}$ , rather than $\text{[math]}$ and $\text{[math]}$ , if it seems appropriate.

Remark 4.4.15. Using the system of natural numbers $\text{[math]}$ , one can give set-theoretic constructions of the set of integers, the set of rational numbers, and then the set of real numbers. A method for constructing the set of integers is suggested in Exercise 9 on page 82. In [5], Enderton gives a more detailed description of this method and constructs the set of rational numbers and the set of real numbers.

Exercises 4.4

1. Let $\text{[math]}$ . Show that $\text{[math]}$ .

2. Let $\text{[math]}$ and $\text{[math]}$ be in $\text{[math]}$ . Show that if $\text{[math]}$ , then $\text{[math]}$ .

3. Let $\text{[math]}$ and $\text{[math]}$ be in $\text{[math]}$ . Show that if $\text{[math]}$ , then $\text{[math]}$ .

4. Let $\text{[math]}$ be inductive and let $\text{[math]}$ . Prove that $\text{[math]}$ is inductive.

5. Let $\text{[math]}$ and $\text{[math]}$ be in $\text{[math]}$ . Suppose that $\text{[math]}$ . Prove that $\text{[math]}$ .

6. Let $\text{[math]}$ and $\text{[math]}$ be natural numbers. Prove that for all $\text{[math]}$ , if $\text{[math]}$ , then $\text{[math]}$ .

7. Let $\text{[math]}$ and $\text{[math]}$ . Prove that for all $\text{[math]}$ , if $\text{[math]}$ , then $\text{[math]}$ .

8. Let $\text{[math]}$ and $\text{[math]}$ be natural numbers. Prove that for all $\text{[math]}$ , if $\text{[math]}$ , then $\text{[math]}$ .

9. Let $\text{[math]}$ and $\text{[math]}$ . Prove that for all $\text{[math]}$ , if $\text{[math]}$ , then $\text{[math]}$ .

10. Use Theorem 4.4.11 and Theorem 4.4.9 to prove Corollary 4.4.12.

11. Let $\text{[math]}$ . Prove that $\text{[math]}$ , for all $\text{[math]}$ .

12. Let $\text{[math]}$ . Prove that for all $\text{[math]}$ , if $\text{[math]}$ , then $\text{[math]}$ for some $\text{[math]}$ .

13. Let $\text{[math]}$ and $\text{[math]}$ be in $\text{[math]}$ . Prove that $\text{[math]}$ if and only if $\text{[math]}$ for some $\text{[math]}$ .

14. Suppose that $\text{[math]}$ satisfies $\text{[math]}$ for all $\text{[math]}$ .

(a) Prove that $\text{[math]}$ is an increasing function; that is, show that for all $\text{[math]}$ and all $\text{[math]}$ , if $\text{[math]}$ , then $\text{[math]}$ .

(b) Prove that $\text{[math]}$ is one-to-one.

15. Prove that there is no function $\text{[math]}$ satisfying $\text{[math]}$ for all $\text{[math]}$ .

16. Let $\text{[math]}$ and let $\text{[math]}$ be nonempty. Prove that $\text{[math]}$ has a largest element; that is, there is an $\text{[math]}$ such that $\text{[math]}$ for all $\text{[math]}$ .

17. Let $\text{[math]}$ . Prove that for all $\text{[math]}$ , the set $\text{[math]}$ has a largest element.

18. Prove for all $\text{[math]}$ , if $\text{[math]}$ , then $\text{[math]}$ , for some $\text{[math]}$ .

19. Let $\text{[math]}$ be in $\text{[math]}$ . Suppose that $\text{[math]}$ . Let

Prove that $\text{[math]}$ is an inductive set.

20. Let $\text{[math]}$ be in $\text{[math]}$ with $\text{[math]}$ . Assume that $\text{[math]}$ where $\text{[math]}$ , and $\text{[math]}$ where $\text{[math]}$ . Prove that $\text{[math]}$ and $\text{[math]}$ . To prove that $\text{[math]}$ , suppose to the contrary that $\text{[math]}$ (without loss of generality). By Exercise 12, there is a $\text{[math]}$ so that $\text{[math]}$ . Complete the following:

(a) Show that $\text{[math]}$ .

(b) Show that $\text{[math]}$ and $\text{[math]}$ . Then show that $\text{[math]}$ , which is a contradiction. Conclude that $\text{[math]}$ .

Exercise Notes: For Exercise 3, apply Theorem 4.4.9. For Exercise 4, apply Exercise 3. For Exercise 6, use induction. For Exercise 7, apply Exercise 6 and Theorem 4.4.9. For Exercise 8, use induction. For Exercise 9, use Exercise 8 and Theorem 4.4.9. For Exercise 13, use Exercises 11–12. For Exercise 14, let $\text{[math]}$ and prove that $\text{[math]}$ is inductive. For Exercise 15, one can apply Theorem 4.4.13 and proof by contradiction: Assume that there is such function $\text{[math]}$ . Let $\text{[math]}$ . Let $\text{[math]}$ be the least element in $\text{[math]}$ . Thus, $\text{[math]}$ for a $\text{[math]}$ . For Exercise 16, use the well-ordering principle and Exercise 2. For Exercise 17, use induction and review 3.3.8(3) on page 60. For Exercise 18, prove that

is an inductive set. For Exercise 19, in the inductive step one can use Exercise 3. Exercises 19–20 yield a proof the Division Algorithm: Let $\text{[math]}$ and $\text{[math]}$ be natural numbers, where $\text{[math]}$ . Then there exist unique natural numbers $\text{[math]}$ and $\text{[math]}$ such that $\text{[math]}$ and $\text{[math]}$ .