Composition of relations

Properties

• Composition of relations is associative: ${\displaystyle R;(S;T)=(R;S);T.}$
• The converse relation of ${\displaystyle R;S}$ is ${\displaystyle (R;S{)}^{\mathsf{\text{T}}}=S^{\mathsf{\text{T}}};R^{\mathsf{\text{T}}}.}$ This property makes the set of all binary relations on a set a semigroup with involution.
• The composition of (partial) functions (that is, functional relations) is again a (partial) function.
• If ${\displaystyle R}$ and ${\displaystyle S}$ are injective, then ${\displaystyle R;S}$ is injective, which conversely together with the requirement that ${\displaystyle S}$ is also left total on ${\displaystyle \text{range}(R)}$ implies the injectivity of only ${\displaystyle R.}$
• If ${\displaystyle R}$ and ${\displaystyle S}$ are surjective, then ${\displaystyle R;S}$ is surjective, which conversely implies the surjectivity of only ${\displaystyle S.}$
• The set of binary relations on a set ${\displaystyle X}$ (that is, relations from ${\displaystyle X}$ to ${\displaystyle X}$) together with (left or right) relation composition forms a monoid with zero, where the identity map on ${\displaystyle X}$ is the neutral element, and the empty set is the zero element.

Composition in terms of matrices

Finite binary relations are represented by logical matrices. The entries of these matrices are either zero or one, depending on whether the relation represented is false or true for the row and column corresponding to compared objects. Working with such matrices involves the Boolean arithmetic with ${\displaystyle 1+1=1}$ and ${\displaystyle 1\times 1=1.}$ An entry in the matrix product of two logical matrices will be ${\displaystyle 1}$, then, only if the row and column multiplied have a corresponding ${\displaystyle 1}$. Thus the logical matrix of a composition of relations can be found by computing the matrix product of the matrices representing the factors of the composition. "Matrices constitute a method for computing the conclusions traditionally drawn by means of hypothetical syllogisms and sorites."

Heterogeneous relations

Consider a heterogeneous relation ${\displaystyle R\subseteq A\times B}$, that is, where ${\displaystyle A}$ and ${\displaystyle B}$ may be distinct sets. Then using composition of relation ${\displaystyle R}$ with its converse ${\displaystyle R^{\mathsf{\text{T}}},}$ there are homogeneous relations ${\displaystyle R;R^{\mathsf{\text{T}}}}$ (on ${\displaystyle A}$) and ${\displaystyle R^{\mathsf{\text{T}}};R}$ (on ${\displaystyle B}$).

If for all ${\displaystyle x\in A}$ there exists some ${\displaystyle y\in B,}$ such that ${\displaystyle xRy}$ (that is, ${\displaystyle R}$ is a (left-)total relation), then for all ${\displaystyle x}$, ${\displaystyle xR;R^{\mathsf{\text{T}}}x}$ so that ${\displaystyle R;R^{\mathsf{\text{T}}}}$ is a reflexive relation or ${\displaystyle \mathrm{I}\subseteq R;R^{\mathsf{\text{T}}}}$ where I is the identity relation ${\displaystyle \{(x,x):x\in A\}.}$ Similarly, if ${\displaystyle R}$ is a surjective relation then $${\displaystyle R^{\mathsf{\text{T}}};R\supseteq \mathrm{I}=\{(x,x):x\in B\}.}$$ In this case ${\displaystyle R\subseteq R;R^{\mathsf{\text{T}}};R.}$ The opposite inclusion occurs for a difunctional relation.

The composition ${\displaystyle {\overline{R}}^{\mathsf{\text{T}}};R}$ is used to distinguish relations of Ferrer's type, which satisfy ${\displaystyle R;{\overline{R}}^{\mathsf{\text{T}}};R=R.}$

Example

Let ${\displaystyle A=}$ { France, Germany, Italy, Switzerland } and ${\displaystyle B=}$ { French, German, Italian } with the relation ${\displaystyle R}$ given by ${\displaystyle aRb}$ when ${\displaystyle b}$ is a national language of ${\displaystyle a.}$ Since both ${\displaystyle A}$ and ${\displaystyle B}$ is finite, ${\displaystyle R}$ can be represented by a logical matrix, assuming rows (top to bottom) and columns (left to right) are ordered alphabetically: $${\displaystyle \left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\\ 1& 1& 1\end{array}\right).}$$

The converse relation ${\displaystyle R^{\mathsf{\text{T}}}}$ corresponds to the transposed matrix, and the relation composition ${\displaystyle R^{\mathsf{\text{T}}};R}$ corresponds to the matrix product ${\displaystyle R^{\mathsf{\text{T}}}R}$ when summation is implemented by logical disjunction. It turns out that the ${\displaystyle 3\times 3}$ matrix ${\displaystyle R^{\mathsf{\text{T}}}R}$ contains a 1 at every position, while the reversed matrix product computes as: $${\displaystyle R{R}^{\mathsf{\text{T}}}=\left(\begin{array}{cccc}1& 0& 0& 1\\ 0& 1& 0& 1\\ 0& 0& 1& 1\\ 1& 1& 1& 1\end{array}\right).}$$ This matrix is symmetric, and represents a homogeneous relation on ${\displaystyle A.}$

Correspondingly, ${\displaystyle R^{\mathsf{\text{T}}};R}$ is the universal relation on ${\displaystyle B,}$ hence any two languages share a nation where they both are spoken (in fact: Switzerland). Vice versa, the question whether two given nations share a language can be answered using ${\displaystyle R;R^{\mathsf{\text{T}}}.}$

Schröder rules

For a given set ${\displaystyle V,}$ the collection of all binary relations on ${\displaystyle V}$ forms a Boolean lattice ordered by inclusion ${\displaystyle (\subseteq ).}$ Recall that complementation reverses inclusion: ${\displaystyle A\subseteq B\text{ implies }{B}^{\complement }\subseteq A^{\complement }.}$ In the calculus of relations it is common to represent the complement of a set by an overbar: ${\displaystyle \overline{A}=A^{\complement }.}$

If ${\displaystyle S}$ is a binary relation, let ${\displaystyle S^{\mathsf{\text{T}}}}$ represent the converse relation, also called the transpose. Then the Schröder rules are $${\displaystyle Q;R\subseteq S\text{ is equivalent to }{Q}^{\mathsf{\text{T}}};\overline{S}\subseteq \overline{R}\text{ is equivalent to }\overline{S};R^{\mathsf{\text{T}}}\subseteq \overline{Q}.}$$ Verbally, one equivalence can be obtained from another: select the first or second factor and transpose it; then complement the other two relations and permute them.

Though this transformation of an inclusion of a composition of relations was detailed by Ernst Schröder, in fact Augustus De Morgan first articulated the transformation as Theorem K in 1860. He wrote $${\displaystyle L;M\subseteq N\text{ implies }\overline{N};M^{\mathsf{\text{T}}}\subseteq \overline{L}.}$$

With Schröder rules and complementation one can solve for an unknown relation ${\displaystyle X}$ in relation inclusions such as $${\displaystyle R;X\subseteq S\text{and}X;R\subseteq S.}$$

For instance, by Schröder rule ${\displaystyle R;X\subseteq S\text{ implies }{R}^{\mathsf{\text{T}}};\overline{S}\subseteq \overline{X},}$ and complementation gives ${\displaystyle X\subseteq \overline{R^{\mathsf{\text{T}}};\overline{S}},}$ which is called the left residual of ${\displaystyle S}$ by ${\displaystyle R}$.

Quotients

Just as composition of relations is a type of multiplication resulting in a product, so some operations compare to division and produce quotients. Three quotients are exhibited here: left residual, right residual, and symmetric quotient. The left residual of two relations is defined presuming that they have the same domain (source), and the right residual presumes the same codomain (range, target). The symmetric quotient presumes two relations share a domain and a codomain.

Definitions:

• Left residual: ${\displaystyle A\mathrm{\setminus }B:=\overline{A^{\mathsf{\text{T}}};\overline{B}}}$
• Right residual: ${\displaystyle D/C:=\overline{\overline{D};C^{\mathsf{\text{T}}}}}$
• Symmetric quotient: ${\displaystyle \mathrm{syq}(E,F):=\overline{E^{\mathsf{\text{T}}};\overline{F}}\cap \overline{{\overline{E}}^{\mathsf{\text{T}}};F}}$

Using Schröder's rules, ${\displaystyle A;X\subseteq B}$ is equivalent to ${\displaystyle X\subseteq A\mathrm{\setminus }B.}$ Thus the left residual is the greatest relation satisfying ${\displaystyle A;X\subseteq B.}$ Similarly, the inclusion ${\displaystyle Y;C\subseteq D}$ is equivalent to ${\displaystyle Y\subseteq D/C,}$ and the right residual is the greatest relation satisfying ${\displaystyle Y;C\subseteq D.}$

One can practice the logic of residuals with Sudoku.

Join: another form of composition

A fork operator ${\displaystyle (<)}$ has been introduced to fuse two relations ${\displaystyle c:H\to A}$ and ${\displaystyle d:H\to B}$ into ${\displaystyle c(<)d:H\to A\times B.}$ The construction depends on projections ${\displaystyle a:A\times B\to A}$ and ${\displaystyle b:A\times B\to B,}$ understood as relations, meaning that there are converse relations ${\displaystyle a^{\mathsf{\text{T}}}}$ and ${\displaystyle b^{\mathsf{\text{T}}}.}$ Then the fork of ${\displaystyle c}$ and ${\displaystyle d}$ is given by $${\displaystyle c(<)d:=c;a^{\mathsf{\text{T}}}\cap d;b^{\mathsf{\text{T}}}.}$$

Another form of composition of relations, which applies to general ${\displaystyle n}$-place relations for ${\displaystyle n\ge 2,}$ is 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. For example, in the query language SQL there is the operation join (SQL).