In mathematics, the category **Rel** has the class of sets as objects and binary relations as morphisms.

A morphism (or arrow) *R* : *A* → *B* in this category is a relation between the sets *A* and *B*, so *R* ⊆ *A* × *B*.

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*.^{[1]}

**Rel** has also been called the "category of correspondences of sets".^{[2]}

Properties

The category **Rel** has the category of sets **Set** as a (wide) subcategory, where the arrow *f* : *X* → *Y* in **Set** corresponds to the relation *F* ⊆ *X* × *Y* defined by (*x*, *y*) ∈ *F* ⇔ *f*(*x*) = *y*.^{[3]}^{[4]}

A morphism in **Rel** is a relation, and the corresponding morphism in the opposite category to **Rel** has arrows reversed, so it is the converse relation. Thus **Rel** contains its opposite and is self-dual.^{[5]}

The involution represented by taking the converse relation provides the **dagger** to make **Rel** a dagger category.

The category has two functors into itself given by the hom functor: A binary relation *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 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.

The category **Rel** can be obtained from the category **Set** as the Kleisli category for the monad whose functor corresponds to power set, 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^{[5]}^{:181} (rather than the cartesian product as it is in **Set**), and so is the coproduct.

**Rel** is monoidal closed, with both the monoidal product *A* ⊗ *B* and the internal hom *A* ⇒ *B* given by cartesian product of sets.

The category **Rel** was the prototype for the algebraic structure called an allegory by Peter J. Freyd and Andre Scedrov in 1990.^{[6]} Starting with a regular category 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 \( {\displaystyle xRy\implies f(x)Sf(y),} \) then f is a morphism.[7]

The same idea is advanced by Adamek, Herrlich and Strecker, where they designate the objects (A, R) and (B, S), set and relation.[8]

References

Mac Lane, S. (1988). Categories for the Working Mathematician (1st ed.). New York: Springer-Verlag. p. 26. ISBN 0-387-90035-7.

Pareigis, Bodo (1970). Categories and Functors. Pure and Applied Mathematics. 39. Academic Press. p. 6. ISBN 978-0-12-545150-5.

This category is called SetRel by Rydeheard and Burstall.

George Bergman (1998), An Invitation to General Algebra and Universal Constructions, §7.2 RelSet, Henry Helson Publisher, Berkeley. ISBN 0-9655211-4-1.

Michael Barr & Charles Wells (1998) Category Theory for Computer Scientists Archived 2016-03-04 at the Wayback Machine, page 83, from McGill University

Peter J. Freyd & Andre Scedrov (1990) Categories, Allegories, pages 79, 196, North Holland ISBN 0-444-70368-3

David Rydeheard & Rod Burstall (1988) Computational Category Theory, page 54, Prentice-Hall ISBN 978-0131627369

Juri Adamek, Horst Herrlich, and George E. Strecker (2004) [1990] Abstract and Concrete Categories, section 3.3, example 2(d) page 22, from Research group KatMAT at University of Bremen

Francis Borceux (1994). Handbook of Categorical Algebra: Volume 2, Categories and Structures. Cambridge University Press. p. 115. ISBN 978-0-521-44179-7.

^{}

Undergraduate Texts in Mathematics

Graduate Studies in Mathematics

Hellenica World - Scientific Library

Retrieved from "http://en.wikipedia.org/"

All text is available under the terms of the GNU Free Documentation License