# Set-Theoretic Issues/Categories

It is a major bummer that one cannot strictly speaking talk about the category of all categories without saying "it is not really a category, since the morphisms between objects may form a class" and "there are set-theoretic issues". However, these words seem to be just phrases, since I haven't seen them explained in detail. Why can't we lax the requirement that the morphisms form a set? We may no longer talk about representing functors (at least it won't be into $\bf{Set}$), but that may be OK in certain contexts. I am mostly scared of running into inconsistencies. I presume that if one tries to do it in the most naive way, there may be arguments of Russel's paradox type and that would be bad. Basically my questions are:

1) Is it possible to extend the definition of categories to things that may have morphism classes between two objects in a consistent way?

2) What are the main obstacles that one has to concern himself with when trying to do this?

-
Take a look at en.wikipedia.org/wiki/…. – jd.r Apr 22 '12 at 2:08
If you allow a category to have a class of objects, you cannot even speak about the "class" of all categories, so you already have a problem with the objects of the category of categories. – Guillaume Brunerie Apr 22 '12 at 2:25
For a similar question see mathoverflow.net/questions/48810/… – Ralph Apr 22 '12 at 6:50
Your dilemmas are a consequence of your presuming that classical set theory in the style of Zermelo and Fraenkel is the only possible foundation. – Andrej Bauer Apr 22 '12 at 9:54
The underlying problem is that, in the same way that the set-theoretic paradoxes showed that naive set theory is inconsistent, if you pursue "naive category theory" far enough you will run into the same issues, no later than the point at which your naive category theory is able to interpret enough naive set theory. – Carl Mummert Apr 22 '12 at 12:25

Regarding (1), the definition of category already doesn't rule out instances in which the collection of morphisms between two objects might be class-sized; these are known as categories which fail to be locally small. Regarding (2), the main issue is that there will come points when size considerations play crucially into the possibility of certain constructions. I recommend Mike Shulman's very nice article "Set theory for category theory," which uses Freyd's special adjoint functor theorem to illustrate that point (in his section 2. Size Does Matter), and then goes on to explore many of the foundational approaches that can be taken to address considerations of size in category theory, e.g. Grothendieck universes, NBG set theory, Morse-Kelley set theory, and so on.

-

Since you don't seem to want to leave ZFC, here's a taste of the issues you might face if you try to work with a stratified universe. (Here I mean the ordinary English word ‘stratified’, rather than a formally stratified logical system like Russell's type theory.) First, a warm-up:

Exercise. Develop the theory of finite categories and locally finite categories.

Now, let $\lambda$ be any infinite limit ordinal greater than $\omega$. The set $V_\lambda$ (!) of all sets of rank less than $\lambda$, together with the set (!) of all functions inside $V_\lambda$, forms a small category $\textbf{Set}_\lambda$ satisfying the axioms of ETCS (the elementary category of sets). As long as you don't try to invoke unbounded separation or replacement, ETCS is a reasonable foundation in which to do mathematics. Thus, we obtain an infinite ascending sequence of full subcategories $$\textbf{Set}_{\omega + \omega} \subset \textbf{Set}_{\omega + \omega + \omega} \subset \cdots \subset \textbf{Set}_{\infty}$$ where $\textbf{Set}_{\infty}$ denotes the (meta)category of all sets. Immediately we have some problems to resolve:

1. Since each $\textbf{Set}_\lambda$ is a priori a different category, there is no reason to believe that limits and colimits in $\textbf{Set}_\lambda$ will agree with limits and colimits in $\textbf{Set}_\kappa$, if $\lambda \lt \kappa$. Fortunately, it is a fact that if $\mathcal{D}$ is a full subcategory of $\mathcal{C}$, and the limit (resp. colimit) $X$ of a diagram in $\mathcal{D}$ exists in $\mathcal{C}$, then as long as $X$ is in $\mathcal{D}$, $X$ will be the limit (resp. colimit) of that diagram in $\mathcal{D}$. In more sophisticated words, the inclusion of a full subcategory always reflects limits and colimits. The trouble is that it may not preserve limits and colimits.

2. None of the categories $\textbf{Set}_\lambda$ have all small limits or colimits. This is due to an observation of Freyd: a small category with all small limits (or colimits) is a preorder category. However, it has all internally-indexed limits and colimits, in the following sense: if $\mathbb{C}$ is an internal category in $\textbf{Set}_\lambda$, meaning $\operatorname{ob} \mathbb{C}$ and $\operatorname{mor} \mathbb{C}$ are sets in $\textbf{Set}_\lambda$, and $A : \mathbb{C} \to \textbf{Set}_\lambda$ is an internal diagram (see [CWM, Ch. XII, § 1]), then $\varprojlim A$ and $\varinjlim A$ both exist in $\textbf{Set}_\lambda$ via the usual construction. In particular, every $\textbf{Set}_\lambda$ is closed under finite limits and colimits.

3. Though $\textbf{Set}_\lambda$ is a small category, it is not an internal category in $\textbf{Set}_\lambda$ itself! Instead, we must go up the hierarchy in order to realise $\textbf{Set}_\lambda$ as an internal category. This a priori seems to mean that we cannot talk about a genuine functor $\mathbb{C} \to \textbf{Set}_\lambda$, where $\mathbb{C}$ is an internal category in $\textbf{Set}_\lambda$, without leaving $\textbf{Set}_\lambda$, and once we leave $\textbf{Set}_\lambda$ we have to worry about whether the results obtained in a bigger category $\textbf{Set}_\kappa$ are still valid in our original category $\textbf{Set}_\lambda$, cf discussions about "change of universe" in SGA.

To be clear, this is a non-trivial problem. It is not so easy to replace a genuine functor $\mathbb{C} \to \textbf{Set}_\lambda$ with an internal diagram in $\textbf{Set}_\lambda$. For example, let $\omega \to \textbf{Set}_{\omega + \omega}$ be the functor $n \mapsto \omega + n$. The obvious way of turning this into an internal diagram uses the axiom of replacement and results in a set of rank at least $\omega + \omega$ – in other words, it is not internal to $\textbf{Set}_{\omega + \omega}$! Nonetheless, for cardinality reasons, it is true that every genuine functor $\mathbb{C} \to \textbf{Set}_\lambda$ is isomorphic to an internal diagram in $\textbf{Set}_\lambda$.

There are other subtleties to think about. A well-known result of Kan implies that the category of presheaves on a small category $\mathcal{C}$ has $\mathcal{C}$ as a colimit dense subcategory via the Yoneda embedding $\mathcal{C} \to [\mathcal{C}^\textrm{op}, \textbf{Set}_\infty]$, but if $\mathcal{C}$ is only a locally small category, then this is in general false: in other words, the relative sizes of $\mathcal{C}$ and $\textbf{Set}_\infty$ matter!

-
Are there stratified theories in which we can develop theory of ordinals, and well-foundedness enough to develop the notion of "rank" at all? Or do you mean that you work inside a model of ZFC? – Asaf Karagila Apr 22 '12 at 13:18
@Asaf: I mean "stratified" as a word in ordinary English, not logic! – Zhen Lin Apr 22 '12 at 13:30
Oh! :-) You should probably point that out in the answer! – Asaf Karagila Apr 22 '12 at 13:40
@Zhen: Could you provide us with a reference please? – user16974 Apr 22 '12 at 18:29
@Ali: A reference ... for what? Internal category theory is discussed extensively in [Johnstone, Sketches of an elephant, Part B], but I have not read it. There is also an informal discussion in [Bénabou, Fibered categories and the foundations of naive category theory]. An introduction to ETCS can be found in [Lawvere and Rosebrugh, Sets for mathematics]. – Zhen Lin Apr 22 '12 at 18:41

I am not sure if this will be exactly on point, but it seems to be toward the right direction. Have a look at the book "Abstract and Concrete Categoies". Before the book delves into category theory proper, it discusses foundations. The book lays out what properties sets should have. Then the book moves on to enlarging the types of collections to classes, which are certain types of collections of sets. Often one stops here ( and I have wondered why one stops here). The book then defines conglomerates which are supposed to be collections of classes. All the while it is stated what properties these collections should have. I imagine one could iterate this process indefinitely. A link to the book is:

http://katmat.math.uni-bremen.de/acc/acc.pdf

-
This discussion starts on page 13. – Lunasaurus Rex Apr 22 '12 at 4:38
Thanks for the answer. This book seems to be helpful! – nerses Apr 22 '12 at 5:41

The Calculus of Constructions is a higher-order, typed lambda calculus that the Coq proof assistant is based on. In this logic, you can do pretty much what you're asking for. To pull it off, the types are stratified in a countable hierarchy. When interpreted in set theory, they correspond to countably many Grothendieck universes.

So, one way to not have "set theoretic issues" is to give yourself countably many levels of "classes" to work with. That requires an extension to ZFC - a mild one, to be sure - but one that many mathematicians are uncomfortable with.

-
It's not clear to me that many mathematicians are "uncomfortable" with it, in the sense that they might strongly think it's false. The large cardinal assumptions are just not among of the axioms of ZFC, so they get marked as extra assumptions in proofs. – Carl Mummert Apr 22 '12 at 12:31