MATH 582, INTRODUCTION TO SET THEORY, WINTER 1999 Answers to Problem Set 4

Problem 1 Recall that a binary relation < on A is said to be a linear order (in the strict sense) if it is:

1. irreflexive: ∀x ∈ A(¬x < x),

2. transitive: ∀x, y, z ∈ A(x < y ∧ y < z ⇒ x < z),

3. connected: ∀x, y ∈ A(x < y ∨ x = y ∨ y < x).

A binary relation ⩽ on A is said to be a linear order (in the non-strict sense) if it is:

1. reflexive: ∀x ∈ A(x ⩽ x),

2. anti-symmetric: ∀x, y ∈ A(x ⩽ y ∧ y ⩽ x ⇒ x = y),

3. transitive: ∀x, y, z ∈ A(x ⩽ y ∧ y ⩽ z ⇒ x ⩽ z),

4. linear: ∀x, y ∈ A(x ⩽ y ∨ y ⩽ x).

Suppose ⟨A, <⟩ is a linear order in the strict sense, and define x ⩽ y to mean x < y ∨ x = y. We claim that ⟨A, ⩽⟩ is a linear order in the non-strict sense. Reflexivity: for all x, one has x = x and thus x ⩽ x. Anti-symmetry: Suppose x ⩽ y and y ⩽ x. Assume, for the sake of contradiction, that x ≠ y. Then x < y and y < x, thus, x < x by transitivity of <, contradicting irreflexivity of <. Thus x = y. Transitivity: Suppose x ⩽ y and y ⩽ z. If x = y then x ⩽ z follows from y ⩽ z, and we are done. Similarly if y = z, then x ⩽ z follows from x ⩽ y, and again we are done. The only case left to consider is when x ≠ y and y ≠ z. But then x < y < z, and x < z, thus x ⩽ z, follows by transitivity of <. Linearity: Take x, y ∈ A. By connectedness of <, either x < y or x = y or y < x. In each of these cases, it follows that x ⩽ y or y ⩽ x.

Conversely, suppose ⟨A, ⩽⟩ is a linear order in the non-strict sense, and define x < y to mean x ⩽ y ∧ x ≠ y. We claim the ⟨A, <⟩ is a linear order in the strict sense. Irreflexivity: For any x, since x ≠ x does not hold, x < x does not hold. Transitivity: Suppose x < y and y < z. Then x ⩽ y and y ⩽ z, and also x ≠ y and y ≠ z. It follows that x ⩽ z by transitivity of ⩽. Assume that x = z, then x = y follows by antisymmetry of ⩽, a contradiction. Hence x ≠ z, and thus x < z. Connectedness: Take x, y ∈ A. If x = y, we are done, so assume x ≠ y. By linearity of ⩽, we know that x ⩽ y or y ⩽ x, and thus x < y or y < x by definition of < and the fact that x ≠ y.

Problem 2 First, assume that E is an equivalence relation on A, and consider any x, y ∈ A. We must show that xEy ⟺ ∀z ∈ A(xEz ⇒ yEz). To prove the left-to-right half of this equivalence, assume xEy. Then yEx by symmetry, and therefore for all z ∈ A, xEz implies yEz by transitivity. To prove the right-to-left implication, assume that ∀z ∈ A(xEz ⇒ yEz) holds. In particular, xEx ⇒ yEx. But xEx by reflexivity, and hence yEx, and by symmetry, xEy.

Conversely, assume that xEy ⟺ ∀z ∈ A(xEz ⇒ yEz) holds for all x, y ∈ A. We want to show that E is an equivalence relation on A. Reflexivity: For any x ∈ A, the statement ∀z ∈ A(xEz ⇒ xEz) is logically valid, and thus xEx by hypothesis. Symmetry: Suppose xEy. Then, by hypothesis, ∀z ∈ A(xEz ⇒ yEz). In particular, xEx ⇒ yEx. But we have already proved that E is reflexive, so yEx holds as desired. Transitivity: Suppose xEy and yEz. The latter gives ∀w ∈ A(yEw ⇒ zEw) by hypothesis, and in particular, yEx ⇒ zEx. We already know that E is symmetric, so we have yEx, and thus zEx. Another application of symmetry gives xEz, as desired.

Problem 3 Suppose R and Q are equivalence relations on sets A and B respectively, and f : A → B is a function. We want to 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 xRx′ implies f(x) Q f(x′), for all x, x′ ∈ A.

For the right-to-left implication, assume that g is such a function. If xRx′, then [x]_{R} = [x′]_{R}, thus g([x]_{R}) = g([x′]_{R}), thus [f(x)]_{Q} = [f(x′)]_{Q} by hypothesis, thus f(x) Q f(x′).

For the left-to-right implication, define g = {⟨[x]_{R}, [f(x)]_{Q}⟩ | x ∈ A}. Then g is certainly a relation of the appropriate type; we must check that it is a function. So consider any ⟨u, v⟩, ⟨u, w⟩ ∈ g. By definition of g, there must be x, x′ ∈ A such that u = [x]_{R} = [x′]_{R}, v = [f(x)]_{Q}, and w = [f(x′)]_{Q}. It follows that xRx′, hence f(x) Q f(x′) by hypothesis, hence v = w. This shows that g is a function. Do see that the domain of g is all of A/R, notice that for every [x]_{R} ∈ A/R, one has ⟨[x]_{R}, [f(x)]_{Q}⟩ ∈ g, hence [x]_{R} ∈ dom g. Thus, g : A/R → B/Q. Moreover, it follows directly from the definition of g that it satisfies the desired property.

Problem 3.34 Assume that A is a non-empty set of transitive relations.

(a) The set ⋂ A is a transitive relation. Being a subset of some A ∈ A, it is a relation. To show that it is transitive, take two pairs ⟨x, y⟩, ⟨y, z⟩ ∈ ⋂ A. Consider an arbitrary A ∈ A. By definition of intersection, ⟨x, y⟩, ⟨y, z⟩ ∈ A. Since A is a transitive relation, it follows that ⟨x, z⟩ ∈ A. Since A was arbitrary, it follows that ⟨x, z⟩ ∈ ⋂ A.

(b) The set ⋃ A is not in general a transitive relation. The simplest counterexample is A = {{⟨0, 1⟩}, {⟨1, 2⟩}}.

Problem 3.36 By definition, we have Q ⊆ A × A, so Q is a relation on A. We want to show that Q is an equivalence relation on A. Reflexivity: For any x ∈ A, we have ⟨f(x), f(x)⟩ ∈ R, by reflexivity of R. Thus, ⟨x, x⟩ ∈ Q. Symmetry: Suppose ⟨x, y⟩ ∈ Q. Then ⟨f(x), f(y)⟩ ∈ R, thus ⟨f(y), f(x)⟩ ∈ R by symmetry of R. Hence ⟨y, x⟩ ∈ Q. Transitivity: Suppose ⟨x, y⟩, ⟨y, z⟩ ∈ Q. Then ⟨f(x), f(y)⟩, ⟨f(y), f(z)⟩ ∈ R, hence ⟨f(x), f(z)⟩ ∈ R by transitivity of R. Thus ⟨x, z⟩ ∈ Q.

Problem 3.41

(a) Q is an equivalence relation: Reflexivity: For any ⟨u, v⟩ ∈ ℝ × ℝ, u + v = u + v, and hence ⟨u, v⟩Q⟨u, v⟩. Symmetry: Suppose ⟨u, v⟩Q⟨x, y⟩. Then u+y = x+v, hence x+v = u+y, hence ⟨x, y⟩Q⟨u, v⟩. Transitivity: Suppose ⟨u, v⟩Q⟨x, y⟩ and ⟨x, y⟩Q⟨w, z⟩. Then u + y = x + v and x + z = w + y. Adding the two equations, we get u + y + x + z = x + v + w + y. Subtracting x + y, we obtain u + z = w + v, and thus ⟨u, v⟩Q⟨w, z⟩.

(b) By Theorem 3Q (or Problem 3), what we must check is whether ⟨u, v⟩Q⟨x, y⟩ implies ⟨u + 2v, v + 2u⟩Q⟨x + 2y, y + 2x⟩. That is, we must check whether u + y = x + v implies (u + 2v) + (y + 2x) = (x + 2y) + (v + 2u). By adding u + v + x + y to each side of the equation, and exchanging left and right sides, this does indeed follow. Therefore, the required G exists.

Problem 3.44 To show that f is one-to-one, take any x ≠ y in A; we have to show f(x) ≠ f(y). By connectedness of <, we have either x < y or y < x. By hypothesis, this implies f(x) < f(y) or f(y) < f(x). In either case f(x) ≠ f(y) by irreflexivity. This shows that f is one-to-one.

Now assume that f(x) < f(y); we want to show x < y. We cannot have x = y, because this would imply f(x) = f(y), contradicting f(x) < f(y) (by irreflexivity). Neither can we have y < x, because this would imply f(y) < f(x) by hypothesis, and we would have f(x) < f(x) by transitivity, again contradicting irreflexivity. Since < is connected, the only possibility left is x < y.

Problem 3.45 Consider linearly ordered sets ⟨A, <_{A}⟩ and ⟨B, <_{B}⟩. The lexicographic ordering on A × B is the relation <_{L} defined as follows:

⟨a_{1}, b_{1}⟩ <_{L} ⟨a_{2}, b_{2}⟩ iff a_{1} <_{A} a_{2} ∨ (a_{1} = a_{2} ∧ b_{1} <_{B} b_{2}).

We show that <_{L} is a linear ordering: Irreflexivity: Consider any ⟨a, b⟩ ∈ A × B. Since neither a <_{A} a nor b <_{B} b hold (by irreflexivity of <_{A} and <_{B}), we do not have ⟨a, b⟩ <_{L} ⟨a, b⟩. Transitivity: Suppose ⟨a_{1}, b_{1}⟩ <_{L} ⟨a_{2}, b_{2}⟩ and ⟨a_{2}, b_{2}⟩ <_{L} ⟨a_{3}, b_{3}⟩. We want to show ⟨a_{1}, b_{1}⟩ <_{L} ⟨a_{3}, b_{3}⟩. Notice that a_{1} ⩽ a_{2} and a_{2} ⩽ a_{3}. If we have a_{1} <_{A} a_{2} or a_{2} <_{A} a_{3}, then a_{1} <_{A} a_{3}, and we are done. Otherwise, a_{1} = a_{2} = a_{3} and b_{1} <_{B} b_{2} <_{B} b_{3}. In this case, we have b_{1} <_{B} b_{3} by transitivity, and again, this implies ⟨a_{1}, b_{1}⟩ <_{L} ⟨a_{3}, b_{3}⟩ as desired. Connectedness: Consider any ⟨a_{1}, b_{1}⟩, ⟨a_{2}, b_{2}⟩ ∈ A × B. By connectedness of <_{A}, we have either a_{1} <_{A} a_{2} or a_{1} = a_{2} or a_{2} <_{A} a_{1}. In the first case, we have ⟨a_{1}, b_{1}⟩ <_{L} ⟨a_{2}, b_{2}⟩, and in the last case, we have ⟨a_{2}, b_{2}⟩ <_{L} ⟨a_{1}, b_{1}⟩; if either of these happens, we are done. The remaining case is a_{1} = a_{2}. By connectedness of <_{B}, we have either b_{1} <_{B} b_{2} or b_{1} = b_{2} or b_{2} <_{B} b_{1}. In the first case, we have ⟨a_{1}, b_{1}⟩ <_{L} ⟨a_{2}, b_{2}⟩, and in the last case, we have ⟨a_{2}, b_{2}⟩ <_{L} ⟨a_{1}, b_{1}⟩. The only remaining case is when b_{1} = b_{2}, but then we have ⟨a_{1}, b_{1}⟩ = ⟨a_{2}, b_{2}⟩. Thus we are done.

Problem 6.22 We will show that the statement

For any set A there is a function F : ⋃ A → A such that x ∈ F (x) for all x ∈ ⋃ A  (*)

is equivalent to the axiom of choice. We discussed four equivalent statements of the axiom of choice in class. Here, we will show (AC2) ⇒ (*) ⇒ (AC3).

To show the first implication, assume (AC2) and let A be any set. Consider the relation R ⊆ (⋃ A) × A defined by ⟨x, a⟩ ∈ R ⟺ x ∈ a ∈ A. By the definition of union, for each x ∈ ⋃ A, there exists a ∈ A with x ∈ a; thus ⋃ A is the domain of R. By (AC2), there exists a function F : ⋃ A → A with F ⊆ R. This function F satisfies the property (*): namely, for all x ∈ ⋃ A, we have ⟨x, F (x)⟩ ∈ F ⊆ R, thus x ∈ F (x) by definition of R.

Now assume (*). We will show (AC3), i.e. the existence of a choice function G : (𝒫A − {∅}) → A, for any set A. So consider any set A. For any z ∈ A, define the set I_{z} = {a ⊆ A | z ∈ a} ∈ 𝒫𝒫A. Let A^{∗} = {I_{z} | z ∈ A} ⊆ 𝒫𝒫A. Let ϕ : A → A^{∗} be the function defined by ϕ(z) = I_{z}. We claim:

1. ϕ is one-to-one and onto. Thus ϕ^{−1} : A^{∗} → A is a well-defined function. Proof: To show that ϕ is one-to-one, assume ϕ(y) = ϕ(z) for some y, z ∈ A. Then I_{y} = I_{z}. Since {y} is a member of I_{y}, it must also be a member of I_{z}, which means, by definition of I_{z}, that z ∈ {y}, hence y = z. This proves that ϕ is one-to-one. Clearly, ϕ is onto A^{∗} by definition of A^{∗}.

2. ⋃ A^{∗} = 𝒫A − {∅}. Proof: a ∈ ⋃ A^{∗} iff ∃z ∈ A(a ∈ I_{z}) iff ∃z ∈ a ⊆ A iff a ⊆ A and a ≠ ∅ iff a ∈ 𝒫A − {∅}.

By the hypothesis (*), when applied to the set A^{∗}, it follows that there exists a function F : ⋃ A^{∗} → A^{∗} such that a ∈ F (a) for all a ∈ ⋃ A^{∗}. We define new define a function G : (𝒫A − {∅}) → A as follows: Let G(a) = ϕ^{−1}(F (a)). By claims 1 and 2 above, this is a well-defined function. Now consider any a ∈ 𝒫A − {∅}. Let z = G(a). Then I_{z} = ϕ(z) = ϕ(G(a)) = ϕ(ϕ^{−1}(F (a))) = F (a) by definitions of ϕ and G. Also a ∈ F (a) by construction of F, hence a ∈ I_{z}. The latter implies z ∈ a by definition of I_{z}. Since z was G(a), we have G(a) ∈ a. Since a was arbitrary, this holds for all a ∈ 𝒫A − {∅}, which proves that G is the desired choice function.

Problem 7.1 Unlike in Problem 3.44, both claims are wrong for partial orders. Consider the following function between partially ordered sets:

This function satisfies x <_{A} y ⇒ f(x) <_{B} f(y), but it is neither one-to-one, nor does it satisfy f(x) <_{B} f(y) ⇒ x <_{A} y. Notice that the elements b and c satisfy f(c) <_{B} f(b), but not c <_{A} b.