Discrete Mathematics for Computer Science

Special Types of Relations 175

Theorem 5. Let R be a binary relation on a set X. Then:

(a) R U Idx is the smallest reflexive relation containing R.

(b) R U R-^1 is the smallest symmetric relation containing R.

(c) R+ is the smallest transitive relation containing R.

(d) R* is the smallest reflexive and transitive relation containing R.

Proof. (a) By Theorem 1, a relation S on X is reflexive if and only if Idx C S. So, S is

reflexive and contains R if and only if R U Idx C S. The smallest such S is R U Idx itself.

(b) We must prove (i) that R U R-^1 is symmetric and (ii) that if S is a symmetric relation

on X and R C S, then R U R-1 C S.

(i) It is enough to show that (R U R-^1 ) -1- R U R-^1 since the result then follows

from Theorem 3 in Section 3.4.2.

(R U R-l)-1 = R-1 U (R-l)-1

=R-1 UR

= R UR-

(ii) Suppose S is a symmetric relation on X and R C S. We must show that R^1 C S.

By Theorem 2 (c) in Section 3.2.1, R-^1 C S-1, and by Theorem 3 in Section

3.4.2, S-1 = S. So, R-^1 C S.

(c) and (d) These proofs are left as Exercises for the reader. U

Definition 7. Let R be any binary relation on a set X. R U Idx is called the reflexive

closure of R. R U R-^1 is called the symmetric closure of R. R+ is called the transitive

closure of R. R* is called the reflexive and transitive closure of R.

Example 12. Let X = {a, b, c}. Define the relation R on X as {(a, b), (b, c)}. Find the

reflexive, symmetric, and transitive closure of R. Also, find the reflexive and transitive

closure of R.

Solution. We must first find the following relations:

(a) Idx = {(a, a), (b, b), (c, c)}

(b) R- - {(b, a), (c, b)}

(c) R= (a, a), (b, b), (c, c)}, R ={(a, b), (b, c)}, R^2 ={(a, c), and R" =0 forn > 3.

(d) R+ [ (a, b), (b, c), (a, c)} and R* = {(a, a), (b, b), (c, c), (a, b), (b, c), (a, c)}

So, the reflexive closure of R is

R U IdX = {(a, b), (b, c), (a, a), (b, b), (c, c)}

The symmetric closure of R is

RUR^1 = {(a, b), (b, c), (b, a), (c, b)}

The transitive closure of R is

R+= {(a, b), (b, c), (a, c)}

Finally, the reflexive and transitive closure of R is

R* = {(a, a), (b, b), (c, c), (a, b), (b, c), (a, c)} U