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.
Previous Page Next Page