Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Transitive relation
Summary
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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.