Transitive relation

In mathematics, a relation R on a set X is transitive if, for all elements a, b, c in X, whenever R relates a to b and b to c, then R also relates a to c. Each partial order as well as each equivalence relation needs to be transitive. A homogeneous relation R on the set X is a transitive relation if, for all a, b, c ∈ X, if a R b and b R c, then a R c. Or in terms of first-order logic: where a R b is the infix notation for (a, b) ∈ R. As a non-mathematical example, the relation "is an ancestor of" is transitive. For example, if Amy is an ancestor of Becky, and Becky is an ancestor of Carrie, then Amy, too, is an ancestor of Carrie. On the other hand, "is the birth parent of" is not a transitive relation, because if Alice is the birth parent of Brenda, and Brenda is the birth parent of Claire, then this does not imply that Alice is the birth parent of Claire. What is more, it is antitransitive: Alice can never be the birth parent of Claire. Non-transitive, non-antitransitive relations include sports fixtures (playoff schedules), 'knows' and 'talks to'. "Is greater than", "is at least as great as", and "is equal to" (equality) are transitive relations on various sets, for instance, the set of real numbers or the set of natural numbers: whenever x > y and y > z, then also x > z whenever x ≥ y and y ≥ z, then also x ≥ z whenever x = y and y = z, then also x = z. More examples of transitive relations: "is a subset of" (set inclusion, a relation on sets) "divides" (divisibility, a relation on natural numbers) "implies" (implication, symbolized by "⇒", a relation on propositions) Examples of non-transitive relations: "is the successor of" (a relation on natural numbers) "is a member of the set" (symbolized as "∈") "is perpendicular to" (a relation on lines in Euclidean geometry) The empty relation on any set is transitive because there are no elements such that and , and hence the transitivity condition is vacuously true.