Answer to Question #153441 in Discrete Mathematics for likhit sankad

Question

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

Answer 1

a) $\rho$ is both symm etric and anti-symmetric. This means if $(a,b)\in \rho$ then $(b,a)\in \rho , (b,a)\notin\rho$ if $a,b$ are distinct. This is impossible. Hence only elements of $\rho$ are $(a,a)$ and hence $\rho\subseteq\{(a,a)|a\in A\}.$ Conversely , by definition, $(a,b)\notin\rho$ if $a,b$ are distinct. Hence $\rho$ is symmetric and anti-symmetric vacuously true.

b) Let $\rho$ be transitive. Let $\rho =\{(1,2),(2,3),(1,3),(5,6)\}$. Then $\rho$ is transitive. But $\rho o\rho =\{(1,3)\}\neq \rho.$ Hence the given question is wrong(only if part).

(if part) Let $(a,b) , (b,c)\in \rho.$ Then by definition $(a,c)\in\rho o \rho.$ Hence $(a,c)\in \rho.$ Hence the relation is transitive.