Answer to Question #209914 in Discrete Mathematics for Sach

Question

Let R = {(0, 0), (1, 1), (1, 2), (1, 3), (2, 0), (2, 2), (3, 0)} be a relation on the set {0, 1, 2, 3}. Find the

(a) Reflexive closure of R

(b) Symmetric closure of R

(c) Transitive closure of R

Answer 1

R = { (0,0), (1,1), (1,2), (1,3), (2,0), (2,2), (3,0) }

Reflexive closure

The reflexive closure is obtained by all elements of the form (a, a) with a $\in$ A

to R, which are thus (0,0),(1,1),(2, 2), and (3,3).

Reflexive closure

= R U { (0,0), (1,1), (2,2), (3,3) }

= { (0,0), (1,1), (1,2), (1,3), (2,0), (2,2), (3,0), (3,3) }

Symmetric closure

Let us first determine the inverse relation of R:

R^-1 = { (0,0), (1,1), (2,1), (3,1), (0,2), (2,2), (0,3) }

The symmetric closure contains all elements in R and its inverse relation R^-1

Symmetric closure

= R U R^-1

= { (0,0), (1,1), (1,2), (1,3), (2,0), (2,2), (3,0), (0,2), (0,3), (2,1), (3,1) }

Transitive closure

We need to add all elements to R that can be obtained by the transitive

property. That is, when (x,y) $\in$ R and (y, z) $\in$ R, then (x, z) needs to be

in the transitive closure as well.

Transitive closure

= { (0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1), (2,2), (3,0), (3,1), (3,2) }