MATH 582, INTRODUCTION TO SET THEORY, WINTER 1999

Answers to Problem Set 10

Problem 1 The given F is clearly a function class. Also, for all sets z, one has F (F (z)) = z, and thus F is one-to-one and onto the class of sets.

Here are some other examples of bijections of the universe onto itself. In the definition of H, A is a fixed arbitrary set.

G(n)  = {n} if n ∈ ω, n ⩾ 1,
G({n}) = n  if n ∈ ω, n ⩾ 1,
G(x)  = x  in all other cases,

H(x) = x ∪ {A} if A ∉ x,_{H(x) = x − {A} if A ∈ x.}

Problem 2 For any set x, one has x ∈′ F^{−1}(∅) iff x ∈ F (F^{−1}(∅)) iff x ∈ ∅. This holds for no x. Moreover, if F is the bijection from Problem 1, then 0 ∈ 1 = F (0), thus 0 ∈′ 0.

Problem 3 Let A and B be any sets such that for all x, x ∈′ A ⟺ x ∈′ B. This means, x ∈ F (A) ⟺ x ∈ F (B). By extensionality (for 𝒰 ), this implies F (A) = F (B), hence, since F is one-to-one, A = B.

Problem 4 We have

x ∈′ B ⟺ x ∈ F (B)  by definition of ∈′
⟺ x ∈ c  by definition of B
⟺ ∃b (x ∈ F (b) ∧ b ∈ F (A)) by definition of union
⟺ ∃b (x ∈′ b ∧ b ∈′ A)  by definition of ∈′.

Thus we have shown

∀A ∃B ∀x [x ∈′ B ⟺ ∃b (x ∈′ b ∧ b ∈′ A)],

which is precisely the union axiom for 𝒰′.

Problem 5 We have c = {F^{−1}(z) | z ⊆ F (A)} = {F^{−1}(z) | z ∈ 𝒫(F (A))}. This is a set by the powerset axiom and replacement. Moreover, we have x ∈′ B iff x ∈ F (B) iff x ∈ c iff F (x) ⊆ F (A) iff x ⊆′ A. Thus, we have shown that

∀A ∃B ∀x (x ∈′ B ⟺ x ⊆′ A),

which is precisely the power set axiom for 𝒰′.

Problem 6 We verify the three properties:

z ∈′ x ∪′ y ⟺ z ∈ F (x ∪′ y)  by definition of ∈′
⟺ z ∈ F (x) ∪ F (y)  by definition of ∪′
⟺ z ∈ F (x) ∨ z ∈ F (y) by definition of union
⟺ z ∈′ x ∨ z ∈′ y  by definition of ∈′.

The reasoning for ∩′ is entirely analogous. Finally

z ∈′ {x}′ ⟺ z ∈ F ({x}′)
⟺ z ∈ {x}
⟺ z = x.

Problem 7 Since η is the range of f, we have ∅′ = f(0) ∈ η = F (A), and thus ∅′ ∈′ A. Also, for any a, if a ∈′ A, then a ∈ F (A) = η, thus a = f(n) for some n. Then a ∪′ {a}′ = f(n^{+}), and thus a ∪′ sa′ ∈ η = F (A), which implies a ∪′ sa′ ∈′ A.

Problem 8 Suppose that x ∈ A_{1}. Let u be such that x = F (u). Then u ∈ F (A) by definition of A_{1} (recall that F is a bijection). This implies u ∈′ A, and hence u ≠ ∅′ by assumption. It follows that x = F (u) ≠ F (∅′) = ∅. This proves the first claim.

Now assume that x, y ∈ A_{1} and x ≠ y. Let u and v be such that x = F (u) and y = F (v). Then u, v ∈ F (A) by definition of A_{1}, hence u, v ∈′ A. Since u ≠ v, we have u ∩′ v = ∅′ by assumption. By definition of ∩′ and ∅′, this means F^{−1}(F (u) ∩ F (v)) = F^{−1}(∅), hence F (u) ∩ F (v) = ∅ since F^{−1} is one-to-one. But this means x ∩ y = ∅, as desired.

Problem 9 We have C ∩′ x = {w}′ iff F^{−1}(F (C) ∩ F (x)) = F^{−1}({w}) iff F (C) ∩ F (x) = {w}, by definition of ∩′, {w}′, and the fact that F is a bijection. But F (C) = C_{1}, so the first claim follows. Further, it follows directly from the definition of A_{1}, and the fact that F is a bijection, that F (x) ∈ A_{1} iff x ∈ F (A) iff x ∈′ A.

Problem 10 In Problem 2, we have seen that the universe 𝒰′ in question satisfies 0 ∈′ 0. But by Theorem 7X, this contradicts regularity. Thus, regularity cannot hold in the universe 𝒰′.