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:
- R $\cup$ {< 2, 2 >, <3, 3>, } - reflexive closure
- R $\cup$ {< a, 1 >} - symmetric closure
- 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$2 Answers
$\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$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$
