Transitivity I
Task number: 3374
Prove that the relation \(R \subseteq X\times X\) is transitive exactly when \(R\circ R\subseteq R\).
Solution
We divide the proof into two implications.
1. If \(R\) is transitive, then from the definition of a composite relation
\(R\circ R =\{(x,z): \exists y: xRy \land yRz\}\)
it follows that whenever we have such a \(y\), then by the transitivity of \(R\) we have \(xRz\), i.e.
\(\{(x,z): \exists y: xRy \land yRz\} \subseteq R\)
2. Now we assume that \(R\circ R\subseteq R\).
If some \(x\), \(y\) and \(z\) fulfill \(xRy \land yRz\), then from the definition of a composite relation it follows that \(x(R\circ R)z\) and by the assumption \(R\circ R\subseteq R\) we can now derive the desired conclusion \(xRz\).
Formally written:
\(\forall x,y,z: xRy \land yRz \ \Longrightarrow\ x(R\circ R)z\ \Longrightarrow\ xRz\)
