Transitive relation
Encyclopedia : T : TR : TRA : 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
See also
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
Sources
- Discrete and Combinatorial Mathematics - Fifth Edition - by Ralph P. Grimaldi
From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.