4
$\begingroup$

Give an example to show that when the symmetric closure of the reflexive closure of the transitive closure of a relation is formed, the result is not necessarily an equivalence relation.

My attempt at a solution:

$R = \{(2,1),(2,3)\}$.

Transitive closure: $\{(2,1),(2,3)\}$.

Reflexive closure: $\{(1,1),(2,1),(2,2),(2,3),(3,3)\}$.

Symmetric closure: $\{(1,1),(1,2),(2,1),(2,2),(2,3),(3,2),(3,3)\}$.

Since the set is missing $(1,3)$ and $(3,1)$ to be transitive, it is not an equivalence relation.

I am not sure if this is correct.

$\endgroup$
6
  • 1
    $\begingroup$ It is indeed correct. $\endgroup$ Nov 30, 2015 at 8:11
  • $\begingroup$ Could you please clarify why R is already transitive at the beginning? $\endgroup$
    – Philippe
    Nov 30, 2015 at 23:40
  • 2
    $\begingroup$ Transitivity says that if there are elements $a,b,c$ (any of which can be equal) such that $\langle a,b\rangle\in R$ and $\langle b,c\rangle\in R$, then $\langle a,c\rangle\in R$. This condition is vacuous – says nothing – if there are no elements $a,b$, and $c$ such that $\langle a,b\rangle\in R$ and $\langle b,c\rangle\in R$. That’s the case here: the hypothesis of the if-then is never satisfied, so the then part is never invoked. To put it differently, if $R$ were not transitive, there would have to be $a,b$, and $c$ such that $\langle a,b\rangle\in R$ and ... $\endgroup$ Dec 1, 2015 at 4:21
  • 1
    $\begingroup$ ... $\langle b,c\rangle\in R$, but $\langle a,c\rangle\notin R$. And there certainly aren’t, since there aren’t even $a,b$, and $c$ such that $\langle a,b\rangle\in R$ and $\langle b,c\rangle\in R$. $\endgroup$ Dec 1, 2015 at 4:22
  • $\begingroup$ Very clear explanation. Thank you very much! $\endgroup$
    – Philippe
    Dec 2, 2015 at 4:32

2 Answers 2

1
$\begingroup$

The best and the most reliable order to satisfy properties of equivalence relation is in the given order => Reflexive Closure-->Symmetric Closure-->Transitivity closure

The reason for this assertion is that like for instance if you are following the order => Transitivity closure-->Reflexive Closure-->Symmetric Closure

(just like has been asked) ,you may just end up with elements that you added for symmetric closure not being accounted for transitivity as has been shown in the example given in question which has been cited here for reference

R={(2,1),(2,3)} .

Transitive closure: {(2,1),(2,3)}.

Reflexive closure: {(1,1),(2,1),(2,2),(2,3),(3,3)}.

Symmetric closure: {(1,1),(1,2),(2,1),(2,2),(2,3),(3,2),(3,3)}.

Since the set is missing (1,3) and (3,1) to be transitive, it is not an equivalence relation.

But if you follow the order of satisfying Reflexive Closure first,then Symmetric Closure and at last Transitivity closure,then the equivalence property is satisfied as shown.

R={(2,1),(2,3)} .

Reflexive closure: {(1,1),(2,1),(2,2),(2,3),(3,3)}.

Symmetric closure: {(1,1),(1,2),(2,1),(2,2),(2,3),(3,2),(3,3)}

Transitive closure:{(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,2),(3,1),(3,3)}

$\endgroup$
0
$\begingroup$

One comment has answered the OP's question. Here I add something related with Manmohan Khandelwal's answer.


Here I give one strict proof that $\text{Reflexive closure} \rightarrow \text{Symmetric Closure} \rightarrow \text{Transitivity Closure}$ will must construct relation $T$ which is one equivalence closure $C(P)$ of $P$.

  1. closure: since each step is one closure operation, $T$ must be one closure of $P$.
  2. reflexive: Trivially at each step, it only adds some pairs, so $T$ is reflexive.
  3. symmetric: After the Symmetric Closure, we do Transitivity Closure. Then $\forall (a,b),(b,c)\in T,(b,a),(c,b)\in T\Rightarrow (a,c),(c,a)\in T$, so we must add one set of pairs which always have the symmetric property at the Transitivity Closure step. So $T$ is symmetric.
  4. transitive: since the last step is the Transitivity Closure, so $T$ is transitive.

Based on the above 4 conditions met, $T\subseteq C(P)$


It can be also shown that the above $T$ is the smallest equivalence relation that contains $P$. Here I quote the answer to section 9 supplementary-exercise 24 in Discrete Mathematics and Its Applications 8th by Kenneth Rosen

Let S be the transitive closure of the symmetric closure of the reflexive closure of R. ... Furthermore, every element added to R to produce S was forced to be added in order to insure reflexivity, symmetry, or transitivity; therefore S is the smallest equivalence relation containing R

It means that we can remove one element from $T$ to construct one new equivalence closure. Here the closure at each step implies the smallest property.


This question has also one similar answer in this QA

$\endgroup$

You must log in to answer this question.

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