Date: Tue, 6 Aug 1996 08:57:57 -0300 (ADT) Subject: a proposal Date: Sun, 4 Aug 1996 21:24:35 -0400 From: Michael Barr Dear Colleagues: There is something that I have been thinking about for a long time that I would like to share with you. This concerns what has happened to publication in the last 50 years, although it possibly continues a trend that has been going on for a long time. I have a habit, when looking up a reference in a journal, of looking at other papers in the same journal to see what people were thinking about at the time. It is astonishing. When I look at the average paper in JPAA, I can make no sense of it in most cases. It is generally ultra-technical and has likely been shortened to the point that only an expert in the subject can read it and not always then. Go back and read a paper from the 40s. From the Annals, or from TAMS. It is amazing, but you will actually be able to read most of them. Many of the authors actually explain clearly what they are dong and why. They go into enough detail that the reader has a chance. It was a different era, of course, but it is amazing to see how technical mathematics has become in just 50 years. There are a number of reasons for this. The pressure to publish is what is ultimately responsible and that has certainly not been entirely bad. Without the possibility of electronic publication, this would even get worse. Electronic journals, like TAC, will help for size per se will no longer be an obstacle. But in the beginning, at least, TAC will not publish expository papers and will be reluctant to publish new proofs too. And given the various pressures by university administrations, untenured people will be loath to spend the time on getting the exposition clear. When I get a paper for TAC, I basically ask myself if the paper would have been publishable in JPAA. I have been an editor of JPAA since it was founded, what, 25 years ago? I hope to remain and editor until it ceases to publish, which I expect in about five years. But in the meantime, I have a fairly good idea of what it publishes and I would like to transfer this quality to TAC. Now imagine you get a paper, say, that takes a known theorem of ring theory and shows that the result depends only on some straightforward categorical property and states and proves that property using an argument that is a direct translation of the ring-theoretic argument. Here is an example: I, and no doubt many others, once observed that the theorem that a von Neumann regular ring has canonical quasi-inverses, unique subject to certain equations has an immediate categorical generalization that applies the category of finite dimensional vector spaces, but it never occurred to me to try to publish it. I assume no one else has either. I think it safe to say that such a paper is not the sort of thing that JPAA would publish. It is a shame really because that is useful insight. Perhaps equally useful is that the same fact is false for strongly von Neumann regular rings. (Actually, the property in question cannot even be stated in a category). Anyway, the point I wanted to make is that we would not want to publish it in TAC, because we must maintain credibility if we are to be in a position to take over gracefully as JPAA loses its subscribers. What we must avoid at all costs is to get a reputation as a place to send your "works of the left hand". Just a few days ago, I was reading a philosopher who imagined that a lot of mathematical publication was concerned with publishing refined proofs on known results. I don't know where he got that idea, but of course it is almost entirely wrong. There is almost no outlet for such material, especially if it is an area of 20th century mathematics, which nearly eliminates the Monthly. There is L'Enseignement Mathematiques and I once made essential use of something published there. But the very name of the journal is a guarantee that deans (and department promotion committees) are not likely to take it seriously. I happen to have sitting on my desk an M.Sc. thesis in math written about 10 years ago by a man who is now a computer scientist. He gives a surprisingly simple proof of the fact that every manifold of class at least C^2 has a simple cover. As it happened, I used this fact in a recent paper. I had to give reference to a classical proof that uses the existence of a Riemannian metric. (You then use small neighbourhoods for your cover.) I would really have liked to have an argument that I understood. But this paper is probably unpublishable, at least in respectable journals, since no matter how nice it is (and several analyst colleagues of mine agree it is very pretty and quite surprising too), the main result is not new. What I think we need is a journal devoted to what I will call explanatory papers. This is not intended to be the same as expository, although expository papers might fit. But new proofs, better proofs, more enlightening proofs, that sort of thing. Generalizations, provided they cast new light, would be welcome, but it would not be intended primarily for new results. I even have a (very) tentative name: Mathematical Insights. If this is too pretentious, it is not cast in concrete. Of course, it would be electronic, under the same regime as TAC. It would not, however, be primarily for category theory but could cover all of mathematics. I post this on the categories bulletin board because that is the one I am on, but I would prefer it to go far and wide. (Since I wrote that someone mentioned to me that that NewAge Celestine Prophecy uses "insight". I cannot let that stop me from using it properly.) Any interest? Michael Date: Tue, 6 Aug 1996 18:55:12 -0300 (ADT) Subject: Re: a proposal Date: Tue, 6 Aug 1996 08:39:32 -0400 From: Peter Freyd I like Mike's proposal. And I would shorten the title to "Insights". When David Buchsbaum became editor of TAMS he announced that he would publish new proofs for old theorems; he would not publish new theorems for old proofs. I gather, though, that Mike is suggesting that occasionaly the later can be a genuine insight. And who, Mike, was the "philosopher"? Date: Tue, 6 Aug 1996 18:57:59 -0300 (ADT) Subject: Re: a proposal Date: Tue, 6 Aug 1996 10:57:29 -0300 (ADT) From: Wendy MacCaull Michael: I think you have an excellent idea. I believe it is important that mathematicians take some time to explain their ideas in such a way that the mathematical community can understand. I suspect that this would enrich us all and provide opportunities for cross-fertilization (I guess interdisciplinary work is the more appropriate word now). Wendy MacCaull Date: Tue, 6 Aug 1996 18:59:25 -0300 (ADT) Subject: Re: a proposal Date: Tue, 6 Aug 1996 08:35:49 -0700 From: Michael J. Healy 206-865-3123 Dear Michael, Your proposed new journal sounds interesting. Having a source that gave, in relatively brief form, the collected results from and overviews of areas of investigation would be wonderful. Often, one needs to read several books and specialized papers to get this---and that only when the material exists. For example, I would like to see some compact papers that discuss categorical logics, such as geometric logic, giving a set of axioms and rules of inference along with a grounding in the model theory and any other machinery useful to a beginner (in my case, to accelerate the learning process so I can apply it). Presently, I find I have to communicate with the people researching the area. While I enjoy doing this, I am feaful of becoming a pest. I have a question in connection with electronic journals that no one has been able to answer so far. What about archival publication? What is the guarantee that an electronic publication will be (1) citable, (2) available 50 years from now? (OK, so there are many questions!) I am citing a paper that appeared in 1943. Thanks, Mike Date: Tue, 6 Aug 1996 19:00:57 -0300 (ADT) Subject: Re: a proposal Date: Tue, 6 Aug 1996 08:58:08 -0700 From: Peter White Dear Mr. Barr Thank you for your thoghtful letter on mathematical publishing. I am not a "mathematician" in the sense that my job is to do research and find new results. I am a "mathematician" in the sense that my job is to bring more mathematics into application, and particular, into application to software. I am particularly interested in category theory for this purpose. I think this makes me a "consumer" of the papers published in mathematics journals. Since I am using category theory, the mathematics I use is not too old. The results of category theory have not been through several generations of mathematicians to refine the concepts in the same way that analysis has. This means that I do have occasion to look at recent articles published in the journals. I would say that articles that show new and better deriviations of known results would be of *primary* interest to me. I think that mathematics is just as much about coming up with proofs as it is about coming up with results. Indeed, no one believes your result until you have a proof. In fact I think a result does not really become part of the mainstream until it has been through a generation or two of refinement and the original proof (probably long) has become a short and elegant proof. Mathematics is as much about elegance as it is about results, and I feel that those who find new proofs are doing original work just as much as those who find new results. As one who applies mathematics, I need to understand the results. For the most part, this means understanding how they were derived - "where they come from". It is possible to apply a body of mathematics when you have a good understanding of most of the material but you skipped the proofs of one or two results that are too lengthy or difficult. It is also possible to understand the main principles of a theory (say integration and differentiation) and then use a large body of technical results without proof (a table of integrals or a table of solutions to differential equations). I think it is _not_ possible to use a body of mathematics by just reading the results and hoping that you understand them well enough that you will not misapply them. To apply the mathematics requires not so much a familiarity with the latest results, as it does a thoorough and deep understanding of the main results of the theory. For example, in category theory, for applications I believe one wants a thorough understanding of limits and colimits, functors and natural transformation, adjoints, toposes, sheaves, probably grothendieck topologies, and I am sure I must have left a few out. In order to understand these concepts it seems to be necessary to know about a couple of domains of application within mathematics, especially abstract algebra and vector spaces. To thoroughly understand this material would mean to have seen the proofs, step by step. Seeing two or three different proofs of the main results would be helpful. In addition, examples and applications of all the main results should be given. The examples and applications should be limited to a narrow sphere, such as basic abstract algebra. It is not useful to be given one example from algebraic geometry, another from topology on 4 manifolds, and a third from harmonic analysis on semi simple lie groups. I know very little about all three of these topics, but I find myself fully capable of understanding category theory. So I say, by all means let us have journals, monthlies, bulletin boards, whatever it takes to get publishing going that addresses new and better proofs, new insights about the connections between two theories AND new applications of the old theories. I think this would - Give students a place to publish results that are useful, but not earthshaking. - Give application people such as me the same thing. - Spread understanding of esoteric topics such as category theory. All of these would eventually lead to more results. Regards Peter White Date: Tue, 6 Aug 1996 19:01:41 -0300 (ADT) Subject: Re: a proposal Date: Tue, 6 Aug 1996 18:08:37 +0100 (BST) From: courtes The ACM publishes Computing Surveys, which contains explanatory papers on a diverse range of computing topics from image processing to unification. Date: Tue, 6 Aug 1996 19:02:25 -0300 (ADT) Subject: extensive stuff Date: Tue, 6 Aug 1996 14:24:15 -0400 From: Peter Freyd The phrase DISTRIBUTIVE CATEGORY is established as referring to a category with finite products and coproducts wherein coproducts distribute with products. The phrase EXTENSIVE CATEGORY refers to a cartesian category (that is, one with finite limits) with finite coproducts wherein coproducts are preserved by pullbacks. (Bill, they tell me you gave it this name because measurements tend to be valued in such. Right?) An equivalent definition of an extensive category is a cartesian category that's _locally_ distributive, that is, every slice category is distributive. I've recently finally been able to find the right expansion of what I've called "cartesian logic" (the syntax of cartesian categories) to what I guess I will have to call "extensive logic" (the syntax of extensive categories). Cartesian logic can be sloganized as the logic of _unique_ existentials. For extensive logic add _exclusive_ disjunctions. (Yes, all you purists, "sloganized" is in the OED. Actually, the American Heritage Electronic Dictionary would seem to define it as the result of turning something into a Scottish war cry.) With cartesian logic we first obtain a completeness theorem with respect to the semantics of cartesian categories (by constructing the free cartesian category from a given theory and noting what rules of inference are needed to make the construction work) and then we obtain a completeness theorem with respect to the "elemental semantics" by using the fact that set-valued representations for any small cartesian category are collectively faithful. By the time we're done we need that the representations reflect not just equality and isomorphisms but non-split-epis into non-epis. (The Cayley representations, of course, do all this.) Similarly for extensive logic. Here we need the fact that the set-valued representations of any small extensive category are collectively faithful, indeed, collectively reflect (not just equality and isomorphisms but) split epis. By "representation" I mean a functor that preserves finite limits and finite coproducts. It would not be enough to preserve just finite products and coproducts for the semantics. That is, I must work in the context of extensive categories not distributive categories. (Cayley, of course, no longer suffices.) Do distributive categories arise in nature that aren't extensive? The quickest artificial example is the full subcategory, *A*, of (*S*)x(*S*), where *S* is the category of sets. A pair is in *A* if either both X and Y are non-empty or both are empty. *A* is coreflective, hence cartesian. It's closed under the formation of products and coproducts, hence distributive (indeed, it's closed under the formation of exponentials, hence an exponential category). *A* is not an extensive category. <{a,b},{a,b}> is the coproduct of <{a},{a}> and <{b},{b}>. The intersection of each of these subobjects with <{a},{b}> is <{},{}> hence pulling back along the inclusion map of <{a},{b}> does not preserve coproducts. But I seem to have stumbled across a more natural example. In Cats and Alligators a pair of idempotents e, e' are said to be "neighbors" if ee'e = e and e'ee' = e'. So, let's understand a SEMIGROUP OF NEIGHBORING IDEMPOTENTS to mean a semigroup satisfying the further equations: xx = x, xyx = x. Note that as a consequence: xyz = (xzx)yz = x(z(xy)z) = xz. The category of semigroups of neighboring idempotents is a distributive category because, even better, it's an exponential category. Construct A => B in the naive way, that is, as the set of homomorphisms from A to B. The semigroup structure on A => B is given pointwise: for homomorphisms f,g:A -> B, define fg = \a.(fa)(ga). The equation xyz = xz forces fg to be a homomorphism. A homomorphism h:X*A -> B curries to a homomorphism h':X ->(A => B) where the naive definition works for h', to wit, h' = \x.(\a.f). The equation xx = x is just what's needed to see that h'x is a homomorphism for each x, and then to see that h'(xy) = (h'x)(h'y). To see that the category of semigroups of neighboring idempotents is not an extensive category consider the four-element semigroup with multiplication given by: a b c d ________ a |a c c a b |d b b d c |a c c a d |d b b d It is a coproduct (in the category of semigroups of neighboring idempotents) of its one-element subsemigroups {a}, {b}. (In other words, it's the free semigroup of neighboring idempotents generated by a and b.) Now intersect these generating subsemigroups with the one-element subsemigroup {c} to see that pulling back along the inclusion map of {c} does not preserve coproducts. Still here? Guess what. The two categories are equivalent and the equivalence carries one example to the other. Given an object, , in *A* turn XxY into a semigroup by defining = . This is how the equivlence gets from *A* to the category of neighboring idempotents. Getting back is left to the reader. Now the real question: how much of all this is already in Johnstone? Date: Wed, 7 Aug 1996 12:54:20 -0300 (ADT) Subject: Peter Freyd's letter of 6 Aug Date: Wed, 7 Aug 1996 17:44:00 +1000 (EST) From: Max Kelly I refer to Peter Freyd's interesting letter of 6 Aug concerning distributive and extensive categories. Peter, you have not got quite right the current nomenclature for these: the definitive account of their interconnexions is in [Carboni, Lack, Walters, Introduction to extensive and distributive categories, JPAA 84 (1983), 145-158]. Their name for your "extensive" is "lextensive", which I think is due to Bill Lawvere; it means "lex and extensive", where "lex' is used to mean "having all finite limits". (By the way, I absolutely detest this usage of "lex"; a CATEGORY cannot be left exact!) Their "extensive" categories have only finite COPRODUCTS as part of the structure; but these are to be such that the canonical A/a x A/b --> A/(a+b) is to be an equivalence of categories. The point is important because a MORPHISM of extensive categories need preserve only finite coproducts, not finite limits (as a morphism of lextensive categories must). So the 2-categories involved are quite different, and this affects the notion of free category-with- -structure. One other thing: those semigroups you discuss are what I called "middle-ignoring semigroups" in my paper with Pultr [ On algebraic recognition of direct-product decompositions, JPAA 12(1978), 207-224], where I showed them equivalent to pairs of sets with neither empty or both - only as the simplest and most trivial example of our extension of Michael Barr's result on algebras for the "n-th power monad" sending A to A^n in any category. The funny thing is that I spoke on this as your guest in the colloquium at Philadelphia in 1977. Anyway, the more general situation of that paper may give more examples of distributive categories - I haven't yet had time to think about it. The category of middle-ignoring semigroups, by the way, and more generally the category of algebras for the n-th power monad P_n on the category of sets, is symmetric monoidal closed by Fred Linton's old result, since this monad is commutative - at least I think it must be so, without stopping now to check it. About the nomenclature: do people agree that "lex" is really terrible? Peter Johnstone in Sussex recently called it something like a twice-dead metaphor - but now I forget what he wanted in its place - was it Peter Freyd's "cartesian" ? Max Kelly. Date: Wed, 7 Aug 1996 12:56:39 -0300 (ADT) Subject: Re: extensive stuff Date: Wed, 7 Aug 96 10:17 BST From: Dr. P.T. Johnstone >Now the real question: how much of all this is already in Johnstone? Not much of it, if you mean what is in Johnstone's published work, rather than in Johnstone's mind. But my paper "A syntactic approach to Diers' localizable categories" in Springer LNM 753 (the 1977 Durham Symposium proceedings) is relevant: in it I introduced what I then called "disjunctive logic", which is exactly what Peter now wants to call "extensive logic" (and I guess that's a better name). What I was doing there was to describe a class of theories whose model categories (in Sets) were just the "localizable categories" (aka multiply presentable categories) introduced by Yves Diers in his thesis: there is nothing about extensive categories in my paper, because I didn't know the concept at that time. However, I've known for some years now that extensive categories are exactly the class of categories in which this fragment of logic should be modelled -- but I haven't found a suitable opportunity to set this down in print. Incidentally, the corresponding class of sketches (those with arbitrary finite cones, but only discrete finite cocones) has been studied by many people -- see for example Barr & Wells (TTT), page 292. Peter Johnstone Date: Wed, 7 Aug 1996 12:57:25 -0300 (ADT) Subject: Extensive stuff Date: Wed, 7 Aug 96 10:41 BST From: Dr. P.T. Johnstone A quick PS: since "semigroups of neighbouring idempotents" satisfy the identity xyz = xz, they already have a name: they are what the semigroup-theorists call "rectangular bands". As such, they appear in my paper "Collapsed toposes and cartesian closed varieties" (J. Algebra 129 (1990); see top of p. 462), as the simplest nontrivial example of what I called a "commutative hyperaffine theory". The fact that they form a category equivalent to the two-valued collapse of Set x Set is in my paper (though it was known long before), as is the fact that this category is cartesian closed but not locally cartesian closed -- and from the proof that it's not lcc you can easily extract a proof that it's not extensive. Peter Johnstone Date: Wed, 7 Aug 1996 12:58:14 -0300 (ADT) Subject: Faculty Position Date: Wed, 7 Aug 1996 10:43:42 +0100 (BST) From: Matthew Hennessy University of Sussex School of Cognitive and Computing Sciences LECTURER IN COMPUTER SCIENCE Applications are invited for a Lectureship in the Computer Science & A.I. group. The person appointed would ideally take up the post from 1 January 1997; a later start may be possible by negotiation. Candidates should be able to show evidence of serious research achievement in Foundations of Computation, preferably in an area close to the research interests of Professor Hennessy and Dr Jeffrey, and should be willing to teach in areas other than their research speciality. The post can be discussed informally with Professor Hennessy, matthewh@cogs.susx.ac.uk, tel. 01273 678101. The appointment will be made on the Lecturer A scale, for which salaries run from #15,154 to #19,848 p.a. Application forms and further particulars of this post are available from Sandra Jenks Staffing Services Office Sussex House University of Sussex Falmer, Brighton BN1 9RH UK tel: (0)1273 606755x3768 email: s.jenks@sussex.ac.uk Applications including CV and names of at least two referees should be sent to that address to arrive not later than 20 September 1996. Date: Wed, 7 Aug 1996 12:58:52 -0300 (ADT) Subject: Re: extensive stuff Date: Wed, 7 Aug 1996 09:40:48 -0300 From: RJ Wood Dear Peter Everybody keeps rediscovering your *A*. It probably belongs in Insights. Mike Barr's ``The Point of the Empty Set'' shows that the I-fold product functor, restricted to the full subcategory of *S*^I determined by the ``pure functors'', is monadic, in fact VTT. For I=2 the monad in question is TX=X^2 and a T-algebra is thus a set with a binary operation satisfying xx=x (xy)(zw)=xw (These are obviously equivalent to associativity and the equations you gave.) Anyway, this explains the equivalence of categories you mentioned. I certainly wasn't aware that *A* is distributive but not extensive. I'd just like to point out that *A* and its generalizations is also useful for showing that certain apparently multisorted algebraic categories are actually single sorted. For example, the obvious category of all modules over all rings is monadic over *A* and thus by the above also monadic over *S*. Others will have more to say on this. On a personal note, I first learned of *A* from my friend Kip Howlett who picked it up at some conference around `71. He realized that it was what I needed for my MSc thesis that involved M-sets with variable M and applications to automata theory. Anyway, sorting out *A* got me into category theory. Best regards RJ > The quickest artificial example is the full subcategory, *A*, of > (*S*)x(*S*), where *S* is the category of sets. A pair is > in *A* if either both X and Y are non-empty or both are empty. > *A* is coreflective, hence cartesian. It's closed under the formation > of products and coproducts, hence distributive (indeed, it's closed > under the formation of exponentials, hence an exponential category). > > *A* is not an extensive category. <{a,b},{a,b}> is the coproduct of > <{a},{a}> and <{b},{b}>. The intersection of each of these > subobjects with <{a},{b}> is <{},{}> hence pulling back along the > inclusion map of <{a},{b}> does not preserve coproducts. > > But I seem to have stumbled across a more natural example. In Cats and > Alligators a pair of idempotents e, e' are said to be "neighbors" > if ee'e = e and e'ee' = e'. So, let's understand a SEMIGROUP OF > NEIGHBORING IDEMPOTENTS to mean a semigroup satisfying the further > equations: > xx = x, > xyx = x. > > Note that as a consequence: xyz = (xzx)yz = x(z(xy)z) = xz. > > The category of semigroups of neighboring idempotents is a > distributive category because, even better, it's an exponential Date: Wed, 7 Aug 1996 12:59:51 -0300 (ADT) Subject: analytic functors Date: Tue, 6 Aug 1996 18:48:54 +0100 From: Luis Soares Barbosa I'm looking for references on analytical functors and their power series expansion. Thanks for any help. L. S. Barbosa Date: Wed, 7 Aug 1996 13:01:09 -0300 (ADT) Subject: Re: extensive stuff Date: Wed, 7 Aug 1996 11:07:35 -0400 From: Peter Freyd Yikes! Paul Taylor has pointed out to me that I left out one of the conditions for distributive and extensive categories, to wit, the disjointness of coproducts. (Please note, however, that all the categories that I said were distributive are distributive.) He also points out that finite limits are not needed to say that coproducts are stable. Of course. But they're certainly needed for extensive logic. So: should the standard definition of extensive categories include finite limits? Or should I -- help! -- go around talking about "locally distributive logic"? (I included finite limits in the definition of locally distributive, but needn't have done so: the condition that the category and that every slice of the category be distributive easily implies finite limits.) Date: Wed, 7 Aug 1996 13:20:21 -0300 (ADT) Subject: Re: extensive stuff Date: Wed, 7 Aug 1996 09:13:45 -0700 From: james dolan -Still here? Guess what. The two categories are equivalent and the -equivalence carries one example to the other. - -Given an object, , in *A* turn XxY into a semigroup by -defining = . This is how the equivlence gets from -*A* to the category of neighboring idempotents. Getting back is left -to the reader. yes, the algebraic theory of semigroups retracts onto the initial theory in two ways (left projection and right projection), so we get a theory morphism to the square of the initial theory that's surjective for some reason or other. the square of the initial theory is also the natural structure theory of the right adjoint but very slightly non-monadic functor "binary cartesian product of sets". i think these funny semigroups are some variety of "bands". unfortunately i can't remember what a "band" is exactly. -Now the real question: how much of all this is already in Johnstone? don't remember seeing it discussed there, but at least the part about the funny semigroups being the algebras for the monad associated to the slightly non-monadic adjunction between sets and pairs of sets is probably well-known, i'd guess. Date: Sat, 10 Aug 1996 23:50:30 -0300 (ADT) Subject: analytic functors Date: Thu, 8 Aug 1996 10:31:50 +1000 From: Ross Street Dear Luis Soares Barbosa >I'm looking for references on analytical functors and >their power series expansion. Presumably you know of Andre Joyal's article in SLNM 1234. There are close relationships amongst analytic functors, species and operads. So the topic is a BIG one. Recent "Notes on the Lie operad" by Todd Trimble might be a good starting place for seeing this connection and for seeing a thoroughly worked example. Sincerely, Ross Street Date: Sat, 10 Aug 1996 23:51:40 -0300 (ADT) Subject: Re: extensive stuff Date: Thu, 8 Aug 1996 11:43:51 +1000 (EST) From: stevel@maths.su.oz.au Dear Peter, I too ``rediscovered'' your *A*, precisely in looking for an example of a distributive category which failed to be locally distributive, but never realized that it had such an illustrious history. As for distributive categories which fail to be extensive, there is another important and natural class of examples. Any distributive lattice, thought of as a preorder, is a distributive category, indeed a locally distributive category but has coproducts which are very far from being disjoint and so fails to be extensive. In a distributive category admits a subdirect decomposition into a distributive and extensive category, and a distributive preorder, in the following way. Given a distributive category D, one can form the preorder reflection D_pr, and this is a distributive preorder and the projection D ---> D_pr a distributive functor. On the other hand, one can form the ``extensive reflection'' D_ext of D (this is the image of D under the left biadjoint to the inclusion of the 2-category of distributive and extensive cats in the 2-category of distributive cats), and the projection D ---> D_ext is also a distributive functor, and moreover the induced functor D ---> D_ext x D_pr is fully faithful. This is similar to a result of Cockett which fully embeds a _locally_ distributive category in the product of a lextensive category and a distributive preorder. The category D_ext has a very simple construction. An object of D_ext is an arrow a:A-->1+1 in D. An arrow from a:A-->1+1 to b:B-->1+1 is an arrow f:A-->B+1 in D satisfying the condition f A ----> B+1 | | a | | b+1 | | v v 1+1---> 1+1+1 inj_13 Steve. Date: Sat, 10 Aug 1996 23:53:32 -0300 (ADT) Subject: Re: extensive stuff Date: Thu, 8 Aug 1996 11:59:20 +1000 (EST) From: stevel@maths.su.oz.au > > He also points out that finite limits are not needed to say that > coproducts are stable. Of course. But they're certainly needed for > extensive logic. So: should the standard definition of extensive > categories include finite limits? Or should I -- help! -- go around > talking about "locally distributive logic"? (I included finite limits > in the definition of locally distributive, but needn't have done so: > the condition that the category and that every slice of the category > be distributive easily implies finite limits.) > > As Max Kelly pointed out, an extensive category with finite limits has been called a lextensive category. The problem still remains what one should call an extensive category with finite products (such a category being necessarily distributive). ``Extensive and distributive category'' is a bit of a mouthful, and prextensive is obviously unacceptable. Other possibilities that have been suggested include ``2-rig'' and ``arithmetic category''. Steve. Date: Sat, 10 Aug 1996 23:54:31 -0300 (ADT) Subject: Re: extensive stuff Date: Thu, 8 Aug 96 09:55 BST From: Dr. P.T. Johnstone Max asks: >About the nomenclature: do people agree that "lex" is really terrible? Peter Johnstone in Sussex recently called it something like a twice-dead metaphor - but now I forget what he wanted in its place - was it Peter Freyd's "cartesian" ? and Peter asks: should the standard definition of extensive categories include finite limits? Or should I -- help! -- go around talking about "locally distributive logic"? Yes, I've been a convert for some time now to the Freydian use of "cartesian" for categories having (or functors preserving) all finite limits. I know this annoys the computer-science people who want to use it for (finite products but not equalizers), but I can't think of a better term. Actually, as applied to categories, "left exact" is a thrice-dead metaphor (twice-dead as applied to functors, since "exact sequence" is a dead metaphor for "exact differential", and "left exact" as applied to functors is a dead metaphor for "preserving the left- hand ends of exact sequences"). What status that gives to the term "lextensive" for "extensive plus all finite limits", I shudder to think. Should the standard definition of extensive categories include finite limits? Obviously Max (and Bob Walters, and Steve Lack, and probably Bill Lawvere) would say "no". But if you want to develop a syntax for these categories, you're not going to get very far without the finite limits; so we do need a name for "extensive plus finite limits". Perhaps, after all, we should revive the term "disjunctive" from my SLNM 753 paper, and call them "disjunctive categories". What do other people think? Peter Johnstone P.S. - If anyone was confused by the two messages I contributed to this discussion yesterday, please note that they were sent out in the reverse of the order in which I sent them in. Not that it matters very much. Date: Sat, 10 Aug 1996 23:55:45 -0300 (ADT) Subject: Re: Peter Freyd's letter of 6 Aug Date: Thu, 8 Aug 1996 11:47:50 +0200 From: Dr. Reinhard B/rger (Prof. Dr. Pumpl^nn) Just for completeness, I think that the category of middle-ignoring semigroups is equivalent to the category of pairs of sets which are either both empty or both non-empty. Another example of a category which is distributive but not extensive is the dual of the category of unital rings; note that the dual of the category of unital commutative rings is even extensive. Greetings Reinhard Date: Sat, 10 Aug 1996 23:56:56 -0300 (ADT) Subject: Re: analytic functors Date: Sat, 10 Aug 1996 22:11:38 -0400 (EDT) From: Andre Joyal Dear Prof. Barbosa, you can read on analytic functors and their power series expansion in my paper "Foncteurs analytiques et especes de structures" published in the proceedings of a Colloquium on Enumerative Combinatorics SLN 1234 (1984 or 1985?). Unfortunatly, the paper is in french. If you have any questions, I would be glad to help. Andre Joyal Date: Wed, 14 Aug 1996 23:04:21 -0300 (ADT) Subject: disjunctive stuff Date: Sun, 11 Aug 1996 16:11:09 -0400 From: Peter Freyd Regarding some comments of Peter Johnstone: I haven't succeeded in interpreting disjunction in arbitrary wcartesian extensive categories and would therefore hesitate in calling them "disjunctive categories." Computer scientists used to use the phrase "concrete" to mean "well- pointed" but seemed to have stoped as they became aware of the clash with existing category terminology. (By the way, I can't think at the moment of many people in CS, other than Robin C and friends, who use "cartesian" just to mean products.) Date: Wed, 14 Aug 1996 23:06:04 -0300 (ADT) Subject: alternating stuff Date: Sun, 11 Aug 1996 17:15:58 -0400 From: Peter Freyd How about "alternating categories"? Alternatives, in ordinary language, are usually understood to be mutually exclusive. So an extensive cartesian category (i.e. a locally distributive category with terminator) would be called an "alternating category" and the corresponding syntax, "alternating logic". A major problem: it would be hard to keep others -- since I find it hard to keep myself -- from corrupting this to "alternative logic". (On the other hand, whenever one is an environment where "linear logic" is sure to be totally misinterpreted, one could claim also to be studying "alternative logic".) Let me go on record here for the syntax. As in cartesian logic conjunction is the only connective and the only terms are conjunctions of primitive predicates each followed by an appropriate sequence of variables. Cartesian logic has just one primitive assertion, written A ue> B, where A and B are terms. Given an elemental interpretation of the primitive predicates, A ue> B is satisfied in the elemental cartesian semantics if for every instantiation of the variables of A such that A holds there is a unique instantiation of the remaining variables of B such that B holds. In alternating logic the primitive assertions are written A ue> B1|B2|...|Bn where A, B1, B2,...,Bn are terms. Such an assertion is said to be satisfied in the elemental alternating semantics if for every instantiation of the variables of A such that A holds there is a unique index, i, such that the remaining variables of Bi can be instantiated so that Bi holds and, further, there is just one such instantiation of the remaining variables of Bi. E.G.: for (decidable) fields, add to the cartesian theory of unital rings the alternating axiom x=x ue> (x=0)|(xy=1). As for the categorical semantics, given an alternative category in which each primitive predicate has been interpreted, extend the interpretation to terms -- just as for cartesian logic -- using finite limits. (For example: if A has variables x and y, and B has variables y and z then, using brackets to designate the interpretations, the interpretation of A^B is characterized by [A^B] l/ \r [A] [B] / \ / \ [x] [y] [z] where the rhombus is a pullback.) Note that the interpretation of a conjunction comes equipped with the two maps, l and r. In cartesian logic the key definition: A ue> B is satisfied iff l:[A^B] -> [A] is an isomorphism. In alternating logic: A ue> B1|B2|...|Bn is satisfied iff the l's combine to give an isomorphism [A^B1] + [A^B2] +...+ [A^Bn] -> [A]. Date: Wed, 14 Aug 1996 23:07:06 -0300 (ADT) Subject: 62nd PSSL Date: Tue, 13 Aug 1996 15:48:52 +0200 From: Jaap van Oosten PRELIMINARY ANNOUNCEMENT Dear colleagues, This is to inform you that the 62nd Peripatetic Seminar on Sheaves and Logic will be held in Utrecht (The Netherlands), in the weekend of 26-27 October, 1996. A "first announcement", with details regarding registration and the like, will follow in September. Carsten Butz, Ieke Moerdijk & Jaap van Oosten Date: Sun, 18 Aug 1996 11:29:37 -0300 (ADT) Subject: Re: alternating stuff Date: Thu, 15 Aug 1996 17:01:33 +1000 (EST) From: stevel@maths.su.oz.au > Date: Wed, 14 Aug 1996 23:06:24 -0300 (ADT) > > Date: Sun, 11 Aug 1996 17:15:58 -0400 > From: Peter Freyd > > How about "alternating categories"? Alternatives, in ordinary > language, are usually understood to be mutually exclusive. So an > extensive cartesian category (i.e. a locally distributive category > with terminator) would be called an "alternating category" and the > corresponding syntax, "alternating logic". > An extensive cartesian category is _not_ the same as a locally distributive category with terminator: as has already been pointed out, extensive categories are also required to have disjoint coproducts, which locally distributive categories need not, as the example of distributive lattices shows. Although I entirely agree that calling a category ``lex'' if it has finite limits is a bad thing, and am not thrilled about the name lextensive for an extensive category with finite limits, I do think that the name does have some advantages. In particular it makes clear that the two notions are closely linked. As various people have pointed out, for many uses the extensive categories won't be much use unless you have the finite limits as well; the reason, at least from my point of view, for isolating the extensive categories is to emphasize the fact that they are in fact categories with finite coproducts satisfying a certain _property_ which does not depend on the _structure_ of having all finite limits. As an ``excuse'' for the name lextensive, one can think of it as standing for (finite )l(imits +)extensive. Steve. Date: Sun, 18 Aug 1996 11:28:38 -0300 (ADT) Subject: alternating stuff Date: Thu, 15 Aug 1996 00:22:45 -0400 From: James Otto Date: Sun, 11 Aug 1996 17:15:58 -0400 From: Peter Freyd How about "alternating categories"? Alternatives, in ordinary language, are usually understood to be mutually exclusive. So an Alternating (Turing) machines are fundamental to complexity and logic programming. The alternation is of bounded quantifiers. The exclusive, inclusive distinction is captured by the orthogonal, injective distinction, which is a strong model, weak model distinction. extensive cartesian category (i.e. a locally distributive category with terminator) would be called an "alternating category" and the corresponding syntax, "alternating logic". ... Let me go on record here for the syntax. As in cartesian logic .... In cartesian logic the key definition: A ue> B is satisfied iff l:[A^B] -> [A] is an isomorphism. On the models side of dualities, this is precisely being orthogonal to a map. In alternating logic: A ue> B1|B2|...|Bn is satisfied iff the l's combine to give an isomorphism [A^B1] + [A^B2] +...+ [A^Bn] -> [A]. On the models side of dualities, this is precisely being orthogonal to a small cone with discrete base. E.g. see Ad\'amek and Rosick\'y's book including its historical remarks e.g. on Y. Diers. I like P. Johnstones's `multi-' for the map, cone distinction. On the theory side of dualities, P. Johnstones's remarks may help me. Just out of curiousity, if one drops the `closed' (which I do not) from `cartesian closed' or `locally cartesian closed', what would one expect to have? Regards, Jim Otto Date: Sun, 18 Aug 1996 11:30:53 -0300 (ADT) Subject: Re: disjunctive stuff Date: Thu, 15 Aug 96 10:27 BST From: Dr. P.T. Johnstone I'm not sure about `alternating logic' and `alternating categories'; perhaps I just need time to get used to them. I think the trouble is that in everyday speech `alternating' means something dynamic (switching back and forth between two states), and the logic doesn't have any such feature. `Alternative' doesn't have the same connotation, but I agree that `alternative logic' is impossible. The original reason for `disjunctive' was a pun: it stands for both `disjunction' and `disjoint'. The way I formulated the syntax (essentially, an extension of Michel Coste's version of cartesian logic), you are allowed to write down a disjunction of formulae if you can prove that it's disjoint (just as you can use an existential quantifier if you can prove that the thing being quantified is unique). Peter Johnstone Date: Sun, 18 Aug 1996 11:31:56 -0300 (ADT) Subject: Weak n-categories Date: Thu, 15 Aug 1996 04:39:47 -0700 (PDT) From: john baez It occurred to me that some people on this list might be interested in seeing the definition of weak n-categories proposed by James Dolan and myself. We are very slowly writing a paper on this, which will appear as part of the series "Higher-dimensional algebra" in Adv. Math.. (The first paper in this series is on braided monoidal 2-categories, and the second will be on 2-Hilbert spaces.) However, a sketch of the definition has been available on the web for some time; it's at http://math.ucr.edu/home/baez/ncat.def.html Also, a bunch of expository material on mathematical physics, category theory and so on can be found at http://math.ucr.edu/home/baez/README.html Sincerely, John Baez Date: Sun, 18 Aug 1996 11:32:47 -0300 (ADT) Subject: Re: extensive stuff Date: Thu, 15 Aug 1996 13:31:16 +0000 From: Steve Vickers If "lex" fills a need in our vocabulary - "having finite limits" when applied to structures, "preserving finite limits" when applied to transformations -, can't we forgive it the deadness of its metaphorical origins? I suspect there are other metaphorically dead words in mathematics - what about ring or field? The fundamental problem with "Cartesian" now is that it is ambiguous. Whenever it's used we have to investigate whether non-product limits are required. Steve Vickers. Date: Sun, 18 Aug 1996 11:33:44 -0300 (ADT) Subject: Re: disjunctive stuff Date: Thu, 15 Aug 1996 15:09:14 -0400 From: Michael Barr A propos the discussion of "cartesian", I might add that I think Descartes also invented the idea of the graph of a function and that is an equalizer. FWIW. Michael Date: Sun, 18 Aug 1996 11:34:51 -0300 (ADT) Subject: Sheaves Date: Thu, 15 Aug 1996 17:36:16 -0300 (EST) From: Regivan Hugo Nunes Santiago I'm looking for introdutory references on Sheaves Thanks for any help. Regivan Date: Sun, 18 Aug 1996 11:35:52 -0300 (ADT) Subject: BOOK: Foundations for Programming Languages (Mitchell) Date: Fri, 16 Aug 1996 11:44:40 -0700 From: John C. Mitchell BOOK ANNOUNCEMENT ----------------- Foundations for Programming Languages by John C. Mitchell "Programming languages embody the pragmatics of designing software systems, and also the mathematical concepts which underlie them. Anyone who wants to know how, for example, object-oriented programming rests upon a firm foundation in logic should read this book. It guides one surefootedly through the rich variety of basic programming concepts developed over the past forty years." -- Robin Milner, Professor of Computer Science, The Computer Laboratory, Cambridge University "Programming languages need not be designed in an intellectual vacuum; John Mitchell's book provides an extensive analysis of the fundamental notions underlying programming constructs. A basic grasp of this material is essential for the understanding, comparative analysis, and design of programming languages." -- Luca Cardelli, Digital Equipment Corporation Written for advanced undergraduate and beginning graduate students, Foundations for Programming Languages uses a series of typed lambda calculi to study the axiomatic, operational, and denotational semantics of sequential programming languages. Later chapters are devoted to progressively more sophisticated type systems. Compared to other texts on the subject, Foundations for Programming Languages is distinguished primarily by its inclusion of material on universal algebra and algebraic data types, imperative languages and Floyd-Hoare logic, and advanced chapters on polymorphism and modules, subtyping and object-oriented concepts, and type inference. The book is mathematically oriented but includes discussion, motivation, and examples that make the material accessible to students specializing in software systems, theoretical computer science, or mathematical logic. Foundations for Programming Languages is suitable as a reference for professionals concerned with programming languages, software validation or verification, and programming, including those working with software modules or object-oriented programming. MIT Press Foundations of Computing series September 1996 ISBN 0-262-13321-0 608 pp. << actually 850 pages >> $60.00 (cloth) MIT PRESS display: http://www-mitpress.mit.edu:80/mitp/recent-books/comp/mitfh.html Date: Sun, 18 Aug 1996 11:36:53 -0300 (ADT) Subject: strongly (or exclusive) disjunctive logic: Hu, Tholen Date: Sat, 17 Aug 1996 11:22:07 -0400 From: James Otto Dear People, Perhaps I already said more about strongly (or exclusive) disjunctive logic than I wished. (So this is 2 of 2.) But I should note H. Hu, W. Tholen, Limits in free coproduct completions, JPAA 105 ('95) Rather than a duality as in P. Gabriel, F. Ulmer, Springer LNM 221 ('71) M. Makkai, A. Pitts, TAMS 299 ('87) but somewhat as in P. Johnstone, In Springer LNM 753 ('79) they construct a dual and a double dual: small with multi-limits of finite diagrams | flat functors to set v finitely accessible with connected limits | functors to set preserving filtered colimits and connected limits v having finite limits and stable disjoint small coproducts with net image the coprimes. By the way, for accessible categories one could see J. Ad\'amek, J. Rosick\'y, Cambridge ('94) F. Borceux, Volumes 1-2, Cambridge ('94) for alternating Turing machines D. Bovet, P. Crescenzi, Prentice Hall ('94) and for quantifiers, games, and interactive proofs (a book which I am less familiar with than the previous 4) J. K\"obler, U. Sch\"oning, J. Tor\'an, Birkh\"auser ('93) Regards, Jim Otto Date: Thu, 22 Aug 1996 09:26:32 -0300 (ADT) Subject: Re: cartesian/(L)extensive/... stuff Date: Tue, 20 Aug 1996 15:38:11 -0600 (MDT) From: Robin Cockett (1) First, in response to Peter's earlier comments about the term "cartesian": I would certainly like to consider Peter as a friend! Some names for mathematical concepts are like old jeans: the more threadbare and holes they have the more comfortable they feel. I suspect the term cartesian might be one such. I tend to think of a "cartesian tensor" as being a product - as saying a bit of structure is cartesian usually means it arises from limits - and have abused terminology by calling what I should have probably called a "cartesian tensor category" (or a "cartesian monoidal category") a "cartesian category" -- yes this is a category with products. I am usually careful, however, to make this usage explicit as I am aware that equalizers are often assumed. (2) Another article of comfy clothing is the term extensive! I agree with Steve Lack that it is unfortunate that extensive categories are not assumed to have a final object (as these creatures are the more common) I merrily suggest abusing terminology to avoid that hiccup. I would be less happy, however, to let the LEXness - or should I say cartesianness - be carried by the context. My reason for this hesitation is as follows: If you start with a distributive category and form its extensive completion, as explained by Lack, then all datatypes (natural numbers, lists, etc.) lift into that completion. These datatypes are shapely in the sense of Barry Jay (naturallity square are cartesian etc.). However, if you, taking the construction from another angle, freely add equalizers to a distributive category with datatypes (i.e. finitely complete it) all bets are off: certainly datatypes which do lift need not be shapely but I conjecture that there is, in fact, no guarantee that they lift at all ... Conjecture: There is a distributive category X with (strong) NNO such that ========== E(X) is its equalizer completion does not have a (strong) NNO. I do not have a proof that this is so ...or not! Coproducts appear to lift as the equalizer completion 2-functor preserves products. However, clearly (consider a distributive lattice) the resulting coproducts need not be extensive -- although, of course, the category E(X) is distributive (another source of non-extensive distributive categories). If the distributive category is separated (or decidable) in the appropriate sense then certainly datatypes lift (as the extensive completion and equalizer completion then coincide). This is the reason why the initial distributive category with (strong) datatypes may be finitely completed to preserve all datatypes. This makes me sensitive about the passage to Lextensive even from extensive. To obtain a completion in a RIGHT SENSE may be a little more delicate (or brutish ... depending on your approach). The point is there are some outstanding issues here .. (3) Lastly a remark on the connection between distributive categories and categorical proof theory: One motivation for developing the theory of weakly distributive categories (wdc) was to provide a unification of the proof theory of "classical" and linear logic. In particular, we supposed that the "and--or" fragment of classical logic has as a proof theory the free distributive category on its propositions. Accordingly, in that original paper, we sketched a proof that distributive categories are cartesian wdc's (i.e. wdc's in which the tensor is a product and the cotensor a coproduct). Subsequently we never revisited the result. Over the summer while studying the nucleus of these categories we realized something was amiss. Re-examing the proof we realized that one of the "obvious" coherence conditions was obviously false. In fact, so badly does it fail for distributive categories that the revision of the result states: Prop. A cartesian wdc which is simultaneously a distributive category is necessarily a preorder. It should be mentioned that cartesian wdc's abound: pointed sets, vector spaces, semi-lattices, ... are examples. Thus cartesian wdc's definitely do not collapse. (Back to names!!!! This does remove one of our motivations for the name "weakly distributive categories": Barr suggested the term "linearly distributive". However, to us the original name is now one of those comfy bits of clothing (even if somewhat frayed) ... In fact, if we had NOT made this oversight it is likely we would have been altogether more hesitant in the development of weakly distributive categories! Mathematics moves in mysterious ways.) There is philosophical significance to the correct result: classical semantic settings separate at an earlier stage than we had suspected from (categorical) proof theoretic settings. In particular, distributive categories (a core fragment of classical setting) do not permit the process of cut elimination (unless they are preorders). -robin (Robin Cockett) (p.s. Revised papers are available under Seely's home page: ftp://triples.math.mcgill.ca/pub/rags/ragstriples.html) Date: Thu, 22 Aug 1996 09:25:46 -0300 (ADT) Subject: Position at QMW Date: Tue, 20 Aug 1996 15:45:32 +0100 (BST) From: Edmund Robinson We'd like to encourage applications for the following position. Please bring it to the attention of those of your friends and colleagues you think might be interested. best wishes Edmund Robinson ----------------------------------------------------------------------- Department of Computer Science Queen Mary and Westfield College University of London Lecturer in Computer Science (Fixed Term for Five Years) The Department of Computer Science will have a vacancy from 1st January 1997 to replace Dr David Pym who has been awarded an EPSRC Advanced Fellowship. The person appointed would be expected to further strengthen the department's existing research groups (Artificial Intelligence, Distributed Systems, Human Computer Interaction, Logic and Foundations of Programming, Parallel Computing) and to be able to teach a range of the undergraduate and postgraduate Computer Science courses. Salary according to experience UK pounds 18,120pa - 21,982pa inclusive. Informal enquiries may be made to Prof. Heather Liddell (Head of Department) on +44 (0)171 975 5167. Further information can be obtained on URL: http://www.dcs.qmw.ac.uk/jobs/temp-lecturer-description.html For further information and an Application Form please contact our 24 hour recruitment line on +44 (0)171 975 5171 quoting Reference 96624. Your application is to be returned by 16/09/1996 and should be addressed to the: Personnel Officer, Queen Mary and Westfield College, Mile End Road, London, E1 4NS. Date: Thu, 22 Aug 1996 22:45:14 -0300 (ADT) Subject: Re: cartesian/(L)extensive/... stuff Date: Fri, 23 Aug 1996 11:02:53 +1000 (EST) From: Steve Lack > > (2) Another article of comfy clothing is the term extensive! I agree > with Steve Lack that it is unfortunate that extensive categories are not > assumed to have a final object (as these creatures are the more common) I can't quite imagine in what context I might have said that; it is certainly true that life becomes easier when the extensive category in question has a terminal object, but the whole point is that the notion of extensivity is a property of finite coproducts. (So in particular an extensive functor is one that preserves finite coproducts only, although of course it then follows that pullbacks along coproduct injections are also preserved.) > > If you start with a distributive category and form its extensive completion, > as explained by Lack, then all datatypes (natural numbers, lists, etc.) lift > into that completion. These datatypes are shapely in the sense of > Barry Jay (naturallity square are cartesian etc.). However, if you, > taking the construction from another angle, freely add equalizers to a > distributive category with datatypes (i.e. finitely complete it) all bets > are off: certainly datatypes which do lift need not be shapely but I conjecture > that there is, in fact, no guarantee that they lift at all ... > > Conjecture: There is a distributive category X with (strong) NNO such that > ========== E(X) is its equalizer completion does not have a (strong) NNO. > > I do not have a proof that this is so ...or not! > > Coproducts appear to lift as the equalizer completion 2-functor > preserves products. However, clearly (consider a distributive lattice) the > resulting coproducts need not be extensive -- although, of course, the category > E(X) is distributive (another source of non-extensive distributive categories). In fact, (1) If X is distributive then E(X) is locally distributive but (2) If X is distributive and E(X) is extensive then X is equivalent to the trivial category 1. To (freely) pass from a distributive category to a lextensive one, you first form E(X) and then the slice category p/E(X) where p is the equalizer i ---> p ---> 1 ---> 1+1 j of the coproduct injections i,j:1--->1+1. The passage from extensive categories to lextensive categories, is, as Robin says, more delicate. Steve Lack. Date: Thu, 22 Aug 1996 22:46:59 -0300 (ADT) Subject: Re: a proposal (4 submissions) [Note from moderator: The following are further posts on Michael Barr's proposal. Since the subject is not directly within the topic of this list, further submissions will be forwarded to Michael, and posted to the list in digests like this one. Regards to all, Bob Rosebrugh] ++++++++++++++++++++++++++++ Date: Wed, 7 Aug 1996 10:11:53 -0400 (EDT) From: James Stasheff flash response I thought significiantly new proofs of known results were publishable on paper I would welcome the paper for TAC but having a journal specifically for what Barr describes is an intriguing idea Jim Stasheff jds@math.unc.edu Math-UNC (919)-962-9607 Chapel Hill NC FAX:(919)-962-2568 27599-3250 http://www.math.unc.edu/Faculty/jds ++++++++++++++++++++++++++++++++++++++++++++ Date: Wed, 7 Aug 1996 09:55:59 +0100 (BST) From: Adam Eppendahl I find it very irritating that so many useful pictures are drawn when a person speaks on a subject and yet so few of these pictures appear in publication. A good drawing is often like a new proof in that it represents how a person is actually using a particular idea on a daily basis. A journal that accepts new proofs might also encourage such drawings. `Journal of Mathematical Illuminations'? Adam Eppendahl +++++++++++++++++++++++++++++++++++++ >From Reinhard.Boerger@FernUni-Hagen.de Date: Thu, 8 Aug 1996 11:40:26 +0200 From: "Dr. Reinhard B/rger I like Mike`s proposal and I think it would even make sense to publish attempts of proofs that do not work in order that it prevents other people from spending much time on the same attempts. Greetings Reinhard +++++++++++++++++++++++++++++++++++++++++++ Date: Thu, 8 Aug 1996 11:57:10 -0400 From: Michael Barr There was a question raised in connection with my suggestion towards a proposal about archiving. There are a number of answers. First off, TAC is being archived by both the Canadian Math. Soc. and some government organization. In addition to Mt. Alison U. What I would like to see is some libraries print and bind each volume. My faith that this will happen is not increased by what I heard about one university library. They are planning, for some journals, that they will receive and shelve the paper copy and then, at the end of the year, when the online volume is available, discard it! I have referred, in recent papers, to papers that appeared in 1944 and 1945 and a book (Lefschetz's Algebraic Topology) from the 30s. I do not have the same faith the librarian does that a 1990s electronic archive will still be usable in 50 years, but that problem is not one for electronic journals alone. Michael +++++++++++++++++++++++++++++++++++++++++++ Date: Fri, 16 Aug 1996 12:49:44 -0400 (EDT) From: F William Lawvere Dear Mike I am strongly in favor of your proposal. Such a journal can begin to solve a very major problem which existing institutions are scarcely addressing. We must end the standard whereby "expository" articles do not EXPLAIN. Bill Lawvere Date: Sat, 24 Aug 1996 11:44:33 -0300 (ADT) Subject: Re: cartesian/(L)extensive/... stuff Date: Fri, 23 Aug 1996 11:53:12 -0600 (MDT) From: Robin Cockett I did mean extensive + products and mistyped "final object." The point being that these are common beasties which deserve a snappy name! Further, Steve Lack is correct about the fact that if E(X) is extensive and X is distributive then X = 1. So I should correct my comments about when the equalizer completion and extensive completion coincide! ... and I have to chuckle at this point as I have tripped on my own snag ... The problem is the initial object. In a distributive category this object is only one way connected to the rest of the category so that the poset collapse of a distributive category is always non-trivial while the category itself is. This means the added equalizer i ---> p ---> 1 ---> 1+1 j of the coproduct injections i,j:1--->1+1 in E(X) is never isomorphic to the initial object. Hence Steve Lack's comment. Some time ago (when I was in Oz, in fact) I sensitized the community there to exactly these issues. In fact, I became a bit of a heretic by considering distributive categories without an initial object (I called these predistributive). It is the initial of these gadgets (with "non-empty" inductive datatypes) which has E(X) extensive ... and the initial object is provided precisely by the added equalizer p, above. However, it really is infinitely better to talk about LEXT(X), the lextensive completion, not the raw E(X) where some preinitial baggage may still be present. The conjecture still stands but is better expressed in the form: Conjecture: There is a distributive category X with (strong) NNO such that ========== LEXT(X) is its lextensive completion does not have a (strong) NNO. -robin Date: Tue, 27 Aug 1996 10:20:01 -0300 (ADT) Subject: terminology Date: Mon, 26 Aug 1996 11:07:26 +1000 (EST) From: Steve Lack Regarding the debate on cartesian/extensive, we'd like to suggest the name "arithmetic category" for an extensive category with products. Certainly such categories seem well structured enough to do some arithmetic, and free such are closely enough related to the free analogies in the algebraic context (ie rigs) to be thought of as behaving "arithmetically" in some sense. Robbie Gates Steve Lack -- ---------------------------------------------------------------------- robbie gates | apprentice algebraist | http://cat.maths.usyd.edu.au/~robbie pgp key available | Date: Tue, 27 Aug 1996 10:21:12 -0300 (ADT) Subject: re: a proposal (3 submissions) Date: Thu, 22 Aug 1996 23:34:24 -0300 From: RJ Wood Dear Michael I am also strongly in favour of `Insights' but I think that those insights that come from our community using categorical ideas should be published in TAC. The fact is that genuine insights are far rarer than publishable technical papers. If TAC also publishes the kind of papers that you spoke of it won't put the journal below JPAA but rather {\em above} it by true scientific criteria. If TAC had a policy of dubbing certain papers as `Insight' papers it would probably confer extra prestige upon them. Why make it necessary to read yet another journal? With the change in medium we have an opportunity for reform. We have a favoured moment in history to rewrite some of the rules and tell the dean set what is important rather than waiting to receive our next set of instructions from them. We also have demography on our side. Many of us have little to lose by putting a bit on the line and that could make things a lot healthier for the next generation of category theorists. RJ +++++++++++++++++++++++++++++++++++++++++++++++++++ Date: Fri, 23 Aug 1996 15:21:01 +0100 From: "Prof R. Brown" Subject: (i) new proofs (ii) Archiving of electronic journals (i) New proofs I had a paper accepted in which the referee wrote t hat the theorem was not new, the proof was not new, but the paper should be accepted, as the originals were notorious! (ii) Archiving I am glad the idea has been put forward of paper archiving of electronic journals, in addition of course to other methods. This would help for authenticity, archiving, and for prospective authors to get a quick idea of what is in the journals. Journals on shelves have advantages over electronic media in some respects, as well as disadvantages. It could be useful to ask libraries to make a small subscription to pay for a well produced cover for a full volume, to be bound in with it, which would also confirm authenticity of the papers. Of course, electronic journals may in the end include more than can easily be put on paper, but this proposal would ensure some of the advantages of paper journals without the currently increasingly prohibitive cost (which includes keeping publishers staff and offices in good order, but based on free service by academics). For example, current technology would allow easy printing of colour where required in a paper archive of an electronic journal, and could include reference to access for further electronic facilities (e.g. animation). Ronnie Brown Prof R. Brown School of Mathematics Dean St University of Wales Bangor Gwynedd LL57 1UT UK Tel: (direct) +44 1248 382474 (office) +44 1248 382475 Fax: +44 1248 355881 email: mas010@bangor.ac.uk wwweb: http://www.bangor.ac.uk/~mas010/home.html wwweb for maths: http: //www.bangor.ac.uk/ma wwweb for `Symbolic Sculptures and Mathematics': http://www.bangor.ac.uk/~mas007/welcome.html +++++++++++++++++++++++++++++++++++ Date: Sun, 25 Aug 1996 16:52:25 -0400 (EDT) From: James Stasheff Subject: pictures In response to Eppendahl's response to Barr's sugestion of a new type or journal or at least article, fortunately drawing capabilities in xy fig or latex or... are becoming so user friendly that even I have attempted a few so hopefully more and more pictures will make it from the blackboard to the publication - electronic or print. Jim Stasheff jds@math.unc.edu Math-UNC (919)-962-9607 Chapel Hill NC FAX:(919)-962-2568 27599-3250 http://www.math.unc.edu/Faculty/jds May 15 - August 15: 146 Woodland Dr Lansdale PA 19446 (215)822-6707 Date: Wed, 28 Aug 1996 10:42:44 -0300 (ADT) Subject: Re: terminology Date: Tue, 27 Aug 1996 14:45:24 +0000 From: Steve Vickers >Regarding the debate on cartesian/extensive, we'd like to suggest >the name "arithmetic category" for an extensive category with products. > >Certainly such categories seem well structured enough to do some >arithmetic, and free such are closely enough related to the free >analogies in the algebraic context (ie rigs) to be thought of as >behaving "arithmetically" in some sense. > >Robbie Gates >Steve Lack The phrase "Arithmetic Category" with this sense doesn't sit comfortably next to Joyal's "Arithmetic Universes", in which the word "arithmetic" also conveys recursive structure. Steve Vickers. Date: Thu, 29 Aug 1996 13:19:18 -0300 (ADT) Subject: Re: alternating stuff Date: Thu, 29 Aug 1996 14:59:54 +0200 (MET DST) From: Jiri Rosicky In a recent paper (An algebraic description of locally multipresentable categories, TAC 2 (1996), 40-54), we have introduced essentially multialgebraic theories and showed that they correspond to locally finitely multipresentable categories in the same way as essentially algebraic theories correspond to locally finitely presentable categories. J.Adamek, J.Rosicky Date: Thu, 29 Aug 1996 13:18:34 -0300 (ADT) Subject: Re: terminology Date: Thu, 29 Aug 1996 03:00:41 -0400 (EDT) From: F William Lawvere The term EXTENSIVE was applied to certain categories in 1991 by Carboni, Lawvere, and Walters on the basis of the following considerations. For centuries, mathematical philosophy has distinguished between extensive quantities and intensive quantities, for example in thermodynamics of inhomogeneous bodies, volume, mass, energy, and entropy on the one hand are distinguished from pressure, density, temperature on the other. Lawvere in 1982 (SLNM 1174) and in 1990 (Categories of Space and of Quantity) had proposed to explain these as modes of variation of quantity. Quantities vary over a domain of variation in both cases. ( A domain of variation is a "space" , which in turn is an object in a category of space, which will be rather more determinate than "category" in general). An extensive quantity type is a covariant functor from a category of space, preserving finite coproducts, to a linear category (= one in which coproducts and products coincide). A distribution, a measure, a current, a homology class on a sum domain is given by a tuple of such , one on each summand ; thus all these are elements of extensive quantity types. An intensive quantity type is a contravariant functor from a category of space which also takes coproducts to products ; but more: intensive quantities usually act linearly on extensive quantities, lending them (not only a linear but also a) multiplicative structure which is also preserved by the contravariant functorality. For example, functions act as densities on distributions and measures, similarly differential forms act on currents, and cohomology classes act on homology classes. Often intensive quantity types are representable and related extensive types are definable as linear duals ( Riesz, Pontrjagin, Eilenberg- Mac Lane etc),but these are not the only possibilities. A fundamental example of a linear "category" is the 2-category of all categories with coproducts; it has an obvious abstraction functor to the linear category of commutative monoids, by taking isomorphism- classes. Part of the idea of K-theory and of K-homology and of the "non-linear K-theory" which I with Schanuel and others have been pursuing under the name of "objective number theory" is that it is useful to "objectify" quantities by lifting their type across this abstraction functor. The most fundamental measure of a thing is the thing itself. But measures can be pushed-forward ( a common colloquial expression for the covariant functorality of extensive quantity).However pullback is more familiar (already in 1844 Grassmann complained that intensives were more familiar than Ausdehnungen) : On any category with pullbacks, there is the contravariant functor to cat which takes the "slice" categories of each object.This functor is commonly viewed as consisting if "functions", namely functions whose values are the fibers. Indeed if the category satisfies suitable conditions , this will be an intensive quantity type. But what extensives will it act on ? On any category at all the slice categories constitute an even simpler covariant cat-valued functor, simply composing the transforming map following the structural map to define the new structural map. It is often appropriate to consider that the structural map distributes the total in the base ( though distributions usually do not have values at points, they do often have totals ) and that the mentioned composing pushes the distribution forward. Indeed if the category has coproducts, this naive pushing forward is automatically linear. Thus a category with coproducts defines an extensive quantity type on itself if and only if it is an extensive category. If we call lextensive any extensive category with (finite) limits, then also by pullback, the intensives act on the extensives in a way that satisfies all reasonable functoralities, including the crucial CCR or "projection formula". More exactly, note that there will typically be lots of subcategories of such a "category of space" which are extensive but do not themselves have products or even a terminal object; it suffices to be closed under sums and summands. Namely the empty space together with all spaces of dimension exactly 7. Any such subcategory A defines the extensive quantity type "distributions of A-dimensional spaces " in each base space X, namely the subslice category. Given A and B two extensive subcategories, there is an objective intensive quantity type which acts roughly as " B-A dimensional cohomology" namely for any X consider the category of all those spaces over X such that for any space over X whose total is in A, the pullback has total in B ; this pulls back along any change of X. Of course many extensive subcategories of a (lextensive) category of space will have products, for example (as Joyal pointed out to me in 1984) if A=B is the "compact" objects , thus defining the extensive notion of distributing a compact object in a base space, the corresponding intensive quantities which act on these are the proper fiberings . Date: Thu, 29 Aug 1996 13:20:08 -0300 (ADT) Subject: LOGSEM Workshop in B'ham Date: Thu, 29 Aug 1996 17:02:30 +0100 From: Valeria DePaiva LOGSEM Workshop Logic and Semantics of Programming Languages September 13 - 16, 1996 School of Computer Science The University of Birmingham !!!!! CALL FOR PARTICIPATION !!!!! The researchers from the EU-funded projects Categorical Logic in Computer Science (CLiCS) I and II are holding a meeting dedicated to the theme "Logic and Semantics in Programming" at the School of Computer Science, University of Birmingham. Keynote speakers include Prof John Hughes (Chalmers, Sweden), Dr Jens Palsberg (to be confirmed), Prof E. Robinson (QMW, London), Dr A. Pitts (Computer Lab, Cambridge), Prof S. Abramsky (LFCS, Edinburgh) and Prof E. Moggi (Genova, Italy). The meeting is happenning over the weekend 13-16th September and talks are invited on the broad topics of mathematical structures in semantics, type systems for programming languages, logic and concurrency theory. We still have a few places available at University House, priced at 23.55 per night, just across the street from the campus. The meeting starts after lunch on Friday and finishes lunch time on Monday, so it is possible to travel on Friday and/or Monday. The registration DEADLINE is Monday, 2nd September, so please email us your registration form (with a short abstract, if you want to give a talk) before that. Best regards, Achim Jung and Valeria de Paiva ------------------------------------------------------------------------------ Valeria de Paiva, | University of Birmingham | Phone: +44 (0)121 414 4766 School of Computer Science | Fax: +44 (0)121 414 4281 Edgbaston, Birmingham | JANET: V.DePaiva@uk.ac.bham.cs B15 2TT, England, UK | Internet: V.DePaiva@cs.bham.ac.uk ------------------------------------------------------------------------------ REGISTRATION FORM ================= Name: ---- Affiliation: ----------- Do you want to give a talk? --------------------------- If yes, can we have a short abstract? Arrival: ------- Departure: --------- Shall we reserve a room for you in University House? (23.55 B&B): ---------------------------------------------------------------- Are you a vegetarian? -------------------- --------------------------------------------------------------------------- Date: Thu, 29 Aug 1996 17:30:36 -0300 (ADT) Subject: Submit exceptional papers to JACM Date: Wed, 28 Aug 1996 12:14:51 -0700 From: John C. Mitchell JACM is the flagship technical journal of the ACM. As recent additions to the Editorial Board, we would like encourage the submission of first-rate papers in the areas of programming languages and logic in computer science, broadly construed. Although the purpose of this message is to encourage submissions, JACM still has a moderate backlog. Space constraints only allow for publication of 3-5 papers per year in each of the main areas of computer science. As a result, only a handful of the most exciting or innovative papers from conferences like LICS, POPL, ICFP and PLDI could be considered in any given year. Within these constraints, we would like to see JACM cover as many active research areas as possible. Submissions may be in the form of postscript files, sent to the Editor-in-Chief (see http://theory.lcs.mit.edu/~jacm/) or area editors by electronic mail. Paper submission is also possible. Robert Harper (rwh@cs.cmu.edu) John Mitchell (jcm@cs.stanford.edu) Date: Fri, 30 Aug 1996 09:18:08 -0300 (ADT) Subject: 2-Hilbert spaces Date: Thu, 29 Aug 1996 15:31:14 -0700 (PDT) From: john baez Here is the abstract of a paper I wrote: Higher-Dimensional Algebra II: 2-Hilbert Spaces A 2-Hilbert space is a category with structures and properties analogous to those of a Hilbert space. More precisely, we define a 2-Hilbert space to be an abelian category enriched over Hilb with a *-structure, conjugate-linear on the hom-sets, satisfying = = . We also define monoidal, braided monoidal, and symmetric monoidal versions of 2-Hilbert spaces, which we call 2-H*-algebras, braided 2-H*-algebras, and symmetric 2-H*-algebras, and we describe the relation between these and tangles in 2, 3, and 4 dimensions, respectively. We prove a generalized Doplicher-Roberts theorem stating that every symmetric 2-H*-algebra is equivalent to the category Rep(G) of continuous unitary finite-dimensional representations of some compact supergroupoid G. The equivalence is given by a categorified version of the Gelfand transform; we also construct a categorified version of the Fourier transform when G is a compact abelian group. Finally, we characterize Rep(G) by its universal properties when G is a compact classical group. For example, Rep(U(n)) is the free connected symmetric 2-H*-algebra on one even object of dimension n. This paper is long and contains pictures and diagrams, so I have made a compressed Postscript file of it available at http://math.ucr.edu/home/baez/2hilb.ps.Z It is also available by anonymous ftp to math.ucr.edu, where it is the file 2hilb.ps.Z in the directory pub/baez. On UNIX systems, at least, one can download it and then uncompress it by typing uncompress 2hilb.ps.Z If any of this presents a problem, email your address to baez@math.ucr.edu and I can send you hardcopy. I look forward to comments, criticisms, and corrections. Date: Fri, 30 Aug 1996 13:54:02 -0300 (ADT) Subject: CFP - CTCS'97 conference Date: Fri, 30 Aug 1996 17:00:08 +0200 From: Eugenio Moggi CATEGORY THEORY AND COMPUTER SCIENCE (CTCS'97) 4-6 SEPTEMBER 1997, S. MARGHERITA LIGURE (GENOA), ITALY URL: "http://www.disi.unige.it/conferences/ctcs97/" PRELIMINARY ANNOUNCEMENT AND CALL FOR PAPERS The seventh biennial conference on Category Theory and Computer Science is to be held in Santa Margherita Ligure in 1997. Previous meetings have been held in Guildford, Edinburgh, Manchester, Paris, Amsterdam and Cambridge. SCOPE. The purpose of the conference series is the advancement of the foundations of computing using the tools of category theory, algebra, geometry and logic. Whilst the emphasis is upon applications of category theory, it is recognized that the area is highly interdisciplinary and the organizing committee welcomes submissions in related areas. Topics central to the conference include: * Models of computation * Program logics and specification * Type theory and its semantics * Domain theory * Linear logic and its applications * Categorical programming Submissions purely on category theory are also acceptable as long as the applicability to computing is evident. It is anticipated that the proceedings will be published in the LNCS series. IMPORTANT DATES: - 15 Feb 1997, soft deadline for notification of intention - 01 Mar 1997, deadline for submissions - 01 May 1997, notification of acceptance/rejection - 15 Jun 1997, deadline for final version ORGANIZING AND PROGRAMME COMMITTEE: S. Abramsky (UK) P.-L. Curien (France), P. Dybjer (Sweden), P. Johnstone (UK), G. Longo (France), G. Mints (USA), J. Mitchell (USA), E. Moggi (Italy), A. Pitts (UK), A. Poigne (Germany), G. Rosolini (Italy), D. Rydeheard (UK), F-J. de Vries (Japan). PRELIMINARY LIST OF INVITED SPEAKERS: J. Baez, Univ. of California at Riverside (USA) R. Bird, Oxford Univ. (UK) B. Jay, Univ. of Technology Sydney (Australia) ELECTRONIC SUBMISSION GUIDELINES * Papers must describe original unpublished research, be written and presented in English, they must not exceed 20 pages nor be submitted for publication elsewhere. * papers should be sent by email to ctcs97@disi.unige.it in postscript format, with a separate text message containing: title, authors, abstract, keywords, and address of corresponding author. * Alternative methods of submission might be accepted, but should be agreed in advance with ctcs97@disi.unige.it. FURTHER INFORMATION is available from the conference URL. Information on local arrangements is still preliminary, and will be finalized in May 1997, at the time of the call for participation. -- Eugenio Moggi Date: Fri, 30 Aug 1996 13:57:09 -0300 (ADT) Subject: Re: terminology Date: Fri, 30 Aug 1996 12:08:55 -0400 (EDT) From: F William Lawvere The following is an improved version of the text sent Thurs. Any suggestions for further improvements will be welcome . Note that the distinction between the objective extensive and the objective intensive is essentially "sampling/sorting" distinction discussed in Conceptual Mathematics. Bill The term EXTENSIVE was applied to certain categories in 1991 by Carboni, Lawvere, and Walters on the basis of the following considerations. For centuries, mathematical philosophy has distinguished between extensive quantities and intensive quantities, for example in thermodynamics of inhomogeneous bodies, volume, mass, energy, and entropy on the one hand are distinguished from pressure, density, temperature on the other. Lawvere in 1982 (SLNM 1174) and in 1990 (Categories of Space and of Quantity) had proposed to explain these as modes of variation of quantity. Quantities vary over a domain of variation in both cases. ( A domain of variation is a "space" , which in turn is an object in a category of space, which will be rather more determinate than "category" in general). An extensive quantity type is a covariant functor from a category of space, preserving finite coproducts, to a linear category (= one in which coproducts and products coincide). A distribution, a measure, a current, a homology class on a sum domain is given by a tuple of such , one on each summand ; thus all these are elements of extensive quantity types. An intensive quantity type is a contravariant functor from a category of space which also takes coproducts to products ; but more: intensive quantities usually act linearly on extensive quantities, lending them (not only a linear but also a) multiplicative structure which is also preserved by the contravariant functorality. For example, functions act as densities on distributions and measures, similarly differential forms act on currents, and cohomology classes act on homology classes. Often intensive quantity types are representable and related extensive types are definable as linear duals ( Riesz, Pontrjagin, Eilenberg- Mac Lane etc),but these are not the only possibilities. A fundamental example of a linear "category" is the 2-category of all categories with coproducts; it has an obvious abstraction functor to the linear category of commutative monoids, by taking isomorphism- classes. Part of the idea of K-theory and of K-homology and of the "non-linear K-theory" which I with Schanuel and others have been pursuing under the name of "objective number theory" is that it is useful to "objectify" quantities by lifting their type across this abstraction functor. The most fundamental measure of a thing is the thing itself. But measures can be pushed-forward ( a common colloquial expression for the covariant functorality of extensive quantity).However pullback is more familiar (already in 1844 Grassmann complained that intensives were more familiar than Ausdehnungen) : On any category with pullbacks, there is the contravariant functor to cat which takes the "slice" categories of each object.This functor is commonly viewed as consisting of "functions", namely functions whose values are the fibers. Indeed if the category satisfies suitable conditions , this will be an intensive quantity type. But what extensives will it act on ? On any category at all the slice categories constitute an even simpler COVARIANT cat-valued functor, simply composing the transforming map following the structural map to define the new structural map. It is often appropriate to consider that the structural map distributes the total in the base ( though distributions usually do not have values at points, they do often have totals ) and that the mentioned composing pushes the distribution forward. Indeed if the category has coproducts, this naive pushing forward is automatically linear.( But even though the slice categories have terminal objects, these are not preserved by the relevant extensive functorality.) THUS A CATEGORY WITH COPRODUCTS DEFINES AN EXTENSIVE QUANTITY TYPE ON ITSELF IF AND ONLY IF IT IS AN EXTENSIVE CATEGORY. If we call lextensive any extensive category with (finite) limits, then also by pullback, the intensives act on the extensives in a way that satisfies all reasonable functoralities, including the crucial CCR or "projection formula". More exactly, note that there will typically be lots of subcategories of such a "category of space" which are extensive but do not themselves have products or even a terminal object ; it suffices to be closed under sums and summands. Namely the empty space together with all spaces of dimension exactly 7. Any such subcategory A defines the extensive quantity type "distributions of A-dimensional spaces " in each base space X, namely the subslice category. Given A and B two extensive subcategories, there is an objective intensive quantity type which acts roughly as " B-A dimensional cohomology" namely for any X consider the category of all those spaces over X such that for any space over X whose total is in A, the pullback has total in B ; this pulls back along any change of X. Of course many extensive subcategories of a (lextensive) category of space will have products, for example (as Joyal pointed out to me in 1984) if A=B is the "compact" objects , thus defining the extensive notion of distributing a compact object in a base space, the corresponding intensive quantities which act on these are the PROPER fiberings.