Set-Theoretic Issues/Categories - MathOverflow

Set-Theoretic Issues/Categories

2012-04-22T01:04:12Z

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?

Answer by Lunasaurus Rex for Set-Theoretic Issues/Categories

2012-04-22T04:37:33Z

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

Answer by Neil Toronto for Set-Theoretic Issues/Categories

2012-04-22T05:00:06Z

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.

Answer by Ed Dean for Set-Theoretic Issues/Categories

2012-04-22T09:02:47Z

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.

Answer by Zhen Lin for Set-Theoretic Issues/Categories

2012-04-22T13:15:33Z

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:

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.
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.
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!