AlegsaOnline.com

Transitivity (mathematics)

Transitivity is a structural property of a binary relation: whenever a relation links a to b and b to c, it also links a to c. It underpins equivalence relations and partial orders.

Author: Leandro Alegsa Creation date: November 13, 2022 Last updated: April 15, 2026

In mathematics and formal reasoning, a binary relation R on a set is called transitive when, for any three elements a, b and c, aRb and bRc together imply aRc. In symbolic form: for all a,b,c, (aRb && bRc) → aRc. This simple condition is fundamental: it governs the way information or ordering can be propagated through chains of related items.

Formal role and logical context

Transitivity appears in both logic and mathematics as one of the standard relation properties studied in set theory, algebra, and order theory. It is a necessary ingredient of an equivalence relation when combined with reflexivity and symmetry, and it is likewise required (with reflexivity and antisymmetry) for a relation to be a partial order. The defining pattern, a chain-of-two implies the chain-of-three, recurs in many abstract settings.

Examples and non-examples

Common examples of transitive relations include:

Equality (=): if x = y and y = z then x = z.
Order relations: <, ≤, and > on numbers are transitive; if a < b and b < c then a < c.
Divisibility among integers: if a divides b and b divides c then a divides c.
Subset inclusion (⊆): if A ⊆ B and B ⊆ C then A ⊆ C.

By contrast, many everyday relations are not transitive. "Is a friend of" is typically non-transitive: A being friends with B and B with C does not ensure A is friends with C. Such counterexamples illustrate why transitivity is a substantive structural requirement, not a default.

Transitive closure and reduction

Given any relation R, its transitive closure is the smallest transitive relation that contains R; it adds all inferred links arising from chains of arbitrary length. Algorithms such as Warshall's (or more generally Floyd–Warshall for weighted graphs) compute closures on finite sets. The related notion of transitive reduction seeks the minimal relation whose transitive closure recovers the original; this is useful for simplifying ordered structures like dependency graphs.

Importance and distinctions

Transitivity affects how one reasons about connectedness, inheritance, and order. In algebra it helps classify congruences and quotient structures; in computer science it underlies reachability in graphs and database query semantics. When combined with other properties (reflexivity, symmetry, antisymmetry) it produces the familiar classes of relations—equivalence relations and partial orders—each serving different modeling needs.

For further reading on foundational aspects and examples, see introductions to relations in elementary set theory and texts on order theory; online references treat the topic in both binary relation and applied contexts such as networks and databases. Additional background on equivalence relations appears via equivalence relation-focused expositions and summaries of relation properties.

Transitivity is therefore a modest-looking axiom with wide practical and theoretical consequences: it determines how local connections extend globally and shapes the algebraic and combinatorial structure of many mathematical systems.

Two transitive and one non-transitive relation (bottom right), shown as directed graphs

Formal definition

If a set and $R\subseteq M\times M$ two-digit relation on then is called transitive if (using infix notation) holds:

$\forall x,y,z\in M:xRy\land yRz\Rightarrow xRz.$

Representation as a directed graph

Any relation on a set can be understood as a directed graph (see example above). The nodes of the graph are the elements of . A directed edge (an arrow $a\longrightarrow b$ ) is drawn from node to node aRb holds.

The transitivity of can now be characterised in the graph in this way: Whenever two arrows follow each other ( $a\longrightarrow b\longrightarrow c$ ), there is also an arrow that directly connects the initial and final nodes ( $a\longrightarrow c$ ) (so also in the Hasse diagram).

Properties

The transitivity of a relation also allows inferences across several steps (as is easily shown by complete induction):

$a\,R\,b_{1}\,R\,b_{2}\,R\,\dots \,R\,b_{n}\,R\,c\implies a\,R\,c$

With the help of the concatenation $\circ$ of relations, transitivity can also be characterised by the following condition:

$R\circ R\subseteq R$

If the relation transitive, then this is also true for the converse relation $R^{-1}$ . Examples: the relation that is converse to ≤ {\displaystyle $\leq$ ≥ $\geq$ which is converse $<\$ to is > {\displaystyle
If the relations and are transitive, then this is also true for their intersection $R\cap S$ . This statement can be generalised from two relations to the average $\cap _{{i\in I}}R_{i}$ any family of transitive relations.
For any relation is a smallest transitive relation which contains , the so-called transitive hull of .
Example: Let be the antecedent relation on the set of natural numbers, so let $a\,R\,b:\Longleftrightarrow a=b-1$ . The relation itself is not transitive. As a transitive envelope of the smaller relation results.

Examples

Order of the real numbers

The lessor relation $<\$ real numbers is transitive, because from x < y x<y y<z a strict total order.

Likewise, the relations $>\$ , ≤ $\leq \$ and ≥ $\geq \$ transitive.

Equality of the real numbers

The ordinary equality $=\$ on the real numbers is transitive, because from x=y and y=z follows x=z . Furthermore, it is an equivalence relation.

The inequality relation $\neq$ on the real numbers, on the other hand, is not transitive: $3\neq 5$ and $5\neq 3$ but $3\neq 3$ does not apply, of course.

Divisibility of the integers

The divisibility relation for integers is transitive, because from a|b and b|c follows a|c . Moreover, it is a quasi-order. When restricting to the set of natural numbers, one obtains a half-order.

For example, the divisor strangeness is not transitive. Thus and are alien to the divisor, as are and but and have the common divisor .

Subset

The subset relation $\subseteq$ between sets is transitive, because from $A\subseteq B$ and $B\subseteq C$ follows $A\subseteq C$ . Furthermore, $\subseteq$ a half-order.

For example, the disjointness of sets is not transitive. Thus the sets $\lbrace 1,2\rbrace$ and are $\lbrace 3\rbrace$ disjoint, as are $\lbrace 3\rbrace$ and $\lbrace 1,4\rbrace$ , but not $\lbrace 1,2\rbrace$ and $\lbrace 1,4\rbrace$ (since they have element 1 in common).

Parallel straight lines

In geometry, the parallelism of lines is transitive: if both the lines $g_{1}$ and $g_{2}$ parallel and the lines $g_{2}$ and $g_{3}$ then $g_{1}$ and $g_{3}$ are also parallel. Furthermore, parallelism is an equivalence relation.