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: community: general

Topic: Counterexamples in Category Theory

Joshua Meyers (Mar 14 2021 at 16:15):

"Counterexamples in Category Theory" -- a book that I'd like to exist, similar to "Counterexamples in Topology" and "Counterexamples in Analysis". Or maybe a website.

When doing category theory it often seems as if everything always works out. I'd like to have a clearer sense of what can go wrong. For example, when are there two functors $F,G:C\to D$ that seem to convey the same information, and there is an family of isomorphisms $(\alpha_c:Fc\to Gc)_{c\in C}$ between them, but this isomorphism is not natural? Is there any "naturally occurring" situation where we have all the data of a monoidal category, except coherence fails?

Joshua Meyers (Mar 14 2021 at 16:16):

For this we would need to define "naturally occurring", which would probably be a syntactic definition.

Joshua Meyers (Mar 14 2021 at 16:17):

So a large class of counterexamples would be of the form: a "syntactically nice" situation which is not "categorically nice".

Joshua Meyers (Mar 14 2021 at 16:17):

It would also be great to get some theorems of the form: every "syntactically nice" situation is "categorically nice". Such theorems would save people (e.g. me) a lot of time proving stuff!

Jules Hedges (Mar 14 2021 at 16:29):

I like this idea, in fact I speculated about this exact idea before. There's a specific barrier to making it work: the "counterexamples" series really is doing 2 things at once. One is constructing a big bank of weird examples of topological spaces that are useful to have around. The other is to show that various hierarchies of properties of topological spaces are sharp, that all the implications between them are strict implications. That second thing doesn't really work in category theory, I think, because we generally don't get long hierarchies of properties like in general topology

Joshua Meyers (Mar 14 2021 at 16:36):

That's true, but I don't think it's much of a barrier. Just means we'll have to look elsewhere for our counterexamples than making hierarchies of properties sharp.

Joshua Meyers (Mar 14 2021 at 16:37):

As for the first thing, I think it's too easy to come up with toy examples of structures that don't have some property that is common "in nature". The more interesting thing would be to find counterexamples "in nature". Which then leads to the question of how to make "in nature" precise. I say, define it syntactically, but I don't know if that would work.

Jules Hedges (Mar 14 2021 at 16:41):

I've definitely encountered some oddities that sharpened my intuition and made me more paranoid about proving stuff. The craziest was one of the early failed ideas for defining Bayesian open games (which had Bayes' law baked into the monoidal product, making it extremely different to the true definition) - the resulting thing turned out to satisfy every axiom of a monoidal category except for naturality of the associator

Jules Hedges (Mar 14 2021 at 16:43):

Another oddity that I still don't properly understand about 8 years after I first encountered it (from a referee rejecting my paper) is the obvious way to define the ! modality of a dialectica category, which is very obviously a comonad...... except that it isn't

Joshua Meyers (Mar 14 2021 at 16:43):

Yeah this would be the sort of stuff that belongs in the book, maybe pared down to make a "minimal working example" that illustrates why it doesn't work.

Joshua Meyers (Mar 14 2021 at 16:45):

I just encountered the tangent bundle functor, which seems like a comonad, except it isn't (except it is??)

Jules Hedges (Mar 14 2021 at 16:47):

Another quite well known one: If you take any noncommutative strong monad (on Set, say), the "obvious" monoidal product on its kleisli category satisfies every axiom of a monoidal category except for bifunctoriality (but it's individually functorial in both arguments). It's so common that "a thing that's a monoidal category except for bifunctoriality" was given its own name, premonoidal category

Martti Karvonen (Mar 14 2021 at 16:49):

Another counterexample is that taking the skeleton of a monoidal category (say Set) does not in general result in a strict monoidal category, see: https://mathoverflow.net/a/128629

Joshua Meyers (Mar 14 2021 at 16:51):

Yes, in general, you cannot simultaneously strictify and skeletalize a monoidal category.

Joshua Meyers (Mar 14 2021 at 16:55):

Joshua Meyers said:

I just encountered the tangent bundle functor, which seems like a comonad, except it isn't (except it is??)

Never mind there's no contradiction, the latter comment says that the cotangent bundle is a comonad

Martti Karvonen (Mar 14 2021 at 17:00):

I guess there's all these cases where people wrote down a tentative distributive law between two monads and assumed it'll work out but turns out there was no distributive law at all. I think some of the history is recounted here: https://arxiv.org/abs/2003.12531 and @Dan Marsden probably knows examples where people fell for this mistake

Jules Hedges (Mar 14 2021 at 17:03):

Joshua Meyers said:

For this we would need to define "naturally occurring", which would probably be a syntactic definition.

So a book (?) like this could work along these lines if it's possible, which would make it a research project, or it could be just a bunch of people recording stuff that they personally find weird, organised by topic

Martti Karvonen (Mar 14 2021 at 17:05):

Monadic functors don't compose: torsion-free abelian groups are monadic over abelian groups which are monadic over sets, but the composite is not monadic (this is in Borceux vol 2 Counterexample 4.6.4)

John Baez (Mar 14 2021 at 17:10):

Nice, @Martti Karvonen! I always use the example that categories are monadic over reflexive graphs and reflexive graphs are monadic over sets but categories are not monadic over sets, but yours has more of a traditional algebra flavor.

Here's a nice counterexample: the map $Z: \mathsf{Gp} \to \mathsf{AbGp}$ sending any group to its center is not a functor. I got this one from James Dolan.

Fabrizio Genovese (Mar 14 2021 at 17:12):

Jules Hedges said:

Another quite well known one: If you take any noncommutative strong monad (on Set, say), the "obvious" monoidal product on its kleisli category satisfies every axiom of a monoidal category except for bifunctoriality (but it's individually functorial in both arguments). It's so common that "a thing that's a monoidal category except for bifunctoriality" was given its own name, premonoidal category

I encountered these things as well at some points. I have a quite wild conjecture that says that premonoidal categories are presented by Petri nets with inhibitor arcs, maybe one day...

Martti Karvonen (Mar 14 2021 at 17:13):

Similarly, sending an object of a category to its automorphism group does not give a functor to groups in general. Isotropy (e.g. discussed here https://www.sciencedirect.com/science/article/pii/S1571066118300914 ) gives for any category (modulo size issues) a functor to groups that in some sense fixes this

John Baez (Mar 14 2021 at 17:16):

@Joe Moeller, John Foley and I wrote a paper Network models from Petri nets with catalysts where we thought we got a monoidal category and it turned out to be premonoidal. I temporarily fell in love with premonoidal categories.

Martti Karvonen (Mar 14 2021 at 17:19):

Oddly, dagger monadic functors are closed under composition, but I'm not sure there's much one can do with that.

John Baez (Mar 14 2021 at 17:20):

Martti Karvonen said:

Similarly, sending an object of a category to its automorphism group does not give a functor to groups in general.

Yes! Similarly for the endomorphism monoid of an object.

Both the endomorphism monoid of an a set and the center of a monoid are examples of the "generalized center" construction that James Dolan and I described in Higher-dimensional algebra and topological quantum field theory. In general this takes a k-tuply monoidal n-category and gives you a (k+1)-monoidal n-category. So, it moves you down one notch on the periodic table. A very famous case is the generalized center of a monoidal category, which is a braided monoidal category.

John Baez (Mar 14 2021 at 17:24):

Jules Hedges said:

Joshua Meyers said:

For this we would need to define "naturally occurring", which would probably be a syntactic definition.

So a book (?) like this could work along these lines if it's possible, which would make it a research project, or it could be just a bunch of people recording stuff that they personally find weird, organised by topic.

I think a wiki might be a good way to do this. There's something called the nLab that could do the job, but if people are reluctant to set up a page called "Counterexamples in category theory" there they could set up their own wiki. Urs Schreiber pushed for creation of the nLab because people were contributing lots of interesting facts in some n-Category Cafe conversations, but it's sort of hard to search blog articles for these facts.

Fawzi Hreiki (Mar 14 2021 at 17:34):

I find it difficult to imagine a surprising counter example in category theory which is actually pure category theory (as opposed to a counter example from another field just restated in categorical language)

Jules Hedges (Mar 14 2021 at 17:39):

Most of the examples in this thread so far look like pure category theory to me

Matteo Capucci (he/him) (Mar 14 2021 at 17:49):

I got very spooked when sometime ago @John Baez mentioned he once stumbled upon two functors $F$, $G$ such that $Hom(FA, B) \cong Hom(A, GB)$, except the isomorphism wasn't natural

John Baez (Mar 14 2021 at 17:54):

Yes, they were the "seemingly obvious" functors between $\mathsf{Petri}$ and $\mathsf{CMC}$, the category of Petri nets and the category of commutative monoidal categories. There's an adjunction between these, which is pretty important I think. The left adjoint $L$ is obvious, but there's a "wrong right adjoint" $R$ where an isomorphism $\mathrm{hom}(LA, B) \cong \mathrm{hom}(A,RB)$ exists but fails to be natural. @Jade Master and I got tripped up by this, and later @Mike Shulman showed us the right right adjoint.

John Baez (Mar 14 2021 at 17:55):

We probably should have mentioned the wrong right adjoint in our paper, but we just ran away from it, screaming.

Jules Hedges (Mar 14 2021 at 17:55):

Speaking from a lot of personal experience, it's very easy to become complacent (or lazy) with checking naturality especially, because it's often tedious and nearly always true for boring reasons...... right up until it's not, and then it blows up in your face

John Baez (Mar 14 2021 at 17:58):

Yup. Similar to how you need to look down now and then when you're walking along....

John Baez (Mar 14 2021 at 17:59):

watch out!

Martti Karvonen (Mar 14 2021 at 18:16):

John Baez said:

Jules Hedges said:

Joshua Meyers said:

For this we would need to define "naturally occurring", which would probably be a syntactic definition.

So a book (?) like this could work along these lines if it's possible, which would make it a research project, or it could be just a bunch of people recording stuff that they personally find weird, organised by topic.

I think a wiki might be a good way to do this. There's something called the nLab that could do the job, but if people are reluctant to set up a page called "Counterexamples in category theory" there they could set up their own wiki. Urs Schreiber pushed for creation of the nLab because people were contributing lots of interesting facts in some n-Category Cafe conversations, but it's sort of hard to search blog articles for these facts.

I created an nlab page and added some of the examples mentioned here : https://ncatlab.org/nlab/show/counterexamples+in+category+theory However, more of the examples should be listed (and some references provided where need be). Moreover, I don't know how to link to this discussion as a source. Anyway, I need to do something else next so if anyone else has the energy to tweak the page, please go ahead!

Martti Karvonen (Mar 14 2021 at 18:17):

Arguably, if the list remains short, it could just be under https://ncatlab.org/nlab/show/counterexamples+in+algebra

Fawzi Hreiki (Mar 14 2021 at 18:20):

The category of topological spaces and local homeomorphisms is locally cartesian closed but it doesn't have a terminal object

Martti Karvonen (Mar 14 2021 at 18:20):

Add it to the nlab page?

Fawzi Hreiki (Mar 14 2021 at 18:21):

Sure

Mike Shulman (Mar 14 2021 at 18:41):

One of my favorites is that there are functors $D:\rm Aff\to Vect$ and $A:\rm Vect \to Aff$ between the categories of vector spaces and affine spaces, and we have $D(A(V)) \cong V$ for any $V\in\rm Vect$ and $A(D(U)) \cong U$ for any $U\in\rm Aff$, but the categories are not equivalent --- the second isomorphism is not natural.

Jade Master (Mar 14 2021 at 19:40):

John Baez said:

Yes, they were the "seemingly obvious" functors between $\mathsf{Petri}$ and $\mathsf{CMC}$, the category of Petri nets and the category of commutative monoidal categories. There's an adjunction between these, which is pretty important I think. The left adjoint $L$ is obvious, but there's a "wrong right adjoint" $R$ where an isomorphism $\mathrm{hom}(LA, B) \cong \mathrm{hom}(A,RB)$ exists but fails to be natural. Jade Master and I got tripped up by this, and later Mike Shulman showed us the right right adjoint.

Yes. If anyone wants more details on this, the wrong right adjoint to the functor $F : Petri \to CMC$ sends a commutative monoidal category $C$ to the Petri net whose source and target are $\eta \circ s : Mor(C) \to \mathbb{N}[Ob(C)]$ and $\eta \circ t : Mor(C) \to \mathbb{N}[Ob(C)]$ where s and t are the source and target of C and $\eta$ is the unit for the monad $\mathbb{N}$. In words, $C$ is sent to the Petri net whose source and target are the source and target of $C$ composed with $\eta$. We didn't talk about this failed attempt in Open Petri Nets...but I talked about it in Remark 4.4 of Petri nets based on Lawvere theories.

John Baez (Mar 14 2021 at 19:42):

Oh good, I'm glad it's in print there. People really should document problems like this.

Jade Master (Mar 14 2021 at 19:51):

Agreed. Anyway does anyone have a favorite functor which preserves limits but does not have a left adjoint? It might make a nice counterexample.

Fawzi Hreiki (Mar 14 2021 at 20:16):

Would the terminal functor $C \rightarrow 1$ for a category $C$ without an initial object count?

John Baez (Mar 14 2021 at 20:18):

That's nice! It gets a bit harder when we require that $C$ have all small limits.

John Baez (Mar 14 2021 at 20:19):

Your same example works but then $C$ needs to be kinda big.

Matteo Capucci (he/him) (Mar 14 2021 at 20:32):

I'm trying to edit the nLab space but my edit is being blocked by the spam filter

Matteo Capucci (he/him) (Mar 14 2021 at 20:33):

Does anyone know what could it be?

Matteo Capucci (he/him) (Mar 14 2021 at 20:36):

Ok splitting the edit worked

Matteo Capucci (he/him) (Mar 14 2021 at 20:37):

@Jade Master I added your counterxample by copying your message almost word by word, I hope you don't mind (I cited your paper, and this thread is being linked as soon as the archive does its magic)

Jade Master (Mar 14 2021 at 21:33):

@Matteo Capucci (he/him) Thank you I appreciate it :)

Jade Master (Mar 14 2021 at 22:05):

Oh whoops, I misremembered this adjunction. After reading what I wrote I realized that the problem with the choice I mentioned is that the natural choice of isomorphism $Hom(FP,C) \to Hom(P,UC)$ doesn't give well-defined morphisms of Petri nets. @John Baez is probably remembering a different adjunction. I'll change the nlab.

John Baez (Mar 14 2021 at 22:10):

What do you mean, "doesn't give well-defined morphisms between Petri nets"? You mean it doesn't really map to $\mathrm{hom}(P, UC)$ after all?

Jade Master (Mar 14 2021 at 22:44):

John Baez said:

What do you mean, "doesn't give well-defined morphisms between Petri nets"? You mean it doesn't really map to $\mathrm{hom}(P, UC)$ after all?

Yes. There are nice choices of functions for the supposed morphisms in the image of this isomorphism but they don't preserve sources and targets. So maybe they're not so nice after all.

Jade Master (Mar 14 2021 at 22:45):

I also added @Fawzi Hreiki's counterexample to the nlab.

Todd Trimble (Mar 15 2021 at 01:44):

Jade Master said:

Agreed. Anyway does anyone have a favorite functor which preserves limits but does not have a left adjoint? It might make a nice counterexample.

There are continuous functors $Grp \to Set$ with no left adjoint. Take a class of simple groups $G_\alpha$, one of each infinite cardinality $\alpha$. Then

$\prod_\alpha \hom(G_\alpha, -)$

makes sense as a functor from groups to sets: for any group $G$, the only morphism $G_\alpha \to G$ is the trivial one as soon as $\alpha$ is greater than the cardinality of $G$ by the simplicity of $G_\alpha$, so $\hom(G_\alpha, G)$ will be nontrivial for only a small number of $G_\alpha$. This product of representables preserves limits. But it can't be representable: for any group $G$, one can find $G_\alpha$ such that $\hom(G_\alpha, G_\alpha)$ is much larger in size than $\hom(G, G_\alpha)$.

John Baez (Mar 15 2021 at 01:46):

Here "small number" is used in a technical sense.

Todd Trimble (Mar 15 2021 at 01:47):

Same sense as in "small-complete": of set-sized cardinality.

John Baez (Mar 15 2021 at 01:50):

Yes, I was alerting newbies who might accidentally think "small number" might mean "like around 5".

Jade Master (Mar 15 2021 at 01:54):

Why can't this one have a left adjoint? Because it's not representable?

Todd Trimble (Mar 15 2021 at 01:57):

Oh right, forgot to mention. We have $Set(1, -) \cong Id_{Set}$, so for any functor $T: C \to Set$, we have $T \cong Set(1, T-)$. If $T$ has a left adjoint $S$, then $T$ is representable, because we have in that case

$T \cong Set(1, T-) \cong C(S1, -)$.

John Baez (Mar 15 2021 at 02:22):

Todd has been using this fact to good effect in our conversations about Schur functors with @Joe Moeller:

For any category $\mathsf{C}$, any right adjoint $T \colon \mathsf{C} \to \mathsf{Set}$ is representable.

Todd Trimble (Mar 15 2021 at 02:26):

And I've also been using this: if $C$ has small coproducts, then representables $\hom(c,-): C \to Set$ are right adjoints. The left adjoint $Set \to C$ takes a set $S$ to $S \cdot c$, the $S$-indexed coproduct of copies of $c$. (This operation is called "tensoring with $S$.)

Jules Hedges (Mar 15 2021 at 10:15):

John Baez said:

For any category $\mathsf{C}$, any right adjoint $T \colon \mathsf{C} \to \mathsf{Set}$ is representable.

Huh, I didn't know that and I immediately feel like I should have known it... it sounds useful...

Graham Manuell (Mar 15 2021 at 13:53):

Perhaps this should have been obvious, but I was very surprised when I first learnt that a monic natural transformation needn't have monic components. I don't know an example 'in nature' and things always work when the codomain category has pullbacks, but I think there is a counterexample where the codomain category is a coequaliser diagram and the domain has a single nontrivial arrow. This is related to the 'accidental' limits that can sometimes exist in functor categories when the componentwise limits fail to exist.

Spencer Breiner (Mar 15 2021 at 15:27):

John Baez said:

Here's a nice counterexample: the map $Z: \mathsf{Gp} \to \mathsf{AbGp}$ sending any group to its center is not a functor. I got this one from James Dolan.

Works for surjective homomorphism?

Jade Master (Mar 15 2021 at 15:45):

@Todd Trimble thank you for the counterexample. It is indeed very pathological. I might add it to the nlab article soon.

John Baez (Mar 15 2021 at 15:47):

Spencer Breiner said:

John Baez said:

Here's a nice counterexample: the map $Z: \mathsf{Gp} \to \mathsf{AbGp}$ sending any group to its center is not a functor. I got this one from James Dolan.

Works for surjective homomorphism?

Yes, it's functorial for surjective homomorphisms.