Formal MethodsHomework Assignment 11, Part 2Due Monday, April 23, 20071. Recollect that if A is a partition of the nonempty set A, then we can define an equiv-alence relation on A bya ∼ b iff ∃B ∈ A such that both a and b belong to B.Also recollect that ifB = {[a] : a ∈ A},we had s hown that A ⊆ B.(a) If [a] ∈ B, find an element B ∈ A such that a ∈ B.Since A is a partition of A, every element of A belongs to some ele ment of A. Sothere exists some element B ∈ A such that a ∈ B.(b) If b ∈ [a], show that b ∈ B. (Here B is the set you found in part (a).)Since b ∈ [a], there exists a set C ∈ A such that both a and b belong to C. SinceA is a partition, either B ∩ C = ∅ or B = C. Since a ∈ B ∩ C, it must be thatB = C. Hence b ∈ B.(c) If c ∈ B, show that c ∈ [a]. (Once again B is the set from part (a).)Since c ∈ B, both a and c belong to B, and hence a ∼ c. So c ∈ [a].(d) Explain why your answers to parts (a), (b), and (c) show that B ⊆ A.If [a] ∈ B, part (a) finds some element B ∈ A such that a ∈ B. Then part (b)shows that [a] ⊆ B, and part (c) shows that B ⊆ [a]. Thus [a] = B, and anyelement [a] ∈ B is also an element of A.50. Let S = {1, 2, 3, 4, 5} and let A = {{1, 2}, {3}, {4, 5}}. List all ordered pairs of theequivalence relation promised by Theorem 4.5.(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (1, 2), (2, 1), (4, 5), (5, 4)57. Let X = {(x, y) ∈ R × R : xy > 0}. That is X is the union of the first and thirdquadrants of the plane. For each positive real number α, letAα= {(x, y) ∈ X : xy = α},1and letA = {Aα: α is a positive real number }.(a) Is the indexed family A a partition of X? (Explain.)If α is a positive real number, then Aα6= ∅ because 1 · α = α, and (1, α) lies inthe first quadrant. So (1, α) ∈ Aα.Suppose α and β are positive real numbers and (x, y) ∈ X such that (x, y) ∈Aα∩ Aβ. Then α = xy = β. So α = β and Aα= Aβ. So if Aαand Aβare elementsof A such that Aα∩ Aβ6= ∅, then Aα= Aβ.Finally suppose (x, y) ∈ X. Then xy > 0. So there is a positive real number αsuch that xy = α. Hence (x, y) ∈ Aα, and every element of X belongs to someelement of A . Thus ∪A = X, and A is a partition of X.(b) LetR = {((x1, y1), (x2, y2)) : ∃Aα∈ A such that both (x1, y1), (x2, y2) ∈ Aα}.Is R an equivalence relation on X. (Prove your answer.)R is an equivalence relation. This follows immediately from the fact that Ais a partition of X, and the theorem which shows that a partition induces anequivalence relation.(c) Draw the graph of R[(1, 3)].Since 1 · 3 = 3, the equivalence class of (1, 3) is the hyperbola consisting of allpairs (x, y) such that xy = 3.58. For each real number b, let Ab= {(x, y) ∈ R×R : y = 2x+b}, and let A = {Ab: b ∈ R}.Is A a partition of R × R? Justify your answer.Yes, A is a partition of R × R.First observe that if b ∈ R, then Ab6= ∅. For the pair (0, b) ∈ Ab.Now s uppose that b and c are real numbers such that (x, y) ∈ Ab∩ Ac. Then y = 2x + band y = 2x + c. So we get that b = y − 2x = c, and Ab= Ac. So if Aband Acareelements of A , then either Ab∩ Ac= ∅, or Ab= Ac.Observe that if (x, y) ∈ R × R, we can solve the equation y = 2x + b for b, gettingb = y − 2x. So (x, y) ∈ Ab. Thus each point in R × R belongs to some element of A,and hence ∪A = R ×
View Full Document