question on "model functor"

question on "model functor"

[Lutz Schroeder]

The following question looks so natural that somebody's
bound to have looked into it:

Does the functor

Cat^op ---> CAT

A  |-->   [A,Set]

reflect isomorphisms (more generally: limits)?

related questions (i.e. ones that would solve the problem or
at least help solving it) are

-- Are epimorphisms in Cat those functors F:A-->B for which
   F[A] generates B by composites and inverses of isomorphisms (in B)?
-- is the source of all covariant hom-functors an extremal mono-source
   in CAT?


The answers are probably in the literature - but where?

Thanks a lot,

Lutz Schroeder
-- 
-----------------------------------------------------------------------------
Lutz Schroeder                  Phone +49-421-218-4683
Dept. of Computer Science       Fax +49-421-218-3550
University of Bremen           
lschrode@informatik.uni-bremen.de           
P.O.Box 330440, D-28334 Bremen 
http://www.informatik.uni-bremen.de/~lschrode
-----------------------------------------------------------------------------

Re: question on "model functor"

[Dr. P.T. Johnstone]

> The following question looks so natural that somebody's
> bound to have looked into it:
>
> Does the functor
>
> Cat^op ---> CAT
>
> A  |-->   [A,Set]
>
> reflect isomorphisms (more generally: limits)?

The question is not very well posed: since Cat and CAT are 2-categories,
one ought to be asking about whether it reflects equivalences. For this,
the answer is negative (and well known): a functor A --> B induces an
equivalence [B,Set] --> [A,Set] iff it induces an equivalence between the
idempotent-completions of A and B. So the inclusion of any non-idempotent-
complete category in its idempotent-completion provides a counterexample.

However, if you insist on asking about isomorphisms rather than 
equivalences, the answer is yes. It's easy to see that if F: A --> B
fails to be surjective (resp. injective) on objects then the induced
functor [F,Set] fails to be injective (resp. surjective); so if [F,Set]
is an isomorphism then F must be bijective on objects, and this combined
with inducing an equivalence of idempotent-completions is enough to make it
an isomorphism.

But this is not a very meaningful result. Provided you assume a sufficiently
powerful form of the axiom of choice, [A,Set] and {B,Set] will be isomorphic
whenever they are equivalent (since each has a proper class of objects in
each isomorphism class, except for the initial object which is unique in
its isomorphism class). The isomorphism will not, of course, be induced by
a functor from A to B; but it will be naturally isomorphic to a functor that
is (at least provided B is idempotent-complete).

Peter Johnstone

Re: question on "model functor"

[Peter Freyd]

Lutz Schroeder asked:

    Does the functor

    Cat^op ---> CAT

    A  |-->   [A,Set]

    reflect isomorphisms (more generally: limits)?

Peter Johnston's answer to the first question is the right one, but 
one could expand. There's no doubt that his argument works well for
small categories (which, I take it, is what was intended by the 
notation), there's a little worry about it working for _locally_ small
categories, and there's no hope at all that it works for arbitrary 
categories, even if we restrict to those categories with small numbers
of objects. (As for the second -- parenthetical -- question: see the
bottom.)

For the fun of it, consider the one-object category whose maps are 
named by pairs  <X,f>  where  X  is a finite set and  f  is a 
permutation thereon. I'll say that  <X,f>  and  <Y,g>  name the same
map if the supports of  f  and  g  are both contained in the 
intersection of  X  and  Y, and further, when  f  and  g  are
restricted to that intersection, they become equal. Given the names of
any two maps, one can always choose names with the same first 
coordinates and that's enough to tell you how to compose them.

There's a functor from this big one-object category to the tiny one-
object category usually called the group, Z_2, to wit, the signature 
functor. This functor is carried by  [-,Set]  to an isomorphism in 
CAT.

Also for the fun of it, here's a proof for locally small categories
that doesn't require considering things like small projectives in 
super-big categories. It's routine to reduce to the case where  T  may
be assumed the be the inclusion functor of a lluf subcategory (one 
that contains all identity maps)  *A*  into a category  *B*. The  next
step is to show that  *A*  is a retract of  *B*.

For any object  A, let  H^A  denote the covariant set-valved functor
on  *A*  represented by  A. Assuming that  [T,Set]  is an isomorphism,
let  G^A  be the unique extension of  H^A  to  *B*. For any  f:A -> X
in  *A*  and  g:X -> Y  in  *B*  (G^A'g)'(f)  is a map in  *A*  from  
A  to  Y. Note that this is not defined as a composition of maps 
(indeed, G^A'g  is not defined as a map in any category other than the
category of sets) but as the application of a function  G^A'g  on an 
element  f  in  G^A'X, hence I will avoid using catenation for other
than composition by inserting prime-marks (for application). The
functoriality says that for  h:Y -> Z  we have  

1:          (G^A'h)'((G^A'g)'f) = (G^A'(hg))'f  

(and, of course, (G^A'1)'(f) = f).

Now let  j:B -> A  be a map in  *A*. The natural transformation  H^j
extends uniquely to a transformation  G^j.  But since the two  Gs
do the same thing to objects as the two  Hs  we know that G^j and  H^j
do the same thing to those objects. We have, therefore,

2:          ((G^A'g)'(f))(j) = (G^B'g)'(fj).

Construct  U:*B* --> *A*  by defining  U(g) = (G^X'g)'1  for
g:X -> Y.  For  h:Y -> Z  in  *A*  we have (using 1)  U(hg) =
(G^X'(hg))'1  =  (G^X'h)'((G^X'g)'1) = (G^X'h)'(Ug)  and  (using 2)
the later is equal to  (G'X'h)'(1Ug) = (G^Y'h)'1)(Ug) = (Uh)(Ug).

Consider the two endo-functors on  *B*, the identity functor and the
idempotent  *B* --> *A*  --> *B*.  The hypothesis that  [T,Set]  is an
isomorphism says that for any set-valued  F  on  *B*  it is the case
that  F  is equal to  *B* --> *A* --> *B* --> Set. But the set-valued
functors (indeed, just the representables) are collectively faithful,
and that forces  *B* --> *A* --> *B*  to be the identity functor,
which, in turn, forces each of  *B* --> *A*  and  *A*  --> *B*  to be
identity functors. The later functor is the given  T.


Finally, as for the question about reflecting limits: if I may quote
Cats and Alligators: "It seems to be a general principle that almost
any property of interest is reflected by [isomorphism-reflecting
embeddings] that preserve it" (1.33) In particular there's an easy
argument for the case of limits in a complete category because a cone
on a diagram fails to be a limit precisely when the induced map from
the limit fails to be an isomorphism.