# confusion over the use of universes in category theory

Fix a universe $U$ of sets. I take it we do this to stop accidentally talking about collections which are not sets. MacLane says that a small category is one where the objects and morphisms are both sets. But where do these sets live? Do they have to live in the universe? Are all categories small in this context? Does this mean if we say a category has small limits does it just have all limits? What if I have a category $C$ and I consider the functor which sends A, B to the morphisms between A and B. How do I know that this set of morphisms lies in $\mathsf{Set}$ for whichever universe I’ve picked?

-
having some trouble with my i key – Paul Slevin Sep 23 '12 at 8:40
I took care of the odd $i$’s. – Brian M. Scott Sep 23 '12 at 8:51
And I fixed the even i. :-) – celtschk Sep 23 '12 at 9:00

The set-theoretic setup of Categories for the working mathematician is somewhat subtle. Let's recall it now for clarity:

1. The base system is Zermelo–Fraenkel set theory with choice.

2. We assume that there is a strongly inaccessible cardinal $\kappa$, and we fix a constant $U = V_\kappa$.

3. A small set is any member of $U$. A metacategory is any model of the first-order theory of categories – for example, the class of all sets and all maps constitute the metacategory $\textbf{SET}$. A category is a model inside our set theory. A locally small category is a category whose hom objects are small sets – for example, the category $\textbf{Set}$ of all small sets. A small category is a locally small category whose object set is also small.

There is therefore a trichotomy of small sets, large sets, and proper classes. This is not the usual practice: we normally think of all sets as being small. This doesn't cause many problems if you only work with some fixed categories, but if you actually want to do category theory rather than just use it, you will eventually find it more convenient to use the CWM setup.

Here are some of the pitfalls of using a class–set theory such as von Neumann–Bernays–Gödel or Morse–Kelley instead of assuming we have a universe:

• As Makoto has highlighted, even if $\mathcal{C}$ and $\mathcal{D}$ are locally small categories, the functor category $[\mathcal{C}, \mathcal{D}]$ does not exist. This is because its objects would be a collection of proper classes, and this fails to even be a class. In the CWM setup, this is a legitimate category, because it lives in $V_{\kappa + 2}$, but MK only lets us talk about $V_{\kappa + 1}$.

• There is no avenue for “universe enlargement”: if you want to talk about categories that are not locally small, then you have to live with the fact that there is no hom functor, because the category of all classes is not a legitimate object. In the CWM setup, this is no problem: hom objects are always sets, so there is always a hom functor even though the target need not be $\textbf{Set}$. (That is why CWM sometimes talks about $\textbf{Ens}$ instead of $\textbf{Set}$.)

• Some theorems cannot be proven as straightforwardly. For example, a well-known argument of Freyd shows that a category $\mathcal{C}$ with products of size $\left| \operatorname{mor} \mathcal{C} \right|$ must be a preorder – but the obvious formalisation of this argument in class–set theory only works when $\operatorname{mor} \mathcal{C}$ is a set! Indeed, at the conclusion of Freyd's argument one essentially invokes Cantor's theorem that $2^\kappa \gneq \kappa$, but Cantor's theorem cannot be applied to proper classes. (In the first place, one cannot talk about the class of all subclasses of a proper class – such a thing does not exist – and although the class of all subsets of a proper class exists, the principle of limitation of size implies it is the same size as any other proper class.) Instead, one must directly apply the diagonal argument to the hom-classes of $\mathcal{C}$ to derive a contradiction.

Mike Shulman has a very nicely written paper comparing the various alternatives to ordinary ZFC in the context of category theory: you should read it when you get the chance.

-
I've seen the claim you attribute to Freyd on Wikipedia in the complete categories article, but can't immediately see the proof. Where might one find the argument spelled out? – Kevin Carlson Sep 24 '12 at 3:48
Suppose there are at least two distinct arrows $A \to B$. Take the $\operatorname{mor} \mathcal{C}$-indexed product of $B$ and count the number of morphisms from $A$ to this product. – Zhen Lin Sep 24 '12 at 4:03
Ah, I thought it ought to be something so simple! I was taking the product of all the objects of $\mathcal{C}$, which didn't go anywhere. – Kevin Carlson Sep 24 '12 at 4:27
~Brilliant answer – Paul Slevin Sep 24 '12 at 13:09

Let $\mathcal{C}, \mathcal{D}$ be categories. Let $\mathcal{D}^{\mathcal{C}}$ be the collection of functors from $\mathcal{C}$ to $\mathcal{D}$. If Ob$(\mathcal{C})$ is not a set, $\mathcal{D}^{\mathcal{C}}$ is not a category in the usual sense. One of the reasons that the universes are introduced is to remedy this problem.

Let $\mathcal{U}$ be a universe. An element of $\mathcal{U}$ is called a small set. It can be proved that $\mathcal{U}$ is not small. We usually consider only a category $\mathcal{C}$ such that Ob$(\mathcal{C}) \subset \mathcal{U}$ and Mor$(\mathcal{C}) \subset \mathcal{U}$. If Ob$(\mathcal{C})$ and Mor$(\mathcal{C})$ are both small, we say $\mathcal{C}$ is small.

-

For MacLane's foundations, we fix a universe $U$ whose elements are the "sets" and whose subcollections are the "classes." So a small category is one whose collections of objects and morphisms are both elements of the universe.

Not all categories are small: the first example is $\mathcal{S}et$, whose collection of objects is exactly $U$. If $\mathcal{S}et$ were small, we'd have $U\in U$, but this would contradict the axiom of foundation. But this begins to look weird, since we defined $U$ as some set, existent according to ZFC (or your favorite set theory,) that satisfies the axioms of a universe. That's why we define $\mathcal{S}et$ as the category of all small sets, that is, all sets which are elements of $U$. The universe axioms guarantee that we can't get from a small set to a large set using standard set-theoretic operations, so this definition is reasonable.

So, no, having small limits is not the same as having all limits. There isn't any limit of the image in $\mathcal{G}roup$ of the identity functor, for instance, since this would be a product of all groups, which would have to have every group including itself as a proper quotient.

As to your last question, if for every $A,B \in \mathcal{C}$, $\hom(A,B)\in U$, we say $\mathcal{C}$ is locally small. $\mathcal{S}et$ and the other main concrete categories are locally small, because the functions $B^A$ from $A$ to $B$ are a subset of $\mathcal{P}(A\times B)$, and the universe axioms guarantee $U$ is closed under products, powersets, and subsets.

-
when maclane defines a small category he says 'set' and not 'small set' though. – Paul Slevin Sep 23 '12 at 10:27
You're reading the wrong definition: a ‘category’ has a set of objects and a set of morphisms; a ‘small category’ has a small set of objects and a small set of morphisms. – Zhen Lin Sep 23 '12 at 10:44
does he not defíne ít as I saId on page 27 (chapter 8 Hom-sets)? – Paul Slevin Sep 23 '12 at 11:46
oops. I am an idiot, he defines it earlier in the middle of a paragraph – Paul Slevin Sep 23 '12 at 14:12