Re: pushouts in REL

["Prof. Peter Johnstone" <P.T.Johnstone@dpmms.cam.ac.uk>]

On Thu, 20 Aug 2009, Michael Barr wrote:

> On Thu, 20 Aug 2009, soloviev@irit.fr wrote:
>
>> To the list:
>>
>> I am actually travelling (in Russia) and I need more or
>> less  urgently a reference concerning pullbacks and pushouts
>> in the category of sets and relations - do they always exist
>> etc - I would not adress it to the list if it would be
>> not urgent and I would not have some difficulty with
>> search from here -
>>
>> Best to all -
>>
>> Sergei Soloviev
>>
>
> You should check this, but it seems right.  Rel is self dual and each
> object is too.  So limits are colimits (of the dual diagram).  Rel has
> arbitrary sums and products--they are disjoint unions.  The empty set is
> initial and terminal.  So to have pullbacks you need equalizers.  So let A
> and B be sets and R,S \inc A x B.  Let A_0 be the subset of A consisting
> of all a such that (a,b) \in R iff (a,b) \in S.  Then it seems to me that
> the inclusion function of A_0 into A is the equalizer of R and S.
>
>
Sadly, that doesn't work. Let A = {0,1}, B = {0,1}, and let R and S be
respectively the identity relation and the relation which relates each
member of A to both members of B. Then Michael's proposed equalizer is
empty, but the relation from C = {0} to A which relates 0 to both members
of A has equal composites with R and S. (The pair (R,S) does have an
equalizer in Rel, namely the relation C -+-> A just described, but with
a little more ingenuity you can find parallel pairs in Rel having no
equalizer.)

Peter Johnstone



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