Transitive relation

Formal definition

In mathematics, a binary relation R over a set X is transitive if it holds for all a, b, and c in X, that if a is related to b and b is related to c, then a is related to c.

To write this in predicate logic:

\forall a, b, c  \in X,\ a  \,R\, b \and b \,R\, c \; \Rightarrow a \,R\, c

Counting transitive relations

Unlike other relation properties, it is not possible to find a general formula that counts the number of transitive relations on a finite set. However, there is a formula for finding the number of relations which are simultaneously reflexive, symmetric, and transitive

Examples

For example, "is greater than" and "is equal to" are transitive relations: if a = b and b = c, then a = c.

On the other hand, "is the mother of" is not a transitive relation, because if Alice is the mother of Brenda, and Brenda is the mother of Claire, then Alice is not the mother of Claire.

Examples of transitive relations include:

"is equal to" (equality)
"is a superset of"
"is a subset of" (set inclusion)
"is less than" and "is less than or equal to" (inequality)
"divides" (divisibility)
"implies" (implication)

Other properties that require transitivity

preorder - a transitive relation that is also reflexive.
partial order - a preorder that is antisymmetric.
equivalence relation - a relation that is a preorder and symmetric.
total ordering - a relation is a total order if it is transitive, antisymmetric, and total

External links

Transitivity in Action at cut-the-knot
Number of transitive relations on n labeled nodes, sequence A006905 from the On-Line Encyclopedia of Integer Sequences

Set theory

Sources

Discrete and Combinatorial Mathematics - Fifth Edition - by Ralph P. Grimaldi