Relation composition

In the mathematics of binary relations, the composition of relations is the forming of a new binary relation from two given binary relations ''R'' and ''S''. In the calculus of relations, the composition of relations is called relative multiplication, and its result is called a relative product. Function composition is the special case of composition of relations where all relations involved are functions.

The word uncle indicates a compound relation: for a person to be an uncle, he must be the brother of a parent. In algebraic logic it is said that the relation of Uncle ($x U z$) is the composition of relations "is a brother of" ($x B y$) and "is a parent of" ($y P z$).
$U = BP \quad \text \quad xByPz \text xUz.$

Beginning with Augustus De Morgan, the traditional form of reasoning by syllogism has been subsumed by relational logical expressions and their composition.

Definition

If $R \subseteq X \times Y$ and $S \subseteq Y \times Z$ are two binary relations, then
their composition $R; S$ is the relation
$R; S = \.$

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

Notational variations

The semicolon as an infix notation for composition of relations dates back to Ernst Schroder's textbook of 1895. Gunther Schmidt has renewed the use of the semicolon, particularly in ''Relational Mathematics'' (2011). A free HTML version of the book is available at http://www.cs.man.ac.uk/~pt/Practical_Foundations/ The use of semicolon coincides with the notation for function composition used (mostly by computer scientists) in category theory, as well as the notation for dynamic conjunction within linguistic dynamic semantics.

A small circle $(R \circ S)$ has been used for the infix notation of composition of relations by John M. Howie in his books considering semigroups of relations.John M. Howie (1995) ''Fundamentals of Semigroup Theory'', page 16, LMS Monograph #12, Clarendon Press However, the small circle is widely used to represent composition of functions $g(f(x)) = (g \circ f)(x)$ which ''reverses'' the text sequence from the operation sequence. The small circle was used in the introductory pages of ''Graphs and Relations'' until it was dropped in favor of juxtaposition (no infix notation). Juxtaposition $(RS)$ is commonly used in algebra to signify multiplication, so too, it can signify relative multiplication.

Further with the circle notation, subscripts may be used. Some authors 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 ⨾ () denotes left composition.

The binary relations $R \subseteq X\times Y$ are sometimes regarded as the morphisms $R : 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.

Properties

* Composition of relations is associative: $R;(S;T) = (R;S);T.$
* The converse relation of $R \, ; S$ is $(R \, ; S)^\textsf = S^ \, ; R^.$ 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 $R$ and $S$ are injective, then $R \, ; S$ is injective, which conversely implies only the injectivity of $R.$
* If $R$ and $S$ are surjective, then $R \, ; S$ is surjective, which conversely implies only the surjectivity of $S.$
* The set of binary relations on a set $X$ (that is, 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.

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 $1 + 1 = 1$ and $1 \times 1 = 1.$ An entry in the matrix product of two logical matrices will be 1, then, only if the row and column multiplied have a corresponding 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 $R \subseteq A \times B;$ that is, where $A$ and $B$ are distinct sets. Then using composition of relation $R$ with its converse $R^\textsf,$ there are homogeneous relations $R R^\textsf$ (on $A$) and $R^\textsf R$ (on $B$).

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

The composition $\bar^\textsf R$ is used to distinguish relations of Ferrer's type, which satisfy $R \bar^\textsf R = R.$

Example

Let $A =$ and $B =$ with the relation $R$ given by $a R b$ when $b$ is a national language of $a.$
Since both $A$ and $B$ is finite, $R$ can be represented by a logical matrix, assuming rows (top to bottom) and columns (left to right) are ordered alphabetically:
$\begin 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 1 & 1 \end.$

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

Correspondingly, $R^\textsf \, ; R$ is the universal relation on $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 $R \, ; R^\textsf.$

Schröder rules

For a given set $V,$ the collection of all binary relation