Inmathematics, thecategoryRel has the class ofsets asobjects andbinary relations asmorphisms.
A morphism (or arrow)R :A →B in this category is a relation between the setsA andB, soR ⊆A ×B.
Thecomposition of two relationsR:A →B andS:B →C is given by
Rel has also been called the "category of correspondences of sets".[2]
The categoryRel has thecategory of setsSet as a (wide)subcategory, where the arrowf :X →Y inSet corresponds to the relationF ⊆X ×Y defined by(x,y) ∈F ⇔f(x) =y.[note 1][3]
A morphism inRel is a relation, and the corresponding morphism in theopposite category toRel has arrows reversed, so it is theconverse relation. ThusRel contains its opposite and isself-dual.[4]
Theinvolution represented by taking the converse relation provides thedagger to makeRel adagger category.
The category has twofunctors into itself given by thehom functor: Abinary relationR ⊆A ×B and its transposeRT ⊆B ×A may be composed either asR RT or asRTR. The first composition results in ahomogeneous relation onA and the second is onB. Since the images of these hom functors are inRel itself, in this case hom is aninternal hom functor. With its internal hom functor,Rel is aclosed category, and furthermore adagger compact category.
The categoryRel can be obtained from the categorySet as theKleisli category for themonad whose functor corresponds topower set, interpreted as a covariant functor.
Perhaps a bit surprising at first sight is the fact thatproduct inRel is given by thedisjoint union[4]: 181 (rather than thecartesian product as it is inSet), and so is thecoproduct.
Rel ismonoidal closed, if one defines both the monoidal productA ⊗B and theinternal homA ⇒B by thecartesian product of sets. It is also amonoidal category if one defines the monoidal product by the disjoint union of sets.[5]
The categoryRel was the prototype for the algebraic structure called anallegory byPeter J. Freyd and Andre Scedrov in 1990.[6] Starting with aregular category and a functorF: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.
David Rydeheard andRod Burstall considerRel to have objects that are homogeneous relations. For example,A is a set andR ⊆A ×A is a binary relation onA. The morphisms of this category are functions between sets that preserve a relation: SayS ⊆B ×B is a second relation andf:A →B is a function such that thenf 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]