In the
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
of
binary relation
In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...
s, 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
In mathematical logic, algebraic logic is the reasoning obtained by manipulating equations with free variables.
What is now usually called classical algebraic logic focuses on the identification and algebraic description of models appropriate for ...
, the composition of relations is called relative multiplication, and its result is called a relative product.
[ ]Function composition
In mathematics, function composition is an operation that takes two functions and , and produces a function such that . In this operation, the function is applied to the result of applying the function to . That is, the functions and ...
is the special case of composition of relations where all relations involved are function
Function or functionality may refer to:
Computing
* Function key, a type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-oriente ...
s.
The word uncle
An uncle is usually defined as a male relative who is a sibling of a parent or married to a sibling of a parent. Uncles who are related by birth are second-degree relatives. The female counterpart of an uncle is an aunt, and the reciprocal relat ...
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, the traditional form of reasoning by syllogism
A syllogism ( grc-gre, συλλογισμός, ''syllogismos'', 'conclusion, inference') is a kind of logical argument that applies deductive reasoning to arrive at a conclusion based on two propositions that are asserted or assumed to be true.
...
has been subsumed by relational logical expressions and their composition.[
]
Definition
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 ).[
]
Notational variations
The semicolon
The semicolon or semi-colon is a symbol commonly used as orthographic punctuation. In the English language, a semicolon is most commonly used to link (in a single sentence) two independent clauses that are closely related in thought. When a ...
as an infix notation
Infix notation is the notation commonly used in arithmetical and logical formulae and statements. It is characterized by the placement of operators between operands—" infixed operators"—such as the plus sign in .
Usage
Binary relations a ...
for composition of relations dates back to Ernst Schroder's textbook of 1895. Gunther Schmidt
Gunther Schmidt (born 1939, Rüdersdorf) is a German mathematician who works also in informatics.
Life
Schmidt began studying Mathematics in 1957 at Göttingen University. His academic teachers were in particular Kurt Reidemeister, Wilhelm K ...
has renewed the use of the semicolon, particularly in ''Relational Mathematics'' (2011).[ A free HTML version of the book is available at http://www.cs.man.ac.uk/~pt/Practical_Foundations/] The use of semicolon coincides with the notation for function composition used (mostly by computer scientists) in category theory
Category theory is a general theory of mathematical structures and their relations that was introduced by Samuel Eilenberg and Saunders Mac Lane in the middle of the 20th century in their foundational work on algebraic topology. Nowadays, cate ...
, as well as the notation for dynamic conjunction within linguistic dynamic semantics Dynamic semantics is a framework in logic and natural language semantics that treats the meaning of a sentence as its potential to update a context. In static semantics, knowing the meaning of a sentence amounts to knowing when it is true; in dynami ...
.
A small circle has been used for the infix notation of composition of relations by John M. Howie
John Mackintosh Howie (23 May 1936 – 26 December 2011) was a Scottish mathematician and prominent semigroup theorist.
Biography
Howie was educated at Robert Gordon's College, Aberdeen, the University of Aberdeen and Balliol College, Oxfo ...
in his books considering semigroup
In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative internal binary operation on it.
The binary operation of a semigroup is most often denoted multiplicatively: ''x''·''y'', or simply ''xy'', ...
s of relations.[ John M. Howie (1995) ''Fundamentals of Semigroup Theory'', page 16, LMS Monograph #12, ]Clarendon Press
Oxford University Press (OUP) is the university press of the University of Oxford. It is the largest university press in the world, and its printing history dates back to the 1480s. Having been officially granted the legal right to print books ...
However, the small circle is widely used to represent composition of functions
In mathematics, function composition is an operation that takes two functions and , and produces a function such that . In this operation, the function is applied to the result of applying the function to . That is, the functions and ...
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
Juxtaposition is an act or instance of placing two elements close together or side by side. This is often done in order to compare/contrast the two, to show similarities or differences, etc.
Speech
Juxtaposition in literary terms is the showing ...
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 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
The Z notation is a formal specification language used for describing and modelling computing systems. It is targeted at the clear specification of computer programs and computer-based systems in general.
History
In 1974, Jean-Raymond Abrial ...
: is used to denote the traditional (right) composition, but ⨾ () denotes left composition.
The binary relations are sometimes regarded as the morphisms in a category
Category, plural categories, may refer to:
Philosophy and general uses
* Categorization, categories in cognitive science, information science and generally
*Category of being
* ''Categories'' (Aristotle)
*Category (Kant)
*Categories (Peirce)
* ...
Rel Rel or REL may mean:
__NOTOC__ Science and technology
* REL, a human gene
* the rel descriptor of stereochemistry, see Relative configuration
*REL (''Rassemblement Européen pour la Liberté''), European Rally for Liberty, a defunct French far-ri ...
which has the sets as objects. In Rel, composition of morphisms is exactly composition of relations as defined above. The category Set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
of sets is a subcategory of Rel that has the same objects but fewer morphisms.
Properties
* Composition of relations is associative
In mathematics, the associative property is a property of some binary operations, which means that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacement f ...
:
* The converse relation
In mathematics, the converse relation, or transpose, of a binary relation is the relation that occurs when the order of the elements is switched in the relation. For example, the converse of the relation 'child of' is the relation 'parent& ...
of is This property makes the set of all binary relations on a set a semigroup with involution In mathematics, particularly in abstract algebra, a semigroup with involution or a *-semigroup is a semigroup equipped with an involutive anti-automorphism, which—roughly speaking—brings it closer to a group because this involution, considered ...
.
* The composition of (partial) functions (that is, functional relations) is again a (partial) function.
* If and are injective
In mathematics, an injective function (also known as injection, or one-to-one function) is a function that maps distinct elements of its domain to distinct elements; that is, implies . (Equivalently, implies in the equivalent contrapositiv ...
, then is injective, which conversely implies only the injectivity of
* If and are surjective
In mathematics, a surjective function (also known as surjection, or onto function) is a function that every element can be mapped from element so that . In other words, every element of the function's codomain is the image of one element of i ...
, 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
In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0.
Monoids ...
with zero, where the identity map on is the neutral element
In mathematics, an identity element, or neutral element, of a binary operation operating on a set is an element of the set that leaves unchanged every element of the set when the operation is applied. This concept is used in algebraic structures su ...
, and the empty set is the zero element
In mathematics, a zero element is one of several generalizations of the number zero to other algebraic structures. These alternate meanings may or may not reduce to the same thing, depending on the context.
Additive identities
An additive identi ...
.
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 and An entry in the matrix product
In mathematics, particularly in linear algebra, matrix multiplication is a binary operation that produces a matrix from two matrices. For matrix multiplication, the number of columns in the first matrix must be equal to the number of rows in the s ...
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 that is, where and are distinct sets. Then using composition of relation with its converse
Converse may refer to:
Mathematics and logic
* Converse (logic), the result of reversing the two parts of a definite or implicational statement
** Converse implication, the converse of a material implication
** Converse nonimplication, a logical c ...
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
In mathematics, a binary relation ''R'' on a set ''X'' is reflexive if it relates every element of ''X'' to itself.
An example of a reflexive relation is the relation " is equal to" on the set of real numbers, since every real number is equal to ...
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
Let and with the relation given by when is a national language
A national language is a language (or language variant, e.g. dialect) that has some connection—de facto or de jure—with a nation. There is little consistency in the use of this term. One or more languages spoken as first languages in the te ...
of
Since both and is finite, can be represented by a logical matrix
A logical matrix, binary matrix, relation matrix, Boolean matrix, or (0, 1) matrix is a matrix with entries from the Boolean domain Such a matrix can be used to represent a binary relation between a pair of finite sets.
Matrix representation ...
, assuming rows (top to bottom) and columns (left to right) are ordered alphabetically:
The converse relation
In mathematics, the converse relation, or transpose, of a binary relation is the relation that occurs when the order of the elements is switched in the relation. For example, the converse of the relation 'child of' is the relation 'parent& ...
corresponds to the transposed matrix, and the relation composition corresponds to the matrix product
In mathematics, particularly in linear algebra, matrix multiplication is a binary operation that produces a matrix from two matrices. For matrix multiplication, the number of columns in the first matrix must be equal to the number of rows in the s ...
when summation is implemented by logical disjunction
In logic, disjunction is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is raining or it is snowing" can be represented in logic using the disjunctive formula R \lor S ...
. 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
In mathematics, a homogeneous relation (also called endorelation) over a set ''X'' is a binary relation over ''X'' and itself, i.e. it is a subset of the Cartesian product . This is commonly phrased as "a relation on ''X''" or "a (binary) 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
For a given set the collection of all binary relation
In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...
s on forms a Boolean lattice ordered by inclusion
Inclusion or Include may refer to:
Sociology
* Social inclusion, aims to create an environment that supports equal opportunity for individuals and groups that form a society.
** Inclusion (disability rights), promotion of people with disabiliti ...
Recall that complementation reverses inclusion:
In the calculus of relations
In mathematical logic, algebraic logic is the reasoning obtained by manipulating equations with free variables.
What is now usually called classical algebraic logic focuses on the identification and algebraic description of models appropriate for ...
it is common to represent the complement of a set by an overbar:
If is a binary relation, let represent the converse relation
In mathematics, the converse relation, or transpose, of a binary relation is the relation that occurs when the order of the elements is switched in the relation. For example, the converse of the relation 'child of' is the relation 'parent& ...
, 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.Gunther Schmidt
Gunther Schmidt (born 1939, Rüdersdorf) is a German mathematician who works also in informatics.
Life
Schmidt began studying Mathematics in 1957 at Göttingen University. His academic teachers were in particular Kurt Reidemeister, Wilhelm K ...
& Thomas Ströhlein (1993) ''Relations and Graphs'', Springer books
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.[Daniel D. Merrill (1990) ''Augustus De Morgan and the Logic of Relations'', page 121, ]Kluwer Academic
Springer Science+Business Media, commonly known as Springer, is a German multinational publishing company of books, e-books and peer-reviewed journals in science, humanities, technical and medical (STM) publishing.
Originally founded in 1842 in ...
He wrote
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
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 [Gunther Schmidt (2011) ''Relational Mathematics'', Encyclopedia of Mathematics and its Applications, vol. 132, ]Cambridge University Press
Cambridge University Press is the university press of the University of Cambridge. Granted letters patent by Henry VIII of England, King Henry VIII in 1534, it is the oldest university press
A university press is an academic publishing hou ...
One can practice the logic of residuals with Sudoku
Sudoku (; ja, 数独, sūdoku, digit-single; originally called Number Place) is a logic-based, combinatorial number-placement puzzle. In classic Sudoku, the objective is to fill a 9 × 9 grid with digits so that each column, each row ...
.
Join: another form of composition
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 of and is given byGunther Schmidt
Gunther Schmidt (born 1939, Rüdersdorf) is a German mathematician who works also in informatics.
Life
Schmidt began studying Mathematics in 1957 at Göttingen University. His academic teachers were in particular Kurt Reidemeister, Wilhelm K ...
and Michael Winter (2018): ''Relational Topology'', page 26, Lecture Notes in Mathematics
''Lecture Notes in Mathematics'' is a book series in the field of mathematics, including articles related to both research and teaching. It was established in 1964 and was edited by A. Dold, Heidelberg and B. Eckmann, Zürich. Its publisher is Spr ...
vol. 2208, Springer books,
Another form of composition of relations, which applies to general -place relations for is the ''join Join may refer to:
* Join (law), to include additional counts or additional defendants on an indictment
*In mathematics:
** Join (mathematics), a least upper bound of sets orders in lattice theory
** Join (topology), an operation combining two top ...
'' operation of relational algebra
In database theory, relational algebra is a theory that uses algebraic structures with a well-founded semantics for modeling data, and defining queries on it. The theory was introduced by Edgar F. Codd.
The main application 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)
A join clause in SQL – corresponding to a join operation in relational algebra – combines columns from one or more tables into a new table. Informally, a join stitches two tables and puts on the same row records with matching fields : INNER, ...
.
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
Walter de Gruyter GmbH, known as De Gruyter (), is a German scholarly publishing house specializing in academic literature.
History
The roots of the company go back to 1749 when Frederick the Great granted the Königliche Realschule in Be ...
,.
{{Order theory
Algebraic logic
Binary operations
Mathematical relations