172 CHAPTER 3 Relations
(b) For any set X, the empty relation 0 is a symmetric, antisymmetric, and irreflexive
relation on X. If X :A 0, then the empty relation 0 is not reflexive on X. If X = 0, then
the empty relation 0 is (vacuously) reflexive on X.(c) Let R = {(x, y) e R^2 : x < y^2 ). R is not reflexive, irreflexive, symmetric, or antisym-
metric. R is not reflexive since (1, 1) 0 R. R is not irreflexive since (2, 2) E R. R is
not symmetric since (1, 2) e R but (2, 1) V R. R is not antisymmetric since (2, 3) E R
and (3, 2) E R. 0Example 5. Define the relation IsAncestorOf so that x IsAncestorOf y means that x is
a parent of y, or that x is the parent of a parent of y, or that x is the parent of a parent
of a parent of y, and so on. The relation IsAncestorOf is an antisymmetric and irreflexive
relation on the set of all people.
Example 6.
(a) The relations < and < are antisymmetric relations on JR. The relation < is reflexive.
The relation < is irreflexive.
(b) The relations C and C are binary relations on the subsets of a set U. Both C and C are
antisymmetric. The relation C is reflexive, and C is irreflexive.Example 7. Let c = 0.0005, and let RE be the relation
{(x, y) E R'^2 : Ix -yI < e}
RE could be interpreted as the relation approximately equal. Prove that RE is reflexive and
symmetric.
Solution. Reflexive: For all x e X, Ix - x = 0 < E. Symmetric: For all x, y E R,
Ix -Y y= I y-x 1. So, if Ix -yI < c, then I y-x - Ix -yI <E. c3.4.3 Transitive Relations
To introduce the next property of relations, suppose that Sue is a parent of Joe and that Tom
is a parent of Sue. We can conclude that Tom is an ancestor of Joe, but we cannot conclude
that Tom is a parent of Joe. The next property, called transitivity, is a formal way of think-
ing about how the two relations, IsParentOf and IsAncestorOf are different. The relation
IsParentOf does not satisfy this next property whereas the relation IsAncestorOf does.
Definition 5. Let R be a binary relation on a set X. R is transitive if (x, z) e R whenever
(x, y) e R and (y, z) E R.
Example 8. Consider the relations in Examples 4 through 7.
(a) Equality is transitive.
(b) The relation 0 is (vacuously) transitive.
(c) Over the set R, the relations < and < are transitive.
(d) The relation IsAncestorOf is transitive.
(e) The relations C and C are transitive.
(f) R, is not transitive.
(g) {(x, y) E R^2 : x < y^2 } is not transitive. To see this, just note that (9, 5) e R and
(5, 3) E R, but that (9, 3) 0 R. U