2
$\begingroup$

I'm working on a task where I need to find out the reflexive, symmetric and transitive closures of R. Statement is given below:

Assume that U = {1, 2, 3, a, b} and let the relation R on U which is 
given by R = {<2,3>, <3, 2>, <1, a>}

1. What is the reflexive closure of R?
2. What is the symmetric closure of R?
3. What is the transitive closure of R?

Here is my answers:

  1. R $\cup$ {< 2, 2 >, <3, 3>, } - reflexive closure
  2. R $\cup$ {< a, 1 >} - symmetric closure
  3. R $\cup$ {<1, 2>, <1, 3>} - transitive closure

I would appreciate if someone could see if i've done this correct or if i'm missing something.

Thanks alot!

$\endgroup$
1
$\begingroup$

The symmetric closure is correct, but the other two are not.

$R\cup\{\langle2,2\rangle,\langle3,3\rangle\}$ fails to be a reflexive relation on $U,$ since (for example), $\langle 1,1\rangle$ is not in that set.

As for the transitive closure, you only need to add a pair $\langle x,z\rangle$ in if there is some $y\in U$ such that both $\langle x,y\rangle,\langle y,z\rangle\in R.$ There are only two such pairs to add, and you've added neither of them.

$\endgroup$
2
  • $\begingroup$ what if I add <a, a> and <b, b> would it make it reflexive closure? If not how can I go forward to make it a reflexive closure? Regarding the transitive closure, then I only need to add <1, 3> to the relation to make it transitive? $\endgroup$
    – Dabbish
    Oct 4 '13 at 21:18
  • $\begingroup$ Yes, the reflexive closure is $$R\cup\{\langle1,1\rangle,\langle2,2\rangle,\langle3,3\rangle,\langle a,a\rangle,\langle b,b\rangle\}.$$ Regarding the transitive closure, as I said, neither of the pairs that you were adding are necessary. Now, if you had (for example) $\langle1,a\rangle,\langle a,3\rangle\in R$, then $\langle 1,3\rangle$ would be in the transitive closure, but this is not the case. Take another look at the relation $R$ and the hint I gave you. Alternately, can you determine $R\circ R$? $\endgroup$ Oct 4 '13 at 21:35
1
$\begingroup$

Transitive Closure:

The transitive closure of a relation $R$ is most simply defined as the smallest superset of $R$ which is a transitive relation. However, this is not a very practical definition. Practically, the transitive closure of $R$ is the set of all $(x,y)$ such that $(x,y)\in R$ or there exist $(x_0,x_1),(x_1,x_2),(x_2,x_3),\dots,(x_{n-1},x_n)\in R$ such that $x=x_0$ and $y=x_n$.

You can see further details and more definitions at ProofWiki.

$\endgroup$

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.