Copyright\begin{matrix}c \\ ◯ \end{matrix}1995–2009 by Stephen G. Simpson

Foundations of Mathematics

Stephen G. Simpson

October 1, 2009

Department of Mathematics The Pennsylvania State University University Park, State College PA 16802

             simpson@math.psu.edu

This is a set of lecture notes for my course, Foundations of Mathematics I, offered as Mathematics 558 at the Pennsylvania State University, most recently in Fall 2009.

Contents

1 Computable Functions 6 1.1 Primitive Recursive Functions . . . . . . . . . . . . . . . . . . . . 6 1.2 The Ackermann Function . . . . . . . . . . . . . . . . . . . . . . 13 1.3 Computable Functions . . . . . . . . . . . . . . . . . . . . . . . . 17 1.4 Partial Recursive Functions . . . . . . . . . . . . . . . . . . . . . 23 1.5 The Enumeration Theorem . . . . . . . . . . . . . . . . . . . . . 25 1.6 Consequences of the Enumeration Theorem . . . . . . . . . . . . 30 1.7 Unsolvable Problems . . . . . . . . . . . . . . . . . . . . . . . . . 34 1.8 The Recursion Theorem . . . . . . . . . . . . . . . . . . . . . . . 39 1.9 The Arithmetical Hierarchy . . . . . . . . . . . . . . . . . . . . . 41

2 Undecidability of Arithmetic 48 2.1 Terms, Formulas, and Sentences . . . . . . . . . . . . . . . . . . . 48 2.2 Arithmetical Definability . . . . . . . . . . . . . . . . . . . . . . . 50 2.3 Gödel Numbers of Formulas . . . . . . . . . . . . . . . . . . . . . 57

3 The Real Number System 60 3.1 Quantifier Elimination . . . . . . . . . . . . . . . . . . . . . . . . 60 3.2 Decidability of the Real Number System . . . . . . . . . . . . . . 66

4 Informal Set Theory 69 4.1 Operations on Sets . . . . . . . . . . . . . . . . . . . . . . . . . . 69 4.2 Cardinal Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . 71 4.3 Well-Orderings and Ordinal Numbers . . . . . . . . . . . . . . . 74 4.4 Transfinite Recursion . . . . . . . . . . . . . . . . . . . . . . . . . 78 4.5 Cardinal Numbers, Continued . . . . . . . . . . . . . . . . . . . . 81 4.6 Cardinal Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . 83 4.7 Some Classes of Cardinals . . . . . . . . . . . . . . . . . . . . . . 85 4.8 Pure Well-Founded Sets . . . . . . . . . . . . . . . . . . . . . . . 87 4.9 Set-Theoretic Foundations . . . . . . . . . . . . . . . . . . . . . . 88

5 Axiomatic Set Theory 92 5.1 The Axioms of Set Theory . . . . . . . . . . . . . . . . . . . . . . 92 5.2 Models of Set Theory . . . . . . . . . . . . . . . . . . . . . . . . 96 5.3 Transitive Models and Inaccessible Cardinals . . . . . . . . . . . 99 5.4 Constructible Sets . . . . . . . . . . . . . . . . . . . . . . . . . . 103 5.5 Forcing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 5.6 Independence of CH . . . . . . . . . . . . . . . . . . . . . . . . . 111

6 Topics in Set Theory 114 6.1 Stationary Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 6.2 Large Cardinals . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 6.3 Ultrafilters and Ultraproducts . . . . . . . . . . . . . . . . . . . . 116 6.4 Measurable Cardinals . . . . . . . . . . . . . . . . . . . . . . . . 119 6.5 Ramsey’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . 119

List of Figures

1.1 Register Machine Instructions . . . . . . . . . . . . . . . . . . . . 18 1.2 An Addition Program . . . . . . . . . . . . . . . . . . . . . . . . 18 1.3 The Initial Functions . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.4 Generalized Composition . . . . . . . . . . . . . . . . . . . . . . 20 1.5 A Multiplication Program . . . . . . . . . . . . . . . . . . . . . . 21 1.6 Primitive Recursion . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.7 Minimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 1.8 A Program with Labeled Instructions . . . . . . . . . . . . . . . 27 1.9 Incrementing P_{i} . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 1.10 Decrementing P_{i} . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 1.11 Stopping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 1.12 Parametrization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

List of Tables

1.1 The Ackermann branches. . . . . . . . . . . . . . . . . . . . . . . 14

Chapter 1

Computable Functions

We use ℕ to denote the set of natural numbers,

ℕ = {0, 1, 2, …} .

For k ≥ 1, the k-fold Cartesian product

\underbrace{ℕ × … × ℕ}_{k}

is denoted ℕ^{k}. A k-place function is a function f : ℕ^{k} → ℕ and is sometimes indicated with the lambda-notation,

f = λx_{1} ⋯ x_{k} [ f(x_{1}, …, x_{k}) ] .

A number-theoretic function is a k-place function for some k ≥ 1.

The purpose of this chapter is to define and study an important class of number-theoretic functions, the recursive functions (sometimes called the computable functions). We begin with a certain subclass known as the primitive recursive functions.

1.1 Primitive Recursive Functions

Loosely speaking, a recursion is any kind of inductive definition, and a primitive recursion is an especially straightforward kind of recursion, in which the value of a number-theoretic function at argument x + 1 is defined in terms of the value at argument x. For example, the factorial function λx [ x! ] is defined by the primitive recursion equations 0! = 1, (x + 1)! = x!(x + 1). A numbertheoretic function is said to be primitive recursive if it can be built up by means of primitive recursions. This concept is made precise in the following definition.

Definition 1.1.1 (Primitive Recursive Functions). The class PR of primitive recursive functions is the smallest class C of number-theoretic functions having the following closure properties.

1. The constant zero function Z = λx [ 0 ] belongs to C.

2. The successor function S = λx [ x + 1 ] belongs to C.

3. For each k ≥ 1 and 1 ≤ i ≤ k, the projection function P_{ki} = λx_{1} ⋯ x_{k} [ x_{i}] belongs to C.

4. C is closed under generalized composition. This means that whenever the k-place functions

λx_{1} ⋯ x_{k} [ g_{1}(x_{1}, …, x_{k}) ], …, λx_{1} ⋯ x_{k} [ g_{m}(x_{1}, …, x_{k}) ]

and the m-place function λy_{1} ⋯ y_{m} [ h(y_{1}, …, y_{m}) ] all belong to C, then the k-place function

f = λx_{1} ⋯ x_{k} [ h(g_{1}(x_{1}, …, x_{k}), …, g_{m}(x_{1}, …, x_{k})) ]

also belongs to C. Here f is defined by

f(x_{1}, …, x_{k}) = h(g_{1}(x_{1}, …, x_{k}), …, g_{m}(x_{1}, …, x_{k})) .

5. C is closed under primitive recursion. This means that whenever the k-place function λx_{1} ⋯ x_{k} [ g(x_{1}, …, x_{k}) ] and the (k+2)-place function

λyzx_{1} ⋯ x_{k} [ h(y, z, x_{1}, …, x_{k}) ]

belong to C, then the (k+1)-place function λyx_{1} ⋯ x_{k} [ f(y, x_{1}, …, x_{k}) ] defined by

\begin{aligned}f(0, x_{1}, …, x_{k}) & = & g(x_{1}, …, x_{k}) \\ f(y + 1, x_{1}, …, x_{k}) & = & h(y, f(y, x_{1}, …, x_{k}), x_{1}, …, x_{k}) \end{aligned}

also belongs to C.

We now list some examples of primitive recursive functions.

Examples 1.1.2.

1. The recursion equations

\begin{aligned}x + 0 & = & x \\ x + (y + 1) & = & (x + y) + 1 \end{aligned}

show that the addition function λxy [ x + y] is primitive recursive.

2. The recursion equations

\begin{aligned}x · 0 & = & 0 \\ x · (y + 1) & = & (x · y) + x \end{aligned}

show that the multiplication function λxy [ x · y] is primitive recursive.

3. The recursion equations

\begin{aligned}x^{0} & = & 1 \\ x^{y+1} & = & x^{y} · x \end{aligned}

show that the exponentiation function λxy [ x^{y}] is primitive recursive.

4. As already mentioned, the recursion equations

\begin{aligned}0! & = & 1 \\ (x + 1)! & = & x! · (x + 1) \end{aligned}

show that the factorial function λx [ x! ] is primitive recursive.

We now proceed to further enlarge our library of primitive recursive functions. First, the recursion equations P (0) = 0, P (x + 1) = x show that the “predecessor” function

P (x) = \{ \begin{matrix}x − 1 & if x > 0 , \\ 0 & if x = 0 \end{matrix}

is primitive recursive. We can then obtain the truncated subtraction function

x · − y = \{ \begin{matrix}x − y & if x ≥ y, \\ 0 & if x < y \end{matrix}

using primitive recursion equations x · −0 = x, x · −(y+1) = P (x · −y). (Truncated subraction is useful because ordinary subtraction is not a function from ℕ^{2} into ℕ.) We shall also have use for

|x − y| = (x · − y) + (y · − x)

and α(x) = 1 · − x. Note that

α(x) = \{ \begin{matrix}0 & if x > 0 , \\ 1 & if x = 0 . \end{matrix}

The following exercise will become easy after we have developed a little more machinery.

Exercise 1.1.3. Show that the Fibonacci function, defined by

fib(0) = 0 ,
fib(1) = 1 ,
fib(x + 2) = fib(x) + fib(x + 1)

is primitive recursive. (The first few values of this function are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ….)

In addition to primitive recursive functions, we shall want to consider primitive recursive predicates. By a k-place predicate we mean a subset of ℕ^{k}. If R ⊆ ℕ^{k} is a k-place predicate and x_{1}, …, x_{k} are elements of ℕ, we say that R(x_{1}, …, x_{k}) is true if ⟨x_{1}, …, x_{k}⟩ ∈ R, otherwise false. A number-theoretic predicate is a k-place predicate for some k ≥ 1.

Definition 1.1.4. A k-place predicate R ⊆ ℕ^{k} is said to be primitive recursive if its characteristic function

χ_{R}(x_{1}, …, x_{k}) = \{ \begin{matrix}1 & if R(x_{1}, …, x_{k}) is true \\ 0 & if R(x_{1}, …, x_{k}) is false \end{matrix}

is primitive recursive.

For example, the 2-place predicates x = y and x < y are primitive recursive, since χ_{=}(x, y) = α(|x − y|) and χ_{<}(x, y) = α(α(y · − x)).

Lemma 1.1.5 (Boolean Connectives). If P and Q are primitive recursive predicates, then so are ¬ P, P ∧ Q, and P ∨ Q. (Here ¬, ∧, and ∨ denote negation, conjunction, and (nonexclusive) disjunction, respectively.)

Proof. We have χ_{¬ P} = α(χ_{P}) and χ_{P ∧Q} = χ_{P} · χ_{Q}. Also

χ_{P ∨Q} = α(α(χ_{P}) · α(χ_{Q}))

since P ∨ Q ≡ ¬ ((¬ P) ∧ (¬ Q)) (de Morgan’s law).

Lemma 1.1.6 (Iterated Sums and Products). If f(x, y, z_{1}, …, z_{k}) is a primitive recursive function, then so are

g(y, z_{1}, …, z_{k}) = ∑_{x=0}^{y−1} f(x, y, z_{1}, …, z_{k}) (= 0 if y = 0)

and

h(y, z_{1}, …, z_{k}) = ∏_{x=0}^{y−1} f(x, y, z_{1}, …, z_{k}) (= 1 if y = 0) .

Proof. We have g(y, z_{1}, …, z_{k}) = g^{∗}(y, y, z_{1}, …, z_{k}) where

g^{∗}(w, y, z_{1}, …, z_{k}) = ∑_{x=0}^{w−1} f(x, y, z_{1}, …, z_{k}) .

The recursion equations

\begin{aligned}g^{∗}(0, y, z_{1}, …, z_{k}) & = & 0 \\ g^{∗}(w + 1, y, z_{1}, …, z_{k}) & = & g^{∗}(w, y, z_{1}, …, z_{k}) + f(w, y, z_{1}, …, z_{k}) \end{aligned}

show that g^{∗} is primitive recursive, hence g is primitive recursive. The treatment of h is similar.

Lemma 1.1.7 (Finite Conjuction and Disjunction). If R(x, y, z_{1}, …, z_{k}) is a primitive recursive predicate, then so are

P (y, z_{1}, …, z_{k}) ≡ ⋀_{x=0}^{y−1} R(x, y, z_{1}, …, z_{k})

and

Q(y, z_{1}, …, z_{k}) ≡ ⋁_{x=0}^{y−1} R(x, y, z_{1}, …, z_{k}) .

Proof. We have

χ_{P} (y, z_{1}, …, z_{k}) = ∏_{x=0}^{y−1} χ_{R}(x, y, z_{1}, …, z_{k})

and

χ_{Q}(y, z_{1}, …, z_{k}) = α(∏_{x=0}^{y−1} α(χ_{R}(x, y, z_{1}, …, z_{k})))

so our result follows from the previous lemma.

Note that ⋀_{x=0}^{y−1} and ⋁_{x=0}^{y−1} can be paraphrased as “for all x in the range 0 ≤ x < y” and “there exists x in the range 0 ≤ x < y”, respectively. These operators are sometimes called bounded quantifiers.

The above lemmas make it easy to show that many familiar predicates are primitive recursive. For example, the set (i.e., 1-place predicate) of prime numbers is primitive recursive, since

Prime (x) ≡ x is a prime number
≡ x > 1 ∧ ¬ ⋁_{u<x} ⋁_{v<x} (x = u · v ∧ u > 1 ∧ v > 1) .

Similarly, the following lemma can be used to show that many familiar functions are primitive recursive.

Lemma 1.1.8 (Bounded Least Number Operator). If R(x, y, z_{1}, …, z_{k}) is a primitive recursive predicate, then the function

f(y, z_{1}, …, z_{k}) = \{ \begin{matrix}least x < y such that R(x, y, z_{1}, …, z_{k}) holds , \\ if such x exists , \\ y otherwise \end{matrix}

is primitive recursive.

Proof. We have

\begin{aligned}f(y, z_{1}, …, z_{k}) & = & ∑_{x=0}^{y−1} (x · χ_{R}(x, y, z_{1}, …, z_{k}) · ∏_{w=0}^{x−1} α(χ_{R}(w, y, z_{1}, …, z_{k}))) \\ & & + y · ∏_{x=0}^{y−1} α(χ_{R}(x, y, z_{1}, …, z_{k})) , \end{aligned}

so f is primitive recursive.

For example, consider the function λn [ p_{n}] which enumerates the prime numbers in increasing order. (The first few values of this function are p_{0} = 2, p_{1} = 3, p_{2} = 5, p_{3} = 7, ….) We want to use the bounded least number operator to show that λn [ p_{n}] is primitive recursive. First, recall a famous theorem of Euclid which gives the bound p_{n+1} ≤ p_{n}!+1. We can then write p_{0} = 2, p_{n+1} = least x ≤ p_{n}! + 1 such that Prime (x) and x > p_{n}. Thus λn [ p_{n}] is primitive recursive.

As another application of the bounded least number operator, note that the functions

Quotient (y, x) = ⌊y/x⌋ = q ,
Remainder (y, x) = (y mod x) = r ,

where y = q · x + r, 0 ≤ r < x, 0 ≤ q, are primitive recursive, in view of

Quotient (y, x) = least q ≤ y such that ⋁_{r<x}(y = q · x + r) ,
Remainder (y, x) = least r < x such that ⋁_{q≤y}(y = q · x + r) .

Using the bounded least number operator, we can obtain a primitive recursive method of encoding ordered pairs of natural numbers as single numbers. For our pairing function we use λuv [ 2^{u}3^{v}]. The unpairing functions are then λz [ (z)_{0} ] and λz [ (z)_{1} ], where

(z)_{n} = least w < z such that Remainder(z, p_{n}^{w+1}) ≠ 0
= the exponent of p_{n} in the prime power factorization of z .

Note that (2^{u}3^{v})_{0} = u and (2^{u}3^{v})_{1} = v.

More generally, we can encode variable-length finite sequences of natural numbers as single numbers. The sequence ⟨a_{0}, a_{1}, …, a_{m−1}⟩ is encoded by

a = ∏_{x<m} p_{x}^{a_{x}} ,

and for decoding we can use the primitive recursive function λzx [ (z)_{x}], since (a)_{x} = a_{x}. This method of prime power coding will be used extensively in the proof of the Enumeration Theorem, below.

The pairing and unpairing functions make it easy to show that the Fibonacci function is primitive recursive (cf. Exercise 1.1.3). Namely, we first note that the auxiliary function λx [ fibpair(x) ], defined by

fibpair(x) = 2^{fib(x)}3^{fib(x+1)} ,

is primitive recursive in view of

fibpair(0) = 2^{0}3^{1} ,
fibpair(x + 1) = 2^{(fibpair(x))^{1}}3^{(fibpair(x))_{0}+(fibpair(x))_{1}} .

Then λx [ fib(x) ] is primitive recursive since fib(x) = (fibpair(x))_{0}.

Exercise 1.1.9. Show that the 2-place number-theoretic functions GCD(x, y) and LCM(x, y), the greatest common divisor and least common multiple of x and y, are primitive recursive.

Solution. LCM(x, y) = least z ≤ x·y such that Remainder(z, x) = Remainder(z, y) = 0. GCD(x, y) = xy/LCM(x, y).

Exercise 1.1.10. Show that the 1-place number-theoretic function f(n) given by

f(n) = 1 + ∑_{k=0}^{n−1} f(k)^{n}

is primitive recursive.

Solution. Consider the so-called course-of-values function

f̃(n) = ∏_{k=0}^{n−1} p_{k}^{f(k)} ,

i.e., f̃(n) encodes the variable-length finite sequence ⟨f(0), f(1), …, f(n − 1)⟩ via prime power coding. Then f̃(n) is primitive recursive, in view of the recursion equations f̃(0) = 1 and

f̃(n + 1) = f̃(n) · p_{n}^{h(n,f̃(n))} ,

where h(n, z) = 1 + ∑_{k=0}^{n−1}((z)_{k})^{n}. It now follows that f(n) = (f̃(n + 1))_{n} is primitive recursive. This general technique is known as course-of-values recursion.

Exercise 1.1.11. Show that the function λn ( nth digit of \sqrt{2} ) is primitive recursive.

Solution. The nth digit of \sqrt{2} is f(n) = Remainder(g(n), 10), where g(n) = the least x < 4 · 10^{2n} such that (x + 1)^{2} > 2 · 10^{2n}.

Exercise 1.1.12. Show that the 1-place number-theoretic function

f(n) = the nth decimal digit of π = 3.141592 ⋯

is primitive recursive.

Hint: You may want to use the fact that |π − a/b| > 1/b^{42} for all integers a, b > 1. This result is due to K. Mahler, On the approximation of π, Nederl. Akad. Wetensch. Proc. Ser. A., 56, Indagationes Math., 15, 30–42, 1953.

Solution. We use the well-known series

\frac{π}{4} = 1 − \frac{1}{3} + \frac{1}{5} − \frac{1}{7} + \frac{1}{9} − ⋯ = ∑_{n=0}^{∞} \frac{(−1)^{n}}{2n + 1} ,

i.e.,

π = 4 − \frac{4}{3} + \frac{4}{5} − \frac{4}{7} + \frac{4}{9} − ⋯ = ∑_{n=0}^{∞} \frac{(−1)^{n}4}{2n + 1} .

Let S_{k} be the kth partial sum of this series. We have S_{k} = a(k)/b(k) where the functions a(k) and b(k) are primitive recursive, namely

a(k) = ∑_{n=0}^{k} \frac{(−1)^{n}4(2k + 1)!}{2n + 1}

and b(k) = (2k + 1)!. Note also that the functions

g(n, a, b) = (μi < 10^{n}b) (10^{i}a ≥ 10^{n}b)

and

h(n, a, b) = Rem(Quot(10^{g(n,a,b)}a, b), 10) = the nth digit of a/b

is primitive recursive. By Mahler’s result, for each n there exists k < 10^{50n} such that S_{k} and S_{k+1} have the same first n digits. Since π lies between S_{k} and S_{k+1}, it follows that S_{k} and π have the same first n digits, so in particular f(n) = the nth digit of S_{k}. Using the bounded least number operator, we have f(n) = h(n, a(k(n)), b(k(n))) where k(n) = the least k < 10^{50n} such that ⋀_{m=0}^{n} g(m, a(k), b(k)) = g(m, a(k + 1), b(k + 1)). Clearly this is primitive recursive.

1.2 The Ackermann Function

In this section we present an example of a function which is not primitive recursive, yet is clearly computable in some intuitive sense. The precise concept of computability which we have in mind will be explained in the next section.

Definition 1.2.1. We define a sequence of 1-place functions A_{n}, n ∈ ℕ, as follows:

\begin{aligned}A_{0}(x) & = & 2x, \\ A_{n+1}(x) & = & \underbrace{A_{n}A_{n} ⋯ A_{n}}_{x}(1) . \end{aligned}

Thus A_{0}(x) = 2x, A_{1}(x) = 2^{x}, A_{2}(x) = 2^{2^{·^{·^{·^{2}}}}}(height x), etc.

Exercise 1.2.2 (the Ackermann hierarchy).

1. Show that, for each n, λx [ A_{n}(x) ] is primitive recursive.

2. Show that

(a) A_{n}(x + 1) > A_{n}(x) > x for all x ≥ 1 and all n.

(b) A_{n+1}(x) ≥ A_{n}(x + 1) for all x ≥ 3 and all n.

3. Show that for each k-place primitive recursive function

λx_{1} … x_{k} [ f(x_{1}, …, x_{k}) ]

there exists n such that

f(x_{1}, …, x_{k}) ≤ A_{n}(max(3, x_{1}, …, x_{k}))

for all x_{1}, …, x_{k}.

4. Show that the 2-place function λnx [ A_{n}(x) ] is not primitive recursive. This is known as the Ackermann function.

5. Show that the 3-place relation λnxy [ A_{n}(x) = y] is primitive recursive. Use this to show that the Ackermann function is computable, i.e., recursive, in the sense of Section 1.3.

Solutions.

1. Show that A_{n}(1) = 2, A_{n}(2) = 4, and A_{n+1}(3) = A_{n}(4) for all n. Compute A_{n}(x) for all n, x with n + x ≤ 8.

Solution. For all n we have A_{n+1}(1) = A_{n}(1), hence by induction A_{n}(1) = A_{0}(1) = 2. Also A_{n+1}(2) = A_{n}(A_{n}(1)) = A_{n}(2), hence by induction A_{n}(2) = A_{0}(2) = 4. Also, for all n and x we have A_{n+1}(x + 1) = A_{n}(A_{n+1}(x)), in particular A_{n+1}(3) = A_{n}(A_{n+1}(2)) = A_{n}(4). Table 1.1 shows A_{n}(x) for small values of n, x.

Table 1.1: The Ackermann branches.

0 1 2  3  4  5
A_{0} 0 2 4  6  8  10
A_{1} 1 2 4  8  16  32
A_{2} 1 2 4  16  2^{16}  2^{2^{16}}
A_{3} 1 2 4  2^{16}  2^{2^{·^{·^{·^{2}}}}}(height 2^{16}) 2^{2^{·^{·^{·^{2}}}}}(height 2^{2^{·^{·^{·^{2}}}}}(height 2^{16}))
A_{4} 1 2 4 2^{2^{·^{·^{·^{2}}}}}(height 2^{16}) A_{3}(2^{2^{·^{·^{·^{2}}}}}(height 2^{16}))
A_{5} 1 2 4 A_{3}(2^{2^{·^{·^{·^{2}}}}}(height 2^{16}))
A_{6} 1 2 4

2. Prove the following:

(a) A_{n}(x + 1) > A_{n}(x) > x for all x ≥ 1 and all n.

(b) A_{n+1}(x) ≥ A_{n}(x + 1) for all x ≥ 3 and all n.

(c) For each primitive recursive function f(x_{1}, …, x_{k}) there exists n such that A_{n} covers f, i.e.,

f(x_{1}, …, x_{k}) ≤ A_{n}(max(3, x_{1}, …, x_{k}))

for all x_{1}, …, x_{k}.

(d) The 1-place function λx (A_{x}(x)) is not primitive recursive.

(e) The 2-place function λxy (A_{x}(y)) is not primitive recursive.

Solution. First we prove A_{n}(x + 1) > A_{n}(x) > x for x ≥ 1, by induction on n. For n = 0 we have A_{0}(x + 1) = 2x + 2 > 2x = A_{0}(x) for all x, and A_{0}(x) = 2x > x for x ≥ 1. For n + 1 and x ≥ 1 we have A_{n+1}(x + 1) = A_{n}(A_{n+1}(x)) > A_{n+1}(x) by inductive hypothesis. Thus A_{n+1} is strictly monotone. Since A_{n+1}(0) > 0, it follows that A_{n+1}(x) > x for all x.

Next we prove A_{n+1}(x) ≥ A_{n}(x+1) for x ≥ 3, by induction on x. For x = 3 we have A_{n+1}(3) = A_{n}(4) as noted above, and inductively A_{n+1}(x + 1) = A_{n}(A_{n+1}(x)) ≥ A_{n}(A_{n}(x+1)) ≥ A_{n}(x+2), since A_{n} is strictly monotone and A_{n}(x + 1) ≥ x + 2 by what has already been proved.

Next we prove that each primitive recursive function is covered by A_{n} for some n. We prove this by induction on the class of primitive recursive functions. We begin by noting that the initial functions are covered by A_{0}.

Suppose f is obtained by generalized composition, say

f(x_{1}, …, x_{k}) = h(g_{1}(x_{1}, …, x_{k}), …, g_{m}(x_{1}, …, x_{k})).

Let n be such that A_{n} covers h and A_{n+1} covers g_{1}, …, g_{m}. We then have

f(x_{1}, …, x_{k}) = h(g_{1}(x_{1}, …, x_{k}), …, g_{m}(x_{1}, …, x_{k}))
≤ A_{n}(max(3, g_{1}(x_{1}, …, x_{k}), …, g_{m}(x_{1}, …, x_{k})))
≤ A_{n}(A_{n+1}(max(3, x_{1}, …, x_{k})))
= A_{n+1}(max(3, x_{1}, …, x_{k}) + 1)
≤ A_{n+2}(max(3, x_{1}, …, x_{k})),

i.e., A_{n+2} covers f.

Suppose f is obtained by primitive recursion, say

\begin{aligned}f(0, x_{1}, …, x_{k}) & = & g(x_{1}, …, x_{k}), \\ f(y + 1, x_{1}, …, x_{k}) & = & h(y, f(y, x_{1}, …, x_{k}), x_{1}, …, x_{k}). \end{aligned}

Let n be such that A_{n} covers h and A_{n+1} covers g. We first claim that

f(y, x_{1}, …, x_{k}) ≤ A_{n+1}(y + max(3, x_{1}, …, x_{k}))

for all y, x_{1}, …, x_{k}. We prove this by induction on y. For y = 0 we have f(0, x_{1}, …, x_{k}) = g(x_{1}, …, x_{k}) ≤ A_{n+1}(max(3, x_{1}, …, x_{k})). For the inductive step we have

f(y + 1, x_{1}, …, x_{k}) = h(y, f(y, x_{1}, …, x_{k}), x_{1}, …, x_{k})
≤ A_{n}(max(3, y, f(y, x_{1}, …, x_{k}), x_{1}, …, x_{k})
≤ A_{n}(max(3, y, A_{n+1}(y + max(3, x_{1}, …, x_{k})), x_{1}, …, x_{k})
= A_{n}(A_{n+1}(y + max(3, x_{1}, …, x_{k})))
= A_{n+1}(y + 1 + max(3, x_{1}, …, x_{k}))

and this proves our claim. We then have

f(y, x_{1}, …, x_{k}) ≤ A_{n+1}(y + max(3, x_{1}, …, x_{k}))
≤ A_{n+1}(2 max(3, y, x_{1}, …, x_{k}))
≤ A_{n+1}(A_{n+2}(max(3, y, x_{1}, …, x_{k})))
= A_{n+2}(max(3, y, x_{1}, …, x_{k}) + 1)
≤ A_{n+3}(max(3, y, x_{1}, …, x_{k})),

i.e., A_{n+3} covers f. This completes the proof that each primitive recursive function is covered by A_{n} for some n.

Now, if A_{x}(x) were primitive recursive, then A_{x}(x) + 1 would be primitive recursive, hence covered by A_{n} for some n ≥ 3. But then in particular A_{n}(n) + 1 ≤ A_{n}(max(3, n)) = A_{n}(n), a contradiction. Thus the 1-place function A_{x}(x) is not primitive recursive. It follows immediately that the 2-place function A_{x}(y) is not primitive recursive.

3. Show that the 3-place relation

{⟨x, y, z⟩ | A_{x}(y) = z}

is primitive recursive. Use this to prove that λxy (A_{x}(y)) is recursive. Hence λx (A_{x}(x)) is recursive.

Solution. For all x, y > 0 we have

0 < y < A_{x}(y) = A_{x−1}(A_{x}(y − 1)) = A_{x−1}(y′)

where y′ = A_{x}(y − 1). Since A_{x−1}(y′) = A_{x}(y) ≥ 2, it follows that 0 < y′ < A_{x−1}(y′) = A_{x}(y). Repeating this step x times, we obtain a finite sequence y_{0}, y_{1}, y_{2}, …, y_{x} starting with y such that

A_{x}(y) = A_{x}(y_{0}) = A_{x−1}(y_{1}) = A_{x−2}(y_{2}) = ⋯ = A_{0}(y_{x}) = 2y_{x},

and each of y_{0}, y_{1}, …, y_{x} is > 0 and < A_{x}(y). Moreover, if y > 2 then we also have x < A_{x}(y). Thus the 3-place predicate A_{x}(y) = z can be defined by course-of-values recursion on z as follows:

A_{x}(y) = z if and only if
(x = 0 ∧ z = 2y) ∨
(x > 0 ∧ y = 0 ∧ z = 1) ∨
(x > 0 ∧ y = 1 ∧ z = 2) ∨
(x > 0 ∧ y = 2 ∧ z = 4) ∨
(x > 0 ∧ y > 2 ∧ x < z ∧ ∃y_{0}, y_{1}, …, y_{x} < z
(y_{0} = y ∧ ∀i < x (y_{i+1} = A_{x−i}(y_{i} − 1)) ∧ z = 2y_{x})).

Actually, the function being defined by primitive recursion is

a(w) = ∏{p_{2^{x}3^{y}5^{z}} | A_{x}(y) = z ∧ x, y, z < w}.

In any case, it follows that the 3-place predicate A_{x}(y) = z is primitive recursive. Applying the least number operator, we see that the 2-place function A_{x}(y) is recursive. It follows immediately that the 1-place function A_{x}(x) is recursive.

1.3 Computable Functions

In this section we define the class of computable (i.e., recursive) number-theoretic functions. We show that the primitive recursive functions form a proper subclass of the computable functions.

Our definition will be given in terms of a register machine. We assume the existence of infinitely many registers R_{1}, R_{2}, …, R_{i}, …. At any given time, each register contains a natural number. If the number contained in R_{i} is 0, we say that R_{i} is empty. At any given time, all but finitely many of the registers are empty. The basic actions that the machine can perform are to increment or decrement a register, i.e., add or subtract 1 from the number contained in it.

A register machine program consists of finitely many instructions linked together in a flow diagram indicating the order in which the instructions are to be executed. There are four types of instructions: R_{i}^{+}, R_{i}^{−}, start, and stop. Each program contains exactly one start instruction, which is executed first. An R_{i}^{+} instruction is executed by incrementing R_{i} and then proceeding to another, specified, instruction. An R_{i}^{−} instruction is executed by testing R_{i} for emptiness. If R_{i} is empty, we proceed to one of two specified instructions. If R_{i} is nonempty, we decrement it and then proceed to the other of the two specified instructions. A stop instruction causes execution of the program to halt. See Figure 1.1.

For example, consider the addition program depicted in Figure 1.2. If we run this program starting with natural numbers x and y in R_{1} and R_{2} respectively, the run will eventually halt with x + y in R_{3}.

[figure: start; R_{i}^{+}]

begin run of program  increment register R_{i}
[figure: R_{i}^{−}; e; stop]

if R_{i} empty go to e,  terminate run of program

otherwise decrement R_{i} Figure 1.1: Register Machine Instructions

[figure: start; R_{3}^{−}; e; R_{1}^{−}; e; R_{2}^{−}; e; stop; R_{3}^{+}; R_{3}^{+}]

Figure 1.2: An Addition Program

Let P be a register machine program, and let x_{1}, …, x_{k} be natural numbers, i.e., elements of ℕ. We write P(x_{1}, …, x_{k}) to denote the unique run of P starting with x_{1} in R_{1}, …, x_{k} in R_{k}, and all other registers empty. Uniqueness follows from the fact that the register machine operates deterministically.

Definition 1.3.1 (Computable Functions). A k-place number-theoretic function

λx_{1} … x_{k} [ f(x_{1}, …, x_{k}) ]

is said to be computable if there exists a register machine program P which computes it, i.e. for all x_{1}, …, x_{k} ∈ ℕ, P(x_{1}, …, x_{k}) eventually halts with y = f(x_{1}, …, x_{k}) in R_{k+1}.

For example, the addition program of Figure 1.2 shows that λx_{1}x_{2} [ x_{1} + x_{2} ] is computable.

We shall now prove that all primitive recursive functions are computable.

Lemma 1.3.2. The initial functions Z, S, and P_{ki}, 1 ≤ i ≤ k, are computable.

Proof. The functions Z = λx [ 0 ], S = λx [ x + 1 ], and P_{ki} = λx_{1} … x_{k} [ x_{i}] are computed by the register machine programs given in Figure 1.3.

Zero  [figure: start; stop]

Successor  [figure: start; R_{1}^{−}; e; R_{2}^{+}; stop; R_{2}^{+}]

Projection  [figure: start; R_{i}^{−}; e; stop; R_{k+1}^{+}]

Figure 1.3: The Initial Functions

[figure: start; F_{1}^{−}; e; …; e; F_{k}^{−}; e; G_{1}; G_{1 k+1}^{−}; e; …; e; G_{m}; G_{m k+1}^{−}; e; H; G_{11}^{+}; G_{1k}^{+}; H_{1}^{+}; H_{m}^{+}; ⋮; ⋮; F_{k+1}^{+}; H_{m+1}^{−}; e; G_{m1}^{+}; G_{mk}^{+}; stop]

Figure 1.4: Generalized Composition

Lemma 1.3.3. The class of computable functions is closed under generalized composition.

Proof. Assume that

λx_{1} … x_{k} [ g_{1}(x_{1}, …, x_{k}) ] , …, λx_{1} … x_{k} [ g_{m}(x_{1}, …, x_{k}) ]

and λy_{1} … y_{m} [ h(y_{1}, …, y_{m}) ] are computed by register machine programs G_{1}, …, G_{m}, H respectively. For convenience we regard these programs as being executed on pairwise disjoint sets of registers. We use G_{j1}, …, G_{jk}, G_{j,k+1}, … to denote the registers on which G_{j} is executed, 1 ≤ j ≤ m. We use H_{1}, …, H_{m}, H_{m+1}, … to denote the registers on which H is executed.

To compute λx_{1} … x_{k} [ f(x_{1}, …, x_{k}) ] where

f(x_{1}, …, x_{k}) = h(g_{1}(x_{1}, …, x_{k}), …, g_{m}(x_{1}, …, x_{k})) .

we shall use a register machine program F which we regard as being executed on registers F_{1}, …, F_{k}, F_{k+1}, …. In order to make it easy for F to call G_{1}, …, G_{m}, H, the registers of G_{1}, …, G_{m}, H will be among the auxiliary registers of F. (The auxiliary registers of F are the registers F_{i}, i ≥ k + 2.) Actually, the auxiliary registers of F consist precisely of the registers of G_{1}, …, G_{m}, H. Our program F is given in Figure 1.4.

Lemma 1.3.4. The class of computable functions is closed under primitive recursion.

In proving this lemma, the idea will be to write a program containing a loop which repeatedly calls the iterator h. Let us first illustrate this idea with a simple example.

Example 1.3.5. The multiplication function λx_{1}x_{2} [ x_{1} · x_{2} ] is computed by iterated addition, using the program given in Figure 1.5.

[figure: start; R_{1}^{−}; e; R_{2}^{−}; e; R_{4}^{−}; e; stop; R_{3}^{+}; R_{2}^{+}; R_{4}^{+}]

Figure 1.5: A Multiplication Program

Exercise 1.3.6. Write a register machine program which computes the exponential function, i.e., the 2-place number-theoretic function exp(x, y) = x^{y}. Note that x^{0} = 1 for all x.

Proof of Lemma 1.3.4. Assume that λx_{1} … x_{k} [ g(x_{1}, …, x_{k}) ] and

λyzx_{1} … x_{k} [ h(y, z, x_{1}, …, x_{k}) ]

are computed by register machine programs G and H with registers G_{1}, …, G_{k}, G_{k+1}, … and H_{1}, H_{2}, H_{3}, …, H_{k+2}, H_{k+3}, … respectively. To compute λyx_{1} … x_{k} [ f(y, x_{1}, …, x_{k}) ] where

\begin{aligned}f(0, x_{1}, …, x_{k}) & = & g(x_{1}, …, x_{k}) , \\ f(y + 1, x_{1}, …, x_{k}) & = & h(y, f(y, x_{1}, …, x_{k}), x_{1}, …, x_{k}) , \end{aligned}

we use a register machine program F with registers F_{1}, F_{2}, …, F_{k+1}, F_{k+2}, …. See Figure 1.6. The auxiliary registers F_{i}, i ≥ k + 3 of F consist of the registers of G and H plus two additional registers, U and V.

Theorem 1.3.7. Every primitive recursive function is computable.

[figure: start; F_{2}^{−}; e; V^{−}; e; …; e; F_{k+1}^{−}; e; V^{−}; e; G; H_{2}^{+}; V^{+}; F_{2}^{+}; V^{+}; F_{k+1}^{+}; F_{1}^{−}; e; G_{k+1}^{−}; e; G_{1}^{+}; G_{k}^{+}; F_{k+2}^{+}; G_{k+1}^{−}; e; stop; H_{2}^{+}; U^{+}; …; H_{4}^{−}; e; H_{3}^{−}; e; H_{k+3}^{−}; e; U^{−}; e; V^{−}; e; F_{2}^{−}; e; V^{−}; e; …; e; F_{k+1}^{−}; e; V^{−}; e; H; H_{2}^{−}; e; V^{+}; U^{+}; V^{+}; F_{2}^{+}; V^{+}; F_{k+1}^{+}; F_{1}^{−}; e; H_{1}^{−}; e; H_{1}^{+}; H_{3}^{+}; H_{k+2}^{+}; F_{k+2}^{+}; H_{k+3}^{−}; e; stop]

Figure 1.6: Primitive Recursion Proof. The above lemmas show that the computable functions form a class which contains the initial functions and is closed under generalized composition and primitive recursion. Since the primitive recursive functions were defined as the smallest such class, our theorem follows.

1.4 Partial Recursive Functions

A k-place partial function is a function ψ : dom(ψ) → ℕ where dom(ψ) ⊆ ℕ^{k}. We sometimes abbreviate this as ψ : ℕ^{k} ⟶^{P} ℕ. We use dom(ψ) and rng(ψ) to denote the domain and range of ψ, respectively. If dom(ψ) = ℕ^{k}, we say that ψ is total. Thus a total k-place function is just what we have previously called a k-place function.

The use of partial functions leads to expressions which may or may not have a numerical value. (For example, ψ(x_{1}, …, x_{k}) + 3 has a numerical value if and only if ⟨x_{1}, …, x_{k}⟩ ∈ dom(ψ)). If E is such an expression, we say that E is defined or convergent (abbreviated E ↓) if E has a numerical value. We say that E is undefined or divergent (abbreviated E ↑) if E does not have a numerical value. We write E_{1} ≃ E_{2} to mean that E_{1} and E_{2} are both defined and equal, or both undefined.

Definition 1.4.1 (Recursive Functions and Predicates). A k-place (total) function is said to be recursive if and only if it is computable. A k-place predicate is said to be recursive if its characteristic function is recursive.

Definition 1.4.2 (Partial Recursive Functions). A k-place partial function ψ is said to be partial recursive if it is computed by some register machine program P. This means that, for all x_{1}, …, x_{k} ∈ ℕ,

ψ(x_{1}, …, x_{k}) ≃ the number in R_{k+1} if and when P(x_{1}, …, x_{k}) stops .

In particular, ψ(x_{1}, …, x_{k}) is defined if and only if P(x_{1}, …, x_{k}) eventually stops.

Partial recursive functions arise because a particular run of a register machine program may or may not eventually stop. One way this can happen is because of an unbounded search, as in the following lemma.

Lemma 1.4.3 (Unbounded Least Number Operator). Let P (x_{1}, …, x_{k}, y) be a (k+1)-place recursive predicate. Then the k-place partial function ψ defined by

ψ(x_{1}, …, x_{k}) ≃ least y such that P (x_{1}, …, x_{k}, y) holds

is partial recursive.

[figure: start; F_{k+1}^{+}; …; P_{2}^{−}; e; P_{1}^{−}; e; F_{1}^{−}; e; V^{−}; e; …; e; F_{k+1}^{−}; e; V^{−}; e; P; P_{k+2}^{−}; e; V^{+}; F_{1}^{+}; V^{+}; F_{k+1}^{+}; stop; P_{1}^{+}; P_{k+1}^{+}]

Figure 1.7: Minimization

Proof. Assume that χ_{P} is computed by a register machine program P with registers P_{1}, …, P_{k}, P_{k+1}, P_{k+2}, …. To compute ψ we use a register machine program F with registers F_{1}, F_{2}, …, F_{k+1}, …. The auxiliary registers F_{i}, i ≥ k + 2, of F are the registers of P plus an additional register V. See Figure 1.7.

The unbounded least number operator is sometimes called the minimization operator. As a byproduct of the work in the next section, we shall see that all partial recursive functions can be obtained from primitive recursive functions by composition and minimization.

Exercise 1.4.4. Show that the function f(n) = nth digit of π is recursive.

Hint: Use an infinite series such as

\frac{π}{4} = 1 − \frac{1}{3} + \frac{1}{5} − \frac{1}{7} + \frac{1}{9} − ⋯

plus the fact that π is irrational.

Solution. This follows from Exercise 1.1.12. A solution not using Mahler’s result is as follows.

Let S_{k} be the kth partial sum of the alternating series

π = 4 − \frac{4}{3} + \frac{4}{5} − \frac{4}{7} + \frac{4}{9} − ⋯ = ∑_{n=0}^{∞} \frac{(−1)^{n}4}{2n + 1} ,

We have S_{k} = a(k)/b(k) where a(k) and b(k) are primitive recursive. Since π is irrational, it follows that for each n there exists k such that S_{k} and S_{k+1} have the same first n digits. Since π lies between S_{k} and S_{k+1}, it follows that S_{k} and π have the same first n digits, so in particular f(n) = the nth digit of S_{k}. Note also that the function

h(n, a, b) = nth digit of a/b

is primitive recursive. Using the least number operator, we have f(n) = h(n, a(k(n)), b(k(n))) where k(n) = the least k such that ⋀_{m=0}^{n} h(m, a(k), b(k)) = h(m, a(k +1), b(k + 1)). Clearly this is recursive.

Exercise 1.4.5. Show that there exists a computable function which is not primitive recursive. (By 1.2.2 it suffices to show that the Ackermann function λnx [ A_{n}(x) ] is computable.)

Exercise 1.4.6. Let f : ℕ ⟶^{1−1 onto} ℕ be a permutation of ℕ, the set of natural numbers. Show that if f is recursive, then the inverse permutation f^{−1} is also recursive.

Solution. Using the least number operator, we have f^{−1}(y) = the least x such that f(x) = y.

Exercise 1.4.7. Give an example of a primitive recursive permutation of ℕ whose inverse is not primitive recursive.

Solution. From our study of the Ackermann function in Section 1.2, we know that the predicate {⟨x, y⟩ | A_{x}(x) = y} is primitive recursive, although the oneto-one increasing function x ↦ A_{x}(x) is not. Let B be the range of x ↦ A_{x}(x), i.e., B = {y | ∃x (A_{x}(x) = y)}. Then B is primitive recursive, because y ∈ B ⇔ ⋁_{x=0}^{y−1} A_{x}(x) = y. Note also that B is infinite and coinfinite.

For any infinite set S ⊆ ℕ, let π_{S} : ℕ → ℕ be the principal function of S, i.e.,

S = {π_{S}(0) < π_{S}(1) < ⋯ < π_{S}(n) < π_{S}(n + 1) < ⋯}

where π_{S}(n) = the nth element of S. Let f be the permutation of ℕ defined by

f(y) = \{ \begin{matrix}2π_{B}^{−1}(y) & if y ∈ B, \\ 2π_{ℕ\B}^{−1}(y) + 1 & if y ∈ ℕ \ B. \end{matrix}

By course-of-values recursion, f is primitive recursive. However, f^{−1} is not primitive recursive, because f^{−1}(2x) = π_{B}(x) = A_{x}(x).

1.5 The Enumeration Theorem

To each register machine program E we shall assign a unique number e = #(E). This number will be called the Gödel number of E and will also be called an index of the k-place partial recursive function which is computed by E

Recall that our register machine is equipped with infinitely many registers R_{i}, i ≥ 1. Initially all of the registers are empty except for R_{1}, …, R_{k} which contain the arguments x_{1}, …, x_{k}. We assume that our program E is given as a numbered sequence of instructions I_{1}, …, I_{l}. By convention our machine starts by executing I_{1} and stops when it attempts to execute the nonexistent instruction I_{0}. Each instruction I_{m}, 1 ≤ m ≤ l, is of the form

increment R_{i} then go to instruction I_{n_{0}},  (1.0)

or

if R_{i} is empty go to I_{n_{0}}, otherwise decrement R_{i} then go to instruction I_{n_{1}}.

(1.1)

Here n_{0} and n_{1} are in the range 0 ≤ n ≤ l. To each instruction I_{m} we assign a Gödel number #(I_{m}), where

#(I_{m}) = \{ \begin{matrix}3^{i} · 5^{n_{0}} & for I_{m} as in (1.0) , \\ 2 · 3^{i} · 5^{n_{0}} · 7^{n_{1}} & for I_{m} as in (1.1) . \end{matrix}

The Gödel number of the entire program E is then defined as

#(E) = ∏_{m=1}^{l} p_{m}^{#(I_{m})} ,

where p_{0}, p_{1}, p_{2}, … are the prime numbers 2, 3, 5, … in increasing order.

Example 1.5.1. Let E be the program in Figure 1.8, which computes λx [ x+1 ]. Listing the instructions I_{1}, I_{2}, I_{3} as shown in the figure, we have

\begin{aligned}#(I_{1}) & = & 2 · 3^{1} · 5^{3} · 7^{2} = 2 · 3 · 125 · 49 = 36750 , \\ #(I_{2}) & = & 3^{2} · 5^{1} = 45 , \\ #(I_{3}) & = & 3^{2} · 5^{0} = 9 , \end{aligned}

so that

#(E) = 3^{#(I_{1})} · 5^{#(I_{2})} · 7^{#(I_{3})} = 3^{36750} · 5^{45} · 7^{9} .

Lemma 1.5.2. The 1-place predicate

Program (e) ≡ (e is the Gödel number of some register machine program)

is primitive recursive.

Proof. We have

Program (e) ≡ ⋁_{l=0}^{e} Program (e, l)

[figure: I_{1}; I_{3}; start; R_{1}^{−}; e; R_{2}^{+}; stop; R_{2}^{+}; I_{2}]

Figure 1.8: A Program with Labeled Instructions

where Program (e, l) says that e is the Gödel number of a register machine program consisting of l instructions I_{1}, …, I_{l}. We then have

Program (e, l) ≡ e = ∏_{m=1}^{l} p_{m}^{(e)_{m}} ∧

⋀_{m=1}^{l} ⋁_{i=1}^{e} ⋁_{n_{0}=0}^{l} ⋁_{n_{1}=0}^{l} [ (e)_{m} = 3^{i} · 5^{n_{0}} ∨ (e)_{m} = 2 · 3^{i} · 5^{n_{0}} · 7^{n_{1}} ] ,

the idea being that (e)_{m} = #(I_{m}). This proves the lemma.

Definition 1.5.3. We denote by φ_{e}^{(k)} the k-place partial computable function which is computed by the register machine program E whose Gödel number is e. In more detail, we define

φ_{e}^{(k)}(x_{1}, ⋯, x_{k}) ≃ the number in R_{k+1} if and when E(x_{1}, ⋯, x_{k})

stops, where e = #(E), and undefined otherwise.

Note that if e is not the Gödel number of a register machine program, then φ_{e}^{(k)}(x_{1}, ⋯, x_{k}) is undefined for all x_{1}, …, x_{k}, so in this case φ_{e}^{(k)} is the empty function.

If ψ is a k-place partial recursive function, an index of ψ is any number e such that ψ = φ_{e}^{(k)}, i.e., e is the Gödel number of a program which computes ψ. Clearly ψ has many different indices, since there are many different programs which compute ψ.

Exercise 1.5.4. Find an index of the function

α(x) = \{ \begin{matrix}1 & if x = 0, \\ 0 & if x > 0. \end{matrix}

Solution. Clearly the labeled program

[figure: I_{1}; I_{2}; start; R_{1}^{−}; e; R_{2}^{+}; stop]

computes α. We have #(I_{1}) = 2 · 3^{1} · 5^{2} · 7^{0} = 150 and #(I_{2}) = 3^{2} · 5^{0} = 9, so an index of α is e = 3^{#(I_{1})} · 5^{#(I_{2})} = 3^{150} · 5^{9}. In other words, φ_{e}^{(1)} = α.

The main theorem on indices reads as follows.

Theorem 1.5.5 (The Enumeration Theorem). For each k ≥ 1, the (k+1)-place partial function

λex_{1} … x_{k} [ φ_{e}^{(k)}(x_{1}, …, x_{k}) ]

is partial recursive.

Remark 1.5.6. The Enumeration Theorem entails the existence of a “universal” program, i.e., a register machine program which can emulate the action of any other register machine program. This concept underlies the stored program digital computer.

In the proof of the Enumeration Theorem, the following easy lemma will be useful.

Lemma 1.5.7 (Definition by Cases). Let P_{1} and P_{2} be k-place primitive recursive predicates and let f_{1} and f_{2} be k-place primitive recursive functions. Assume that P_{1} and P_{2} are mutually exclusive and exhaustive, i.e., for each k-tuple ⟨x_{1}, …, x_{k}⟩ ∈ ℕ^{k}, either P_{1}(x_{1}, …, x_{k}) or P_{2}(x_{1}, …, x_{k}) holds but not both. Then the k-place function f defined by

f(x_{1}, …, x_{k}) = \{ \begin{matrix}f_{1}(x_{1}, …, x_{k}) & if P_{1}(x_{1}, …, x_{k}) holds \\ f_{2}(x_{2}, …, x_{k}) & if P_{2}(x_{1}, …, x_{k}) holds \end{matrix}

is primitive recursive.

Proof. This is clear since f = f_{1} · χ_{P_{1}} + f_{2} · χ_{P_{2}}. The extension to more than two cases is also easy.

Proof of the Enumeration Theorem.

The idea of the proof is to represent the state of E(x_{1}, …, x_{k}) after executing n instructions by a single number

\begin{aligned}z & = & State (e, x_{1}, …, x_{k}, n) \\ & = & p_{0}^{m} · ∏_{i=1}^{∞} p_{i}^{z_{i}} , \end{aligned}

where z_{i} is the number in register R_{i}, and I_{m} is the next instruction to be executed. Note that (z)_{0} = m and, for all i ≥ 1, (z)_{i} = z_{i}.

We first show that the State function is primitive recursive. We have

State (e, x_{1}, …, x_{k}, 0) = p_{0}^{1} · p_{1}^{x_{1}} · . . . · p_{k}^{x_{k}}

(begin by executing I_{1}) ,

State (e, x_{1}, …, x_{k}, n + 1) = NextState (e, State (e, x_{1}, …, x_{k}, n)) ,

NextState (e, z) = \{ \begin{matrix}z · p_{i} · p_{0}^{−m+n_{0}} & if ((e)_{m})_{0} = 0 , \\ z · p_{0}^{−m+n_{0}} & if ((e)_{m})_{0} = 1 and (z)_{i} = 0 , \\ z · p_{i}^{−1} · p_{0}^{−m+n_{1}} & if ((e)_{m})_{0} = 1 and (z)_{i} > 0 , \\ z & otherwise , \end{matrix}

where

m = (z)_{0} , i = ((e)_{m})_{1} , n_{0} = ((e)_{m})_{2} , n_{1} = ((e)_{m})_{3} .

We are now ready to prove the theorem. We use the least number operator to obtain

Stop (e, x_{1}, …, x_{k}) ≃ least n such that (State (e, x_{1}, …, x_{k}, n))_{0} = 0
∧ Program (e) .

(The idea is that our machine stops if and when it is about to execute I_{0}. Note that Stop (e, x_{1}, …, x_{k}) is undefined if e is not the Gödel number of a register machine program.) We then use composition to get

FinalState (e, x_{1}, …, x_{k}) ≃ State (e, x_{1}, …, x_{k}, Stop (e, x_{1}, …, x_{k}))

(the state of our machine if and when it stops)

and

Output (e, x_{1}, …, x_{k}) ≃ (FinalState (e, x_{1}, …, x_{k}))_{k+1}

(the number that is finally in register R_{k+1}) .

Since the Output function was obtained by composition, primitive recursion and the least number operator, it is partial recursive. Moreover, for all e and x_{1}, …, x_{k}, we clearly have

φ_{e}^{(k)}(x_{1}, …, x_{k}) ≃ Output (e, x_{1}, …, x_{k}) .

This completes the proof of the Enumeration Theorem.

Exercise 1.5.8. Let f : ℕ^{k} → ℕ be a k-place total recursive function. Show that f is primitive recursive if and only if there exists an index e of f such that

λx_{1} … x_{k} [ Stop (e, x_{1}, …, x_{k}) ]

is majorized by some primitive recursive function. (See also Exercise 1.2.2.)

Exercise 1.5.9. Fix k ≥ 1. Construct a k+1-place total recursive function Φ_{k} : ℕ^{k+1} → ℕ with the following properties:

1. for each e ∈ ℕ, the k-place function λx_{1} … x_{k} [ Φ_{k}(e, x_{1}, …, x_{k}) ] is primitive recursive;

2. for each k-place primitive recursive function f : ℕ^{k} → ℕ, there exists an e such that f = λx_{1} … x_{k} [ Φ_{k}(e, x_{1}, …, x_{k}) ].

Exercise 1.5.10. Given a k-place partial recursive function ψ(x_{1}, …, x_{k}), show that there is a 1-place partial recursive function ψ^{∗}(x) such that

ψ^{∗}(p_{1}^{x_{1}} ⋯ p_{k}^{x_{k}}) ≃ p_{k+1}^{ψ(x_{1},...,x_{k})}

for all x_{1}, …, x_{k}, and ψ^{∗} is computable by a register machine program which uses only two registers, R_{1} and R_{2}.

Solution. We begin with a register machine program P which computes ψ(x_{1}, …, x_{k}). Let P_{1}, …, P_{k}, P_{k+1}, …, P_{s} be the registers used in P. We may safely assume that, whenever P(x_{1}, …, x_{k}) halts, it leaves all registers except P_{k+1} empty.

We transform P into a program R which uses only two registers, R_{1} and R_{2}. The idea is that, if P_{1}, …, P_{s} contain z_{1}, …, z_{s} respectively, then R_{1} contains z = p_{1}^{z_{1}} ⋯ p_{s}^{z_{s}}, while R_{2} contains 0. Incrementing (decrementing) P_{i} corresponds to multiplication (division) by p_{i}. Each instruction in P is replaced by a corresponding set of instructions in R.

We replace [figure: P_{i}^{+}] in P by Figure 1.9 in R.

We replace [figure: P_{i}^{−}; e; A; B] in P by Figure 1.10 in R.

We replace [figure: stop] in P by Figure 1.11 in R.

1.6 Consequences of the Enumeration Theorem

In this section we present some important consequences of the Enumeration Theorem.

[figure: R_{1}^{−}; e; R_{2}^{−}; e; R_{2}^{+}; R_{1}^{+}; ⋮; R_{2}^{+}]

The number of R_{2}^{+} instructions is p_{i}. Figure 1.9: Incrementing P_{i}

[figure: R_{1}^{+}; R_{1}^{−}; e; R_{2}^{−}; e; A; R_{1}^{+}; R_{2}^{+}; R_{1}^{−}; e; R_{1}^{+}; R_{2}^{−}; e; R_{1}^{+}; ⋮; ⋮; B; ⋮; R_{1}^{−}; e; R_{1}^{+}; R_{1}^{+}]

The number of R_{1}^{−} instructions is p_{i}. Figure 1.10: Decrementing P_{i}

[figure: R_{1}^{−}; e; stop; R_{2}^{+}]

Figure 1.11: Stopping

Theorem 1.6.1. All partial recursive functions can be obtained from primitive recursive functions by composition and minimization.

Proof. This is immediate from the proof of the Enumeration Theorem. The State function is primitive recursive, the Stop function is obtained from the State function by minimization, and the FinalState and Output functions are obtained by composing the Stop and State functions with the primitive recursive function λz [ (z)_{k+1} ].

The following characterizations of the class of partial recursive functions do not involve register machines and are similar to our definition of the class of primitive recursive functions.

Corollary 1.6.2. The class of partial recursive functions is the smallest class of functions containing the primitive recursive functions and closed under composition and minimization.

Corollary 1.6.3. The class of partial recursive functions is the smallest class of functions containing the initial functions and closed under composition, primitive recursion, and minimization.

Proof. Both corollaries are immediate from the previous theorem and Lemmas 1.3.2, 1.3.3, 1.3.4, 1.4.3.

Next we present an interesting example showing that the consideration of partial functions is in some sense unavoidable or inherent in recursive function theory.

Example 1.6.4. We present an example of a partial recursive function ψ : ℕ ⟶^{P} ℕ which cannot be extended to a total recursive function f : ℕ → ℕ. Namely, we define

ψ(x) ≃ φ_{x}^{(1)}(x) + 1 .

By the Enumeration Theorem, ψ is a partial recursive function. Suppose ψ were extendible to a total recursive function f. Let e be an index of f. Then ψ(e) ≃ φ_{e}^{(1)}(e) + 1 ≃ f(e) + 1 is defined, hence f(e) ≃ ψ(e) ≃ f(e) + 1, a contradiction.

Definition 1.6.5. A set A ⊆ ℕ is said to be recursive if its characteristic function χ_{A} : ℕ → ℕ is recursive. More generally, a k-place predicate R ⊆ ℕ^{k} is said to be recursive if its characteristic function χ_{R} : ℕ^{k} → ℕ is recursive.

Example 1.6.6. We present an example of a nonrecursive set. Let K be the subset of ℕ consisting of all x ∈ ℕ such that φ_{x}^{(1)}(x) is defined. Thus K = dom(ψ) where ψ is as in the previous example. We claim that K is not recursive. If K were recursive, then the total function f : ℕ → ℕ defined by

f(x) = \{ \begin{matrix}ψ(x) & if x ∈ K, \\ 0 & if x ∉ K \end{matrix}

would be recursive, contradicting the fact that ψ is not extendible to a total recursive function.

Definition 1.6.7. A pair of sets A, B ⊆ ℕ is said to be recursively inseparable if there is no recursive set X such that A ⊆ X and X ∩ B = ∅.

Exercise 1.6.8. Letting K_{n} = {x ∈ ℕ | φ_{x}^{(1)}(x) ≃ n}, show that K_{0} and K_{1} are recursively inseparable.

Exercise 1.6.9. Show that there exists a set A ⊆ ℕ which is recursive but not primitive recursive.

(Caution: It can be shown that the 3-place predicate z = A_{x}(y) is primitive recursive, even though the 2-place function λxy [ A_{x}(y) ] is not primitive recursive. See Exercises 1.2.2, 1.4.5, 1.5.8, 1.5.9.)

Remark 1.6.10 (Church’s Thesis). Perhaps the most important consequence of the proof of the Enumeration Theorem is that it provides strong evidence for Church’s Thesis. We shall first explain what Church’s Thesis says, and then we shall present the evidence for it.

The context of Church’s Thesis is that, as mathematicians, we have an intuitive notion of what it means for a function f : ℕ^{k} → ℕ to be algorithmically computable. Since recursive functions are register machine computable, they are obviously algorithmically computable in the intuitive sense. Church’s Thesis states the converse: All functions f : ℕ^{k} → ℕ which are algoritmically computable in the intuitive sense are in fact recursive.

To present our evidence for Church’s thesis, assume that we are given a function f : ℕ^{k} → ℕ which is algorithmically computable in the intuitive sense. We want to show that f is recursive. Since the given algorithm for f is presumably deterministic, the execution of the algorithm should be describable as a sequence of states with deterministic transition from one state to the next. The precise nature of the states depends on the nature of the algorithm, but no matter what the states actually consist of, it should be possible to view them as finite strings of symbols and to assign Gödel numbers to them. Once this has been done, the transition from the Gödel number of one state to the Gödel number of the next state should be very simple, in particular primitive recursive. Thus we should be able to carry out an analysis similar to what is in the proof of Theorem 1.5.5 (State, NextState, Stop, etc.). Such an analysis will show that f is obtained from primitive recursive functions by means of composition and minimization. It will then follow by Corollary 1.6.2 that f is recursive.

The argument in the previous paragraph is of necessity nonrigorous. However, it can be specialized to provide rigorous proofs that various models of computation (similar to but differing in details from register machine computability) give rise to exactly the same class of functions, the recursive functions. Some of the models of computation that have been analyzed in this way are: Turing machines, Markov algorithms, Kleene’s equation calculus. There is no reason to think that the same analysis could not be carried out for any similar model. This constitutes very strong evidence for Church’s thesis.

Note that the same arguments and evidence apply more generally in case f is a partial rather than a total function. From now on, we shall take Church’s Thesis for granted and identify the class of partial recursive functions with the class of partial functions from ℕ^{k} into ℕ that are algorithmically computable in the intuitive sense.

The fact that the intuitive notion of algorithmic computability is captured by a rigorous mathematical notion of recursiveness is one of the successes of modern mathematical logic.

1.7 Unsolvable Problems

The purpose of this section is twofold: (1) to discuss and make precise the concept of an unsolvable mathematical problem, and (2) to present some important examples of such problems.

We begin with a preliminary clarification. In certain contexts, the word problem refers to a mathematical statement which has a definite truth value, True or False, but whose truth value is unknown at the present time. (An example of a problem in this sense is the Riemann Hypothesis.) However, we shall not deal with this type of problem now. Instead, we consider a somewhat different concept. For us in this section, a problem is any mathematical statement that involves a parameter. A solution of such a problem would be an algorithm which would enable us to compute the truth value of the problem statement for any given value of the parameter. The problem is said to be solvable if there exists such an algorithm, otherwise unsolvable. An instance of a problem is the specialization of the problem statement to a particular parameter value.

As an example of a solvable problem, we mention:

Example 1.7.1. The statement “n is prime” represents the problem of deciding whether an arbitrary number n ∈ ℕ is prime or composite. Here the parameter is the variable n. For any particular n (e.g. n = 123456789), the question of whether this particular n is prime or composite is an instance (i.e., special case) of the general “primality problem”. Since the set of prime numbers

{n ∈ ℕ | n is prime}

is primitive recursive, the general primality problem is solvable.

On the other hand, we have the following example of an unsolvable problem.

Example 1.7.2. The set K defined in Example 1.6.6 is nonrecursive. Hence by Church’s Thesis there is no algorithm to decide whether or not a given number n belongs to K. It is therefore appropriate to describe the membership problem for K (i.e., the problem of computing the truth value of n ∈ K for any given n) as an unsolvable problem.

The ability to distinguish solvable problems from unsolvable ones is of basic importance for the mathematical enterprise. Among the most famous unsolvable mathematical problems are:

Example 1.7.3 (Hilbert’s Tenth Problem). Hilbert’s Tenth Problem is to determine, for a given polynomial p in several variables with integral coeffients, p ∈ ℤ[X_{1}, …, X_{n}], whether or not the equation p(X_{1}, …, X_{n}) = 0 has a solution in integers X_{1}, …, X_{n} ∈ ℕ. This problem encompasses the entire theory of Diophantine equations. A theorem of Matijasevič shows that Hilbert’s Tenth Problem is unsolvable. Actually Matijasevič produced a particular polynomial

p(X_{0}, X_{1}, …, X_{9})

with 10 indeterminates, such that

{n ∈ ℕ | p(n, a_{1}, …, a_{9}) = 0 for some a_{1}, …, a_{9} ∈ ℤ}

is nonrecursive. Once again, our notion of unsolvable problem is related to the existence of a nonrecursive set, namely the set of parameter values n for which the problem statement holds.

Example 1.7.4 (Word Problems). Let G be a group presented by finitely many generators and relations. The word problem for G is the problem of determining, for a given word w in the generators of G and their inverses, whether or not w = 1 in G. In this case the parameter is w, and the word problem for G is solvable if and only if there exists an algorithm for determining whether or not a given word w is equal to 1 in G. It is known that the word problem is solvable for some groups G and not solvable for others. For example, the word problem for free groups or groups with one relation is solvable, but Boone and Novikov have exhibited groups G with finitely many relations such that the word problem for G is unsolvable.

Example 1.7.5 (The Halting Problem). Some famous unsolvable problems arise from computability theory itself. One of these is the Halting Problem: To determine whether or not a given register machine program P will eventually stop, if started with all registers empty. By Gödel numbering, we can identify the Halting Problem with the problem of deciding whether a given natural number e belongs to the set

H = {e ∈ ℕ | φ_{e}^{(1)}(0) is defined} .

We shall prove below that H is nonrecursive, i.e., the Halting Problem is unsolvable.

In all of the above examples, the issue of solvability or unsolvability of a particular problem was rephrased as an issue of whether or not a particular subset of ℕ is recursive. Such considerations based on Church’s Thesis motivate the following definition:

Definition 1.7.6 (Unsolvability). Recall that a set A ⊆ ℕ is said to be recursive if and only if its characteristic function χ_{A} : ℕ → {0, 1} is recursive. A problem is defined to be a subset of ℕ. If A ⊆ ℕ is a problem in this sense, the problem A is said to be solvable if A is recursive, and unsolvable if A is nonrecursive.

We shall prove the unsolvability of the Halting Problem, i.e., the nonrecursiveness of the set H in Example 1.7.5 above. The proof will be accomplished by showing that the problem of membership in K is “reducible” to the problem of membership in H. In this context, reducibility of one problem to another means that each instance of the former problem can be effectively converted to an equivalent instance of the latter problem. Our precise notion of reducibility is given by:

Definition 1.7.7 (Reducibility). Let A and B be subsets of ℕ (i.e., problems, cf. Definition 1.7.6). We say that A is reducible to B if there exists a recursive function f : ℕ → ℕ such that, for all n ∈ ℕ, n ∈ A implies f(n) ∈ B, and n ∉ A implies f(n) ∉ B.

Lemma 1.7.8. Suppose that A is reducible to B. If B is recursive, then A is recursive. If A is nonrecursive, then B is nonrecursive.

Proof. The first statement follows easily from the fact that χ_{A}(x) = χ_{B}(f(x)). The second statement follows since it is the contrapositive of the first.

Exercise 1.7.9. Write A ≤_{m} B to mean that A is reducible to B. Show that

1. A ≤_{m} A for all A ⊆ ℕ.

2. A ≤_{m} B and B ≤_{m} C imply A ≤_{m} C.

3. If ∅ ≠B≠ ℕ, then for every recursive set A we have A ≤_{m} B.

In order to prove that the set H is nonrecursive, we shall need the following important technical result:

Theorem 1.7.10 (The Parametrization Theorem). Let θ(x_{0}, x_{1}, …, x_{k}) be a (k+1)-ary partial recursive function. Then we can find a unary primitive recursive function f(x_{0}) such that, for all x_{0}, x_{1}, …, x_{k} ∈ ℕ,

φ_{f(x_{0})}^{(k)}(x_{1}, …, x_{k}) ≃ θ(x_{0}, x_{1}, …, x_{k}) .

Proof. Let T be a register machine program which computes the k+1-ary partial recursive function θ. The idea of the proof is to let f(x_{0}) be the Gödel number of a program which is similar to T but has x_{0} hard-coded as the first argument of θ.

Formally, let T′ be a register machine program which computes the k+1-ary partial recursive function

θ′(x_{1}, …, x_{k}, x_{0}) ≃ θ(x_{0}, x_{1}, …, x_{k}) .

Let I_{1}, …, I_{l} be the instructions of T′, and let T′′ be the same as T′ but modified so that the instructions are numbered I_{5}, …, I_{l+4} instead of I_{1}, …, I_{l}. Then for any given x_{0} ∈ ℕ, the program T′′′_{x_{0}} depicted in Figure 1.12 computes the k-ary partial recursive function λx_{1} … x_{k} [ θ′(x_{1}, …, x_{k}, x_{0}) ], i.e. λx_{1} … x_{k} [ θ(x_{0}, x_{1}, …, x_{k}) ]. The instructions of T′′′_{x_{0}} are numbered as I_{1}, …, I_{l+x_{0}+5}. Let f(x_{0}) be the Gödel number of T′′′_{x_{0}}. Note that

\begin{aligned}f(x_{0}) & = & ∏_{m=1}^{l+x_{0}+5} p_{m}^{#(I_{m})} \\ & = & ∏_{m=1}^{l+4} p_{m}^{#(I_{m})} · ∏_{m=l+5}^{l+x_{0}+4} p_{m}^{3^{k+1}·5^{m+1}} · p_{l+x_{0}+5}^{2·3^{k+1}·5^{5}·7^{5}} \end{aligned}

where the first factor ∏_{m=1}^{l+4} p_{m}^{#(I_{m})} does not depend on x_{0}. Thus f(x_{0}) is a primitive recursive function of x_{0}. This completes the proof.

[figure: I_{1}; I_{l+5}; …; I_{l+x_{0}+4}; I_{l+x_{0}+5}; I_{5} ⋯ I_{l+4}; I_{2}; I_{3}; start; R_{k+1}^{+}; R_{k+1}^{+}; …; R_{k+1}^{+}; R_{k+1}^{−}; e; _{T _{′′}}; R_{k+1}^{−}; e; R_{k+2}^{−}; e; stop; x_{0}; R_{k+1}^{+}; I_{4}]

Figure 1.12: Parametrization

We can now prove that the Halting Problem is unsolvable.

Theorem 1.7.11 (Unsolvability of the Halting Problem). The Halting Problem is unsolvable. In other words, the set

H = {x ∈ ℕ | φ_{x}^{(1)}(0) is defined}

of Example 1.7.5 is nonrecursive.

Proof. Let H be as in Example 1.7.5 and let K be as in Example 1.6.6, i.e.,

K = {x ∈ ℕ | φ_{x}^{(1)}(x) is defined} .

We shall prove that K is reducible to H. Since K is known to be nonrecursive (Example 1.6.6), it will follow by Lemma 1.7.8 that H is nonrecursive.

Consider the partial recursive function θ(x, y) ≃ φ_{x}^{(1)}(x). Note that θ is a 2-place function. By the Enumeration Theorem, θ is partial recursive. By the Parametrization Theorem applied with k = 1, we can find a primitive recursive function f : ℕ → ℕ such that

φ_{f(x)}^{(1)}(y) ≃ θ(x, y) ,

i.e.,

φ_{f(x)}^{(1)}(y) ≃ φ_{x}^{(1)}(x)

for all x and y. In particular, if x ∈ K then φ_{x}^{(1)}(x) is defined, hence φ_{f(x)}^{(1)}(0) is

defined, i.e., f(x) ∈ H. On the other hand, if x ∉ K then φ_{x}^{(1)}(x) is undefined, hence φ_{f(x)}^{(1)}(0) is undefined, i.e., f(x) ∉ H. Thus K is reducible to H via f. This completes the proof.

Exercise 1.7.12. Show that the following sets and predicates are nonrecursive:

1. {x ∈ ℕ | φ_{x}^{(1)} : ℕ ⟶^{P} ℕ is total}.

2. {x ∈ ℕ | φ_{x}^{(1)} is the empty function}.

3. {⟨x, y⟩ ∈ ℕ × ℕ | φ_{x}^{(1)} = φ_{y}^{(1)}}.

4. {⟨x, y⟩ ∈ ℕ × ℕ | y ∈ rng(φ_{x}^{(1)})}.

5. {x ∈ ℕ | 0 ∈ rng(φ_{x}^{(1)})}.

6. {x ∈ ℕ | rng(φ_{x}^{(1)}) is infinite}.

Exercise 1.7.13 (Rice’s Theorem). Let P be the class of 1-place partial recursive functions. For C ⊆ P, define I_{C} to be the set of indices of functions in C, i.e.,

I_{C} = {x ∈ ℕ | φ_{x}^{(1)} ∈ C} .

Show that if ∅ ≠ C ≠ P then I_{C} is nonrecursive.

Solution. Let e_{0} be an index of the empty function. Let e_{1} be an index such that φ_{e_{1}}^{(1)} ∈ C if and only if φ_{e_{0}}^{(1)} ∉ C. By the Enumeration and Parametrization theorems, we can find a primitive recursive function f such that

φ_{f(x)}^{(1)}(y) ≃ \{ \begin{matrix}φ_{e_{1}}^{(1)}(y) & if φ_{x}^{(1)}(x) ↓, \\ ↑ & otherwise, \end{matrix}

for all x and y. Thus x ∈ K implies φ_{f(x)}^{(1)} = φ_{e_{1}}^{(1)}, while x ∉ K implies

φ_{f(x)}^{(1)} = φ_{e_{0}}^{(1)}. Thus f reduces K either to I_{C} (if φ_{e_{1}}^{(1)} ∈ C) or to the complement

of I_{C} (if φ_{e_{1}}^{(1)} ∉ C). In either case it follows that I_{C} is not recursive.

1.8 The Recursion Theorem

In this section we present an interesting and mysterious theorem known as the Recursion Theorem.

Theorem 1.8.1 (The Recursion Theorem). Let θ(w, x_{1}, …, x_{k}) be a partial recursive function. Then we can find an index e such that, for all x_{1}, …, x_{k},

φ_{e}^{(k)}(x_{1}, …, x_{k}) ≃ θ(e, x_{1}, …, x_{k}) .

Proof. Applying the Parametrization Theorem and the Enumeration Theorem, we can find primitive recursive functions f and d such that, for all w, u, x_{1}, …, x_{k},

φ_{f(w)}^{(k)}(x_{1}, …, x_{k}) ≃ θ(w, x_{1}, …, x_{k}) .

and

φ_{d(u)}^{(k)}(x_{1}, …, x_{k}) ≃ φ_{φ_{u}^{(1)}(u)}^{(k)}(x_{1}, …, x_{k}) .

Let v be an index of f ∘ d, i.e., φ_{v}^{(1)}(u) = f(d(u)) for all u. Then

φ_{d(v)}^{(k)}(x_{1}, …, x_{k}) ≃ φ_{φ_{v}^{(1)}(v)}^{(k)}(x_{1}, …, x_{k})
≃ φ_{f(d(v))}^{(k)}(x_{1}, …, x_{k})
≃ θ(d(v), x_{1}, …, x_{k})

so we may take e = d(v). This completes the proof.

Example 1.8.2. As an example, if we take θ(w, x) = w + x, then we obtain an index e such that φ_{e}^{(1)}(x) = e + x for all x.

Example 1.8.3. As another illustration of the Recursion Theorem, we now use it to prove that the Ackermann function λnx [ A_{n}(x) ] (see Section 1.2) is computable. The recursion equations defining the Ackermann function can be written as

\begin{aligned}A_{0}(x) & = & 2x \\ A_{n+1}(0) & = & 1 \\ A_{n+1}(x + 1) & = & A_{n}(A_{n+1}(x)) . \end{aligned}

Writing A(x, y) = A_{x}(y), this becomes

\begin{aligned}A(0, y) & = & 2y \\ A(x + 1, 0) & = & 1 \\ A(x + 1, y + 1) & = & A(x, A(x + 1, y)) \end{aligned}

or in other words

A(x, y) = \{ \begin{matrix}2y & if x = 0 , \\ 1 & if x > 0 and y = 0 , \\ A(x · − 1, A(x, y · − 1)) & if x > 0 and y > 0 . \end{matrix}

By the Enumeration Theorem together with the Recursion Theorem, we can find an index e such that

φ_{e}^{(2)}(x, y) ≃ \{ \begin{matrix}2y & if x = 0 , \\ 1 & if x > 0 and y = 0 , \\ φ_{e}^{(2)}(x · − 1, φ_{e}^{(2)}(x, y · − 1)) & if x > 0 and y > 0 . \end{matrix}

It is then straightforward to prove by induction on x that, for all y, φ_{e}^{(2)}(x, y) ≃ A(x, y). This completes the proof.

Exercise 1.8.4.

1. Find a primitive recursive function f(x, y) such that, for all x and y,

φ_{f(x,y)}^{(1)} = φ_{x}^{(1)} ∘ φ_{y}^{(1)} .

2. Find a primitive recursive function g(x, y) such that, for all x and y,

dom(φ_{g(x,y)}^{(1)}) = dom(φ_{x}^{(1)}) ∩ dom(φ_{y}^{(1)}) .

3. Find a primitive recursive function h(x, y) such that, for all x and y,

dom(φ_{h(x,y)}^{(1)}) = dom(φ_{x}^{(1)}) ∪ dom(φ_{y}^{(1)}) .

Solution.

1. By the Enumeration Theorem and the Parametrization Theorem, find a primitive recursive function f̂(w) such that

φ_{f̂(w)}^{(1)}(z) ≃ φ_{(w)_{1}}^{(1)}(φ_{(w)_{2}}^{(1)}(z))

for all w, z. Then f(x, y) = f̂(3^{x}5^{y}) has the desired property.

2. By the Enumeration Theorem and the Parametrization Theorem, find a primitive recursive function ĝ(w) such that

φ_{ĝ(w)}^{(1)}(z) ≃ φ_{(w)_{1}}^{(1)}(z) + φ_{(w)_{2}}^{(1)}(z)

for all w, z. Then g(x, y) = ĝ(3^{x}5^{y}) has the desired property.

3. By the Parametrization Theorem, find a primitive recursive function ĥ(w) such that

φ_{ĥ(w)}^{(1)}(z) ≃ least n such that (State((w)_{1}, z, n))_{0} · (State((w)_{2}, z, n))_{0} = 0

for all w, z. Then h(x, y) = ĥ(3^{x}5^{y}) has the desired property.

Exercise 1.8.5.

1. Find a primitive recursive function f(x) such that for all x, if φ_{x}^{(1)} is a permutation of ℕ, then φ_{f(x)}^{(1)} is the inverse permutation.

2. What happens if φ_{x}^{(1)} is assumed only to be partial and one-to-one, and not necessarily a permutation?

Solution. Consider the partial recursive function θ(x, y) ≃ least w such that (State(x, (w)_{1}, (w)_{2}))_{0} = 0 and (State(x, (w)_{1}, (w)_{2}))_{2} = y. By construction, if φ_{x}^{(1)}(z) ≃ y then (θ(x, y))_{1} ≃ z. Therefore, by the Parametrization Theorem, let f(x) be a primitive recursive function such that φ_{f(x)}^{(1)}(y) ≃ (θ(x, y))_{1}. This

works even if φ_{x}^{(1)} is only assumed to be partial and one-to-one.

Exercise 1.8.6. Find m and n such that m ≠ n and φ_{m}^{(1)}(0) = n and φ_{n}^{(1)}(0) = m.

Solution. By the Parametrization Theorem, let f be a 1-place primitive recursive function such that φ_{f(x)}^{(1)}(y) = x for all x, y. The construction of f in the proof of the Parametrization Theorem shows that f(x) > x for all x. By the Recursion Theorem, let e be such that φ_{e}^{(1)}(y) ≃ f(e) for all y. In particular we have φ_{e}^{(1)}(0) ≃ f(e), φ_{f(e)}^{(1)}(0) = e, and f(e) > e. So take m = e and n = f(e).

1.9 The Arithmetical Hierarchy

In this section we study some important classes of number-theoretic predicates: Σ_{1}^{0}, Π_{1}^{0}, Σ_{2}^{0}, Π_{2}^{0}, …. These classes collectively are known as the arithmetical hierarchy.

Definition 1.9.1 (The Arithmetical Hierarchy). We define Σ_{0}^{0} and Π_{0}^{0} to be the class of primitive recursive predicates. For n ≥ 1, we define Σ_{n}^{0} to be the class of k-place predicates P ⊆ ℕ^{k} (for any k ≥ 1) such that P can be written in the form

P (x_{1}, …, x_{k}) ≡ ∃y R(x_{1}, …, x_{k}, y)

where R is a k+1-place predicate belonging to the class Π_{n−1}^{0}. Similarly, we define Π_{n}^{0} to be the class of predicates that can be written in the form

P (x_{1}, …, x_{k}) ≡ ∀y R(x_{1}, …, x_{k}, y)

where R belongs to the class Σ_{n−1}^{0}.

For example, a predicate P (x_{1}, …, x_{k}) belongs to the class Σ_{3}^{0} if and only if it can be written in the form

∃y_{1}∀y_{2}∃y_{3} R(x_{1}, …, x_{k}, y_{1}, y_{2}, y_{3})

where R is primitive recursive. Similarly, P belongs to the class Π_{3}^{0} if and only if it can be written in the form

∀y_{1}∃y_{2}∀y_{3} R(x_{1}, …, x_{k}, y_{1}, y_{2}, y_{3})

where R is primitive recursive. Theorem 1.9.2. We have:

1. The classes Σ_{n}^{0} and Π_{n}^{0} are included in the classes Σ_{n+1}^{0} and Π_{n+1}^{0}.

2. The classes Σ_{n}^{0} and Π_{n}^{0} are closed under conjunction and disjunction.

3. The classes Σ_{n}^{0} and Π_{n}^{0} are closed under bounded quantification.

4. For n ≥ 1, the class Σ_{n}^{0} is closed under existential quantification.

5. For n ≥ 1, the class Π_{n}^{0} is closed under universal quantification.

6. A predicate P belongs to Σ_{n}^{0} (respectively Π_{n}^{0}) if and only if ¬ P belongs

to Π_{n}^{0} (respectively Σ_{n}^{0}). Proof. Straightforward. Theorem 1.9.3. A k-place predicate P ⊆ ℕ^{k} belongs to the class Σ_{1}^{0} if and only if P = dom(ψ) for some k-place partial recursive function ψ : ℕ^{k} ⟶^{P} ℕ. Proof. If P is Σ_{1}^{0}, then we have

P (x_{1}, …, x_{k}) ≡ ∃y R(x_{1}, …, x_{k}, y)

where R is primitive recursive, hence P = dom(ψ) where

ψ(x_{1}, …, x_{k}) ≃ least y such that R(x_{1}, …, x_{k}, y) holds , and clearly ψ is partial recursive. Conversely, if P = dom(ψ), then letting e be an index of ψ, we have as in the proof of the Enumeration Theorem

P (x_{1} …, x_{k}) ≡ ∃n (State(e, x_{1}, …, x_{k}, n))_{0} = 0 ,

hence P is Σ_{1}^{0}. Corollary 1.9.4. P ⊆ ℕ^{k} is Σ_{1}^{0} if and only if

P (x_{1}, …, x_{k}) ≡ ∃y R(x_{1}, …, x_{k}, y)

where R ⊆ ℕ^{k+1} is recursive (not only primitive recursive).

Remark 1.9.5. It follows that, in the definition of Σ_{n}^{0} and Π_{n}^{0} for n ≥ 1, we may replace “primitive recursive” by “recursive”. Exercises 1.9.6. If ψ is a k-place partial function, the graph of ψ is the (k+1)- place predicate G_{ψ} = {⟨x_{1}, …, x_{k}, y⟩ | ψ(x_{1}, …, x_{k}) ≃ y}.

1. Show that ψ is partial recursive if and only if the graph of ψ is Σ_{1}^{0}.

2. Show that, for every (k+1)-place Σ_{1}^{0} predicate P (x_{1}, …, x_{k}, y) there exists a k-place partial recursive function ψ(x_{1}, …, x_{k}) which uniformizes P, i.e., G_{ψ} ⊆ P and dom(ψ) = {⟨x_{1}, …, x_{k}⟩ | ∃y P (x_{1}, …, x_{k}, y)}.

Definition 1.9.7. Let A be an infinite subset of ℕ. The principal function of A is the one-to-one function π_{A} : ℕ → ℕ that enumerates the elements of A in increasing order. Lemma 1.9.8. Let A be an infinite subset of ℕ. The set A is recursive if and only if the function π_{A} is recursive. Proof. If A is recursive then the functions ν_{A} and π_{A} defined by

ν_{A}(x) = least y such that y ≥ x and y ∈ A
π_{A}(0) = ν_{A}(0)
π_{A}(x + 1) = ν_{A}(π_{A}(x) + 1)

are obviously recursive. Conversely, if π_{A} is recursive then we have

y ∈ A if and only if ⋁_{x=0}^{y} π_{A}(x) = y .

Since the class of recursive predicates is closed under bounded quantification, it follows that A is recursive. Theorem 1.9.9. For A ⊆ ℕ, the following are pairwise equivalent:

1. A is Σ_{1}^{0};

2. A = dom(ψ) for some partial recursive function ψ : ℕ ⟶^{P} ℕ;

3. A = rng(ψ) for some partial recursive function ψ : ℕ ⟶^{P} ℕ;

4. A = ∅ or A = rng(f) for some total recursive function f : ℕ → ℕ;

5. A is finite or A = rng(f) for some one-to-one total recursive function f : ℕ → ℕ.

Proof. The equivalence of 1 and 2 is a special case of Theorem 1.9.3, and the fact that 3 implies 1 is proved similarly. It is easy to see that 5 implies 4 and 4 implies 3. To see that 1 implies 5, suppose that A ⊆ ℕ is infinite and Σ_{1}^{0}, say

x ∈ A ≡ ∃yR(x, y)

where R is primitive recursive. Put

B = {2^{x}3^{y} | R(x, y) ∧ ¬ ⋁_{z=0}^{y−1} R(x, z)} .

Then B is an infinite primitive recursive set, so by Lemma 1.9.8, π_{B} is a one-to-one recursive function. Putting f(n) = (π_{B}(n))_{0}, we see that f is a one-to-one recursive function and A = rng(f). This completes the proof.

Remark 1.9.10. A set A satisfying the conditions of Theorem 1.9.9 is sometimes called a recursively enumerable set.

Exercises 1.9.11.

1. Show that every nonempty recursively enumerable set is the range of a primitive recursive function.

2. Find an infinite primitive recursive set that is not the range of a one-to-one primitive recursive function.

Definition 1.9.12. For each n ∈ ℕ, the class Δ_{n}^{0} is defined to be the intersection of the classes Σ_{n}^{0} and Π_{n}^{0}.

Theorem 1.9.13. A k-place predicate P ⊆ ℕ^{k} belongs to the class Δ_{1}^{0} if and only if P is recursive.

Proof. If P is recursive, it follows easily by Theorem 1.9.3 that P is Δ_{1}^{0}. Conversely, if P is Δ_{1}^{0}, then we have

P (x_{1}, …, x_{k}) ≡ ∃y R_{1}(x_{1}, …, x_{k}, y) ≡ ∀y R_{2}(x_{1}, …, x_{k}, y)

where R_{1} and R_{2} are primitive recursive. Define a total recursive function f by

f(x_{1}, …, x_{k}) = least y such that R_{1}(x_{1}, …, x_{k}, y) ∨ ¬ R_{2}(x_{1}, …, x_{k}, y) .

Then we have

P (x_{1}, …, x_{k}) ≡ R_{1}(x_{1}, …, x_{k}, f(x_{1}, …, x_{k})) ,

hence P is recursive.

Exercise 1.9.14. A function f : ℕ^{k} → ℕ is said to be limit-recursive if there exists a recursive function g : ℕ^{k+1} → ℕ such that

f(x_{1}, …, x_{k}) = lim_{y} g(x_{1}, …, x_{k}, y)

for all x_{1}, …, x_{k} ∈ ℕ. Show that a predicate P is Δ_{2}^{0} if and only if its characteristic function χ_{P} is limit-recursive.

Solution. For simplicity, let x be an abbreviation for x_{1}, …, x_{k}.

First assume that χ_{P} is limit-recursive, say

χ_{P} (x) = lim_{n} f(n, x)

for all x, where f(n, x) is a recursive function. Then we have

P (x) ≡ ∃m ∀n (n ≥ m ⇒ f(n, x) = 1)

and

¬ P (x) ≡ ∃m ∀n (n ≥ m ⇒ f(n, x) = 0)

so P is Δ_{2}^{0}.

For the converse, assume that P is Δ_{2}^{0}, say

P (x) ≡ ∃y ∀z R_{1}(x, y, z)

and

¬ P (x) ≡ ∃y ∀z R_{0}(x, y, z)

where R_{1} and R_{0} are primitive recursive predicates. Using the bounded least number operator, define g(n, x) = the least y < n such that either ∀z < n R_{1}(x, y, z) or ∀z < n R_{0}(x, y, z) or both, if such a y exists, and g(n, x) = n otherwise. Thus g(n, x) is a primitive recursive function, and it is easy to see that, for all x, g(x) = lim_{n} g(n, x) exists and is equal to the least y such that ∀z R_{1}(x, y, z) or ∀z R_{0}(x, y, z). Now define h(n, x) = 1 if ∀z < n R_{1}(x, g(n, x), z), and h(n, x) = 0 otherwise. Thus h(n, x) is again a primitive recursive function, and for all x, h(x) = lim_{n} h(n, x) exists. Moreover P (x) implies h(x) = 1, and ¬ P (x) implies h(x) = 0. Thus χ_{P} is limit-recursive. This completes the proof.

Theorem 1.9.15 (Universal Σ_{n}^{0} Predicate). For each n ≥ 1 and k ≥ 1, we can find a predicate U = U_{n,k} with the following properties:

1. U is a k+1-place predicate belonging to the class Σ_{n}^{0}; and

2. for any k-place predicate P belonging to the class Σ_{n}^{0}, there exists an e ∈ ℕ

such that

P (x_{1}, …, x_{k}) ≡ U(e, x_{1}, …, x_{k})

for all x_{1}, …, x_{k}.

Proof. This is a straightforward consequence of the Enumeration Theorem. The proof is by induction on n. For n = 1 we have

U_{1,k}(e, x_{1}, …, x_{k}) ≡ φ_{e}^{(k)}(x_{1}, …, x_{k}) ↓ ≡ ∃s (State(e, x_{1}, …, x_{k}, s))_{0} = 0

in view of Theorem 1.9.3. For n > 1 we have

U_{n,k}(e, x_{1}, …, x_{k}) ≡ ∃y ¬ U_{n−1,k+1}(e, x_{1}, …, x_{k}, y) .

This completes the proof.

Lemma 1.9.16. Let A, B ⊆ ℕ and assume that A is reducible to B. Assume n ≥ 1. If B belongs to Σ_{n}^{0}, then so does A. If B belongs to Π_{n}^{0}, then so does A.

Proof. Suppose for example that B belongs to Σ_{3}^{0}. Then we have

x ∈ B if and only if ∃y_{1} ∀y_{2} ∃y_{3} R(x, y_{1}, y_{2}, y_{3})

where R ⊆ ℕ^{4} is a primitive recursive predicate. If A is reducible to B via the recursive function f, then we have

x ∈ A  if and only if  f(x) ∈ B
if and only if  ∃y_{1} ∀y_{2} ∃y_{3} R(f(x), y_{1}, y_{2}, y_{3}) .

Note that the predicate R(f(x), y_{1}, y_{2}, y_{3}) is recursive, hence Δ_{1}^{0}. It follows that the predicate ∃y_{3} R(f(x), y_{1}, y_{2}, y_{3}) is Σ_{1}^{0}. Hence A is Σ_{3}^{0}.

Definition 1.9.17. Given n ≥ 1, a set B ⊆ ℕ is said to be complete Σ_{n}^{0} if

1. B belongs to the class Σ_{n}^{0}; and

2. for any set A ⊆ ℕ belonging to the class Σ_{n}^{0}, A is reducible to B.

The notion of complete Π_{n}^{0} set is defined similarly.

Theorem 1.9.18. For each n ≥ 1 there exists a complete Σ_{n}^{0} set. For each n ≥ 1 there exists a complete Π_{n}^{0} set. For each n ≥ 1, a complete Σ_{n}^{0} set is not Π_{n}^{0}, and a complete Π_{n}^{0} set is not Σ_{n}^{0}.

Proof. By Theorem 1.9.15 let U(e, x) be a universal Σ_{n}^{0} predicate. Obviously the set {2^{e}3^{x} | U(e, x)} is Σ_{n}^{0} complete. To show that a Σ_{n}^{0} complete set can never be Π_{n}^{0}, it suffices by Lemma 1.9.16 to show that there exists a Σ_{n}^{0} set which is not Π_{n}^{0}. A simple diagonal argument shows that the Σ_{n}^{0} set {x | U(x, x)} is not Π_{n}^{0}. This completes the proof of the Σ_{n}^{0} part of the theorem. The Π_{n}^{0} part follows easily by taking complements.

Corollary 1.9.19. For all n ∈ ℕ we have

Δ_{n}^{0} ⊆ Σ_{n}^{0} ,  Δ_{n}^{0} ⊆ Π_{n}^{0} ,  Σ_{n}^{0} ∪ Π_{n}^{0} ⊆ Δ_{n+1}^{0}

and, except for n = 0, all of these inclusions are proper.

Proof. Given n ≥ 1, let A be a complete Σ_{n}^{0} set. Then the complement B = ℕ\A is complete Π_{n}^{0}. Clearly A belongs to Σ_{n}^{0} \ Δ_{n}^{0} and B belongs to Π_{n}^{0} \ Δ_{n}^{0}. Moreover it follows by Theorem 1.9.2 and Lemma 1.9.16 that the set

A ⊕ B = {2x | x ∈ A} ∪ {2x + 1 | x ∈ B}

belongs to Δ_{n+1}^{0} \ (Σ_{n}^{0} ∪ Π_{n}^{0}).

Exercises 1.9.20.

1. Show that the sets

H = {x | φ_{x}^{(1)}(0) is defined}

and

K = {x | φ_{x}^{(1)}(x) is defined}

are complete Σ_{1}^{0} sets.

2. Show that the set

T = {x | φ_{x}^{(1)} is total}

is a complete Π_{2}^{0} set.

Exercise 1.9.21. What reducibility and non-reducibility relations exist among the following sets? Note that H, T, E, and S are index sets.

K = {x ∈ ℕ | φ_{x}^{(1)}(x) ↓},
H = {x ∈ ℕ | φ_{x}^{(1)}(0) ↓},
T = {x ∈ ℕ | φ_{x}^{(1)} is total},
E = {x ∈ ℕ | φ_{x}^{(1)} is the empty function},
S = {x ∈ ℕ | dom(φ_{x}^{(1)}) is infinite}.

Prove your answers.

Hint: Using the Parametrization Theorem as in the proof of Theorem 1.7.11, show that H and K are Σ_{1}^{0} complete, S and T are Π_{2}^{0} complete, and E is Π_{1}^{0} complete. These completeness facts, together with Lemma 1.9.16 and Theorem 1.9.18, determine the reducibility relations among H, K, S, T, and E.

Undecidability of Arithmetic

We are going to show that arithmetic is undecidable. This means that there is no algorithm to decide whether a given sentence in the language of arithmetic is true or false.

2.1 Terms, Formulas, and Sentences

By arithmetic we mean the set of sentences which are true in the structure (ℕ, +, ·, 0, 1, =). Here ℕ = {0, 1, 2, …} is the set of non-negative integers, + and · denote the 2-place operations of addition and multiplication on ℕ, and = denotes the 2-place relation of equality between elements of ℕ. For the benefit of the reader who has not previously studied mathematical logic, we shall now review the concept of a sentence being true in a structure. Since we are only interested in the particular structure (ℕ, +, ·, 0, 1, =), we shall concentrate on that case.

It is first necessary to define a language appropriate for the structure

(ℕ, +, ·, 0, 1, =).

Our language contains infinitely many variables x_{0}, x_{1}, …, x_{n}, … which are usually denoted by letters such as x, y, z, …. Each of these variables is also a term of our language. In addition the symbols 0 and 1 are terms. Other terms are built up using the 2-place operation symbols + and ·. Examples of terms are

1 + 1 + 1 ,  x + 1 ,  (x + y) · z + x .

When writing terms, we may employ the usual abbreviations. For instance 1 + 1 + 1 = 3 and x · x · x = x^{3}. Thus a term is essentially a polynomial in several variables with non-negative integer coefficients.

An atomic formula is a formula of the form t_{1} = t_{2} where t_{1} and t_{2} are terms. Examples of atomic formulas are

x + 1 = y , x = 3y^{2} + 1 .

Formulas are built from atomic formulas by using the Boolean propositional connectives ∧, ∨, ¬ (and, or, not) and the quantifiers ∀, ∃ (for all, there exists). An example of a formula is

∃z (x + z + 1 = y)  (2.1)

In this formula, x, y and z are to be interpreted as variables ranging over the set ℕ. Similarly the expression ∃z … is to be interpreted as “there exists a non-negative integer z in ℕ such that ….” Thus the formula (2.1) expresses the assertion that x is less than y. From now on we shall write x < y as an abbreviation for (2.1). This idea of introducing new relation symbols as abbreviations for formulas allows us to expand our language indefinitely.

Another example of a formula is

x > 1 ∧ ¬ ∃y ∃z (y > 1 ∧ z > 1 ∧ x = y · z) .  (2.2)

This formula expresses the assertion that x is a prime number. Thus we might choose to abbreviate (2.2) by some expression such as Prime(x) or “x is prime.”

In any particular formula, a free variable is a variable which is not acted on by any quantifier in that formula. For example, the free variables of (2.1) are x and y, while in (2.2) the only free variable is x. A sentence is a formula with no free variables. Examples of sentences are

∀x (∃y (x = 2y) ∨ ∃y (x = 2y + 1))  (2.3)

and

∀x ∃y (x = y + 1) .  (2.4)

When interpreting formulas or sentences in the structure (ℕ, +, ·, 0, 1, =), please bear in mind that the quantifiers ∀ and ∃ range over the set of nonnegative integers, ℕ. Thus ∀x means “for all x in ℕ,” and ∃x means “for some x in ℕ” or “there exists x in ℕ such that ….” With this understanding, we know what it means for a sentence of our language to be true or false in the structure (ℕ, +, ·, 0, 1, =). For example (2.3) is true (because every element of ℕ is either even or odd) and (2.4) is false (because not every element of ℕ is the successor of some other element of ℕ).

Let F (x_{1}, …, x_{k}) be a formula whose free variables are x_{1}, …, x_{k}. Then for any non-negative integers a_{1}, …, a_{k} ∈ ℕ, we can form the sentence F (a_{1}, …, a_{k}) which is obtained by substituting (“plugging in”) the constants a_{1}, …, a_{k} for the free occurrences of the variables x_{1}, …, x_{k}. For example, let F (x, y) be the formula

∃z (x^{2} + z = y)

with free variables x and y. Then for any particular non-negative integers m and n, F (m, n) is a sentence which expresses the assertion that m^{2} is less than or equal to n. For instance F (5, 40) is true and F (5, 20) is false.

This completes our review of the concept of a sentence being true or false in the structure (ℕ, +, ·, 0, 1, =).

Exercise 2.1.1. Write a sentence expressing Goldbach’s Conjecture: Every even number is the sum of two prime numbers.

2.2 Arithmetical Definability

We now present a key definition.

Definition 2.2.1 (Arithmetical Definability). A k-place partial function

λx_{1} ⋯ x_{k} [ ψ(x_{1}, …, x_{k}) ]

is said to be arithmetically definable if there exists a formula

F (x_{1}, …, x_{k}, x_{k+1})

with free variables x_{1}, …, x_{k}, x_{k+1}, such that for all m_{1}, …, m_{k}, n ∈ ℕ,

ψ(m_{1}, …, m_{k}) ≃ n if and only if F (m_{1}, ..., m_{k}, n) is true.

(Of course it doesn’t matter whether we use the variables x_{1}, …, x_{k}, x_{k+1} or some other set of k + 1 distinct variables.)

For example, the 1-place function λx [ 2x] is arithmetically definable, by the formula y = 2x. (Here we are using a formula with two free variables x and y.) As another example, note that the 2-place functions λxy [ Quotient(y, x) ] and λxy [ Remainder(y, x) ] (the quotient and remainder of y on division by x) are arithmetically definable, by the formulas

∃u ∃v (y = u · x + v ∧ v < x ∧ z = u)

and

∃u ∃v (y = u · x + v ∧ v < x ∧ z = v)

respectively. (Here we are using formulas with free variables x, y, and z.)

Exercise 2.2.2. Show that the function

λxy [ least common multiple of x and y]

is arithmetically definable.

Remark 2.2.3. A more “mathematical” characterization of arithmetical definability, not involving formulas, may be given as follows. Let us say that a predicate P ⊆ ℕ^{k} is strongly Diophantine if there exists a polynomial with integer coefficients, f(x_{1}, …, x_{k}) ∈ ℤ[x_{1}, …, x_{k}], such that

P = {⟨a_{1}, …, a_{k}⟩ ∈ ℕ^{k} | f(a_{1}, …, a_{k}) = 0}.

For Q ⊆ ℕ^{k+1}, the projection of Q is given as

π(Q) = {⟨a_{1}, …, a_{k}⟩ ∈ ℕ^{k} | ⟨a_{1}, …, a_{k}, a_{k+1}⟩ ∈ Q for some a_{k+1} ∈ ℕ} .

Then, the arithmetically definable predicates may be characterized as the smallest class of number-theoretic predicates which contains all strongly Diophantine predicates and is closed under union, complementation, and projection. Clearly each arithmetically definable predicate is obtained by applying these operations only a finite number of times.

Exercise 2.2.4. Show that the following number-theoretic predicates are arithmetically definable, by exhibiting formulas which define them over the structure (ℕ, +, ·, 0, 1, =).

1. GCD(x, y) = z.

2. LCM(x, y) = z.

3. Quotient(x, y) = z.

4. Remainder(x, y) = z.

5. x is the largest prime number less than y.

6. x is the product of all the prime numbers less than y.

Remark 2.2.5. The principal result of this section, Theorem 2.2.21 below, is that all recursive functions and predicates are arithmetically definable. From this it will follow easily that there exists an arithmetically definable predicate which is not recursive (Corollary 2.2.22 below). In addition, we shall characterize the class of arithmetically definable predicates in terms of the arithmetical hierarchy (Theorem 2.2.23 below).

Lemma 2.2.6. The initial functions are arithmetically definable.

Proof. The constant zero function λx [ 0 ] is defined by the formula

x = x ∧ y = 0 .

The successor function λx [ x + 1 ] is defined by the formula

y = x + 1 .

For 1 ≤ i ≤ k, the projection function λx_{1} … x_{k} [ x_{i}] is defined by the formula

x_{1} = x_{1} ∧ … ∧ x_{k} = x_{k} ∧ y = x_{i} .

This completes the proof.

Lemma 2.2.7. If the functions g_{1}(x_{1}, …, x_{k}), …, g_{m}(x_{1}, …, x_{k}) and h(y_{1}, …, y_{m}) are arithmetically definable, then so is the function

f(x_{1}, …, x_{k}) = h(g_{1}(x_{1}, …, x_{k}), …, g_{m}(x_{1}, …, x_{k}))

obtained by composition.

Proof. Let g_{1}(x_{1}, …, x_{k}), …, g_{m}(x_{1}, …, x_{k}), h(y_{1}, …, y_{m}) be defined by the formulas

G_{1}(x_{1}, …, x_{k}, y) , …, G_{m}(x_{1}, …, x_{k}, y) , H(y_{1}, …, y_{m}, z)

respectively. Then f(x_{1}, …, x_{k}) is defined by the formula

∃y_{1} ⋯ ∃y_{m}(G_{1}(x_{1}, …, x_{k}, y_{1}) ∧ … ∧ G_{m}(x_{1}, …, x_{k}, y_{m}) ∧ H(y_{1}, …, y_{m}, z))

which we may abbreviate as F (x_{1}, …, x_{k}, z). This proves the lemma.

A k-place predicate P (x_{1}, …, x_{k}) is said to be arithmetically definable if it is definable over the structure (ℕ, +, ·, 0, 1, =) by a formula with k free variables x_{1}, …, x_{k}.

Lemma 2.2.8. If the k+1-place predicate R(x_{1}, …, x_{k}, y) is arithmetically definable, then so is the k-place partial function

ψ(x_{1}, …, x_{k}) ≃ least y such that R(x_{1}, …, x_{k}, y) holds.

Proof. Our λx_{1} … x_{k}[ψ(x_{1}, …, x_{k})] is arithmetically definable by the formula

R(x_{1}, …, x_{k}, y) ∧ ¬ ∃z (z < y ∧ R(x_{1}, …, x_{k}, z))

which we may abbreviate as F (x_{1}, …, x_{k}, y). This proves the lemma.

It remains to prove:

Lemma 2.2.9. If the total k-place function g(y_{1}, …, y_{k}) and the total k+2place function h(x, z, y_{1}, …, y_{k}) are arithmetically definable, then so is the total k+1-place function

f(x, y_{1}, …, y_{k})

obtained by primitive recursion:

\begin{aligned}f(0, y_{1}, …, y_{k}) & = & g(y_{1}, …, y_{k}) , \\ f(x + 1, y_{1}, …, y_{k}) & = & h(x, f(x, y_{1}, …, y_{k}), y_{1}, …, y_{k})) . \end{aligned}

In order to prove Lemma 2.2.9, we need some definitions and lemmas from number theory. Two positive integers m and n are said to be relatively prime if they have no common factor greater than 1. A set of positive integers is said to be pairwise relatively prime if any two distinct integers in the set are relatively prime.

Lemma 2.2.10. Given a positive integer k, we can find infinitely many positive integers a such that the k integers in the set

a + 1 , 2a + 1 , …, ka + 1

are pairwise relatively prime.

Proof. Let a be any positive integer which is divisible by all of the prime numbers which are less than k. We claim that a + 1, 2a + 1, …, ka + 1 are pairwise relatively prime. Suppose not. Let i and j be such that 1 ≤ i < j ≤ k and ia+1 and ja+1 are not relatively prime. Let p be a prime number which is a factor of both ia + 1 and ja + 1. Then p cannot be a factor of m. Hence p is greater than or equal to k. On the other hand p is a factor of (ja + 1) − (ia + 1) = (j − i)a. Hence p is a factor of j − i. But j − i is less than k, hence p is less than k, a contradiction.

Example 2.2.11. If k = 5, the primes less than k are 2 and 3, so we can take a to be any multiple of 6. Then the integers a + 1, 2a + 1, 3a + 1, 4a + 1, 5a + 1 will be pairwise relatively prime. Taking a = 6 we see that 7, 13, 19, 25, 31 are paiwise relatively prime. Taking a = 12 we see that 13, 25, 37, 49, 61 are pairwise relatively prime. And taking a = 600 we see that 601, 1201, 1801, 2401, 3001 are pairwise relatively prime.

Lemma 2.2.12 (Chinese Remainder Theorem). Let m_{1}, …, m_{k} be a set of k distinct positive integers which are pairwise relatively prime. Then for any given non-negative integers r_{i} < m_{i}, 1 ≤ i ≤ k, we can find a non-negative integer r such that Remainder(r, m_{i}) = r_{i} for all i.

Proof. Let m be the product of m_{1}, …, m_{k}. For any non-negative integer r less than m, define the remainder sequence of r to be the sequence ⟨r_{1}, …, r_{k}⟩ where r_{i} = Remainder(r, m_{i}). We claim that any two distinct non-negative integers less than m have distinct remainder sequences. To see this, let r and s be non-negative integers less than m. If r and s have the same remainder sequence, then r − s is divisible by each of m_{1}, …, m_{k}. Since m_{1}, …, m_{k} are pairwise relatively prime, it follows that r − s is divisible by m. Since r and s are both less than m, we must have r = s. This proves the claim. Define a possible remainder sequence to be any sequence ⟨r_{1}, …, r_{k}⟩ with 0 ≤ r_{i} < m_{i} for all i. The number of possible remainder sequences is exactly m. From this and the claim, we see that any possible remainder sequence must actually occur as the remainder sequence associated with some r in the range 0 ≤ r < m. The lemma follows immediately.

Example 2.2.13. Continuing the previous example, we see that for any nonnegative integers r_{1} < 7, r_{2} < 13, r_{3} < 19, r_{4} < 25, r_{5} < 31, there must be a non-negative integer r less than 7·13·19·25·31 such that Remainder(r, 7) = r_{1}, …, Remainder(r, 31) = r_{5}. We may view the integer r as a “code” for the sequence (r_{1}, r_{2}, r_{3}, r_{4}, r_{5}). The “decoding” is accomplished by means of the key integer 6, since r_{i} = Remainder(r, 6i + 1).

Definition 2.2.14. For any non-negative integers r, a, i, we define

β(r, a, i) = Remainder(r, a · (i + 1) + 1) .

This 3-place function is known as Gödel’s β-function. Note that the β-function is arithmetically definable.

The significance of the β-function is that it can be used to encode an arbitrary sequence of non-negative integers ⟨r_{0}, r_{1}, …, r_{k}⟩ by means of two nonnegative integers r and a. We make this precise in the following lemma.

Lemma 2.2.15. Given a finite sequence of non-negative integers r_{0}, r_{1}, …, r_{k}, we can find a pair of non-negative integers r and a such that β(r, a, 0) = r_{0}, β(r, a, 1) = r_{1}, …, β(r, a, k) = r_{k}.

Proof. By Lemma 2.2.10 (replacing k by k + 1), we can find a positive integer a such that r_{0} < a+1, r_{1} < 2a+1, …, r_{k} < (k +1)·a+1, and furthermore a+1, 2a + 1, …, (k + 1) · a + 1 are pairwise relatively prime. Then by Lemma 2.2.12 we can find a non-negative integer r such that Remainder(r, a + 1) = r_{0}, Remainder(r, 2a + 1) = r_{1}, …, Remainder(r, (k + 1) · a + 1) = r_{k}. This proves the lemma.

Exercise 2.2.16. Find a pair of numbers r, a such that β(r, a, 0) = 11, β(r, a, 1) = 19, β(r, a, 2) = 30, β(r, a, 3) = 37, β(r, a, 4) = 51.

Hint: First find an appropriate a by hand. Then write a small computer program to find r by brute force.

We are now ready to prove Lemma 2.2.9.

Proof of Lemma 2.2.9. Let the total functions g(y_{1}, …, y_{k}) and h(x, z, y_{1}, …, y_{k}) be defined by the formulas G(y_{1}, …, y_{k}, w) and H(x, z, y_{1}, …, y_{k}, w) respectively. We wish to write down a formula F (x, y_{1}, …, y_{k}, w) which would say that there exists a finite sequence r_{0}, r_{1}, …, r_{x} such that G(y_{1}, …, y_{k}, r_{0}) holds, and H(i, r_{i}, y_{1}, …, y_{k}, r_{i+1}) holds for all i < x, and finally r_{x} = w. If we could do this, then clearly F (x, y_{1}, …, y_{k}, w) would define the function f(x, y_{1}, …, y_{k}). This would prove the lemma. The only difficulty is that our language is not powerful enough to talk directly about finite sequences of variable length in the required way. Our language allows us to say things like “there exists a non-negative integer r such that …,” but it does not allow us to directly say things like “there exists a sequence of non-negative integers r_{0}, r_{1}, …, r_{x} (of variable length, x) such that ….” The way to overcome this difficulty is to use the β-function. Instead of saying “there exists a finite sequence r_{0}, r_{1}, …, r_{k},” we can say “there exists a pair of non-negative integers r and a which encode the required sequence, via the β-function.” Namely, we write down a formula F (x, y_{1}, …, y_{k}, w) which says, informally, there exist r and a such that G(y_{1}, …, y_{k}, β(r, a, 0)) holds, and H(i, β(r, a, i), y_{1}, …, y_{k}, β(r, a, i + 1)) holds for all i < x, and finally β(r, a, x) = w. By Lemma 2.2.15 it is clear that this formula defines the function f(x, y_{1}, …, y_{k}). Formally, let B(r, a, i, w) be a formula which defines the β-function. We may then take F (x, y_{1}, …, y_{k}, w) to be the formula

\begin{matrix}∃r ∃a ( ∃u (B(r, a, 0, u) ∧ G(y_{1}, …, y_{k}, u)) ∧ B(r, a, x, w) ∧ \\ ∀i ( i ≥ x ∨ ∃u ∃v (B(r, a, i, u) ∧ B(r, a, i + 1, v) ∧ H(i, u, y_{1}, …, y_{k}, v)) ) ) . \end{matrix}

This completes the proof of Lemma 2.2.9.

Example 2.2.17. The exponential function λxy [ y^{x}] is arithmetically definable by the formula

\begin{matrix}∃r ∃a ( B(r, a, 0, 1) ∧ B(r, a, x, w) ∧ \\ ∀i ( i ≥ x ∨ ∃u ∃v (B(r, a, i, u) ∧ B(r, a, i + 1, v) ∧ v = u · y) ) ) \end{matrix}

which we may abbreviate as Exp(x, y, w), meaning that y^{x} = w.

Exercise 2.2.18. Consider the function f : ℕ → ℕ defined by

f(n) = \{ \begin{matrix}n/2 & if n is even, \\ 3n + 1 & if n is odd. \end{matrix}

For each k ∈ ℕ let

f^{k} = \underbrace{f ∘ ⋯ ∘ f}_{k} ,

i.e., f^{0}(n) = n and f^{k+1}(n) = f(f^{k}(n)).

Write a formula F (x, y, z) in the language +, ·, 0, 1, =, < which, when interpreted over the natural number system ℕ, defines the 3-place predicate f^{x}(y) = z.

Exercise 2.2.19. Show that the function λx [ the xth Fibonacci number ] is arithmetically definable.

Exercise 2.2.20. Which of the following number-theoretic predicates are arithmetically definable? Prove your answers.

1. x is the sum of all the prime numbers less than y.

2. x^{y} = z.

3. x! = y.

Theorem 2.2.21. Every partial recursive function is arithmetically definable.

Proof. Recall that the partial recursive functions have been characterized as the smallest class of functions which includes the initial functions and is closed under composition, primitive recursion, and the least-number operator. Lemma 2.2.6 says that the class of arithmetically definable functions includes the initial functions. Lemmas 2.2.7, 2.2.8, and 2.2.9 say that the class of arithmetically definable functions is closed under composition, the least-number operator, and primitive recursion, respectively. It follows that the arithmetically definable functions include the partial recursive functions.

Corollary 2.2.22. There exists a set K ⊆ ℕ which is arithmetically definable but not recursive.

Proof. Recall that

K = {x ∈ ℕ | φ_{x}^{(1)}(x) is convergent}

is our basic example of a non-recursive set. By the Enumeration Theorem, the 2-place partial function λxy[φ_{x}^{(1)}(y)] is partial recursive. Hence, by Theorem 2.2.21 λxy[φ_{x}^{(1)}(y)] is arithmetically definable. Let F (x, y, z) be a formula which defines this function. Then K is defined by the formula ∃zF (x, x, z). This completes the proof.

More generally, recall our discussion of the arithmetical hierarchy in Chapter 1, Section 1.9. The next theorem characterizes arithmetically definability (Definition 2.2.1) in terms of the arithmetical hierarchy (Definition 1.9.1).

Theorem 2.2.23. Let P be a k-place predicate, P ⊆ ℕ^{k}. The following are equivalent:

1. P is arithmetically definable;

2. P belongs to the arithmetical hierarchy, i.e., P belongs to the class Σ_{n}^{0} for some n ∈ ℕ.

Proof. Theorem 2.2.21 implies that every predicate in the class Σ_{0}^{0} (= Π_{0}^{0}) is arithmetically definable. From this it is straightforward to prove by induction on n ∈ ℕ that every predicate in the class Σ_{n}^{0} ∪ Π_{n}^{0} is arithmetically definable. For the converse, put

Σ_{∞}^{0} = ⋃_{n∈ℕ} Σ_{n}^{0} = ⋃_{n∈ℕ} Π_{n}^{0} .

By Theorem 1.9.2, the class Σ_{∞}^{0} is closed under Boolean connectives ∧, ∨, ¬ and universal and existential quantification ∀ and ∃. From this it follows that every arithmetically definable predicate P belongs to the class Σ_{∞}^{0}; this is proved by induction on the number of symbols in a defining formula for P.

Exercise 2.2.24. Let A and B be subsets of ℕ. Prove that if A is reducible to B and B is arithmetically definable, then A is arithmetically definable.

Exercise 2.2.25. For each n ≥ 1 let C_{n} be a set which is Σ_{n}^{0} complete. Consider the set B = {2^{n}3^{x} | x ∈ C_{n}}. Prove that B is not arithmetically definable.

Remark 2.2.26 (Hilbert’s Tenth Problem). A refinement of Theorem 2.2.23 due to Matiyasevich 1967 is as follows. Let us say that P ⊆ ℕ^{k} is Diophantine if P = π^{l}(Q) for some l ≥ 0 and some strongly Diophantine Q ⊆ ℕ^{k+l}. Thus

P = {⟨a_{1}, …, a_{k}⟩ ∈ ℕ^{k} | ∃⟨b_{1}, …, b_{l}⟩ ∈ ℕ^{l} (f(a_{1}, …, a_{k}, b_{1}, …, b_{l}) = 0)} where f(x_{1}, …, x_{k}, y_{1}, …, y_{l}) is a polynomial with integer coefficients. Matiyasevich’s Theorem states that P is Diophantine if and only if P is Σ_{1}^{0}.

A corollary of Matiyasevich’s Theorem is that, for example, the sets K and H are Diophantine. Thus, we can find a polynomial f(z, x_{1}, …, x_{l}) with integer coefficients, such that the set of a ∈ ℕ for which f(a, x_{1}, …, x_{l}) = 0 has a solution in ℕ is nonrecursive. Here it is known that one can take l = 9, but l = 8 is an open question.

Hilbert’s Tenth Problem, as stated in Hilbert’s famous 1900 problem list, reads as follows:

To find an algorithm which allows us, given a polynomial equation in several variables with integer coefficients, to decide in a finite number of steps whether or not the equation has a solution in integers.

From Matiyasevich’s Theorem plus the unsolvability of the Halting Problem, it follows that there is no such algorithm. In other words, Hilbert’s Tenth Problem is unsolvable.

A full exposition of Hilbert’s Tenth Problem and the proof of Matiyasevich’s Theorem is in my lecture notes for Math 574, Spring 2005, at

             http://www.math.psu.edu/simpson/notes/.

Exercise 2.2.27. Recall that ℕ = {0, 1, 2, …} = the natural numbers, while ℤ = {…, −2, −1, 0, 1, 2, …} = the integers. In our formulation of Matiyasevich’s Theorem, we have spoken of solutions in ℕ. What happens if we replace “solution in ℕ” by “solution in ℤ”?

Hint: Use the following well-known theorem of Lagrange: For each n ∈ ℕ there exist a, b, c, d ∈ ℕ such that n = a^{2} + b^{2} + c^{2} + d^{2}.

2.3 Gödel Numbers of Formulas

For each formula F in the language of arithmetic, we shall define a unique positive integer #(F), which will be called the Gödel number of F. The number #(F) will serve as a “code” for the formula F.

Before assigning Gödel numbers to formulas, we shall first assign Gödel numbers to terms. We define

\begin{aligned}#(0) & = & 1 \\ #(1) & = & 3 \\ #(x_{i}) & = & 3^{2} · 5^{i} \\ #(t_{1} + t_{2}) & = & 3^{3} · 5^{#(t_{1})} · 7^{#(t_{2})} \\ #(t_{1} · t_{2}) & = & 3^{4} · 5^{#(t_{1})} · 7^{#(t_{2})} \end{aligned}

For example, the Gödel number of the term 1 + x_{0} is

#(1 + x_{0}) = 3^{3} · 5^{3} · 7^{9}

since #(1) = 3 and #(x_{0}) = 9.

We now define the Gödel numbers of formulas:

\begin{aligned}#(t_{1} = t_{2}) & = & 2 · 5^{#(t_{1})} · 7^{#(t_{2})} \\ #(F ∧ G) & = & 2 · 3 · 5^{#(F)} · 7^{#(G)} \\ #(F ∨ G) & = & 2 · 3^{2} · 5^{#(F)} · 7^{#(G)} \\ #(¬ F) & = & 2 · 3^{3} · 5^{#(F)} \\ #(∀x_{i}F) & = & 2 · 3^{4} · 5^{i} · 7^{#(F)} \\ #(∃x_{i}F) & = & 2 · 3^{5} · 5^{i} · 7^{#(F)} \end{aligned}

For example, the Gödel number of the formula ∃x_{1}(x_{1} = 1) is

#(∃x_{1}(x_{1} = 1)) = 2 · 3^{5} · 5^{1} · 7^{2·5^{45}·7^{3}}

since #(x_{1}) = 45, #(1) = 3, and #(x_{1} = 1) = 2 · 5^{45} · 7^{3}.

If F is any collection of formulas, we denote by #(F) the collection of all Gödel numbers of formulas in F. Let

Fml = #(all formulas) ,

Snt = #(all sentences) ,

and TrueSnt = #(all true sentences) .

Note that Fml, Snt, and TrueSnt are subsets of ℕ.

Theorem 2.3.1. The sets Fml and Snt are primitive recursive.

Proof. The proof is straightforward and we omit it.

We are going to prove that the set TrueSnt is nonrecursive. In other words, the problem of deciding whether a given sentence of the language of arithmetic is true or false is unsolvable. This result may be paraphrased as “arithmetical truth is undecidable,” or simply, “arithmetic is undecidable.”

Theorem 2.3.2. Every arithmetically definable set A ⊆ ℕ is reducible to TrueSnt.

Proof. Given an arithmetically definable set A, let F (x_{1}) be a formula with one free variable x which defines A, i.e.,

A = {m ∈ ℕ | F (m) is true} .

Define

f(m) = #(∃x_{1}(x_{1} = m ∧ F (x_{1}))) .

Thus for all m ∈ ℕ we have that m ∈ A if and only if f(m) ∈ TrueSnt. We claim that the function f : ℕ → ℕ is primitive recursive. This is clear since

f(m) = 2 · 3^{3} · 7^{2·3·5^{#(x_{1}=m)}·7^{#(F (x_{1}))}}

where

#(x_{1} = m) = 2 · 5^{45} · 7^{#(m)} ,

and #(m) = #(\underbrace{1 + … + 1}_{m}) can be defined primitive recursively by

\begin{aligned}#(0) & = & 1 , \\ #(m + 1) & = & 3^{3} · 5^{#(m)} · 7^{3} . \end{aligned}

Thus A is reducible to TrueSnt via f. This proves the theorem.

Theorem 2.3.3. TrueSnt is not recursive.

Proof. By Corollary 2.2.22 we have an arithmetically definable set K which is not recursive. By the previous theorem K is reducible to TrueSnt. Hence by Lemma 1.7.8 TrueSnt is not recursive.

More generally we have the following theorem, which may be paraphrased as “arithmetical truth is not arithmetically definable.”

Theorem 2.3.4 (Tarski). TrueSnt is not arithmetically definable.

Proof. Suppose that TrueSnt were arithmetically definable. Then by Theorem 2.2.23 we would have that TrueSnt belongs to the class Σ_{n}^{0} for some n. By Theorem 1.9.18, let C be a complete Σ_{n+1}^{0} set. By Theorem 2.2.23 C is arithmetically definable. Hence by Theorem 2.3.2 C is reducible to TrueSnt. Hence by Lemma 1.9.16 C belongs to the class Σ_{n}^{0}. This contradicts that fact (Theorem 1.9.18) that a complete Σ_{n+1}^{0} set can never belong to the class Σ_{n}^{0}. This completes the proof.

Exercise 2.3.5. Prove that the set Fml of all Gödel numbers of formulas is primitive recursive.

Exercise 2.3.6. Prove that the set Snt of all Gödel numbers of sentences is primitive recursive.

The Real Number System

In Chapter 2 we have shown that TrueSnt_{ℕ} is nonrecursive, i.e., the theory of the natural number system is undecidable. In this Chapter we shall show that, by contrast, TrueSnt_{ℝ} is recursive, i.e., the theory of the real number system is decidable.

3.1 Quantifier Elimination

Let L_{OR} be the language of ordered rings, i.e.,

L_{OR} = (+, −, ·, 0, 1, <, =)

where + and · are 2-ary operation symbols, − is a 1-ary operation symbol, < and = are 2-place predicate symbols, and 0 and 1 are constant symbols. We consider the L_{OR}-structure

R = (ℝ, +_{ℝ}, −_{ℝ}, ·_{ℝ}, 0_{ℝ}, 1_{ℝ}, <_{ℝ}, =_{ℝ}) ,

i.e., the real number system, the ordered field of real numbers. Formulas of L_{OR} are interpreted with reference to R, i.e., ∃x … means “there exists x ∈ ℝ such that …,” etc.

Two L_{OR}-formulas F and G are said to be equivalent if they have the same free variables x_{1}, …, x_{k} and define the same k-place predicate P ⊆ ℝ^{k}. An equivalent condition is that the sentence

∀x_{1} ⋯ ∀x_{k} (F (x_{1}, …, x_{k}) ⇔ G(x_{1}, …, x_{k}))

is true in R.

We are going to prove the following theorem, due originally to Tarski:

Theorem 3.1.1 (Quantifier Elimination). For any L_{OR}-formula F, we can find an equivalent quantifier-free L_{OR}-formula F^{∗}.

Example 3.1.2. The formula

∃x (ax^{2} + bx + c = 0)

is equivalent to the quantifier-free formula

(a = 0 ∧ b = 0 ∧ c = 0) ∨ (a = 0 ∧ b ≠ 0) ∨ (a ≠ 0 ∧ b^{2} − 4ac ≥ 0) .

Exercise 3.1.3. Find quantifier-free formulas in the language +, −, ·, 0, 1, <, = which are equivalent, over the real number system ℝ, to:

1. ∃x (ax^{2} + bx + c > 0).

2. ∃x (ax^{3} + bx^{2} + cx + d > 0).

3. ∃x (ax^{4} + bx^{3} + cx^{2} + dx + e > 0).

Exercise 3.1.4. Does there exist a constant c such that the following holds?

Given a formula F (x) in the language +, ·, 0, 1, = with exactly one free variable x, we can find a formula F^{∗}(x) in the same language which is equivalent to F (x) over the natural number system ℕ, and which contains at most c quantifiers.

Prove your answer.

Remark 3.1.5. The only properties of R that will be used in the proof of Theorem 3.1.1 are: (1) R is a commutative ordered field; and (2) R has the intermediate value property for polynomials, i.e.,

( x < y ∧ p(x) < 0 < p(y) ) ⇒ ∃z ( x < z < y ∧ p(z) = 0 )

for any polynomial p(x) ∈ ℝ[x]. An ordered field with these properties is called a real closed ordered field. This is related to Hilbert’s 17th Problem.

Remark 3.1.6. The proof of Theorem 3.1.1 which we shall present below is due to P. J. Cohen. In order to present the proof, we shall define and study a class of functions called the effective functions. This notion of effectivity has no importance beyond the proof of Theorem 3.1.1. See also Corollary 3.1.21 below.

Definition 3.1.7. A predicate A on the reals, i.e., A ⊆ ℝ^{k}, is said to be effective if it is definable over R by a quantifier-free formula. That is, A is a Boolean combination of sets in ℝ^{k} which are defined by equations and inequations p(x_{1}, …, x_{k}) = 0, p(x_{1}, …, x_{k}) > 0, where p ∈ ℤ[x_{1}, …, x_{k}].

Remark 3.1.8. If we allow parameters from ℝ, we get semi-algebraic sets. Thus “effective = semi-algebraic with parameters from ℤ”.

Definition 3.1.9. A function f : D → ℝ, D ⊆ ℝ^{k} is said to be effective if 1. D is effective, and

2. for every effective predicate A(x_{1}, …, x_{k}, y, z_{1}, …, z_{n}), the predicate

B(x_{1}, …, x_{k}, z_{1}, …, z_{n}) ≡ A(x_{1}, …, x_{k}, f(x_{1}, …, x_{k}), z_{1}, …, z_{n})

is effective.

Example 3.1.10. It can be shown that the function \sqrt{x} is effective. This is because, first, the domain of \sqrt{x} is the effective set \{x ∈ ℝ | x ≥ 0\}, and second, for instance, \sqrt{x} > 3 ≡ x > 9.

In order to prove Theorem 3.1.1, we shall build up a library of effective functions. We shall use notations such as \overline{x} and \overline{y} to abbreviate sequences of variables such as x_{1}, …, x_{k} and y_{1}, …, y_{m}.

Lemma 3.1.11. The functions x + y, x · y, −x and x/y are effective.

Proof. For x + y, x · y and −x there is nothing to prove. For x/y, note first that the domain is {(x, y) | y ≠ 0} which is obviously effective. It remains to show that if A(z, …) is an effective predicate then so is A(x/y, …). The latter is a Boolean combination of predicates of the form

a_{n} (\frac{x}{y})^{n} + … + a_{1} (\frac{x}{y}) + a_{0} > 0

and this is equivalent to the atomic formula

a_{n}x^{n} + a_{n−1}x^{n−1}y + … + a_{1}xy^{n−1} + a_{0}y^{n} > 0 ,

assuming as we may that n is even.

Corollary 3.1.12. Any rational function

f(x_{1}, …, x_{k}) ∈ ℚ(x_{1}, …, x_{k})

is effective.

Lemma 3.1.13. The composition of effective functions is effective.

Proof. Consider for instance f(g(x)) where f and g are effective 1-place functions. If D(y) is a quantifier-free formula defining the dom(f), then D(g(x)) defines the dom(fg), which is therefore effective. If A(y, \overline{z}) is any effective predicate, then clearly A(f(y), \overline{z}) is effective, hence A(f(g(x)), \overline{z}) is effective.

Lemma 3.1.14. The function

sgn(x) = \{ \begin{matrix}1 & if x > 0 \\ 0 & if x = 0 \\ −1 & if x < 0. \end{matrix}

is effective.

Proof. Let A(y, \overline{z}) be an effective predicate. Then A(sgn(x), \overline{z}) is equivalent to

(x > 0 ∧ A(1, \overline{z})) ∨ (x = 0 ∧ A(0, \overline{z})) ∨ (x < 0 ∧ A(−1, \overline{z}))

which is again effective. This proves the lemma.

More generally we have:

Lemma 3.1.15. If a function f(\overline{x}) takes only finitely many values, all integers, then f(\overline{x}) is effective if and only if for each j ∈ ℤ, the predicate f(\overline{x}) = j is effective.

Proof. If: Let j_{1}, …, j_{n} be the finitely many values. For any effective predicate A(y, \overline{z}), the predicate A(f(\overline{x}), \overline{z}) is equivalent to

(f(\overline{x}) = j_{1} ∧ A(j_{1}, \overline{z})) ∨ ⋯ ∨ (f(\overline{x}) = j_{n} ∧ A(j_{n}, \overline{z}))

and is therefore effective.

Only if: Trivial.

Lemma 3.1.16 (Definition by Cases). If two functions f_{1}(\overline{x}) and f_{2}(\overline{x}) and a predicate A(\overline{x}) are effective, then the function

f(\overline{x}) = \{ \begin{matrix}f_{1}(\overline{x}) & if A(\overline{x}), \\ f_{2}(\overline{x}) & if ¬ A(\overline{x}) \end{matrix}

is effective.

Proof. We must show that, for each effective predicate B(y, \overline{z}), the predicate C(\overline{x}, \overline{z}) ≡ B(f(\overline{x}), \overline{z}) is effective. This is so because C(\overline{x}, \overline{z}) is equivalent to

(A(\overline{x}) ∧ B(f_{1}(\overline{x}), \overline{z})) ∨ (¬ A(\overline{x}) ∧ B(f_{2}(\overline{x}), \overline{z})) .

Since f_{1}(\overline{x}) and f_{2}(\overline{x}) and B(y, \overline{z}) are effective, B(f_{1}(\overline{x}), \overline{z}) and B(f_{2}(\overline{x}), \overline{z}) are effective. Since A(\overline{x}) is effective, it follows that C(\overline{x}, \overline{z}) is effective. This proves the lemma.

The extension of the previous lemma to more than two cases is obvious.

Lemma 3.1.17. A function f(\overline{x}) is effective if and only if for every positive integer d ≥ 1 and every polynomial q(y) ∈ ℝ[y] of degree d, sgn(q(f(\overline{x}))) is an effective function of \overline{x} and the d + 1 coefficients of q(y).

Proof. Only if: Trivial, since for instance

sgn(q(f(\overline{x}))) = 1 ≡ q(f(\overline{x})) > 0 ≡ A(f(\overline{x})),

where A(y) is the predicate q(y) > 0.

If: We must show that if A(y, \overline{z}) is effective then A(f(\overline{x}), \overline{z}) is effective. Note that A(y, \overline{z}) can be viewed as a Boolean combination of atomic predicates of the form p(y, \overline{z}) > 0, for various polynomials p(y, \overline{z}) with coefficients in ℤ. It suffices to show that the predicates p(f(\overline{x}), \overline{z}) > 0 are effective. In order to show this, write p(y, \overline{z}) = q(y) ∈ ℤ[\overline{z}][y] i.e., q(y) is a polynomial in y whose coefficients are polynomials in \overline{z} with integer coefficients. Then

p(f(\overline{x}), \overline{z}) > 0 ≡ sgn(q(f(\overline{x}))) = 1 .

By assumption sgn(q(f(\overline{x}))) is an effective function of \overline{x} and the cofficients of q; hence by composition sgn(q(f(\overline{x}))) is an effective function of \overline{x} and \overline{z}.

The next lemma says that the real roots of a polynomial are effective functions of the coefficients. For example, the quadratic formula

x = \frac{−b ± \sqrt{b^{2} − 4ac}}{2a}

shows that the roots of ax^{2} + bx + c are effective functions of a, b and c.

Lemma 3.1.18 (Main Lemma). Let p(x) = a_{n}x^{n} + ⋯ + a_{1}x + a_{0} ∈ ℝ[x]. Write \overline{a} = a_{0}, …, a_{n}. There are n + 1 effective functions ξ_{1}(\overline{a}), …, ξ_{n}(\overline{a}), and k = k(\overline{a}) such that

ξ_{1}(\overline{a}) < ⋯ < ξ_{k}(\overline{a})

are all of the real roots of p(x).

Proof. By induction on n. Let

p′(x) = na_{n}x^{n−1} + ⋯ + 2a_{2}x + a_{1}

be the derivative of p(x). This is of degree ≤ n−1. By inductive hypothesis, the roots of p′(x) are among t_{1} < ⋯ < t_{m}, m = n − 1, where the t_{i}’s are effective function of \overline{a}. Note that p(x) is monotone on each of the open intervals

(−∞, t_{1}) , (t_{1}, t_{2}) , …, (t_{m−1}, t_{m}) , (t_{m}, +∞)

So, in each of these intervals, there is at most one root of p(x). In addition the t_{i}’s could be roots of p(x). Thus the number of roots is determined by sgn(p(t_{i})), 1 ≤ i ≤ n − 1 and sgn(p′(t_{1} − 1)) and sgn(p′(t_{n} + 1)). We can therefore use definition by cases to obtain k(\overline{a}) as an effective function of \overline{a}.

It remains to show that the roots themselves are effective functions of \overline{a}. Consider for example a root ξ = ξ(\overline{a}) in the interval (t_{1}, t_{2}) where p(t_{1}) > 0 and p(t_{2}) < 0. By the previous lemma, it suffices to show that, for each d ≥ 1 and polynomial q(x) of degree d, sgn(q(ξ)) is effective (as a function of \overline{a} and the coefficients of q).

Replacing q(x) by its remainder on division by p(x), we may assume deg(q(x)) < n. [Details: Long division gives q(x) = p(x) · f(x) + r(x), where deg(r(x)) < n and the coefficients of r(x) are effective functions of the coefficients of p(x) and q(x). We can replace q(x) by r(x).]

By induction hypothesis, the roots of q(x) can be found effectively. Let the roots of q(x) be among u_{1} < ⋯ < u_{m}. Then the sign of q(x) on the m + 1 intervals

(−∞, u_{1}) , (u_{1}, u_{2}) , …, (u_{m−1}, u_{m}) , (u_{m}, +∞)

is given by m + 1 effective functions

sgn(q(u_{1}−1)) , sgn (q (\frac{u_{1} + u_{2}}{2} )) , …, sgn (q (\frac{u_{m−1} + u_{m}}{2} )) , sgn(q(u_{m}+1)) .

Moreover the position of ξ relative to the u_{i}’s is determined by the positions of t_{1} and t_{2} relative to the u_{i}’s and by the sgn(p(u_{i}))’s. Thus we can use definition by cases to obtain sgn(q(ξ)) as an effective function. In view of the previous lemma characterizing effective functions, this shows that ξ is an effective function. The proof of the Main Lemma is now complete.

Lemma 3.1.19. If A(x_{1}, x_{2}, …, x_{k}) is an effective predicate, then the predicate

B(x_{2}, …, x_{k}) ≡ ∃x_{1} A(x_{1}, x_{2}, …, x_{k})

is effective.

Proof. The predicate A(x_{1}, x_{2}, …, x_{k}) may be viewed as a Boolean combination of polynomial inequalities of the form p_{i}(x_{1}) > 0, 1 ≤ i ≤ l, where the coefficients of the p_{i}(x)’s are polynomials in x_{2}, …, x_{k} with integer coefficients. By the Main Lemma, the roots of the p_{i}(x)’s are effective function of x_{2}, …, x_{k}. Let ξ_{1}, …, ξ_{m} be all of these roots. Hence the p_{i}(x)’s change sign only at ξ_{1}, …, ξ_{m}. It follows that

∃x_{1} A(x_{1}, x_{2}, …, x_{k})

is equivalent to a finite disjunction

A(η_{1}, x_{2}, …, x_{k}) ∨ ⋯ ∨ A(η_{n}, x_{2}, …, x_{k}) ,

where η_{1}, …, η_{n} is a list of all the ξ_{i}’s and (ξ_{i} + ξ_{j})/2’s and ξ_{i} ± 1’s. Since the η_{i}’s are effective functions of x_{2}, …, x_{k}, it follows that the above disjunction is an effective predicate of x_{2}, …, x_{k}. This proves the lemma.

Theorem 3.1.20. Any predicate A ⊆ ℝ^{k} which is definable over R is effective.

Proof. A ⊆ ℝ^{k} is defined over R by a formula F (x_{1}, …, x_{k}) of L_{OR}. Therefore, it suffices to show that any formula F of L_{OR} is equivalent over R to a quantifierfree formula F^{∗}. We shall prove this by induction on the number of symbols in F.

If F is quantifier-free, we may take F^{∗} ≡ F.

If F ≡ ¬ G, then we may take F^{∗} ≡ ¬ G^{∗}.

If F ≡ G ∧ H, then we may take F^{∗} ≡ G^{∗} ∧ H^{∗}.

If F ≡ ∃x G, let F (\overline{y}) ≡ ∃x G(x, \overline{y}), where \overline{y} is a list of the free variables of F. By the inductive hypothesis, G(x, \overline{y}) is equivalent to a quantifier-free formula G^{∗}(x, \overline{y}). Then G^{∗}(x, \overline{y}) defines an effective predicate B(x, \overline{y}). By the previous lemma, the predicate A(\overline{y}) ≡ ∃x B(x, \overline{y}) is effective, i.e., is defined by a quantifier-free formula F^{∗}(\overline{y}). Clearly F is equivalent to F^{∗}. This completes the proof.

Corollary 3.1.21. For a predicate A ⊆ ℝ^{k} the following three conditions are equivalent:

1. A is effective.

2. A is definable over R.

3. A is definable over R by a quantifier-free formula.

Similarly for functions f : D → ℝ, D ⊆ ℝ^{k}.

Proof. For predicates this follows immediately from Theorem 3.1.20. Consider now a function f. Note first that if f is effective then the predicate y = f(\overline{x}) is effective, i.e., definable by a quantifier-free formula. Conversely, suppose that f is definable. Then for any effective predicate A(y, \overline{z}), the predicate A(f(\overline{x}), \overline{z}) is equivalent to the definable predicate ∃y (y = f(\overline{x}) ∧ A(y, \overline{z})), which is therefore effective in view of what has already been proved. Thus f is effective.

Theorem 3.1.22 (Quantifier Elimination). If a predicate A ⊆ ℝ^{k} is definable over R, then it is definable over R by a quantifier-free formula.

Proof. This is merely a restatement of the previous corollary.

Proof of Theorem 3.1.1. Theorem 3.1.1 is a restatement of the previous theorem.

3.2 Decidability of the Real Number System

Theorem 3.2.1. Given a formula F of L_{OR}, there is an algorithm to find an equivalent quantifier-free formula F^{∗}.

Proof. The algorithm can be obtained by tracing back through the proof of Theorem 3.1.22.

Theorem 3.2.2. Given a sentence S of L_{OR}, there is an algorithm to determine whether or not R satisfies S, i.e., whether S is true in the real number system.

Proof. Given a sentence S, a special case of the previous theorem is that we can algorithmically compute S^{∗}, an equivalent quantifier-free sentence. But then S^{∗} is a Boolean combination of atomic sentences of the form t_{1} = t_{2} and t_{1} < t_{2} where t_{1} and t_{2} are variable-free terms, for example 1+(0+1) < (1+1)·−(1+0), and the truth value of such sentences is easily computed. This completes the proof.

Corollary 3.2.3. The set

TrueSnt_{ℝ} = {#(S) | S is a sentence ∧ S is true in R}

is recursive.

Proof. This follows from the previous Theorem plus Church’s Thesis. Alternatively, we can convert the proof of Theorem 3.1.1 into a rigorous proof that the function taking #(F) to #(F^{∗}) is primitive recursive.

Exercise 3.2.4. Recall that ℕ = {0, 1, 2, …} = the natural numbers, ℤ = {…, −2, −1, 0, 1, 2, …} = the integers, and ℝ = (−∞, ∞) = the real numbers.

Show that TrueSnt_{ℕ} and TrueSnt_{ℤ} are not recursive. (This is in contrast to the fact that TrueSnt_{ℝ} is recursive.)

Theorem 3.2.5. The theory of the ordered ring of real numbers is decidable.

Proof. This is a restatement of the previous corollary.

Corollary 3.2.6. Plane and solid geometry are decidable.

Proof. By the methods of Cartesian analytic geometry, the theory of points, lines and circles in the plane is interpretable into the theory of the real numbers. For example, a point is an ordered pair (x, y) where x and y are real numbers. A line is an ordered quadruple (a, b, u, v) where (u, v) ≠ (0, 0). A point (x, y) lies on a line (a, b, u, v) if and only if

∃t (x = a + tu ∧ y = b + tv) .

Two lines are considered identical if and only if they contain the same points. A circle is an ordered triple (a, b, r) where r > 0. A point (x, y) lies on a circle (a, b, r) if and only if (x − a)^{2} + (y − b)^{2} = r^{2}. A triangle consists of three non-collinear points, the vertices of the triangle. Etc., etc.

Similarly for the theory of points, lines, planes, circles, and spheres in space.

Exercise 3.2.7. Write sentences of the language +, −, ·, 0, 1, <, = which, when interpreted over the real number system, express the following statements of Euclidean plane geometry.

1. For every two points, there is a unique line passing through them.

2. For every three non-collinear points, there is a unique circle passing through them.

3. For every line L and circle C, the intersection of L and C consists of at most two points.

4. Given a line L and a point P, among all points on L there is exactly one which is at minimum distance from P.

5. For every circle C and point P lying on C, there exists one and only one line L such that L ∩ C = P. (I.e., a tangent line.)

6. Every line segment has a unique midpoint.

7. Every angle can be uniquely bisected.

Exercise 3.2.8. Explain in detail how you would translate the following statements of Euclidean plane geometry into sentences of the language +, −, ·, 0, 1, < , = over the real number system.

1. The three angle bisectors of any triangle meet in a single point.

2. Every angle can be uniquely trisected.

Exercise 3.2.9. Recall that ℕ = {0, 1, 2, …} = the natural numbers, ℤ = {…, −2, −1, 0, 1, 2, …} = the integers, and ℝ = (−∞, ∞) = the real numbers. According to Matiyasevich’s Theorem, we can find a polynomial

f(w, x_{1}, …, x_{k})

with integer coefficients, such that the set of a ∈ ℕ for which the equation f(a, x_{1}, …, x_{k}) = 0 has a solution in ℕ is noncomputable.

1. Discuss the analogous question in which “solution in ℕ” is replaced by “solution in ℤ”.

2. Discuss analogous questions in which “solution in ℕ” is replaced by “solution in ℝ”.

Informal Set Theory

The purpose of this chapter is to develop set theory in an informal, preaxiomatic way. A good reference for this material is Naïve Set Theory by P. R. Halmos.

4.1 Operations on Sets

Informally, a set is any collection of objects which may be regarded as a completed totality. We use capital letters X, Y, … to denote sets. If a is any object and X is any set, we write a ∈ X to mean that a belongs to X, and a ∉ X to mean that a does not belong to X. Synonyms for “belongs to” are “is an element of”, “is a member of”, and “is contained in”.

Since a set is nothing but a collection of elements, the set itself having no further structure, it follows that two sets are equal if and only if they contain exactly the same elements. Symbolically,

X = Y ⇔ ∀a (a ∈ X ⇔ a ∈ Y) .

This is known as the principle of extensionality. It can be taken as a definition of equality between sets.

If P (a) is any definite property that an object a may or may not have, we use the notation {a | P (a)} to denote the set of all objects a which have property P, if such a set exists. (If such a set exists, it will be unique in view of extensionality.)

In order to be a set, a collection of objects must be limited in size and definite. These requirements are rather vague, but we shall try to give some explanation of what they entail. Definiteness means that any object a either belongs or does not belong to the collection, i.e., there is no third possibility. Limitedness means that the collection is in some sense not too large. The need for some limitation-of-size requirement will be shown below in connection with the Russell paradox.

One of the most basic concepts in set theory is that of one set being included in another. We say that Y is a subset of X, symbolically Y ⊆ X, if every element of Y is an element of X, i.e.,

∀a (a ∈ Y ⇒ a ∈ X) .

If P (a) is any definite property as above, and if X is any set, we can form a subset Y = {a ∈ X | P (a)}, consisting of all elements a of X which have property P. Thus

∀a(a ∈ Y ⇔ (a ∈ X ∧ P (a))) .

Note that any set X is itself a mathematical object and as such can be an element of another set. Indeed, given a set X, we can form a set

P(X) = {Y | Y ⊆ X} ,

called the power set of X, whose elements are all possible subsets of X.

We now prove a theorem which implies that not all definite collections of mathematical objects are sets. This means that some limitation-of-size principle is needed.

Theorem 4.1.1 (Russell Paradox). The collection of all sets is not itself a set.

Proof. Suppose to the contrary that there were a set S consisting of all sets. Form the subset D consisting of all sets which are not members of themselves. Symbolically,

D = {X ∈ S | X ∉ X} .

Then D ∈ D if and only if D ∉ D, a contradiction. This completes the proof.

The Russell Paradox shows that we cannot form sets with complete freedom. Nevertheless, a wide variety of sets can be formed. Some examples of sets are ∅ (the empty set, i.e., the unique set which has no elements), {∅} (the one-element set whose unique element is the empty set), {∅, {∅}}, etc. For any objects a, b, and c, we can form the set {a, b, c} whose elements are exactly a, b, and c. The cardinality of this set will be one, two or three depending on which of a, b, and c are equal to each other. Some examples of infinite sets are ℕ (the set of natural numbers), ℝ (the set of real numbers), P(ℕ), P(ℝ), P(P(ℝ)), etc. Another source of examples is subsets defined by properties, for example {n ∈ ℕ | n is prime} and {X ⊆ ℝ | X is countably infinite}. Further sets can be obtained using the set operations discussed below.

Given two objects a and b, there is an object (a, b) called the ordered pair of a and b. The ordered pair operation is assumed to have the following property:

(a, b) = (a′, b′) ⇔ (a = a′ ∧ b = b′) .

Given two sets X and Y, the Cartesian product X × Y is the set of all ordered pairs (a, b) such that a ∈ X and b ∈ Y.

For any set X, a function with domain X is a rule f associating to each object a ∈ X a definite, unique object f(a). In this case we write dom(f) = X and rng(f) = {f(a) | a ∈ X}. The latter is again a set, called the range of F.

If f is a function and Z is a set, there is a unique function f↾Z, the restriction of f to Z, whose domain is dom(f) ∩ Z and such that (f↾Z)(a) = f(a) for all a in its domain.

We write f : X → Y to mean that f is a function, dom(f) = X, and rng(f) ⊆ Y. The set of all such functions is denoted Y^{X}.

Summarizing some of the above points, we have the following binary operations on sets:

X ∪ Y = {a | a ∈ X ∨ a ∈ Y }  (union) ,
X ∩ Y = {a | a ∈ X ∧ a ∈ Y }  (intersection) ,
X \ Y = {a | a ∈ X ∧ a ∉ Y }  (difference) ,
X × Y = {(a, b) | a ∈ X ∧ b ∈ Y }  (product) ,
X^{Y}  = {f | f : Y → X}  (exponential) .

By an indexed collection with index set I, we mean simply a function f whose domain is I. In discussing indexed collections, we use notation such as f = ⟨a_{i}⟩_{i∈I} where a_{i} = f(i). For example, an ordered n-tuple ⟨a_{1}, …, a_{n}⟩ is a function whose domain is {1, …, n}, and a sequence ⟨a_{n}⟩_{n∈ℕ} is a function whose domain is ℕ.

Given an indexed collection of sets ⟨X_{i}⟩_{i∈I}, the following operations are defined.

⋃_{i∈I} X_{i} = {a | ∃i ∈ I (a ∈ X_{i})}  (union) ,
⋂_{i∈I} X_{i} = {a | ∀i ∈ I (a ∈ X_{i})}  (intersection) ,
∏_{i∈I} X_{i} = {⟨a_{i}⟩_{i∈I} | ∀i ∈ I (a_{i} ∈ X_{i})}  (product) .

If in the latter operation we take all of the sets X_{i} to be the same set X, we get the Cartesian power

∏_{i∈I} X = X^{I}

which is the same as the previously mentioned exponential.

The Axiom of Choice is the assertion that, for any indexed collection of sets ⟨X_{i}⟩_{i∈I}, if ∀i ∈ I (X_{i} ≠ ∅) then ∏_{i∈I} X_{i} ≠ ∅. This implies that it is possible to choose one element a_{i} ∈ X_{i} for each i ∈ I. In the early years of set theory, there was some controversy about the Axiom of Choice. Nowadays the Axiom of Choice is accepted as being intuitively obvious, but we shall follow the custom of indicating which proofs use it.

4.2 Cardinal Numbers

A function f is said to be one-to-one if for all a, a′ ∈ dom(f), a ≠ a′ implies f(a) ≠ f(a′). Note that in this case there is an inverse function f^{−1} with dom(f^{−1}) = rng(f) and rng(f^{−1}) = dom(f), defined by

f^{−1}(b) = a ⇔ f(a) = b .

Definition 4.2.1. If X and Y are sets, we say X is equinumerous with Y, written X ≈ Y, if there exists a one-to-one correspondence between X and Y, i.e., a one-to-one function f with dom(f) = X and rng(f) = Y. Lemma 4.2.2.

1. X ≈ X.

2. X ≈ Y if and only if Y ≈ X.

3. X ≈ Y and Y ≈ Z imply X ≈ Z. Proof. Straightforward.

Because of the preceding lemma, we can associate to any set X an object card(X), the cardinality or cardinal number of X, in such a way that

X ≈ Y ⇔ card(X) = card(Y) .

If X is finite, we take card(X) to be the number of elements in X. For infinite sets X, it is not important at this stage what sort of object the cardinal number card(X) is, so long as the above property holds. We use Greek letters κ, λ, μ, ν, … to denote cardinal numbers. Definition 4.2.3. We write X ≼ Y to mean that X ≈ X_{1} for some X_{1} ⊆ Y. Lemma 4.2.4.

1. If X ≈ X′ and Y ≈ Y′, then X ≼ Y if and only if X′ ≼ Y′.

2. X ≼ X.

3. X ≼ Y and Y ≼ Z imply X ≼ Z.

4. X ≼ Y and Y ≼ X imply X ≈ Y.

5. For all sets X and Y, either X ≼ Y or Y ≼ X. Proof. Parts 1, 2, and 3 are straightforward. Parts 4 and 5 will be proved later, as consequences of the Well-Ordering Theorem. Part 4 is known as the Cantor-Schroeder-Bernstein Theorem.

We can now make the following definition for cardinal numbers: κ ≤ λ if and only if X ≼ Y where κ = card(X) and λ = card(Y). This does not depend on the choice of X and Y, as noted in part 1 of Lemma 4.2.4. The rest of Lemma 4.2.4 implies that ≤ is a linear ordering of the cardinal numbers, i.e., we have:

1. κ ≤ κ.

2. (κ ≤ λ ∧ λ ≤ μ) ⇒ κ ≤ μ.

3. (κ ≤ λ ∧ λ ≤ κ) ⇒ κ = λ.

4. ∀κ ∀λ (κ ≤ λ ∨ λ ≤ κ). Definition 4.2.5 (Cardinal Arithmetic). For cardinal numbers κ = card(X) and λ = card(Y), we define

1. κ + λ = card(X ∪ Y).

2. κ · λ = card(X × Y).

3. κ^{λ} = card(X^{Y}). (In the definition of κ + λ, it is assumed that X ∩ Y = ∅.)

For example, 2^{κ} = card(P(X)) where κ = card(X). Theorem 4.2.6. For cardinal numbers κ, λ, and μ, we have

1. κ + λ = λ + κ.

2. (κ + λ) + μ = κ + (λ + μ).

3. κ · λ = λ · κ.

4. (κ · λ) · μ = κ · (λ · μ).

5. κ · (λ + μ) = κ · λ + κ · μ.

6. κ^{λ+μ} = κ^{λ} · κ^{μ}.

7. κ^{λ·μ} = (κ^{λ})^{μ}.

8. κ + 0 = κ, κ · 0 = 0, κ · 1 = κ. Proof. Straightforward.

Later we shall prove that, for infinite cardinal numbers κ and λ,

κ + λ = κ · λ = max(κ, λ) .

Theorem 4.2.7 (Cantor’s Theorem). For any cardinal number κ, we have 2^{κ} > κ. In other words, for any set X, we have X ≼ P(X) and P(X) ⋠ X. Proof. We have X ≼ P(X) via the one-to-one function f : X → P(X) where f(a) = {a}. Suppose now that P(X) ≼ X holds. Let g : P(X) → X be one-to-one. Put

D = {a ∈ X | a ∈ rng(g) ∧ a ∉ g^{−1}(a)} .

Then g(D) ∈ D if and only if g(D) ∉ D, a contradiction.

Exercise 4.2.8. Define ℵ_{0} = card(ℕ). Without using the Cantor-Schroeder-Bernstein Theorem, prove that

ℵ_{0} = card(ℤ) = card(ℚ)

and

2^{ℵ_{0}} = card(ℝ) = card(ℂ) = card([0, 1]) = card([0, 1] × [0, 1]).

Definition 4.2.9. If ⟨κ_{i}⟩_{i∈I} is an indexed set of cardinal numbers, we define

1. ∑_{i∈I} κ_{i} = card(⋃_{i∈I} X_{i})

2. ∏_{i∈I} κ_{i} = card(∏_{i∈I} X_{i})

where κ_{i} = card(X_{i}). In the definition of ∑_{i∈I} κ_{i}, it is assumed that X_{i}∩X_{j} = ∅ for all i, j ∈ I with i ≠ j.

Exercise 4.2.10 (König’s Theorem). Suppose that ⟨κ_{i}⟩_{i∈I} and ⟨λ_{i}⟩_{i∈I} are indexed sets of cardinal numbers with the same index set I. Show that if κ_{i} < λ_{i} for all i ∈ I, then

∑_{i∈I} κ_{i} < ∏_{i∈I} λ_{i} .

Remark 4.2.11. Cantor’s Theorem may be viewed as the special case of König’s Theorem with κ_{i} = 1 and λ_{i} = 2. The Axiom of Choice may be viewed as the special case of König’s Theorem with κ_{i} = 0 and λ_{i} > 0.

4.3 Well-Orderings and Ordinal Numbers

Definition 4.3.1. Given a set A, a relation on A is a set R ⊆ A × A. A relational structure is an ordered pair (A, R) where A is a set and R ⊆ A × A. We sometimes write aRa′ instead of (a, a′) ∈ R.

Definition 4.3.2. Given two relational structures (A, R) and (B, S), an isomorphism from (A, R) to (B, S) is a one-to-one function f such that dom(f) = A, rng(f) = B, and

aRa′ ⇔ f(a)Sf(a′)

for all a, a′ ∈ A. We say that (A, R) is isomorphic to (B, S), symbolically (A, R) ≅ (B, S), if there exists an isomorphism from (A, R) to (B, S).

Lemma 4.3.3.

1. (A, R) ≅ (A, R).

2. (A, R) ≅ (B, S) if and only if (B, S) ≅ (A, R).

3. (A, R) ≅ (B, S) and (B, S) ≅ (C, T) imply (A, R) ≅ (C, T).

Proof. Straightforward.

Because of the preceding lemma, we can associate to any relational structure (A, R) a mathematical object type(A, R), the isomorphism type of (A, R), in such a way that

(A, R) ≅ (B, S) ⇔ type(A, R) = type(B, S) .

It is not important at this stage exactly what sort of mathematical object type(A, R) is, so long as the above property holds.

Definition 4.3.4. A relational structure (A, R) is said to be well-founded if for every nonempty set X ⊆ A, there exists a ∈ X such that there is no b ∈ X with bRa. Such an a might be called an R-minimal element of X.

Lemma 4.3.5. A relational structure (A, R) is well-founded if and only if there is no infinite descending R-sequence. (By an infinite descending R-sequence we mean a sequence ⟨a_{n}⟩_{n∈ℕ} such that a_{n+1}Ra_{n} for all n ∈ ℕ.)

Proof. If ⟨a_{n}⟩_{n∈ℕ} is an infinite descending R-sequence, then X = {a_{n} | n ∈ ℕ} is a counterexample to well-foundedness of (A, R). Conversely, suppose that X ⊆ A is a counterexample to well-foundedness. Then we have X ≠ ∅ and ∀a ∈ X ∃b ∈ X bRa. By the Axiom of Choice, there is a function f : X → X such that f(a)Ra for all a ∈ X. Pick an element a_{0} ∈ X and define ⟨a_{n}⟩_{n∈ℕ} recursively by putting a_{n+1} = f(a_{n}) for all n ∈ ℕ. This is an infinite descending R-sequence. The lemma is proved.

Definition 4.3.6. A linear ordering is a relational structure (A, R) with the following properties: aRb and bRc imply aRc; and for all a, b ∈ A exactly one of aRb, a = b, bRa hold. A well-ordering is a linear ordering which is well-founded.

Note that if (A, R) is a well-ordering and X is a nonempty subset of A, then X has an R-least element, i.e., there is a unique a ∈ X such that aRb holds for all b ∈ X, b ≠ a.

Definition 4.3.7. An ordinal number is the isomorphism type of a well-ordering.

For n ∈ ℕ, we identify n with the ordinal number which is the order type of all n-element well-orderings. Another important ordinal number is ω, the order type of ℕ itself (more precisely of (ℕ, <) = (ℕ, {(m, n) ∈ ℕ × ℕ | m < n})). The following definition and exercise show how to generate further examples of ordinal numbers.

Definition 4.3.8. Let α = type(A, R) and β = type(B, S) be ordinal numbers. We define

1. α + β = type(A ∪ B, R ∪ S ∪ (A × B)). Here we assume that A ∩ B = ∅.

2. α · β = type(A × B, {((a, b), (a′, b′)) | bSb′ ∨ (b = b′ ∧ aRa′)}).

Thus we have operations of ordinal addition, α + β, and ordinal multiplication, α · β. (Later we shall define an analogous operation of ordinal exponentiation, α^{β}.) Note that the commutative laws fail, for example 1 + ω = ω ≠ ω + 1 and 2 · ω = ω ≠ ω · 2 = ω + ω. However, we have the following properties.

Exercise 4.3.9. Prove the following laws of ordinal arithmetic.

1. (α + β) + γ = α + (β + γ).

2. (α · β) · γ = α · (β · γ).

3. α · (β + γ) = α · β + α · γ.

4. α + 0 = 0 + α = α, α · 0 = 0 · α = 0, α · 1 = 1 · α = α.

Give an example showing the failure of (α + β) · γ = α · γ + β · γ.

Definition 4.3.10. If (A, R) is a linear ordering, an initial segment of (A, R) is any subset of A of the form {b | bRa}, where a ∈ A. Note that

({b | bRa}, {(c, b) | cRb ∧ bRa})

is again a linear ordering, and we sometimes identify the initial segment with this ordering.

Theorem 4.3.11 (Comparability of Well-Orderings). Let (A, R) and (B, S) be well-orderings. Then exactly one of the following holds.

1. (A, R) ≅ (B, S);

2. (A, R) ≅ some initial segment of (B, S);

3. (B, S) ≅ some initial segment of (A, R).

Moreover, in each case, the isomorphism is unique.

Proof. We first prove that the isomorphism is unique. Suppose for instance that f_{1} and f_{2} are two different isomorphisms from (A, R) to (B, S) or to some initial segment of (B, S). Then {a ∈ A | f_{1}(a) ≠ f_{2}(a)} is a nonempty subset of A, so let a be its R-least element. Then f_{1}(a′) = f_{2}(a′) for all a′Ra but f_{1}(a) ≠ f_{2}(a), say f_{1}(a)Sf_{2}(a). Then f_{1}(a) ∉ rng(f_{2}), contradicting the fact that rng(f_{2}) is B or an initial segment of B with respect to S.

Now let f be a function with dom(f) ⊆ A and rng(f) ⊆ B, defined by putting f(a) = the unique b ∈ B such that

({a′ | a′Ra}, {(a′′, a′) | a′′Ra′ ∧ a′Ra}) ≅ ({b′ | b′Sb}, {(b′′, b′) | b′′Sb′ ∧ b′Sb}) ,

provided such a b exists. If for a given a ∈ A no such b exists, f(a) is undefined. If b exists, its uniqueness follows from what we have already proved. It is clear that a′Ra and a ∈ dom(f) imply a′ ∈ dom(f), and b′Rb and b ∈ rng(f) imply b′ ∈ rng(f).

We claim that dom(f) = A or rng(f) = B or both. If not, let a be the R-least element of A \ dom(f), and let b be the S-least element of B \ rng(f). Then f is an isomorphism from ({a′ | a′Ra}, {(a′′, a′) | a′′Ra′ ∧ a′Ra}) to ({b′ | b′Sb}, {(b′′, b′) | b′′Sb′ ∧ b′Sb}). This implies that a ∈ dom(f), a contradiction. The claim is proved.

If both dom(f) = A and rng(f) = B, then we have (A, R) ≅ (B, S). If dom(f) ≠ A, then letting a be the R-least element of A \ dom(f), we see that f is an isomorphism from ({a′ | a′Ra}, {(a′′, a′) | a′′Ra′ ∧ a′Ra}) to (B, S). If rng(f) ≠ B, then letting b be the S-least element of B \ rng(f), we see that f is an isomorphism from (A, R) to ({b′ | b′Sb}, {(b′′, b′) | b′′Sb′ ∧ b′Sb}). This completes the proof of the theorem.

Definition 4.3.12. For ordinal numbers α and β, we define α < β to mean that (A, R) ≅ some initial segment of (B, S), where α = type(A, R) and β = type(B, S). We define α ≤ β to mean α < β ∨ α = β.

Lemma 4.3.13. For all ordinal numbers α and β, exactly one of α < β, α = β, and β < α holds. Moreover α < β and β < γ imply α < γ.

Proof. The first part follows from comparability of well-orderings. The second part is straightforward.

Exercise 4.3.14. For ordinal numbers α, β, γ, prove that α < β if and only if α + γ = β for some γ > 0.

Lemma 4.3.15. If (A, R) is a well-ordering and B ⊆ A, then (B, R ∩ (B × B)) is a well-ordering, and

type(B, R ∩ (B × B)) ≤ type(A, R) .

Proof. Straightforward, using comparability of well-orderings.

The next theorem implies that any well-ordering is isomorphic to an initial segment of the ordinal numbers.

Theorem 4.3.16. For any ordinal number α, the relational structure

({β | β < α}, {(γ, β) | γ < β < α})

is a well-ordering of type α.

Proof. Let (A, R) be some fixed well-ordering of type α. Define f : A → {β | β < α} by

f(b) = type({c ∈ A | cRb}, {(d, c) | dRc ∧ cRb}) .

It is straightforward to verify that f is an isomorphism from (A, R) onto

({β | β < α}, {(γ, β) | γ < β < α}) .

This proves the theorem.

Corollary 4.3.17. For any ordinal number α, there is a set {β | β < α} consisting of all smaller ordinal numbers.

Proof. This follows from the previous theorem.

Lemma 4.3.18. Let X be a set of ordinal numbers. Then there is an ordinal number γ = sup X which is the least upper bound of X under <, i.e., ∀α (α ∈ X ⇒ α ≤ γ) and ∀β (β < γ ⇒ ∃α (α ∈ X ∧ β < α)).

Proof. Put

A = {α | ∃β (β ∈ X ∧ α < β)} = ⋃_{β∈X}{α | α < β} .

It is straightforward to verify that

(A, {(α, β) ∈ A × A | α < β})

is a well-ordering. Let γ be the type of this well-ordering. It is straightforward to verify that A = {α | α < γ} and that γ = sup X.

Exercise 4.3.19. If α is an ordinal number and X is a nonempty set of ordinal numbers, show that α + sup X = sup{α + β | β ∈ X} and α · sup X = sup{α · β | β ∈ X}.

Lemma 4.3.20. Let X be a nonempty set of ordinal numbers. Then X has a smallest element under <.

Proof. Put α = sup X. Then X is a nonempty subset of {β | β ≤ α}. The latter set of ordinal numbers is well-ordered under <, hence X has a least element.

Theorem 4.3.21 (Burali-Forti Paradox). The class Ord of all ordinal numbers is not a set.

Proof. If Ord were a set, then by the above lemmas, (Ord, <) would be a wellordering. Letting α be the type of this well-ordering, we see that (Ord, <) would be isomorphic to an initial segment of itself, namely ({β | β < α}, {(γ, β) | γ < β < α}). This contradiction completes the proof.

4.4 Transfinite Recursion

By a class we mean a collection of objects which is not necessarily a set. Every set is a class, but not every class is a set. Examples of classes which are not sets are Set = {X | X is a set} and Ord = {α | α is an ordinal}. These classes are “too big” to be sets. We have seen this in connection with the Russell Paradox and the Burali-Forti Paradox.

If C is a class, then by a function with domain C we mean a rule F which associates to each element a of C a uniquely defined object F (a). For example, although the class Ord of all ordinal numbers is not a set, we shall be interested in functions with domain Ord. The next theorem gives us a powerful method for defining such functions.

Theorem 4.4.1 (Transfinite Recursion). Let F be the class of all functions whose domain is an initial segment of Ord. Suppose that G is a function with domain F. Then there is a unique function F with domain Ord such that, for all ordinal numbers α,

F (α) = G(F ↾{β | β < α}) .

Proof. Let us say that f ∈ F is good if for all β ∈ dom(f), f(β) = G(f↾{γ | γ < β}). We claim that for all ordinal numbers α, there is at most one good f with dom(f) = {β | β < α}. If not, let f_{1} ≠ f_{2} be two such f’s. Let γ be the smallest β < α such that f_{1}(β) ≠ f_{2}(β). Then f_{1}↾{β | β < γ} = f_{2}↾{β | β < γ}, hence

f_{1}(γ) = G(f_{1}↾{β | β < γ}) = G(f_{2}↾{β | β < γ}) = f_{2}(γ) ,

a contradiction.

Using the above claim, let f_{α} be the unique good f with dom(f) = {β | β < α}, if it exists. We claim that f_{α} exists for all α. If not, let α be the smallest counterexample. Then f_{β} exists for all β < α, and it is easy to check that {(β, G(f_{β})) | β < α} is good. This contradicts the choice of α. Thus f_{α} exists for all α. Define F by putting F (α) = G(f_{α}) for all α. It is easy to check that F ↾{β | β < α} = f_{α} and that F satisfies the desired conclusions. This completes the proof.

As an example of transfinite recursion, we define the following operations of ordinal arithmetic.

Definition 4.4.2.

1. α + β = sup{α, (α + γ) + 1 | γ < β}.

2. α · β = sup{(α · γ) + α | γ < β}.

3. α^{β} = sup{1, α^{γ} · α | γ < β} (assuming α > 0).

Exercise 4.4.3. Show that parts 1 and 2 of Definition 4.4.2 agree with parts 1 and 2 of Definition 4.3.8. In the next exercise we show how to extend Definition 4.3.8 to encompass part 3 of Definition 4.4.2.

Exercise 4.4.4. Let α = type(A, R) and β = type(B, S) be ordinal numbers. Show that α^{β} = type(C, T) where C is the set of all f : B → A such that, for all but finitely many b ∈ B, f(b) = a_{0}, where a_{0} is the R-least element of A. Here T is the set of all (f_{1}, f_{2}) ∈ C × C such that f_{1}(b′)Rf_{2}(b′), where b′ is the S-greatest b ∈ B such that f_{1}(b) ≠ f_{2}(b).

Exercise 4.4.5. If α is an ordinal number and X is a nonempty set of ordinal numbers, show that

1. α + sup X = sup{α + β | β ∈ X}, 2. α · sup X = sup{α · β | β ∈ X}, and

3. α^{sup X} = sup{α^{β} | β ∈ X}. Exercise 4.4.6. For ordinal numbers α, β, and γ, show that

1. (α + β) + γ = α + (β + γ).

2. (α · β) · γ = α · (β · γ).

3. α · (β + γ) = α · β + α · γ.

4. α^{β+γ} = α^{β} · α^{γ}.

5. α^{β·γ} = (α^{β})^{γ}.

6. α + 0 = 0 + α = α, α · 0 = 0 · α = 0, α · 1 = 1 · α = α.

7. α^{0} = 1.

8. 0^{α} = 0 provided α > 0.

9. α^{1} = α, 1^{α} = 1. Exercise 4.4.7. Show that β < γ implies the following:

1. α + β < α + γ;

2. α · β < α · γ provided α > 0;

3. α^{β} < α^{γ} provided α > 1. Definition 4.4.8. A successor ordinal is an ordinal number of the form α + 1. A limit ordinal is an ordinal number δ such that δ > 0 and α + 1 < δ for all α < δ. Examples of limit ordinals are ω and ω · 2. Exercise 4.4.9. Show that α + 1 is the smallest ordinal number β > α. Show that every ordinal number is either 0, a successor ordinal, or a limit ordinal. Show that δ > 0 is a limit ordinal if and only if δ = sup{α | α < δ}. Show that δ > 0 is a limit ordinal if and only if δ = ω · α for some α > 0. Exercise 4.4.10. Show that the operations of ordinal arithmetic could have been defined by transfinite recursion as follows (letting δ denote a limit ordinal):

1. α + 0 = α, α + (β + 1) = (α + β) + 1, α + δ = sup{α + β | β < δ}.

2. α · 0 = 0, α · (β + 1) = (α · β) + α, α · δ = sup{α · β | β < δ}.

3. α^{0} = 1, α^{β+1} = (α^{β}) · α, α^{δ} = sup{α^{β} | β < δ} (assuming α > 0).

Exercise 4.4.11. For an ordinal number δ > 0, show that the following are equivalent.

1. α + δ = δ for all α < δ.

2. α + β < δ for all α, β < δ.

3. δ = ω^{α} for some α ≤ δ.

An ordinal number with these properties is said to be additively indecomposable.

Exercise 4.4.12. Show that for any ordinal number α, there is one and only one way to write α in the form α = α_{1} + ⋯ + α_{n} where α_{1} ≥ ⋯ ≥ α_{n} > 0 are additively indecomposable, and n ∈ ℕ.

4.5 Cardinal Numbers, Continued

Lemma 4.5.1. Given a set X, there exists a choice function for X, i.e., a function

c : P(X) \ {∅} → X

such that c(Y) ∈ Y for all Y ⊆ X, Y ≠ ∅.

Proof. Consider the indexed set of sets ⟨X_{i}⟩_{i∈I}, where I = P(X) \ {∅} and X_{i} = i for all i ∈ I. By the Axiom of Choice, ∏_{i∈I} X_{i} is nonempty, i.e., there exists ⟨a_{i}⟩_{i∈I} such that a_{i} ∈ X_{i} for all i ∈ I. Putting c(i) = a_{i} we obtain our choice function.

Theorem 4.5.2 (Well-Ordering Theorem). Given a set X, we can find a relation R ⊆ X × X such that (X, R) is a well-ordering.

Proof. We shall prove the theorem in the following equivalent formulation: For any set X, there exists an ordinal number α such that X ≈ {β | β < α}. (Neither α nor the one-to-one function from X onto {β | β < α} is asserted to be unique.)

Fix a choice function c for X. Fix an object a_{0} such that a_{0} ∉ X. By transfinite recursion, define

F (α) = \{ \begin{matrix}c(X \ rng(F ↾\{β | β < α\})), & if X \ rng(F ↾\{β | β < α\}) ≠ ∅ \\ a_{0} & otherwise. \end{matrix}

We claim that F (α) = a_{0} for some α. If not, we would have F (α) ∈ X for all α, and F (α) ≠ F (β) for all α ≠ β. Form the set

Y = rng(F) = {a ∈ X | ∃α(F (α) = a)} .

Then F^{−1} is a function with domain Y, and we have rng(F^{−1}) = Ord, hence Ord is a set. This contradiction proves the claim.

Let α be the smallest ordinal number such that F (α) = a_{0}. Then F ↾{β | β < α} is one-to-one, and rng(F ↾{β | β < α}) = X. Thus {β | β < α} ≈ X. Our theorem is proved.

Remark 4.5.3. The previous theorem shows that the Axiom of Choice implies the Well-Ordering Theorem. There is also a converse: the Well-Ordering Theorem implies the Axiom of Choice. To see this, suppose we have an indexed set of nonempty sets ⟨X_{i}⟩_{i∈I}. Put A = ⋃_{i∈I} X_{i}. By the Well-Ordering Theorem, there exists R ⊆ A × A such that (A, R) is a well-ordering. Define ⟨a_{i}⟩_{i∈I} by putting a_{i} = the R-least element of X_{i}. Thus ⟨a_{i}⟩_{i∈I} ∈ ∏_{i∈I} X_{i} and we have proved the Axiom of Choice from the Well-Ordering theorem.

Exercise 4.5.4. Let X be a set of sets. By a chain within X we mean a set C ⊆ X such that for all U, V ∈ C either U ⊆ V or V ⊆ U. A chain within X is said to be maximal if it is not properly included in any other chain within X.

Use the Axiom of Choice plus transfinite recursion to prove that there exists a maximal chain within X.

Note: This is a version of Zorn’s Lemma.

Definition 4.5.5. An initial ordinal is an ordinal number α such that, for all β < α,

{γ | γ < α} ≉ {γ | γ < β} .

The finite ordinal numbers 0, 1, 2, … are initial ordinals, as is the first infinite ordinal number ω. But it is easy to see that ordinal numbers such as ω + 1, ω + 2, …, ω · 2, ω · 2 + 1, … are not initial ordinals. Another simple fact worth noting is that every infinite initial ordinal is a limit ordinal.

Definition 4.5.6. For any set X, we define |X| to be the smallest ordinal number α such that X ≈ {β | β < α}. (The existence of such an ordinal is a consequence of the Well-Ordering Theorem.) Clearly |X| is an initial ordinal. In fact, |X| is the unique initial ordinal such that X ≈ {β | β < α}.

Lemma 4.5.7. If X ⊆ {β | β < α}, then |X| ≤ α.

Proof. Immediate from Lemma 4.3.15.

Theorem 4.5.8. For all sets X and Y we have

X ≈ Y if and only if |X| = |Y | ,

and

X ≼ Y if and only if |X| ≤ |Y | .

Proof. The first equivalence is obvious, as is the fact that |X| ≤ |Y | implies X ≼ Y. Suppose now that X ≼ Y. Then X ≈ Z for some Z ⊆ {β | β < |Y |}. By the previous lemma it follows that |X| = |Z| ≤ |Y |. This completes the proof.

Remark 4.5.9. By the previous theorem, we have card(X) = card(Y) if and only if |X| = |Y |, and card(X) < card(Y) if and only if |X| < |Y |. Thus we may identify cardinal numbers with initial ordinals. From now on we shall make this identification, writing card(X) = |X|. For instance, the finite cardinal numbers are now identified with the finite ordinal numbers, and the smallest infinite cardinal number is the same as the ordinal number ω.

Theorem 4.5.10.

1. If X ≼ Y and Y ≼ X, then X ≈ Y.

2. For all sets X and Y, either X ≼ Y or Y ≼ X.

Proof. Both parts follow from the previous theorem plus the fact that |X| and |Y | are ordinal numbers, hence exactly one of |X| < |Y |, |X| = |Y |, |Y | < |X| holds.

4.6 Cardinal Arithmetic

We now present some basic results about the arithmetic of infinite cardinal numbers. Most of these results are easy consequences of the following lemma.

Lemma 4.6.1. For infinite cardinals κ, we have κ · κ = κ.

Proof. If not, let κ be the smallest counterexample. Note that κ is an infinite initial ordinal, and λ · λ < κ for all λ < κ.

Put A = {α | α < κ} and R = {(α′, α) | α′ < α < κ}. Thus (A, R) is a well-ordering of type κ. Note that |A| = κ but every initial segment I of (A, R) has |I| < κ.

Put B = A × A and define S ⊆ B × B by

(α′, β′)S(α, β) if and only if
max(α′, β′) < max(α, β) ∨
(max(α′, β′) = max(α, β) ∧ α′ < α) ∨
(max(α′, β′) = max(α, β) ∧ α′ = α ∧ β′ < β) .

It is straightforward to verify that (B, S) is a well-ordering.

If J ⊆ B is any initial segment of (B, S), we have J ⊆ I × I where I is an appropriately chosen initial segment of (A, R). Thus every initial segment of (B, S) has cardinality < κ. Hence (A, R) cannot be isomorphic to an initial segment of (B, S). From comparability of well-orderings, it follows that (B, S) is isomorphic to (A, R). In particular B ≈ A. In other words, A × A ≈ A, hence κ · κ = κ. This completes the proof.

Theorem 4.6.2. For infinite cardinals κ and λ, we have

κ + λ = κ · λ = max(κ, λ) .

Proof. Put μ = max(κ, λ). Then by the previous lemma we have

μ ≤ κ + λ ≤ μ + μ = 2 · μ ≤ μ · μ = μ

and

μ ≤ κ · λ ≤ μ · μ = μ .

This proves the theorem.

Theorem 4.6.3. For λ infinite and 2 ≤ κ ≤ 2^{λ}, we have κ^{λ} = 2^{λ}.

Proof. 2^{λ} ≤ κ^{λ} ≤ (2^{λ})^{λ} = 2^{λ·λ} = 2^{λ}.

For any set X, let X^{∗} be the set of finite sequences of elements of X, i.e.,

X^{∗} = {⟨a_{i}⟩_{i<n} | n < ω, a_{i} ∈ X for all i < n} .

Theorem 4.6.4. For any infinite set X, we have |X^{∗}| = |X|.

Proof. Putting κ = |X|, we have κ^{2} = κ · κ = κ and it is easy to prove by induction on n that κ^{n} = κ for all n ≥ 1, n < ω. Hence we have

|X^{∗}| = ∑_{n<ω} κ^{n} = ω · κ = κ .

This proves the theorem.

Definition 4.6.5. For any ordinal β we define β^{+} = the smallest initial ordinal κ > β. To each ordinal number α we associate an infinite initial ordinal ω_{α} as follows, by transfinite recursion:

1. ω_{0} = ω,

2. ω_{α+1} = ω_{α}^{+},

3. ω_{δ} = sup_{α<δ} ω_{α} for limit ordinals δ.

Remark 4.6.6. It is easy to see that ⟨ω_{α}⟩_{α∈Ord} is a strictly increasing enumeration of all the infinite initial ordinals, i.e., the infinite cardinals. It follows that the class Card = {κ | κ is an infinite cardinal} is not a set.

Exercise 4.6.7. Prove that there exist arbitrarily large ordinals α such that α = ω_{α}.

Remark 4.6.8. Although cardinals are now the same thing as initial ordinals, the notation ℵ_{α} = ω_{α} is sometimes used in order to maintain a notational distinction between cardinals and initial ordinals. ℵ_{α} is taken to be a cardinal, while ω_{α} is an initial ordinal. For example, even though ℵ_{0} is the same thing as ω, ℵ_{0} is thought of as the cardinality of the set of natural numbers, while ω is thought of as the order type of the natural numbers under <.

Theorem 4.6.9. Let ℕ, ℚ, and ℝ be the set of natural numbers, the rational numbers, and the real numbers respectively. The cardinalities of these sets are given by |ℕ| = |ℚ| = ℵ_{0}, |ℝ| = 2^{ℵ_{0}}.

Proof. The fact that |ℕ| = ℵ_{0} is obvious. Since ℕ ⊆ ℚ and each rational number q ∈ ℚ is of the form q = ±m/n for some (m, n) ∈ ℕ × ℕ, we have

|ℕ| ≤ |ℚ| ≤ 2 · |ℕ| · |ℕ| = |ℕ|

so |ℚ| = |ℕ| = ℵ_{0}. For the real numbers, note first that P(ℕ) ≼ ℝ via the function which sends X ⊆ ℕ to ∑_{n∈X} 2/3^{n}. Hence 2^{ℵ_{0}} ≤ |ℝ|. On the other hand, ℝ ≼ P(ℚ) ≈ P(ℕ) via the function which sends x ∈ ℝ to {q ∈ ℚ | q < x}. Thus |ℝ| = 2^{ℵ_{0}}.

Exercise 4.6.10. Prove that |ℝ^{ℕ}| = 2^{ℵ_{0}} and |ℝ^{ℝ}| = 2^{2^{ℵ_{0}}} .

The most important problem of infinite cardinal arithmetic is the Continuum Problem: What is the cardinality of ℝ? Equivalently, what is the ordinal number β such that 2^{ℵ_{0}} = ℵ_{β}? By Cantor’s Theorem we have 2^{ℵ_{0}} ≥ ℵ_{1}. The assertion that 2^{ℵ_{0}} = ℵ_{1} is known as the Continuum Hypothesis, or CH.

More generally, for any infinite cardinal κ, Cantor’s Theorem tells us that 2^{κ} ≥ κ^{+}, and we can ask whether 2^{κ} = κ^{+}. The assertion that 2^{κ} = κ^{+} for all infinite cardinals κ (equivalently, 2^{ℵ_{α}} = ℵ_{α+1} for all ordinal numbers α) is known as the Generalized Continuum Hypothesis, or GCH.

Exercise 4.6.11. Prove that 2^{ℵ_{0}} ≠ ℵ_{ω}. (Hint: Use König’s Theorem.)

4.7 Some Classes of Cardinals

A cardinal is said to be uncountable if it is > ℵ_{0}. In this section we introduce some important classes of uncountable cardinals.

Definition 4.7.1. Let λ be an uncountable cardinal. We say that λ is a successor cardinal if λ = κ^{+} for some κ < λ. We say that λ is a limit cardinal if κ^{+} < λ for all κ < λ. We say that λ is a strong limit cardinal if 2^{κ} < λ for all κ < λ.

Note that λ is a successor cardinal if and only if λ = ℵ_{α+1} for some successor ordinal α + 1, and λ is a limit cardinal if and only if λ = ℵ_{δ} for some limit ordinal δ. The first few uncountable successor cardinals are ℵ_{1}, ℵ_{2}, …. The first uncountable limit cardinal is ℵ_{ω}. Clearly every strong limit cardinal is a limit cardinal, and the GCH implies that every limit cardinal is a strong limit cardinal.

Lemma 4.7.2. Every uncountable cardinal is either a successor cardinal or a limit cardinal, and exactly one of these possibilities holds.

Proof. Obvious.

Definition 4.7.3. An infinite cardinal λ is said to be regular if it is not the sum of fewer than λ cardinals each less than λ. In other words, for any indexed set of cardinals ⟨κ_{i}⟩_{i∈I} with |I| < λ and κ_{i} < λ for all i ∈ I, we have ∑_{i∈I} κ_{i} < λ.

Trivially ℵ_{0} is regular, since it is not the sum of a finite set of finite cardinals.

Theorem 4.7.4. Every uncountable successor cardinal is regular.

Proof. Let λ be an uncountable successor cardinal. Thus λ = κ^{+} where κ is an infinite cardinal. Given an indexed set of cardinals ⟨κ_{i}⟩_{i∈I}, we see that κ_{i} < λ implies κ_{i} ≤ κ, also |I| < λ implies |I| ≤ κ, hence

∑_{i∈I} κ_{i} ≤ ∑_{i∈I} κ = |I| · κ ≤ κ · κ = κ < λ.

This shows that λ is regular.

In particular ℵ_{1}, ℵ_{2}, … are regular. An infinite cardinal is said to be singular if it is not regular. The first singular cardinal is ℵ_{ω}, since ℵ_{ω} = ∑_{n∈ℕ} ℵ_{n}.

Exercise 4.7.5. Let α be an ordinal number which is > ω. Show that α is a regular cardinal (i.e., a regular initial ordinal) if and only if, for every set of ordinal numbers X with sup X = α, we have type(X) = α.

Definition 4.7.6. Let λ be an uncountable cardinal. The cofinality of λ, written cf(λ), is the smallest cardinal κ such that λ = ∑_{i∈I} λ_{i} for some indexed set of cardinals λ_{i} < λ, i ∈ I, with |I| = κ.

Exercise 4.7.7. Prove the following facts.

1. cf(λ) is regular.

2. λ is regular if and only if cf(λ) = λ.

3. λ is singular if and only if cf(λ) < λ.

4. λ^{cf(λ)} > λ. (Hint: Use König’s Theorem.)

5. For any infinite cardinal κ we have cf(μ^{κ}) > κ for all μ > 1. In particular, cf(2^{κ}) > κ.

Exercise 4.7.8. Let κ be an infinite regular cardinal. Show that there exist arbitrarily large strong limit cardinals λ such that cf(λ) = κ. Moreover, for all such λ we have λ^{μ} = λ for all μ < κ.

Exercise 4.7.9. Assuming the GCH, prove that for all infinite cardinals κ and λ we have

λ^{κ} = \{ \begin{matrix}λ & if κ < cf(λ), \\ λ^{+} & if cf(λ) ≤ κ ≤ λ, \\ κ^{+} & if κ ≥ λ. \end{matrix}

Definition 4.7.10. An inaccessible cardinal is an uncountable, regular, strong limit cardinal. A weakly inaccessible cardinal is an uncountable, regular, limit cardinal.

Remark 4.7.11. Clearly every inaccessible cardinal is weakly inaccessible, and the GCH implies that every weakly inaccessible cardinal is inaccessible. It can be shown that every weakly inaccessible cardinal is a fixed point of the ℵ_{α}’s, i.e., such cardinals are of the form λ = ℵ_{λ}. Moreover, every strongly inaccessible cardinal has λ^{κ} = λ for all κ < λ.

The existence of inaccessible and/or weakly inaccessible cardinals is not obvious. Indeed, we shall see later that the existence of such cardinals cannot be established using the accepted axioms of set theory.

4.8 Pure Well-Founded Sets

A set X is said to be transitive if, for every set Y such that Y ∈ X, we have Y ⊆ X.

Lemma 4.8.1. Given a set X, there is a smallest transitive set TC(X) including X. (TC(X) is called the transitive closure of X.)

Proof. Define U(X) = ⋃{Y | Y ∈ X, Y a set}. By recursion on n < ω define

\begin{aligned}TC_{0}(X) & = & X \\ TC_{n+1}(X) & = & U(TC_{n}(X)) . \end{aligned}

Then TC(X) = ⋃_{n∈ℕ} TC_{n}(X) is easily seen to be the smallest transitive set Y such that Y ⊇ X.

For any set A, we write

∈|A = {(b, a) | a, b ∈ A, a is a set, b ∈ a} .

Definition 4.8.2. A set X is said to be well-founded if the relational structure (TC(X), ∈|TC(X)) is well-founded.

Applying Lemma 4.3.5 to the relational structure (TC(X), ∈|TC(X)), we see that X is well-founded if and only if there is no infinite sequence of sets ⟨X_{n}⟩_{n∈ℕ} with

X = X_{0} ∋ X_{1} ∋ ⋯ ∋ X_{n} ∋ · · · .

Definition 4.8.3. A set X is said to be pure if every element of TC(X) is a set. In other words, X is a pure set if not only X but also all the elements of X, elements of elements of X, …, are sets.

By transfinite recursion we define transitive sets R_{α}, α ∈ Ord, as follows:

R_{0} = ∅
R_{α+1} = P(R_{α})
R_{δ} = ⋃_{α<δ} R_{α} for limit ordinals δ .

By transfinite induction on α ∈ Ord, it is clear that β < α implies R_{β} ∈ R_{α}, hence β ≤ α implies R_{β} ⊆ R_{α}.

Theorem 4.8.4. X ∈ ⋃_{α∈Ord} R_{α} if and only if X is a pure, well-founded set.

Proof. It is straightforward to prove by transfinite induction on α that all elements of R_{α} are pure and well-founded. Conversely, suppose X is pure and well-founded. We claim that, for all Y ∈ TC({X}), there exists an ordinal number α such that Y ∈ R_{α}. If not, let Y ∈ TC({X}) be ∈-minimal such that no such α exists. For each Z ∈ Y, let f(Z) be the least ordinal number β such that Z ∈ R_{β}. Put γ = sup_{Z∈Y} f(Z). Then Y ⊆ R_{γ}, hence Y ∈ P(R_{γ}) = R_{γ+1}, a contradiction. This proves the claim. In particular, X ∈ R_{α} for some α. This proves the theorem.

The class of all pure, well-founded sets is denoted V. Thus we have

V = ⋃_{α∈Ord} R_{α} .

If X is a pure, well-founded set, we define the rank of X to be the least ordinal number α such that X ⊆ R_{α}. Then clearly

rank X = sup{rank Y + 1 | Y ∈ X} .

Moreover, for all ordinals α we have

R_{α} = {X | X is a pure well-founded set of rank < α} ,

and rank R_{α} = α.

Exercise 4.8.5. Assuming the GCH, prove that |R_{ω+α}| = ℵ_{α} for all ordinals α.

4.9 Set-Theoretic Foundations

In the next chapter we shall begin the study of axiomatic set theory. In axiomatic studies of set theory, the set concept is usually restricted to pure, well-founded sets. This restriction tends to isolate set theory from the rest of mathematics. Nevertheless, the restriction is partially justified by the fact that many or most mathematical objects can be reconstructed or redefined as pure, well-founded sets.

For example, the natural numbers 0, 1, 2, … are not ordinarily regarded as being sets, but within the universe of pure, well-founded sets, it is possible to define a structural replica of the natural numbers. Thus, from a certain perspective, natural numbers can be viewed as certain kinds of pure, well-founded sets.

A similar remark applies to each of following mathematical concepts: natural number, real number, ordinal number, cardinal number, ordered pair, function. For each concept in this list, it is possible to identify mathematical objects of the given type with certain pure, well-founded sets. The purpose of this section is to show exactly how these identifications can be made. We begin with ordered pairs and progress to functions, ordinal numbers, and real numbers.

Definition 4.9.1. For any two objects a and b, let us write

(a, b) = {{a}, {a, b}} .

Thus (a, b) is a set. Note that if a and b are pure, well-founded sets, then so is (a, b).

Lemma 4.9.2. If (a, b) = (a′, b′) then a = a′ and b = b′.

Proof. Putting X = (a, b), we see that a is the unique element of ⋂_{Y ∈X} Y, and b is the unique element of ⋃_{Y ∈X} Y \ {a} if the latter is nonempty, otherwise b = a. Thus a and b can be recovered from (a, b) by single-valued set-theoretic operations. The lemma follows.

By the above lemma, we may view (a, b) as the ordered pair formed from a and b. From now on we shall make this identification, which is customary in pure set theory.

In an earlier section of these notes, we defined a function with domain X to be a rule associating to each a ∈ X a unique b. In pure set theory, it is customary to replace this definition by the following, which we shall use from now on.

Definition 4.9.3. A function is a set of ordered pairs, f, which is single-valued, i.e.,

∀a ∀b ∀c (((a, b) ∈ f ∧ (a, c) ∈ f) ⇒ b = c) .

The domain of f is dom(f) = {a | ∃b ((a, b) ∈ f)}. If f is a function and a ∈ dom(f) we write f(a) = the unique b such that (a, b) ∈ f.

The pure set-theoretic reconstruction of the ordinal numbers, due to von Neumann, is as follows:

Definition 4.9.4. A von Neumann ordinal is a transitive, pure, well-founded set A such that (A, ∈|A) is a well-ordering.

Note that if A is a von Neumann ordinal, then for each b ∈ A, the initial segment B = {a | a ∈ b} is again a von Neumann ordinal.

Lemma 4.9.5. For each ordinal number α, there is a unique von Neumann ordinal A_{α} such that type(A_{α}, ∈|A_{α}) = α. Moreover, the rank of A_{α} is α.

Proof. By transfinite recursion we define A_{α} = {A_{β} | β < α} for all ordinals α. By transfinite induction on α, it is straightforward to verify that A_{α} is the unique von Neumann ordinal such that type(A_{α}, ∈|A_{α}) = α, and that rank(A_{α}) = α.

Remark 4.9.6. It is customary in pure set theory to identify the ordinal number α with the von Neumann ordinal A_{α}. From now on we shall make this identification. Thus we have 0 = ∅ = {}, 1 = {0} = {{}}, 2 = {0, 1} = {{}, {{}}}, …, ω = {0, 1, 2, …} = ℕ. Moreover, for all ordinals α we have α = {β | β < α} and α + 1 = α ∪ {α}. Also, if X is any set of ordinals, then

sup X = ⋃ X = ⋃_{α∈X} α .

As for cardinal numbers, we have already seen how cardinal numbers may be identified with certain ordinal numbers, namely, the initial ordinals. Thus, we already know how to identify cardinal numbers with certain pure, well-founded sets.

Finally, we turn to the set-theoretic construction of the real number system. The construction emplys the usual factorization of a set by an equivalence relation, as per the following definitions and remark.

Definition 4.9.7. Let A be a set. An equivalence relation on A is a binary relation R ⊆ A × A with the following properties: aRb and bRc imply aRc; aRb implies bRa; and aRa for all a ∈ A.

Definition 4.9.8. Let R be an equivalence relation on A. For any a ∈ A we write [a]_{R} = {b ∈ A | aRb}, the equivalence class of a with respect to R. We write A/R = {[a]_{R} | a ∈ A}.

Remark 4.9.9. Let R be an equivalence relation on A. Then aRb if and only if [a]_{R} = [b]_{R}. Moreover A/R is a partition of A, i.e., a collection of pairwise disjoint sets whose union is A.

Definition 4.9.10 (the real number system). In order to define the real number system, we follow Dedekind and begin with the natural number system (ℕ, +, ·, 0, 1, =, <).

The integers are defined by putting ℤ = (ℕ × ℕ)/≡_{ℤ}, where (m, n) ≡_{ℤ} (m′, n′) if and only if m + n′ = m′ + n. The ordered ring structure of ℤ is given by

\begin{aligned}[(m, n)] +_{ℤ} [(m′, n′)] & = & [(m + m′, n + n′)] \\ [(m, n)] ·_{ℤ} [(m′, n′)] & = & [(mm′ + nn′, mn′ + m′n)] \\ −_{ℤ} [(m, n)] & = & [(n, m)] \\ 0_{ℤ} & = & [(0, 0)] \\ 1_{ℤ} & = & [(1, 0)] \\ [(m, n)] = [(m′, n′)] & ⇔ & m + n′ = m′ + n \\ [(m, n)] <_{ℤ} [(m′, n′)] & ⇔ & m + n′ < m′ + n \end{aligned}

The rationals are defined by putting ℚ = (ℤ × ℤ^{+})/≡_{ℚ}, where ℤ^{+} = {b ∈ ℤ | b > 0}, and (a, b) ≡_{ℚ} (a′, b′) if and only if a · b′ = a′ · b. The ordered ring structure of ℚ is given by

\begin{aligned}[(a, b)] +_{ℚ} [(a′, b′)] & = & [(ab′ + a′b, b · b′)] \\ [(a, b)] ·_{ℚ} [(a′, b′)] & = & [(aa′, bb′)] \\ −_{ℚ} [(a, b)] & = & [(−a, b)] \\ 0_{ℚ} & = & [(0, 1)] \\ 1_{ℚ} & = & [(1, 1)] \\ [(a, b)] = [(a′, b′)] & ⇔ & ab′ = a′b \\ [(a, b)] <_{ℚ} [(a′, b′)] & ⇔ & ab′ < a′b \end{aligned}

Finally, the reals are defined by putting ℝ = S/≡_{ℝ}. Here S is defined to be the set of Cauchy sequences over ℚ, i.e., sequences ⟨q_{n}⟩_{n∈ℕ} ∈ ℚ^{ℕ} satisying

∀ε > 0 ∃m ∀n (n > m ⇒ |q_{m} − q_{n}| < ε) .

And ≡_{ℝ} is the equivalence relation on S defined by putting ⟨q_{n}⟩_{n} ≡_{ℝ} ⟨q′_{n}⟩_{n} if and only if lim_{n} |q_{n} − q′_{n}| = 0, i.e.,

∀ε > 0 ∃m ∀n (n > m ⇒ |q_{n} − q′_{n}| < ε) .

The ordered ring structure of ℝ is given by

\begin{aligned}[⟨q⟩_{n}] +_{ℝ} [⟨q′_{n}⟩_{n}] & = & [⟨q_{n} + q′_{n}⟩_{n}] \\ [ ⟨q_{n}⟩_{n}] ·_{ℝ} [⟨q′_{n}⟩_{n}] & = & [⟨q_{n} · q′_{n}⟩_{n}] \\ −_{ℝ} [⟨q_{n}⟩_{n}] & = & [⟨−q_{n}⟩_{n}] \\ 0_{ℝ} & = & [⟨0⟩_{n}] \\ 1_{ℝ} & = & [⟨1⟩_{n}] \\ [ ⟨q_{n}⟩_{n}] = [⟨q′_{n}⟩_{n}] & ⇔ & ∀ε > 0 ∃m ∀n (n > m ⇒ |q_{n} − q′_{n}| < ε) \\ [ ⟨q_{n}⟩_{n}] <_{ℝ} [⟨q′_{n}⟩_{n}] & ⇔ & ∃ε > 0 ∃m ∀n (n > m ⇒ q_{n} + ε < q′_{n}) \end{aligned}

Exercise 4.9.11. Show that the real number system is complete, i.e., every nonempty bounded subset of ℝ has a least upper bound.

Remark 4.9.12. In this section we have shown how many or most mathematical objects may be redefined or reconstructed as pure, well-founded sets. In this sense, pure set theory may be said to encompass virtually all of mathematics, and one may speak of the set-theoretic foundations of mathematics. This is why set theory is viewed as being of fundamental or foundational importance.

Axiomatic Set Theory

This chapter is an introduction to axiomatic set theory.

5.1 The Axioms of Set Theory

Definition 5.1.1. We define L_{∈}, the language of set theory. The language contains variables x, y, z, . . .. The atomic formulas of the language are x = y and x ∈ y, where x and y are variables. Formulas are built up as usual from atomic formulas by means of propositional connectives ∧, ∨, ¬, ⇒, ⇔ and quantifiers ∀, ∃. The notion of free variable is defined as usual. A sentence is a formula with no free variables.

Remark 5.1.2. The standard or intended interpretation of L_{∈} is that the variables are to range over the class of pure, well-founded sets. Thus formulas and sentences are normally interpreted as making assertions about pure, wellfounded sets. This standard interpretation or model of L_{∈} is sometimes known as the real world.

Example 5.1.3. An example of a sentence of L_{∈} is

∀x ∀y (x = y ⇔ ∀u (u ∈ x ⇔ u ∈ y)) .

This sentence asserts the extensionality principle for pure, well-founded sets: two pure, well-founded sets are equal if and only if they contain the same pure, well-founded sets as elements.

Example 5.1.4. An example of a formula of L_{∈} is

∀u (u ∈ z ⇔ (u = x ∨ u = y)) .

This formula has free variables x, y, and z. It asserts that z is the unordered pair {x, y}, i.e., the set whose only elements are x and y.

As mentioned above, the standard interpretation of L_{∈} is in terms of the real world, i.e., the class of pure, well-founded sets. In later sections of this chapter, we shall consider interpretations or models of L_{∈} other than the real world. Such alternative interpretations play an essential role in axiomatic set theory.

We can expand the language L_{∈} indefinitely by introducing abbreviations. Some important abbreviations are given in the following definition.

Definition 5.1.5.

1. (unordered pair) z = {x, y} is an abbreviation for

∀u (u ∈ z ⇔ (u = x ∨ u = y)).

2. (singleton) z = {x} is an abbreviation for z = {x, x}.

3. (ordered pair) z = (x, y) is an abbreviation for z = {{x}, {x, y}}, i.e.,

∃u ∃v (u = {x} ∧ v = {x, y} ∧ z = {u, v}).

4. (subset) x ⊆ y is an abbreviation for ∀u (u ∈ x ⇒ u ∈ y).

5. (powerset) z = P(x) is an abbreviation for

∀y (y ∈ z ⇔ y ⊆ x).

6. (union of a set of sets) z = ⋃ x is an abbreviation for

∀u (u ∈ z ⇔ ∃v (v ∈ x ∧ u ∈ v)).

7. (union of two sets) z = x ∪ y is an abbreviation for z = ⋃{x, y}, i.e.,

∃w (w = {x, y} ∧ z = ⋃ w).

8. (intersection of a set of sets) z = ⋂ x is an abbreviation for

∀u (u ∈ z ⇔ ∀v (v ∈ x ⇒ u ∈ v)).

9. (intersection of two sets) z = x ∩ y is an abbreviation for z = ⋂{x, y}, i.e.,

∃w (w = {x, y} ∧ z = ⋂ w).

10. (empty set) x = ∅ and x = {} are abbreviations for ∀u (u ∉ x).

Using these abbreviations, we can write down sentences expressing some of the axioms of Zermelo-Fraenkel set theory:

Definition 5.1.6 (Some Axioms of Set Theory).

1. Axiom of Extensionality: ∀x ∀y (x = y ⇔ ∀u (u ∈ x ⇔ u ∈ y)).

2. Empty Set Axiom: ∃x (x = ∅).

3. Pairing Axiom: ∀x ∀y ∃z (z = {x, y}).

4. Union Axiom: ∀x ∃z (z = ⋃ x).

5. Power Set Axiom: ∀x ∃z (z = P(x)).

6. Axiom of Foundation: ∀x (x ≠ ∅ ⇒ ∃u (u ∈ x ∧ u ∩ x = ∅)). Most of the above axioms are self-explanatory. Only the Axiom of Founda-

tion needs explanation. The Axiom of Foundation is an attempt to express the idea that all of the sets under consideration are well-founded. This is expressed by saying that, for all sets x, if x is nonempty then x contains an element u which is ∈-minimal. Note that, for u ∈ x, u ∩ x = ∅ means that u is ∈-minimal among elements of x, i.e., there is no element v of x such that v ∈ u.

We now introduce some more abbreviations and axioms. Definition 5.1.7.

1. (Cartesian product) z = x × y is an abbreviation of ∀w (w ∈ z ⇔ ∃u ∃v (u ∈ x ∧ v ∈ y ∧ w = (u, v))).

2. (function) Fcn(f) is an abbreviation for a formula saying that f is a function, i.e., ∀w (w ∈ f ⇒ ∃x ∃y (w = (x, y)))∧∀x ∀y ∀z (((x, y) ∈ f∧(x, z) ∈ f) ⇒ y = z) .

3. (value of a function) y = f(x) is an abbreviation of Fcn(f) ∧ (x, y) ∈ f.

4. (domain of a function) z = dom(f) is an abbreviation of Fcn(f) ∧ ∀x (x ∈ z ⇔ ∃y (x, y) ∈ f).

5. (generalized Cartesian product) z = ∏ f is an abbreviation of Fcn(f)∧∀g (g ∈ z ⇔ (dom(g) = dom(f)∧∀x (x ∈ dom(f) ⇒ g(x) ∈ f(x)))) .

Definition 5.1.8. The Axiom of Choice is the sentence ∀f ((Fcn(f) ∧ ∀x (x ∈ dom(f) ⇒ f(x) ≠ ∅)) ⇒ ∏ f ≠ ∅).

Definition 5.1.9. The Axiom of Infinity is the sentence

∃z (∅ ∈ z ∧ ∀x (x ∈ z ⇒ x ∪ {x} ∈ z)).

The purpose of the Axiom of Infinity is to assert the existence of at least one infinite set. This is accomplished by asserting the existence of a set that contains all of the sets 0 = {} = ∅, 1 = {0}, 2 = {0, 1}, 3 = {0, 1, 2}, ….

We now introduce the two remaining axioms of Zermelo-Fraenkel set theory. Actually, these two so-called axioms are not individual axioms, but rather axiom schemes. An axiom scheme is an infinite set of axioms all of which have a common form.

Recall that, if F is a formula with free variables x_{1}, …, x_{n}, then the universal closure of F is the sentence ∀x_{1} ⋯ ∀x_{n} F.

Definition 5.1.10.

1. The Comprehension Scheme is an infinite set of axioms, consisting the universal closures of all formulas of the form

∃z ∀u (u ∈ z ⇔ (u ∈ x ∧ F (u))) ,

where F (u) is any formula in which z does not occur freely.

2. For any formula F (u), we write z = {u ∈ x | F (u)} as an abbreviation for

∀u (u ∈ z ⇔ (u ∈ x ∧ F (u))) .

The Comprehension Scheme is our attempt to express the principle that, given a set x and a property P that particular elements of x may or may not have, there necessarily exists a set z ⊆ x consisting of all elements of x which have the given property P. Since our language L_{∈} does not enable us to discuss or quantify over arbitrary properties, we restrict attention to properties that are definable, i.e., expressible by means of a formula F (u). The syntactical requirement that the variable z does not occur freely in F (u) is imposed in order to avoid obvious contradictions such as z = {u ∈ x | u ∉ z}, the idea being that the set z should be in some sense logically subordinate to the property P.

The Comprehension Scheme is extremely useful and important. For example, given a function f, the Comprehension Scheme together with the Union, Pairing, and Power Set Axioms logically imply the existence of a set z which is the domain of f,

z = domf = {x ∈ ⋃ ⋃ f | ∃y ((x, y) ∈ f)},

and of the generalized Cartesian product

∏ f = {g ∈ PPP(⋃ ⋃ f ∪ ⋃ ⋃ ⋃ f) | domg = z ∧ ∀x (x ∈ z ⇒ g(x) ∈ f(x))}.

Definition 5.1.11.

1. We write ∃! x to mean “there exists exactly one x such that”. In other words, for any formula F (x) in which x occurs as a free variable, ∃! x F (x) is an abbreviation of

∃y ∀x (F (x) ⇔ x = y) .

2. The Replacement Scheme is an infinite set of axioms, consisting of the universal closures of all formulas of the form

∀u (u ∈ x ⇒ ∃! v F (u, v)) ⇒ ∃y ∀v (v ∈ y ⇔ ∃u (u ∈ x ∧ F (u, v))) ,

where F (u, v) is any formula in which y does not occur freely.

The Replacement Scheme is our attempt to express the principle that, given a set x and a rule associating to each element u of x a unique object v, there exists a set y consisting of all the objects v which are associated to elements of x. Since our language L_{∈} does not enable us to discuss or quantify over arbitrary rules, we restrict attention to rules that are definable, i.e., expressible by means of a formula F (u, v). The syntactical requirement that the variable y does not occur freely in F (u, v) is imposed in order to avoid obvious contradictions.

We have now introduced all of the axioms of Zermelo/Fraenkel set theory. We have, finally:

Definition 5.1.12 (Zermelo/Fraenkel Set Theory). The axioms of Zermelo/Fraenkel set theory are as follows: the Axiom of Extensionality, the Empty Set Axiom, the Pairing Axiom, the Union Axiom, the Power Set Axiom, the Axiom of Foundation, the Axiom of Infinity, the Comprehension Scheme, and the Replacement Scheme. We use ZF as an abbreviation for “Zermelo/Fraenkel set theory”.

Definition 5.1.13 (ZFC). The axioms of ZFC consist of the axioms of ZF plus the Axiom of Choice.

The Zermelo/Fraenkel axioms together with the Axiom of Choice constitute the commonly accepted, rigorous, set-theoretic foundation of mathematics. A mathematical theorem is regarded as proved if and only if it is clear how to deduce it as a theorem of ZFC, i.e., a logical consequence^{1} of the ZFC axioms. It can be shown that all of the theorems of 19th and 20th century rigorous mathematics are logical consequences of the ZFC axioms. In particular, essentially all of the results of Chapter 4 can be stated and proved as theorems of ZFC.

5.2 Models of Set Theory

As mentioned above, the intended interpretation of L_{∈} is the so-called real world, i.e., the class of pure, well-founded sets. However, the general notion of pure, well-founded set is rather vague. In order to study and delimit this vagueness, axiomatic set theorists frequently consider alternative interpretations of L_{∈}.

One important class of interpretations of L_{∈} is given in terms of relational structures. Recall that a relational structure is an ordered pair (A, E) where A is a set and E ⊆ A × A. Given a relational structure (A, E) and a sentence F of L_{∈}, it makes sense to ask whether F is true in (A, E), i.e., true when the variables are interpreted as ranging over A and x ∈ y is interpreted as xEy, i.e., (x, y) ∈ E.

1The notions of theorem and logical consequence that we are using here will be explained in the next section.

Examples 5.2.1. The Axiom of Extensionality is true in a particular relational structure (A, E) if and only if (A, E) is extensional, i.e., for all a, b ∈ A, a ≠ b implies {c | cEa} ≠ {c | cEb}. Note that some relational structures are extensional and some are not. An example of an extensional relational structure is any linear ordering. An example of a nonextensional relational structure is (A, E) whenever |A| ≥ 2 and E = ∅.

Thus a relational structure is extensional if and only if it is a model of (i.e., satisfies) the Axiom of Extensionality. The general point here is that any collection of sentences of L_{∈} defines a property of relational structures, namely the property of satisfying the given sentences. We formalize this in the following definition.

Definition 5.2.2. Let S be any set of sentences of L_{∈}. A model of S is a relational structure (A, E) such that all of the sentences of S are true in (A, E). We say that S is consistent if there exists a model of S. If F is another sentence of L_{∈}, we say that F is a logical consequence of S, written S ⊢ F, if F is true in every model of S.

Note that if S is inconsistent then all sentences are logical consequences of S, so the notion of logical consequence is uninteresting in this case. If however S is consistent, then it is meaningful to ask which sentences are logical consequences of S, i.e., what conclusions follow when the sentences of S are assumed as axioms. This is the kind of question which axiomatic set theory seeks to answer. Naturally the focus is on sets of sentences which make assertions that could reasonably be true in the intended model, i.e., the real world, i.e., the class of all pure, well-founded sets.

As an easy example of the notion of logical consequence, note that the sentence ∀x (x ∉ x) is a logical consequence of the Axiom of Foundation plus the Pairing Axiom. This is so because x ∈ x would imply that {x} has no ∈-minimal element.

Specializing Definition 5.2.2 to S = ZF and S = ZFC, we have:

Definition 5.2.3. A model of ZFC is a relational structure (A, E) such that (A, E) satisfies all of the Zermelo/Fraenkel axioms plus the Axiom of Choice. A theorem of ZFC is any sentence which is a logical consequence of the ZFC axioms. The notions model of ZF and theorem of ZF are defined similarly.

Axiomatic set theory is essentially the study of models of ZF and of ZFC, with an eye to discovering which set-theoretic propositions follow or do not follow from these axiom systems. For instance, one of the important results^{2} of axiomatic set theory is that there exists a model of ZF which is not a model of ZFC. In other words, the Axiom of Choice is not a logical consequence of the ZF axioms. Another key result is that both the Continuum Hypothesis and its negation are consistent with ZFC. In other words, CH is independent of ZFC. Thus the ZFC axioms, although powerful and flexible, do not suffice to answer basic set-theoretic questions such as the Continuum Problem.

2This result will not be proved here.

We end this section by presenting some general definitions and results concerning relational structures.

Definition 5.2.4. Let (A, E) be a relational structure. A k-place predicate P ⊆ A^{k} is said to be definable over (A, E) if there exists a formula F (x_{1}, …, x_{k}, y_{1}, …, y_{m}) of L_{∈} and parameters b_{1}, …, b_{m} ∈ A such that

P = {⟨a_{1}, …, a_{k}⟩ ∈ A^{k} | (A, E) satisfies F (a_{1}, …, a_{k}, b_{1}, …, b_{m})} . (5.1)

More generally, given B ⊆ A, we say that P ⊆ A^{k} is definable over (A, E) allowing parameters from B if there exists a formula

F (x_{1}, …, x_{k}, y_{1}, …, y_{m})

of L_{∈} and parameters b_{1}, …, b_{m} ∈ B such that (5.1) holds.

Definition 5.2.5. Let (A, E) be a relational structure. Then Def((A, E)) is the set of all subsets of A that are definable over (A, E). Note that Def((A, E)) ⊆ P(A).

Lemma 5.2.6. Let (A, E) be a relational structure.

1. If A is finite, then Def((A, E)) = P(A) and |Def((A, E)| = 2^{|A|}.

2. If A is infinite, then |Def((A, E))| = |A|.

Proof. For finite A the result is obvious. Suppose now that A is infinite. By Gödel numbering, the set of all formulas of L_{∈} is countable. Since any element of Def((A, E)) is determined by a formula and a finite sequence of parameters from A, we have

|Def((A, E))| ≤ ℵ_{0} · |A^{∗}| = |A| .

On the other hand {{a} | a ∈ A} ⊆ Def((A, E)), hence |A| ≤ |Def((A, E))|. This completes the proof.

Definition 5.2.7. Let (A, E) and (A′, E′) be relational structures. We say that (A′, E′) is a substructure of (A, E), abbreviated (A′, E′) ⊆ (A, E), if A′ ⊆ A and E′ = E ∩ (A′ × A′). We say that (A′, E′) is an elementary substructure of (A, E), abbreviated (A′, E′) ⊆_{elem} (A, E), if (A′, E′) ⊆ (A, E) and, for all formulas F (x_{1}, …, x_{n}) and a_{1}, …, a_{n} ∈ A′, (A, E) satisfies F (a_{1}, …, a_{n}) if and only if (A′, E′) satisfies F (a_{1}, …, a_{n}).

Lemma 5.2.8. Given (A′, E′) ⊆ (A, E), we have (A′, E′) ⊆_{elem} (A, E) if and only if every nonempty subset of A which is definable over (A, E) allowing parameters from A′ has a nonempty intersection with A′.

Proof. Straightforward.

Recall that a relational structure (A, E) is said to be countable if the underlying set A is countable.

Theorem 5.2.9 (Löwenheim/Skolem Theorem). For any relational structure (A, E), there exists a countable elementary substructure (A′, E′) ⊆_{elem} (A, E).

Proof. Let c : P(A) \ {∅} → A be a choice function for A. We define recursively a sequence of sets A_{n} ⊆ A, n ∈ ℕ, by A_{0} = ∅, A_{n+1} = {c(X) | ∅ ≠ X ⊆ A∧X is definable over (A, E) allowing parameters from A_{n}}. Note that A_{n} ⊆ A_{n+1} for all n. By induction on n it is straightforward to show that A_{n} is countable for all n. Hence A′ = ⋃{A_{n} | n ∈ ℕ} is countable. Moreover c(X) ∈ A′ for all X ≠ ∅ definable over (A, E) allowing parameters from A′. Hence by Lemma 5.2.8 we have (A′, E′) ⊆_{elem} (A, E), where E′ = E ∩ (A′ × A′). This completes the proof.

Corollary 5.2.10 (Skolem Paradox). If ZFC is consistent, then there exists a countable model of ZFC.

Proof. Assume that ZFC is consistent. Then there exists a model (A, E) of ZFC. By Theorem 5.2.9 (A, E) has a countable elementary submodel, (A′, E′). Then (A′, E′) is a countable model of ZFC.

The Skolem Paradox is called a paradox for the following reason: the existence of a countable model of ZFC would seem to contradict the fact that the existence of uncountable sets is a theorem of ZFC. Actually, there is no contradiction here, because a set that is uncountable within a particular model (A, E) may be countable in the real world. In other words, the notion of countability is relative to the model under consideration (as are many other set-theoretic notions).

A straightforward generalization of Theorem 5.2.9 is:

Theorem 5.2.11 (Generalized Löwenheim-Skolem Theorem). Let κ be an infinite cardinal. Let (A, E) be a relational structure such that |A| ≥ κ, and let X ⊆ A be a subset of A such that |X| ≤ κ. Then there exists an elementary substructure (A′, E′) of (A, E) such that X ⊆ A′ and |A′| = κ.

Proof. Straightforward.

Exercise 5.2.12. Prove Theorem 5.2.11.

5.3 Transitive Models and Inaccessible Cardinals

In this section we study an important class of models. Recall that a set T is transitive if and only if every element of T is a subset of T.

Definition 5.3.1. Let S be a set of sentences of L_{∈}. A transitive model of S is any transitive, pure, well-founded set T such that the relational structure (T, ∈|T) satisfies all the sentences of S. In this context it is customary to identify the transitive set T with the relational structure (T, ∈|T).

Note that every transitive model is well-founded and extensional. The following theorem provides a converse and thereby characterizes transitive models up to isomorphism among arbitrary models.

Theorem 5.3.2. Let (A, E) be a relational structure which is well-founded and extensional. Then there exists a transitive, pure, well-founded set T such that the relational structures (A, E) and (T, ∈|T) are isomorphic. Moreover the transitive set T and the isomorphism f : (A, E) ≅ (T, ∈|T) are unique.

Proof. Fix an object a_{0} ∉ A. By transfinite recursion on the rank of an arbitrary pure, well-founded set x, define F (x) as follows: F (x) = the unique a ∈ A such that rng(F ↾x) = {b | bEa} if such an a exists; F (x) = a_{0} otherwise. Note that F (x) = F (y) ∈ A implies x = y. Hence T = rng(F^{−1}↾A) is a set. It is easy to verify that T is a transitive, pure, well-founded set and that F ↾T is an isomorphism of (T, ∈|T) onto (A, E). Hence f = F^{−1}↾A is an isomorphism of (A, E) onto (T, ∈|T). It is straightforward to verify that T and f are unique.

Corollary 5.3.3. If (A, E) is a relational structure, then the following assertions are equivalent:

1. (A, E) is isomorphic to some transitive model (T, ∈|T);

2. (A, E) is well-founded and extensional.

The rest of this section is devoted to the study of transitive models, i.e., relational structures of the form (A, ∈|A) where T is a transitive, pure, wellfounded set. The following definition concerning transitive models is of general interest.

Definition 5.3.4. Let T be any transitive, pure, well-founded set. A k-place predicate P ⊆ T^{k} is said to be definable over T if and only if it is definable over (T, ∈|T) (allowing parameters from T). We write

Def(T) = Def((T, ∈|T)) = {X ⊆ T | X is definable over T } .

Of particular interest are transitive models of ZFC. The following lemma consists of some simple remarks characterizing which transitive models satisfy which axioms of ZFC.

Lemma 5.3.5. Let T be a transitive, pure, well-founded set.

1. T always satisfies the Axiom of Extensionality.

2. T always satisfies the Axiom of Foundation.

3. T satisfies the Pairing Axiom if and only if T is closed under pairing, i.e.,

∀a ∀b ((a ∈ T ∧ b ∈ T) ⇒ {a, b} ∈ T).

4. T satisfies the Union Axiom if and only if T is closed under union, i.e.,

∀a (a ∈ T ⇒ ⋃ a ∈ T).

5. T satisfies the Empty Set Axiom if and only if ∅ ∈ T.

6. T satisfies the Axiom of Infinity if and only if ∃a (a ∈ T ∧ ω ⊆ a).

7. T satisfies the Power Set Axiom if and only if

∀a (a ∈ T ⇒ P(a) ∩ T ∈ T).

8. T satisfies the Axiom of Choice if and only if, for every indexed family of nonempty sets ⟨a_{i}⟩_{i∈I} ∈ T, we have T ∩ ∏_{i∈I} a_{i} ≠ ∅.

9. T satisfies the Comprehension Scheme if and only if, for all X ∈ Def(T), we have

∀a (a ∈ T ⇒ a ∩ X ∈ T).

10. T satisfies the Replacement Scheme if and only if for all functions F : T → T such that F ∈ Def(T), we have

∀a (a ∈ T ⇒ rng(F ↾a) ∈ T).

Proof. Straightforward.

We shall now show that inaccessible cardinals give rise to transitive models of ZFC. Recall that an inaccessible cardinal is a regular, uncountable, strong limit cardinal. Recall also that we have identified cardinals with initial von Neumann ordinals (cf. Sections 4.4.5 and 4.4.8).

Lemma 5.3.6. Let δ be a limit ordinal > ω. Then R_{δ} is a transitive model of all of the ZFC axioms except possibly the Replacement Scheme.

Proof. We apply Lemma 5.3.5. The Axioms of Extensionality and Foundation hold in R_{δ} because R_{δ} is a transitive, pure, well-founded set. The Empty Set, Power Set, Pairing, and Union Axioms and the Axiom of Choice and the Comprehension Scheme hold in R_{δ} because δ is a limit ordinal. The Axiom of Infinity holds in R_{δ} because ω ∈ R_{δ}, since ω < δ.

Lemma 5.3.7. An infinite cardinal λ is regular if and only if, for all X ⊆ λ, |X| < λ implies sup X < λ.

Proof. Straightforward.

Lemma 5.3.8. If λ is an inaccessible cardinal, then

1. ∀x ((x ⊆ R_{λ} ∧ |x| < λ) ⇒ x ∈ R_{λ}).

2. ∀x (x ∈ R_{λ} ⇒ |x| < λ).

3. |R_{λ}| = λ.

Proof. 1. Define ρ : x → λ by ρ(u) = rank(u). Then |rngρ| ≤ |x| < λ. Since λ is regular, it follows by the previous lemma that sup(rngρ) < λ, say rngρ ⊆ α < λ. Hence x ⊆ R_{α}, hence x ∈ R_{α+1} ⊆ R_{λ} since λ is a limit ordinal.

2. By transfinite induction on α < λ we prove |R_{α}| < λ. We have R_{0} = ∅. If |R_{α}| = κ < λ, then |R_{α+1}| = |P(R_{α})| = 2^{κ} < λ since λ is a strong limit cardinal. For limit ordinals δ < λ, we have inductively |R_{δ}| = | ⋃_{α<δ} R_{α}| = sup_{α<δ} |R_{α}| < λ, since |R_{α}| < λ and λ is regular.

3. |R_{λ}| = sup_{α<λ} |R_{α}| = λ.

Theorem 5.3.9. Let λ be an inaccessible cardinal. Then R_{λ} is a transitive model of ZFC.

Proof. Clearly λ is a limit ordinal > ω, hence by Lemma 5.3.6 we see that R_{λ} satisfies all of the ZFC axioms except possibly the Replacement Scheme.

Let F : R_{λ} → R_{λ} and a ∈ R_{λ} be given. Then rng(F ↾a) ⊆ R_{λ} and |rng(F ↾a)| ≤ |a| < λ, hence by the previous lemma rng(F ↾a) ∈ R_{λ}. Specializing this to the case when F is definable over R_{λ}, we see by Lemma 5.3.5 that the Replacement Scheme holds in R_{λ}. This completes the proof.

Corollary 5.3.10. If there exists an inaccessible cardinal, then ZFC is consistent.

Proof. Immediate from the theorem.

Exercise 5.3.11. A hereditarily finite set is a finite set x such that all elements of x, elements of elements of x, …, are finite sets. Show that R_{ω} is the set of all hereditarily finite, pure, well-founded sets. Show that R_{ω} is a model of all of the axioms of ZFC except the Axiom of Infinity.

Exercise 5.3.12. Define E ⊆ ℕ by putting mEn if and only if 2^{m} occurs in the binary expansion of n, i.e., m = n_{i} for some i where n = 2^{n_{1}} + ⋯ + 2^{n_{k}}.

1. Show that (ℕ, E) ≅ (R_{ω}, ∈|R_{ω}).

2. Conclude that P ⊆ ω^{k} is definable over R_{ω} if and only if P is arithmetical.

Theorem 5.3.13. If there exists an inaccessible cardinal, then the existence of an inaccessible cardinal is not a theorem of ZFC.

Proof. Assume that there exists an inaccessible cardinal. Let λ be the smallest inaccessible cardinal. By the previous theorem, R_{λ} is a model of ZFC. We claim that R_{λ} also satisfies “inaccessible cardinals do not exist”. To see this, suppose that R_{λ} satisfies “there exists at least one inaccessible cardinal”. Let κ ∈ R_{λ} be such that R_{λ} satisfies “κ is an inaccessible cardinal”. Then it is easy to see that κ is also an inaccessible cardinal in the real world. But clearly κ < λ. This contradicts the choice of λ. Thus R_{λ} is a model of ZFC + “inaccessible cardinals do not exist”.

The previous theorem shows that, if we assume only the axioms of ZFC, then we cannot hope to prove the existence of inaccessible cardinals.

Exercise 5.3.14. Show that, if two or more inaccessible cardinals exist, then the existence of two or more inaccessible cardinals is not a theorem of ZFC + “there exists at least one inaccessible cardinal”.

Theorem 5.3.15. If there exists an inaccessible cardinal, then there exists a countable, transitive model of ZFC.

Proof. Let λ be an inaccessible cardinal. Then (R_{λ}, ∈|R_{λ}) is a model of ZFC. By the Löwenheim-Skolem Theorem, there exists a countable set A ⊆ R_{λ} such that (A, ∈|A) is an elementary submodel of (R_{λ}, ∈|R_{λ}). Thus (A, ∈|A) is a countable, well-founded, extensional model of ZFC. By Theorem 5.3.2, (A, ∈|A) is isomorphic to a transitive model (T, ∈|T). Thus (T, ∈|T) is a countable, transitive model of ZFC.

Exercise 5.3.16. Let λ be an inaccessible cardinal. Prove that there exists a limit ordinal δ < λ such that (R_{δ}, ∈|R_{δ}) is an elementary submodel of (R_{λ}, ∈|R_{λ}).

5.4 Constructible Sets

Recall that, if T is any transitive, pure, well-founded set, Def(T) is the set of all subsets of T that are definable over T (i.e., over (T, ∈|T)) allowing parameters from T.

Definition 5.4.1. By transfinite recursion we define L_{α}, α ∈ Ord, as follows:

L_{0} = ∅
L_{α+1} = Def(L_{α})
L_{δ} = ⋃_{α<δ} L_{α}  for limit ordinals δ .

A set X is said to be constructible if X ∈ L_{α} for some ordinal α. The class of all constructible sets is denoted L.

Lemma 5.4.2. For all ordinals α, L_{α} is a transitive, pure, well-founded set, and L_{α} ⊆ R_{α}.

Proof. For any transitive, pure, well-founded set T, we have T ⊆ Def(T) ⊆ P(T) and hence Def(T) is again a transitive, pure, well-founded set. With these observations, the lemma follows easily by transfinite induction on α.

Lemma 5.4.3. For all ordinals α, we have α = L_{α} ∩ Ord.

Proof. If T is any transitive, pure, well-founded set, then for any a ∈ T we have that a is an ordinal (i.e., a von Neumann ordinal) if and only if T satisfies “a is transitive and (a, ∈|a) is a linear ordering”. Thus T ∩ Ord ∈ Def(T). With this observation, the lemma follows easily by transfinite induction on (von Neumann) ordinals α.

We are going to show that the constructible sets form a model of ZFC.

Some of the axioms of ZFC are straightforwardly verified in L using Lemma 5.3.5. For instance, the Union Axiom holds in L because x ∈ L_{α} implies ⋃ x ∈ L_{α}. The Pairing Axiom holds in L because x, y ∈ L_{α} implies {x, y} ∈ L_{α+1}. The Empty Set Axiom holds in L because ∅ ∈ L_{1}. The Axiom of Infinity holds in L because ω ∈ L_{ω+1}. The Axioms of Extensionality and Foundation hold in L because L is transitive and consists of pure, well-founded sets.

To show that the Power Set Axiom holds in L, let X be any constructible set. For each Y ∈ P(X) ∩ L put ρ(Y) = the least β such that Y ∈ L_{β}. Put α = sup{ρ(Y) | Y ∈ P(X) ∩ L}. Thus P(X) ∩ L ⊆ L_{α}. Hence P(X) ∩ L is definable over L_{α}; namely, it is the set of all Y ∈ L_{α} such that L_{α} satisfies Y ⊆ X. Hence P(X) ∩ L ∈ Def(L_{α}) = L_{α+1}. We have now shown that for all X ∈ L, P(X) ∩ L ∈ L. From this it follows by Lemma 5.3.5 that the Power Set Axiom holds in L.

To show that Comprehension and Replacement hold in L, we shall need the following lemmas.

Lemma 5.4.4. Let f_{1}, …, f_{k} be functions from Ord to Ord. Then there exist arbitrarily large ordinals α such that α is closed under f_{1}, …, f_{k}, i.e., f_{i}(β) < α for all β < α, 1 ≤ i ≤ k.

Proof. Given an ordinal γ, define an increasing sequence of ordinals α_{n}, n ∈ ℕ inductively by α_{0} = γ, α_{n+1} = max(α_{n} + 1, sup{f_{i}(β) | β < α_{n}, 1 ≤ i ≤ k}). Putting α = sup{α_{n} | n ∈ ℕ} we see that α > γ and α is closed under f_{1}, …, f_{k}.

Lemma 5.4.5 (reflection). Let F (x_{1}, …, x_{n}) be a formula of L_{∈} with free variables x_{1}, …, x_{n}. Then there exist arbitrarily large ordinals α such that, for all a_{1}, …, a_{n} ∈ L_{α}, L satisfies F (a_{1}, …, a_{n}) if and only if L_{α} satisfies F (a_{1}, …, a_{n}).

Proof. Replacing ∀ by ¬ ∃¬ as necessary, we may safely assume that F contains no occurrences of ∀. Now let ∃y G_{i}, i = 1, …, k be a list of the subformulas of F of the form ∃y G. Write G_{i} ≡ G_{i}(y, x_{i1}, …, x_{in_{i}}) where x_{i1}, …, x_{in_{i}} are the free variables of ∃y G_{i}. For a_{1}, …, a_{n_{i}} ∈ L, put g_{i}(a_{1}, …, a_{n_{i}}) = the least ordinal β such that a_{1}, …, a_{n_{i}} ∈ L_{β} and such that, if L satisfies ∃y G_{i}(y, a_{1}, …, a_{n_{i}}), then L satisfies G_{i}(b, a_{1}, …, a_{n_{i}}) for some b ∈ L_{β}. Define f_{i} : Ord → Ord by f_{i}(β) = sup{g_{i}(a_{1}, …, a_{n_{i}}) | a_{1}, …, a_{n_{i}} ∈ L_{β}}. By the previous lemma, there exist arbitrarily large ordinals α such that that α is closed under f_{1}, …, f_{k}. It is straightforward to verify that such an α has the desired property.

Remark 5.4.6. The proof of the previous lemma used only the following properties of the constructible hierarchy: α ≤ β implies L_{α} ⊆ L_{β}; and L_{δ} = ⋃_{α<δ} L_{α} for limit ordinals δ. Since the R_{α} hierarchy also has these properties, the same lemma holds for the R_{α} hierarchy as well. This has the following interesting consequence: If F_{1}, …, F_{k} is a finite set of sentences that are true in the real world, then there exist arbitrarily large ordinals α such that F_{1}, …, F_{k} are true in R_{α}.

Lemma 5.4.7. L satisfies the Comprehension and Replacement Schemes.

Proof. To show that the Replacement Scheme holds in L, let f : L → L be a function which is definable over L. We must prove that, for all a ∈ L, rng(f↾a) = {f(u) | u ∈ a} also belongs to L. Note first that, since f is definable over L, we have parameters c_{1}, …, c_{n} ∈ L and a formula F (u, v, z_{1}, …, z_{n}) with free variables u, v, z_{1}, …, z_{n} such that, for all u ∈ L, f(u) = the unique v ∈ L such that L satisfies F (u, v, c_{1}, …, c_{n}). Now given a ∈ L, put b = rng(f↾a). We must show that b ∈ L. Let β be an ordinal so large that a, c_{1}, …, c_{n} ∈ L_{β} and b ⊆ L_{β}. By Reflection, let α be such that α > β and, for all u, v ∈ L_{α}, L satisfies F (u, v, c_{1}, …, c_{n}) if and only if L_{α} satisfies F (u, v, c_{1}, …, c_{n}). We claim that b is definable over L_{α}. This is clear since

b = {v ∈ L | L satisfies ∃u (u ∈ a ∧ F (u, v, c_{1}, …, c_{n}))}
= {v ∈ L_{α} | L_{α} satisfies ∃u (u ∈ a ∧ F (u, v, c_{1}, …, c_{n}))} .

Thus b ∈ Def(L_{α}) = L_{α+1}, whence b ∈ L. This shows that the Replacement Scheme holds in L. The proof that the Comprehension Scheme holds in L is similar.

We introduce some more abbreviations:

Definition 5.4.8.

1. Const(x) is an abbreviation for a formula asserting that a given pure, wellfounded set x is constructible. In more detail, Const(x) asserts the existence of a transfinite sequence of sets ⟨L_{β}⟩_{β≤α} such that L_{β} = ⋃{Def(L_{γ}) | γ < β} for all β ≤ α, and x ∈ L_{α}.

2. Recall that V is the class of all pure, well-founded sets, and L is the class of all constructible sets. We use V = L to abbreviate ∀x Const(x). Thus V = L is a sentence asserting that all pure, well-founded sets are constructible.

Theorem 5.4.9. The class L of constructible sets satisfies the ZF axioms plus V = L.

Proof. The above lemmas show that L satisfies the ZF axioms. It is tedious but straightforward to show that L satisfies V = L.

Lemma 5.4.10. For all ordinals α ≥ ω, we have |L_{α}| = |α|.

Proof. By Lemma 5.2.6 we have |L_{ω}| = ℵ_{0} and, for α ≥ ω, |L_{α+1}| = |Def(L_{α})| = |L_{α}|. From this the lemma easily follows by induction on α ≥ ω.

Theorem 5.4.11. The class L of constructible sets satisfies the Axiom of Choice.

Proof. Lemma 5.4.10 implies that each L_{α} is well-orderable. Refining the proof of Lemma 5.4.10, we can explicitly define by transfinite recursion a function F : Ord → V such that, for all ordinals α, F (α) is a well-ordering of L_{α}. Since the definition of F is explicit, its validity does not depend on the Axiom of Choice. Hence by Theorem 5.4.9 the definition of F can be carried out within L. In particular L satisfies that each L_{α} is well-orderable. Hence by Remark 4.5.3 L satisfies the Axiom of Choice. This argument actually shows that the Axiom of Choice follows from ZF plus V = L.

Our remaining goal with respect to constructible sets is to show that L satisfies the GCH.

Lemma 5.4.12. There is a sentence S of L_{∈} with the following property. For all transitive sets A, A satisfies S if and only if A = L_{α} for some limit ordinal α.

Proof. The construction of the sentence S is straightforward but tedious. Roughly speaking, S is identical with the sentence V = L of Definition 5.4.8. For details of the construction of S, see Boolos and Putnam, “Degrees of unsolvability of constructible sets of integers,” Journal of Symbolic Logic, Volume 33, 1968, pages 497–513.

Lemma 5.4.13. If a is any constructible subset of ω, then a ∈ L_{α} for some countable ordinal α. More generally, if a ∈ P(κ) ∩ L where κ is an infinite cardinal, then a ∈ L_{α} for some ordinal α such that |L_{α}| = κ.

Proof. Let κ be an infinite cardinal. Suppose that a ⊆ κ and a is constructible. Let δ > κ be a limit ordinal such that a ∈ L_{δ}. By the Generalized Löwenheim/- Skolem Theorem (Theorem 5.2.11), we can find a set A ⊆ L_{δ} such that κ ∪ {a} ⊆ A, |A| = κ, and (A, ∈|A) is an elementary submodel of (L_{δ}, ∈|L_{δ}). By Theorem 5.3.2 and Lemma 5.4.12, we have (A, ∈|A) ≅ (L_{α}, ∈|L_{α}) for some limit ordinal α. Since κ ∪ {a} is a transitive subset of A, it follows by another application of Theorem 5.3.2 that κ ∪ {a} ⊆ L_{α}. In particular a ∈ L_{α}. Clearly |L_{α}| = κ, and this completes the proof.

Lemma 5.4.14. For any infinite cardinal κ, we have |P(κ) ∩ L| ≤ κ^{+}.

Proof. From the previous lemma we have P(κ) ∩ L ⊆ L_{κ^{+}}. The desired conclusion is immediate, since |L_{κ^{+}}| = |κ^{+}|.

Theorem 5.4.15. The class L of constructible sets satisfies the Generalized Continuum Hypothesis.

Proof. Since L satisfies the axioms of set theory, the proof of the previous lemma can be carried out within L. Thus for all infinite cardinals κ of L, we have within L that |P(κ)| = κ^{+}, hence 2^{κ} = κ^{+}. This proves the theorem.

Theorem 5.4.16.

1. If ZF has a transitive model, then so does ZFC + GCH.

2. If ZF is consistent, then so is ZFC + GCH.

Proof. Let A be a transitive model of ZF. Within A we can carry out the definition of L to obtain a transitive submodel B (sometimes called an “inner model”) consisting of the constructible sets of A. (It can be shown that B = L_{α} where α is the least ordinal that is not an element of A.) The proofs of theorems 5.4.9, 5.4.11, and 5.4.15 then show that B is a model of ZF plus V = L plus the Axiom of Choice plus the GCH. This proves the first part. The proof of the second part is similar, starting with a model (A, E) that is not necessarily transitive.

Remark 5.4.17. The previous theorem, due to Gödel 1939, is one of the most significant achievements of axiomatic set theory. The second part is sometimes described as a relative consistency result: ZFC + GCH is consistent relative to ZF.

5.5 Forcing

Let M be a countable transitive model of ZFC. Let P = (P, ≤) be a partially ordered set belonging to M. We say that p, q ∈ P are compatible if there exists r ∈ P such that r ≤ p and r ≤ q. If p, q ∈ P are incompatible, we write p ⊥ q.

Definition 5.5.1. A filter on P is a set G ⊆ P such that

1. p, q ∈ G implies ∃r ∈ G (r ≤ p, q);

2. p ∈ G, p ≤ q imply q ∈ G.

Definition 5.5.2. D ⊆ P is dense open if

1. ∀p ∈ P ∃q ≤ p (q ∈ D);

2. ∀p ∈ D ∀q ≤ p (q ∈ D).

Definition 5.5.3. A filter G ⊆ P is said to be M-generic if G ∩ D ≠ ∅ for all dense open D ⊆ P such that D ∈ M.

Lemma 5.5.4. Given p ∈ P we can find an M-generic filter G ⊆ P such that p ∈ G.

Proof. Let {D_{n} | n ∈ ℕ} be an enumeration of {D ∈ M | D dense open in P }. Put p_{0} = p and, given p_{n}, let p_{n+1} ≤ p_{n} be such that p_{n+1} ∈ D_{n}. It is easy to verify that G = {q ∈ P | ∃n (p_{n} ≤ q)} is an M-generic filter.

Definition 5.5.5. Let G be an M-generic filter. We put

M[G] = {a_{G} | a ∈ M},

where

a_{G} = {b_{G} | (p, b) ∈ a for some p ∈ G}.

Remark 5.5.6. Think of each a ∈ M as a “name” for a_{G} ∈ M[G]. We shall show that M[G] is a countable transitive model of ZFC containing M.

Lemma 5.5.7. M[G] is a countable transitive set. We have M[G] ⊇ M ∪ {G}, and Ord ∩ M[G] = Ord ∩ M.

Proof. It is obvious from the definition that M[G] is a countable transitive set. For all a ∈ M we have a = (ȧ)_{G}, where ȧ = P × {ḃ | b ∈ a}. We also have G = (Ġ)_{G}, where Ġ = {(p, ṗ) | p ∈ P }. Thus M ∪ {G} ⊆ M[G], and from this it follows that Ord ∩ M ⊆ Ord ∩ M[G]. On the other hand, for each a ∈ M we clearly have rank(a) ≥ rank(a_{G}), hence Ord ∩ M ⊇ Ord ∩ M[G].

A major result is:

Theorem 5.5.8. M[G] is a countable transitive model of ZFC.

Remark 5.5.9. The proof of Theorem 5.5.8 is long and employs a new method known as forcing. However, some parts of the proof are easy and do not require forcing.

For example, given a, b ∈ M, put c = P × {a, b}, then c_{G} = {a_{G}, b_{G}}. This shows that M[G] satisfies the Pairing Axiom. Also, M[G] satisfies the Axiom of Infinity because ω = (ω̇)_{G} ∈ M[G]. Furthermore, M[G] satisfies Extensionality and Foundation automatically, because M[G] is a transitive set.

So far we have not used the assumption that G is an M-generic filter.

In order to prove the rest of Theorem 5.5.8, we now introduce the method of forcing.

Definition 5.5.10. The forcing language consists of binary relation symbols ∈ and = plus constant symbols a for each a ∈ M. Sentences of the forcing language are of the form F (a_{1}, …, a_{n}), where F (x_{1}, …, x_{n}) is a formula of L_{∈} with free variables x_{1}, …, x_{n}, and a_{1}, …, a_{n} ∈ M. We have M[G] ⊧ F (a_{1}, …, a_{n}) if and only if F (a_{1}, …, a_{n}) is true in M[G], where quantifiers are interpreted as ranging over M[G], and a_{1}, …, a_{n} are interpreted as (a_{1})_{G}, …, (a_{n})_{G} respectively.

Definition 5.5.11 (forcing). Let p ∈ P and let F be a sentence of the forcing language. We say that p ∥− F (read p forces F) if and only if M[G] ⊧ F for all M-generic filters G such that p ∈ G.

Lemma 5.5.12 (the extension lemma). If p ∥− F and q ≤ p, then q ∥− F.

Proof. This is obvious, because q ∈ G, q ≤ p imply p ∈ G.

Lemma 5.5.13 (definability of forcing). For each formula F (x_{1}, …, x_{n}) there is a formula F^{∗}(p, x_{1}, …, x_{n}) such that, for all p ∈ P and a_{1}, …, a_{n} ∈ M,

p ∥− F (a_{1}, …, a_{n}) if and only if M ⊧ F^{∗}(p, a_{1}, …, a_{n}).

Lemma 5.5.14 (forcing equals truth). M[G] ⊧ F if and only if ∃p ∈ G (p ∥− F).

Proof. We shall prove Lemmas 5.5.13 and 5.5.14 by simultaneous induction on the number of connectives and quantifiers in F. We assume that F contains only ∧, ¬, and ∀ (not ∨, ⇒, ⇔, ∃).

For the base step, we need to find formulas ∈^{∗}(p, x, y) and =^{∗}(p, x, y) of L_{∈} defining the relations p ∥− a ∈ b and p ∥− a = b, respectively, over M. The formulas ∈^{∗} and =^{∗} are defined by a rather complicated simultaneous transfinite recursion within M. The properties

p ∥− a ∈ b if and only if M ⊧ ∈^{∗}(p, a, b)

and

p ∥− a = b if and only if M ⊧ =^{∗}(p, a, b)

are proved by transfinite induction on rank(a) and rank(b). We omit the details. For the inductive step, note that

p ∥− F_{1} ∧ F_{2} if and only if p ∥− F_{1} and p ∥− F_{2},

and

p ∥− ∀x F (x) if and only if p ∥− F (a) for all a ∈ M.

Thus we may define (F_{1} ∧ F_{2})^{∗} = F_{1}^{∗} ∧ F_{2}^{∗} and (∀x F (x))^{∗} = ∀x F^{∗}(x). This takes care of ∧ and ∀. For ¬, we claim that

p ∥− ¬ F if and only if ¬ ∃q ≤ p (q ∥− F).

To see this, assume the right hand side. Let G be generic with p ∈ G. To show M[G] ⊧ ¬ F. Otherwise, M[G] ⊧ F so let q ∈ G be such that q ∥− F. Let r ∈ G be such that r ≤ p and r ≤ q. Then r ≤ p and r ∥− F, contradicting our assumption. For the converse, assume the left hand side. Suppose q ≤ p, q ∥− F. Let G be generic such that q ∈ G. Then M[G] ⊧ F. Also p ∈ G since q ≤ p. Therefore p does not force ¬ F, contradicting our assumption.

Thus, for definability of forcing, we may take

(¬ F)^{∗}(p, a_{1}, …, a_{n}) ≡ ¬ (∃q ≤ p) F^{∗}(q, a_{1}, …, a_{n}).

For focing equals truth, suppose M[G] ⊧ ¬ F. To show (∃p ∈ G) p ∥− ¬ F. Put D = {p | p ∥− F or p ∥− ¬ F }. Clearly D is dense open. By definability of forcing, D ∈ M. Let p ∈ D ∩ G. If p ∥− F, then M[G] ⊧ F, a contradiction. Hence p ∥− ¬ F.

We now proceed to the proof of Theorem 5.5.8.

Lemma 5.5.15. M[G] ⊧ the Comprehension Scheme.

Proof. Given a, a_{1}, …, a_{n} ∈ M, to find c ∈ M such that

M[G] ⊧ ∀u (u ∈ c ⇔ (u ∈ a ∧ F (u, a_{1}, …, a_{n}))).

Put

c = {(p, b) | b ∈ ⋃ ⋃ a and p ∥− b ∈ a ∧ F (b, a_{1}, …, a_{n})}.

Then c ∈ M, by Definability of Forcing in M. Then, by the Forcing Equals Truth Lemma, we have

c_{G} = {b_{G} | b ∈ ⋃ ⋃ a and M[G] ⊧ F (b, a_{1}, …, a_{n})}.

Lemma 5.5.16. M[G] ⊧ the Power Set Axiom.

Proof. Given a ∈ M, put c = P × P(P × ⋃ ⋃ a) ∩ M. We claim that

c_{G} ⊇ P(a_{G}) ∩ M[G].

To see this, given e_{G} ∈ M[G], let d = {(p, b) ∈ P × ⋃ ⋃ a | p ∥− b ∈ e ∩ a}. By definability of forcing, d ∈ M, hence d_{G} ∈ c_{G}. Moreover d_{G} = e_{G} ∩ a_{G}. This proves our claim. The Power Set Axiom follows by Comprehension in M[G], since P(a_{G}) ∩ M[G] = {d_{G} ∈ c_{G} | M[G] ⊧ d ⊆ a}.

Lemma 5.5.17. M[G] ⊧ the Union Axiom.

Proof. This is similar to the Power Set Axiom. Given a ∈ M put

c = P × ⋃ ⋃ ⋃ ⋃ a.

Then c_{G} ⊇ ⋃ a_{G}, and the Union Axiom follows by Comprehension in M[G].

Lemma 5.5.18. M[G] ⊧ the Replacement Scheme.

Proof. It suffices to prove that M[G] ⊧ the Bounding Scheme:

∀w_{1} ⋯ w_{n} [ ∀u ∃! v F (u, v, w_{1}, …, w_{n}) ⇒ ∀x ∃y ∀u ∈ x ∃v ∈
y F (u, v, w_{1}, …, w_{n}) ].

This is because Bounding plus Comprehension implies Replacement.

Given a, a_{1}, …, a_{n} ∈ M, let c ∈ M be such that, for all (p, b) ∈ P × ⋃ ⋃ a, if there exists d ∈ M such that p ∥− F (b, d, a_{1}, …, a_{n}), then c contains such a d. We then have

M[G] ⊧ ∀u ∃! v F (u, v, w_{1}, …, w_{n}) ⇒ ∀u ∈ a ∃v ∈ c′ F (u, v, a_{1}, …, a_{n}),

where c′ ∈ M, namely c′ = P × c. Thus M[G] ⊧ Bounding.

Lemma 5.5.19. M[G] ⊧ the Axiom of Choice.

Proof. Given a_{G} ∈ M[G], let f ∈ M map an ordinal α onto ⋃ ⋃ a. Since M ⊆ M[G], we have f = (ḟ)_{G} ∈ M[G]. Composing f with the function b ↦ b_{G}, we obtain in M[G] a mapping of α = (α̇)_{G} onto {b_{G} | b ∈ ⋃ ⋃ a} ⊇ a_{G}. Thus a_{G} is well orderable in M[G].

The proof of Theorem 5.5.8 is now complete.

As a first application, we prove the independence of V = L.

Theorem 5.5.20. There exists a countable transitive model of ZFC plus V ≠ L.

Proof. Let M be a countable transitive model of ZFC. Let P be the set of finite partial functions from ω into 2 = {0, 1}. Partially order P by putting p ≤ q if and only if p extends q. Then P ∈ M. Let G be an M-generic filter on P. By Theorem 5.5.8 we have M[G] ⊧ ZFC.

Note that p, q ∈ P are compatible if and only if p ∪ q ∈ P. Thus g = ⋃ G is a partial function from ω into 2. We claim that dom(g) = ω. To see this, given n ∈ ω, put D_{n} = {p ∈ P | n ∈ dom(g)}. Clearly D_{n} is dense open, and D_{n} ∈ M. Letting p ∈ G ∩ D_{n}, we see that n ∈ dom(p), hence n ∈ dom(g).

Thus g : ω → 2 and g ∈ M[G]. We claim that g ∉ M. If g ∈ M, then clearly G = {p ∈ P | p ⊆ g} ∈ M, so let D = P \ G = {p ∈ P | p ∉ G}. Then D ∈ M, and clearly D is dense open. But G ∩ D = ∅, a contradiction.

We claim that M[G] ⊧ V ≠ L. In fact,

M[G] ⊧ ġ ∉ L ∧ ġ : ω → 2

where (ġ)_{G} = g.

5.6 Independence of CH

As in the previous section, let M be a countable transitive model of ZFC, let P be a partially ordered set belonging to M, and let G be an M-generic filter on P. We begin with a discussion of cardinal collapsing and cardinal preservation in M[G].

Remark 5.6.1. Clearly every cardinal of M[G] is a cardinal of M. However, the converse does not always hold. Cardinals of M can be collapsed in M[G].

Example 5.6.2. Let κ be an uncountable cardinal of M. Let P be the set of finite partial functions from ω into κ, ordered by p ≤ q if and only if p extends q. Let G be an M-generic filter on P. Put g = ⋃ G. As in the proof of Theorem 5.5.20, we see that g : ω → κ.

We claim that rng(g) = κ. To see this, give α < κ, put D_{α} = {p ∈ P | α ∈ rng(p)}. Clearly D_{α} ∈ M. Because ω is infinite, D_{α} is dense open. Letting p ∈ G ∩ D_{α}, we see that α ∈ rng(p), hence α ∈ rng(g).

Thus g ∈ M[G] maps ω onto κ. It follows that M[G] ⊧ “κ̇ is a countable ordinal”. In particular κ is not a cardinal of M[G].

On the other hand, cardinals of M are often preserved, i.e., remain cardinals in M[G].

Lemma 5.6.3. Suppose M ⊧ “κ is a cardinal > |P |”. Then M[G] ⊧ “κ is a cardinal”. In other words, all cardinals > |P | in M are preserved in M[G].

Proof. Suppose not, say f_{G} : λ → κ, λ < κ, rng(f_{G}) = κ, f_{G} ∈ M[G]. Then in M we have

∀α < κ ∃β < λ ∃p ∈ P (p ∥− f | λ̇ → κ̇ and p ∥− f(β̇) = α̇).

By the Pigeonhole Principle, we can find p ∈ P, β < λ, α_{1} < α_{2} < κ such that p ∥− f : λ̇ → κ̇ and p ∥− f(β̇) = α̇_{1} and f(β̇) = α̇_{2}. This is a contradiction.

Definition 5.6.4. An antichain in P is a set A ⊆ P such that the elements of A are pairwise incompatible. P is said to have the countable chain condition (c.c.c.) if every antichain of P is countable.

Lemma 5.6.5. Suppose M ⊧ P is c.c.c. Then all cardinals of M are preserved in M[G].

Proof. Suppose not, say κ > λ, M ⊧ “κ is a cardinal”, M[G] ⊧ “f maps λ̇ onto κ̇”. Fix p ∈ P such that p ∥− “f maps λ̇ onto κ̇”. Reasoning within M, for α < κ and β < λ say that α is a possible value of f(β) if ∃q ≤ p (q ∥− f(β̇) = α̇). Let X_{β} = {α | α is a possible value of f(β)}. Note that κ = ⋃_{β<λ} X_{β}. Therefore, some X_{β} is uncountable. Fix such a β. For each α ∈ X_{β} let q_{α} ≤ p be such that q_{α} ∥− f(β̇) = α̇. Note that α_{1}, α_{2} ∈ X_{β}, α_{1} ≠ α_{2} implies q_{α_{1}} ⊥ q_{α_{2}}. Thus A_{β} = {q_{α} | α ∈ X_{β}} is an uncountable antichain in P. This contradicts the assumption that P is c.c.c.

We now proceed to the independence of the Continuum Hypothesis.

Definition 5.6.6. A Δ-system is an indexed family of sets ⟨X_{i}⟩_{i∈I} such that, for some fixed set D, X_{i} ∩ X_{j} = D for all i, j ∈ I, i ≠ j.

Lemma 5.6.7 (the Δ-system lemma). Any uncountable family of finite sets contains an uncountable subfamily which is a Δ-system.

Proof. Let ⟨X_{i}⟩_{i∈I} be an uncountable family of finite sets. We may safely assume that |I| = ℵ_{1} and that ⋃_{i∈I} X_{i} ⊆ ω_{1}. Passing to an uncountable subfamily, we may assume that ∃n ∀i ∈ I |X_{i}| = n. For each i ∈ I, let X_{i}(1) < ⋯ < X_{i}(n) be the elements of X_{i}.

Case 1: For each k = 1, …, n, {X_{i}(k) : i ∈ I} is countable. In this case, ⋃_{i∈I} X_{i} is countable. Hence, by passing to an uncountable subfamily, we may assume X_{i} = X_{j} for all i, j ∈ I. In particular, we have an uncountable Δ-system.

Case 2: Otherwise. Let k be as small as possible such that {X_{i}(k) | i ∈ I} is uncountable. Then, for each l < k, {X_{i}(l) | i ∈ I} is countable. By passing to an uncountable subfamily, we may assume X_{i}(l) = X_{j}(l) for all l < k and all i, j ∈ I. Thus we have a fixed finite set D = {X_{i}(l) | 1 ≤ l < k} for all i ∈ I. Since {X_{i}(k) | i ∈ I} is uncountable, we may use transfinite recursion to define a function f : ω_{1} → I such that, for each α < ω_{1}, X_{f(α)}(k) > sup_{β<α} X_{f(β)}(n). Then ⟨X_{f(α)}⟩_{α<ω_{1}} is an uncountable Δ-system contained in ⟨X_{i}⟩_{i∈I}.

Lemma 5.6.8. Let X be any set. Let P be the set of finite partial functions from X into {0, 1}, ordered by putting p ≤ q if and only if p ⊇ q. Then P is c.c.c.

Proof. Suppose not. Let ⟨p_{i}⟩_{i∈I} be an uncountable antichain in P. By the Δ-system lemma, we may pass to a subfamily such that ⟨dom(p_{i})⟩_{i∈I} is a Δsystem. Say dom(p_{i})∩dom(p_{j}) = D for all i, j ∈ I, i ≠ j. There are only finitely many functions from D into {0, 1}, so by passing to an uncountable subfamily we may assume that p_{i}↾D = p_{j}↾D for all i, j ∈ I. Then for all i, j ∈ I we have that p_{i} ∪ p_{j} is a function, hence p_{i} and p_{j} are compatible, a contradiction.

Theorem 5.6.9. Let M be a countable transitive model of ZFC. Let κ be an uncountable cardinal of M. Then there exists a countable transitive model M′ of ZFC extending M such that (1) M′ satisfies 2^{ℵ_{0}} ≥ κ, and (2) M′ has the same ordinals and cardinals as M.

Proof. Let P be the set of finite partial functions from κ × ω into {0, 1}. Let G be an M-generic filter on P. By Lemma 5.5.7 and Theorem 5.5.8, M[G] is a countable transitive model of ZFC which includes M and has the same ordinals as M. By Lemma 5.6.8 P is c.c.c. By Lemma 5.6.5 M[G] has the same cardinals as M.

Put g = ⋃ G. As in the proof of Theorem 5.5.20 we see that g ∈ M[G] and g : κ × ω → {0, 1}. For α < κ define g_{α} : ω → {0, 1} by g_{α}(n) = g((α, n)). We claim that g_{α} ≠ g_{β} for all α < β < κ. To see this, let D_{αβ} be the set of p ∈ P such that p((α, n)) ≠ p((β, n)) for some n ∈ ω such that (α, n), (β, n) ∈ dom(p). Clearly D_{αβ} ∈ M and is dense open. Hence G ∩ D_{αβ} ≠ ∅. Hence g_{α} ≠ g_{β}.

It is now clear that M[G] ⊧ 2^{ℵ_{0}} ≥ κ̇. Thus we may take M′ = M[G].

Topics in Set Theory

6.1 Stationary Sets

Definition 6.1.1. Let S be a set of ordinals. We say that S is unbounded in a limit ordinal δ if sup(S ∩ δ) = δ. We say that S is closed in κ if S ⊆ κ and, for all limit ordinals δ < κ, if S is unbounded in δ then δ ∈ S. A closed unbounded set in κ (sometimes called a club of κ) is any subset of κ which is closed in κ and unbounded in κ.

Lemma 6.1.2. Let κ be a regular uncountable cardinal.

1. If C_{i}, i ∈ I, is a collection of closed unbounded sets in κ, and if |I| < κ, then ⋂_{i∈I} C_{i} is again a closed unbounded set in κ.

2. If C_{α}, α < κ is a collection of closed unbounded sets in κ indexed by the ordinals less than κ, then the diagonal intersection

△_{α<κ}C_{α} = {β < κ | β ∈ C_{α} for all α < β}

is again a closed unbounded set in κ.

Proof. Straightforward.

Definition 6.1.3. Let κ be a regular uncountable cardinal. A set S ⊆ κ is said to be stationary in κ if S ∩ C ≠ ∅ for every closed unbounded set C in κ.

Lemma 6.1.4. Let κ be a regular uncountable cardinal, and let S ⊆ κ be stationary in κ. Suppose S = ⋃_{i∈I} S_{i} where |I| < κ. Then S_{i} is stationary for some i ∈ I.

Proof. Suppose the conclusion fails. Then for each i ∈ I let C_{i} be a closed unbounded set such that S_{i} ∩ C_{i} = ∅. By Lemma 6.1.2.1, C = ⋂_{i∈I} C_{i} is a closed unbounded set. Since S is stationary, S ∩ C is nonempty, say α ∈ S ∩ C. Then for each i ∈ I we have α ∉ S_{i}, a contradiction.

Theorem 6.1.5 (Fodor’s Theorem). Let κ be a regular uncountable cardinal, and let S ⊆ κ be stationary in κ. Suppose f : S → κ is such that f(α) < α for all α ∈ S. Then f is constant on a stationary set. In other words, there exist a stationary S_{0} ⊆ S and a β_{0} < κ such that f(α) = β_{0} for all α ∈ S_{0}.

Proof. Similar to the proof of the previous lemma, using 6.1.2.2 instead of 6.1.2.1. The details are left as an exercise for the reader.

Theorem 6.1.6. For any regular uncountable cardinal κ, there exists a stationary set S ⊆ κ such that κ \ S is also stationary.

Proof. …

We state without proof the following theorem of Solovay.

Theorem 6.1.7. Let κ be a regular uncountable cardinal. Any stationary set S ⊆ κ can be decomposed into κ pairwise disjoint stationary sets.

6.2 Large Cardinals

Definition 6.2.1 (hyperinaccessible cardinals). For each n < ω we define a class of cardinals called the n-hyperinaccessible cardinals. We define κ to be 0hyperinaccessible if it is inaccessible. We define κ to be n+1-hyperinaccessible if it is inaccessible and

{λ < κ | λ is n-hyperinaccessible}

is unbounded in κ.

Definition 6.2.2 (Mahlo cardinals). For each n < ω we define a class of cardinals called the n-Mahlo cardinals. We define κ to be 0-Mahlo if it is inaccessible. We define κ to be n+1-Mahlo if it is inaccessible and {λ < κ | λ is n-Mahlo} is stationary in κ.

Exercise 6.2.3. Show that n+1-hyperinaccessible implies n-hyperinaccessible. Show that n+1-Mahlo implies n-Mahlo. Show that 1-Mahlo implies n-hyperinaccessible for all n < ω.

Lemma 6.2.4. Let δ be a limit ordinal. Suppose κ < δ and n < ω. Then κ is n-hyperinaccessible if and only if R_{δ} satisfies “κ is n-hyperinaccessible.” Also, κ is n-Mahlo if and only if R_{δ} satisfies “κ is n-Mahlo.”

Proof. Straightforward.

Theorem 6.2.5.

1. The existence of an n+1-hyperinaccessible cardinal is not provable in ZFC + “for all α there exists κ > α such that κ is n-hyperinaccessible” (assuming this theory is consistent).

2. The existence of an n+1-Mahlo cardinal is not provable in ZFC + “for all α there exists κ > α such that κ is n-Mahlo” (assuming this theory is consistent).

Proof. Straightforward using the previous lemma. Lemma 6.2.6.

1. If κ is a cardinal, then L satisfies “κ is a cardinal.”

2. If κ is a regular cardinal, then L satisfies “κ is a regular cardinal.”

3. If κ is n-hyperinaccessible, then L satisfies “κ is n-hyperinaccessible.”

4. If κ is n-Mahlo, then L satisfies “κ is n-Mahlo.” Proof. Straightforward. Theorem 6.2.7.

1. If ZFC + “there exists an n-hyperinaccessible cardinal” is consistent, then so is ZFC + V = L + “there exists an n-hyperinaccessible cardinal.”

2. If ZFC + “there exists an n-Mahlo cardinal” is consistent, then so is ZFC

+ V = L + “there exists an n-Mahlo cardinal.” Proof. Straightforward using the previous lemma.

6.3 Ultrafilters and Ultraproducts

Definition 6.3.1. Let I be a nonempty set. A filter on I is a set F ⊆ P(I) such that

1. ∅ ∉ F and I ∈ F;

2. if X_{1}, …, X_{n} ∈ F then X_{1} ∩ … ∩ X_{n} ∈ F;

3. if X ∈ F and X ⊆ Y ∈ P(I) then Y ∈ F. Examples 6.3.2.

1. F = {I}.

2. F = {X ⊆ I | X ⊇ X_{0}}, where ∅ ≠ X_{0} ⊆ I. Such an F is called a principal filter.

3. F = {X ⊆ I | X is cofinite, i.e., I \ X is finite} (assuming I is infinite).

4. F = {X ⊆ I | |I \ X| < κ}, where κ is any infinite cardinal ≤ |I|.

5. I = ℝ^{n}, F = {X ⊆ ℝ^{n} | ℝ^{n} \ X has Lebesgue measure 0}. Here we could replace ℝ^{n} by any measure space.

6. I = ℝ^{n}, F = {X ⊆ ℝ^{n} | ℝ^{n} \ X is meager}. Here we could replace ℝ^{n} by any complete metric space.

7. Let I = κ where κ is a regular uncountable cardinal. Then

F = {X ⊆ κ | X ⊇ C for some closed unbounded set C ⊆ κ}

is a filter, known as the closed unbounded filter on κ.

8. Let A be an uncountable set. Put

I = P_{c}(A) = {Y ⊆ A | Y is countable} .

Recall that A^{<ω} is the set of finite sequences of elements of A. Given f : A^{<ω} → A, put

C_{f} = {Y ∈ P_{c}(A) | Y is closed under f, i.e., f[Y^{<ω}] ⊆ Y } .

Then

F_{c}(A) = {X ⊆ P_{c}(A) | X ⊇ C_{f} for some f}

is a filter known as the closed unbounded filter on P_{c}(A).

Definition 6.3.3. Let κ be an infinite cardinal. A filter F is said to be κadditive if ⋂_{i∈I} X_{i} ∈ F whenever X_{i} ∈ F for all i ∈ I, |I| < κ.

Examples 6.3.4.

1. Every filter is finitely additive, i.e., ℵ_{0}-additive.

2. The Lebesgue and Baire filters on ℝ^{n} are countably additive, i.e., ℵ_{1}- additive.

3. For any infinite cardinal κ ≤ |I|, the filter {X ⊆ I | |I − X| < κ} is κ-additive.

4. For any regular uncountable cardinal κ, the closed unbounded filter on κ is κ-additive.

5. For any uncountable set A, the closed unbounded filter on P_{c}(A) is countably additive.

Definition 6.3.5. An ultrafilter on I is a filter U on I such that for all X ⊆ I either X ∈ U or I \ X ∈ U.

Remark 6.3.6. The filters in 6.3.2.3–8 are not ultrafilters. Indeed, it is difficult to find explicit examples of nonprincipal ultrafilters. However, as we shall now show, nonprincipal ultrafilters can be constructed by means of transfinite recursion plus the Axiom of Choice.

Theorem 6.3.7. Any filter F on I can be extended to an ultrafilter U on I.

Proof. Say that G ⊆ P(I) has the finite intersection property (f.i.p.) if Y_{1} ∩…∩ Y_{m} ≠ ∅ for all Y_{1}, …, Y_{m} ∈ G.

By the well-ordering theorem, let κ = |P(I)|, say

P(I) = {X_{α} | α < κ} .

We shall use transfinite recursion to define a sequence of sets F_{α} ⊆ P(I), α ≤ κ, each of which has the f.i.p.

Stage 0. Put F_{0} = F. Note that F has the f.i.p. since it is a filter.

Stage α + 1. Assume inductively that F_{α} has the f.i.p. We claim that at least one of F_{α} ∪ {X_{α}}, F_{α} ∪ {I \ X_{α}} has the f.i.p. Otherwise we would have X_{α} ∩ Y_{1} ∩ … ∩ Y_{m} = ∅, Y_{1}, …, Y_{m} ∈ F_{α}, (I \ X_{α}) ∩ Z_{1} ∩ … ∩ Z_{m} = ∅, Z_{1}, …, Z_{n} ∈ F_{α}. Then Y_{1} ∩ … ∩ Y_{m} ∩ Z_{1} ∩ … ∩ Z_{n} = ∅ so F_{α} does not have the f.i.p., a contradiction. We therefore set

F_{α+1} = \{ \begin{matrix}F_{α} ∪ \{X_{α}\} & if this has the f.i.p., \\ F_{α} ∪ \{I \ X_{α}\} & otherwise. \end{matrix}

Then clearly F_{α+1} has the f.i.p.

Stage δ, where δ is a limit ordinal. Put F_{δ} = ⋃_{α<δ} F_{α}. Clearly this has the f.i.p.

Finally put U = F_{κ} = ⋃_{α<κ} F_{α}. Clearly U has the f.i.p. and for every X ∈ P(I) either X ∈ U or I \ X ∈ U. It follows easily that U is an ultrafilter. This completes the proof.

Lemma 6.3.8. Any principal ultrafilter U on I is of the form

U = {X ⊆ I | i_{0} ∈ X}

for some fixed i_{0} ∈ I.

Proof. Let U be a principal ultrafilter on I. By definition we have

U = {X ⊆ I | X ⊇ X_{0}}

where ∅ ≠ X_{0} ⊆ I. If |X_{0}| ≥ 2, let Y ⊆ I be such that Y ∩ X_{0} ≠ ∅ and (I \ Y) ∩ X_{0} ≠ ∅. Then Y, I \ Y ∉ U, a contradiction. Thus |X_{0}| = 1, i.e., X_{0} = {i_{0}} for some i_{0} ∈ I. This proves the lemma.

Theorem 6.3.9. For every infinite set I there exists a nonprincipal ultrafilter U on I.

Proof. Consider the filter F = {X ⊆ I | I \X is finite}. By Theorem 6.3.7, let U be an ultrafilter on I such that F ⊆ U. For all i_{0} ∈ I we have I \ {i_{0}} ∈ F ⊆ U, hence {i_{0}} ∉ U. Thus U is nonprincipal.

Definition 6.3.10. A structure is a relational structure, i.e., an ordered pair (A, E) where A is a nonempty set and E ⊆ A × A.

Definition 6.3.11 (ultraproduct). Suppose we are given an indexed family of structures ⟨(A_{i}, E_{i})⟩_{i∈I} and an ultrafilter U on the index set I. We are going to define a structure

(A, E) = ∏_{U}⟨(A_{i}, E_{i})⟩_{i∈I}

known as an ultraproduct. Recall that

∏_{i∈I} A_{i} = {f | f : I → ⋃_{i∈I} A_{i}, f(i) ∈ A_{i} for all i ∈ I} .

For f, g ∈ ∏_{i∈I} A_{i} define

\begin{aligned}f ≈ g & ⇔_{def} & f ≈_{U} g \\ & ⇔_{def} & \{i ∈ I | f(i) = g(i)\} ∈ U . \end{aligned}

This is an equivalence relation. We define

[f] =_{def} [f]_{U} =_{def} {g ∈ ∏_{i∈I} A_{i} | f ≈_{U} g}

and

A = ∏_{U}⟨A_{i}⟩_{i∈I} = ∏_{i∈I} A_{i}/U = {[f]_{U} | f ∈ ∏_{i∈I} A_{i}} .

Finally, for f, g ∈ ∏_{i∈I} A_{i}, we define

([f], [g]) ∈ E ⇔_{def} {i ∈ I | (f(i), g(i)) ∈ E_{i}} ∈ U .

Note that this last definition is independent of representatives, i.e., f ≈ f′, g ≈ g′, ([f], [g]) ∈ E imply ([f′], [g′]) ∈ E. Thus E ⊆ A × A is well-defined, and so (A, E) is a structure.

Theorem 6.3.12 (Łoś’s Theorem). Let (A, E) = ∏_{U}⟨(A_{i}, E_{i})⟩_{i∈I} be an ultraproduct. Let ψ(x_{1}, …, x_{k}) be a formula with free variables among x_{1}, …, x_{k}. Then for all [f_{1}], …, [f_{k}] ∈ A we have

⊧_{(A,E)} ψ([f_{1}], …, [f_{k}]) ⇔ {i ∈ I | ⊧_{(A_{i},E_{i})} ψ(f_{1}(i), …, f_{k}(i))} ∈ U .

6.4 Measurable Cardinals

6.5 Ramsey’s Theorem

Index

R_{α}, 87 Δ_{n}^{0} predicate, 44 Π_{n}^{0} predicate, 41 Σ_{n}^{0} predicate, 41 ℵ_{α}, 84 ↓, 23 κ-additive, 117 ω, 75 ω_{α}, 84 ≃, 23 ↑, 23 Łoś’s theorem, 119

Ackermann function, 13, 25, 30, 33, 39 additive, 117 additively indecomposable ordinal, 80 arithmetic, 48

cardinal, 73 language of, 48 ordinal, 75, 79, 80

arithmetical definability, 50–56, 59 arithmetical hierarchy, 41–47, 56 arithmetical truth, 58, 59 axioms

of set theory, 92–96 axiom of choice, 94, 97, 101, 106 axiom of infinity, 94 axiom scheme, 95

Boolean connective, 9, 49 bounded

least number operator, 10 quantifier, 10

Cantor’s theorem, 73 cardinal

hyperinaccessible, 115 inaccessible, 86 limit, 85 Mahlo, 115 regular, 85 singular, 86 strong limit, 85 successor, 85 uncountable, 85 weakly inaccessible, 86

cardinal arithmetic, 73

cardinal number, 71–74, 81–86 cases

definition by, 28, 63 Cauchy sequence, 90 CH, 85, 97 characteristic function, 9 Chinese remainder theorem, 53 Church’s thesis, 33 class, 78 closed, 114 closed unbounded filter, 117 club, 114 cofinality, 86 complete, 46 comprehension, 95, 101 computable function, 17–23 connective

Boolean, 9, 49 propositional, 49

consequence

logical, 97 consistency, 97

relative, 107 constructible set, 103–107 Continuum Hypothesis, 85 continuum hypothesis, 85, 97, 106 Continuum Problem, 85 continuum problem, 85, 97 convergent, 23 countably additive, 117 course-of-values recursion, 12

decidability, 67 Def, 98 definability

arithmetical, 50–56, 59 over the real number system, 60 over a relational structure, 98 over the real number system, 66

defined, 23 definition by cases, 28, 63 dense open set, 107 diagonal intersection, 114 divergent, 23

effective function, 61 enumeration theorem, 28 equivalence relation, 90 extensionality, 92, 94, 97, 100

f.i.p., 118 falsity, 49 filter, 107, 116

closed unbounded, 117 principal, 116

finitely additive, 117 finite intersection property, 118 Fodor’s theorem, 115 forcing, 108 formula, 48, 60, 92 function, 89

computable, 17–23 effective, 61 limit-recursive, 44 number-theoretic, 6 partial, 23 partial recursive, 23 primitive recursive, 6–13, 30 recursive, 23 total, 23

Gödel number of a formula, 57

of a program, 26, 27 GCH, 85, 107 generalized continuum hypothesis, 85,

106

halting problem, 35, 37 Hilbert’s 10th problem, 35 Hilbert’s 17th problem, 61 hyperinaccessible cardinal, 115

inaccessible cardinal, 86, 101–103 index

of a partial recursive function, 26,

27 induction

transfinite, 78 initial ordinal, 82 isomorphism, 74

König’s Theorem, 74

L, 103, 106 Löwenheim/Skolem theorem, 99 language

of arithmetic, 48 of ordered rings, 60 of set theory, 92–96

least number operator, 23

bounded, 10 limit-recursive function, 44 limit cardinal, 85 limit ordinal, 80 linear ordering, 75 logical consequence, 97

Mahlo cardinal, 115 minimization, 24, 30 model, 97

number cardinal, 71–74, 81–86 ordinal, 75, 89

number systems, 90

ordered field, 60 ordered pair, 70, 89 ordering linear, 75 well, 75

ordinal, 75, 89 additively indecomposable, 80 initial, 82 limit, 80 successor, 80 von Neumann, 89

ordinal arithmetic, 75, 79, 80 ordinal number, 75, 89

parameter, 98 parametrization theorem, 36 partial function, 23 partial recursive function, 23, 32 power set, 93, 101 predicate, 9 primitive recursive

function, 6–13, 30 predicate, 9

principal filter, 116 principal function, 43 program, 17 propositional connective, 49 pure set, 87, 92, 93, 96, 97, 102, 104

quantifier, 49

bounded, 10 quantifier elimination, 60, 66

real number system, 60, 90 real world, 92, 93, 97 recursion

course-of-values, 12 primitive, 6 transfinite, 78

recursion theorem, 39 recursively enumerable set, 44 recursive function, 23 reducible, 36 register machine program, 17 regular cardinal, 85 relational structure, 74, 96 relative consistency, 107 replacement, 95, 101 Rice’s theorem, 38 scheme, 95 sentence, 49 set theory

axioms of, 92–96 language of, 92–96 models of, 93, 96, 97, 99–104

singular cardinal, 86 Skolem paradox, 99 Solovay, 115 state, 29 stationary, 114 strong limit cardinal, 85 structure

arithmetic, 48

real number system, 60

relational, 74, 96 successor cardinal, 85 successor ordinal, 80

term, 48 total function, 23 transfinite induction, 78 transfinite recursion, 78 transitive model, 99–103 transitive set, 87, 99 truth

arithmetical, 49, 58, 59

ultrafilter, 117 ultraproduct, 119 unbounded, 114 uncountable cardinal, 85 undecidability, 58 undefined, 23 universal

Σ_{n}^{0} predicate, 45

register machine program, 28 unsolvable problem, 34–39, 58

V, 88 von Neumann ordinal, 89

weakly inaccessible cardinal, 86 well-founded, 75 well-ordering, 75 well-ordering theorem, 81 word problem, 35

Zermelo/Fraenkel set theory, 96 ZF, 96 ZFC, 96