In the mathematics of binary relations, the composition of relations is the forming of a new binary relation R; S from two given binary relations R and S. In the calculus of relations, the composition of relations is called relative multiplication, [1] and its result is called a relative product. [2]: 40 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 () is the composition of relations "is a brother of" () and "is a parent of" ().
Beginning with Augustus De Morgan, [3] the traditional form of reasoning by syllogism has been subsumed by relational logical expressions and their composition. [4]
If and are two binary relations, then their composition is the relation
In other words, is defined by the rule that says if and only if there is an element such that (that is, and ). [5]: 13
The semicolon as an infix notation for composition of relations dates back to Ernst Schroder's textbook of 1895. [6] Gunther Schmidt has renewed the use of the semicolon, particularly in Relational Mathematics (2011). [2]: 40 [7] The use of semicolon coincides with the notation for function composition used (mostly by computer scientists) in category theory, [8] as well as the notation for dynamic conjunction within linguistic dynamic semantics. [9]
A small circle has been used for the infix notation of composition of relations by John M. Howie in his books considering semigroups of relations. [10] 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 [5]: 18 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 [11] prefer to write and 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, but ⨾ ( U+2A3E ⨾ Z NOTATION RELATIONAL COMPOSITION) denotes left composition. [12] [13]
Binary relations are morphisms in the category . In Rel the objects are sets, the morphisms are binary relations and the composition of morphisms is exactly composition of relations as defined above. The category Set of sets and functions is a subcategory of where the maps are functions .
Given a regular category , its category of internal relations has the same objects as , but now the morphisms are given by subobjects in . [14] Formally, these are jointly monic spans between and . Categories of internal relations are allegories. In particular . Given a field (or more generally a principal ideal domain), the category of relations internal to matrices over , has morphisms linear subspaces . The category of linear relations over the finite field is isomorphic to the phase-free qubit ZX-calculus modulo scalars.
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 and 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." [15]
Consider a heterogeneous relation that is, where and are distinct sets. Then using composition of relation with its converse there are homogeneous relations (on ) and (on ).
If for all there exists some such that (that is, is a (left-)total relation), then for all so that is a reflexive relation or where I is the identity relation Similarly, if is a surjective relation then
The composition is used to distinguish relations of Ferrer's type, which satisfy
Let { France, Germany, Italy, Switzerland } and { French, German, Italian } with the relation given by when is a national language of Since both and is finite, can be represented by a logical matrix, assuming rows (top to bottom) and columns (left to right) are ordered alphabetically:
The converse relation corresponds to the transposed matrix, and the relation composition corresponds to the matrix product when summation is implemented by logical disjunction. It turns out that the matrix contains a 1 at every position, while the reversed matrix product computes as:
Correspondingly, is the universal relation on 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
For a given set the collection of all binary relations on forms a Boolean lattice ordered by inclusion Recall that complementation reverses inclusion: In the calculus of relations [16] it is common to represent the complement of a set by an overbar:
If is a binary relation, let represent the converse relation, also called the transpose. Then the Schröder rules are
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. [4] He wrote [17]
With Schröder rules and complementation one can solve for an unknown relation in relation inclusions such as
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:
Using Schröder's rules, is equivalent to Thus the left residual is the greatest relation satisfying Similarly, the inclusion is equivalent to and the right residual is the greatest relation satisfying [2]: 43–6
One can practice the logic of residuals with Sudoku.[ further explanation needed]
A fork operator has been introduced to fuse two relations and into The construction depends on projections and understood as relations, meaning that there are converse relations and Then the fork of and is given by [18]
Another form of composition of relations, which applies to general -place relations for 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).
In the mathematics of binary relations, the composition of relations is the forming of a new binary relation R; S from two given binary relations R and S. In the calculus of relations, the composition of relations is called relative multiplication, [1] and its result is called a relative product. [2]: 40 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 () is the composition of relations "is a brother of" () and "is a parent of" ().
Beginning with Augustus De Morgan, [3] the traditional form of reasoning by syllogism has been subsumed by relational logical expressions and their composition. [4]
If and are two binary relations, then their composition is the relation
In other words, is defined by the rule that says if and only if there is an element such that (that is, and ). [5]: 13
The semicolon as an infix notation for composition of relations dates back to Ernst Schroder's textbook of 1895. [6] Gunther Schmidt has renewed the use of the semicolon, particularly in Relational Mathematics (2011). [2]: 40 [7] The use of semicolon coincides with the notation for function composition used (mostly by computer scientists) in category theory, [8] as well as the notation for dynamic conjunction within linguistic dynamic semantics. [9]
A small circle has been used for the infix notation of composition of relations by John M. Howie in his books considering semigroups of relations. [10] 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 [5]: 18 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 [11] prefer to write and 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, but ⨾ ( U+2A3E ⨾ Z NOTATION RELATIONAL COMPOSITION) denotes left composition. [12] [13]
Binary relations are morphisms in the category . In Rel the objects are sets, the morphisms are binary relations and the composition of morphisms is exactly composition of relations as defined above. The category Set of sets and functions is a subcategory of where the maps are functions .
Given a regular category , its category of internal relations has the same objects as , but now the morphisms are given by subobjects in . [14] Formally, these are jointly monic spans between and . Categories of internal relations are allegories. In particular . Given a field (or more generally a principal ideal domain), the category of relations internal to matrices over , has morphisms linear subspaces . The category of linear relations over the finite field is isomorphic to the phase-free qubit ZX-calculus modulo scalars.
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 and 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." [15]
Consider a heterogeneous relation that is, where and are distinct sets. Then using composition of relation with its converse there are homogeneous relations (on ) and (on ).
If for all there exists some such that (that is, is a (left-)total relation), then for all so that is a reflexive relation or where I is the identity relation Similarly, if is a surjective relation then
The composition is used to distinguish relations of Ferrer's type, which satisfy
Let { France, Germany, Italy, Switzerland } and { French, German, Italian } with the relation given by when is a national language of Since both and is finite, can be represented by a logical matrix, assuming rows (top to bottom) and columns (left to right) are ordered alphabetically:
The converse relation corresponds to the transposed matrix, and the relation composition corresponds to the matrix product when summation is implemented by logical disjunction. It turns out that the matrix contains a 1 at every position, while the reversed matrix product computes as:
Correspondingly, is the universal relation on 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
For a given set the collection of all binary relations on forms a Boolean lattice ordered by inclusion Recall that complementation reverses inclusion: In the calculus of relations [16] it is common to represent the complement of a set by an overbar:
If is a binary relation, let represent the converse relation, also called the transpose. Then the Schröder rules are
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. [4] He wrote [17]
With Schröder rules and complementation one can solve for an unknown relation in relation inclusions such as
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:
Using Schröder's rules, is equivalent to Thus the left residual is the greatest relation satisfying Similarly, the inclusion is equivalent to and the right residual is the greatest relation satisfying [2]: 43–6
One can practice the logic of residuals with Sudoku.[ further explanation needed]
A fork operator has been introduced to fuse two relations and into The construction depends on projections and understood as relations, meaning that there are converse relations and Then the fork of and is given by [18]
Another form of composition of relations, which applies to general -place relations for 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).