Re: Function composition of natural transformations?
Here is a technical/pedagogical question which has been bothering me for about twelve years.
In problem 5 on page 19 of "Categories for the Working Mathematician" (CWM), Saunders Mac Lane points out that a natural transformation may be fully extended to an intertwining function from one category to another, intertwining meaning (except in the void case), that the function transforms on one side according to its domain functor and on the other according to its codomain functor. Then on page 42 Mac Lane introduces what he calls "horizontal" composition diagramatically and without reference to the fully extended intertwining functions. But the function composite of such a pair of functions trivially intertwines the function composite of the domain functors with that of the codomain functors, and this function composition operation is very quickly verified to be "horizontal" composition when written in terms of restrictions to sets of objects. Thus Mac Lane and everyone else I have read leaves the impression that an honest verification of, say, the associativity of "horizontal" composition would require a somewhat involved diagrammatic demonstration which, in fact, would be nothing other than the hard way to prove the associativity of function composition. Presumably this has been noticed for a long, long time, but the 1998 edition of CWM did not mention it, and I can't help but be struck by the fact that other authors' terminologies leave the impression that they don't know or don't care that "horizontal", star or Godement composition is function composition.[...]
At least in the book "Elemente der Kategorientheorie" by D. Pumpl\"un the above characterization of natural maps is used explicitely; there is also a short discussion on obtaining simpler proofs this way. For the above reason \circ is used for the "horizontal composition"; \cdot or \ast (I do not remember which one) is used for the "vertical composition", which after all looks more "point-wise". Unfortunately some authors use these symbols just the other way round. Marc
Marc Olschok wrote:
For the above reason \circ is used for the "horizontal composition"; \cdot or \ast (I do not remember which one) is used for the "vertical composition", which after all looks more "point-wise".
Unfortunately some authors use these symbols just the other way round.
Marc
It is also possible to use a 2-dimensional syntax, in which horizontal composition is composed horizontally and vertical composition is composed vertically. Then algebraic manipulations are a bit like sliding tiles around in a tray. Steve Vickers.
Steve Vickers wrote:
It is also possible to use a 2-dimensional syntax, in which horizontal composition is composed horizontally and vertical composition is composed vertically. Then algebraic manipulations are a bit like sliding tiles around in a tray.
Of course this can be done using big diagrams. But is there a tight syntax for this just using text? Can you point to an example? (preferably a TeX source online, but a printed page in a regular journal would also work). -- Toby
For function composition, I just use the standard small circle \circ. So the function composite of natural transformations \tau and \sigma (if it exists) is \tau\circ\sigma. It is advisable to give up subscripting as a way of denoting values of (fully extended) natural transformations: The value of \tau at morphism a is just \tau(a). I would not use juxtaposition or any other generic means (e.g., a centered dot) of denoting composition in a general category for function composition or, for that matter, for any other composition which already has a specified composition symbol, but I do denote pointwise ("vertical") composition generically. Here is an example of how this goes---a line proof of the interchange law for function and pointwise composition: {\noindent\bf Proposition (Interchange Law):} When $\nu\mu\circ\tau\sigma$ is defined for natural transformations $\nu$, $\mu$, $\tau$ and $\sigma$, then so is $(\nu\circ\tau)\cdot(\mu\circ\sigma)$, and $$\nu\mu\circ\tau\sigma=(\nu\circ\tau)\cdot(\mu\circ\sigma).$$ \medskip {\noindent\bf Proof:} The void cases are trivial. Assume that $\nu\mu\circ\tau\sigma$ is defined. Then surely $\nu\circ\tau$ and $\mu\circ\sigma$ are defined, and $$\dom(\nu\circ\tau)=\dom\nu\circ\dom\tau=\cod\mu\circ\cod\sigma=\cod(\mu\circ \sigma),$$ so $\nu\circ\tau$ composes pointwise with $\mu\circ\sigma$. Calculate as follows at an $a$ in the common domain category of both sides of the interchange formula: $$\eqalign{[(\nu\cdot\mu)\circ(\tau\cdot\sigma)](a)=&\nu[\tau(\cod a)\cdot\sigma(a)]\cdot\mu(\dom[\tau(\cod a)\cdot\sigma(a)])\cr &\cr =&\nu(\tau(\cod a))\cdot(\dom\nu)[\sigma(a)]\cdot\mu[\dom\sigma(a)]\cr &\cr =&(\nu\circ\tau)(\cod a)\cdot(\cod\mu)[\sigma(a)]\cdot\mu[\dom\sigma(a)]\cr &\cr =&(\nu\circ\tau)(\cod a)\cdot\mu(\sigma(a))\cr &\cr =&(\nu\circ\tau)(\cod a)\cdot(\mu\circ\sigma)(a)\cr &\cr =&[(\nu\circ\tau)\cdot(\mu\circ\sigma)](a).\cr}$$ So the two sides of the interchange equation have the same intertwining function. Checking domain functors, $$\eqalign{\dom(\nu\mu\circ\tau\sigma)&=\dom\nu\mu\circ\dom\tau\sigma\cr &=\dom\mu\circ\dom\sigma\cr &=\dom(\mu\circ\sigma)\cr &=\dom(\nu\circ\tau)(\mu\circ\sigma);\cr}$$ similarly, $\cod(\nu\mu\circ\tau\sigma)=\cod(\nu\circ\tau)(\mu\circ\sigma)$. Thus the two natural transformations are equal. In this, \dom and \cod are defined by \def\dom {\hbox{\rm dom }} \def\cod {\hbox{\rm cod }} and respectively represent the domain and the codomain function on the implicit category. The proof uses the following formulas for pointwise composition in terms of fully extended natural transformations (i.e., in terms of their intertwining functions \pi and \tau): (\pi\cdot\tau)(a)=\pi(a)\cdot\tau(\dom a)=\pi(\cod a)\cdot\tau(a) which I can't help mentioning as an aside shows that evaluation of fully extended natural transformations at a morphism intertwines evaluation at its domain object with evaluation at its codomain object. (And, incidentally, codomains are on the left in my notations, domains on the right.) If I haven't explained something necessary here, I hope that you can nevertheless see that the above line proof represents a moderately massive amount of diagram drawing and chasing and would fit convincingly on the page of a textbook. I hope that this addresses your request. The only examples which I know are all in my personal set of notes which I set up PCTex32 over the last dozen years and which come out at about 200 pages. This is probably a little too much to drop on you all at once. I am, however, anxious to answer any further questions which you may have.
This may be `mere' pedagogy for ordinary categories, but if you try the same thing for 2-categories then it becomes a `genuine' issue. To put it another way, the two different but equivalent presentations of a concept (natural transformation) become, on categorification, significantly different. First the 1-dimensional situation. As I understand it, Pat Donaly's original point was that given functors F, G: C ---> D between categories, you can either define a natural transformation in the standard way (assigning an arrow of D to each object of C) or in an alternative way (assigning an arrow of D to each arrow of C). With the standard method, vertical composition of transformations is "easy" to define, and horizontal composition is "hard". With the alternative method, horizontal composition is now easy to define (as Pat noted), but vertical composition is "hard". So the situation is reversed. Of course, neither of these "hard"s is really hard, but in both cases you have two evident ways of defining a composite - one left-handed, one right-handed - and if you're going to do anything whatsoever with the definition then you need to show that these two ways give exactly the same result. Now suppose that C and D are 2-categories and F and G are 2-functors. It doesn't matter whether C, D, F and G are strict or weak for the purposes of this discussion. Suppose we're interested in defining weak (=pseudo) transformations F ---> G. The usual way is to say that such a transformation consists of a 1-cell alpha_c : Fc ---> Gc for each c in C, together with an invertible 2-cell inside each naturality square, satisfying axioms. With this definition, vertical composition of transformations is easy to define (and there's only one evident way of doing it), but horizontal composition can be defined in two different ways, which are not equal but canonically isomorphic. An alternative approach is to say that a transformation consists of a 1-cell alpha_f: Fc ---> Gc' for each 1-cell f: c ---> c' in C, together with certain further 2-cells, satisfying axioms. You can guess the rest of this paragraph: with this definition, horizontal composition is now easily (and canonically) defined, but vertical composition can be defined in two different ways, which are not equal but canonically isomorphic. You might think that this isn't a genuine difference or "problem" so far, because everything is the same up to isomorphism. But now suppose that you're interested in *lax* transformations F ---> G (where F and G are still 2-functors, as above). The usual definition is that such a lax transformation alpha consists of a 1-cell alpha_c as above for each object c of C, and then a not-necessarily-invertible 2-cell inside each naturality square (pointing in a direction fixed by convention), satisfying axioms. These lax transformations can still be composed vertically perfectly easily, but horizontal composition is now *impossible* to define. (More accurately, you can define two different horizontal compositions, but they're not isomorphic, only connected by a non-invertible cell; you could of course choose one over the other, but it won't have good properties.) And if you define "lax transformation" according to the alternative method, then horizontal composition is now easy and vertical composition impossible. In summary, if you define transformation of 1- or 2-category in the standard style then vertical composition is always easy, and regarding horizontal composition: - for transformations of categories, it's canonically defined - for weak transformations of 2-categories, it's not canonically defined (you have to choose "left" or "right"), but is canonically defined up to isomorphism - for lax transformations of 2-categories, it's not defined at all. If you use the alternative style then the situation is similar but with "vertical" and "horizontal" reversed. Puzzling. Tom
It may be useful to recall the Ehresmann method of setting up the exponential law for categories using the double categoy of commuting squares in a category. This is also written up in (R.Brown, P. NICKOLAS), ``Exponential laws for topological categories, groupoids and groups and mapping spaces of colimits'', {\em Cah. Top. G\'eom. Diff.} 20 (1979) 179-198. The nice point is that the category structure is induced by a double category composition, and so if you have extra structure, such as a topology, that carries over. Ronnie Brown On Tue, 3 Jun 2003, Toby Bartels wrote:
Steve Vickers wrote:
It is also possible to use a 2-dimensional syntax, in which horizontal composition is composed horizontally and vertical composition is composed vertically. Then algebraic manipulations are a bit like sliding tiles around in a tray.
Of course this can be done using big diagrams. But is there a tight syntax for this just using text? Can you point to an example? (preferably a TeX source online, but a printed page in a regular journal would also work).
-- Toby
Prof R. Brown, School of Informatics, Mathematics Division, University of Wales, Bangor Dean St., Bangor, Gwynedd LL57 1UT, United Kingdom Tel. direct:+44 1248 382474|office: 382681 fax: +44 1248 361429 World Wide Web: home page: http://www.bangor.ac.uk/~mas010/ (Links to survey articles: Higher dimensional group theory Groupoids and crossed objects in algebraic topology) Centre for the Popularisation of Mathematics Raising Public Awareness of Mathematics CDRom Symbolic Sculpture and Mathematics: http://www.cpm.informatics.bangor.ac.uk/centre/index.html
Toby Bartels wrote:
Steve Vickers wrote:
It is also possible to use a 2-dimensional syntax, in which horizontal composition is composed horizontally and vertical composition is composed vertically. Then algebraic manipulations are a bit like sliding tiles around in a tray.
Of course this can be done using big diagrams. But is there a tight syntax for this just using text? Can you point to an example? (preferably a TeX source online, but a printed page in a regular journal would also work).
-- Toby
Dear All, In reply to Toby Bartels, there are various models of higher categories in which the syntax is well attested and the `sliding of tiles' is algebraically described. One possible one that extends to arbitrary dimensions is given in the paper: AL-AGL, A.A., BROWN, R. & STEINER, R., Multiple categories: the equivalence of a globular and a cubical approach, Advances in Math. 170 (2002) 71-118. The links between `cubical' syntax and a more globular syntax are at the heart of the extensive work on the equivalence between the various models for weak n-categories. One problem is that there are no normal forms for elements. In fact I think (possibly!) that the problem of rewriting in these higher dimensional settings needs a higher dimensional rewriting systems, and to model that one needs n-cateories (and so on!) Tim Porter
Tom---I understand your general point to be that 2-categories are different, and from this I tentatively suspect that you would not favor my habit of calling "horizontal" composition function composition if that proposition were before the board. I have to give the particulars of this some thought, but while I am thinking, I'm going to wish that you had been aware of my perspective on 2-categories when you made your comment. What follows is a failed attempt to convey this perspective in a reasonably brief email in hopes that you will kindly make some additional comments with this background in view. Reading this will require some patience, because my lack of erudition is going to show up here, but let me state that the objective is to define a general natural transformation to be a functor into a cell category which is actually the first participating category in a certain type of split interchange category, then to define its arithmetic in these terms. This is an extremely general but surely not unprecedented definition of naturality which provides a correspondingly general definition of "vertical" or (as I prefer) pointwise composition without any conflicts which I can see, although it is true that function composition does not seem to exist in this generality. Your sharpest criticisms are very welcome. To begin, everyone knows that a double category is an ordered pair of participating categories which have the same underlying set (of morphisms), and a double functor is a function between underlying sets which is functorial between first participants and also between second participants. Say that a double category splits if the domain and codomain function of each of these participants is endofunctorial on the other participant. First fact: In this case, the set of objects of each participant forms a subcategory of the other participant---call it the object subcategory of the other participant and be careful to distinguish it from the subcategory of objects which any category has. My excuse for using "split" in this context is that a category participates with itself in a split double category exactly when it is a disjoint union of monoids. Everyone also knows the interchange law for double categories: The compositions of the participants commute with each other in the weak sense that $ab\# cd=(a\#c)(b\#d)$ if both sides are defined (visible composition symbols are used as delimiters in the obvious fashion). Say that a double category is a split interchange category if it splits and satisfies this interchange law. To be brief, call it a splintor. A category participates in a splintor with itself exactly when it is synonymously its own reverse, opposite or dual category, which amounts to being the disjoint union of a set of commutative monoids. Call it a core splintor, because every splintor contains a strongly maximal core subsplintor whose underlying set consists of those elements at which all four object (i.e., domain and codomain) functions agree, so that the double objects are obviously in the core. Strongly maximal means that any core splintor which is a subsplintor of the given splintor is contained in its core. (Incidentally, aside from core splintors, I know of only one general type of splintor which has a nondiscrete core---namely splintors of classical natural transformations under pointwise and function composition. In fact, in this example, the core consists of those natural transformations which intertwine identity functors. If an identity functor is the identity functor of a monoid, the natural transformations which intertwine it with itself is isomorphic to the classical monoidal center by evaluation at the monoid's object, and from this I have picked up the habit of saying that a core component monoid is the center of its object.) There are a couple of other ways to come across splintors. The easiest is to just strip off the composition of a category---this gives the discrete, say, first participant of a splintor for which the second participant is just the given category itself, so that every category participates in a splintor of some kind. Call such a splintor a stripping splintor or strippor for short. As in the case of core categories, every subsplintor of a strippor is a strippor, and every splintor contains a strippor which is strongly maximal as a contained strippor: This strippor is just the discrete subcategory of objects of the first participant and the object subcategory of the second participant. I call the originally given splintor an objectification of this latter object subcategory, since it amounts to a way of converting the morphisms of the object subcategory into the objects of the first participant. Objectifications are good, because they give a systematic way of converting the objectified category into a category of functors under function composition, thus generalizing the Cayley Representation Theorem for groups in a fairly grandiose manner. This would not lead anyone to think that there would be any point to objectifying a category which is already discrete, but such objectifications are precisely the splintors whose second participant's objects are the splintor double objects. Because of the endofunctoriality of the second participant's object functions, the homsets of the second participant are subcategories of the first participant, and bicomposition---simultaneously composing on the left by one morphism and on the right by another---defines a homset structuring bifunctor. For this reason, I call objectifications of discrete categories structuring categories or just structors. This will disgust you, because structors are what everyone else calls 2-categories. At any rate, every subsplintor of a structor is a structor, and every splintor contains a structor which is strongly maximal in the splintor vis-a-vis being a structor. Core categories and strippors are structors. For that matter, so is a strict monoidal category, which is just a splintor whose second participant (say) is a monoid. Here is the crucial property as far as "vertical" or pointwise composition of natural transformations is concerned. One knows that the functions from a set into the underlying set of a category have a categorical pointwise composition: (fg)(xy)=f(x)g(y) when the right side is always defined. So fix a category and a splintor and consider the functors from the category into the splintor's first participant. The underlying functions of these functors are stable under pointwise composition in the second participant, and thus the functors themselves may be said to form a category under pointwise composition in that second participant. This is why the homomorphisms from a group into a commutative group form a group under pointwise composition---because the commutative group participates in a core splintor with itself. I would almost be willing to say that a hypergeneral natural transformation is a functor into a splintor first participant just because you get one of the primary operations of the arithmetic in this way, but I realistically know that this much generality isn't going to go far in terms of my talents; so there is a need for more specialized splintors which more visibly include the classical natural transformation concept. This strong market for splintors of various sorts necessitates a more categorical phrasing of the standard banalities on transitive relations. Given a set X, define transition composition on its self-cartesian product by (a,b)(b,c)=(a,c). Any subcategory of this is a transition category on X; the whole thing is the full transition category X* on X. A transition category is a transitive relation if it is reflexive in this full transition category; i.e., it has the same objects. The term "preorder" is dropped. A transitive relation is an equivalence relation if it is its own subcategory of isomorphisms; it is a partial ordering if this subcategory is discrete. A function h:X->Y defines a functor h* between full transition categories by slotwise evaluation: h*(a, b)=(h(a),h(b)). Every functor between transitive relations is obtained by restricting and narrowing some such h*. Every equivalence relation is the kernel of some h*, meaning that it is the inverse image of the discrete subcategory of objects of the codomain category of h*. This said, the full transition category of the underlying set of a category participates with the self-product of the category in a splintor. A subsplintor for which the first participant is a transitive relation on this underlying set is a stable transitive relation on the given category. So a partially ordered group is a splintor. Also interesting is the product category whose first component is the said full transition category and whose second component is the said self-product, since it contains various subcategories of "commutative squares", where I use quotes because I may be referring to commuting to within an isomorphism or to within an inequality or, generally, to within a morphism of some specified category which I'll call the value category. I'm now pretty close to the ideas of a cell category and a cell splintor. These are splintor concepts. Begin with an objectification (B,C) of the category A (with composition \# on C and hence on A) whose quasi-commutative squares are to be constructed. Form the product category A*\times(A\times A), where A* is the full transition category of the underlying set of A. Take the value category B to be the first participant of the given objectification, and form the set [A*\times(A\times A)]\times B, showing no interest in its cartesian product composition, because there is a subset S of it which has a more interesting cell composition. To bring this out, write the quintuples in [A*\times(A\times A)]\times B in attachment form, so that a member looks like (q,u,b,v,p) with b in B, (u,v) in A\times A and the transition (q,p) in A*. In this, ( q,u,v,p) is the square (of A-morphisms) which is to be regarded as commuting to within the morphism b. So S consists of those quintuples for which q\# u and v\# p are defined in A, while b is in the homset of B-morphisms from v\# p to q\# u, and domains and codomains are organized as follows: The domain of b in C is the domain of p in C which is also the domain of u in C, while the codomain of b in C is the codomain in C of q and also the codomain in C of v. These quintuples are the cells of (B,C). The cell composite of a cell (r,s,c,t,q) with cell (q,u,b,v,p) is the cell (r,s\#u,(c\#u)(t\#b),t\#v,p). The outside components are just the composite of (r,s,t,q) with (q,u,v,p) in [A*\times(A\times A)] when the members of this category are written as attached pairs. The middle term, which involves one composition in B, is defined whenever the composite (r,s,t,q)(q,u,v,p) is defined in [A*\times(A\times A)]. So this defines cell composition relative to an objectification. It is categorical, and the projection (q,u,b,v,p)->(q,u,v,p) is injective when restricted to the set of objects of S, thus has a subcategory of [A*\times(A\times A)] as image, and this subcategory is reasonably called the category of squares which commute to within a B-morphism. Now I can say that a natural transformation (to within B) is a functor from some category into the cell category S. To get the idea closer to the classical form, you notice that following such a functor by the detaching functors (q,u,b,v,p)->u and (q,u,b,v,p)->v gives candidates for the domain and codomain functors (my domains are on the right, and codomains are on the left) of the natural transformation, and, to get a fully extended intertwining function, follow by (q,u,b,v,p)->b. This last map is functorial into B exactly when the given splintor (B,C) is a structor (i.e., a 2-category), which is so if and only if it is surjective. Both B and C have functorial representations in S in this case, which is my personal, idiosyncratic explanation of why the elements of 2-categories are called cells. To get pointwise composition out of this, you construct a second participating cell category by first of all reversing B to get a splintor (B',C) which still objectifies A. Then you construct the cell category of this semireversed splintor and apply the double switch (q,u,b,v,p)->(v,p,b,q,u) to pull the semireverse cell composition back onto the underlying set of the first cell category S. This gives the second participant T of the the cell splintor (S,T) of (B,C). Pointwise composition of natural transformations means pointwise composition of functors into S in T. By the way, (S,T) is a structor exactly when the objectified category A is discrete, which reflects the fact that forming a cell splintor does not change (except by a functorial isomorphism) a splintor's maximal structor, nor does the core change. This is my argument that structors are not enough to fully describe the cell concept. To get the classical idea of a natural transformation, begin with a discrete value category B; that is, begin with the strippor of C, then regard the natural transformation as running from A to C. This is justified by the fact that, in this case, the cell category S is isomorphic to its commutation category by the projection (q,u,b,v,p)->(q,u,v,p); so the intertwining function (q,u,b,v,p)->b can just as well be written as (q,u,v,p)->qu=vp, and so on. When this follows the functor version of a classical natural transformation, it gives the fully extended intertwining function which I mentioned in my first email. You can see that, as far as this point of view goes, there is no particularly obvious conflict between function composition of natural transformations and pointwise composition. Function composition doesn't obviously exist when values are not discrete. There is presumably still plenty to be said in terms of function composition of splintor functors, but I haven't thought about this at all, and I'm not likely to start until I have understood your note. Thanks for your comments and your patience if you have any left. Pat Donaly
There is another way of looking at the strict multiple globular category case, which is to use the monoidal closed structure, as ws established via the cubical case in 116. (A. AL-AGL, R. BROWN and R. STEINER), ``Multiple categories: the equivalence between a globular and cubical approach'', Advances in Mathematics 170 (2002) 71-118. This monoidal closed structure is fairly clear cubically, but is difficult to translate into globular formulae in higher dimensions. If A=END(C), where C is a multiple category (globular or cubical), so that A is one also, then the `enriched composition' is a morphism A \otimes A \to A. In low dimensions this gives left and right whiskering A_0 \times A_1 \to A_1, A_1 \times A_0 \to A_1, and there is also a function say { , }: A_1 \to A_1 \to A_2, which measures the lack of agreement of two possible definitions of compositions, and I think this is what Tom refers to in his email. In the cubical formulation, A_2 consists of `squares', and the sides of the squares are easy to interpret using whiskering. One way round the square is a.g \circ f.v and the other is f.u\circ b.g if f:a \to b, g:u \to v. In the groupoid case, ideas of this type are used in 59. (R. BROWN and N.D. GILBERT), ``Algebraic models of 3-types and automorphism structures for crossed modules'', {\em Proc. London Math. Soc.} (3) 59 (1989) 51-73. and in other papers of Nick Gilbert. The extra structure on a crossed module M (or 2-groupoid, for that matter) of a monoid morphism M \otimes M \to M allows the modelling of homotopy 3-types. However, for calculations of 3-types, crossed squares seem better, because of a Van Kampen Type theorem, not apparently available for the other structures. Ronnie Brown Tom LEINSTER wrote:
This may be `mere' pedagogy for ordinary categories, but if you try the same thing for 2-categories then it becomes a `genuine' issue. To put it another way, the two different but equivalent presentations of a concept (natural transformation) become, on categorification, significantly different.
snip... -- Professor Emeritus R. Brown, School of Informatics, Mathematics Division, University of Wales, Bangor Dean St., Bangor, Gwynedd LL57 1UT, United Kingdom Tel. direct:+44 1248 382474|office: 382681 fax: +44 1248 361429 World Wide Web: home page: http://www.bangor.ac.uk/~mas010/ (Links to survey articles: Higher dimensional group theory Groupoids and crossed objects in algebraic topology) Centre for the Popularisation of Mathematics: http://www.cpm.informatics.bangor.ac.uk/ (reorganised site with new sculpture animations)
participants (7)
-
Jpdonaly@aol.com -
Marc Olschok -
Ronnie Brown -
Steve Vickers -
Tim Porter -
Toby Bartels -
Tom LEINSTER