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
    Yes, join operation is just that. So, the statement I've tried to prove was wrong. Thank you very much.2011-05-26
  • 0
    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!2013-02-15
  • 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