Meaning of "small" in category theory

Question

The following is taken from the text Arrows, Structures and Functors the categorical imperative by Arbib and Manes.

We assumed the following theorem and exercise designated respectively as Theorem 17 and also exercise 2.4.13.

Theorem 17: Let $D$ be a diagram in $\textbf{K}$ with sets $V$-indexed family and every $E$-indexed family of objects in $\textbf{K}$ has a product and if every pair of $\textbf{K}$-morphisms (between the same two objects) has an equalizer, $D$ has a limit.

We say a collection is small if it is a set, i.e. an object of $\textbf{Set.}$ We say a diagram is small just in case its collection of vertices forms a set, and its collection of edges forms a set. Thus we may paraphrase Theorem 17 as saying that if a category $\textbf{K}$ has equalizers and small products, then it has small limits.

Exercise 2.4.13: Show that the product $P$ of all non-empty sets $X$ in $\textbf{Set}$ is not itself in $\textbf{Set}$. [Hint: If $P$ is in $\textbf{Set}$ is the power set $2^P$. Thus we have the projection $\pi:P\rightarrow 2^P$ of $P$ to be the set $2^P$, which is clearly a surjection. Define $A$ in $2^P$ by $A=\{x\in P\mid x\notin \pi(x)\}$ and let $\pi(y)=A$. Then "$y\in A$" implies "$y\notin A$" where as "$y\notin A$" implies "$y\in A$," the desired contradiction.]

Exercise: Prove that every small diagram in $\textbf{Top}$ has a colimit.

Question: I have three quick questions about the exercise in bold.

1. I don't know what the exercise in bold is asking, is it asking to show that the category of Topological space has a colimit, in terms of the diagram for representing cocone, and the diagram for the diagram for cocone category has finite vertices and edges. Also, the diagrams are of coproduct and pushback?

2. Also from the assumed italicized exercise 2.4.13's I don't know what it means when the hint, states that says that for a category (diagrams, collection of stuff) are termed "small" if it forms a set. This is a bit ambiguous. When it says it is a "set", does it mean a finite, infinite, countable or uncountable set. Basically what type of set?

Also, what is the difference if the question simply ask the reader to show that that either: the category of diagrams in $\textbf{}$ has a colimit; or that the category of $\textbf{}$ (or simply category of some mathematical structure) has a colimit.

Answer 1

(A suggestion: try another text. My first choice would be Leinster, which is freely available online. I've written up a comprehensive set of solutions to the exercises. A close second would be Riehl, also free online.)

There are two issues here, one almost purely set-theoretic, the other category-theoretical.

Set theory: sets and classes. A bit of historical background may help with your question (ii). Set theory was developed informally starting in the late 19th century, mainly by Cantor. At that time it was implicitly assumed that you could always form the set of all things satisfying a given property: $\{x|P(x)\}$, $P$ being some property, always made sense.

Then around 1900 Russell and Zermelo independently discovered Russell's paradox: the set of all sets that are not elements of themselves, i.e., $R=\{x | x\not\in x\}$, is a contradictory concept. For, $x\in R$ if and only if $x\not\in x$, so $R\in R$ if and only if $R\not\in R$.

The most popular solution today is probably is the axiomatic system known as ZF set theory. $\{x|P(x)\}$ is no longer assumed to always make sense. Corresponding to a property, you may have a set containing all things with that property (e.g., the set of all real numbers), or you may not (e.g., there is no "set of all sets"). One talks informally about the class of all things satisfying a property, e.g. the class of all sets. (Another axiomatic set theory, NBG, formalizes this notion of class.)

Generally people feel that a class is not a set when it is "too big". All sets are classes, but only "small enough" classes are sets. (This intuition is vague, but that's why ZF has axioms: to allow for precise reasoning about this stuff.) We have a class of all sets, a class of all groups, a class of all topological spaces, etc. Classes that are not sets are called proper classes.

A small category is one whose class of objects is a set, and whose class of morphisms is a set. The category of sets, or of groups, or of topological spaces, etc., are not small. However, you could (for example) consider the category of all sets that are subsets of some given fixed set $U$; that would be a small subcategory of the not-small category of all sets.

This set vs. proper class distinction is analogous to other "small/big" distinctions, like finite vs. infinite or countable vs. uncountable, but it is its own thing.

I hope that helps with your question (ii).

Category theory: colimits. When we say a "category has colimits", we mean that every cocone in it has a colimit. Without going into details, part of the definition of a cocone involves a small category. So the diagram of the cocone can't be "too big".

Example: a coproduct is a type of colimit. In the category of sets, the coproduct is the disjoint union. Set has coproducts because you can take the disjoint union of a collection of sets, provided the collection is itself a set. However, you're not allowed to form the disjoint union of all sets, because that collection is a proper class.

It is a theorem that if a category has coproducts and coequalizers (i.e., every coproduct diagram has a colimit, and every coequalizer diagram has a colimit), then it has colimits. (This is the dual of Theorem 17.)

The boldface exercise is asking you to use this fact to show that Top has colimits.

For a deeper understanding of what coproducts, coequalizers, and colimits look like in Top and several other categories, I recommend again either Leinster (chapter 5) or Riehl (chapter 3).

Answer 2

I think a lot of your confusion comes from the set/class distinction. It is actaully pretty hard to understand what small/large/locally small categories are without proper context, so in my answer I will try to give you that context. It is pretty long, but I hope you like it anyway.

I will have to start with a short introduction into formal set theory. Say we choose to formalize mathematics by chosing some formal set theory as a foundation. For simplicity, let us look at the most popular formal set theory, which is ZFC.

ZFC is a single-sorted theory in first-order logic. This means there is a single sort over which all variables range and from which all constants are taken: the sets. In ZFC every mathematical object is a set. There is a single relation symbol $\in$ whose intuitive meaning is "element of". Then there are a bunch of axioms, and that is it. Here is an example: $$\exists x\,\forall y\, \neg(y\in x)$$ The axiom states that there is a set such that no other set is contained in it. I.e. the axiom states the existence of an empty set. Another axiom is the following one: $$\forall x\,\forall y \,(\forall z\,(z\in x\leftrightarrow z\in y) \to x = y) $$ The axiom states that two sets are equal when they have the same elements. Together with the first axiom we can show that there is a unique set which has no elements, and this justifies giving it a name $\varnothing$ which we can use from now on in praxis. There are a bunch of axioms which tell us that certain sets exist: pairs, unions, power sets, the natural numbers, subsets cut out by predicates, and so on. In each case (except in case of the choice axiom) the resulting set can be shown to be unique, and we may give it a name. This is then how informal mathematics can be formalised. We build more and more sets, give them names and prove stuff about them.

We can also define what a category is. Since a everything is a set, a category has to be a set too! A category is a set $C$ which is a tuple of a number of sets $C_0,C_1,\circ$ etc. which encode the objects, morphisms, composition functions and indenties and satisfies a bunch of conditions. Even the composition function has to be encoded as a set, because everything is a set. We can write down a formula in formal set theory $\varphi$ with a free variable $x$ such that $\varphi[C/x]$ will be true if and only if $C$ is actually a set which encodes the data of a category. Of course, in order to write down that formula we would have to use formulas which express that a set is a tuple of a certain length, that a set is a function, etc. which we would have to define first.

To clarify some terminology: A formula is a well-formed expression in the formal language of ZFC which may contain free unbounded variables. Here is an example of a formula $\varphi$. $$\forall y\, \neg(y\in x)$$ The free variable is $x$ and $\varphi[t/x]$ will be true if and only if $t$ is an empty set. So that formula expresses "$x$ is an empty set". I hope you are convinced that we may also find formulas $\varphi$ with one free variable $x$ which express that "$x$ is a group", or "$x$ is a category". If you take a formal set-theory book and look at the first few chapters to see how they encode tuples, functions, natural numbers, lists, and so on, then you will probably believe that almost everything be encoded in this minimal language.

The categories of the kind which I have described above are the small categories. They are fully encoded by a set, in particular their collection of objects and their collection of morphisms form a set. In progamming-terms: small categories are first-class citizens in ZFC. You can name them, work with them, and reason about them staying fully inside the language, without having to look from the outside on it.

There is a problem though. Most of the important categories that we like to work with are not of this kind. For example, say you want to define the category $Set$ of all sets. Your predicate $isacategory(x)$ tells you that you will have to construct a set of objects, a set of morphisms, and so on, and then pack that data up into a new set, which is a tuple. Hence you would like to form a set of all sets. But famously, such a set can not exist. $$\exists x\, \forall y\,(y\in x)$$ is inconsistent with the rest of the axioms of ZFC (separation + a set of all sets is what you need for Russels paradox). Hence, whatever $Set$ is, it can not be a category in the small sense described above. You will never be able to form $Set$ as an actual thing inside ZFC. This is what category theorists mean when they say that $Set$ is a large category. The same problem arises for all the other categories of comparable size: Groups, Rings, Top, and so on. If you want to work with them in formal ZFC, and you are unwilling to modify your foundations, then you can only do this by means of formulas, and your reasoning will have to be half externally, half internally. This is very similar to people who use macro programming to exploit the capabilities of a programming language to its very edge. Here is for example how you could "define" a very large category:

A large category is a formula $ob(x)$ in one free variable, and a predicate $mor(x,y,z)$ in three free variables. Additionally, there are predicates which can be used to express composition and identities.

The idea is, that the first predicate cuts out the collection of objects of your very large category, and the second predicate cuts out the collection of morphisms given any two objects. The best way to picture this is by drawing the collection of all sets as I have done below:

I should have probably drawn it in a more hierachical way, but this is good enough for our purpose. The little dots are the sets, and all small categories are such little dots. The axioms of set theory are all (except choice) of the form that they allow us to draw a circle around some of such dots and turn them into a dot themselves. For example, here is my mental picture of the axiom of infinity:

But note that there is no dot inside which is labeled $U$. I.e. no set of all sets. This would make the picture look pretty weird, and is actually inconsistent. Drawing a circle around some of the dots in $U$ is what people call a class, and when the class can not be internalised (internalised means that there is a set such that the elements of that set are precisely the sets which belong to the class), then that class is a proper class. Every formula in one free variable cuts out a class, and in particular $U$ is such a class. So if you are a very serious person, then the picture below shows you how you have to think about a large category. As an example I have drawn the large (but locally small) category of abelian groups below. The circle on the other left contains those sets for which the predicate "$x$ is an abelian group" is true. This is a proper class and can not be turned into a set. In other words $$\exists y\,\forall x\, (x\in y \leftrightarrow isabeliangroup(x))$$ is inconsistent. The circle on the right hand side is the class of morphism $\mathbb Z\to \mathbb Z/2\mathbb Z$. This class can be internalized. In fact, all morphism classes of $Ab$ can be internalized and are actual citizens of ZFC. This is what category theorists mean when they say that $Ab$ is a large but locally small category. Some large categories are not even locally small.

An important point is that in order to even formulate the definition of a large category you have to somehow step our your language and have to look from the outside on it. You can only speak about classes in forms of formulas, and formulas are part of the formal language and not objects of the domain of discourse about which the language speaks. This is pretty unsatisfactory for several reasons:

• It is difficult to explain to people what the class/set distinction is, because you have to explain all of the above first.
• You can not work with classes the same way you can work with sets. The axioms of set theory, which allow to build new sets from old ones, do not apply to classes, because they are formulas and not first-class citizens. This is very similar to how a construct in a programming language is much more useful when it is a first-class citizen, so that you can pass it around and use all the other features of the language on it. You have to be careful with classes, when you are a very serious person (I am not). For example, you will have trouble forming functor categories of large categories and so on. It is hard to do category theory this way.
• The definition of a large category is really a definition on a meta-level, and having two levels of reasoning is pretty unpleasent and makes stuff unneccesarily complicated.

First let me describe some solutions, which make the set/class distinction more workable. There is a conservative extension of ZFC called NBG (von Neumann-Bernays-Gödel set theory) which allows to speak about both classes and sets. This fixes the third and parts of the second problem. The quantifiers of NBG range over classes, some of which are sets. The classes become actual objects in the domain of discourse (in any model) and it is also clearly stated in NBG which constructions you may apply to classes. Still, you can apply less constructions to classes than to sets (after all NBG is a conservative extension), and forming functor categories/localisations and so on will still be hard or impossible in some cases. The last, and in my opinion best, solution is to add an axiom to ZFC, which states that there are lots of large inaccessible cardinals (equivalently, that every set is an element of a Grothendieck-universe). What this does is to add a dot for all the sets which we have drawn in the picture above! The new picture looks like this: The Grothendieck-universe $\kappa$ will not contain all sets, but it will contain all the sets that you can build explicitly with the constructions of ZFC (it is closed under taking power sets, unions, etc.). Now you can form a small category $Set_\kappa$ whose set of objects is $\kappa$, and you can work with it without having to think about the subtle difference between sets and classes. This is in my opinion the best solution.

Even though this all looks very technical and not relevant to category theory itself, some sort of size constraints on the indexing categories of colimits and limits are an unavoidable and intrinsic part of the category theory itself and not just an artifact of the foundations. There is a famous theorem by Freyd that every small category (for example $Set_\kappa$) which has all limits (indexed by all small categories of arbitrary size) will be a preorder. The category $Set_\kappa$ will only have limits indexed by categories whose cardinality (objects and morphisms together) is strictly smaller than $\kappa$.

Similarly in the class/set setup, you can not expect that your large categories have limits indexed by all other large categories. They will only have small limits (indexed by small categories). This is what exercise 2.4.13 is about. There you are supposed to show that the large category $Set$ can not have a product of all of its objects (similarly $Set_\kappa$ will not have a product of all of its objects). I hope this helps, have fun and write a comment if you have a question. :)