Re: pushouts in REL

[Dominic Hughes <dominic@theory.stanford.edu>]

Rel doesn't have equalizers (pullbacks, pushouts, or co-equalizers).  It's
rather surprising, and apparently not very well known.

Counter-example.   Let A = { a, b }, write id for the identity A -> A, and
define z : A -> A by adding an edge to id:

    a --- a
        /
       /
      /
    b --- b

Then id and z do not have an equalizer in Rel.

To see why, first note that we can identify any equalizer with a set Q of
non-empty subsets of A, on each of which z and id have the same direct
image [Footnote 1].  The only such candidate subsets are

  { a }

  { a, b }

This leaves us with just 2x2 = 4 possibilities for our equalizer, all of
which fail [Footnote 2].

Interestingly, the related self-dual category Coh of coherence spaces
*does* have equalizers (generalizing co-equalizers/pushouts of partial
functions).  A few years back I conjectured that Coh should have
pullbacks/equalizers, based on thinking about path-based composition in
categories of linkings (Kelly-Mac Lane graphs, proof nets, etc).  Robin
Houston worked out the details of the Coh definition.  See this draft for
the use of pullbacks for linking composition:

  http://arxiv.org/PS_cache/arxiv/pdf/0805/0805.1441v1.pdf

Dominic

Footnote 1.  Let e : Q --> A be an equalizer.  Were the direct image e[q]
of q empty in A, then uniqueness in the universal property would fail.
Were q,r in Q distinct with the same direct image e[q]=e[r] \subseteq A,
then again uniqueness would fail. Thus we can identify an equalizer with a
set of distinct non-empty subsets of A.  For any such subset q, we must
have the direct images z[q] and id[q] equal subsets of A, otherwise we
would not have id e = z e .

Footnote 2.  Let e : Q --> A be our supposed equalizer.

Case 1: Q empty.  Consider the test function f : X --> A where
X = {x} and f is a single edge x---a .  Then for no f' : X --> Q can we
have f = e f' as required (since the e is empty, while f is not).

Case 2: Q = { a,b }.  Consider the same test function as in case 1.  For
no f' : X --> Q can we have f = e f' (since f hits a but not b, while e f'
hits neither (if f' is empty) or both (if f' has an edge)).

Case 3: Q = { a }.  Consider the test function g : X --> A where
X = {x} and g has two edges x---a and x---b .  For no g' : X --> Q can we
have g = e g' (since g hits both a and b, while e hits only a).

Case 4: Q contains { a,b } and { a }.  Consider the same test function as
in case 3.  Since g hits both a and b, we must have an edge in g' from x
to { a,b }.  Then an edge in g' from x to { a } is optional, while still
having g = e g', so uniqueness fails in the universal property.



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.
>


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