Limits and colimits in Rel?

Limits and colimits in Rel?

[Uwe.Wolter]

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

Re: Limits and colimits in Rel?

[Fred Linton]

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

Re: Limits and colimits in Rel?

[Prof. Peter Johnstone]

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

Re: Limits and colimits in Rel?

[Marco Grandis]

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

Re: Limits and colimits in Rel?

[Fred E.J. Linton]

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

Re: Limits and colimits in Rel?

[Koslowski]

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