Composition of relations

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

Definition

If $R\subseteq X\times Y$ and $S\subseteq Y\times Z$ are two binary relations, then their composition $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\}.$

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 ∘ S what is defined here to be S ∘ 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. Some authors^[1] prefer to write $\circ _{l}$ and $\circ _{r}$ explicitly when necessary, depending whether the left or the right relation is the first one applied.

A further variation encountered in computer science is the Z notation: $\circ$ is used to denote the traditional (right) composition, but ⨾ ; (a fat open semicolon with Unicode code point U+2A3E) denotes left composition.^[2][3] This use of semicolon coincides with the notation for function composition used (mostly by computer scientists) in Category theory,^[4] as well as the notation for dynamic conjunction within linguistic dynamic semantics.^[5] The semicolon notation (with this semantic) was introduced by Ernst Schröder in 1895.^[6]

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.

Properties

Composition of relations is associative.

The inverse relation of S ∘ R is (S ∘ R)⁻¹ = R⁻¹ ∘ S⁻¹. This property makes the set of all binary relations on a set a semigroup with involution.

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

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

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

The set of binary relations on a set X (i.e. relations from X to X) together with (left or right) relation composition forms a monoid with zero, where the identity map on X is the neutral element, and the empty set is the zero element.

Join: another form 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.

Composition in terms of matrices

If $R$ is a relation between two finite sets then one obtains an associated adjacency matrix $M_R$ (see here). Then if $R$ and $S$ are two relations which can be composed, the matrix $M_{S \circ R}$ is exactly the matrix product $M_R M_S$, where it is understood that $1 + 1 = 1$. (Note also the reversal of order of $R$ and $S$.)

See also

• Binary relation
• Relation algebra
• Demonic composition
• Function composition
• Join (SQL)
• Logical matrix

Notes

1. Kilp, Knauer & Mikhalev, p. 7
2. ISO/IEC 13568:2002(E), p. 23
3. http://www.fileformat.info/info/unicode/char/2a3e/index.htm
4. http://www.math.mcgill.ca/triples/Barr-Wells-ctcs.pdf, p. 6
5. http://plato.stanford.edu/entries/dynamic-semantics/#EncDynTypLog
6. Paul Taylor (1999). Practical Foundations of Mathematics. Cambridge University Press. p. 24. ISBN 978-0-521-63107-5. A free HTML version of the book is available at http://www.cs.man.ac.uk/~pt/Practical_Foundations/

References

• M. Kilp, U. Knauer, A.V. Mikhalev, Monoids, Acts and Categories with Applications to Wreath Products and Graphs, De Gruyter Expositions in Mathematics vol. 29, Walter de Gruyter, 2000, ISBN 3-11-015248-7.