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.
Contents
Definition
If
In other words,
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 prefer to write
A further variation encountered in computer science is the Z notation:
The binary relations
Properties
Composition of relations is associative.
The inverse relation of S ∘ R is (S ∘ R)−1 = R−1 ∘ S−1. 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