Formal MethodsHomework Assignment 10, Part 2April 16, 20077. Let A = {x ∈ R : 1 ≤ x ≤ 2}, B = {x ∈ R : 3 < x < 4}, and C = {x ∈ R : 2 ≤ x ≤ 4}.(a) Sketch the graph of C ×(A ∪ B).The graph consists of two, disjoint, rectangles in the plane. In the x-direction,both rectangles run from 2 to 4 (inclusive). In the y-direction, the lower rectangleruns from 1 to 2 (inclusive), and the upper rectangle runs from 2 to 4 (exclusive).(b) Sketch the graph of (C ×A) ∪ (C × B).This is the same as the graph in part (a).(c) Sketch the graph of B × (A ∩ C).The graph consists of an open line segment in the plane that is parallel to thex-axis. It runs from 3 to 4 (exclusive) in the x-direction, and each point on thesegment has y-coordinate 2.8. Give an example of two relations S and T such that R = the domain of S = the domainof T = the range of S = the range of T, but S ∩ T = ∅.There are a lot of possibilities here. The key is to choose relations for which the graphsin R × R are disjoint. One possibility isS = {(x, y) ∈ R × R : y = x} and T = {(x, y) ∈ R × R : y = x + 1}.Then both S and T have domain and range R. Further, they have empty intersection.For suppose (x, y) is a point in S ∩ T. Then (x, y) = (x, x), since (x, y) ∈ S, and(x, y) = (x, x + 1), since (x, y) ∈ T. This leads to the contradiction that x = x + 1.16. Let A and B be nonempty sets. Prove that A × B = B × A iff A = B.We need to prove two implications. For the first we assume that A and B are nonemptyand that A ×B = B ×A. We want to see that A = B. So suppose x ∈ A. Since B 6= ∅,there exists an element y ∈ B. So (x, y) ∈ A ×B. Since A ×B = B ×A, (x, y) ∈ B ×A.So x ∈ B. That is, A ⊆ B.To see that B ⊆ A, suppose y ∈ B. Since A is nonempty, there is some element x ∈ A.So (x, y) ∈ A ×B. Since A ×B = B ×A, (x, y) ∈ B ×A. So y ∈ A, B ⊆ A and A = B.1For the converse, we assume that A and B are nonempty and that A = B. Then if(x, y) ∈ A × B, both x and y are elements of A as well as B. So (x, y) ∈ B × A.This gives us that A ×B ⊆ B × A. The argument for reverse containment is virtuallyidentical. So A ×B = B × A.17. Which of the following relations are symmetric?(a) A ∪ B, where A = {(x, y) ∈ R × R : x = 0}, and B = {(x, y) ∈ R ×R : y = 0}.The graph is just the union of the x- and y-axes. It is symmetric. If (x, y) ∈ A∪B,then (x, y) ∈ A or (x, y) ∈ B. If (x, y) ∈ A, then x = 0. So (x, y) = (0, y) and(y, x) = (y, 0) ∈ B. So (y, x) ∈ A ∪ B. A completely analogous argument showsthat if (x, y) ∈ B, then (y, x) ∈ A ∪ B.(b) This is not symmetric. For example, the graph contains a line segment in thesecond quadrant. But if (x, y) is any point in the second quadrant, x < 0 andy > 0. So (y, x) is a point in the fourth quadrant, and the graph contains nopoints in the fourth quadrant.(c) The circle with center (1, 0) and radius 1.This is also not symmetric. To se e this just reverse the argument in the precedingproblem: the graph has points in the fourth quadrant, but no points in the secondquadrant. For example, (1, −1) belongs to the circle, but (−1, 1) doesn’t — itsdistance from (1, 0) is√5 > 1.18. For each of the following relations R, sketch the graph of R−1.(a) The graph of R looks like a parabola that opens up with vertex at the origin. Sothe graph of R−1will be a parabola (or something that looks like one) that opensto the right with vertex at the origin.(b) The graph of R is a horizontal line with positive y-intercept c. So the graph ofR−1will be a vertical line with x-intercept c.24. (a) Prove Proposition 4.3(a): If R is a relation, then R = (R−1)−1.Proof. Suppose (x, y) ∈ R. Then (y, x) ∈ R−1, and hence (x, y) ∈ (R−1)−1.Conversely, if (x, y) ∈ (R−1)−1, then (y, x) ∈ R−1and (x, y) ∈ R. So (x, y) ∈ R iff(x, y) ∈ (R−1)−1, and R = (R−1)−1.(d) Prove Proposition 4.3(e): If R is a relation, then R ∪R−1is symmetric.Proof. We give two proofs. First, if we use the definition from the text, we needto show thatR ∪R−1= (R ∪ R−1)−1.By part (c) of Proposition 4.3, we know that(R ∪R−1)−1= R−1∪ (R−1)−1,and by part (a) of Proposition 4.3, we know that R = (R−1)−1. So(R ∪R−1)−1= R−1∪ R = R ∪ R−1.2Alternatively, we use the theorem we proved in class: S is symmetric iff (x, y) ∈ Simplies (y, x) ∈ S . So suppose (x, y) ∈ R ∪ R−1. Then (x, y) ∈ R or (x, y) ∈ R−1.If (x, y) ∈ R, then (y, x) ∈ R−1, and (y, x) ∈ R ∪ R−1. Similarly, if (x, y) ∈ R−1,then (y, x) ∈ R, and (y, x) ∈ R ∪ R−1. In either case, then, (y, x) ∈ R ∪ R−1andR ∪R−1is
View Full Document