1

If $R$ is transitive relation. How can I prove that composition of its transpose is also transitive.

i.e. $R^T\ ;R^T$ is transitive too.

TechJ
  • 295
  • What is the transposition of a relation? – Git Gud Oct 30 '15 at 16:22
  • 1
    @GitGud the matrix of a relation is its adjacency matrix. That is, the matrix of a relation on $n$ elements is an $n \times n$ matrix whose $a=i,j$ entry is a $1$ if $(x_i,x_j) \in R$ and $0$ otherwise. The transpose relation is the relation corresponding to the transposed graph. – Ben Grossmann Oct 30 '15 at 16:25
  • More concisely: $xRy \iff y R^Tx$ – Ben Grossmann Oct 30 '15 at 16:26

1 Answers1

5

Let $x R^T y$ and $ y R^T z$. Then $ zRy $ and $ yRx$ by definition of the transpose relation. Since $R$ is transitive, that means that $zRx$. Again, by definition of the transpose relation, $xR^Tz$.

Kevin Long
  • 5,159