FOM: Russell paradox for naive category theory

[Stephen G Simpson]

Carsten Butz 30 Apr 1999 11:27:29 writes:

 > As for sets you can form (gramatically) the "category of all
 > categories" (this is different to other structures: the collection
 > of all groups does not have a group structure, ...). After Russell
 > one _has_ to reflect on this and think about whether this gives
 > problems or not.  Since such a step from naive to non-naive is the
 > study of foundations, at the end I probably agree with Steve ...

As I think about this, it seems to me there is an analog of the
Russell paradox for naive category theory.  I outline it below.

Assumptions: Assume we are working in some sort of ``naive category
theory'' setting, i.e., category theory where the foundation
(set-theoretic or otherwise) has been left unspecified.

We begin with some easy category-theoretic definitions.

Define a *category of categories* to be a category c such that (i)
each object of c is a category, (ii) for any objects A and B of c, the
morphisms from A to B in c are exactly the functors from A to B, (iii)
for any object A of c, the identity morphism 1_A at A is the identity
functor on A, (iv) the composition law for morphisms of c is given by
composition of functors.

An *autistic* category is a category c such that (1) c is a catogory
of categories, (2) c is isomorphic to some category which is an object
of c.  A *pseudoautistic* category is a category which is isomorphic
to some autistic category.

For example, the trivial category, with one object A and one morphism
1_A, is pseudoautistic.  A category with one object A and two
morphisms, 1_A and f, is pseudoautistic if ff=f, non-pseudoautistic if
ff=1_A.  The category with two objects A and B and three morphisms
1_A, 1_B, f:A->B is not pseudoautistic.

Now suppose there exists a ``category of all categories'', i.e., a
category C such that (a) C is a category of categories, (b) every
category is isomorphic to some category which is an object of C.  Let
D be the full subcategory of C consisting of all categories which are
not pseudoautistic.  Then D is a category of categories.  Suppose
first that D is autistic.  Then D is isomorphic to some category E
which is an object of D.  Then E is pseudoautistic.  Hence, by
definition of D, E is not an object of D.  This is a contradiction.
We have shown that D is not autistic.  It can also be shown that D is
not pseudoautistic.  (This requires an argument, but I think it is
OK.)  By our assumption about C, D is isomorphic to some category E
which is an object of C.  Hence E is not psuedoautistic.  Hence E is
an object of D.  Thus D is autistic.  This is a contradiction.

Conclusion: There is no category of all categories.

Is this argument correct?  Is this kind of argument well known to
category theorists?

It seems to me that the above argument is devastating, in the sense
that it completely rules out any idea of ``the category of all
categories'', by showing that any such idea is inconsistent with
minimal assumptions of naive category theory.

If category theorists do not fully accept this argument, why not?

If category theorists *do* fully accept this argument, then they
should stop using language like ``the category of all categories''.

Set theorists stopped talking about ``the set of all sets'' a very
long time ago.

-- Steve