Category of relations
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 if (and only if) for some b ∈ B, (a, b) ∈ R and (b, c) ∈ S.
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 was the prototype for the algebraic structure called an allegory by Peter J. Freyd and Andre Scedrov in 1990. 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 which 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.
- Lane, S. Mac (1988). Categories for the working mathematician (1st ed.). New York: Springer-Verlag. p. 26. ISBN 0-387-90035-7.
- 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, 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
- Francis Borceux (1994). Handbook of Categorical Algebra: Volume 2, Categories and Structures. Cambridge University Press. p. 115. ISBN 978-0-521-44179-7.