*mbx* 3bb593a900000000 2-Sep-1996 15:56:49 -0300,895;000000000000-00000000 Received: from bigmac.mta.ca by mailserv.mta.ca; (5.65/1.1.8.2/09Sep94-0117PM) id AA03101; Mon, 2 Sep 1996 15:56:48 -0300 Date: Mon, 2 Sep 1996 15:55:35 -0300 (ADT) From: categories To: categories Subject: flexible sheaves Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII 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 3-Sep-1996 17:23:21 -0300,3632;000000000000-00000000 Received: from bigmac.mta.ca by mailserv.mta.ca; (5.65/1.1.8.2/09Sep94-0117PM) id AA16978; Tue, 3 Sep 1996 17:23:21 -0300 Date: Tue, 3 Sep 1996 17:22:10 -0300 (ADT) From: categories To: categories Subject: Revision of paper on ftp Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII 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 ) 3-Sep-1996 17:23:22 -0300,2327;000000000000-00000000 Received: from bigmac.mta.ca by mailserv.mta.ca; (5.65/1.1.8.2/09Sep94-0117PM) id AA01534; Tue, 3 Sep 1996 17:23:21 -0300 Date: Tue, 3 Sep 1996 17:21:19 -0300 (ADT) From: categories To: categories Subject: Ph.D. Studentships Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Date: Tue, 3 Sep 96 12:58:36 BST From: Roy L. Crole LEICESTER UNIVERSITY, UK, FUNDED PH.D. STUDENTSHIPS COMPUTER SCIENCE The University is offering 2 fully funded research studentships in computer science leading to the award of a Ph.D. degree, commencing in October 1996, or as soon as possible thereafter, for three years. Applications are invited from high quality, well motivated students. Candidates should have a first-class or good second-class honours degree. Students with an M.Sc. or equivalent degree may also apply. Students will receive maintenance allowances of 5050 UKpounds, and University fees will be waived. Applicants must be U.K. or European Community nationals. Applicants in those areas of computer science of interest to staff in the Department of Mathematics and Computer Science will be considered. These areas are mainly in theoretical computer science and include, but are not restricted to: categorical logic; computational aspects of combinatorial group and semigroup theory; computational complexity theory; design and analysis of algorithms; finite model theory; formal languages; formal methods; graph theory (pure, applied and algorithmic); operational and denotational semantics; program logics; real-time and fault-tolerant systems; and type theory. More details can be found via the Departmental WWW entry whose URL is: http://www.mcs.le.ac.uk In the first instance, applicants should contact, AS SOON AS POSSIBLE, one of: Dr. Roy Crole, email r.crole@mcs.le.ac.uk Prof. Iain A. Stewart, email i.a.stewart@mcs.le.ac.uk Dr. Rick M. Thomas, email r.thomas@mcs.le.ac.uk Department of Mathematics and Computer Science, University of Leicester, University Road, LEICESTER, LE1 7RH, United Kingdom. Dept Tel +44 (0)116 252 3884 Fax +44 (0)116 252 3604 or +44 (0)116 252 3915 4-Sep-1996 14:44:34 -0300,1609;000000000001-00000000 Received: from bigmac.mta.ca by mailserv.mta.ca; (5.65/1.1.8.2/09Sep94-0117PM) id AA30264; Wed, 4 Sep 1996 14:44:34 -0300 Date: Wed, 4 Sep 1996 14:44:10 -0300 (ADT) From: categories To: categories Subject: preprint: Minimal Realization in Bicategories of Automata Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII 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. 4-Sep-1996 14:44:41 -0300,3697;000000000001-00000000 Received: from bigmac.mta.ca by mailserv.mta.ca; (5.65/1.1.8.2/09Sep94-0117PM) id AA00458; Wed, 4 Sep 1996 14:44:41 -0300 Date: Wed, 4 Sep 1996 14:44:33 -0300 (ADT) From: categories To: categories Subject: preprints available Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII 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) 5-Sep-1996 14:12:02 -0300,7223;000000000001-00000000 Received: from bigmac.mta.ca by mailserv.mta.ca; (5.65/1.1.8.2/09Sep94-0117PM) id AA17184; Thu, 5 Sep 1996 14:12:02 -0300 Date: Thu, 5 Sep 1996 14:11:00 -0300 (ADT) From: categories To: categories Subject: Correction to paper - distributive is not weakly distributive Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII 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) 11-Sep-1996 11:54:26 -0300,2845;000000000000-00000000 Received: from bigmac.mta.ca by mailserv.mta.ca; (5.65/1.1.8.2/09Sep94-0117PM) id AA03946; Wed, 11 Sep 1996 11:54:26 -0300 Date: Wed, 11 Sep 1996 11:52:54 -0300 (ADT) From: categories To: categories Subject: PhD Studentship at Birmingham Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Date: Tue, 10 Sep 1996 17:49:58 +0100 From: Eike Ritter The School of Computer Science, University of Birmingham, England, has a research studentship available, tenable from 1 October 1996 for three years. The research student will work under the supervision of Dr Eike Ritter as part of the theory group, of which the other members are Dr Natasha Alechina, Dr Marta Kwiatkowska, Prof Achim Jung, Dr Valeria de Paiva and Dr Mark Ryan. The group has expanded significantly in the last few years and has an excellent reputation in the development of logics and the semantics for programming languages. The research student should be willing to work in the area of functional languages, type theory and logic. The student might participate in Dr Ritter and Dr de Paiva's project on investigating how to model memory allocation and garbage collection in type theory and how to construct abstract machines for functional languages. We are seeking applications from high-quality and well-motivated students, normally in their final year of undergraduate studies or finishing an M.Sc. or equivalent degree in Mathematics or Computer Science, or a closely related subject. Candidates are expected to obtain either a first class or upper second class honours degree. The successful candidate will receive a studentship with similar terms to an EPSRC-studentship, with a basic minimum of 5,190.00 pounds pa. University tuition fees will be waived. Applicants must be eligible residents of the UK or the European Union. Informal enquiries about the studentship are most welcome and should be directed to Dr Eike Ritter, Tel. +44-121-414-4772, e-mail: E.Ritter@cs.bham.ac.uk. Application forms can be obtained from the address below, or electronically in PostScript at http://www.cs.bham.ac.uk/~pjh/prospectus/general_info/appl_form.ps/. There are notes to help you fill it in at http://www.cs.bham.ac.uk/~pjh/prospectus/research/res_appl_form_www.html. The closing date for applications is 15 October 1996. Late applications will be considered if the selection process has not advanced too far. Dr Eike Ritter University of Birmingham, School of Computer Science Edgbaston Birmingham B15 2TT Office: First floor, room 122 Tel: +44 121 414 4772 Fax: +44 121 414 4281 Email: E.Ritter@cs.bham.ac.uk Home Page: http://www.cs.bham.ac.uk/~exr 11-Sep-1996 11:54:28 -0300,972;000000000000-00000000 Received: from bigmac.mta.ca by mailserv.mta.ca; (5.65/1.1.8.2/09Sep94-0117PM) id AA11232; Wed, 11 Sep 1996 11:54:27 -0300 Date: Wed, 11 Sep 1996 11:53:47 -0300 (ADT) From: categories To: categories Subject: Co-well-poweredness of varieties of algebras Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Date: Tue, 10 Sep 1996 21:18:11 -0700 From: William H. Rowan If we are given an algebra A in a variety of algebras, then the set of onto homomorphisms with domain A is obviously a small set. Is the same true of the set of epimorphisms in the variety, with domain A? I believe this is what is meant by asking, "Is the variety co-well-powered?" In any case, I think the answer must be known, and I think the answer is yes, but I don't have any reference. So, could someone help me with this? Bill Rowan 11-Sep-1996 13:16:31 -0300,1125;000000000001-00000000 Received: from bigmac.mta.ca by mailserv.mta.ca; (5.65/1.1.8.2/09Sep94-0117PM) id AA04626; Wed, 11 Sep 1996 13:16:31 -0300 Date: Wed, 11 Sep 1996 13:15:42 -0300 (ADT) From: categories To: categories Subject: Re: Co-well-poweredness of varieties of algebras Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Date: Wed, 11 Sep 1996 11:48:31 -0400 (EDT) From: Peter Freyd William Rowan asks if equational varieties, when viewed as categories, are well-co-powered. Yes. A method of proof appears in my 1964 "Abelian Categories" on pages 91-93. The context of the method is much more general: it holds for any category whose objects are defined as the models of a given set of elementary sentences and whose maps are defined as the functions that preserve a given set of elementary formulae. Ditto for well-poweredness. I believe, also, that that book is the initial appearence of "co-well-powered". It should, of course, have been "well-co-powered". 11-Sep-1996 21:25:35 -0300,729;000000000000-00000000 Received: from bigmac.mta.ca by mailserv.mta.ca; (5.65/1.1.8.2/09Sep94-0117PM) id AA19842; Wed, 11 Sep 1996 21:25:33 -0300 Date: Wed, 11 Sep 1996 21:23:38 -0300 (ADT) From: categories To: categories Subject: Re: Co-well-poweredness of varieties of algebras Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Date: Wed, 11 Sep 1996 12:55:51 -0400 (EDT) From: Peter Freyd Minor point. John mentions that his argument for algebras "obviously extends to infinitary algebras but Peter's doesn't." But it does. I guess it's a matter of what one means by "obviously". 13-Sep-1996 12:09:16 -0300,1785;000000000000-00000000 Received: from bigmac.mta.ca by mailserv.mta.ca; (5.65/1.1.8.2/09Sep94-0117PM) id AA13854; Fri, 13 Sep 1996 12:09:16 -0300 Date: Fri, 13 Sep 1996 12:07:30 -0300 (ADT) From: categories To: categories Subject: Physical braids Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Date: Thu, 12 Sep 1996 23:54:28 -0700 From: Vaughan Pratt Forwarded from Phillip Schewe's Physics News Update, #285: BRAIDS PLAITED BY MAGNETIC HOLES. The study of braids and knots is important for both mathematics (where it is a subfield of topology) and for quantum physics, where it is used to describe the interactions of particles in an abstract multidimensional phase space. Now physicists at the Institute of Energy Technology in Norway (Geir Helgesen, geirh@ife.no) have demonstrated a practical way to investigate complicated braids using tiny beads confined between two plates and subjected to complex magnetic fields. The motion of these beads constitutes a three-dimensional braid if you consider time as a third spatial dimension; a sequence of photos of the beads at regular intervals is assembled into a plait-like trajectory not unlike the smoke trails used in wind-tunnel experiments, except that in this case the observed braid topology can reveal information about the magnetic fields pushing the beads around. The researchers expect that the behavior of the beads (actually non-magnetic spheres immersed in a ferrofluid) can be used as a simple experimental tool for modeling complex interactions in quantum field theory or chaos theory. (P. Pieranski et al., Physical Review Letters, 19 August 1996.) 16-Sep-1996 10:36:55 -0300,1139;000000000000-00000000 Received: from bigmac.mta.ca by mailserv.mta.ca; (5.65/1.1.8.2/09Sep94-0117PM) id AA09360; Mon, 16 Sep 1996 10:36:54 -0300 Date: Mon, 16 Sep 1996 10:35:29 -0300 (ADT) From: categories To: categories Subject: Re: Co-well-poweredness of varieties of algebras Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Date: Mon, 16 Sep 1996 14:22:06 +0200 (MET DST) From: Jiri Rosicky The fact that varieties are co-well-powered follows from much more general results proved in M.Makkai and R.Pare, Accessible categories: the foundation of categorical model theory, Cont. Math. 104, AMS 1989 (e.g., any accessible category with pushouts is co-well-powered). For locally presentable categories, which cover varieties, it is shown in P.Gabriel and F.Ulmer, Lokal Presentierbare Kategorien, L.N. in Math. 221 (1971). These results are also contained a recent book Locally Presentable and Accessible Categories, Cambridge Univ. Press 1994 written by J.Adamek and me. Jiri Rosicky 18-Sep-1996 11:58:06 -0300,632;000000000000-00000000 Received: by mailserv.mta.ca; (5.65/1.1.8.2/09Sep94-0117PM) id AA26057; Wed, 18 Sep 1996 11:55:41 -0300 Date: Wed, 18 Sep 1996 11:55:41 -0300 (ADT) From: categories To: categories Subject: papers available by ftp Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII 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 18-Sep-1996 14:11:19 -0300,4697;000000000000-00000000 Received: by mailserv.mta.ca; (5.65/1.1.8.2/09Sep94-0117PM) id AA05297; Wed, 18 Sep 1996 14:10:55 -0300 Date: Wed, 18 Sep 1996 14:10:53 -0300 (ADT) From: categories To: categories Subject: Grothendieck manuscripts Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Date: Wed, 18 Sep 1996 08:21:54 -0700 From: David Espinosa Here is a translation from French of an announcement that appeared on this list in July. I've included the original text, as the translation is probably inaccurate in places. David ------------------------- Date: Wed, 10 Jul 1996 11:14:37 +0200 (MET DST) To: mathmeca@oceane.cict.fr From: Nicolas Saby To: categories Subject: Free complete Heyting algebras Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Date: Mon, 23 Sep 96 11:42 BST From: Dr. P.T. Johnstone Does anyone know whether the free complete Heyting algebra on two generators exists? That is, does it have a set rather than a proper class of elements? It's obvious that the free cHa on aleph_0 generators is a proper class, since it has the free complete Boolean algebra on the same generators as a quotient. However, when you look at the finitary theory of Heyting algebras, the free algebra on two generators already exhibits all the bad behaviour you get in larger free algebras. (By the way, the free cHa on one generator does exist: it has just one more element than the free Ha on one generator.) Peter Johnstone 23-Sep-1996 13:59:46 -0300,943;000000000001-00000000 Received: by mailserv.mta.ca; (5.65/1.1.8.2/09Sep94-0117PM) id AA29351; Mon, 23 Sep 1996 13:59:16 -0300 Date: Mon, 23 Sep 1996 13:59:15 -0300 (ADT) From: categories To: categories Subject: irreducibility Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Date: Mon, 23 Sep 1996 17:31:19 +0200 From: Pierre Ageron Say that an object X in a category is irreducible iff Hom(X,-) preserves pushouts. Probably this (or a similar) notion is classical. Am I right ? 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 23-Sep-1996 15:23:17 -0300,1267;000000000001-00000000 Received: by mailserv.mta.ca; (5.65/1.1.8.2/09Sep94-0117PM) id AA05712; Mon, 23 Sep 1996 15:22:34 -0300 Date: Mon, 23 Sep 1996 15:22:33 -0300 (ADT) From: categories To: categories Subject: Re: irreducibility Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Date: Mon, 23 Sep 1996 13:55:53 -0400 (EDT) From: F William Lawvere Concerning Pierre Ageron's proposed definition of "irreducible" : Since such terms as "connected"," local", etc should always exclude the empty case, "connected" in particular is usually defined to mean preserving all coproducts (including the empty one) . Preserving moreover pushouts would then amount to "connected and projective", which in a presheaf category catches only the Cauchy completion of the representables. Usually "irreducible" is understood as something broader than that; for example among finite presheaves on a finite category, there are an infinite number of connected objects iff the finite category is not a groupoid. Indeed in G-sets for G a group, each orbit is connected, but the only orbit which is projective is the biggest one. 23-Sep-1996 15:33:59 -0300,1437;000000000001-00000000 Received: by mailserv.mta.ca; (5.65/1.1.8.2/09Sep94-0117PM) id AA28520; Mon, 23 Sep 1996 15:33:31 -0300 Date: Mon, 23 Sep 1996 15:33:30 -0300 (ADT) From: categories To: categories Subject: Re: Free complete Heyting algebras Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Date: Mon, 23 Sep 1996 14:27:29 -0400 (EDT) From: F William Lawvere Concerning Peter Johnstone's question about the free complete Heyting algebras on finitely many generators: 1) If the free one on one generator is presented as a finitary algebra on two generators, presumably it is infinitely related ? 2) Is the result re one generator valid in any topos ? If so, the method so effective in complex analysis might conceivably work : the n+1 generator algebra is a one generator algebra in a topos over n dimensional space ? 3) I often speculated that a useful way of picturing these things might be to consider the parallel coHeyting algebras and use Euler-Venn diagrams with a more subtle interpretation that takes boundaries seriously. 4) There is apparently a connection between this idea of achieving completeness with few elements and Andy Pitts result concerning adjoints between finitary algebras. Can this connection be spelled out more precisely ? Bill Lawvere 24-Sep-1996 13:51:30 -0300,1116;000000000001-00000000 Received: by mailserv.mta.ca; (5.65/1.1.8.2/09Sep94-0117PM) id AA08166; Tue, 24 Sep 1996 13:49:38 -0300 Date: Tue, 24 Sep 1996 13:49:36 -0300 (ADT) From: categories To: categories Subject: Re: Free complete Heyting algebras Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Date: Tue, 24 Sep 96 10:00 BST From: Dr. P.T. Johnstone Replies to two of Bill's questions: 1) If the free one on one generator is presented as a finitary algebra on two generators, presumably it is infinitely related ? Yes. The free cHa on one generator is not finitely presentable as a finitary Ha. 2) Is the result re one generator valid in any topos ? I don't think so: the proof that I know relies on the decidedly non-constructive fact that every subset of the free Ha on one generator (L, say) is either finite or cofinal in L - {\top}. So I don't see much hope of getting an inductive proof along the lines suggested by Bill. Peter Johnstone 24-Sep-1996 13:51:35 -0300,2879;000000000001-00000000 Received: by mailserv.mta.ca; (5.65/1.1.8.2/09Sep94-0117PM) id AA08373; Tue, 24 Sep 1996 13:50:33 -0300 Date: Tue, 24 Sep 1996 13:50:31 -0300 (ADT) From: categories To: categories Subject: Re: Free complete Heyting algebras Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Date: Tue, 24 Sep 1996 11:05:59 +0000 From: Steve Vickers >... (By the way, the free >cHa on one generator does exist: it has just one more element than the >free Ha on one generator.) /// >2) Is this result re one generator valid in any topos ? (1) Certainly not as stated: if H is the free Ha on one generator (a, say), then one new element is not enough to complete it. (2) Its completion to a frame (over H qua distributive lattice (DL)) is the ideal completion Idl(H). (Classically, there is only one non-principal ideal.) One might ask whether this is the free cHa generated by a (as it is classically), but this seems unlikely to me - though I don't quite have a definitive counterexample. Let B be a cHa with a given element b. Then there is a unique Ha homomorphism f: H -> B taking a to b, and since f is a DL homomorphism, there is a unique frame homomorphism g: Idl(H) -> B taking a (or, rather, the principal ideal generated by a) to b. If there is a cHa homomorphism taking a to b, it must be g; but it remains to prove that g is a Heyting algebra homomorphism. In Idl(H), let I be {0} u {a: p} for some proposition p. Then I -> 0 is {x in H: p => x/\a = 0} For g to preserve ->, we must have \/{b: p} -> 0 = \/{f(x): p => x/\a = 0} Hence if p => c/\b = 0 we must have c < \/{f(x): p => x/\a = 0}. Let us construct B and c as follows: let L be the DL generated by H (qua DL) and c, subject to the p-indexed set of relations c/\a = 0 (if p), and let B be Idl(L). (Note that the injection of generators H -> L -> B is different from f.) Then this concrete construction reduces the condition c < \/{f(x): p => x/\a = 0} to showing that there exists x in H such that p => x/\a = 0 and c < f(x). Classically, we take x to be /\{~a: p}, but constructively this meet is not finite and so doesn't necessarily exist in H. (3) Assuming the reasoning in (2) goes through, it still leaves open the question of whether the free cHa on one generator exists (constructed in some other way). (4) Incidentally, the original question is ambiguous, surely? To define the notion of free cHa you must define the notion of homomorphism between cHa's. Assuming that all joins must be preserved, must all meets also be preserved, or - a la frames - only finitary ones? The question doesn't arise with complete Boolean algebras, where negation is an order antiisomorphism. Steve Vickers. 25-Sep-1996 10:40:18 -0300,3703;000000000001-00000000 Received: by mailserv.mta.ca; (5.65/1.1.8.2/09Sep94-0117PM) id AA03670; Wed, 25 Sep 1996 10:39:09 -0300 Date: Wed, 25 Sep 1996 10:39:07 -0300 (ADT) From: categories To: categories Subject: Announcement of paper: FILL Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII 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 25-Sep-1996 10:40:31 -0300,898;000000000001-00000000 Received: by mailserv.mta.ca; (5.65/1.1.8.2/09Sep94-0117PM) id AA07661; Wed, 25 Sep 1996 10:39:48 -0300 Date: Wed, 25 Sep 1996 10:39:46 -0300 (ADT) From: categories To: categories Subject: Re: Free complete Heyting algebras Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Date: Tue, 24 Sep 1996 16:22:02 -0400 (EDT) From: Peter Freyd With regard to PeterJ's answer to BillL's question 1: a quick way to see that the free cHa on one generator is not finitely presentable is to use the fact that any finitely presented Ha is residually finite. Residual finiteness is, in turn, equivalent to everything being the sup of the finite elements below it (where finite element means one with only a finite number of elements below it). 25-Sep-1996 15:54:52 -0300,840;000000000000-00000000 Received: by mailserv.mta.ca; (5.65/1.1.8.2/09Sep94-0117PM) id AA20679; Wed, 25 Sep 1996 15:53:56 -0300 Date: Wed, 25 Sep 1996 15:53:56 -0300 (ADT) From: categories To: categories Subject: Re: Free complete Heyting algebras Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Date: Wed, 25 Sep 1996 14:26:39 -0400 (EDT) From: F William Lawvere Peter J and Steve V offered comments which suggest the following sharpening of my vague proposal for approaching Peter's interesting problem : 1. Which toposes with free finitary algebras have also the free cocomplete HA on one generator ? 2.Do these include toposes based on free HAs as sites ? Bill Lawvere 26-Sep-1996 12:10:08 -0300,1071;000000000001-00000000 Received: by mailserv.mta.ca; (5.65/1.1.8.2/09Sep94-0117PM) id AA30691; Thu, 26 Sep 1996 12:09:01 -0300 Date: Thu, 26 Sep 1996 12:09:00 -0300 (ADT) From: categories To: categories Subject: Re: irreducibility Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Date: Thu, 26 Sep 1996 11:33:11 +0200 From: Pierre Ageron As William Lawvere pointed out courteously, my tentative definition of "irreducible" was stupid. So let me ask: is there a standard categorical treatment of irreducibility (or, dually, of primality), or is it an essentially order-theoretic concept? Pierre Ageron 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 28-Sep-1996 11:43:51 -0300,1052;000000000001-00000000 Received: by mailserv.mta.ca; (5.65/1.1.8.2/09Sep94-0117PM) id AA23217; Sat, 28 Sep 1996 11:42:55 -0300 Date: Sat, 28 Sep 1996 11:42:55 -0300 (ADT) From: categories To: categories Subject: Conference Picture Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Date: Fri, 27 Sep 1996 16:33:10 -0400 From: Walter Tholen I have put a group photograph of the participants of the Oberwolfach meeting on Descent Theory from a year ago on my home page. Regards, Walter. -- Walter Tholen tel: (1-416) 736 5250 Dept. of Mathematics and Statistics or 736 2100 ext. 33918 York University fax: (1-416) 736 5757 North York, Ontario email: tholen@mathstat.yorku.ca Canada M3J 1P3 web: http://www.math.yorku.ca/Who/Faculty/Tholen/menu.html