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: free cartesian category for dummies

Asad Saeeduddin (Sep 05 2021 at 06:18):

Hello there. I was wondering if it's possible to simplify the article given here https://ncatlab.org/nlab/show/free+cartesian+category. The article seems to explain everything in terms of the free coproduct cocompletion to start with, then dives into some 2-categorical business. Would it be significantly more complicated to just write out the hom structure of the free cartesian category directly?

Jules Hedges (Sep 05 2021 at 09:51):

It's totally possible to do it directly. If you know a bit of formal logic then you basically already know the construction: morphisms in the free cartesian category are (certain equivalence classes of) proofs in a logic that has "and" as its only connective. I think this might be what section 3 is trying to say...

Simon Burton (Sep 05 2021 at 13:07):

Looking at the history page for this article, yep, it's another well thought out article by Todd Trimble. It seems that so many of the good nlab pages are the ones that Todd wrote, or mainly wrote.

John Baez (Sep 05 2021 at 16:56):

It's absolutely fundamental that the category P(C) of presheaves on a category C is what you get by freely cocompleting C.

John Baez (Sep 05 2021 at 16:57):

So, it's very natural to want to describe other cocompletions of C, where you freely throw in just some colimits, as subcategories of P(C).

John Baez (Sep 05 2021 at 16:58):

For example, if you want to freely throw in just coproducts, you take the full subcategory of P(C) where the objects are just coproducts of representable presheaves. (Remember, by Yoneda the representables give you a copy of C sitting inside P(C).)

John Baez (Sep 05 2021 at 17:00):

Or if you want to freely throw in products, you just twist this idea around using "op": you take the full subcategory of $P(C^{\textrm{op}})$ where the objects are just coproducts of representable presheaves, and then take the opposite of that!

John Baez (Sep 05 2021 at 17:02):

But yes, there's another way to take C and freely throw in products. I find it less stressful to think about freely throwing in finite products. Then you build a category where the objects are finite lists of objects in $C$, and morphisms are "the obvious things".

John Baez (Sep 05 2021 at 17:21):

It's a wee bit easier for the free symmetric monoidal category on C. Here objects are finite lists of objects in C, and a morphism from $(c_1, \dots, c_n)$ to $(c'_1, \dots, c'_n)$ is a permutation $\sigma \in S_n$ together with morphisms $f_i : c_i \to c'_{\sigma(i)}$.

(Don't sue me if that last $\sigma$ should be a $\sigma^{-1}$; you can just draw the string diagrams and see what works.)

John Baez (Sep 05 2021 at 17:23):

For the free category with finite products on C, you need to use functions instead of just permutations, and you need to get the functions going the right way, which I guess is backwards.

John Baez (Sep 05 2021 at 17:25):

For example: the free category with finite coproducts on the terminal category is $\mathrm{FinSet}$, so here the functions go forwards.

The free category with finite products on the terminal category is $\mathrm{FinSet}^{\rm op}$, so here the functions go backwards.

John Baez (Sep 05 2021 at 17:25):

In these examples the morphisms in our original category C are trivial: there's just the identity morphism. In general you need to "label" the functions with morphisms in C.

Asad Saeeduddin (Sep 06 2021 at 19:02):

@John Baez incredible, thank you so much. the correspondence between {bijections, "forward", "backward" functions} and the free {symmetric monoidal, cocartesian, cartesian} categories made this so much clearer for me

John Baez (Sep 06 2021 at 19:09):

Great, thanks!

Patrick Nicodemus (Sep 07 2021 at 08:59):

John Baez said:

It's absolutely fundamental that the category P(C) of presheaves on a category C is what you get by freely cocompleting C.

Very interesting. Can we extend this picture to the case where C is equipped with a Grothendieck topology and we consider the category of sheaves? Is there a way to modify "free cocompletion" in a way that accounts for this?

If F : C -> A is some diagram from a small cat C into a cocomplete category A, and C has a topology J, then it should be easy to write down a condition on A such that the 'nerve' functor which sends a to Hom(F(-),a) is valued in the subcategory of sheaves. For each a, and for each covering sieve {s_i} on c, any family of maps f_i : dom(s_i) -> a satisfying some coherence conditions should glue together into a unique map f : c -> a. But I'm not sure where, if at all, the topology would play in the associated 'realization' functor, I assume we would just restrict the domain to sheaves.

For the sake of argument, let's assume the topology is subcanonical.

Morgan Rogers (he/him) (Sep 07 2021 at 09:05):

Patrick Nicodemus said:

John Baez said:

It's absolutely fundamental that the category P(C) of presheaves on a category C is what you get by freely cocompleting C.

Very interesting. Can we extend this picture to the case where C is equipped with a Grothendieck topology and we consider the category of sheaves? Is there a way to modify "free cocompletion" in a way that accounts for this?

Yes: I believe that the composite of the Yoneda embedding with the $J$-sheafification functor is the universal functor sending $J$-covering sieves to universal effective epimorphic sieves (i.e. to colimit cocones which are stable under pullbacks); the subcanonicity requirement isn't needed.

Morgan Rogers (he/him) (Sep 07 2021 at 09:05):

I didn't really understand the remainder of your comment, though.

Patrick Nicodemus (Sep 07 2021 at 09:11):

Ok, cool. I guess that answers my question, can you provide any intuition for the 'effectiveness' condition? I'm not sure how pullbacks arise here, seems like a bit of a surprise to me. And sure, sounds like in the subcanonical case we would just be able to suppress reference to sheafification.

Patrick Nicodemus (Sep 07 2021 at 09:15):

to clarify the rest of the comment, in the usual case of presheaves, for any functor F : C -> A for C small and A cocomplete, there is a unique cocontinuous functor F' : \hat[C} -> A which I call the "realization" associated to F, and F' has a right adjoint, the "nerve" A -> \hat{C} sending a to the presheaf Hom(F(-),c). i was speculating on how these two were both altered when the topology was added

Fawzi Hreiki (Sep 07 2021 at 14:26):

Any functor $F: C \rightarrow E$ into a cocomplete category $E$ which sends $J$-covering sieves to universal effective epimorphic sieves factors uniquely through the restricted Yoneda embedding $C \rightarrow \text{Sh}(C, J)$.

Fawzi Hreiki (Sep 07 2021 at 14:27):

This is just the definition of what @Morgan Rogers (he/him) said above.

Morgan Rogers (he/him) (Sep 07 2021 at 15:08):

Patrick Nicodemus said:

Ok, cool. I guess that answers my question, can you provide any intuition for the 'effectiveness' condition? I'm not sure how pullbacks arise here, seems like a bit of a surprise to me. And sure, sounds like in the subcanonical case we would just be able to suppress reference to sheafification.

Colimits are universal/stable under pullback in any Grothendieck topos, but thinking about it there is no reason that this has to be the case in the codomain category of the functor being universally factored, so I'll roll that back. We only need to require that $J$-covering sieves become colimit cocones. Although what @Fawzi Hreiki is still certainly true as a special case.

Fawzi Hreiki (Sep 07 2021 at 15:20):

If $E$ is an elementary topos and $j$ is a topology on its subobject classifier, then the sheafification functor $E \rightarrow \text{Sh}_j(E)$ is the universal functor out of $E$ localising all the $j$-local isomorphisms (I believe).

Fawzi Hreiki (Sep 07 2021 at 15:20):

Combining this with the free cocompletion universal property of presheaf categories gives the universal property of sheaf categories.

Asad Saeeduddin (Sep 10 2021 at 13:04):

Sorry for the somewhat tangential question, but am I understanding correctly that the notion of "multigraph" referred to in the M-span business towards the end of https://ncatlab.org/nlab/show/free+cartesian+category is _not_ referring to the multigraphs of e.g. https://en.wikipedia.org/wiki/Multigraph, but instead to what are described here as "hypergraphs"?

Nathanael Arkor (Sep 10 2021 at 13:06):

By multigraph, they mean the analogue of a quiver for a multicategory, i.e. a directed multigraph where each edge can have multiple inputs.

Nathanael Arkor (Sep 10 2021 at 13:07):

This is like a "multicategory without composition".

Nathanael Arkor (Sep 10 2021 at 13:09):

It's not quite the same as a hypergraph, which doesn't specify source/targets. The terminology on that page is confusing, though; I think it ought to be changed.

Asad Saeeduddin (Sep 10 2021 at 13:16):

Ah yes, I admit I didn't actually read the Wikipedia definition, I just vaguely misremembered it to be the same as the one in https://www.sciencedirect.com/science/article/pii/0166218X9390045P

Asad Saeeduddin (Sep 10 2021 at 13:17):

(which describes "directed hypergraphs" aka multicategories without composition)

Nathanael Arkor (Sep 10 2021 at 13:20):

Asad Saeeduddin said:

(which describes "directed hypergraphs" aka multicategories without composition)

The directed hypergraphs of that paper appear to be more like "polycategories without composition", i.e. they permit multiple targets.

Antonin Delpeuch (Sep 17 2021 at 12:49):

One useful characterization of cartesian categories is as "symmetric monoidal categories with copying and discarding" (see https://ncatlab.org/nlab/show/cartesian+monoidal+category#properties), and so that makes it possible to think of free cartesian categories on a signature as a category of string diagrams. Perhaps it would be useful to describe that in this "free cartesian category" page?