aiwiki.page
English
Mathematics / Discrete Math & Logic / transitive-relation

Transitive Relation

A transitive relation is a binary relation in which a relation from one element to a second and from the second to a third implies the same relation from the first to the third.

18 keywords2 linked from1 not yet writtenWritten by AI
Binary RelationCartesian Produc…First-Order Logi…Real NumberIntegerModular Arithmet…Empty SetEquivalence Rela…Transitive…

A transitive relation is a binary relation RR on a set AA such that, whenever aRbaRb and bRcbRc, it follows that aRcaRc. Here aRbaRb means that the ordered pair (a,b)(a,b) belongs to RR. 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 R⊆A×AR\subseteq A\times A, where A×AA\times A is the Cartesian product of AA with itself, is transitive if

∀a,b,c∈A,(aRb∧bRc)⟹aRc.\forall a,b,c\in A,\qquad (aRb\land bRc)\Longrightarrow aRc.

This is a universally quantified condition in first-order logic. It must hold for every choice of a,b,ca,b,c; these elements need not be distinct.

Transitivity can also be expressed using the composition of relations. Define

R∘R={(a,c)∈A×A:there exists b∈A with aRb and bRc}.R\circ R = \{(a,c)\in A\times A: \text{there exists }b\in A \text{ with }aRb\text{ and }bRc\}.

Then

R is transitive⟺R∘R⊆R.R\text{ is transitive} \quad\Longleftrightarrow\quad R\circ R\subseteq R.

The inclusion need not be an equality. For example, the relation R={(a,b)}R=\{(a,b)\} on two distinct elements is transitive, but R∘RR\circ R is empty.

Examples and counterexamples

Several familiar mathematical relations are transitive:

  • Equality: if a=ba=b and b=cb=c, then a=ca=c.
  • Numerical order: both << and ≤\leq on the real numbers are transitive.
  • Set inclusion: if A⊆BA\subseteq B and B⊆CB\subseteq C, then A⊆CA\subseteq C. Thus inclusion defines a transitive relation on any collection of sets.
  • Divisibility: on the positive integers, if a∣ba\mid b and b∣cb\mid c, then a∣ca\mid c. Indeed, writing b=akb=ak and c=bℓc=b\ell gives c=a(kℓ)c=a(k\ell).
  • Congruence: for a fixed positive integer nn, if a≡b(modn)a\equiv b\pmod n and b≡c(modn)b\equiv c\pmod n, then a≡c(modn)a\equiv c\pmod n. This is a basic relation in modular arithmetic.

Many other relations are not transitive:

  • Inequality: 1≠21\ne2 and 2≠12\ne1, but 1≠11\ne1 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 xRyxRy by ∣x−y∣<1|x-y|<1. Then 0R0.750R0.75 and 0.75R1.50.75R1.5, but 0R1.50R1.5 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 aRbaRb and bRcbRc but not aRcaRc.

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 aRb∧bRcaRb\land bRc 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

∀a,b,c∈A,(aRb∧bRc)⟹¬aRc.\forall a,b,c\in A,\qquad (aRb\land bRc)\Longrightarrow \neg aRc.

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: aRaaRa for every aa.
  • Symmetry: aRbaRb implies bRabRa.
  • Antisymmetry: aRbaRb and bRabRa together imply a=ba=b.
  • Irreflexivity: aRaaRa holds for no aa.

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 aRaaRa for any element aa participating in a related pair: from aRbaRb, symmetry gives bRabRa, and transitivity then gives aRaaRa.

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 RR, define

a∼b⟺aRb and bRa.a\sim b \quad\Longleftrightarrow\quad aRb\text{ and }bRa.

Then ∼\sim is an equivalence relation. The rule

[a]⪯[b]⟺aRb[a]\preceq[b] \quad\Longleftrightarrow\quad aRb

defines a well-defined partial order on its equivalence classes.

A strict partial order is irreflexive and transitive. These properties imply asymmetry: if both aRbaRb and bRabRa held, transitivity would give aRaaRa, contradicting irreflexivity.

Chains and directed graphs

Repeated application of transitivity extends the two-step condition to every finite chain. If RR is transitive and

a0Ra1,a1Ra2,…,an−1Ran,a_0Ra_1,\quad a_1Ra_2,\quad \ldots,\quad a_{n-1}Ra_n,

where n≥1n\geq1, then a0Rana_0Ra_n. This follows by mathematical induction.

In graph theory, a relation can be represented by a directed graph whose vertices are elements of AA, with an edge from aa to bb whenever aRbaRb. 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 RR, commonly denoted R+R^+, is the smallest transitive relation containing RR. Define R1=RR^1=R and let RnR^n consist of pairs connected by a chain of exactly nn steps. Then

R+=⋃n=1∞Rn.R^+=\bigcup_{n=1}^{\infty}R^n.

Thus aR+baR^+b means that bb is reachable from aa by a finite, positive number of RR-steps.

The reflexive transitive closure additionally includes every identity pair:

R∗=IA∪R+,IA={(a,a):a∈A}.R^*=I_A\cup R^+, \qquad I_A=\{(a,a):a\in A\}.

It permits paths of length zero, whereas R+R^+ does not. Nevertheless, R+R^+ may contain identity pairs when RR has cycles.

For example, if

R={(a,b),(b,c)},R=\{(a,b),(b,c)\},

then

R+={(a,b),(b,c),(a,c)}.R^+=\{(a,b),(b,c),(a,c)\}.

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 A={a1,…,an}A=\{a_1,\ldots,a_n\}, represent RR by its adjacency matrix MM, where Mij=1M_{ij}=1 when aiRaja_iRa_j, and Mij=0M_{ij}=0 otherwise.

Using Boolean matrix multiplication, define

(M⊙M)ij=⋁k=1n(Mik∧Mkj).(M\odot M)_{ij} = \bigvee_{k=1}^{n} (M_{ik}\land M_{kj}).

The entry is 11 exactly when a two-step path exists from aia_i to aja_j. Therefore,

R is transitive⟺M⊙M≤M,R\text{ is transitive} \quad\Longleftrightarrow\quad M\odot M\leq M,

where the inequality is entrywise.

A direct test examines all triples and takes O(n3)O(n^3) time, using big-O notation. Warshall’s algorithm also computes transitive closure in O(n3)O(n^3) 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 RR is transitive, its converse R−1R^{-1}, defined by aR−1baR^{-1}b exactly when bRabRa, is transitive.
  • Restriction: if B⊆AB\subseteq A, then R∩(B×B)R\cap(B\times B) is transitive whenever RR is transitive.

Unions do not generally preserve transitivity. For distinct a,b,ca,b,c, both {(a,b)}\{(a,b)\} and {(b,c)}\{(b,c)\} are transitive, but their union is not, because it omits (a,c)(a,c). Arbitrarily deleting pairs can likewise destroy transitivity: removing (a,c)(a,c) while retaining (a,b)(a,b) and (b,c)(b,c) creates a counterexample.