In
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 ...
, the
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 has the class of
sets as
objects
Object may refer to:
General meanings
* Object (philosophy), a thing, being, or concept
** Object (abstract), an object which does not exist at any particular time or place
** Physical object, an identifiable collection of matter
* Goal, an ...
and
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 as
morphisms
In mathematics, particularly in category theory, a morphism is a structure-preserving map from one mathematical structure to another one of the same type. The notion of morphism recurs in much of contemporary mathematics. In set theory, morphisms ...
.
A morphism (or arrow) ''R'' : ''A'' → ''B'' in this category is a relation between the sets ''A'' and ''B'', so .
The
composition of two relations ''R'': ''A'' → ''B'' and ''S'': ''B'' → ''C'' is given by
:(''a'', ''c'') ∈ ''S''
o ''R'' ⇔ for some ''b'' ∈ ''B'', (''a'', ''b'') ∈ ''R'' and (''b'', ''c'') ∈ ''S''.
Rel has also been called the "category of correspondences of sets".
Properties
The category Rel has the
category of sets
In the mathematical field of category theory, the category of sets, denoted as Set, is the category whose objects are sets. The arrows or morphisms between sets ''A'' and ''B'' are the total functions from ''A'' to ''B'', and the composition of m ...
Set as a (wide)
subcategory
In mathematics, specifically category theory, a subcategory of a category ''C'' is a category ''S'' whose objects are objects in ''C'' and whose morphisms are morphisms in ''C'' with the same identities and composition of morphisms. Intuitivel ...
, where the arrow in Set corresponds to the relation defined by .
[This category is called SetRel by Rydeheard and Burstall.]
A morphism in Rel is a relation, and the corresponding morphism in the
opposite category
In category theory, a branch of mathematics, the opposite category or dual category ''C''op of a given category ''C'' is formed by reversing the morphisms, i.e. interchanging the source and target of each morphism. Doing the reversal twice yields t ...
to Rel has arrows reversed, so it is 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& ...
. Thus Rel contains its opposite and is
self-dual
In mathematics, a duality translates concepts, theorems or mathematical structures into other concepts, theorems or structures, in a Injective function, one-to-one fashion, often (but not always) by means of an Involution (mathematics), involutio ...
.
The
involution
Involution may refer to:
* Involute, a construction in the differential geometry of curves
* '' Agricultural Involution: The Processes of Ecological Change in Indonesia'', a 1963 study of intensification of production through increased labour inpu ...
represented by taking the converse relation provides the dagger to make Rel a
dagger category
In category theory, a branch of mathematics, a dagger category (also called involutive category or category with involution) is a category equipped with a certain structure called ''dagger'' or ''involution''. The name dagger category was coined ...
.
The category has two
functor
In mathematics, specifically category theory, a functor is a Map (mathematics), mapping between Category (mathematics), categories. Functors were first considered in algebraic topology, where algebraic objects (such as the fundamental group) ar ...
s into itself given by the
hom functor
In mathematics, specifically in category theory, hom-sets (i.e. sets of morphisms between objects) give rise to important functors to the category of sets. These functors are called hom-functors and have numerous applications in category theory and ...
: A
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 ...
''R'' ⊆ ''A'' × ''B'' and its transpose ''R''
T ⊆ ''B'' × ''A'' may be composed either as ''R R''
T or as ''R''
T ''R''. The first composition results in a
homogeneous 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 ''A'' and the second is on ''B''. Since the images of these hom functors are in Rel itself, in this case hom is an
internal hom functor
In mathematics, specifically in category theory, hom-sets (i.e. sets of morphisms between objects) give rise to important functors to the category of sets. These functors are called hom-functors and have numerous applications in category theory and ...
. With its internal hom functor, Rel is a
closed category In category theory, a branch of mathematics, a closed category is a special kind of category.
In a locally small category, the ''external hom'' (''x'', ''y'') maps a pair of objects to a set of morphisms. So in the category of sets, this is an obje ...
, and furthermore a
dagger compact category
In category theory, a branch of mathematics, dagger compact categories (or dagger compact closed categories) first appeared in 1989 in the work of Sergio Doplicher and John E. Roberts on the reconstruction of compact topological groups from thei ...
.
The category Rel can be obtained from the category Set as the
Kleisli category In category theory, a Kleisli category is a category (mathematics), category naturally associated to any monad (category theory), monad ''T''. It is equivalent to the category of free Monad (category theory)#Algebras for a monad, ''T''-algebras. The ...
for the
monad
Monad may refer to:
Philosophy
* Monad (philosophy), a term meaning "unit"
**Monism, the concept of "one essence" in the metaphysical and theological theory
** Monad (Gnosticism), the most primal aspect of God in Gnosticism
* ''Great Monad'', an ...
whose functor corresponds to
power set
In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is po ...
, interpreted as a covariant functor.
Perhaps a bit surprising at first sight is the fact that
product
Product may refer to:
Business
* Product (business), an item that serves as a solution to a specific consumer problem.
* Product (project management), a deliverable or set of deliverables that contribute to a business solution
Mathematics
* Produ ...
in Rel is given by the
disjoint union
In mathematics, a disjoint union (or discriminated union) of a family of sets (A_i : i\in I) is a set A, often denoted by \bigsqcup_ A_i, with an injection of each A_i into A, such that the images of these injections form a partition of A (th ...
[ (rather than the ]cartesian product
In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is
: A\ti ...
as it is in Set), and so is the coproduct
In category theory, the coproduct, or categorical sum, is a construction which includes as examples the disjoint union of sets and of topological spaces, the free product of groups, and the direct sum of modules and vector spaces. The coprodu ...
.
Rel is monoidal closed, with both the monoidal product ''A'' ⊗ ''B'' and the internal hom
In mathematics, specifically in category theory, hom-sets (i.e. sets of morphisms between objects) give rise to important functors to the category of sets. These functors are called hom-functors and have numerous applications in category theory and ...
''A'' ⇒ ''B'' given by cartesian product
In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is
: A\ti ...
of sets.
The category Rel was the prototype for the algebraic structure called an allegory
As a literary device or artistic form, an allegory is a narrative or visual representation in which a character, place, or event can be interpreted to represent a hidden meaning with moral or political significance. Authors have used allegory th ...
by Peter J. Freyd and Andre Scedrov in 1990. Starting with a regular category
In category theory, a regular category is a category with finite limits and coequalizers of a pair of morphisms called kernel pairs, satisfying certain ''exactness'' conditions. In that way, regular categories recapture many properties of abelian ...
and a functor ''F'': ''A'' → ''B'', they note properties of the induced functor Rel(''A,B'') → Rel(''FA, FB''). For instance, it preserves composition, conversion, and intersection. Such properties are then used to provide axioms for an allegory.
Relations as objects
David Rydeheard and Rod Burstall
Rodney Martineau "Rod" Burstall FRSE (born 1934) is a British computer scientist and one of four founders of the Laboratory for Foundations of Computer Science at the University of Edinburgh.
Biography
Burstall studied physics at the Universi ...
consider Rel to have objects that are homogeneous relations. For example, ''A'' is a set and ''R'' ⊆ ''A'' × ''A'' is a binary relation on ''A''. The morphisms of this category are functions between sets that preserve a relation: Say ''S'' ⊆ ''B'' × ''B'' is a second relation and ''f'': ''A'' → ''B'' is a function such that then ''f'' is a morphism.
The same idea is advanced by Adamek, Herrlich and Strecker, where they designate the objects (''A, R'') and (''B, S''), set and relation.
Notes
References
*
{{refend
Binary relations
Monoidal categories