Collection of Maths Problems

Closure of transitivity

Task number: 3371

• Variant

  \(R\cup S\)

• Solution

  On the set \(X=\{a,b,c\}\) consider the transitive relations \(R=\{(a,b)\}\) and \(S=\{(b,c)\}\). The union \(R\cup S\) contains both pairs, but does not contain the pair \((a,c)\).

• Answer

  The union of transitive relations need not be transitive.

• Variant

  \(R\cap S\)

• Solution

  If \((a,b),(b,c)\in R\cap S\), then these two pairs must be in both relations. By the transitivity of \(R\) and \(S\) both relations must also contain the pair \((a,c)\).

• Answer

  The relation \(R\cap S\) is transitive.

• Variant

  \(R\setminus S\)

• Solution

  If e.g. \(R\) contains all pairs on a two-element set and \(S\) contains only the reflexive pairs, then both relations are reflexive, but \(R\setminus S\) is not.

• Answer

  The relation \(R\setminus S\) need not be transitive.

• Variant

  \(R\mathbin{\Delta}S\)

• Solution

  If e.g. \(R\) contains all pairs on a two-element set and \(S\) contains only the reflexive pairs, then both relations are reflexive, but \(R\mathbin{\Delta}S=R\setminus S\) is not.

• Answer

  The relation \(R\mathbin{\Delta}S\) need not be transitive.

• Variant

  \(R\circ S\)

• Solution

  On the set \(X=\{a,b,c\}\) consider the transitive relations \(R=\{(a,a),(b,c)\}\) and \(S=\{(a,b),(c,c)\}\). The composition \(R\circ S\) contains the pairs \((a,b),(b,c)\), but not the pair \((a,c)\).

• Answer

  The composition of transitive relations need not be transitive.

• Variant

  \(R^{-1}\)

• Solution

  If \((a,b),(b,c)\in R^{-1}\), then the pairs \((c,b),(b,a)\in R\). By the transitivity of \(R\) we have \((c,a)\in R\) and so \((a,c)\in R^{-1}\).

• Answer

  The relation \(R^{-1}\) is transitive.