FOM: Russell paradox for naive category theory

[Stephen G Simpson]

This is a continuation the discussion of my version of the Russell
paradox for naive category theory.  Relevant earlier postings are mine
of 11 May 1999 and Solovay's of 11 March 2000.  Solovay raised some
objections to my argument, which I now want to answer.

I would like to thank Bob Solovay for his helpful remarks.

Solovay's main objection concerns the fact that the framework for my
version of the Russell paradox was not completely specified.  Solovay
says:

 > Simpson makes a point of the fact that he does not spell out the
 > set-theoretic framework in which he is working. I found the lack of
 > such a framework made it difficult for me to think about his proof.

Note that Solovay is assuming that the framework I have in mind is
set-theoretical.

Actually, as I stated in my posting, the framework that I have in mind
is one of ``naive category theory (set-theoretical or otherwise)''.
This was a key point in my posting, because the context was the
discussion of the alleged so-called ``categorical foundations'', where
category theorists are proposing to found mathematics on a
category-theoretic basis, replacing the usual set-theoretic foundation
formalized as ZFC.  The entire purpose of my posting was to make the
following foundational point: Even within an allegedly
non-set-theoretical ``categorical foundations'' framework, it is
impossible for category theorists to evade the Russell paradox and
speak of ``the category of all categories'', as they are sometimes
wont to do.

To answer Solovay's objection, let me now give a precise but tentative
formalization of naive category theory.  Let this formalism be called
NCT.  NCT is a theory in the predicate calculus with identity.  By
predicate calculus I of course mean first-order, classical, predicate
calculus.

NCT contains the following predicates, in addition to the identity
predicate.

   Cx: x is a category
   Oxy: x is an object of category y
   Mxyzw: x is a morphism from object y to object z in category w
   Ixyz: x is the identity morphism of object y in category z
   Dxyzw: x is obtained by composition of y with z in category w
   Fxyz: x is a functor from category y to category z
   Gxyz: x is a functor, and y corresponds to z under x

In addition to the usual axioms and rules of the predicate calculus
with identity, NCT contains axioms as follows, formulated in the
obvious way as predicate calculus sentences.

   Every morphism in a category x is a morphism from a unique object y
   of x to a unique object z of x.  Given morphisms in category x from
   y to z and from z to w, there is a unique composition morphism in x
   from y to w, and all compositions are of this kind.  Composition of
   morphisms obeys the usual associative law.  For every object x of
   category y, there is a unique identity morphism on x in y, which is
   a morphism from x to x in y and obeys the usual identity law.  If x
   and y are categories with the same objects and morphisms and
   composition, then x and y are identical.

   For every category x, there exists the opposed category, whose
   objects and morphisms are those of x and whose composition is the
   opposite of that of x.  There exists a category M consisting of two
   objects x and y and three morphisms: the identity morphisms of x
   and y, and a morphism from x to y.  There exists a category N
   consisting of three objects x, y, z and six morphisms: the identity
   morphisms of x, y, z, and morphisms from x to y, y to z, x to z.

   Every functor is a functor from a unique category x to a unique
   category y.  If x is a functor from y to z, then to each object
   (morphism) of y there corresponds under x a unique object
   (morphism) of z, etc etc.  If x and y are functors from z to w
   carrying identical objects and morphisms to identical objects and
   morphisms, then x and y are identical.

In addition, NCT contains axiom schemes saying that, given a category
x and a definable property P of objects of x, there exists the full
subcategory of x consisting of the objects of x having property P.
And, given two categories x and y and a definable relation R on
objects and morphisms of x and y, if the obvious necessary conditions
hold, then there exists the functor from x to y defined by R.  Here
definable properties and relations are expressed by formulas of the
predicate calculus, with parameters.  

(My arguments do not require the full strength of the above schemes.
Also, it may be useful for some purposes to supplement the above
predicates and axioms and schemes with additional ones.)

Within NCT, a *category of categories* is defined to be a category x
such that the objects of x are categories, the morphisms of x are all
functors between objects of x, composition of morphisms of x is given
by functor composition, identity morphisms of x are identity functors,
etc etc.  Two categories x and y are defined to be *isomorphic* if
there exists a functor from x to y which is an isomorphism of x onto
y, in the usual sense.

My claimed result is that the following is provable in NCT: ``There
does not exist a category of categories containing an isomorphic copy
of every category.''  This is my Russell paradox for NCT.

The outline of the proof of my result remains substantially as it was
in my 11 May 1999 posting.  As Solovay pointed out, there is an error
in that posting which needs to be corrected.  See below.

Solovay says:

 > whatever framework I supplied, I found it easy to find a
 > proof of the "non-existence of the category of all categories"
 > which is different from Simpson's.

I leave it to Solovay to explain what he means by ``the category of
all categories'', and to outline the proofs of his results.  However,
I note that Solovay's posting, as well as Solovay's remarks in
off-line correspondence with me, seem to confirm that the frameworks
considered by Solovay are set-theoretical, namely subsystems of ZF and
NBG.  Thus, my argument in the NCT framework appears to be
considerably more general.

Solovay's other objections have to do with the details of my proof
outline.  Solovay says:

 > The principle which he asserts without proof and which I am unable
 > to establish is the following. Let c1 and c2 be "categories of
 > categories". Suppose that M and N are objects of c1 and that c2 is
 > isomorphic qua abstract category to c1. Then c2 contains as objects
 > categories isomorphic to M and N.

I still claim that this is true, and in fact provable in NCT.  For the
proof, it is useful to note that M can be characterized up to
isomorphism by the fact that there are exactly three functors from M
to M, the identity functor and two others, call them f and g, such
that fg=ff=f and gf=gg=g.  Also, N can be characterized up to
isomorphism, in a similar vein.  I need to supply details, but I think
I can do so.

Solovay also provides a counterexample, showing that one of my lemmas
is incorrect.  However, there is a modified lemma which is correct and
suffices for my purpose.  Here is the corrected lemma.  I claim that
this is provable in NCT.

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 or anti-isomorphic to some
category belonging to c2, and vice versa.

The only change here is the replacement of ``isomorphic'' by
``isomorphic or anti-isomorphic''.  My definition of *autistic* is to
be modified similarly.  With these changes, the details of proof are
as outlined in my 11 May 1999 posting.

-- Steve