Discrete Mathematics for Computer Science

Special Types of Relations 173

Theorem 4. A binary relation R is transitive if and only if R o R C R.

Proof This just restates the definition. If there is a y such that (x, y) E R and (y, z) E R,

then (x, z) E R. U

In Table 3.8, we summarize the properties, their characterizations, and how we prove

a property holds for a relation R defined on a set X.

Table 3.8 Properties of Relations

Property Characterization Method of Proof

Reflexive Idx c R Let x E X. Prove (x, x) E R.

Antireflexive Idx n R = 0 Let x E X. Prove (x, x) 0 R.

Symmetric R = R-1 Let (x, y) E R. Prove (y, x) E R.

Antisymmetric R n R-^1 C Idx Suppose that (x, y) E R and (y, x) E R.

Prove x = y.

Transitive R o R C R Let (x, y), (y, z) e R. Prove (x, z) E R.

3.4.4 Reflexive, Symmetric, and Transitive Closures

A question that arises for relations that do not possess a particular property, such as being
reflexive, symmetric, or transitive, is whether more elements can be added to a relation
R to produce a relation R' that does have some desired property. One obvious way is to
take R' to be the universal relation (check this). What we really want to know is how to
find a smallest relation R' that contains R and has some desired property, such as trans-
itivity.
For example, how is the relation GeR (>) related to the relation Gt (>)? Clearly,

GeR = GtR U IdMR. The relation GeR turns out to be the smallest reflexive relation on R

containing GtR. GeR is called the reflexive closure of GtR. (The term reflexive closure
will be defined formally below.) More generally, GeX is the reflexive closure of Gtx over
any set X such that X C IR.
Suppose people are waiting in a ticket line. We say that person x is the person In-
FrontOf person y, expressed as x InFrontOf y, if x is the person standing immediately in
front of person y. How is the relation IsAdjacentTo related to the relation InFrontOf? A
person x is adjacent to a person y if x is the person in front of y or y is the person after x.
Said another way, x IsAdjacentTo y means that x is just in front of or just behind y. It can
be shown that IsAdjacentTo is the smallest symmetric relation containing InFrontOf. The
relation IsAdjacentTo is called the symmetric closure of InFrontOf
Finally, in the case of transitivity, we ask how the relation IsAncestorOf is related
to the relation IsParentOf. A person x is the ancestor of a person y if x is a parent of
y, or a parent of a parent of y, or a parent of a parent of a parent of y, and so on. The
relation IsAncestorOf is the smallest transitive relation containing IsParentOf. The relation
IsAncestorOf is called the transitive closure of IsParentOf
To characterize the reflexive, symmetric, and transitive closures of a relation, we first
define a new operation on relations.