Transitivity Chain Finder: Given (a, b) and (b, c), Is (a, c) There?

Transitivity is the property that "if you can reach c from a in two hops, you can also reach it in one." Written formally: if (a, b) \in R and (b, c) \in R, then (a, c) \in R. The visual version is cleaner: scan every two-arrow path a \to b \to c in the directed graph, and check that the shortcut arrow a \to c is drawn. One missing shortcut is enough to break transitivity. This article makes the chain-check a reflex.

The picture

Take A = \{1, 2, 3, 4\}. Draw the relation as a directed graph. Every pair (x, y) \in R becomes an arrow x \to y. Transitivity says: for every two-hop path you can follow, the direct one-hop shortcut must also exist.

A relation containing $(1, 2)$ and $(2, 3)$. Transitivity demands the shortcut $(1, 3)$. If it is absent — shown here as a red dashed arrow — the relation is *not* transitive. Drag the slider to toggle between five sample relations and watch each chain either close (green shortcut appears) or glow red (missing shortcut).

What transitivity actually demands

For every ordered pair of arrows (a, b) and (b, c) with a shared middle element b, the direct arrow (a, c) must also be in R. Note the scope:

The shared middle matters. If a = b, the first arrow is a self-loop; the check becomes "does (a, c) exist given (a, c) exists?" — trivially yes.
The endpoints can be equal. If a = c, the demand reduces to "does (a, a) exist?" — which asks for a self-loop at a whenever there is a two-hop round trip a \to b \to a. This does not automatically give reflexivity; it gives a conditional self-loop only where a round-trip exists.
Two separate chains must each be checked independently. If (1, 2), (2, 3), (2, 4) \in R, you have two chains to close: 1 \to 2 \to 3 needs (1, 3), and 1 \to 2 \to 4 needs (1, 4).

Why: transitivity is universally quantified over pairs of arrows sharing a middle. A single unclosed chain — one (a, b), (b, c) \in R with (a, c) \notin R — is one counter-example, which is enough to falsify the universal statement. Transitivity checks must touch every chain, but one failure kills the property.

The five cases the slider walks through

Case 0 — the empty relation. No arrows at all. No chains to check. Vacuously transitive.

Case 1 — a single arrow \{(1, 2)\}. One arrow, no chain (a chain needs two arrows with a shared middle). Nothing to close. Transitive — vacuously again.

Case 2 — two linked arrows, shortcut missing: \{(1, 2), (2, 3)\}. One chain: 1 \to 2 \to 3. Needs (1, 3). It isn't there. Not transitive. This is the picture in the figure.

Case 3 — two linked arrows, shortcut present: \{(1, 2), (2, 3), (1, 3)\}. Chain closes. Transitive — and this is the smallest non-trivially transitive relation (three elements, three arrows, shortcut included).

Case 4 — "a \leq b" on \{1, 2, 3, 4\}. Every chain a \leq b \leq c automatically gives a \leq c, so every shortcut exists. Transitive. This is the classic example and the reason partial orders are transitive by definition.

The chain-closure reflex

When you see a relation, here is the mechanical routine to decide transitivity:

List every pair (a, b) \in R.
For each pair, find every pair (b, c) \in R starting with the same element b.
For each such match, check whether (a, c) \in R.
If any match fails, declare not transitive and point to the missing shortcut as a counter-example.
If every match succeeds, declare transitive.

This is O(|R|^2) in the worst case — for a relation with n pairs, you do up to n lookups per pair. For small n this is instant; for large n the grid or matrix view is faster.

The grid view of transitivity

The same check has a matrix form. Let M be the |A| \times |A| matrix where M_{a, b} = 1 if (a, b) \in R and 0 otherwise. Compute M^2 using Boolean multiplication (sums replaced by OR). Then:

(M^2)_{a, c} = 1 means there exists some b with (a, b) \in R and (b, c) \in R — i.e., a two-hop path from a to c.
Transitivity requires that every such (a, c) already has M_{a, c} = 1.

Equivalently: M^2 \subseteq M (entrywise, after OR'ing). For hand calculation with small |A|, writing M and M^2 on a grid and comparing is faster than chasing arrows in a picture.

Self-loop traps

Self-loops create chains with themselves. If (a, a) \in R and (a, b) \in R, the chain a \to a \to b needs (a, b) — but that is already present, so the chain closes trivially. Self-loops therefore never cause a transitivity failure on their own.

However, self-loops can be created by transitivity. If (a, b) and (b, a) are both in R, the chains a \to b \to a and b \to a \to b demand self-loops (a, a) and (b, b). If those are missing, transitivity fails. This is the most common way transitivity and symmetry together force reflexivity on the elements they touch (sometimes).

Common misconception: "Symmetric plus transitive implies reflexive." This is almost true but subtly wrong — it implies reflexivity only on elements that appear in some pair. An element not mentioned anywhere in R is unaffected. The symmetry + transitivity + everyone-appears-in-some-pair combination does force reflexivity on the whole set.

Finding the counter-example in a list

Problem: "Is R = \{(1, 2), (2, 3), (3, 4), (1, 3)\} transitive on \{1, 2, 3, 4\}?"

Chain scan:

1 \to 2 \to 3: needs (1, 3). Present. \checkmark
2 \to 3 \to 4: needs (2, 4). Missing. \times
1 \to 3 \to 4: needs (1, 4). Missing. \times

Two failed chains. Not transitive. Counter-example: (2, 3) \in R and (3, 4) \in R but (2, 4) \notin R.

The answer drops out in under a minute with a systematic scan.

Transitive closure — the smallest fix

When a relation is not transitive, you can make it transitive by adding the minimum number of arrows. This is called the transitive closure of R, written R^+ or R^*. For the example above, the missing shortcuts (2, 4) and (1, 4) must be added, giving R^+ = \{(1, 2), (2, 3), (3, 4), (1, 3), (2, 4), (1, 4)\} — but wait, adding (2, 4) creates a new chain 1 \to 2 \to 4 demanding (1, 4), and (1, 4) is also needed from the (1, 3) \to (3, 4) chain. So R^+ must include everything; each addition may spawn further demands. Computing R^+ is itself a small algorithm — Warshall's algorithm is the classic textbook method. You do not need it for JEE-level problems; recognising when a chain is broken is enough.

The habit

Draw the directed graph (or the grid).
For every ordered pair (a, b) \in R, look for pairs starting at b. Each such continuation is a chain.
Every chain demands a shortcut arrow. One missing shortcut kills transitivity.
Find the missing shortcut and you have your counter-example.

Transitivity is not a single property you verify in one glance — it is a scan of all chains. But the scan is mechanical, and once you internalise it, you read it off pictures as fast as you read symmetry or reflexivity.