left and right euclidean;
Roughly, is the category whose objects are sets and whose morphisms are (binary) relations between sets. It becomes a 2-category (in fact, a 2-poset) by taking 2-morphisms to be inclusions of relations.
is a 2-poset (a category enriched in the category of posets), whose objects or -cells are sets, whose morphisms or -cells are relations , and whose 2-morphisms or -cells are inclusions of relations. The composite of morphisms and is defined by the usual relational composite
and the identity is the equality relation, in other words the usual diagonal embedding
Another important operation on relations is taking the opposite: any relation induces a relation
and this operation obeys a number of obvious identities, such as and .
and there is an obvious category whose objects are spans from to and whose morphisms are morphisms between such diagrams. The terminal span from to is
and a relation from to is just a subobject of the terminal span, in other words an isomorphism class of monos into the terminal span.
To each span from to , there is a corresponding relation from to , defined by taking the image of the unique morphism of spans between and . It may be checked that this yields a lax morphism of bicategories
More generally, given any regular category , one can form a 2-category of relations in similar fashion. The objects of are objects of , the morphisms in are defined to be subobjects of the terminal span from to , and 2-cells are subobject inclusions. To form the composite of and , one takes the image of the unique span morphism
in the category of spans from to , thus giving a mono into the terminal span from to . The subobject class of this mono defines the relation
and the axioms of a regular category ensure that is a 2-category with desirable properties. Similar to what was said above, there is again a lax morphism of bicategories
There is also a functor
that takes a morphism to the functional relation defined by , i.e., the relation defined by the subobject class of the mono
Such functional relations may also be characterized as precisely those 1-cells in which are left adjoints; the right adjoint of is the opposite relation . The unit amounts to a condition
which says that the functional relation is total, and the counit amounts to a condition
which says the functional relation is well-defined.
does have products and coproducts; they coincide (by self-duality) and are just disjoint unions of sets. However, otherwise has very few (co)limits; it doesn’t even have splittings of all idempotents. All symmetric idempotents have splittings, but the order-relation can’t be split. It follows that it can’t have (co)equalisers.
However, has weak equalizers, therefore one can take its exact completion. This happens to be the category of complete sup-lattices and sup-preserving maps. And the tensor product on extends to the exact completion.
Since is the category of free algebras (Kleisli category) for the powerset monad, there is, indeed, very little chance of a limit of such algebras being free again. To get decent limits, one has to move to the Eilenberg-Moore category of the powerset monad, viz., the category of complete suplattices.
If you insert the category into the double category of sets, mappings and relations, one has a double category with all double limits? and colimits. For instance, the obvious cartesian product (resp. sum ) of two relations is indeed a product (resp. a sum) in the double category.
Similarly, many bicategories of spans, cospans, relations, profunctors, etc. have poor (co)limits, but can be usefully embedded in weak double categories (with the same objects, “strict morphisms”, “same morphisms”, suitable double cells) that have all limits and colimits.
is remarkable. This was probably first noticed by Dana May Latch, in the 20th century, for the category of of complete suplattices.
The matrix algebra for maps to products, from coproducts, and most especially, from coproducts to products, works just as it does in the case of additive categories, when it comes to these -categories.
See van Kampen colimit.
For generalizations of see