Composition of relations

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 words uncle and aunt indicate a compound relation: for a person to be an uncle, he must be a brother of a parent (or a sister for an aunt). In algebraic logic it is said that the relation of Uncle ( "xUz" ) is the composition of relations "is a brother of" ( "xBy" ) and "is a parent of" ( "yPz" ).
Beginning with Augustus De Morgan, the traditional form of reasoning by syllogism has been subsumed by relational logical expressions and their composition.
Definition.
If formula_2 and formula_3 are two binary relations, then
their composition formula_4 is the relation
In other words, formula_6 is defined by the rule that says formula_7 if and only if there is an element formula_8 such that formula_9 (i.e. formula_10 and formula_11).
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). 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 formula_12 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 formula_13 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 formula_14 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 formula_15 and formula_16 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: formula_17 is used to denote the traditional (right) composition, but ⨾ (a fat open semicolon with Unicode code point U+2A3E) denotes left composition. 
The binary relations formula_2 are sometimes regarded as the morphisms formula_19 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.
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 × 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" ⊆ "A" × "B", i.e. where A and B are distinct sets. Then using composition of relation "R" with its converse "R"T, there are homogeneous relations "R R"T (on "A") and "R"T "R" (on "B").
If ∀"x" ∈ "A" ∃"y" ∈ B "xRy" (that is, "R" is a (left-)total relation), then ∀"x" "xRR"T"x" so that "R R"T is a reflexive relation or I ⊆ "R R"T where I is the identity relation {"x"I"x" : "x" ∈ "A"}. Similarly, if "R" is a surjective relation then 
The composition formula_21 is used to distinguish relations of Ferrer's type, which satisfy formula_22
Example.
Let "A" = { France, Germany, Italy, Switzerland } and "B" = { French, German, Italian } with the relation "R" given by "aRb" when "b" is a national language of "a". The logical matrix for "R" is given by
Schröder rules.
For a given set "V", the collection of all binary relations on "V" forms a Boolean lattice ordered by inclusion (⊆). Recall that complementation reverses inclusion:
formula_26 In the calculus of relations it is common to represent the complement of a set by an overbar: formula_27
If "S" is a binary relation, let formula_28 represent the converse relation, also called the "transpose". Then the Schröder rules are
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 
With Schröder rules and complementation one can solve for an unknown relation "X" in relation inclusions such as 
For instance, by Schröder rule formula_32 and complementation gives formula_33 which is called the left residual of S by R .
Quotients.
Just as composition of relations is a type of multiplication resulting in a product, so some compositions 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:
Using Schröder's rules, "AX" ⊆ "B" is equivalent to "X" ⊆ "A"formula_37"B". Thus the left residual is the greatest relation satisfying "AX" ⊆ "B". Similarly, the inclusion "YC" ⊆ "D" is equivalent to "Y" ⊆ "D"/"C", and the right residual is the greatest relation satisfying "YC" ⊆ "D".
Join: another form of composition.
A fork operator (<) has been introduced to fuse two relations "c": "H" → "A" and "d": "H" → "B" into "c"(<)"d": "H" → "A" × "B".
The construction depends on projections "a": "A" × "B" → "A" and "b": "A" × "B" → "B", understood as relations, meaning that there are converse relations "a"T and "b"T. Then the fork of "c" and "d" is given by
Another form of composition of relations, which applies to general "n"-place relations for "n" ≥ 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).