Transitive Relation

A relation is transitive if for any three elements: if (a,b) and (b,c) are in the relation, then (a,c) is also in it.

In other words: if the connection holds between the first and second, and the second and third elements, then it must also hold between the first and the third.

Examples of Transitive Relations

• The ≤ relation is transitive: if 2 ≤ 4 and 4 ≤ 6, then 2 ≤ 6.
• The = relation is also transitive: if a = b and b = c, then a = c.
• The divisibility relation is transitive: if 2 divides 4 and 4 divides 8, then 2 divides 8.

Counterexamples (Non-Transitive Relations)

• The sibling relation is not transitive: if Anna is sibling of Béla and Béla of Csaba, then Anna is not necessarily sibling of Csaba.
• The friend relation is also not transitive: if Anna is friend of Béla and Béla of Csaba, it does not mean Anna is friend of Csaba.

Summary

Transitivity ensures that the connection can be transferred from one element to another through intermediaries. Therefore, transitive relations are very important in defining orderings and mathematical structures.

Practice Exercise