FOM: Russell paradox for naive category theory

[Stephen G Simpson]

Simpson 6 May 1999 11:29:10

 > > The real question that I was asking is: Why do people keep
 > > talking about ``the category of all categories'', when there is
 > > (my version of) the Russell paradox for naive category theory?
 ...

Butz 6 May 1999 14:38:04

 > Who does this? I for myself have not seen this. And I would not
 > trust a paper doing this unless the typing is easy to restore
 > (i.e., that it is meant the (large) category of all (small)
 > categories, i.e., Cat).

According to section I.6 of MacLane's ``Categories for the Working
Mathematician'', set-theoretic foundations of category theory are not
entirely satisfactory because they require artificial maneuvers like
the small/large distinction, Grothendieck universes, etc.  One gets
the strong impression that MacLane is wishing for an alternative
foundation which removes the need for these maneuvers.  Section II.5
is entitled ``The Category of All Categories'' and grudgingly invokes
a small/large distinction in order to state the results.

MacLane and other category theorists who talk this way are perhaps not
aware how much would be lost by abandoning set-theoretic foundations
and insisting on something like the category of all categories.  My
Russell paradox for naive category theory brings this point home in an
apparently new way.

In 6 May 1999 11:29:10 I said:

 > It seems to me that (my version of) the Russell paradox for naive
 > category theory is fairly hard to evade.  In order to evade it, you
 > would have to evade a very simple category-theoretic notion, what I
 > called pseudoautistic categories.  A category C is said to be
 > pseudoautistic if there exists a category of categories C1 and a
 > category C2 belonging to C1 such that C is isomorphic to both C1
 > and C2.  This definition involves only perfectly clear and
 > straightforward notions of naive category theory.
 > .... stratification does not seem to provide a way out.

Subsequently, as a result of off-line discussion with Forster and
Holmes, I now see that the concept ``pseudoautistic category'' cannot
be defined by a stratified formula.  Thus NFU avoids my Russell
paradox for naive category theory, but it does so at terrific cost.

Just for reference, let me give some more details of my Russell
paradox for naive category theory.

Setting: We are working in a naive category theory setting, i.e.,
category theory where the foundation (set-theoretic or otherwise) has
been left unspecified.

Definition. A *category of categories* is 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.

Definition.  A category c is *universal* if (i) c is a category of
categories, (ii) every category is isomorphic to some category which
belongs to c.

Theorem.  There is no universal category.

In order to give the proof, we use the following definitions and
lemmas.

Let M be the category with exactly two objects A and B and
exactly three morphisms 1_A, 1_B, and f: A -> B.

Let N be the category with exactly three objects A, B, C and exactly
six morphisms 1_A, 1_B, 1_C, f: A -> B, g: B -> C, h: A -> C.

Lemma. Let c1 and c2 be two isomorphic categories such that (i) c1 is
a category of categories, (ii) c2 is a category of categories, (iii)
c1 contans categories that are isomorphic to M and N.  Then every
category belonging to c1 is isomorphic to some category belonging to
c2, and vice versa.

Proof (sketch).  If C is any category belonging to c1, there is an
obvious one-to-one correspondence between morphisms of C and functors
from M into C, and compositions of such morphisms are picked out by
functors from N into C.  Thus the isomorphism types of categories
belonging to c1 are determined by the isomorphism type of c1 itself.
Furthermore, the same goes for c2, because c2 also contains categories
isomorphic to M and N.  The lemma follows.

Definition.  A category c is *autistic* if (i) c is a catogory of
categories, (ii) c is isomorphic to some category which is an object
of c.  A category c is *pseudoautistic* if it is isomorphic to some
autistic category.

Lemma. Let c be a category of categories such that (i) c is
pseudoautistic, (ii) c contains categories isomorphic to M and N.
Then c is autistic.

Proof.  This follows immediately from the previous lemma.

To prove the theorem, let c be a universal category.  Let d be the
full subcategory of c consisting of all categories belonging to c
which are not pseudoautistic.  Then d is again a category of
categories.  Also, since M and N are not pseudoautistic, d contains
categories isomorphic to M and N.  Suppose first that d is autistic.
Then d is isomorphic to some category e which belongs to d.  Then e is
pseudoautistic.  Hence, by definition of d, e does not belong to d.
This is a contradiction.  We have shown that d is not autistic.  It
follows by the previous lemma that d is not pseudoautistic.  Since c
is universal, d is isomorphic to some category e which belongs to c.
Hence e is not psuedoautistic.  Hence e belongs to d.  Thus d is
autistic.  This is a contradiction.  The theorem is proved.

-- Steve