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

-

## 1 Answer

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

-

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 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 at 16:32
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 32, "mathjax_display_tex": 2, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9642634987831116, "perplexity_flag": "head"}