24 2. Background (viii) Reflexive and symmetric but not transitive. (ix) Symmetric, antisymmetric, and transitive. (x) Reflexive, symmetric, and transitive. (xi) None of reflexive, symmetric, or transitive. Exercise 2.3.8. Suppose R and S are binary relations on A. For each of the following properties, if R and S possess the property, must R ∪ S possess it? R ∩ S? (i) Reflexivity (ii) Symmetry (iii) Antisymmetry (iv) Transitivity Exercise 2.3.9. Each of the following relations has a simpler de- scription than the one given. Find such a description. (i) R− on P(N) where R−(A, B) ↔ A − B = ∅. (ii) R(∩) on R where R(∩)(x, y) ↔ (−∞,x) ∩ (y, ∞) = ∅. (iii) R[∩] on R where R[∩](x, y) ↔ (−∞,x] ∩ [y, ∞) = ∅. (iv) R(∪) on R where R(∪)(x, y) ↔ (−∞,x) ∪ (y, ∞) = R. (v) R[∪] on R where R[∪](x, y) ↔ (−∞,x] ∪ [y, ∞) = R. We may visualize a binary relation R on A as a directed graph. The elements of A are the vertices, or nodes, of the graph, and there is an arrow (directed edge) from vertex x to vertex y if and only if R(x, y) holds. The four properties we have just been exploring may be stated as: • Reflexivity: every vertex has a loop. • Symmetry: any pair of vertices is either directly connected in both directions or not directly connected at all. • Antisymmetry: any two vertices have at most one edge di- rectly connecting them. • Transitivity: if there is a path of edges from one vertex to an- other (always proceeding in the direction of the edge), there is an edge directly connecting them, in the same direction as the path.
Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2012 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.
