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. Considering 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 diagonal 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
/
-
----- .
x
, (0,0)
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 whenever (x, y) G R.
Clearly, the relation = is a symmetric relation. Neither < nor <, however, is symmetric. 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, IsParentOf SameSuit, HigherValue, and IsSameGeneration.
(a) The relation IsMarriedTo is symmetric, and IsParentOf is not. (Mary, Elaine) E IsParentOf 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.
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. Considering 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 diagonal 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
/
-
----- .
x
, (0,0)
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 whenever (x, y) G R.
Clearly, the relation = is a symmetric relation. Neither < nor <, however, is symmetric. 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, IsParentOf SameSuit, HigherValue, and IsSameGeneration.
(a) The relation IsMarriedTo is symmetric, and IsParentOf is not. (Mary, Elaine) E IsParentOf 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.