FOM: small category theory

[Till Mossakowski]

Stephen G Simpson wrote: (Thu, 29 Apr 1999 18:39:59)

> Till Mossakowski writes:
>  > Category theory is largely concerned with the study of smallness
>  > conditions, so the distinction between classes and sets (and
>  > categories possibly being classes) is crucial for category theory.
> 
> I'd like to follow up on these points.  What is a ``smallness
> condition''?  Can you give some examples?  What major insights
> concerning ``smallness conditions'' has category theory obtained?

By a smallness condition, I mean a condition stating that a certain
class has the size of a set (or that some set with a specific
property exists, in a context where the existence of a class
with that property is obvious).

A typical examples of smallness condition is the property
of a category being well-powered (co-well-powered), 
which means that for each object, the class of its subobjects 
(quotient objects) has the size of a set.

There are a lot of theorems of the form
"weaker structural property plus smallness condition implies
 stronger strucutral property".

For example:
Let C be a category that
- is cocomplete,
- has a separator, and
- is co-well-powered.
Then C also is complete.

(For the discussion, it is not essential to know these technical
terms, except that (co)completeness is an important structural
property, while (co)well-poweredness is a smallness condition.)

> So far as I know, the terms ``small'' and ``large'' in category theory
> refer only to a distinction that was borrowed from set theory, namely
> the distinction between sets and proper classes.  And maybe category
> theory has made some use of some other distinctions that were also
> borrowed from set theory.  For example, there is the distinction
> between cardinality less than kappa and cardinality equal to kappa,
> where kappa is some fixed inaccessible cardinal.  This is what
> category theorists call Grothendieck universes.  This idea also came
> from set theory, didn't it?  For example, MacLane's definition of a
> Grothendieck universe in his book ``Categories for the Working
> Mathematician'' is given in terms of set theory.
> 
> Is there a good way to get at these distinctions in purely
> category-theoretic terms, not using concepts borrowed from set theory?
> Did category theory obtain any insights not already obtained by set
> theory?  Please enlighten me.

I don't know. As far as I know, category theory borrows these
things just from set theory (this is what a leading
category theorist told me).
Perhaps people working with internal categories in a topos
have made some progress here?
 
>  > I wonder whether category theory can be founded entirely on
>  > sets.
> 
> I'm not sure what you have in mind here, but let me mention a specific
> proposal.  What would be lost, and what would be gained, if category
> theory restricted itself to ``small'' (i.e. set size) categories?
> Let's call this subject ``small category theory''.
> 
> It seems to me that, if we were to replace category theory by small
> category theory, then essentially nothing would be lost, at least with
> respect to applications.  (See also my posting of 22 Apr 1999
> 17:42:45, concerning how this would work in Hartshorne's book on
> algebraic geometry.)

For small categories, the above theorem just reduces to
A small category is cocomplete iff it is complete.
But this is relatively uninteresting, because (co)complete small
categories are just (well, modulo some easy coding) complete lattices, 
and the theorem reduces to the well-known fact that a sup-complete 
lattice also is inf-complete. (Note that a category is complete
iff it has all *small* limits.)

To enlighten this point, let me introcude a more explicit formulation 
of the above theorem:

Let kappa be an inaccessible cardinal.
Let C be a category of size <= kappa that 
- 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.

The interesting application of this theorem is a category of
size exactly kappa, since only trivial categories of size < kappa
have all colimits of size < kappa.

It does not seem to be possible to reformulate the above theorem
while using only "of size < kappa", and not using "of size <= kappa"
(or "of size = kappa"). If one tries to do so, one probably has 
to destroy its essential content and end up with an assertion like
"A small category is cocomplete iff it is complete." which is
relatively uninteresting.

>But fields aren't ``essentially algebraic'' in this sense either, are
>they?  But small categories are, right?

Yes.

>Anyway, I apologize for stating my point somewhat carelessly.  But I
>still think my point is correct.  When I said that a small category is
>an algebraic structure, I meant this in a naive sense, i.e. it is a
>set (the set of arrows) together with a partially defined operation
>(composition of arrows), and maybe a distinguished subset (the
>identity arrows) and is required to satisfy certain simple laws
>(associativity etc).  My point is that you could write an algebra book
>consisting of chapter 1 on groups, chapter 2 on rings, chapter 3 on
>fields, chapter 4 on small categories, etc.  It is all algebra.

Completely agreed. Indeed, F. Borceux has called his three-volume
book on category theory "handbook on categorical algebra".

>This is why I questioned Mossakowski's comment that category theory is
>*particularly* concerned with the small/large (i.e. set/class)
>distinction.  It seems to me you can make the same distinction in any
>branch of algebra, so this distinction does not particularly belong to
>category theory.

It is because in category theory, structural properties are intimately
linked with smallness conditions (i.e. the distinction between
"of size < kappa" and "of size <= kappa"), while this seems 
not to be the case for other branches of algebra.

>  > The more exciting story would of course be a foundation that would
>  > allow to reduce the amount of study of smallness conditions within
>  > category theory, and that would allow to concentrate on the structure.
>  > But this seems to be heavily difficult, if not impossible.
> 
> Do you mean you want something like the category of all categories?

Yes, something like that.
One would like to get rid of the distinction "of size < kappa"
and "of size <= kappa", but this seems to be hard, because the
distinction is intimately linked with the structural properties.
 
> Has anyone ever tried to set up something like this on the basis of NF
> set theory?  I don't know enough about NF to know whether this makes
> sense, but I seem to have heard that NF has the set of all sets ....

As Carsten Butz mentiond, Colin McLarty has shown that NF is of not
so much use here, since the category of categories would not be
cartesian closed.

Till Mossakowski