## August 31, 2015

### Wrangling Generators for Subobjects

#### Posted by Emily Riehl Guest post by John Wiltshire-Gordon

My new paper arXiv:1508.04107 contains a definition that may be of interest to category theorists. Emily Riehl has graciously offered me this chance to explain.

In algebra, if we have a firm grip on some object $X$, we probably have generators for $X$. Later, if we have some quotient $X / \sim$, the same set of generators will work. The trouble comes when we have a subobject $Y \subseteq X$, which (given typical bad luck) probably misses every one of our generators. We need theorems to find generators for subobjects.

Category theory offers a clean definition of generation: if $C$ is some category of algebraic objects and $F \dashv U$ is a free-forgetful adjunction with $U : C \longrightarrow \mathrm{Set}$, then it makes sense to say that a subset $S \subseteq U X$ generates $X$ if the adjunct arrow $F S \rightarrow X$ is epic.

Certainly $R$-modules fit into this setup nicely, and groups, commutative rings, etc. What about simplicial sets? It makes sense to say that some simplicial set $X$ is “generated” by its 1-simplices, for example: this is saying that $X$ is 1-skeletal. But simplicial sets come with many sorts of generator…Ah, and they also come with many forgetful functors, given by evaluation at the various objects of $\Delta^{op}$.

Let’s assume we’re in a context where there are many forgetful functors, and many corresponding notions of generation. In fact, for concreteness, let’s think about cosimplicial vector spaces over the rational numbers. A cosimplicial vector space is a functor $\Delta \longrightarrow \mathrm{Vect}$, and so for each $d \in \Delta$ we have a functor $U_d : \mathrm{Vect}^{\Delta} \longrightarrow \mathrm{Set}$ with $U_d V = V d$ and left adjoint $F_d$. We will say that a vector $v \in V d$ sits in degree $d$, and generally think of $V$ as a vector space graded by the objects of $\Delta$.

Definition A cosimplicial vector space $V$ is generated in degree $d \in \Delta$ if the component at $V$ of the counit $F_d U_d V \longrightarrow V$ is epic. Similarly, $V$ is generated in degrees $\{d_i \}$ if $\oplus_i F_{d_i} U_{d_i} V \longrightarrow V$ is epic.

Example Let $V = F_d \{ \ast \}$ be the free cosimplicial vector space on a single vector in degree $d$. Certainly $V$ is generated in degree $d$. It’s less obvious that $V$ admits a unique nontrivial subobject $W \hookrightarrow V$. Let’s try to find generators for $W$. It turns out that $W d = 0$, so no generators there. Since $W \neq 0$, there must be generators somewhere… but where?

Theorem (Wrangling generators for cosimplicial abelian groups): If $V$ is a cosimplicial abelian group generated in degrees $\{ d_i \}$, then any subobject $W \hookrightarrow V$ is generated in degrees $\{d_i + 1 \}$.

Ok, so now we know exactly where to look for generators for subobjects: exactly one degree higher than our generators for the ambient object. The generators have been successfully wrangled.

### The preorder on degrees of generation $\leq_d$

Time to formalize. Let $U_d, U_x, U_y: C \longrightarrow \mathrm{Set}$ be three forgetful functors, and let $F_d, F_x, F_y$ be their left adjoints. When the labels $d, x, y$ appear unattached to $U$ or $F$, they represent formal “degrees of generation,” even though $C$ need not be a functor category. In this broader setting, we say $V \in C$ is generated in (formal) degree $\star$ if the component of the counit $F_{\star} U_{\star} V \longrightarrow V$ is epic. By the unit-counit identities, if $V$ is generated in degree $\star$ , the whole set $U_{\star} V$ serves as a generating set.

Definition Say $x \leq_d y$ if for all $V \in C$ generated in degree $d$, every subobject $W \hookrightarrow V$ generated in degree $x$ is also generated in degree $y$.

Practically speaking, if $x \leq_d y$, then generators in degree $x$ can always be replaced by generators in degree $y$ provided that the ambient object is generated in degree $d$.

Suppose that we have a complete understanding of the preorder $\leq_d$ , and we’re trying to generate subobjects inside some object generated in degree $d$. Then every time $x \leq_d y$, we may replace generators in degree $x$ with their span in degree $y$. In other words, the generators $S \subseteq U_x V$ are equivalent to generators $\mathrm{Im}(U_y F_x S \longrightarrow U_y V) \subseteq U_y V$. Arguing in this fashion, we may wrangle all generators upward in the preorder $\leq_d$. If $\leq_d$ has a finite system of elements $m_1, m_2, \ldots, m_k$ capable of bounding any other element from above, then all generators may be replaced by generators in degrees $m_1, m_2, \ldots, m_k$. This is the ideal wrangling situation, and lets us restrict our search for generators to this finite set of degrees.

In the case of cosimplicial vector spaces, $d + 1$ is a maximum for the preorder $\leq_d$ with $d \in \Delta$. So any subobject of a simplicial vector space generated in degree $d$ is generated in degree $d + 1$. (It is also true that, for example, $d + 2$ is a maximum for the preorder $\leq_d$. In fact, we have $d + 1 \leq_d d+2 \leq_d d + 1$. That’s why it’s important that $\leq_d$ is a preorder, and not a true partial order.)

### Connection to the preprint arXiv:1508.04107

In the generality presented above, where a formal degree of generation is a free-forgetful adjunction to $\mathrm{Set}$, I do not know much about the preorder $\leq_d$. The paper linked above is concerned with the case $C = (\mathrm{Mod}_R)^{\mathcal{D}}$ of functor categories of $\mathcal{D}$-shaped diagrams of $R$-modules. In this case I can say a lot.

In Definition 1.1, I give a computational description of the preorder $\leq_d$. This description makes it clear that if $\mathcal{D}$ has finite hom-sets, then you could program a computer to tell you whenever $x \leq_d y$.

In Section 2.2, I give many different categories $\mathcal{D}$ for which explicit upper bounds are known for the preorders $\leq_d$. (In the paper, an explicit system of upper bounds for every preorder is called a homological modulus.)

### Connection to the field of Representation Stability

If you’re interested in more context for this work, I highly recommend two of Emily Riehl’s posts from February of last year on Representation Stability, a subject begun by Tom Church and Benson Farb. With Jordan Ellenberg, they explained how certain stability patterns can be considered consequences of structure theory for the category of $\mathrm{FI}$-modules $(\mathrm{Vect}_{\mathbb{Q}})^{\mathrm{FI}}$ where $\mathrm{FI}$ is the category of finite sets with injections. In the category of $\mathrm{FI}$-modules, the preorders $\leq_n$ have no finite system of upper bounds. In contrast, for $\mathrm{Fin}$-modules, every preorder has a maximum! (Here $\mathrm{Fin}$ is the usual category of finite sets). So having all finite set maps instead of just the injections gives much better control on generators for subobjects. As an application, Jordan and I use this extra control to obtain new results about configuration spaces of points on a manifold. You can read about it on his blog.

For more on the recent progress of representation stability, you can also check out the bibliography of my paper or take a look at exciting new results by CEF, as well as Rohit Nagpal, Andy Putman, Steven Sam, and Andrew Snowden, and Jenny Wilson.

Posted at August 31, 2015 5:33 PM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2841

### Re: Wrangling generators for subobjects

Thanks for the post. A comment:

Category theory offers a clean definition of generation: if $C$ is some category of algebraic objects and $F \dashv U$is a free-forgetful adjunction with $U : C \longrightarrow \mathrm{Set}$ , then it makes sense to say that a subset $S \subseteq U X$ generates $X$ if the adjunct arrow $F S \rightarrow X$ is epic.

Certainly $R$-modules fit into this setup nicely, and groups, commutative rings, etc.

I’m not convinced that’s the right definition. Consider the theory of commutative rings (with 1) and the unique ring homomorphism $F(\emptyset) = \mathbb{Z} \to \mathbb{Q}$. This is epic, but is it really appropriate to say that $\emptyset$ “generates” the ring $\mathbb{Q}$?

The usual categorical story about presentation of algebras runs as follows. Take some algebraic theory — groups, for concreteness. We have the free-forgetful adjunction $F \dashv U$, and the induced monad $T = U F$.

Given a set $S$, the set $T S$ consists of all words in the variables (or “generators”) $S$. So, an equation (or “relation”) in these variables is an element of $T S \times T S$. So, a family of equations in a set $S$ of variables is a set $I$ together with a map $I \to T S \times T S$.

Equivalently, it’s a parallel pair of maps $I \stackrel{\to}{\to} T S$ in $Set$. Equivalently (by adjointness), it’s a parallel pair of maps $F I \stackrel{\to}{\to} F S$ in $Group$.

So: a group presentation consists of sets $S$ and $I$ and a pair of homomorphisms $F I \stackrel{\to}{\to} F S$. And the group presented by this presentation is exactly the coequalizer of this pair.

This suggests that (in your notation) $S \subseteq U X$ should be said to generate $X$ if the corresponding map $F S \to X$ is regular epic (that is, a coequalizer). One could perhaps argue for other variants such as strong or extremal epic, but the $\mathbb{Z} \hookrightarrow \mathbb{Q}$ example above suggests to me that “epic” is too weak.

Posted by: Tom Leinster on August 31, 2015 8:57 PM | Permalink | Reply to this

### Re: Wrangling generators for subobjects

Posted by: Qiaochu Yuan on August 31, 2015 9:33 PM | Permalink | Reply to this

### Re: Wrangling generators for subobjects

The word “generates” as used this way does however have its precedents in the literature. For example, in the old terminology, an object $x$ is (often said to be) a generator if, whenever one has distinct arrows $f, g \in \hom(y, z)$, there exists $h: x \to y$ such that $f h \neq g h$. The idea behind the terminology was essentially as given by John W-G: if the category has coproducts, then this condition is equivalent to saying that the canonical arrow $\hom(x, y) \cdot x \to y$ out of a copower of $x$ is an epimorphism to $y$, in other words for suitable categories you could use copies of $x$ to generate or span any $y$.

(Those “suitable categories” include abelian categories and set-valued sheaf categories, i.e., those categories which received the most attention in the early days of category theory. This may have been an influence on the naming.)

Nowadays, I think that terminology is somewhat deprecated and preferences are leaning toward calling such $x$ a separator, pretty much for the reasons Tom gave. I don’t know how widespread it is to define “generator” in terms of regular epis, as he suggests.

Posted by: Todd Trimble on August 31, 2015 11:08 PM | Permalink | Reply to this

### Re: Wrangling generators for subobjects

I have a fondness for the old usage of “generator” because it generalizes consistently; if $x$ is a “generator” when $hom(x,y)\cdot x\to y$ is an epimorphism, then we can say that $x$ is a “strong generator” or “regular generator”, etc., according as $hom(x,y)\cdot x\to y$ is a strong epi, regular epi, etc.

Posted by: Mike Shulman on September 1, 2015 2:59 AM | Permalink | Reply to this

### Re: Wrangling generators for subobjects

Thank you for the comment, and the clear explanation of why one might (should) be doubtful of my stated definition of generation. Probably I was too hasty saying that the definition works well for commutative rings, in light of the example you give.

Although my application is to categories of representations in which the distinctions you’re discussing do not appear, there is usually great value in figuring out the perfect definition that works, works, works. Indeed, part of why I’m posting here is to hear the modern categorical perspective on these ideas!

My work is mostly concerned with what Todd Trimble calls “those categories which received the most attention in the early days of category theory,” so I hope any inadequacy of perspective can be forgiven.

Posted by: John Wiltshire-Gordon on September 2, 2015 6:14 AM | Permalink | Reply to this

### Re: Wrangling generators for subobjects

Although my application is to categories of representations in which the distinctions you’re discussing do not appear

Right — that’s an important fact.

It’s curious how often it happens that in commonly-encountered categories of algebras, all epimorphisms are surjective. This fact for the category of groups is actually quite hard, as I remember (though I don’t recall the proof). But it’s true!

Posted by: Tom Leinster on September 2, 2015 11:14 AM | Permalink | Reply to this

### Re: Wrangling generators for subobjects

Proving that epis of groups are regular is actually not that bad. For categories of algebras and using the regular epi-mono factorization, it’s equivalent to proving that the category of groups is balanced (monic epis are isos).

However, many proofs of that last fact involve some case analysis and are not to my taste. Typically they go something like this: given a monic epi $i: H \hookrightarrow G$ that is not an iso, the index of $H$ in $G$ is $2$ or greater. The index $2$ case is not so bad because there the subgroup $H$ must be normal and one can consider the two maps from $G$ to $G/H$. For index greater than $2$, one can find three disjoint cosets $H$, $u H$, and $v H$, and one can build two homomorphisms $G \to Perm(G)$, one of which is Cayley and the other a conjugate of Cayley by a permutation $\sigma: G \to G$ which is fixed except on the cosets $u H$, $v H$, where elements $u h$ are swapped with elements $v h$. I won’t give any further details because, as I say, this is not my favorite proof – it’s a bit fiddly.

The proof I’ve seen that I like the best is recorded in the nLab here, and involves a wreath product construction, with no case analysis.

Now: proving that monomorphisms of groups are regular – there I’ve never seen a proof I’m completely happy with. If anyone has a clean constructive proof of that, I’d like to see it.

Posted by: Todd Trimble on September 2, 2015 1:16 PM | Permalink | Reply to this

### Re: Wrangling generators for subobjects

This seems reasonably clean to me:

Let $H \subseteq G$. We want to construct a group $T$ and two maps $G \to T$ which become equal precisely on $H$. Let $X = G/H$ and write $h$ for the coset $H$ in $X$. So $G$ acts transitively on $X$, and $H$ is the stabilizer of $h$.

Let $S$ be the set of subsets of $X$, let $\mathrm{Sym}(S)$ be the group of permutations of $S$, and let $\rho: G \to \mathrm{Sym}(S)$ be the obvious action of $G$ on $X$. Let $\alpha \in \mathrm{Sym}(S)$ be the map $\alpha(A) = A \oplus \{ h \}$, where $\oplus$ is the symmetric difference.

Then $\rho(g) = \alpha \rho(g) \alpha^{-1}$ precisely for $g \in H$.

Posted by: David Speyer on September 2, 2015 4:58 PM | Permalink | Reply to this

### Re: Wrangling generators for subobjects

Thanks, David. That looks like a close relative of an argument I’ve seen before which can be found here. Although the way you put it here makes it look rather more attractive to me.

I don’t think it’s going to quite work for my desired purposes. What I would like is a proof that will work in an arbitrary topos (I didn’t specify this, but that’s my working benchmark for a proof to be ‘constructive’), where power objects need not be (internal) Boolean algebras. In particular, taking the symmetric difference with an element need not be an invertible operation, if one is dealing with power objects in a topos, which are internal Heyting algebras.

Probably many mathematicians would regard this as the reaction of an overly delicate sensibility. Heck, I’m not even sure group monomorphisms are regular in an arbitrary topos. It would be nice to know though; there was some MathOverflow discussion on it here, which needless to say, didn’t reach a firm conclusion.

Posted by: Todd Trimble on September 2, 2015 8:00 PM | Permalink | Reply to this

### Re: Wrangling generators for subobjects

I think I like the way it is sketched in that MO question better than either mine or the nLab link: $G/H \sqcup \{ \ast \}$ is a much smaller object than the set of all subsets of $G/H$, and equally concrete.

So, the problem is if $H$ is not “detachable”. I always find thinking in constructively very confusing. (In the technical sense which you mean it; I don’t have a problem actually making constructions!) But, if I had two maps $\alpha$, $\beta: G \to T$, would the formula $\{ g : \alpha(g) = \beta(G) \}$ be a “detachment” of $H$, thus making the criterion if and only if?

Posted by: David Speyer on September 2, 2015 8:13 PM | Permalink | Reply to this

### Re: Wrangling generators for subobjects

The way I think of it, “detachments” are typically used to make sense of multiline definitions, i.e. definitions of the form “if $x$ is of this form, do this; if $x$ is of that form, do that”. In other words, if-then-else definitions make tacit appeal to excluded middle. The involution $t$ in the MO post is defined in that manner.

Just having an equation of the form $H = \{g: \alpha(g) = \beta(g)\}$, or establishing $\subseteq$ and $\supseteq$, needn’t mean $H$ is detachable or that every element of $G$ belongs to $H$ or its complement.

Posted by: Todd Trimble on September 2, 2015 8:43 PM | Permalink | Reply to this

### Re: Wrangling generators for subobjects

Monomorphisms of internal groups in a Grothendieck topos are effective monomorphisms. Consider the classifying topos for group monomorphisms. This is a presheaf topos (because it is the classifying topos of a cartesian theory), and internal groups in a presheaf topos are group-valued presheaves, so it is enough to prove that monomorphisms of ordinary groups are effective monomorphisms. But that has been done, so the conclusion also holds in an arbitrary Grothendieck topos.

Moreover, by embedding into sheaves, we may deduce the same result for $\sigma$-pretoposes. Unfortunately, I do not know of any tricks for extending the result to (pre)toposes with NNO. It would be very strange if it were not true, though.

Posted by: Zhen Lin on September 2, 2015 9:23 PM | Permalink | Reply to this

### Re: Wrangling generators for subobjects

That’s a nice argument, Zhen Lin! Of course, that’s for Grothendieck toposes; is there anything you can say here about general toposes?

Or maybe you’ve answered that by reference to $\sigma$-pretoposes? The trouble is that I don’t know what those are. But this looks like food for thought.

Posted by: Todd Trimble on September 2, 2015 9:50 PM | Permalink | Reply to this

### Re: Wrangling generators for subobjects

I pressed ‘Submit’ too quickly. Maybe you’re suggesting this gives a proof for toposes with countable coproducts; is that the idea?

Posted by: Todd Trimble on September 2, 2015 9:53 PM | Permalink | Reply to this

### Re: Wrangling generators for subobjects

A $\sigma$-pretopos is a pretopos with countable coproducts, or equivalently, countable colimits. Having countable coproducts is a stronger condition than having a NNO – for one thing, it implies that the NNO is standard. So my argument does not apply to e.g. the effective topos.

I insist on a $\sigma$-pretopos (as opposed to a finitary pretopos) so that the embedding into sheaves preserves all countable colimits – which in turn ensures that the embedding preserves finite colimits of internal groups.

Posted by: Zhen Lin on September 3, 2015 12:12 AM | Permalink | Reply to this

### Re: Wrangling generators for subobjects

Of course, once we know that $Grp$ is balanced, if there is an (epi, regular mono) factorization system then all monos are regular. But I’m not sure if that helps any.

Posted by: Mike Shulman on September 2, 2015 11:55 PM | Permalink | Reply to this

### Re: Wrangling generators for subobjects

I thought about that too. But I didn’t see a way to take advantage of it.

Posted by: Todd Trimble on September 3, 2015 12:08 AM | Permalink | Reply to this

Post a New Comment