In themathematics ofbinary relations, thecomposition of relations is the forming of a new binary relationR ;S from two given binary relationsR andS. In thecalculus of relations, the composition of relations is calledrelative multiplication,^[1] and its result is called arelative product.^[2]: 40Function composition is the special case of composition of relations where all relations involved arefunctions.

The worduncle indicates a compound relation: for a person to be an uncle, he must be the brother of a parent. Inalgebraic logic it is said that the relation of Uncle (${\displaystyle xUz}$) is the composition of relations "is a brother of" (${\displaystyle xBy}$) and "is a parent of" (${\displaystyle yPz}$).$${\displaystyle U=BP\text{ is equivalent to: }xUz\text{ if and only if }\mathrm{\exists }yxByPz.}$$

Beginning withAugustus De Morgan,^[3] the traditional form of reasoning bysyllogism has been subsumed by relational logical expressions and their composition.^[4]

If${\displaystyle R\subseteq X\times Y}$ and${\displaystyle S\subseteq Y\times Z}$ are two binary relations, thentheir composition${\displaystyle R;S}$ is the relation$${\displaystyle R;S=\{(x,z)\in X\times Z:\text{ there exists }y\in Y\text{ such that }(x,y)\in R\text{ and }(y,z)\in S\}.}$$

In other words,${\displaystyle R;S\subseteq X\times Z}$ is defined by the rule that says${\displaystyle (x,z)\in R;S}$ if and only if there is an element${\displaystyle y\in Y}$ such that${\displaystyle xRySz}$ (that is,${\displaystyle (x,y)\in R}$ and${\displaystyle (y,z)\in S}$).^[5]: 13

Thesemicolon as aninfix notation for composition of relations dates back toErnst Schröder's textbook of 1895.^[6]Gunther Schmidt has renewed the use of the semicolon, particularly inRelational Mathematics (2011).^{[2]: 40 [7]} The use of the semicoloncoincides with the notation for function composition used (mostly by computer scientists) incategory theory,^[8] as well as the notation for dynamic conjunction within linguisticdynamic semantics.^[9]

A small circle${\displaystyle (R\circ S)}$ has been used for the infix notation of composition of relations byJohn M. Howie in his books consideringsemigroups of relations.^[10] However, the small circle is widely used to representcomposition of functions${\displaystyle g(f(x))=(g\circ f)(x)}$, whichreverses the text sequence from the operation sequence. The small circle was used in the introductory pages ofGraphs and Relations^[5]: 18 until it was dropped in favor of juxtaposition (no infix notation).Juxtaposition${\displaystyle (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^[11] prefer to write${\displaystyle {\circ }_l}$ and${\displaystyle {\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 theZ notation:${\displaystyle \circ }$ is used to denote the traditional (right) composition, while left composition is denoted by a fat semicolon. The unicode symbols are ⨾ and ⨟.^[12][13]

Binary relations${\displaystyle R\subseteq X\times Y}$ are morphisms${\displaystyle R:X\to Y}$ in thecategory${\displaystyle \mathsf{R}\mathsf{e}\mathsf{l}}$. InRel the objects aresets, the morphisms are binary relations and the composition of morphisms is exactly composition of relations as defined above. The categorySet of sets and functions is asubcategory of${\displaystyle \mathsf{R}\mathsf{e}\mathsf{l}}$ where the maps${\displaystyle X\to Y}$ are functions${\displaystyle f:X\to Y}$.

Given aregular category${\displaystyle \mathbb{X}}$, its category of internal relations${\displaystyle \mathsf{R}\mathsf{e}\mathsf{l}(\mathbb{X})}$ has the same objects as${\displaystyle \mathbb{X}}$, but now the morphisms${\displaystyle X\to Y}$ are given by subobjects${\displaystyle R\subseteq X\times Y}$ in${\displaystyle \mathbb{X}}$.^[14] Formally, these arejointly monicspans between${\displaystyle X}$ and${\displaystyle Y}$. Categories of internal relations areallegories. In particular${\displaystyle \mathsf{R}\mathsf{e}\mathsf{l}(\mathsf{S}\mathsf{e}\mathsf{t})\cong \mathsf{R}\mathsf{e}\mathsf{l}}$. Given afield${\displaystyle k}$ (or more generally aprincipal ideal domain), the category of relations internal tomatrices over${\displaystyle k}$,${\displaystyle \mathsf{R}\mathsf{e}\mathsf{l}(\mathsf{M}\mathsf{a}\mathsf{t}(k)),}$ has morphisms${\displaystyle n\to m}$ thelinear subspaces${\displaystyle R\subseteq k^n\oplus k^m}$. The category of linear relations over thefinite field${\displaystyle {\mathbb{F}}_2}$ is isomorphic to the phase-free qubitZX-calculus modulo scalars.

• Composition of relations isassociative:${\displaystyle R;(S;T)=(R;S);T.}$
• Theconverse 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 asemigroup with involution.
• The composition of(partial) functions (that is, functional relations) is again a (partial) function.
• If${\displaystyle R}$ and${\displaystyle S}$ areinjective, then${\displaystyle R;S}$ is injective, which conversely implies only the injectivity of${\displaystyle R.}$
• If${\displaystyle R}$ and${\displaystyle S}$ aresurjective, then${\displaystyle R;S}$ is surjective, which conversely implies only the surjectivity of${\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 amonoid with zero, where the identity map on${\displaystyle X}$ is theneutral element, and the empty set is thezero element.

Finite binary relations are represented bylogical 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 thematrix 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 forcomputing the conclusions traditionally drawn by means of hypothetical syllogisms andsorites."^[15]

Consider a heterogeneous relation${\displaystyle R\subseteq A\times B;}$ that is, where${\displaystyle A}$ and${\displaystyle B}$ are distinct sets. Then using composition of relation${\displaystyle R}$ with itsconverse${\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,xR{R}^{\mathsf{\text{T}}}x}$ so that${\displaystyle R{R}^{\mathsf{\text{T}}}}$ is areflexive 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 asurjective 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 adifunctional 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.}$

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 anational language of${\displaystyle a.}$Since both${\displaystyle A}$ and${\displaystyle B}$ is finite,${\displaystyle R}$ can be represented by alogical matrix, assuming rows (top to bottom) and columns (left to right) are ordered alphabetically:

Theconverse relation${\displaystyle R^{\mathsf{\text{T}}}}$ corresponds to thetransposed matrix, and the relation composition${\displaystyle R^{\mathsf{\text{T}}};R}$ corresponds to thematrix product${\displaystyle R^{\mathsf{\text{T}}}R}$ when summation is implemented bylogical 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:This matrix is symmetric, and represents a homogeneous relation on${\displaystyle A.}$

Correspondingly,${\displaystyle R^{\mathsf{\text{T}}};R}$ is theuniversal 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}}}.}$

For a given set${\displaystyle V,}$ the collection of allbinary relations on${\displaystyle V}$ forms aBoolean lattice ordered byinclusion${\displaystyle (\subseteq ).}$ Recall thatcomplementation reverses inclusion:${\displaystyle A\subseteq B\text{ implies }{B}^{\complement }\subseteq A^{\complement }.}$ In thecalculus of relations^[16] 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 theconverse relation, also called thetranspose. Then the Schröder rules are$${\displaystyle QR\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.^{[5]: 15–19}

Though this transformation of an inclusion of a composition of relations was detailed byErnst Schröder, in factAugustus De Morgan first articulated the transformation as Theorem K in 1860.^[4] He wrote^[17]$${\displaystyle LM\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 RX\subseteq S\text{and}XR\subseteq S.}$$For instance, by Schröder rule${\displaystyle RX\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 theleft residual of${\displaystyle S}$ by${\displaystyle R}$.

Just as composition of relations is a type of multiplication resulting in a product, so someoperations 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 AX\subseteq B}$ is equivalent to${\displaystyle X\subseteq A\mathrm{\setminus }B.}$ Thus the left residual is the greatest relation satisfying${\displaystyle AX\subseteq B.}$ Similarly, the inclusion${\displaystyle YC\subseteq D}$ is equivalent to${\displaystyle Y\subseteq D/C,}$ and the right residual is the greatest relation satisfying${\displaystyle YC\subseteq D.}$^{[2]: 43–6}

One can practice the logic of residuals withSudoku.^{[further explanation needed]}

A fork operator has been introduced to fuse two relations${\displaystyle c:H\to A}$ and${\displaystyle d:H\to B}$ into 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 thefork of${\displaystyle c}$ and${\displaystyle d}$ is given by^[18]

Another form of composition of relations, which applies to general${\displaystyle n}$-place relations for${\displaystyle n\ge 2,}$ is thejoin operation ofrelational 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 thequery languageSQL there is the operationjoin (SQL).

• Demonic composition – Mathematical operation
• Friend of a friend – Human contact that exists because of a mutual friend

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

• Algebraic logic
• Binary operations
• Mathematical relations

• Webarchive template wayback links
• Articles with short description
• Short description matches Wikidata
• Wikipedia articles needing clarification from January 2022