Re: Limits and colimits in Rel?

["Fred Linton" <flinton@wesleyan.edu>]

On Mon, 24 Feb 2014 23:36:55 +0100, Uwe.Wolter@ii.uib.no asked,
among other things:

> 2. Is it true that there are, in general, no products and equalizer
> (sums and coequalizer) in Rel?

I don't know about (co-)equalizers, but (co-)products, unless my
Alzheimer's is very advanced, should be available ... if by category
"Rel of binary relations" you mean with sets as objects, binary
relations as morphisms, and usual composition of relations as
composition rule (so usual identity functions as identity maps).

Indeed, let A be a family (i /in I) of sets A_i. Write C for the usual
set-theoretic disjoint union of the sets A_i -- C = /join_i A_i.

a) For each i /in I, write p_i: C --> A_i for the partial function
which "is" the identity function on the summand A_i. It seems to me
that the relations p_i serve as projections making C the product
of the various A_i of the family A.

b) Again, for each i /in I, write s_i :A_i --> C for the function which
"is" the identity function on A_i. It seems to me that the relations
s_i serve as injections making C the coproduct of the various A_i of
the family A.

c) In fact, much as is the case with additive categories, the compositions
of these injections and projections satisfy

p_i s_k = /empty (i /ne k),
p_i s_i = id_(A_i),
s_i p_i = the partial function on C which is identity on summand A_i, and
/join(s_i p_i) = id_C.

Of course, Wolters' own observation, in 4 (below), serves as link
between a) and b); and c) is, as it were, the observation that
"coproduct and product both serve as biproduct":

> 4. ... the fact that the
> formation of converse relations establishes an isomorphism between Rel
> and its opposite ...

Indeed, p_i and s_i are mutually converse.

Do let me know, please, if I've just been talking through my hat --
that'll be a sign it's time for me to retire for real :-) .

Cheers, -- Fred
> Any reply or reference is well-come.
>
> Best regards
>
> Uwe Wolter
>




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