A transitive relation is a binary relation on a set such that, whenever and , it follows that . Here means that the ordered pair belongs to . Transitivity is a defining property of order relations and equivalence relations, and it underlies reasoning about chains of comparisons, implications, and reachability.
Definition
Formally, a relation , where is the Cartesian product of with itself, is transitive if
This is a universally quantified condition in first-order logic. It must hold for every choice of ; these elements need not be distinct.
Transitivity can also be expressed using the composition of relations. Define
Then
The inclusion need not be an equality. For example, the relation on two distinct elements is transitive, but is empty.
Examples and counterexamples
Several familiar mathematical relations are transitive:
- Equality: if and , then .
- Numerical order: both and on the real numbers are transitive.
- Set inclusion: if and , then . Thus inclusion defines a transitive relation on any collection of sets.
- Divisibility: on the positive integers, if and , then . Indeed, writing and gives .
- Congruence: for a fixed positive integer , if and , then . This is a basic relation in modular arithmetic.
Many other relations are not transitive:
- Inequality: and , but is false. This illustrates why repeated elements must be considered when checking the definition.
- Being a parent of: a parent of a parent is not thereby a parent of the same person. By contrast, the relation “is an ancestor of” is transitive.
- Being within a fixed distance: on the real line, define by . Then and , but is false.
- Having a common member: two sets may intersect, and the second may intersect a third, without the first and third intersecting.
To disprove transitivity, it is enough to exhibit a single triple satisfying and but not .
Vacuous transitivity and intransitivity
A relation can be transitive even when it contains no chain of two consecutive related pairs. In that case, the premise is never true, so the defining implication holds vacuously. The empty relation is therefore transitive on every set.
A distinction is needed between a relation that is not transitive and one that is antitransitive. Antitransitivity means
Failure of transitivity requires at least one counterexample; antitransitivity forbids the conclusion for every two-step chain. A relation may contain some chains whose endpoints are related and others whose endpoints are not, making it neither transitive nor antitransitive.
The term intransitive is sometimes used for failure of transitivity and sometimes for the stronger antitransitive condition, so its intended meaning must be checked. Vacuously, a relation with no two-step chains is both transitive and antitransitive.
Connection with other relation properties
Transitivity is distinct from reflexivity, symmetry, and antisymmetry:
- Reflexivity: for every .
- Symmetry: implies .
- Antisymmetry: and together imply .
- Irreflexivity: holds for no .
Different combinations define important classes of relations.
Equivalence relations
An equivalence relation is reflexive, symmetric, and transitive. Transitivity ensures that elements linked through an intermediate equivalent element are themselves equivalent. Together, these properties organize a set into disjoint equivalence classes.
Symmetry and transitivity alone do not imply reflexivity on the entire underlying set. They do, however, imply for any element participating in a related pair: from , symmetry gives , and transitivity then gives .
Orders and preorders
A partial order is reflexive, antisymmetric, and transitive. Set inclusion and divisibility on positive integers are standard examples.
A preorder is reflexive and transitive, without necessarily being antisymmetric. For a preorder , define
Then is an equivalence relation. The rule
defines a well-defined partial order on its equivalence classes.
A strict partial order is irreflexive and transitive. These properties imply asymmetry: if both and held, transitivity would give , contradicting irreflexivity.
Chains and directed graphs
Repeated application of transitivity extends the two-step condition to every finite chain. If is transitive and
where , then . This follows by mathematical induction.
In graph theory, a relation can be represented by a directed graph whose vertices are elements of , with an edge from to whenever . The relation is transitive precisely when every directed walk of length two has a direct edge joining its starting vertex to its ending vertex. Equivalently, every finite directed walk of positive length has such an edge.
Consequently, a transitive relation containing a directed cycle must contain loops at the vertices of that cycle. An irreflexive transitive relation cannot contain a directed cycle.
Transitive closure
The transitive closure of , commonly denoted , is the smallest transitive relation containing . Define and let consist of pairs connected by a chain of exactly steps. Then
Thus means that is reachable from by a finite, positive number of -steps.
The reflexive transitive closure additionally includes every identity pair:
It permits paths of length zero, whereas does not. Nevertheless, may contain identity pairs when has cycles.
For example, if
then
Transitive closure is used to compute reachability, indirect dependencies, and the consequences of repeatedly applying a relation.
Matrix representation and computation
For a finite set , represent by its adjacency matrix , where when , and otherwise.
Using Boolean matrix multiplication, define
The entry is exactly when a two-step path exists from to . Therefore,
where the inequality is entrywise.
A direct test examines all triples and takes time, using big-O notation. Warshall’s algorithm also computes transitive closure in time by successively allowing each vertex as an intermediate point.
Preservation properties
Several operations preserve transitivity:
- Intersections: any nonempty intersection of transitive relations on the same set is transitive.
- Converse: if is transitive, its converse , defined by exactly when , is transitive.
- Restriction: if , then is transitive whenever is transitive.
Unions do not generally preserve transitivity. For distinct , both and are transitive, but their union is not, because it omits . Arbitrarily deleting pairs can likewise destroy transitivity: removing while retaining and creates a counterexample.