Subject: categories: Re: Questions on dinatural transformations.

From: Vaughan Pratt <[email-masked]>
Date: Thu, 01 Jul 2004 10:01:28 -0700

>From: [email-masked]
>I was hoping that the category of small categories, functors and
>dinat transformations...

There's a category problem already at this point.  Dinats don't go between
functors F,G:C->D, they go between sesquifunctors F:C^op x C->D and differ
from n.t.'s of that type by only being defined on the diagonal of C^op x C.
The off-diagonal and non-identity-morphism entries in F,G only participate
in the dinaturality condition, not in the transformation itself.

>a) It is well known that there is no vertical
>composition of dinatural transformations.
>How about horizontal composition?

Before you can compose dinats horizontally you have to be able to compose
the sesquifunctors they bridge.  I don't know how others do this, but if I
had to compose G:D^op x D -> E with F:C^op x C -> D, my inclination would
be to restrict the evident composite G(F(a,b),F(c,d)) to a=d, b=c (i.e.
where the variances match up).  That is, GoF:C^op x C -> E is defined by
G(F(c,c'),F(c',c)) on object pairs (c',c) of C^op x C, with the expected
extension to morphism pairs (f',f) where f':c'->d' in C^op (i.e.
f':d'->c' in C) and f:c->d in C, namely

  G(F(f,f'),F(f',f)): G(F(c,c'),F(c',c)) -> G(F(d,d'),F(d',d)).

With that (or some) choice of sesquifunctor composition one can then ask
about horizontal composition tos where s:F->F', t:G->G'.  How would you
whisker a dinatural on the left, i.e. apply the whisker G:D^op x D->E
on the left to the dinat s:F->F' on the right where F,F':C^op x C->D?
For natural transformations, G is just a functor G:D->E, so this is just a
matter of applying G pointwise to each s_c.  For dinaturals however, G is
a sesquifunctor.  What do you want a sesquifunctor to do to a morphism s_c?
Maybe there's some span-like thing one can do here but I don't see it.

For dinaturals, vertical composition may turn out to be easier than
horizontal, in that it at least makes sense provided one solves the
shape-matching problem somehow.  In doing so one also solves another
problem, that dinaturality is too weak a condition, typically admitting
transformations on the internal hom that aren't Church numerals (Pare & Roman,
JPAA 128 33-92 for Set, Pratt, TCS 294:3, bottom of p461, for Chu(Set,K) and
chu(Set,K) which awkwardly seem to need different treatments).  Mike Barr
has a notion of strong dinatural (unpublished?), and the notion of binary
(more generally n-ary) logical transformation also works well here when
definable on the category of interest.

Vaughan Pratt

---

From: Claudio Hermida <[email-masked]>
Date: Fri, 02 Jul 2004 20:20:11 -0400

>  G(F(f,f'),F(f',f)): G(F(c,c'),F(c',c)) -> G(F(d,d'),F(d',d)).
There is a `canonical' choice of composition for such `sesquifunctors'
(what follows is presumably folklore and written up somewhere).

Consider the category SDCat of *self-dual* categories: objects are
categories C, equipped with a duality c: C -> C^op (with c^op c = id),
and morphisms F: (C,c) -> (D,d) are functors F:C -> D such that F^op c =
d F. The forgetful SDCat -> Cat admits both adjoints (and SDCat is
actually both monadic and comonadic over Cat): the right adjoint takes a
category A to (A^op x A, s) where s is the switch isomorphism (the
second projection \pi' : A^op x A -> A is the counit of the
adjunction).  We thus get a comonad G on Cat, and sesquifunctors are the
morphisms of the resulting Kleisli category Cat_G, which tells us how to
compose G:D^op x D -> E with F:C^op x C -> D. The composite is G(F^op s,
F)\delta, which agrees indeed with the formula above. (This is  of
course the composite in SDCat via the adjunction)

>definable on the category of interest.
The counterexamples mentioned in P. Scott's posting concern the lack of
a well-defined *vertical* composition of dinaturals. If one persists on
endowing them with such a composite, one possible approach is to accept
the partiality of this composition and work with *paracategories*.
Pushing this simple idea to its logical conclusion leads to a decent
enough basic theory, which allows to make sense of the fact that `dinats
into a ccc form a cartesian-closed paracat'. See

Hermida, C; Mateus, P.
Paracategories. II. Adjunctions, fibrations and examples from
probabilistic automata theory.
Theoret. Comput. Sci. 311 (2004), no. 1-3, 71--103.

(also available at my homepage  http://maggie.cs.queensu.ca/chermida)

Making a 2-dimensional structure with dinats, using their partial
vertical composition, leads to consider enrichment over ParCat (the
cartesian closed category of paracategories). But whiskering (and
therefore *horizontal* composition) is bound to be a partial operation
as well, so one has to broaden/weaken ParCat to accommodate this fact.
Ultimately, the kind of composite required in Yanosfky's posting:

S,S':C^op x C---->B  T,T':C^op x C ----> B^op U,U':B^op x B --->A
\alpha: S--->S' dinat \alpha': T--->T' dinat \beta: U--->U' dinat
-------------------------------------------------------------------
\beta \circ (\alpha',\alpha)

suggests a *partial multicategory* structure (as introduced in the
article above), with homs in ParCat.

Claudio Hermida