Composition of relations explained
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 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,[1] the traditional form of reasoning by syllogism has been subsumed by relational logical expressions and their composition.
Definition
If
and
are two binary relations, thentheir 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 as an infix notation for composition of relations dates back to Ernst Schroder's textbook of 1895.[2] Gunther Schmidt has renewed the use of the semicolon, particularly in Relational Mathematics (2011).[3] The use of semicolon coincides with the notation for function composition used (mostly by computer scientists) in category theory,[4] as well as the notation for dynamic conjunction within linguistic dynamic semantics.[5]
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.
[6] 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[7] 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 ⨟.
[8] [9] Mathematical generalizations
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
.
, its category of internal relations
has the same objects as
, but now the morphisms
are given by subobjects
in
.
[10] 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.
Properties
is
} \, ; R^. 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
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
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."
[11] Heterogeneous relations
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
Let
and
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:
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
For a given set
the collection of all
binary relations on
forms a
Boolean lattice ordered by
inclusion
Recall that
complementation reverses inclusion:
A\subseteqBimpliesB\complement\subseteqA\complement.
In the calculus of relations
[12] 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.
[13] 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[14]
With Schröder rules and complementation one can solve for an unknown relation
in relation inclusions such as
For instance, by Schröder rule
RX\subseteqSimpliesRsf{T}\bar{S}\subseteq\bar{X},
and complementation gives
X\subseteq\overline{Rsf{T}\bar{S}},
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:
A\backslashBl{:=}\overline{Asf{T}\bar{B}}
D/Cl{:=}\overline{\bar{D}Csf{T}}
\operatorname{syq}(E,F)l{:=}\overline{Esf{T}\bar{F}}\cap\overline{\bar{E}sf{T}F}
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
One can practice the logic of residuals with Sudoku.
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 by
[15] 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).
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,.
Notes and References
- A. De Morgan (1860) "On the Syllogism: IV and on the Logic of Relations"
- [Ernst Schroder]
- Book: Paul Taylor. Practical Foundations of Mathematics. 1999. Cambridge University Press. 978-0-521-63107-5. 24. A free HTML version of the book is available at http://www.cs.man.ac.uk/~pt/Practical_Foundations/
- Michael Barr & Charles Wells (1998) Category Theory for Computer Scientists, page 6, from McGill University
- Rick Nouwen and others (2016) Dynamic Semantics §2.2, from Stanford Encyclopedia of Philosophy
- [John M. Howie ]
- Kilp, Knauer & Mikhalev, p. 7
- ISO/IEC 13568:2002(E), p. 23
- See U+2A3E and U+2A1F on FileFormat.info
- Web site: internal relations . nlab . 26 September 2023.
- [Irving Copilowish]
- [Vaughn Pratt]
- [Gunther Schmidt]
- De Morgan indicated contraries by lower case, conversion as M−1, and inclusion with)), so his notation was
- [Gunther Schmidt]