Editing Transitive closure (section)

== Transitive relations and examples ==

A relation ''R'' on a set ''X'' is transitive if, for all ''x'', ''y'', ''z'' in ''X'', whenever {{nowrap|''x R y''}} and {{nowrap|''y R z''}} then {{nowrap|''x R z''}}. Examples of transitive relations include the equality relation on any set, the "less than or equal" relation on any linearly ordered set, and the relation "''x'' was born before ''y''" on the set of all people. Symbolically, this can be denoted as: if {{nowrap|''x'' < ''y''}} and {{nowrap|''y'' < ''z''}} then {{nowrap|''x'' < ''z''}}.

One example of a non-transitive relation is "city ''x'' can be reached via a direct flight from city ''y''" on the set of all cities. Simply because there is a direct flight from one city to a second city, and a direct flight from the second city to the third, does not imply there is a direct flight from the first city to the third. The transitive closure of this relation is a different relation, namely "there is a sequence of direct flights that begins at city ''x'' and ends at city ''y''". Every relation can be extended in a similar way to a transitive relation.

An example of a non-transitive relation with a less meaningful transitive closure is "''x'' is the [[day of the week]] after ''y''". The transitive closure of this relation is "some day ''x'' comes after a day ''y'' on the calendar", which is trivially true for all days of the week ''x'' and ''y'' (and thus equivalent to the [[Cartesian product|Cartesian square]], which is "''x'' and ''y'' are both days of the week").