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) ρ is a partial order if and only if ρ^−1 is a partial order

Answer 1

(i) Recall that a relation $\rho$ is called a partial order if it is reflexive, transitive and antisymmetric.

Let $\rho$ be a partial order.

Since $\rho$ is a reflexive relation, $(a,a)\in\rho$ for any $a\in A.$ The defenition of $\rho^{-1}$ implies that

$(a,a)\in\rho^{-1}$ for any $a\in A.$ Thus, $\rho^{-1}$ is reflexive as well.

Let $(a,b)\in\rho^{-1}, (b,c)\in\rho^{-1}.$ Then $(b,a)\in\rho, (c,b)\in\rho.$ Since $\rho$ is transitive, $(c,a)\in\rho$, and therefore, $(a,c)\in\rho^{-1}.$ This implies that $\rho^{-1}$ is a transitive relation.

Let $(a,b)\in\rho^{-1}, (b,a)\in\rho^{-1}.$ By definition of $\rho^{-1},$ $(b,a)\in\rho$ and $(a,b)\in\rho$. Since $\rho$ is antisymmetric, $a=b.$ Therefore, $\rho^{-1}$ is antisymmetric. We conclude that $\rho^{-1}$ is a partial order.

Let us prove in the other direction.

Let $\rho^{-1}$ be a partial order.

Since $\rho^{-1}$ is a reflexive relation, $(a,a)\in\rho^{-1}$ for any $a\in A.$ The defenition of $\rho^{-1}$ implies that

$(a,a)\in\rho$ for any $a\in A.$ Thus, $\rho$ is reflexive as well.

Let $(a,b)\in\rho, (b,c)\in\rho.$ Then $(b,a)\in\rho^{-1}, (c,b)\in\rho^{-1}.$ Since $\rho^{-1}$ is transitive, $(c,a)\in\rho^{-1}$, and therefore, $(a,c)\in\rho.$ This implies that $\rho$ is a transitive relation.

Let $(a,b)\in\rho, (b,a)\in\rho.$ By definition of $\rho^{-1},$ $(b,a)\in\rho^{-1}$ and $(a,b)\in\rho^{-1}$. Since $\rho^{-1}$ is antisymmetric, $a=b.$ Therefore, $\rho$ is antisymmetric. We conclude that $\rho$ is a partial order.