Transitive relation

From Knowino
Jump to: navigation, search

In mathematics, a transitive relation on a set is a relation with the property that if xy and yz then xz.

[edit] Examples

[edit] Properties

Transitivity may be defined in terms of relation composition. A relation R is transitive if the composite R.R implies (is contained in) R.

[edit] Transitive closure

The transitive closure of a relation R may be defined as the intersection R* of all transitive relations containing R (one always exists, namely the always-true relation): loosely the "smallest" transitive relation containing R. The closure may also be constructed as

R^* = R \cup (R\circ R) \cup \cdots \cup R^{{\circ}n} \cup \cdots \,

where R^{{\circ}n} denotes the composition of R with itself n times.

Information.svg Some content on this page may previously have appeared on Citizendium.
Personal tools