nLab transitive relation

A transitive relation is a semicategory or magmoid AA such that for all objects aa and bb in AA, there are no more than one morphism with domain aa and codomain bb. Equivalently, a transitive relation is a semicategory or magmoid enriched on truth values.

Set theoretically, a (binary) relation \sim on a set AA is transitive if in every chain of 33 pairwise related elements, the first and last elements are also related:

(x,y,z:A),xyyzxz\forall (x, y, z: A),\; x \sim y \;\wedge\; y \sim z \;\Rightarrow\; x \sim z

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

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

R 2RR^2 \subseteq R

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

Transitive relations are often understood as orders.

Last revised on May 17, 2021 at 16:04:25. See the history of this page for a list of all contributions to it.