Limits in REL

Limits in REL

[Ondrej Rypacek]

Hi all

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

And what about SPAN(C) or REL(C), spans and relations over a suitable
category  C ?

Thanks a lot in advance,
Ondrej


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

Re: Limits in REL

[Uday S Reddy]

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

Re: Limits in REL

[Marco Grandis]

There was a similar question "Limits and colimits in Rel?" by  UweWolter, on 24 Feb 2014, which had various replies.
I copy my own (with an addition in [[...]]).
Regards   MG

----COPY----

As Peter J. is saying, categories of relations have poor (co)limits. [[ Eg no equalisers nor coequalisers.]]
For abelian groups, Rel(Ab) does not even have products (sums).

However, if you insert the 2-category Rel  into the double category RRel of sets, mappings and relations [GP1]
you have a double category with all double limits and colimits.
For instance: the obvious cartesian product  a x b: XxY --> X' x Y'  (resp. sum  a + b: X+Y --> X' + Y')  of two relations a, b
is indeed a product (resp. a sum) in the double category.
See [GP1] for definitions and discussion of these aspects.

Similarly, many bicategories of spans, cospans, relations, profunctors... have poor (co)limits, but can be usefully embedded in
weak double categories (with the same objects, "strict morphisms", "same morphisms", suitable double cells) that have all limits
and colimits.

Also adjoints work well in the extended settings: see [GP2].

Best regards

Marco

[GP1] M. Grandis - R. Paré, Limits in double categories, Cah. Topol. Géom. Différ. Catég. 40 (1999), 162-220.
[GP2] M. Grandis - R. Paré, Adjoint for double categories,  Cah. Topol. Géom. Différ. Catég. 45 (2004), 193-240.
   both downloadable at:   http://ehres.pagesperso-orange.fr/Cahiers/Ctgdc.htm



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

Re: Limits in REL

[Pino Rosolini]

Since I failed to add a comment to the previous posting about limits in REL, I
take the opportunity to recall a nice remark of Aurelio Carboni:
"REL has finite products and _weak_ equalizers. So you can take its exact
completion. This happens to be the category of complete sup-lattices and
sup-preserving maps. And the tensor product on REL extends to the exact
completion."

You can find more details in
Anna Bucalo, G.R., Completions, comonoids, and topological spaces
Annals of Pure and Applied Logic 137 (2006) 104?125

--Pino


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

Re: Limits in REL

[Pawel Sobocinski]

Dear Ondrej,

Since many people have already replied to you about Rel, let me add
something about colimits in Span(C). Note that since Span(C) is a
bicategory, the "morally correct" notion is bicolimits.

With Tobias Heindel we showed that any colimit diagram in C that satisfies
something called a Van Kampen property is mapped to a bicolimit diagram
through the canonical embedding C -> Span(C). So the Van Kampen property is
really a characterisation of when a colimit satisfies the universal
property of being a (bi)colimit in the wild world of Span(C).

Some examples of Van Kampen properties for particular colimits: a Van
Kampen initial object is a strict initial object, a Van Kampen coproduct is
a coproduct that has the properties of coproducts in extensive categories,
a Van Kampen pushout is a pushout that has the properties of pushouts
(along monos) in adhesive categories.

You will find the details and more examples in:

Tobias Heindel, Pawel Sobocinski: Being Van Kampen is a universal property.
Logical Methods in Computer Science 7(1) (2011)

All the best,
Pawel.


On 3 July 2014 11:57, Ondrej Rypacek <ondrej.rypacek@gmail.com> wrote:

> Hi all
>
> What is known about limits in REL , the (bi)category of sets and relations?
> I know there are biproducts; are there equalisers?
>
> And what about SPAN(C) or REL(C), spans and relations over a suitable
> category  C ?
>
> Thanks a lot in advance,
> Ondrej
>

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

Re: Limits in REL

[Ondrej Rypacek]

Dear all,
as promised this and the previous similar thread has now been compiled
at http://ncatlab.org/nlab/show/Rel.
Please feel free to review and amend as you seem fit.

Thank you all for your answers!
Ondrej

On 7 July 2014 11:03, Ondrej Rypacek <ondrej.rypacek@gmail.com> wrote:
> Thank you everyone for your time in answering my question. It has been
> most helpful!
>
> Following Bas Spitters's suggestion, and because this was the second
> time someone asked exactly the same question in a short period of
> time, I'm going to compile a digest for
> http://ncatlab.org/nlab/show/Rel soon.
>
> Thanks,
> Ondrej
>
>
>>
>> On 3 July 2014 11:57, Ondrej Rypacek <ondrej.rypacek@gmail.com> wrote:
>>
>>> Hi all
>>>
>>> What is known about limits in REL , the (bi)category of sets and relations?
>>> I know there are biproducts; are there equalisers?
>>>
>>> And what about SPAN(C) or REL(C), spans and relations over a suitable
>>> category  C ?
>>>
>>> Thanks a lot in advance,
>>> Ondrej
>>>

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

Re: Limits in REL

[Ondrej Rypacek]

Thank you everyone for your time in answering my question. It has been
most helpful!

Following Bas Spitters's suggestion, and because this was the second
time someone asked exactly the same question in a short period of
time, I'm going to compile a digest for
http://ncatlab.org/nlab/show/Rel soon.

Thanks,
Ondrej


>
> On 3 July 2014 11:57, Ondrej Rypacek <ondrej.rypacek@gmail.com> wrote:
>
>> Hi all
>>
>> What is known about limits in REL , the (bi)category of sets and relations?
>> I know there are biproducts; are there equalisers?
>>
>> And what about SPAN(C) or REL(C), spans and relations over a suitable
>> category  C ?
>>
>> Thanks a lot in advance,
>> Ondrej
>>

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

Re: Limits in REL

[René Guitart]

It is known that REL (also denoted as COR) has biproducts, even products which are also sums for small infinite indexation.
We can give examples that  some kernel, some cokernel, some image or some coimage do not exist
(see :  Davar-Panah, Thèse de 3ème cycle, Paris, 1968 ;   Guitart, Thèse de 3ème cycle, Paris, 1970).
For the lack of splitting idempotents :  
the completion of REL with respect to splitting idempotents is  the category of complete completely  distributive lattices, with sup compatible maps (R. Guitart and J. Riguet, Enveloppe karoubienne de catégories de Kleisli, CTGDC, XXXIII-3 (1992), p. 261-266). 
The case of {0,1} it is clear because a preorder is splittable if and only if it is an equivalence relation (Prop. 5 in Guitart-Riguet). It is   also  indicated exactly when an idempotents split in REL. 
In fact the construction in Guitart-Riguet works for any Kleisli category i.e. category of free algebras, and if the monad (T, u,m) on C is with T an injective map, then the completion of Kl(T) is the full subcategory of EM(T) with objects U_T-projective algebras.  So  idempotents split in Kl(T) if and only if every projective algebra is free.
This analysis works also for the description of the splitting of idempotent of the category of continuous relations between compact spaces: cf. my talk at the PSSL 51, Valenciennes, 13-14 février 1993 (An unpublished paper available on my page, in the section preprint).
Best regards,
René Guitart

Le 4 juil. 2014 à 09:45, Peter Johnstone a écrit :

> REL has very few limits other than biproducts: it doesn't even have
> splittings for all idempotents (so no equalizers or coequalizers).
> The simplest non-splittable idempotent is the usual order relation
> on {0,1}, and the same example works in REL(C) for any regular C
> where the disjoint coproduct 1+1 exists.
> 
> Peter Johnstone
> 
> On Thu, 3 Jul 2014, Ondrej Rypacek wrote:
> 
>> Hi all
>> 
>> What is known about limits in REL , the (bi)category of sets and relations?
>> I know there are biproducts; are there equalisers?
>> 
>> And what about SPAN(C) or REL(C), spans and relations over a suitable
>> category  C ?
>> 
>> Thanks a lot in advance,
>> Ondrej
> 



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

Re: Limits in REL

[Peter Johnstone]

REL has very few limits other than biproducts: it doesn't even have
splittings for all idempotents (so no equalizers or coequalizers).
The simplest non-splittable idempotent is the usual order relation
on {0,1}, and the same example works in REL(C) for any regular C
where the disjoint coproduct 1+1 exists.

Peter Johnstone

On Thu, 3 Jul 2014, Ondrej Rypacek wrote:

> Hi all
>
> What is known about limits in REL , the (bi)category of sets and relations?
> I know there are biproducts; are there equalisers?
>
> And what about SPAN(C) or REL(C), spans and relations over a suitable
> category  C ?
>
> Thanks a lot in advance,
> Ondrej


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