Composition of relations

From Wikipedia, the free encyclopedia

In mathematics, the composition of binary relations is a concept of forming a new relation S o R from two given relations R and S, having as its most well-known special case the composition of functions.

1 Definition
2 Properties
3 Other forms of composition
4 See also

[edit] Definition

If $R\subseteq X\times Y$ and $S\subseteq Y\times Z$ are two binary relations, then their compose $S\circ R$ is the relation

$S\circ R = \{ (x,z)\in X\times Z\mid \exists y\in Y: (x,y)\in R\land (y,z)\in S \} \subseteq X\times Z$ .

In other words, $S\circ R\subseteq X\times Z$ is defined by the rule that says $(x,z)\in S\circ R$ if and only if there is an element $y\in Y$ such that $x\,R\,y\,S\,z$ (i.e. $(x,y)\in R$ and $(y,z)\in S$ ).

In particular fields, authors might denote by R o S what is defined here to be S o R. The convention chosen here is such that function composition (with the usual notation) is obtained as a special case, when R and S are functional relations.

The binary relations $R\subseteq X\times Y$ are sometimes regarded as the morphisms $R\colon X\to Y$ in a category Rel which has the sets as objects. In Rel, composition of morphisms is exactly composition of relations as defined above. The category Set of sets is a subcategory of Rel that has the same objects but fewer morphisms. A generalization of this is found in the theory of allegories.

[edit] Properties

Composition of relations is associative.

The inverse relation of S o R is (S o R)^-1 = R^-1 o S^-1.

The compose of (partial) functions (i.e. functional relations) is again a (partial) function.

If R and S are injective, then S o R is injective, which conversely implies only the injectivity of R.

If R and S are surjective, then S o R is surjective, which conversely implies only the surjectivity of S.

The binary relations on a set X (i.e. relations from X to X) form a monoid for composition, with the identity map on X as neutral element.

[edit] Other forms of composition

Other forms of composition of relations, which apply to general n-place relations instead of binary relations, are found in the join operation of relational algebra. The usual composition of two binary relations as defined here can be obtained by taking their join, leading to a ternary relation, followed by a projection that removes the middle component.