R is symmetric and transitive relation, if and only if $R = R^{-1}\circ R$

Question

How do I prove that the following:

Let $R$ be a (binary) relation on a set. Prove that $R$ is symmetric and transitive relation, if and only if $R = R^{-1}\circ R$.

Here, $R^{-1} \circ R$ is defined as the relation $\{(u,v) | \exists x, uR^{-1}x \land xRv\}$, where $xRu$ means $\left(x,u\right) \in R$.

I only have a problem with assuming the 2nd, and deriving the first, any tips on the proof technique?

Answer 1

Let $R = R^{-1} \circ R$.

Let $(a,b) \in R$. Since $(a,b) \in R^{-1} \circ R$, there is $c$ such that $(a,c) \in R^{-1}$ and $(c,b) \in R$.

So $(c,a) \in R$. Then, $(a,c) \in R^{-1}$, so $(a,a) \in R^{-1} \circ R = R$, so $(b,a) \in R^{-1} \circ R = R$.

So $R$ is symmetric.

Let $(a,b),(b,c) \in R$. By the above, $(b,a) \in R$, so $(a,b) \in R^{-1}$, so $(a,c) \in R^{-1} \circ R = R$

So $R$ is transitive.

---

Let $R$ be symmetric and transitive.

Then, let $(a,b) \in R$. Since $R$ is symmetric, $(b,a) \in R$, so $(a,b) \in R^{-1}$. Since $R$ is transitive, $(b,b) \in R$. Therefore, $(a,b) \in R^{-1} \circ R$.

Let $(a,b) \in R^{-1} \circ R$, and let $(a,c) \in R^{-1}$ and $(c,b) \in R$. So $(c,a) \in R$. Since $R$ is symmetric, $(a,c) \in R$. Since $R$ is transitive, $(a,b) \in R$.

Therefore, for all $(a,b)$, $(a,b) \in R \iff (a,b) \in R^{-1} \circ R$, so $R = R^{-1} \circ R$ by axiom of extensionality.

Answer 2

Preparations:

$\newcommand{\op}[2]{ \left\langle #1 ,\, #2 \right\rangle }$ $\newcommand{\rel}[1]{ \mathcal{#1} }$ $\newcommand{\dom}[1]{ \mathrm{dom} \ {#1} }$ $\newcommand{\ran}[1]{ \mathrm{ran} \ {#1} }$

Define ordered pair:

$$\op{x}{y} = \left\{\left\{x\right\},\,\left\{x,\,y\right\}\right\}$$

Define domain and range of relation:

\begin{align} \dom{R} &= \left\{ x \in \cup\cup\rel{R} \mid \exists y :\: \op{x}{y} \in \rel{R} \right\}, \\ \ran{R} &= \left\{ x \in \cup\cup\rel{R} \mid \exists t :\: \op{x}{y} \in \rel{R} \right\}. \end{align}

---

If $X$ and $Y$ are sets, and $R$ is a relation between $X$ and $Y$, i.e. $\rel{R} \subseteq X \times Y$.

Let $\rel{T}$ is a composite relation on $Y$, i.e. $\rel{T} \subseteq Y \times Y$, which satisfies $\rel{T} = \rel{R}^{-1}\circ\rel{R}$.

Assume $\op{x}{y} \in \rel{R},\; x \in \dom{R} \subseteq X,\; y \in \ran{R} \subseteq Y$.

\begin{align} \op{x}{y} \in \rel{R} &\implies \op{y}{x} \in \rel{R}^{-1} \\ &\implies \op{y}{y} \in \rel{R}^{-1}\circ\rel{R} \\ &\implies \op{x}{x} \in \rel{T} \end{align}

Therefore, the composite relation $\rel{T}$ is reflexive.

Assume $\op{a}{b} \in \rel{T},\; a \in \dom{T} \subseteq Y,\; b \in \ran{T} \subseteq Y$.

\begin{align} \op{a}{b} \in \rel{T} &\implies \op{a}{b} \in \rel{R}^{-1}\circ\rel{R} \\ &\implies \exists t \in X :\: \op{a}{t} \in \rel{R}^{-1} \;\land\; \op{t}{b} \in \rel{R} \\ &\implies \exists t \in X :\: \op{b}{t} \in \rel{R}^{-1} \;\land\; \op{t}{a} \in \rel{R} \\ &\implies \op{b}{a} \in \rel{R}^{-1}\circ\rel{R} \\ &\implies \op{b}{a} \in \rel{T} \end{align}

Therefore, the composite relation $\rel{T}$ is symmetric.

Sufficiency:

Given $\rel{R} = \rel{R}^{-1}\circ\rel{R}$, because $\rel{R}^{-1}\circ\rel{R}$ is both reflexive and symmetric, $\rel{R}$ has the same properties.

Suppose $\ran{R} \cap \dom{R} \neq \varnothing$, hence $\exists b :\: \op{a}{b} \in \rel{R}$, $\op{b}{c} \in \rel{R}$, \begin{align} \op{a}{b} \in \rel{R} \land \op{b}{c} \in \rel{R} &\implies \op{a}{b} \in \rel{R}^{-1} \land \op{b}{c} \in \rel{R} \\ &\implies \op{a}{c} \in \rel{R}^{-1}\circ\rel{R} \\ &\implies \op{a}{c} \in \rel{R} \end{align}

Therefore, $\rel{R}$ is transitive as well.

Necessity:

If $\rel{R}$ is both symmetric and transitive, assume $\op{x}{y} \in \rel{R},\;\op{y}{z} \in \rel{R},\;\op{x}{z} \in \rel{R}$, \begin{align} \left\{ \begin{array}{l} \op{x}{z} \in \rel{R} \\ \op{y}{z} \in \rel{R} \end{array} \right. &\implies \left\{ \begin{array}{l} \op{z}{x} \in \rel{R} \\ \op{z}{y} \in \rel{R} \end{array} \right. \\ &\implies \left\{ \begin{array}{l} \op{x}{z} \in \rel{R}^{-1} \\ \op{z}{y} \in \rel{R} \end{array} \right. \\ &\implies \op{x}{y} \in \rel{R}^{-1}\circ\rel{R} \\ \left\{ \begin{array}{l} \op{x}{y} \in \rel{R}^{-1}\circ\rel{R} \\ \op{x}{y} \in \rel{R} \end{array} \right. &\implies \rel{R} = \rel{R}^{-1}\circ\rel{R} \end{align}

---

All in all, $\rel{R}$ is symmetric and transitive if and only if $\rel{R} = \rel{R}^{-1}\circ\rel{R}$.