From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.io/gmane.science.mathematics.categories/5110 Path: news.gmane.org!not-for-mail From: Dominic Hughes Newsgroups: gmane.science.mathematics.categories Subject: Re: pushouts in REL Date: Fri, 21 Aug 2009 15:02:44 -0700 (PDT) Message-ID: Reply-To: Dominic Hughes NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Trace: ger.gmane.org 1250947211 8866 80.91.229.12 (22 Aug 2009 13:20:11 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sat, 22 Aug 2009 13:20:11 +0000 (UTC) To: soloviev@irit.fr, Michael Barr , categories@mta.ca Original-X-From: categories@mta.ca Sat Aug 22 15:20:04 2009 Return-path: Envelope-to: gsmc-categories@m.gmane.org Original-Received: from mailserv.mta.ca ([138.73.1.1]) by lo.gmane.org with esmtp (Exim 4.50) id 1MeqVn-0007Re-DF for gsmc-categories@m.gmane.org; Sat, 22 Aug 2009 15:20:03 +0200 Original-Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MepzK-00077V-7x for categories-list@mta.ca; Sat, 22 Aug 2009 09:46:30 -0300 Original-Sender: categories@mta.ca Precedence: bulk Xref: news.gmane.org gmane.science.mathematics.categories:5110 Archived-At: 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/ ]