From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.io/gmane.science.mathematics.categories/4415 Path: news.gmane.org!not-for-mail From: Nick Benton Newsgroups: gmane.science.mathematics.categories Subject: RE: General notions of equivalence and exactness Date: Thu, 29 May 2008 05:43:57 -0700 Message-ID: NNTP-Posting-Host: main.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable X-Trace: ger.gmane.org 1241019933 13186 80.91.229.2 (29 Apr 2009 15:45:33 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 29 Apr 2009 15:45:33 +0000 (UTC) To: Sam Staton , "categories@mta.ca" Original-X-From: rrosebru@mta.ca Thu May 29 15:59:39 2008 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 29 May 2008 15:59:39 -0300 Original-Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1K1nA9-0004Zv-9w for categories-list@mta.ca; Thu, 29 May 2008 15:47:45 -0300 Content-Language: en-US Original-Sender: cat-dist@mta.ca Precedence: bulk X-Keywords: X-UID: 38 Original-Lines: 75 Xref: news.gmane.org gmane.science.mathematics.categories:4415 Archived-At: Hi Sam, These "zigzag closed" relations are called "difunctional". Some old referen= ces are: [1] J Riguet. Relations binaries, fermetures, correspondances de Galois (19= 48) [2] J Riguet. Quelques proprieties des relations difonctionelles (1950) [3] Katuzi Ono. On some properties of binary relations (1957). and once one knows what to search for, it turns out they're well-known. An interesting characterization (which is how we(*) discovered them) is tha= t in sets, they're the TT-closed relations, where if x,x'\in A, x(R^TT)x' i= f forall k k' : A->2, (forall y y', yRy' -> k y =3D k y') -> k x =3D k x' ([4] M Abadi. TT-closed relations and admissibility (2000) considers the situation in cpos). Nick (*) Martin Hofmann, Andrew Kennedy, Lennart Beringer and I. Martin initiall= y called these Quasi-PERs. -----Original Message----- From: cat-dist@mta.ca [mailto:cat-dist@mta.ca] On Behalf Of Sam Staton Sent: 29 May 2008 10:02 To: categories@mta.ca Subject: categories: General notions of equivalence and exactness Hello. In a category with pullbacks, say that a binary relation X <- R -> Y is "z-closed" if it satisfies the following axiom (interpreted as usual): If x R y and x' R y and x' R y' then x R y'. (The "z" in "z-closed" refers to the pattern of variables in the premise.) Z-closedness seems to be a sensible generalization of "equivalence" to relations between two different objects. (e.g. In computer science, it is common to relate the state spaces of two different systems.) Note that an endorelation is an equivalence relation if and only if it is z-closed and reflexive. Also note that, in an abelian category, every relation is z-closed. The [z-closed v. equivalence] connection seems to extend to [pullbacks v. kernel pairs]. Every span that arises from a pullback is a z-closed relation. Say that a category is "z-effective" if every z-closed relation arises as a pullback. - every abelian category is straightforwardly z-effective; - in a topos, every z-closed relation arises as a pullback span. Indeed, an extensive regular category has effective equivalence relations if and only if it is z-effective. These notions and ideas seem quite elementary, even fundamental, and I would be surprised if no-one had thought of them before. I borrowed the terminology "z-closed" from a paper by Erik de Vink and Jan Rutten (Theoret Comput Sci, 221:271-293, 1999) but I couldn't find any other references. Have I missed something? I'd be grateful for any observations or suggestions. Sam PS. I'd like to take the opportunity to acknowledge the helpful replies (public and private) to my question about W-types, a few months ago.