MATH 582, INTRODUCTION TO SET THEORY, WINTER 1999

Answers to Problem Set 5

Problem 4.2 Suppose a is a transitive set. Then ⋃(a^{+}) = a ⊆ a^{+} by Theorem 4E. This shows that a^{+} is transitive.

Problem 4.3

(a) Suppose a is a transitive set. To show that 𝒫a is transitive, take any x ∈ y ∈ 𝒫a; it suffices to show that x ∈ 𝒫a. We know x ∈ y ⊆ a, hence x ∈ a. Since a is transitive, this implies x ⊆ a, thus x ∈ 𝒫a, as desired.

(b) Suppose 𝒫a is a transitive set. To show that a is transitive, take any y ∈ a. It suffices to show that y ⊆ a. We know that {y} ⊆ a, hence {y} ∈ 𝒫a. Since 𝒫a is transitive, this implies {y} ⊆ 𝒫a, hence y ∈ 𝒫a, thus y ⊆ a, as desired.

Problem 4.4 Suppose that a is a transitive set. To show that ⋃ a is transitive, take any y ∈ ⋃ a. It will suffice to show that y ⊆ ⋃ a. We know that y ∈ z ∈ a for some z, by definition of union. Thus y ∈ a by transitivity of a, which implies y ⊆ ⋃ a, as desired.

Problem 4.6 Suppose ⋃(a^{+}) = a. To prove that a is transitive, observe that a ⊆ a^{+}, hence ⋃ a ⊆ ⋃(a^{+}) = a by Problem 2.4. This shows a is transitive.

Problem 4.8 Assume f : A → A is one-to-one and c ∈ A − ran f. Define h : ω → A by recursion:

\begin{aligned}h(0) & = & c, \\ h(n^{+}) & = & f(h(n)). \end{aligned}

Remark: First observe that h(n^{+}) ≠ h(0) for all n ∈ ω, since h(n^{+}) is in the range of f, whereas h(0) is not. Also recall from Theorem 4C that every natural number is either 0 or a successor.

To show that h is one-to-one, we have to show that h(n) = h(m) implies n = m, for all n, m ∈ ω. We prove this by induction on n. So let

T = {n ∈ ω | (∀m ∈ ω) h(n) = h(m) ⇒ n = m}.

We show that T is inductive. Base case: Suppose h(0) = h(m). By the above remark, m is not a successor, hence m = 0. Induction step: Assume n ∈ T. To show that n^{+} ∈ T, assume h(n^{+}) = h(m). By the remark, m ≠ 0, so m = k^{+} for some k ∈ ω. Then h(n^{+}) = h(k^{+}) implies f(h(n)) = f(h(k)), which implies h(n) = h(k), since f is one-to-one. By induction hypothesis, h(n) = h(k) implies n = k, and thus n^{+} = k^{+} = m. This shows that T is inductive, and thus that h is one-to-one.

Problem 4.9 To show that C^{∗} = C_{∗}, we show each inclusion seperately. Let

ℬ = {X | A ⊆ X ⊆ B ∧ f[[X]] ⊆ X}.

To prove the left-to-right inclusion, we first claim that f[[C_{∗}]] ⊆ C_{∗}. To prove this, consider any y ∈ f[[C_{∗}]]. Then y = f(x) for some x ∈ C_{∗}. Since C_{∗} = ⋃_{i∈ω} h(i), this implies x ∈ h(i) for some i ∈ ω, by definition of union. It follows that y = f(x) ∈ f[[h(i)]] ⊆ h(i^{+}) ⊆ C_{∗}. Since y was arbitrary, this proves our first claim.

Also, note that A = h(0) ⊆ C_{∗} ⊆ B. Thus, C_{∗} is a member of the set ℬ. But C^{∗} = ⋂ ℬ, and hence C^{∗} ⊆ C_{∗}, which proves the first inclusion.

Before we prove the right-to-left inclusion, notice that for all X, Y ⊆ B, X ⊆ Y implies f[[X]] ⊆ f[[Y]]. This is proved as in Theorem 3K.

We claim that h(n) ⊆ C^{∗} for all n ∈ ω. We prove this by induction: Base case: Since A ⊆ X holds for all X ∈ ℬ, we have A ⊆ ⋂ ℬ, and thus h(0) ⊆ C^{∗}. Induction step: Suppose h(n) ⊆ C^{∗}. Then for all X ∈ ℬ, one has h(n) ⊆ X, and hence, by the above remark, f[[h(n)]] ⊆ f[[X]] ⊆ X. Since this holds for all X ∈ ℬ, we also have f[[h(n)]] ⊆ ⋂ ℬ = C^{∗}. We already know h(n) ⊆ C^{∗}, and thus h(n^{+}) = h(n) ∪ f[[h(n)]] ⊆ C^{∗}. This finishes the induction step.

We have shown that h(n) ⊆ C^{∗} for all n ∈ ω. This implies the desired inclusion C_{∗} = ⋃_{i∈ω} h(i) ⊆ C^{∗}. So the proof is finished.

Problem 4.13 Suppose to the contrary that there are natural numbers m, n ≠ 0 such that m · n = 0. Then m = k^{+} and n = l^{+} for some k, l ∈ ω. We calculate

\begin{aligned}m · n & = & k^{+} · l^{+} \\ & = & k^{+} · l + k^{+} & by (M2) \\ & = & (k^{+} · l + k)^{+} & by (A2), \end{aligned}

Thus, m · n is a successor, a contradiction.

Problem 4.17 First notice that for all m ∈ ω, one has m · 1 = m · 0^{+} = m · 0 + m = 0 + m = m + 0 = m, by definition of 1, (M2), (M1), commutativity of +, and (A1).

We now prove m^{n+p} = m^{n} · m^{p} by induction on p. Base case: For p = 0, we have

m^{n+0} = m^{n}  by (A1)
= m^{n} · 1 by the above remark
= m^{n} · m^{0} by (E1)

Induction step: Suppose the claim holds for p. To show that it holds for p^{+}, we calculate

m^{n+p^{+}} = m^{(n+p)^{+}}  by (A2)
= m^{n+p} · m  by (E2)
= (m^{n} · m^{p}) · m by ind. hyp.
= m^{n} · (m^{p} · m) by associativity of multiplication
= m^{n} · m^{p^{+}}  by (E2).