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.
Gershom (May 08 2020 at 06:38):, I'm pretty sure, does not admit an epi-mono factorization system. A mono in is a relation that when viewed as is a mono in -- i.e. injective. Dually for epis. In any case, consider now the codiscrete endorelation on some set, say , which relates each element to all elements. This should be neither epi nor mono, nor do I see how it could factor into such.
However, we could consider the subcategory of which only admits morphisms that do have a factorization. This seems like an interesting gadget. Has it been named and/or studied?
Morgan Rogers (he/him) (May 08 2020 at 10:05):It's a little dry, but I reckon there's bound to be some material relevant to you in Freyd and Scedrov's Categories, Allegories.
Joe Moeller (May 08 2020 at 20:46):https://www.cambridge.org/core/journals/canadian-journal-of-mathematics/article/hopf-algebras-of-combinatorial-structures/6975D3AB1823155B48F2FD378A4C793C
In this paper, Schmitt talks about relational categories: categories which are between FinBij and FinRel. There is some sort of factorization you can do for relations: into an injection, a surjection, a coinjection, and a cosurjection.
Mike Shulman (May 09 2020 at 13:39):Gershom said:
However, we could consider the subcategory of which only admits morphisms that do have a factorization.
Is it clear that the collection of such morphisms is a subcategory? That is, that the composite of two such morphisms is again such a morphism?
Gershom (May 09 2020 at 17:43):I tried to consider the above and now i think i realized my counterexample isn't a counterexample (apparently all my thinking is particularly fuzzy today, sorry)? i.e. we can send {1,2} to {1} to {1,2} and that should be an epi followed by a mono in Rel. So now I still don't think Rel has a factorization system, but I don't have a good concrete answer why. But again, I'm feeling terribly confused about everything at the moment, so...
Gershom (May 09 2020 at 18:47):Ok now that I've done more thinking about Joe's link (thanks!) I think that Rel does have an epi-mono factorization system. In particular, Joe's link says, as I understand it, that all relations between sets are generated by four elementary operations -- adding elements, removing elements, merging elements, and splitting elements. This is very plausible, and I bet it's in some standard literature I don't know about?
In any case, adding and splitting should both be monos in Rel, and removing and merging should both be epis. So there's some things to check (not least uniqueness) but that should give a standard epi-mono ofs. The algorithm is similar to that of Set. (And I guess its the same if we consider a splitting of x R y as a splitting of x -> P(Y))? If two elements of X relate to the same set (possibly empty) in Y, first relate them to a single element in Z. Now relate each element in Z to a distinct set in Y. Done.
I looked around for a while for material on these sorts of properties of Rel and didn't find much. So I wonder if its folklore, or just well buried.
Cole Comfort (May 09 2020 at 21:39):Gershom said:
Ok now that I've done more thinking about Joe's link (thanks!) I think that Rel does have an epi-mono factorization system. In particular, Joe's link says, as I understand it, that all relations between sets are generated by four elementary operations -- adding elements, removing elements, merging elements, and splitting elements. This is very plausible, and I bet it's in some standard literature I don't know about?
The prop version of sets and relations is given by matrices over the Boolean semiring with the direct product as the tensor, so you can show that it is presented in the usual way for matrices over a semiring, involving bi-commutative bialgebras + specialness. This is related to spans, cospans and corelations in this paper: https://arxiv.org/pdf/1601.02307.pdf.
Are these 4 operations related to the generators of this bialgebra?
Gershom (May 10 2020 at 03:05):Cole, your comments remind me of the lisa simpson quote "I understand those words, but not in that order". Do you think you could spell this out in some further detail?
Cole Comfort (May 10 2020 at 03:33):Gershom said:
Cole, your comments remind me of the lisa simpson quote "I understand those words, but not in that order". Do you think you could spell this out in some further detail?
First, convince yourself that the symmetric monoidal catgory of finite ordinals and functions under the monoidal product + is classified by the prop of commutative monoids. That is, this category is generated by the free commutative monoid on the one object set under direct sum. Let us take a detour through spans before we talk about rel. How can we glue two copies of finite sets and functions to get finite spans of functions? The usual way is to consider the category induced by the (almost) distributive law given by pulling back functions, which allows us to turn cospans into spans. This distributive law, at the level of monoids, turns out to be given by the equations of a bi-commutative bialgebra. My intuition is, because one can think of spans as matrices over the natural numbers: the comonoid is copying, and the monoid is addition. The counit of copying is deleting and the unit of addition is 0. One can verify that copying and addition over forms a bialgebra. To get from spans to Rel, one has to take a quotient; think of this as taking you from natural number matrices to matrices over the Boolean semiring. This quotient is precisely asserting that copying and then adding is the identity. So we have to add one more equation to the equations of a bicommutative bialgebra, ``specialness'', to express the equation 1+1=1 in Bool.
This is discussed in further detail in Lack's paper: http://www.tac.mta.ca/tac/volumes/13/9/13-09.pdf
Gershom (May 11 2020 at 04:21):Thanks. I'll think more about this.
I should mention that I thought a bit more about things and now I think I have a good counterexample, and also can explain why the factorization in the paper probably doesn't help. Again, all just sort of high-level thoughts. So the counterexample is the inverse of the diagonal map on any set greater than two. I.e. it sends each element to every element except itself. This one I genuinely can't see how to factor as an epi followed by a mono. What the paper lets you do, I think, is give a factorization as a mono followed by an epi, since the key steps are cosurjection followed by surjection, which i as I think of it "splitting" (which is mono) followed by "merging" (which is epi). You "pull apart" each element that lands in multiple places into a copy for each place it lands, and then you remerge the split bits into new things which tell you where they actually land. But just as in set, this is far from unique. You can always "oversplit" followed by doing more merging. So even {1} -> {1} can factor a lot of ways with this process, and its still always a mono followed by an epi, and in fact even (i think?) a split mono followed by a split epi. So the paper gives a nice factorization that lets you think of how relations are generated, but it doesn't give a unique factorization.
Reasoning like the above has me pretty convinced that the "antidiagonal" can't factor the other way as an epi followed by a mono at all.
Which brings me back to the original question, I guess, that Mike asked, which is (in my mind) "what class of morphisms correspond to the ones that do factor, and can we show that they're closed under composition".
Gershom (May 11 2020 at 05:01):And actually, if you can't factor the antidiagonal, this also shows that since two "nice" morphisms composed in the "wrong" order give something tricky, that things which factor don't compose into things which factor, answering that question in the negative. So it seems possible the only "nice" subcategory where things factor is going to be something like Set or Set^op, i.e. something where the relationality of Rel is gone entirely. So that answers this whole thread in the negative. Well, it was a useful exercise anyway!
Cole Comfort (May 11 2020 at 05:07):Gershom said:
And actually, if you can't factor the antidiagonal, this also shows that since two "nice" morphisms composed in the "wrong" order give something tricky, that things which factor don't compose into things which factor, answering that question in the negative. So it seems possible the only "nice" subcategory where things factor is going to be something like Set or Set^op, i.e. something where the relationality of Rel is gone entirely. So that answers this whole thread in the negative. Well, it was a useful exercise anyway!
I would imagine that this also works for sets and partial functions, but that isn't that removed from Set.
Gershom (May 11 2020 at 09:34):An interesting place I just was led by this is the paper "Completions, comonoids, and topological spaces" (https://www.sciencedirect.com/science/article/pii/S0168007205000679) which gives the category of basic pairs (used in formal topology) as the "Freyd completion" of Rel, which I guess adds an ofs to any category. This is due to grandis: http://www.dima.unige.it/~grandis/Var2.pdf (2.1).