transitive relation

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 December 2, 2012 at 20:18:21. See the history of this page for a list of all contributions to it.