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: How do generators work?

John Onstead (Jan 07 2025 at 12:44):

I've recently been getting into learning more about generators. Say a category $M$ is monadic over $\mathrm{Set}$. Let $\mathrm{Sub}(X)$ be the subobject poset of an object $X$ in $M$ and $\mathrm{Sub}(U(X))$ the subset poset of the underlying set of $X$. Of course, there's a forgetful functor $U_X: \mathrm{Sub}(X) \to \mathrm{Sub}(U(X))$. However, instinctually, there should be a functor going the opposite direction: $\mathrm{Clos}: \mathrm{Sub}(U(X)) \to \mathrm{Sub}(X)$ that "closes" a subset under the operations of the algebraic structure. For instance, if a subset is a generator, this functor will send the subset to the maximal element of $\mathrm{Sub}(X)$ that represents $X$ itself.

My hypothesis is the following: $\mathrm{Clos}$ and $U_X$ are adjoint functors, and somehow this adjunction is "generated" by the fact that $M$ is monadic. If this is the case, then one gets an idempotent monad on $\mathrm{Sub}(U(X))$ that satisfies all the axioms of a closure operator. This would then exhibit generators as a special case of the more general abstract notion of "density under a closure operator".

My question is: is my hypothesis correct, and if so, then how does one prove it?

Todd Trimble (Jan 07 2025 at 16:20):

(Let $T$ denote a monad on $\mathsf{Set}$, so that your $M$ is of the form $T$-$\mathrm{Alg}$.)

It's a nice question, and the answer gets into the weeds of some important facts about $T$-$\mathsf{Alg}$, specifically the fact that this category has well-behaved image factorizations (it is a [[regular category]]), and images of algebra maps can be computed at the underlying set level. This takes some slight doing for general monads $M$, but see Theorem 2.6 here in the nLab.

First note that for any algebra $X$, the monad $T$ induces a monad $\tilde{T}$ on $\mathsf{Set}/UX$. It takes an object $f: S \to UX$ in the slice to the object

$TS \overset{Tf}{\to} TUX \overset{\alpha}{\to} UX$

where $\alpha$ is the $T$-algebra structure on $UX$ that comes from $X$. This is a pleasant and straightforward exercise which I'll leave to you.

The closure operator you want takes a subset $i: S \hookrightarrow UX$ to the image of the function $\tilde{T}(i) = (\alpha \circ Ti): TS \to UX$, as a subobject $\tilde{i}$ of $UX$. By "image", I mean the intersection of all subsets of the codomain through which the function factors, i.e., the smallest subset through which it factors.

(Incidentally, the taking of images can be viewed as part of an adjunction: we have an inclusion functor

$\mathrm{Sub}(UX) \hookrightarrow \mathsf{Set}/UX$

and the functor $\mathsf{Set}/UX \to \mathrm{Sub}(UX)$ that takes an object $f: A \to UX$ to $\mathrm{im}(f) \in \mathrm{Sub}(UX)$ is the left adjoint to this inclusion. Notice by the way that the inclusion functor is full and faithful; equivalently, the counit of the adjunction is an isomorphism.)

So the claim is that $(i: S \hookrightarrow UX) \mapsto (\tilde{i}: \mathrm{im}(\alpha \circ Ti) \hookrightarrow UX)$ is a closure operator, i.e., defines a monad on $\mathrm{Sub}(UX)$. First we check for the unit inclusion $i \leq \tilde{i}$. Let

$TS \overset{q}{\to} \mathrm{im}(\alpha \circ Ti) \overset{j}{\to} UX$

be the image factorization of $\alpha \circ Ti$. Then the map from $S$ to $\mathrm{im}(\alpha \circ Ti)$ that witnesses $i \leq \tilde{i}$ is given by

$S \overset{\eta S}{\to} TS \overset{q}{\to} \mathrm{im}(\alpha \circ Ti)$

where $\eta: 1 \to T$ denotes the unit of the monad $T$.

For the inclusion $\tilde{\tilde{i}} \leq \tilde{i}$, we need a map from the following object $\phi$ in the slice,

$T(\mathrm{im}(\alpha \circ Ti)) \overset{T\tilde{i}}{\to} TUX \overset{\alpha}{\to} UX,$

to the subobject $\tilde{i}: \mathrm{im}(\alpha \circ Ti) \to UX$. This is where we use the fact that the image of an algebra map, as computed in $\mathsf{Set}$, carries a $T$-algebra structure: that gives you the map $T(\mathrm{im}(\alpha \circ Ti)) \to \mathrm{im}(\alpha \circ Ti)$ you need in the slice. Then, since this shows that $\phi$ factors through the subobject

$\tilde{i}: \mathrm{im}(\alpha \circ Ti) \to UX$

and the image of $\phi$, which is $\tilde{\tilde{i}}$, is the smallest subobject through which $\phi$ factors, we get $\tilde{\tilde{i}} \leq \tilde{i}$.

Finally, note that $\tilde{i}$ is a $T$-algebra map, so $i \mapsto \tilde{i}$ gives you the map $\mathrm{Sub}(UX) \to \mathrm{Sub}(X)$ you were expecting.

I haven't given every last detail, but this should be enough to go on.

Mike Shulman (Jan 07 2025 at 17:25):

Here's a more abstract argument. Suppose $C$ and $M$ are well-powered categories with all intersections of families of subobjects, and $U:M\to C$ is a functor that preserves monomorphisms and their intersections. (For instance, if $C$ is well-powered and complete, like Set, then any $M$ monadic over it is such.) Then since $U$ preserves monomorphisms, it induces a poset map $\mathrm{Sub}(X) \to \mathrm{Sub}(U(X)$ for any $X\in M$. And since $C$ and $M$ are well-powered and have arbitrary intersections and $U$ preserves them, these posets are small complete lattices and the map between them preserves arbitrary meets. Therefore, by the adjoint functor theorem for posets, this map has a left adjoint, and so the induced poset-monad on $\mathrm{Sub}(X)$ is a closure operator.

John Onstead (Jan 07 2025 at 18:20):

Thanks to both of you for your help! There's a lot to breakdown and review here which I will probably need to do for a bit...

John Onstead (Jan 08 2025 at 12:39):

So I've read through everything a few times and here are my thoughts. In general, I was surprised by how non-trivial this result is- to be honest, I was expecting there to just be some sort of composition or lifting I had just overlooked.

Here's what I tried to gather from the above. In my understanding, a "generator" of an algebraic object $A$ is a subset $S$ such that $A$ is a quotient of the free algebra on it $FS$. The quotient in turn is what allows one to include "relations", leading to the "presentation in terms of generators and relations". I'm not sure exactly what alpha is in the "straightforward exercise", but I do know that since $A$ is a coequalizer of a diagram involving $FUA$ by the canonical presentation, there is a canonical resulting projection $FUA \to A$ as part of the complete coequalizer diagram. That means, following $U$, there's a resulting morphism $TUA \to UA$ in $\mathrm{Set}$.

John Onstead (Jan 08 2025 at 12:41):

So one can think of this morphism as the restriction from the full free object on the underlying set to the algebraic object in question. Then, we proceed by identifying a subset $S \to UA$ and taking its free algebra $FS \to FUA$, but then we have to make sure we do the restriction on $FS$ just like we did on $FUA$ to make it back into a component of $A$, so this is why we have to compose $FS \to FUA \to A$, and then take the image. Anyways I'm really hoping I understood at least some of the stuff!

The only thing I don't see is why this doesn't work in general, even outside $\mathrm{Set}$? It doesn't really seem like, at any point in the above, you needed to know that the objects in the base category were sets. Plus, even if the base category doesn't have nice properties like colimits or powers, it shouldn't matter since the EM category always has the ability to do the necessary coequalizers on free objects as part of its defining property. Maybe it's because the image isn't always possible to construct? Or maybe I misunderstood a step (probably likely!)

Todd Trimble (Jan 08 2025 at 15:38):

to be honest, I was expecting there to just be some sort of composition or lifting I had just overlooked

If it helps, you can write out the monad on $\mathrm{Sub}(UX)$ as a composition

$\mathrm{Sub}(UX) \hookrightarrow \mathsf{Set}/UX \overset{\tilde{T}}{\to} \mathsf{Set}/UX \overset{\mathrm{im}}{\to} \mathrm{Sub}(UX).$

But I don't think it's immediate from this description that you actually get a monad.

I'm not sure exactly what alpha is in the "straightforward exercise",

You gave a correct description of $\alpha$ after you wrote this, but note that I had written "where $\alpha$ is the $T$-algebra structure on $UX$ that comes from $X$". What is $X$? It's some $T$-algebra. What is a $T$-algebra? It's a set $S$ (the underlying set, $S = UX$) together with a structural map $TS \to S$ obeying the $T$-algebra axioms. That map is your $\alpha: TUX \to UX$, and that's what I meant.

The only thing I don't see is why this doesn't work in general, even outside Set?

It does, as long as your base category is good enough. (I didn't know you wanted to go beyond $\mathsf{Set}$: you explicitly wrote about $\mathsf{Set}$ in your question, so that's what I went with.) Mike gave an alternative path which honestly I didn't think of, but even in his proof there you have to assume something about the base category, e.g., well-poweredness and existence of intersections.

it shouldn't matter since the EM category always has the ability to do the necessary coequalizers on free objects as part of its defining property. Maybe it's because the image isn't always possible to construct?

To get one thing out of the way: that the EM category has coequalizers generally is not automatic, and it's not even true generally: you have to assume some things. (See the flurry of results in section 2 of the nLab link I gave.) There are strange examples where the base category $C$ is something very reasonable, even locally presentable if I recall correctly (ah, see Example III.10 here) with a monad $T$ where the EM category doesn't have all coequalizers. (Mike's argument would still handle this type of example.)

So, how does one construct images? The way I was going about it, working in categories monadic over $\mathsf{Set}$, the image factorization of a map $f: X \to Y$ involves an epi followed by a mono,

$X \overset{p}{\twoheadrightarrow} \mathrm{im}(f) \overset{i}{\rightarrowtail} Y$

where the epi $p$ is intuitively thought of as taking an element $x \in X$ to its "$f$-equivalent class", where $x \sim_f y$ if $f(x) = f(y)$. To formalize this equivalence relation categorically, one can take the [[kernel pair]] of $f$, which is the pullback of $f$ along itself. Intuitively this pullback expresses the object $\{(x, y): f(x) = f(y)\}$. If $E$ is this pullback, with the two pullback projections $p_1, p_2: E \rightrightarrows X$ where for $(x, y) \in E$, $p_1(x, y) = x$ and $p_2(x, y) = y$, then coequalizer of $p_1, p_2$ is a map which identifies $x$ and $y$ whenever $(x, y)$ belongs to $E$. This coequalizer gives the desired epi $p: X \to \mathrm{im}(f)$. This is a tried-and-true way of constructing images in [[regular categories]]. In our situation, the map $f$ I wanted the image of is this composite

$TS \overset{Ti}{\to} TUX \overset{\alpha}{\to} UX$

construed as a map $TS \to X$ in the EM category (viewing $Ti$ and $\alpha$ as algebra maps), or perhaps you would prefer it if I said we're talking about the map $FS \to X$ that corresponds to $i: S \to UX$ under the adjunction $F \dashv U$.

Mike's argument can be seen as referring not to the epi end of things, but instead the mono end $i: \mathrm{im}(f) \to X$, where you consider instead the smallest subalgebra of $X$ through which this map $TS \to X$ factors, by taking the intersection of all subalgebras through which the map factors.

But instead of giving austere categorical arguments, let me try to give some more intuition based on concrete examples. For example, if the EM category is the category of vector spaces $X$, then the monad on $\mathrm{Sub}(UX)$ takes a subset $S \hookrightarrow UX$ to the vector subspace of $X$ that the subset $S$ generates. This subspace consists of all linear combinations $a_1 s_1 + \cdots + a_n s_n$ that you can form from elements $s_1, \ldots, s_n \in S$. Now the vector space $TS$, the free vector space on $S$, has for its elements formal linear combinations of elements in $S$, and then the map $TS \to X$ interprets those formal combinations as elements of the vector space $X$. We take the image of that map to get the subspace generated by $S$, i.e., the closure of $S$ under the vector space operations.

In general, any monad $T$ on $\mathsf{Set}$ can be thought of in terms of an algebraic theory of operations on sets, and the procedure of the last paragraph generalizes, to close up the subset $S$ under all the operations of the theory. You can look at the crucial aspect of this, taking the image of this $TS \to X$, either from the epi end or the mono end.

Mike Shulman (Jan 08 2025 at 16:00):

Todd Trimble said:

it shouldn't matter since the EM category always has the ability to do the necessary coequalizers on free objects as part of its defining property. Maybe it's because the image isn't always possible to construct?

To get one thing out of the way: that the EM category has coequalizers generally is not automatic, and it's not even true generally: you have to assume some things.

In case it clears up some confusion, the EM category does always have some coequalizers, specifically the split coequalizer presentation $FUFUA \rightrightarrows FUA \to A$ of any object $A$. But the coequalizer you need to construct the image, as an object of the EM category, is not of this form.

Mike Shulman (Jan 08 2025 at 16:05):

To expand a bit on the intuition for my argument, as Todd said it's based on the general idea that the subalgebra $\langle S\rangle$ generated by a subset $S\subseteq UX$ is "the smallest subalgebra of $X$ that contains $S$". The invocation of the adjoint functor theorem is just a highfalutin' way of saying that $\langle S \rangle$ is the intersection (wide pullback) of all the monomorphisms $Y \rightarrowtail X$ such that $S\hookrightarrow UX$ factors through $UY \rightarrowtail UX$, which corresponds in concrete cases to how one can construct $\langle S \rangle$ abstractly as an intersection of subalgebras (rather than, as in Todd's description, the set of linear combinations etc.).

John Onstead (Jan 08 2025 at 20:26):

Todd Trimble said:

So, how does one construct images? The way I was going about it, working in categories monadic over Set, the image factorization of a map $f: X \to Y$ involves an epi followed by a mono,

Ok, that helps to clear things up! That's why when working over Set we can always find the image, because the category of algebras is a regular category and so has this factorization system. So we can always take a coequalizer of a kernel pair... but this might not be true for monadic categories for a base other than Set. Also, yes, as Mike suggests when I was talking about coequalizers I meant specifically the ones for generators and relations. I didn't know images could be given as a coequalizer until now!

Todd Trimble said:

Now the vector space $TS$, the free vector space on $S$, has for its elements formal linear combinations of elements in $S$, and then the map $TS \to X$ interprets those formal combinations as elements of the vector space $X$. We take the image of that map to get the subspace generated by $S$, i.e., the closure of $S$ under the vector space operations.

Thanks, this example helped! I suspected the map from the free algebra to the algebra in question was a form of "restriction", and so composing with it would be the necessary restriction of elements of the free algebra for a subset to a part of that algebra. But now I see you can interpret this "restriction" as sending formal linear combinations to realizations of those formal combinations as elements of the actual vector space being worked in.

John Onstead (Jan 08 2025 at 20:30):

Mike Shulman said:

But the coequalizer you need to construct the image, as an object of the EM category, is not of this form.

Ok, so it seems I was right in my assumption that the existence of the image is the main roadblock to defining this closure operator in general. Since if the coequalizer of the kernel pair, or if the wide pullback of all monomorphisms that our subobject factors through, does not exist, then this monad will also fail to exist. The adjoint functor theorem, when applied to this problem, then gives the conditions in which such an image construction will exist. And that's probably what requires the category to be well powered and all that.

Todd Trimble (Jan 08 2025 at 21:14):

when I was talking about coequalizers I meant specifically the ones for generators and relations

Yes, I think maybe you meant even more specifically coequalizers of type

$FUFUA \overset{\varepsilon FUA}{\underset{FU \varepsilon A}{\rightrightarrows}} FUA \overset{\varepsilon A}{\to} A$

where $\varepsilon$ is the counit of the free-forgetful adjunction. Generally, though, when people speak of a generators and relations presentation of a $T$-algebra $A$, they refer to a coequalizer more general than that specific type of coequalizer, something that could be put in the form

$FR \rightrightarrows FS \to A$

where typically $R$ is a set of "relations" or equations that you want to mod out $FS$ by (via a coequalizer) in order to get $A$. So for example, when people write down a group presentation like $\langle x, y|x^2 = y^3 \rangle$, you would have $S = \{x, y\}$, and $R$ the singleton set $\{t\}$ where $t$ is a formal variable standing in for the equation "$x^2 = y^3$", where one of the arrows $FR \to FS$ takes $t$ to $x^2$ and the other takes $t$ to $y^3$. So $S$ is the set of generators, and $R$ is the set of relations or equations to be imposed.

The specific sort of coequalizer I think you were referring to might be called the "canonical" presentation of an algebra $A$. They are theoretically important, but they are too "tautological" to be of much benefit for the down and dirty job of describing complicated objects $A$ -- for example, maybe it's important to know whether $A$ is finitely presented, where the $R$ and $S$ are finite sets. The canonical presentation would of course be useless for settling this.

John Onstead (Jan 08 2025 at 21:27):

Todd Trimble said:

The specific sort of coequalizer I think you were referring to might be called the "canonical" presentation of an algebra

Right, I was being kind of loose with my terminology! Though in a sense this canonical coequalizer is the "most important" one since one can use it as we did above in the derivation of the "closure" of a subset under the operations of an algebraic structure. Thus any other generator presentation can be derived from this one, since if the image of the morphism we derived for some subset is that of the entire algebraic structure, that subset is a generator of the algebraic object. So the object can be expressed as a coequalizer involving the free algebra on the subset.

Mike Shulman (Jan 08 2025 at 21:50):

No, the coequalizer used in defining closure isn't one of the canonical ones. That was Todd's point about why the EM category not having all coequalizers is relevant.

John Onstead (Jan 08 2025 at 22:14):

Alright, I think I understand the basics of generators and how they work. Now I want to try and extend this reasoning to new contexts. In mathematics, there's many situations in which a small subset of a thing generates the rest of the elements of that thing under some operation. Usually, this is given as presentation of an algebraic structure in terms of a generator. For example, as we know, given a basis of a vector space, one may express any other element of the vector space as a sum of scalar multiples of the basis vectors.

A similar thing happens in a presheaf category. In this case, the "small subset" is the representables, and the operation is taking a colimit. This allows one to express any object of the presheaf category as a colimit over representables- in a sense, the representables form a "basis" or "generator" of the presheaf category. My question is: is there any way to formalize this analogy? That is, is there some way to "decategorify" a presheaf category into an algebraic object of some form such that the set of representables is then literally the generator? Or going another way- is the category of presheaf categories equipped with the colimit operation monadic over Set or Cat, in which case we can take a more direct approach and realize the Yoneda embedding directly as a generator?

Mike Shulman (Jan 09 2025 at 01:35):

The category of cocomplete categories (= large categories with all small colimits) is monadic over CAT (the very-large 2-category of large categories). Presheaf categories are then the algebras for this monad that are freely generated by some small category.

John Onstead (Jan 09 2025 at 02:44):

Mike Shulman said:

The category of cocomplete categories (= large categories with all small colimits) is monadic over CAT (the very-large 2-category of large categories). Presheaf categories are then the algebras for this monad that are freely generated by some small category.

Wow! That's really cool! I think it's really interesting that the presheaf categories can be thought of as being free objects since the two concepts have a lot in common, namely when it comes to some sort of a "maximal enlargement" of a set or category. This gives a really nice "category-centric" example of thinking about generators, free algebras, and non-free algebras.

John Onstead (Jan 14 2025 at 12:32):

I wanted to return briefly to this discussion of generators because I had an interesting thought. Could generators be seen as a generalized form of "self similarity"? For instance, the most common example of self-similarity in math is in fractals. One can think of a self-similar fractal as having a subset that, in some sense, "generates" the rest of the set through the operation of rescaling (as well as perhaps translation and rotation if needed). This seems quite similar to how some algebraic objects have a generator, a subset that generates the rest of the set by the algebraic operation. By any chance, is there any way to view self-similarity as an actual generator in the sense of abstract algebra?

Todd Trimble (Jan 14 2025 at 13:18):

If you would like to view self-similarity through a categorical lens, then a good place to start would be the work of Tom Leinster, for example here.

Mike Shulman (Jan 14 2025 at 16:07):

It might be relevant to consider the category of "sets equipped with an endomorphism". In that category, given an object $(X, f:X\to X)$ and a subset $S\subseteq X$, the subobject of $X$ generated by $S$ is the set of everything in $X$ that you can get to by starting with something in $S$ and iterating $f$ on it some finite number of times.

John Onstead (Jan 14 2025 at 20:01):

Todd Trimble said:

If you would like to view self-similarity through a categorical lens, then a good place to start would be the work of Tom Leinster, for example here.

Thanks! It seems he goes in a different direction with the idea, but it is still fascinating nonetheless! I'm also intrigued by the relationship drawn between self similarity and systems of equations, since those are two concepts I would not otherwise have found to be related.

Mike Shulman said:

It might be relevant to consider the category of "sets equipped with an endomorphism". In that category, given an object $(X, f:X\to X)$ and a subset $S\subseteq X$, the subobject of $X$ generated by $S$ is the set of everything in $X$ that you can get to by starting with something in $S$ and iterating $f$ on it some finite number of times.

Ah, so this is like a category of "dynamical systems". I didn't know that it was monadic! But this does make sense, thanks! (By the way, would you know which monad this comes from?)

Todd Trimble (Jan 14 2025 at 20:06):

It's the category of $\mathbb{N}$-sets (sets equipped with an action of the monoid $\mathbb{N}$).

John Onstead (Jan 14 2025 at 20:15):

Thanks!