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. Euclid, a famous Greek mathematician known as the father of geometry, is shown here in detail from The School of Athens by Raphael. ... In mathematics, the concept of binary relation, sometimes called dyadic relation, is exemplified by such ideas as is greater than and is equal to in arithmetic, or is congruent to in geometry, or is an element of or is a subset of in set theory. ... In mathematics, a set can be thought of as any collection of distinct things considered as a whole. ...

In mathematical notation, this is: Mathematical notation is used in mathematics, and throughout the physical sciences, engineering, and economics. ...

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)
• "imples" (implication)

In mathematics, two mathematical objects are considered equal if they are precisely the same in every way. ... A is a subset of B, and B is a superset of A. In mathematics, especially in set theory, a set A is a subset of a set B, if A is contained inside B. The relationship of one set being a subset of another is called inclusion. ... A is a subset of B, and B is a superset of A. In mathematics, especially in set theory, a set A is a subset of a set B, if A is contained inside B. The relationship of one set being a subset of another is called inclusion. ... The feasible regions of linear programming are defined by a set of inequalities. ... In mathematics, a divisor of an integer n, also called a factor of n, is an integer which evenly divides n without leaving a remainder. ... In logic, material implication is a binary operator. ...

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

This article is about the mathematics concept. ... In set theory, a binary relation can have, among other properties, reflexivity or irreflexivity. ... In mathematics, especially order theory, a partially ordered set (or poset for short) is a set equipped with a partial order relation. ... This article is about the mathematics concept. ... In mathematics, a binary relation R on a set X is antisymmetric if, for all a and b in X, if a is related to b and b is related to a, then a = b. ... In mathematics, an equivalence relation on a set X is a binary relation on X that is reflexive, symmetric and transitive, i. ... This article is about the mathematics concept. ... In mathematics, a binary relation R over a set X is symmetric if it holds for all a and b in X that if a is related to b then b is related to a. ... In mathematics, a total order or linear order on a set X is any binary relation on X that is antisymmetric, transitive, and total. ... In mathematics, a binary relation R on a set X is antisymmetric if, for all a and b in X, if a is related to b and b is related to a, then a = b. ... In mathematics, a binary relation R over a set X is total if it holds for all a and b in X that a is related to b or b is related to a (or both). ...

See also

• transitive closure
• transitive reduction
• intransitivity
• reflexive relation
• symmetric relation

In mathematics, the transitive closure of a binary relation R on a set X is the smallest transitive relation on X that contains R. For any relation R the transitive closure of R always exists. ... In mathematics, the transitive reduction of a binary relation R on a set X is the smallest relation on X such that that the transitive closure of is the same as the transitive closure of R. If the transitive closure of R is antisymmetric and finite, then is unique. ... Intransitivity is a scenario in which weighing several options produces a loop of preference. ... In set theory, a binary relation can have, among other properties, reflexivity or irreflexivity. ... In mathematics, a binary relation R over a set X is symmetric if it holds for all a and b in X that if a is related to b then b is related to a. ...

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

This article is being considered for deletion in accordance with Wikipedias deletion policy. ... The On-Line Encyclopedia of Integer Sequences (OEIS) is an extensive searchable database of integer sequences, freely available on the Web. ...

Sources

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