Discrete Mathematics for Computer Science

Special Types of Relations 169

The difference between < and < that we have discussed is formalized in Definition 2.

Definition 2. Let R be a binary relation on a set X. R is irreflexive if (x, x) 0 R for all

x e X.

Clearly, LtR is an irreflexive relation since x < x is never true for any x e R. Consid-

ering relations as sets, we can characterize irreflexive relations in terms of their intersection

with an identity relation.

Theorem 2. A binary relation R on a set X is irreflexive if and only R n Idx = 0.

Example 1. The usual convention in graphing LtR (see Figure 3.5) is to draw the diag-

onal line x = y dotted to show that it is not included in the graph. Since no point on this

line is in LtR, it can be concluded that LtR is irreflexive.

y

/

, -(0,0)-----. x

Figure 3.5 LtR.

The relation f{(1, 1), (1, 2)1 on X f {1, 21 is not reflexive, because (2, 2)^0 R and it is

not irreflexive because (1, 1) E R.

3.4.2 Symmetric and Antisymmetric Relations

A principal distinction between the equality relation = on the one hand and the relations

< and < on the other is captured by the notion of symmetry.

Definition 3. Let R be a binary relation on a set X. R is symmetric if (y, x) E R when-

ever (x, y) G R.

Clearly, the relation = is a symmetric relation. Neither < nor <, however, is symmet-

ric. For example, notice it is true that 3 < 5 but not that 5 < 3, and it is true that 3 < 5 but

not that 5 < 3. Therefore, neither < nor < is a symmetric relation.

Example 2. Refer to Section 3.1 for the definitions of the relations IsMarriedTo, IsPar-
entOf SameSuit, HigherValue, and IsSameGeneration.
(a) The relation IsMarriedTo is symmetric, and IsParentOf is not. (Mary, Elaine) E IsPar-
entOf whereas (Elaine, Mary) 0 IsParent~f.
(b) The relation SameSuit is symmetric, whereas HigherValue is not. (Jack of Hearts, 10
of Hearts) E HigherValue, whereas (10 of Hearts, Jack of Hearts) 0 HigherValue.
(c) IsSameGeneration is symmetric.