Reflexivity, Symmetry, and Transitivity

Let A = {2, 3, 4, 6, 7, 9} and define a binary relation R on A as follows:

" x, y Î A, x R y Û 3|(x – y).

We have a directed graph adjacency matrix G:

Clearly the digraph is disconnected since the matrix for G Ú G² Ú G³ Ú G⁴ Ú G⁵ would not be full.

To see the components rearrange the matrix in the order 2, 7, 4, 3, 6, 9 such that adjacent vertices are sequential:

Excuse the diversion, to focus on the topic at hand, refer again to the drawing of G representing our relation R.

This graph has three important properties:

1. Each point of the graph has an arrow looping back to itself.
2. In each case where there is an arrow going from one point to a second, there is an arrow going from the second point back to the first.
3. In each case where there is an arrow going from one point to a second and from a second point to a third, there is an arrow going from the first point to the third. That is there are no "incomplete directed triangles" in the graph.

Properties (1), (2), and (3) correspond to properties of general binary relations called reflexivity, symmetry, and transitivity.

Definition Let R be a binary relation on a set A.

1. R is reflexive iff " x Î A, x R x.
2. R is symmetric iff " x, y Î A, if x R y then y R x.
3. R is transitive iff " x, y, z Î A, if x R y and y R z then x R z.

Recall that we can think of the relation itself as a totality of ordered pairs whose elements are related by the given condition. In other words, given an ordered pair (x, y) in A X B, x is related to y by R, written x R y, if, and only if, (x, y) is in the set R. It is instructive to consider these definitions using set notation:

1. R is reflexive Û " x Î A, (x, x) Î R.
2. R is symmetric Û " x, y Î A, if (x, y) Î R then (y, x) Î R.
3. R is transitive Û " x, y, z Î A, if (x, y) Î R and (y, z) Î R then (x, z) Î R.

We can also state these properties informally but be aware that some nuances are lost in the translation. In particular, the elements referred to need not be distinct.

1. Reflexive: Each element is related to itself.
2. Symmetric: If any one element is related to any other element, then the second element is related to the first.
3. Transitive: If any one element is related to a second and that second element is related to a third, then the first element is related to the third.

Note also the vacuous nature of the transitive property. Where the antecedent (or hypotheses) is not met, the implication is true.

To prove any of these universal statements, reflexivity, symmetry, or transitivity for a given relation either use the method of exhaustion or the method of generalizing from the generic particular.

Now consider what it means for a relation not to have one of the properties defined above. Recall that the negation of a universal statement is existential. Write expressions for the three informal statements:

1. R is not reflexive:
2. R is not symmetric:
3. R is not transitive:

It follows that you can show a binary relation does not have one of the properties by finding a counterexample.

Example: Using a digraph to check for properties of a relation.
Let A = {0, 1, 2, 3, 4}, and define R Í A X A on A by {(0,1), (0, 2), (0, 3), (0, 4), (1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (3, 0), (3, 1), (3, 2), (3, 4)}. Show that R is reflexive, symmetric, and transitive or give a counterexample for each as applicable.
If the relation R on A X A is reflexive, what ordered pairs must belong to R?

If the relation R on A X A is symmetric, what ordered pairs must belong to R?

If the relation R on A X A is transitive, what ordered pairs must belong to R?

Solution

Reflexive ordered pairs: (0,0), (1,1), (2,2), (3,3), & (4,4). R is missing (0,0), (3,3), & (4,4).
Symmetric ordered pairs: Knowing that a relation is symmetric does not give information about any of the ordered pairs that might belong to R. If we know some ordered pairs that belong to R, then we know certain other pairs that must belong to R. For R we see we have (0, 2) but not (2, 0), we have (1, 2) but not (2, 1), we have (1, 4) but not (4, 1), etc.
Transitive ordered pairs: if (x, y) Î R and (y, z) Î R then (x, z) Î R. For R these tuplets are: {(0,1),(1,2),(0,2); (0,3),(3,4),(0,4); (1,3),(3,4),(1,4); (1,0),(0,4),(1,4); (1,0),(0,2),(1,2); (3,1),(1,0),(3,0); (3,0),(0,2),(3,2); (3,0),(0,1),(3,1)}.

Be sure to carefully review examples
10.2.1 Properties of Binary Relations on Sets
10.2.3 Properties of Equality ("=" is reflexive, symmetric, and transitive)
10.2.4 Properties of "Less Than" ("<" is not reflexive, not symmetric, but is transitive)
10.2.5 Properties of Congruence Modulo 3 (reflexive, symmetric, and transitive)