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/ ]
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/ ]
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/ ]
[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/ ]
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/ ]
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/ ]
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/ ]
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/ ]
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/ ]
participants (7)
-
Marco Grandis -
Ondrej Rypacek -
Pawel Sobocinski -
Peter Johnstone -
Pino Rosolini -
René Guitart -
Uday S Reddy