Re: General notions of equivalence and exactness

[Sam Staton <sam.staton@cl.cam.ac.uk>]

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