How to prove that symmetric closure of reflexive closure is identical to reflexive closure of symmetric closure?

548 Views Asked by At

Let $X$ be the set of all relations over $\mathbb N$. Let $R\in X$. Let $r(R)$ be the reflexive closure of some relation $R$. Accordingly, let $s(R)$ be the symmetric closure of $R$. I need to prove that $s(r(R))=r(s(R))$.

While this totally makes sense, I'm not sure how to formally prove this.

For any $(a,b)\in R$ such that $a\neq b$ we have that $r(R)=\{(a,b)\}\cup \{(a,a), (b,b)\}$. If $(a,a)\in R$ then $r(R)=R$. So essentially $r(R)$ is a union of all original pairs in $R$ plus their reflexive "counterparts". Applying $s$ onto $r(R)$ will add symmetric "counterparts" for all pairs $(a,b)$ such that $a\neq b$ while the pairs of type $(a,a)$ are already symmetric. So all pairs $(a,a)\in R$ are already symmetric and reflexive therefore applying $s$ and $r$ on them will just return the pairs themselves, while applying $r$ and $s$ on all pairs $(a,b)$ will result in the union of symmetric and reflexive pairs which is the same for $s(r(R))=r(s(R))$.

1

There are 1 best solutions below

0
On

R' = { (a,b) : bRa }. sR = R $\cup$ R'. rR = R $\cup$ N×N.
rsR = sR $\cup$ N×N = R $\cup$ R' $\cup$ N×N.
srR = s(R $\cup$ N×N) = R $\cup$ N×N $\cup$ (R $\cup$ N×N)'
. . = R $\cup$ N×N $\cup$ R' $\cup$ N×N.