6 Transfinite Recursion

6
Transfinite Recursion

In Definition 3.4.2, we introduced the notion of a partial order on a set. The concept of a total order was then presented in Definition 3.4.3. We also proved that there exists a total ordering on the natural numbers so that every nonempty set of natural numbers has a least element with respect to this ordering (see Theorem 4.4.13). As a result, we were able to prove the important recursion theorem. In this chapter, we will generalize these ideas.

6.1 Well-Ordering

Definition 6.1.1. (Well-Ordering) A well-ordering is a total ordering on a set $\text{[math]}$ for which every nonempty subset of $\text{[math]}$ has a smallest (least) element.

Suppose that $\text{[math]}$ is a well-ordering on a set $\text{[math]}$ . Whenever $\text{[math]}$ is nonempty, then the set $\text{[math]}$ has a least element $\text{[math]}$ ; that is, $\text{[math]}$ and $\text{[math]}$ for all $\text{[math]}$ .

Let $\text{[math]}$ be the usual order on set $\text{[math]}$ of integers. Then $\text{[math]}$ is a total order on $\text{[math]}$ . Since $\text{[math]}$ has no least element, $\text{[math]}$ is not a well-ordering on $\text{[math]}$ .

Theorem 6.1.2. Let $\text{[math]}$ be a well-ordering on $\text{[math]}$ . Then there exists no function $\text{[math]}$ satisfying $\text{[math]}$ for all $\text{[math]}$ .

Proof. Suppose there is a function such that $\text{[math]}$ for all $\text{[math]}$ , where $\text{[math]}$ is a well-ordering on $\text{[math]}$ . Let $\text{[math]}$ . Clearly, $\text{[math]}$ is a nonempty subset of $\text{[math]}$ . Thus, $\text{[math]}$ has a least element $\text{[math]}$ . So $\text{[math]}$ for all $\text{[math]}$ ; however, by assumption, we have that $\text{[math]}$ , a contradiction. ☐

Let $\text{[math]}$ be a set with well-ordering $\text{[math]}$ and let $\text{[math]}$ be nonempty. When $\text{[math]}$ is the smallest element in $\text{[math]}$ , we shall write

Lemma 3.4.12 implies that $\text{[math]}$ is unique.

Theorem 6.1.3. If $\text{[math]}$ is an infinite set with the well-ordering $\text{[math]}$ , then there is a function $\text{[math]}$ such that $\text{[math]}$ for all $\text{[math]}$ .

Proof. For each $\text{[math]}$ , let $\text{[math]}$ be the set of elements in $\text{[math]}$ that are “greater” than $\text{[math]}$ , and let $\text{[math]}$ be the set of elements in $\text{[math]}$ that are “less than or equal” to $\text{[math]}$ . As $\text{[math]}$ is a total order, $\text{[math]}$ for each $\text{[math]}$ . Moreover, since $\text{[math]}$ is infinite, it follows (see Exercise 15, page 116) that for any $\text{[math]}$ ,

: (6.1)

Let $\text{[math]}$ be the $\text{[math]}$ -least element in $\text{[math]}$ , and define $\text{[math]}$ by

: (6.2)

So ( $\text{[math]}$ ) if $\text{[math]}$ and $\text{[math]}$ , then $\text{[math]}$ . By the recursion theorem, there is a function $\text{[math]}$ such that

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

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

We now prove that $\text{[math]}$ is finite for all $\text{[math]}$ . Let $\text{[math]}$ . Because $\text{[math]}$ is the smallest element in $\text{[math]}$ , we see that $\text{[math]}$ , which is finite. So $\text{[math]}$ . Let $\text{[math]}$ . Thus, $\text{[math]}$ is finite, and $\text{[math]}$ by (6.1). As $\text{[math]}$ and $\text{[math]}$ , we infer from (6.2) that $\text{[math]}$ is the $\text{[math]}$ -least element in $\text{[math]}$ . It follows that $\text{[math]}$ , which is a finite set. Hence, $\text{[math]}$ . Therefore, $\text{[math]}$ and $\text{[math]}$ is finite for all $\text{[math]}$ . Thus, by (6.1), $\text{[math]}$ for all $\text{[math]}$ . Let $\text{[math]}$ . Since $\text{[math]}$ and $\text{[math]}$ , the above ( $\text{[math]}$ ) implies that $\text{[math]}$ . ☐

Theorem 6.1.4. Let $\text{[math]}$ be a well-ordering on the set $\text{[math]}$ . Suppose that $\text{[math]}$ is one-to-one. Define the relation $\text{[math]}$ on $\text{[math]}$ by $\text{[math]}$ if and only if $\text{[math]}$ , for all $\text{[math]}$ and $\text{[math]}$ in $\text{[math]}$ . Then $\text{[math]}$ is a well-ordering on $\text{[math]}$ .

Proof. See Exercise 6. ☐

Let $\text{[math]}$ be a well-ordering on a set $\text{[math]}$ . For each $\text{[math]}$ , we define the following initial segments up to $\text{[math]}$ :

The set $\text{[math]}$ consists of the elements in $\text{[math]}$ that are less than (smaller than) $\text{[math]}$ , whereas $\text{[math]}$ is the set of elements that are less than or equal to $\text{[math]}$ . In other words, $\text{[math]}$ and $\text{[math]}$ . Furthermore, for $\text{[math]}$ and $\text{[math]}$ in $\text{[math]}$ , if $\text{[math]}$ , then

If the well-ordering $\text{[math]}$ is understood, we shall write $\text{[math]}$ for $\text{[math]}$ as well as $\text{[math]}$ in place of $\text{[math]}$ . For example, because $\text{[math]}$ is well-ordered by $\text{[math]}$ and it is transitive, if $\text{[math]}$ , then

Theorem 4.4.14, the strong induction principle, applies to the finite elements in $\text{[math]}$ . The term transfinite applies to elements that may not be finite.

Theorem 6.1.5 (Transfinite Induction Principle). Let $\text{[math]}$ be a well-ordering on $\text{[math]}$ . Let $\text{[math]}$ be a subset of $\text{[math]}$ , and suppose that

: (6.7)

Then $\text{[math]}$ .

Proof. Suppose that $\text{[math]}$ satisfies (6.7) and assume, for a contradiction, that there exists a $\text{[math]}$ . Thus, the set $\text{[math]}$ is nonempty. Since $\text{[math]}$ is a well-ordering, $\text{[math]}$ has a least element $\text{[math]}$ . So $\text{[math]}$ , and if $\text{[math]}$ , then $\text{[math]}$ . Hence, $\text{[math]}$ . As $\text{[math]}$ satisfies (6.7), we have that $\text{[math]}$ , a contradiction. ☐

Exercises 6.1

1. Let $\text{[math]}$ be the set of real numbers and let $\text{[math]}$ be the standard order on $\text{[math]}$ . Suppose $\text{[math]}$ is such that for all $\text{[math]}$ and $\text{[math]}$ in $\text{[math]}$ , if $\text{[math]}$ , then $\text{[math]}$ . Let $\text{[math]}$ .

(a) Let $\text{[math]}$ and $\text{[math]}$ be in $\text{[math]}$ . Prove that if $\text{[math]}$ , then $\text{[math]}$ .

(b) Prove that $\text{[math]}$ is a well-ordering on $\text{[math]}$ .

2. Let $\text{[math]}$ , and for all $\text{[math]}$ and $\text{[math]}$ in $\text{[math]}$ , define the relation $\text{[math]}$ on $\text{[math]}$ by $\text{[math]}$ if and only if $\text{[math]}$ or $\text{[math]}$ . Show that $\text{[math]}$ is a well-ordering on $\text{[math]}$ .

3. Suppose that $\text{[math]}$ is a well-ordering on $\text{[math]}$ and that $\text{[math]}$ is such that if $\text{[math]}$ , then $\text{[math]}$ whenever $\text{[math]}$ and $\text{[math]}$ are in $\text{[math]}$ .

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

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

4. Let $\text{[math]}$ be an infinite set with the well-ordering $\text{[math]}$ . Now let $\text{[math]}$ be the function defined in the proof of Theorem 6.1.3. Let $\text{[math]}$ . Prove that for all $\text{[math]}$ , if $\text{[math]}$ , then $\text{[math]}$ for some $\text{[math]}$ .

5. Suppose that $\text{[math]}$ is a well-ordering on $\text{[math]}$ and let $\text{[math]}$ . Show that $\text{[math]}$ is a well-ordering on $\text{[math]}$ .

6. Prove Theorem 6.1.4.

7. Prove that every finite set has a well-ordering.

8. Prove that every countably infinite set has a well-ordering.

Exercise Notes: For Exercise 5, apply the result of Exercise 14 on page 76 and review Definition 3.4.15. For Exercise 6, Exercise 12 on page 76 implies that $\text{[math]}$ is a total order on $\text{[math]}$ . For Exercises 7–8, use Theorem 6.1.4.

6.2 Transfinite Recursion Theorem

A powerful tool in set theory is definition by transfinite recursion. If one wants to define a function on a set using transfinite recursion, then one must first have a well-ordering on the set. Many of the important functions that we shall introduce later in the book are defined by means of transfinite recursion. This recursion principle plays a crucial role in set theory, and its importance cannot be overstated.

The concept of transfinite recursion is grounded in recursion on $\text{[math]}$ . Let us recall the “finite” Recursion Theorem 4.2.1: Let $\text{[math]}$ be a function and let $\text{[math]}$ . Then there exists a unique function $\text{[math]}$ such that

The value $\text{[math]}$ depends on the “previous” value $\text{[math]}$ and on the function $\text{[math]}$ . Our proof of the finite recursion theorem used the fact that $\text{[math]}$ was a set.

We would like to extend Theorem 4.2.1 and prove that there exists a function $\text{[math]}$ so that $\text{[math]}$ depends on all of the prior values $\text{[math]}$ , $\text{[math]}$ , …, $\text{[math]}$ . We would prefer, however, to prove that there is a function $\text{[math]}$ where each value $\text{[math]}$ depends on the restricted function $\text{[math]}$ , that is, on $\text{[math]}$ . Can we prove such a result?

As noted on page 121, Theorem 2.1.3 implies that the following is a set:

Thus, for every function $\text{[math]}$ , where $\text{[math]}$ , we have that $\text{[math]}$ . Now let $\text{[math]}$ be a function and let $\text{[math]}$ . To positively address the above question, we would need to prove that there exists a function $\text{[math]}$ that satisfies the following two conditions:

One can combine conditions (i) and (ii) into one condition. Since the empty function $\text{[math]}$ is in $\text{[math]}$ , one can let the function $\text{[math]}$ satisfy $\text{[math]}$ and then require that $\text{[math]}$ meet the following single condition:

: (6.8)

If $\text{[math]}$ satisfies (6.8), then it will satisfy (i) and (ii); namely, we will have

Our proof of the Recursion Theorem 4.2.1 can be adapted to show that such a function $\text{[math]}$ actually does exist; however, rather than do this, we will pursue a much more general result. In fact, we will establish two such generalizations, the first of which will imply that there exists a function $\text{[math]}$ satisfying (6.8) (see Corollary 6.2.2).

6.2.1 Using a Set Function

Let $\text{[math]}$ be a well-ordering on $\text{[math]}$ and let $\text{[math]}$ be a set. Recall the initial segment functions $\text{[math]}$ and $\text{[math]}$ that were defined on page 143. Theorem 2.1.3 implies that the following sets exist:

Our next theorem is an extension of the finite recursion theorem on $\text{[math]}$ . The proof of this theorem uses a method that will be applied again in Section 6.2.2. We shall be using the expression set function only to emphasize that a given function is a set.

Transfinite Recursion Theorem 6.2.1. Let $\text{[math]}$ be a well-ordering on a set $\text{[math]}$ . If $\text{[math]}$ is a set function, then there exists a unique function $\text{[math]}$ such that

: (6.9)

Proof. Let $\text{[math]}$ be a well-ordering on $\text{[math]}$ and let $\text{[math]}$ be a function. When $\text{[math]}$ , we will say that $\text{[math]}$ is $\text{[math]}$ -recursive up to $\text{[math]}$ if and only if for all $\text{[math]}$ , we have that $\text{[math]}$ .

Claim 1. Let $\text{[math]}$ and $\text{[math]}$ be $\text{[math]}$ -recursive up to $\text{[math]}$ . Then $\text{[math]}$ .

Proof. Suppose that $\text{[math]}$ , and let $\text{[math]}$ be the $\text{[math]}$ -least element such that $\text{[math]}$ . Thus, $\text{[math]}$ for all $\text{[math]}$ . So ( $\text{[math]}$ ) $\text{[math]}$ . Hence,

We conclude that $\text{[math]}$ , a contradiction. (Claim 1) ☐

Claim 2. Let $\text{[math]}$ and let $\text{[math]}$ be $\text{[math]}$ -recursive up to $\text{[math]}$ . Then for all $\text{[math]}$ , the function $\text{[math]}$ is $\text{[math]}$ -recursive up to $\text{[math]}$ .

Proof. Let $\text{[math]}$ and let $\text{[math]}$ . Hence, $\text{[math]}$ and

: (6.10)

For each $\text{[math]}$ , we have that $\text{[math]}$ , and therefore,

So $\text{[math]}$ , and thus, $\text{[math]}$ is $\text{[math]}$ -recursive up to $\text{[math]}$ . (Claim 2) ☐

Consider the relation $\text{[math]}$ defined by

: (6.11)

Claim 1 implies that $\text{[math]}$ is a function. For each $\text{[math]}$ , let $\text{[math]}$ . Therefore, we have that the function $\text{[math]}$ is $\text{[math]}$ -recursive up to $\text{[math]}$ whenever $\text{[math]}$ . In particular, $\text{[math]}$ for all $\text{[math]}$ .

Claim 3. Let $\text{[math]}$ . If $\text{[math]}$ , then $\text{[math]}$ and $\text{[math]}$ .

Proof. Let $\text{[math]}$ and $\text{[math]}$ . Hence, $\text{[math]}$ is $\text{[math]}$ -recursive up to $\text{[math]}$ . Claim 2 implies that $\text{[math]}$ is $\text{[math]}$ -recursive up to $\text{[math]}$ . Therefore, $\text{[math]}$ and $\text{[math]}$ by Claim 1. So $\text{[math]}$ as $\text{[math]}$ . (Claim 3) ☐

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

Proof. Clearly, $\text{[math]}$ . Suppose, to the contrary, that $\text{[math]}$ . Let $\text{[math]}$ be the $\text{[math]}$ -least such that $\text{[math]}$ . So $\text{[math]}$ for all $\text{[math]}$ . Let $\text{[math]}$ be the function defined by ( $\text{[math]}$ ) $\text{[math]}$ for all $\text{[math]}$ , and let $\text{[math]}$ . Claim 3 implies that $\text{[math]}$ for all $\text{[math]}$ . Thus, $\text{[math]}$ for all $\text{[math]}$ , and therefore, ( $\text{[math]}$ ) $\text{[math]}$ . Define $\text{[math]}$ by

: (6.12)

We will show that $\text{[math]}$ is $\text{[math]}$ -recursive up to $\text{[math]}$ . Let $\text{[math]}$ . There are two cases to consider: $\text{[math]}$ and $\text{[math]}$ . If $\text{[math]}$ , we can prove that $\text{[math]}$ as follows:

When $\text{[math]}$ , we need to show that $\text{[math]}$ . The definition of $\text{[math]}$ in (6.12) implies that $\text{[math]}$ and hence,

Thus, $\text{[math]}$ is $\text{[math]}$ -recursive up to $\text{[math]}$ . So $\text{[math]}$ , a contradiction.(Claim 4) ☐

Define $\text{[math]}$ by $\text{[math]}$ . The argument used to prove Claim 4, involving $\text{[math]}$ , shows that $\text{[math]}$ for all $\text{[math]}$ . Moreover, the proof of Claim 1 adapts to show that $\text{[math]}$ is unique. (See Exercise 1.) (Theorem) ☐

The relation $\text{[math]}$ is a well-ordering on $\text{[math]}$ , as established by Theorem 4.4.13. Theorem 6.2.5 and (6.5) thereby imply the following corollary.

Corollary 6.2.2. Let $\text{[math]}$ be a function. There exists a unique function $\text{[math]}$ such that

: (6.13)

Corollary 6.2.2 allows us to prove the converse of Corollary 5.1.11.

Theorem 6.2.3 (AC). Suppose that $\text{[math]}$ is an infinite set. Then there is one-to-one function $\text{[math]}$ .

Proof. Let $\text{[math]}$ be an infinite set. Recall that (see page 146)

Whenever $\text{[math]}$ and $\text{[math]}$ , we observe that $\text{[math]}$ is a finite subset of $\text{[math]}$ , and therefore, $\text{[math]}$ is infinite by Exercise 12 on page 116. Let $\text{[math]}$ . By Theorem 3.3.24, there is a function $\text{[math]}$ such that $\text{[math]}$ for all $\text{[math]}$ . Define $\text{[math]}$ by

By Corollary 6.2.2, there exists a function $\text{[math]}$ with domain $\text{[math]}$ such that

: (6.14)

Thus, $\text{[math]}$ , and Exercise 11 on page 123 shows that $\text{[math]}$ is one-to-one. ☐

Richard Dedekind [3] defined a set to be infinite if and only if it has the same cardinality as a proper subset of itself. Such a set is said to be Dedekind-infinite. For example, the function $\text{[math]}$ defined by $\text{[math]}$ is one-to-one and shows that $\text{[math]}$ and $\text{[math]}$ have the same cardinality. So, according to Dedekind, $\text{[math]}$ is an infinite set. Our next result confirms Dedekind’s definition in general.

Corollary 6.2.4 (AC). A set $\text{[math]}$ is infinite if and only if there exists a one-to-one function $\text{[math]}$ that is not onto $\text{[math]}$ .

Proof. Let $\text{[math]}$ be set. Assume that $\text{[math]}$ is infinite. Theorem 6.2.3 asserts that there is a one-to-one function $\text{[math]}$ . Define $\text{[math]}$ by

: (6.15)

Since $\text{[math]}$ is one-to-one, it follows that $\text{[math]}$ is a function and that $\text{[math]}$ is one-to-one. As $\text{[math]}$ and $\text{[math]}$ is not in the range of $\text{[math]}$ , we see that $\text{[math]}$ is not onto $\text{[math]}$ .

To prove the converse, suppose $\text{[math]}$ is a one-to-one function that is not onto $\text{[math]}$ . Corollary 5.1.6 implies that $\text{[math]}$ is infinite. ☐

6.2.2 Using a Class Function

Let us say that a formula $\text{[math]}$ is functional if $\text{[math]}$ ; that is, for all $\text{[math]}$ there exists a unique $\text{[math]}$ such that $\text{[math]}$ . Let $\text{[math]}$ be functional formula and consider the class

Because $\text{[math]}$ is functional, we can now view $\text{[math]}$ as a class function. Let $\text{[math]}$ be a well-ordering on a set $\text{[math]}$ . If there were a set $\text{[math]}$ such that for all $\text{[math]}$ , there is a $\text{[math]}$ such that $\text{[math]}$ , then Theorem 2.1.3 would imply that the following function $\text{[math]}$ is a set:

Theorem 6.2.1 would then yield the existence of a function $\text{[math]}$ so that

(where the initial segment $\text{[math]}$ is defined on page 143). Thus, the set function $\text{[math]}$ would satisfy

Can one prove the existence of this function $\text{[math]}$ without a set such as $\text{[math]}$ ? Yes, and this will be verified by our next theorem, whose proof is based on the argument used to prove Theorem 6.2.1. This theorem also validates an essential general tool in set theory, namely, definition by transfinite recursion.

Transfinite Recursion Theorem 6.2.5 (Class Form). Suppose that $\text{[math]}$ is a functional formula (which may contain parameters). If $\text{[math]}$ is a well-ordering on a set $\text{[math]}$ , then there exists a unique function $\text{[math]}$ with domain $\text{[math]}$ such that

: (6.16)

The crucial ingredient in the proof of Theorem 6.2.1 was the existence of the set function $\text{[math]}$ (see (6.11)). In our proof of Theorem 6.2.5, using the functional formula $\text{[math]}$ and the replacement axiom, we will be able to get a function such as $\text{[math]}$ . Recall that the replacement axiom asserts that for any set $\text{[math]}$ , if for each $\text{[math]}$ , there is an element $\text{[math]}$ that is “uniquely connected” to $\text{[math]}$ , then we can replace every $\text{[math]}$ with its unique connection $\text{[math]}$ , and the result is a new set.

Replacement Axiom. Let $\text{[math]}$ be a formula. For every set $\text{[math]}$ , if for each $\text{[math]}$ there is a unique $\text{[math]}$ such that $\text{[math]}$ , then there is a set $\text{[math]}$ that consists of all the elements $\text{[math]}$ such that $\text{[math]}$ for some $\text{[math]}$ .

Thus, if $\text{[math]}$ , then for each set $\text{[math]}$ , we have the following set:

Hence, $\text{[math]}$ is a set function $\text{[math]}$ .

We are now ready to prove Theorem 6.2.5. In a loose sense, our proof will be the result of replacing all of the expressions $\text{[math]}$ and $\text{[math]}$ , appearing in the proof of Theorem 6.2.1, with the expression $\text{[math]}$ . We could just ask the reader to do this as an exercise, but since the proof requires the replacement axiom, we shall provide a complete proof.

Proof (of Theorem 6.2.5). Let $\text{[math]}$ be a well-ordering on $\text{[math]}$ . Suppose that $\text{[math]}$ is functional. When $\text{[math]}$ , we will say that a function $\text{[math]}$ is $\text{[math]}$ -recursive up to $\text{[math]}$ if and only if $\text{[math]}$ and

We now establish four claims.

Claim 1. Let $\text{[math]}$ and $\text{[math]}$ be $\text{[math]}$ -recursive up to $\text{[math]}$ . Then $\text{[math]}$ .

Proof. Let $\text{[math]}$ and $\text{[math]}$ be $\text{[math]}$ -recursive up to $\text{[math]}$ . Suppose that $\text{[math]}$ . Let $\text{[math]}$ be the $\text{[math]}$ -least element such that $\text{[math]}$ . Thus, $\text{[math]}$ for all $\text{[math]}$ . Hence, ( $\text{[math]}$ ) $\text{[math]}$ . Since $\text{[math]}$ and $\text{[math]}$ are $\text{[math]}$ -recursive up to $\text{[math]}$ , we have that $\text{[math]}$ and $\text{[math]}$ . Since $\text{[math]}$ is functional, ( $\text{[math]}$ ) implies that $\text{[math]}$ , a contradiction. (Claim 1) ☐

Claim 2. If $\text{[math]}$ and $\text{[math]}$ is $\text{[math]}$ -recursive up to $\text{[math]}$ , then for all $\text{[math]}$ , the function $\text{[math]}$ is $\text{[math]}$ -recursive up to $\text{[math]}$ .

Proof. Let $\text{[math]}$ and $\text{[math]}$ be $\text{[math]}$ -recursive up to $\text{[math]}$ . Let $\text{[math]}$ and $\text{[math]}$ . So

: (6.17)

Let $\text{[math]}$ . Therefore, $\text{[math]}$ and $\text{[math]}$ . Hence, $\text{[math]}$ and $\text{[math]}$ , by (6.17). As $\text{[math]}$ is $\text{[math]}$ -recursive up to $\text{[math]}$ and $\text{[math]}$ , we have that $\text{[math]}$ . Since $\text{[math]}$ and $\text{[math]}$ , we conclude that $\text{[math]}$ . Thus, $\text{[math]}$ is $\text{[math]}$ -recursive up to $\text{[math]}$ . (Claim 2) ☐

Let $\text{[math]}$ represent the property

Let $\text{[math]}$ . Claim 1 implies that for all $\text{[math]}$ there is a unique $\text{[math]}$ such that $\text{[math]}$ . Thus, by the replacement axiom we have that $\text{[math]}$ is a set. Now define the relation $\text{[math]}$ by

: (6.18)

Claim 1 implies that $\text{[math]}$ is a function. For each $\text{[math]}$ , let $\text{[math]}$ , and hence, $\text{[math]}$ is $\text{[math]}$ -recursive up to $\text{[math]}$ .

Claim 3. Let $\text{[math]}$ . If $\text{[math]}$ , then $\text{[math]}$ and $\text{[math]}$ .

Proof. Let $\text{[math]}$ and $\text{[math]}$ . So $\text{[math]}$ is $\text{[math]}$ -recursive up to $\text{[math]}$ . Claim 2 implies that $\text{[math]}$ is $\text{[math]}$ -recursive up to $\text{[math]}$ . Thus, $\text{[math]}$ and $\text{[math]}$ by Claim 1. Since $\text{[math]}$ , we conclude that $\text{[math]}$ . (Claim 3) ☐

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

Proof. Clearly, $\text{[math]}$ . Suppose, to the contrary, that $\text{[math]}$ . Let $\text{[math]}$ be the $\text{[math]}$ -least such that $\text{[math]}$ . So $\text{[math]}$ for all $\text{[math]}$ . Let $\text{[math]}$ be the function with domain $\text{[math]}$ defined by ( $\text{[math]}$ ) $\text{[math]}$ , and let $\text{[math]}$ . Claim 3 implies that $\text{[math]}$ for all $\text{[math]}$ . Therefore, ( $\text{[math]}$ ) $\text{[math]}$ . Let $\text{[math]}$ be the unique element satisfying $\text{[math]}$ . Define the function $\text{[math]}$ with domain $\text{[math]}$ by

: (6.19)

Since $\text{[math]}$ is $\text{[math]}$ -recursive up to $\text{[math]}$ , we have that $\text{[math]}$ holds, and thus its equivalent $\text{[math]}$ also holds.

When $\text{[math]}$ , we need to show that $\text{[math]}$ holds. The definition of $\text{[math]}$ in (6.19) implies that $\text{[math]}$ , and therefore the following are equivalent:

Since $\text{[math]}$ was chosen to satisfy $\text{[math]}$ , we conclude that $\text{[math]}$ is true. Thus, $\text{[math]}$ is $\text{[math]}$ -recursive up to $\text{[math]}$ . So $\text{[math]}$ , a contradiction. (Claim 4) ☐

Now define the function $\text{[math]}$ with domain $\text{[math]}$ by $\text{[math]}$ . The argument in the proof of Claim 4, involving $\text{[math]}$ , shows that $\text{[math]}$ for all $\text{[math]}$ . Moreover, the proof of Claim 1 adapts to show that $\text{[math]}$ is unique. (Theorem) ☐

Remark 6.2.6. Let $\text{[math]}$ be a well-ordering on $\text{[math]}$ . In Theorem 6.2.5, let $\text{[math]}$ be a formula that contains parameters (free variables other than $\text{[math]}$ and $\text{[math]}$ ). The function $\text{[math]}$ given in Theorem 6.2.5 depends on the values that are assigned to these parameters. To illustrate this, suppose that $\text{[math]}$ is a parameter appearing in $\text{[math]}$ . Because $\text{[math]}$ is a free variable in $\text{[math]}$ , we can express $\text{[math]}$ as $\text{[math]}$ . Now let $\text{[math]}$ be a set that can be assigned to the parameter $\text{[math]}$ so that $\text{[math]}$ is functional. Theorem 6.2.5 implies that there is a unique function $\text{[math]}$ such that $\text{[math]}$ , for all $\text{[math]}$ . So $\text{[math]}$ depends on $\text{[math]}$ , and Theorem 6.2.5 holds whenever the formula $\text{[math]}$ contains fixed sets, because these sets can be viewed as values that have been assigned to parameters (see page 25).

Since the relation $\text{[math]}$ is a well-ordering of $\text{[math]}$ , Theorem 6.2.5 and (6.5) (see page 144) imply the next corollary.

Corollary 6.2.7. Let $\text{[math]}$ be a formula that is functional. Then there exists a unique function $\text{[math]}$ with domain $\text{[math]}$ such that

: (6.20)

Let $\text{[math]}$ be as in Corollary 6.2.7. Because $\text{[math]}$ , (6.20) implies that $\text{[math]}$ equals the unique $\text{[math]}$ satisfying $\text{[math]}$ . Since $\text{[math]}$ , we see that $\text{[math]}$ is the unique $\text{[math]}$ for which $\text{[math]}$ holds, and $\text{[math]}$ equals the unique $\text{[math]}$ satisfying $\text{[math]}$ , etc. We now apply Corollary 6.2.7 to show that every set is a subset of a transitive set.

Theorem 6.2.8. For every set $\text{[math]}$ , there exists a transitive set $\text{[math]}$ such that $\text{[math]}$ .

Proof. Let $\text{[math]}$ be a set. Now consider the following definition by cases:

: (6.21)

Let $\text{[math]}$ be a formula that expresses (6.21). Clearly, for each $\text{[math]}$ , there is a unique $\text{[math]}$ so that $\text{[math]}$ . By Corollary 6.2.7, there is a function $\text{[math]}$ with domain $\text{[math]}$ such that $\text{[math]}$ for all $\text{[math]}$ . Thus, for each $\text{[math]}$ , we have that

: (6.22)

Let $\text{[math]}$ . We see that $\text{[math]}$ , by (6.22). So $\text{[math]}$ . Thus, $\text{[math]}$ . To show that $\text{[math]}$ is a transitive set, let $\text{[math]}$ and $\text{[math]}$ . We show that $\text{[math]}$ . Because $\text{[math]}$ , we have $\text{[math]}$ for some $\text{[math]}$ . Thus, $\text{[math]}$ . Since $\text{[math]}$ , we see that $\text{[math]}$ . Hence, $\text{[math]}$ and $\text{[math]}$ is transitive. ☐

Let $\text{[math]}$ , $\text{[math]}$ , and $\text{[math]}$ be as in the statement and the proof of Theorem 6.2.8. By evaluating $\text{[math]}$ for $\text{[math]}$ , one can verify that

Definition 6.2.9. Let $\text{[math]}$ be a set. Then the set $\text{[math]}$ constructed in the proof of Theorem 6.2.8 is called the transitive closure of $\text{[math]}$ .

Exercise 6 shows that $\text{[math]}$ , the transitive closure of a set $\text{[math]}$ , is the “smallest” transitive set of which $\text{[math]}$ is a subset.

Exercises 6.2

1. Complete the proof of Theorem 6.2.1 by showing that the function $\text{[math]}$ satisfies $\text{[math]}$ , for all $\text{[math]}$ . Also show that $\text{[math]}$ is the only such function.

2. Show that Theorem 6.2.5 implies Theorem 6.2.1.

3. Let $\text{[math]}$ be a well-ordering on a set $\text{[math]}$ and $\text{[math]}$ be a set. Define $\text{[math]}$ by $\text{[math]}$ equals the $\text{[math]}$ -least $\text{[math]}$ in $\text{[math]}$ such that $\text{[math]}$ . So if $\text{[math]}$ and $\text{[math]}$ , then $\text{[math]}$ . Let $\text{[math]}$ be a function. Show that Theorem 6.2.1 implies there exists a function $\text{[math]}$ such that

4. Suppose that $\text{[math]}$ is a well-ordering on a set $\text{[math]}$ and $\text{[math]}$ is a function. Let $\text{[math]}$ be as in Theorem 6.2.1.

(a) Let $\text{[math]}$ and $\text{[math]}$ be in $\text{[math]}$ . Prove that if $\text{[math]}$ , then $\text{[math]}$ .

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

5. Let $\text{[math]}$ be a well-ordering on $\text{[math]}$ and $\text{[math]}$ be a well-ordering on $\text{[math]}$ . Assume for each $\text{[math]}$ , there is a $\text{[math]}$ such that $\text{[math]}$ for all $\text{[math]}$ . Show that there is an $\text{[math]}$ so that for all $\text{[math]}$ and $\text{[math]}$ , if $\text{[math]}$ , then $\text{[math]}$ .

6. Let $\text{[math]}$ be a set. Suppose that $\text{[math]}$ where $\text{[math]}$ is a transitive set. Prove that $\text{[math]}$ . Thus, $\text{[math]}$ is the “smallest” transitive set for which $\text{[math]}$ is a subset.

7. Let $\text{[math]}$ be a set. Conclude from Exercise 6 that $\text{[math]}$ is the smallest transitive set that contains $\text{[math]}$ as an element.

8. Let $\text{[math]}$ be a set. Using the replacement axiom, one can show that $\text{[math]}$ is a set. Establish the following:

(a) Prove that if $\text{[math]}$ , then $\text{[math]}$ .

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

(d) Prove that $\text{[math]}$ .

9. Let $\text{[math]}$ be a set. Using the proof of Theorem 6.2.8 as a model, prove that there is a function $\text{[math]}$ with domain $\text{[math]}$ such that

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

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

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

10. Let $\text{[math]}$ be a set. Using the proof of Theorem 6.2.8 as a model, prove that there is a function $\text{[math]}$ with domain $\text{[math]}$ such that

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

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

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

Exercise Notes: For Exercise 6, let $\text{[math]}$ be as in the proof of Theorem 6.2.8, and prove that $\text{[math]}$ . For Exercise 8, use Exercise 6.