FOM: small category theory

[Till Mossakowski]

Stephen G Simpson wrote: (Sun, 2 May 1999 14:51:35)
>It seems to me that it would be a good idea for category  theorists to
>take account of standard set-theoretic notions (cardinality  etc) in
>order to clear up all this confusion and obtain sharper  theorems.  Why
>are category theorists apparently reluctant to do this?

To clarify this, let me sum up. Several ideas for 
the foundation of category theory have been proposed:

1. Naive small category theory
------------------------------
Require categories to be sets, and work with set-indexed 
limits.

This does not work well, because set-sized categories can have 
all set-indexed limits only if they are equivalent to pre-orders,
i.e. not very interesting.

2. Reflected small category theory
----------------------------------
Let kappa be a cardinal with appropriate closure properties.
Require categories to be sets of size <= kappa, and consider 
limits of size < kappa.

This works better, since non-trivial categories of size <= 
kappa can have all limits of size < kappa.
However, I have cited a standard theorem
(cf. Adamek, Herrlich, Strecker: Abstract and concrete
 categories, p. 200), reformulated in this setting:

Let kappa be a regular cardinal.
Let C be a category of size <= kappa that
      - has hom-sets of size < kappa
      - has all colimits of size < kappa,
      - has a separator, and
      - has quotient-object-classes of size < kappa,
Then C also has all limits of size < kappa.

Now
(1) The assumption of hom-sets of size < kappa
is necessary: In the proof, coproducts indexed by
hom-sets are taken.

(2) Regularity of kappa is needed because, e.g.,
a product \Pi_{i\in I} hom(S,A_i) is expected to yield
a set of size < kappa, where I and hom(S,A_i) 
have size < kappa.

(3) To be able to construct a non-trivial category
satisfying the first two assumptions of the theorem,
we need the assumption that kappa is a strong limit
cardinal (see my message from 1st May).

Altogther:
To be able to apply the theorem in a useful context,
we need that kappa is inaccessible, which goes
beyond ZFC. Note that the above theorem is only one
theorem of this kind, I believe that a similar argument
holds for a large number of other theorems.
Thus, "small" category theory does not make much sense.

3. Category theory in VNBG
--------------------------
In this setting, we can do quite a lot of useful
category theory, and circumvent the above problems,
without the need to assume an inaccessible cardinal
(Steve Simpson noted that VNBG is conservative over
ZFC).

However, there are still some -quite famous- theorems
which do need more. For example, the Yoneda embedding
theorem. It states that the functor

E : A -> [A^op , Set]

defined by

E(A--f-->B) = hom(_,A) -- _ o g --> hom(_,B)

(where _ o g is composition with g)

is full and faithful.

The theorem is used quite often.
Now the functor category [A^op , Set] of all
functors from A^op to sets and all natural
transformations between them is of the size
of the collection of all functions from
a class to a class, and hence ifself not a class,
and thus not definable in VBNG.

4. Category theory in ZFC + one universe
   (or one inaccessible cardinal kappa)
----------------------------------------

In this setting, we can distinguish small categories
(those of size < kappa), large categories (those of
size = kappa), and quasi-categories (those of size 
> kappa). Then, we can form the functor 
quasi-category [A^op , Set].

The assumption of more than one universe (or inaccessible
cardinal) is very rarely needed, if it is needed at all.
 



> Your comment on Herrlich-Strecker is not very clear.  I would be very
> surprised if Herrlich-Strecker include a phrase such as ``hom sets of
> size less than kappa'' in their definition of ``category''.  Perhaps
> what you mean is that they define a category to have small hom sets,
> i.e. it is required that for all objects A and B, Hom(A,B) is a set.

Actually, Herrlich and Strecker use the one-universe foundation,
so essentially they say hom sets of have size less than kappa,
where kappa is a fixed inaccessible cardinal.

> After all, ``smallness conditions'' are only
> a special case of cardinality conditions.  Notions such as cardinality
> and the distinction between sets and proper classes were first
> formulated in the context of set theory, not category theory, and it
> seems to me that they are best studied in the set-theoretic context.

Agreed. Category theory has set-theoretic foundations, and it studies
the interplay of smallness conditions with the structural properties
(and not the smallness conditions for themselves).

Till Mossakowski