mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

, the

category Category, plural categories, may refer to: General uses *Classification, the general act of allocating things to classes/categories Philosophy * Category of being * ''Categories'' (Aristotle) * Category (Kant) * Categories (Peirce) * Category ( ...

Rel has the class of sets as objects and

binary relation In mathematics, a binary relation associates some elements of one Set (mathematics), set called the ''domain'' with some elements of another set called the ''codomain''. Precisely, a binary relation over sets X and Y is a set of ordered pairs ...

s as

morphisms In mathematics, a morphism is a concept of category theory that generalizes structure-preserving maps such as homomorphism between algebraic structures, functions from a set to another set, and continuous functions between topological spaces. Al ...

. 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 by Set, is the category whose objects are sets. The arrows or morphisms between sets ''A'' and ''B'' are the functions from ''A'' to ''B'', and the composition of mor ...

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. Intuitively, ...

, where the arrow in Set corresponds to the relation defined by .This category is called Set_Rel 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^ of a given Category (mathematics), category C is formed by reversing the morphisms, i.e. interchanging the source and target of each morphism. Doing the reversal ...

to Rel has arrows reversed, so it is the

converse relation In mathematics, the converse 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'. In formal terms ...

. Thus Rel contains its opposite and is self-dual. The

involution Involution may refer to: Mathematics * Involution (mathematics), a function that is its own inverse * Involution algebra, a *-algebra: a type of algebraic structure * Involute, a construction in the differential geometry of curves * Exponentiati ...

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

. 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 object (category theory), objects) give rise to important functors to the category of sets. These functors are called hom-functors and have numerous applicati ...

: A

''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) on a set ''X'' is a binary relation between ''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. With its internal hom functor, Rel is a closed category, 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 for the monad 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 in Rel is given by the

disjoint union In mathematics, the disjoint union (or discriminated union) A \sqcup B of the sets and is the set formed from the elements of and labelled (indexed) with the name of the set from which they come. So, an element belonging to both and appe ...

(rather than the

cartesian product In mathematics, specifically set theory, the Cartesian product of two sets and , denoted , is the set of all ordered pairs where is an element of and is an element of . In terms of set-builder notation, that is A\times B = \. A table c ...

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

. Rel is monoidal closed, if one defines both the monoidal product ''A'' ⊗ ''B'' and the internal hom ''A'' ⇒ ''B'' by the

of sets. It is also a

monoidal category In mathematics, a monoidal category (or tensor category) is a category (mathematics), category \mathbf C equipped with a bifunctor :\otimes : \mathbf \times \mathbf \to \mathbf that is associative up to a natural isomorphism, and an Object (cate ...

if one defines the monoidal product by the disjoint union of sets. The category Rel was the prototype for the algebraic structure called an

allegory As a List of narrative techniques, literary device or artistic form, an allegory is a wikt:narrative, narrative or visual representation in which a character, place, or event can be interpreted to represent a meaning with moral or political signi ...

by Peter J. Freyd and Andre Scedrov in 1990. Starting with a

regular category In category theory, a regular category is a category with limit (category theory), finite limits and coequalizers of all pairs of morphisms called kernel pairs, satisfying certain ''exactness'' conditions. In that way, regular categories recapture ...

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

xRy \implies f(x)Sf(y),

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 Categories in category theory Binary relations Monoidal categories