Composition of relations

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.

Definition

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

$S\circ R:X\to Z$ defined by $\forall(x,z)\in X\times Z:\exists y\in Y: x\,R\,y\,S\,z$

where, as usual, $x\,R\,y\,S\,z \iff x\,R\,y\land y\,S\,z$ . In other words, S o R is the relation from X to Z whose graph is

$\operatorname{graph}\,S\circ R = \{ (x,z)\in X\times Z\mid \exists y\in Y: (x,y)\in \operatorname{graph}\,R\land (y,z)\in \operatorname{graph}\,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.

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.

Composition of relations

Definition

Properties

See also

Tackle These

Keep Reading