Composition of relations

Summary

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]

Definition

edit

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 

Notational variations

edit

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 the 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, while left composition is denoted by a fat semicolon. The unicode symbols are ⨾ and ⨟.[12][13]

Mathematical generalizations

edit

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   the linear subspaces  . The category of linear relations over the finite field   is isomorphic to the phase-free qubit ZX-calculus modulo scalars.

Properties

edit
  • Composition of relations is associative:  
  • The converse relation of   is   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   and   are injective, then   is injective, which conversely implies only the injectivity of  
  • If   and   are surjective, then   is surjective, which conversely implies only the surjectivity of  
  • The set of binary relations on a set   (that is, relations from   to  ) together with (left or right) relation composition forms a monoid with zero, where the identity map on   is the neutral element, and the empty set is the zero element.

Composition in terms of matrices

edit

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]

Heterogeneous relations

edit

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   In this case   The opposite inclusion occurs for a difunctional relation.

The composition   is used to distinguish relations of Ferrer's type, which satisfy  

Example

edit

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:   This matrix is symmetric, and represents a homogeneous relation on  

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  

Schröder rules

edit

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   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 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   For instance, by Schröder rule   and complementation gives   which is called the left residual of   by  .

Quotients

edit

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:

  • Left residual:  
  • Right residual:  
  • Symmetric quotient:  

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]

Join: another form of composition

edit

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

See also

edit

Notes

edit
  1. ^ Bjarni Jónsson (1984) "Maximal Algebras of Binary Relations", in Contributions to Group Theory, K.I. Appel editor American Mathematical Society ISBN 978-0-8218-5035-0
  2. ^ a b c Gunther Schmidt (2011) Relational Mathematics, Encyclopedia of Mathematics and its Applications, vol. 132, Cambridge University Press ISBN 978-0-521-76268-7
  3. ^ A. De Morgan (1860) "On the Syllogism: IV and on the Logic of Relations"
  4. ^ a b Daniel D. Merrill (1990) Augustus De Morgan and the Logic of Relations, page 121, Kluwer Academic ISBN 9789400920477
  5. ^ a b c Gunther Schmidt & Thomas Ströhlein (1993) Relations and Graphs, Springer books
  6. ^ Ernst Schroder (1895) Algebra und Logik der Relative
  7. ^ Paul Taylor (1999). Practical Foundations of Mathematics. Cambridge University Press. p. 24. ISBN 978-0-521-63107-5. A free HTML version of the book is available at http://www.cs.man.ac.uk/~pt/Practical_Foundations/
  8. ^ Michael Barr & Charles Wells (1998) Category Theory for Computer Scientists Archived 2016-03-04 at the Wayback Machine, page 6, from McGill University
  9. ^ Rick Nouwen and others (2016) Dynamic Semantics §2.2, from Stanford Encyclopedia of Philosophy
  10. ^ John M. Howie (1995) Fundamentals of Semigroup Theory, page 16, LMS Monograph #12, Clarendon Press ISBN 0-19-851194-9
  11. ^ Kilp, Knauer & Mikhalev, p. 7
  12. ^ ISO/IEC 13568:2002(E), p. 23
  13. ^ See U+2A3E and U+2A1F on FileFormat.info
  14. ^ "internal relations". nlab. Retrieved 26 September 2023.
  15. ^ Irving Copilowish (December 1948) "Matrix development of the calculus of relations", Journal of Symbolic Logic 13(4): 193–203 Jstor link, quote from page 203
  16. ^ Vaughn Pratt The Origins of the Calculus of Relations, from Stanford University
  17. ^ De Morgan indicated contraries by lower case, conversion as M−1, and inclusion with )), so his notation was  
  18. ^ Gunther Schmidt and Michael Winter (2018): Relational Topology, page 26, Lecture Notes in Mathematics vol. 2208, Springer books, ISBN 978-3-319-74451-3

References

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