You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.
Hi,
I've long been interested in the potential of the category of sets in relations for use in practical applications like knowledge representation. I recently was reading on the nlab page about a generalization of the construction of Rel from set for any regular category. https://ncatlab.org/nlab/show/Rel#relations_in_a_category
I was working through this construction to try to fill in the details as concretely as possible. I wrote up these notes.
Generalizing the Rel Construction to Regular Categories.pdf
I'll share them here in case it's useful for anyone, and also so that those with more knowledge than me can point out any mistakes.
The next thing I want to do is try to work out a similarly concrete description of the construction for Rel(Cat). I am struggling with understanding the definition of an epimorphism in Cat, which is necessary for the final step of the construction when you split the projection from the pullback in order to get the actual composition of subcategories.
I read this post about it
https://math.stackexchange.com/questions/693970/monomorphisms-and-epimorphisms-in-the-category-of-small-categories
Which refers to an article Epimorphisms and domininions, III by John Isbell.
I found the paper itself somewhat forbidding, and I'm wondering if anybody might know of a resource that explains the zig zag theorem a little bit more pedagogically and step-by-step (with pictures if possible!)
You should note that Cat is not regular. One of the requirements is pullback-stability of reg-epis, and this fails in Cat (or even Pos).
The simplest example involves a pair of arrows , where and are the walking arrow and the walking composite .
Oh, thanks that probably saves me a lot of time :face_with_peeking_eye:
So I guess then you can't use the Rel(C) construction for Cat?
I wonder if there are any work arounds? I have some ideas of my own for defining a practical notion of a Relator which is to a functor what a relation is to a function. I'm pretty sure it's possible to define a category where categories are objects and relators are morphisms.
I've proven that Relators from C to D are isomorphic to subcategories of C x D.
I think the Relator definition, even though it's equivalent to subcategory of product is possibly useful for applied settings where we want to define relations between categories in terms of ordinary relations.
For those who don't speak Lean, here is the definition in notation.
Let and be categories. A relator from to consists of:
A relation
A relation
Note: and are just regular relations between sets satisfying the following conditions:
For all objects and ,
if and only if, .
For all objects and , and for all morphisms
if , then
and
This ensures that for any related morphisms, the object endpoints of those morphisms are also related.
For any and in and corresponding and in
If and , then
.
Is a 'relator' from to the same as a subcategory of ? It looks like it to me, though I didn't take a lot of time to check everything.
Very often when people try to generalize relations from to they work with [[profunctors]] between categories.
I said in my post above that a Relator is equivalent to a subcategory. I proved it in the Lean code I linked to.
I think the Relator definition, even though it's equivalent to subcategory of product is possibly useful for applied settings where we want to define relations between categories in terms of ordinary relations.
I am aware of the idea that Profunctors generalize relations for a categorical setting. But as far as I can tell Profunctors act like generalized relations for objects of categories, but they still operate deterministically on morphisms of categories. I'm trying to find a definition that allows relational mappings of both objects and mrophisms. I'd consider this more in keeping with the spirit of relations between sets. That's basically a sub-category.
I'm still working on formalizing the composition of relators, but the basic idea is this.
For morphisms you do a preliminary composition:
Then you add any compositions of morphisms related in .
I need to check about identities, but at least for composition closure I think this should results in R;S being a Relator. I also need to check associativity.
No, profunctors don't give a deterministic mapping between morphisms. A profunctor includes both a span on objects and a (closely related) span on morphisms. For instance, the profunctor from the walking arrow to with a single heteromorphism connecting each object in the domain to each of its two copies in the codomain, and in which all possible squares commute, represents the relation relating the arrow of to both its copies in the codomain.
It is critical to the usefulness of relations that they correspond to boolean-valued functions on the cartesian product. Boolean-valued functors correspond only to certain very strong full subcategories (sieves), which is why we generalize to set-valued functors, i.e. profunctors.
You can represent an arbitrary relator via a profunctor by adding a heteromorphism whenever and adding relations saying whenever and
Avi Craimer said:
I said in my post above that a Relator is equivalent to a subcategory.
Sorry, I didn't notice that!
I'm curious whether the (2-)category of categories and relators (and some sort of transformations between relators) is a sub-(2-)-category of categories and profunctors (and natural transformations between profunctors).
(The parenthetical stuff could be skipped on a first pass, but we really need natural transformations between profunctors, much as Mac Lane said he and Eilenberg invented categories and functors mainly in order to be able to talk about natural transformations. So, if you can figure out how to compose relators, it might then pay to study transformations between them.)
Well @John Baez thanks for that idea.
And thanks to @Kevin Carlson for the clarification about profunctors and non-determinism. I wanted to ask a follow up, which is that the other way in which profunctors could be less relational with respect to morphisms is that you can't have partial relations between morphisms if the endpoint objects are related.
This also speaks to John's question about whether every relater is a certain kind of profunctor. I think about a following potential counterexample.
Start with a category C which has at least one non-identity morphism. Define a relator D: C -> C that discretizes C, that is it relates every object to itself, and every identity morphism to itself, but does not relate any other morphisms. I don't think that would be possible as a profunctor since the functorality would require us to map all the morphisms. But, I don't understand the profunctor-as-relation interpretation that well, so maybe there is some way of interpreting a certain kind of functorial mapping as effectively throwing away unrelated pairs of morphisms.
Kevin Carlson said:
You can represent an arbitrary relator via a profunctor by adding a heteromorphism whenever and adding relations saying whenever and
If you have a chance to explain this a bit more I'd be grateful. I don't really understand what you mean by a heteromorphism.
One way to describe a profunctor is simply as a category that contains and as disjoint full subcategories, there are no other objects, and such that there are no morphisms from 's to 's, only in the other direction. Morphisms from 's to 's can be called "heteromorphisms", because they're like morphisms that cross between different categories. The way to recover the definition as a functor on is by mapping to the set of heteromorphisms crossing from to So you can construct profunctors by asserting the existence of some certain heteromorphisms, requiring some relations such as, in the case I gave, when and then freely generating the category resulting from those relations. The fact that morphisms only run from across to means the resulting category has no new morphisms between 's or between 's, as required by the definition.
That much is standard; I don't actually know anything about the properties of my suggested construction of a profunctor from a relator, which I just made up. But I bet something like that will subsume anything you'd want to do with relators, and I wonder whether attempts to compose relators (which might get weird due to the irregularity of Cat) will more naturally push you into profunctor composition anyway. That said, a simpler and more widely-applicable way to work with a relation-like structure in a non-regular category is to use plain spans.
This paper describes in detail two notions of pro-functor presentation, including the one described by Kevin, and a "curried" version similar to relational conjunctive queries: https://arxiv.org/abs/2404.01406