category of relations
{{Short description|Category whose objects are sets and whose morphisms are binary relation}}
{{multiple image
| align = right
| direction = horizontal
| caption_align = center
| width = 200
| header =
| header_align = center
| header_background =
| footer =
| footer_align =
| footer_background =
| background color =
|image1=Relations category.svg
|width1= 200
|caption1=Category of Relations Rel.
|alt1=Rel
|image2=Relations category op.svg
|width2= 200
|caption2=Rel
|alt2=Relop
}}
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 {{nowrap| 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.{{cite book|authorlink = Saunders Mac Lane|last1=Mac Lane|first1=S. |title=Categories for the Working Mathematician|date=1988|publisher=Springer|isbn=0-387-90035-7|page=26|edition=1st}}
Rel has also been called the "category of correspondences of sets".{{Cite book| last=Pareigis| first=Bodo| title=Categories and Functors| year=1970 |page=6| isbn=978-0-12-545150-5| publisher=Academic Press| series=Pure and Applied Mathematics| volume=39}}
Properties
The category Rel has the category of sets Set as a (wide) subcategory, where the arrow {{nowrap| f : X → Y}} in Set corresponds to the relation {{nowrap| F ⊆ X × Y}} defined by {{nowrap|1= (x, y) ∈ F ⇔ f(x) = y}}.This category is called SetRel by Rydeheard and Burstall.{{cite book |first=George |last=Bergman |chapter=§7.2 RelSet |title=An Invitation to General Algebra and Universal Constructions |publisher=Henry Helson |date=1998 |isbn=0-9655211-4-1 |pages= |url=http://math.berkeley.edu/~gbergman/245/index.html}}
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.{{cite book |last1=Barr |first1=Michael |url=https://math.mcgill.ca/triples/Barr-Wells-ctcs.pdf |title=Category Theory for Computing Science |last2=Wells |first2=Charles |date=1990 |publisher=Prentice Hall |isbn=978-0131204867 |location= |pages=181 |author1-link=Michael Barr (mathematician) |author2-link=Charles Wells (mathematician)}}
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 RT ⊆ B × A may be composed either as R RT or as RT 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{{rp|181}} (rather than the cartesian product as it is in Set), and so is the coproduct.
Rel is monoidal closed, if one defines both the monoidal product A ⊗ B and the internal hom A ⇒ B by the cartesian product of sets. It is also a monoidal category if one defines the monoidal product by the disjoint union of sets.{{cite arXiv |eprint=1908.02633 |last1=Fong |first1=Brendan |author2=David I Spivak |title=Supplying bells and whistles in symmetric monoidal categories |year=2019 |class=math.CT }}
The category Rel was the prototype for the algebraic structure called an allegory by Peter J. Freyd and Andre Scedrov in 1990.{{cite book |first1=Peter J. |last1=Freyd |author1-link=Peter J. Freyd |first2=Andre |last2=Scedrov |title=Categories, Allegories |publisher=North Holland |date=1990 |isbn=0-444-70368-3 |pages=79, 196 |url=}} 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 then f is a morphism.{{cite book |first1=David |last1=Rydeheard |first2=Rod |last2=Burstall |author2-link=Rod Burstall |title=Computational Category Theory |publisher=Prentice-Hall |date=1988 |isbn=978-0131627369 |pages=41 |url=}}
The same idea is advanced by Adamek, Herrlich and Strecker, where they designate the objects (A, R) and (B, S), set and relation.{{cite book |first1=Juri |last1=Adamek |first2=Horst |last2=Herrlich |first3=George E. |last3=Strecker |chapter=§3.3, example 2(d) |title=Abstract and Concrete Categories |publisher=KatMAT Research group, University of Bremen |location= |date=2004 |orig-year=1990 |isbn= |pages=22 |url=http://katmat.math.uni-bremen.de/acc/acc.pdf |archive-url=https://web.archive.org/web/20220811222404/http://katmat.math.uni-bremen.de/acc/acc.pdf |archive-date=2022-08-11 }}
Notes
{{Reflist|group=note}}
References
{{Reflist}}
{{refbegin}}
- {{cite book |first=Francis |last=Borceux |series=Handbook of Categorical Algebra |volume=2 |title=Categories and Structures|url=https://books.google.com/books?id=5i2v9q0m5XAC&pg=PA115|year=1994|publisher=Cambridge University Press|isbn=978-0-521-44179-7|page=115}}
{{refend}}