2
$\begingroup$

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.

1 Answers 1

1

How is the join operation defined? Is it really just set union?

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$.

  • 0
    (I realise this is an old question and the OP hasn't been on the site for some time, so the above comment was mainly intended for anyone else who might stumble across this.)2013-02-15