Questions on dinatural transformations.

Questions on dinatural transformations.

[Noson Yanofsky]

Hello,

Two quick questions:

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

i.e. Given
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
and
\beta: U--->U' dinat

is there a \beta \circ (\alpha',\alpha) and is it dinat?
It should be. But I can not seem to find the right definition.

How about if we restrict to a nice category of moduals for a nice algebra
over a nice field? Does that help?

I was hoping that the category of small categories, functors and
dinat transformations
should be a graph-category (a category enriched over graphs) but
am having a hard time
finding what the composition is. Did someone write on these
things?


b) Also, I was wondering if anyone ever wrote about
quasi-dinatural transformations. Those
are dinats where the target category is a 2-category and the
hexagon commutes up to a
two cell. They show up in something I am working on. But they are
very painful. Has anyone
worked on such things?


Any thoughts?

All the best,
Noson Yanofsky

Re: Questions on dinatural transformations.

[Phil Scott]

In general, the naive horizontal merging of dinaturals fails to be
dinatural.  This is discussed in the article "Functorial
Polymorphism" by Bainbridge, Freyd, Scedrov and me (Theoretical Computer
Science 1990, pp. 35-64).

Several counterexamples  are given there.

For example, in a cartesian closed category of domains or CPO's, consider
a dinatural family Y_A:  A^A --> A (e.g. in domains, let Y_A = the least
fixed point operator).  If you were able to compose this with the
"polymorphic identity" dinat id_A: 1---> A^A (i.e. a dinat from
constant functor 1 to (-) ==> (-)  where  id_A = the transpose of the
identity on A),  then the category would be degenerate (proved in BFSS,
Appendix A.4).

Of course, if the middle diamond (of an attempted merging of two dinat
families) is a pullback or pushout, then merging works. (see BFSS, Fact
1.2).

Re vertical merging, some things can be said quite generally: e.g BFSS,
Propn. 1.3.

For various generalizations, see Peter Freyd's paper "Structural
Polymorphism" (in TCS, 1993, pp.107-129).  Soloviev has also discussed
compositionality of dinats in several articles in JPAA.


                    Philip Scott



On Tue, 29 Jun 2004, Noson Yanofsky wrote:

> Hello,
>
> Two quick questions:
>
> a) It is well known that there is no vertical
> composition of dinatural transformations.
> How about horizontal composition?
>
> i.e. Given
> 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
> and
> \beta: U--->U' dinat
>
> is there a \beta \circ (\alpha',\alpha) and is it dinat?
> It should be. But I can not seem to find the right definition.
>
> How about if we restrict to a nice category of moduals for a nice algebra
> over a nice field? Does that help?
>
> I was hoping that the category of small categories, functors and
> dinat transformations
> should be a graph-category (a category enriched over graphs) but
> am having a hard time
> finding what the composition is. Did someone write on these
> things?
>
>
> b) Also, I was wondering if anyone ever wrote about
> quasi-dinatural transformations. Those
> are dinats where the target category is a 2-category and the
> hexagon commutes up to a
> two cell. They show up in something I am working on. But they are
> very painful. Has anyone
> worked on such things?
>
>
> Any thoughts?
>
> All the best,
> Noson Yanofsky
>
>
>
>

Re: Questions on dinatural transformations.

[Claudio Hermida]

Vaughan Pratt wrote:

>>From: noson@sci.brooklyn.cuny.edu
>>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)).
>
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)



>
>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
>
>
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

Re: Questions on dinatural transformations.

[Vaughan Pratt]

>From: noson@sci.brooklyn.cuny.edu
>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