FOM: Simpson on Russell's paradox for category theory

[Robert M. Solovay]

	This posting is in response to a posting of Steve Simpson,
dated May 11, 1999 01:13:44 and entitled 
	FOM: Russell paradox for naive category theory 

Simpson's posting reports details of his version of Russell's
paradox. In this posting I want to do the following:

	1) Point out a step in Simpson's posting that I can't follow.
	2) Give a counterexample to one of Simpson's lemmas. [The
error is not at the point referred to in 1).]

	For all I know there is a slight variant of the lemma I
counterexample which supports Simpson's proof.

	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. However, 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. 

	In discussing Simpson's posting, I shall work in ZFC. Thus 
all categories will be "small". I presume that proofs that fail in ZFC
would also fail in the unspecified "set-theoretic background" in which
Simpson works.

	Simpson introduces two categories M and N. In a moment I will
recall the standard construction which associates to each poset a
category. M and N are the categories associated to {0,1} (= 2) with
its usual ordering and {0,1,2} = 3 with its usual ordering. 

	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.

	The lemma I am going to counterexample is the first lemma
following the statement of the theorem that there are no universal
categories. Before giving my counterexample, it is necessary to
rehearse some well-known definitions.

	A poset is a pair <X,R> where X is a set and R is a reflexive
transitive relation on X. Notice we do not require that R be
antisymmetric.

	Any such poset determines a category C(X,R) thus: The objects
of C are the members of X. If a, b are members of X then Hom(a,b) has
cardinality either 0 or 1. It has cardinality 1 iff (a,b) is in
R. It's sole member, then is the pair (a,b). There is precisely one
way to define identities and compositions so as to make C(X,R) a
category.

	We will identify a poset with the corresponding category. If
C_1 and C_2 are posets categories, then the functors from C_1 to C_2
are precisely the order-preserving maps.

	As usual in ZFC we identify each ordinal lambda with the set
of ordinals smaller than lambda. Because this posting is being written
in ascii, I write w for the set of non-negative integers.

	If a is a poset, I write a* for the poset with the same
underlying set but whose partial ordering is the converse of the
partial ordering on a. Viewed as categories, the * operation is just
the operation that takes a category to its dual.

	It is important that w* is not isomorphic [or even equivalent]
to w. Indeed, w has an initial object but no terminal object; w* has a
terminal object but no initial object.

	Notice that if a and b are posets, then there is a natural
bijection between the functors from a to b and the functors from a* to
b*.

	Any set of posets determines in an evident way a categorie of
categories. 

	We take c1 to be the category of categories whose members are
the categories 2,3,w.

	We take c2 to be the category of categories whose members are
the categories 2*, 3*, and w*. Then c2 is isomorphic to c1; c1 has as
members categories isomorphic to M and N. But no category of c2 is
isomorphic to the category w of c1.

	I believe the erroneous part of Simpson's argument occurs in
the following passage:

... 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.

	--Robert Solovay