In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, a
relation on a set is transitive if, for all elements , , in , whenever relates to and to , then also relates to . Each
partial order
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary ...
as well as each
equivalence relation
In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation.
Each equivalence relation ...
needs to be transitive.
Definition
A
homogeneous relation
In mathematics, a homogeneous relation (also called endorelation) over a set ''X'' is a binary relation over ''X'' and itself, i.e. it is a subset of the Cartesian product . This is commonly phrased as "a relation on ''X''" or "a (binary) relation ...
on the set is a ''transitive relation'' if,
:for all , if and , then .
Or in terms of
first-order logic
First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifie ...
:
:
,
where is the
infix notation
Infix notation is the notation commonly used in arithmetical and logical formulae and statements. It is characterized by the placement of operators between operands—" infixed operators"—such as the plus sign in .
Usage
Binary relations a ...
for .
Examples
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
In mathematics, intransitivity (sometimes called nontransitivity) is a property of binary relations that are not transitive relations. This may include any relation that is not transitive, or the stronger property of antitransitivity, which descri ...
: Alice can ''never'' be the birth parent of Claire.
"Is greater than", "is at least as great as", and "is equal to" (
equality
Equality may refer to:
Society
* Political equality, in which all members of a society are of equal standing
** Consociationalism, in which an ethnically, religiously, or linguistically divided state functions by cooperation of each group's elit ...
) 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
In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are ...
of" (set inclusion, a relation on sets)
* "divides" (
divisibility
In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a multiple of m. An integer n is divisible or evenly divisible by ...
, a relation on natural numbers)
* "implies" (
implication, symbolized by "⇒", a relation on
proposition
In logic and linguistics, a proposition is the meaning of a declarative sentence. In philosophy, " meaning" is understood to be a non-linguistic entity which is shared by all sentences with the same meaning. Equivalently, a proposition is the no ...
s)
Examples of non-transitive relations:
* "is the
successor
Successor may refer to:
* An entity that comes after another (see Succession (disambiguation))
Film and TV
* ''The Successor'' (film), a 1996 film including Laura Girling
* ''The Successor'' (TV program), a 2007 Israeli television program Musi ...
of" (a relation on natural numbers)
* "is a member of the set" (symbolized as "∈")
* "is
perpendicular
In elementary geometry, two geometric objects are perpendicular if they intersect at a right angle (90 degrees or π/2 radians). The condition of perpendicularity may be represented graphically using the ''perpendicular symbol'', ⟂. It can ...
to" (a relation on lines in
Euclidean geometry
Euclidean geometry is a mathematical system attributed to ancient Greek mathematics, Greek mathematician Euclid, which he described in his textbook on geometry: the ''Euclid's Elements, Elements''. Euclid's approach consists in assuming a small ...
)
The
empty relation
In mathematics, a homogeneous relation (also called endorelation) over a set ''X'' is a binary relation over ''X'' and itself, i.e. it is a subset of the Cartesian product . This is commonly phrased as "a relation on ''X''" or "a (binary) relation ...
on any set
is transitive because there are no elements
such that
and
, and hence the transitivity condition is
vacuously true
In mathematics and logic, a vacuous truth is a conditional or universal statement (a universal statement that can be converted to a conditional statement) that is true because the antecedent cannot be satisfied. For example, the statement "she d ...
. A relation containing only one
ordered pair
In mathematics, an ordered pair (''a'', ''b'') is a pair of objects. The order in which the objects appear in the pair is significant: the ordered pair (''a'', ''b'') is different from the ordered pair (''b'', ''a'') unless ''a'' = ''b''. (In con ...
is also transitive: if the ordered pair is of the form
for some
the only such elements
are
, and indeed in this case
, while if the ordered pair is not of the form
then there are no such elements
and hence
is vacuously transitive.
Properties
Closure properties
* The
converse
Converse may refer to:
Mathematics and logic
* Converse (logic), the result of reversing the two parts of a definite or implicational statement
** Converse implication, the converse of a material implication
** Converse nonimplication, a logical c ...
(inverse) of a transitive relation is always transitive. For instance, knowing that "is a
subset
In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are ...
of" is transitive and "is a
superset
In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset of ...
of" is its converse, one can conclude that the latter is transitive as well.
* The intersection of two transitive relations is always transitive. For instance, knowing that "was born before" and "has the same first name as" are transitive, one can conclude that "was born before and also has the same first name as" is also transitive.
* The union of two transitive relations need not be transitive. For instance, "was born before or has the same first name as" is not a transitive relation, since e.g.
Herbert Hoover
Herbert Clark Hoover (August 10, 1874 – October 20, 1964) was an American politician who served as the 31st president of the United States from 1929 to 1933 and a member of the Republican Party, holding office during the onset of the Gr ...
is related to
Franklin D. Roosevelt
Franklin Delano Roosevelt (; ; January 30, 1882April 12, 1945), often referred to by his initials FDR, was an American politician and attorney who served as the 32nd president of the United States from 1933 until his death in 1945. As the ...
, which is in turn related to
Franklin Pierce
Franklin Pierce (November 23, 1804October 8, 1869) was the 14th president of the United States, serving from 1853 to 1857. He was a northern Democrat who believed that the abolitionist movement was a fundamental threat to the nation's unity ...
, while Hoover is not related to Franklin Pierce.
* The complement of a transitive relation need not be transitive. For instance, while "equal to" is transitive, "not equal to" is only transitive on sets with at most one element.
Other properties
A transitive relation is
asymmetric if and only if it is
irreflexive
In mathematics, a binary relation ''R'' on a set ''X'' is reflexive if it relates every element of ''X'' to itself.
An example of a reflexive relation is the relation " is equal to" on the set of real numbers, since every real number is equal ...
.
A transitive relation need not be
reflexive. When it is, it is called a
preorder
In mathematics, especially in order theory, a preorder or quasiorder is a binary relation that is reflexive and transitive. Preorders are more general than equivalence relations and (non-strict) partial orders, both of which are special c ...
. For example, on set ''X'' = :
* ''R'' = is reflexive, but not transitive, as the pair (1,2) is absent,
* ''R'' = is reflexive as well as transitive, so it is a preorder,
* ''R'' = is reflexive as well as transitive, another preorder.
Transitive extensions and transitive closure
Let be a binary relation on set . The ''transitive extension'' of , denoted , is the smallest binary relation on such that contains , and if and then . For example, suppose is a set of towns, some of which are connected by roads. Let be the relation on towns where if there is a road directly linking town and town . This relation need not be transitive. The transitive extension of this relation can be defined by if you can travel between towns and by using at most two roads.
If a relation is transitive then its transitive extension is itself, that is, if is a transitive relation then .
The transitive extension of would be denoted by , and continuing in this way, in general, the transitive extension of would be . The ''transitive closure'' of , denoted by or is the set union of , , , ... .
The transitive closure of a relation is a transitive relation.
The relation "is the birth parent of" on a set of people is not a transitive relation. However, in biology the need often arises to consider birth parenthood over an arbitrary number of generations: the relation "is a birth ancestor of" ''is'' a transitive relation and it is the transitive closure of the relation "is the birth parent of".
For the example of towns and roads above, provided you can travel between towns and using any number of roads.
Relation types that require transitivity
*
Preorder
In mathematics, especially in order theory, a preorder or quasiorder is a binary relation that is reflexive and transitive. Preorders are more general than equivalence relations and (non-strict) partial orders, both of which are special c ...
– a
reflexive and transitive relation
*
Partial order
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary ...
– an
antisymmetric preorder
*
Total preorder
In mathematics, especially order theory, a weak ordering is a mathematical formalization of the intuitive notion of a ranking of a set, some of whose members may be tied with each other. Weak orders are a generalization of totally ordered set ...
– a
connected
Connected may refer to:
Film and television
* ''Connected'' (2008 film), a Hong Kong remake of the American movie ''Cellular''
* '' Connected: An Autoblogography About Love, Death & Technology'', a 2011 documentary film
* ''Connected'' (2015 TV ...
(formerly called total) preorder
*
Equivalence relation
In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation.
Each equivalence relation ...
– a
symmetric
Symmetry (from grc, συμμετρία "agreement in dimensions, due proportion, arrangement") in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more precise definiti ...
preorder
*
Strict weak ordering – a strict partial order in which incomparability is an equivalence relation
*
Total ordering
In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X:
# a \leq a ( reflexive) ...
– a connected (total), antisymmetric, and transitive relation
Counting transitive relations
No general formula that counts the number of transitive relations on a finite set is known. However, there is a formula for finding the number of relations that are simultaneously reflexive, symmetric, and transitive – in other words,
equivalence relation
In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation.
Each equivalence relation ...
s – , those that are symmetric and transitive, those that are symmetric, transitive, and antisymmetric, and those that are total, transitive, and antisymmetric. Pfeiffer has made some progress in this direction, expressing relations with combinations of these properties in terms of each other, but still calculating any one is difficult. See also Brinkmann and McKay (2005). Mala showed that no polynomial with integer coefficients can represent a formula for the number of transitive relations on a set, and found certain recursive relations that provide lower bounds for that number. He also showed that that number is a polynomial of degree two if contains exactly two
ordered pair
In mathematics, an ordered pair (''a'', ''b'') is a pair of objects. The order in which the objects appear in the pair is significant: the ordered pair (''a'', ''b'') is different from the ordered pair (''b'', ''a'') unless ''a'' = ''b''. (In con ...
s.
Related properties
![Rock-paper-scissors](https://upload.wikimedia.org/wikipedia/commons/6/67/Rock-paper-scissors.svg)
A relation ''R'' is called ''
intransitive
In grammar, an intransitive verb is a verb whose context does not entail a direct object. That lack of transitivity distinguishes intransitive verbs from transitive verbs, which entail one or more objects. Additionally, intransitive verbs ar ...
'' if it is not transitive, that is, if ''xRy'' and ''yRz'', but not ''xRz'', for some ''x'', ''y'', ''z''.
In contrast, a relation ''R'' is called ''
antitransitive
In mathematics, intransitivity (sometimes called nontransitivity) is a property of binary relations that are not transitive relations. This may include any relation that is not transitive, or the stronger property of antitransitivity, which descri ...
'' if ''xRy'' and ''yRz'' always implies that ''xRz'' does not hold.
For example, the relation defined by ''xRy'' if ''xy'' is an
even number is intransitive, but not antitransitive. The relation defined by ''xRy'' if ''x'' is even and ''y'' is
odd
Odd means unpaired, occasional, strange or unusual, or a person who is viewed as eccentric.
Odd may also refer to:
Acronym
* ODD (Text Encoding Initiative) ("One Document Does it all"), an abstracted literate-programming format for describing X ...
is both transitive and antitransitive.
The relation defined by ''xRy'' if ''x'' is the
successor
Successor may refer to:
* An entity that comes after another (see Succession (disambiguation))
Film and TV
* ''The Successor'' (film), a 1996 film including Laura Girling
* ''The Successor'' (TV program), a 2007 Israeli television program Musi ...
number of ''y'' is both intransitive and antitransitive. Unexpected examples of intransitivity arise in situations such as political questions or group preferences.
Generalized to stochastic versions (''
stochastic transitivity Stochastic transitivity models are stochastic versions of the transitivity property of binary relations studied in mathematics. Several models of stochastic transitivity exist and have been used to describe the probabilities involved in experiment ...
''), the study of transitivity finds applications of in
decision theory
Decision theory (or the theory of choice; not to be confused with choice theory) is a branch of applied probability theory concerned with the theory of making decisions based on assigning probabilities to various factors and assigning numerical ...
,
psychometrics
Psychometrics is a field of study within psychology concerned with the theory and technique of measurement. Psychometrics generally refers to specialized fields within psychology and education devoted to testing, measurement, assessment, and ...
and
utility models
A utility model is a patent-like intellectual property right to protect inventions. This type of right is available in many countries but, notably, not in the United States, United Kingdom or Canada. Although a utility model is similar to a patent ...
.
A ''
quasitransitive relation
The mathematical notion of quasitransitivity is a weakened version of transitivity that is used in social choice theory and microeconomics. Informally, a relation is quasitransitive if it is symmetric for some values and transitive elsewhere. Th ...
'' is another generalization; it is required to be transitive only on its non-symmetric part. Such relations are used in
social choice theory
Social choice theory or social choice is a theoretical framework for analysis of combining individual opinions, preferences, interests, or welfares to reach a ''collective decision'' or ''social welfare'' in some sense.Amartya Sen (2008). "Soci ...
or
microeconomics
Microeconomics is a branch of mainstream economics that studies the behavior of individuals and firms in making decisions regarding the allocation of scarce resources and the interactions among these individuals and firms. Microeconomics fo ...
.
Proposition: If ''R'' is a
univalent, then R;R
T is transitive.
: proof: Suppose
Then there are ''a'' and ''b'' such that
Since ''R'' is univalent, ''yRb'' and ''aR''
T''y'' imply ''a''=''b''. Therefore ''x''R''a''R
T''z'', hence ''x''R;R
T''z'' and R;R
T is transitive.
Corollary: If ''R'' is univalent, then R;R
T is an
equivalence relation
In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation.
Each equivalence relation ...
on the domain of ''R''.
: proof: R;R
T is symmetric and reflexive on its domain. With univalence of ''R'', the transitive requirement for equivalence is fulfilled.
See also
*
Transitive reduction
In the mathematical field of graph theory, a transitive reduction of a directed graph is another directed graph with the same vertices and as few edges as possible, such that for all pairs of vertices , a (directed) path from to in exists i ...
*
Intransitive dice
A set of dice is intransitive (or nontransitive) if it contains three dice, ''A'', ''B'', and ''C'', with the property that ''A'' rolls higher than ''B'' more than half the time, and ''B'' rolls higher than ''C'' more than half the time, but it is ...
*
Rational choice theory
Rational choice theory refers to a set of guidelines that help understand economic and social behaviour. The theory originated in the eighteenth century and can be traced back to political economist and philosopher, Adam Smith. The theory postula ...
*
Hypothetical syllogism
In classical logic, a hypothetical syllogism is a valid argument form, a syllogism with a conditional statement for one or both of its premises.
An example in English:
:If I do not wake up, then I cannot go to work.
:If I cannot go to work, then ...
— transitivity of the material conditional
Notes
References
*
*
*
Gunther Schmidt
Gunther Schmidt (born 1939, Rüdersdorf) is a German mathematician who works also in informatics.
Life
Schmidt began studying Mathematics in 1957 at Göttingen University. His academic teachers were in particular Kurt Reidemeister, Wilhelm Kl ...
, 2010. ''Relational Mathematics''. Cambridge University Press, .
*
External links
* {{springer, title=Transitivity, id=p/t093810
Transitivity in Actionat
cut-the-knot
Alexander Bogomolny (January 4, 1948 July 7, 2018) was a Soviet-born Israeli-American mathematician. He was Professor Emeritus of Mathematics at the University of Iowa, and formerly research fellow at the Moscow Institute of Electronics and Math ...
Binary relations
Elementary algebra