# nLab transitive relation

## In higher category theory

A (binary) relation $\sim$ on a set $A$ is transitive if in every chain of $3$ pairwise related elements, the first and last elements are also related:

$\forall \left(x,y,z:A\right),\phantom{\rule{thickmathspace}{0ex}}x\sim y\phantom{\rule{thickmathspace}{0ex}}\wedge \phantom{\rule{thickmathspace}{0ex}}y\sim z\phantom{\rule{thickmathspace}{0ex}}⇒\phantom{\rule{thickmathspace}{0ex}}x\sim z$\forall (x, y, z: A),\; x \sim y \;\wedge\; y \sim z \;\Rightarrow\; x \sim z

which generalises from $3$ to any finite, positive number of elements.

In the language of the $2$-poset Rel of sets and relations, a relation $R:A\to A$ is transitive if it contains its composite with itself:

${R}^{2}\subseteq R$R^2 \subseteq R

from which it follows that ${R}^{n}\subseteq R$ for any positive natural number $n$. To include the case where $n=0$, we must explicitly state that the relation is reflexive.

Transitive relations are often understood as orders.

Revised on December 2, 2012 20:18:21 by Urs Schreiber (82.113.106.154)