HOME

TheInfoList




In
mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and their changes (cal ...
, a relation on a set is transitive if, for all elements , , in , whenever relates to and to , then also relates to . Each
partial order upright=1.15, Fig.1 The set of all subsets of a three-element set \, ordered by set inclusion">inclusion Inclusion or Include may refer to: Sociology * Social inclusion, affirmative action to change the circumstances and habits that leads to s ...
as well as each
equivalence relation In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). ...
needs to be transitive.


Definition

A
homogeneous relation Homogeneity and heterogeneity are concepts often used in the sciences and statistics Statistics is the discipline that concerns the collection, organization, analysis, interpretation, and presentation of data. In applying statistics to a sc ...
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 system A formal system is an used for inferring theorems from axioms according to a set of rules. These rul ...
: :\forall a,b,c \in X: (aRb \wedge bRc) \Rightarrow aRc, where is the
infix notation Infix notation is the notation commonly used in arithmetical and logic Logic (from Ancient Greek, Greek: grc, wikt:λογική, λογική, label=none, lit=possessed of reason, intellectual, dialectical, argumentative, translit=logikḗ) ...
for .


Examples

As a nonmathematical 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 Alice is not the birth parent of Claire. What is more, it is
antitransitive In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It h ...
: Alice can ''never'' be the birth parent of Claire. "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 In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). ...

subset
of" (set inclusion, a relation on sets) * "divides" (
divisibility In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). ...

divisibility
, a relation on natural numbers) * "implies" ( implication, symbolized by "⇒", a relation on
proposition In logic Logic is an interdisciplinary field which studies truth and reasoning Reason is the capacity of consciously making sense of things, applying logic Logic (from Ancient Greek, Greek: grc, wikt:λογική, λογική, lab ...
s) Examples of non-transitive relations: * "is the
successor Successor is someone who, or something which succeeds or comes after (see success (disambiguation), success and Succession (disambiguation), succession) Film and TV * The Successor (film), ''The Successor'' (film), a 1996 film including Laura Girli ...
of" (a relation on natural numbers) * "is a member of the set" (symbolized as "∈") * "is
perpendicular In elementary geometry Geometry (from the grc, γεωμετρία; ' "earth", ' "measurement") is, with , one of the oldest branches of . It is concerned with properties of space that are related with distance, shape, size, and relativ ...

perpendicular
to" (a relation on lines in
Euclidean geometry Euclidean geometry is a mathematical system attributed to Alexandria Alexandria ( or ; ar, الإسكندرية ; arz, اسكندرية ; Coptic Coptic may refer to: Afro-Asia * Copts, an ethnoreligious group mainly in the area of modern ...
) The
empty relation Empty may refer to: ‍ Music Albums * ''Empty'' (God Lives Underwater album) or the title song, 1995 * ''Empty'' (Nils Frahm album), 2020 * ''Empty'' (Tait album) or the title song, 2001 Songs * "Empty" (The Click Five song), 2007 * ...
on any set X is transitive because there are no elements a,b,c \in X such that aRb and bRc, and hence the transitivity condition is
vacuously trueIn mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ha ...
. A relation containing only one
ordered pair In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It h ...

ordered pair
is also transitive: if the ordered pair is of the form (x, x) for some x \in X the only such elements a,b,c \in X are a=b=c=x, and indeed in this case aRc, while if the ordered pair is not of the form (x, x) then there are no such elements a,b,c \in X and hence R 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 categorical or implicational statement ** Converse implication, the converse of a material implication ** Converse nonimplication, a logical ...
(inverse) of a transitive relation is always transitive. For instance, knowing that "is a
subset In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). ...

subset
of" is transitive and "is a
superset In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). ...
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 and engineer who served as the 31st president of the United States The president of the United States (POTUS) is the head of state and head of gove ...

Herbert Hoover
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 who served as the 32nd president of the United States from 1933 until his death in 1945. A member of the De ...

Franklin D. Roosevelt
, which is in turn related to
Franklin Pierce Franklin Pierce (November 23, 1804October 8, 1869) was the 14th president of the United States The president of the United States (POTUS) is the and of the . The president directs the of the and is the of the . The power of the ...

Franklin Pierce
, 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 homogeneous binary relation ''R'' over a set (mathematics), set ''X'' is reflexive if it relates every element of ''X'' to itself. An example of a reflexive relation is the relation "equality (mathematics), is equal to" on the se ...
. A transitive relation need not be reflexive. When it is, it is called a
preorder In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities a ...
. 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 properties that require transitivity

*
Preorder In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities a ...
– a reflexive and transitive relation *
Partial order upright=1.15, Fig.1 The set of all subsets of a three-element set \, ordered by set inclusion">inclusion Inclusion or Include may refer to: Sociology * Social inclusion, affirmative action to change the circumstances and habits that leads to s ...
– an antisymmetric preorder *
Total preorder The 13 possible strict weak orderings on a set of three elements . The only total orders are shown in black. Two orderings are connected by an edge if they differ by a single dichotomy. In mathematics Mathematics (from Ancient Greek, Gre ...
– a connected (formerly called total) preorder *
Equivalence relation In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). ...
– a
symmetric Symmetry (from Greek συμμετρία ''symmetria'' "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 pre ...
preorder *
Strict weak ordering The 13 possible strict weak orderings on a set of three elements . The only total orders are shown in black. Two orderings are connected by an edge if they differ by a single dichotomy. In mathematics Mathematics (from Ancient Greek, Gre ...
– a strict partial order in which incomparability is an equivalence relation *
Total ordering In mathematics, a total order, simple order, linear order, connex order, or full order is a binary relation on some Set (mathematics), set X, which is Antisymmetric relation, antisymmetric, Transitive relation, transitive, and a connex relation. ...
– 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 Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). ...
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 .


Related properties

A relation ''R'' is called ''
intransitive In grammar In linguistics, the grammar (from Ancient Greek ''grammatikḗ'') of a natural language is its set of structure, structural constraints on speakers' or writers' composition of clause (linguistics), clauses, phrases, and words. Th ...
'' 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 Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It h ...
'' if ''xRy'' and ''yRz'' always implies that ''xRz'' does not hold. For example, the relation defined by ''xRy'' if ''xy'' is an
even number In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no ge ...
is intransitive, but not antitransitive. The relation defined by ''xRy'' if ''x'' is even and ''y'' is odd is both transitive and antitransitive. The relation defined by ''xRy'' if ''x'' is the
successor Successor is someone who, or something which succeeds or comes after (see success (disambiguation), success and Succession (disambiguation), succession) Film and TV * The Successor (film), ''The Successor'' (film), a 1996 film including Laura Girli ...
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 transitivityStochastic transitivity models are stochastic Stochastic () refers to the property of being well described by a random In common parlance, randomness is the apparent or actual lack of pattern or predictability in events. A random sequence ...
''), 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 the study of an agent's choices. Decision theory can be broken into two branches: normative Normative generally means relating to an evaluative standard. Normativi ...
,
psychometrics Psychometrics is a field of study within psychology Psychology is the scientific Science () is a systematic enterprise that builds and organizes knowledge Knowledge is a familiarity or awareness, of someone or something, s ...
and utility models. A ''
quasitransitive relation The mathematical notion of quasitransitivity is a weakened version of transitive relation, transitivity that is used in social choice theory and microeconomics. Informally, a relation is quasitransitive if it is symmetric relation, symmetric for som ...
'' 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 A theory is a rational Rationality is the quality or state of being rational – that is, being based on or agreeable to reason Reason is the capacity of consciously making sense o ...
or
microeconomics Microeconomics is a branch of mainstream economics Mainstream economics is the body of knowledge, theories, and models of economics, as taught by universities worldwide, that are generally accepted by economists as a basis for discussion. Als ...
.


See also

*
Transitive reductionIn mathematics, a transitive reduction of a directed graph ''D'' is another directed graph with the same vertices and as few edges as possible, such that for all pairs of vertices ''v'', ''w'' a (directed) path from ''v'' to ''w'' in ''D'' exists if ...
*
Intransitive diceA 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 ...

Intransitive dice
*
Rational choice theory Rational choice theory refers to a set of guidelines that help understand economic and social behaviour. The theory postulates that an individual will perform a cost-benefit analysis to determine whether an option is right for them. It also sugge ...
*
Hypothetical syllogism In classical logic Classical logic (or standard logic) is the intensively studied and most widely used class of deductive logic Deductive reasoning, also deductive logic, is the process of reasoning from one or more statements (premises) to reach ...
— transitivity of the material conditional


Notes


References

* * *
Gunther Schmidt Gunther Schmidt (born 1939, Rüdersdorf) is a Germans, 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, Wilhe ...
, 2010. ''Relational Mathematics''. Cambridge University Press, . *


External links

* {{springer, title=Transitivity, id=p/t093810
Transitivity in Action
at
cut-the-knot Alexander Bogomolny (January 4, 1948 July 7, 2018) was a Soviet Union, 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 Electron ...
Binary relations Elementary algebra