44
$\begingroup$

I think a related question might be this (Set-Theoretic Issues/Categories).

There are many ways in which you can avoid set theoretical paradoxes in dealing with category theory (see for instance Shulman - Set theory for category theory).

Some important results in category theory assume some kind of ‘smallness’ of your category in practice. A very much used result in homological algebra is the Freyd–Mitchell embedding theorem:

  • Every small abelian category admits an fully faithful exact embedding in a category $\text{$R$-mod}$ for a suitable ring $R$.

Now, in everyday usage of this result, the restriction that the category is small is not important: for instance, if you want to do diagram chasing in a diagram on any category, you can always restrict your attention to the abelian subcategory generated by the objects and maps on the diagram, and the category will be small.

I am wondering:

What are results of category theory, commonly used in mathematical practice, in which considerations of size are crucial?

Shulman in [op. cit.] gives what I think is an example, the Freyd Special Adjoint Functor Theorem: a functor from a complete, locally small, and well-powered category with a cogenerating set to a locally small category has a left adjoint if and only if it preserves small limits.

I would find interesting to see some discussion on this topic.

$\endgroup$
69
$\begingroup$

Very often one has the feeling that set-theoretic issues are somewhat cheatable, and people feel like they have eluded foundations when they manage to cheat them. Even worse, some claim that foundations are irrelevant because each time they dare to be relevant, they can be cheated. What these people haven't understood is that the best foundation is the one that allows the most cheating (without falling apart).

In the relationship between foundation and practice, though, what matters the most is the phenomenology of every-day mathematics. In order to make this statement clear, let me state the uncheatable lemma. In the later discussion, we will see the repercussion of this lemma.

Lemma (The uncheatable). A locally small, large-cocomplete category is a poset.

The lemma shows that no matter how fat are the sets where you enrich your category, there is no chance that the category is absolutely cocomplete.

Example. In the category of sets, the large coproduct of all sets is not a set. If you enlarge the universe in such a way that it is, then some other (even larger) coproduct will not exist. This is inescapable and always boils down to the Russel Paradox.

Excursus. Very recently Thomas Forster, Adam Lewicki, Alice Vidrine have tried to reboot category theory in Stratified Set Theory in their paper Category Theory with Stratified Set Theory (arXiv: https://arxiv.org/abs/1911.04704). One could consider this as a kind of solution to the uncheatable lemma. But it's hard to tell whether it is a true solution or a more or less equivalent linguistic reformulation. This theory is at its early stages.

At this point one could say that I haven't shown any concrete problem, we all know that the class of all sets is not a set, and it appears as a piece of quite harmless news to us.

In the rest of the discussion, I will try to show that the uncheatable lemma has consequences in the daily use of category theory. Categories will be assumed to be locally small with respect to some category of sets. Let me recall a standard result from the theory of Kan extensions.

Lemma (Kan). Let $\mathsf{B} \stackrel{f}{\leftarrow} \mathsf{A} \stackrel{g}{\to} \mathsf{C}$ be a span where $\mathsf{A}$ is small and $\mathsf{C}$ is (small) cocomplete. The the left Kan extension $\mathsf{lan}_f g$ exists.

Kan extensions are a useful tool in everyday practice, with applications in many different topics of category theory. In this lemma (which is one of the most used in this topic) the set-theoretic issue is far from being hidden: $\mathsf{A}$ needs to be small (with respect to Ob$\mathsf{C})$! There is no chance that the lemma is true when $\mathsf{A}$ is a large category. Indeed since colimits can be computed via Kan extensions, the lemma would imply that every (small) cocomplete category is large cocomplete, which is not allowed by the uncheatable. Also, there is no chance to solve the problem by saying: well, let's just consider $\mathsf{C}$ to be large-cocomplete, again because of the the uncheatable.

This problem is hard to avoid because the size of the categories of our interest is as a fact always larger than the size of their inhabitants (this just means that most of the time Ob$\mathsf{C}$ is a proper class, as big as the size of the enrichment).

Notice that the Kan extension problem recovers the Adjoint functor theorem one, because adjoints are computed via Kan extensions of identities of large categories. Indeed, in that case, the solution set condition is precisely what is needed in order to cut down the size of some colimits that otherwise would be too large to compute, as can be synthesized by the sharp version of the Kan lemma.

Sharp Kan lemma. Let $\mathsf{B} \stackrel{f}{\leftarrow} \mathsf{A} \stackrel{g}{\to} \mathsf{C}$ be a span where $\mathsf{B}(f-,b)$ is a is small presheaf for every $b \in \mathsf{B}$ and $\mathsf{C}$ is (small) cocomplete. Then the left Kan extension $\mathsf{lan}_f g$ exists.

Indeed this lemma allows $\mathsf{A}$ to be large, but we must pay a tribute to its presheaf category: $f$ needs to be somehow locally small (with respect to Ob$\mathsf{C}$).

Kan lemma Fortissimo. Let $ \mathsf{A} \stackrel{f}{\to} \mathsf{B} $ be a functor. The following are equivalent:

  • for every $g :\mathsf{A} \to \mathsf{C}$ where $\mathsf{C}$ is a small-cocomplete category, $\mathsf{lan}_f g$ exists.
  • $\mathsf{lan}_f y$ exists, where $y$ is the Yoneda embedding in the category of small presheaves $y: \mathsf{A} \to \mathcal{P}(\mathsf{A})$.
  • $\mathsf{B}(f-,b)$ is a is small presheaf for every $b \in \mathsf{B}$.

Even unconsciously, the previous discussion is one of the reasons of the popularity of locally presentable categories. Indeed, having a dense generator is a good compromise between generality and tameness. As an evidence of this, in the context of accessible categories the sharp Kan lemma can be simplified.

Tame Kan lemma. Let $\mathsf{B} \stackrel{f}{\leftarrow} \mathsf{A} \stackrel{g}{\to} \mathsf{C}$ be a span of accessible categories, where $f$ is an accessible functor and $\mathsf{C}$ is (small) cocomplete. Then the left Kan extension $\mathsf{lan}_f g$ exists.


References for Sharp. I am not aware of a reference for this result. It can follow from a careful analysis of Prop. A.7 in my paper Codensity: Isbell duality, pro-objects, compactness and accessibility. The structure of the proof remains the same, presheaves must be replaced by small presheaves.

References for Tame. This is an exercise, it can follow directly from the sharp Kan lemma, but it's enough to properly combine the usual Kan lemma, Prop A.1&2 of the above-mentioned paper, and the fact that accessible functors have arity.


This answer is connected to this other.

$\endgroup$
7
  • $\begingroup$ This is such a good answer! $\endgroup$ – Harry Gindi Jul 20 '20 at 10:41
  • $\begingroup$ Thanks, @HarryGindi! :) $\endgroup$ – Ivan Di Liberti Jul 20 '20 at 10:43
  • $\begingroup$ This is a good answer, but I feel it would be even better with a very concrete example. The one I had in mind was actually given by David Roberts in his answer, so that's a good complement $\endgroup$ – Maxime Ramzi Jul 21 '20 at 12:51
  • $\begingroup$ @MaximeRamzi thanks! :-) $\endgroup$ – David Roberts Jul 24 '20 at 0:32
  • 1
    $\begingroup$ Re: my paper with Forster and Lewicki, I think I speak for my co-authors as well when I say that as a cheat goes, an NF-like universe isn't a very good cheat (and was never really meant to be; it was more a route to get at what kind of beast NF is). All of your usual size problems end up turning into $T$-functor problems, which are usually even more opaque. As an aside, I'm surprised our paper made anyone's radar! $\endgroup$ – Malice Vidrine Nov 3 '20 at 14:24
24
$\begingroup$

Here's an example that links more to mathematical practice outside category theory proper. Recall that for a small site $(C,J)$, where I take $J$ to be a Grothendieck pretopology on the small category $C$, any presheaf $C^{op} \to \mathbf{Set}$ has a sheafification, and this extends to give us a functor $[C^{op},\mathbf{Set}] \to Sh(C,J)$ from presheaves to sheaves, left adjoint to the inclusion. Sheafification can be described as two applications of the Grothendieck plus construction, which is a colimit indexed by a set of covering sieves.

Now we can also talk about large sites, and at least talk about individual (pre)sheaves even when we cannot form the categories of them (say because, like the Stacks project, we do not wish to use universes, or whatever). There is then a real obstruction to forming the sheafification. Famously the category of schemes (over a base scheme, if desired) with the fpqc (pre)topology has presheaves on it that don't admit a sheafification (see tag 0BBK). What is happening here is that the condition WISC (Weakly Initial Set of Covers) is violated. This condition says that for any object, there is a set of covering families such that every covering family is refined by one in that set. This allows the construction of the colimit in the plus construction, and can be also seen as a kind of solution set condition for the construction of the left adjoint to the inclusion of sheaves into presheaves. So in a sense, this is a special case of Ivan's answer.

Large sites are not all that uncommon in practice, even if they are glossed over. Ignoring essentially small examples (like that of the category of finite-dimensional manifolds), then the category of all topological spaces (or CGWH spaces, even) with the open cover topology is large but satisfies WISC; same for the category of schemes (or the relative case) with pretty much any topology coarser than fpqc; same for any category of infinite-dimensional smooth manifolds (again with the open cover topology). Thus this condition WISC is very natural from both a category-theoretic point of view, and also from a sheaf-theoretic or even geometric viewpoint, being satisfied very often, but not always. From a set theoretic point of view (considering forcing as being an instance of forming sheaf toposes), it's actually quite hard to make it fail, and one cannot to that without proper class forcing (or the analogous thing in a topos-theoretic approach).

$\endgroup$
3
  • 2
    $\begingroup$ I should add: I understand that the fppf satisfies WISC, but I don't know if the ph topology (which is finer than the fppf topology) does. Of the topologies on categories of schemes listed in the Stacks Project, the fpqc and v-topologies definitely don't satisfy WISC. Anything coarser than fppf (so: syntomic, smooth, étale and Zariski topologies) does satisfy WISC. So the ph topology is the only one there I don't know about. $\endgroup$ – David Roberts Jul 20 '20 at 11:32
  • 1
    $\begingroup$ Johan de Jong informs me the h and the ph topologies both satisfy WISC. I believe this implies that in the chart at pbelmans.ncag.info/topologies-comparison (slightly incomplete), everything except the fpqc topology satisfies WISC. $\endgroup$ – David Roberts Jul 24 '20 at 0:31
  • $\begingroup$ Interestingly, the h topology isn't subcanonical (!), which in my mind makes it rather fine/large, but it is incomparable with fpqc (which is subcanonical), so WISC and subcanonicity are independent. $\endgroup$ – David Roberts Jul 26 '20 at 1:31
18
$\begingroup$

The other answers are good, but I would like to point out that Ivan's "uncheatable" lemma can in fact be cheated. The proof of that lemma (due to Freyd) makes inescapable use of classical logic, and in constructive mathematics it is possible to have a non-poset that is complete for the size of its own set of objects (a complete small category). It is even possible to have a category "of sets" with this property (e.g. those called "modest sets" in realizability). Then all Kan extensions into such a category exist, all sheafifications of modest presheaves exist, and presumably all Bousfield localizations of modest spectra exist (although the latter may get you into HoTT water when you try to do it constructively).

About the only thing the category of modest sets lacks is a subobject classifier (it is locally cartesian closed). So these days I prefer the following argument as the "least cheatable" (calling something "uncheatable" sounds like a challenge) manifestation of size issues in category theory.

Lemma 1: Any endofunctor of a complete small category has a fixed point.

Proof: If $C$ is complete-small, so is the category of $F$-algebras for any endofunctor $F:C\to C$. But any complete small category has an initial object (by essentially the same argument that any complete meet-semilattice also has all joins), and an initial $F$-algebra is a fixed point of $F$ (by Lambek's lemma).

Lemma 2: If $C$ is an elementary topos, the double powerset functor $X \mapsto \Omega^{\Omega^X}$ has no fixed point.

Proof: By Cantor's diagonalization argument.

Thus, no elementary topos can have all limits of the size of its collection of objects.

$\endgroup$
2
  • 4
    $\begingroup$ HoTT water, hah! $\endgroup$ – Kevin Arlin Jul 28 '20 at 16:52
  • 2
    $\begingroup$ I really appreciate that you challenged my answer. I'll bring a gauntlet at the next conference. Get ready to fight. $\endgroup$ – Ivan Di Liberti Aug 3 '20 at 11:18
10
$\begingroup$

Let me share a basic theorem in algebraic topology that hides a subtle set-theoretic point that turns out to be the item at stake. I am talking about Bousfield localization. Let me put it this way, consider the category $\mathcal{T}: = \mathsf{Ho}\mathcal{Sp}$ the homotopy category of spectra. Let $E \in \mathcal{T}$ and consider the smallest triangulated category stable with coproducts that contains $E$, denoted $\langle E \rangle$. Bousfield's theorem asserts that the inclusion functor $$\langle E \rangle \hookrightarrow \mathcal{T}$$ has a right adjoint.

The idea of the proof is clear, Given a spectrum $X$ build step by step spectra $N_\alpha \in \langle E \rangle$ (indexed by cardinals) and consider its cofiber sequence $$ N_\alpha \to X \to B_\alpha $$ If one takes the (homotopy) limit of all $B_\alpha$ one arrives to an object in $\langle E \rangle^\perp$ whose fiber $N$ (the colimit of $N_\alpha$) is automatically the value of the adjoint. Up to some checking and some precisions this would be the proof. The problem is that one cannot take a class-indexed limit, unless one accepts a form of the universe axiom in which case these limits live outside our initial universe!

So, what is the way out? Bousfield clever argument was that there is an cardinal $\gamma$ such that $B_\gamma \in \langle E \rangle^\perp$ by using regular cardinals and arguments related to the presentability of the model category of spectra. With this reasoning, both $N_\gamma$ and $B_\gamma$ live in our universe, or otherwise said, the proof makes sense with our favorite choice of foundations (von Neumann-Gödel-Bernays, say).

Needless to say, there are other versions of this result that use the same set-theoretic trick to achieve a bound on the index cardinal, for instance an analogous result for derived categories.

All of this is related to the so called "small object argument".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.