Solutions to Elements of Set Theory∗
Contents
1 Introduction 1
2 Axioms and Operations 3
3 Relations and Functions 11
3.1 Ordered Pairs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2
...
Solutions to Elements of Set Theory∗
Contents
1 Introduction 1
2 Axioms and Operations 3
3 Relations and Functions 11
3.1 Ordered Pairs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2 Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.3 n-ary Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.4 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.5 Infinite Cartesian Products . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.6 Ordering Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4 Natural Numbers 30
4.1 Inductive Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.2 Peano’s Postulates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.3 Recursion on ω . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.4 Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.5 Ordering on ω . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.6 Review Exercise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
5 Construction of the Real Numbers 42
5.1 Integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
5.2 Rational Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
1 Introduction
Exercise 1.1. Which of the following become true when ∈ is inserted in place of the
blank? Which become true when ⊆ is inserted?
(a) {∅} {∅, {∅}}.
∗by Herbert Enderton. I make no claim to correctness, as I’m just learning as I write these.
11 INTRODUCTION 2
(b) {∅} {∅, {{∅}}}.
(c) {{∅}} {∅, {∅}}.
(d) {{∅}} {∅, {{∅}}}.
(e) {{∅}} {∅, {∅, {∅}}}.
Solution. Choices (a) and (d) become true when ∈ is inserted in place of the blank.
Choices (b) and (c) become true when ⊆ is inserted in place of the blank. Choice (e) is
not true in either case.
Exercise 1.2. Show that not two of the three sets ∅, {∅}, and {{∅}} are equal to each
other.
Solution. Note that {∅} ! ∅, and {{∅}} ! ∅. Also, {{∅}} ! {∅}. Hence no two are
equal.
Exercise 1.3. Show that if B ⊆ C, then PB ⊆ PC.
Solution. Suppose A ∈ PB. Then A ⊆ B, and thus A ⊆ C, as containment is transitive.
Hence A ∈ PC.
Exercise 1.4. Assume that x and y are members of a set B. Show that {{x}, {x, y}} ∈
PPB.
Proof. Since x and y are members of B, it follows that {x} ⊆ B and {x, y} ⊆ B. So {x}
and {x, y} ∈ PB, and thus {{x}, {x, y}} ⊆ PB, so {{x}, {x, y}} ∈ PPB.
Exercise 1.5. Define the rank of a set c to be the least α such that c ⊆ Vα. Compute the
rank of {{∅}}. Compute the rank of {∅, {∅}, {∅, {∅}}}.
Solution. Observe that Vα+1 = PVα. Taking V0 = A = ∅, it follows that
V1 = PV0 = {∅, {∅}}.
Hence the rank of {{∅}} is 1. Futhermore,
V2 = PV1 = {∅, {∅}, {{∅}}, {∅, {∅}}}.
Thus {∅, {∅}, {∅, {∅}}} has rank 2.
Exercise 1.6. We have stated that Vα+1 = A ∪ PVα. Prove this at least for α < 3.
Solution. By definition, for α = 0,
V1 = V0 ∪ PV0 = A ∪ PV0.
For α = 1,
V2 = V1 ∪ PV1 = A ∪ PV0 ∪ PV1 = A ∪ PV1.
The last equality follows from Exercise 1.3, as V0 ⊆ V1, and thus PV0 ∪ PV1 = PV1.
The case for α = 2 follows similarly
[Show More]
, 3e by Steven Krantz.png)
