MATH 582, INTRODUCTION TO SET THEORY, WINTER 1999

Answers to the Second Midterm

Problem 1 For the sake of a contradiction, suppose that D ⊈ B, i.e., the set A = D − B is non-empty. By regularity, there exists a ∈ A such that a ∩ A = ∅. Then a ∈ D, and for all x ∈ a, we have x ∈ D (because D is transitive), but x ∉ A (because a ∩ A = ∅). It follows that x ∈ B for all x ∈ a, and thus a ⊆ B. By hypothesis, we have a ∈ B, contradicting a ∈ A.

Problem 2

(a) Suppose q is a limit of s, and take an arbitrary ϵ > 0. Since q is a limit of s, there exists k ∈ ω such that for all n > k, |s_{n} − q| < ϵ/2. But then, for all m, n > k,

|s_{m} − s_{n}| = |s_{m} − q + q − s_{n}| ⩽ |s_{m} − q| + |q − s_{n}| < ϵ/2 + ϵ/2 = ϵ.

This shows that s is a Cauchy sequence, as desired.

(b) There are many such examples. For instance, consider the decimal expansion of the irrational number \sqrt{2} = 1.41421356 . . .. Let

s_{0} = 1,  s_{1} = 1.4,  s_{2} = 1.41,  s_{3} = 1.414,  s_{4} = 1.4142,

and so forth, i.e., let s_{n} be the decimal expansion of \sqrt{2} cut off after the nth digit. Then s is a Cauchy sequence of rational numbers, but it does not converge to a rational number. If you are looking for a more precise way of stating the definition of this sequence, you may state it as follows: let s_{n} = m/10^{n}, where m is the largest integer that is smaller than \sqrt{2} · 10^{n}. Or: let s_{n} = m/10^{n}, where m is the largest integer such that m^{2} < 2 · 10^{2n}.

Problem 3 Yes, such an F must exist, although it is not necessarily unique. Notice that W can have elements that are neither 0 nor a successor; at such elements, F may be defined arbitrarily. More precisely:

(a) Let γ(f, y) be the formula

“If f is a function with domain seg S(t), for some t ∈ W, then y = g(f(t)). Otherwise, y = a.”

Then for each f, there exists a unique y such that γ(f, y). In particular, γ satisfies the hypothesis of the Transfinite Recursion Theorem Schema. Thus, there exists a unique function F with domain W such that

γ(F |_{seg t}, F (t))

for all t ∈ W. We have γ(F |_{seg 0}, a), which shows that F (0) = a. Also, for any t ∈ W, we have γ(F |_{seg S(t)}, g(F (t))), and thus F (S(t)) = g(F (t)) as desired.

(b) In general, F is not unique. The simplest counterexample is given by W = ω · 2, A = {0, 1}, a = 0, and g(x) = x. Let F_{1}, F_{2} : W → A be given by

F_{1}(x) = 0,  for all x ∈ W,
F_{2}(x) = \{ \begin{matrix}0,  if x < ω, \\ 1,  otherwise. \end{matrix}

Then both F_{1} and F_{2} satisfy the recursion conditions.

Problem 4 Let α ≠ 0 be an ordinal. We distinguish two cases:

Case 1: α has a largest element x. Then for all y ∈ α, y ∈ − x, thus y ∈ x ∪ {x} = x^{+}. This implies α ⊆ x^{+}. Conversely, notice that x ∈ α and, because α is transitive, x ⊆ α, hence x^{+} = x ∪ {x} ⊆ α. Thus we have α = x^{+} is a successor ordinal.

Case 2: α does not have a largest element. We know that ⋃ α ⊆ α because α is a transitive set. Conversely, take any x ∈ α. Since α has no largest element, there exists y with x ∈ y ∈ α, and thus x ∈ ⋃ α. This shows that α ⊆ ⋃ α, and thus α = ⋃ α is a limit ordinal.

To show that α cannot be a successor ordinal and a limit ordinal at the same time, observe that if α = β^{+}, then ⋃ α = ⋃ β^{+} = β ≠ α by Theorem 4E.