General notions of equivalence and exactness

General notions of equivalence and exactness

[Sam Staton]

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.

Re: General notions of equivalence and exactness

[Sam Staton]

Many thanks to all who replied to my message, in private and publicly.

I notice that these concerns also arose on this mailing list back in
1992:
http://www.mta.ca/~cat-dist/archive/1992/92-06.txt

At that time, Michael Barr was asking, amongst other things, about the
exactness property that "every Mal'cev [=difunctional=z-closed]
relation is a pullback", which holds both in toposes and in abelian
categories (as I mentioned below). I wonder if anything more came out
of that. He mentioned a possible connection with "effective unions",
but I haven't been able to get anything to work there.

By the way, following the comments about Mal'cev operators, and Peter
Freyd's "Mal'cev allegories", I note that (exact) categories in which
every relation is difunctional have been called "Mal'cev
categories" [see e.g. the book by Bourn and Borceux on the topic
(pointed out by Peter Lumsdaine), or Carboni, Lambek, Pedicchio,
Diagram chasing in Mal'cev categories, JPAA 69].

Sam


On 29 May 2008, at 10:01, Sam Staton wrote:

> 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.
>
>

Re: General notions of equivalence and exactness

[Marco Grandis]

In Genoa, in the late 60's and after, our group was studying
categories of relations.

I was interested in relations on abelian categories, for homological
algebra, while Gabriele Darbo, Franco Parodi and others were more
interested - after the general construction - in relations on sets,
and even more in "corelations on sets" (relations on Set^op), called
"transductors". (It is the dual construction, based on equivalence
classes of cospans of sets, i.e. quotients of the sum of domain and
codomain; used to simulate electric connections between two sets of
terminals [see how they compose], and as a formal basis for a general
"theory of devices".)

At that time, a category with involution  u |--> u*  (typically, a
category of relations in some sense) was called "von Neumann regular"
if the condition  u.u*.u = u  holds for every arrow (plainly related
to von Neumann regularity of semigroups and rings).

The category of relations of sets is not vN-regular, the simplest
counterexample being likely the Z-shaped relation which transgresses
your condition:

R: {x, y} --> {x', y'}
x R y,    x' R y,     x' R y'

This relation was precisely called "Z" in the paper

  [Pa] F. Parodi, Simmetrizzazioni di una categoria II, Sem. Mat.
Univ. Padova, 44 (1970), 223-262.


http://archive.numdam.org/ARCHIVE/RSMUP/RSMUP_1970__44_/
RSMUP_1970__44__223_0/RSMUP_1970__44__223_0.pdf

On the other hand, as you say, category of relations on abelian
categories are von Neumann regular (which is a crucial fact in
studying subquotients, see Mac Lane's text on Homology).

But, interestingly, the category of CORELATIONS on sets is also von
Neumann regular, see the paper above [Pa].

Best regards

Marco Grandis



On 29 May 2008, at 11:01, Sam Staton wrote:

> 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.
>
>
>

RE: General notions of equivalence and exactness

[Nick Benton]

Hi Sam,

These "zigzag closed" relations are called "difunctional". Some old references are:

[1] J Riguet. Relations binaries, fermetures, correspondances de Galois (1948)
[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 that in sets, they're the TT-closed relations, where if x,x'\in A, x(R^TT)x' if
 forall k k' : A->2, (forall y y', yRy' -> k y = k y') -> k x = 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 initially 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.