FOM: Set theory vs category theory: Representability of categories

[Vaughan Pratt]

From: Soren Moller Riis <smriis at brics.dk>
>Footnote and another question: I am very fascinated of some of the more
>concrete aspects of category theory (though it is not my own research
>area). In computer science (especially in semantics) I am convinced
>that category theory have been much more successful than set theory
>(which is not even an alternative).  In many areas of mathematics there
>exists a central representation theorem.  For C^*-algebras we have the
>Gelfand-Neumann-Segel theorem showing every abstract C^*-algebra have
>a concrete representation as functions of suitable space.  We have
>a representation theorem for Boolean Algebras. Abstract groups has a
>representation as subgroups of permutation groups.  I am wondering: Why
>is there no representation theorem for category theory? There are many
>different categories with many different properties. If the axioms of
>a category are well stated there ought to be a representation theorem.
>Or is this against the ideology?

A number of representation theorems were found by Czech algebraists and
category theorists during the latter half of the 1960's, representing
arbitrary small categories as categories of familiar concrete structures
and their homomorphisms.  Two notable representations are in terms
of semigroups, and of directed graphs.  In each case the theorem is
that every small category is representable as a category of semigroups
(directed graphs, etc.) and their homomorphisms (of the standard kind
in each case).

The criteria used here for representability of objects  a  and morphisms
f:a->b of a category C by respectively structures F(a) and homomorphisms
F(f):F(a)->F(b) of the concrete representing category D are as follows.

(i) F:C->D is a *functor*, that is, a graph homomorphism (viewing the
morphisms of C and D as edges of their respective underlying graphs)
that preserves composition and identities (a condition exactly analogous
to those of monoid homomorphism and group homomorphism).

(ii) F is *faithful*, i.e. for any pair a,b of objects of C, distinct
morphisms f:a->b of C are represented by distinct homomorphisms
F(f):F(a)->F(b) of D.

(iii) F is *full*, i.e. every homomorphism from F(a) to F(b) in D is
the representation under F of some morphism from a to b in C.

The intuitive meaning of full and faithful is that the representing
object is just as stiff as the object it represents when you wiggle both.
Fullness means it is at least as stiff (D offers no new transformations),
while faithfulness means it is at most as stiff (no transformations are
lost by identification).

Unfortunately the project of embedding arbitrary categories fully and
faithfully in familiar concrete categories has turned out not to have
the impact of its counterparts in group theory (permutations), Boolean
algebras (fields of sets), distributive lattices (rings of sets), etc.
These results have in consequence not been widely publicized in the
introductory categorical literature.

The most objectionable feature of these embeddings in my view (and I
am aware of no other serious objection) is their lack of respect for
concreteness itself.  If one takes for C a small *concrete* category,
such as all quotient groups of the additive group of natural numbers
and their group homomorphisms, the above-mentioned embedding represents
the finite group Z_2 as an infinite semigroup!  And if "natural numbers"
is replaced by "reals", the corresponding embedding represents Z_2 as an
uncountable semigroup.  Such a lack of respect for concreteness would
seem to undermine the very point of representing abstract objects as
concrete structures.

In contrast a finite group of order n is representable by permutations of
n things, a finite Boolean algebra as a field of subsets of a finite set,
and so on.  In these better-known representation theorems, cardinality
is respected, typically to within at most two exponentials (which in
the infinite case means to within two beth numbers) and often much better.

This unsatisfactory situation with the concrete representation of
objects of arbitrary categories prompts the speculation that the notion
of category is too broad to admit of any improvement in the situation.
After all, any random graph G is made a category by adding to its
edges all paths in G, with composition defined as path concatenation
(the free category generated by G).  How could there possibly be a
cardinality-respecting representation of the vertices of a random graph
in terms of the objects of a familiar concrete category?  When one can
do any violence one wishes to the structure by adding an edge at random
between any two vertices, it would seem that any concrete representation
of each object would inevitably have a cardinality on the order of the
whole category.

But in fact there *is* a representation that does the job.  Let us make
two easily understood modifications to the usual notion of topological
space.

First, drop the requirement that the open sets be closed under arbitrary
union and finite intersection.  (The role of this traditional restriction
is in effect to limit the "signature" of a topological space to just that
needed to express the notion of limit, or even less with the more discrete
spaces; dropping it greatly broadens the range of possible signatures.)

Second, in place of the customary two degrees of membership in the open
sets (ordinary sets), permit a set K of possible degrees of membership,
call such open sets fuzzy (Zadeh's fuzzy sets are the case K the reals).

Define continuity as usual for functions between topological spaces,
wording the definition in such a way however that its extension to
fuzzy sets is made clear.  Specifically, f:X->Y is continuous when for
every open set g:Y->K (here expressed as a characteristic function),
the composite

		   f      g
		X ---> Y ---> K

is an open set of X.  When K = {0,1} it is easily verified that this is
the standard notion of continuity.

Call such generalized topological spaces Chu spaces over K.  An even more
general notion was first studied in detail by Peter Chu in the 1970's,
a master's student of Michael Barr.  The more elementary version above
was first studied by Lafont and Streicher in 1991 (LICS) under the rubric
of games but the term "Chu construction" was already in the computer
science air in the late 1980's making it too late to change the name.

Definitions.

1.  A concrete category is a pair (C,U) where C is a category and U:C->Set
is a faithful functor, the "forgetful" functor giving the *underlying
set* of each object along with the realization of each morphism of C as
a function (a morphism of Set).

2.  A concrete functor F:(C,U)->(D,V) between two concrete categories
is one satisfying VF = U.  That is, the underlying set VF(a) of the
representation F(a) of a is the same as the underlying set U(a) of
a itself.

Remark.  The elements of all the representing sets of a small concrete
category (C,U) themselves form a single set, namely the disjoint or
marked union of all the sets in the category.  Call this set Elt(C,U),
the set of elements of (C,U).

A very minor technicality requires the notion of an *honest* concrete
category, namely one having, for all objects a and b, a morphism from
a to b if U(a) is empty (necessarily at most one, by concreteness).
Dishonest concrete categories cannot be represented as below because
the empty topological space has nowhere to store the information as to
which other spaces it does or does not have functions to.  (Thanks to
Peter Freyd for pointing out the lacuna in my proof that necessitated
this condition.)

Theorem.  Every small honest concrete category (C,U) embeds fully,
faithfully, and concretely in the category of Chu spaces over Elt(C,U).

(This theorem enjoys all the advantages of the previous embeddings, but
in addition satisfies the strongest possible concreteness requirement:
the representing object has the *same* underlying set as the object it
represents, and the representing morphisms viewed concretely are exactly
the same functions.)

Proof.  Let b be an object of C with underlying set X = U(b).  Represent
b by a generalized topological space X, having one open set Y_h for
each morphism h:b->c in C for some c.  Form Y_h by taking the degree of
membership of each point x in Y_h to be U(h)(x), i.e. the element of U(c)
which is the image of x under the underlying function U(h) of h.

It is then straightforward to show that this representation is faithful,
full, and concrete.

Obviously the burden of the obstacle that we have overcome has merely
been shifted to the open sets, the number of which must now be on the
order of the cardinality of the category.  But since when has the number
of open sets been an obstacle to topology?  The points of a space are
clearly visible, but our embedding has left these untouched.  Who has
ever seen an open set or cares about how many there are?

For more information on Chu spaces consult

	http://boole.stanford.edu/chuguide.html

My original interest in Chu spaces was as a model of concurrent
behavior.  More recently I have become interested in them as a primarily
set-theoretic foundation for mathematics that more directly emulates
what category theory has to offer than the extant litany of single-sorted
and and multisorted relational structures and algebras with and without
(ordinary) topology and their standard homomorphisms, all of which are
fully, faithfully, and concretely representable by Chu spaces.

---
Name: Vaughan Pratt
Position: Professor of Computer Science
Institution: Stanford University
Research interests: Foundations of computation and mathematics
For more information: http://boole.stanford.edu