Dear all, I remember that there was some time ago a discussion on this list about limits and colimits in the category Rel of binary relations. Unfortunately, I can not remember or trace the final answer. But, if I remember right there are, besides initial and terminal objects, in general no limits or colimits in Rel. So my questions are: 1. Is there a characterization of monomorphisms and epimorphisms in Rel? 2. Is it true that there are, in general, no products and equalizer (sums and coequalizer) in Rel? 3. Are there some general results about what limits/colimits exist or don't exist? 4. Is the presumable non-existence related to the fact that the formation of converse relations establishes an isomorphism between Rel and its opposite Rel^op? Any reply or reference is well-come. Best regards Uwe Wolter [For admin and other information see: http://www.mta.ca/~cat-dist/ ]
Dear Uwe, Of course, Rel is self-dual, as you already remarked. Consider a relation R from A to B, i.e., a subset of A x B. Define the image-function img(R) from the powerset P(A) to the powerset P(B) by mapping a subset U of A to the union of all subsets of B of the form aR with a in U (where aR consists of all elements in B R-related to a). Then R is a monomorphism in Rel iff img(R) is injective, which in particular implies that R is total. Dually, R is an epimorphism in Rel iff img(R^op) is injective, in particular R^op then is total. Moreover, disjoint unions serve as both coproducts and products in Rel, but (co)equalizers in general fail to exist. Best regards, -- Jürgen Koslowski [For admin and other information see: http://www.mta.ca/~cat-dist/ ]
On Mon, 24 Feb 2014 23:36:55 +0100, Uwe.Wolter@ii.uib.no asked, among other things:
2. Is it true that there are, in general, no products and equalizer (sums and coequalizer) in Rel?
I don't know about (co-)equalizers, but (co-)products, unless my Alzheimer's is very advanced, should be available ... if by category "Rel of binary relations" you mean with sets as objects, binary relations as morphisms, and usual composition of relations as composition rule (so usual identity functions as identity maps). Indeed, let A be a family (i /in I) of sets A_i. Write C for the usual set-theoretic disjoint union of the sets A_i -- C = /join_i A_i. a) For each i /in I, write p_i: C --> A_i for the partial function which "is" the identity function on the summand A_i. It seems to me that the relations p_i serve as projections making C the product of the various A_i of the family A. b) Again, for each i /in I, write s_i :A_i --> C for the function which "is" the identity function on A_i. It seems to me that the relations s_i serve as injections making C the coproduct of the various A_i of the family A. c) In fact, much as is the case with additive categories, the compositions of these injections and projections satisfy p_i s_k = /empty (i /ne k), p_i s_i = id_(A_i), s_i p_i = the partial function on C which is identity on summand A_i, and /join(s_i p_i) = id_C. Of course, Wolters' own observation, in 4 (below), serves as link between a) and b); and c) is, as it were, the observation that "coproduct and product both serve as biproduct":
4. ... the fact that the formation of converse relations establishes an isomorphism between Rel and its opposite ...
Indeed, p_i and s_i are mutually converse. Do let me know, please, if I've just been talking through my hat -- that'll be a sign it's time for me to retire for real :-) . Cheers, -- Fred
Any reply or reference is well-come.
Best regards
Uwe Wolter
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
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. Peter Johnstone On Mon, 24 Feb 2014, Uwe.Wolter@ii.uib.no wrote:
Dear all,
I remember that there was some time ago a discussion on this list about limits and colimits in the category Rel of binary relations. Unfortunately, I can not remember or trace the final answer. But, if I remember right there are, besides initial and terminal objects, in general no limits or colimits in Rel.
So my questions are:
1. Is there a characterization of monomorphisms and epimorphisms in Rel? 2. Is it true that there are, in general, no products and equalizer (sums and coequalizer) in Rel? 3. Are there some general results about what limits/colimits exist or don't exist? 4. Is the presumable non-existence related to the fact that the formation of converse relations establishes an isomorphism between Rel and its opposite Rel^op?
Any reply or reference is well-come.
Best regards
Uwe Wolter
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
Writing V for the category of complete join-semilattices that Peter brought into the discussion,
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.
it might be worth pointing out that Uwe's category Rel is a V-category (in exactly the sense that Eilenberg, Kelly, Street, Day, and others mean) for exactly this choice of V. With that in mind, the parallel in additive categories with zero object, finitary (co-)products are biproducts and in V-categories with zero object, arbitrary (co-)products are biproducts (first noticed, in my awareness, by Dana May Latch, in the 20th century, for the category V of complete join-semilattices itself), is remarkable. Anyway, the second line of that parallel works much as it does for Rel. And the "matrix algebra" for maps to products, from coproducts, and, most especially, from coproducts to products, works just as it does in the case of additive categories, when it comes to these V-categories. Cheers, -- Fred [For admin and other information see: http://www.mta.ca/~cat-dist/ ]
As Peter J. is saying, categories of relations have poor (co)limits. 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. oSee [GP] 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 On 24 Feb 2014, at 23:36, Uwe.Wolter@ii.uib.no wrote:
Dear all,
I remember that there was some time ago a discussion on this list about limits and colimits in the category Rel of binary relations. Unfortunately, I can not remember or trace the final answer. But, if I remember right there are, besides initial and terminal objects, in general no limits or colimits in Rel.
So my questions are:
1. Is there a characterization of monomorphisms and epimorphisms in Rel? 2. Is it true that there are, in general, no products and equalizer (sums and coequalizer) in Rel? 3. Are there some general results about what limits/colimits exist or don't exist? 4. Is the presumable non-existence related to the fact that the formation of converse relations establishes an isomorphism between Rel and its opposite Rel^op?
Any reply or reference is well-come.
Best regards
Uwe Wolter
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
participants (6)
-
Fred E.J. Linton -
Fred Linton -
Koslowski -
Marco Grandis -
Prof. Peter Johnstone -
Uwe.Wolter＠ii.uib.no