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$
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 '13 at 5:26
  • $\begingroup$ @Tobias: So I did; thanks! $\endgroup$ Jun 27 '13 at 5:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.