Re: Limits in REL

[Uday S Reddy <u.s.reddy@cs.bham.ac.uk>]

[Note from moderator: Apologies for forgetting how recently this was 
asked and extensivly answered. Some short responses are not being posted.]

Ondrej Rypacek writes:

> Hi all
>
> What is known about limits in REL , the (bi)category of sets and relations?
> I know there are biproducts; are there equalisers?

Professor Johnstone answered this question a few months ago as below.  Since
REL is the category of *free algebras* for the powerset monad, there is very
little chance of a limit of such algebras being free again.  To get decent
limits, you need to move to the Eilenberg-Moore category of the powerset
monad, viz., the category of complete semilattices.

     Rel does have products and coproducts; they coincide (by self-duality)
     and are just disjoint unions of sets. If's not hard to see that
     a relation R \subseteq A \times B is a monomorphism A \to B iff the
     map PA \to PB sending a subset of A to the set of all R-relatives
     of its members is injective; dually for epimorphisms. Rel has very few
     (co)limits other than (co)products; it doesn't even have splittings of
     all idempotents. (All symmetric idempotents have splittings, but the
     order-relation \leq \subseteq {0,1} \times {0,1} can't be split.)

     However, I don't think that the self-duality is in any sense responsible
     for the lack of (co)limits in Rel. The category of complete
     join-semilattices is self-dual, and is complete and cocomplete.

Cheers,
Uday


[For admin and other information see: http://www.mta.ca/~cat-dist/ ]