Discrete Mathematics for Computer Science

170 CHAPTER 3 Relations

One can see that a binary relation on R is symmetric if and only if its graph is sym-

metric about the diagonal line x = y. Figure 3.6 shows a symmetric relation on R.

y

Figure 3.6 Symmetric relation on R.

We really begin to understand the properties of relations when we understand how

different concepts express the same idea. Theorem 3 relates inverses of relations to the

property of a relation being symmetric.

Theorem 3. A relation R on a set X is symmetric if and only if R = R-^1.

Proof. Let R be a symmetric relation. Then, (x, y) e R if and only if (y, x) e R, which

is the case if and only if (x, y) e R-^1. 0

The relation shown in Figure 3.7 is not symmetric: (0, -7) is an element of the rela-

tion, whereas (-7, 0) is not.

(-7, relation on R

/• •,-7)

Figure 3.7 Nonsymmetric relation on IR.