Answer to Question #136799 in Discrete Mathematics for ashmita

Question

Let ρ be a relation on a set A. Define ρ^−1 = {(b, a) | (a, b) ∈ ρ}. Also, for two relations ρ, σ on
A, define the composite relation ρ ◦ σ as (a, c) ∈ ρ ◦ σ if and only if there exists b ∈ A such that (a, b) ∈ ρ and (b, c) ∈ σ. Prove the following assertions.

i.) If ρ is non-empty, then ρ is an equivalence relation if and only if ρ^−1 ◦ ρ = ρ.

Answer 1

If $\rho^{-1}\circ\rho=\rho$, then $\rho$ can be not an equivalence relation. Indeed, if $A=\{a,b,c\}$ and $\rho=\{(a,b),(b,b),(a,a),(b,a)\}$, then $\rho^{-1}\circ\rho=\rho$, but $(c,c)\not\in\rho$, so $\rho$ is not an equivalence relation on $A$.

We prove that if $\rho^{-1}\circ\rho=\rho$, then $\rho$ is an equivalence relation on $A=\bigcup\limits_{(u,v)\in\rho}\{u,v\}$.

Indeed,

1)Let $(a,b)\in\rho$. Since $\rho=\rho^{-1}\circ\rho$, there is $x\in A$ such that $(a,x)\in\rho^{-1}$, that is $(x,a)\in\rho$, and $(x,b)\in\rho$.

Since $(x,a)\in\rho$, we have $(a,x)\in\rho^{-1}$, so $(a,a)\in\rho^{-1}\circ\rho=\rho$. And since $(x,b)\in\rho$, we similarly obtain $(b,b)\in\rho$.

So $\rho$ is reflexive on $A=\bigcup\limits_{(u,v)\in\rho}\{u,v\}$.

2)Let $(a,b)\in\rho$. Then $(b,a)\in\rho^{-1}$ and by point 1) we have $(a,a)\in\rho$, so $(b,a)\in\rho^{-1}\circ\rho=\rho$. So $\rho$ is symmetric on $A=\bigcup\limits_{(u,v)\in\rho}\{u,v\}$.

3)Let $(a,b),(b,c)\in\rho$. By point 2) we have $(b,a)\in\rho$, that is $(a,b)\in\rho^{-1}$. So since $(b,c)\in\rho$, we have $(a,c)\in\rho^{-1}\circ\rho=\rho$.

So $\rho$ is transitive on $A=\bigcup\limits_{(u,v)\in\rho}\{u,v\}$.

We obtain that $\rho$ is an equivalence relation on $A=\bigcup\limits_{(u,v)\in\rho}\{u,v\}$.

Now let $\rho$ be an equivalence relation on a set $A$. Note that then $A=\bigcup\limits_{(u,v)\in\rho}\{u,v\}$. Prove that $\rho^{-1}\circ\rho=\rho$.

Since $\rho$ is symmetric, we have $\rho^{-1}\subset\rho$, so $\rho^{-1}\circ\rho\subset\rho^2$. Since $\rho$ is transtitive, we have $\rho^2\subset\rho$, that is $\rho^{-1}\circ\rho\subset\rho$.

Now prove that $\rho^{-1}\circ\rho\supset\rho$.

Indeed, let $(a,b)\in\rho$. We have $a\in A$, so $(a,a)\in\rho$, that is $(a,a)\in\rho^{-1}$. Then $(a,b)\in\rho^{-1}\circ\rho$. So we obtain $\rho^{-1}\circ\rho\supset\rho$.

We have $\rho^{-1}\circ\rho=\rho$.

So we proved that $\rho^{-1}\circ\rho=\rho$ if and only if $\rho$ is an equivalence relation on $A=\bigcup\limits_{(u,v)\in\rho}\{u,v\}$