FOM: foundations of category theory

[Stephen G Simpson]

This is a response to messages of Hasan Keler and Matt Insall of
February 20, 2000 on category theory.

According to Hasan Keler, Edwin Mares said that category theory is the
1 percent of mathematics for which ZFC is not a foundation.
Apparently this was said off-line, i.e., not here on FOM.

I don't know the full off-line context of the Mares remark, but taken
by itself, the Mares remark is seriously misleading in at least two
respects.

First, category theory is normally formulated with an underlying
set-theoretical foundation, either ZFC or some closely related system
such as NBG, or ZFC plus an inaccessible cardinal.  See for instance
my FOM postings of May 19, 2000, related to category theory, including
a summary of the foundational appendix of the category theory textbook
by Herrlich and Strecker.  (Unfortunately, in some discussions of the
foundations of category theory, there is a tendency to overplay an
alleged need for set-theoretic assumptions beyond ZFC.)  

Moreover, it is quite clear that most if not all of category could be
given a perfectly adequate ``small category'' foundation, entirely
within ZFC.  And there would be logical advantages to this approach.
See the discussion of ``small category theory'' here on FOM in April
and May, 1999.

Second, the Mares remark leaves completely out of account the work on
genuine uses of large cardinals (far beyond ZFC) in mathematics.  I
have in mind the use of large cardinals in descriptive set theory
(Solovay, Woodin, Steel, Martin, ...) and combinatorial set theory
(Ramsey cardinals, etc etc) and Friedman's work on finite
combinatorial independence results using large cardinals.

Insall:

 > Actually, some categories are sets.  These are, as I recall, called
 > ``small categories''.

That is correct.  

 > In a model-theoretic sense, however, I expect that even the theory
 > of categories can be realized, if it is consistent, by a model
 > within some model of ZFC.

What is ``the theory of categories''?  Is it a formal theory like ZFC?
I think it is a branch of algebra, just like the theory of groups or
the theory of rings.  But, if somebody were to make it into a formal
theory, there is no doubt that it could be interpreted into ZFC or
some slight extension of ZFC, just as group theory can be developed in
ZFC.  Indeed, this is the usual foundation of category theory.

 > Basically, if V is a given model of ZFC, then there should be a
 > model W of ZFC for which V is a member of W.  Then the proper
 > classes of V are sets in the model W, so in particular, the
 > category, in V, of all topological spaces, is a model, in W, of the
 > category of all topological spaces in V.  

This vague discussion seems to be a loose exposition of something like
the theory of ``sets, classes, conglomerates'' as presented in the
Herrlich-Strecker appendix.  ZFC plus an inaccessible is more than
enough as a foundation for this.

 > For instance, I am certain there is an appropriate formulation of
 > AC in terms of categories, which, for some theories of categories
 > holds, and for other such theories, does not hold.

Well, some categories satisfy ``for all epimorphisms f:X->Y there
exists a morphism g:Y->X such that fg:Y->Y is the identity morphism'',
and some do not.  Is this what you mean?  In any case, there are a
great many different kinds of categories with different properties.

 > I have, however, wondered at times, how category-theory supposes to
 > get around a paradox related to that of Russell, for I have seen
 > references (in Herrlick and Strecker, for example) to a ``category
 > of all categories''.

The answer to this is that category theory *cannot* get around the
Russell paradox.  When category theorists speak of ``the category of
all categories'' (as they often do), they are whistling in the dark.

In some FOM postings around May 11, 1999, I came up with a fairly
general argument which is a category-theoretic analog of the Russell
paradox.  The argument takes place in an informal ``naive category
theory'' setting and could easily be transplanted to a variety of
formal settings.  The argument concludes that, not only does ``the
category of all categories'' not exist, but there is no category of
categories containing *an isomorphic copy of* every category.

-- Steve