Re: pushouts in REL

Re: pushouts in REL

[Prof. Peter Johnstone]

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/ ]

Re: pushouts in REL

[Vaughan Pratt]

Peter Freyd gave a talk at a small conference circa 1990 (at CSLI
perhaps?) where he drew attention to the lack of (co)equalizers in Rel
as a warm-up (I forget how) to an eloquent tribute to the benefits of
toposes for intuitionistic logic.

Oddly there didn't seem to be anything about this in Cats and
Alligators.  However 1.429 therein makes the point that "if a category
has enough equalizers then all idempotents split."  So a witness to
missing equalizers is any nonsplitting idempotent, for example Dominic's
z below.

Vaughan Pratt

Dominic Hughes wrote:
> 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.


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

Re: pushouts in REL

[Chris Heunen]

Dear all,

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

I already answered Sergei privately, but this should be corrected
publicly: Rel does not have equalisers. In fact, it has almost no
equalisers.

For a counterexample, consider the sets A = {0,1} and B = {0}, and the
parallel relations R = A x B and S = {(0,0)}. Their equaliser, if it
existed, must be contained in T = {(0,0)}. But T' = {0} x A also
satisfies RT'=ST', but does not factor through any subrelation of T.

Best wishes,
Chris Heunen


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

Re: pushouts in REL

[Dusko Pavlovic]

On Aug 20, 2009, at 2:38 PM, 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.

i must be missing something.

what if A = {0,1}, B = {#}, R = {<0,#>} and S = {<1,#>}?

then A_0 = empty. (you don't say how to quantify over b; but since
there is just one b here, it doesn't matter)

on the other hand take the relation E \inc BxA where E = {<#,0>,<#,1>}

now E;R = E;S = id_B

but E does not factor through A_0.

what am i missing?

-- dusko



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

Re: pushouts in REL

[Dominic Hughes]

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/ ]

Re: pushouts in REL

[Jamie Vicary]

Rel does not have all finite equalizers. I believe the smallest
example is the parallel pair (1 1 0 0) and (0 0 1 1), seen as
relations from the 4-element set to the 1-element set.

Cheers,
Jamie.

2009/8/20 Michael Barr <barr@math.mcgill.ca>:
> 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/ ]

Re: pushouts in REL

[Michael Barr]

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/ ]

pushouts in REL

[soloviev]

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


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