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.
