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\).

Difficulty level: Moderate task
Proving or derivation task
Cs translation
Send comment on task by email