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: Smallest category containing subsets of morphisms?

Alex Kreitzberg (Mar 24 2025 at 01:26):

So I had this idea, that we could start with a category, and choose subsets of morphisms from each of its homsets.

In general this collection of subsets won't be a category, but there is at least one category that contains them, the one we started with.

But there could be lots of other subcategories containing our chosen collection of subsets.

Intuitively it seems to me there should be a smallest one of these, the one that contains all of the compositions of morphisms from our subsets.

But [[subcategory]] emphasizes that one should approach such constructions with care, because you have to think about the principle of equivalence.

It seems like my intuition can be made to work, but there are steps along the way to making that happen, do folks have advice on how to use the above intuition to define the subcategory generated by a given collection of subsets of a category?

Kevin Carlson (Mar 24 2025 at 03:14):

You don't have to think about the principle of equivalence, it's just often a good idea. There aren't any police empowered to write you tickets for this kind of thing! If you don't worry about that, then, yeah, you just take the intersection of all the subcategories containing all your chosen arrows to get the smallest one you want. This kind of "intersection of a big set of subsets which I know is nonempty" procedure is a very common way to construct closures.

Mike Shulman (Mar 24 2025 at 19:26):

If you do want, or need, to think about the principle of equivalence, then the first question to ask is what notion of "subcategory" you mean, since the very notion of non-full subcategory is not equivalence-invariant. What examples do you have in mind?

Alex Kreitzberg (Mar 24 2025 at 21:51):

I guess for what I'm trying to understand, is say I want to "master" a given category $C$, maybe I'm trying to learn all the symmetries of some object or something.

I'll get used to some arrows of the category $C$ first.

Now, assuming I can comfortably compose these "basic arrows", what subcategory describes the morphisms I can make given the morphisms I've learned so far.

So if I have an Octogon, and I learn I can rotate it once, "I can now perform" any cyclic symmetry in $C^8$. If I am able to perform $\{r, f\}$, so I'm able to rotate and flip, then I get the entire group and I'm done, I've "mastered the group".

So I guess the technical problem I'm solving is, "How do I know when a collection of morphisms of a category generate the entire category?", and one way to know is "Well I know I haven't succeeded if the closure of the subset of arrows of the category is 'too small'".

I think equivalence is worth thinking about here, because a would be subcategory can actually be equivalent to the whole category. That will usually happen in a contractible groupoid for example. In this case it's fair to say "if you are familiar with one of the objects of a groupoid, you're familiar with all of them".

It's like how there's an infinite number of ways to define a product, but once we've established there's only a contractible groupoids worth of them, we don't need to stress ourselves out getting familiar with all of them.

Ryan Wisnesky (Mar 24 2025 at 22:35):

If "how do I know when a collection of morphisms in a category generates the entire category" reduces to checking if two presentations of a category are equivalent, then this problem will be undecidable

Kevin Carlson (Mar 24 2025 at 22:37):

I don't think "a subcategory being equivalent to the whole category" is particularly interesting, but the inclusion being an equivalence is.

Alex Kreitzberg (Mar 25 2025 at 00:40):

Ryan Wisnesky said:

If "how do I know when a collection of morphisms in a category generates the entire category" reduces to checking if two presentations of a category are equivalent, then this problem will be undecidable

It's so hard to ask questions that have answers :laughter_tears:.

Kevin Carlson said:

I don't think "a subcategory being equivalent to the whole category" is particularly interesting, but the inclusion being an equivalence is.

This is such a sharp distinction, I feel like in trying to answer the first part, I would naturally try to prove an inclusion is an equivalence. So now I'm not sure if I know whether I'm getting excited about the right stuff.

Making a temporary aside to my "category for drawing" thread - one idea I had for a "category of lines", was to note the Moore-path category was already a category, and then I could specify a subset of continuous paths I know a person can draw. Then I could ask "which lines do I get after I take the closure of such a family of lines?"

Practically speaking, I think that problem has been mostly solved with presentations, but I realized I was initially thinking about this by trying to take closures of morphisms.

So coming back to this thread, maybe I can take a big step back and ask, what do you think would be a good example of taking closures without thinking about equivalence? And what would be a good example of when thinking about equivalence is important when taking closures? Are these commonly related with presentations of categories?

My goal here for this thread is to ground my understanding of this operation irrespective of how my intuition got there (I really thought I asked a focused enough question, I hope this context helps).

Kevin Carlson (Mar 25 2025 at 01:57):

I don't see why the example you already gave involves thinking about equivalence. With the ideas your thoughts are calling up in my mind right now, I wouldn't be thinking about the principle of equivalence in any case. After all, if a subcategory's inclusion is an equivalence, then if you would just change it to span all the objects, you'd have the whole category. (That is, wide full subcategories are the whole category.) So I wouldn't really think this question would arise very naturally.

Alex Kreitzberg (Mar 25 2025 at 03:57):

Maybe it's a mix of getting distracted by the nlab article before I'm ready, and genuine curiousity about what equivalence preserves.

It seems like when I understand equivalence a little bit better, it's like looking behind a veil and seeing a deeper reality behind overtly concrete patterns.

Subcategories just seemed to me like a good excuse to bring up equivalence is all. If I'm getting ahead of myself that's good to know.

John Baez (Mar 25 2025 at 04:37):

Before getting into subtler issues, do you see how to prove the fact that given a category C and any set S of morphisms in C, the following three subcategories of C are equal:

1) the intersection of all subcategories of C whose setbof mophisms contains S

2) the smallest subcategory of C containing all the morphisms in S

3) the category whose objects are those objects that are sources and targets of morphisms in S, and whose morphisms are composites of morphisms in S (any finite number of morphisms in S, including 0, which needs to be handled carefully).

John Baez (Mar 25 2025 at 04:39):

We call any one of these the subcategory of C generated by S.

John Baez (Mar 25 2025 at 04:41):

(@Kevin Carlson said some of this, but I want to emphasize that proving categories 1, 2, and 3 are equal is a good little exercise. People often state a similar theorem about groups.)

Alex Kreitzberg (Mar 25 2025 at 22:08):

1 and 2 aren't bad. The "smallest subcategory of $C$ containing $S$", let's denote it $\langle S\rangle$, is defined by the universal property - for all subcategories $D \subset C$ if $S \subset D$ then $\langle S\rangle \subset D$.

Since the intersection of all subcategories that contain $S$ necessarily contain any such $D$ it satisfies this universal property.

I haven't seen 3 before.

Let's show it's a category first. Label this category $\langle S\rangle'$.

Let objects be objects of arrows in $S$,

And let its arrows be arrows of $C$ that are the composition of a finite sequence of arrows in $S$ plus identities of all the objects.

The identity and associativity properties are all inherited, but we need to verify its closed under composition.

Suppose we have two arrows, $f$ and $g$, then $f \circ g = (f_1 \circ f_2 \circ f_3 \ldots \circ f_n) \circ (g_1 \circ g_2 \ldots ,\circ g_m) = f_1 \circ f_2 \ldots \circ g_m \in \langle S\rangle '$

So the composition is in $\langle S\rangle'$ because it contains all finite compositions, and the composition of two finite compositions is still a finite composition. So we have a category.

Now, why is this the smallest such category?

We need to show $\langle S\rangle' \subset \langle S\rangle$

All the identities are contained by $\langle S\rangle$, and any finite list of arrows in $S$, are in every category containing $S$, and therefore their composition is in any category which contains $S$ and therefore is an arrow of $\langle S\rangle$

So we do have $\langle S\rangle' \subset \langle S\rangle$ so I'm willing to now drop the $'$ and just write $\langle S\rangle$.

You didn't ask for this, but I want to tie this together with presentations, because I've been thinking about those a lot, and they seem important here as well (or I'm at least confusing them with this concept).

The subset $S$ has an underlying graph, you can freely generate a category on this graph. Now, there is a Functor from this free category into $C$ that takes the generators to the arrows that inspired them from $S$. Now our freely generated category factors through the inclusion of $\langle S\rangle$ into $C$.

John Baez (Mar 28 2025 at 04:15):

All very nice! :+1:

Alex Kreitzberg (Mar 31 2025 at 19:49):

(deleted)