MATH 582, INTRODUCTION TO SET THEORY, WINTER 1999

Answers to Problem Set 7

Problem from Class. Using the replacement axiom, give an alternative proof that A × B = {⟨a, b⟩ | a ∈ A ∧ b ∈ B} is a set, for sets A and B.

The trick is that we must apply the replacement axiom in each component separately. First, for each b ∈ B, we apply the replacement axiom to the set A and the formula ϕ(x, y) ≡ (y = ⟨x, b⟩) to obtain the set A_{b} = {⟨a, b⟩ | a ∈ A}. Then, we can apply the replacement axiom again, this time to the set B and the formula ψ(x, y) ≡ (y = A_{x}), to obtain the set C = {A_{b} | b ∈ B}. Then x ∈ ⋃ C if and only if for some b ∈ B, x ∈ A_{b}, if and only if for some b ∈ B and some a ∈ A, x = ⟨a, b⟩. Thus, ⋃ C = A × B is the desired product.

Problem 7.4 First, notice that the definition of R is equivalent to

mRn ⟺ ϕ(m) <_{L} ϕ(n),

where ϕ : P → P × P is the function ϕ(n) = ⟨f(n), n⟩, and <_{L} is the lexicographic order on P × P. Notice that ϕ is one-to-one.

We prove that R is a well-order by showing two things: (a) <_{L} is a well-order on P × P, and (b) well-orders are reflected by one-to-one functions. The last statement means that if ⟨W, <⟩ is a well-order and ϕ : B → W is a one-to-one function, then the relation R that is defined on B by xRy ⟺ ϕ(x) < ϕ(y) is a well-order on B.

Clearly, from these two statements it follows that R is a well-order.

(a) We know from Problem 3.45 that the lexicographic order <_{L} is a linear order on P × P. To show that <_{L} is a well-order, take any non-empty subset A of P × P. Let A_{0} = {m ∈ P | ∃n.⟨m, n⟩ ∈ A}. Then A_{0} is nonempty, thus it has a least element m_{0}, by the well-order property of P. Now let A_{1} = {n ∈ P | ⟨m_{0}, n⟩ ∈ A}. Then A_{1} is non-empty, thus it has a least element n_{0}. We claim that ⟨m_{0}, n_{0}⟩ is the least element of ⟨A, <_{L}⟩. Clearly, by construction, ⟨m_{0}, n_{0}⟩ ∈ A. Consider any other ⟨m, n⟩ ∈ A. Then m ∈ A_{0}, and thus m_{0} ⩽ m by leastness of m_{0}. There are two cases: either m_{0} < m, in which case ⟨m_{0}, n_{0}⟩ <_{L} ⟨m, n⟩ by definition of the lexicographic order. Or else, m_{0} = m. In the latter case, we have n ∈ A_{1}, and by the leastness of n_{0}, it follows that n_{0} ⩽ n. Again, by the definition of the lexicographic order, this implies ⟨m_{0}, n_{0}⟩ ⩽_{L} ⟨m, n⟩, showing that ⟨m_{0}, n_{0}⟩ is the least element of A. Thus, <_{L} is a well-order on P × P.

(b) Suppose ⟨W, <⟩ is a well-order and ϕ : B → W is a one-to-one function. Define a relation R on B by xRy ⟺ ϕ(x) < ϕ(y). One easily sees that this relation is irreflexive, transitive, and connected: thus it is a linear order. Now if A is a non-empty subset of B, then ϕ[[A]] is a non-empty subset of W, thus it has a least element ϕ(x). This means that for all y ∈ A, ϕ(x) ⩽ ϕ(y), hence xRy. Thus, x is a least element of A, showing that R is a well-order.

The claim follows. Actually, the well-order R resembles that shown in Fig. 45(d).

Problem 7.5 Suppose x ⩽ f(x) does not hold for all x ∈ A; then there is a least x ∈ A such that f(x) < x. By hypothesis, this implies f(f(x)) < f(x), i.e.f(y) < y, where y = f(x). But y < x, contradicting the leastness of x.

Problem 7.7 Let C be a fixed set, and let γ(x, y) be the formula

y = C ∪ ⋃ ⋃ ran x.

Clearly, for every set x, there exists a unique y with γ(x, y). Thus, we can apply transfinite recursion to obtain a function F with domain ω, such that for all n ∈ ω, γ(F ↾ seg n, F (n)), which is to say,

F (n) = C ∪ ⋃ ⋃ ran(F ↾ seg n)
= C ∪ ⋃ ⋃ F [[seg n]].

(a)

F (0) = C ∪ ⋃ ⋃ ∅ = C
F (1) = C ∪ ⋃ ⋃{F (0)} = C ∪ ⋃ C
F (2) = C ∪ ⋃ ⋃{F (0), F (1)} = C ∪ ⋃(C ∪ ⋃ C)
= C ∪ ⋃ C ∪ ⋃ ⋃ C (by Problem 2.21)

Our best guess is that F (n) = C ∪ ⋃ C ∪ … ∪ ⋃^{n} C.

(b) Suppose a ∈ F (n). Then

a ⊆ ⋃ F (n)  by Problem 2.3
= ⋃ ⋃{F (n)}
⊆ C ∪ ⋃ ⋃ F [[seg n^{+}]] because {F (n)} ⊆ F [[seg n^{+}]]
= F (n^{+}).

(c) Let C̄ = ⋃ ran F = ⋃_{n∈ω} F (n). Then C = F (0) ⊆ C̄, and C̄ is transitive: if a ∈ C̄, then a ∈ F (n) for some n ∈ ω, and thus a ⊆ F (n^{+}) by (b), which implies a ⊆ C̄.

Moreover, one can show that C̄ is actually the smallest transitive set containing C. To prove this, one first proves that if C is already a transitive set, then F (n) = C, for all n, and thus C̄ = C. One can prove this claim by transfinite induction on n: for the induction hypothesis, assume that F (x) = C has already been shown for all x ∈ seg n. Then F [[seg n]] ⊆ {C}, and equality holds if and only if n ≠ 0. We have F (n) = C ∪ ⋃ ⋃ F [[seg n]] ⊆ C ∪ ⋃ ⋃{C} = C ∪ ⋃ C = C. The last step follows because C is transitive. On the other hand, clearly C ⊆ F (n), hence C = F (n) as desired.

Next, one proves that C ⊆ D implies C̄ ⊆ D̄; this is again shown by transfinite induction. Now it follows that if C is any set, and D is a transitive set containing C, then C̄ ⊆ D̄ = D. Hence C̄ is contained in any transitive set containing C, as desired. For this reason, C̄ is called the transitive closure of C.

Problem 7.8 Let ϕ(x) be any formula not containing the variable B. (ϕ(x) may contain some other variables). We want to prove the subset axiom

∀A∃B∀x(x ∈ B ⟺ x ∈ A ∧ ϕ(x))

from the other axioms. Consider the formula ψ(x, y) ≡ (x = y ∧ ϕ(y)). Clearly, ψ(x, y_{1}) and ψ(x, y_{2}) implies y_{1} = y_{2} = x, and we can apply the replacement axiom schema to ψ to obtain a set B such that for all y, y ∈ B if and only if there exists x ∈ A such that ψ(x, y). By definition of ψ, we thus have y ∈ B if and only if y ∈ A and ϕ(y), and thus B is the set that the subset axiom requires.

Problem 7.9 First, use the empty set axiom and twice the power set axiom to get the set 𝒫𝒫∅ = {∅, {∅}}. This set has precisely two elements. Given any sets u and v, we can construct the pair set {u, v} by the replacement axiom: Let ψ(x, y) be the formula

(x = ∅ ∧ y = u) ∨ (x = {∅} ∧ y = v).

Clearly, for each x there exists at most one y such that ψ(x, y), so by replacement, there exists a set B such that y ∈ B if and only if ψ(x, y) for some x ∈ {∅, {∅}}, if and only if y ∈ {u, v}.