Subject: categories: Naturality Squares and Pullbacks Date: Tue, 24 Mar 1998 11:15:42 +0900 From: Neil Ghani(1998-03) A natural transformation is an indexed family of arrows such that a certain diagram commutes. One could require a stronger condition, namely that the said diagram is a pullback. What would such a transformation be called? I'm sure I've seen this in the literature before but I cant remember where. Pointers? This problem arose in the context of finitary monads where T(X) is the derived operations over a set X for some signature. The naturality square for the unit turns out to be a pullback. This then implies that the unit of the monad is a monic - presumably this is a result in the literature somewhere. Again, pointers? Neil Ghani Date: Wed, 25 Mar 1998 18:23:46 +1100 (EST) From: maxk@maths.usyd.edu.au (Max Kelly) Subject: categories: Re: Naturality Squares and Pullbacks In response to the question of Neil Ghani, namely A natural transformation is an indexed family of arrows such that a certain diagram commutes. One could require a stronger condition, namely that the said diagram is a pullback. What would such a transformation be called? I'm sure I've seen this in the literature before but I cant remember where. Pointers? This problem arose in the context of finitary monads where T(X) is the derived operations over a set X for some signature. The naturality square for the unit turns out to be a pullback. This then implies that the unit of the monad is a monic - presumably this is a result in the literature somewhere. Again, pointers? Neil Ghani this phenomenon is now quite well recognised. some call such natural transformations "cartesian", while others use Robin Cockett's term "shapely". For my own contribution to the subject, see [G.M. Kelly, On clubs and data-type constructors, in applications of Categories to Computer Science (Proc. LMS Symposium, Durham 1991), Cambridge Univ. Press 1992, 163-190]. Max Kelly. Subject: categories: Re: Naturality Squares and Pullbacks Date: Wed, 25 Mar 1998 10:04:10 +0000 (GMT) From: "Dr. P.T. Johnstone" Natural transformations for which the naturality square is a pullback are commonly called cartesian: it's not an ideal name for them, but it's quite well established. For the question of when the unit and multiplication of a monad on Sets are cartesian, see section 3 of "Connected limits, familial representability and Artin glueing" by A. Carboni and P.T. Johnstone (Math. Struct. Comp. Sci. 5 (1995), 441--459). Peter Johnstone From: Michael Barr Subject: categories: Neil Ghani's question A week or two ago, Neil Ghani asked about natural transformations between set-valued functors (I think they were set-valued, but anyway that is what my answer refers to and is probably true for any reasonably complete codomain category although a different argument would be required), say a: F ---> G, such that for any arrow f: A ---> B of the domain category, the square aA FA --------> GA | | | | |Ff |Gf | | | | v aB v FB --------> GB is a pullback. At the time, I sent Neil a private reply, but it bounced for some reason. (I said that that I thought that this condition was reasonable only when restricted to monic f and then such an a is called an elementary embedding.) Then a couple of people answered that it was called a cartesian arrow and I didn't try to resend my answer. Well, there is a simpler answer. In that generality, such an a is called a natural equivalence. In other words, non-trivial examples do not exist. To see this, it is useful to translate it, using Yoneda, into the following form. As usual, I will say that of two classes E and M of arrows in a category, E _|_ M (E is orthogonal to M) if in any diagram e A ----> B | | | | | | v m v C ----> D with e in E and m in M, there is a unique arrow B ---> C (called a diagonal fill-in) making both triangles commute. Let us denote by h^A the covariant functor represented by A and for f: A ---> B, denote by h^f, the induced natural transformation h^B ---> h^A. Let E be the class of all h^f. Then a is cartesian iff E _|_ {a}. Now suppose a is cartesian. First I show that a is monic (that is injective). If not, there is an object A and two different arrows u, v: h^A ---> F such that aA(u) = aA(v). Let E be the equalizer of u and v and let h^B ---> E be any arrow. Then the square B A h -----> h | | | |aA(u)=aA(v) | | v a v F -----> G has two diagonal fill-ins, u and v. Here the arrow h^B ---> h^A is the composite h^B ---> E ---> h^A and the arrow h^B ---> F is the composite h^B ---> E ---> h^A ---> F, the latter via u or v. In a similar way, we can show that a is surjective. In fact, given u: h^A ---> G, let E be a pullback of a and u and let h^B ---> E be arbitrary. Then we have a commutative square B A h -----> h | | | |u | | v a v F ------> G whose diagonal fill-in gives a lifting of u. It therefore seems appropriate to restrict the question to certain classes of arrows A ---> B, for example monics. Here are a couple of examples. If g: C --->> D is a regular (or just strict) epimorphism between objects of the domain category, then for E the class of h^f for all monic f, we have E _|_ {h^g}. Similarly if E is the class of h^f for all strict monic f and g is any epimorphism, E _|_ {h^g}. Subject: Re: categories: Neil Ghani's question Date: Sat, 4 Apr 1998 15:57:18 +0100 (BST) From: "Dr. P.T. Johnstone" Mike Barr's answer to Neil Ghani's question is very pretty, but unfortunately wrong. There are many examples of cartesian natural transformations (e.g. between functors Set --> Set) which are neither epic nor monic: for example, the natural transformation (-) x A --> (-) x B induced by an arbitrary map A --> B. The mistake in Mike's proof occurs when he says > Let E be the equalizer of u and v > and let h^B ---> E be any arrow. The trouble is that E could be the zero functor, so that there may not be any arrows h^B --> E. Peter Johnstone Date: Sat, 4 Apr 1998 10:42:17 -0500 (EST) From: Peter Freyd Subject: categories: a fantastic simplification of our subject I can't make Mike's proof type-check, so let me try the following: For any set-valued functor, T, from any category, let a:O -> T be the unique transformation from the empty functor. Isn't it obviously cartesian? Has Mike shown all set-valued functors are empty? Good heavens. Date: Mon, 6 Apr 1998 12:06:21 +1000 (EST) From: maxk@maths.usyd.edu.au (Max Kelly) Subject: Re: categories: Neil Ghani's question I refer to Michael Barr's comments on Neil Ghani's question on cartesian natural transformations. These have been much studied, especially in computer science conrexts, and Michael admits he had seen the replies of Peter Johnstone and myself, in which we independently give precise references to our separate contributions to the study of monads whose multiplication and unit are cartesian natural transformations; such as the monad whose algebras are pointed sets, the multiplication for which is the cartesian natural transformation whose A-component is A+1+1 --> A+1. Accordingly I thought it odd that Michael, in the face of this, trusted his proof that they exist only trivially. Of course, as Peter Johnstone said, Michael's E is usually empty. Ironically, Michael is tha author of a famous and striking paper on the point of the empty set, which inter alia points out earlier errors of this kind on the part of others. Max Kelly. Date: Mon, 6 Apr 1998 13:15:54 +1000 (EST) From: Barry Jay >A natural transformation is an indexed family of arrows such that a >certain diagram commutes. One could require a stronger condition, >namely that the said diagram is a pullback. What would such a >transformation be called? I'm sure I've seen this in the literature >before but I cant remember where. Pointers? Cartesion natural transformations data:F=>L into the list functor have been used to represent the data-shape decomposition of many data types of the form FX. data_X FX --------> LX | | | F! = | | | L! = shape |-- | length | | F1 --------> L1 data_1 = arity Examples include tree types and array types. See, for example @Article{Jay95b, Author= cbj, Title={A semantics for shape}, Journal={Science of Computer Programming}, Volume=25, Year={1995}, Pages={251--283} } and other papers at http://linus.socs.uts.edu.au/~cbj. >This problem arose in the context of finitary monads where >T(X) is the derived operations over a set X for some signature. >The naturality square for the unit turns out to be a pullback. >This then implies that the unit of the monad is a monic - >presumably this is a result in the literature somewhere. >Again, pointers? > >Neil Ghani If T(X) = mu_Y. X + P(X,Y) for some polynomial P then the cartesian-ness of the unit for the monad follows from one of the main theorems of the paper above, which shows that taking initial algebras preserves cartesian-ness. Here it is applied to the (cartesian) inclusion X -> X + P(X,Y). Barry Jay | Associate Professor C. Barry Jay www: linus.socs.uts.edu.au/~cbj | Reader in Computing Sciences ftp: ftp.socs.uts.edu.au/Users/cbj Date: Mon, 6 Apr 1998 15:07:33 -0400 (EDT) From: Michael Barr Subject: categories: My posting Oops! I thank Peter J. for an extremely gentle explanation. And yes, Peter F., I did once take note of a certain lack of elements in the empty set, but, believe it or not that was not the real source of my error. But that was so unbelievably dumb that I will keep it secret. Michael