In

Transitivity in Action

at

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

Ahomogeneous 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 ...

:
:$\backslash forall\; a,b,c\; \backslash in\; X:\; (aRb\; \backslash wedge\; bRc)\; \backslash 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 isantitransitive
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). ...

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). ...

, 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 ...

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\; \backslash 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 ...

is also transitive: if the ordered pair is of the form $(x,\; x)$ for some $x\; \backslash in\; X$ the only such elements $a,b,c\; \backslash 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\; \backslash in\; X$ and hence $R$ is vacuously transitive.
Properties

Closure properties

* Theconverse
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). ...

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 ...

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 ...

, 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 ...

, 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 isirreflexive
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 ...

* 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/t093810Transitivity 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