[Prev][Next][Index][Thread]

Mitchell's problem

Date: Mon, 19 Sep 88 16:32:15 CDT

I tried to post this note earlier and failed, so I'll try
again.
	"Problem for domain theorists: what is the smallest 
category containing your favorite domains (Scott domains, L-domains,
whatever you like) and closed under pullbacks?"

	I would like to amplify on Andy Pitt's response to John
Mitchell's query.  The theory of sketches treats exactly this kind of 
question.  (See, Barr and Well, Toposes, Theories and Triples,
Springer-Verlag,  or my paper, Categorical Aspects of Data Type
Constructors, TCS 50, 103-135.)  Sketches are presentations of
equational Horn theories (actually a bit more).  There is a sketch,
S1, for categories with finite products, in the sense that the 
category of models of this sketch is the category of small categories
with chosen finite products..  There is another sketch, S2, for 
categories with finite products and pullbacks and an
inclusion sketch homomorphisms: S1 -> S2. It induces a "forgetful" 
functor, the other way on categories of models; U: MOD(S2) -> MOD(S1).

	John's question can be interpreted as asking for information 
about the left adjoint functor going the other way:
	h* : MOD(S1) -> MOD(S2),
whose value on a small category C with finite products is the free
category h*(C) with finite products and pullbacks.  The general
theory of sketches guarantees that this left adjoint functor exists,
but it doesn't give very much information about it.  For instance,
consider the adjunction morphism (which in this case is a functor),
	eta : C -> U h*(C).
The setup tells us that eta preserves finite products exactly, but
it doesn't say much of anything else.  Eta is always faithful.  
Maybe Andy knows an argument saying that it is also full.

	h*(C) is given by a kind of syntactic "term" construction, so
it is not any nice recognizable category when C is a known
category.  If C were already imbedded in a "too large" category C' with
pullbacks, such as the presheaf category, then a good thing to look at 
would be the image of h*(C) in C'.  There is a rather extensive 
literature on this kind of question.  E.g., Lair et al, Kelly et al, 
Ulmer, etc.

	John Gray