Category Theory
Zulip Server
Archive

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.

Stream: learning: questions

Topic: functors between presheaf categories

John Baez (May 09 2024 at 14:13):

As well-known, a functor $F: C \to D$ between categories gives a functor $F^\ast: \widehat{D} \to \widehat{C}$ between their presheaf categories (given by precomposition with $F^{\textrm{op}} \colon C^{\textrm{op}} \to D^{\textrm{op}}$) which has both a left and right adjoint. Does the left adjoint of $F^*$ preserve monics? I see no reason it should, but I haven't found a counterexample yet. What's the simplest counterexample, if there is one?

Amar Hadzihasanovic (May 09 2024 at 14:17):

Functors that preserve pullbacks also preserve monics, so in particular all right adjoint functors preserve monics. Or did I misunderstand the question?

John Baez (May 09 2024 at 14:18):

Sorry, I meant left. I'll fix the question.

Morgan Rogers (he/him) (May 09 2024 at 15:24):

See Theorem 2.32 here. If I take a monoid as a one-object category and consider the unique functor to the terminal category, the left adjoint of the induced functor between presheaf categories preserves monomorphisms iff the monoid satisfies the right Ore condition.

Morgan Rogers (he/him) (May 09 2024 at 15:27):

(More generally, I can replace my monoid with any category, and "right Ore condition" becomes the dual of what is more commonly called the "amalgamation property". I think the proof generalises. You can find the equivalence between this property and the property of the presheaf topos being De Morgan in Johnstone's Sketches of an Elephant)

Morgan Rogers (he/him) (May 09 2024 at 15:28):

(I should also mention that I have a proposal for a Masters research project on my website with the goal of verifying and exploring this connection :wink: )

Aaron David Fairbanks (May 09 2024 at 15:31):

I think this left adjoint is the functor between the free cocompletions of $C$ and $D$ induced by $F$. Is that right? If $F$ doesn't preserve a certain monic, the induced map between free cocompletions doesn't either. (The Yoneda embedding preserves and reflects monics.)

Morgan Rogers (he/him) (May 09 2024 at 16:43):

Great point! So from that perspective, the simplest example would be the inclusion of a composable pair into the "walking mono" (I'll let you figure out notation for that if you need it). On the other hand, the free monoid on two elements isn't right Ore so the terminal functor on that category gives an example where all monos are trivially preserved but the extension still doesn't preserve monos!

John Baez (May 09 2024 at 18:13):

Great! Thanks for all these examples. By the way, this is a question that came up in our team's work on agent-based modeling: we were wondering whether (and when) "data migration" along such a left adjoint preserves the monicity requirement of the left arrow in a "double pushout rewrite rule" $$L \lhookarrow I \to R$$. So y'all have helped us understand this.

By the way, how does the inclusion of a composable pair into the "walking mono" fail to preserve monics? It seems more like that functor fails to reflect monics. Maybe I'm not understanding what you meant, @Morgan Rogers (he/him).

Kevin Carlson (May 09 2024 at 18:17):

I don’t understand what the walking mono is even supposed to be, since being a mono isn’t an equational condition. The free thing-with-a-mono in a category of mono-preserving functors is just the arrow, and the free thing-with-a-mono in a category of arbitrary functors doesn’t exist; are we talking about the walking split mono?

John Baez (May 09 2024 at 18:25):

I think the counterexample functor $F: C \to D$ that I want is the inclusion of the "walking arrow" category, with an arrow $f: y \to z$ and no other morphisms but identities, into the "walking non-mono" category, with an arrow $f: y \to z$, two arrows $g,h: x \to y$, a single arrow from $x$ to $z$, so that $fg = fh$, and no other morphisms but identities.

Evan Patterson (May 09 2024 at 19:04):

I would guess that the "walking mono" is a finite limit theory, or a sketch, or another such object, such that a model is precisely a monomorphism.

John Baez (May 09 2024 at 19:15):

By the way, my calling the category $D$ "the walking non-mono" was intended humorously, since I'm working in the doctrine of plain categories, and functors don't preserve non-monicness, so it's easy to find a functor that maps this non-mono to a mono. A more precise name would have been "the walking pair of parallel arrows that become equal upon postcomposition with a third arrow". A functor from $D$ to any other category picks out a pair of parallel arrows that become equal upon postcomposition with a specified third arrow.

Spencer Breiner (May 09 2024 at 19:26):

The walking [[fork]]
https://thumbs.dreamstime.com/b/fork-metal-legs-walking-fork-metal-legs-queue-line-walking-d-illustration-horizontal-isolated-over-white-135160466.jpg

Ryan Wisnesky (May 09 2024 at 20:21):

May I ask more about the example, @John Baez ? I ask because we've encountered a similar problem before in algebraic data integration: namely, if f and g and monos, we want the pushout of f and g to be monos, because that guarantees a conservativity property that ensures the pushout didn't "over integrate" data. In our example f and g will themselves arise from the left adjoint to pre-composition (our 'sigma' operation), so we have an interest in your question as well. For the pushout question David had a UROP work out some special cases and write a report, am looking for it now.

John Baez (May 09 2024 at 20:47):

May I ask more about the example, John Baez?

Sure! What do you want to know about it?

Ryan Wisnesky (May 09 2024 at 21:06):

Sure, I'm curious what the failure of mono-ness "means" for your example: would it indicate the same thing as what we mean by "over-integration", for example. And are there other places where you also need mono-ness to rule out more examples of your phenomenon? I'm also just curious to see examples of the functor F that arises in your context. Thanks!

John Baez (May 09 2024 at 22:04):

Okay! As you know, graphs, combinatorial structures of various other kinds, and databases can be seen as presheaves on various categories. In 'double pushout rewriting' we look for instances of some pattern $L$ in a presheaf and replace it with some other pattern $R$. By 'pattern' I simply mean another presheaf. So, we specify a double pushout rewriting rule using a diagram

$L \hookleftarrow I \to R$

where $L, I, R$ are presheaves. $L$ is the pattern whose instances we will look for, $R$ is the pattern we replace it, and $I$ is what these two patterns have in common. For this to work well we need the morphism $L \hookleftarrow I$ to be monic.

So far all this is happening in some fixed presheaf category, say the category of presheaves on $C$, which I will call $\widehat{C}$. But a functor $\phi: C \to D$ induces a functor

$\phi^* : \widehat{D} \to \widehat{C}$

which has a left adjoint

$\phi_! : \widehat{C} \to \widehat{D}$

This left adjoint is - as you well know - useful for converting presheaves on $C$ into presheaves on $D$, a process called "$\Sigma$ migration" when our presheaves are thought of as databases.

It's interesting whether a rewrite rule for presheaves on $C$ can be converted into a rewrite rule for presheaves on $D$ via this process of $\Sigma$ migration. Given

$L \stackrel{f}{\hookleftarrow} I \stackrel{g}{\to} R$

we get

$\phi_!(L) \stackrel{\phi_!(f)}{\longleftarrow}\phi_!(I) \stackrel{\phi_!(g)}{\longrightarrow} \phi_!(R)$

But does $f$ being monic imply that $\phi_!(f)$ is monic?

No! Not in general.

John Baez (May 09 2024 at 22:06):

I didn't think it would, but I couldn't see a counterexample. That's been solved now, thanks to the power of the folks here.

John Baez (May 09 2024 at 22:19):

By the way, for people who prefer $C$-sets (objects of $\mathrm{Set}^C$) to presheaves (objects of $\mathrm{Set}^{C^{\rm op}}$), it's worth remembering that the specific counterexample I mentioned needs to be "opped" to work for $C$-sets.

Ryan Wisnesky (May 09 2024 at 22:33):

Thanks for being so explicit! To elaborate my question, I'm wondering about what "works well" means. For example, if I -> L is not monic, what would "go wrong"? I'll compare your answer with what happens in algebraic data integration when the related pushout diagrams "go wrong" due to failure to be monic, to see if the phenomenon you're witnessing is in fact the perennial problem of "over-integrating".

John Baez (May 09 2024 at 22:43):

@Kris Brown understands this better than me, but to actually "apply" a rule in double pushout rewriting, you need to find something called a [[pushout complement]], and to be sure this is unique (up to isomorphism) you want $L \hookleftarrow I$ to be monic.

John Baez (May 09 2024 at 22:50):

I could say more about how double pushout rewriting works, but what I don't have is an example of how the non-monicness of this map causes the nonuniqueness of the pushout complement, and how that in turn makes double pushout rewriting "bad".

Kris Brown (May 09 2024 at 23:03):

Here's the simplest example (rewriting in Set) where there are three possible pushout complements (two, up to isomorphism).

Screenshot-2024-05-10-at-12.02.18AM.png

Ryan Wisnesky (May 09 2024 at 23:33):

I'm trying to understand this in terms of logic/database theory. In logical terms, f : I -> L can be read as a sequent in regular logic, and g : I -> R is called a "trigger"; in such a circumstance, we may "repair" R to admit a map from L (this being called "chasing" database R with formula f on trigger g). However, this map from L need not be unique, and when f is mono the map might be unique (I'd have to look this up). Pushout complement diagrams seem to arise in some related process. So I think the requirement that f be a mono probably is related to "over-integrating" data (or rather, 'damaging' a pre sheaf when extending it: https://intranet.csc.liv.ac.uk/~frank/publ/cons.pdf). Thanks for the replies!

John Baez (May 10 2024 at 07:10):

Sure. Now I'll finally ask: what's "over-integrating"?

Morgan Rogers (he/him) (May 10 2024 at 08:25):

John Baez said:

I think the counterexample functor $F: C \to D$ that I want is the inclusion of the "walking arrow" category, with an arrow $f: y \to z$ and no other morphisms but identities, into the "walking non-mono" category

Umm yes oops, the "non-" in "walking non-mono" was quite a significant omission on my part... Sorry for the confusion folks. And you only need to include the one arrow, I think the train of thought that led me to "composable pair" was the (largely unrelated) example of an essential geometric morphism which is not locally connected.

Kevin Carlson (May 10 2024 at 11:41):

Ryan, what’s this you’re saying about a pushout of monos not being mono, by the way? This can’t happen in a topos, right? Maybe you mean something different than what I’m thinking of.

John Baez (May 10 2024 at 16:26):

I'd like to ask about the converse of something we've seen in this thread.

We start with a functor $F: C \to D$ between categories. From this we get a functor $F^\ast: \widehat{D} \to \widehat{C}$ between their presheaf categories given by precomposition with $F^{\textrm{op}} \colon C^{\textrm{op}} \to D^{\textrm{op}}$. Then we look at the left adjoint of that, say $\widehat{F} : \widehat{C} \to \widehat{D}$. We've seen that if $F$ fails to preserve monics, so does $\widehat{F}$. What about this: if $F$ preserves monics, must $\widehat{F}$ preserve monics?

Ryan Wisnesky (May 10 2024 at 18:00):

report.pdf
Here's the paper about the mono pushout property. Not sure about topoi, but the mono pushout property holds in Set and Ab and fails in Cmon and CRing if I understand that paper correctly. @Kevin Carlson

Ryan Wisnesky (May 10 2024 at 18:26):

Screenshot-2024-05-10-at-11.17.03AM.png
@John Baez "over integration" is the failure of Sigma_F(I), considered as a theory, to be conservative over I, considered as a theory, when both theories extend a common theory (say integers or strings). In data integration, the common theory is usually the data types- strings, integers, etc, and I is an attributed copresheaf over the common theory, and non-conservativity means that Sigma_F(I) proves a fact about strings/integers etc that I does not, probably indicating an error (i.e., we don't usually want 1 = 2 in Sigma_F(I) if 1 != 2 in I). The paper I mentioned above, 'Did I damage my ontology', describes this phenomenon in the context of description logic. I've attached a screen shot of an example in CQL, where we are moving data from a schema about people with salaries and ssns to a schema where salaries and ssns must be equal. For some inputs this over-integrates, in the sense that if you have a person with salary 1 and ssn 2, then in the Sigma'd result you have 1 = 2. So it's natural to look for conditions on F which guarantee this can't arise (and I think we have such a result, I'm asking David; it might answer your most recent question). In the non-attributed case, you can make this precise using different machinery, which I can describe if there's interest.

Kevin Carlson (May 10 2024 at 18:54):

Ryan Wisnesky said:

report.pdf
Here's the paper about the mono pushout property. Not sure about topoi, but the mono pushout property holds in Set and Ab and fails in Cmon and CRing if I understand that paper correctly. Kevin Carlson

Oh I see, you have funny pushouts in the algebraic theory of the attributes, sure. Yeah, pushouts of monos are mono in any topos, so any presheaf category, or any abelian category.

Kevin Carlson (May 10 2024 at 19:00):

John Baez said:

I'd like to ask about the converse of something we've seen in this thread.

We start with a functor $F: C \to D$ between categories. From this we get a functor $F^\ast: \widehat{D} \to \widehat{C}$ between their presheaf categories given by precomposition with $F^{\textrm{op}} \colon C^{\textrm{op}} \to D^{\textrm{op}}$. Then we look at the left adjoint of that, say $\widehat{F} : \widehat{C} \to \widehat{D}$. We've seen that if $F$ fails to preserve monics, so does $\widehat{F}$. What about this: if $F$ preserves monics, must $\widehat{F}$ preserve monics?

No; if $D$ is terminal then $\widehat F$ just takes a colimit. $F$ will always preserve monos since the only map in $D$ is a mono, but colimit functors don’t always preserve monos, even when the colimits are in Set. Coequalizers are the easiest counterexample: if you make a relation on a fixed set bigger, that gives a mono of parallel pairs, but it makes the coequalizer/set of equivalence classes smaller.

Kevin Carlson (May 10 2024 at 19:06):

Similar problems happen with pushouts; in fact the colimits that commute with pullbacks in Set are precisely the coproducts of filtered colimits. Since in general $\widehat F$ is a left Kan extension, which involves taking colimits along a bunch of comma categories $F/d$, maybe we could show that in general $\widehat F$ preserves monos if and only if $F$ does and all the $F/d$ are coproducts of filtered categories (ie have filtered connected components.)

John Baez (May 11 2024 at 08:44):

Thanks!

Morgan Rogers (he/him) (May 11 2024 at 16:20):

Morgan Rogers (he/him) said:

On the other hand, the free monoid on two elements isn't right Ore so the terminal functor on that category gives an example where all monos are trivially preserved but the extension still doesn't preserve monos!

Although it was preceded by a confusing sentence, I did give an answer to your question before you asked it @John Baez :sweat_smile:

John Baez (May 11 2024 at 16:44):

Okay, true. I think anytime I see the term "Ore" my mind blanks out and I find myself in a gutter later that night.