Date: Mon, 20 Jun 1994 18:43:23 +0500 (GMT+4:00) From: categories Subject: Topology: a geometric account of general topology, homotopy types and t he fundamental groupoid, published 1988, by Ronald Brown Date: Mon, 20 Jun 1994 14:28:33 +0100 From: "Prof R. Brown" The publishers have just informed informed me that the above book has been out of print since sept, 1993, that no stock is available, and that the copyright reverts to me. I would consider getting some loose page copies printed and sold if this seemed economic, and/or if for example there was a desire to use part or all for course adoption. For the latter I could supply a top copy and allow for copying to students at a moderate fee per student. Offers welcomed. The aim is to get the book available and read. The publisher's previous distribution at 50 pounds sterling discouraged this. This book has material on groupoids, homotopy types, fundamental groupoid of orbit spaces, etc. not available elsewhere. Ronnie Brown Prof R. Brown Tel: +44 248 382474 School of Mathematics Fax: +44 248 355881 Dean St email: mas010@uk.ac.bangor University of Wales Bangor Gwynedd LL57 1UT UK Date: Fri, 17 Jun 1994 13:59:52 +0500 (GMT+4:00) From: categories Subject: ANNOUNCE: Kock-Moerdijk preprint Date: Fri, 17 Jun 1994 08:40:31 +0200 From: kock@mi.aau.dk Preprint "Spaces with local equivalence relations, and their monodromy" available. The final version of Kock and Moerdijk's work on this topic is now available by ftp at theory.doc.ic.ac.uk (login: anonymous, directory: papers/Kock, file: km-ler.dvi). Compared to the 1991 preprint, it has more emphasis on topology, less on toposes (the topos theoretic aspects are dealt with in our article published in JPAA 82 (1992)). A paper version (Aarhus Preprint 1994 No. 8) is also available, on request. Date: Wed, 22 Jun 1994 22:36:48 +0500 (GMT+4:00) From: categories Subject: in case you hadn't heard Date: Tue, 21 Jun 94 11:51:50 -0400 From: jds@math.upenn.edu available on the hep-th list server is a paper by V. Lychagin Calculus and quantizations over Hopf algebras hep-th 9406097 It includes ``a general notion of quantization in monoidal cats'' which `deforms all natural algebraic and differential objects''. This occurs in Section 3 p. 31 + so skim rapidly if this is the part that interests you. [Note from moderator: th poster provided the following information on accessing hep-th server] This bulletin board for string/conformal field theory/2d gravity preprints, hepth@xxx.lanl.gov, described in an earlier message is now turned on. For the first week or so, replies to messages received during the day will be sent out only during the evening (so that potential bugs can be identified and corrected under actual combat conditions). A (subscribe all / cancel all) option has been added that allows automatic receipt of the full text of each paper on day of receipt. This is recommended only for large groups where a single such account could be used for general distribution or posting in a preprint library. Commands to the system, entered in the Subject: field of messages, are get # returns to requester the paper specified by # put submit paper (body of message in format described below*) paper is assigned #, and added to listing replace # replace paper specified by # with revised version (only original submitter can do this). listing returns title/author list of all papers currently held find (keyword) search title/author list for keyword (either authorname or word in title) to recall # subscribe add new username to distribution list (email address automatically extracted from return address) cancel remove username from distribution list subscribe all automatically receive full text of all papers cancel all return to receipt only of authors/titles/abstracts distribution returns full list of email addresses on distribution list comment forwards mail message for human perusal help returns this list of commands Date: Thu, 23 Jun 1994 14:21:29 +0500 (GMT+4:00) From: categories Subject: Domain Theory and Partial Maps Date: Thu, 23 Jun 1994 17:47:33 +0000 From: Marcelo Fiore My thesis (Axiomatic Domain Theory in Categories of Partial Maps) is available by anonymous ftp from ftp.dcs.ed.ac.uk directory pub/mf files thesis.dvi.Z and thesis.ps.Z. Marcelo Fiore P.S. The abstract follows: ------------------------------------------------------------------------ Axiomatic Domain Theory in Categories of Partial Maps Marcelo P. Fiore Department of Computer Science Laboratory for Foundations of Computer Science University of Edinburgh, The King's Buildings Edinburgh EH9 3JZ, Scotland Phone: + 44 31 650 5145. Fax: + 44 31 667 7209. June 1994 Synopsis This thesis is an investigation into axiomatic categorical domain theory as needed for the denotational semantics of deterministic programming languages. To provide a direct semantic treatment of non-terminating computations, we make partiality the core of our theory. Thus, we focus on categories of partial maps. We study representability of partial maps and show its equivalence with classifiability. We observe that, once partiality is taken as primitive, a notion of approximation may be derived. In fact, two notions of approximation, contextual approximation and specialisation, based on testing and observing partial maps are considered and shown to coincide. Further we characterise when the approximation relation between partial maps is domain-theoretic in the (technical) sense that the category of partial maps Cpo-enriches with respect to it. Concerning the semantics of type constructors in categories of partial maps, we present a characterisation of colimits of diagrams of total maps; study order-enriched partial cartesian closure; and provide conditions to guarantee the existence of the limits needed to solve recursive type equations. Concerning the semantics of recursive types, we motivate the study of enriched algebraic compactness and make it the central concept when interpreting recursive types. We establish the fundamental property of algebraically compact categories, namely that recursive types on them admit canonical interpretations, and show that in algebraically compact categories recursive types reduce to inductive types. Special attention is paid to Cpo-algebraic compactness, leading to the identification of a 2-category of kinds with very strong closure properties. As an application of the theory developed, enriched categorical models of the metalanguage FPC (a type theory with sums, products, exponentials and recursive types) are defined and two abstract examples of models, including domain-theoretic models, are axiomatised. Further, FPC is considered as a programming language with a call-by-value operational semantics and a denotational semantics defined on top of a categorical model. Operational and denotational semantics are related via a computational soundness result. The interpretation of FPC expressions in domain-theoretic Poset-models is observed to be representation-independent. And, to culminate, a computational adequacy result for an axiomatisation of absolute non-trivial domain-theoretic models is proved. ------------------------------------------------------------------------ Date: Thu, 7 Jul 1994 11:24:29 +0500 (GMT+4:00) From: categories Subject: Revised version of Acyclic models Date: Thu, 7 Jul 94 09:02:39 EDT From: Michael Barr A totally revised version of Acyclic models is now available for ftp on my directory on triples. .tex, .dvi and .ps versions are there. Michael Date: Thu, 7 Jul 1994 21:53:53 +0500 (GMT+4:00) From: categories Subject: Re: Empty types and typed lambda calculus To: categories Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO Date: Thu, 07 Jul 94 09:37:26 -0700 From: "John C. Mitchell" We looked into this kind of thing about seven or eight years ago. See @inproceedings( mmms87, author="A. R. Meyer and J. C. Mitchell and E. Moggi and R. Statman", Key="MMMS 87", Title="Empty types in polymorphic lambda calculus", Booktitle="Proc. 14th ACM Symp. on Principles of Programming Languages", Month="January",Year="1987", pages="253-262", Note="Reprinted with minor revisions in {\it Logical Foundations of Functional Programming,} ed. G. Huet, Addison-Wesley (1990) 273--284.") @article( mm87, author="Mitchell, J.C. and Moggi, E.", Title="Kripke-style models for typed lambda calculus", Journal="Ann. Pure and Applied Logic", Volume="51",Year="1991", pages="99--124", Note="Preliminary version in {\it Proc. IEEE Symp. on Logic in Computer Science,} 1987, pages 303--314.") @incollection( MitchScott,Author="Mitchell, J.C. and Scott, P.J.", Title="Typed lambda calculus and cartesian closed categories", Booktitle="Categories in Computer Science and Logic, Proc. Summer Research Conference, Boulder, Colorado, June, 1987", Series="Contemporary Mathematics", volume="92", publisher="Amer. Math. Society", editors="J.W. Gray and A. Scedrov", Year="1989", pages="301-316") Friedman's completeness theorem is completeness of beta,eta for full classical model (i.e., Set). Deductive completeness fails for Set and for models (interpretations into categories) where every type (every object named by a type expression) is required to be non-empty (have a global element). I tried to clarify this in my book (still to appear). If anyone is seriously interested, I could email the appropriate sections of the book. John Mitchell te: Tue, 19 Jul 1994 13:38:12 +0500 (GMT+4:00) From: categories Subject: Re: Anouncement of Preprints Date: Tue, 19 Jul 1994 16:33:59 +1000 From: Murray Adelman I have mounted four papers by John Corbett and myself that attempt to use sheaf theory to interpret Quantum Logic (or our version thereof) on the Sydney University ftp site. They are called Adelman-Corbett.ps ---Long with a lot of expository material for physicists. comparison.ps---Attempts to compare Birkhoff and vonNeumann Quantum logic to the internal logic of the category of sheaves over state space newpaper.ps--- Attempts to show how continuous data can become discrete data via the global sections functor heidelberg.ps---Derives a formula for interference of particles that allows more of the configuration of the experiment to be parametrized than the usual Hilbert Space description. The union of heidelberg.ps and comparison.ps approximates (and perhaps supersedes) Adelman-Corbett.ps which is somewhat older. They can be obtained by anonymous ftp from maths.su.oz.au in the directory sydcat/papers/murray Regards, Murray Date: Tue, 26 Jul 1994 09:09:33 +0500 (GMT+4:00) From: categories Subject: New edition of "Category Theory for Computing Science" Date: Mon, 25 Jul 1994 14:13:54 -0400 From: "Charles F. Wells" We are revising our text, "Category Theory for Computing Science", for its second edition. We would appreciate any comments or suggestions concerning this revision, including papers and books we should refer to, new topics we should include, and topics we could delete. Please reply to either of us. Michael Barr Charles Wells barr@triples.math.mcgill.ca cfw2@po.cwru.edu -- Charles Wells, Department of Mathematics, Case Western Reserve University 10900 Euclid Avenue, Cleveland OH 44106-7058, USA Phone 216 368 2880 or 216 774 1926 FAX 216 368 5163 Date: Tue, 26 Jul 1994 09:14:44 +0500 (GMT+4:00) From: categories Subject: Papers Date: Sat, 23 Jul 1994 11:53:22 +1000 From: Murray Adelman There seems to be some problem obtaining the papers that I announced a few days ago. I have put them in a second location ftp.mpce.mq.edu.au in the directory /pub/maths/murray (This is more patriotic, as it is the Macquarie University server instead of the Sydney University server :-) Sorry for the inconvenience. Murray From schreine Mon Aug 29 20:54 MDT 1994 Received: from admin.risc.uni-linz.ac.at by melmac.risc.uni-linz.ac.at with SMTP id AA19148 (Sendmail 5.65c/IDA-1.4.4 for ); Mon, 29 Aug 1994 20:54:21 +0200 Received: from nimble.mta.ca by admin.risc.uni-linz.ac.at with SMTP id AA11570 (5.65c/IDA-1.4.4 for ); Mon, 29 Aug 1994 20:54:13 +0200 Received: by nimble.mta.ca (5.65/DEC-Ultrix/4.3) id AA12175; Mon, 29 Aug 1994 15:35:16 +0500 Date: Mon, 29 Aug 1994 15:34:59 +0500 (GMT+4:00) From: categories Subject: Top\op is a quasi-variety To: categories Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO Date: Sat, 27 Aug 94 14:47:11 EDT From: Michael Barr by Michael Barr and M. Cristina Pedicchio We show that there is a certain variety (= category tripleable over sets) and a simple Horn sentence in it of the form phi(u) = phi(v) ==> psi(u) = psi(v) whose category of models is equivalent to the opposite of topological spaces. The theory consists of that of frames together with a unary operation we denote ' (it is a kind of pseudocomplement) satisfying a small set of equations plus an equation scheme that forces all intervals of the form [u /\ u',u \/ u'] to be complete atomic boolean algebras with the Sup and ' as operations. The underlying set functor on Top\op takes a space to the set of all pairs (U,A) where U is open and A is an arbitrary subset of U. The frame operations are the usual, while (U,A)' = (U,U - A). The Horn clause is u \/ u' \/ 1' = v \/ v' \/ 1' ==> u \/ u' = v \/ v'. [note from moderator: Michael says the paper will be available by ftp from triples.math.mcgill.ca soon.] Date: Sat, 10 Sep 1994 22:54:25 +0500 (GMT+4:00) From: categories Subject: "Homotopical algebra and triangulated categories" Date: Thu, 8 Sep 1994 09:35:25 +0200 From: Marco Grandis The following preprint is available (by hard mail) Marco Grandis, "Homotopical algebra and triangulated categories" to appear in: Math. Proc. Cambridge Philos. Soc. Abstract We study here the connections between the well known Puppe-Verdier notion of triangulated category and an abstract setting for homotopical algebra, based on homotopy kernels and cokernels, which was exposed by the author in two previous papers ["On the categorical foundations of homological and homotopical algebra", Cahiers Top. Geom. Diff. Categ. 33 (1992), 135-175. "Homotopical algebra in homotopical categories", Appl. Categ. Struct., to appear]. We show that a right-homotopical category A (having well-behaved homotopy cokernels, i.e. mapping cones) has a sort of weak triangulated structure with regard to the suspension endofunctor Sigma, called Sigma-homotopical category. If A is right- and left-homotopical and h-stable (in a sense related to the suspension-loop adjunction), also this structure is h-stable, i.e. satisfies "up to homotopy" the axioms of Verdier for a triangulated category, excepting the octahedral one which depends on some further elementary conditions on the cone endofunctor of A. Every Sigma-homotopical category can be stabilised, by two universal procedures, respectively initial and terminal. Date: Tue, 11 Oct 1994 08:59:49 +0500 (GMT+4:00) From: categories Subject: Graph-based Logic and Sketches Date: 7 Oct 1994 19:30:41 GMT From: Charles Wells "Graph-based Logic and Sketches I: The General Framework" by Atish Bagchi and Charles Wells is now available by anonymous FTP from ftp.cwru.edu in the directory math/wells. It is also available by gopher at gopher.cwru.edu, path 1/class/mans/math/pub/wells. In either case the files are logstr.dvi and logstr.ps. To print the dvi file requires AMS fraktur and the 1992 version of the xypic fonts. -- Charles Wells Department of Mathematics, Case Western Reserve University 10900 Euclid Avenue, Cleveland, OH 44106-7058, USA 216 368 2893 Date: Fri, 14 Oct 1994 18:57:05 +0500 (GMT+4:00) From: categories Subject: Lambda Definability in Categorical Models Date: Tue, 11 Oct 1994 18:02:14 -0400 From: Andre Scedrov A Characterization of Lambda Definability in Categorical Models of Implicit Polymorphism Moez Alimohamed University of Pennsylvania This paper contains the work of Moez Alimohamed, a mathematics graduate student at the University of Pennsylvania who died tragically on August 29th. Lambda definability is characterized in categorical models of simply typed lambda calculus with type variables. A category-theoretic framework known as glueing or sconing is used to extend the Jung-Tiuryn characterization of lambda definability in Henkin models for the simply typed lambda calculus first to ccc models, and then to categorical models of the calculus with type variables. WWW access is http://www.cis.upenn.edu/~andre/moez.html. The paper is also available by anonymous ftp from the host ftp.cis.upenn.edu as the file pub/papers/scedrov/def.ps.Z. te: Wed, 9 Nov 1994 15:53:25 +0400 (GMT+4:00) From: categories Subject: New papers available by gopher & ftp Date: 8 Nov 1994 20:51:40 GMT From: Charles Wells Three papers are newly available by gopher and by anonymous ftp from Case Western Reserve University: "The categorical theory generated by a limit sketch", by Michael Barr and Charles Wells. This was formerly called "The category of diagrams". "Varieties of mathematical prose" by Atish Bagchi and Charles Wells. This is not about category theory but was referred to in our paper "The logic of sketches" (also available by gopher & ftp). "Extension theories for categories", by Charles Wells. This is an old paper that was never submitted for publication. I have updated the bibliography as far as I can, but would appreciate it if anyone knows of other suitable references. They are available by gopher in both DVI and Postscript form from the host gopher.cwru.edu, path 1/class/mans/math/pub/wells. Most www clients can get gopher files, and some of the can view Postscript files on screen. The files are also available by anonymous ftp from ftp.cwru.edu in the directory math/wells, under the following filenames: "Varieties of mathematical prose": MATHRITE.DVI, MATHRITE.PS "Extension theories for categories": CATEXT.DVI, CATEXT.PS "The categorical theory generated by a limit sketch": DIAGC.DVI, DIAGC.PS "The logic of sketches": LOGSTR.DVI, LOGSTR.PS I would appreciate knowing if anyone has problems downloading these files. -- Charles Wells Department of Mathematics, Case Western Reserve University 10900 Euclid Avenue, Cleveland, OH 44106-7058, USA 216 368 2893 Date: Thu, 10 Nov 1994 18:47:37 +0400 (GMT+4:00) From: categories Subject: Announce paper: Cockett & Seely Date: Wed, 9 Nov 94 22:38:25 EST From: "Robert A. G. Seely" The following paper has been placed on anonymous ftp at triples.math.mcgill.ca, directory /pub/rags/wk_dist_cat Weakly distributive categories by J.R.B. Cockett and R.A.G. Seely Abstract: There are many situations in logic, theoretical computer science, and category theory where two binary operations---one thought of as a (tensor) ``product'', the other a ``sum''---play a key role. In distributive and *-autonomous categories these operations can be regarded as, respectively, the and/or of traditional logic and the times/par of (multiplicative) linear logic. In the latter logic, however, the distributivity of product over sum is conspicuously absent: this paper studies a ``linearization'' of that distributivity which is present in both case. Furthermore, we show that this weak distributivity is precisely what is needed to model Gentzen's cut rule (in the absence of other structural rules) and can be strengthened in two natural ways to generate full distributivity and *-autonomous categories. This is the journal version of the similarly named paper appearing in the Proceedings of the Durham conference (1991): M.P. Fourman, P.T. Johnstone, A.M. Pitts, eds., Applications of Categories to Computer Science, London Mathematical Society Lecture Note Series 177 (1992) 45 - 65. This version is to appear in the Journal of Pure and Applied Algebra. The paper has been rewritten, including more details and several examples, including shifted tensors, Span categories, and categories of modules of a bialgebra. Date: Thu, 10 Nov 1994 18:50:26 +0400 (GMT+4:00) From: categories Subject: Announce paper: Mendler, Panangaden, Scott, & Seely Date: Wed, 9 Nov 94 22:40:42 EST From: "Robert A. G. Seely" The following paper has been placed on anonymous ftp at triples.math.mcgill.ca in directory (file) /pub/rags/ccp/mpss.* A Logical View of Concurrent Constraint Programming by Nax Paul Mendler Prakash Panangaden P.J. Scott R.A.G. Seely Abstract; The Concurrent Constraint Programming paradigm has been the subject of growing interest as the focus of a new paradigm for concurrent computation. Like logic programming it claims close relations to logic. In fact these languages _are_ logics in a certain sense that we make precise in this paper. In recent work it was shown that the denotational semantics of determinate concurrent constraint programming languages forms a categorical structure called a hyperdoctrine, which is used as the basis of the categorical formulation of first order logic. What this connection shows is the combinators of determinate concurrent constraint programming can be viewed as logical connectives. In the present work we extend these ideas to the operational semantics of these languages and thus make available similar analogies for a much broader variety of languages including the indeterminate concurrent constraint programming languages and concurrent block-structured imperative languages. \begin{BTW} In the same directory you will find the earlier paper dealing with the denotational semantics (psss*). This paper has appeared: P. Panangaden, V. Saraswat, P. J. Scott, R. A. G. Seely, A Hyperdoctrinal View of Concurrent Constraint Programming, in J.W. de Bakkee et al, eds. Semantics: Foundations and Applications; Proceedings of REX Workshop, Beekbergen, The Netherlands, June 1992. Springer Lecture Notes in Comp. Science, 666 (1993) pp. 457 -- 476. \end{BTW} Date: Thu, 10 Nov 1994 13:01:16 +0400 (GMT+4:00) From: categories Subject: cat logic of interactions Date: Wed, 9 Nov 1994 22:10:43 +0000 (GMT) From: Dusko Pavlovic I just remembered that I never announced this paper in which I was trying to learn some concurrency theory. It depends on a note on representation, that used to be its appendix. It will be available soon. The ps-file with A4-format is in papers/Pavlovic on theory.doc.ic.ac.uk; the American format is in pub/pavlovic on triples.math.mcgill.ca. All the best, -- Dusko CATEGORICAL LOGIC OF CONCURRENCY AND INTERACTION I: SYNCHRONOUS PROCESSES by Dusko Pavlovic (August 1994) Abstract. This is a report on a mathematician's effort to understand some concurrency theory. The starting point is a logical interpretation of Nielsen and Winskel's account of the basic models of concurrency. Upon the obtained logical structures, we build a calculus of relations which yields, when cut down by bisimulations, Abramsky's interaction category of synchronous processes. It seems that all interaction categories arise in this way. The obtained presentation uncovers some of their logical contents and perhaps sheds some more light on the original idea of processes as relations extended in time. The sequel of this paper will address the issues of asynchronicity, preemption, noninterleaving and linear logic in the same setting. Date: Tue, 15 Nov 1994 19:29:48 -0400 (AST) From: categories To: categories Subject: Announcement Date: Tue, 15 Nov 94 15:27:16 EST From: Michael Makkai This is to announce two papers, "Avoiding the axiom of choice in general category theory" and "Generalized sketches as a framework for completeness theorems" both by M. Makkai, McGill University. Both papers are revised versions of ones with identical titles; the original versions were produced about a year ago. Both papers will appear in the Journal of Pure and Applied Algebra. Unfortunately, they are not available electronically. If you are interested in obtaining copies, please send your request to Makkai@triples.math.mcgill.ca . The abstracts of the papers follow. ABSTRACT of "Avoiding the axiom of choice in general category theory", by M. Makkai, McGill University: "The notion of anafunctor is introduced. An anafunctor is, roughly, a "functor defined up to isomorphism". Anafunctors have a general theory paralleling that of ordinary functors; they have natural transformations, they form categories, they can be composed, etc. Anafunctors can be saturated, to ensure that any object isomorphic to a possible value of the anafunctor is also a possible value at the same argument object. The existence of anafunctors in situations when ordinarily one would use choice is ensured without choice; e.g., for a category which has binary products, but not specified binary products, the anaversion of the product functor is canonically definable, unlike the ordinary product functor that needs the axiom of choice. When the composition functors in a bicategory are changed into anafunctors, one obtains anabicategories. In the standard definitions of bicategories such as the monoidal category of modules over a ring, or the bicategory of spans in a category with pullbacks, and many others, one uses choice; the anaversions of these bicategories have canonical definitions. The overall effect is an elimination of the axiom of choice, and of non-canonical choices, in large parts of general category theory. To ensure the Cartesian closed character of the bicategory of small categories, with anafunctors as 1-cells, one uses a weak version of the axiom of choice, which is related to A. Blass' axiom of Small Violations of Choice ("Injectivity, projectivity, and the axiom of choice", Trans. Amer. Math. Soc. 255(1979), 31-59)." ABSTRACT of "Generalized sketches as a framework for completeness theorems", by M. Makkai, McGill University: "A generalized concept of sketch is introduced. Because of their role, morphisms of (generalized) sketches are called sketch-entailments. A sketch is said to satisfy a sketch-entailment if the former is injective relative to the latter in the standard sense; the models of a set R of sketch-entailments are the sketches satisfying all members of R . R logically implies a sketch-entailment s if every model of R is also a model of {s} . A deductive calculus is introduced in which s is deducible from R iff R logically implies s (General Completeness Theorem, GCT). A large number of examples of kinds of structured category is presented showing that the structured categories are selected from among the corresponding generalized sketches as the models of a set of sketch-entailments. As a consequence, the sketch-entailments satisfied by all structured categories of a given kind are exactly the ones that are deducible from a certain, usually finite, set of axioms. In the finitary case, which is the only one considered in detail in the paper, the notion of deduction is effective, and straightforwardly implementable on a computer. One obtains Specific Completeness Theorems (SCT's), each of which asserts that the exactness properties (certain kinds of sketch-entailments) that hold in a specific class of structured categories coincide with the ones that are deducible from a given set of axioms. Each of these specific completeness theorems is deduced from the GCT, and a particular Representation Theorem (RT); RT's are a well-known class of results in categorical logic. The concepts of Compactness and of Abstract Completeness are introduced, and shown to correspond to the same-named concepts in logics in the usual symbolic form, via a translation between the sketch-based syntax and semantics on the one hand, and the Tarskian syntax and semantics on the other. The sketch-based concepts are available for several logics defined categorically for which there are no available symbolic presentations." Date: Wed, 16 Nov 1994 18:47:19 -0400 (AST) From: categories To: categories Subject: Availability of new paper by ftp Date: Wed, 16 Nov 94 16:56:03 +1100 From: Max Kelly A new preprint "On localization and stabilization for factorization systems", by Carboni, Janelidze, Kelly, and Pare', is available in our ftp site at the address maths.su.oz.au (= 129.78.68.2), in the directory sydcat/papers/kelly, under the titles cjkp.dvi or cjkp.ps; there is also cjkp.tex, but that requires two macros - namely diagrams.tex and kluwer.sty. The paper contains new ideas, but also self-contained introductions to several areas with which some may be unfamiliar: namely factorization systems, descent theory, Galois theory, Eilenberg's monotone-light factorization for maps between compact hausdorff spaces, hereditary torsion theories for abelian categories, the category of finite families of objects of a given category, and the (separable, purely-inseparable) factorization for field extensions. What ways are there of constructing a factorization system (E, M) on a category C ? One simple one is to start with a full reflective subcategory X of C, and to take E to consist of the maps inverted by the reflexion. Of course, this (E, M) doesn't have E pullback-stable except in the special case where X is a LOCALIZATION of C. We examine another general process, which leads to an (E, M) with E stable when it succeeds. We start from ANY factorization system (E, M), and define new classes thus: a map lies in E' if EACH of its pullbacks lies in E; and it lies in M* if SOME pullback of it along an effective descent map lies in M. Note the connexion with Galois theory, in Janelidze's categorical formulation of it: if the (E, M) we begin with arises as above from a reflective full subcategory, the class M* consists of what Janelidze calls the COVERINGS (or, in some contexts, the CENTRAL EXTENSIONS). It is not always the case that (E', M*) is a factorization system; we give necessary and sufficient conditions for it to be so, and apply these to three major examples: Eilenberg's factorization above, certain factorizations connected to hereditary torsion theories, and a new factorization system for finite-dimensional algebras over a field that generalizes (separable, purely-inseparable) factorization for field extensions. Regards to all - Max Kelly. ps: For those without electronic access, a limited number of printed copies will shortly be available; please request them soon, so that we can alert the printer. Max Kelly. Date: Thu, 17 Nov 1994 10:18:13 -0400 (AST) From: categories To: categories Subject: The categorical theory generated by a limit sketch Date: Wed, 16 Nov 1994 15:20:51 -0500 From: Charles F. Wells About two weeks ago I announced the availability of a paper The categorical theory generated by a limit sketch by Michael Barr and Charles Wells by gopher from gopher.cwru.edu and by ftp from ftp.cwru.edu. I have discovered that the copy I posted was not the latest version. The latest version has now been posted. The differences are correction of a few minor errors plus some additional references. -- Charles Wells, Department of Mathematics, Case Western Reserve University 10900 Euclid Avenue, Cleveland OH 44106-7058, USA Phone 216 368 2880 or 216 774 1926 FAX 216 368 5163 Date: Thu, 17 Nov 1994 17:07:27 -0400 (AST) From: categories To: categories Subject: processes and irredundant trees Date: Thu, 17 Nov 1994 16:28:43 +0000 (GMT) From: Dusko Pavlovic The promised companion to the paper I announced last week is now available. The first version, which I gave to some people, actually CONTAINED AN ERROR --- so please download this version if you have an old copy. The file is CCPS.ps, and can be downloaded either from triples.math.mcgill.ca, or from theory.doc.ic.ac.uk. Regards, -- Dusko CONVENIENT CATEGORIES OF PROCESSES AND SIMULATIONS by Dusko Pavlovic Abstract. We show that irredundant trees, used by Dana Scott in the early sixties, can be used as canonical representants of the bisimilarity classes of automata (or of transition systems). Simulations then boil down to tree morphisms. Along the same lines, the categories of processes modulo the observational and the branching congruences, with the suitable simulations as morphisms again, are shown to be isomorphic with certain subcategories of the category of irredundant trees. Date: Mon, 12 Dec 1994 20:20:30 -0400 (AST) From: categories To: categories Subject: ftp announcement Date: Mon, 12 Dec 94 14:25:36 EST From: Michael Makkai Some weeks ago, I announced two papers, "Generalized sketches as a framework for completeness theorems", and "Avoiding the axiom of choice in general category theory" as being available as hard copies. I now have run out of the copies, which were rather expensive because of the lengths of the papers. Now, the same papers have been placed on anonymous ftp at triples.math.mcgill.ca in the directory /pub/makkai ; the first paper is in directory /sketch , the second in /anafun , each paper is in several files. They are also available via WWW ftp://triples.math.mcgill.ca/pub/makkai/makkai_triples.html . If you need help, there is a README file which you can obtain as follows: ftp triples.math.mcgill.ca cd pub/makkai get README bye Michael Makkai Date: Wed, 25 Jan 1995 10:07:29 -0400 (AST) Subject: Preprint Available Date: Tue, 24 Jan 95 17:53:08 +1100 From: Walter Tholen The following paper may be requested from Maria Manuel Clementino (paper or electronic copy) by writing to clementino@gemini.ci.uc.pt "Compact objects and perfect morphisms" by M.M. Clementino, E. Giuli and W. Tholen Abstract: In a category with a subobject structure and a closure operator, we provide a categorical theory of compactness and perfectness which yields a number of classical results of general topology as special cases, including the product theorems by Tychonoff and Frolik and the existence of Stone-Cech compactifications, both for spaces and maps. Applications to other categories are also provided. Date: Mon, 30 Jan 1995 00:52:51 -0400 (AST) Subject: Announce: revision of paper Date: Fri, 27 Jan 95 11:28:56 EST From: Robert A. G. Seely We wish to announce the availability (by ftp or WWW) of the following paper (revised version) Natural deduction and coherence for weakly distributive categories by R.F. Blute, J.R.B. Cockett, R.A.G. Seely, and T.H. Trimble ABSTRACT: This paper examines coherence for certain monoidal categories using techniques coming from the proof theory of linear logic, in particular making heavy use of the graphical techniques of proof nets. We define a two sided notion of proof net, suitable for categories like weakly distributive categories which have the two-tensor structure (times/par) of linear logic, but lack a negation operator. Representing morphisms in weakly distributive categories as such nets, we derive a coherence theorem for such categories. As part of this process, we develop a theory of expansion-reduction systems with equalities and a term calculus for proof nets, each of which is of independent interest. In the symmetric case the expansion reduction system on the term calculus yields a decision procedure for the equality of maps for free weakly distributive categories. The main results of this paper are these. First we have proved coherence for the full theory of weakly distributive categories, extending similar results for monoidal categories to include the treatment of the tensor units. Second, we extend these coherence results to the full theory of *-autonomous categories - providing a decision procedure for the maps of free symmetric *-autonomous categories. Third, we derive a conservative extension result for the passage from weakly distributive categories to *-autonomous categories. We show strong categorical conservativity, in the sense that the unit of the adjunction between weakly distributive and *-autonomous categories is fully faithful. NOTES: This is a significant revision of an earlier version announced a year ago. The paper has been completely rewritten, and has been enhanced in several ways: 1) We now treat the cases with non-logical axioms, and with non-commutative tensor and par, in considerable detail, pointing out in passing where the traditional treatment (of the pure commutative case) does not work in these cases. For example, the traditional proof of sequentiality (via splitting links) does not work in the presence of non-logical axioms. 2) We develop a term calculus for proof nets, and a theory of expansion - reduction rewrite systems, both of which are of independant interest. 3) Using this new material has made the proofs clearer and more complete. TO OBTAIN THE PAPER: By ftp: ftp triples.math.mcgill.ca login as anonymous use your email address as password cd pub/rags/nets binary get nets.ps.gz (or nets.dvi.gz if you prefer) (You will have to gunzip this file to get the PostScript - or DVI - file for the paper.) By WWW (Mosaic, netscape, ...) My home page is: ftp://triples.math.mcgill.ca/pub/rags/ragstriples.html click on the item labelled with the paper's title - this will display the PostScript file. (other papers dealing with weakly distributive categories and proof nets may be found easily via my home page.) (If you need to get gunzip, you can find it at pip.shsu.edu: issue the command "quote site index gzip" once you have ftp'd the site to get a list of files suitable for various computer platforms.) = rags = Date: Tue, 7 Feb 1995 01:59:00 -0400 (AST) Subject: Higher-dimensional algebra and TQFT Date: Sun, 5 Feb 95 19:53:07 PST From: john baez The paper "Higher-dimensional algebra and topological quantum field theory", by John Baez and James Dolan, is now available by anonymous ftp as the file baez/tqft.tex from math.ucr.edu It is in LaTeX, but to LaTeX it you also need the files auxdefs.sty and diagram.sty, which are also in the directory baez. Here's an abstract: The study of topological quantum field theories increasingly relies upon concepts from higher-dimensional algebra such as n-categories and n-vector spaces. We review progress towards a definition of n-category suited for this purpose, and outline a program in which n-dimensional TQFTs are to be described as n-category representations. First we describe a `suspension' operation on n-categories, and hypothesize that the k-fold suspension of a weak n-category stabilizes for k greater than or equal to n + 2. We give evidence for this hypothesis and describe its relation to stable homotopy theory. We then propose a description of n-dimensional unitary extended TQFTs as weak n-functors from the `free stable weak n-category with duals on one object' to the n-category of `n-Hilbert spaces'. We conclude by describing n-categorical generalizations of deformation quantization and the quantum double construction. Date: Wed, 22 Feb 1995 03:56:25 -0400 (AST) Subject: course on categories available Date: Tue, 21 Feb 1995 15:46:42 +0100 From: Jaap van Oosten I wrote a first course in category theory which I think more or less contains what's presumed knowledge in not too specialized papers and thesises (in computer science). It's 75 pages. The synopsis is: 1. Categories and functors. Definitions and examples. Duality principle. 2. Natural transformations. Exponents in Cat. Yoneda lemma. Equivalence of categories; Set^{op} equivalent to Complete Atomic Boolean Algebras. 3. Limits and Colimits. Functors preserving (reflecting) them. (Finitely) complete categories. Limits by products and equalizers. 4. A little piece of categorical logic. Regular categories, regular epi-mono factorization, subobjects. Interpretation of coherent logic in regular categories. Expressing categorical facts in the logic. Example of \Omega -valued sets for a frame \Omega. 5. Adjunctions. Examples. (Co)limits as adjoints. Adjoints preserve (co)limits. Adjoint functor theorem. 6. Monads and Algebras. Examples. Eilenberg Moore and Kleisli as terminal and initial adjunctions inducing a monad. Groups monadic over Set. Lift and Powerset monads and their algebras. Forgetful functor from T-Alg creates limits. 7. Cartesian closed categories and the \lambda-calculus. Examples of ccc's. Parameter theorem. Typed \lambda calculus and its interpretation in ccc's. Ccc's with natural numbers object: all primitive recursive functions are representable The notes are available by anonymous ftp via: ftp ftp.daimi.aau.dk cd pub/BRICS/LS/95/1 get BRICS-LS-95-1.ps.gz Jaap van Oosten Date: Tue, 21 Mar 1995 04:07:59 -0400 (AST) From: categories To: categories Subject: Linear Lauchli Semantics: paper available Date: Mon, 20 Mar 95 23:42:24 EST From: SCPSG@acadvm1.uottawa.ca The paper below is available by anonymous ftp from the following sites: triples.math.mcgill.ca, in the directory: pub/blute, theory.doc.ic.ac.uk, in the directory: papers/Scott. ftp.csi.uottawa.ca , in the directory: pub/papers/PhilScott The file is called: lauchli.ps.Z. Any comments would be greatly appreciated. Cheers, Philip Scott P. S. Of course, you may also contact either of the authors for a hard copy: R. F. Blute & P. J. Scott Dept. of Mathematics University of Ottawa 585 King Edward Ottawa, Ont. K1N 6N5 Canada ---------------------------------------------- LINEAR LAUCHLI SEMANTICS R. F. Blute P. J. Scott We introduce a linear analogue of Lauchli's semantics for intuitionistic logic. In fact, our result is a strengthening of Lauchli's work to the level of proofs, rather than provability. This is obtained by considering continuous actions of the additive group of integers on a category of topological vector spaces. The semantics, based on functorial polymorphism, consists of dinatural transformations which are equivariant with respect to all such actions. Such dinatural transformations are called uniform. To any sequent in Multiplicative Linear Logic (MLL), we associate a vector space of ``diadditive'' uniform transformations. We then show that this space is generated by denotations of cut-free proofs of the sequent in the theory MLL+MIX. Thus we obtain a full completeness theorem in the sense of Abramsky and Jagadeesan, although our result differs from theirs in the use of dinatural transformations. As corollaries, we show that these dinatural transformations compose, and obtain a conservativity result: diadditive dinatural transformations which are uniform with respect to actions of the additive group of integers are also uniform with respect to the actions of arbitrary cocommutative Hopf algebras. Finally, we discuss several possible extensions of this work to noncommutative logic. It is well known that the intuitionistic version of Lauchli's semantics is a special case of the theory of logical relations, due to Plotkin and Statman. Thus, our work can also be viewed as a first step towards developing a theory of logical relations for linear logic and concurrency. Date: Mon, 27 Mar 1995 20:31:16 -0400 (AST) From: categories To: categories Subject: the thesis, Complexity Doctrines, by web or ftp Date: Mon, 27 Mar 1995 17:14:24 -0500 From: Jim Otto Dear People, The thesis, Complexity Doctrines (14+121 pages), contains the chapters
  • Tensor and Linear Time
  • V-Comprehensions and P Space
  • Dependent Products and Church Numerals
  • 3-Comprehensions and Kalmar Elementary
and was submitted 3-28-95.
It is available by web from either of ftp://triples.math.mcgill.ca/ctrc.html ftp://triples.math.mcgill.ca/pub/otto/otto.html or by ftp from triples.math.mcgill.ca /pub/otto/thesis.ps.gz (E.g. use gunzip and ghostview.) Bon Soir, Jim Otto Date: Wed, 10 May 1995 23:03:36 -0300 (ADT) Subject: announcement of paper Date: Wed, 10 May 1995 20:24:52 +1000 (EST) From: C. Barry Jay A Semantics for Shape ===================== by C. Barry Jay is now available by anonymous ftp at ftp.socs.uts.edu.au in the file users/cbj/shape_semantics.ps.Z Abstract -------- Shapely types separate data, represented by lists, from shape, or structure. This separation supports shape polymorphism, where operations are defined for arbitrary shapes, and shapely operations, for which the shape of the result is determined by that of the input, permitting static shape checking. The shapely types are closed under the formation of fixpoints, and hence include the usual algebraic types of lists, trees, etc. They also include other standard data structures such as arrays, graphs and records. Date: Wed, 17 May 1995 00:58:55 -0300 (ADT) Subject: Announcement of papers Date: Wed, 17 May 95 10:40:41 +1000 From: Sjoerd Crans Dear people, The following papers are now available by anonymous ftp from ftp.maths.usyd.edu.au, in the directory sydcat/papers/crans. Hardcopies are also available, requests for this can be sent to the address below. thcms.ps Sjoerd E. Crans Quillen closed model structures for sheaves, to appear in {\em Journal Pure Appl. Algebra} 100 (1995). Abstract: In this paper I give a general procedure of transferring closed model structures along adjoint functor pairs. As applications I derive from a global closed model structure on the category of simplicial sheaves closed model structures on the category of sheaves of 2-groupoids, the category of bisimplicial sheaves and the category of simplicial sheaves of groupoids. Subsequently, the homotopy theories of these categories are related to the homotopy theory of simplicial sheaves. thpp.ps Sjoerd E. Crans Pasting presentations for $\omega$-categories. Abstract: The pasting theorem showed that pasting schemes are useful in studying free $\omega$-categories. It was thought that their inflexibility with respect to composition and identities prohibited wider use. This is not the case: there is a way of dealing with identities which makes it possible to describe $\omega$-categories in terms of generating pasting schemes and relations between generated pastings, \ie{}, with pasting presentations. In this paper I develop the necessary machinery for this. The main result, that the $\omega$-category generated by a pasting presentation is universal with respect to respectable families of realizations, is a generalization of the pasting theorem. thten.ps Sjoerd E. Crans Pasting schemes for the monoidal biclosed structure on $\omega\mbox{-} \bf Cat$. Abstract: Using the theory of pasting presentations, developed in the previous paper, I give a detailed description of the tensor product on $\omega$-categories, which extends Gray's tensor product on $2$-categories and which is closely related to Brown-Higgins's tensor product on $\omega$-groupoids. Immediate consequences are a general and uniform definition of higher dimensional lax natural transformations, and a nice and transparent description of the corresponding internal homs. Further consequences will be in the development of a theory for weak $n$-categories, since both tensor products and lax structures are crucial in this. Sjoerd Crans School of Mathematics and Statistics University of Sydney NSW 2006 Australia email: crans_s@maths.usyd.edu.au Date: Mon, 26 Jun 1995 09:57:17 -0300 (ADT) Subject: defended and corrected thesis: `Complexity Doctrines' Date: Sun, 25 Jun 95 21:25:02 EDT From: James Otto Dear people, The thesis `Complexity Doctrines', which was announced to this list at submission, was defended June 9. The June 13 corrected version is now linked to ftp://triples.math.mcgill.ca/pub/otto/otto.html which is in turn linked to ftp://triples.math.mcgill.ca/ctrc.html (The thesis is actually at ftp://triples.math.mcgill.ca/pub/otto/thesis.ps.gz.) Bon Soir, Jim Otto otto@triples.math.mcgill.ca Date: Tue, 22 Aug 1995 08:38:24 -0300 (ADT) Subject: update to (and correction of) Complexity Doctrines Date: Sun, 20 Aug 95 20:39:50 EDT From: James Otto Dear People, The following update to (and correction of) my thesis, Complexity Doctrines, is also linked to (either of) ftp://triples.math.mcgill.ca/ctrc.html ftp://triples.math.mcgill.ca/pub/otto/otto.html Regards, Jim Otto Update to Complexity Doctrines J. Otto August 20, 1995 In this note we 1. point out an (annoying) error (of ours) in background material on G"odel's system T, and thus pose an question, 2. improve the definition of tier 0, 3. improve the definition (and name) of sketches theories, 4. reduce presheaves to (Makkai) sketches, and 5. propose a definition of resolutions. We thus update the June 13, 1995 version of Complexity Doctrines. That version is currently linked to ftp://triples.math.mcgill.ca/pub/otto/otto.html By the way, Springer LNCS 953 contains a slightly earlier (with an X which clearly should be a 1) and abridged version of Chapter 2 of Complexity Doctrines. 1. System T We consider NNO (= natural numbers objects) in SMC (=symmetric monoidal closed) and CC (= cartesian closed) categories. Write (as this is not TeX) * for tensor and I for the unit. Define -o by _ * X -| X -o _. Write S for the category of SMC categories having NNO and of functors preserving chosen structure, and T for the category of CC categories having NNO and of functors preserving chosen structure. With J and K initial categories in S and T and with standard structure on set (the category of small sets), we have the (unique) S and T functors j : J --> set and k : K --> set. Statement 5 of Proposition 1.2.4.1 claims (which we now doubt) that j and k represent the same numeric functions (= functions between finite powers of N). The purported proof of Statement 5 fails (as we finally saw after kind remarks by P. Scott at the 1995 Category Theory and Computer Science meeting) as while the diagonal diag : N --> N * N is definable in J [Par'e Rom'an], it is doubtful that e.g. the diagonal diag : N -o N --> (N -o) * (N -o N) is definable in J. As both j and k represent the primitive recursive numeric functions, they both represent Turing machines modulo how long the machines run. Thus which numeric functions j and k represent is a matter of how fast such functions can grow. It is known [Rose, Subrecursion] that the (set of) numeric functions represented by k is the extended Grzegorczyk hierarchy below epsilon_0. At least a naive attempt to obtain such growth of numeric functions represented by j fails. In J we can define, by commuting diagrams, 0 * N s * N I * N ----> N * N ----> N * N | | | | l_N | + | + v v v N --------> N --------> N id s e_2 = + diag 0 s I ------> N ------> N | | | | id | e_n+1 | e_n+1 v v v I ------> N ------> N s 0 e_n Now we would like to diagonalize the e_n to get beyond primitive recursion. But this may be undefinable in J. However in K, by using diag : N -o N --> (N -o N) * (N -o N) and now writing _ x X -| X => _ and 1 rather than _ * X -| X -o _ and I, we can define 0 x (N => N) s x (N => N) 1 x (N => N) ------> N x (N => N) ------> N x (N => N) | | | | p_1 | p_1, ' | p_1, ' v v v N => N ---------> (N => N) x N ------> (N => N) x N id, s 0 ! p_0, @ 0 s 1 ------> N --------> N | | | | id | f | f v v v 1 ----> N => N ---> N => N f_2 " Here _ x X -| X => _ defines @ : (X => Y) x X --> Y terminal in the comma category (_ x X)/Y and e_2 : N --> N ------------------ f_2 : 1 --> N => N ' : N x (N => N) --> N ------------------------- " : (N => N) --> (N => N) e : N x N --> N ---------------- f : N --> N => N Further ! is the unique map to 1. Then we can diagonalize: e diag. Thus we pose the question Which numeric functions are represented by j? 2. Tier 0 Tier 0 can be defined as the pseudo-equalizer (aka iso-inserter) of T C ----> C ----> I ! (with I ! taking objects to the unit I and maps to the identity on I). 3. Sketches Theories Sketches theories, formerly sketch theories, are theories of (Makkai rather than Ehresmann) sketches. Definition. With a a cardinal, an a-sketches theory is a category S such that 1. S is small, 2. S is well-founded, and 3. S has fan-out < a. Here that S is well-founded is that for all S objects X all chains of composable non-identity maps starting from X X --> --> ... have finite length. Note that well-founded implies acyclic (aka 1-way) and skeletal. Further, S having fan-out < a is that for all S objects X the cardinality of the set (indeed, cone) of maps starting from X is < a. We are mainly interested in the finitary case, which is when a is countable. 4. Reducing Presheaves to (Makkai) Sketches. [Ad'amek Rosick'y] elegantly present the accessible categories, in various classes, as the full subcategories in categories of presheaves set^C of the objects [cone] (orthogonal | injective) relative to small sets A of (cones | maps). We reduce, by orthogonality, the categories of presheaves set^C to categories of a-sketches set^S. Proposition. Given a small category C there is a 4-sketches theory S and a (small) set A of finitely presentable set^S maps such that set^C is equivalent to the full subcategory in set^S of objects orthogonal to A. Proof. As S objects, take the objects and maps of C. As non-identity S maps, indexed by the C maps f : X --> Y, take the (formal) maps c_f : f --> Y, d_f : f --> X. Define a functor G : S --> C by c_f |-> f, d_f |-> id_X. Then G^* : set^C --> set^S by F |-> F G is faithful full. We recover the image of G^*, up to equivalence, by defining A through the following 3 schemes (using notation as in Complexity Doctrines). For C maps f : X --> Y {! i_f x : f d_f i_f x = x : X [x : X]} For C identity maps j : X --> X {c_j a = d_j a : X [a : j]} For C compositions h ------------> X ----> Y ----> Z f g {c_h c = c_g b : Z [d_h c = d_f a : X c_f a = d_g b : Y a : f b: g c : h]} QED 5. Resolutions Consider a finitary sketches theory S and a (small) set A of finitely presentable maps in set^S. Again (as in [Ad'amek Rosick'y]) reduce orthogonality to injectivity. (Thus, for non-epi maps a in A, add to A the a^* : P --> X induced by the push-out of a along a: a a ------> ------> | | | | | a | | a | id v po v v v ------> P ------> X id .) Roughly following [Makkai], define deductions d as compositions of push-outs (in set^S) of maps a (thought of as axioms) in A. We propose defining resolutions as cospans (in set^S) | | v ----> d with the left map a deduction. Then resolutions compose as cospans: | | d' v ----> | | | | v po v ----> ----> d As the initial sketch orthogonal to the (original) A is the colimit of the diagram of deductions from the empty sketch 0, one may wish to resolve to 0: | | v 0 ----> d In a resolution X | | f v ----> d think of X as a query and of f as a partial answer. End of note. Date: Sat, 30 Sep 1995 14:25:17 -0300 (ADT) Subject: Braided monoidal 2-categories Date: Fri, 29 Sep 1995 16:27:23 -0700 From: john baez Martin Neuchl and I have written a paper entitled "Higher-dimensional algebra I: braided monoidal 2-categories". In it, we begin with a brief sketch of what is known and conjectured concerning braided monoidal 2-categories and their relevance to 4d topological quantum field theories and 2-tangles. Then we give concise definitions of semistrict monoidal and braided monoidal 2-categories, and show how these may be unpacked to give definitions similar to, but not quite the same as, those given by Kapranov and Voevodsky. Finally, we describe how to construct a semistrict braided monoidal 2-category as the "center" of a semistrict monoidal 2-category, in a manner analogous to the construction of a braided monoidal category as the center (or "quantum double") of a monoidal category. As a corollary this yields a strictification theorem for braided monoidal 2-categories. This paper is available by anonymous ftp to math.ucr.edu. It is the file bm2cat in the directory baez. It is in uuencoded, compressed form, because it is 51 pages with lots of pictures. To print it, first save the file as "bm2cat" and do "uudecode bm2cat". This should produce a file "bm2cat.dvi.Z". Then do "uncompress bm2cat.dvi.Z". This should produce a file "bm2cat.dvi," which you can print out in the way you usually print dvi files. John Baez Date: Mon, 30 Oct 1995 16:37:23 -0400 (AST) Subject: Shape papers Date: Mon, 30 Oct 1995 13:47:03 GMT From: Barry Jay The following papers on SHAPE may be of interest to category theorists and computer scientists. The titles are: "A semantics for shape" shape_semantics.ps.Z "Data categories and functors" datacats.dvi.Z "Covariant types" covtypes.dvi.Z "Polynomial Polymorphism" (in directory P2) "Type-free term reduction for covariant types" typefree.dvi.Z "Shape analysis for parallel computing" parshape.dvi.Z All are available by anonymous ftp from ftp.socs.uts.edu.au in the directory Users/cbj *Some* can be acessed from my www home page at http://linus.socs.uts.edu.au/~cbj The rest of this message describes the main results of the papers, and some of the goals of the Shape project. Barry Jay University of Technology, Sydney cbj@socs.uts.edu.au Reply-To: cbj21@newton.cam.ac.uk (until 30/11/95) A semantics for shape ===================== The basic observation behind shape theory is that most of the functors F used to model data types share a common characteristic; they have a cartesian natural transformation into a functor used to store unstructured data. In the simplest case, the latter is the list (or free monoid) functor: data: F => L The main result of this paper is that in a locos (an extensive category with all finite limits and lists) all functors shapely over lists are closed under the formation of initial algebras. The proof is constructive - simply build a parser for the initial algebra, using the existing lists and pullbacks. Data categories and functors ============================ The functors which are cartesian over lists are good for handling first order structures, but they are not closed under exponentiation, and so are inadequate for higher-order types. This defect is remedied by changing the functor used to store data from lists to a *position functor* given by an object of positions P. Such a functor maps an object A to the object P --> A+1 . A *data functor* is a functor F with a given cartesian transformation to such a position functor. Now, for any object X the functor which maps A to the object X --> FA is also a position functor, with object of positions XxP. The key result about data functors is that every natural transformation between two such is given by a uniform, or parametric natural transformation. More precisely, if F is a data functor with object of positions P, and G is a data functor, then every natural transformation F ==> G is determined by a morphism F1 --> GP This fact makes the data functors suitable for modelling higher types. Covariant Types =============== The data categories, in which the theory of data functors is developed, include the usual semantic categories, such as Sets, and bottomless c.p.o.'s. However, Reynolds proved that "Polymorphism is not set-theoretic" by showing that the second-order polymorphic lambda calculus (system F) has no set-theoretic models. This leads us to ask what kind of polymorphism is modelled by the data functors. This leads to the covariant type system in which function types are replaced by *transformation types*. The system is strong enough to capture the usual polymorphism of lists and trees, while still having set-theoretic models. Thus, Polymorphism *can* be set-theoretic Polynomial Polymorphism ======================= As a sub-system of F, the covariant types do not capture functoriality. For shape (or functorial) polymorphism to make sense, there must be a polymorphic algorithm for evaluating the action of functors on morphisms, i.e. a polymorphic map. Such an algorithm was first developed in the type system P2, as described in the following paper. Type-free term reduction for covariant types ============================================ A generic algorithm for mapping requires the detection of the data to which the mapped function must be applied. One method of doing this is to *tag* the data using a single system of tags appropriate for all the functors under discussion. A naive approach leads to the tagged types of this paper. Functorial types ================ Current work aims to have functors represented directly by types so that, for example, composition of functors is a primitive operation on types. This is intended to extend the notion of category theory as a programming technique. Shape analysis for parallel computing ===================================== While shape polymorphism allows us to "ignore" the shape, shape analysis uses detailed shape information to improve errr detection and compilation. This is particularly important in parallel programming, where the shape of the data structures, and their distribution, are central concerns. This paper presents a survey of the issues, and a computational paradigm, that will be developed by the Algorithms and Languages Group University of Technology, Sydney http://linus.socs.uts.edu.au/~shape Date: Tue, 7 Nov 1995 21:54:02 -0400 (AST) Subject: announcement Date: Tue, 7 Nov 1995 20:30:48 -0500 From: Michael Makkai This is to announce a research monograph, First Order Logic with Dependent Sorts, with Application to Category Theory by M. Makkai (McGill Univ.) (Preliminary version) Abstract J. Cartmell [2] introduced a syntax of variable types, which I call dependent sorts, for the purposes of presenting generalized algebraic theories. Cartmell's syntax was "abstracted from ... Martin-Lof type theory". I add propositional connectives and quantification to a simplified version of Cartmell's syntax, to obtain what I call First-Order Logic with Dependent Sorts (FOLDS). The simplification consists in the exclusion of operation symbols, and a severe restriction on the use of equality. Quantification is subject to the natural restriction that a quantifier "for all x " or "there is x " cannot be applied if in the resulting formula there is a free variable whose sort depends on x . An important special case of FOLDS was introduced by G. Blanc [1] for the purpose of characterizing first-order formulas in the language of categories that are invariant under equivalence of categories. P. Freyd's earlier characterization [3], although not explicitly coached in an instance of FOLDS, is essentially the same as Blanc's. A. Preller [7] gives an explicit comparison of Blanc's and Freyd's contexts. The main aim of the present work is to extend Blanc's and Freyd's characterization from statements about categories to statements about more complex categorical structures. A similarity type for structures for FOLDS is given by a one-way category of sort-forming symbols and relation symbols. One-way categories were isolated by F. W. Lawvere [4], and were subsequently shown by him to be relevant for the generalized sketch-syntax of [5]. The basic metatheory of FOLDS is a simple extension of that of ordinary multisorted first-order logic. There are simply formulated complete formal systems for both classical and intuitionistic FOLDS, with Kripke-style completeness for the intuitionistic case. The systems use entailments-in-contexts as their basic units; contexts are systems of typings of variables as usual in Martin- Lof-style systems. We have Gentzen-style systems admitting cut- elimination. Natural forms of Craig Interpolation and Beth Definability are true in both classical and intuitionistic FOLDS. Much of the basic metatheory is done through the formalism of appropriate fibrations (hyper-doctrines). The main new concept is a notion of equivalence of structures for FOLDS. Equivalent structures satisfy the same sentences of FOLDS. The main general result is that conversely, first order properties invariant under equivalence are expressible in FOLDS. A stronger version of the result takes the form of an interpolation theorem. Two categories are equivalent in the usual sense iff they are equivalent as structures for FOLDS. This connection between the categorical concept of equivalence and FOLDS-equivalence persists for more complex categorical structures such as (1) a diagram of categories, functors and natural transformations, or (2) a bicategory, or (3) a diagram of bicategories, etc., if we pass to "ana"-versions of the concepts of functor, bicategory, etc.; the latter were introduced in [6]. Every functor, bicategory, etc., has its so-called saturation, a simply defined saturated anafunctor, saturated anabicategory, etc., respectively. A property written in FOLDS of the saturation is a particular, "good", kind of first- order property of the original. Applications of the foregoing give syntactical characterizations of properties invariant under equivalence in the contexts mentioned. E.g., a first-order property of a variable bicategory is invariant under biequivalence iff it is expressible in FOLDS as a property of the saturated anabicategory canonically associated with the given bicategory. References [1] G. Blanc, Equivalence naturelle et formules logiques en theorie des categories. Archiv math. Logik 19 (1978), 131-137. [2] J. Cartmell, Generalised algebraic theories and contextual categories. Annals of Pure and Applied Logic 32 (1986), 209-243. [3] P. Freyd, Properties invariant within equivalence types of categories. In: Algebra, Topology and Category Theories, ed. A. Heller and M. Tierney, Academic Press, New York, 1976; pp. 55-61. [4] F. W. Lawvere, More on graphic toposes. Cah. de Top. et Geom. Diff. 32 (1991), 5-10. [5] M. Makkai, Generalized sketches as a framework for completeness theorems. To appear in J. Pure and Applied Algebra. [6] M. Makkai, Avoiding the axiom of choice in general category theory. To appear in J. Pure and Applied Algebra. [7] A. Preller, A language for category theory in which natural equivalence implies elementary equivalence of models. Zeitschrift f. math. Logik und Grundlagen d. Math. 31 (1985), 227-234. (End of Abstract) A manuscript copy of this work was placed on exhibit at the Category Theory Meeting in Halifax, 1995; my talk was about the same subject. I promised to send copies to people who signed up for them. I would appreciate if those who have been waiting for this, and now find this announcement, would let me know. I will try to contact those on the list with me who do not respond. The manuscript has been placed on anonymous ftp at triples.math.mcgill.ca in directory /pub/makkai/folds in several files. You may consult the README file in the directory /pub/makkai. Date: Fri, 3 Nov 1995 16:21:57 -0400 (AST) Subject: Electronic supplement to ctcs Date: Fri, 3 Nov 1995 15:00:11 -0500 From: Michael Barr The electronic supplement is now in my ftp directory under the name that is given in ctcs, namely ctcs.elec.supp.??. There are actually six forms: {ps,dvi}{ ,gz,zip}. Date: Fri, 10 Nov 1995 14:45:43 -0400 (AST) Subject: Book Announcement Date: Fri, 10 Nov 1995 11:17:20 -0500 From: Walter Tholen The book "Categorical Structure of Closure Operators" by D. Dikranjan and W. Tholen has appeared in the "Mathematics and Its Applications" series of Kluwer Academic Publishers (Dordrecht, Boston, London 1995; ISBN 0-7923-3772-7). Abstract: The book provides a comprehensive categorical theory of closure operators, with applications to topological and uniform spaces, groups, R-modules, fields and topological groups, as well as to partially ordered sets and graphs. In particular, closure operators are used to give solutions to the epimorphism and cowellpoweredness problem in many concrete categories. The material is illustrated with many examples and exercises, and open problems are formulated in order to stimulate further research. -- Walter Tholen Department of Mathematics and Statistics York University, North York, Ont. Canada M3J 1P3 tel. (416) 736 5250 fax. (416) 736 5757 Date: Fri, 10 Nov 1995 16:39:59 -0400 (AST) Subject: Abstracts "Descent Theory", Oberwolfach '95 Date: Fri, 10 Nov 1995 15:20:10 -0500 From: Walter Tholen Anybody who is interested in getting the files for the Abstracts of talks given at the meeting on "Geometric and Logical Aspects of Descent Theory" in Oberwolfach (September '95) may access these by contacting my home page on the WWW (address below) and clicking on the respective item. Participants will receive a hardcopy of these abstracts automatically, sent to them by the Institute. -- Walter Tholen Department of Mathematics and Statistics York University, North York, Ont., Canada M3J 1P3 tel. (416) 736 5250 or 736 2100, ext. 33918 fax. (416) 736 5757 http://www.math.yorku.ca/Who/Faculty/Tholen/menu.html Date: Tue, 5 Dec 1995 22:41:33 -0400 (AST) Subject: paper on equivariant homotopy Date: Mon, 4 Dec 1995 18:06:48 GMT From: Manuel Bullejos The following paper can be obained from my www page with address http:\\www.ugr.es\~bullejos \title{On the equivariant 2-type of a $G$-space} \begin{abstract} A classical theorem of Mac Lane and Whitehead states that the homotopy type of a topological space with trivial homotopy at dimensions 3 and greater can be re\-con\-struct\-ed from its $\pi_1$ and $\pi_2$, and a cohomology class $k_3\in H^3(\pi_1,\pi_2)$. More recently, Moerdijk and Svensson suggested the possibility of using Bredon cohomology to extend this result to the equivariant case, that is, for spaces $X$ equipped with an action by a fixed group $G$. In this paper we carry out this suggestion and prove an analogue of the classical result in the equivariant case. \end{abstract} Date: Thu, 21 Dec 1995 10:14:00 -0400 (AST) Subject: (Fwd) Re: Abstracts "Descent Theory", Oberwolfach '95 Date: Wed, 20 Dec 1995 13:51:34 -0500 From: Walter Tholen Dear Colleagues, a link has been appended to my WWW home page to obtain the notes of Ross Street's lectures on Descent Theory at the Oberwolfach Conference in September.These files may accessed also directly; the address is ftp://ftp.mpce.mq.edu.au/pub/maths/Categories/Oberwolfach/ The files themselves are: -rw-r--r-- 1 ross ftpmaths 1329104 Dec 13 16:34 Oberwolfach_1.ps -rw-r--r-- 1 ross ftpmaths 707855 Dec 13 16:33 Oberwolfach_1.ps.Z -rw-r--r-- 1 ross ftpmaths 1196252 Dec 13 16:34 Oberwolfach_2.ps -rw-r--r-- 1 ross ftpmaths 605741 Dec 13 16:34 Oberwolfach_2.ps.Z -rw-r--r-- 1 ross ftpmaths 1018897 Dec 13 16:37 Oberwolfach_3.ps -rw-r--r-- 1 ross ftpmaths 549743 Dec 13 16:37 Oberwolfach_3.ps.Z ... giving a PostScript file (txt) and a compressed (binary) version of each. A good Web browser can get them using the above as a URL. It may even automatically uncompress and render the PostScript file. Best wishes for the Holiday Season and a Happy New Year! Walter. -- Walter Tholen Department of Mathematics and Statistics York University, North York, Ont., Canada M3J 1P3 tel. (416) 736 5250 or 736 2100, ext. 33918 fax. (416) 736 5757 http://www.math.yorku.ca/Who/Faculty/Tholen/menu.html Date: Tue, 23 Jan 1996 21:08:18 -0400 (AST) Subject: draft paper: From Horn formula to Makkai sketch resolution Date: Mon, 22 Jan 1996 23:42:51 -0500 From: James Otto Dear People, The plain text draft paper, whose title and abstract follows, is availabe by web or ftp at ftp://triples.math.mcgill.ca/pub/otto/res and is linked to ftp://triples.math.mcgill.ca/pub/otto/otto.html Best regards, Jim From Horn formula to Makkai sketch resolution J. Otto January 22, 1996 otto@triples.math.mcgill.ca Abstract. We provide a basis for logic programming into locally finitely presentable (or l.f.p.) categories. We thus begin to consider higher order logic programming. Horn formulas, in particular systems of equations, generalize to finite Makkai (or M-) sketches. Further, models of sets of Horn clauses generalize to, again called models and forming the l.f.p. categories, M-sketches orthogonal to sets of maps (axioms) between finite M-sketches. Resolutions compute maps (answers) from finite M-sketches (queries) to initial models. Resolutions are cospans and lift to compositions of special resolutions. Date: Mon, 29 Jan 1996 17:09:08 -0400 (AST) Subject: correction to `From ... resolution' Date: Sat, 27 Jan 1996 08:31:41 -0500 From: James Otto Dear People, A correction was made to the 1-23-96 version of ftp://triples.math.mcgill.ca/pub/otto/res Regards, Jim 1-27-96 Date: Wed, 31 Jan 1996 14:12:27 -0400 (AST) Subject: groupoids Date: Wed, 31 Jan 1996 09:12:09 -0800 (PST) From: Alan Weinstein Dear Colleagues, I've just finished a survey article entitled "Groupoids: unifying internal and external symmetry", which I have submitted to the Notices of the AMS. It is available as a postscript file via email (alanw@math.berkeley.edu) or my web page (http://math.berkeley.edu/~alanw). Comments are welcome, of course. Alan Weinstein Date: Fri, 2 Feb 1996 14:55:38 -0400 (AST) Subject: Preprints Date: Fri, 2 Feb 1996 10:29:02 +0100 From: Marco Grandis The following two preprints will soon be available. A "hard" copy will be sent on request. With best regards, Marco Grandis Dipartimento di Matematica Universita' di Genova Via Dodecaneso 35 16146 Genova, Italy (E-mail: grandis@dima.unige.it) *** 1. M. Grandis, Categorically algebraic foundations for homotopical algebra, Dip. Mat. Univ. Genova, Preprint 293 (1996). Abstract. We investigate a structure for an abstract cylinder endofunctor I which produces a good basis for homotopical algebra. It essentially consists of the usual operations (faces, degeneracies, connections, symmetries, composition) together with a transformation I^2 -> I^2, which we call lens collapse after its realisation in the standard topological case. This structure, if somewhat heavy, has the interest of being "categorically algebraic", i.e. based on operations on functors. Consequently, it can be naturally lifted from a category A to its categories of diagrams A^S and its slice categories A\X, A/X. Further, the dual structure, based on a cocylinder (or path) endofunctor P can be lifted to the category of A-valued sheaves on a site, whenever P preserves limits, and to the category of internal monoids in A, with respect to any monoidal structure of A consistent with P. 2. M. Grandis, On the homotopy structure of strongly homotopy associative differential algebras, Dip. Mat. Univ. Genova, Preprint 294 (1996). Abstract. We study here the homotopy structure of Shad, the category of strongly homotopy associative d-algebras (shad-algebras for short), also called A_infinity-algebras and introduced by Stasheff ([St], 1963) for the study of the singular complex of the loop-space of a pointed topological space. Shad extends the category Da of associative differential (graded) algebras, by allowing for a homotopy relaxation of objects and morphisms, up to systems of homotopies of arbitrary degree. The better known category Dash of associative differential algebras and strongly homotopy multiplicative maps (Stasheff-Halperin [StH], Munkholm [Mu1-4]), having strict objects (the ones of Da) and lax morphisms (the ones of Shad) is intermediate between them. A crucial advantage of Shad over its subcategories Dash and Da is the homotopy invariance property proved by Gugenheim - Stasheff [GuS]. In order to study shad-homotopies of any order and their operations, the usual cocylinder functor of d-algebras is here extended to Shad, where we construct the vertical composition and reversion of homotopies (also existing in Dash, but not in Da) and homotopy pullbacks (which exist in Da, but not in Dash). Shad acquires thus a laxified version of the homotopy structure studied by the author in previous works; the main results therein, developing homotopical algebra from the Puppe sequence to stabilisation and triangulated structures, can very likely be extended to the new axioms, so to be available for Shad. Date: Wed, 14 Feb 1996 15:16:30 -0400 (AST) Subject: Preprint (announcement) Date: Wed, 14 Feb 1996 13:12:33 +0100 From: Anders Kock The paper "Frame distributions, and support" by A. Kock and G.E,. Reyes is available by anonymous ftp : ftp://theory.doc.ic.ac.uk/papers/Kock where it appears as distr.ps.Z It is a slightly expanded version of the preprint with the same title, Universite de Montreal DMS No 386, janvier 1996. Abstract: We analyze in terms of constructive frame theory the relationship between support of distributions, regularization of opens, and "frame distributions" (sup lattice maps from a frame to the frame of truth values, as considered recently by Bunge and Funk). Date: Thu, 15 Feb 1996 11:13:38 -0400 (AST) Subject: Prolongation by zero (preprint) Date: Thu, 15 Feb 1996 14:26:36 +0100 From: Anders Kock The preprint "Locally closed sublocales and prolongation by zero" is available by anonymous ftp from theory.doc.ic.ac.uk/papers/Kock where it appears as the file: loc-clo.ps (it is about 150 kb). Abstract: We prove that abelian group valued sheaves over a locally closed sublocale admit prolongation by zero, and that the prolongation functor has a right adjoint. The method is by left exact comonads; specifically, it uses a version of Artin-Wraith glueing, where one has to put glue on _both_ the items to be glued. Date: Tue, 28 Feb 1995 08:43:22 -0400 (AST) Subject: Enrichment and Representation Theorems for Domains. Date: Mon, 26 Feb 1996 15:06:26 GMT From: Marcelo Fiore The prepint "Enrichment and Representation Theorems for Categories of Domains and Continuous Functions" is available from http://www.dcs.ed.ac.uk/home/mf files rep.dvi or rep.ps, or by anonymous ftp from ftp.dcs.ed.ac.uk directory pub/mf files rep.dvi or rep.ps. ----------------------------------------------------------------------- Enrichment and Representation Theorems for Categories of Domains and Continuous Functions Synopsis Domain-theoretic categories are axiomatised by means of categorical non-order-theoretic requirements on a cartesian closed category equipped with a commutative monad. We prove an enrichment theorem showing that every axiomatic domain-theoretic category can be endowed with an intensional notion of approximation, the path relation, with respect to which the category Cpo-enriches. Subsequently, we provide a representation theorem of the form: every small domain-theoretic category (with a lifting monad) has a full and faithful representation in a domain-theoretic category of cpos and continuous functions (with a lifting monad) in a suitable intuitionistic set theory. Our analysis suggests more liberal notions of domains. In particular, we present a category where the path order is not omega-complete, but in which the constructions of domain theory (as, for example, the existence of uniform fixed-point operators and the solution of domain equations) are possible. ----------------------------------------------------------------------- Date: Tue, 28 Feb 1995 08:44:04 -0400 (AST) Subject: Paper available by ftp Date: Tue, 27 Feb 1996 14:17:21 -0500 From: Robert A. G. Seely The following paper is available via ftp or WWW browser, at the URLs given after the abstract. Categories for computation in context and unified logic: I by R.F. Blute, J.R.B. Cockett, and R.A.G. Seely Abstract In this paper we introduce the notion of contextual categories. These provide a categorical semantics for the modelling of computation in context, based on the idea of separating logical sequents into two zones, one representing the context over which the computation is occurring, the other the computation itself. The separation into zones is achieved via a bifunctor equipped with a tensorial strength. We show that a category with such a functor can be viewed as having an action on itself. With this interpretation, we obtain a fibration in which the base category consists of contexts, and the reindexing functors are used to change the context. We further observe that this structure also provides a framework for developing categorical semantics for Girard's Unified Logic, a key feature of which is to separate logical sequents into two zones, one in which formulas behave classically and one in which they behave linearly. This separation is analogous to the context/computation separation above, and is handled by our semantics in a similar fashion. Furthermore, our approach allows an analysis of the exponen ntial structure of linear logic using a tensorially strong action as the primitive notion. We demonstrate that from such a structure one can recover a model of the linear storage operator. Finally, we introduce a sequent calculus for the fragment of Unified Logic modeled by contextual categories. We show cut elimination for this fragment, and we introduce a simple notion of proof circuit, which provides a description of free contextual categories. ----------------------------- Available via browser on my home page ftp://triples.math.mcgill.ca/pub/rags/ragstriples.html or directly via ftp ftp://triples.math.mcgill.ca/pub/rags/bang/context1.[ps,dvi].gz (The [X,Y] syntax means you should use either X or Y in the URL, not both and not the "[", "]".) Date: Mon, 18 Mar 1996 16:32:18 -0400 (AST) Subject: Paper available: Linear Logic complements Classical Logic Date: Mon, 18 Mar 1996 11:24:50 -0800 From: Vaughan Pratt The paper described below is available by FTP or the web as follows. FTP ftp boole.stanford.edu cd pub bin get llcocl.ps.gz WEB URL: http://boole.stanford.edu/pub/llcocl.ps.gz Linear Logic complements Classical Logic V.R. Pratt To appear in preliminary proceedings of Linear Logic '96, Tokyo Classical logic enforces the separation of individuals and predicates, linear logic draws them together via interaction; these are not right-or-wrong alternatives but dual or complementary logics. Linear logic is an incomplete realization of this duality. While its completion is not essential for the development and maintenance of logic, it is crucial for its application. We outline the ``four-square'' program for completing the connection, whose corners are set, function, number, and arithmetic, and define ordinal Set, a bicomplete *equational* topos, meaning its canonical isomorphisms are identities, including associativity of product. This directory also contains 44 other papers on related topics. For a list of abstracts, see the file ABSTRACTS in this directory, URL: http://boole.stanford.edu/pub/ABSTRACTS Vaughan Pratt Date: Thu, 21 Mar 1996 13:36:59 -0400 (AST) Subject: Money_Games Date: Thu, 21 Mar 1996 11:48:11 -0500 (EST) From: Andre Joyal My paper "Free Lattices, communication and money games" is available on the WWW at: http://www.math.uqam.ca/_rapports/joyal/Money_Games.html It is to appear in the Proceedings of the International Congress of Logic, Methodology and Philosophy of Science held in Firenze, August 1995. Andre Joyal Date: Thu, 21 Mar 1996 23:15:48 -0400 (AST) Subject: Address:Money_Games Date: Thu, 21 Mar 1996 17:38:11 -0500 (EST) From: Andre Joyal The correct WWW address for my paper "Free Lattices, communication and money games" is: http://www.math.uqam.ca/_rapports/RapportsTech.html It is to appear in the Proceedings of the International Congress of Logic, Methodology and Philosophy of Science held in Firenze, August 1995. Andre Joyal Date: Mon, 25 Mar 1996 10:27:29 -0400 (AST) Subject: more on locally closed sublocales and subtoposes Date: Mon, 25 Mar 1996 11:26:29 +0100 From: Anders Kock This is to announce the preprint A. Kock and T. Plewe: Locally closed subtoposes, and prolongation by zero. It is available by anonymous ftp from theory.doc.ic.ac.uk/papers/Kock where it appears as the file Kock-Plewe.ps or Kock-Plewe.dvi . It subsumes the paper by Kock, announced here on Feb. 15 1996, and this paper has therefore now been removed from the above ftp-site. Abstract: We prove the equivalence of some conditions on a complemented subtopos of a topos, one of which is that the subtopos is locally closed, and another is that abelian group objects in the smaller topos admit prolongation by zero; the prolongation functor then has a right adjoint. Date: Fri, 19 Apr 1996 14:21:32 -0300 (ADT) Subject: My talk at Penn Date: Fri, 19 Apr 1996 11:41:28 -0400 From: Michael Barr A number of people have written to ask if the paper I am talking about at Penn is available. Yes. In the ftp directory of triples, in pub/barr/newasymm.dvi and .ps. Michael Date: Tue, 28 May 1996 12:12:19 -0300 (ADT) Subject: revised `From Horn clause to Makkai sketch resolution' Date: Mon, 27 May 1996 17:14:57 -0400 From: James Otto Dear people, The May 27, 1996 revision of `From Horn clause to Makkai sketch resolution' is now at (linked to, indirectly linked to) ftp://triples.math.mcgill.ca/pub/otto/res ftp://triples.math.mcgill.ca/pub/otto/otto.html ftp://triples.math.mcgill.ca/ctrc.html 1. Axiom templates are gone. This simplifies the main result --- lifting (for l.f.p. logic programming) --- and eliminates a section. 2. The examples are greatly improved. Even and + are added and head consolidation is gone. 3. Some terminology is improved and more motivation is added. Regards, Jim Otto Date: Tue, 4 Jun 1996 22:23:37 -0300 (ADT) Subject: Preprint (announcement) Date: Tue, 4 Jun 1996 11:57:15 +0200 From: Anders Kock The paper "Remarks on the Bianchi Identity" by A. Kock is available (compressed dvi or ps versions) from the Hypatia archive in London http://hypatia.dcs.qmw.ac.uk It uses synthetic differential geometry to understand the Bianchi identity in terms of combinatorial groupoid theory. Date: Sun, 9 Jun 1996 20:41:04 -0300 (ADT) Subject: May 28, '96 corrected revised `... Makkai sketch resolution' Date: Sat, 8 Jun 1996 14:45:43 -0400 From: James Otto Dear people, In the May 27, '96 revised `... Makkai sketch resolution' I implied that showing that f.p. presheaves over the opposites of signature categories have projective covers was not besides the point. But, as an anonymous referee indicated, it seems that it is as it seems that all f.p. presheaves have projective covers. This was fixed in the May 28, '96 corrected revised `... Makkai sketch resolution' which was linked then to the URL ftp://triples.math.mcgill.ca/pub/otto/otto.html Regards, Jim Otto Date: Wed, 24 Jul 1996 10:43:31 -0300 (ADT) Subject: paper Date: Wed, 17 Jul 1996 18:07:50 +0100 (BST) From: Dusko Pavlovic Dear Categories, The following preprint by me (to appear in MSCS) is available via http://www.cogs.susx.ac.uk/users/duskop/index.html or by anonymous ftp from ftp.cogs.susx.ac.uk file pub/users/duskop/CLNA.ps.gz. Regards, -- Dusko Pavlovic CATEGORICAL LOGIC OF NAMES AND ABSTRACTION IN ACTION CALCULI Abstract. Milner's action calculus implements abstraction in monoidal categories, so that familiar lambda-calculi can be subsumed together with the pi-calculus and the Petri nets. Variables are generalised to *names*: only a restricted form of substitution is allowed. In the present paper, the well-known categorical semantics of the lambda-calculus is generalised to the action calculus. A suitable functional completeness theorem for symmetric monoidal categories is proved: we determine the conditions under which the abstraction is definable. Algebraically, the distinction between the variables and the names boils down to the distinction between the transcendental and the algebraic elements. The former lead to polynomial extensions, like e.g. the ring Z[x], the latter to algebraic extensions like Z[\sqrt{2}] or Z[i]. Building upon the work of P.~Gardner, we introduce *action categories*, and show that they are related to the static action calculus exacly as cartesian closed categories are related to the lambda-calculus. Natural examples of this structure arise from allegories and cartesian bicategories. On the other hand, the free algebras for any commutative Moggi monad form an action category. The general correspondence of action calculi and Moggi monads will be worked out in a sequel to this work. Date: Wed, 24 Jul 1996 14:16:45 -0300 (ADT) Subject: Answer book for CTCS, 2nd Ed. Date: Wed, 24 Jul 1996 10:57:36 -0400 From: Michael Barr In the second edition, the answer book was omitted (trying, not with a great deal of success, to hold the price down). We thought it was going to be published separately, but instead the publisher was simply sending a photocopy to all who requested it. All who knew to request it, in fact. So with their permission, we have posted it. On triples, it will be in usual place (~ftp/pub/barr) as ctcs.ansbook.[dvi,ps]. [ ,zip,gz]. Michael Date: Wed, 31 Jul 1996 14:56:56 -0300 (ADT) Subject: Answers to "Category Theory for Computing Science" Date: Tue, 30 Jul 1996 12:22:37 -0400 From: Charles Wells We have made the answers to the second edition of "Category Theory for Computing Science" available on the web, in two ways. 1) As Mike Barr already announced, you can get them by anonymous FTP, at triples.math.mcgill.ca in /pub/barr, files ctcs.ansbook.*. These are available in TeX DVI and Postscript formats. 2) You can also get them by webserver, at http://www.cwru.edu/CWRU/Dept/Artsci/math/wells/pub/papers.html#ansbook These are available in DVI, Postscript and Acrobat Reader formats. Charles Wells, Department of Mathematics, Case Western Reserve University 10900 Euclid Avenue, Cleveland, OH 44016-7058. Office phone: 216 368 2893. Math dept phone: 216 368 2880. Fax: 216 368 5163. Home phone: 216 774 1926. Home Page URL: http://www.cwru.edu/CWRU/Dept/Artsci/math/wells/home.html. "Some have said that I cannot sing; but no one will say that I didn't sing." --Florence Foster Jenkins Date: Sun, 18 Aug 1996 11:36:15 -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: Fri, 30 Aug 1996 09:17:54 -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: Mon, 2 Sep 1996 15:55:57 -0300 (ADT) Subject: flexible sheaves Date: Fri, 30 Aug 1996 10:18:54 -0400 (EDT) From: James Stasheff If it hasn't been mentionned here already Carlos Simpson has just posted Flexible sheaves q-alg/9608025 [at http://eprints.math.duke.edu/q-alg/ - RR] 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: Tue, 3 Sep 1996 17:22:30 -0300 (ADT) Subject: Revision of paper on ftp Date: Tue, 3 Sep 1996 16:11:05 -0400 From: Robert A. G. Seely We wish to announce the following (revised) paper now available on triples: CATEGORIES FOR COMPUTATION IN CONTEXT AND UNIFIED LOGIC by R.F. Blute, J.R.B. Cockett, and R.A.G. Seely ABSTRACT In this paper we introduce context categories to provide a framework for computations in context. The structure also provides a basis for developing the categorical proof theory of Girard's unified logic. A key feature of this logic is the separation of sequents into classical and linear zones. These zones may be modelled categorically as a context/computation separation given by a fibration. The perspective leads to an analysis of the exponential structure of linear logic using strength (or context) as the primitive notion. Context is represented by the classical zone on the left of the turnstile in unified logic. To model the classical zone to the right of the turnstile, it is necessary to introduce a notion of cocontext. This results in a fibrational fork over context and cocontext and leads to the notion of a bicontext category. When we add the structure of a weakly distributive category in a suitably fork fibred manner, we obtain a model for a core fragment of unified logic. We describe the sequent calculus for the fragment of unified logic modelled by context categories; cut elimination holds for this fragment. Categorical cut elimination also is valid, but a proof of this fact is deferred to a sequel. REMARKS This is a completely revised version of the paper we announced in February this year. At the suggestion of an anonymous referee, we have dropped all reference to the circuits of the system we originally described, and extended the system to include multiple-conclusions as well as multiple-hypotheses in the sequent calculus, in both the "classical" and "linear" positions. This is the heart of the system LU of Girard, and a recipe is given to allow further extensions. We plan to describe the circuits (proof nets) for the expanded system in a sequel, which will allow shorter and clearer proofs of categorical cut elimination, as well as comparisons with other systems (such as our own weakly distributive categories with storage and Bierman's MELL). Since the original paper contains some material not carried over to the revision - most significantly, the sequent calculus for the single- conclusion logic (the "intuitionist" case), plus the proof circuits for that logic - it remains on the ftp site with a different name and link. FTP and WWW locations: The paper may be found at this URL: ftp://triples.math.mcgill.ca/pub/rags/bang/context1.[dvi,ps].gz (The earlier version is ...context0... at the same place.) You can also get it from my WWW page: http://www.math.mcgill.ca/~rags As you can see from the URL above, the dvi and ps files are gzipped - if you save the files (in binary) format, gunzip them with the command gunzip -- email me if you need help. Rick Blute Robin Cockett Robert Seely ( contact person for ftp help: rags@math.mcgill.ca ) Date: Wed, 4 Sep 1996 14:42:53 -0300 (ADT) Subject: preprint: Minimal Realization in Bicategories of Automata Date: Tue, 3 Sep 1996 17:18:20 -0300 (ADT) From: Bob Rosebrugh This is to announce that the article whose abstract follows is available at ftp://sun1.mta.ca/pub/papers/rosebrugh/mnrl.dvi or from my Web page http://www.mta.ca/~rrosebru/ Regards to all, Bob Rosebrugh ============================================================================== Minimal Realization in Bicategories of Automata R. Rosebrugh, N. Sabadini and R. F. C. Walters The context of this article is the program to develop monoidal bicategories with a feedback operation as an algebra of processes, with applications to concurrency theory. The objective here is to study reachability, minimization and minimal realization in these bicategories. In this setting the automata are 1-cells in contrast with previous studies where they appeared as objects. As a consequence we are able to study the relation of minimization and minimal realization to serial composition of automata using (co)lax (co)monads. We are led to define suitable behaviour categories and prove minimal realization theorems which extend classical results. Date: Wed, 4 Sep 1996 14:44:53 -0300 (ADT) Subject: preprints available Date: Wed, 4 Sep 1996 16:00:06 +0200 (MET DST) From: koslowj@iti.cs.tu-bs.de I've finally given in and created a home page: http://www.iti.cs.tu-bs.de/TI-INFO/koslowj/koslowski.html Two recent preprints of interest are: - A convenient category for games and interaction (15 pages) (Workshop Domains II, Braunschweig, May 1996 and PSSL 61, Dunkerque, June 1996) - Monads and Interpolads in bicategories (29 pages, uses string diagrams) (CT95, Halifax, July 1995 and in much revised form Sussex, July 1996) Other papers will be added in the next few weeks. The abstracts follow below: %% Abstract for: A convenient category for games and interaction We present a simple construction of an order-enriched category gam that simultaneously dualizes and parallels the familiar construction of the category rel of relations. Objects of gam are sets, and arrows are games, viewed as special kinds of trees. The quest for identities for the composition of trees naturally leads to the consideration of alternating sequences and games of a specific polarity. gam may be viewed as a canonical extension of rel , and just as for rel , the maps in gam admit a nice charactrization. Disjoint union of sets induces a special tensor product on gam that allows us to recover the monoidal closed category of games and strategies of interest in game theory. If we allow games with explicit delay moves, the categorical description of the structure that leads to the monoidal closed category is even more satisfying. In particular, we then obtain an explicit involution. %% Abstract for: Monads and interpolads in bicategories Monads may be viewed as lax functors from the terminal category into a bicategory. If the target has local stable coequalizers, monads together with lax functors from the two-element chain, here called m-modules, can be organized into another bicategory, through which every lax functor into the original one factors. M-modules are special cases of modules between endo-1-cells, which behave well with respect to composition, but in general fail to have identities. To overcome this problem, we do not need to impose the full structure of a monad on the endo-1-cells, an associative coequalizing operation suffices. The bicategory of these so-called interpolads together with structure-preserving modules is Cauchy-complete, and contains the bicategory of monads as a usually non-full sub-bicategory. If we start from a bicategory that has all right liftings, modules in general, and the bicategories of interpolads and of monads in particular, inherit this property, provided the hom-categories of the base have equalizers. While interpolads over rel are just idempotent relations, over the suspension of set they correspond to interpolative semi-groups, and over spn they lead to a notion of ``category without identities'', also known as a taxonomy. -- J\"urgen Koslowski % Stupidity is the basic building block ITI % of the universe. TU Braunschweig % koslowj@iti.cs.tu-bs.de % (Frank Zappa) Date: Thu, 5 Sep 1996 14:11:33 -0300 (ADT) Subject: Correction to paper - distributive is not weakly distributive Date: Tue, 3 Sep 1996 16:13:35 -0400 From: Robert A. G. Seely The following notice and discussion amplifies some recent remarks made by Robin Cockett on the CATEGORIES list. We wish to announce a correction to a statement in the paper Weakly distributive categories by J.R.B. Cockett and R.A.G. Seely An error in Proposition 3.1, where we claimed that distributive categories are weakly distributive, was found in proof. The result is totally incorrect: a distributive category is a cartesian weakly distributive category if and only if it a preorder. (Note: a weakly distributive category may be cartesian - by which we just mean the tensor and cotensor ("par") are cartesian product and coproduct respectively - without being a preorder; it is the distributivity that causes the collapse.) In particular, any distributive category which satisfies equation (13): \delta^R_R (A+B)x(C+D) ------------> A+(Bx(C+D)) | | \delta^L_L | | v | ((A+B)xC)+D | 1 + \delta^L_L | | \delta^R_R + 1 | | v a v (A+(BxC))+D ------------> A+((BxC)+D) (where we write x for the tensor, + for the cotensor (par), and 1 for identity) for the choice of weak distributions described in the paper is immediately a preorder. This because in that diagram if A=D=1 and B=C=0 then, up to equivalence, we obtain for the two sides of diagram the coproduct embeddings of 1 into 1+1. This suffices to cause collapse. The argument can be modified to show that in any distributive category which is simultaneously weakly distributive (no matter how the weak distributions are defined), Boolean negation must have a fixed point. This also suffices to cause collapse. A consequence of this observation is that the categorical proof theory of not-necessarily-intuitionist AND/OR logic is somewhat subtle. In the absence of any connective for implication, there is no apparent a priori reason not to have multiple-conclusion sequents; let's see what this yields. We start with the premise that a good semantics for AND/OR logic ought to be a polycategory; in particular, that the morphisms interpreting the following two derivations must be equal. (That these are equal is a consequence of the polycategory definition, but you can judge them on their own merits if you like. This type of permutation of cuts is pretty standard, and categorical cut elimination then would demand that they be equal.) (Notation: I use -> for the sequent turnstile, and x and + for AND and OR. The interpretation of the commas is, as is usual in such logics, AND on the left and OR on the right, so there are evident identity maps representing A,B -> AxB and A+B -> A,B. All deduction steps are cuts. The cut rule is XX,A -> YY and WW -> A,UU entail XX,WW -> YY,UU and variants via exchange.) B,C -> BxC A+B -> A,B ------------------------- A+B,C -> A,BxC C+D -> C,D -------------------------------- A+B,C+D -> A,BxC,D B,C -> BxC C+D -> C,D ------------------------- = B,C+D -> BxC,D A+B -> A,B -------------------------------- A+B,C+D -> A,BxC,D But here's the catch - with the obvious interpretation, these come out different in SETS: think of the image of a pair in (A+B)x(C+D), where a \in A and d \in D. For the top map, this is mapped to a, whereas for the bottom map it is mapped to d. This is just our equation (13) again, so the point of our initial comment is that in any distributive category, with any interpretation, these two maps are equal iff the category is a preorder. This is a pretty "stripped down" example - it seems that categorical cut elimination is inconsistent with using distributive categories for AND/OR logic and general sequents. This problem is averted of course if one restricts oneself to "intuitionist" sequents (with the right of the turnstile restricted to single formulas), but then this result may be seen as indicating how the folkloric result concerning the collapse of categorical proof theory for classical logic (Joyal) doesn't really depend on very much structure - note that we have assumed no structure rules beyond cut, and the linear versions of the AND/OR sequent rules; the collapse just needs multiple-conclusion sequents and distributivity. It is interesting to note, however, that by carefully choosing the weak distributions one can construct a cartesian weakly distributive category from an elementary distributive category by simply passing to the Kleisli category of the ``exception monad'' E(X) = X+1. So, for example, although SETS is not weakly distributive itself, POINTED_SETS is. The error means, of course, that all discussion in the paper of non-posetal distributive categories as examples of weakly distributive categories must be discounted. This mainly affects the Introduction and Section 3, where Proposition 3.1 must be restated as indicated above, and the surrounding text must take this restatement into account. In particular, Theorem 3.3, although still correct, ought to be stengthened to state that a cartesian weakly distributive category is a preorder if and only if it has a strict initial object. A version of this paper which contains a rewritten Introduction and Section 3 may be found on rags' WWW home page at this URL: . These comments will also appear in the published version of the paper (to appear in JPAA). Finally, the inevitable controversy about terminology: we have decided to continue calling these categories "weakly distributive", since we have done so for so long and in so many places. Besides, Hyland and dePaiva had arrived at the same name for the "weak distributivities", independently, and at the same time. But we keep an open mind about these matters: if another name seems to have near-universal approval, we will adopt it too. The most promising seems to be Barr's suggestion of "linearly distributive". Indeed, had that suggestion been made in 1991, we might have adopted it then (it certainly beats "dissociative categories"!) Robin Cockett Robert Seely (for ftp help: rags@math.mcgill.ca) Date: Mon, 9 Sep 1996 11:25:43 -0300 (ADT) Subject: Change of address, paper Date: Sun, 8 Sep 1996 9:20:29 GMT From: MHEBERT@acs.auc.eun.eg Here is the abstract of a paper recently accepted in JPAA, available on request (by mail): Purity and injectivity in accessible categories Michel Hebert Abstract. We introduce a strenghtening of the concept of purity which may be more appropriate in the context of accessible categories (and which we prove to be equivalent to the usual one in locally presentable categories). We then use it to obtain a characterization of (cone-) injectivity classes which, in particular, provides a solution to the corresponding problem of L.Fuchs(in the context of Abelian Groups) which avoids the set-theoretic assumptions of the Adamek-Rosicky solution. Please note that I have also a (slightly modified) new e-mail address: mhebert@acs.auc.eun.eg Michel Hebert Date: Mon, 9 Sep 1996 11:24:46 -0300 (ADT) Subject: Noncommutative Full Completeness: paper available Date: Sat, 7 Sep 1996 14:02:37 -0400 From: Phil Scott The following paper is available by anonymous ftp from the sites: triples.math.mcgill.ca in directory pub/blute theory.doc.ic.ac.uk in directory theory/papers/Scott Both A4 and North American sized versions are given in gzipped form as shufA4.ps.gz and shuf.ps.gz. Of course, anyone having problems can contact either of the authors at the email addresses below. ---------------------------------------------------------------------- The Shuffle Hopf Algebra and Noncommutative Full Completeness by R.F. Blute and P.J. Scott email: rblute@mathstat.uottawa.ca, phil@csi.uottawa.ca ABSTRACT We present a full completeness theorem for the multiplicative fragment of a variant of noncommutative linear logic known as cyclic linear logic (CyLL), first defined by Yetter. The semantics is obtained by considering dinatural transformations on a category of topological vector spaces which are equivariant under certain actions of a noncocommutative Hopf algebra, called the shuffle algebra. Multiplicative sequents are assigned a vector space of such dinaturals, and we show that the space has the denotations of cut-free proofs in CyLL+MIX as a basis. This can be viewed as a fully faithful representation of a free *-autonomous category, canonically enriched over vector spaces. This work is a natural extension of the authors' previous work, ``Linear Lauchli Semantics'', where a similar theorem is obtained for the commutative logic. In that paper, we consider dinaturals which are invariant under certain actions of the additive group of integers. We also present here a simplification of that work by showing that the invariance criterion is actually a consequence of dinaturality. The passage from groups to Hopf algebras corresponds to the passage from commutative to noncommutative logic. Date: Wed, 18 Sep 1996 11:55:55 -0300 (ADT) Subject: papers available by ftp Date: Wed, 18 Sep 1996 13:45:24 +0200 (MET DST) From: Jiri Rosicky My recent papers are available through anonymous ftp at ftp.math.muni.cz in the directory /pub/math/people/Rosicky/papers Jiri Rosicky Date: Wed, 25 Sep 1996 10:39:29 -0300 (ADT) Subject: Announcement of paper: FILL Date: Tue, 24 Sep 1996 13:00:00 -0400 From: Robert A. G. Seely We wish to announce the following paper made available for ftp on our WWW site. Proof theory for full intuitionistic linear logic, bilinear logic, and mix categories by J.R.B. Cockett and R.A.G. Seely ABSTRACT This note is a survey of techniques we have used in studying coherence for monoidal categories with two tensors, corresponding to the tensor - par fragment of linear logic. We apply these ideas to several situations which extend our previous work, in particular, the Full Intuitionistic Linear Logic (FILL) of Hyland and de Paiva, and the Bilinear Logic of Lambek. Note that the latter is a noncommutative logic; we also consider the noncommutative version of FILL. We show that the essential difference between FILL and multiplicative linear logic lies in making a tensorial strength natural transformation an isomorphism. We briefly discuss the structure of the nucleus of a category modelling FILL: the nucleus is a *-autonomous full subcategory. In addition, we define and study the appropriate categorical structure corresponding to the mix rule. For all these structures, we do not restrict consideration to ``pure'' logic, in that we allow for the inclusion of non-logical axioms. We define the appropriate notion of proof nets for these logics, and use them to describe coherence results for the corresponding categorical structures. We would draw your attention to the following "highlights": - we develop proof nets for FILL (as well as bilinear logic - but this latter is shown equivalent to the system of non-commutative *-autonomous categories we studied in an earlier paper [BCST], so that is not new). - we show several equivalent formulations of bilinear logic = non-commutative $*$-autonomous categories. One interesting one is that if one requires of a FILL category that a natural transformation equivalent to the tensorial strength given by the weak distributivity is isomorphic, then you get the full bilinear logic. - we introduce a generalisation of the notion of "nuclear map" suitable for weakly distributive categories, and show the nucleus of a FILL category is *-autonomous. - we give a rigorous definition of what it means for a category to satisfy the MIX rule (previous attempts dealt only with the existence of the required maps, and not the necessary coherence also needed), and prove a coherence theorem for this doctrine. - these last two points are linked by the observation that a weakly distributive category satisfies MIX iff its nucleus does. As a consequence we note that "cartesian" weakly distributive categories (where the tensor is cartesian product) must satisfy MIX. The paper is available by ftp at the URL or as well as on the home page For assistance with ftp, please contact rags@math.mcgill.ca. Robin Cockett Robert Seely Date: Thu, 10 Oct 1996 21:59:00 -0300 (ADT) Subject: New paper Date: Thu, 10 Oct 1996 10:56:10 GMT From: MHEBERT@acs.auc.eun.eg Here is the abstract of a paper recently accepted in Annals of Pure and Applied Logic, available on request (by mail): Syntactic characterization of closure under pullbacks and of locally polypresentable categories Michel Hebert Abstract: We give syntactic characterizations of (1): the (finitary) theories whose categories of models are closed under the formation of pullbacks, and of (2) (its categorical counterpart): the locally omega-polypresentable categories. A somewhat typical example is the category of algebraically closed fields. Case (1) is proved by classical model-theoretic methods; it solves a problem raised by H. Volger (with motivations from the theory of abstract data types). The solution of case (2) is in the spirit of the ones for the locally omega-presentable and omega-multipresentable cases found by M. Coste and P.T. Johnstone respectively. The problem (2) was raised in the context of Domain Theory by F. Lamarche. This implies in particular the (maybe already known) fact that a (finitary) theory invariant under pullbacks has its category of models omega-accessible. We give an example showing that this is false for equalizers. (Note: The paper was written (and submitted) more than 3 years ago) Michel Hebert Date: Wed, 16 Oct 1996 11:59:13 -0300 (ADT) Subject: PREPRINTS AVAILABLE Date: Wed, 16 Oct 1996 11:09:57 +0200 From: I. Moerdijk I would like to announce that ps-files for the following two recent preprints are available from 1. I. Moerdijk, Proof of a Conjecture of A. Haefliger. [Summary: It is proved that for any etale topological groupoid G, and any abelian G-sheaf A, there is a natural isomorphism H*(G,A) = H*(BG,A') for the associated sheaf A' on the classifying space.] 2. C. Butz, I. Moerdijk, Topological representation of sheaf cohomology of sites. [Summary: We construct for each topos T with enough points a topological space X(T) and a morphism p from the topos of sheaves on X(T) to T which is acyclic, i.e. induces a full embedding of derived categories from D(T) into D(X(T)).] ---------------------------------------- Date: Wed, 16 Oct 1996 12:01:28 -0300 (ADT) Subject: New Paper Available Date: Wed, 16 Oct 1996 08:34:46 -0400 From: Phil Scott The following paper is available by anonymous ftp from the following sites: theory/doc/ic.ac.uk in directory theory/papers/Scott Homepage of P. Dybjer: http://www.cs.chalmers.se/~peterd Homepage of P.J.Scott: http://www.csi.uottawa.ca/~phil/extra/papers ======================================================================= Normalization and the Yoneda Embedding by Djordje Cubric, Peter Dybjer, and Philip Scott We show how to solve the word problem for simply typed \lambda\beta\eta-calculus by using a few well-known facts about categories of presheaves and the Yoneda embedding. The formal setting for these results is $\cP$-category theory, a version of ordinary category theory where each hom-set is equipped with a partial equivalence relation. The part of $\cP$-category theory we develop here is constructive and thus permits extraction of programs. It is this intuitionistic aspect of our work which is fundamental to obtaining a normalization algorithm. In a certain sense, our program is dual to J. Lambek's original goal of categorical proof theory, in which he used cut-elimination to study categorical coherence problems. Here, we use a method inspired from categorical coherence proofs to normalize lambda terms (and thus intuitionistic proofs). It is important to stress that in our method, we make no use of traditional proof-theoretic or rewriting techniques. Date: Mon, 21 Oct 1996 11:51:34 -0300 (ADT) Subject: preprint Date: Mon, 21 Oct 1996 12:02:57 +0100 From: Till Plewe The following preprint (abstract see below) is now available either via ftp at theory.doc.ic.ac.uk as papers/Plewe/LocQuot.ps.gz or LocQuot.dvi.gz or at my home page http://theory.doc.ic.ac.uk/~tp5/index.html ------------------------------------------------------------------------------- "Quotient maps of locales" This paper considers the question of how to characterize regular epis in the category Loc of locales. The most interesting results are that regular epis don't compose in Loc, and that not all closed surjections are regular epis, although those with subfit domain (= all open sublocales are joins of closed sublocales) are. The paper also contains a characterization of regular epis in Loc and several examples which indicate that it is unlikely that there is a characterization similar to the characterization of regular epis in the category of topological spaces as quotient maps. Date: Wed, 30 Oct 1996 13:46:57 -0400 (AST) Subject: Preprints on axiomatic and synthetic domain theory. Date: Wed, 30 Oct 1996 16:45:09 GMT From: Marcelo Fiore The following papers are available from http://www.dcs.ed.ac.uk/home/mf/ =============================================================================== File: SDT-models.dvi or .ps Two Models of Synthetic Domain Theory (by Fiore and Rosolini) Two models of synthetic domain theory encompassing traditional categories of domains are introduced. First, we present a Grothendieck topos embedding the category \omega-Cpo of \omega-complete posets and \omega-continuous functions as a reflective exponential ideal. Second, we obtain analogous results with respect to a category of domains and stable functions. =============================================================================== File: ADT_and_SDT.dvi or .ps An Extension of Models of Axiomatic Domain Theory to Models of Synthetic Domain Theory (by Fiore and Plotkin) We relate certain models of Axiomatic Domain Theory (ADT) and Synthetic Domain Theory (SDT). On the one hand, we introduce a class of non-elementary models of SDT and show that the domains in them yield models of ADT. On the other hand, for each model of ADT in a wide class we construct a model of SDT such that the domains in it provide a model of ADT which conservatively extends the original model. =============================================================================== Date: Wed, 30 Oct 1996 13:46:10 -0400 (AST) Subject: Preprint (announcement) Date: Wed, 30 Oct 1996 13:57:32 +0100 From: Anders Kock Anders Kock: "The maximal atlas of a foliation". This is my contribution to the 62. PSSL that has just been held. It corrects the attempt I made in 1987 (in "Generalized Fibre Bundles") to describe the holonomy groupoid of a foliation F in canonical terms, using the pregroupoid structure on the maximal atlas for F (meaning the set of all F-distinguished germs). The preprint is at ftp://ftp.mi.aau.dk/pub/kock/atlas.ps and the size is about 120 kb. Date: Fri, 13 Dec 1996 16:06:58 -0400 (AST) Subject: preprint available Date: Fri, 13 Dec 1996 10:46:36 +0100 From: Marco Grandis The following hard-copy preprint is available M. Grandis, Variables and weak limits in categories and homotopy categories, Dip. Mat. Univ. Genova, Preprint 329 (1996). Regards, Marco Grandis Abstract. Variables in a category X are introduced, extending subobjects. Variables are well related to weak limits, as subobjects to limits; and they may be viewed as a replacement of subobjects in categories just possessing weak limits, typically homotopy categories. From a formal point of view, the Freyd embedding X --> FrX (introduced to embed the stable homotopy category of spaces into an abelian category, in Freyd, "Stable homotopy", La Jolla) allows one to reduce variables in X to distinguished subobjects in FrX (with respect to a canonical factorisation structure) and, loosely speaking, weak limits to limits. Thus, "homotopy variables" for a space X, with respect to the homotopy category HoTop, form a lattice Fib(X) of types of fibrations over X, which can be identified to the lattice of distinguished subobjects of X in Fr(HoTop). Concretely, we give here various instances of the classification of variables within finitely generated abelian groups, as a first step towards a general classification of such variables, and of homotopy variables for spaces having the homotopy type of a CW-complex. [From the Introduction: A (categorical) *variable* of an object A is an equivalence-class of morphisms with values in A, where x: X -- > A corresponds to y: Y -- > A iff there exist maps u, v such that x = yu, y = xv. Among them, the *monic* variables (having some representative which is so) can be identified to subobjects. As a motivation for the name, a morphism x: X --> A is commonly viewed within category theory as a "variable element" of A, parametrised over X.] Date: Sun, 2 Feb 1997 14:03:15 -0400 (AST) Subject: Manuscript Date: Sun, 2 Feb 1997 17:11:05 GMT From: MHEBERT@acs.auc.eun.eg Here is an Abstract of a manuscript recently submitted, and available on request. Part of it was presented at the last summer Sussex Category Meeting. On generation and implicit partial operations in locally presentable categories Michel Hebert (The American University in Cairo, Cairo, Egypt) Abstract. In a locally a-presentable category C, seen as a category of a-ary S-sorted structures, we describe the subobjects (resp. the regular, strong subobjects) generated by a subset, first in terms of closure under specific types of implicit partial operations (IPO), and then in syntactic terms, using variations on the concept of dominion. This extends previous results from [Hebert, Can. J.Math 93]. The domain of definition of an IPO of arity s ->s is a subfunctor V >--> U(s) of the appropriate forgetful functor, and each limit-closed domain V determines, in a natural way, a structure P(V) in C having as its elements of sort s the (s->s)-ary IPO's with domain V (This generalizes the fact that the elements of sort s of the free structure F(s) can be seen as the (s->s)-ary implicit total operations in C). The P(V)'s for subobject-closed V >--> Us with | s | < a are precisely the a-generated objects (in the sense of Gabriel-Ulmer) of C. Finally we use IPO's to give a characterization of the so-called a-retractions, which parallels the known syntactic characterization of a-pure morphisms. The point of view adopted in this paper is the one of the algebraist or model-theorist wishing to use the tools of category theory without making radical changes in the concrete description of his/her favourite structures (in particular without modifying the type). A part of the paper deals with the translation problems which arise. Date: Wed, 19 Feb 1997 11:52:46 -0400 (AST) Subject: revised paper available Date: Wed, 19 Feb 1997 12:17:32 +0100 (MET) From: koslowj@iti.cs.tu-bs.de Hello, A revised version of my article "A convenient category for games and interaction" is available from my home page http://www.iti.cs.tu-bs.de/TI-INFO/koslowj/koslowski.html It better substantiates my claim of last year's workshop Domains II here in Braunschweig that the composition of games I introduced is orthogonal to the established composition of strategies. The abstract is appended at the end. If you had trouble in the past reaching my home page, we did find a faulty entry in a name server last Fall. If the problems persist, please let me know! -- J"urgen %% Abstract for: A convenient category for games and interaction Guided by the familiar construction of the category rel of relations, we first construct an order-enriched category gam . Objects are sets, and 1-cells are games, viewed as special kinds of trees. The quest for identities for the composition of arbitrary trees naturally suggests alternating trees of a specific orientation. Disjoint union of sets induces a tensor product $\otimes$ and an operation --o on gam that allow us to recover the monoidal closed category of games and strategies of interest in game theory. Since gam does not have enough maps, \ie, left adjoint 1-cells, these operations do not have nice intrinsic descriptions in gam . This leads us to consider games with explicit delay moves. To obtain the ``projection'' maps lacking in gam , we consider the Kleisli-category K induced by the functor _+1 on the category of maps in gam . Then we extend gam as to have K as category of maps. Now a satisfactory intrinsic description of the tensor product exists, which also allows us to express --o in terms of simpler operations. This construction makes clear why $\multimap$, the key to the notion of strategy, cannot be functorial on gam . Nevertheless, the composition of games may be viewed as orthogonal to the familiar composition of strategies in a common framework. -- J"urgen Koslowski % If I don't see you no more in this world ITI % I meet you in the next world TU Braunschweig % and don't be late! koslowj@iti.cs.tu-bs.de % Jimi Hendrix (Voodoo Child) Date: Fri, 21 Feb 1997 12:28:11 -0400 (AST) Subject: Locales as "topology-free spaces" Date: Fri, 21 Feb 1997 11:34:36 +0000 From: Steve Vickers I am making two papers available as Departmental Research Reports: "Topical Categories of Domains" "Localic Completion of Quasimetric Spaces" Both explore the idea of locales (and, indeed, toposes) as "topology-free spaces". The technique is to work not with frames (point-free topologies) but with presentations of them, understood as propositional geometric theories whose models are the points. (But it is normally more convenient to work with equivalent predicate theories.) Then - * the geometric theory already determines an implicit topology on its models; * any construction of models of one theory out of models of another automatically determines a continuous map (or geometric morphism), just so long as the construction is geometric. In effect, a restriction to geometric mathematics removes the need to treat topology explicitly, hence "topology-free spaces". Apparently, explicit topology is needed to correct the over-credulousness of classical reasoning principles, though in practice the geometric constraints often end up forcing one to reintroduce the normal topological arguments in a different guise. The two papers test the applicability of the idea in the two areas of domain theory and quasimetric spaces. Aside from the "topology-free space" aspects, the papers develop some new results: "Topical Categories of Domains" addresses categorical domain theory and replaces the usual classes of objects and morphisms by toposes classifying them. New general results concerning fixpoints of endo-geometric-morphisms of toposes exploit their intrinsically topological nature to give a simple approach to the solution of domain equations. The paper also gives a summary of the constructive theory of Kuratowski finite sets and establishes some limitations to the Cartesian closedness of Sets. "Localic Completion of Quasimetric Spaces" proposes a construction of locales in completion of quasimetric spaces (using ideas of flatness deriving from Lawvere's enriched category account), studies the powerlocales and shows that a limit map from a locale of Cauchy sequences to the completion is triquotient in the sense of Plewe. Paper copies are available from me; electronic copies are expected to be available shortly in the Department of Computing's Research Report series coordinated by Frank Kriwaczek (frk@doc.ic.ac.uk). Steve Vickers. Date: Thu, 10 Apr 1997 16:34:46 -0300 (ADT) Subject: Preprint available. The following preprint is available at http://www.dcs.ed.ac.uk/home/mf/ADT/ as cub.dvi and cub.ps. Best, Marcelo. Complete Cuboidal Sets in Axiomatic Domain Theory Marcelo Fiore Gordon Plotkin John Power Department of Computer Science Laboratory for Foundations of Computer Science University of Edinburgh, The King's Buildings Edinburgh EH9 3JZ, Scotland Synopsis We study the enrichment of models of axiomatic domain theory. To this end, we introduce a new and broader notion of domain, viz. that of complete cuboidal set, that complies with the axiomatic requirements. We show that the category of complete cuboidal sets provides a general notion of enrichment for a wide class of axiomatic domain-theoretic structures. Cuboidal sets play a role similar to that played by posets in the traditional setting. They are the analogue of simplicial sets but with the simplicial category enlarged to the cuboidal category of cuboids, i.e. of finite products O_n1 x ... x O_ni of finite ordinals. These cuboids are the possible shapes of paths. A cuboidal set P has a set P(C) of paths of every shape C = n1 x ... x ni; indeed, it is a (rooted) presheaf over the cuboidal category. The set of points of P is P(O_1). The set of (one-dimensional) paths of length n is P(O_n+1); they can be thought of as (linear) computations conditional on the occurrence of n linearly ordered events e_1 < ... < e_n. Evidently, O_n is the partial order associated to this simple linear event structure, and can be considered as a sequential process of length n. At higher dimensions, P(O_n1 x ... x O_ni) can be thought of as the set of computations conditional on the occurrence of n_1 + ... + n_i events ordered by e_1,1 < ... < e_1,n1 ; ... ; e_i,1 < ... < e_i,ni. This is the event structure which can be considered as i sequential processes, of respective lengths O_n1, ..., O_ni, running concurrently. Complete cuboidal sets are cuboidal sets equipped with a formal-lub operator satisfying three algebraic laws, which are exactly those needed of the lub operator in order to prove the fixed-point theorem. Computationally, the passage from cuboidal sets to complete cuboidal sets corresponds to allowing infinite processes. In fact, the formal-lub operator assigns paths of shape C to `paths of shape C x omega', for every C. Here the set of paths of shape C x omega is the colimit of the paths of shape C x O_n; such paths can be thought of as the higher-dimensional analogue of the increasing sequences of traditional domain theory. Date: Sat, 12 Apr 1997 16:01:26 -0300 (ADT) Subject: new preprint available Date: Sat, 12 Apr 97 16:40:29 +1000 From: Max Kelly A LaTeX preprint of the paper "On the monadicity over graphs of categories with limits", by G.M. Kelly and I.J. Le Creurer, and to appear in Cahiers de Topologie et Ge'om. Diff. Cate'goriques, is in our public site sydcat at maths.usyd.edu.au (=129.78.68.2), in the directory sydcat/papers/kelly, as the file named monograph.tex . I presume I already announced another comparatively-recent preprint there: to wit, the file jk.tex contains "The Reflectiveness of Covering Morphisms in Algebra and Geometry", by G. Janelidze and G.M. Kelly, which is still with the referee. Max Kelly. Date: Wed, 16 Apr 1997 17:21:16 -0300 (ADT) Subject: protected files Date: Mon, 14 Apr 97 15:20:49 +1000 From: Max Kelly Several readers have pointed out that the new files monograph.tex and jk.tex, whose availability on our site sydcat I announced the other day were protected; this oversight has now been corrected, Max Kelly. Date: Thu, 24 Apr 1997 15:26:59 -0300 (ADT) Subject: preprint available Date: Tue, 22 Apr 1997 21:26:04 +0200 (METDST) From: Anders Kock The article: "Geometric Construction of the Levi-Civita Parallelism" by Anders Kock is available from ftp://ftp.mi.aau.dk/pub/kock/parallel.ps (about 150 kb). (The Levi-Civita Parallellism is also called the Riemannian Connection; it is the unique symmetric affine connection compatible with a given Riemannian metric. We present a geometric construction of it, using variational principles and synthetic differential geometry.) Date: Thu, 24 Apr 1997 15:29:45 -0300 (ADT) Subject: Notes of two lectures Date: Thu, 24 Apr 1997 15:37:19 +1100 From: Ross Street This is to announce the placement on the WWW of the notes of my two lectures at the Conference on Higher Category Theory and Mathematical Physics, Northwestern University (Evanston, Illinois; 28-30 March 1997). The site is: [I have tried to eliminate offending fonts and to accommodate funny US paper size. Thanks to Sjoerd Crans for helping here.] Title: The role of Michael Batanin's monoidal globular categories Lecture I: Globular categories and trees Lecture II: Higher operads and weak omega-categories This is a report on recent work of Michael Batanin. The goal of his work is to provide an environment for defining the concepts associated with weak omega-categories and for developing the ensuing theory. The approach is "globular". To put this in context, I might mention some important steps in the development of weak omega-categories. Categories were defined by Eilenberg-Mac Lane in 1945. Monoidal and symmetric monoidal categories were defined by Mac Lane in 1963. Ehresmann defined (strict) n-categories in 1966. Bénabou defined bicategories in 1967. In the early 80s, monoidal bicategories were in the air but a full definition was not published in that period. Joyal-Street defined braided monoidal categories in 1985. Gordon-Power-Street defined tricategories in 1991 (this, and the coherence theorem, were published in 1995). Braided monoidal categories were defined by Kapranov-Voevodsky-Baez-Neuchl-Breen around 1993. Trimble produced a definition of tetracategory in 1995. Diverse approaches to weak n-categories for all n have appeared. Street (1985) suggested a simplicial definition with horn filler conditions. Trimble (1994) approached the problem using operads and Stasheff associahedra. Baez-Dolan (1995) have a definition using typed operads and opetopes. Tamsamani (1996) gave a multisimplicial definition. Batanin uses higher operads and globular sets. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Ross Street email: street@mpce.mq.edu.au Mathematics Department phone: +612 9850 8921 Macquarie University fax: +612 9850 8114 Sydney, NSW 2109 Australia Internet: http://www.mpce.mq.edu.au/~street/ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Date: Mon, 28 Apr 1997 07:29:10 -0300 (ADT) Subject: weak \omega-categories Date: Fri, 25 Apr 1997 14:56:43 +1100 From: Olga Batanin The preprint version of my paper "Monoidal globular categories as a natural environment for the theory of weak n-categories" is now available. The dvi file is at http://www-math.mpce.mq.edu.au/~mbatanin/coh0.dvi Please, contact me if you have any difficulties with printing it out. I can mail hard copies. Michael Batanin. Abstract. The paper is devoted to the problem of defining weak $\omega$-categories. The definition presented here is based on a nontrivial generalization of the apparatus of operads and their algebras, originally developed by P.May \cite{May} for the needs of algebraic topology. Yet, for the purposes of higher order category theory, a higher dimensional notion of operad is required. Briefly, the idea of a higher operad may be explained as follows. An ordinary non-symmetric operad in $Set$ associates a set $A_{n}$ to every integer $n$. The set of integers may be interpreted as the set of $1$-cells in the free category generated by one object and one nonidentity endomorphism of this object. To find a higher order generalization of the notion of operad we have to describe the free strict $\omega$-category generated by one object and one nonidentity endomorphism of this object and one nonidentity endomorphism of this endomorphism and so on (so, for example, the set of integers is the one-dimensional part of this category). The required $\omega$-category $Tr$ will be the category of planar trees of a special type. The $k$-th composition of cells will be given by the colimit of the diagram of trees over a special tree $M_{n}^{k}$. The other component of the theory of operads is an appropriate monoidal category (with some extrastructure like braiding or symmetry) where one can consider the notion of operad. We need also a monoidal category (perhaps, with extrastructure as well) where one can define the notion of algebra for an operad. Finally, the corresponding coherence theorems for both types of monoidal categories are required. I call all these components a natural environment for a given theory of operads. One of my main goals was to find a natural environment for the theory of higher order operads. For this I introduce monoidal globular categories and show they are suitable for the development of the theory of higher order operads. The crucial point here is a coherence theorem for monoidal globular categories (section 4) which includes as special cases the coherence theorems for monoidal, symmetric monoidal, and braided monoidal categories and a sort of pasting theorem for $\omega$-categories. A primary example of a globular monoidal category is the globular category of $n$-spans $Span$. The $0$-spans are just the sets. The $1$-spans are the spans in $Set$ in the usual sense. In some informal sense, an $n$-span is a relation between two $(n-1)$-spans. This globular monoidal category plays the same role for higher-order category theory as the category of sets does for ordinary category theory. These results allow me to formulate the notion of higher order operad. An $\omega$-operad will associate an $n$-span to every $n$-cell in $Tr$ for every $n\ge 0$.} There are also the units and multiplications and some axioms for these operations. The category of non-symmetric operads (in the category of sets) is just a one-dimensional subcategory of the category of $\omega$-operads. Finally, Iintroduce a notion of a contractible $\omega$-operad, So the main definition is: A weak $\omega$-category is a globular set together with the structure of algebra over a universal contractible $\omega$-operad. I construct also a fundamental $n$-groupoid functor from topological spaces to the category of weak $n$categories for all $n$ including $\omega$ and consider another examples of weak $n$-categories, hifger operads and their algebras. Date: Tue, 29 Apr 1997 20:23:53 -0300 (ADT) Subject: weak \omega-categories Date: Tue, 29 Apr 1997 23:13:53 +1000 From: Michael Batanin Some people informed me that they have had the difficulties in printing out the dvi file of my paper "Monoidal globular categories as a natural environment for the theory of weak n-categories" It seems that the following address works better http://www-math.mpce.mq.edu.au/~mbatanin/papers.html You can find here the .ps file of my paper. Michael Batanin. Date: Wed, 30 Apr 1997 20:00:52 -0300 (ADT) Subject: Notes of two lectures Date: Wed, 30 Apr 1997 11:39:29 +1100 From: Ross Street With computers, things we expect to be simple never are! Last week I announced the placement on the WWW of the notes (see the short description below) of my two lectures at the Conference on Higher Category Theory and Mathematical Physics, Northwestern University (Evanston, Illinois; 28-30 March 1997). The site is: I'll spare you the details of the problems, but, up until today, what was at this site was an old version prepared before the conference. This is not what I had intended. I am truly sorry to people who have downloaded that version already. The correct version is NOW at the site. There still seems to be a problem when the document is viewed (by some "ghost" technology) but it does (at least for us) print out pretty well. There is a colour table on page 2 which even seems to view correctly! I am extremely grateful to Ross Moore and Sjoerd Crans for helping me out of the mess I (and my little Mac) created. I invite people who have downloaded the old version to try again; I am really sorry. Title: The role of Michael Batanin's monoidal globular categories Lecture I: Globular categories and trees Lecture II: Higher operads and weak omega-categories This is a report on recent work of Michael Batanin. The goal of his work is to provide an environment for defining the concepts associated with weak omega-categories and for developing the ensuing theory. The approach is "globular". Apart from providing a precise definition of weak omega-category, the work gives a new algebra of planar trees and uses them to define higher operads which I believe will find many other applications. Note that, in the meantime (and again not without trouble!), Michael Batanin has announced his paper containing the full details of this part of his work. It is available at: Happy surfing and enjoy the trees. Ross Date: Thu, 15 May 1997 22:19:05 -0300 (ADT) Subject: An introduction to n-categories Date: Tue, 13 May 1997 17:29:58 -0700 (PDT) From: john baez Here is the abstract of a paper that is now available in Postscript form at: http://math.ucr.edu/home/baez/ncat.ps If downloading it or printing it out is a problem, I can mail copies to people. ---------------------------------------------------------------------- An Introduction to n-Categories John C. Baez An n-category is some sort of algebraic structure consisting of objects, morphisms between objects, 2-morphisms between morphisms, and so on up to n-morphisms, together with various ways of composing them. We survey various concepts of n-category, with an emphasis on `weak' n-categories, in which all rules governing the composition of j-morphisms hold only up to equivalence. (An n-morphism is an equivalence if it is invertible, while a j-morphism for j < n is an equivalence if it is invertible up to a (j+1)-morphism that is an equivalence.) We discuss applications of weak n-categories to various subjects including homotopy theory and topological quantum field theory, and review the definition of weak n-category recently proposed by Dolan and the author. Date: Tue, 3 Jun 1997 11:06:15 -0300 (ADT) Subject: New versions of papers available Date: Mon, 02 Jun 1997 15:18:51 -0400 From: Charles Wells New versions of three papers by Atish Bagchi and myself are available at http://www.cwru.edu/CWRU/Dept/Artsci/math/wells/pub/papers.html The papers are Varieties of Mathematical Prose Graph Based Logic and Sketches I: The General Framework Graph Based Logic and Sketches II: Finite Product Categories and Equational Logic Charles Wells, 105 South Cedar Street, Oberlin, Ohio 44074, USA. EMAIL: cfw2@po.cwru.edu. HOME PHONE: 216 774 1926. FAX: Same as home phone. HOME PAGE: URL http://www.cwru.edu/CWRU/Dept/Artsci/math/wells/home.html "Some have said that I can't sing. But no one will say that I _didn't_ sing." --Florence Foster Jenkins Date: Wed, 11 Jun 1997 11:53:50 -0300 (ADT) Subject: Announcement: paper on linear functors available Date: Wed, 11 Jun 1997 10:13:43 -0400 From: Robert A. G. Seely We wish to announce the availability of the following paper. Linearly distributive functors by J.R.B. Cockett R.A.G. Seely ABSTRACT This paper introduces a notion of "linear functor" between linearly distributive categories that is general enough to account for common structure in linear logic, such as the exponentials (!, ?), and the additives (product, coproduct), and yet when interpreted in the doctrine of *-autonomous categories, gives the familiar notion of monoidal functor. We show that there is a bi-adjunction between the 2--categories of linearly distributive categories and linear functors, and of *-autonomous categories and monoidal functors, given by the construction of the "nucleus" of a linearly distributive category. We develop a calculus of proof nets for linear functors, and show how linearity accounts for the essential structure of the exponentials and the additives. This paper was first presented at a conference held in Montreal in May 1997, in honour of Michael Barr's 60th birthday, and is dedicated to him in celebration of this occasion. ------------------------ The paper may be found at the following URLs or from the WWW home page Contact if there is any problem retrieving this paper. Date: Tue, 1 Jul 1997 15:12:45 -0300 (ADT) Subject: Preprint available Date: Tue, 1 Jul 97 13:38 BST From: Dr. P.T. Johnstone The Pure Mathematics Department of Cambridge University has a new electronic preprint server (accessible via our home page at http://www.pmms.cam.ac.uk). The first preprint available may be of interest to people on the categories mailing list: it is C. Butz and P.T. Johnstone: Classifying toposes for first-order theories Abstract: By a classifying topos for a first-order theory $\Bbb T$, we mean a topos $\cal E$ such that, for any topos $\cal F$, models of $\Bbb T$ in $\cal F$ correspond exactly to open geometric morphisms ${\cal F} \rightarrow{\cal E}$. We show that not every (infinitary) first-order theory has a classifying topos in this sense, but we characterize those which do by an appropriate `smallness condition', and we show that every Grothendieck topos arises as the classifying topos of such a theory. We also show that every first-order theory has a conservative extension to one which possesses a classifying topos, and we obtain a Heyting-valued completeness theorem for infinitary first-order logic. For those who would prefer to receive a hard copy of this paper, I shall be bringing a supply with me to the Vancouver meeting. Peter Johnstone Date: Thu, 3 Jul 1997 22:13:34 -0300 (ADT) Subject: announcement Date: Thu, 3 Jul 1997 20:52:47 -0400 (EDT) From: Michael Makkai The following paper is announced: On weak higher dimensional categories by Claudio Hermida, Michael Makkai and John Power Abstract: Inspired by the concept of opetopic set introduced in a recent paper by John C. Baez and James Dolan, we give a modified notion called multitopic set. The name reflects the fact that, whereas the Baez/Dolan concept is based on operads, the one in this paper is based on multicategories. The concept of multicategory used here is a mild generalization of the same-named notion introduced by Joachim Lambek in 1969. Opetopic sets and multitopic sets are both intended as vehicles for concepts of weak higher dimensional category. Baez and Dolan define weak n-categories as (n+1)-dimensional opetopic sets satisfying certain properties. The version intended here, multitopic n-category, is similarly related to multitopic sets. Multitopic n-categories are not described in the present paper; they are to follow in a sequel. The present paper gives complete details of the definitions and basic properties of the concepts involved in multitopic sets. The category of multitopes, analogs of opetopes of Baez and Dolan, is presented in full, and it is shown that the category of multitopic sets is equivalent to the category of set-valued functors on the category of multitopes. The paper is available by anonymous ftp from triples.math.mcgill.ca in directory pub/makkai, or via the CRTC home page ftp://triples.math.mcgill.ca/crtc.html and click on "Makkai". The paper is in nine files, each with a name starting with `mult`; they are PostScript files. I will send a limited number of hard copies upon request. Michael Makkai Date: Tue, 8 Jul 1997 14:20:18 -0300 (ADT) Subject: announcement of preprint Date: Tue, 8 Jul 1997 16:32:22 +0200 From: I. Moerdijk Dear colleagues, A ps-file of the following short preprint can be picked up from my homepage (http://www.math.ruu.nl/people/moerdijk) I Moerdijk, J. Vermeulen, Proof of a conjecture of A. Pitts. Abstract: Using only elementary properties of inverse limits and localization, we prove the Beck-Chevalley condition for lax pullbacks of coherent toposes. In this way, we obtain a simple and constructive proof of the descent theorem for coherent (pre)toposes. With best regards, Ieke Moerdijk. Date: Tue, 8 Jul 1997 14:18:24 -0300 (ADT) Subject: addendum to announcement Date: Mon, 7 Jul 1997 18:03:49 -0400 (EDT) From: Michael Makkai A couple of days ago I announced the paper "On weak higher dimensional categories" by C. Hermida, M. Makkai and J. Power. Now, I am announcing some small changes of the arrangements concerning the electronic access to the paper. The paper is available by anonymous ftp from triples.math.mcgill.ca in the directory pub/makkai/multitopicsets [so, the change is that now the paper is put into a subdirectory of pub/makkai]. There are ten files [there were nine before; I have cut the largest into two]. M. Makkai Date: Thu, 10 Jul 1997 16:51:01 +0200 (MET DST) Subject: un peu de r'eclame Date: Wed, 9 Jul 1997 18:01:19 +0200 From: Pierre Ageron Let me advertise for some more or less recent work of mine about sketches/accessible categories (not available electronically, but I'll be happy to send reprints or preprints on request). ------- (1) Cat'egories accessibles `a limites projectives non vides et cat'egories accessibles `a limites projectives finies Diagrammes 34 (1995) 1-10 For fixed b, b-accessible categories with non-empty limits are characterized as the categories of models of specific sketches. As a corollary, the category of these categories is Cartesian closed. (Proved independantly by Ad'amek.) Accessible categories with finite limits are also characterized. ------- (2) Effective taxonomies and crossed taxonomies Cahiers de Top. et de G'eom. Diff. Cat. XXXVII (1996) 82-90 A taxonomy is a "category without identities". This bare structure is somewhat dull, but "crossed modules of taxonomies" seem more interesting. In the latter structure, "Dedekind-finite" objects play a role similar to that of finitely presentable objects in a category. A notion similar to that of accessibility can thus be defined. ------- (3) La tour holomorphe d'une esquisse Cahiers de Top. et de G'eom. Diff. Cat. XXXVII (1996) 295-314 A construction of Lair's in the category of sketches is revisited and noticed to specialize to the construction of the holomorph when restricted to groups. The iteration of this construction reveals two invariants of a sketch: an ordinal and a group. Some explicit computations are provided. ------- (4) Cat'egories accessibles `a produits fibr'es (preprint) Continuation of (1). Accessible categories with (finite) pullbacks are characterized in terms of sketches. This is achieved by introducing "free" colimits in Set: such colimits are proved to be exactly those that commute with pullbacks. ------- (5) Limites projectives conditionnelles dans les cat'egories accessibles (preprint) For fixed b, those b-accessible categories s.t. every diagram with a cone has a limit are characterized in terms of sketches. As a corollary, the category of these categories is Cartesian closed. Similarly for those b-accessible categories s.t. every non-empty diagram with a cone has a limit, or for those with "consistent wide pullbacks". ------- PIERRE AGERON 1) coordonnees bureau adresse : mathematiques, Universite de Caen, 14032 Caen Cedex telephone : 02 31 56 57 37 telecopie : 02 31 93 02 53 adresse electronique : ageron@math.unicaen.fr 2) coordonnees domicile adresse : 28 rue de Formigny 14000 Caen telephone : 02 31 84 39 67 Date: Wed, 30 Jul 1997 13:39:54 -0300 (ADT) Subject: Preprint available Date: Wed, 30 Jul 1997 15:51:32 +0200 (MET DST) From: Carsten Butz Dear Colleagues, the ps-file of the following preprint is available at the homepage http://www.brics.dk/~butz : Topological Completeness for Higher-Order Logic by Steve Awodey (awodey@cmu.edu), Carsten Butz (butz@brics.dk). Abstract: Using recent results in topos theory, two systems of higher-order logic are shown to be complete with respect to sheaf models over topological spaces---so-called ``topological semantics''. The first is classical higher-order logic, with relational quantification of finitely high type; the second system is a predicative fragment thereof with quantification over functions between types, but not over arbitrary relations. The second theorem applies to intuitionistic as well as classical logic. Best regards, Steve Awodey and Carsten Butz Date: Wed, 6 Aug 1997 08:47:28 -0300 (ADT) Subject: Preprints available Date: Tue, 5 Aug 1997 17:19:51 -0400 From: Walter Tholen The following two preprints (joint work with George Janelidze) are available as postscript files from my home page at http://www.math.yorku.ca/Who/Faculty/Tholen/menu.html For titles and abstracts, see below. Walter Tholen -------------------------------------------------------------------------- "Functorial Factorization, Well-pointedness and Separabilty" Abstract: A functorial treatment of factorization structures is presented, under extensive use of well-pointed endofunctors. Actually, so-called weak factorization systems are interpreted as pointed lax indexed endofunctors, and this sheds new light on the correspondence between reflective subcategories and factorization systems. The second part of the paper presents two improtant factorization structures in the context of pointed endofunctors: concordant-dissonant and inseparable-sepaprable. "Extended Galois Theory And Dissonant Morphisms" Abstract: For a given Galois structure on a category C and an effective descent morphism p: E --> B in C we describe the category of so-called weakly split objects over (E,p) in terms of internal actions of the Galois (pre)groupoid of (E,p) with an additional structure. We explain that this generates various known results in categorical Galois theory and in particular two results of M. Barr and R. Diaconescu. We also give an elaborate list of examples and applications. Date: Thu, 7 Aug 1997 14:13:07 -0300 (ADT) Subject: preprint Date: Thu, 7 Aug 1997 15:43:23 +1000 From: Michael Batanin The preprint " Finitary monads on globular sets and notions of computad they generate " is available as postscript files at http://www-math.mpce.mq.edu.au/~mbatanin/papers.html Abstract Consider a finitary monad on the category of globular sets. We prove that the category of its algebras is isomorphic to the category of algebras of an appropriate monad on the special category (of computads) constructed from the data of the initial monad. In the case of the free $n$-category monad this definition coincides with R.Street's definition of $n$-computad. In the case of a monad generated by a higher operad this allows us to define a pasting operation in a weak $n$-category. It may be also considered as the first step toward the proof of equivalence of the different definitions of weak $n$-categories. Date: Tue, 2 Sep 1997 09:19:27 -0300 (ADT) Subject: preprint available Date: Mon, 1 Sep 1997 14:47:02 +0200 (MET DST) From: Koslowski Dear Colleagues, An updated preprint of my paper "Beyond the Chu-construction", which I presented in Vancouver in July, is now available on my web-page http://www.iti.cs.tu-bs.de/TI-INFO/koslowj/koslowski.html The abstract follows below. From a symmetric monoidal closed (= autonomous) category Po-Hsiang Chu originally constructed a *-autonomous one, ie, a self-dual autonomous category where the duality is realized by means of a dualizing object. Recently, Michael Barr introduced an extension for the non-symmetric, but closed, case that after an initial step utilized monads and modules between them. Since these tools are well-understood in a bicategorical setting, we introduce a notion of local *-autonomy for closed bicategories that turns out to be inherited by the bicategories of monads and the bicategory of interpolads. Since the first step of Barr's construction carries over directly to the bicategorical setting, we recover his main result as an easy corollary. Furthermore, the Chu-construction at this level may be viewed as a procedure to turn the endo-1-cells of a bicategory into the objects of a new bicategory, and hence is conceptually close to the constructions of bicategories of monads and of interpolads. Best regards, -- J"urgen -- J"urgen Koslowski % If I don't see you no more in this world ITI % I meet you in the next world TU Braunschweig % and don't be late! koslowj@iti.cs.tu-bs.de % Jimi Hendrix (Voodoo Child) Date: Wed, 3 Sep 1997 15:29:23 -0300 (ADT) Subject: preprint available: not yet :-( Date: Tue, 2 Sep 1997 15:19:46 +0200 (MET DST) From: koslowj@iti.cs.tu-bs.de Dear Colleagues, A technical glitch prevents me from puttting the preprint "Beyond the Chu-Construction", announced yesterday, on my web page ("no space on device", which doesn't make sense). I won't be able to fix this until I return from CTCS97 next Sunday, since our technician isn't here right now. Please wait until next Monday or Tuesday before downloading the paper. I'm sorry about this problem. -- J"urgen -- J"urgen Koslowski % If I don't see you no more in this world ITI % I meet you in the next world TU Braunschweig % and don't be late! koslowj@iti.cs.tu-bs.de % Jimi Hendrix (Voodoo Child) Date: Mon, 8 Sep 1997 15:07:16 -0300 (ADT) Subject: For Category Bulletin: New Preprint Date: Mon, 8 Sep 1997 16:27:35 +0100 (BST) From: Ronnie Brown Groupoids and Crossed Objects in Algebraic Topology Ronald Brown Notes for Lectures at the Summer School on the `Foundations of Algebraic Topology', Grenoble, June 14 -July 5, 1997 (71 pages). Abstract: The notes concentrate on the background, intuition, proof and applications of the 2-dimensional Van Kampen Theorem (for the fundamental crossed module of a pair), with sketches of extensions to higher dimensions. One of the points stressed is how the extension from groups to groupoids leads to an extension from the abelian homotopy groups to non abelian higher dimensional generalisations of the fundamental group, as was sought by the topologists of the early part of this century. This links with J.H.C. Whitehead's efforts to extend combinatorial group theory to higher dimensions in terms of combinatorial homotopy theory, and which analogously motivated his simple homotopy theory. Available from http://www.bangor.ac.uk/~mas010/brownpr.html (gzipped postscript). Ronnie Brown Prof R. Brown, School of Mathematics, University of Wales, Bangor Dean St., Bangor, Gwynedd LL57 1UT, United Kingdom Tel. direct:+44 1248 382474|office: 382475 fax: +44 1248 383663 World Wide Web: home page: http://www.bangor.ac.uk/~mas010/ New article: Higher dimensional group theory Symbolic Sculpture and Mathematics: http://www.bangor.ac.uk/SculMath/ Mathematics and Knots: http://www.bangor.ac.uk/ma/CPM/exhibit/welcome.htm Date: Thu, 2 Oct 1997 16:47:17 -0300 (ADT) Subject: resolutions as fractions, space complexity Date: Thu, 2 Oct 1997 12:19:44 -0500 (CDT) From: J. R. Otto Dear People, The following revisions of talks on work in progress may be of interest. From NNO to Complexity (12 pages, October 2, 1997). We begin to revisit space complexity by collapsing resolutions to maps. So we evolve our talk `Presenting LCC Categories by Answering Queries' by stratifying higher order types and allowing alternatives. Presenting LCC Categories by Answering Queries (15 pages, October 1, 1997). We present LCC categories in a manner that provides a basis for logic programming with dependent types and equality. We find that resolutions are left fractions which collapse to the maps. They are linked to http://www.mcs.net/~quant/ . Regards, Jim Otto quant@mcs.com Date: Mon, 13 Oct 1997 09:17:41 -0300 (ADT) Subject: Operads, multicategories Date: Mon, 13 Oct 1997 10:36:43 +0100 (BST) From: Tom Leinster An advertisement for an article, available by electric transmission from http://www.dpmms.cam.ac.uk/~leinster. ABSTRACT Notions of `operad' and `multicategory' abound. This work provides a single framework in which many of these various notions can be expressed. Explicitly: given a monad * on a category S, we define the term (S,*)-multicategory, subject to certain conditions on S and *. Different choices of S and * give some of the existing notions. We then describe the algebras for an (S,*)-multicategory, and finish with a selection of possible further developments. Our approach enable concise descriptions of Baez and Dolan's opetopes and Batanin's operads; both of these are included. Tom Leinster Date: Thu, 16 Oct 1997 16:53:03 -0300 (ADT) Subject: Weak higher dimensional categories Date: Thu, 16 Oct 1997 10:13:07 +0100 From: ajp@dcs.ed.ac.uk Those people interested in Tom Leinster's paper on multicategories and weak higher dimensional categories might also be interested in recent, closely related work by Claudio Hermida at McGill. I do not think there is a paper available yet, but he has given talks at Vancouver and at the recent meeting of the Canadian Math Society in Montreal, so there are probably slides available. Date: Sun, 9 Nov 1997 14:21:08 -0400 (AST) Subject: higher-dimensional multicategories and weak n-categories Date: Fri, 7 Nov 1997 17:45:34 +0000 (GMT) From: Claudio Hermida Dear all, I've just finished scanning the slides of my talks at CT97 (Vancouver) and the AMS meeting at Montreal on Higher-dimensional multicategories aimed as a set up for weak n-categories in the Baez/Dolan sense, ie. using universally defined composites to avoid coherence conditions. The slides are a series of .JPG files accessible through my web page http://www.math.mcgill.ca/~hermida Claudio Hermida Date: Thu, 13 Nov 1997 15:56:31 -0400 (AST) Subject: preprints available Date: Wed, 12 Nov 1997 14:16:30 +0100 (MET) From: Anders Kock The following preprints are available: Differential Forms as Infinitesimal Cochains This is essentially my contribution at the Vancvouver Category Theory Meeting in July. It proves that the simplicial complex given by the first neighbourhood of the diagonal of a manifold (in a well adapted model for SDG) has de Rham cohomology of the manifold as its R-dual. Extension Theory for Local Groupoids We relate Extension Theory for (non-abelian) groups (a la Eilenberg-Mac Lane) with the theory of Connections (a la Ehresmann), via a notion of local groupoid. In particular, we give in this setting a kind of converse to the statement "the curvature 2-form of a connection satisfies Bianchi identity". Both these preprints are accessible via my home page: http://www.mi.aau.dk/~kock/ or directly at ftp://ftp.mi.aau.dk/pub/kock/Cochains.ps (respectively ../locg.ps) Anders Kock Date: Thu, 13 Nov 1997 15:57:52 -0400 (AST) Subject: Limits in double categories, preprint Date: Wed, 12 Nov 1997 19:34:32 +0100 From: Marco Grandis The following preprint is available: Limits in double categories by Marco Grandis and Robert Pare Abstract. We define the notion of (horizontal) double limit for a double functor F: I -> A between double categories, and we give a construction theorem for such limits, from double products, double equalisers and tabulators (the double limits of vertical arrows). Double limits can describe important tools; for instance, the Grothendieck construction of a profunctor is its tabulator, in the "double category" of categories, functors and profunctors. If A is a 2-category, the previous result reduces to Street's construction theorem of weighted limits, by ordinary limits and cotensors 2*X (the tabulator of the vertical identity of the object X). Marco Grandis Dipartimento di Matematica Universita' di Genova via Dodecaneso 35 16146 GENOVA, Italy e-mail: grandis@dima.unige.it tel: +39.10.353 6805 fax: +39.10.353 6752 home page: http://www.dima.unige.it/STAFF/GRANDIS/ Date: Thu, 27 Nov 1997 16:02:23 -0400 (AST) Subject: Big Omega available Date: Thu, 27 Nov 1997 10:31:13 +1100 From: Ross Street Dear Colleagues This is to announce the availability at http://www-math.mpce.mq.edu.au/~mbatanin/Bigomega.ps of a short 10 page note which begins as follows: ********************************************************************** "The universal property of the multitude of trees" Michael Batanin and Ross Street Macquarie University, N S W 2109 AUSTRALIA Email and November 1997 Lawvere [BL] essentially pointed out that the category Delta, whose objects are finite ordinals and whose arrows are order-preserving functions, is the generic monoidal category containing a monoid. Let Mon be the category of monoids in the category Set of sets. Bénabou [Be] pointed out that the (simplicial) nerve of the category Delta is the standard resolution [BB] of the terminal monoid via the comonad generated by the underlying functor Mon --> Set and its left adjoint. Let Omcat denote the category of omega-categories and let Glob denote the category of globular sets. In this note we announce a generic property of the category BigOmega whose nerve is the standard resolution of the terminal omega-category via the comonad generated by the underlying functor Omcat --> Glob and its left adjoint. We also give a concrete model for BigOmega in terms of trees. Furthermore, we make connections with the recent work of Joyal [J]. Full proofs of our claims will appear elsewhere. ************************************************************************** Regards, Michael Batanin and Ross Street Date: Thu, 4 Dec 1997 09:48:43 -0400 (AST) Subject: preprints available Date: Thu, 4 Dec 1997 11:54:52 +0100 From: Marco Grandis The following preprints are now accessible as ps-files, via web of ftp: http://www.dima.unige.it/STAFF/GRANDIS/ ftp://www.dima.unige.it/pub/STAFF/GRANDIS (1). "Limits in double categories", by Marco Grandis and Robert Pare Dbl.Dec97.ps (2). "Weak subobjects and weak limits in categories and homotopy categories", by M.G. Var1.Aug97.ps (3). "Weak subobjects and the epi-monic completion of a category", by M.G. Var2.Dec97.ps *** The first was announced on this mailing list, on 13 Nov 1997. (With respect to the printed preprint, this is a slightly revised version, containing a more detailed comparison with Bastiani-Ehresmann's "limits relative to double categories".) The second and third form an expanded version of a printed preprint ("Variables and weak limits in categories and homotopy categories", Dec 1996), announced on this list on 13 Dec 1996. Abstracts for (2) and (3) are given below. *** (2). Abstract. We introduce the notion of "variation", or "weak subobject", in a category, as an extension of the notion of subobject. The dual notion is called a covariation, or weak quotient. Variations are important in homotopy categories, where they are well linked to weak limits, much in the same way as, in "ordinary" categories, subobjects are linked to limits. Thus, "homotopy variations" for a space S, with respect to the homotopy category HoTop, form a lattice Fib(S) of "types of fibration" over S. Nevertheless, the study of weak subobjects in ordinary categories, like abelian groups or groups, is interesting in itself and relevant to classify variations in homotopy categories of spaces, by means of homology and homotopy functors. (To appear in: Cahiers Top. Geom. Diff. Categ.) (3). Abstract. Formal properties of weak subobjects are considered. The variations in a category X can be identified with the (distinguished) subobjects in the epi-monic completion of X, or Freyd completion FrX, the free category with epi-monic factorisation system over X, which extends the Freyd embedding of the stable homotopy category of spaces in an abelian category (P. Freyd, Stable homotopy, La Jolla 1965). If X has products and weak equalisers, as HoTop and various other homotopy categories, FrX is complete. If X has zero-object, weak kernels and weak cokernels, as the homotopy category of pointed spaces, then FrX is a "homological" category. Finally, if X is triangulated, FrX is abelian and the embedding X --> FrX is the universal homological functor on X, as in the original case. These facts have consequences on the ordered sets of variations. Marco Grandis Dipartimento di Matematica Universita' di Genova via Dodecaneso 35 16146 GENOVA, Italy e-mail: grandis@dima.unige.it tel: +39.10.353 6805 fax: +39.10.353 6752 http://www.dima.unige.it/STAFF/GRANDIS/ Date: Thu, 15 Jan 1998 17:12:24 -0400 (AST) Subject: Report available Date: Thu, 15 Jan 1998 14:37:37 +0000 (GMT) From: Alan Jeffrey I'd like to announce a technical report relating Power and Robinson's premonoidal categories to a category of mixed data-flow and control-flow graphs. Premonoidal Categories and a Graphical View of Programs Alan Jeffrey University of Sussex The report is available electronically from: http://www.cogs.susx.ac.uk/users/alanje/premon/ Abstract -------- This paper describes the relationship between two different presentations of the semantics of programs: * Mixed data and control flow graphs are commonly used in software engineering as a semi-formal notation for describing and analysing algorithms. * Category theory is used as an abstract presentation of the mathematical structures used to give a formal semantics to programs. In this paper, we formalize an appropriate notion of flow graph, and show that acyclic flow graphs form the initial symmetric premonoidal category. Thus, giving a semantics for a programming language in flow graphs uniquely determines a semantics in any symmetric premonoidal category. For languages with recursive definitions, we show that cyclic flow graphs form the initial partially traced cartesian category. Finally, we conclude with some more speculative work, showing how closed structure (to represent higher-order functions) or two-categorical structure (to represent operational semantics) might be included in this graphical framework. The semantics has been implemented as a Java applet, which takes a program text and draws the corresponding flow graph (all the diagrams in this paper are drawn using this applet). The categorical presentation is based on Power and Robinson's premonoidal categories and Joyal, Street and Verity's monoidal traced categories, and uses similar techniques to Hasegawa's semantics for recursive declarations. The closed and two-categorical structure is related to Gardner's name-free presentation of Milner's action calculi. Date: Mon, 19 Jan 1998 09:45:42 -0400 (AST) Subject: announcement Date: Sun, 18 Jan 1998 18:33:38 -0600 From: Brooke Shipley Title:Algebras and modules in monoidal model categories Authors: Stefan Schwede, Brooke E. Shipley Email: schwede@math.mit.edu Email2: bshipley@math.uchicago.edu We construct model category structures for monoids and modules in symmetric monoidal model categories which satisfy an extra axiom, the monoidal axiom. This paper was inspired in particular to deal with two of the new symmetric monoidal categories of spectra, symmetric spectra and $\Gamma$-spaces. This paper is available at the homotopy theory archive at http://hopf.math.purdue.edu or via anonymous ftp at hopf.math.purdue.edu. It will also be available through math.AT at xxx.lanl.gov. Date: Thu, 22 Jan 1998 16:40:03 -0400 (AST) Subject: coinduction papers Date: Wed, 21 Jan 1998 21:22:55 +0000 (GMT) From: Dusko Pavlovic Dear Categories, Two papers about coinduction and guarded induction, one of them joint work with Martin Escardo, are available from http://www.cogs.susx.ac.uk/users/duskop/ or ftp://ftp.cogs.susx.ac.uk/pub/users/duskop/ *Calculus in coinductive form* is not one of those funny calculi where you can prove anything, just your old Newton-Leibniz-Taylor-Laplace calculus, with a special emphasis on Taylor and Laplace, and a bit of categories. *Guarded induction*, on the other hand, is this logical principle whereby, to prove a proposition p, you are allowed to use, among other things, that very same proposition p --- erm, provided, of course, that you make sure that it is #guarded#. This gives rise to various funny calculi, and a bit of categories. (Proper abstracts follow.) With best wishes, -- Dusko Pavlovic =================================================================== CALCULUS IN COINDUCTIVE FORM by D. Pavlovic and M.H. Escardo Abstract. Coinduction is often seen as a way of implementing infinite objects. Since real numbers are typical infinite objects, it may not come as a surprise that calculus, when presented in a suitable way, is permeated by coinductive reasoning. What *is* surprising is that mathematical techniques, recently developed in the context of computer science, seem to be shedding a new light on some basic methods of calculus. We introduce a coinductive formalization of elementary calculus that can be used as a tool for symbolic computation, and geared towards computer algebra and theorem proving. So far, we have covered parts of ordinary differential and difference equations, Taylor series, Laplace transform and the basics of the operator calculus. =================================================================== GUARDED INDUCTION ON FINAL COALGEBRAS by D. Pavlovic Abstract. We make an initial step towards categorical semantics of guarded induction. While ordinary induction is usually modelled in terms of least fixpoints and initial algebras, guarded induction is based on *unique* fixpoints of certain operations, called guarded, on *final* coalgebras. So far, such operations were treated syntactically. We analyse them categorically. Guarded induction appears as couched in coinduction. The applications of the presented categorical analysis span across the gamut of the applications of coinduction, from modelling of computation to solving differential equations. A subsequent paper will provide an account of some domain theoretical aspects, which are presently left implicit. Date: Sun, 8 Feb 1998 12:38:37 -0400 (AST) Subject: Categorification Date: Sat, 7 Feb 1998 16:00:14 -0800 (PST) From: john baez Here is the abstract of a paper that is now available at my website. ---------------------------------------------------------------------- Categorification John C. Baez and James Dolan To appear in Proceedings of the Workshop on Higher Category Theory and Mathematical Physics at Northwestern University, Evanston, Illinois, March 1997, eds. Ezra Getzler and Mikhail Kapranov. Categorification is the process of finding category-theoretic analogs of set-theoretic concepts by replacing sets with categories, functions with functors, and equations between functions by natural isomorphisms between functors, which in turn should satisfy certain equations of their own, called `coherence laws'. Iterating this process requires a theory of `n-categories', algebraic structures having objects, morphisms between objects, 2-morphisms between morphisms and so on up to n-morphisms. After a brief introduction to n-categories and their relation to homotopy theory, we discuss algebraic structures that can be seen as iterated categorifications of the natural numbers and integers. These include tangle n-categories, cobordism n-categories, and the homotopy n-types of the loop spaces Omega^k S^k. We conclude by describing a definition of weak n-categories based on the theory of operads. ----------------------------------------------------------------------- The paper is available in Postscript form on the web at http://math.ucr.edu/home/baez/cat.ps I can also email or snailmail you a copy at your request. Date: Tue, 24 Feb 1998 14:18:32 GMT From: Samin Ishtiaq Subject: categories: new paper: A Relevant Analysis of Natural Deduction We apologize for multiple copies of this mail. The following paper will appear in the Journal of Logic and Computation (expected in Vol. 8) later this year: A Relevant Analysis of Natural Deduction S Ishtiaq and DJ Pym Queen Mary and Westfield College University of London {si,pym}@dcs.qmw.ac.uk We study a framework, RLF, for defining natural deduction presentations of linear and other relevant logics. RLF consists in a language together, in a manner similar to that of LF, with a representation mechanism. The language of RLF, the $\lambda\Lambda_{\kappa}$-calculus, is a system of first-order linear dependent function types which uses a function $\kappa$ to describe the degree of sharing of variables between functions and their arguments. The representation mechanism is judgements-as-types, developed for linear and other relevant logics. The $\lambdal\Lambda_{\kappa}$-calculus is a conservative extension of the $\lambda\Pi$-calculus and RLF is a conservative extension of LF. The paper will be available from our Hypatia entries, at http://hypatia.dcs.qmw.ac.uk. It is also available at http://www.dcs.qmw.ac.uk/~si. We are currently engaged in further study of the proof theory of the $\lambda\Lambda_{\kappa}$-calculus; this includes setting up a proposition-as-types correspondence and a Gentzenization of the type theory. We are also investigating categorical models, specifically resourced-indexed Kripke models, of the $\lambda\Lambda_{\kappa}$-calculus. Samin Ishtiaq David Pym Date: Fri, 27 Feb 1998 09:33:00 -0500 From: rblute@mathstat.uottawa.ca (Richard Blute) Subject: categories: Paper available The following paper is available by anonymous ftp at triples.math.mcgill.ca in the directory pub/blute as nuclear.ps.gz. It is also on Prakash Panangaden's homepage at www-acaps.cs.mcgill.ca. Feel free to contact me if there are any problems. Cheers, Rick Blute Nuclear and Trace Ideals in Tensored *-Categories ================================================= Samson Abramsky Richard Blute Department of Computer Science Department of Mathematics University of Edinburgh and Statistics Edinburgh, Scotland University of Ottawa Ottawa, Ontario, Canada Prakash Panangaden Department of Computer Science McGill University Montreal, Quebec, Canada Presented to Mike Barr on the occasion of his 60th birthday. Abstract ======== We generalize the notion of nuclear maps from functional analysis by defining nuclear ideals in tensored *-categories. The motivation for this study came from attempts to generalize the structure of the category of relations to handle what might be called ``probabilistic relations''. The compact closed structure associated with the category of relations does not generalize directly, instead one obtains nuclear ideals. Most tensored *-categories have a large class of morphisms which behave as if they were part of a compact closed category, i.e. they allow one to transfer variables between the domain and the codomain. We introduce the notion of nuclear ideals to analyze these classes of morphisms. In compact closed categories, we see that all morphisms are nuclear, and in the category of Hilbert spaces, the nuclear morphisms are the Hilbert-Schmidt maps. We also introduce two new examples of tensored *-categories, in which integration plays the role of composition. In the first, morphisms are a special class of distributions, which we call tame distributions. We also introduce a category of probabilistic relations which was the original motivating example. Finally, we extend the recent work of Joyal, Street and Verity on traced monoidal categories to this setting by introducing the notion of a trace ideal. For a given symmetric monoidal category, it is not generally the case that arbitrary endomorphisms can be assigned a trace. However, we can find ideals in the category on which a trace can be defined satisfying equations analogous to those of Joyal, Street and Verity. We establish a close correspondence between nuclear ideals and trace ideals in a tensored *-category, suggested by the correspondence between Hilbert-Schmidt operators and trace operators on a Hilbert space. When we apply our notion of trace ideal to the category of Hilbert spaces, we obtain the usual trace of an endomorphism in the trace class. Date: Sat, 28 Feb 1998 11:41:14 -0500 (EST) From: Robert Seely Subject: categories: Paper on Feedback announced The following paper is available on RAG Seely's WWW home page at or directly by ftp at or Comments are most welcome; please send them to any of the authors. Any problems in obtaining the paper should be sent to rags@math.mcgill.ca. Feedback for linearly distributive categories: traces and fixpoints by R.F. Blute J.R.B. Cockett R.A.G. Seely ABSTRACT In the present paper, we develop the notion of a trace operator on a linearly distributive category, which amounts to essentially working within a subcategory (the "core") which has the same sort of "type degeneracy" as a compact closed category. We also explore the possibility that an object may have several trace structures, introducing a notion of compatibility in this case. We show that if we restrict to compatible classes of trace operators, an object may have at most one trace structure (for a given tensor structure). We give a linearly distributive version of the "geometry of interaction" construction, and verify that we obtain a linearly distributive category in which traces become canonical. We explore the relationship between our notions of trace and fixpoint operators, and show that an object admits a fixpoint combinator precisely when it admits a trace and is a cocommutative comonoid. This generalises an observation of Hyland and Hasegawa. This paper is presented to Bill Lawvere on the occasion of his 60th birthday. =================================== RAG Seely [ NB - please use the "generic" email address above and not machine specific e-addresses like "rags@triples.math.mcgill.ca" ] =================================== Date: Sat, 25 Apr 1998 16:03:09 +0300 (IDT) From: ZIPPIE Gonczarowski Subject: categories: Pre-prints available The following pre-prints are available. Please e-mail to: zippie@actcom.co.il 1. Introducing the Mathematical Category of Artificial Perceptions by Z. Arzi-Gonczarowski and D. Lehmann To be published this summer in `The Annals of Mathematics and Artificial Intelligence'. 2. From Environments to Representations - A Mathematical Theory of Artificial Perceptions by Z. Arzi-Gonczarowski and D. Lehmann To be published in `Artificial Intelligence'. (To those of you who have already asked for them - they are being posted today). __________________________________________________________________________ Dr. Zippora Arzi-Gonczarowski Typographics, Ltd. 46 Hehalutz St. Jerusalem 96222 Israel Tel: (+972)-2-6437819 Fax: (+972)-2-6434252 E-mail: zippie@actcom.co.il __________________________________________________________________________ From: Giuseppe Longo Date: Tue, 28 Apr 98 15:46:15 +0200 Subject: categories: Book available by ftp The book below is currently out of print. Upon kind permission of the M.I.T. Press, it is now available by ftp, via my web page (see the book content page in Downloadable Papers). Andrea Asperti and Giuseppe Longo. Categories, Types and Structures: an introduction to Category Theory for the working computer scientist. M.I.T.- Press, 1991. (pp. 1--300). --Giuseppe Longo http://www.dmi.ens.fr/users/longo e-mail: longo@dmi.ens.fr Date: Wed, 6 May 1998 18:15:06 -0400 (EDT) From: Steve Awodey Subject: categories: preprint available Dear Colleagues, The preprint mentioned below is available from my page on the WWW, http://www.andrew.cmu.edu/user/awodey/ Please let me know if you have difficulty obtaing or printing it, or if you would like to have a paper copy sent. Steve A. ******************************************************************************* "Topological representation of the lambda-calculus" S. Awodey Abstract: The lambda-calculus can be represented topologically by assigning certain spaces to the types and certain continuous maps to the terms. Using a recent result from topos theory, the usual calculus of lambda-conversion is shown to be deductively complete with respect to such topological semantics. It is also shown to be functionally complete, in the sense that there is always a ``minimal'' topological model, in which every continuous function is lambda-definable. These results subsume earlier ones using cartesian closed categories, as well as those employing so-called Henkin and Kripke lambda-models. ******************************************************************************* Date: Thu, 7 May 1998 15:25:22 -0400 (EDT) From: Steve Awodey Subject: categories: more precisely ... Dear Colleagues, Since this is the categories list, I could and should have been more specific about the contents of the preprint I announced yesterday: "Topological representation of the lambda-calculus", available from my page on the WWW, http://www.andrew.cmu.edu/user/awodey/ In a nut-shell, the point is that the Butz-Moerdijk spatial covering theorem for topoi can be used to embed any CCC fully and faithfully (and CC) into a topos of sheaves on a space. So the "topological semantics" mentioned are actually in such topoi of sheaves. Steve A. Subject: categories: Higher-dimensional paper available Date: Fri, 5 Jun 1998 15:48:32 +0100 (BST) From: Tom Leinster Higher-dimensional paper available, from http://www.dpmms.cam.ac.uk/~leinster. Structures in Higher-Dimensional Category Theory This is an exposition of some of the constructions which have arisen in higher-dimensional category theory. We start with a review of the general theory of operads and multicategories. Using this we give an account of Batanin's definition of n-category; we also give an informal definition in pictures. Next we discuss Gray-categories and their place in coherence problems. Finally, we present various constructions relevant to the opetopic definitions of n-category. New material includes a suggestion for a definition of lax cubical n-category; a characterization of small Gray-categories as the small substructures of 2-Cat; a conjecture on coherence theorems in higher dimensions; a construction of the category of trees and, more generally, of n-pasting diagrams; and an analogue of the Baez-Dolan slicing process in the general theory of operads. (A few corrections have been made to the version of this distributed at the PSSL in Utrecht, and these are listed at the web site.) Tom Leinster From: "JONATHON FUNK" Date: Wed, 10 Jun 1998 17:39:14 EET +0200 DST Subject: categories: preprint available Dear Colleagues, A preprint, whose abstract follows, is available in compressed .dvi form (for DOS and for UNIX) from: http://www.emu.edu.tr/academic/facartsc/mathsdep/staffpic/jfunk.htm or if you are browsing the web, click on academics, teaching staff, Mathematics, Jonathon Funk, additional information, after you have reached the EMU homepage http://www.emu.edu.tr If you would like a copy, but are unable to retrieve the preprint, please don't hestitate to contact me, as I would be happy to send you the .dvi file personally. funk@mozart.emu.edu.tr ---------------------------------------------------------------- ``On branched covers in topos theory'' Abstract: We present some new findings conerning branched covers in topos theory. Our discussion involves a particular subtopos of a given topos that can be described as the smallest subtopos closed under small coproducts in the including topos. We also have some new results concerning the general theory of KZ-doctrines, such as the the closure under composition of discrete fibrations for a KZ- doctrine (in the sense of Bunge/Funk, ``On a bicomma object condition for KZ-doctrines''). Regards, Jonathon Funk Jonathon Funk Department of Mathematics Eastern Mediterranean University Gazimagusa Turkish Republic of North Cyprus via Mersin 10, Turkey tel: (90) 392 366 6588, Ext: 1227, 1228, 1138 fax: (90) 392 366 1604 Date: Mon, 15 Jun 1998 11:23:12 +0200 (MET DST) From: "I. Moerdijk" Subject: categories: new preprint Dear categorists, The following preprint is available from the K-Theory archive at http://www.math.uiuc.edu/K-theory, and hopefully from our homepages before long. Please let us know in case you wish to be sent a hard copy. Ieke Moerdijk. --------------------- A Homology Theory for Etale Groupoids by Marius Crainic and Ieke Moerdijk In this paper we introduce a homology theory for etale groupoids, dual to Haefliger's cohomology theory (via Poincare duality). We prove basic facts like Morita invariance, Leray spectral sequence, Verdier duality. We also outline the application to the computation of cyclic homology of the convolution algebra of the groupoid (including the non-Hausdorff situation). An appendix about "compact supports" on non-Hausdorff manifolds is added. Marius Crainic Ieke Moerdijk -------------------- Date: Wed, 24 Jun 1998 10:49:40 -0400 (EDT) From: Susan Niefield Subject: categories: preprint available The following reprint is available at http://www1.union.edu/~niefiels/ESU.ps http://www1.union.edu/~niefiels/ESU.dvi EXPONENTIABILITY AND SINGLE UNIVERSES by Marta BUNGE and Susan NIEFIELD ABSTRACT - The search for suitable single universes for opposite or dual pairs of notions (such as those of discrete fibration and discrete opfibration, or of open and closed inclusions, or of functions and distributions on a Grothendieck topos) leads naturally to exponentiability. Using exponentiability techniques, such as model-generated categories and glueing, we settle a standing conjecture and an open problem. The conjecture, due to F. Lamarche, states that for a small category B, the category of unique factorization liftings (also known as discrete Conduche fibrations) over B is a topos. We also construct the smallest topos containing the local homeomorphisms (functions) and the complete spreads (distributions) over any given topos satisfying a certain condition (true of presheaf toposes). This solves a problem posed by F. W. Lawvere. Along the way, we introduce two new sorts of geometric morphisms, characterize locally closed inclusions in Cat, and investigate new features of generalized coverings in topos theory, such as branched coverings, cuts, and complete spreads. Date: Thu, 2 Jul 1998 22:10:56 -0400 (EDT) From: Susan Niefield Subject: categories: withdrawal of preprint The paper "Exponentiablity and Single Universes" by Marta Bunge and Susan Niefield, recently announced on the site ww1.union.edu/~niefiels has been temporarily withdrawn. A revised version will be posted soon. The paper contained an erroneous result - namely, that for an arbitrary small category B, the category UFL/B of Giraud-Conduche fibrations over B is a topos. A counterexample has been found by Peter Johnstone. Date: Mon, 6 Jul 1998 16:49:05 +1000 From: mbatanin@mpce.mq.edu.au (Michael Batanin) Subject: categories: generalized computads Dear collegues, the following preprint "Computads for finitary monads on globular sets" is available at http://www-math.mpce.mq.edu.au/~mbatanin/papers.html >From Introduction. This work arose as a reflection on the foundation of higher dimensional category theory. One of the main ingredients of any proposed definition of weak $n$-category is the shape of diagrams (pasting scheme) we accept to be composable. In a globular approach \cite{Bat} each $k$-cell has a source and target $(k-1)$-cell. In the opetopic approach of Baez and Dolan \cite{BD} and the multitopic approach of Hermida, Makkai and Power \cite{HMP} each $k$-cell has a unique $(k-1)$-cell as target and a whole $(k-1)$-dimensional pasting diagram as source. In the theory of strict $n$-categories both source and target may be a general pasting diagram \cite{J,StH, StP}. The globular approach being the simplest one seems too restrictive to describe the combinatorics of higher dimensional compositions. Yet, we argue that this is a false impression. Moreover, we prove that this approach is a basic one from which the other type of composable diagrams may be derived. One theorem proved here asserts that the category of algebras of a finitary monad on the category of $n$-globular sets is {\bf equivalent} to the category of algebras of an appropriate monad on the special category (of computads) constructed from the data of the original monad. In the case of the monad derived from the universal contractible operad \cite{Bat} this result may be interpreted as the equivalence of the definitions of weak $n$-categories (in the sense of \cite{Bat}) based on the `globular' and general pasting diagrams. It may be also considered as the first step toward the proof of equivalence of the different definitions of weak $n$-category. We also develop a general theory of computads and investigate some properties of the category of generalized computads. It turned out, that in a good situation this category is a topos (and even a presheaf topos under some not very restrictive conditions, the property firstly observed by S.Schanuel and reproved by A,Carboni and P.Johnstone for $2$-computads in the sense of Street). /\ / \ M --/ Co \--> MQ / A C T\ /________\ Centre of Australian Category Theory Mathematics Department, Macquarie University New South Wales 2109, AUSTRALIA Date: Tue, 21 Jul 1998 13:55:47 -0400 (EDT) From: Susan Niefield Subject: categories: revised preprint available A revised version of the following reprint is available at http://www1.union.edu/~niefiels/ESU.ps http://www1.union.edu/~niefiels/ESU.dvi EXPONENTIABILITY AND SINGLE UNIVERSES by Marta BUNGE and Susan NIEFIELD ABSTRACT - In this paper, we first consider known universes for pairs of opposite notions such as those of discrete fibrations/discrete opfibrations and of open/closed locale inclusions, and then extrapolate these in order to introduce new single universes for open/closed inclusions of subcategories and for functions/distributions on a topos. A key factor that these notions have in common is exponentiability in the ambient category. Along the way, we (1) prove that, for a factorization linearly ordered small category B, the category of discrete Giraud-Conduche fibrations over B is a (model generated) topos, (2) characterize locally closed inclusions in the category Cat of small categories, (3) investigate ``generalized coverings'' in topos theory, including branched coverings, cuts, and complete spreads, and (4) examine the preservations of exponetiability under the passage from Cat/B to the category of Grothendieck toposes over the presheaves PB. Date: Mon, 03 Aug 1998 14:18:11 +0100 From: "David J. Pym" Subject: categories: The Logic of Bunched Implications. We, Peter O'Hearn and David Pym, are pleased to announce our new paper, ``The Logic of Bunched Implications''. We hope it will be of interest to readers of `categories'. BI is a relevant logic which extends both linear and intuitionistic logic. It has a semantics of proofs based on `doubly closed categories', which carry two monoidal closed structures, one of which is cartesian in models of BI. A rich class of models is provided by Day's tensor product construction on the category of presheaves over a small monoidal category. It also comes with a lambda calculus, a truth semantics and a computational interpretation as a logic of resources, quite different from that of linear logic. The paper is available at: http://www.dcs.qmw.ac.uk/~pym and http://www.dcs.qmw.ac.uk/~ohearn where drafts of various companion and related papers can/will be found. P.W.O'Hearn and D.J. Pym Queen Mary & Wesfield College, University of London Abstract. Introduce a logic BI in which a multiplicative (or linear) and an additive (or intuitionistic) implication live side by side. The propositional version of BI arises from an analysis of the proof-theoretic relationship between conjunction and implication, and may be viewed as a merging of intuitionistic logic and multiplicative, intuitionistic linear logic. The predicate version of BI includes, in addition to standard additive quantifiers, multiplicative (or intensional) quantifiers ``forall-new'' and ``exist-new'' which arise from observing restrictions on structural rules on the level of terms as well as propositions. We discuss computational interpretations, based on sharing, at both the propositional and predicate levels. Date: Mon, 3 Aug 1998 19:01:17 +0100 (BST) From: Ronnie Brown Subject: categories: New Preprint New preprint R. Brown and I. Icen. "Lie local subgroupoids and their monodromy", UWB Math Preprint 98.15, 12pp. ABSTRACT:The notion of local equivalence relation on a topological space is generalised to that of local subgroupoid. Properties of coherence are considered. The main result is notions of holonomy and monodromy groupoid for certain Lie local subgroupoids. http://www.bangor.ac.uk/~mas010/papers/sub6.ps,.dvi Prof R. Brown, School of Mathematics, University of Wales, Bangor Dean St., Bangor, Gwynedd LL57 1UT, United Kingdom Tel. direct:+44 1248 382474|office: 382475 fax: +44 1248 383663 World Wide Web: home page: http://www.bangor.ac.uk/~mas010/ Symbolic Sculpture and Mathematics: http://www.bangor.ac.uk/SculMath/ Mathematics and Knots: http://www.bangor.ac.uk/ma/CPM/exhibit/welcome.htm Date: Tue, 4 Aug 1998 18:01:18 +0100 Subject: categories: Injectives via KZ-monads From: "Martin Escardo" The following short paper is available from my home page: http://www.dcs.ed.ac.uk/home/mhe/pub/papers/top97.ps.gz or http://www.dcs.ed.ac.uk/home/mhe/papers.html (It is an updated version of a paper which was previously circulated in other lists.) ===================================== Injective spaces via the filter monad ====================================================================== An injective space is a topological space with a strong extension property for continuous maps with values on it. A certain filter space construction embeds every T_0 topological space into an injective space. The construction gives rise to a monad. We show that the monad is of the Kock-Zoberlein type and apply this to obtain a simple proof of the fact that the algebras are the continuous lattices (Alan Day, 1975, Oswald Wyler, 1976). In previous work we established an injectivity theorem for monads of this type, which characterizes the injective objects over a certain class of embeddings as the algebras. For the filter monad, the class turns out to consist precisely of the subspace embeddings. We thus obtain as a corollary that the injective spaces over subspace embeddings are the continuous lattices endowed with the Scott topology (Dana Scott, 1972). Similar results are obtained for continuous Scott domains, which are characterized as the injective spaces over dense subspace embeddings, via the proper filter monad. ====================================================================== Two notes (and some questions concerning credit) ========= (i) Bob Flagg and I have also considered the following variations on the filter monad (a report is being written) (a) Category: T_0 exponentiable spaces (= core-compact = open sets form a continuous lattice) Restriction on filters: Scott open. => Associated maps: "semi-proper" embeddings (= right adjoint of the frame maps preserve directed joins) => Algebras (and hence injectives over semi-proper): continuous meet-semilattices with Scott topology. (Corollary: continuous meet-semilattices and Scott continuous functions form a CCC. Was this known before?) This characterization of the algebras was previously known (Andrea Shalk--anyone else?), but the "KZ-method" outlined in the above abstract gives a much shorter proof. (b) Category: T_0 spaces Restriction on filters: prime. => Associated maps: flat embeddings (= right adjoint of the frame maps preserve finite joins) => Algebras (and hence injectives over flat): compact, stably locally compact spaces. (A localic version is given via the ideal monad. What Johnstone refers to as Joyal's Lemma appears as a special case of this.) (I don't know what was previously known about this.) (A result by Isbell (in his paper "Flat = prosupersplit") implies that the flat embeddings form the largest class of embeddings over which the CSLCSs are injective, because finite spaces are (trivially) CSLCSs.) (c) Category: T_0 spaces Restriction on filters: completely prime. => Associated maps: "completely flat" embeddings (= right adjoint of the frame maps preserve all joins) => Algebras (and hence injectives over completely flat): sober spaces. (d) Category: T_0 locally connected spaces Restriction on filters: filters of connected open sets. => Associated maps: "locally dense" embeddings (= frame maps preserve connectedness (and hence right adjoints preserve disjoint unions)) => Algebras (and hence injectives over locally dense): L-domains. (This was obtained by Bob, based on some previous work by Paul Taylor (and Andrea Shalk) on the algebras. Again, the KZ-method gives a simpler proof of the characterization.) (ii) The filter monad is formally analogous to the so-called continuation monad, as it is observed (with the formal details of the analogy) in the paper being advertised. I would like to also mention that the general injectivity result for KZ-monads referred to in the above abstract was established in the paper http://www.dcs.ed.ac.uk/home/mhe/pub/papers/injective.ps.gz which is (mainly) about continuity of the extension process (answering a question by Scott in his 1972 paper on continuous lattices). Comments are wellcome. Martin ================================================================= Martin H. Escardo, Department of Computer Science, LFCS King's Buildings, Mayfield Road, Edinburgh EH9 3JZ, Scotland office: 2606 (JMCB) fax: +44 131 667 7209 phone: +44 131 650 5135 mailto:mhe@dcs.ed.ac.uk http://www.dcs.ed.ac.uk/home/mhe ================================================================= Date: Fri, 7 Aug 1998 09:44:50 +0100 (BST) From: Ronnie Brown Subject: categories: New Preprint (revised) The url for the following was not correct and is revised below: New preprint R. Brown and I. Icen. "Lie local subgroupoids and their monodromy", UWB Math Preprint 98.15, 12pp. ABSTRACT:The notion of local equivalence relation on a topological space is generalised to that of local subgroupoid. Properties of coherence are considered. The main result is notions of holonomy and monodromy groupoid for certain Lie local subgroupoids. http://www.bangor.ac.uk/~mas010/brownpr.html#monodromy Prof R. Brown, School of Mathematics, University of Wales, Bangor Dean St., Bangor, Gwynedd LL57 1UT, United Kingdom Tel. direct:+44 1248 382474|office: 382475 fax: +44 1248 383663 World Wide Web: home page: http://www.bangor.ac.uk/~mas010/ Symbolic Sculpture and Mathematics: http://www.bangor.ac.uk/SculMath/ Mathematics and Knots: http://www.bangor.ac.uk/ma/CPM/exhibit/welcome.htm Date: Wed, 28 Oct 1998 15:10:20 -0500 (EST) From: Michael Barr Subject: categories: Papers available I have just posted two new papers on ftp.math.mcgill.ca. The first is called balls.dvi and is my joint paper with Heinrich Kleisli on *-autonomous categories of topological balls. It will appear, bye and bye, in the Cahiers. The second, called chu_se.dvi is on the separated extension Chu category and is to be published in TAC within the next day or two. Michael Date: Fri, 30 Oct 1998 08:24:52 -0400 From: Marta Bunge Subject: categories: Paper available This is to announce a new paper, by Marta Bunge and Marcelo Fiore, "Unique factorization Lifting Functors and Categories of Processes". http://www.dcs.ed.ac.uk/~mf/CONCURRENCY/ufl.dvi http://www.dcs.ed.ac.uk/~mf/CONCURRENCY/ufl.ps The paper is organised as follows. After an Introduction, Section 1 presents background material motivated from the point of view of computer science. In Section 2, the category UFL of unique factorisation lifting (ufl) functors is recalled and its basic properties are studied. Section 3 explores applications of ufl functors to concurrency. In particular we show that they may be used in the study of interleaving models like transition systems. In Section 4, we introduce triangulated categories. Our main use for them is in Section 5 where, for C a triangulated category, we exhibit the category UFL/C as a sheaf topos. These toposes may be regarded as models of linearly-controlled processes. Some concluding remarks are provided in Section 6. Professor Marta Bunge McGill University Department of Mathematics & Statistics Burnside Hall 805 Sherbrooke Street West Montreal, QC Canada H3A 2K6 Fax: (514) 933 8741 Phone: (514) 933 6191 Date: Thu, 12 Nov 1998 15:26:28 +0100 From: grandis@dima.unige.it (Marco Grandis) Subject: categories: Preprint available The following preprint: M. Grandis, "An intrinsic homotopy theory for simplicial complexes with applications to image processing" is available at: ftp://pitagora.dima.unige.it/WWW/FTP/GRANDIS/ as: Lnk.Nov98.ps *** Abstract. A simplicial complex is a set equipped with a down-closed family of distinguished finite subsets; this structure is mostly viewed as codifying a triangulated space. Here, this structure is used directly to describe "spaces" of interest in various applications, where the associated triangulated space would be misleading. An intrinsic homotopy theory, not based on topological realisation, is introduced. The applications considered here are aimed at metric spaces and digital topology; concretely, at image processing and computer graphics. A metric space X has a structure t_e(X) of simplicial complex at each "resolution" e > 0; the resulting n-homotopy group \pi_n(t_e(X)) detects those singularities which can be captured by an n-dimensional grid, with edges bound by e; this works equally well for continuous or discrete regions of euclidean spaces. *** Comments would be appreciated. In particular, I am uneasy about a question of terminology. In my opinion, the term "simplicial complex", quite appropriate when the structure is viewed as codifying a triangulated space, is unfit when such objects are treated as "spaces" in themselves (somewhat close to bornological spaces, which have similar axioms on objects and maps). In other words, "simplicial complex" should not refer to the category itself, say C, but to its usual embedding in Top, the simplicial realisation. The two aspects may clash, e.g. with respect to initial or final structures: the coarse C-object on three points (final structure, all parts are distinguished) is realised as a euclidean triangle; a C-subobject is sufficient to produce a topological subspace (a regular subobject in Top), but a C-subspace (a regular subobject in C) is a stronger notion. Moreover, from a more concrete point of view, the simplicial realisation is quite inappropriate in most of the applications considered in this work. The opposition "C-object / simplicial complex" is in part similar to "sequence / series": the second term refers to a more specific view & use of the same data; the clashing of the opposition is particularly evident in the notions of convergence, for a sequence or a series. That's why I am calling a C-object a "combinatorial space". (The term "combinatorial complex" has also been used for simplicial complex; and I wanted a term of the form "attribute + space", to use freely of topological terms like discrete, coarse, subspace...) But of course it is embarassing to propose a new term for a classical notion. Marco Grandis Date: Tue, 17 Nov 1998 09:26:51 +0100 From: grandis@dima.unige.it (Marco Grandis) Subject: categories: Re: preprint available (on simplicial complexes) Reply to James Stasheff > is it also available on your web page without ftp? No, from my home page: http://pitagora.dima.unige.it/webdima/STAFF/GRANDIS/ you would just have access to all papers available by ftp, at the address I gave: ftp://pitagora.dima.unige.it/WWW/FTP/GRANDIS/ *** > will you be posting it to the math archive at lanl? yes, in a while and possibly after revision. *** With best wishes Marco Grandis Date: Wed, 18 Nov 1998 13:27:09 +0100 From: kock Subject: categories: preprint available (Kock and Reyes) The following preprint A. Kock and G.E. Reyes: Fractional Exponent Functors and Categories of Differential Equations is available via the Home Page http://www.mi.aau.dk/~kock/ or directly by ftp (200 KB) ftp://ftp.imf.au.dk/pub/kock/ODE5.ps (also available in .dvi format, 100 KB). Abstract: This paper grew out of a question/suggestion of Lawvere: to use the "amazing right adjoints" (= fractional exponents) of Synthetic Differential Geometry, to get information on the category of second order differential equations. As a byproduct of our investigations, we derive some information about the strength (enrichment) of fractional exponent functors in general. Date: Wed, 18 Nov 1998 16:09:09 +0000 (GMT) Subject: categories: preprint available From: "Martin Escardo" The following preprint is available at http://www.dcs.ed.ac.uk/home/mhe/pub/papers/patch-CSLC.ps.gz & http://www.dcs.ed.ac.uk/home/mhe/papers.html & ftp://ftp.dcs.ed.ac.uk/pub/mhe/patch-CSLC.ps.gz On the compact-regular coreflection of a compact stably locally compact locale. ABSTRACT: The Scott continuous nuclei form a subframe of the frame of all nuclei. We refer to this subframe as the patch frame. We show that the patch construction exhibits (i) the category of Stone locales and continuous maps as a coreflective subcategory of the category of coherent locales and coherent maps, (ii) the category of compact regular locales and continuous maps as a coreflective subcategory of the category of compact stably locaaly compact locales and perfect maps, and (iii) the category of regular locally compact locales and continuous maps as a coreflective subcategory of the category of stably locally compact locales. We relate our patch construction to Banaschewski and Brümmer's construction of the dual equivalence of the category of compact stably locally compact locales and perfect maps with the category of compact regular biframes and biframe homomorphisms. Comments are welcome. ----------------------------------------------------------------- Martin H. Escardo, LFCS, Computer Science, Edinburgh University King's Buildings, Mayfield Road, Edinburgh EH9 3JZ, Scotland office: 2606 (JMCB) fax: +44 131 667 7209 phone: +44 131 650 5135 mailto:mhe@dcs.ed.ac.uk http://www.dcs.ed.ac.uk/home/mhe ----------------------------------------------------------------- Date: Thu, 19 Nov 1998 22:49:16 -0500 (EST) From: F W Lawvere Subject: categories: announcement of pre-prints There are two items now available for downloading (PDF) from my homepage http://www.acsu.buffalo.edu/~wlawvere/ They are: Volterra's functionals and the covariant cohesion of space Abstract: Volterra's principle of passage from finiteness to infinity is far less limited than a linearized construal of it might suggest; I outline in Section III a nonlinear version of the principle with the help of category theory. As necessary background I review in Section II some of the mathematical developments of the period 1887-1913 in order to clarify some more recent advances and controversies which I discuss in Section I. Some relevant historical and current literature is discussed in relation to the categorical analysis: Volterra and Hadamard on the notion of element, Fichera's critique of the relation between functional analysis and continuum physics, and the recent Michor & Kriegl book published by the AMS. Outline of Synthetic Differential Geometry Abstract: These rough notes were distributed to the geometry seminar at Buffalo in February 1998, sketching the background of categorical dynamics in anticipation of the April 1999 AMS Meeting in which there will be a special session on related matters. In particular, some of the results stated in my September 1997 AMS talk in Montreal "Toposes of laws of motion" are outlined, especially the relation of second order differential equations to a.t.o.m's (amazingly tiny object models). An additional appendix has been added (November 1998) to these rough notes concerning recent advances on these questions by Kock and Reyes. Toposes of laws of motion will be added to the web page as soon as the transcript of the original video is completed. ********************************************************************** F. William Lawvere Mathematics Dept. SUNY wlawvere@acsu.buffalo.edu 106 Diefendorf Hall 716-829-2144 ext. 117 Buffalo, N.Y. 14214, USA ********************************************************************** Date: Fri, 20 Nov 1998 15:53:55 -0500 (EST) From: Michael Barr Subject: categories: staragain.dvi A paper titled *-Autonomous categories: once more around the track has just been posted: ftp.math.mcgill.ca/pub/barr/staragain.dvi Basically, it redoes nearly all of the original Lecture Notes volume in about one fifth the space, using the Chu construction and proving a very general theorem. The only example from the original monograph that is not convered by this theorem is the category of Banach balls, the subject of a recent paper by Kleisli and me. That is also thee under the name balls.dvi (if I have remembered it correctly). This paper is to be submitted to tac for the Lambekfestschrift. From: john baez Subject: categories: HDA4: 2-Tangles Date: Mon, 23 Nov 1998 20:08:31 -0800 (PST) The following preprint is now available at the places listed below. Comments and corrections are welcome! -------------------------------------------------------------------- Higher-Dimensional Algebra IV: 2-Tangles John C. Baez, Laurel Langford Just as knots and links can be algebraically described as certain morphisms in the category of tangles in 3 dimensions, compact surfaces smoothly embedded in R^4 can be described as certain 2-morphisms in the 2-category of `2-tangles in 4 dimensions'. Using the work of Carter, Rieger and Saito, we prove that this 2-category is the `free semistrict braided monoidal 2-category with duals on one unframed self-dual object'. By this universal property, any unframed self-dual object in a braided monoidal 2-category with duals determines an invariant of 2-tangles in 4 dimensions. --------------------------------------------------------------------- This paper is math.QA/981139 on the mathematics preprint server, so you can get it at: http://xxx.lanl.gov/abs/math.QA/9811139 It's also available as a Postscript file at my website: http://math.ucr.edu/home/baez/hda4.ps If you have any trouble, let me know and I can send you a copy. Date: Wed, 9 Dec 1998 22:22:03 -0800 (PST) From: Jonathon Funk Subject: categories: preprint (revised) available The preprint: On Branched Covers in Topos Theory is available from my home page http://www.math.ubc.ca/~funk/ in postscript or .dvi format. This is a revision and extension of a preprint I had posted from Cyprus in June, 98. Abstract: We present some new findings concerning branched covers in topos theory. Our discussion involves a particular subtopos of a given topos that can be described as the smallest subtopos closed under small coproducts in the including topos. Our main result is a description of the covers of this subtopos as a category of fractions of branched covers, in the sense of R. Fox, of the including topos. We also have some new results concerning the general theory of KZ-doctrines, such as the closure under composition of discrete fibrations for a KZ-doctrine, in the sense of Bunge-Funk. Date: Mon, 14 Dec 1998 17:51:26 -0500 (EST) From: F W Lawvere Subject: categories: Preprint available PREPRINT AVAILABLE A transcript of the video of my talk at the September 1997 AMS Meeting in Montreal is now available for downloading in pdf format. The title is TOPOSES OF LAWS OF MOTION I will be very grateful for comments and suggestions on this paper, as well as on the other two papers available: http://www.acsu.buffalo.edu/~wlawvere ******************************************************************************* F. William Lawvere Mathematics Dept. SUNY wlawvere@acsu.buffalo.edu 106 Diefendorf Hall 716-829-2144 ext. 117 Buffalo, N.Y. 14214, USA ******************************************************************************* Subject: categories: Preprint available (Fiore, Plotkin, and Turi). From: Marcelo Fiore Date: Tue, 15 Dec 1998 21:12:32 +0000 The following preprint Abstract Syntax and Variable Binding by M.Fiore, G.Plotkin., and D.Turi. is available as http://www.dcs.ed.ac.uk/~dt/abstractsyn.ps Synopsis: We show that categorical algebra in the object-classifier topos provides a suitable mathematical universe for modelling algebraic structures with binding operators. Date: Wed, 16 Dec 1998 12:10:31 +0100 (MET) From: Jaap van Oosten Subject: categories: paper on SDT available The following paper is available: Axioms and (Counter)examples in Synthetic Domain Theory by Jaap van Oosten and Alex K. Simpson the paper can be found at the URL: http://www.math.uu.nl/publications/preprints/1080.ps.gz ABSTRACT: Chapter 1 presents a development of basic Synthetic Domain Theory on the basis of 4 axioms (1:\Sigma is complete; 2:\Sigma is \neg\neg-separated; 3:\bot\in\Sigma; 4:the Phoa Principle). New results are, that 1 and 2 imply that the \Sigma-order on \Sigma , I and F (the initial lift algebra and the final lift coalgebra, respectively) is (pointwise) implication, that 1 and 2 imply that complete extensional objects (we call them complete regular \Sigma-posets) are stable under lifting, that under 1,2,3, axiom 4 is equivalent to \Sigma having binary joins, and that if \Sigma is closed under N-idexed joins in \Omega, then all complete objects are stable under lifting. We also present an analysis of when I is an internal colimit of a diagram 0->L(0)->L^2(0)->... Chapters 2,3,4 investigate models. We study models of the axioms in: the Modified realizability topos Mod, the Effective topos Eff, and a particular Grothendieck topos. In Mod, the Scott principle fails and L(2) is not complete. In Eff, we have that the internal colimit of 0->L(0)->L^2(0)->... is complete (whence it is not isomorphic to I), and a general theorem characterizing I for \neg\neg-separated dominances. Finally, in a sheaf topos we have an example where L(2) is complete but L(N) isn't. Jaap van Oosten Date: Fri, 18 Dec 1998 17:44:08 -0800 From: Dusko Pavlovic Subject: categories: preprint Dear All, As many of you know, December is the season of two column logic/CS related preprints. The title of mine is: Towards semantics of guarded induction and it is at the bottom of the page http://www.kestrel.edu/HTML/people/pavlovic/ Comments **most** welcome, esp. as I am still a bit in the darkness as to how to present some parts. This is still an extended abstract, but a bit more extended and less abstract than the version some of you have seen before. (Thanks again for the questions that helped me improve it!) With the very best wishes, -- Dusko ============================================================================== Towards semantics of guarded induction by Dusko Pavlovic Abstract. We analyze guarded induction, a coalgebraic method for implementing abstract data types with infinite elements (e.g. various dynamic systems, continuous or discrete). It is widely used not just in computation, but also, tacitly, in many basic constructions of differential calculus. However, while syntactic characterisations abound, only the very first steps towards a formal semantics have been made. A language independent analysis was recently initiated, but just special cases were covered so far. In the present paper, we propose a new approach, based on a somewhat unusual combination of monads and polynomial categories. The first result is what appears to be a precise semantic characterisation of guarded operators on arbitrary final coalgebras. Date: Tue, 22 Dec 1998 11:36:02 +0000 (GMT) From: Anne Heyworth Subject: categories: thesis (involving rewriting and Kan extensions) New PhD thesis to be found at: http://xxx.lanl.gov/abs/math.CT/9812097 Summary of details: Title: Applications of Rewriting Systems and Groebner Bases to Computing Kan Extensions and Identities Among Relations. Authors: Anne Heyworth (University of Wales, Bangor). Comments: PhD thesis, 104 pages, LaTeX2e. Report-no: University of Wales, Bangor preprint number 98-23. Subj-class: Category Theory; Combinatorics. MSC-class: 18-04 (Primary) 05-02; 20F05; 68Q42; 68Q40; 16S15 (Secondary). \\ This thesis concentrates on the development and application of Groebner bases methods to a range of combinatorial problems (involving groups, semigroups, categories, category actions, algebras and K-categories). Chapter Two contains the generalisation of rewriting and Knuth-Bendix procedures to Kan extensions. Chapter Three shows that the standard Knuth-Bendix algorithm is step-for-step a special case of the Buchberger's algorithm for noncommutative Groebner bases. The one-sided cases and higher dimensions are considered, and the relations between these are made precise. Chapter Four relates rewrite systems, Groebner bases and automata. Reduction machines for rewrite systems are identified with standard output automata and the reduction machines devised for algebras are expressed as Petri-nets. Chapter Five introduces logged rewriting for group presentations. The completion of a logged rewriting system for a group determines a partial contracting homotopy which enables the computation of a set of generators for the module of identities among relations using the covering groupoid methods devised by Brown and Razak Sallah. Reducing the resulting set of submodule generators is identified as a Groebner basis problem. -- Anne Heyworth. Subject: categories: Paper Announcement Date: Wed, 06 Jan 1999 18:04:29 +0000 From: Alex Simpson The following paper is available by anonymous FTP or over the Web Lambda Definability with Sums via Grothendieck Logical Relations by Marcelo Fiore and Alex Simpson We introduce a notion of *Grothendieck logical relation* and use it to characterise the definability of morphisms in *stable* bicartesian closed categories by terms of the simply-typed lambda calculus with finite products and finite sums. Our techniques are based on concepts from topos theory, however our exposition is elementary. The paper is written in a style appropriate for the conference Typed Lambda-Calculi and Applications where it is to be presented in April. However, we briefly discuss the true categorical content of the paper, which will be further expanded upon in a full version of the paper (forthcoming). The paper is available over the Web: http://www.dcs.ed.ac.uk/~mf/TYPES/glr.{dvi,ps} http://www.dcs.ed.ac.uk/~als/Research/glr.ps.gz or by anonymous FTP: ftp://ftp.dcs.ed.ac.uk/pub/mf/TYPES/glr.{dvi,ps} ftp://ftp.dcs.ed.ac.uk/pub/als/Research/glr.ps.gz Best wishes for a happy New Year, Alex Simpson -- Alex Simpson, LFCS, Division of Informatics, University of Edinburgh Email: Alex.Simpson@dcs.ed.ac.uk Tel: +44 (0)131 650 5113 FTP: ftp.dcs.ed.ac.uk/pub/als Fax: +44 (0)131 667 7209 URL: http://www.dcs.ed.ac.uk/home/als Date: Tue, 12 Jan 1999 12:32:25 -0500 From: Zhaohua Luo Subject: categories: categorical geometry In a recent paper (TAC, Vol 4, 208-248) On Generic Separable Objects, by Robbie Gates, the author mentioned a well known "boolean algebraic structure of the summands of an object in an extensive category". This reminded me a paper I posted to my homepage last year (8/30/98, see the abstract below), in which the same boolean structure was reconstructed (at that time this was not "well known" to me), and was applied to define the Pierce topology for any extensive category, extending some results of Diers. The paper Pierce Topologies of Extensive Categories is available at Categorical Geometry Homepage at the following new (permanent, hopefully) address http://www.geometry.net (or http://www.azd.com) (The new service is a little bit slow, but offers more functions than the old one, so please be patient.) Best wishes, Zhaohua Luo ------------------------------------------------------------------------------- Pierce Topologies of Extensive Categories by Zhaohua Luo Abstraction An extensive category is a category with finite stable disjoint sums. In this note we show that each extensive category carries a natural subcanonical coherent Grothendieck topology defined by injections of sums. This Grothendieck topology is induced by a strict metric topology, which is a functor to the category of Stone spaces. We call this metric topology the Pierce topology of the category, as it generalizes the classical Pierce spectrums of commutative rings. Recall that the Pierce spectrum of a commutative ring R is the spectrum of the Boolean algebra of idempotents of R, which is a Stone space. A theorem of R. S. Pierce states that R can be represented as the ring of global sections of a sheaf of commutative rings on its Pierce spectrum (called the Pierce sheaf or representation), whose stalks are indecomposable rings (with respect to product decomposations). Diers showed that Pierce's theorem can be extended to any object in a locally finitely presentable category such that the opposite of the subcategory of finitely presentable objects is lextensive (called a locally indecomposable category). We shall see that a weak form of Pierce representation exists for any object in an extensive category. Subject: categories: Paper Announcement Date: Wed, 20 Jan 1999 12:28:53 +0000 From: Alex Simpson The following paper is available by anonymous FTP or over the Web Computational Adequacy in an Elementary Topos We place simple axioms on an elementary topos which suffice for it to provide a denotational model of call-by-value PCF with sum and product types. The model is synthetic in the sense that types are interpreted by their set-theoretic counterparts within the topos. The main result characterises when the model is computationally adequate with respect to the operational semantics of the programming language. We prove that computational adequacy holds if and only if the topos is $1$-consistent (i.e. its internal logic validates only true $\Sigma^0_1$-sentences). This paper is to appear in the forthcoming proceedings of CSL 98. It is available from: http://www.dcs.ed.ac.uk/~als/Research/adequacy.ps.gz ftp://ftp.dcs.ed.ac.uk/pub/als/Research/adequacy.ps.gz Best wishes, Alex Simpson -- Alex Simpson, LFCS, Division of Informatics, University of Edinburgh Email: Alex.Simpson@dcs.ed.ac.uk Tel: +44 (0)131 650 5113 FTP: ftp.dcs.ed.ac.uk/pub/als Fax: +44 (0)131 667 7209 URL: http://www.dcs.ed.ac.uk/home/als Subject: categories: Generalized Enrichment Date: Fri, 29 Jan 1999 12:29:26 +0000 (GMT) From: Tom Leinster The following is now available, at http://www.dpmms.cam.ac.uk/~leinster/ Generalized Enrichment for Categories and Multicategories In this paper we answer the question: `what kind of a structure can a general multicategory be enriched in?' (Here `general multicategory' is used in the sense of the author, Burroni or Hermida.) The answer is, in a sense to be made precise, that a multicategory of one type can be enriched in a multicategory of the type one level up. In particular, we will be able to speak of a T_n-multicategory enriched in a T_{n+1}-multicategory, where T_n is the monad expressing the pasting-together of n-opetopes. The answer for general multicategories reduces to something surprising in the case of ordinary categories: a category may be enriched in an `fc-multicategory', a very general kind of 2-dimensional structure encompassing monoidal categories, plain multicategories, bicategories and double categories. It turns out that fc-multicategories also provide a natural setting for the bimodules construction. We also explore enrichment for some multicategories other than just categories. An extended application is given: the relaxed multicategories of Borcherds and Soibelman are explained in terms of enrichment. Tom Leinster PS - There's been the odd problem in the past with the web address; if it doesn't work, try substituting "can" for "www", or send me an email. From: Koslowski Subject: categories: paper announcement Date: Mon, 1 Feb 1999 01:00:07 +0100 (MET) A heavily revised version of my paper "Beyond the Chu-construction" is now available from my home page: http://www.iti.cs.tu-bs.de/~koslowj/RESEARCH/ It will eventually be published in Applied Categorical Structures. I have not attempted to attribute the term "dualizing object" to anyone in particular. The open problem of an earlier version, as to whether Cauchy-complete bicategories of interpolads inherit local *-autonomy from their base, has been answered affirmatively. Here is the abstract: Starting from symmetric monoidal closed (= autonomous) categories, Po-Hsiang Chu showed how to construct new *-autonomous categories, i.e., autonomous categories that are self-dual because of a dualizing object. Recently, Michael Barr extended this to the non-symmetric, but closed, case, utilizing monads and modules between them. Since these notions are well-understood for bicategories, we introduce a notion of local *-autonomy for these that implies closedness and, moreover, is inherited when forming bicategories of monads and of interpolads. Since the initial step of Barr's construction also carries over to the bicategorical setting, we recover his main result as an easy corollary. Furthermore, the Chu-construction at this level may be viewed as a procedure for turning the endo-1-cells of a closed bicategory into the objects of a new closed bicategory, and hence conceptually is similar to constructing bicategories of monads and of interpolads. Best regards, -- J"urgen -- J"urgen Koslowski % If I don't see you no more in this world ITI % I meet you in the next world TU Braunschweig % and don't be late! koslowj@iti.cs.tu-bs.de % Jimi Hendrix (Voodoo Child) From: john baez Subject: categories: higher-dimensional algebra and Planck-scale physics Date: Fri, 5 Feb 1999 17:26:13 -0800 (PST) Here is a new paper of mine that may be interesting to fans of categories and n-categories: Higher-Dimensional Algebra and Planck-Scale Physics to appear in "Physics Meets Philosophy at the Planck Scale", eds. Craig Callender and Nick Huggett, Cambridge U. Press, Cambridge. This is a nontechnical introduction to recent work on quantum gravity that uses ideas from higher-dimensional algebra. We argue that reconciling general relativity with the Standard Model requires a `background-free quantum theory with local degrees of freedom propagating causally'. We describe the insights provided by work on topological quantum field theories such as quantum gravity in 3-dimensional spacetime. These are background-free quantum theories lacking local degrees of freedom, so they only display some of the features we seek. However, they suggest a deep link between the concepts of `space' and `state', and similarly those of `spacetime' and `process', which we argue is to be expected in any background-free quantum theory. We sketch how higher-dimensional algebra provides the mathematical tools to make this link precise. Finally, we comment on attempts to formulate a theory of quantum gravity in 4-dimensional spacetime using `spin networks' and `spin foams'. Available in LaTeX and Postscript form at http://xxx.lanl.gov/abs/gr-qc/9902017 and in Postscript form at http://math.ucr.edu/home/baez/planck.ps From: Peter Selinger Subject: categories: Paper Announcement: Control Categories and Duality Date: Tue, 23 Feb 1999 00:09:47 -0500 (EST) Dear Category Theorists, The paper "Control Categories and Duality: on the Categorical Semantics of the Lambda-Mu Calculus" is now available from http://www.math.lsa.umich.edu/~selinger/papers.html http://hypatia.dcs.qmw.ac.uk/author/SelingerP This is a revised and improved version of a paper I presented at MFPS'98. Let me briefly summarize the part of the paper that I think will be the most interesting to category theorists; the actual abstract is appended at the end. Consider a category C with distributive finite products and coproducts and a distinguished object R, such that all exponentials of the form R^A exist. Let R^C denote the full subcategory of C consisting of objects of the form R^A. It is an old observation that R^C is cartesian-closed. This observation is at the heart of continuation passing style (CPS) interpretations of programming languages with control operators, and it has been used recently by Hofmann and Streicher to give a sound and complete categorical model of Parigot's lambda-mu calculus. (The lambda-mu calculus generalizes the simply-typed lambda calculus; it is a proof term calculus for propositional classical logic). In this paper, I give an independent, algebraic characterization of the structure of categories of the form R^C. By "independent", I mean that it does not depend on an ambient category C, and by "algebraic", that it is given in terms of operations and equations only. The crucial structure that R^C has, besides cartesian closure, is an operation called "classical disjunction" that takes R^A and R^B to R^(AxB). This operation is functorial in each argument, but not bifunctorial; it forms a premonoidal structure in the sense of Power and Robinson. Abstracting from R^C, I define the class of "control categories", which are cartesian-closed categories with a premonoidal structure and suitable axioms. The presence of an operation which is not bifunctorial leads to some interesting twists, as one has to be a bit careful about how one defines concepts such as weak structure-preserving functors and equivalences of categories. The main theorem is a structure theorem, which shows that every control category is equivalent to a category of the form R^C (and, of course, vice versa). An algebraic class of categories calls out for an internal language. I prove that the call-by-name lambda-mu calculus (with product and disjunction types) forms an internal language for control categories. Thus, these categories can be considered as models for (a certain kind of) proof theory of classical logic. Also, the call-by-value lambda-mu-calculus forms an internal language for the dual class of co-control categories. As a consequence of this categorical duality, it follows that there is a syntactic duality between the call-by-name and the call-by-value calculus, i.e., there are mutually inverse translations between call-by-name and call-by-value that preserve the categorical (and also the operational) semantics. Such dualities have been observed in a different setting by Filinski. In the case of the lambda-mu calculus, such a syntactic duality was conjectured by Streicher and Reus. Comments are welcome. Best wishes, -- Peter Selinger ---------------------------------------------------------------------- ABSTRACT: We give a categorical semantics to the call-by-name and call-by-value versions of Parigot's lambda-mu calculus with disjunction types. We introduce the class of control categories, which combine a cartesian-closed structure with a premonoidal structure in the sense of Power and Robinson. We prove, via a categorical structure theorem, that the categorical semantics is equivalent to a CPS semantics in the style of Hofmann and Streicher. We show that the call-by-name lambda-mu calculus forms an internal language for control categories, and that the call-by-value lambda-mu calculus forms an internal language for the dual co-control categories. As a corollary, we obtain a syntactic duality result: there exist syntactic translations between call-by-name and call-by-value which are mutually inverse and which preserve the operational semantics. This answers a question of Streicher and Reus. From: Philippe Gaucher Subject: categories: Oriented homotopy and Concurrency Date: Wed, 24 Feb 1999 23:50:21 +0100 Dear category theorists, Here is an annoucement of preprint. URL : http://www-irma.u-strasbg.fr/~gaucher/multi_en.ps.gz or http://www-irma.u-strasbg.fr/irma/publications/1999/99010.shtml Title : Homotopy invariants of multiple categories and concurrency in computer science Abstract : We associate to any (strict) multiple category $\C$ three homology theories : the first one is called the globular homology and it contains the oriented loops of $\C$ ; both other ones are called corner homology, the negative one and the positive one, which contain the corners included in $\C$. We show up the link between this homology theories and the homotopy of paths in multiple category. At the end of the paper, we explain the reason why this theories are interesting for some geometric problems coming from computer science. Date: Thu, 25 Feb 1999 00:01:23 -0500 From: "Robert A.G. Seely" Subject: categories: Paper on linear bicategories (and non-commutative linear logic) I would like to announce the following paper, which has been posted on my www site . (The McGill ftp site is currently not functionning, but as soon as it is restored, this paper ought to appear on the Hypatia mirror site as well.) The abstract follows. =================================== Introduction to linear bicategories by J.R.B. Cockett, J. Koslowski, R.A.G. Seely Linear bicategories are a generalization of the notion of a bicategory, in which the one horizontal composition is replaced by two (linked) horizontal compositions. These compositions provide a semantic model for the tensor and par of linear logic: in particular, as composition is fundamentally noncommutative, they provides a suggestive source of models for noncommutative linear logic. In a linear bicategory, the logical notion of complementation becomes a natural linear notion of adjunction. Just as ordinary adjoints are related to (Kan) extensions, these linear adjoints are related to the appropriate notion of linear extension. There is also a stronger notion of complementation, which arises, for example, in cyclic linear logic. This sort of complementation is modelled by cyclic adjoints. This leads to the notion of a *-linear bicategory and the coherence conditions which it must satisfy. Cyclic adjoints also give rise to linear monads: these are, essentially, the appropriate generalization (to the linear setting) of Frobenius algebras. A number of examples of linear bicategories arising from different sources are described, and a number of constructions which result in linear bicategories are indicated. This paper is dedicated to Jim Lambek, as part of the celebration of his 75th birthday. Date: Tue, 9 Mar 1999 10:17:18 -0500 (EST) From: James Stasheff Subject: categories: Quantum vertex algebras math.QA/9903038 [abs, src, ps, other] : Title: Quantum vertex algebras Authors: Richard E. Borcherds Comments: 18 pages, plain tex Subj-class: Quantum Algebra; Category Theory concludes with a large set of problems some of which are strictly n-categorical The purpose of this paper is to make the theory of vertex algebras trivial. We do this by setting up some categorical machinery so that vertex algebras are just ``singular commutative rings'' in a certain category. This makes it easy to construct many examples of vertex algebras, in particular by using an analogue of the construction of a twisted group ring from a bicharacter of a group. We also define quantum vertex algebras as singular braided rings in the same category and construct some examples of them. The constructions work just as well for higher dimensional analogues of vertex algebras. (18kb) ************************************************************ Jim Stasheff jds@math.upenn.edu 146 Woodland Dr Lansdale PA 19446 (215)822-6707 Jim Stasheff jds@math.unc.edu Math-UNC (919)-962-9607 Chapel Hill NC FAX:(919)-962-2568 27599-3250 Date: Thu, 11 Mar 1999 14:20:07 +0000 (GMT) From: Anne Heyworth Subject: categories: Rewrite Methods for Kan Extensions of Actions of Categories The following is available on the xxx archive. http://xxx.soton.ac.uk/abs/math.CO/9903032 Title: Using Rewriting Systems to Compute Kan Extensions and Induced Actions of Categories Authors: Ronald Brown, Anne Heyworth (University Of Wales, Bangor) Comments: 31 pages, LaTeX2e, (submitted to JSC) Subj-class: Combinatorics MSC-class: 68Q42 18A40 68Q40 The basic method of rewriting for words in a free monoid given a monoid presentation is extended to rewriting for paths in a free category given a `Kan extension presentation'. This is related to work of Carmody-Walters on the Todd-Coxeter procedure for Kan extensions, but allows for the output data to be infinite, described by a language. The result also allows rewrite methods to be applied in a greater range of situations and examples, in terms of induced actions of monoids, categories, groups or groupoids. (28kb) Prof R. Brown, School of Mathematics, University of Wales, Bangor Dean St., Bangor, Gwynedd LL57 1UT, United Kingdom Tel. direct:+44 1248 382474|office: 382475 fax: +44 1248 383663 World Wide Web: home page: http://www.bangor.ac.uk/~mas010/ New article: Higher dimensional group theory Symbolic Sculpture and Mathematics: http://www.bangor.ac.uk/SculMath/ Mathematics and Knots: http://www.bangor.ac.uk/ma/CPM/exhibit/welcome.htm Dr Anne Heyworth, School of Mathematics, University of Wales, Bangor home page: http://www.bangor.ac.uk/~map130/welcome.html Date: Wed, 10 Mar 1999 14:29:03 +0800 (CST) From: farn@iis.sinica.edu.tw (Farn Wang) Subject: categories: Report on verification of unknown number of processes Recently, we have developed a new verification technique which can be used to verify infinite state systems. A manuscript: Verification of Dynamic Linear Lists for All Numbers of Processes in PostScript format can be obtained through my webpage: http://www.iis.sinica.edu.tw/~farn/index.html#quo A preliminary report can also be found in TR-IIS-98-019 published last year. Thank you for reading this email. Best wishes, Farn ABSTRACT: In real-world design and verification of concurrent systems with many identical processes, the number of processes is never a factor in the system correctness. This paper embodies such an engineering reasoning to propose an almost automatic method to safely verify safety properties of such systems. The central idea is to construct a finite collective quotient structure (CQS) which collapses state-space representations for all system implementations with all numbers of processes. The problem is presented as safety bound problem which ask if the number of processes satisfying a certain property exceeds a given bound. Our method can be applied to systems with dynamic linear lists of unknown number of processes. Processes can be deleted from or inserted at any position of the linear list during transitions. We have used our method to develop CQS constructing algorithms for two classes of concurrent systems : (1) untimed systems with a global waiting queue and (2) dense-time systems with one local timer per process. We show that our method is both sound and complete in verifying the first class of systems. The verification problem for the second class systems is undecidable even with only one global binary variable. However, our method can still automatically generate a CQS of size no more than 1512 nodes to verify that an algorithm in the class: Fischer's timed algorithm indeed preserves mutual exclusion for any number of processes. Subject: categories: Weak Bisimulation and Open Maps Date: Thu, 06 May 1999 12:54:46 +0100 From: Luca Cattani The following paper, to be presented at LICS '99, is available from my home page: http://www.cl.cam.ac.uk/~glc25/weabom.html . Weak Bisimulation and Open Maps Marcelo Fiore Gian Luca Cattani Glynn Winskel COGS Computer Laboratory BRICS Univ. Sussex, UK Univ. Cambridge, UK Univ. Aarhus, DK Abstract A systematic treatment of weak bisimulation and observational congruence on presheaf models is presented. The theory is developed with respect to a ``hiding'' functor from a category of paths to observable paths. Via a view of processes as bundles, we are able to account for weak morphisms (roughly only required to preserve observable paths) and to derive a saturation monad (on the category of presheaves over the category of paths). Weak morphisms may be encoded as strong ones via the Kleisli construction associated to the saturation monad. A general notion of weak open-map bisimulation is introduced, and results relating various notions of strong and weak bisimulation are provided. The abstract theory is accompanied by the concrete study of two key models for concurrency, the interleaving model of synchronisation trees and the independence model of labelled event structures. Comments are welcome. Luca -- ----------------------------------------------------------- Gian Luca Cattani Phone: +44 (0)1223 334697 Cambridge University Fax: +44 (0)1223 334678 Computer Laboratory, email: Luca.Cattani@cl.cam.ac.uk New Museums Site, Pembroke Street, CB2 3QG, Cambridge, United Kingdom ----------------------------------------------------------- Date: Fri, 7 May 1999 11:51:07 +0100 From: grandis@dima.unige.it (Marco Grandis) Subject: categories: Preprint: Combinatorial homology and image analysis The following preprint is available, at my home page and by ftp: Combinatorial homology and image analysis M. Grandis ABSTRACT. This is the sequel of a paper, cited as Part I ("An intrinsic homotopy theory for simplicial complexes, with applications to image analysis"), introducing intrinsic homotopies and homotopy groups for simplicial complexes. We study here the relations of this intrinsic homotopy theory with the well-known intrinsic homology theory of simplicial complexes. Also here, the applications are aimed at image analysis. A metric space X has a structure t_e(X) of simplicial complex at each resolution e > 0; the corresponding *metric combinatorial homology groups* H_n( t_e(X)) can be directly computed, in cases of interest for applications, via the Mayer-Vietoris exact sequence and a study of deformation retracts given in Part I. http://www.dima.unige.it/STAFF/GRANDIS/ "ftp://pitagora.dima.unige.it/WWW/FTP/GRANDIS/Cmb2.May99.ps With best regards Marco Grandis Dipartimento di Matematica Universita' di Genova via Dodecaneso 35 16146 GENOVA, Italy e-mail: grandis@dima.unige.it tel: +39.010.353 6805 fax: +39.010.353 6752 Date: Wed, 16 Jun 1999 15:51:20 +0200 (MET DST) From: "I. Moerdijk" Subject: categories: Preprint: I. Moerdijk: "On the Connes-Kreimer construction of Hopf algebras" I. Moerdijk: "On the Connes-Kreimer construction of Hopf algebras" Abstract: We give a universal construction of families of Hopf P-algebras for any Hopf operad P. As a special case, we recover the Connes-Kreimer Hopf algebra of rooted trees. Available from http://www.math.uu.nl/people/moerdijk/preprints.html. --------------------------------------- Date: Sat, 19 Jun 1999 12:35:14 -0700 From: Vaughan Pratt Subject: categories: Coimbra course notes on Chu Spaces The notes for my course on Chu Spaces in Coimbra next month are online at http://boole.stanford.edu/pub/coimbra.ps.gz Vaughan Pratt Date: Tue, 22 Jun 1999 15:53:36 +1000 From: Claudio Hermida Subject: categories: preprint: Representable Multicategories The preprint `Representable multicategories' is available at http://www.maths.usyd.edu.au:8000/u/hermida Abstract: We introduce the notion of representable multicategory, which stands in the same relation to that of monoidal category as fibration does to contravariant pseudofunctor (into Cat). We give an abstract reformulation of multicategories as monads in a suitable Kleisli bicategory of spans. We describe representability in elementary terms via universal arrows. We also give a doctrinal characterisation of representability based on a fundamental monadic adjunction between the 2-category of multicategories and that of strict monoidal categories. The first main result is the coherence theorem for representable multicategories, asserting their equivalence to strict ones, which we establish via a new technique based on the above doctrinal characterisation. The other main result is a 2-equivalence between the 2-category of representable multicategories and that of monoidal categories and strong monoidal functors. This correspondence extends smoothly to one between bicategories and a localised version of representable multicategories. -- Claudio Hermida School of Mathematics and Statistics F07, University of Sydney, Sydney, NSW 2006, Australia Date: Thu, 24 Jun 1999 08:53:40 -0500 From: Walter Tholen Subject: categories: HHA article available The following paper is now available: A Categorical Guide to Separation, Compactness and Perfectness Walter Tholen Based on a rather arbitrary class of morphisms in a category, which play the role of "closed maps", we present a general approach to separation and compactness, both at the object and the morphism levels. It covers essential parts of the classical topological theory, generalizes various previous categorical treatments of the theme, and allows for a number of less expected applications outside topology. Homology, Homotopy and Applications, Vol. 1, 1999, No. 6, pp 147-161 http://www.rmi.acnet.ge/hha/volumes/1999/n6/n6.dvi http://www.rmi.acnet.ge/hha/volumes/1999/n6/n6.ps http://www.rmi.acnet.ge/hha/volumes/1999/n6/n6.dvi.gz http://www.rmi.acnet.ge/hha/volumes/1999/n6/n6.ps.gz ftp://ftp.rmi.acnet.ge/pub/hha/volumes/1999/n6/n6.dvi ftp://ftp.rmi.acnet.ge/pub/hha/volumes/1999/n6/n6.ps ftp://ftp.rmi.acnet.ge/pub/hha/volumes/1999/n6/n6.dvi.gz ftp://ftp.rmi.acnet.ge/pub/hha/volumes/1999/n6/n6.ps.gz Date: Mon, 12 Jul 1999 16:21:32 +0200 From: Anton Antonov Subject: categories: Category theory for Mathematica -> HPF Hi, Recently I presented in the Hewlett Packard conference HiPer'99 the paper "Translating Mathematica expressions to High Performance Fortran" with the following abstract: This paper introduces some ideas for translating the functional language Mathematica to the data-parallel language High Performance Fortran (HPF). It first discusses why we have the ability to do that. Then it gives some interpretations by Category Theory. Third the translating approach is presented for different Mathematica expressions that could be interpreted as specifications for parallel independence, reduction, task parallelism and subprogram's data mapping. Last is shown a simple executable program generated by the translator. You can find more about that on http://www.imm.dtu.dk./~aaa/MathematicaToHPF.html . I am glad that Category theory exists! With it I was able to express that Functional, Object-oriented and Parallel programing are the same kind of management. Regards Anton From: Peter Selinger Subject: categories: Paper announcement Date: Sat, 31 Jul 1999 00:45:43 -0400 (EDT) Dear Category Theorists, I am pleased to announce the availability of a new paper, Categorical Structure of Asynchrony, available via http://www.math.lsa.umich.edu/~selinger/papers.html. In this paper, I investigate properties of traced monoidal categories that are satisfied by networks of asynchronously communicating processes. Among these properties are Hasegawa's uniformity principle, as well as a version of Kahn's principle: the subcategory of *deterministic* processes is equivalent to a category of domains. The paper also contains the following observation, which may be of interest to categorists. I do not know whether this was observed before, and would be grateful for references. Suppose T:Set-->Set is a functor which is lax for the symmetric monoidal structure given by products on the category of sets. Then T associates to any category C another category C', which Benabou called the "direct image of C by T". This category is defined as follows: obj(C') = obj(C), and C'(X,Y) = T(C(X,Y)). The observation is that direct images preserve linear structure. More precisely, if the category C possesses some algebraic structure which is given by linear equations, then C' inherits that structure. Non-linear structure is not in general preserved, although one can give conditions on T under which the construction will preserve, for instance, affine structure. One can also loosen the conditions on T, so that it will only preserve non-commutative linear structure. One can use the direct image construction to extract the linear "part" of an arbitrary algebraic structure: for instance, if C has finite products, then C' has a monoidal structure with diagonals, which is precisely the part of a finite product structure which is given by linear equations. Traced monoidal structure with diagonals is the linear part of finite product structure with fixpoints. One direction of this, namely that the latter structure is a special case of the former, was observed by Hasegawa and by Hyland, but I don't know whether it had been noticed that the former is precisely the linear part of the latter. An example of a non-commutative linear structure (given by linear equations where the variables occur in the same left-to-right order on both sides) is the premonoidal structure of Power and Robinson. This is precisely the non-commutative part of monoidal structure. More details and examples are in the paper. Comments are, as usual, welcome. Best wishes, -- Peter Selinger ---------------------------------------------------------------------- ABSTRACT: We investigate a categorical framework for the semantics of asynchronous communication in networks of parallel processes. Abstracting from a category of asynchronous labeled transition systems, we formulate the notion of a categorical model of asynchrony as a uniformly traced monoidal category with diagonals, such that every morphism is total and the focus is equivalent to a category of complete partial orders. We present a simple, non-deterministic, cpo-based model that satisfies these requirements, and we discuss how to refine this model by an observational congruence. We also present a general construction of passing from deterministic to non-deterministic models, and more generally, from non-linear to linear structure on a category. Date: Sun, 01 Aug 1999 14:55:53 +0300 From: Zippora Arzi-Gonczarowski Subject: categories: Pre-print announcement The following pre-print is available: ----------------------------------------------------------------------- Perceive This as That - Analogies, Artificial Perception, and Category Theory By Zippora Arzi-Gonczarowski It is forthcoming in `The Annals of Mathematics and Artificial Intelligence'. ----------------------------------------------------------------------- Please e-mail to zippie@actcom.co.il if you want to receive the pre-print. (((((((( This paper is a continuation of the project that started with two papers that were already announced on this list: @article{aaa98, Author = "Z. Arzi-Gonczarowski and D. Lehmann", title = "Introducing the Mathematical Category of Artificial Perceptions", journal = "Annals of Mathematics and Artificial Intelligence", volume = "23", number = "3,4", month = "November", pages = "267--298", publisher = "Baltzer Science Publishers", address = "The Netherlands", year = "1998" } @article{bbb98, Author = "Z. Arzi-Gonczarowski and D. Lehmann", title = "From Environments to Representations--A Mathematical Theory of Artificial Perceptions", journal = "Artificial Intelligence", publisher = "Elsevier", address = "Amsterdam", volume = "102", number = "2", pages = "187--247", month = "July", year = "1998" } ))))))))) ----------------------------------------------------------------------- Dr. Zippora Arzi-Gonczarowski Typographics, Ltd. 46 Hehalutz St. Jerusalem 96222 Israel Tel:(+972)-2-6437819 Fax:(+972)-2-6434252 E-mail: zippie@actcom.co.il ----------------------------------------------------------------------- Date: Wed, 15 Sep 1999 19:02:00 -0400 From: Michael MAKKAI I am announcing a paper, and enclose an (somewhat) extended abstract. The paper is available at the site ftp://ftp.math.mcgill.ca/pub/makkai , the name of the file is mltomcat.zip . It is a ZIPPED package of 8 POSTSCRIPT files. When accessed through NETSCAPE, there was no difficulty getting it; but with ordinary ftp-ing, we couldn't get to it. The problems with the ftp sites here at McGill are being looked at, but they are not solved yet. The multitopic omega-category of all multitopic omega-categories by M. Makkai (McGill University) September 2, 1999 Abstract The paper gives two definitions: that of "multitopic omega-category" and that of "the (large) multitopic set of all (small) multitopic omega-categories". It also announces the theorem that the latter is a multitopic omega-category. (The proof of the theorem will be contained in a sequel to this paper.) The work has two direct sources. One is the paper [H/M/P] (for the references, see at the end of this abstract) in which, among others, the concept of "multitopic set" was introduced. The other is the present author's work on FOLDS, First Order Logic with Dependent Sorts. The latter was reported on in [M2]. A detailed account of the work on FOLDS is in [M3]. For the understanding of the present paper, what is contained in [M2] suffices. In fact, section 1 of the present paper gives the definitions of all that's needed in this paper; so, probably, there won't be even a need to consult [M2]. The concept of multitopic set, the main contribution of [H/M/P], was, in turn, inspired by the work of J. Baez and J. Dolan [B/D]. Multitopic sets are a variant of opetopic sets of loc. cit. The name "multitopic set" refers to multicategories, a concept originally due to J. Lambek [L], and given an only moderately generalized formulation in [H/M/P]. The earlier "opetopic set" of [B/D] is based on a concept of operad. I should say that the exact relationship of the two concepts ("multitopic set" and "opetopic set") is still not clarified. The main aspect in which the theory of multitopic sets is in a more advanced state than that of opetopic sets is that, in [H/M/P], there is an explicitly defined category Mlt of *multitopes*, with the property that the category of multitopic sets is equivalent to the category of Set-valued functors on Mlt, a result given a detailed proof in [H/M/P]. The corresponding statement on opetopic sets and opetopes is asserted in [B/D], but the category of opetopes is not described. In this paper, the category of multitopes plays a basic role. Multitopic sets and multitopes are described in section 2 of this paper; for a complete treatment, the paper [H/M/P] should be consulted. The indebtedness of the present work to the work of Baez and Dolan goes further than that of [H/M/P]. The second ingredient of the Baez/Dolan definition, after "opetopic set", is the concept of "universal cell". The Baez/Dolan definition of weak n-category achieves the remarkable feat of specifying the composition structure by universal properties taking place in an opetopic set. In particular, a (weak) opetopic (higher-dimensional) category is an opetopic set with additional properties ( but with no additional data), the main one of the additional properties being the existence of sufficiently many universal cells. This is closely analogous to the way concepts like "elementary topos" are specified by universal properties: in our situation, "multitopic set" plays the "role of the base" played by "category" in the definition of "elementary topos". In [H/M/P], no universal cells are defined, although it was mentioned that their definition could be supplied without much difficulty by imitating [B/D]. In this paper, the "universal (composition) structure" is supplied by using the concept of FOLDS-equivalence of [M2]. In [M2], the concepts of "FOLDS-signature" and "FOLDS-equivalence" are introduced. A (FOLDS-) signature is a category with certain special properties. For a signature L , an *L-structure* is a Set-valued functor on L. To each signature L, a particular relation between two variable L-structures, called L-equivalence, is defined. Two L-structures M, N, are L-equivalent iff there is a so-called L-equivalence span M<---P--->N between them; here, the arrows are ordinary natural trasnformations, required to satisfy a certain property called "fiberwise surjectivity". The slogan of the work [M2], [M3] on FOLDS is that *all meaningful properties of L-structures are invariant under L-equivalence*. As with all slogans, it is both a normative statement ("you should not look at properties of L-structures that are not invariant under L-equivalence"), and a statement of fact, namely that the "interesting" properties of L-structures are in fact invariant under L-equivalence. (For some slogans, the "statement of fact" may be false.) The usual concepts of "equivalence" in category theory, including the higher dimensional ones such as "biequivalence", are special cases of L-equivalence, upon suitable, and natural, choices of the signature L; [M3] works out several examples of this. Thus, in these cases, the slogan above becomes a tenet widely held true by category theorists. I claim its validity in the generality stated above. The main effort in [M3] goes into specifying a language, First Order Logic with Dependent Sorts, and showing that the first order properties invariant under L-equivalence are precisely the ones that can be defined in FOLDS. In this paper, the language of FOLDS plays no role. The concepts of "FOLDS-signature" and "FOLDS-equivalence" are fully described in section 1 of this paper. The definition of *multitopic omega-category* goes, in outline, as follows. For an arbitrary multitope SIGMA of dimension >=2, for a multitopic set S, for a pasting diagram ALPHA in S of shape the domain of SIGMA and a cell a in S of the shape the codomain of SIGMA, such that a and ALPHA are parallel, we define what it means to say that a is a *composite* of ALPHA. First, we define an auxiliary FOLDS signature L extending Mlt, the signature of multitopic sets. Next, we define structures S and S, both of the signature L, the first constructed from the data S and a , the second from S and ALPHA, both structures extending S itself. We say that a is a composite of ALPHA if there is a FOLDS-equivalence-span E between S and S that restricts to the identity equivalence-span from S to S . Below, I'll refer to E as an *equipment* for a being a composite of ALPHA. A multitopic set is a *mulitopic omega-category* iff every pasting diagram ALPHA in it has at least one composite. The analog of the universal arrows in the Baez/Dolan style definition is as follows. A *universal arrow* is defined to be an arrow of the form b:ALPHA-----> a where a is a composite of ALPHA via an equipment E that relates b with the identity arrow on a : in turn, the identity arrow on a is any composite of the empty pasting diagram of dimension dim(a)+1 based on a . Note that the main definition does *not* go through first defining "universal arrow". A new feature in the present treatment is that it aims directly at weak *omega*-categories; the finite dimensional ones are obtained as truncated versions of the full concept. The treatment in [B/D] concerns finite dimensional weak categories. It is important to emphasize that a multitopic omega category is still just a multitopic set with additional properties, but with no extra data. The definition of "multitopic omega-category" is given is section 5; it uses sections 1, 2 and 4, but not section 3. The second main thing done in this paper is the definition of MltOmegaCat. This is a particular large multitopic set. Its definition is completed only by the end of the paper. The 0-cells of MltOmegaCat are the samll multitopic omega-categories, defined in section 5. Its 1-cells, which we call 1-transfors (thereby borrowing, and altering the meaning of, a term used by Sjoerd Crans [Cr]) are what stand for "morphisms", or "functors", of multitopic omega-categories. For instance, in the 2-dimensional case, multitopic 2-categories correspond to ordinary bicategories by a certain process of "cleavage", and the 1-transfors correspond to homomorphisms of bicategories [Be]. There are n-dimensional transfors for each n in N . For each multitope (that is, "shape" of a higher dimensional cell) PI, we have the *PI-transfors*, the cells of shape PI in MltOmegaCat. For each fixed multitope PI, a PI-transfor is a *PI-colored multitopic set* with additional properties. "PI-colored multitopic sets" are defined in section 3; when PI is the unique zero-dimensional multitope, PI-colored multitopic sets are the same as ordinary multitopic sets. Thus, the definition of a transfor of an arbitrary dimension and shape is a generalization of that of "multitopic omega-category"; the additional properties are also similar, they being defined by FOLDS-based universal properties. There is one new element though. For dim(PI)>=2 , the concept of PI-transfor involves a universal property which is an omega-dimensional, FOLDS-style generalization of the concept of right Kan-extension (right lifting in the terminology used by Ross Street). This is a "right-adjoint" type universal property, in contrast to the "left-adjoint" type involved in the concept of composite (which is a generalization of the usual tensor product in modules). The main theorem, stated but not proved here, is that MltOmegaCat is a multitopic omega-category. The material in this paper has been applied to give formulations of omega-dimensional versions of various concepts of homotopy theory; details will appear elesewhere. I thank Victor Harnik and Marek Zawadowski for many stimulating discussions and helpful suggestions. I thank the members of the Montreal Category Seminar for their interest in the subject of this paper, which made the exposition of the material at a time when it was still in an unfinished state a very enjoyable and useful process for me. References: [B/D] J. C. Baez and J. Dolan, Higher-dimensional algebra III. n-categories and the algebra of opetopes. Advances in Mathematics 135 (1998), 145-206. [Be] J. Benabou, Introduction to bicategories. In: Lecture Notes in Mathematics 47 (1967), 1-77 (Springer-Verlag). [Cr] S. Crans, Localizations of transfors. Macquarie Mathematics Reports no. 98/237. [H/M/P] C. Hermida, M. Makkai and J. Power, On weak higher dimensional categories I. Accepted by: Journal of Pure and Applied Algebra. Available electronically (when the machines work ...). [L] J. Lambek, Deductive systems and categories II. Lecture Notes in Mathematics 86 (1969), 76-122 (Springer-Verlag). [M2] M. Makkai, Towards a categorical foundation of mathematics. In: Logic Colloquium '95 (J. A. Makowski and E. V. Ravve, editors). Lecture Notes in Logic 11 (1998) (Springer-Verlag). [M3] M. Makkai, First Order Logic with Dependent Sorts. Research momograph, accepted by Lecture Notes in Logic (Springer-Verlag). Under revision. Original form available electronically (when the machines work ...). Cheers: M. Makkai Date: Thu, 16 Sep 1999 12:15:16 -0400 From: Michael MAKKAI Subject: categories: announcement update This is an update on the announcement I made yesterday. I announced the paper "The multitopic omega-category of all multitopic omega-categories". The site I named for it does not seem to work, however. Instead, try http://mystic.biomed.mcgill.ca/M_Makkai As I said earlier, you'll find MLTOMCAT.ZIP, a ZIPped package of 8 POSTSCRIPT files. Good luck: M. Makkai Date: Sun, 19 Sep 1999 18:26:36 -0400 From: Michael MAKKAI Subject: categories: second update This is the second update on the paper "The multitopic omega-category of all multitopic omega-categories". The zip-file that got onto both sites I mentioned before was bad. I have now replaced it with another one which I had tested for "unzipping". The two sites: ftp://ftp.math.mcgill.ca/pub/makkai http://mystic.biomed.mcgill.ca/M_Makkai The filename is MLTOMCAT.ZIP. It is a ZIPped package of 8 POSTSCRIPT files. M. Makkai Date: Fri, 24 Sep 1999 10:27:48 +0100 From: grandis@dima.unige.it (Marco Grandis) Subject: categories: preprint: Simplicial toposes and combinatorial homotopy The following preprint is available: M. Grandis Simplicial toposes and combinatorial homotopy, Dip. Mat. Univ. Genova, Preprint 400 (1999). Abstract. The term *combinatorial topos* denotes here a topos of presheaves over a small subcategory of the category of finite sets. The main instances we want to consider are the presheaf categories of simplicial sets, cubical sets, and globular sets, together with their symmetric versions: e.g., the topos !Smp of symmetric simplicial sets consists of all presheaves on the category !Delta of finite, positive cardinals. We show here how combinatorial homotopy, developed in previous works for simplicial complexes (the cartesian closed subcategory of *simple* presheaves in !Smp) can be extended to the topos !Smp. As a crucial advantage, the (extended) fundamental groupoid Pi_1: !Smp --> Gpd is left adjoint to a natural functor M_1: Gpd --> !Smp, the symmetric nerve of a groupoid, and therefore - as a strong van Kampen property - preserves all colimits. Analogously, a notion of (non-reversible) *directed* homotopy can be developed in Smp, with applications to image analysis similar to the ones of the symmetric case. We have now a homotopy n-category functor C_n: Smp --> n-Cat, left adjoint to a nerve N_n = n-Cat(C_n(Delta[n]), -). It would be interesting to determine whether the n-category C_n(Delta[n]) coincides with Street's oriental O_n, and the previous nerve with Street's, as it seems likely. ___ Available at: ftp://pitagora.dima.unige.it/WWW/FTP/GRANDIS/CmbTop.Sep99.ps (459 K) ___ Marco Grandis Dipartimento di Matematica Universita' di Genova via Dodecaneso 35 16146 GENOVA, Italy e-mail: grandis@dima.unige.it tel: +39.010.353 6805 fax: +39.010.353 6752 http://www.dima.unige.it/STAFF/GRANDIS/ ftp://pitagora.dima.unige.it/WWW/FTP/GRANDIS/ Date: Fri, 01 Oct 1999 18:30:06 +0000 From: Fabio Gadducci Subject: categories: paper announcement Dear members of the mailing list, I'm pleased to annouce that the paper ``Rewriting on Cyclic Structures'', by myself and Andrea Corradini, is available at http://www.di.unipi.it/~gadducci/papers/RAIRO.ps. The abstract follows, but shortly, it uses traced monoidal 2-categories --where, in addition, each object ha`s a comonoidal structure-- in order to simulate various kinds of (eventually cyclic) term (graph) rewriting. Its interest for a broader audience may lie, besides in showing a practical application of the trace structure in the rewriting field, in its appendix, where we tried to sketch a very SHORT history of the notion of feedback in theoretical computer science, with a particular attention to the algebraic specification field. We found it interesting to review previous approaches to the topic, after the results of Joyal-Street-Verity have newly sparkled the interest in the algebraic description of fixed points (see e.g. the recent paper by Selinger advertised a few weeks ago on this mailing list). Best regards, Fabio Gadducci xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx \begin{abstract} We present a categorical formulation of the rewriting of possibly cyclic term graphs, based on a variation of algebraic 2-theories. We show that this presentation is equivalent to the well-accepted operational definition proposed by Barendregt et alii---but for the case of ``circular redexes'', for which we propose (and justify formally) a different treatment. The categorical framework allows us to model in a concise way also automatic garbage collection and rules for sharing/unsharing and folding/unfolding of structures, and to relate term graph rewriting to other rewriting formalisms. \end{abstract} Date: Tue, 12 Oct 1999 14:18:48 +0100 From: kock Subject: categories: preprint available The preprint Algebra of Principal Fibre Bundles, and Connections is available at ftp://ftp.imf.au.dk/pub/kock/princ4.ps (102 kb). The classical relationship between the curvature of a connection, and the coboundary of its connection form, here comes about from a pure groupoid calculation. The preprint updates and expands my 1983/1986 paper, "Combinatorial notions relating to principal fibre bundles". Anders Kock http://www.imf.au.dk/~kock/ From: Martin Escardo Date: Fri, 29 Oct 1999 16:25:57 +0100 (BST) Subject: categories: function spaces Dear Comprox and Categories members, Here is a short note that Reinhold Heckmann and I have written. Your comments are welcome, as always. On function spaces in topology ------------------------------ It is the purpose of this expository note to provide a self-contained, elementary and brief development of the fact that the exponentiable topological spaces are precisely the core-compact spaces. The only prerequisite is a basic knowledge of topology (continuous functions, product topology and compactness). We hope that teachers and students of topology will find this useful. As far as we know, there is no such development available in the literature. Although there are one or two embellishments, our methods are certainly not original. We briefly discuss more advanced treatments in the introduction. ------------------------------------------------------------------- http://www.dcs.st-and.ac.uk/~mhe/papers/exponentiablespaces.ps.gz http://www.dcs.st-and.ac.uk/~mhe/papers/exponentiablespaces.dvi.gz http://www.dcs.st-and.ac.uk/~mhe/papers/exponentiablespaces.ps http://www.dcs.st-and.ac.uk/~mhe/papers/exponentiablespaces.dvi ------------------------------------------------------------------- Best regards, Martin & Reinhold Subject: categories: Paper announcement Date: Fri, 12 Nov 1999 14:05:07 +0000 From: Luca Cattani The following paper is available at http://www.cl.cam.ac.uk/~glc25/premcl.html . It will also be available soon as BRICS Report, RS-99-36 (see www.brics.dk/Publications), and as Cambridge University Computer Laboratory Technical Report n. 477 (contact tech-reports@cl.cam.ac.uk to obtain a hard copy) : Presheaf Models for CCS-like Languages Gian Luca Cattani Glynn Winskel Computer Laboratory BRICS University of Cambridge University of Aarhus England Denmark Abstract ========= The aim of this paper is to harness the mathematical machinery around presheaves for the purposes of process calculi. Joyal, Nielsen and Winskel proposed a general definition of bisimulation from open maps. Here we show that open-map bisimulations within a range of presheaf models are congruences for a general process language, in which CCS and related languages are easily encoded. The results are then transferred to traditional models for processes. By first establishing the congruence results for presheaf models, abstract, general proofs of congruence properties can be provided and the awkwardness caused through traditional models not always possessing the cartesian liftings, used in the break-down of process operations, are side-stepped. The abstract results are applied to show that hereditary history-preserving bisimulation is a congruence for CCS-like languages to which is added a refinement operator on event structures as proposed by van Glabbeek and Goltz. Date: Mon, 15 Nov 1999 08:49:41 +1100 From: Claudio Hermida Subject: categories: coherence => universality (preprint) The preprint "From coherent structures to universal properties" is available from http://www.maths.usyd.edu.au:8000/u/hermida under coh-univ.ps Abstract: Given a 2-category K admitting a calculus of bimodules, and a 2-monad T on it compatible with such calculus, we construct a 2-category L with a 2-monad S on it such that: i) S has the adjoint-pseudo-algebra property. ii) The 2-categories of pseudo-algebras of S and T are equivalent. Thus, coherent structures (pseudo-T-algebras) are transformed into universally characterised ones (adjoint-pseudo-S-algebras). The 2-category L consists of lax algebras for the pseudo-monad induced by T on the bicategory of bimodules of K. We give an intrinsic characterisation of pseudo-S-algebras in terms of {\em representability\/}. Two major consequences of the above transformation are the classifications of lax and strong morphisms, with the attendant coherence result for pseudo-algebras. We apply the theory in the context of internal categories and examine monoidal and monoidal globular categories (including their {\em monoid classifiers\/}) as well as pseudo-functors into Cat. -- Claudio Hermida School of Mathematics and Statistics F07, University of Sydney, Sydney, NSW 2006, Australia From: Martin Escardo Date: Thu, 18 Nov 1999 09:15:52 +0000 (GMT) Subject: categories: Re: function spaces I wrote: > It is the purpose of this expository note to provide a > self-contained, elementary and brief development of the fact that > the exponentiable topological spaces are precisely the > core-compact spaces. The only prerequisite is a basic knowledge of > topology (continuous functions, product topology and compactness). > We hope that teachers and students of topology will find this > useful. As far as we know, there is no such development available > in the literature. Although there are one or two embellishments, > our methods are certainly not original. > >------------------------------------------------------------------- > http://www.dcs.st-and.ac.uk/~mhe/papers/exponentiablespaces.ps It turns out, as Fred Linton kindly let me know just after I posted this, that Eilenberg developed such an account to general function spaces in topology. Yesterday I got a copy of Eilenberg's manuscript (in the literal sense of manuscript) that Fred Linton sent me, which I read with pleasure. Apparently this will be eventually published. It was written around 1985. So, after all, there is (going to be) such a development available in the literature. The methods that both papers use are the same, and are due to Fox, Arens, Dugundji, Day and Kelly, Scott, and Isbell (although we combine them in different ways). These references and most of these methods are discussed in a paper on function spaces published by Isbell in 1985. Martin