MATH 582, INTRODUCTION TO SET THEORY, WINTER 1999

Answers to Problem Set 3 (Revised)

Problem 3.8 Consider any set A. Then

x ∈ dom ⋃ A ⟺ (∃y)⟨x, y⟩ ∈ ⋃ A  (by definition of dom)
⟺ (∃y)(∃R ∈ A)⟨x, y⟩ ∈ R (by definition of union)
⟺ (∃R ∈ A)(∃y)⟨x, y⟩ ∈ R
⟺ (∃R ∈ A)x ∈ dom R  (by definition of dom)
⟺ x ∈ ⋃{dom R | R ∈ A} (by definition of union)

The proof for “ran” is similar.

Problem 3.9 If we replace the union operation by intersection in the previous problem (assuming that A is nonempty), the corresponding result is not true. For a simple example, let A = {{⟨a, b⟩}, {⟨a, c⟩}}, where b ≠ c. Then dom ⋂ A = dom ∅ = ∅, whereas ⋂{dom R | R ∈ A} = ⋂{{a}} = {a}. However, the inclusion from left to right is still valid, namely dom ⋂ A ⊆ ⋂{dom R | R ∈ A}. Compare the proof to that of Problem 3.8:

x ∈ dom ⋂ A ⟺ (∃y)⟨x, y⟩ ∈ ⋂ A  (by definition of dom)
⟺ (∃y)(∀R ∈ A)⟨x, y⟩ ∈ R (by definition of intersection)
⇒ (∀R ∈ A)(∃y)⟨x, y⟩ ∈ R (*)
⟺ (∀R ∈ A)x ∈ dom R  (by definition of dom)
⟺ x ∈ ⋂{dom R | R ∈ A} (by definition of intersection)

Notice that in the step marked (*), the converse implication does not hold: ∃y∀R … implies ∀R∃y …, but not the other way around.

Problem 3.11 Assume that F and G are functions with dom F = dom G. Assume that F (x) = G(x) for all x in the common domain. We claim that F = G. We will show this by proving F ⊆ G and G ⊆ F (recall that functions are sets, namely certain sets of ordered pairs). So suppose z ∈ F. Then, since F is a function, z is an ordered pair, i.e., z = ⟨x, y⟩ for some x, y. By definition of F (x), we have F (x) = y. Since x is in the domain of F, we have G(x) = F (x) by hypothesis, and thus G(x) = y. This implies z = ⟨x, y⟩ ∈ G by definition of G(x). This proves F ⊆ G; the converse follows by a similar argument.

Problem 3.15 Let A be a set of functions such that for any f, g ∈ A, either f ⊆ g or g ⊆ f. We claim that ⋃ A is a function. First, notice that each element of ⋃ A is an ordered pair, and thus ⋃ A is a relation. To prove that it is a function, consider any ⟨x, y⟩ and ⟨x, y′⟩ in ⋃ A. We have to show that y = y′. First, by definition of union, we know that ⟨x, y⟩ ∈ f and ⟨x, y′⟩ ∈ g for some f, g ∈ A. By hypothesis, we know that either f ⊆ g or g ⊆ f. We do a case distinction: if f ⊆ g, then ⟨x, y⟩ ∈ g, which implies y = y′, since g is a function. Similarly, if g ⊆ f, then ⟨x, y′⟩ ∈ f, which again implies y = y′, since f is a function. In either case, y = y′, and we are done.

Problem 3.29 Given f : A → B, define G : B → 𝒫A by G(b) = {x ∈ A | f(x) = b}. Assuming that f is onto B, we want to show that G is one-to-one. So consider b, b′ ∈ B with G(b) = G(b′). We have to show b = b′. Since f is onto, we know that there is some a ∈ A with f(a) = b. It follows, by definition of G, that a ∈ G(b), and thus, a ∈ G(b′) by hypothesis. Using the definition of G again, this in turns implies f(a) = b′, and thus b = f(a) = b′; we are done.

The converse does not in general hold. In other words, it is possible for G to be one-to-one even if f is not onto. To be precise: if there is at most one element of B that is not in the range of f, then G will still be one-to-one. Proof: Assume that there is at most one element of B that is not in the range of f. Suppose G(b) = G(b′). If b is in the range of f, then b = b′ follows as above; similarly if b′ is in the range of f. The only case left is if neither b nor b′ is in the range of f; in this case, b = b′ by hypothesis.

However, if there are at least two different elements of B that are not in the range of f, then G will not be one-to-one: Let b, b′ be such different elements, then G(b) = G(b′) = ∅ but b ≠ b′, and hence G is not one-to-one.

Problem 3.30 Let F : 𝒫A → 𝒫A have the monotonicity property X ⊆ Y ∈ 𝒫A ⇒ F (X) ⊆ F (Y). Define

B = ⋂{X ⊆ A | F (X) ⊆ X} and C = ⋃{X ⊆ A | X ⊆ F (X)}.

Note that F (A) ⊆ A, and thus the set {X ⊆ A | F (X) ⊆ X} is non-empty, making the above intersection welldefined.

(a) Let ℬ be the set {X ⊆ A | F (X) ⊆ X}, so that B = ⋂ ℬ. We claim that F (B) = B.

• First, we claim that F (B) ⊆ B. So take any z ∈ F (B). To show that z ∈ B, consider an arbitrary X ∈ ℬ; we have to show that z ∈ X. By definition of B, we know that B ⊆ X, and hence by monotonicity, F (B) ⊆ F (X), which implies z ∈ F (X). On the other hand, since X ∈ ℬ, we know that F (X) ⊆ X, and thus z ∈ X. Since X ∈ ℬ was arbitrary, this proves z ∈ B, and we have F (B) ⊆ B as desired.

• To prove the converse, B ⊆ F (B), we use the fact that we already know F (B) ⊆ B. By monotonicity, this implies F (F (B)) ⊆ F (B), and hence, we have F (B) ∈ ℬ. It follows that B = ⋂ ℬ ⊆ F (B).

Now, let 𝒞 be the set {X ⊆ A | X ⊆ F (X)}, so that C = ⋃ 𝒞. We claim that C = F (C).

• First, we claim that C ⊆ F (C). So take any z ∈ C. Then there exists some X ∈ 𝒞 such that z ∈ X. By definition of 𝒞, we know that X ⊆ F (X), and thus z ∈ F (X). Also, since C = ⋃ 𝒞, we know that X ⊆ C, and hence by monotonicity, F (X) ⊆ F (C). It follows that z ∈ F (C), as desired.

• To prove the converse, F (C) ⊆ C, we use the fact that we already know C ⊆ F (C). By monotonicity, this implies F (C) ⊆ F (F (C)), and hence, we have F (C) ∈ 𝒞. It follows that F (C) ⊆ ⋃ 𝒞 = C.

(b) Suppose F (X) = X. Then X ∈ ℬ, and hence B = ⋂ ℬ ⊆ X. Similarly, X ∈ 𝒞, and hence X ⊆ ⋃ 𝒞 = C.

Homework for Feb. 5:

1. We gave two definitions of linear order in class, one in terms of < and one in terms of ⩽. Show that they are equivalent, i.e., show that if ⟨A, <⟩ is a linear order in the first sense, and if one defines

x ⩽ y :⟺ x < y ∨ x = y,

then ⟨A, ⩽⟩ is a linear order in the second sense; and if ⟨A, ⩽⟩ is a linear order in the second sense, and if one defines

x < y :⟺ x ⩽ y ∧ x ≠ y,

then ⟨A, <⟩ is a linear order in the first sense.

2. Prove that a relation E on A is an equivalence relation if and only if, for all x, y ∈ A,

xEy ⟺ ∀z ∈ A(xEz ⇒ yEz).

3. Suppose R and Q are equivalence relations on sets A and B respectively, and f : A → B is a function. Prove that there exists a function g : A/R → B/Q satisfying g([x]_{R}) = [f(x)]_{Q} for all x ∈ A, if and only if xRy implies f(x) Q f(y), for all x, y ∈ A.

Chapter 3, Problems 34, 36, 41, 44, 45. Chapter 6, Problem 22 [or 18]. Chapter 7, Problem 1.