May 28, 2019

Posted by John Baez

I’m interested in internalizing the “free category on a reflexive graph” construction.

We can define reflexive graphs internal to any category $C$, and categories internal to $C$ whenever $C$ has finite limits. Suppose $C$ has finite limits; let $\mathsf{RGph}(C)$ be the category of reflexive graphs internal to $C$, and let $\mathsf{Cat}(C)$ be the category of categories internal to $C$. There’s a forgetful functor

$U \colon \mathsf{Cat}(C) \to \mathsf{RGraph}(C)$

When does this have a left adjoint?

I’m hoping it does whenever $C$ is the category of algebras of a Lawvere theory in $\mathsf{Set}$, but I wouldn’t be surprised if it were true more generally.

Also, I’d really like references to results that answer my question!

Posted at May 28, 2019 6:54 AM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/3114

Re: A Question on Left Adjoints

This functor preserves all limits that exist, so it has a left adjoint whenever the adjoint functor theorem applies. For instance, this is the case when $C$ (hence also $RGraph(C)$ and $Cat(C)$) is locally presentable. This includes the category of algebras for any accessible monad (such as a finitary monad, i.e. Lawvere theory) on a locally presentable category (such as $Set$).

Posted by: Mike Shulman on May 28, 2019 9:48 AM | Permalink | Reply to this

Re: A Question on Left Adjoints

I’d add maybe just a little more to that, because of course it’s not true that any limit-preserving functor out of a locally presentable category has a left adjoint (there are counterexamples in the case $Grp$, for instance).

But in this case the forgetful functor $Cat(C) \to RGraph(C)$ is also accessible (because it satisfies the stronger condition of preserving filtered colimits), and so by Theorem 1.66 of Locally Presentable and Accessible Categories, that together with its continuity ensure that the adjoint functor theorem will apply.

But I think you ought to be able to make the construction pretty concrete. It’s slightly easier to consider the case for directed graphs in $C$ in place of reflexive directed graphs, but the idea is similar: write the directed graph as a span $V \leftarrow E \to V$, and then take the coproduct (over natural numbers $n$) of the $n$-fold span composite (involving iterated pullbacks) in the category of spans from $V$ to $V$. This gives you the free category of the directed graph.

The case for reflexive graphs involves taking a quotient of this construction to force the loops to behave as identities. If the details of that feel too messy, you can always quote a general result on relatively free functors; see for example the nLab, using the monadicity of $Cat$ and of reflexive graphs over the category of directed graphs.

Posted by: Todd Trimble on May 28, 2019 2:50 PM | Permalink | Reply to this

Re: A Question on Left Adjoints

(Actually, I think I need to be a little more careful about the claimed concrete construction, because in my head it seems to use distributivity of certain limits over coproducts.)

Posted by: Todd Trimble on May 28, 2019 4:09 PM | Permalink | Reply to this

Re: A Question on Left Adjoints

Urgh, sorry for the multiple comments. But regarding a concrete construction: instead of what I proposed a few comments ago for the case of directed graphs, involving a coproduct of iterated span composites, maybe it’s easier after all in the reflexive graph setting, by imitating one or another free monad construction.

That is: a paths of length $m$ in an internal reflexive graph can be embedded into paths of length $n$ for any $n \gt m$, by inserting a bunch of extra loops at the beginning. Here $Path_n(G)$ is, as before, the iterated span composite which is a certain type of finite limit in $C$. So we would form a filtered colimit of type

$Path_0(G) \hookrightarrow Path_1(G) \hookrightarrow Path_2(G) \hookrightarrow \ldots$

and then the free category would be formed as a suitable quotient of this colimit, one that would force loops to be two-sided identities.

I have a feeling this works, but assuming it does, I think someone like Mike would be able to answer questions about this more quickly than I could. Actually, maybe I could just ask Mike directly: do you think something like this works?

Posted by: Todd Trimble on May 28, 2019 4:41 PM | Permalink | Reply to this

Re: A Question on Left Adjoints

Thank you this is very helpful. I did some digging and the result we want seems to be part of Gabriel-Ulmer duality which gives a biequivalence

$\mathsf{Lex}^{op} \to \mathsf{LFP}$

where $\mathsf{Lex}^{op}$ is the 2-category of categories with finite limits, finite limit preserving functors and natural transformations. $\mathsf{LFP}$ is the 2-category of locally finitely presentable categories, right adjoints between them, and natural transformations. This equivalence makes the assignment $C \mapsto \mathsf{Lex} ( C , \mathsf{Set} )$ and $f \colon C \to D \mapsto (-) \circ f \colon \mathsf{Lex} ( C , \mathsf{Set} ) \to \mathsf{Lex} ( D , \mathsf{Set} )$ i.e. composition with $f$.

Let $C$ be the category with two parallel arrows freely closed under finite limits and let $D$ be the finite limit theory for categories. Then there is a finite limit preserving functor $f \colon C \to D$ which includes $C$ into $D$ in the natural way.Then Gabriel-Ulmer duality being well-defined says that the forgetful functor this induces is a right adjoint. This is the result I want.

The most detailed description of this duality is probably in Adamek’s Algebraic Theories of Quasivarieties. Unfortunately, as far as I can tell, Adamek’s detailed description of the equivalence skips the proof that this is well defined. The original source is in German (and I can’t read it). It seems likely to me that I’m missing something.

Re: A Question on Left Adjoints

Sorry I made a mistake here. The Gabriel-Ulmer duality is contravariant. The functor $(-) \circ f$ goes from $\mathsf{Lex} (D, \mathsf{Set} ) \to \mathsf{Lex} (C , \mathsf{Set} )$.

Re: A Question on Left Adjoints

Yeah, I think this is a nice way to go. I’d just make one correction in your description of $LFP$: you want finitary (= filtered-colimit preserving) right adjoints as the $1$-cells. Otherwise: it’s slick to let Gabriel-Ulmer do the work for you this way.

It sounds from your description that you’re now going with directed graphs, not reflexive directed graphs. Of course either way it works fine.

I think Mike had in mind something more general (that on some level this should work in the generality of locally presentable, not just locall finitely presentable, categories). But your approach seems sound for the locally finitely presentable case.

Posted by: Todd Trimble on May 31, 2019 2:39 AM | Permalink | Reply to this

Re: A Question on Left Adjoints

Thanks for that correction; of course in the right adjoint case you also need the functor to be accessible. It’s not obvious to me that this forgetful functor preserves ($\omega$-)filtered colimits in the general case of an arbitrary locally presentable category $C$ (for instance, if finite limits in $C$ fail to commute with filtered colimits — they do commute if $C$ is locally finitely presentable, or if it’s a Grothendieck topos, but in general I don’t think they do, do they?). But I would expect to be able to conclude that it’s accessible using generalities about functors induced by morphisms of sketches.

I didn’t mention an explicit construction due to precisely the same worries about limit-colimit distributivity that you mention in your second comment. The “obvious” construction involving a countable coproduct of objects of length-$n$ paths does seem to me only to work if pullbacks preserve countable coproducts. But your alternative approach, mimicking the transfinite construction of free algebras seems likely to work in general (though again, in the general case it’s not clear to me that you can get away with a merely countable colimit). Something similar appears in appendix D.1 of Tom’s book Higher operads, higher categories.

Posted by: Mike Shulman on May 28, 2019 5:52 PM | Permalink | Reply to this

Re: A Question on Left Adjoints

Thanks for the (guarded) confirmation, Mike. Since Jade seems interested particularly in the case of algebras of a Lawvere theory, maybe it’s okay not to worry too much about the general locally presentable case, and just focus on the locally finitely presentable case, where the length-$n$ path construction probably gets the job done without too much fuss.

Posted by: Todd Trimble on May 28, 2019 6:39 PM | Permalink | Reply to this

Re: A Question on Left Adjoints

Are we on the same page? I was referring to the construction that mimics the transfinite construction of free algebras. (Oh, I see now why my last comment might have been confusing there.)

Posted by: Todd Trimble on May 28, 2019 10:22 PM | Permalink | Reply to this

Re: A Question on Left Adjoints

Are you sure? Even in a locally finitely presentable category, countable coproducts may not be stable under pullback, which I think is the “obvious” condition to require for that construction to work.

Posted by: Mike Shulman on May 28, 2019 9:37 PM | Permalink | Reply to this

Re: A Question on Left Adjoints

Oops, I replied to the wrong thing. See my comment above.

Posted by: Todd Trimble on May 28, 2019 10:23 PM | Permalink | Reply to this

Re: A Question on Left Adjoints

Ah. I thought “length-$n$ path construction” referred to the one with countable coproducts, since that’s where I used the phrase in my comment, but you meant your sequential colimit one which also uses length-$n$ paths. (-:

Posted by: Mike Shulman on May 29, 2019 12:23 AM | Permalink | Reply to this

Re: A Question on Left Adjoints

To be clear the original proposition for a concrete construction was to form the left adjoint as the following coproduct $\sum_{n=0}^{\infty} E^n$ where $E^n$ is the $n$-fold composition of the span $V \leftarrow E \to V$ with itself. The problem is that when you want to define composition $\circ \colon \sum_{n=0}^{\infty} E^n \times_{V} \sum_{n=0}^{\infty} E^n \to \sum_{n=0}^{\infty} E^n$ you want the pullback to commute with the coproducts so you can define composition on each pair $E^n \times_{V} E^m$.

To avoid this problem you say that we are in a locally finitely presentable category and compute the free category as the directed colimit you suggested. Then to define composition you still want to define it in pairs $\mathrm{Path}_n (G) \times_V \mathrm{Path}_m (G) \to \mathrm{Path}_{n+m} (G)$ so you want this pullback to commute with directed colimits. In locally finitely presentable categories is this always true? An object is called finitely presentable if its representable preserves directed colimits. It seems like this might imply that this pullback does as well but I’m not sure how.

Re: A Question on Left Adjoints

In a locally finitely presentable category $D$, finite limits commute with filtered colimits. If you like, you can invoke Gabriel-Ulmer duality to see this: write $D$ as $Lex(C^{op}, Set)$ where $C$ is the category of finitely presented objects, and then use the fact that finite limits commute with filtered colimits in $Set$, so that filtered colimits in $Lex(C^{op}, Set)$ may be computed pointwise and the same commutation would hold in that category.

Posted by: Todd Trimble on May 31, 2019 11:32 AM | Permalink | Reply to this

Re: A Question on Left Adjoints

Thank you. This is beautiful.

Kevin

This is just to record an example of a locally presentable category in which finite limits don’t commute with filtered colimits. Consider the $\aleph_1$-presentable category $\omega-SLat$ of posets admitting suprema of nonempty countable subsets and maps preserving those suprema. For finite posets, these are just order-preserving maps. The filtered diagrams $D_1=\{[0]\to [1]\to...\to [n]\to...\}$ and $D_2=\{[1]\to [2]\to...\to [n+1]\to...\}$, where the maps are inclusions of finite ordinals as initial segments, both have as colimit the ordinal $\omega+1$. There are two natural transformations $I,F: D_1\to D_2$ given by the inclusion of the initial and of the final segments, respectively. The equalizer of $I$ and $F$ in $\omega-SLat^{\mathbb{N}}$ is the empty diagram and has empty colimit. But $\mathrm{colim} I$ and $\mathrm{colim} F$ have nonempty equalizer, namely the single point $\omega\in \omega+1$.

Posted by: Kevin Carlson on June 5, 2019 2:06 AM | Permalink | Reply to this

Re: A Question on Left Adjoints

That’s nice – thanks!

I changed the subject line back to what it was; hope you don’t mind.

Posted by: Todd Trimble on June 5, 2019 12:40 PM | Permalink | Reply to this

Re: A Question on Left Adjoints

Oops, weird. I don’t remember editing the subject in my previous comment, certainly didn’t mean it to be my name!

Posted by: Kevin Carlson on June 5, 2019 5:22 PM | Permalink | Reply to this

Re: A Question on Left Adjoints

I don’t see a way to change the subject header of that one comment. No big deal: it’s a nice example, Kevin! Thanks!

Posted by: John Baez on June 5, 2019 5:41 PM | Permalink | Reply to this

Re: A Question on Left Adjoints

The following two results may be relevant:

• Proposition 7.3 in M. E. Maietti, “Joyal’s arithmetic universes as a list-arithmetic pretopos”, Theory and Applications of Categories 24 (3) (2010), pp. 39–83.

• Proposition 1.6 in T. M. Fiore, N. Gambino and J. Kock, “Monads in double categories”, Journal of Pure and Applied Algebra 215 (2011), pp. 1174-1197.

Posted by: Nicola Gambino on May 30, 2019 3:54 PM | Permalink | Reply to this

Re: A Question on Left Adjoints

Thank you. I am working on understanding these propositions and I will let you know if I have any questions :-)

Re: A Question on Left Adjoints

Hi thanks. This might be exactly what I need. For a Lawvere theory $\mathsf{Q}$ I would like the category $\mathsf{Mod} ( \mathsf{Q} )$ to be a list-arithmetic pretopos. Do you have any intuition about whether or not this would be true?

Re: A Question on Left Adjoints

It would be true only very rarely. You would need the category to be extensive for one thing, and already that’s pretty rare for a category of algebras. It would be an interesting side question to know just how rare; someone like Peter Johnstone might know the answer to that.

Was there something insufficient about the other responses you got?

Posted by: Todd Trimble on June 18, 2019 5:58 PM | Permalink | Reply to this

Re: A Question on Left Adjoints

Your construction involving taking the directed colimit of $\mathrm{Path}_0 (G) \hookrightarrow \mathrm{Path}_1 (G) \ldots$ takes care of the left unit law. To take care of the right unit law you quotient by it directly (using a coequalizer?). The problem is that in general, coequalizers are not directed colimits so I’m not sure how to define the operation of composition in the same way as in the coproduct construction.

The proof involving the Gabriel-Ulmer duality doesn’t apply. Let $A$ and $B$ be categories with finite limits. Then the duality says that every functor

$\mathrm{Lex}(A, \mathsf{Set} ) \to \mathrm{Lex}(B,\mathsf{Set} )$ induced by composition is a finitary right adjoint. However, I am interested in a right adjoint to the forgetful functor

$\mathrm{Lex}(A, \mathrm{Prod}(Q,\mathsf{Set}) ) \to \mathrm{Lex}(\mathrm{Prod}(Q,\mathsf{Set}) )$

where $Q$ is a Lawvere theory. I suspect that there may be some way to use Gabriel-Ulmer in a “pointwise way”. If there is a tensor product in $mathsf{Lex}$ with $\mathsf{Lex} (A \otimes B, C) \cong \mathsf{Lex} ( A, \mathsf{Lex} (B,C) )$ then we can close $Q$ under finite limits to get $\bar{Q}$ and

$\mathsf{Lex} (A \otimes \bar{Q}, \mathsf{Set} ) \cong \mathsf{Lex}( A, \mathsf{Lex} (\bar{Q}, \mathsf{Set} ) \cong \mathsf{Lex} (A, \mathsf{Prod} (Q, \mathsf{Set} ) )$

Then Gabriel-Ulmer duality can be used to prove that the functor induced by composition with $f \otimes 1$ is a finitary right adjoint.

Does this seem like it’s on the right track?

Re: A Question on Left Adjoints

Following the free monoid construction, I would expect you should do the quotient for the other unit law at each finite stage rather than waiting to the end. That is, define something like $P_0 = Path_0$, $P_1=Path_1$, and $P_2 = coeq(P_1 \rightrightarrows Path_2)$, so that $P_2$ consists of length-2 paths with $(f,id) = (id,f)$ imposed, and “so on”. Then the directed colimit should be correct right away without any further quotienting, and it should be all that has to be preserved.

As for the second approach, I believe there is such a tensor product in $Lex$ (at least, bicategorically), but I can’t think of a reference off the top of my head. Probably it is a special case of algebras for a commutative lax-idempotent pseudomonad or something.

Posted by: Mike Shulman on June 18, 2019 10:58 PM | Permalink | Reply to this

Re: A Question on Left Adjoints

Thanks, Jade, for pointing out the deficiency of the earlier suggestion (of the concrete construction for free internal categories).

I was about to say that I don’t have a lot to add to what Mike just said, and also that I personally haven’t sat down to check that everything works as advertised. Since I’ve made a few silly mistakes so far in the discussion, you would be justified in not accepting a claim just on my personal say-so.

However, after googling a bit, I did find a paper by Steve Lack which addresses your question. Specifically, in the beginning of section 5, he answers your exact question of constructing free internal categories within varieties (categories of algebras of Lawvere theories). So hopefully that will do for your purposes.

I do agree with Mike that your idea of using a tensor product on $\mathsf{Lex}$ should work and is nicely high-powered, but nailing down every last detail may be more work than you want for your immediate purposes.

Posted by: Todd Trimble on June 19, 2019 9:20 PM | Permalink | Reply to this

Re: A Question on Left Adjoints

Glad you found that Lack paper, Todd. In particular, he points out that Kelly’s construction is designed for free monads, where the tensor product (composition of endofunctors) preserves only directed colimits on one side, but preserves all colimits on the other side. So possibly my last suggestion, which was based on that, will not work in this situation either, and you need his more refined version.

Someone should add a reference to that Lack paper to the nLab page on free monoids.

Posted by: Mike Shulman on June 21, 2019 7:17 PM | Permalink | Reply to this

Post a New Comment