Transitivity II
Task number: 3375
Prove that for every relation \(R \subseteq X\times X\), the relation \(T\) defined as \(T=\bigcup\limits_{i=1}^\infty R^i\) is transitive.
Hint
What can we infer from the relationship \(xTy\)?
Solution
Assume that \(xTy \land yTz\).
Notice that
\(xTy \ \Longrightarrow\ (x,y)\in \bigcup\limits_{i=1}^\infty R^i \ \Longrightarrow\ \exists i: (x,y)\in R^i\).
because if an element belongs to a union of sets (even an infinite one), it must belong to at least one of the sets.
Similarly \(yTz \ \Longrightarrow\ \exists j: (y,z)\in R^j\).
Composing the relations, it follows that
\(xR^iy \land yR^jz \ \Longrightarrow\ xR^{i+j}z \ \Longrightarrow\ xTz\),
which proves the transitivity of \(T\).
