Questions on dinatural transformations.
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
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
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
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
participants (4)
-
Claudio Hermida -
Noson Yanofsky -
Phil Scott -
Vaughan Pratt