# Category of relations

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

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

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^{[4]}^{: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.^{[5]} 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 [math]\displaystyle{ xRy \implies f(x)Sf(y), }[/math] then *f* is a morphism.^{[6]}

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

## Notes

- ↑ This category is called
**Set**_{Rel}by Rydeheard and Burstall.

## References

- ↑ Mac Lane, S. (1988).
*Categories for the Working Mathematician*(1st ed.). Springer. 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. - ↑ Bergman, George (1998). "§7.2 RelSet".
*An Invitation to General Algebra and Universal Constructions*. Henry Helson. ISBN 0-9655211-4-1. http://math.berkeley.edu/~gbergman/245/index.html. - ↑
^{4.0}^{4.1}Barr, Michael; Wells, Charles (1990).*Category Theory for Computing Science*. Prentice Hall. pp. 181. ISBN 978-0131204867. https://math.mcgill.ca/triples/Barr-Wells-ctcs.pdf. - ↑ Freyd, Peter J.; Scedrov, Andre (1990).
*Categories, Allegories*. North Holland. pp. 79, 196. ISBN 0-444-70368-3. - ↑ Rydeheard, David; Burstall, Rod (1988).
*Computational Category Theory*. Prentice-Hall. pp. 41. ISBN 978-0131627369. - ↑ Adamek, Juri; Herrlich, Horst; Strecker, George E. (2004). "§3.3, example 2(d)".
*Abstract and Concrete Categories*. KatMAT Research group, University of Bremen. pp. 22. http://katmat.math.uni-bremen.de/acc/acc.pdf.

- Borceux, Francis (1994).
*Categories and Structures*. Handbook of Categorical Algebra.**2**.*Cambridge University Press*. p. 115. ISBN 978-0-521-44179-7. https://books.google.com/books?id=5i2v9q0m5XAC&pg=PA115.

Original source: https://en.wikipedia.org/wiki/Category of relations.
Read more |