Skip to content
Home

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: Created: Updated:

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
Two transitive and one non-transitive relation (bottom right), shown as directed graphs

Formal definition

If Ma set and R\subseteq M\times Mtwo-digit relation on Mthen is called Rtransitive if (using infix notation) holds:

{\displaystyle \forall x,y,z\in M:xRy\land yRz\Rightarrow xRz.}

Representation as a directed graph

Any relation Ron a set Mcan be understood as a directed graph (see example above). The nodes of the graph are the elements of M. A directed edge (an arrow a\longrightarrow b) bis drawn from node ato node aRbholds.

The transitivity of Rcan 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 Ralso 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 Rtransitive, 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 Rand are Stransitive, 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 Ris a smallest transitive relation Swhich Rcontains , the so-called transitive hull of R.
    Example: Let     Rbe the antecedent relation on the set of natural numbers, so let a\,R\,b:\Longleftrightarrow a=b-1. The relation Ritself is not transitive. As a transitive envelope of the smaller relation Rresults.

Examples

Order of the real numbers

The lessor relation <\ real numbers is transitive, because from x < y x<yy<za 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=yand y=zfollows 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 5and 5\neq 3but 3\neq 3does not apply, of course.

Divisibility of the integers

The divisibility relation |for integers is transitive, because from a|band b|cfollows 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 12and are 5alien to the divisor, as are 5and 9but 12and 9have the common divisor 3.

Subset

The subset relation \subseteq between sets is transitive, because from A\subseteq Band B\subseteq Cfollows 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.

Implication in logic

In logic, transitivity applies with regard to implication, although in predicate logic this is also known as modus barbara:

From A \Rightarrow Band B\Rightarrow Cfollows A\Rightarrow C(compare also: cutting rule).

The implication defines a quasi-order on the formulae of the logic under consideration.

From a &gt; b and b &gt; c follows a &gt; c
From a &gt; b and b &gt; c follows a &gt; c

See also

  • Transitive shell
  • Negative transitivity

Related articles

Author

AlegsaOnline.com Transitivity (mathematics)

URL: https://en.alegsaonline.com/art/101168

Share