2
$\begingroup$

I'm working on a sample exam with no solutions and I've googled examples of similar problems but can't understand them either. Can someone show me a clear cut way to solve this problem:

Let R be a relation on { a,b,c,d,e } defined by R = { ( a,c ) , ( b,d ) , ( c,a ) , ( d,b ) , ( e,d ) } .Find S= the reflexive closure of R, T = the symmetric closure of R, and U = the transitive closure of R.

I know what it means to be reflexive, symmetrical, and transitive but don't understand the closure part. Thank you.

$\endgroup$

1 Answer 1

4
$\begingroup$

The reflexive closure of $R$ is the smallest relation $S$ on $\{a,b,c,d,e\}$ such that (1) $R\subseteq S$ and (2) $S$ is reflexive. To form this, just add to $R$ the ordered pairs required by reflexivity:

$$S=R\cup\{\langle a,a\rangle,\langle b,b\rangle,\langle c,c\rangle,\langle d,d\rangle,\langle e,e\rangle\}\;.$$

Similarly, the symmetric closure $R$ is the smallest relation $T$ on $\{a,b,c,d,e\}$ such that (1) $R\subseteq T$ and (2) $T$ is symmetric. Here again you need only add to $R$ the missing ordered pairs needed for symmetric. There is only one; what is it?

Finally, the transitive closure of $R$ is the smallest relation $U$ on $\{a,b,c,d,e\}$ such that (1) $R\subseteq U$ and (2) $U$ is transitive. Finding the transitive closure can be little trickier than finding the reflexive or symmetric closure, because you may have to go through several stages of adding ordered pairs. $R$ has the ordered pairs $\langle a,c\rangle$ and $\langle c,a\rangle$, so $U$ will have those pairs as well. In order to be transitive, $U$ will therefore also have to include the pair $\langle a,a\rangle$. Similarly reasoning, reversing the rôles of $a$ and $c$, shows that $U$ must contain the ordered pair $\langle c,c\rangle$. And we can apply the same reasoning to the pairs $\langle b,d\rangle,\langle d,b\rangle\in R$ to conclude that $U$ must contain $\langle b,b\rangle$ and $\langle d,d\rangle$. Is there anything else? Yes: $R$ includes both $\langle e,d\rangle$ and $\langle d,b\rangle$, so $U$ does as well and must therefore contain $\langle e,b\rangle$ in order to be transitive. At this point we know that we must have at least

$$R\cup\{\langle a,a\rangle,\langle b,b\rangle,\langle c,c\rangle,\langle d,d\rangle,\langle e,b\rangle\}\;.\tag{1}$$

Is the relation $(1)$ transitive? If so, it’s the transitive closure of $R$. If not, what do you need to add to it to make it transitive?

$\endgroup$
2
  • $\begingroup$ You accidently typed transitive a couple of times in the part about symmetric closure. $\endgroup$ Jun 27, 2013 at 5:26
  • $\begingroup$ @Tobias: So I did; thanks! $\endgroup$ Jun 27, 2013 at 5:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .