How to prove that the transitive closure of a symmetric closure of a relation is greater than the symmetric closure of a transitive closure of a relation?
Asked
Active
Viewed 426 times
0
-
the only idea i have is that transitive closure of symmetric closure contains reflexive elements but the other one does not necessarily contain reflexive elements – Aditya Nambiar Nov 10 '13 at 12:51
1 Answers
0
Essential is here that the symmetric closure of a transitive relation is not necessarily transitive. For instance on positive integers look at the relation $n\mid m$, i.e $n$ divides $m$. The symmetric closure of it is the relation $n\mid m\vee m\mid n$. The numbers $4$ and $12$ are related and so are the numbers $12$ and $6$, but $4$ and $6$ are clearly not.
On the other hand the transitive closure of a symmetric relation is symmetric itself. So if we denote the transitive and symmetric closure of a relation $R$ respectively by $\tau\left(R\right)$ and $\sigma\left(R\right)$ then we find in $\tau\left(\sigma\left(R\right)\right)$ a transitive and symmetric relation that contains $\tau\left(R\right)$. This leads to $\sigma\left(\tau\left(R\right)\right)\subset\tau\left(\sigma\left(R\right)\right)$.
In $\sigma\left(\tau\left(R\right)\right)$ we recognize a relation that contains $\sigma\left(R\right)$ but is not necessarily transitive. If it is not transitive then $\sigma\left(\tau\left(R\right)\right)$ must be a proper subset of $\tau\left(\sigma\left(R\right)\right)$.
drhab
- 151,093
-
-
$\sigma\left(\tau\left(R\right)\right)$ is the 'smallest' symmetric relation that contains $\tau\left(R\right)$ and can be defined as the intersection of all symmetric relations that contain $\tau\left(R\right)$. This way it is a subset of all symmetric relations that contain $\tau\left(R\right)$. One of them is $\tau\left(\sigma\left(R\right)\right)$. – drhab Nov 10 '13 at 20:08