Re: General notions of equivalence and exactness

[Marco Grandis <grandis@dima.unige.it>]

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