# Basic relations theorem

I need to prove that

If relations $\rho$, $\sigma$ are both reflexive and symmetric, and their composition $\rho\sigma$ is symmetric, then $\rho\sigma = \rho\vee\sigma$.

It's obvious that $\rho\sigma$ includes all relations from both $\rho$ and $\sigma$, but I'm having hard time proving that it doesn't include extra relations.

Example of such case on set {1,2,3,4,5}:

$\rho$ (mark on $i$-th row and $j$-th column denotes $i\rho j$):

  1 2 3 4 5
1 •     •
2   • •
3   • •
4 •     •
5         •


$\sigma$:

  1 2 3 4 5
1 • •
2 • •
3     •
4       •
5         •


$\rho\sigma$:

  1 2 3 4 5
1 • •   •
2 • • •
3 • • •
4 • •   •
5         •


$3\rho\sigma1$, but $3\bar{\rho}1$ and $3\bar{\sigma}1$.

I've tried reduction to the absurd, assuming that $\rho\sigma$ is symmetric and that there are some $x$,$y$,$w$ for which $x \bar{\rho} y$ and $x\bar{\sigma} y$, but $x \rho w\sigma y$. From symmetry of $\rho\sigma$ it follows that $y\rho q\sigma x$ for some $q$. But I can't figure out what to do next.

-

If so, consider the following example: \begin{align*} \rho &= \{(1,1),(2,2),(3,3),(4,4),(1,2),(2,1),(3,4),(4,3)\}, \\ \sigma &= \{(1,1),(2,2),(3,3),(4,4),(3,2),(2,3),(1,4),(4,1)\}. \end{align*} We have $$1\rho2\sigma3, 3\rho4\sigma1, 2\rho1\sigma4, 4\rho3\sigma2.$$ Therefore $\rho\sigma$ is the full relation. In particular, it's symmetric. But it's different from $\rho \cup \sigma$.
Actually the join operation is not just set union: the join of $\rho$ and $\sigma$ is the smallest relation containing both $\rho$ and $\sigma$. And the statement you tried to prove is correct! –  Tara B Feb 15 '13 at 16:31