In the mathematics of binary relations, the composition of relations. 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 functionss.

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

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

Definition

).

Notational variations

The semicolon as an infix notation for composition of relations dates back to Ernst Schröder's textbook of 1895. Gunther Schmidt has renewed the use of the semicolon, particularly in Relational Mathematics (2011). The use of the 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.

has been used for the infix notation of composition of relations by John M. Howie in his books considering semigroups of relations. However, the small circle is widely used to represent composition of functions, 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 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 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 is used to denote the traditional (right) composition, while left composition is denoted by a fat semicolon. The unicode symbols are ⨾ and ⨟.

Mathematical generalizations

in the category of relations. Its objects are sets, its morphisms are binary relations and the composition of morphisms is exactly composition of relations as defined above. The category of sets of sets and functions is a subcategory.

Given a regular category. Formally, these are jointly monic spans. Categories of internal relations are allegories. Given a field (or more generally a principal ideal domain), the category of relations internal to matrices the linear subspaces. The category of linear relations over the finite field is isomorphic to the phase-free qubit ZX-calculus modulo scalars.

Properties

• Composition of relations is associative

• The converse relation This property makes the set of all binary relations on a set a semigroup with involution.

• The composition of (partial) functionss (that is, functional relations) is again a (partial) function.

• are injective

• are surjective

• ) together with (left or right) relation composition forms a monoid 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 An entry in the matrix product. 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

with its converse).

is a (left-)total relation is a reflexive relation is a surjective relation The opposite inclusion occurs for a difunctional relation.

Example

is a national language can be represented by a logical matrix

The converse relation corresponds to the transposed matrix corresponds to the matrix product when summation is implemented by logical disjunction

is the universal relation

Schröder rules

the collection of all binary relations forms a Boolean lattice ordered by inclusion Recall that complementation In the calculus of relations

represent the converse relation, also called the transpose 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

which is called the left residual.

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:

One can practice the logic of residuals with Sudoku.

Join: another form of composition

Then the is given by

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).

See also

Notes

References

• 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,.