Question

Find the transitive closure of R = {(a, a), (b, a), (b, c), (c, a), (c, c), (c, d), (d, a), (d, c)} on the set {a, b, c, d}.

Answer 1

Answer on Question#37634 - Math - Discrete Mathematics

Find the transitive closure of $\mathsf{R} = \{\{\mathsf{a},\mathsf{a}\} ,\{\mathsf{b},\mathsf{a}\} ,\{\mathsf{b},\mathsf{c}\} ,\{\mathsf{c},\mathsf{a}\} ,\{\mathsf{c},\mathsf{c}\} ,\{\mathsf{c},\mathsf{d}\} ,\{\mathsf{d},\mathsf{a}\} ,$ (d,c)} on the set $\{\mathsf{a},\mathsf{b},\mathsf{c},\mathsf{d}\}$

Solution:

The relation is represented by a matrix:

R:

The first composition is:

The union $R \cup R \circ R$ is:

There are no new links added, so we can stop the process.

The transitive closure is equal to the original relation, hence the original relation $R$ is transitive.