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.