Lecture
In mathematics, the category Rel comprises 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 defined as follows:
Rel is also called the «category of correspondences of sets». [ 2 ]
The category Rel has the category of sets Set as a (wide) subcategory , where an arrow f : X → Y in Set corresponds to the relation F ⊆ X × Y, defined as ( x , y ) ∈ F ⇔ f ( x ) = y .
A morphism in Rel — is a relation, and the corresponding morphism in the opposite category to Rel has arrows pointing in the reverse direction, so it is the inverse relation . Thus, Rel contains its own opposite and is self-dual . [ 4 ]
The involution given by taking the inverse relation yields a dagger , allowing Rel to be made a dagger category .
The category has two functors into itself, given by the hom functor : a binary relation R ⊆ A × B and its transpose relation R T ⊆ B × A can be composed either as RR T or as R T R. The first composition gives a homogeneous relation on A , and the second — on B. Since the images of these hom functors lie in the category Rel itself, in this case hom is an internal hom functor . By means of its internal hom functor the category Rel is a closed category , as well as a compact «dagger»-type category .
The category Rel can be obtained from the category Set as the Kleisli category for the monad whose functor corresponds to the power set , interpreted as a covariant functor.
Perhaps somewhat surprisingly at first glance, the product in Rel is given by the disjoint union [ 4 ] : 181 (rather than the Cartesian product, as in Set ), and the same applies to the coproduct .
The category Rel is monoidally closed if one defines both the monoidal product A ⊗ B and the internal hom A ⇒ B by means of the Cartesian product of sets. It is also a monoidal category if one defines the monoidal product by means of the disjoint union of sets. [ 5 ]
The category Rel served as the prototype for an algebraic structure named an allegory by Peter J. Freyd and Andre Scedrov in 1990. [ 6 ] Starting from a regular category and a functor F : A → B , they note the properties of the induced functor Rel( A,B ) → Rel( FA, FB ). For example, it preserves composition, conversion and intersection. Such properties are then used to provide axioms for an allegory.
David Rydeheard and Rod Burstall consider that the category Rel has objects that are homogeneous relations. For example, A — is a set, and R ⊆ A × A — a binary relation on A. The morphisms of this category are functions between sets that preserve the relation: suppose S ⊆ B × B — is a second relation, and f : A → B — a function such that
then f is a morphism. [ 7 ]
The same idea is put forward by Adámek, Herrlich and Strecker, who denote the objects ( A, R ) and ( B, S ) as a set and as a relation. [ 8 ]
Comments