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 antisymmetric. 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.
0
Example 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
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 thinking 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
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 antisymmetric. 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.
0
Example 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
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 thinking 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