From cat-dist Wed Jan 7 13:06:26 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id MAA01424; Wed, 7 Jan 1998 12:59:50 -0400 (AST) Date: Wed, 7 Jan 1998 12:59:50 -0400 (AST) From: categories To: categories Subject: Functor algebras Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Tue, 06 Jan 1998 17:26:17 -0600 From: Uday S Reddy Happy New Year, everyone. I have been wondering about a little question. Category theory texts talk about "algebras" for an endofunctor, which are arrows of type FA -> A, and dually coalgebras A -> GA. I am interested in the symmetric case, arrows of type FA -> GA for endofunctors F and G. Have such structures been studied? This is only scratching the surface. One can ask for a family of such arrows for an algebra. One can consider functors F,G: C -> D between different categories leading to algebras of the form GA> where A is an object of C, and f an arrow in D, and so on. I am also interested in the "diagonal" case, arrows of type FAA -> GAA where F and G are functors C^op x C -> C. (Note that all these structures have a "natural" notion of homomorphisms.) I would appreciate any pointers to the literature. Uday Reddy From cat-dist Wed Jan 7 17:58:18 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id RAA32108; Wed, 7 Jan 1998 17:58:09 -0400 (AST) Date: Wed, 7 Jan 1998 17:58:08 -0400 (AST) From: categories To: categories Subject: FMCS 98 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Wed, 7 Jan 1998 12:07:33 -0800 (PST) From: Jeff Lewis **** Announcement and Registration **** Foundational Methods in Computer Science: A workshop on applications of categories in computer science May 29--31, 1998 Reed College, Portland, Oregon Sponsored by the Computer Science and Engineering Department at Oregon Graduate Institute of Science & Technology and the Department of Mathematics at Reed College. The workshop is an informal meeting to bring together researchers in mathematics and computer science with a focus on the application of category theory in computer science. It is a three day meeting that starts off with a day of tutorials aimed at students and newcomers to category theory, followed by a day and a half of research talks. All sessions will be held on the Reed campus which is quiet, beautifully landscaped, and adjacent to a park and a public golf course. Guest speakers at this year's workshop include: David Espinosa (Kestrel Institute) Richard Jullig (Arrow Logics) Eugenio Moggi (University of Genova) Philip Wadler (Lucent) The remaining research talks are solicited from the participants. Time is limited, so please register early if you would like to give a talk. Student participation is particularly encouraged at FMCS. We have applied for an NSF grant which would provide some support for students to attend the workshop. Please inquire if you are interested. The registration fee is $105 for regular registration and $70 for students. Registration includes reception, all meals, including a banquet, and proceedings of the meeting. The lodging fee is $80, which covers 3 nights lodging ($25/night) and linen fee ($5.00) at Reed College. Please visit the FMCS98 web site for further details: http://www.cse.ogi.edu/PacSoft/conf/fmcs ** Registration ** Please send registration information via email to Kelly@cse.ogi.edu. You can also register on-line at http://www.cse.ogi.edu/PacSoft/conf/fmcs/registration.html Advance payment is preferred. Checks should be payable to Oregon Graduate Institute and should reference FMCS98. They should be mailed to: FMCS98 (Kelly Atkinson) Computer Science and Engineering Oregon Graduate Institute P.O. Box 91000 Portland, OR 97291-1000 Name: Job title: Affiliation: Address: email: phone: fax: registration fee (regular = $105, student = $70): _______ Vegetarian banquet meal? (yes/no) presentation? (yes/no) title: Accommodation: dorm rooms: (list nights needed) cost = $5.00 + ____ nights * $25 = $__.00 If you want to stay off campus, please make those arrangements on your own. Please mark the days you plan to attend: Reception, Thursday, May 28, 1998 ____ Friday, May 29, 1998 ____ Saturday, May 30, 1998 ____ Sunday, May 31, 1998 ____ Extra Banquet tickets ($25/person): ** Questions? ** If you have any questions or comments, please contact Jeff Lewis, Jim Hook or Kelly Atkinson at OGI. Jeff Lewis jlewis@cse.ogi.edu Phone: (503) 690-4035 Fax: (503) 690-1548 James Hook hook@cse.ogi.edu Phone: (503) 690-1169 Fax: (503) 690-1548 Kelly Atkinson kelly@cse.ogi.edu Phone: (503) 690-1336 Fax: (503) 690-1548 Department of Computer Science and Engineering Oregon Graduate Institute of Science & Technology P.O. Box 91000 Portland, OR 97291-1000 From cat-dist Thu Jan 8 16:29:19 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id QAA22065; Thu, 8 Jan 1998 16:28:34 -0400 (AST) Date: Thu, 8 Jan 1998 16:28:33 -0400 (AST) From: categories To: categories Subject: Re: Functor algebras Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Wed, 7 Jan 1998 23:06:24 -0500 (EST) From: Ernie Manes > > Date: Tue, 06 Jan 1998 17:26:17 -0600 > From: Uday S Reddy > > Happy New Year, everyone. > > I have been wondering about a little question. Category theory texts > talk about "algebras" for an endofunctor, which are arrows of type FA -> > A, and dually coalgebras A -> GA. I am interested in the symmetric > case, arrows of type FA -> GA for endofunctors F and G. > Have such structures been studied? > > This is only scratching the surface. One can ask for a family of such > arrows for an algebra. One can consider functors F,G: C -> D between > different categories leading to algebras of the form GA> where > A is an object of C, and f an arrow in D, and so on. I am also > interested in the "diagonal" case, arrows of type FAA -> GAA where F and > G are functors C^op x C -> C. (Note that all these structures have a > "natural" notion of homomorphisms.) > > I would appreciate any pointers to the literature. > > Uday Reddy > > Algebras of form FA -> GA were considered in some detail by the Prague school in the 1970s. Email Jiri Adamek for precise references. egm From cat-dist Thu Jan 8 16:29:21 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id QAA20645; Thu, 8 Jan 1998 16:29:14 -0400 (AST) Date: Thu, 8 Jan 1998 16:29:13 -0400 (AST) From: categories To: categories Subject: Re: Functor algebras Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Thu, 08 Jan 1998 11:52:54 MEZ From: Martin Hofmann Dear Uday, There has been an Edinburgh PhD thesis by Tatsuya Hagino on the subject of the se dialgebras. He defines a strongly normalising lambda calculus based on initial terminal dialgebras and also does some general theory. Hope this helps, Martin -- Martin Hofmann AG Logik und mathemat. Grundl. der Informatik Fachbereich Mathematik Technische Hochschule Darmstadt Schlossgartenstrasse 7 D-64289 Darmstadt Germany Tel. : x49-6151-16-3615 FAX : x49-6151-16-4011 e-mail: mh@mathematik.th-darmstadt.de WWW : http://www.mathematik.th-darmstadt.de/ags/ag14/mitglieder/hofmann-e.html From cat-dist Thu Jan 8 16:33:20 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id QAA14778; Thu, 8 Jan 1998 16:33:19 -0400 (AST) Date: Thu, 8 Jan 1998 16:33:19 -0400 (AST) From: categories To: categories Subject: Workshop on Fixed Points Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Thu, 8 Jan 98 15:27 MET From: esik@inf.u-szeged.hu ******************************************************************************* ******************************************************************************* ** ** ** F I C S ' 9 8 ** ** ** ** Fixed Points in Computer Science ** ** ** ** A Satellite Workshop to MFCS'98 ** ** ** ** August 27-28, 1998, Brno, Czech Republic ** ** ** ** CALL FOR PAPERS ** ** ** ******************************************************************************* ******************************************************************************* Aim: Fixed points play a fundamental role in several areas of computer science, and the construction and properties of fixed points have been investigated in many different frameworks. The aim of the workshop is to provide a forum for researchers to present their results to those members of the computer science community who study or apply the fixed point operation in the different fields and formalisms. Topics: Construction and reasoning about properties of fixed points, categorical, metric and ordered fixed point models, continuous algebras, relation algebras, fixed points in process algebras and process calculi, regular algebra of finitary and infinitary languages, formal power series, tree automata and tree languages, infinite trees, the mu-calculus and other programming logics, fixed points in relation to dataflow and circuits, fixed points and the lambda calculus. Invited speakers: A. Arnold (Bordeaux) J. W. de Bakker (Amsterdam) Y. N. Moschovakis (Los Angeles/Athens) Program Committee: R. Backhouse (Eindhoven) S. L. Bloom (Hoboken) C. Boehm (Rome) R. De Nicola (Florence) Z. Esik (Szeged, chairman) P. Freyd (Philadelphia) I. Guessarian (Paris) D. Kozen (Cornell) W. Kuich (Vienna) M. Mislove (Tulane) R. F. C. Walters (Sydney) Contact person: Zoltan Esik Dept. of Computer Science Jozsef Attila University P.O.B. 652 6701 Szeged, Hungary e-mail: fics@inf.u-szeged.hu phone: ++36-62-454-289 fax: ++36-62-312-292 Paper submission: Authors are invited to send three copies of an abstract not exceeding three pages to the PC chair. Electronic submissions in the form of uuencoded postscript file are encouraged and can be sent to fics@inf.u-szeged.hu. Submissions are to be received before May 25, 1998. Authors will be notified of acceptance by June 25, 1998. Proceedings: Preliminary proceedings containing the abstracts of the talks will be available at the meeting. Publication of final proceedings as a special issue of Theoretical Informatics and Applications depends on the number and quality of the papers. The workshop will be organised at the same place as the federated MFCS'98/CSL'98 conference and care will be taken that participants of the workshop can attend invited talks of the MFCS and CSL conferences. No special registration fee will be required for participants who also register for MFCS'98 or CSL'98 and have a presentation at the workshop. Other workshop participants registered for MFCS'98 or CSL'98 will be requested to pay a small fee for the preliminary proceedings. Registration only for the workshop will also be possible--expenses for fee, accommodation, and basic meals will be very modest. Organising Committee: L. Bernatsky (Szeged) A. Kucera (Brno) T. Szeles (Szeged) More information is available at the following web sites: http://www.inf.u-szeged.hu/fics/ http://www.cs.stevens-tech.edu/CFP/FICS/ From cat-dist Fri Jan 9 09:55:11 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id JAA13743; Fri, 9 Jan 1998 09:54:40 -0400 (AST) Date: Fri, 9 Jan 1998 09:54:39 -0400 (AST) From: categories To: categories Subject: MFCS'98 CFPW Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Fri, 9 Jan 1998 14:38:43 +0100 (MET) From: Jiri Rosicky ******************************************************************************* ******************************************************************************* ** ** ** M F C S ' 9 8 ** ** ** ** ** ** Call for Papers, Call for Workshops ** ** The Current List of Workshops and Tutorials ** ** ** ** ** ** The 23rd International Symposium on ** ** Mathematical Foundations of Computer Science ** ** ** ** August 24-28, 1998, Brno, Czech Republic ** ** ** ** ** ******************************************************************************* ******************************************************************************* MFCS'98 is organised by the Faculty of Informatics of Masaryk University in cooperation with universities in Aachen, Hagen, Linz, Pisa, Szeged, Wien, and other institutions. MFCS'98 will be held 25 years after the first MFCS meeting in Czechoslovakia at Strbske pleso. MFCS'73 is remembered for taking a very broad, advanced, and stimulating view of the theoretical foundations of computing, and for the high scientific and organisational standard. MFCS'98 is intended to be another step along these lines. Programme Committee: S. Abramsky (Edinburgh), B. Buchberger (Linz), J. Diaz (Barcelona), V. Diekert (Stuttgart), J. Gruska, co-chair (Brno), I. Guessarian (Paris), T. Henzinger (Berkeley), R. J. Lipton (Princeton), G. Mirkowska (Pau), F. Moller (Uppsala), U. Montanari (Pisa), J. Nesetril (Prague), M. Paterson (Warwick), G. Paun (Bucharest), J. Sgall (Prague), W. Thomas (Kiel), J. Tiuryn (Warsaw), U. Vaccaro (Salerno), P. Vitanyi (Amsterdam), P. Voda (Bratislava), M. Wirsing (Munich), J. Zlatuska, co-chair (Brno).} Principal topics of interest include (but are not limited to): design and analysis of algorithms (sequential, parallel, distributed, approximation, computational biology, computational geometry, graph, network, number theory, on-line, optimisation) and data structures, automata, grammars and formal languages, complexity (communication, computational, descriptional) and computability, concurrency theory, cryptography and security, databases and knowledge-based systems, foundations of programming, formal specifications and program development, models of computation, parallel and distributed computing, quantum computing, molecular computing, semantics and logics of programs, theoretical issues in artifical intelligence. Invited talks of broad and stimulating orientation are offered, consistent with the more than quarter-century tradition of MFCS. Speakers: G. Ausiello (Rome), E. Borger (Pisa), Y. Gurevich (Ann Arbor), D. Harel (Rehovot), R.M. Karp (Seattle), F.T. Leighton (MIT-Cambridge), W. Maass (Graz), Yu. Matiyasevich (Petersburg), K. Mehlhorn (Saarbrucken), S. Micali (MIT-Cambridge), M. Nielsen (Aarhus), A. Pnueli (Rehovot), P. Pudlak (Prague), C. Stirling (Edinburgh), J. Wiedermann (Prague), M. Yannakakis (Murray Hill). MFCS'98 will have several tutorials and workshops. Proposals can be sent to PC co-chairs. The current list of workshops and tutorials is included below. The CSL'98 conference (Computer Science Logic) will be held in parallel with MFCS'98 at the same place. The federated CSL/MFCS conference will have common plenary sessions and social events. Participants registering for one conference can attend talks of both conferences and parallel workshops. Contact persons: Antonin Kucera (PC secretary) Jan Staudek (OC chair) Address: MFCS'98, Faculty of Informatics, Masaryk University Botanicka 68a, 60200 Brno, Czech Republic tel: ++420-5-4151 2336, fax: ++420-5-4121 2568 e-mail: {gruska,kucera,staudek,zlatuska,mfcs98}@fi.muni.cz}} WWW: http://www.fi.muni.cz/mfcs98/ Costs: The conference fee will be very reasonable as well as daily expenses (see the www page for details). The accommodation prices range from business-like level to very modest. Students will be able to participate at a very low cost. The best student papers will be specially recognised. The social programme will include a reception, an excursion to nearby attractions, a conference dinner, and activities for accompanying persons. First deadline: The first deadline is the usual one. Accepted papers go to the hard copy proceedings. Authors are invited to submit an extended abstract not exceeding 10 LNCS pages. Papers are thoroughly reviewed, double submissions other than those explicitly mentioned by MFCS/CSL PC are not allowed (see the www page for details). Submission: March 20, 1998 Notification: May 20, 1998 Second deadline: The second deadline is for `wild tiger' session (last minute hot topics). Accepted papers will appear in electronic proceedings. Authors are invited to send an abstract not exceeding 5 pages. The emphasis is on attractiveness of potential talks. There is no restriction on double submissions. Submission: July 1, 1998 Notification: August 1, 1998 All submission should be done electronically using special www forms. ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- ******************************************************************************* ******************************************************************************* ** ** ** ** ** MFCS'98 Workshops and Tutorials ** ** ** ** The 23rd International Symposium on ** ** Mathematical Foundations of Computer Science ** ** ** ** August 21-30, 1998, Brno, Czech Republic ** ** ** ** TENTATIVE ** ** ** ** ** ******************************************************************************* ******************************************************************************* CCA'98 - Workshop on Computability and Complexity (August, 24-27) ------------------------------------------------------------------ All aspects of computability and computational complexity with emphasis on the Turing machine model of computation. PC: Ker-I Ko (Stony Brook), A. Nerode (Cornell University), M. Pour-El (Minnessota), K. Weihrauch (chair, Hagen), J. Wiedermann (Prague). Deadline: May 25, 1998 Contact: Klaus.Weihrauch@fernuni-hagen.de FICS'98 - Fixed Points in Computer Science (August 27-28) ---------------------------------------------------------- Construction and reasoning about properties of fixed points in various models, algebras, and logics. PC: R. Backhouse (Eindhoven), S.L. Bloom (Hoboken), C. Boehm (Rome), R. De Nicola (Florence), Z. Esik (chair, Szeged), P. Freyd (Philadelphia), I. Guessarian (Paris), D. Kozen (Cornell), W. Kuich (Vienna), M. Mislove (Tulane), R.F.C. Walters (Sydney). Deadline: May 25, 1998 Contact: esik@inf.u-szeged.hu Frontiers between Decidability and Undecidability (August 24-25) ----------------------------------------------------------------- Frontiers between decidable and undecidable (halting) problems in various computational settings. PC: J. Gabarro (Barcelona), I. Korec (Bratislava), Yu. Rogozhin (Kishinev), M. Margenstern (co-chair, Metz), G. Mauri (Milan), K. Morita (co-chair, Hiroshima), G. Paun (Bucharest). Deadline: May 25, 1998 Contact: margens@antares.iut.univ-metz.fr MFCS'98 Workshop on Communications (August 24-25) -------------------------------------------------- Communication complexity, communication algorithms in networks, interactive and zero-knowledge proofs, cryptography and cryptographical protocols. PC: M. Dietzfelbinger (Dortmund), P. Duris (Bratislava), J. Hromkovic (chair, Aachen), A. Liesman (Burnaby), A. Pelz (Quebec), G. Schnitger (Frankfurt), J. Sgall (Prague), W. Unger (Paderborn) Deadline: May 15, 1998 Contact: jh@I1.Informatik.RWTH-Aachen.de MFCS'98 Workshop on Concurrency (August 27-28) ----------------------------------------------- Decidability and complexity issues, model checking, software tools for modelling and verification of concurrent systems, verification of infinite-state processes. PC: A. Bouajjani (Grenoble), J. Bradfield (Edinburgh), W. Brauer (Munich), P. Jancar (co-chair, Ostrava), M. Kretinsky (co-chair, Brno), M. Nielsen (Aarhus), C. Stirling (Edinburgh). Deadline: May 25, 1998 Contact: mojmir@fi.muni.cz MFCS'98 Workshop on Grammar Systems (August 22-23) -------------------------------------------------- Cooperating/distributed grammar systems, colonies, team grammar systems, eco-grammar systems, network and language processors. PC: E. Csuhaj-Varju (Budapest), J. Dassow (Magdeburg), J. Kelemen (Bratislava/Opava), A. Kelemenova (chair, Opava), G. Paun (Bucharest, Turku), D. Wotschke (Franfurkt). Deadline: May 31, 1998 Contact: kelemenova@fpf.slu.cz Molecular Computing (August 24-26) ----------------------------------- Any theoretical computer science directions of research on the possible use of DNA as a support for computation. PC: C. Calude (Auckland), T. Head (Binghamton), L. Kari (London-Ontario), K. Krithivasan (Madras), G. Paun (chair, Bucharest), T. Yokomori (Tokyo). Deadline: May 25, 1998 Contact: gpaun@imar.ro Randomized Algorithms (August 26-28) ------------------------------------ Design and analysis of randomized algorithms, derandomization, randomized complexity classes. PC: S. Arikawa (Fukuoka), S. Arora (Princeton), H. Buhrman (Amsterdam), C. Calude (Auckland), L. Fortnow (Chicago), R. Freivalds (chair, Riga), J. Hromkovic (Aachen), R. Impagliazzo (San Diego), L. Kucera (Prague), Ming Li (Waterloo), A. Lingas (Lund), S. Rajasekaran (Gainesville), J. Rolim (Geneva), O. Watanabe (Tokyo), R. Wiehagen (Kaiserslautern), T. Zeugmann (Fukuoka) Deadline: March 20, 1998 Contact: rusins@paul.cclu.lv Weak Arithmetic (August 27-28) ------------------------------ Weak arithmetics, complexity of logical theories, complexity of algorithms in number theory, recursive analysis. PC: P. Cegielski (chair, Paris), I. Korec (Bratislava), Y. Matyiasevich (Petersburg), D. Richard (Clermont-Ferrand). Deadline: March 20, 1998 Contact: cep@capella.liafa.jussieu.fr Xth Peripathetic Seminar on Sheaves and Logic, X >= 66 (August 29-30) --------------------------------------------------------------------- Category theory, sheaves, logic, applications to computer science. PC: none Deadline: August 29, 1998 Contact: rosicky@math.muni.cz ******************************************************************************* ******************************************************************************* ** ** ** ** ** MFCS'98 Tutorials ** ** ** ** ** ******************************************************************************* ******************************************************************************* Abstract state machines ----------------------- by E. Borger (Pisa) and Yu. Gurevich (Ann Arbor). Approximation algorithms ------------------------ by P.L. Crescenzi (Florence), J. Diaz (Barcelona), and A.M. Spaccamela (Rome). Quantum logic and quantum computing ----------------------------------- by K. Svozil (Wien) and A. Barenko (Geneva). The Theorema system: An introduction with demos ----------------------------------------------- by B. Buchberger and T. Jebelan (RISC -- Linz). ******************************************************************************* ******************************************************************************* ** ** ** For additional information see http://www.fi.muni.cz/mfcs98/ ** ** ** ** ** ** *** END of this message *** ** ** ** ** ** ******************************************************************************* ******************************************************************************* ----- End of forwarded message from Jozef Gruska ----- From cat-dist Sun Jan 11 15:14:42 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id PAA14282; Sun, 11 Jan 1998 15:09:04 -0400 (AST) Date: Sun, 11 Jan 1998 15:09:04 -0400 (AST) From: categories To: categories Subject: iced categories Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-Status: Date: Sun, 11 Jan 1998 09:56:26 -0500 (EST) From: Peter Freyd Since a good fraction of the world's category theorists are witnessing an historic ice-storm, can they tell us how they're faring? From cat-dist Mon Jan 12 14:38:34 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id OAA29710; Mon, 12 Jan 1998 14:38:01 -0400 (AST) Date: Mon, 12 Jan 1998 14:38:01 -0400 (AST) From: categories To: categories Subject: Re: iced categories Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Mon, 12 Jan 1998 09:39:46 -0500 From: P. Scott Dear Colleagues: Peter asked how things are going, so I thought I would mention what I know. As you all know, eastern Ontario and Quebec were hit by a massive ice storm: Montreal island was particularly badly hit. Downtown Montreal is apparently in very bad shape, with large areas still without power. The island was cut-off physically (all the bridges were down) for several days, and many downtown hotels are now without power. Many streets still have downed power-lines, and it is unsafe in some cases to walk near trees, buildings, or powerlines because of falling ice. Triples (and McGill) is down, so there is no e-mail contact for now. In terms of individuals, I have spoken to many of the categorists and everyone is ok although several people (Barr, Prakash,...) are without heat and power in their homes. They are either staying with friends or rigged-up some kind of power line from neighbours with electricity at least to run a heater. But basically Montreal and nearby communities are a disaster area. the entire South Shore off Montreal has lost its power grid (i.e. transmission towers twisted like pretzels because of ice); the same happened in parts of Eastern Ontario as far as Kingston, with disastrous effects on dairy farmers, etc. Here in Ottawa, the situation was bad, although not quite as disastrous as Montreal. Forty percent of the trees in Ottawa are damaged, and parts of Ottawa are still without power (for example, my house since Thursday!). But downtown is getting back in shape, and Carleton and University of Ottawa have managed to keep heat. I am still camping-out here in my office for the near future... Keep warm-- Phil Scott From cat-dist Mon Jan 12 14:39:52 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id OAA23063; Mon, 12 Jan 1998 14:38:51 -0400 (AST) Date: Mon, 12 Jan 1998 14:38:51 -0400 (AST) From: categories To: categories Subject: Re: iced categories Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Mon, 12 Jan 1998 16:05:33 +0000 (GMT) From: J.M. Egger > > Date: Sun, 11 Jan 1998 09:56:26 -0500 (EST) > From: Peter Freyd > > Since a good fraction of the world's category theorists are witnessing > an historic ice-storm, can they tell us how they're faring? > > Probably not... `triples.math.mcgill.ca' has been inoperative since before the ice-storm began, which means that many category-theorists in Montreal have not been receiving e-mail from this mailing list even before the [ note from moderator: actually, the list has been reaching the McGill people - until last week of course... ] blackouts, etc. began. I think power has been restored to most of the island of Montreal (the downtown area lost power at 3pm on Friday, and was still without it when I left on Saturday evening), but the electrical infrastructure of the South Shore has been destroyed to the point that it must be replaced from scratch. Now that temperatures have dropped to the more usual range for this time of year, mass evacuation of the hardest-hit areas by the army is a distinct possibility. From cat-dist Mon Jan 12 14:40:39 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id OAA12734; Mon, 12 Jan 1998 14:40:36 -0400 (AST) Date: Mon, 12 Jan 1998 14:40:36 -0400 (AST) From: categories To: categories Subject: Re: Functor algebras Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Mon, 12 Jan 1998 16:16:14 +0000 From: J Robin B Cockett > > Date: Tue, 06 Jan 1998 17:26:17 -0600 > From: Uday S Reddy > > Happy New Year, everyone. > > I have been wondering about a little question. Category theory texts > talk about "algebras" for an endofunctor, which are arrows of type FA -> > A, and dually coalgebras A -> GA. I am interested in the symmetric > case, arrows of type FA -> GA for endofunctors F and G. > Have such structures been studied? > > This is only scratching the surface. One can ask for a family of such > arrows for an algebra. One can consider functors F,G: C -> D between > different categories leading to algebras of the form GA> where > A is an object of C, and f an arrow in D, and so on. I am also > interested in the "diagonal" case, arrows of type FAA -> GAA where F and > G are functors C^op x C -> C. (Note that all these structures have a > "natural" notion of homomorphisms.) > > I would appreciate any pointers to the literature. > > Uday Reddy The category with objects GA> and evident maps is sometimes called an inserter. It is a weighted limit - a sort of "lax equalizer" of the two functors F and G: it may be written as F//G to distinguish it from the comma category (which is written F/G). It is used in the construction of datatypes (Hagino's thesis - as mentioned earlier - see also Dwight Spencer and my paper "Strong categorical datatypes II" TCS 139 (1995) 69-113 and its predecessor). Furthermore, one can express the parametricity properties of combinators and modules using these categories (see Peter Vesely's MSc thesis on the Charity site (http:/www.cpsc.ucalgary.ca/projects/charity/home.html) and Maarten Fokkinga's thesis - and paper in a recent MSCS issue - where I believe he uses the term "transformer" rather than combinator). I recently gave a working presentation to IFIP 2.1 entitled a "A reminder on inserters" ... this because I felt the connection to datatypes and the software structuring and parametricity ramifications of this seemingly innocuous limit had still not been sufficiently recognized or exploited. Robin Cockett From cat-dist Wed Jan 14 14:38:38 1998 Received: from localhost (cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) with SMTP id OAA08944; Wed, 14 Jan 1998 14:35:15 -0400 (AST) Date: Wed, 14 Jan 1998 14:35:14 -0400 (AST) From: categories To: categories Subject: Research Position at Sussex Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-Status: Date: Wed, 14 Jan 1998 09:53:54 +0000 (GMT) From: Matthew Hennessy UNIVERSITY OF SUSSEX RESEARCH FELLOW IN THE FOUNDATIONS OF COMPUTING One Research Fellow is required to join the EPSRC funded project entitled ``Foundations for the Integration of Concurrent Distributed and Functional Computation'', under the direction of Matthew Hennessy. The aim of the project is to - provide a uniform coherent semantic foundation for concurrent, distributed and functional behaviour; - develop proof methodologies for establishing properties of process descriptions expressed in specification languages using these paradigms; - develop prototypes of supporting verification systems. The project has already been running for approximately 18 months and work has concentrated on two streams of research: - development of languages, type systems and behavioural theories for mobile computing, where independent processes roam widely distributed networks in search of resources and information. - denotational models for languages combining higher-order functional notation with the pi-calculus (examples include Cml and core Facile) The successful candidate will be expected to carry out research related to one of these topics. The appointment will be for a period of two years, starting on 1/04/98, and salary will be related to the academic 1A scale. A Ph.D. in Computer Science or Mathematics or equivalent experience is required. In addition to normal research duties the successful candidate will be expected to provide some assistance to undergraduate teaching. More details of the project and the conditions of service are available at ftp://ftp.cogs.sussex.ac.uk/pub/users/matthewh/details.ps.gz To apply please submit applications to Prof M Hennessy School of COGS University of Sussex Falmer Brighton BN1 9QH UK Tel: +44 01273 678101 email: matthewh@cogs.sussex.ac.uk Applications should include - a detailed curriculum vitae, - names of three referees with their email addresses, - a statement outlining the candidates proposed contribution to the goals of the project, - copies (or URL references) of any relevant publications. From cat-dist Wed Jan 14 15:10:16 1998 Received: from localhost (cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) with SMTP id PAA26136; Wed, 14 Jan 1998 15:10:01 -0400 (AST) Date: Wed, 14 Jan 1998 15:10:01 -0400 (AST) From: categories To: categories Subject: Combining monads Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-Status: Date: Wed, 14 Jan 1998 16:21:51 +0000 (GMT) From: Tom Leinster Is the pullback of a monadic functor along a monadic functor necessarily monadic? Is the diagonal of the pullback square monadic? Does this work if your restrict yourself to, say, finitary monadic functors? (E.g. it works for finitary monads on Set: the theory of sets with both ring and lattice structure (not interacting in any particular way) comes from a monad.) Thanks, Tom Leinster From cat-dist Wed Jan 14 19:35:18 1998 Received: from localhost (cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) with SMTP id TAA32757; Wed, 14 Jan 1998 19:35:00 -0400 (AST) Date: Wed, 14 Jan 1998 19:34:59 -0400 (AST) From: categories To: categories Subject: Non-well-powered Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Wed, 14 Jan 1998 16:39:27 -0500 (EST) From: Michael Barr As most of you know, we at McGill are offline since about a week. McGill's main computer seems to be online and I was able to telnet to an old account I had at Penn. Anyway, I think we are all well. I was without power for a week (less 4 four hours). We spent part of that time in my office (sleeping bag and couch) and then the power was shut off at McGill (where it still is) and we went to the Foxes until we got our power back on Tuesday morning. We are now back home and everything is back to normal. I know there have been some inquiries, whence this note. Michael From cat-dist Wed Jan 14 19:38:13 1998 Received: from localhost (cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) with SMTP id TAA01585; Wed, 14 Jan 1998 19:38:11 -0400 (AST) Date: Wed, 14 Jan 1998 19:38:11 -0400 (AST) From: categories To: categories Subject: Re: Combining monads Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Thu, 15 Jan 1998 09:58:50 +1100 From: Ross Street >Date: Wed, 14 Jan 1998 16:21:51 +0000 (GMT) >From: Tom Leinster > > >Is the pullback of a monadic functor along a monadic functor >necessarily monadic? No. And I seem to remember this was one of the main points of the thesis (under Lawvere) of Michel Thie'baud. The thesis title was "Self-dual structure-semantics & algebraic categories" (Dalhousie University, Halifax, Nova Scotia, August 1971). Comonads (= cotriples) in Mod (= Bimod = Prof = Dist) are the subject. Using these to define "algebraic", Michel obtained stability under pullback. --Ross From cat-dist Wed Jan 14 19:43:34 1998 Received: from localhost (cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) with SMTP id TAA28779; Wed, 14 Jan 1998 19:43:25 -0400 (AST) Date: Wed, 14 Jan 1998 19:43:25 -0400 (AST) From: categories To: categories Subject: oops Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Thu, 15 Jan 1998 10:32:43 +1100 From: Ross Street I just realised my hasty response to Tom Leinster was to the question of pullback of a monadic alond an *arbitrary* functor; not Tom's question! --Ross From cat-dist Thu Jan 15 17:11:25 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id RAA01978; Thu, 15 Jan 1998 17:10:14 -0400 (AST) Date: Thu, 15 Jan 1998 17:10:14 -0400 (AST) From: categories To: categories Subject: Re: Combining monads Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Thu, 15 Jan 1998 15:44:30 +1100 (EST) From: Steve Lack > Date: Wed, 14 Jan 1998 15:10:43 -0400 (AST) > From: categories > > Date: Wed, 14 Jan 1998 16:21:51 +0000 (GMT) > From: Tom Leinster > > > Is the pullback of a monadic functor along a monadic functor > necessarily monadic? > Is the diagonal of the pullback square monadic? > Does this work if your restrict yourself to, say, finitary monadic > functors? > > (E.g. it works for finitary monads on Set: the theory of sets with > both ring and lattice structure (not interacting in any particular > way) comes from a monad.) > > Thanks, > Tom Leinster > > Let K be a complete and cocomplete category, and Mnd(K) the category of monads on K and strict morphisms of monads. If T and S are monads on K which preserve (alpha-)filtered colimits (for a regular cardinal alpha), then (i)the coproduct T+S exists in Mnd(K) (ii)this coproduct is ``algebraic'', meaning that the diagonal of the pullback square K^S | | v K^T-->K is the forgetful functor K^(T+S)-->K (iii)the projections K^(T+S)-->K^T and K^(T+S)-->K^S are monadic. Much can be done without completeness, but the proofs become a bit harder. See the paper G.M.Kelly, A unified treatment of transfinite constructions for free algebras, free monoids, colimits, associated sheaves, and so on, Bull. Austral. Math. Soc. 22(1980):1--83 for a survey of many such results. In fact if K is locally finitely presentable then the category Mnd_f(K) of finitary monads on K and strict morphisms of monads is itself locally finitely presentable; for this see my paper ``On the monadicity of finitary monads'', to appear in JPAA, but in the meantime available at http://www.maths.usyd.edu.au:8000/res/Catecomb/Lack/1997-29.html. Regards, Steve. From cat-dist Thu Jan 15 17:11:30 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id RAA00846; Thu, 15 Jan 1998 17:11:21 -0400 (AST) Date: Thu, 15 Jan 1998 17:11:21 -0400 (AST) From: categories To: categories Subject: Conference Announcement Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from QUOTED-PRINTABLE to 8bit by mailserv.mta.ca id RAA00846 Status: O X-Status: Date: Thu, 15 Jan 1998 09:59:05 +0100 From: Alberto Peruzzi We are pleased to announce a conference on Wholes and their Parts (W/P) to be held in Bolzano, Maretsch Castle, 17-19 June 1998 1. PRESENTATION Science is connected to the complementarity of analysis and synthesis. It may be said that classical physics is characterized by an in-built analysis of the world into constituent parts (such as atoms or elementary particles). These are then recomposed together to provide, by means of synthesis, any system; interactions are linearly and locally described; the resulting hierarchy of structures is grounded on such constituent parts. In contemporary science, the age of "pure" analysis seems to have ended. There are deep mathematical reasons for this. Non-linear systems have properties that, in general, cannot be expressed in terms of decomposition into ultimate, unstructured, pointlike parts plus a suitable sets of relations among them. Moreover, the "dialectic" of quantity and quality is subtler than was previously thought and this dialectic is needed in the explanation of all sorts of phenomena. It arises not only in physics, but also in the study of cognitive systems and natural and programming languages. Within psychology, it is said that "Gestalten" are cohesive wholes and that "the whole is more than the sum of its parts". But what does this mean exactly? Similar questions emerge in other contexts as well. What is relevant for the foundations of science, the need for a clear understanding of the part/whole relationships, emerges even in logic and mathematics, since these provide the tools for organizing our rational image of the world, in its multi-stratified complexity. Thus, we are faced with the problem of relating in a possibly coherent way the various forms of part/whole relationships arising in different branches of science. We have not only to classify the different kinds of wholes and their inherent "grammars", but also to take into account the process of formation for wholes, in order to describe precisely in which sense the whole emerges out of its parts and is irreducible to an aggregate of autonomous, more or less pointlike, entities. What makes (in part, at least) the difference between mere aggregates and cohesive wholes? The members of the whole do not simply hang together: they hang together in the whole, and the structure of the whole influences the description of the parts and their local interactions. In view of the growing interest in this sort of pattern, of so deep relevance for theoretical and applied sciences, it is therefore suitable to clarify the whole/part issues in crucial fields of research, to compare different approaches and to develop a foundational discussion. 2. PROGRAM June 17 9 Registration 10 Bill Lawvere, Opening Lecture 11,30 Coffee break 12 John Bell, W/P in algebraic and logical structures 13-15 Lunch 15 Ieke Moerdjik, W/P in geometry, topology and topos theory 16 Coffee break 16,30 Colin McLarty, W/P in foundations of mathematics 17,30 Carlo Cellucci, W/P in logical analysis June 18 9 Steve Vickers, W/P in semantics for programming languages 10 Gonzalo Reyes, W/P in categorical analysis of language 11 Coffee break 11,30 John Mayberry, W/P in set theory 12,30-15 Lunch 15 Niles Eldredge, W/P in biology 16 Coffee break 16,30 Alberto Peruzzi, W/P in epistemology and semantics 17,30 Roberto Poli, W/P in ontology June 19 9 Ettore Casari, W/P in phenomenology 10 Alf Zimmer, W/P in Gestalt psychology 11 Coffee break 11,30 Ron Langacker, W/P in linguistics 12,30-15 Lunch 15 George Lakoff, W/P in cognitive sciences (to be confirmed) 16 Coffee break 16,30 Chris Isham, W/P in quantum topology 17,30 Basil Hiley, W/P in mechanics and cosmology 3. UPDATES To keep you updated with more information on the conference this is the URL for the W/P home page: http://www.gelso.unitn.it/~poli/ 4. REGISTRATION FEES Registration fees only cover the participation in this conference. Miscellaneous expenses (accomodation, meals and social activities) are in addition. The registration deadline to get the early registration fare is : March 1998, 31st. Students must enclose with the registration form a photocopy of their student card. –––––––––––+––––––––––––––––––––––––––––+––––––––––––––––– Status Early registration (before 3/31/98) Late registration –––––––––––+––––––––––––––––––––––––––––+––––––––––––––––– Student 50,000 100,000 Scholar 100,000 200.000 Industrial 200,000 300.000 –––––––––––+––––––––––––––––––––––––––––+––––––––––––––––– 5. ACCOMODATION Participants should book their own accomodation. A selected hotel list is the following one: PARKHOTEL LAURIN**** 4, Laurinstrasse single-room and breakfast: 180,000-265,000 tel. +39 471 31 10 00, fax +39 471 31 11 48 CITTA’*** 21, Waltherplatz single-room and breakfast: 110,000 tel. +39 471 97 52 21; fax: +39 471 97 66 88 FEICHTER** 15, via Weintraubengasse single-room and breakfast: 60,000-80,000 tel. +39 471 978 768; fax: +39 471 974 803 REGINA ANGELORUM** 1, Rittnerstrasse single-room and breakfast: 65,000-85,000 tel.: +39 471 972195; fax: +39 471 97 89 44 KOLPINGHAUS** (Student house) 3, Spitalgasse single-room and breakfast: 50,000-65,000 tel.: +39 471 97 11 70; fax.: +39 471 97 39 17 (all the above hotels are at a walkable distance from both the railway station and Maretsch Castle.) FOR MORE INFORMATION: City tourist office 8, Waltherplatz tel.: +39 471 307 000 / 001 / 002 fax.: +39 471 98 01 26 or +39 471 98 03 00 Time table: 8.30-18.00; Saturday 9-12.30 closed on sunday and holidays. 6. METHODS OF PAYMENT Cheques : Made out in Italian Liras, payable to Istituto Mitteleuropeo di Cultura, vicolo Gumer 7, 39100 Bolzano, ITALY. Bank transfers : Sorry but you will have to pay the banking charges (if you don't, your registration will be considered as incomplete). Please enclose with this form a copy of your transfer. This copy should mention the name and adress of your bank. Do not forget to write down your name on the transfer. The bank transfer must be done in Italian Liras on the account: Bank : Cassa di Risparmio di Bolzano Account number : 873900 Swift Codes: ABI: 06045; CAB: 11601 References : W/P conference / your name Address : Istituto Mitteleuropeo di Cultura vicolo Gumer 7 39100 Bolzano, Italy If these methods of payment are inconvenient, it will be possible for you to pay cash once you are in Bolzano. In this case, you will have to pay the late registration fee. Some exceptions to these arrangements can be made for people coming from countries which do not allow any of the long distance methods of payment above. 7. CANCELLATION Cancellations received before April 1998, 15th: running costs = 20,000 It Liras Cancellations received after May 1998, 15th: running costs = 50% of the registration fees 8. REGISTRATION FORM Name: ____________________________________________ First Name: ________________________________________ Institution: _________________________________________ Address: ___________________________________________ ___________________________________________________ ___________________________________________________ Country: ___________________________________________ Phone : ___________________________ Fax : _____________________________ E-mail : __________________________ Date : _____________________ Signature : ___________________________ To return by e-mail to : poli@risc1.gelso.unitn.it A copy of this registration form together with the justificatory of payment and the copy of the student card has to be sent by surface mail to : Istituto Mitteleuropeo di Cultura vicolo Gumer 7 39100 Bolzano ITALY 9. CONFERENCE COMMITTEE Alberto Peruzzi: peruzzi@dada.it Roberto Poli: poli@risc1.gelso.unitn.it ************************************* Roberto Poli Department of Sociology and Social Research 26, Verdi street 38100 Trento -- Italy Tel. ++39-461-881-403 Fax: ++39-461-881-348 e-mail: poli@risc1.gelso.unitn.it Axiomathes: http://www.soc.unitn.it/dsrs/axiomathes.htm IMC: http://www.soc.unitn.it/dsrs/IMC.htm Alberto Peruzzi Dipartimento di Filosofia Università di Firenze via Bolognese 52 50139 Firenze Italia peruzzi@dada.it From cat-dist Thu Jan 15 17:11:44 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id RAA04412; Thu, 15 Jan 1998 17:11:42 -0400 (AST) Date: Thu, 15 Jan 1998 17:11:42 -0400 (AST) From: categories To: categories Subject: Report available Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: 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. From cat-dist Fri Jan 16 14:20:51 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id OAA25809; Fri, 16 Jan 1998 14:20:24 -0400 (AST) Date: Fri, 16 Jan 1998 14:20:24 -0400 (AST) From: categories To: categories Subject: Re: Combining monads Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Thu, 15 Jan 1998 23:21:27 +0100 From: Jan Juerjens > > Date: Wed, 14 Jan 1998 16:21:51 +0000 (GMT) > From: Tom Leinster > > > Is the pullback of a monadic functor along a monadic functor > necessarily monadic? > Is the diagonal of the pullback square monadic? > Does this work if your restrict yourself to, say, finitary monadic > functors? > > (E.g. it works for finitary monads on Set: the theory of sets with > both ring and lattice structure (not interacting in any particular > way) comes from a monad.) > > Thanks, > Tom Leinster > Hi Tom, if I'm not mistaken, this reduces for full isomorphism-closed embeddings to the (finite) Intersection Problem (of full iso-closed subcategories) answered negatively by Trnkova, Adamek, Rosicky ("Topological reflections revisited", ProcAMS 108,3 (1990) p605; see also Tholen "Reflective Subcategories" TopAppl 27 (1987) p201, Adamek, Rosicky "Intersections of reflective subcategories" ProcAMS 103 (1988) p710). Full iso-closed subcategories of locally lambda-presentable categories are reflective and closed under lambda-directed colimits iff they are lambda-orthogonal, so intersections of such subcategories are reflective (Adamek, Rosicky "Locally presentable and Accessible Categories" CUP 94). Bye, Jan [ + thanks again for the supervisions ... :-) ] From cat-dist Mon Jan 19 09:46:48 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id JAA10702; Mon, 19 Jan 1998 09:45:42 -0400 (AST) Date: Mon, 19 Jan 1998 09:45:42 -0400 (AST) From: categories To: categories Subject: announcement Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: 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. From cat-dist Mon Jan 19 09:46:49 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id JAA15892; Mon, 19 Jan 1998 09:46:12 -0400 (AST) Date: Mon, 19 Jan 1998 09:46:12 -0400 (AST) From: categories To: categories Subject: Master Class in Mathematical Logic Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Mon, 19 Jan 1998 13:26:49 +0100 (MET) From: Jaap van Oosten Dear Colleagues, Please bring the following to the attention of possibly interested students: In the academic year 1998-1999 the Universities of Utrecht and Nijmegen organize, as part of the MRI Master Class, a year-long education program in Mathematical Logic. The program is aimed at students who intend to enter a Ph.D.-program in the subsequent year. The courses are in English and foreign students are specifically invited to apply. A limited number of stipends are available. The contents of the program are detailed in a brochure which exists both as hard copy and electronically. The text can be seen on the homepage of the Mathematical Research Institute. URL: http://www.math.ruu.nl/mri If you're interested in receiving a hard copy of the brochure, please send a message to Marian Brands, at brands@math.ruu.nl Thank you, Henk Barendregt Ieke Moerdijk Jaap van Oosten From cat-dist Tue Jan 20 14:59:42 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id OAA02502; Tue, 20 Jan 1998 14:58:27 -0400 (AST) Date: Tue, 20 Jan 1998 14:58:27 -0400 (AST) From: categories To: categories Subject: ICM'98 Second Announcement Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Tue, 20 Jan 1998 12:04:37 +0100 From: Christoph Helmberg Dear Colleague: The Organizing Committee is pleased to announce the availability of The Second Announcement of THE INTERNATIONAL CONGRESS OF MATHEMATICIANS BERLIN, August 18-27, 1998 It can be retrieved from the homepage of the Congress with URL: http://elib.zib.de/ICM98 ICM'98 is one of the quadrennial congresses held under the auspices of the International Mathematical Union (IMU). Mathematicians from all countries gather to discuss recent developments in mathematics that are presented by leading scientists from all mathematical fields. Responsibility for the scientific program lies with the Program Committee appointed by IMU. There will be 21 one-hour Plenary Lectures covering the major areas of mathematics and about 160 forty-five-minute Invited Lectures in nineteen sections. The Fields Medals and the Nevanlinna Prize will be awarded during the Opening Ceremony on the first day of the Congress. This will take place in the International Congress Center Berlin (ICC). All other scientific events will be held at Technische Universitaet Berlin. No scientific activities are scheduled for Sunday, August 23. The Second Announcement of ICM'98 describes the scientific program and the social events of the Congress and gives instructions on how to complete the registration process and obtain accommodation. It contains a call for contributed short presentations, and provides guidelines regarding the submission of abstracts. The Second Announcement also includes advice on how to proceed upon arrival at airports and railway stations, and it will be accompanied by a brochure describing the day trips and tours organized by a professional tour and congress organizer. Postscript and LaTeX versions of the Second Announcement can be obtained from the WWW with URL: http://elib.zib.de/ICM98/Second_Announcement or by anonymous ftp from elib.zib.de in the subdirectory pub/IMU/HTML/ICM98/Second_Announcement. The files of interest are scndannc.ps Announcement Postscript DIN A4 us_scnda.ps Postscript US-paper scndannc.tex LaTeX (no maps) reg-form.ps Registration Form Postscript DIN A4 us_regf.ps Postscript US-paper wordregf.doc MS-Word 6.0 We look forward to welcoming you at ICM'98 in Berlin. Christoph Helmberg (for the ICM'98 Organizing Committee) From cat-dist Tue Jan 20 14:59:42 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id OAA02646; Tue, 20 Jan 1998 14:59:15 -0400 (AST) Date: Tue, 20 Jan 1998 14:59:15 -0400 (AST) From: categories To: categories Subject: Lectureships in Computer Science Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Tue, 20 Jan 1998 12:09:26 GMT From: rlc3@mcs.le.ac.uk Dear Colleagues, I would be grateful if you could publicize the following lectureship advertisement. Thank you, Roy Crole. --------------------------------------------------------------------- Leicester University UK DEPARTMENT OF MATHEMATICS & COMPUTER SCIENCE 2 LECTURESHIPS IN COMPUTER SCIENCE Applications are invited for 2 Lectureships in Computer Science in the Department of Mathematics and Computer Science at the University of Leicester. One lectureship will be in the general area of Software Engineering and Formal Methods, and there are no restrictions on the other lectureship. The posts are tenable from 1st September 1998 or as soon as possible thereafter. This is a superb opportunity for persons of energy, drive and ambition to assume rewarding roles and to establish themselves in a young, dynamic and rapidly developing department. Initial salary, dependent upon qualifications and experience, will be on the Lecturer Grade A or B scale 16,045 to 27,985 GBP p.a. Candidates who are interested in either of the lectureships are invited, if they so wish, to contact Professor Iain Stewart (telephone 0116 252 5237, e-mail i.a.stewart@mcs.le.ac.uk) or Professor Rick Thomas (telephone 0116 252 3411, email rmt@mcs.le.ac.uk), who will be pleased to discuss the lectureships further. Information about the Department is also available on the WWW [http://www.mcs.le.ac.uk]. Further particulars (which are also available on the World Wide Web) and application forms are available from the Personnel and Planning Office (Academic Appointments), University of Leicester, University Road, Leicester LE1 7RH, telephone +44 (0)116 252 2758. The closing date for applications is 20th March 1998. Please quote reference A5167. From cat-dist Tue Jan 20 15:00:32 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id PAA02950; Tue, 20 Jan 1998 15:00:30 -0400 (AST) Date: Tue, 20 Jan 1998 15:00:30 -0400 (AST) From: categories To: categories Subject: PhD Studentships Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Tue, 20 Jan 1998 12:09:28 GMT From: rlc3@mcs.le.ac.uk Dear Colleagues, I would be grateful if you could publicize the following studentship advertisement. Thank you, Roy Crole. --------------------------------------------------------------------- Leicester University UK DEPARTMENT OF MATHEMATICS & COMPUTER SCIENCE 3 PH.D. STUDENTSHIPS IN MATHEMATICS OR COMPUTER SCIENCE Applications are invited for three fully funded research studentships leading to the degree of PhD in any aspect of Mathematics or Computer Science. The studentships are available for studies beginning in October 1998. Applicants should have, or expect to have, a first or upper second class degree in the relevant subject area. The Department of Mathematics and Computer Science is divided into three groups: Computer Science, Pure Mathematics and Applicable Mathematics. The Pure Mathematics Group carries out research in several major branches of algebra. The key areas of expertise are in: the theory of groups and their representations; algebraic topology and its applications; the theory of rings and their modules; and the representation theory and cohomology of finite dimensional algebras. The Applicable Mathematics Group focuses mainly on numerical analysis, and in particular on: approximation theory; the numerical solution of ordinary and partial differential equations; and integral equations. There is also research undertaken on statistics. Research in the Computer Science Group has three main themes: logic, algebra and complexity; the theory of distributed systems; and semantics. There is an active Graduate Programme. The studentships will be awarded to the best three applicants regardless of subject area. Candidates should identify their preferred area of research and supervisor. Details of the possible areas of research and supervisors are available via the Departmental web pages [http://www.mcs.le.ac.uk] or the Department's Postgraduate Brochure. The Postgraduate Brochure, application forms and further details are available from Dr. S.J. Ambler, Department of Mathematics and Computer Science, Leicester University, University Road, Leicester LE1 7RH (telephone: 0116 252 3406, email: s.ambler@mcs.le.ac.uk). The closing date for applications is 1st May 1998. From cat-dist Tue Jan 20 15:02:19 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id PAA03437; Tue, 20 Jan 1998 15:02:18 -0400 (AST) Date: Tue, 20 Jan 1998 15:02:18 -0400 (AST) From: categories To: categories Subject: Re: pullback categories Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-Status: Date: Tue, 20 Jan 1998 14:20:35 -0500 (EST) From: Michael Barr Triples is back, at least for the time being, after having been down, either from its problems or the lack of power at McGill for most of the last month. I have just seen the question about pullback of tripleable functors and I have not seen a really satisfactory reply. A lot--maybe all--of what I say below is probably in Ernie Manes' thesis (A Triple Miscellany, Wesleyan U., 1967). The answer is definitely no, but the problem is the lack of adjoint. Consider, for the example, the complete semilattice triple on Set. It is also the covariant powerset triple, with singleton for eta and union (or intersection) for mu (one will give you sup semilattices, the other the inf semilattices). That is one triple and the other is N x -, whose algebras are sets with a single unary operation. The pullback is the category whose objects are complete semilattices with a single unary function that is not assumed to cohere in any way with the semilattice structure. A complete boolean algebra is model of such a theory, taking complement as the unary operation. If there were free algebras of this type, then a quotient of them would be a free complete boolean algebra, but we know these don't exist. Of course, one can raise the question under the assumption that the adjoint exists. For example, if the category is locally presentable (complete and accessible) and the functors are accessible. Then if the functors are T_1 and T_2, simply apply them alternately, taking colimits at limit ordinals, until they stabilize and that will give you free algebras. Of course, it is obvious that the pullback is the category whose objects consist of T_1A ---> A <--- T_2A which are algebras for each triple, but no assumption of coherence between the two structures is made. It seems pretty obvious, although I have no really checked the details carefully, that this will satisfy Beck's condition. Or rather the forgetful functor to each of the individual category of algebras as well as the composite. For example, if we had the situation T_1A -----------> A <------------- T_2A || || || || || || || || || || || || || || || || || || vv vv vv T_1B -----------> B <------------- T_2B of such a nature that A ======> B -----> C is a split coequalizer, then the outer columns of T_1A -----------> A <------------- T_2A || || || || || || || || || || || || || || || || || || vv vv vv T_1B -----------> B <------------- T_2B | | | | | | | | | | | | | | | | | | v v v T_1C - - - - - -> C <- - - - - - - T_2C are split coequalizers too, whence the dotted arrows exist. That the whole diagram is a coequalizer in the pullback category is also easy. Thus the answer is yes, provided the adjoint exists, but that is not guaranteed even over Set. Michael From cat-dist Tue Jan 20 17:32:52 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id RAA29284; Tue, 20 Jan 1998 17:32:44 -0400 (AST) Date: Tue, 20 Jan 1998 17:32:43 -0400 (AST) From: categories To: categories Subject: 5th WoLLIC'98 - 2nd Call Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Tue, 20 Jan 1998 17:12:29 -0300 (EST) From: Ruy de Queiroz Second Call for Contributions 5th Workshop on Logic, Language, Information and Computation (WoLLIC'98) July 28-31, 1998 ! TUTORIALS >> (Tutorial Day: July 28th) << TUTORIALS ! IME-USP, Sao Paulo, Brazil The "5th Workshop on Logic, Language, Information and Computation" (WoLLIC'98), the fifth version of a series of workshops which started in 1994 with the aim of fostering interdisciplinary research in pure and applied logic, will be held in Sao Paulo, Brazil, from July 28th to 31st 1998. Contributions are invited in the form of short papers (6 10pt pages or 1800 words) in all areas related to logic, language, information and computation, including: pure logical systems, proof theory, model theory, algebraic logic, type theory, category theory, constructive mathematics, lambda and combinatorial calculi, program logic and program semantics, logics and models of concurrency, logic and complexity theory, nonclassical logics, nonmonotonic logic, logic and language, discourse representation, logic and artificial intelligence, automated deduction, foundations of logic programming, logic and computation, and logic engineering. The 5th WoLLIC'98 has the scientific sponsorship of the Interest Group in Pure and Applied Logics (IGPL), the European Association for Logic, Language and Information (FoLLI), the Association for Symbolic Logic (ASL), the Sociedade Brasileira de Computacao (SBC), and the Sociedade Brasileira de Logica (SBL). There will be a number of guest speakers, including: Sergei Artemov (Moscow State Univ, Russia) (CONFIRMED), Sam Buss (Univ Calif San Diego, US) (CONFIRMED), Edmund Clarke (Carnegie-Mellon Univ, US) (CONFIRMED), Heinz Dieter Ebbinghaus (Universitaet Freiburg, Germany) (CONFIRMED), Michael Fourman (Edinburgh Univ, UK) (CONFIRMED), Ehud Hrushovski (Hebrew Univ Jerusalem, Israel) (*), Hans Kamp (Stuttgart Univ, Germany) (CONFIRMED), Phokion Kolaitis (Univ Calif Santa Cruz, US) (*), Valeria de Paiva (Birmingham Univ, UK) (CONFIRMED), Maarten de Rijke (Warwick Univ, UK) (CONFIRMED), Giovanni Sambin (Padoa Univ, Italy) (CONFIRMED). (*) TO BE CONFIRMED Submission: Papers (sent preferably in LaTeX format by e-mail to ** wollic@ime.usp.br **, or in 5(five) copies to postal address) must be RECEIVED by APRIL 3rd, 1998 by one of the Co-Chairs of the Organising Committee. Papers must be written in English and give enough detail to allow the programme committee to assess the merits of the work. Papers should start with a brief statement of the issues, a summary of the main results, and a statement of their significance and relevance to the workshop. References and comparisons with related work is also expected. Technical development directed to the specialist should follow. Results must be unpublished and not submitted for publication elsewhere, including the proceedings of other symposia or workshops. One author of each accepted paper will be expected to attend the conference in order to present it. Authors will be notified of acceptance by MAY 15th, 1998. The abstracts of the papers will be published in a "Conference Report" section of the Logic Journal of the IGPL (ISSN 1367-0751) (Oxford Univ Press) as part of the meeting report. Papers presented at the meeting will be invited for submission (in full version) to the Logic Journal of the IGPL (http://www.oup.co.uk/jnls/igpl/). The WoLLIC'98 is hosted by Universidade de Sao Paulo (USP), and will take place at the Mathematics and Statistics Institute (IME). Programme Committee: Andreas Blass (Michigan Univ, USA), Itala D'Ottaviano (Univ Campinas, BR), J. Michael Dunn (Indiana Univ, USA), Wilfrid Hodges (Queen Mary Coll, UK), Francisco Miraglia (Univ Sao Paulo, BR), Luiz Carlos Pereira (Cathol Univ Rio, BR), Andrew Pitts (Cambridge Univ, UK), Amir Pnueli (Weizmann Inst, Israel). Organising Committee: L. S. C. Baptista (UFPE/UFPB), M. Finger (USP), E. Hermann Haeusler (PUC-Rio), A. C. V. de Melo (USP), A. G. de Oliveira (UFBA/UFPE), R. de Queiroz (UFPE), F. C. da Silva (USP). For further information, contact the Co-Chairs of the Organising Committee: Ruy de Queiroz, Departamento de Informatica, Univ. Federal de Pernambuco, CP 7851, 50732-970 Recife, PE, Brazil, e-mail: ruy@di.ufpe.br, tel.: (+55 81) 271 8430, fax: (+55 81) 271 8438. Marcelo Finger, Departamento de Ciencia da Computacao, Instituto de Matematica e Estatistica, Universidade de Sao Paulo, Rua do Matao 1010, 05508-900 Sao Paulo, SP, Brazil, e-mail: mfinger@ime.usp.br, tel.: (+55 11) 818 6287, fax: (+55 11) 818 6134. Web page: http://www.ime.usp.br/~wollic From cat-dist Tue Jan 20 17:33:35 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id RAA29430; Tue, 20 Jan 1998 17:33:34 -0400 (AST) Date: Tue, 20 Jan 1998 17:33:34 -0400 (AST) From: categories To: categories Subject: Re: Combining monads and Pullback cats Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Tue, 20 Jan 98 15:30:07 EST From: John Duskin Mike is right. The problem lies in the existence of a left adjoint. However if one pulls back over a Grothendieck co-(=op-)fibration, then if U has a left adjoint, then so does its pullback. In fact, a functor is a cofibration iff it is universal for this property, i.e., it has this property and this property is stable under arbitrary pullbacks."A cofibration is a universal change of base for right adjoints". I don't know if this is of much help, but it is amusing. From cat-dist Wed Jan 21 13:35:07 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id NAA10324; Wed, 21 Jan 1998 13:34:06 -0400 (AST) Date: Wed, 21 Jan 1998 13:34:05 -0400 (AST) From: categories To: categories Subject: Journals Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-Status: Date: Tue, 20 Jan 1998 16:46:32 -0500 (EST) From: Michael Barr I recently received (but just read because of the power outages) a letter inviting me, along with a great many of you, to become an editor of a new journal published by Kluwer on homological, homotopical and categorical algebra. I attach my reply. Michael ==================================================================== >From barr@scylla.math.mcgill.ca Tue Jan 20 16:40:24 1998 Status: O X-Status: Date: Tue, 20 Jan 1998 16:40:17 -0500 (EST) From: Michael Barr To: Hvedri Inassaridze Subject: Re: journal In-Reply-To: Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII I am not participating in any journal published by a commercial publisher, either as author, refereee or editor. I make an exception for JPAA, but only for historical reasons and even there I will neither be an author nor referee. This is a protest against the price gouging that the commercial publishers, and Kluwer is one of the worst, have engaged in in recent years. Moreover, my univerity will not subscribe to any new commercial journal. Michael Barr From cat-dist Wed Jan 21 13:35:10 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id NAA12645; Wed, 21 Jan 1998 13:34:52 -0400 (AST) Date: Wed, 21 Jan 1998 13:34:52 -0400 (AST) From: categories To: categories Subject: PSSL'66 Announcement and Registration Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Wed, 21 Jan 1998 11:56:24 +0000 (GMT) From: Neil Ghani **** Announcement and Registration **** The 66th Peripatetic Seminar on Sheaves and Logic March 28-29, 1998 University of Birmingham England The 66th meeting of the PSSL will be held at the University of Birmingham, England, over the weekend of 28-29 March 1998. Since its inception, the focus of the PSSL has broadened and now includes talks related to category theory, logic and theoretical computer science. The meetings are informal in nature and talks on work in progress is welcome. We have arranged bed and breakfast in the University House which will cost 23 pounds per night. In addition, a buffet lunch and tea/coffee will be provided on Saturday and Sunday at a cost of 8 pounds per day. Student participation is particularly encouraged at this meeting and hence we have been granted a small fund to help with the costs of attendence for students. Those interested in this offer should contact the organisers as soon as possible. A more detailed announcement will be made closer to the meeting. More details can be found at http://www.cs.bham.ac.uk/~nxg/pssl66.html ** Registration ** Please send the following registration information via email to nxg@cs.bham.ac.uk by Monday 23 March and include the phrase PSSL in the title. Please make cheques payable to the "University of Birmingham" in sterling. Name: Job title: Affiliation: Address: email: phone: fax: presentation? (yes/no) title: Accommodation: Nights required: cost @ 23.00 per night: Lunch, Tea, Coffee : Saturday @ 8.00: Sunday @ 8.00: Total Cost: From cat-dist Wed Jan 21 15:08:35 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id PAA30110; Wed, 21 Jan 1998 15:07:28 -0400 (AST) Date: Wed, 21 Jan 1998 15:07:27 -0400 (AST) From: categories To: categories Subject: TAC: Abstracts from Volume 3, 1997 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-Status: Date: Mon, 19 Jan 1998 17:31:10 -0400 (AST) From: Bob Rosebrugh Following are a table of contents and abstracts of articles in Volume 3 of Theory and Applications of Categories. They are accessible on the Web from www.tac.mta.ca/tac/ or by ftp from ftp.tac.mta.ca/pub/tac/html/volumes/1997 Submission of articles to any of the Editors (who are listed after the abstracts) is invited. Please consult the Information for Authors at the Web or ftp sites. For subscription write to tac@mta.ca including a postal address. Robert Rosebrugh, Managing Editor http://www.tac.mta.ca/tac Theory and Applications of Categories tac@mta.ca Department of Mathematics and Computer Science 67 York Street ********NEW STREET ADDRESS******** Sackville, NB E4L 1E6 ********NEW POSTAL CODE*********** Canada +1-506-364-2530 (fax)+1-506-364-2645 ---------------------------------------------------------------------- ISSN 1201-561X THEORY AND APPLICATIONS OF CATEGORIES Volume 3 - 1997 Higher dimensional Peiffer elements in simplicial commutative algebras, Z. Arvasi and T. Porter, 1 Doctrines whose structure forms a fully faithful adjoint string, F. Marmolejo, 23 Note on a theorem of Putnam's, Michael Barr, 45 Lax operad actions and coherence for monoidal n-categories, A_{\infty} rings and modules, Gerald Dunn, 50 Proof theory for full intuitionistic linear logic, bilinear logic, and MIX categories, J.R.B. Cockett and R.A.G. Seely, 85 The reflectiveness of covering morphisms in algebra and geometry, George Janelidze and Max Kelly, 132 Crossed squares and 2-crossed modules of commutative algebras, Zekeriya Arvasi, 160 Monads and interpolads in bicategories, J"urgen Koslowski, 182 On property-like structures, G. M. Kelly and Stephen Lack, 213 Closed model categories for [n,m]-types, J. Ignacio Extremiana Aldana, Luis J. Hernandez Paricio, and M. Teresa Rivas Rodriguez, 251 Multilinearity of Sketches, David B. Benson, 269 ---------------------------------------------------------------------- ABSTRACTS: Higher Dimensional Peiffer Elements in Simplicial Commutative Algebras Z. Arvasi and T. Porter Let E be a simplicial commutative algebra such that E_n is generated by degenerate elements. It is shown that in this case the n^th term of the Moore complex of E is generated by images of certain pairings from lower dimensions. This is then used to give a description of the boundaries in dimension n-1 for n = 2, 3, and 4. ------------------------------------------------------------------------ Doctrines whose structure forms a fully faithful adjoint string F. Marmolejo We pursue the definition of a KZ-doctrine in terms of a fully faithful adjoint string Dd -| m -| dD. We give the definition in any Gray-category. The concept of algebra is given as an adjunction with invertible counit. We show that these doctrines are instances of more general pseudomonads. The algebras for a pseudomonad are defined in more familiar terms and shown to be the same as the ones defined as adjunctions when we start with a KZ-doctrine. ------------------------------------------------------------------------ Note on a theorem of Putnam's Michael Barr In a 1981 book, H. Putnam claimed that in a pure relational language without equality, for any model of a relation that was neither empty nor full, there was another model that satisfies the same first order sentences. Ed Keenan observed that this was false for finite models since equality is a definable predicate in such cases. This note shows that Putnam's claim is true for infinite models, although it requires a more sophisticated proof than the one outlined by Putnam. ------------------------------------------------------------------------ Lax Operad Actions and Coherence for Monoidal n-Categories, A_{\infty} Rings and Modules Gerald Dunn We establish a general coherence theorem for lax operad actions on an n-category which implies that an n-category with such an action is lax equivalent to one with a strict action. This includes familiar coherence results (e.g. for symmetric monoidal categories) and many new ones. In particular, any braided monoidal n-category is lax equivalent to a strict braided monoidal n-category. We also obtain coherence theorems for A_{\infty} and E_{\infty} rings and for lax modules over such rings. Using these results we give an extension of Morita equivalence to A_{\infty} rings and some applications to infinite loop spaces and algebraic K-theory. ------------------------------------------------------------------------ Proof theory for full intuitionistic linear logic, bilinear logic, and MIX categories J.R.B. Cockett and R.A.G. Seely This note applies techniques we have developed to study coherence in monoidal categories with two tensors, corresponding to the tensor-par fragment of linear logic, to several new situations, including Hyland and de Paiva's Full Intuitionistic Linear Logic (FILL), and Lambek's Bilinear Logic (BILL). Note that the latter is a noncommutative logic; we also consider the noncommutative version of FILL. The essential difference between FILL and BILL lies in requiring that a certain tensorial strength be an isomorphism. In any FILL category, it is possible to isolate a full subcategory of objects (the ``nucleus'') for which this transformation is an isomorphism. In addition, we define and study the appropriate categorical structure underlying the MIX rule. For all these structures, we do not restrict consideration to the ``pure'' logic as we allow 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. ------------------------------------------------------------------------ The reflectiveness of covering morphisms in algebra and geometry G. Janelidze and G. M. Kelly Each full reflective subcategory X of a finitely-complete category C gives rise to a factorization system (E, M) on C, where E consists of the morphisms of C inverted by the reflexion I : C --> X. Under a simplifying assumption which is satisfied in many practical examples, a morphism f : A --> B lies in M precisely when it is the pullback along the unit \etaB : B --> IB of its reflexion If : IA --> IB; whereupon f is said to be a trivial covering of B. Finally, the morphism f : A --> B is said to be a covering of B if, for some effective descent morphism p : E --> B, the pullback p^*f of f along p is a trivial covering of E. This is the absolute notion of covering; there is also a more general relative one, where some class \Theta of morphisms of C is given, and the class Cov(B) of coverings of B is a subclass -- or rather a subcategory -- of the category C \downarrow B \subset C/B whose objects are those f : A --> B with f in \Theta. Many questions in mathematics can be reduced to asking whether Cov(B) is reflective in C \downarrow B; and we give a number of disparate conditions, each sufficient for this to be so. In this way we recapture old results and establish new ones on the reflexion of local homeomorphisms into coverings, on the Galois theory of commutative rings, and on generalized central extensions of universal algebras. ------------------------------------------------------------------------ Crossed squares and 2-crossed modules of commutative algebras Zekeriya Arvasi In this paper, we construct a neat description of the passage from crossed squares of commutative algebras to 2-crossed modules analogous to that given by Conduche in the group case. We also give an analogue, for commutative algebra, of T. Porter's simplicial groups to n-cubes of groups which implies an inverse functor to Conduche's one. ------------------------------------------------------------------------ Monads and interpolads in bicategories Jurgen Koslowski Given a bicategory, 2, with stable local coequalizers, we construct a bicategory of monads Y-mnd by using lax functors from the generic 0-cell, 1-cell and 2-cell, respectively, into Y. Any lax functor into Y factors through Y-mnd and the 1-cells turn out to be the familiar bimodules. The locally ordered bicategory rel and its bicategory of monads both fail to be Cauchy-complete, but have a well-known Cauchy-completion in common. This prompts us to formulate a concept of Cauchy-completeness for bicategories that are not locally ordered and suggests a weakening of the notion of monad. For this purpose, we develop a calculus of general modules between unstructured endo-1-cells. These 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 endo-1-cells. We show that associative coequalizing multiplications suffice and call the resulting structures interpolads. Together with structure-preserving i-modules these form a bicategory Y-int that is indeed Cauchy-complete, in our sense, and contains the bicategory of monads as a not necessarily full sub-bicategory. Interpolads over rel are 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 ``taxonomy''. If Y locally has equalizers, then modules in general, and the bicategories Y-mnd and Y-int in particular, inherit the property of being closed with respect to 1-cell composition. ------------------------------------------------------------------------ On property-like structures G. M. Kelly and Stephen Lack A category may bear many monoidal structures, but (to within a unique isomorphism) only one structure of `category with finite products'. To capture such distinctions, we consider on a 2-category those 2-monads for which algebra structure is essentially unique if it exists, giving a precise mathematical definition of `essentially unique' and investigating its consequences. We call such 2-monads property-like. We further consider the more restricted class of fully property-like 2-monads, consisting of those property-like 2-monads for which all 2-cells between (even lax) algebra morphisms are algebra 2-cells. The consideration of lax morphisms leads us to a new characterization of those monads, studied by Kock and Zoberlein, for which `structure is adjoint to unit', and which we now call lax-idempotent 2-monads: both these and their colax-idempotent duals are fully property-like. We end by showing that (at least for finitary 2-monads) the classes of property-likes, fully property-likes, and lax-idempotents are each coreflective among all 2-monads. ------------------------------------------------------------------------ Closed model categories for [n,m] types J. Ignacio Extremiana Aldana, Luis J. Hernandez Paricio, Maria T. Rivas Rodriguez For m >= n > 0, a map f between pointed spaces is said to be a weak [n,m]-equivalence if f induces isomorphisms of the homotopy groups \pi_k for n <= k <= m~. Associated with this notion we give two different closed model category structures to the category of pointed spaces. Both structures have the same class of weak equivalences but different classes of fibrations and therefore of cofibrations. Using one of these structures, one obtains that the localized category is equivalent to the category of n-reduced CW-complexes with dimension less than or equal to m+1 and m-homotopy classes of cellular pointed maps. Using the other structure we see that the localized category is also equivalent to the homotopy category of (n-1)-connected (m+1)-coconnected CW-complexes. ------------------------------------------------------------------------ Multilinearity of Sketches David B. Benson We give a precise characterization for when the models of the tensor product of sketches are structurally isomorphic to the models of either sketch in the models of the other. For each base category K call the just mentioned property (sketch) K-multilinearity. Say that two sketches are K-compatible with respect to base category K just in case in each K-model, the limits for each limit specification in each sketch commute with the colimits for each colimit specification in the other sketch and all limits and colimits are pointwise. Two sketches are K-multilinear if and only if the two sketches are K-compatible. This property then extends to strong Colimits of sketches. We shall use the technically useful property of limited completeness and completeness of every category of models of sketches. That is, categories of sketch models have all limits commuting with the sketched colimits and and all colimits commuting with the sketched limits. Often used implicitly, the precise statement of this property and its proof appears here. ------------------------------------------------------------------------ Editors of Theory and Applications of Categories John Baez, University of California Riverside baez@math.ucr.edu Michael Barr, McGill University barr@math.mcgill.ca Lawrence Breen, Universite de Paris 13 breen@math.univ-paris13.fr Ronald Brown , University of North Wales r.brown@bangor.ac.uk Jean-Luc Brylinski, Pennsylvania State University jlb@math.psu.edu Aurelio Carboni, Universita della Calabria carboni@unical.it Peter T. Johnstone, University of Cambridge ptj@pmms.cam.ac.uk G. Max Kelly, University of Sydney kelly_m@maths.usyd.edu.au Anders Kock, University of Aarhus kock@mi.aau.dk F. William Lawvere, State University of New York at Buffalo wlawvere@acsu.buffalo.edu Jean-Louis Loday, Universite Louis Pasteur et CNRS, Strasbourg loday@math.u-strasbg.fr Ieke Moerdijk, University of Utrecht moerdijk@math.ruu.nl Susan Niefield , Union College niefiels@union.edu Robert Pare, Dalhousie University pare@mscs.dal.ca Andrew Pitts , University of Cambridge ap@cl.cam.ac.uk Robert Rosebrugh , Mount Allison University rrosebrugh@mta.ca Jiri Rosicky, Masaryk University rosicky@math.muni.cz James Stasheff , University of North Carolina jds@charlie.math.unc.edu Ross Street , Macquarie University street@macadam.mpce.mq.edu.au Walter Tholen , York University tholen@mathstat.yorku.ca Myles Tierney, Rutgers University tierney@math.rutgers.edu Robert F. C. Walters , University of Sydney walters_b@maths.usyd.edu.au R. J. Wood, Dalhousie University rjwood@mscs.dal.ca From cat-dist Thu Jan 22 16:40:37 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id QAA31811; Thu, 22 Jan 1998 16:39:30 -0400 (AST) Date: Thu, 22 Jan 1998 16:39:30 -0400 (AST) From: categories To: categories Subject: coinduction papers Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-Status: 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. From cat-dist Thu Jan 22 16:40:41 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id QAA10512; Thu, 22 Jan 1998 16:40:12 -0400 (AST) Date: Thu, 22 Jan 1998 16:40:12 -0400 (AST) From: categories To: categories Subject: CfP: ESSLLI-98 Workshop on Logical Abstract Machines Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Thu, 22 Jan 1998 13:44:26 +0000 From: Eike Ritter ESSLLI-98 Workshop on LOGICAL ABSTRACT MACHINES August 17 - 21, 1998 A workshop held as part of the 10th European Summer School in Logic, Language and Information (ESSLLI-98) August 17 - 28, 1998, Saarbrueken, Germany ** SECOND CALL FOR PAPERS ** ORGANISERS: Valeria de Paiva and Eike Ritter (University of Birmingham) Web site: http://www.cs.bham.ac.uk/~exr/logmach.html BACKGROUND: This workshop brings together recent work on the design of abstract machines for functional programming languages based on logical foundations. Abstract machines describe implementations of functional languages on a level of abstraction which is high enough to make it possible to reason about the implementation but low enough as to allow an easy coding of the abstract machine. The workshop is aimed at students and researchers with a basic understanding of functional programming and intuitionistic logic who want to work on the exciting field of programming with a solid logical basis. We focus the workshop along two main themes: explicit substitutions and abstract machines based on Linear Logic. Most of the more recent work on abstract machines is directed towards implementing and proving correct functional languages based on Linear Logic ideas. Linear Logic, being a resource logic, was deemed ideal to model resource control in functional languages. FORMAT OF THE WORKSHOP: The workshop consists of five sessions of 90 minutes and time will be allocated according to the quality of the submissions. We seek original papers on the full spectrum of abstract machines from theory to application. Among the topics of interest are: Theory Design and Implementation ------ ------------------------- formal semantics description of working systems explicit substitution calculi combinators type theory graph reduction techniques linear decorations run-time/memory management game theory for linear logic applications SUBMISSIONS: All researchers in the area, but especially Ph.D. students and young researchers, are encouraged to submit an extended abstract (up to 12 pages) and preferably in postscript A4 format by **February 15, 1998** via e-mail to E.Ritter@cs.bham.ac.uk or alternatively by post to Dr E. Ritter University of Birmingham School of Computer Science Edgbaston, Birmingham B15 2TT, England, UK Authors will be notified of acceptance or rejection by April 15. Final version of the accepted papers must be received in camera-ready form by June 1st, for inclusion in the informal proceedings. We are looking into formal publication of the proceedings. INVITED SPEAKERS (to be confirmed): Andrea Asperti, University of Bologna Pierre-Louis Curien, ENS, Paris Vincent Danos, Paris 7 Ian Mackie, Ecole Polytechnique Kristoffer Rose, ENS Lyon REGISTRATION: Workshop contributors will be required to register for ESSLLI-98, but they will be elligible for a reduced registration fee. IMPORTANT DATES: Feb 15, 98: Deadline for submissions Apr 15, 98: Notification of acceptance May 15, 98: Deadline for final copy Aug 17, 98: Start of workshop FURTHER INFORMATION: To obtain further information about ESSLLI-98 please visit the ESSLLI-98 home page at http://www.coli.uni-sb.de/esslli From cat-dist Thu Jan 22 16:40:57 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id QAA03724; Thu, 22 Jan 1998 16:40:56 -0400 (AST) Date: Thu, 22 Jan 1998 16:40:56 -0400 (AST) From: categories To: categories Subject: Perfect double negation Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Thu, 22 Jan 1998 17:22:17 GMT From: Martin Escardo Dear toposophers, Every sober space has a smallest dense perfect subspace. In many cases this is precisely the subspace of maximal points in the specialization order. In general it is larger than that. This is approached via locales. Every locale A has a smallest dense perfect sublocale, which is spatial if A is. It is obtained by the perfect coreflection of the double negation nucleus. The construction seems to generalize from locales to toposes. But what does it produce (instead of subspaces of maximal points)? And what is its logical content? Could toposes of sheaves help one to understand this? Thanks in advance for any clue. Details follow. Martin Escardo --------------------------------------------------------------------- http://www.dcs.ed.ac.uk/home/mhe --------------------------------------------------------------------- Every finite T_0 space has a smallest dense subspace, namely its subspace of maximal points in the specialization order. And every locale has a smallest dense sublocale, induced by the double negation nucleus, as it is well known. But it is also well known that this is hardly ever spatial, even if the given locale is. I have considered a modification of this construction. Let's say that a nucleus on a locale is perfect if it preserves directed joins. If we say that a perfect map is a continuous map f:A->B such that the right adjoint f_*:O(A)->O(B) of the frame map f^*:O(B)->O(A) preserves directed joins, then a nucleus is perfect iff it is induced by a perfect map. Let's also say that a sublocale is perfect if the inclusion is perfect. It turns out that every locale has a smallest dense perfect sublocale. Classically, one can show that spatial locales are closed under perfect sublocales. Hence every sober space has a smallest dense perfect sober subspace. This goes as follows. One knows that the set NA of nuclei on a locale A, with the pointwise ordering, is a frame. Denote by FA the set of perfect nuclei. Then one can show that FA is a subframe of NA. (The join of a set of perfect nuclei is computed by taking the pointwise (directed) join of the finite compositions of the given nuclei.) [[Digression: F is functorial on the category of compact and stably locally compact locales with perfect maps. For such a locale A, the locale FA is compact regular, and if A is compact regular then FA=A. For example, if A is the topology of lower semicontinuity (=Scott topology) on the unit interval, then FA is the Euclidean topology on the unit interval. But this is another story.]] Thus, there is a coreflective adjunction between FA and NA, which in one way includes FA into NA and in the other assigns to each nucleus in NA the join of the perfect nuclei below it. (If A is compact and stably locally compact then there is a simple formula for the perfect coreflection of nuclei on A.) Thus the smallest dense perfect sublocale is induced by the perfect coreflection of the double negation nucleus. But what is it? Let's call it the support of A and denote it by Supp A. The support always contains the subspace of maximal points (oh, I should say Max Pt A is included in Pt Supp A---but I'll refer to a locale as space for terminological simplicity). In many cases it consists exactly of the maximal points. For instance, if A is compact and stably locally compact then this is the case iff the subspace of maximal points is compact, and in this case Supp A is a compact regular locale. (I observe at this point that compact stably locally compact locales are closed under perfect sublocales). Some examples and counterexamples can be useful: (i) Let A be the Scott topology induced by the prefix order on finite and infinite sequences over {0,1}. Then Supp A is the topology of Cantor space. (ii) Same but sequences over natural numbers. Then Supp A = A, and not Baire space as one could expect from the previous example, because Baire space fails badly to be locally compact. (iii) Let A be the Scott topology on compact real intervals ordered by reverse inclusion. Then Supp A is the topology of the Euclidean real line. (iv) The previous example doesn't fit in the above characterization as it is not compact. If we add an artificial bottom interval, then we get a compact stably locally compact locale. But Supp A is then the topology of the Euclidean real line with a bottom element in the specialization order---bottom doesn't get removed in this case. (v) Let UA be the upper power locale of a compact regular locale A. Then Supp UA = A. This again fits in the above characterization. (The above claims [[except the ones in double brackets]] are proved in the paper "Properly injective spaces and functions spaces", which should have been called "Perfectly injective spaces and function spaces". It is going to appear soon. Meanwhile it is available at http://www.dcs.ed.ac.uk/home/mhe/pub/papers/injective.ps.gz) -------------------------- Some questions to finish: -------------------------- Perfect double negation on the topology of a space removes the partial points of the space in many cases. What does it do to toposes? Any clue is very much appreciated. In another direction, double negation takes us from intuitionistic logic to classical logic. Is that behind any correlation intuitionistic logic<->partiality, classical logic<->totality? Can we make this precise by taking toposes of sheaves? The inclusion s:A->Supp A, being a continuous map, induces a geometric morphism S=Shv(s):Shv(A)->Shv(Supp A). Since s_* preserves directed joins, one could guess that S_* preserves directed colimits. Would that be the case? Have these "perfect" geometric morphisms been studied? From cat-dist Fri Jan 23 14:52:20 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id OAA01348; Fri, 23 Jan 1998 14:51:21 -0400 (AST) Date: Fri, 23 Jan 1998 14:51:20 -0400 (AST) From: categories To: categories Subject: Research position Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Fri, 23 Jan 1998 19:41:39 +0200 From: Enrico Vitale Dear colleagues, A research position in mathematics has been opened in Louvain-la-Neuve. It is a two-year position with a salary (free of taxes) of FB 40,000 per month. After these two years, there are good possibilities to obtain a six-year assistantship position, with then a salary of FB 50,000 per month. Candidates must have a degree in mathematics and good academic results. For the two-year position now open, there are no teaching duties; thus no knowledge of French is required. The successful candidate will enter the local research group in category theory with the aim of preparing a Ph.D. in this area. He must be ready to start working as soon as possible, and not beyond the beginning of next academic year. Please, contact me if you know anybody interested. Enrico Vitale xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx Enrico Vitale Universite catholique de Louvain tel: +32-10-473188 Institut de Mathematique Pure et Appliquee fax: +32-10-472530 Chemin du Cyclotron, 2 email: vitale@agel.ucl.ac.be B 1348 LOUVAIN-LA-NEUVE, BELGIUM From cat-dist Fri Jan 23 16:27:01 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id QAA14391; Fri, 23 Jan 1998 16:26:48 -0400 (AST) Date: Fri, 23 Jan 1998 16:26:47 -0400 (AST) From: categories To: categories Subject: Challenge from Harvey Friedman Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-Status: Date: Fri, 23 Jan 1998 11:11:28 -0800 From: Vaughan Pratt I'm taking the liberty of forwarding to the categories mailing list the following challenge posted by Harvey Friedman to Steve Simpson's Foundations of Mathematics mailing list. This is the latest in a long-running engagement about sets vs. categories on the latter list, recent postings to which can be read at http://www.math.psu.edu/simpson/fom/postings/9801.html Postings with "categor{y,ical}" in their subject lines are the relevant ones. Information about the fom list (how to subscribe etc.) can be found at http://www.math.psu.edu/simpson/fom/fom-info As we were fond of saying quarter of a century ago, Peace Vaughan Pratt ------- Forwarded Message Date: Fri, 23 Jan 1998 00:54:20 +0100 To: fom@math.psu.edu From: Harvey Friedman Subject: FOM: Set Theory Axioms The point of this posting is to give some entirely conventional axioms for set theory that are a bit simpler than many that are normally given. They are fully formal. By comparison, look at the axioms of elementary topoi that are given in MacLane/Moerdijk, Sheaves in Geometry and Logic, A first Introduction to Topos Theory, Springer-Verlag, 1994, on p. 163. The difference in complexity is strikingly grotesque. I challenge anyone to write down their favorite fully formal axioms for topoi that are sufficient to do real analysis, so we can compare them side by side with the fully formal axioms I write down here. Topos theory with natural number object is insufficient to develop undergraduate real analysis - although many fom postings conceal this fact. One has to add to topoi: natural number object, well pointedness, and choice. The latter two are nothing more than slavish translations of set theory into the topos framework. The "idea" is to take a fatally flawed foundational idea and force it to "work" by transporting important ideas from set theoretic foundations. But the axioms of elementary topoi are already incomparably more complicated than the axioms for set theory presented here. Let me start with the dramatically simple axioms of finite set theory. These amazingly simple axioms are tremendously powerful. We work in the usual classical predicate calculus with equality and one binary relation symbol epsilon - which we abbreviate here by "in." It is also useful to use the constant symbol 0 (for the empty set), the unary function symbol { } (for singletons), and the binary function symbol U (for pairwise union). Note that axioms 2-4 amount to the most trivial of definitions. 1. (forall x)(x in a iff x in b) implies a = b. 2. (forall x)(not(x in 0)). 3. x in {a} iff x = a. 4. x in a U b if and only if (x in a or x in b). 5. [phi(0) & (forall x,y)((phi(x) & phi(y)) implies phi(x U {y}))] implies phi(x). Here phi(x) is any formula in the language in which y is not free. That's all! One ***derives*** pairing, union, power set, foundation, replacement, and choice, from these axioms alone!!! Also, when appropriately formalized, "every set is finite" and things like "every set has a transitive closure." These axioms are "practically" complete - an informal concept that I have alluded to before on the fom. Now for ZFC. We take a different tack and only use epsilon. 1. (forall x)(x in a iff x in b) implies a = b. 2. (therexists x)(a in x & b in x). 3. (therexists x)(forall y in a)(forall z in y)(z in x). 4. (therexists x)(forall y)((forall z in a)(z in y) implies y in x). 5. (forall x,y)(x in y implies (therexists z in y)(forall w in z)(w notin y)). 6. (therexists x,y)(x in y & (forall z in y)(therexists w in y)(z in w)). 7. (therexists x)(forall y)(y in x iff (y in a & phi)), where phi is any formula in the language in which x is not free. 8. (forall x in a)(therexists y)(phi) & (forall x,y,z)((phi(x,z) & phi(y,z)) implies x = y) implies (therexists w)(forall x in a)(therexists unique y in w)(phi), A novelty is the axiom of infinity, 6, is simpler than usual; and also choice and replacement are combined nicely by 8. This allows such a simple axiomatization in purely primitive notation. Try to right down the axioms of a topos with natural number object, well pointed, and choice, in simple primitive notation!! Good luck. As is well known, ZFC is "practically" complete. The version in the book on p.163 - which does not even include natural number object, well pointedness, or choice - requires a very substantial amount of preliminary abbreviations in order to formalize. ------- End of Forwarded Message From cat-dist Fri Jan 23 19:38:27 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id TAA09366; Fri, 23 Jan 1998 19:37:44 -0400 (AST) Date: Fri, 23 Jan 1998 19:37:43 -0400 (AST) From: categories To: categories Subject: Re: Challenge from Harvey Friedman Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Fri, 23 Jan 1998 16:32:35 -0600 (CST) From: David Yetter Dear Fellow Categorists: I am personally not likely to take up Harvey Friedman's challenge, having long been doing "category theory as algebra" rather than "category theory as foundations". I would like to point out, though that Friedman has deliberately chosen as a test case real analysis, a subject which exists only to simulate the existence of fluxions on the basis of foundations tied to two-valued logic. How about asking Friedman to give an elegant, elementary foundation for rings satisfying the Kock-Lawvere axioms? The use of an axiom schema in which arbitrarily complex formulae may be subsituted also seems a bit of a dodge. At first glance, elementary topoi plus NNO, well-pointed and choice still doesn't need such things (but I could be wrong, not having thought much about it for years). Best Thoughts, David Yetter From cat-dist Sat Jan 24 13:33:51 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id NAA00967; Sat, 24 Jan 1998 13:33:23 -0400 (AST) Date: Sat, 24 Jan 1998 13:33:23 -0400 (AST) From: categories To: categories Subject: Re: Challenge from Harvey Friedman Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-Status: Date: Fri, 23 Jan 1998 21:22:39 -0500 (EST) From: Michael Barr I guess simplicity is in the eye of the beholder. For example, I do not consider the categorical version of either choice (epis split) or well-pointed (1 is a generator) to be translations of set theory, but perfectly natural categorical axioms. The point is that Harvey is a set-theorist, so he thinks comprehension and all that stuff (which at least 95% of all mathematicians could not state properly if their lives depended on it) is perfectly natural and I don't. But my actual criticism of ZF(C) is much simpler. I have taught these courses in set theory and we spend a lot of time developing these epsilon trees and then totally ignore the structure. In other words, the epsilon tree structure of sets is totally irrelevant to what you do with them. There are a number of definitions of pairs, but they are irrelevant. The only thing we need to know about pairs (and the only thing a categoriest does know) is when two pairs are equal. All the defintions of pairs have that property of course, but they also have irrelevant properties. Mike From cat-dist Sat Jan 24 13:34:45 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id NAA19677; Sat, 24 Jan 1998 13:34:43 -0400 (AST) Date: Sat, 24 Jan 1998 13:34:43 -0400 (AST) From: categories To: categories Subject: Re: Challenge from Harvey Friedman Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-Status: Date: Sat, 24 Jan 1998 15:59:46 +0000 (GMT) From: Dr. P.T. Johnstone > But the axioms of elementary topoi are already incomparably more > complicated than the axioms for set theory presented here. What on earth does Friedman mean by complicated? As Peter Freyd pointed out a long time ago, the axioms for an elementary topos are essentially algebraic -- that is, they live at a very low level of logical complexity. The very first axiom in anyone's (including Friedman's) axiomatization of set theory is the axiom of extensionality, which is not expressible even in coherent logic (at least, not unless you take not-membership as a primitive predicate, on the same level as membership). Unless Friedman can put forward an objective measure of complexity (as opposed to "unfamiliarity to H. Friedman") which justifies the above quote, then his challenge is not worth considering. Peter Johnstone From cat-dist Mon Jan 26 15:00:08 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id OAA30246; Mon, 26 Jan 1998 14:59:18 -0400 (AST) Date: Mon, 26 Jan 1998 14:59:18 -0400 (AST) From: categories To: categories Subject: Immodest proposal Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-Status: Date: Sun, 25 Jan 1998 10:48:12 -0500 (EST) From: John R Isbell Contemplating Harvey Friedman's Challenge, I asked myself 'Aren't there more important problems around?' And of course there are. Moreover, I believe I have solved one of them. P. What should we call the ancient substitute for e-mail? S. Why not m-mail? Snappy; memorable; unmistakable; and m=e\over {c^2} gives the value. John Isbell From cat-dist Mon Jan 26 15:00:12 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id OAA01465; Mon, 26 Jan 1998 14:58:35 -0400 (AST) Date: Mon, 26 Jan 1998 14:58:35 -0400 (AST) From: categories To: categories Subject: Re: Challenge from Harvey Friedman Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-Status: Date: Sun, 25 Jan 1998 10:13 +0530 From: CAYLEY@tifrvax.tifr.res.in I remember to have seen a paper on frameworks for measuring complexity of mathematical concepts by two autors earlier. (I don't exactly recall where) but I also remeber that one of the authors was H.Friedman! P.S.Subramanian Tata Institute. From cat-dist Mon Jan 26 15:00:16 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id PAA29830; Mon, 26 Jan 1998 15:00:15 -0400 (AST) Date: Mon, 26 Jan 1998 15:00:15 -0400 (AST) From: categories To: categories Subject: Re: Challenge from Harvey Friedman Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-Status: Date: Mon, 26 Jan 1998 12:10:01 +0000 From: Steven Vickers >Topos theory with natural number object is insufficient to develop >undergraduate real analysis - although many fom postings conceal this fact. >One has to add to topoi: natural number object, well pointedness, and >choice. The latter two are nothing more than slavish translations of set >theory into the topos framework. The "idea" is to take a fatally flawed >foundational idea and force it to "work" by transporting important ideas >from set theoretic foundations. The slavish translation of well pointedness and choice actually arises from a more subtle slavish translation of point-set topology. Point-set topology postulates that the points of a topological space can be comprehended as a set, but this apparently innocuous idea is questionable (perhaps we should be more sceptical about what sets can comprehend following our experience with proper classes). When we formulate our foundations based on the ideas of topos theory, and interpret "set" as object in an elementary topos, then - given a natural numbers object - we can ideed construct "sets of reals" but we find that they misbehave. Normal theorems of analysis, such as Heine-Borel, fail unless we also impose the additional ideas from set-theoretic foundations. However, there is a different way of formulating topology, using locales or "formal spaces", that works in any elementary topos (still need an NNO to get the reals, of course) and preserves the validity of theorems such as Heine-Borel. It works by addressing the topology directly, without regard to what the opens in it might be sets of. It still has a concept of point, but generalized point with respect to a varying set-theory (stage of definition) instead in a fixed one. We can't take a single comprehension in our favourite set-theory as encompassing all the points. The moral is that a topological space is more than just a set of points together with a topology of open subsets. If, for any reasons at all, we are interested in doing mathematics constructively, then we should discard point-set topology and use locales. My picture of what is going on is this: when we try to make a set out of a space by stripping off the topology, we damage the points, and we put the well-pointedness and choice in as crutches and plasters to try to rectify the damage we should never have done in the first place. Steve Vickers. From cat-dist Mon Jan 26 15:01:07 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id PAA26123; Mon, 26 Jan 1998 15:01:06 -0400 (AST) Date: Mon, 26 Jan 1998 15:01:05 -0400 (AST) From: categories To: categories Subject: Re: Challenge from Harvey Friedman Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-Status: Date: Mon, 26 Jan 1998 14:21:40 +0000 (GMT) From: Ronnie Brown How does Harvey Friedman know that the formulation of real analysis as carried out in set theory will do all that real analysis *should* do? My favourite example is that of partial functions. Most teachers of real analysis (calculus) rightly impress on students the importance of the domain of a function, and the domain of f+g, etc. So a student might think that the algebra and analysis of partial functions would occupy a good part of the literature. Solutions of ODEs (such as dy/dx=exp(-y) ) are often given by partial functions with domain involving a parameter, and the solution (including its domain) seems to vary smoothly with this parameter. In fact there is very little in the literature on such matters. I had a small go with 29. (with A.M. ABD-ALLAH), ``A compact-open topology on partial maps with open domain'', {\em J. London Math Soc.} (2) 21 (1980) 480-486. It is not clear that the most general case of the functional analysis of partial functions with domain neither open nor closed can be successfully handled within classical set theory. There is a chance it can be handled within topos theory. (Try functions defined on the leaves of foliations. Any answers?) Another point of topos theory is to handle categories such as that of directed graphs in a similar manner to the category of sets, and to make comparisons between such categories. (Bill Lawvere has of course written a lot on this.) Ronnie Brown From cat-dist Mon Jan 26 19:34:20 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id TAA02019; Mon, 26 Jan 1998 19:34:05 -0400 (AST) Date: Mon, 26 Jan 1998 19:34:04 -0400 (AST) From: categories To: categories Subject: Re: Challenge from Harvey Friedman Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Mon, 26 Jan 1998 17:36:31 -0500 (EST) From: John R Isbell P. S. Subramanian's 'A framework for measuring ... complexity' is by H. Friedman and R. C. Flagg, Adv. in Appl. Math. 11 (1990), 1-34 [MR91f:03111]. John Isbell From cat-dist Wed Jan 28 10:10:05 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id KAA01244; Wed, 28 Jan 1998 10:09:34 -0400 (AST) Date: Wed, 28 Jan 1998 10:09:34 -0400 (AST) From: categories To: categories Subject: Re: Challenge from Harvey Friedman Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Tue, 27 Jan 1998 11:26:45 +0000 (GMT) From: Dusko Pavlovic According to Harvey Friedman: > I challenge anyone to write down their favorite fully formal axioms for > topoi that are sufficient to do real analysis, so we can compare them side > by side with the fully formal axioms I write down here. The papers I announced here the other day do not offer any such "dramatically simple" or "tremendously powerful" axioms, comparable with Friedman's, nor indeed anything as politically engaged --- but I think they may have to do with the issue. Given a field in any category with enough limits, we implement analytic functions, solve differential equations --- do quite a bit of real analysis. It turns out that most of it can be captured as guarded induction on final coalgebras. We did not try to use this to embed real analysis in any fully formal foundational theory, but to provide a uniform way of implementing it on a computer, together with infinitary constructions and all. The result may not be as "amazingly simple" as Friedman's axioms, but it is fairly simple, and conceptually clear. Check it out (the last two papers at http://www.cogs.susx.ac.uk/users/duskop/). Sorry for the plug, but I actually want to make a point. I don't think category theory should spend time trying to beat set theory on its own territory of fully formal systems. Sets were invented in the time of doubt about the consistency of mathematics, when foundations were really sought for. Nowadays people go and prove Fermat Theorem. Set theory wants to be something like a formal grammar of mathematics. That is fine, can be very interesting in itself, but great stories are usually told without thinking of grammar. Category theory might perhaps do better to try to be some kind of a programming language or mathematics, a set of object-(or better: method-)oriented tools, conceptualizing large "software" projects of the day. How about that? -- Dusko Pavlovic PS On the other hand, us toposophers competing against them setologists who can do analysis --- aren't we a bit like A Frenchman and an Englishman making the bet who can faster translate a sentence from German. Little Gretschen comes by and says: (fg)' = f'g + fg'... I mean, didn't analysts tell *everyone* by now: THEY DO NOT CARE FOR FOUNDATIONS. They do not think of their manifolds neither as sets of little elements, nor hanging on a bunch of morphisms among other manifolds. Most of the time, they are quite happy with their manifolds as manifolds. Next time they need foundations, they'll invent them again, like they invented sets and sheaves. From cat-dist Wed Jan 28 10:10:07 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id KAA00514; Wed, 28 Jan 1998 10:08:50 -0400 (AST) Date: Wed, 28 Jan 1998 10:08:50 -0400 (AST) From: categories To: categories Subject: The Friedman/Flagg paper Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Mon, 26 Jan 1998 19:16:12 -0500 (EST) From: Peter Freyd 91f:03111 03E99 03B30 03F99 68Q25 Friedman, H.(1-OHS); Flagg, R. C.(1-SME) A framework for measuring the complexity of mathematical concepts. (English) Adv. in Appl. Math. 11 (1990), no. 1, 1--34. _________________________________________________________________ This paper presents a system $\scr F\sb 0(\scr B)$ that is intended to allow practical computation of the complexity of mathematical concepts. $\scr F\sb 0(\scr B)$ is an untyped theory of sets and partial functions in a first-order free logic with equality and a description operator. Its language $\scr L\sb 0(\scr B)$ contains many primitive operations, such as $n$-tuples, lambda abstraction, comprehension terms, finite set and Cartesian product formation, and definition by cases. $\scr B$ denotes a set of "descriptive forms" that are patterns according to which new constants, functions, and predicates can be defined. After a rigorous presentation of the syntax of $\scr L\sb 0(\scr B)$, standard programming language procedures yield parsing and recognition algorithms. A precise semantics for $\scr L\sb 0(\scr B)$ is given, followed by a deductive system $\scr F\sb 0(\scr B)$ that is shown to be complete by means of a Henkin-style proof. Finally, the authors introduce the notions of definition sequence, definition dag (directed acyclic graph), and definition tree. On the basis of these notions, they promise that, in a future paper, they will develop measures of complexity of definitions that will make possible practical calculation of the complexity of concepts in a large part of current mathematical practice. Reviewed by E. Mendelson From cat-dist Wed Jan 28 10:10:36 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id KAA32430; Wed, 28 Jan 1998 10:10:35 -0400 (AST) Date: Wed, 28 Jan 1998 10:10:35 -0400 (AST) From: categories To: categories Subject: 67th PSSL Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-Status: Date: Tue, 27 Jan 1998 14:38:06 +0100 (MET) From: Jaap van Oosten FIRST ANNOUNCEMENT Dear friends and colleagues, We plan to organize the 67th meeting of the Peripatetic Seminar on Sheaves and Logic in Utrecht over the weekend of 30-31 May, 1998. As usual we welcome talks on sheaves, logic and related areas. In order to register, please fill in the form below and return (preferably by email) to Jaap van Oosten (jvoosten@math.ruu.nl, or to the address below). We'd be obliged if you could register before half May. Postal address: Dept. of Mathematics, P.O.Box 80.010 3508 TA Utrecht, The Netherlands --------------------------------------------------------------- Name _____________________________ Address _____________________________ _____________________________ _____________________________ _____________________________ email I wish to give a talk entitled__________________________________ ________________________________________________________ I wish to reserve accomodation for the following nights: (single/double)_______________________ ---------------------------------------------------------------- Looking forward to meeting you in Utrecht, Carsten Butz, Ieke Moerdijk and Jaap van Oosten From cat-dist Wed Jan 28 10:11:19 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id KAA02626; Wed, 28 Jan 1998 10:11:18 -0400 (AST) Date: Wed, 28 Jan 1998 10:11:18 -0400 (AST) From: categories To: categories Subject: Announcement of PhD Positions in Computing Science at Chalemrs Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from QUOTED-PRINTABLE to 8bit by mailserv.mta.ca id KAA02626 Status: O X-Status: Date: Wed, 28 Jan 1998 13:29:40 +0100 (MET) From: Mary Sheeran The Department of Computing Science at the Chalmers University of Technology and Göteborgs University announces free PhD positions. The major research topics at the department are programming logic and type theory, functional programming, concurrency, fault tolerant distributed systems, formal methods, cognition technology, and algorithms and discrete optimisation, but research is also carried out in a number of other topics. More information about the research at the department can be found on the WWW on page: http://www.cs.chalmers.se/ComputingScience/Research Most PhD positions are five year scholarships. The PhD student will spend about 80 percent of his or her time on graduate studies, and about 20 percent on teaching. Applicants must have an undergraduate degree in Computer Science with excellent results. The department tries to increase the number of female employees, and especially welcomes female applicants. At the moment the scholarships consists of 15400 (18000) SEK per month in the first (last) year. Usually a foreign PhD student does not teach in his or her first year in Sweden, and as a consequence the scholarship is of a slightly smaller size. More information about the graduate programmes can be found on the WWW on page: http://www.cs.chalmers.se/Cs/Grad/gradinfo/gradinfo.html To apply, send us a letter in English, covering 1 data about yourself; 2 a copy of an official paper giving grades from your undergraduate degree(s); 3 a statement about your main interests and your plans for research; 4 some letters of recommendation from people that know you as a student or as an employee; 5 any scientific papers you have written. Send your application to Director of Graduate Studies Department of Computing Science Chalmers University of Technology 412 96 Göteborg Sweden Furthermore, send an email containing the data about yourself to ms@cs.chalmers.se The last date for your application to arrive is March 2, 1998. A decision about to whom we will offer the PhD positions will be taken before June 1, 1998. From cat-dist Wed Jan 28 10:22:51 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id KAA31045; Wed, 28 Jan 1998 10:22:45 -0400 (AST) Date: Wed, 28 Jan 1998 10:22:45 -0400 (AST) From: categories To: categories Subject: Terminology for Kan extensions Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Wed, 28 Jan 1998 10:25:34 +0000 (GMT) From: Ronnie Brown There seems some confusion as to whether Left Kan extensions are right Kan extensions and conversely, and it seems different authors use different conventions. What do people think of using a terminology analogous to limits and colimits, i.e. Kan extensions and Kan coextensions? In particular, what Carmody and Walters call left Kan extensions would here be Kan coextensions, which can be constructed as coends (as in Mac Lane, CFTWM). This point has come from Anne Heyworth, where left Kan extensions use right rewriting, if you write composition in a category in the algebraic rather than functional way. Any other ideas? Ronnie 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 From cat-dist Thu Jan 29 16:16:54 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id QAA32194; Thu, 29 Jan 1998 16:14:56 -0400 (AST) Date: Thu, 29 Jan 1998 16:14:56 -0400 (AST) From: categories To: categories Subject: Re: Challenge from Harvey Friedman Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Wed, 28 Jan 1998 22:15:27 +0000 From: Carlos Simpson Being a newcomer to the category list, I have a really naive and stupid question (concerning H. Friedman's challenge). Namely, I was always under the impression that you had to know what a set was before you could talk about what a category was (in particular a topos). Is it possible to talk about toposes without knowing what a set is? This seems somewhat related to a question that has been bugging me for some time, namely how to talk about a ``category'' which is enhanced over itself, but not necessarily having any functor to or from Sets. The very first part of the structure would be a class of objects O together with a function (x,y)\mapsto H(x,y) from O\times O to O, but I can't get beyond that. ---Carlos Simpson From cat-dist Thu Jan 29 16:16:54 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id QAA19519; Thu, 29 Jan 1998 16:16:34 -0400 (AST) Date: Thu, 29 Jan 1998 16:16:33 -0400 (AST) From: categories To: categories Subject: Insights: adjunctions and languages Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Thu, 29 Jan 1998 17:55:05 +1100 (AEDT) From: Jonathan Burns Hello and goodwill Now that I have my PhD dissertation submitted, I've had a while to stand back from the material, and consider the categorial territory that I stumbled into in the last year or so. Although I'm acquainted with a mere fraction of the crucial concepts here, what I have found seems to contain really elegant insights into computer languages, and I want to clarify these to myself, as a philosophical basis for future study. It may well be that it will all be old news here, but the introductory texts don't spell things out in quite the way I perceive them. (My reading started out wide, but narrowed down mainly to MacLane, Barr and Wells, and articles by Ridenour in some S-V workshop proceedings some years back. Asperti and Longo has been good too.) To cut to the chase, consider Cartesian closure. If we leave out matters of storage, scoping and other time-related resources, a Lisp-family language is lambda-calculus with a reduction policy - that is, a set of decisions that one expression form is to be replaced by another. (For Lisp, the policy is to do beta- and eta-reduction in some order until no more redexes can be found.) And lambda is a CCC with name binding - as opposed to expressing everything with projectors. But more: a CCC is defined by adjunctions: unique-terminal, diagonal- product, product-exponential. These adjunctions define isomorphisms between expression forms: f = n (F g) g = (G f) u where u and n are unit and counit. In other words, the isomorphisms are determined by natural transformations, of a very simple and intuitive kind: if you can have one of a thing, you can have two of them; if you can have one thing and another, you can have both together in a product; if you have a product expression, then you can have a product expression constructor (exponential) with one term curried out. These natural transformations are universal structural operators; inherently polymorphic or domain-free, in programming terms. And using only a handful of them, you can define these isomorphisms, which then constitute an equational theory for a language - in the sense that lambda is the equational theory behind Lisp. Whatever can be defined by adjunctions is what they call "referentially transparent": equals are substituted only for equals. It's stronger than that, in fact, because with an adjunctive system like this, an expression can be substituted for another only when there is also a rule for the reverse substitution. E.g. x * x = square x The referentially-transparent equational theory stands by itself. But on top of it, we may now impose reduction policies, ("games") of various kinds: 1. We can substitute equals for equals by hand: "just doing algebra". 2. We can specify an algorithm for substitutions: intepreters. 3. We can extend this to interpreters where we introduce new reduction rules as we go along: symbolic algebra systems. 4. We can specify a data-directed backtracking algorithm, which is allowed to apply a reduction rule in either order: equational logic systems. 5. We can specify a data-directed heuristic backtracking algorithm: dunno quite what we call these, maybe constraint systems. 6. We can specify systems which not only use backtracking and heuristics, but assert and retract additional rules as we go along: traditional AI. "Extending the rules" is a dangerous game, of course; you have the responsibility for maintaining referential transparency. Nobody I've read has hinted at the possibility of automating the definition of equational rules by adjunction. Even if such a thing could only be done in a very restrained sense, though, it would still be very powerful. Vaguely, I think the rubric has to be: OK, here's the kind of data we want to work on - regular expressions, perms and coms, machine code, whatever - now, what are the equivalences we see in these domains, and are they isomorphisms? And if so, _why_ are they isomorphisms, and what natural transformations might possibly define them by adjunction? The key insight for me, the thing that categories has revealed, is that reduction polices for equational theories are _the_ bridge between the declarative and the procedural; and equational theories can be built by adjunction from universal constructors. It's so beautiful I just want to sit and gaze at it. It's one of those obvious things that you see side-on for years, and then suddenly you see it directly. More later. Jonathan Burns | burns@latcs1.lat.oz.au| A student approached Susskind, in hopes Computer Science Dept | of understanding the lambda-nature... La Trobe University | From cat-dist Fri Jan 30 15:55:23 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id PAA09514; Fri, 30 Jan 1998 15:55:05 -0400 (AST) Date: Fri, 30 Jan 1998 15:55:04 -0400 (AST) From: categories To: categories Subject: Re: Insights: adjunctions and languages Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Fri, 30 Jan 1998 10:36:58 -0500 (EST) From: F W Lawvere Mathematicians and computer scientists who have developed a clear vision of the relation between lambda calculus and cartesian-closed categories, as Jonathan Burns evidently has, may wish to consider the following PROBLEM: 1. There is a great deal of technical development of the presentational machinery of lambda calculus. 2. Lately, there have been interesting advances in the study of the algebraic theory of exponential rigs, which Tarski called "the high school" theory. (See papers of Stanley Burris et al. on counter examples by Wilkie et al. to naive completeness conjectures.) 3. There are many objectively (or semantically) arising examples of cartesian-closed categories in the form of presheaf toposes, such as that of finite directed graphs or of discrete dynamical systems (as explained in our recent elementary book published by Cambridge). 4. The rich variety of models mentioned in 3. has apparently NEVER BEEN DIRECTLY RELATED to the abstract theory of lambda calculus, nor to the theory of exponential rigs. In the latter case, although specific models are of great interest, they have been constructed by formal syntactical means, rather than through the "objective number theory" means via Steiner-Cantor- Burnside-Grothendieck-Schanuel abstraction from these concrete categories of combinatorial structures, in which the exponent- iation operation has a very explicit mathematical content and construction. Although the exponential rigs capture only the "existence of isomorphisms" equations between objects as opposed to the detailed knowledge of given morphisms (usually not iso) between the combinatorial structures and the detailed particular operations that lambda calculus eventually wants to apply to, nonetheless already at that level nontrivial equational questions arise. For example, there are often "connected" objects A which satisfy equations B^A + C^A = (B+C)^A, and there are sometimes sufficiently separating "figures" or "elements" of connected shapes. As another example, exponential objects occasionally are actually polynomial in the sense that B^A is actually iso- morphic to F(A,B) where F is a combination of products and co-products; two cases that I know of are, with B = A, F = 2A^2 and F = 1+A. The latter has a clear intuitive interpretation that the only internally definable endomaps are either identity or constant. But it is an open PROBLEM whether there are any other polynomials F for which there exists a finite presheaf topos, in which there exist objects A enjoying such isomorphisms. From cat-dist Fri Jan 30 15:55:29 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id PAA12166; Fri, 30 Jan 1998 15:55:28 -0400 (AST) Date: Fri, 30 Jan 1998 15:55:27 -0400 (AST) From: categories To: categories Subject: Re: Challenge from Harvey Friedman Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Fri, 30 Jan 1998 10:40:55 -0500 (EST) From: Michael Barr Well the first question has an easy answer. It is just as possible to talk about a category without knowing what a set is as it is to talk about a set without knowing what a set is. Of course, you cannot talk about homsets. It is interesting to read the very first Eilenberg-Mac Lane paper, which did not talk about homsets. A set is an undefined notion and there is a relation, epsilon that may hold between one set and another, subject to certain axioms, one version of which Friedman listed. A category consists of undefined things called arrows and three relations, two functional and the third partially functional (actually better than that, but leave that aside). Friedman's axioms are not coherent, as has been pointed out, while the categorical axioms are. On the other hand, one can state Friedman's axioms, in all their glorious incomprehensibility (I think I could stare at the 8th one from now until the middle of next year without understanding what it says, and the 6th, asserted to be the axiom of infinity is not much clearer) in a couple hundred words, while it is pretty much necessary to interrupt the topos axioms for some definitions (at least monic and subobject) to do the topos axioms. Thus each one looks simpler to its devotees and there is really no point in arguing about it. Michael On Thu, 29 Jan 1998, categories wrote: > Date: Wed, 28 Jan 1998 22:15:27 +0000 > From: Carlos Simpson > > Being a newcomer to the category list, I have a really naive and stupid question > (concerning H. Friedman's challenge). Namely, I was always under the impression > that you had to know what a set was before you could talk about what a > category was (in particular a topos). Is it possible to talk about toposes > without knowing what a set is? > > This seems somewhat related to a question that has been bugging me for some > time, namely how to talk about a ``category'' > which is enhanced over itself, but not necessarily having any functor to or > from Sets. The very first part of the structure would be a class of objects > O > together with a function (x,y)\mapsto H(x,y) from O\times O to O, but I > can't get beyond that. > > ---Carlos Simpson > > > From cat-dist Fri Jan 30 15:56:12 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id PAA10566; Fri, 30 Jan 1998 15:56:11 -0400 (AST) Date: Fri, 30 Jan 1998 15:56:10 -0400 (AST) From: categories To: categories Subject: Generic Programming Workshop: Final Call Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Fri, 30 Jan 1998 17:15:40 +0100 (MET) From: Roland Backhouse Final Call for Papers Workshop on Generic Programming June 18th 1998, Marstrand, Sweden (In Conjunction with Mathematics of Program Construction Conference) ---------------------------------------------- Deadline for submissions: 16th February, 1998. ---------------------------------------------- Generic programming is about making programs more adaptable by making them more general. A generic program embodies some sort of polymorphism; ordinary programs are obtained from it by suitably instantiating its parameters. The parameters may be other programs, types or type constructors, or even programming paradigms. Generic programming techniques have always been of interest, both to practitioners and theoreticians, but to date have rarely been a specific focus of research. Recent developments in functional and object-oriented programming lead the organizers of this workshop to believe that there is sufficient interest to warrant the organisation of a one-day workshop on the theme of generic programming. The workshop will be on June 18th, 1998, following on from the Mathematics of Program Construction conference. The goal of the workshop is to inventorise the full diversity of research activities in the area of generic programming, both theoretical and applied, by attracting as wide a spectrum of participants as possible to the workshop. The results of the workshop will be published in the form of a detailed summary of all presentations, prepared by the organizers and made available on internet. We cordially invite all those with an active interest in this important new area to submit a short position paper on their work to Roland Backhouse (rolandb@win.tue.nl). The position paper should outline your current research activities in this area and include references to published papers and/or web links to technical reports where more information can be found. The recommended length is approximately three pages. The deadline for submission is 16th February, 1998. Notification of acceptance will be on or before 15th March, 1998. The organizers are as follows: Roland Backhouse (Cochair), Netherlands Tim Sheard (Cochair), USA Robin Cockett, Canada Barry Jay, Australia Johan Jeuring, Sweden Karl Lieberherr, USA Oege de Moor, UK Bernhard Moeller, Germany Jose Oliveira, Portugal Fritz Ruehr, USA For further details on the Mathematics of Program Construction and this workshop please consult: http://www.md.chalmers.se/Conf/MPC98/ From cat-dist Fri Jan 30 15:56:57 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id PAA08556; Fri, 30 Jan 1998 15:56:55 -0400 (AST) Date: Fri, 30 Jan 1998 15:56:55 -0400 (AST) From: categories To: categories Subject: Friedman's challenge, and the ordinals Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-Status: Date: Fri, 30 Jan 1998 19:11:18 GMT From: Paul Taylor Date: Mon Jan 26 21:40:18 1998 Subject: Friedman's challenge The reason why 1970s topos theorists did a "slavish translation" of well-pointedness, choice, etc is quite simple: it is known in computer science and engineering as "reverse compatibility". We (ie Lawvere, Tierney and others) needed to show that whatever you could allegedly do with set theory, you could do with elementary toposes too. Now that reverse compatibility has been achieved, the old methods are obsolete, and we should be able to move on from there. We show that the new methods (by which I mean category theory in general, not necessarily elementary toposes) are more idiomatic for the old purposes and more powerful for new ones. For example we would never have got anywhere with domain models of polymorphism, or with synthetic domain theory, without category theory as our guide. I'm sure that most of the readers of "categories" can add examples from their own interests. I have a personal reason for bitterly resenting ever being taught set theory. (I don't want anybody to interpret that as resentment towards the particular people in Cambridge who did the teaching - the problem is with the mathematical community as a whole which has perpetuated this pernicious theory.) For several years I was trying to prove (in an elementary topos, in particular without excluded middle, or the axiom of collection, which seems to me to be set-theoretic hocus pocus): Let (X, <=) be a poset with least element and directed joins, and s:X->X a monotone (not necessarily Scott continuous) function. Then s has a least fixed point. I talked about my attempts at this at at least two international category meetings and several other project meetings and conferences. Because of my set-theoretic indoctrination, much as I rebelled against it, I set about defining ordinal iterates of the function s and its values at the least element. The intuitionistic theory of ordinals is complicated, and there are several flavours of them, but there is no doubt that ordinals as big as you please exist in any elementary topos. See JSL 61 (1996) 703-742. Always with traditional applications of ordinals, the problem is knowning when to stop. The textbook solution is due to Friedrich Hartogs, 1917. Basically, you take a pair of scissors ... . Andre Joyal and Ieke Moerdijk have a pair of scissors which make a cleaner cut (by our standards in category theory), but they too still chop off the standard sequence. (Maybe someone would like to write a PhD thesis which uses their methods to eliminate the set theory from the "alpha-presentable" versions of Gabriel-Ulmer duality.) In fact this result has now been proved, by a Georgian called Dimitri Pataraia. (I haven't met him, or been able to find out much about him, despite now sharing an office with another Georgian). Pataraia's solution is pure order theory. You could teach it to a third year undergraduate class in a course on lattices or domain theory. There is not an ordinal in sight. In fact, looking more closely at his solution, there *are* ordinals in it. [My version of] his proof looks remarkably like Zermelo's second proof of Choice => well ordering. It may seem strange that such an infamously classical result should contain a the essence of an intuitionistic argument, but in fact [Zermelo's version of] Choice occurs in the first line of the argument and never again. Zermelo manufactures the required ordinal structure out of the given object, whereas the subsequent orthodox approach, due to Hartogs 9 years later, is based on a single monolithic system, which has to be chopped off in a rather unceremonious fashion. Ordinals similar to Zermelo's, though only satisfying the induction scheme for a restricted class of predicates, and not satisfying any recursion scheme I can find, are also to be found in Pataraia's proof. Throughout my (personally unsuccessful) study of this problem, whenever I sought intuition from set theory it took me in the WRONG direction. I cannot think of any other branch of mathematics, with the exception of infinitessimal calculus before it was reformed, which I would condemn so utterly. In fact, 18th century calculus did give a lot of right answers, and at least its wrong ones were interesting and provoked good research. In answer to Harvey Friedman, I *don't* advocate topos theory as foundations. It still reeks of set theory (sorry, Bill). Paul Taylor =================================== Part II (it seems that I originally sent the above to the wrong email alias) I didn't properly spell out my philosophical conclusions about ordinals. What I mean is that a [not "the"] system of ordinals *ought* to have a top element (a fixed point for successor). In other words, I am contradicting the usual interpretation of the Burali-Forti paradox, and discarding the tradition of chopping the monolithic system of ordinals off, as Hartogs, Joyal/Moerdijk and many others have done (including me). The notion of cardinality is clearly stupid from a categorical point of view (we know better than to classify objects up to isomorphism, without even any regard to their automorphism groups) and, as an atheist, I find Cantor's theologically motivated notion of "size" utterly incomprehensible. While I'm at it, I don't accept the argument in either Russell's paradox (re the set {x:x not in x}) or Cantor's theorem that P(X) =/= X. It's not that I am particularly keen to have a set of all sets (though such a thing is probably to be expected from the right logical principles in much the same way as a universal Turing machine is in recursion theory), but that I do not consider that these classic arguments ought to be valid. Andy Pitts and I traced Russell's paradox to a particular quantifier (in fact in a locally cartesian closed category) - see our paper in Studia Logica 1989 p 387. It is this quantifier which I reject. In fact he and I independently had models which had a type of types, and achieved this by restricting the quantifiers which could be interpreted. The Burali-Forti paradox goes away too if the class of predicates for which the induction scheme is valid (in the definition of an ordinal) is retricted. For example, the domain of increasing natural numbers plus a fixed point is such an ordinal for Scott-continuous predicates (the Crole-Pitts FIX object). I think I may be able to adjust the notion of elementary topos (I prefer to think in these terms than in symbolic logic) to a useful fragment in which Cantor's theorem fails. (Sorry to be so vague, but I haven't got very far with this, and currently have a head full of perl programming.) Paul From cat-dist Sat Jan 31 10:57:55 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id KAA22369; Sat, 31 Jan 1998 10:56:58 -0400 (AST) Date: Sat, 31 Jan 1998 10:56:58 -0400 (AST) From: categories To: categories Subject: sad news Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-Status: Date: Fri, 30 Jan 1998 17:04:36 -0500 (EST) From: Peter Freyd Sammy Eilenberg died today. He had been unconscious since June. Knowing it was inevitable doesn't really help.