Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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         •


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


  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.

share|cite|improve this question
up vote 1 down vote accepted

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

share|cite|improve this answer
Yes, join operation is just that. So, the statement I've tried to prove was wrong. Thank you very much. – furikuretsu May 26 '11 at 20:01
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
(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.) – Tara B Feb 15 '13 at 16:32

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.