# [FOM] Dual of a category

Florian Lengyel flengyel at gc.cuny.edu
Mon Jan 30 18:27:51 EST 2006

Moderator: did not see this on the list...I've attempted forcing plain
text The previous version had minor typos. -F

Hello,

What is the relation between the dual  Cat^op  of the
category of small categories  Cat, and the dual of a
small category?

In fact, I'd like to know if it is possible to define
the dual C^op of a small category C, using the dual of
the category of small categories.

Thanks,

Laurent

To address the second question, one possible construction of the dual
via Cat^op is simple enough: each small category C can be embedded in
Cat as a small category of categories by a faithful functor to Cat that
sends an object X of C to the comma category C/X of objects  over X,
and that sends a morphism f:X --> Y of C to the functor f_*:C/X --> C/Y
induced by composition with f. This is clearly faithful:
if f_*,g_*:C/X --> C/Y  are such that f_*=g_*, then evaluating each
at the object 1_X of C/X, f=g. The corresponding subcategory of
Cat^op is isomorphic to C^op; moreover, this is an object of Cat
since it is a small category.

Of course there are more conventional approaches to the opposite--I
don't know what motivated the question. Was it a certain notational
infelicity in Mac Lane's CWM (compare page 33 of CWM on the opposite
category with the treatment of adjoint functors on page 80)? For some
applications it is inconvenient to  identify the arrows of the opposite
category with those of the original (in CWM, Mac Lane only requires that
they are in one-one correspondence); consider, for example the Ph.D.
thesis "A Formal Calculus of Categories" of Mario Caccamo,  in which the
formalization of duality "...results in a nonstandard notion of
substitution of terms." The thesis is available online at
http://www.brics.dk/DS/03/7/.

Another construction. Let's suppose we insist that the arrows of the
opposite category are precisely the arrows of the original. Consider the
graph G with objects {0,1} and arrows \omega (natural numbers).
Let {\phi_n} be a standard enumeration of the partial recursive
functions of one variable, for n\in\omega. Define the source and target
of an arrow n\in\omega by setting n:0-->1 in G if \phi_n(n) converges,
and by setting n:1-->0 if \phi_n(n) diverges. Let C be the category
generated by G. The category C and its opposite C^op have precisely the
same arrows, but it is undecidable to determine, as a function of n,
whether the assertion n:0->1 (namely, that n is an arrow with domain 0
and codomain 1) holds in C or C^op.

FL