November 1991 - Categories - categories.org.au

Two-sided proof nets with units
by rags＠triples.Math.McGill.CA 29 Nov '91

29 Nov '91

We wish to announce the following preprint: The logic of weakly distributive categories I: Two sided proof nets with units R. Blute R.A.G. Seely Abstract We define a two sided notion of proof nets, suitable for logics, like the logic of weakly distributive categories, which have the two-tensor structure (with/par) of linear logic, but lack a negation operator. These proof nets have a structure more closely parallel to that of traditional natural deduction than Girard's one-sided nets do. In particular, there is no cut, and cut elimination is replaced by normalization. We prove a sequentialisation theorem for these nets and the corresponding sequent calculus, and deduce the coherence theorem for weakly distributive categories as an application. We extend these techniques to cover the case of non symmetric tensors ("planar logic"). One significant feature of this version of proof nets is that we are able to include the units for the tensors in our presentation. With this, we are able to extend these nets to the full case of multiplicative linear logic (with units), and prove sequentialisation there. This represents an improvement over the treatment via one sided nets, which cannot handle the units successfully. ==================================================== The preprint may be obtained by anonymous ftp from triples.Math.McGill.CA (132.206.150.30) in the usual manner, or by contacting one of the authors. Via ftp: Login as anonymous, use your email ID as password. The various files are located in the directory pub/rags/nets You will find a PostScript file, a DVI file, and the TeX source code. If you want to take the TeX source code, read the nets.README file first, to find out what macro files are also necessary. (And for other instructions.) At the moment only the extended abstract will be found in this ftp directory; shortly the full paper (including other results, such as conservativity of the extension from weakly distributive categories to *-autonomous categories, in the unit-free case,) will be placed there as well. If you wish to be notified of such "upgrades", drop one of us a line. (Or just browse, from time to time.) Authors' address: Department of Mathematics McGill University 805 Sherbrooke St. W. Montreal Quebec H3A 2K6 Canada FAX: (514) 398-3899 Phone: (514) 398-3804 Authors' email addresses: Blute: blute(a)triples.math.mcgill.ca Seely: rags(a)triples.math.mcgill.ca

1 0

Union Conference
by NIEFIELD, SUSAN 23 Nov '91

23 Nov '91

UNION COLLEGE MATHEMATICS CONFERENCE Saturday and Sunday Schenectady April 25-26, 1992 New York KEYNOTE SPEAKER John Milnor This is a preliminary announcement of the eighth occasional Union College Mathematics Conference. This year the conference topics are category theory, dynamical systems, and number theory. The dynamical systems session will be directed towards complex dynamics and chaos. In addition to the keynote lecture, of interest to the entire Conference audience, there will also be shorter contributed talks in parallel sessions. Anyone interested in giving such a talk should contact one of the organizers. The meeting will begin with a reception from 9:00pm to 11:30pm on Friday, 24 April, and end on Sunday afternoon. A more detailed notice (including registration and hotel information) will be mailed in January. Organizers Category Theory Susan Niefield NiefielS(a)Union.Bitnet NiefielSGar.Union.Edu Kimmo Rosenthal RosenthK(a)Union.Bitnet RosenthK(a)Gar.Union.Edu Number Theory William F. Hammond (SUNY Albany) Hammond(a)Leah.Albany.Edu Karl Zimmermann ZimmermK(a)Union.Bitnet ZimmermK(a)Gar.Union.Edu Dynamical Systems Michael Frame FrameM(a)Union.Bitnet FrameM(a)Gar.Union.Edu Department of Mathematics Union College Schenectady, New York 12308-2311 Telephone (518) 370-6426 FAX (518) 370-6789 =============================

1 0

Are there French words for locales and frames
by curien＠FRULM63.BITNET 20 Nov '91

20 Nov '91

I wonder whether a terminology exists in French for the kind of stuff in Johnstone's book Stone Spaces. In particular: locales and frames. Due to the French speaking Canadian category theorist at least, the question must have arisen at some stage. Thanks to anyone for help in this matter. ============================

4 3

None
by Fred E.J. Linton 18 Nov '91

18 Nov '91

I believe Ehresmann (and some of his school) used "treillis local[e]" (sorry, I've lost the gender of "treillis" :-( ) for what Dowker and his followers later called "frame". You can see then how the English term "locale" might have arisen, from either a misinterpretation of (or, more generously, a simple borrowing from) the French. -- Fred ======================

1 0

None
by barr＠triples.Math.McGill.CA 17 Nov '91

17 Nov '91

It is called, ``Numbers can be just what they have to''. It appears to be a preprint and done, unfortunately, on a typewriter. I have written to Charles asking him to ask Colin if he wants to post it, but Colin, in a Philosophy Dept, isn't into computers and almost certainly doesn't have in computer readable form. You can of course write him at Dept of Philosophy, Case Western, Cleveland, OH USA 44106. There is something I would like to add. I got one query from someone who didn't believe that it was possible to use categories or toposes as a foundation because a category has a set of objects and a set of morphisms (or a class, but that's not the issue here) and you cannot talk about the domain or codomain functions and the rest of the structure unless you have some underlying set. Right? No! You have no more need (or exactly the same need) to have an underlying set as you do when axiomatizing sets. If you need to have a set to talk about a function, then you need a set to talk about the membership relation. In both cases, it would be nice to have a set; it puts us on familiar territory, but when founding mathematics you have to start somewhere. It is as legitimate to start with a pre-existing notion of morphism, domain, codomain and so on as with a pre-existing notion of set and membership. Are your intuitions well-founded? How do I know? I think mine are, but I cannot prove it to my satisfaction, let alone prove that yours are. That's the way it is with foundations. Michael ++++++++++++++++++++++++++++++++

1 0

None
by James Stasheff 16 Nov '91

16 Nov '91

thanks one of the delights is the current rage of applications of category theory to mathematical physics - of all things!! but it's particularly crucial there to emphasize the useful and not be too pedantic about max generality anybody there interested in the relevant physics Patera et al are one step removed =======================

1 0

We've been shafted again
by barr＠triples.Math.McGill.CA 16 Nov '91

16 Nov '91

By we I mean the world of category theorists. Twice, I have tried to publish something on categories in the so-called Mathematical Intelligencer. Not that it's relevant, but earlier this year they published an article on the philosophy of mathematics by such an ignoramus that he didn't know the difference between the axiom of choice and the axiom of pairs. The most recent one contains an article by Barwise on non-well-founded set theory. Barwise has discovered that there are no non-trivial solutions to domain equations (the one he is looking at is S = N x S, where N is the natural numbers and he really means equals) in WF set theory, because it is clear that a set satisfying it and WF could only be empty. (Although he doesn't mention it, for such an equation as S = 1 + S, there's no solution at all.) Of course, these equations are important in computer science and something has to be done etc, etc. And what does he propose? Rather than accepting what is staring him in the face, that set theory founded on the epsilon relation is irrelevant to the workings of virtually the entire world of mathematics, he proposes to compound the felony by taking as mathematical foundations Aczel's theory of NWF sets. Consider that probably not one mathematician in ten could give a coherent account of ZF axioms. Have you ever seen a complex analyst begin a paper by saying if his complex numbers are ordered pairs of reals or 2 x 2 matrices with certain properties (and what are the elements of the matrix ring anyway?) or equivalences classes of R[x] mod (x^2 + 1) or ... ? Of course not. And there is no problem with domain equations in a categorical framework. Nor for that matter, with what Barwise calls the largest solution, by which he apparently means the terminal one. Peter Freyd once asked how you know that the largest sporadic simple group isn't the smallest counter-example to the Riemann Hypothesis. Actually, I suspect that for all the constructions of the complex numbers I know of, that cannot happen. But the very answer points up the irrelevance of the elements of a set. Certainly not very many mathematicians could give you the categorical axioms for sets either. The difference is that if you explained to him the categorical axioms, he would recognize in them constructions he uses daily. It is the categorical notion of subobject that is used when she considers the integers as a subset of the rationals, the rationals of the reals and the reals of the complexes. On the other hand, it now appears that Barwise is proposing to move set theory even further from practice by introducing an even more complicated set of axioms with the anti-foundation axiom that Aczel has introduced. I can only hope that someone with enough prestige that the Intelligencer might feel constrained to accept it would write a paper pointing out these things and suggesting that the topos-based axioms (which can be easily described) lead to a much simpler and more natural approach to the same thing. As for me, I've decided to drop my subscription. They have irritated me just once too often. Michael ===================================

4 5

FTP archive at Imperial etc
by Paul Taylor 15 Nov '91

15 Nov '91

Public FTP archive at Imperial College, London The Theory and Formal Methods section of the Department of Computing in Imperial College, London, now has a public FTP archive for its papers. You can access this by the fairly memorable ftp theory.doc.ic.ac.uk and then log in using the name "anonymous" or "ftp" and your email address as password. The IP address is currently 129.31.81.37 but is going to change shortly, so please note the name (which cost a three month fight within the department!), not the number. Papers, in various formats (DVI, LaTeX source, PostScript, RTF, ASCII), are in the directory /theory/papers/... where the next subdirectory is the surname of the author. For example, /theory/papers/Abramsky/cill.dvi.Z is the compressed DVI of Samson Abramsky's "Computational Interpretation of Linear Logic". There isn't a great deal of stuff there at the moment, but hopefully it will expand. It is intended to include papers from the CLiCS (Categorical Logic in Computer Science: European Community Basic Research Action 3003) project as well as local ones. If you believe one of us has written a paper but you cannot find it in the archive, please send email to the author (not me); in most cases the email address consists of the initials with @doc.ic.ac.uk. There is also a directory /theory/software, which contains some tex bits (including my commutative diagrams) and wp (Mark Dawson's omega Prolog). Finally, you can write to /theory/tmp (within reason!). ============================================================================= Since I'm here: Perhaps other sites who have FTP archives of theoretical computer science and category theory papers would declare themselves for future reference. On-line bibliographies and address lists, too. Also: My commutative diagrams package (/theory/software/tex/diagrams.tex) hasn't changed much since July 1990, but when I have time (one day) I intend to overhaul it, fix some bugs and incorporate some features people have suggested. Please would those who have acquired the package indirectly, or passed it on to others, advise me so as to ensure that you get the new version when it becomes available (NOT YET!). Bugs and suggestions are also welcome. Paul Taylor <pt(a)doc.ic.ac.uk> Dept of Computing, Imperial College, London SW7 2BZ, UK +44 71 589 5111 x 5057 ===================================

1 1

None
by James Stasheff 14 Nov '91

14 Nov '91

To Michael Barr Yes, but... Elements are occassionally useful. Avoiding them entirely is like insisting on writing po russki without the `Cyrillic' alphabet. And then there are those of us who don't speak the categorical dialect fluently. jim =================================

1 0

NNO
by barr＠triples.Math.McGill.CA 13 Nov '91

13 Nov '91

I went too far when I said in my recent flame that there was no solution to 1 + X = X in standard set theory. If we take 1 = {0}, where 0 is the empty set and take A + B = A x {0} u B x {1}, then the set {(0,0), (0,0,1), (0,0,1,1), (0,0,1,1,1), ... } satisfies it on the nose, where I use (a,b,c,d,...) for the left associated ((...(a,b),c),d),e),...). I guess typical covariant domain equations have initial solutions, but not final ones in standard set theory. Thanks to Bob Tennent for pointing this out. Note that this is not the Von Neumann NNO. Michael ++++++++++++++++++++++++ Apologies to Mike for sending this late - it got lost temporarily in the shuffle of mailer problems. Bob Rosebrugh ===========================

1 0