From rrosebru@mta.ca Wed Feb 4 10:02:53 2004 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 04 Feb 2004 10:02:53 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1AoNWd-0003LN-00 for categories-list@mta.ca; Wed, 04 Feb 2004 09:57:07 -0400 Date: Mon, 2 Feb 2004 09:45:08 -0500 (EST) From: Peter Freyd Message-Id: <200402021445.i12Ej8dv026046@saul.cis.upenn.edu> To: categories@mta.ca Subject: categories: Tom Fox in the news Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 1 Copyright 2004 National Post, All Rights Reserved National Post (Canada) February 2, 2004 Monday National Edition SECTION: Editorials; Pg. A11 LENGTH: 216 words HEADLINE: 'Lying' statistics SOURCE: National Post BYLINE: Thomas Fox BODY: Re: How Efficient Are Our Governments? Not Very. William Watson, Jan. 29 Mr. Watson should take a refresher course in mathematics before quoting statistics to prove the thesis in his title. He uses "performance per unit of public spending" to measure government efficiency when it measures nothing of the kind. Consider the following model: Suppose in country A, people spend $100 each on health care, paid directly to service providers (doctors, hospitals, etc.). In country B, people pay $100 in taxes to the government, which then pays for all health care. If the health care delivered is the same, Mr. Watson would say the government of country B was horribly inefficient because it spends a portion of the GDP on health care while government A spends 0% of GDP on health care. And if the people of country B get better service, Mr. Watson still says government B is inefficient -- "there isn't much bang for the big-government buck." How can better service for the same cost to the public be a sign of inefficiency? There are, of course, reasonable and accurate ways to measure government efficiency, but this isn't it. As Disraeli said "There are three kinds of lies: lies, damned lies and statistics." Dr. Thomas Fox professor of mathematics Dawson College, Montreal. From rrosebru@mta.ca Fri Feb 6 10:17:10 2004 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 06 Feb 2004 10:17:10 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1Ap6kW-0004ks-00 for categories-list@mta.ca; Fri, 06 Feb 2004 10:14:28 -0400 From: iu3@mcs.le.ac.uk To: categories@mta.ca Subject: categories: CFP: SOS 2004 Date: 06 Feb 2004 13:51:07 +0000 X-Mailer: Prayer v1.0.7 X-Originating-IP: [143.210.72.63] Mime-Version: 1.0 Content-Type: text/plain; format=flowed; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Message-Id: <20040206135107.C1E8C2F6738@scyros.mcs.le.ac.uk> Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 2 Call for Papers =09 Structural Operational Semantics http://www.cs.auc.dk/~luca/SOS-WORKSHOP/ A Satellite Workshop of CONCUR 2004 30 August, 2004, London, United Kingdom Aims: Structural operational semantics (SOS) provides a framework=20 for giving operational semantics to programming and specification=20 languages. A growing number of programming languages from=20 commercial and academic spheres have been given usable semantic=20 descriptions by means of structural operational semantics.=20 Because of its intuitive appeal and flexibility, structural=20 operational semantics has found considerable application in=20 the study of the semantics of concurrent processes. Moreover,=20 it is becoming a viable alternative to denotational semantics=20 in the static analysis of programs, and in proving compiler=20 correctness. Recently, structural operational semantics has been successfully=20 applied as a formal tool to establish results that hold for classes=20 of process description languages. This has allowed for=20 the generalization of well-known results in the field of process=20 algebra, and for the development of a meta-theory for process calculi=20 based on the realization that many of the results in this field=20 only depend upon general semantic properties of language constructs. The proposed SOS workshop aims to be a forum for researchers,=20 students and practitioners interested in new developments and=20 directions for future investigation in the field of structural=20 operational semantics. One of the specific goals of the workshop is=20 to establish synergies between the concurrency and programming=20 language communities working on the theory and practice of SOS.=20 The workshop will also mark the publication of a special issue of=20 the Journal of Logic and Algebraic Programming, devoted to SOS.=20 Together with original research papers on SOS, this special issue=20 will feature a definitive version of Gordon Plotkin's 1981 DAIMI memo=20 on SOS, together with a piece by Plotkin on the origins of SOS.=20 Specific topics of interest include (but are not limited to): * programming languages * process algebras * higher-order formalisms * rule formats for operational specifications * meaning of operational specifications * comparisons between denotational, axiomatic and SOS=20 * compositionality of modal logics with respect to=20 operational specifications * congruence with respect to behavioural equivalences * conservative extensions * derivation of proof rules from operational specifications * software tools that automate, or are based on, SOS Papers reporting on applications of SOS to software engineering and=20 other areas of computer science are welcome. Paper submission: =20 We solicit unpublished papers reporting on original research on=20 the general theme of SOS. Prospective authors are invited to submit=20 a pdf or postscript file with their extended abstract, whose length=20 should not exceed 15 pages, by email to all of the co-chairs at their=20 respective email addresses. The email message with the submission=20 should also include, in plain text, contact information for=20 the author(s), together with the title and abstract of the submission. =20 Submissions are to be received by Sunday, 6 June, 2004. Authors will=20 be notified of acceptance by Wednesday, 30 June, 2004. Submissions=20 from the PC members are allowed.=20 Proceedings: =20 Preliminary proceedings containing the abstracts of the talks will be=20 published as a volume in the BRICS Notes Series, and will be available=20 at the meeting. The final proceedings of the workshop will appear as=20 a volume in the ENTCS series. =20 If the quality and quantity of the submissions warrant it, the co-chairs=20 plan to arrange a special issue of an archival journal devoted to full=20 versions of selected papers from the workshop.=20 Important Dates: * Submission: Sunday 6 June 2004 * Notification: Wednesday 30 June 2004 * Final version: Friday July 16 2004 * Workshop: Monday 30 August 2004 Invited Speakers: Andrew Pitts (Cambridge, United Kingdom) Gordon Plotkin (Edinburgh, United Kingdom) (To be confirmed)=20 Program Committee: Luca Aceto (BRICS, Aalborg, Denmark, co-chair) Wan Fokkink (CWI, The Netherlands, co-chair) Rob van Glabbeek (NICTA, Sydney, Australia) Ralf Laemmel (CWI, The Netherlands) Peter Mosses (BRICS, Aarhus, Denmark) David Sands (Chalmers, Sweden) Alex Simpson (Edinburgh, United Kingdom) Simone Tini (Insubria, Italy) Irek Ulidowski (Leicester, United Kingdom, co-chair) Erik de Vink (Eindhoven, The Netherlands) Organizing Committee: Luca Aceto, email: luca AT cs.auc.dk, (BRICS, Aalborg, Denmark) Wan Fokkink, email: wan AT cwi.nl,=20 (CWI, The Netherlands) Irek Ulidowski, email iu3 AT mcs.le.ac.uk (Leicester, United Kingdom) --------------------------------------------------------- Irek Ulidowski, Department of Computer Science, University of Leicester, University Road, LEICESTER, LE1 7RH, England. Tel: +44 (0) 116 252 3801 Fax: +44 (0) 116 252 3604 http://www.mcs.le.ac.uk/~iulidowski From rrosebru@mta.ca Tue Feb 10 08:59:35 2004 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 10 Feb 2004 08:59:35 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1AqXR2-0006zz-00 for categories-list@mta.ca; Tue, 10 Feb 2004 08:56:16 -0400 To:categories@mta.ca From:alberto@sip.ucm.es Subject: categories: WRLA 2004 - Call for participation Message-Id: Date: Mon, 09 Feb 2004 18:35:02 +0100 Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 4 [[ -- Apologies in advance for multiple copies of this message -- ]] +----------------------------------------------------------+ | | | 5th International Workshop on | | Rewriting Logic and its Applications | | | | W R L A 2004 | | | | Barcelona, Spain, March 27-28, 2004 | | | | http://www.fdi.ucm.es/wrla2004 | +----------------------------------------------------------+ The workshop will be held in conjunction with ETAPS 2004 7th European Joint Conferences on Theory and Practice of Software March 27 - April 4, 2004 http://www.lsi.upc.es/etaps04 IMPORTANT !!! DEADLINE FOR EARLY REGISTRATION: *** February, 15 *** Detailed registration information together with the ETAPS online registration form is available at http://www.lsi.upc.es/etaps04/Registration/registration-frame.html It is possible to register for the workshop without registering for the main conference. PRELIMINARY PROGRAM The WRLA 2004 Preliminary Program is available at http://www.fdi.ucm.es/wrla2004/preSchedule.pdf It consists of 2 invited talks, 17 accepted papers, and 4 system demos (ASF+SDF, CafeOBJ, ELAN, and Maude). The two invited speakers are: Gilles Dowek Ecole Polytechnique & INRIA, Palaiseau Mario Rodriguez-Artalejo Universidad Complutense de Madrid ORGANIZING COMMITTEE Narciso Marti-Oliet, Manuel Clavel, and Alberto Verdejo Departamento de Sistemas Informaticos y Programacion Universidad Complutense de Madrid, Spain CONTACT INFORMATION For more information, please contact the organizers wrla2004@sip.ucm.es From rrosebru@mta.ca Tue Feb 10 08:59:36 2004 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 10 Feb 2004 08:59:36 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1AqXRq-00075D-00 for categories-list@mta.ca; Tue, 10 Feb 2004 08:57:06 -0400 Message-ID: <20040210045212.39411.qmail@web12208.mail.yahoo.com> Date: Mon, 9 Feb 2004 20:52:12 -0800 (PST) From: Galchin Vasili Subject: categories: typeful logic programming languages and categorical semantics/logic To: cat group MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 5 Hello, can somebody point to the application/research of categorical semantics/logic to typeful logic programming languages? Thank you, Bill Halchin From rrosebru@mta.ca Wed Feb 11 21:05:30 2004 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 11 Feb 2004 21:05:30 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1Ar5Fu-0003X5-00 for categories-list@mta.ca; Wed, 11 Feb 2004 21:03:02 -0400 Date: Tue, 10 Feb 2004 14:35:28 -0500 (EST) From: Jim Lipton To: cat group Subject: categories: Re: typeful logic programming languages and categorical semantics/logic In-Reply-To: <20040210045212.39411.qmail@web12208.mail.yahoo.com> Message-ID: References: <20040210045212.39411.qmail@web12208.mail.yahoo.com> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-ECS-MailScanner: Found to be clean Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 6 Papers I know of in Categorical Semantics of Logic Programming (and related topics such as unification): ================================================================= -- Rydeheard, Burstall: A Categorical Unification Algorithm, 1986, LNCS 240, 1986. (This work also appeard in Rydeheard and Burstall's book: "Computational Category Theory", Prentice-Hall, 1988) -- Goguen: "What is Unification? A categorical View of Substitution, Equations and Solution" CSLI-88 (Report) , 1988 -- Martini, Asperti: Projections instead of Variables, a Category-Theoretic Interpretation of Logic Programs, Proc 6th ICLP, MIT Press, 1989 -- Corradini, Asperti: A categorical Model for Logic Programs: Indexed Monoidal Categories, 1992 -- Corradini, Montanari: An algebraic Semantics for Structured Transition Systems and its applications to logic programs, TCS 1992 -- Finkelstein, Freyd, Lipton: Logic Programming in Tau Categories, CSL 94, 1995 (LNCS 933) -- Power, Kinoshita: A New Foundation for Logic Programming, ELP 96, 1996 (LNCS #?) Springer. -- McGrail: "Monads and Control in Logic Programming", Ph. D. Dissertation, Wesleyan University, 1997. -- Lipton, McGrail: Encapsulating data in Logic Programming via Categorical Constraints, in Principles of Declarative Programming, LNCS 1490, 1998. -- Amato: Sequent Calculus and Indexed Categories as Foundations for Logic Programming, P. D. Thesis, Univ. of Pisa, 2000 --Amato, Lipton: Indexed Categories and bottom-up semantics of Logic Programming, Proceedings LPAR 01, Lecture Notes in Artifical Intelligence 2250 -- Finkelstein, Freyd Lipton: A New Framework for Declarative Programming, TCS 300, 2003. The bibliography in the last paper cited contains more detailed references. There is a dissertation by Diaconescu, 1994, Oxford, on an Institutions-and-categories-based approach to logic programming. I regret not having the title and specifics with me at present. Apologies for incomplete information, I am away from my files at present. If anyone knows of publications that should be added to the list I would appreciate hearing of them. Regards, --Jim Lipton ======================================================== On Mon, 9 Feb 2004, Galchin Vasili wrote: > Hello, > > can somebody point to the application/research of > categorical semantics/logic to typeful logic > programming languages? > > Thank you, Bill Halchin > > ________________________________________________________________________ Jim Lipton |jlipton@wesleyan.edu |jlipton@fi.upm.es |jlipton.web.wesleyan.edu Math & Computer Science, Wesleyan University, Middletown CT 06459 Ramon y Cajal Visiting Researcher: Facultad de Informatica Universidad Politecnica de Madrid, 28660-Boadilla del Monte, MADRID SPAIN ==================================================================== From rrosebru@mta.ca Sun Feb 15 17:18:26 2004 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 15 Feb 2004 17:18:26 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1AsTax-0002G7-00 for categories-list@mta.ca; Sun, 15 Feb 2004 17:14:31 -0400 Mime-Version: 1.0 (Apple Message framework v609) Content-Transfer-Encoding: quoted-printable Message-Id: <8120F557-5D7D-11D8-BF81-F243200CF146@inria.fr> Content-Type: text/plain; charset=ISO-8859-1; format=flowed To: categories@mta.ca From: Jean-Jacques Levy Subject: categories: IFIP TCS 2004 Date: Thu, 12 Feb 2004 18:04:22 +0100 X-Mailer: Apple Mail (2.609) X-Miltered: at concorde by Joe's j-chkmail ("http://j-chkmail.ensmp.fr")! Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 7 Dear colleague, please notice the deadline for paper submissions of IFIP TCS 2004 has been redefined. Best regards, -JJ- ---------------------------------------------------------------- 3RD CALL FOR PAPERS -- TCS 2004 3rd IFIP International Conference on Theoretical Computer Science (Foundations of Global Computing) August 23-26, 2004, Toulouse, France URL: http://jeanjacqueslevy.net/TCS2004 TCS2004 will be held as part of the IFIP 2004 World Computer Congress. TCS2004 will be composed of two distinct, but interrelated tracks: Track 1 Algorithms, Complexity and Models of Computation, Track 2 Logic, Semantics, Specification and Verification. Submissions are limited to 14 A4 pages, in 11 point or larger font, LNCS style. The Proceedings will be published by Kluwer, the official publisher of IFIP. For detailed information, please visit the web site. IMPORTANT DATES Submission: March 31, 2004 <--------------- NEW DATE Notification: April 21, 2004 Given the very short delay between the dates for submission and for notification of acceptance, authors are asked to submit final versions of their articles. Authors are strongly encouraged to submit papers before the deadline for submission. The IFIP TCS2004 conference is sponsored by IFIP TC1 on Foundations of Computer Science in cooperation with SIGACT, EATCS and INRIA. The IFIP World Computer Congress has 60 grants of 500 euros each which can be awarded to students presenting a paper at one of the congress event. PROGRAM COMMITTEE Track 1: ------- Farid Ablayev, State University, Kazan Hagit Attiya, The Technion Sorin Istrail, Celera Genomics Stefano Leonardi, Universita di Roma Maurice Margenstern, Universit=E9 de Metz Ernt Mayr, Technische Universit=E4t M=FCnchen (chair) Satoru Miyano, University of Tokyo Jean-Eric Pin, LIAFA, CNRS Nicola Santoro, Carleton University Thomas Schwentick, Philipps-Universit=E4t Marburg Sandeep Sen, Indian Institute of Technology Delhi Subhash Suri, University of California Santa Barbara Osamu Watanabe, Tokyo Institute of Technology Track 2: ------- Roberto Amadio, Universit=E9 de Provence Luca Cardelli, Microsoft Research Cambridge Giuseppe Castagna, =C9cole Normale Sup=E9rieure Hubert Comon-Lundh, =C9cole Normale Sup=E9rieure de Cachan Adriana Compagnoni, Stevens Institute of Technology Drew Dean, SRI Marcelo Fiore, University of Cambridge Giorgio Ghelli, Universit=E0 di Pisa Martin Hofmann, Universit=E4t M=FCnchen Alan Jeffrey, DePaul University Bruce Kapron, University of Victoria Orna Kupferman, Hebrew University John Mitchell, Stanford University, (chair) George Necula, University of California Berkeley Catuscia Palamidessi, INRIA Futurs Martin Rinard, MIT Davide Sangiorgi, University of Bologna Vladimiro Sassone, University of Sussex Vitaly Shmatikov, SRI Martin Wirsing, Ludwig-Maximilians-Universit=E4t LIST OF AREAS Track 1 (Algorithms, Complexity and Models of Computation): Analysis and design of algorithms, Automata and formal languages, Cellular automata and systems, Combinatorial, graph and optimization algorithms, Computational and mathematical finance, Computational learning theory, Continuous algorithms and complexity, Computational complexity, Computational geometry, Cryptography, Distributed computing, Descriptional complexity, Evolutionary and genetic computing, Experimental algorithms, Mobile computing, Molecular computing and algorithmic aspects of bioinformatics, Network computing, Neural computing, Parallel and distributed algorithms, Probabilistic and randomized algorithms, Quantum computing, Structural information and communication complexity Track 2 (Logic, Semantics, Specification and Verification): Concurrency theory, Constructive and non-standard logics in computer science, Foundations of global computing, Foundations of mobile computing, Foundations of security, Foundations of system specification, Foundations of wide area programming, Logic and semantics for programs and languages, Logic, specification and verification of hybrid and real-time systems, Proofs and specifications in computer science, Term rewriting systems, Theoretical aspects of software concepts, Theoretical aspects of specification, and verification of hardware and software, Theoretical foundations of databases, Theoretical foundations of open systems, Theory of Internet languages and systems, Theory of parallel and distributed systems, Type and category theory in computer science. SPECIAL FOCUS The IFIP TCS2004 conference will have a special focus on Foundations of Global Computing. Original and significant contributions on the special focus and on foundational questions are sought from all areas of theoretical computer science. CONTACT Jean-Jacques Levy INRIA Rocquencourt 78153 Le Chesnay Cedex France email: jean-jacques.levy@inria.fr Tel: +33 1 39 63 56 89 From rrosebru@mta.ca Sun Feb 15 17:18:26 2004 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 15 Feb 2004 17:18:26 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1AsTcp-0002ME-00 for categories-list@mta.ca; Sun, 15 Feb 2004 17:16:27 -0400 Message-Id: <5.2.0.9.0.20040213221352.00b618f0@pop.cwru.edu> X-Sender: cxm7@pop.cwru.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.2.0.9 Date: Fri, 13 Feb 2004 22:24:12 -0500 To: categories@mta.ca From: Colin McLarty Subject: categories: Cohomology of an elementary topos Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 8 What is there to say about cohomology of an elementary topos with natural number object? That is, not assuming it is a Grothendieck topos. Is there any kind of general theory? thanks, Colin From rrosebru@mta.ca Sun Feb 15 17:18:27 2004 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 15 Feb 2004 17:18:27 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1AsTbS-0002HC-00 for categories-list@mta.ca; Sun, 15 Feb 2004 17:15:02 -0400 Date: Fri, 13 Feb 2004 09:30:25 -0500 Mime-Version: 1.0 (Apple Message framework v552) Content-Type: text/plain; charset=US-ASCII; format=flowed Subject: categories: Constructive Category Theory From: Steve Stevenson To: Categories List Content-Transfer-Encoding: 7bit Message-Id: <29AB61A4-5E31-11D8-8395-000A959EB774@cs.clemson.edu> X-Mailer: Apple Mail (2.552) X-CPSC-Clemson-MailScanner: Found to be clean Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 9 Is there a "tradition" in constructive development of category theory? If so, what is a good reference? best regards, steve -------- D. E. Stevenson, Department of Computer Science Director, Institute for Modeling and Simulation Applications Clemson University, Clemson, SC 29634-0974 864.656.5880 http://www.cs.clemson.edu/~steve From rrosebru@mta.ca Sun Feb 15 17:18:27 2004 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 15 Feb 2004 17:18:27 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1AsTZl-0002Cu-00 for categories-list@mta.ca; Sun, 15 Feb 2004 17:13:17 -0400 Date: Thu, 12 Feb 2004 10:27:07 +0000 (GMT) From: Dr Eugenia Cheng X-X-Sender: elgc2@yellow.csi.cam.ac.uk To: categories@mta.ca Subject: categories: 80th PSSL - second announcement Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: X-Keywords: X-UID: 10 PSSL 80 - Cambridge, UK Second announcement Dear All, This is the second announcement for the 80th Peripatetic Seminar on Sheaves and Logic, which will be held on the weekend of 3rd and 4th April in Cambridge, UK. The conference will be based at Newnham College, with talks taking place at the Centre for Mathematical Sciences. If you would like to attend the PSSL please send an e-mail to Eugenia Cheng, using the form attached below. COST The residential cost will be 102 pounds. This includes 2 nights bed, breakfast and lunch at Newnham College, and drinks reception upon arrival. In addition, for Saturday evening we have organised a large group booking with a special menu at a restaurant in the centre of Cambridge, serving Tapas and Paella. The cost for the three course menu is 15 pounds, making a total of 117 pounds. This is based on accommodation for Friday and Saturday nights. If you need to stay for more nights this can be arranged at a rate of 32 pounds per extra night. Please note that this is single student accommodation with shared facilities. If you do not require accommodation the cost for all of the above except bed and breakfast comes to 41 pounds. If you require any other combination of options, you can indicate it on the form. PAYMENT Payment will be by cash (British pounds) upon registration. Alternatively, if you prefer and are able, you are welcome to make an online payment. I have opened a bank account for this purpose and will supply details on request. This information can be found at the PSSL80 website: http://www.dpmms.cam.ac.uk/~elgc2/pssl80 Here you can also find information about travel to Cambridge and to Newnham College. A list of participants and schedule will be posted in due course. We look forward to seeing you in April. With best regards, The organisers, Eugenia Cheng (e.cheng@dpmms.cam.ac.uk) Martin Hyland (martin@dpmms.cam.ac.uk) Peter Johnstone (ptj@dpmms.cam.ac.uk) ----------------------------------------------------------------------- REGISTRATION FORM (please delete as appropriate) I, __________________________________________, would like to attend the 80th PSSL. I will not be giving a talk / I would like to give a talk entitled ________________________________________________________________________ My affiliation is _____________________________________ (University etc) I will not require accommodation in Newnham College / I would like accommodation in Newnham College for the nights of _____________ April I will not be attending the dinner on Saturday / I would like to attend the dinner on Saturday for 15 pounds. I need the following non-standard combination of the above options: ____________________________________________________________________ I have the following special dietary requirements: ____________________________________________________________________ I expect that the amount payable will be: Residential + dinner 117 pounds Residential without dinner 102 pounds Non-residential + dinner 41 pounds Non-residential without dinner 26 pounds + ____ extra nights @ 32 pounds TOTAL _________________ I will pay in cash upon registration / I would like to pay online ------------------------------------------------------------------- From rrosebru@mta.ca Sun Feb 15 17:18:27 2004 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 15 Feb 2004 17:18:27 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1AsTcH-0002KA-00 for categories-list@mta.ca; Sun, 15 Feb 2004 17:15:53 -0400 X-Organisation: Faculty of Science, University of Amsterdam, The Netherlands X-URL: http://www.science.uva.nl/ Date: Fri, 13 Feb 2004 17:02:07 +0100 From: Carlos Areces To: areces@loria.fr Subject: categories: ESSLLI 2004: Registration Open Message-ID: <20040213160207.GA24339@remote.science.uva.nl> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.3.25i X-Virus-Scanned: by amavisd-new Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 11 ======================================================================= ESSLLI 2004 ESSLLI 2004 ESSLLI 2004 ESSLLI 2004 ESSLLI 2004 ESSLLI 2004 Call for Registration ESSLLI 2004 Nancy, France 9-20 August, 2004 ======================================================================= Registration for ESSLLI 2004, the 16th European Summer School in Logic, Language and Information, is now open. To register go to: http://esslli2004.loria.fr click on the registration button, fill out the online form, print out the result, and fax (or surface-mail) it in. As well as registering, you can use the same form to reserve student accomodation and book lunch tickets (the lunch menu is available on the ESSLLI 2004 website). Please note: we can only guarantee 360 student accomodation places, and these will be distributed on a first-come-first-served basis. Also, please note that the deadline for early registration is May 1st 2004. We look forward to seeing you in Nancy this August! Carlos Areces, Patrick Blackburn (for the organising committee) Helene Kirchner (Director of Loria) ======================================================================= ESSLLI 2004 ESSLLI 2004 ESSLLI 2004 ESSLLI 2004 ESSLLI 2004 ESSLLI 2004 ======================================================================= From rrosebru@mta.ca Sun Feb 15 17:19:00 2004 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 15 Feb 2004 17:19:00 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1AsTeX-0002T0-00 for categories-list@mta.ca; Sun, 15 Feb 2004 17:18:13 -0400 Date: Sun, 15 Feb 2004 08:47:57 -0500 (EST) From: Gabor Lukacs X-X-Sender: To: Subject: categories: Compact subsets of k-spaces (without separation axioms) Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 12 Dear Topologists, Categorists and Categorical Topologists, It is well-known that for a *Hausdorff* topological space X, its k-ification kX and X have the same compact subspaces. It is also well-known that when we assume no separation axioms, X and kX have the same k-continuous maps (i.e. maps f:X -->Y such that ft is continuous for every "test-function" t: K --> X, where K is a compact Hausdorff space). I was wondering if anyone knows whether the first statement is true *without separation axioms*, i.e., whether for every topological space X, its k-ification kX and X have the same compact subspaces. I would very much appreciate any suggestion, reference or counterexample. Gabor Lukacs From rrosebru@mta.ca Mon Feb 16 22:01:25 2004 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 16 Feb 2004 22:01:25 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1AsuSG-00074p-00 for categories-list@mta.ca; Mon, 16 Feb 2004 21:55:20 -0400 From: Martin Escardo MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <16432.39871.67026.622299@gargle.gargle.HOWL> Date: Mon, 16 Feb 2004 10:30:23 +0000 To: Gabor Lukacs , Subject: categories: Re: Compact subsets of k-spaces (without separation axioms) In-Reply-To: References: X-Mailer: VM 7.07 under 21.4 (patch 8) "Honest Recruiter" XEmacs Lucid Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 13 Gabor Lukacs writes: > I was wondering if anyone knows whether the first statement is true > *without separation axioms*, i.e., whether for every topological space X, > its k-ification kX and X have the same compact subspaces. Sometime ago Alex Simpson advertised a paper "Comparing cartesian closed categories of (core) compactly generated spaces". http://www.cs.bham.ac.uk/~mhe/papers/ELS03.pdf where we have the same question (problem 9.2). Hence if anyone has an answer, please forward it to us as well - thanks. (I also take the opportunity to mention that we have updated the paper with some references given to us by some members of this list, in Section 3.) MHE From rrosebru@mta.ca Mon Feb 16 22:01:25 2004 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 16 Feb 2004 22:01:25 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1AsuTF-00077r-00 for categories-list@mta.ca; Mon, 16 Feb 2004 21:56:21 -0400 From: Bas Spitters Reply-To: spitters@cs.kun.nl To: Steve Stevenson Subject: categories: Re: Constructive Category Theory Date: Mon, 16 Feb 2004 16:53:55 +0100 User-Agent: KMail/1.6 References: <29AB61A4-5E31-11D8-8395-000A959EB774@cs.clemson.edu> In-Reply-To: <29AB61A4-5E31-11D8-8395-000A959EB774@cs.clemson.edu> MIME-Version: 1.0 Content-Disposition: inline Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit Message-Id: <200402161653.55691.spitters@cs.kun.nl> Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 14 On Friday 13 February 2004 15:30, Steve Stevenson wrote: > Is there a "tradition" in constructive development of category theory? > If so, what is a good reference? I am not aware of a "tradition", but I know two references. In the book A course in constructive algebra (Mines, Richman, Ruitenburg) there is a very short outline of category theory. There is a machine checked formalization inside constructive type theory by Huet and Saibi. http://citeseer.nj.nec.com/huet98constructive.html The impression I got from both approaches is that basic constructive category theory is fairly similar to its its classical counter part, which might explain the apparent lack of tradition. I hope this is of any use. Bas ------------------------------------------------------- Department of Computer Science, University of Nijmegen. P.O.box 9010, NL-6500 GL Nijmegen, The Netherlands. e-mail: spitters@cs.kun.nl Phone: +31-24-3652631. Fax: +31-24-3652525 Room: A5024 http://www.cs.kun.nl/~spitters/ From rrosebru@mta.ca Tue Feb 17 13:49:54 2004 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 17 Feb 2004 13:49:54 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1At9Kd-00058e-00 for categories-list@mta.ca; Tue, 17 Feb 2004 13:48:27 -0400 Date: Tue, 17 Feb 2004 16:10:42 +0000 (GMT) From: Dr Eugenia Cheng To: categories@mta.ca Subject: categories: 80th PSSL: addendum Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 15 80th PSSL: addendum Dear All, Further to the 2nd announcement of the 80th PSSL in Cambridge, I would like to add that if you would particularly like en suite accommodation, I can arrange this for you on request. This would be at St Catharine's College, and costs 21 pounds extra per night. They will hold the rooms until February 26th after which it is subject to availability, so early booking is recommended. Regards, Eugenia Cheng From rrosebru@mta.ca Sat Feb 21 09:42:23 2004 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 21 Feb 2004 09:42:23 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1AuXLV-0005Hz-00 for categories-list@mta.ca; Sat, 21 Feb 2004 09:39:05 -0400 X-Authentication-Warning: pascal.math.ubc.ca: johnm owned process doing -bs Date: Thu, 19 Feb 2004 15:58:50 -0800 (PST) From: John MacDonald To: categories@mta.ca Subject: categories: International Category Theory Conference(CT04) Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: X-Keywords: X-UID: 16 THIRD ANNOUNCEMENT INTERNATIONAL CATEGORY THEORY CONFERENCE (CT04) July 18-24, 2004 University of British Columbia Vancouver, Canada This conference will be held on the University of British Columbia campus. It will begin with a reception at 6pm on Sunday July 18, 2004, and will end at 1pm on Saturday July 24, 2004. All those interested in category theory and its applications are welcome. The CT04 website is http://www.pims.math.ca/science/2004/CT04 You will find all information about Registration and Accommodation there, as well as a link to Visitor Information. Currently we are trying to make a preliminary estimate of the number of people who will be attending the conference for the purpose of booking lecture rooms and in order to provide an estimate to catering services. If you will or may attend and have not already indicated this to me by email, then please send a note to johnm@math.ubc.ca with the words "will attend" or "may attend", as appropriate. Some important deadlines are as follows: Graduate student requests for support of accommodation costs - March 15, 2004. A maximum of 5 such requests will be granted. Note that PIMS has no other support available to anyone for accommodation, registration or travel. Abstracts - May 31, 2004. Please use the form from the website. Registration Deposit or Early Registration payment - May 31, 2004 Accommodation - June 18, 2004. After this date the block of rooms reserved for CT04 will be released to the general public, although reservations can still be made if space is available. Early booking is recommended, especially for those with accompanying persons. Extra spaces for the excursion or banquet for accompanying persons - June 30, 2004. The excursion and banquet for delegates is included in the conference fee. CT04 Advisory Committee: Jiri Adamek, Braunschweig Michael Barr, Montreal Eduardo Dubuc, Buenos Aires Marco Grandis, Genoa George Janelidze, Capetown Michael Johnson, Sydney P. T. Johnstone, Cambridge F. W. Lawvere, Buffalo S. Niefield, Schenectady T. Porter, Bangor Jiri Rosicky, Brno Phil Scott, Ottawa Robert Seely, Montreal Art Stone, Vancouver Ross Street, Sydney Enrico Vitale, Louvain Walter Tholen, Toronto R. J. Wood, Halifax This conference is being organized with the help of the Pacific Institute of Mathematics(PIMS}. Please let me know of any errors, omissions or suggestions for changes that you may have. John MacDonald, Vancouver From rrosebru@mta.ca Sat Feb 21 09:42:23 2004 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 21 Feb 2004 09:42:23 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1AuXK6-0005FD-00 for categories-list@mta.ca; Sat, 21 Feb 2004 09:37:38 -0400 Date: Thu, 19 Feb 2004 11:37:29 -0500 (EST) From: James Stasheff X-X-Sender: stasheff@login5.isis.unc.edu To: categories@mta.ca Subject: categories: graphics package Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 17 Anyone have a recommendation for a software package that makes it easy to draw the equivalent of flow chart? with boxes, triangles, circles as junctions?? .oooO Jim Stasheff jds@math.unc.edu (UNC) since retiring from UNC hanging out at U Penn jds@math.upenn.edu \ ( 146 Woodland Dr FAX:(215)-573-4063 \*) Lansdale PA 19446-1437 http://www.math.unc.edu/Faculty/jds From rrosebru@mta.ca Sun Feb 22 16:06:53 2004 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 22 Feb 2004 16:06:53 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1Auzka-0001jl-00 for categories-list@mta.ca; Sun, 22 Feb 2004 15:58:52 -0400 From: Topos8@aol.com Message-ID: Date: Sat, 21 Feb 2004 08:46:40 EST Subject: categories: Equivalences and psuedo-equivalences (two items) To: categories@mta.ca MIME-Version: 1.0 Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 18 The answer to this question must be in the literature somewhere but I haven't been able to track it down or figure it out for myself. Let A and B be bicategories. By a functor from A to B I shall mean a morphism of underlying reflexive globular sets that preserves all operations and identities on the nose and satisfies the standard coherence conditions. A psuedo-functor is a morphism that preserves operations and identities only up to 1 cells that are equivalences in B ( a 1-cell f is an equivalence if there is a 1-cell g such that fg and gf are both defined and isomorphic to the respective identitity 1-cells). (These 1-cells must of course satisfy additional, standard coherence conditions.) An equivalence from A to B is a functor that is essentially surjective on 0-cells (every 0-cell of B is equivalent in B to a 0-cell in the image of F) and which induces an equivalence of 1-categories between A( x,y ) and B ( Fx, Fy ) for all 0-cells x, y in A. A psuedo-equivalence from A to B is a psuedo-functor that has these same properties. Question 1 : If F is a psuedo-equivalence from A to B does there exist an equivalence G from A to B? (references/counterexamples?) Question 2: Same as question 1 but with A and B strict 2-categories. Qestion 3: If the answer to question 1 is yes, then can G be chosen to be equivalent to F in the bicategory whose 0-cells are psuedo-functors from A to B? I shall be very grateful for any guidance the list can provide on these questions. Carl Futia ------------------------------------------------------ SECOND ITEM: Subject: Correction to my last query I have to apologize for a silly error in my last request for help. The problem lies with the definition of psuedo functor. I should have said that a psuedo functor preserves operations up to a 2-cell isomorphism, not a 1-cell equivalence. Sorry! Carl Futia From rrosebru@mta.ca Sun Feb 22 16:06:53 2004 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 22 Feb 2004 16:06:53 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1Auzl8-0001pW-00 for categories-list@mta.ca; Sun, 22 Feb 2004 15:59:26 -0400 Message-Id: <5.2.0.9.0.20040221100321.00b63dc8@pop.cwru.edu> X-Sender: cxm7@pop.cwru.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.2.0.9 Date: Sat, 21 Feb 2004 10:20:21 -0500 To: categories@mta.ca From: Colin McLarty Subject: categories: Re: graphics package Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 19 Jim Stasheff wrote: >Anyone have a recommendation for a software package that >makes it easy to draw the equivalent of flow chart? >with boxes, triangles, circles as junctions?? I like Xy-Pic very much (with LaTeX). It can do that. You would probably use the "graph" feature or see the worked example on p. 10 of the user's guide. The downside is that the user's guide and the reference manual are very spotty. I find the only way to learn to use Xy-pic, and then to learn to use any given feature, is to copy the examples out of the relevant section of the user's guide or the reference manual and fool around with them until you see which parts do what. The Xy-pic chapter of the LaTeX GRAPHICS COMPANION was *extremely* helpful to me. Colin From rrosebru@mta.ca Sun Feb 22 16:06:53 2004 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 22 Feb 2004 16:06:53 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1AuznX-00027D-00 for categories-list@mta.ca; Sun, 22 Feb 2004 16:01:55 -0400 Message-ID: <039f01c3f885$d8a2e9c0$62bacdd1@farmer> Reply-To: "Michael Mislove" From: "Michael Mislove" Subject: categories: Re: graphics package Date: Sat, 21 Feb 2004 08:20:23 -0600 Organization: Tulane University MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 6.00.2800.1158 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2800.1165 Sender: cat-dist@mta.ca Precedence: bulk Bcc: Status: O X-Status: X-Keywords: X-UID: 20 Try gastex - it's available from Paul Gastin's home page: http://www.liafa.jussieu.fr/~gastin/gastex/gastex.html Best regards, Mike Mislove ----- Original Message ----- From: "James Stasheff" To: Sent: Thursday, February 19, 2004 10:37 AM Subject: categories: graphics package | Anyone have a recommendation for a software package that makes it easy | to draw the equivalent of flow chart? | with boxes, triangles, circles as junctions?? | | | .oooO Jim Stasheff jds@math.unc.edu | (UNC) since retiring from UNC hanging out at U Penn jds@math.upenn.edu | \ ( 146 Woodland Dr FAX:(215)-573-4063 | \*) Lansdale PA 19446-1437 | | http://www.math.unc.edu/Faculty/jds | | | From rrosebru@mta.ca Sun Feb 22 16:08:44 2004 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 22 Feb 2004 16:08:44 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1Auzok-0002BT-00 for categories-list@mta.ca; Sun, 22 Feb 2004 16:03:10 -0400 Message-ID: <40378E0A.27BD85D7@math.upenn.edu> Date: Sat, 21 Feb 2004 11:57:46 -0500 From: jim stasheff Organization: University of Pennsylvania X-Mailer: Mozilla 4.77 [en]C-CCK-MCD NECCK (Windows NT 5.0; U) X-Accept-Language: en MIME-Version: 1.0 To: categories@mta.ca Subject: categories: graphics Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Scanned-By: MIMEDefang 2.36 Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 21 Thanks to all the suggestions for `flow chart' graphics. I had first asked the alg top list and had no responses whereas here I've received 4 or 5 suggestions gastex, dia (on Linux) xy-pic xfig "The LaTeX Graphics Companion", Goossens, Rahtz, and Mittelbach use the xy-pic and PSTricks packages to draw flowcharts. if anyone has used more than one and cares to comment, I would appreciate that as for example Subject: Re: categories: graphics package Date: Sat, 21 Feb 2004 15:24:28 +0000 (GMT) From: Michael Abbott To: James Stasheff References: 1 > Anyone have a recommendation for a software package that makes it easy > to draw the equivalent of flow chart? > with boxes, triangles, circles as junctions?? This can be done, with the dint of much pain, with XyPic directly in LaTeX. The layout tends to be perfect, but learning how to use the tool for anything beyond the simplest diagrams is remarkably painful. On the other hand, xfig produces very nice results with manual layout, and is really quite easy to use (though figuring out how to drop the diagrams into your LaTeX document has its surprises). jim From rrosebru@mta.ca Sun Feb 22 16:11:50 2004 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 22 Feb 2004 16:11:50 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1Auzrl-0002P3-00 for categories-list@mta.ca; Sun, 22 Feb 2004 16:06:17 -0400 Message-ID: <4037BB8B.CA50E6C1@math.upenn.edu> Date: Sat, 21 Feb 2004 15:11:55 -0500 From: jim stasheff Organization: University of Pennsylvania X-Mailer: Mozilla 4.77 [en]C-CCK-MCD NECCK (Windows NT 5.0; U) X-Accept-Language: en MIME-Version: 1.0 To: "categories@mta.ca" Subject: categories: [Fwd: Your father's thesis] Content-Type: multipart/mixed; boundary="------------D96ADF0F57F61BE1FD4431E5" X-Scanned-By: MIMEDefang 2.36 Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: X-Keywords: X-UID: 22 With thanks to all the others who made this happen jim -------------- From: Pearbeck@aol.com Date: Sat, 21 Feb 2004 14:22:29 EST Subject: Re: Your father's thesis To: jds@math.upenn.edu Hi Jim-- The bound thesis did reach him, and he was very happy to have it. It came to my house, actually, and we got it to him. I probably forgot to write you and tell you so -- sorry about that. It's really nice for him to still reap rewards from that part of his life, as he seems to have aged prematurely. Thanks so much for making it happen. --Nadine In a message dated 2/21/04 7:09:31 AM, jds@math.upenn.edu writes: > Dear Nadine, > Pardon my faulty memory if you have alreadey answered this: > > Did the copy of the reissue of Jon's thesis ever reach him? > what was his reaction? > > jim From rrosebru@mta.ca Sun Feb 22 17:38:13 2004 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 22 Feb 2004 17:38:13 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1Av1Ck-0007ad-00 for categories-list@mta.ca; Sun, 22 Feb 2004 17:32:02 -0400 X-Mailer: exmh version 2.6.3 04/04/2003 with nmh-1.0.4 To: categories@mta.ca Subject: categories: Re: graphics package Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Date: Sat, 21 Feb 2004 08:18:30 -0800 From: Vaughan Pratt Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: RO X-Status: X-Keywords: X-UID: 23 >Anyone have a recommendation for a software package that makes it easy >to draw the equivalent of flow chart? >with boxes, triangles, circles as junctions?? For this and many similar applications (Hasse diagrams, one-off characters like inverted ampersand, etc.), Latex's picture environment is a remarkably expressive language, permitting a self-contained library of macros for drawing circuits to be implemented in 20 noncomment lines. See http://boole.stanford.edu/pub/sumprod.pdf http://boole.stanford.edu/pub/TEX/sumprod.tex for the circuit realization of sum and tensor product in chu(Set,2), which appeared in http://boole.stanford.edu/pub/gates.pdf (FOCS'93 Palo Alto) and http://boole.stanford.edu/pub/bud.pdf (TEMPUS'94 Budapest). Vaughan Pratt From rrosebru@mta.ca Mon Feb 23 16:39:01 2004 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 23 Feb 2004 16:39:01 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1AvMnc-00017E-00 for categories-list@mta.ca; Mon, 23 Feb 2004 16:35:32 -0400 Message-ID: <4037BB8B.CA50E6C1@math.upenn.edu> Date: Sat, 21 Feb 2004 15:11:55 -0500 From: jim stasheff Organization: University of Pennsylvania MIME-Version: 1.0 To: "categories@mta.ca" Subject: categories: [Fwd: Your father's thesis] Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 24 [from moderator: this message arrived blank when first sent due to an editing error, so is being repeated.] With thanks to all the others who made this happen jim -------------- From: Pearbeck@aol.com Date: Sat, 21 Feb 2004 14:22:29 EST Subject: Re: Your father's thesis To: jds@math.upenn.edu Hi Jim-- The bound thesis did reach him, and he was very happy to have it. It came to my house, actually, and we got it to him. I probably forgot to write you and tell you so -- sorry about that. It's really nice for him to still reap rewards from that part of his life, as he seems to have aged prematurely. Thanks so much for making it happen. --Nadine In a message dated 2/21/04 7:09:31 AM, jds@math.upenn.edu writes: > Dear Nadine, > Pardon my faulty memory if you have alreadey answered this: > > Did the copy of the reissue of Jon's thesis ever reach him? > what was his reaction? > > jim From rrosebru@mta.ca Tue Feb 24 18:18:46 2004 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 24 Feb 2004 18:18:46 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1AvkqL-0000D8-00 for categories-list@mta.ca; Tue, 24 Feb 2004 18:15:57 -0400 X-Authentication-Warning: gradient.cis.upenn.edu: geoffw owned process doing -bs Date: Sun, 22 Feb 2004 15:36:10 -0500 (EST) From: "Geoffrey A. Washburn" To: categories@mta.ca Subject: categories: (co)limit in the category of types Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 25 A few weeks ago I posted a query to the TYPES mailing list about the a nature of a particular categorical construction. In particular, I was interested in the colimit of an individual morphism in the category where objects are types, and arrows terms that are functions between them. Specifically consider the diagram length int list ----------> nat Where I abbreviate the type of integers as int and the type of natural numbers as nat. (All diagrams are in ASCII so you will need to use a proportional font; maybe someday I will be able to use inline SVG diagrams). I figured that it might be instructive to understand the nature of the colimit of this diagram by first considering the limit of this diagram (with its associated UMP) X / | \ f / | \x:X. \ g / | \ / | \ / | \ / fst v snd \ v <----- Sigma l:int list.S(length(l)) -----> v int list nat ------------------------------------------> length Where snd o \x:X. = g and length o f = g. This limit Sigma l:int list.S(length(l)) is a dependent sum, essentially a tuple, that constrains its second component to be the natural number that is exactly the length of the list that is its first component. I indicate this by using the singleton type constructor S. S(length(l)) is the type of those terms that are equivalent to length(l). However, it was quickly pointed out to me on the TYPES list that there is a "simpler" limit that is isomorphic to Sigma l:int list.S(length(l)) X / | \ / | \ f / | f \ g / | \ / | \ / id v length \ v <------ int list --------> v int list nat -------------------------> length Where it must be the case that, length o f = g. What is interesting here is that while these two limits are isomorphic, operationally they are very different. We can think of the limit an abstract data-type with two operations, one that will give us a list, or the length of the list it encapsulates. In SML syntax sig type limit val fst : limit -> int list val snd : limit -> nat end When we use int list as the limit, the abstract datatype is lazy, in the sense that it does not compute the length until it is requested. My more "complex" limit on the other-hand is eager, and computes the length when constructed. This actually provides even more intuition as to what is going on with the colimit. First the simpler colimit length ------------------> int list nat \ --------> nat <---- / \ length | id / \ | / \ | / f \ | g / g \ | / \ | / v v v X Where it must be the case that g o length = f. Returning to our abstract datatype analogy, sig type colimit val inl : int list -> colimit val inr : nat -> colimit end Here, our abstract datatype is encapsulates the length of a list, which can either be given directly, or by supplying a list. This simpler colimit can thought of as being eager, because it calculates the length of the list immediately when injecting into the "abstract type". Therefore, if our intuitions are correct, the a dependent colimit should compute the length lazily... length --------------------------------------------> int list nat \ -----> CoSigma l:int list.S(length(l)) <----- / \ inl | inr / \ | / \ | / f \ | [f,g] / g \ | / \ | / v v v X Where [f,g] o inl = f and g o length = f. And indeed it is. Instead of calculating the length immediately, it requires that the function deconstructing the "abstract type" compute length if given a list instead of a length; this is forced by the requirement that f must be the same as g o length. My remaining unanswered questions: Are there any other interesting isomorphic (co)limits than the two discussed above? It is possible to add enough structure to the category so that these (co)limits can be distinguished? Naively we might have expected the dual of a dependent sum type to be a dependent product (as existential types are dual to universal types). Is there a construction that corresponds to the dual of a dependent product? Is there a relationship between the CoSigma type and other known mathematical structures? What are the typing rules for CoSigma? Sigma l:int list.S(length(l)) should be isomorphic to the more common dependent type Sigma n:nat.int list(n). How does CoSigma l:int list.S(length(l)) relate to the type CoSigma n:nat.int list(n)? From rrosebru@mta.ca Tue Feb 24 18:18:46 2004 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 24 Feb 2004 18:18:46 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1Avkqw-0000FR-00 for categories-list@mta.ca; Tue, 24 Feb 2004 18:16:34 -0400 Date: Sun, 22 Feb 2004 20:20:40 -0600 Subject: categories: Re: graphics Content-Type: text/plain; charset=US-ASCII; format=flowed Mime-Version: 1.0 (Apple Message framework v543) From: David Yetter To: categories@mta.ca Content-Transfer-Encoding: 7bit In-Reply-To: <40378E0A.27BD85D7@math.upenn.edu> Message-Id: X-Mailer: Apple Mail (2.543) Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 26 My favorite method is to draw figures in xfig, then export the result as LaTeX picture code and edit the text to take advantage of LaTeX's text processing capabilities, fonts and special symbols. It would be quite suitable for flow chart graphics. D. Yetter On Saturday, February 21, 2004, at 10:57 AM, jim stasheff wrote: > Thanks to all the suggestions for `flow chart' graphics. > I had first asked the alg top list and had no responses > whereas here I've received 4 or 5 suggestions > > > gastex, > dia (on Linux) > xy-pic > xfig > "The LaTeX Graphics Companion", > Goossens, Rahtz, and Mittelbach > use the xy-pic and PSTricks packages > to draw flowcharts. > > if anyone has used more than one and cares to comment, > I would appreciate that > > as for example > Subject: > Re: categories: graphics package > Date: > Sat, 21 Feb 2004 15:24:28 +0000 (GMT) > From: > Michael Abbott > To: > James Stasheff > References: > 1 > > > > >> Anyone have a recommendation for a software package that makes it easy >> to draw the equivalent of flow chart? >> with boxes, triangles, circles as junctions?? > > This can be done, with the dint of much pain, with XyPic directly in > LaTeX. The layout tends to be perfect, but learning how to use the > tool > for anything beyond the simplest diagrams is remarkably painful. > > On the other hand, xfig produces very nice results with manual layout, > and > is really quite easy to use (though figuring out how to drop the > diagrams > into your LaTeX document has its surprises). > > jim > From rrosebru@mta.ca Tue Feb 24 18:18:46 2004 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 24 Feb 2004 18:18:46 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1Avkrf-0000Jk-00 for categories-list@mta.ca; Tue, 24 Feb 2004 18:17:19 -0400 Date: Mon, 23 Feb 2004 12:35:01 GMT Message-Id: <200402231235.i1NCZ1TF021321@mercury.comlab.ox.ac.uk> X-Authentication-Warning: mercury.comlab: jg set sender to jg@mercury.comlab using -f From: Jeremy Gibbons To: categories@mta.ca Subject: categories: Re: Constructive Category Theory References: <29AB61A4-5E31-11D8-8395-000A959EB774@cs.clemson.edu> Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 27 > Is there a "tradition" in constructive development of category theory? > If so, what is a good reference? Not sure if this is what you're looking for, but there's a very nice paper, "Category theory as coherently constructive lattice theory", by Roland Backhouse et al: http://www.cs.nott.ac.uk/~rcb/papers/abstract.html#CatTheory Jeremy -- Jeremy.Gibbons@comlab.ox.ac.uk Oxford University Computing Laboratory, TEL: +44 1865 283508 Wolfson Building, Parks Road, FAX: +44 1865 273839 Oxford OX1 3QD, UK. URL: http://www.comlab.ox.ac.uk/oucl/people/jeremy.gibbons.html From rrosebru@mta.ca Tue Feb 24 18:18:46 2004 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 24 Feb 2004 18:18:46 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1Avkso-0000Lj-00 for categories-list@mta.ca; Tue, 24 Feb 2004 18:18:30 -0400 From: Topos8@aol.com Message-ID: <159.2e745aaa.2d6b7dcf@aol.com> Date: Mon, 23 Feb 2004 11:01:19 EST Subject: categories: Who invented n-categories? To: categories@mta.ca MIME-Version: 1.0 Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 28 Can anyone offer a reference to the first published work which defined a notion of strict n-category equivalent to that used today? I know that Ehresmann invented n-tuple ( or n-fold ) categories which contain strict n-categories as special cases. If this is the first implicit defintion of strict n-category does anyone know who was the first to isolate our current notion of strict n-category as a particularly interesting special case of an n-tuple category? Carl Futia From rrosebru@mta.ca Tue Feb 24 18:18:46 2004 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 24 Feb 2004 18:18:46 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1AvkpZ-0000BP-00 for categories-list@mta.ca; Tue, 24 Feb 2004 18:15:09 -0400 Message-Id: <200402222008.i1MK8xK29901@math-cl-n03.ucr.edu> Subject: categories: higher-dimensional algebra To: categories@mta.ca (categories) Date: Sun, 22 Feb 2004 12:08:59 -0800 (PST) From: "John Baez" X-Mailer: ELM [version 2.5 PL6] MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 29 Dear Categorists - I thought some of you might enjoy this article about Joyal's structure types, Fiore and Leinster's work on distributive categories, Leinster's new book on higher categories, and a bunch of other new papers on higher-dimensional algebra. Best, John Baez .......................................................................... Also available at http://math.ucr.edu/home/baez/week202.html February 21, 2004 This Week's Finds in Mathematical Physics - Week 202 John Baez This week I'll deviate from my plan of discussing number theory, and instead say a bit about something else that's been on my mind lately: structure types. But, you'll see my fascination with Galois theory lurking beneath the surface. Andre Joyal invented these in 1981 - he called them "especes de structure". Basically, a structure type is just any sort of structure we can put on finite sets: an ordering, a coloring, a partition, or whatever. In combinatorics people count such structures using "generating functions". A generating function is a power series where the coefficient of x^n keeps track of how many structures of the given kind you can put on an n-element set. By playing around with these functions, you can often figure out the coefficients and get explicit formulas - or at least asymptotic formulas - that count the structures in question. The reason this works is that operations on generating functions come from operations on structure types. For example, in "week190", I described how addition, multiplication and composition of generating functions correspond to different ways to get new structure types from old. Joyal's great contribution was to give structure types a rigorous definition, and use this to show that many calculations involving generating functions can be done directly with structure types. It turns out that just as generating functions form a *set* equipped with various operations, structure types form a *category* with a bunch of completely analogous operations. This means that instead of merely proving *equations* between generating functions, we can construct *isomorphisms* between their underlying structure types - which imply such equations, but are worth much more. It's like the difference between knowing two things are equal and knowing a specific reason WHY they're equal! Of course, this business of replacing equations by isomorphisms is called "categorification". In this lingo, structure types are categorified power series, just as finite sets are categorified natural numbers. A while back, James Dolan and I noticed that since you can use power series to describe states of the quantum harmonic oscillator, you can think of structure types as states of a categorified version of this physical system! This gives new insights into the combinatorial underpinnings of quantum physics. For example, the discrete spectrum of the harmonic oscillator Hamiltonian can be traced back to the discreteness of finite sets! The commutation relations between annihilation and creation operators boil down to a very simple fact: there's one more way to put a ball in a box and then take one out, than to take one out and then put one in. Even better, the whole theory of Feynman diagrams gets a simple combinatorial interpretation. But for this, one really needs to go beyond structure types and work with a generalization called "stuff types". I've been thinking about this business for a while now, so last fall I decided to start giving a year-long course on categorification and quantization. The idea is to explain bunches of quantum theory, quantum field theory and combinatorics all from this new point of view. It's fun! Derek Wise has been scanning in his notes, and a bunch of people have been putting their homework online. So, you can follow along if you want: 1) John Baez and Derek Wise, Categorification and Quantization. Fall 2003 notes: http://math.ucr.edu/home/baez/qg-fall2003/ Winter 2004 notes: http://math.ucr.edu/home/baez/qg-winter2004/ I'd like to give you a little taste of this subject now. But, instead of explaining it in detail, I'll just give some examples of how structure types yield some far-out generalizations of the concept of "cardinality". This stuff is a continuation of some themes developed in "week144", "week185", "week190", so I'll start with a review. Suppose F is a structure type. Let F_n be the *set* of ways we can put this structure on a n-element set, and let |F_n| be the *number* of ways to do it. In combinatorics, people take all these numbers |F_n| and pack them into a single power series. It's called the generating function of F, and it's defined like this: |F_n| |F|(x) = sum ----- x^n n! It may not converge, so in general it's just a "formal" power series - but for interesting structure types it often converges to an interesting function. What's good about generating functions is that simple operations on them correspond to simple operations on structure types. We can use this to count structures on finite sets. Let me remind you how it works for binary trees! There's a structure type T where a T-structure on a set is a way of making it into the leaves of a binary tree drawn in the plane. For example, here's one T-structure on the set {a,b,c,d}: b d a c \ \ / / \ \/ / \ / / \/ / \ / \/ Thanks to the choice of different orderings, the number of T-structures on an n-element set is n! times the number of binary trees with n leaves. Annoyingly, the latter number is traditionally called the (n-1)st Catalan number, C_{n-1}. So, we have: |T|(x) = sum C_{n-1} x^n where the sum starts at n = 1. There's a nice recursive definition of T: "To put a T-structure on a set, either note that it has one element, in which case there's just one T-structure on it, or chop it into two subsets and put a T-structure on each one." In other words, any binary tree is either a degenerate tree with just one leaf: X or a pair of binary trees stuck together at the root: ----- ----- | | | | | T | | T | | | | | ----- ----- \ / \ / \ / \/ We can write this symbolically as T = X + T^2 Here's why: X is a structure type called "being the one-element set", + means "exclusive or", and squaring a structure type means you chop your set in two parts and put that structure on each part. (I explained these rules more carefully in "week190".) I should emphasize that the equals sign here is really an *isomorphism* between structure types - I'm only using "equals" because the isomorphism key on my keyboard is stuck. But if we take the generating function of both sides we get an actual equation, and the notation is set up to make this really easy: |T| = x + |T|^2 In "week144" I showed how you can solve this using the quadratic equation: |T| = (1 - sqrt(1 - 4x))/2. and then do a Taylor expansion to get |T| = x + x^2 + 2x^3 + 5x^4 + 14x^5 + 42x^6 + ... Lo and behold! The coefficient of x^n is the number of binary trees with n leaves! There's also another approach where we work directly with the structure types themselves, instead of taking generating functions. This is harder because we can't subtract structure types, or divide them by 2, or take square roots of them - at least, not without stretching the rules of this game. All we can do is use the isomorphism T = X + T^2 and the basic rules of category theory. It's not as efficient, but it's illuminating. It's also incredibly simple: we just keep sticking in "X + T^2" wherever we see "T" on the right-hand side, over and over again. Like this: T = X + T^2 T = X + (X + T^2)^2 T = X + (X + (X + T^2)^2)^2 and so on. You might not think we're getting anywhere, but if you stop at the nth stage and expand out what we've got, you'll get the first n terms of the Taylor expansion we had before! At least, you will if you count "stages" and "terms" correctly. I won't actually do this, because it's better if you do it yourself. When you do, you'll see it captures the recursive process of building a binary tree from lots of smaller binary trees. Each time you see a "T" and replace it with an "X + T^2", you're really taking a little binary tree: ----- | | | T | | | ----- and replacing it with either a degenerate tree with just a single leaf: X or a pair of binary trees: ----- ----- | | | | | T | | T | | | | | ----- ----- \ / \ / \ / \/ So, each term in the final result actually corresponds to a specific tree! This is a good example of categorification: when we calculate the coefficient of x^n this way, we're not just getting the *number* of binary planar trees with n leaves - we're getting an actual explicit description of the *set* of such trees. Now, what happens if we take the generating function |T|(x) and evaluate it at x = 1? On the one hand, we get a divergent series: |T|(1) = 1 + 1 + 2 + 5 + 14 + 42 + ... This is the sum of all Catalan numbers - or in other words, the number of binary planar trees. On the other hand, we can use the formula |T| = (1 - sqrt(1 - 4x))/2 to get |T|(1) = (1 - sqrt(-3))/2 It may seem insane to conclude 1 + 1 + 2 + 5 + 14 + 42 + ... = (1 - sqrt(-3))/2 but Lawvere noticed that there's a kind of strange sense to it. The trick is to work not with generating function |T| but with the structure type T itself. Since |T|(1) is equal to the *number* of planar binary trees, T(1) should be naturally isomorphic to the *set* of planar binary trees. And it is - it's obvious, once you think about what it really means. The number of binary planar trees is not very interesting, but the set of them is. In particular, if we take the isomorphism T = X + T^2 and set X = 1, we get an isomorphism T(1) = 1 + T(1)^2 which says "a planar binary tree is either the tree with one leaf or a pair of planar binary trees." Starting from this, we can derive lots of other isomorphisms involving the set T(1), which turn out to be categorified versions of equations satisfied by the number |T|(1) = (1 - sqrt(-3))/2 For example, this number is a sixth root of unity. While there's no one-to-one correspondence between 6-tuples of trees and the 1 element set, which would categorify the formula |T|(1)^6 = 1 there *is* a very nice one-to-correspondence between 7-tuples of trees and trees, which categorifies the formula |T|(1)^7 = |T|(1) Of course the set of binary trees is countably infinite, and so is the set of 7-tuples of binary trees, so they can be placed in one-to-one correspondence - but that's boring. When I say "very nice", I mean something more interesting: starting with the isomorphism T = x + T^2 we get a one-to-one correspondence T(1) = 1 + T(1)^2 which says that any binary planar tree is either degenerate or a pair of binary planar trees... and using this we can *construct* a one-to-one correspondence T(1)^7 = T(1) The construction is remarkably complicated. Even if you do it as efficiently as possible, I think it takes 18 steps, like this: T(1)^7 = T(1)^6 + T(1)^8 = T(1)^5 + T(1)^7 + T(1)^8 . . . = 1 + T(1) + T(1)^2 + T(1)^4 = 1 + T(1) + T(1)^3 = 1 + T(1)^2 = T(1) I'll let you fill in the missing steps - it's actually quite fun if you like puzzles. If you get stuck, you can look up the answer in a couple of different places. While Lawvere was the first to figure this out, the first to write it up was Andreas Blass: 2) Andreas Blass, Seven trees in one, Jour. Pure Appl. Alg. 103 (1995), 1-21. Also available at http://www.math.lsa.umich.edu/~ablass/cat.html There's also a nice treatment based on more general results here: 3) Marcelo Fiore, Isomorphisms of generic recursive polynomial types, to appear in 31st Symposium on Principles of Programming Languages (POPL04). Also available at http://www.cl.cam.ac.uk/~mpf23/papers/Types/recisos.ps.gz In fact, Fiore and Leinster have a nice general theory that explains why the set T(1) acts so much like a sixth root of unity: 4) Marcelo Fiore and Tom Leinster, Objects of categories as complex numbers, available as math.CT/0212377. The idea is that when we have an object Z in a distributive category (a category with finite products and coproducts, the former distributing over the latter), and it's equipped with an isomorphism Z = P(Z) where P is a polynomial with natural number coefficients, we can associate to it a "cardinality" |Z|, namely any complex solution of the equation |Z| = P(|Z|) Which solution should we use? Well, for simplicity let's consider the case where P has degree at least 2 and the relevant Galois group acts transitively on the solutions of this equation, so "all roots are created equal". Then we can pick *any* solution as the cardinality |Z|. Any polynomial equation with natural number coefficients satisfied by one solution will be satisfied by *all* solutions, so it doesn't matter which one we choose. Now suppose the cardinality |Z| satisfies such an equation: Q(|Z|) = R(|Z|) where neither Q nor R is constant. Then the results of Fiore and Leinster say we can construct an isomorphism Q(Z) = R(Z) in our distributive category! In other words, a bunch of equations satisfied by the object's cardinality automatically come from isomorphisms involving the object itself. This explains why the set T(1) of binary trees acts like it has cardinality |T|(1) = (1 - sqrt(-3))/2 or equally well, |T|(1) = (1 + sqrt(-3))/2 (Since the relevant Galois group interchanges these two numbers, we can use either one.) More generally, the set T(n) consisting of binary trees with n-colored leaves acts a lot like the number |T|(n). This has gotten me interested in trying to find a nice example of a "Golden Object": an object G in some distributive category that's equipped with an isomorphism G^2 = G + 1 The Golden Object doesn't fit into Fiore and Leinster's formalism, since this isomorphism is not of the form G = P(G) where P has natural number coefficients. But, it still seems that such an object deserves to have a "cardinality" equal to the golden number: |G| = (1 + sqrt(5))/2 = 1.618033988749894848204586834365... James Propp came up with an interesting idea related to the Golden Object: consider what happens when we evaluate the generating function for binary trees at -1. On the one hand we get an alternating sum of Catalan numbers: |T|(-1) = -1 + 1 - 2 + 5 - 14 + 42 + ... On the other hand, we can use the formula |T| = (1 - sqrt(1 - 4x))/2 to get |T|(1) = (1 - sqrt(5))/2 which is -1 divided by the golden number. Of course, it's possible we should use the other sign of the square root, and get |T|(1) = (1 + sqrt(5))/2 which is just the golden number! Galois theory says these two roots are created equal. Either way, we get a bizarre and fascinating formula: - 1 + 1 - 2 + 5 - 14 + 42 + ... = (1 +- sqrt(5))/2 Can we fit this into some clear and rigorous framework, or is it just nuts? We'd like some generalization of cardinality for which "the set of binary trees with -1-colored leaves" has cardinality equal to the golden number. James Propp suggested one avenue. Following Schanuel's ideas on Euler characteristic as a generalization of cardinality, it makes sense to treat the real line as a "space of cardinality -1". This will sound crazy unless you go back and read "week147", so please do that! Anyway, using this idea it seems reasonable to consider the space of binary trees with leaves labelled by real numbers as a rigorous version of "the set of binary trees with -1-colored leaves". So, we just need to figure out what generalization of Euler characteristic gives this space an Euler characteristic equal to the golden number. It would be great if we could make this space into a Golden Object in some distributive category, but that may be asking too much. Whew! There's obviously a lot of work left to be done here. Here's something easier: a riddle. What's this sequence? un, dos, tres, quatre, cinc, seis, set, vuit, nou, deu,... The answer is at the end of this article. Now I'd like to mention some important papers on n-categories. You may think I'd lost interest in this topic, because I've been talking about other things. But it's not true! Most importantly, Tom Leinster has come out with a big book on n-categories and operads: 5) Tom Leinster, Higher Operads, Higher Categories, Cambridge U. Press, Cambridge, 2003. Also available as math.CT/0305049. As you'll note, he managed to talk the press into letting him keep his book freely available online! We should all do this. Nobody will ever make much cash writing esoteric scientific tomes - it takes so long, you could earn more per hour digging ditches. The only *financial* benefit of writing such a book is that people will read it, think you're smart, and want to hire you, promote you, or invite you to give talks in cool places. So, maximize your chances of having people read your books by keeping them free online! People will still buy the paper version if it's any good.... And indeed, Leinster's book has many virtues besides being free. He gracefully leads the reader from the very basics of category theory straight to the current battle front of weak n-categories, emphasizing throughout how operads automatically take care of the otherwise mind-numbing thicket of "coherence laws" that inevitably infest the subject. He doesn't take well-established notions like "monoidal category" and "bicategory" for granted - instead, he dives in, takes their definitions apart, and compares alternatives to see what makes these concepts tick. It's this sort of careful thinking that we desperately need if we're ever going to reach the dream of a clear and powerful theory of higher-dimensional algebra. He does a similar careful analysis of "operads" and "multicategories" before presenting a generalized theory of operads that's powerful enough to support various different approaches to weak n-categories. And then he describes and compares some of these different approaches! In short: if you want to learn more about operads and n-categories, this is *the* book to read. Leinster doesn't say too much about what n-categories are good for, except for a nice clear introduction entitled "Motivation for Topologists", where he sketches their relevance to homology theory, homotopy theory, and cobordism theory. But this is understandable, since a thorough treatment of their applications would vastly expand an already hefty 380-page book, and diffuse its focus. It would also steal sales from *my* forthcoming book on higher- dimensional algebra - which would be really bad, since I plan to retire on the fortune I'll make from this. Secondly, Michael Batanin has worked out a beautiful extension of his ideas on n-categories which sheds new light on their applications to homotopy theory: 6) Michael A. Batanin, The Eckmann-Hilton argument, higher operads and E_n spaces, available as math.CT/0207281. Michael A. Batanin, the combinatorics of iterated loop spaces, available as math.CT/0301221. Getting a manageable combinatorial understanding of the space of loops in the spaces of loops in the space of loops... in some space has always been part of the dream of higher-dimensional algebra. These "k-fold loop spaces" or have been important in homotopy theory since the 1970s - see the end of "week199" for a little bit about them. People know that k-fold loop spaces have k different products that commute up to homotopy in a certain way that can be summarized by saying they are algebras of the E_k operad, also called the "little k-cubes operad". However, their wealth of structure is still a bit mind-boggling. James Dolan and I made some conjectures about their relation to k-tuply monoidal categories in our paper "Categorification" (see "week121"), and now Batanin is making this more precise using his approach to n-categories - which is one of the ones described in Leinster's book. There's also been a lot of work applying higher-dimensional algebra to topological quantum field theory - that's what got me interested in n-categories in the first place, but a lot has happened since then. For a highly readable introduction to the subject, with tons of great pictures, try: 7) Joachim Kock, Frobenius Algebras and 2D Topological Quantum Field Theories, Cambridge U. Press, Cambridge, 2003. This is mainly about 2d TQFTs, where the concept of "Frobenius algebra" reigns supreme, and everything is very easy to visualize. When we go up to 3-dimensional spacetime life gets harder, but also more interesting. This book isn't so easy, but it's packed with beautiful math and wonderfully drawn pictures: 8) Thomas Kerler and Volodymyr L. Lyubashenko, Non-Semisimple Topological Quantum Field Theories for 3-Manifolds with Corners, Lecture Notes in Mathematics 1765, Springer, Berlin, 2001. The idea is that if we can extend the definition of a quantum field theory to spacetimes that have not just boundaries but *corners*, we can try to build up the theory for arbitrary spacetimes from its behavior on simple building blocks - since it's easier to chop manifolds up into a few basic shapes if we let those shapes have corners. However, it takes higher-dimensional algebra to describe all the ways we can stick together manifolds with corners! Here Kerler and Lyubashenko make 3-dimensional manifolds going between 2-manifolds with boundary into a "double category"... and make a bunch of famous 3d TQFTs into "double functors". Closely related is this paper by Kerler: 9) Thomas Kerler, Towards an algebraic characterization of 3-dimensional cobordisms, Contemp. Math. 318 (2003) 141-173. Also available as math.GT/0008204. It relates the category whose objects are 2-manifolds with a circle as boundary, and whose morphisms are 3-manifolds with corners going between these, to a braided monoidal category "freely generated by a quasitriangular Hopf algebra object". (I'm leaving out some fine print here, but probably putting in more than most people want!) It comes close to showing these categories are the same, but suggests that they're not quite - so the perfect connection between topology and higher categories remains elusive in this important example. Answer to the riddle: these are the Catalan numbers - i.e., the natural numbers as written in Catalan. This riddle was taken from the second volume of Stanley's book on enumerative combinatorics (see "week144"). ----------------------------------------------------------------------- Previous issues of "This Week's Finds" and other expository articles on mathematics and physics, as well as some of my research papers, can be obtained at http://math.ucr.edu/home/baez/ For a table of contents of all the issues of This Week's Finds, try http://math.ucr.edu/home/baez/twf.html A simple jumping-off point to the old issues is available at http://math.ucr.edu/home/baez/twfshort.html If you just want the latest issue, go to http://math.ucr.edu/home/baez/this.week.html From rrosebru@mta.ca Tue Feb 24 18:19:04 2004 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 24 Feb 2004 18:19:04 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1AvktE-0000Nh-00 for categories-list@mta.ca; Tue, 24 Feb 2004 18:18:56 -0400 From: Peter Selinger Message-Id: <200402240209.i1O29Du08607@quasar.mathstat.uottawa.ca> Subject: categories: Workshop on Quantum Programming Languages To: categories@mta.ca (Categories List) Date: Mon, 23 Feb 2004 21:09:13 -0500 (EST) X-Mailer: ELM [version 2.5 PL3] MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 30 CALL FOR PAPERS 2nd International Workshop on Quantum Programming Languages (QPL2004) July 12-13, 2004, Turku, Finland Affiliated with LICS 2004 http://quasar.mathstat.uottawa.ca/~selinger/qpl2004/ * * * The goal of this workshop is to bring together researchers working on mathematical formalisms and programming languages for quantum computing. In the last few years, there has been a growing interest in logical tools, languages, and semantical methods for analyzing quantum computation. These foundational approaches complement the more mainstream research in quantum computation which emphasizes algorithms and complexity theory. Possible topics include the syntax and semantics of quantum programming languages, new paradigms for quantum programming, specification of quantum algorithms, higher-order quantum computation, quantum data types, reversible computation, axiomatic approaches to quantum computation, concurrent and distributed quantum computation, compilation of quantum programs, semantical methods in quantum information theory, and categorical models for quantum computation. The first workshop in this series was held June 15-16, 2003, in Ottawa, Canada. SUBMISSION PROCEDURES: The workshop will be a 1.5-day workshop, with some invited speakers and some contributed presentations. Those who wish to give a contributed presentation should submit a one-page abstract (or a full paper up to 12 pages, if available) by April 25 to selinger@mathstat.uottawa.ca (please put "workshop submission" in the subject line). Authors of accepted abstracts or papers are invited to submit a full version (subject to a page limit, details to be announced) for inclusion in the workshop proceedings (to be distributed at the workshop) by June 7. If there is a sufficient number of papers, we will also arrange for them to be published as a volume of ENTCS, probably in association with other LICS or ICALP associated workshops (details to be announced). REGISTRATION: Registration and local arrangements will be handled through the LICS 2004 main conference (http://www.dcs.ed.ac.uk/home/als/lics/lics04/). There will be a small fee for attending the workshop, which will cover lunch, coffee, and proceedings. IMPORTANT DATES/DEADLINES: Submission of abstracts: April 25, 2004 Notification of acceptance: May 20, 2004 Paper for inclusion in proceedings: June 7, 2004 Workshop: July 12-13, 2004 CONTACT INFORMATION: Organizer: Peter Selinger Department of Mathematics and Statistics University of Ottawa, Canada Email: selinger@mathstat.uottawa.ca From rrosebru@mta.ca Tue Feb 24 19:20:03 2004 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 24 Feb 2004 19:20:03 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1Avlpi-0004Mh-00 for categories-list@mta.ca; Tue, 24 Feb 2004 19:19:22 -0400 From: Steve Lack MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <16443.53610.557110.403907@milan.maths.usyd.edu.au> Date: Wed, 25 Feb 2004 09:34:18 +1100 To: categories@mta.ca Subject: categories: re: Equivalences and psuedo-equivalences (two items) X-Mailer: VM 6.90 under 21.1 (patch 7) "Biscayne" XEmacs Lucid Reply-To: s.lack@uws.edu.au Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 31 Carl Futia asks the following questions: (1) If F:A-->B is a biequivalence of bicategories, is it equivalent to a strict homomorphism? (2) As in (1), but suppose that A and B are 2-categories. The answer to both questions is no. Here's an example. Let A be the 2-element group {0,1}, seen as a 2-category with one object, two arrows, and no non-trivial 2-cells. Let B be the 2-category with one object, with the integers as arrows (and composition given by addition) and with a unique, invertible 2-cell between arrows m and n if m-n is even, and no other 2-cells. The only strict homormorphism (i.e. 2-functor) from A to B sends both arrows of A to the identity arrow 0 of B. There is, however, a biequivalence F:A-->B, sending 0 to 0 and 1 to 1. Note also that there is an obvious 2-functor G:B-->A which is a biequivalence. So the example also illustrates that for a 2-functor which is a biequivalence it may not be possible to choose an ``inverse biequivalence'' which is a 2-functor. This example appeared in: Stephen Lack, A Quillen model structure for 2-categories, K-Theory 26:171-205, 2002 as Example 3.1 on page 178. In that context G:B-->A is actually a trivial fibration, so the fact that there is no 2-functor F with GF=1 also shows that the 2-category A is not cofibrant. Those interested in the rest of the paper should also look at the sequel: Stephen Lack, A Quillen model structure for bicategories, available from http://www.maths.usyd.edu.au/u/stevel/papers/qmcbicat.html which corrects an error in the model structure definition given in the earlier paper, and also extends the model structure to bicategories, giving a Quillen equivalence between the two model categories. Steve Lack. From rrosebru@mta.ca Fri Feb 27 11:16:20 2004 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 27 Feb 2004 11:16:20 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1Awjhg-0005Es-00 for categories-list@mta.ca; Fri, 27 Feb 2004 11:15:04 -0400 From: Topos8@aol.com Message-ID: <7d.478d000c.2d6e3856@aol.com> Date: Wed, 25 Feb 2004 12:41:42 EST Subject: categories: Eilenberg and Kelly invented n-categories? To: categories@mta.ca MIME-Version: 1.0 Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 36 I have received many helpful responses to my question asking who invented n-categories. However, a short while ago I was rereading the 1965 La Jolla paper by Eilenberg and Kelly (Closed categories, Proc. Conf.on Cat. Alg, Springer, 1965). On page 552 of the conference proceedings, chapter 4, section 2 of their paper, the authors write: [S]o one may define an n-category with morphisms of every type i [between 1 and n], a morphism of type i connecting two of type i - 1...". This is a very explicit reference to the notion of a strict n-category. The definition of an n-category given is that of a category enriched in n-1 categories. Eilenberg and Kelly also offer a reference to to Ehresmann's 1963 paper on structured categories but I can only find Ehresman's definition of n-tuple categories in his paper. Carl Futia From rrosebru@mta.ca Fri Feb 27 11:16:20 2004 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 27 Feb 2004 11:16:20 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1Awjh1-0005CD-00 for categories-list@mta.ca; Fri, 27 Feb 2004 11:14:23 -0400 Message-ID: <02dc01c3fb87$d0074540$befd4c51@brown1> From: "Ronald Brown" To: References: <159.2e745aaa.2d6b7dcf@aol.com> Subject: categories: Re: Who invented n-categories? Date: Wed, 25 Feb 2004 09:57:21 -0000 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 6.00.2800.1106 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2800.1106 Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 37 reply to r.brown@bangor.ac.uk There is the following paper 34. (with P.J. HIGGINS), ``The equivalence of $\infty$-groupoids and crossed complexes'', {\em Cah. Top. G\'eom. Diff.} 22 (1981) 371-386. which first defines an n-fold category, specialises to an n-category, and relates that to a notion of globular set in (2.2), (2.3), (without using the term globular, which I think came from Pursuing Stacks, 1983). Published at the same time was 33. (with P.J. HIGGINS), ``The equivalence of $\omega$-groupoids and cubical $T$-complexes'', {\em Cah. Top. G\'eom. Diff.} 22 (1981) 349-370 which deals with the cubical, groupoid, case (essential for the topological applications) and of which some announcement was made in 22. (with P.J. HIGGINS), ``Sur les complexes crois\'es, $\omega$-groupo\"{\i}des et T-complexes'', {\em C.R. Acad. Sci. Paris S\'er. A.} 285 (1977) 997-999. Were there earlier definitions? There was an unpublished manuscript by O. Wyler (1972) referred to in 34, which my memory suggests did define n-fold categories. Ronnie Brown http://www.bangor.ac.uk/~mas010 ----- Original Message ----- From: To: Sent: Monday, February 23, 2004 4:01 PM Subject: categories: Who invented n-categories? > Can anyone offer a reference to the first published work which defined a > notion of strict n-category equivalent to that used today? > > I know that Ehresmann invented n-tuple ( or n-fold ) categories which > contain strict n-categories as special cases. If this is the first > implicit defintion of strict n-category does anyone know who was the first > to isolate our current notion of strict n-category as a particularly > interesting special case of an n-tuple category? > > Carl Futia > From rrosebru@mta.ca Fri Feb 27 11:16:20 2004 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 27 Feb 2004 11:16:20 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1Awjfr-000540-00 for categories-list@mta.ca; Fri, 27 Feb 2004 11:13:11 -0400 Message-Id: <200402250526.i1P5Q8gA007761@coraki.Stanford.EDU> X-Mailer: exmh version 2.6.3 04/04/2003 with nmh-1.0.4 To: categories@mta.ca Subject: categories: Re: graphics Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Date: Tue, 24 Feb 2004 21:26:08 -0800 From: Vaughan Pratt Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 38 >My favorite method is to draw figures in xfig, then export the result as >LaTeX picture code and edit the text to take advantage of LaTeX's >text processing capabilities, fonts and special symbols. >It would be quite suitable for flow chart graphics. >D. Yetter Xfig is pretty convenient, but one can get a tad impatient with xfig's imprecision after a while. The time it takes to drag a vertex into position with acceptable precision tends in practice to be several times what it takes to simply type that position in by hand if you can see right away which lattice point it has to be. If you're a Picasso in such things then starting off with xfig isn't so bad, but if you're more of a Mondrian you might prefer to work in Latex's picture environment from the get-go. As with xypic, choosing a scale that makes the coordinates meaningful integers helps a lot here, e.g. being able to coordinatize the vertices of a diamond as (1,0), (0,1), (-1,0), (0,-1), or putting the inputs to an AND gate at (0,1) and (0,3) and the output at (4,2), or putting the vertices of a Hasse diagram at small lattice points. The only other widely supported language I know that's expressive enough to write a complete macro library in 20 lines for capabilities like flowcharts, digital or analog circuits, and lattice diagrams and that interoperates smoothly with Latex is PostScript. That works too, the main downside compared to programming directly in Latex's picture environment (for those using pdflatex) is the external file needed in the use of epstopdf plus includegraphics. (I'm using both in the paper I'm currently working on, mainly for fear of running out of Tex's memory with the more complex figures. Not that either are great programming languages per se, actually they kind of suck in that regard, thank you Don, Leslie, John, and Chuck!) The above comment about picking the right scale applies equally to Latex's picture environment and PostScript. When your diagrams are sufficiently like the ones that xypic, diagram.tex, and diagrams.tex are designed for, those are pretty good too. But they're not really conceived of as programming languages, making their usefulness inversely proportional to the distance between their kind of diagrams and yours. Vaughan Pratt From rrosebru@mta.ca Fri Feb 27 11:18:28 2004 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 27 Feb 2004 11:18:28 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1Awjkq-0005YG-00 for categories-list@mta.ca; Fri, 27 Feb 2004 11:18:20 -0400 Message-ID: <000d01c3fc26$fa44b730$1767eb44@grassmann> From: "Stephen Schanuel" To: Subject: categories: On Baez on 'complex Euler characteristics' Date: Thu, 26 Feb 2004 00:11:23 -0500 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: X-Keywords: X-UID: 39 Dear colleagues, For those who read the most recent long discursion of John Baez, a = few of the errors in the section on distributive categories merit = correction: (1) J. B. suggests that Blass published what Lawvere had already worked = out. In fact, Lawvere (partly to counteract some incorrect uses of = infinite series in analyses of 'data types' in computer science) had = worked out the algebra of the rig presented by one generator X and one = relation X=3D1+X^2, roughly by the method in (3) below, and conjectured = that this rig could be realized as the isomorphism classes in a = distributive (even extensive) category, which conjecture Blass then = proved (and a bit more) in "Seven Trees...". (2) The generalization of Blass's theorem to one generator ond one = polynomial relation of the 'fixed-point' form X=3Dp(X), where p is a = polynomial with natural number coefficients and nonzero constant term is = not, as J. B. seems to suggest, due to Fiore and Leinster; it was part = of the prize-winning doctoral thesis of Robbie Gates, who (using a = calculus of fractions) described explicitly the free distributive = category on one object X together with an isomorphism from p(X) to X, = proving that this category is extensive and that its rig of isomorphism = classes satisfies no further relations, i.e. is the rig R presented by = one generator and the one relation above. (3) If p is as in (2) and of degree at least 2, the algebra of the rig R = is made by J. B. to seem mysterious. It is more easily understood in the = way the X=3D2X+1 case was treated in my "Negative Sets..." paper; just = show that the Euler and dimension homomorphisms, tensoring with Z and = with 2 (the rig true/false) respectively, are jointly injective. In this = case the dimension rig has only three elements, which explains why the = Euler characteristic captures almost, but not quite, everything. Greetings to all, Steve Schanuel From rrosebru@mta.ca Fri Feb 27 11:37:34 2004 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 27 Feb 2004 11:37:34 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1Awk3D-0007lG-00 for categories-list@mta.ca; Fri, 27 Feb 2004 11:37:19 -0400 Date: Thu, 26 Feb 2004 07:27:05 -0600 Subject: categories: Re: Categorified GNS Mime-Version: 1.0 (Apple Message framework v543) To: categories@mta.ca From: David Yetter In-Reply-To: <20040224231341.14631.qmail@web12507.mail.yahoo.com> Message-Id: <785C1892-685F-11D8-A008-000393168DFE@math.ksu.edu> Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 40 I'm not quite sure whether its what you want, but a paper of mine, Measurable Categories, on the LANL preprint server at http://www.arxiv.org/abs/math.CT/0309185 develops the theory of measurable categories, and a 2-category of measurable functors and measurable natural transformations. The categories are categories of measurable fields of Hilbert spaces on a measurable space, which for technical reasons must be the Borel space associated to a Lusin space whose points are measureable. The functors between them are induced by measureable fields of Hilbert spaces on the product of source and target and a uniformly $\sigma$-finite conditional distribution of measures with respect to the second projection. The natural transformations are more or less induced by a field of bounded operators between the fields of Hilbert spaces inducing the functors, though one has to handle some technical difficulties involving Radon-Nikodym derivatives to get the definition to work. So far as I know this paper, and a companion in which Crane and I use measurable categories to begin the representation theory of 2-groups (including such things as Baez's Poincare 2-group) is the only progress to date on categorifying things functional-analytic. D.N. Yetter On Tuesday, February 24, 2004, at 05:13 PM, Iain wrote: > I am looking for information on categorifications of > C*-algebras. First, I know that there exists a theory > for finite dimensional 2-Hilbert spaces due to J.Baez, > but is there more recent work on infinite dimensional > versions of 2Hilb? Second, has anyone categorified the > GNS construction? > > -I > From rrosebru@mta.ca Fri Feb 27 11:38:19 2004 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 27 Feb 2004 11:38:19 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1Awk49-00005M-00 for categories-list@mta.ca; Fri, 27 Feb 2004 11:38:17 -0400 X-Sender: ehres@mailx.u-picardie.fr X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Thu, 26 Feb 2004 19:52:29 +0100 To: cat-dist@mta.ca From: Andree Ehresmann Subject: categories: Re: Who invented n-categories? In-Reply-To: <159.2e745aaa.2d6b7dcf@aol.com> Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 41 In answer to Carl Futia The first given example of a strict 2-category is the example of a 2-category of natural transformations. It has been given by Charles Ehresmann in his paper "Foncteurs types" of 1960 (reprinted in "Charles Ehresmann: Oeuvres completes et commentees" Part IV-1, page 103). He does not give the name 2-category but he explicits the "permutability" of the two laws of which Godement had given some particular cases in his book on sheaf theory in 1958. It is this example as well as the double category of squares of a category (which Charles called 'quatuors' and defined about the same time) that suggested the definition of double categories. I don't know who introduced the name 2-category nor when, but I remembers that Benabou used it around 1962-63. The general definition of an n-fold category is given by Charles in his paper "Categories structurees" in 1963 (reprinted in the "Oeuvres" Part III-1, p. 68), as an example of the general notion of an internal category in a concrete category (which he then called a structured category). The particular case of (strict) n-categories is not specified there. We used it in the last series of papers I wrote with Charles on n-fold categories in 1978 (reprinted in "Oeuvres", Part IV-2, p. 681, but it was well-known by this time. Andree C. Ehresmann From rrosebru@mta.ca Fri Feb 27 18:14:37 2004 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 27 Feb 2004 18:14:37 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1AwqD1-0007JP-00 for categories-list@mta.ca; Fri, 27 Feb 2004 18:11:51 -0400 Date: Fri, 27 Feb 2004 11:44:08 -0500 (EST) From: Robert Seely To: Categories List Subject: Re: categories: Re: graphics In-Reply-To: <200402250526.i1P5Q8gA007761@coraki.Stanford.EDU> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: X-Keywords: X-UID: 42 Using picture mode is very convenient when things aren't too complicated, and editing picture mode code is always (well, almost always) easier than redoing mouse based drawing. But the combination of a mouse-based drawing to generate picture mode code, then editing that for fine-tuning is often helpful. For those who are condemned to the Windows framework, let me recommend TeXCad - originally written by G Horn (it was then part of the emtex distribution), currently maintained by Gautier de Montmollin . Like Xfig, it creates picture mode code from your mouse-based drawing. The two programs are not completely similar (I prefer TeXCad, but others may differ!), but if you're using Windows, give it a try. -= rags =- On Tue, 24 Feb 2004, Vaughan Pratt wrote: > Xfig is pretty convenient, but one can get a tad impatient with xfig's > imprecision after a while. -- From rrosebru@mta.ca Fri Feb 27 18:14:37 2004 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 27 Feb 2004 18:14:37 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1AwqEL-0007NA-00 for categories-list@mta.ca; Fri, 27 Feb 2004 18:13:13 -0400 From: Topos8@aol.com Message-ID: Date: Fri, 27 Feb 2004 12:11:07 EST Subject: categories: The invention of n-categories To: categories@mta.ca MIME-Version: 1.0 Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: X-Keywords: X-UID: 43 Thanks to all who contributed information on history of the notion of a strict n-category. I'd like to summarize for the benefit of those interested what I have learned. The structure of CAT as a strict 2-category was of course implicit in Eilenberg and MacLane's original 1945 definition of categories, functors and natural transformations. Around 1958 Godement observed the significance of what we now call the exchange law relating horizontal and vertical compostion of natural transformations. In 1960 Charles Ehresmann codified our current notion of a strict 2-category and this notion also appeared in the thesis of his student Jean Benabou shortly thereafter. In 1963 Ehresmann published a defintion of n-tuple categories which include strict n-categories as a special case. However, Ehresmann did not isolate strict n-categories themselves as objects worthy of special attention. At the 1965 La Jolla conference Eilenberg and Kelly presented their paper on closed categories which defined strict n-categories recusively as categories enriched in strict n-1 categories. Around the same time the group surrounding Grothendieck at IHES had informally developed a non-recursive definition of strict n-category similar to what is used today. Finally, at the 1969 Bowdin conference, category theorists recognized that the recursive definition of Eilenberg-Kelly and the non recursive definition of the IHES group were equivalent. As far as I can tell the first significant technical development of the theory of strict n-categories (n > 2 ) appeared in a 1981 Cahiers paper by Ronnie Brown and PJ Higgins and in a 1984 Cahiers paper by Dominique Bourn. Carl Futia From rrosebru@mta.ca Sat Feb 28 11:03:59 2004 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 28 Feb 2004 11:03:59 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1Ax5y8-0007RA-00 for categories-list@mta.ca; Sat, 28 Feb 2004 11:01:32 -0400 Message-Id: <200402272235.i1RMZDdw010529@coraki.Stanford.EDU> X-Mailer: exmh version 2.6.3 04/04/2003 with nmh-1.0.4 To: categories@mta.ca Subject: categories: Re: The invention of n-categories Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Date: Fri, 27 Feb 2004 14:35:13 -0800 From: Vaughan Pratt Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 44 >From: Topos8@aol.com (Carl Futia) >Around the same time the group surrounding Grothendieck at IHES had >informally developed a non-recursive definition of strict n-category >similar to what is used today. ...prompting the question of whether x-categories for noninteger real x have been looked at. Presumably an early question here would be whether the spaces of fractional dimension that have already been studied depend on any geometric properties beyond those of n-categories. In particular what restrictions must one accept in order to have a coherent notion of a 1.5-category? Vaughan Pratt From rrosebru@mta.ca Sat Feb 28 11:04:17 2004 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 28 Feb 2004 11:04:17 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1Ax5zt-0007XS-00 for categories-list@mta.ca; Sat, 28 Feb 2004 11:03:21 -0400 Message-ID: <839BE2CA5177D3119C7000508B11F5DB04876B38@dagobah.parc.xerox.com> From: Valeria.dePaiva@parc.com To: categories@mta.ca Subject: categories: RE: graphics Date: Fri, 27 Feb 2004 15:48:28 PST MIME-Version: 1.0 X-Mailer: Internet Mail Service (5.5.2657.72) Content-Type: text/plain Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 45 Hi all, Robert suggested TeXCad for people who use Windows. I haven't used this system, so cannot comment, but here are my 2 cents worth, just in case... I believe that some day we will be able to draw in the computer as easily as we do in a piece of paper. But meanwhile, you can draw your diagrams in pieces of paper and use ScanScribe (overview at) http://www.parc.com/spl/groups/pda/scanscribe/index.html to make them digital. They won't look as neat as our latex ones, directly. So I, for one, won't be giving up on my latex diagrams quite yet. But you can read about possible uses of ScanScribe for *manipulating* category theory diagrams in http://www.parc.com/saund/papers/diagrams-poster-ss-abstract.html Also if you haven't yet invested the time into getting your latex (xypic or other) in place, maybe these diagrams will be good enough for you, I don't know. Moreover, Eric Saund the creator of ScanScribe is a very helpful computer scientist, who usually likes to have users and tend to be glad to assist them, whenever necessary. In particular, I think he has worked with flowchart diagrams (which might have been the beginning of this thread, I don't remember.) Best, Valeria Dr Valeria de Paiva PARC 3333 Coyote Hill Road PAlo Alto CA 94304 USA -----Original Message----- From: Robert Seely [mailto:rags@math.mcgill.ca] Sent: Friday, February 27, 2004 8:44 AM To: Categories List Subject: Re: categories: Re: graphics Using picture mode is very convenient when things aren't too complicated, and editing picture mode code is always (well, almost always) easier than redoing mouse based drawing. But the combination of a mouse-based drawing to generate picture mode code, then editing that for fine-tuning is often helpful. For those who are condemned to the Windows framework, let me recommend TeXCad - originally written by G Horn (it was then part of the emtex distribution), currently maintained by Gautier de Montmollin . Like Xfig, it creates picture mode code from your mouse-based drawing. The two programs are not completely similar (I prefer TeXCad, but others may differ!), but if you're using Windows, give it a try. -= rags =- On Tue, 24 Feb 2004, Vaughan Pratt wrote: > Xfig is pretty convenient, but one can get a tad impatient with xfig's > imprecision after a while. -- From rrosebru@mta.ca Sat Feb 28 11:09:16 2004 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 28 Feb 2004 11:09:16 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1Ax65R-0000Gv-00 for categories-list@mta.ca; Sat, 28 Feb 2004 11:09:05 -0400 Message-ID: <021701c3fde4$3ae0fce0$01ee4c51@brown1> From: "Ronald Brown" To: References: Subject: categories: Re: graphics: comment and a query Date: Sat, 28 Feb 2004 10:15:28 -0000 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 46 reply to r.brown@bangor.ac.uk Comment: We are redoing the pictures in my old Topology book for reprinting and find Overpic (a standard tex package) convenient to superimpose Latex math code onto postscript pictures produced from a graphics package. An advantage is the ease in such a package of putting in colour and variable shading. Sometimes the dvi or postscript output from the file does not work, yet the dvi to pdf does, and you get a good pdf file. (see comments on overpic on the web). Query: I would like to use color in xypic, particularly xymatrix, but the reference guide is difficult to follow on this point. My dvi viewer (YAP) has no problem with color. Can color be used in xymatrix? I would be grateful for some sample xymatrix or xy code using color for different arrows in a commutative diagram, such as those in the following file. Ronnie Brown http://www.bangor.ac.uk/~mas010 %vktdiagrams.tex 16/02/04 19/02/04 \documentclass[a4paper, 12pt]{article} \usepackage{amsmath,amssymb,geometry,xypic,epic,eepic,color} \xyoption{all} \geometry{textwidth=3D17cm} \def\io{^{-1}} \def\red{\textcolor{red}} \begin{document} \today \noindent{\bf van Kampen diagrams} This is a method of deducing consequences of relations, and indeed can be used to write an element as a consequence of the relations. \noindent { \sc Example 1:} The quaternion group of order 8 is usually presented in the form $$Q_8 =3D gp\langle x,y \mid x^4, x^2y^{-2}, y^{-1}xyx \rangle.$$ However the following diagram shows that the relation $x^4=3D1$ is a consequence of the other two relators. Set $r=3Dx^4, s=3Dx^2y^{-2}, t=3Dy^{-1}xyx$. $$\def\labelstyle{\textstyle}\xymatrix@R=3D1pc{A \ar @{}[dr] | s \ar = @{-}[rrr] | \tip ^ x &&& B \ar @{-}[dddd] | \tip ^ x\\ & E \ar @{-}[urr] | \tip _ y \save[]+<4.5em,-1.3ex>*{ t} \restore \save[]+<1em,-5ex>*{{s^{-1}} } \restore&& \\ && F \ar @{-} [ul] | \tip _x \ar @{-} [ddr] | \tip ^y & \\ & G \save[]+<0.1em,2ex>*{ \bullet} \restore \ar @{} [drr] |t \ar @{-}[ur] | \tip _ x \ar @{-}[dl] | \tip ^ y && \\ H \save[]+<-1em,-0.5ex>*{\bullet}\restore\save[]+<0.4em,3.5ex>*{ \bullet} \restore \save[]+<1.3em,0.8ex>*{ \bullet} \restore\ar @{-}[uuuu] | \tip _ x \ar @{-}[uuur] | \tip _ y && & \save[]+<-0.3em,3ex>*{ \bullet} \restore K\ar @{-}[lll] | \tip ^ x } $$ In this diagram, each cell has to have a base point, represented in the diagram by a $\bullet$, which is where the reading of the boundary starts, and an orientation. Here each label is read clockwise, and this explains why we have an $s$ and $s^{-1}$, since the latter is read counterclockwise. Now we have to show how we can deduce from this diagram the expression we want. We take the outside loop starting from $H$ (which has a base point for the outside `cell') and then change it to traverse the boundary of each internal cell, obtaining the rule which you can easily verify: $$xxy\io y\io. y x\io x\io y. y\io xyx. x\io. y\io xyx .x =3D x^4. $$ This can be reread as: $$s. y x\io x\io y . t. x\io. t.x=3Dx^4.$$ But $y x\io x\io y=3D yx\io x\io .yyx\io x\io . xxy\io =3D (s \io ) ^{xxy\io}$. So our final result is that $$ s.(s \io )^{xxy\io}.t. t^x. r\io $$is an identity among relators, or, alternatively, shows in a precise way how $x^4$ is a consequence of the other relators. \noindent {\sc Example 2:} To see the start of this process, consider the diagram: \red{ $$\def\labelstyle{\textstyle}\xymatrix @R=3D3pc {B \ar @{-}@/^3pc/ [rr] | \tip ^d \save[]+<3.2em,4ex>*{ t} \restore \save[]+<1em,1ex>*{ \bullet} \restore\ar @{-} [rr] |\tip _b && C \ar = @{-} [dl] |\tip ^c \\ & A \ar @{-} [ul] | \tip ^a \save[]+<0em,5.5ex>*{s} \restore \save[]+<0em,1.5ex>*{\bullet}\restore \save[]+<-1em,-0.5ex>*{\bullet}\restore & } $$} We write $\delta s=3D abc, \; \delta t =3D db\io$. Hence $$ adc =3D abc. c \io b \io . db\io .bc =3D (\delta s)( \delta ( t^{bc})).$$ Of course $t^{bc}$ makes sense in the context of crossed modules of groupoids, since $t$ is based at $B$ whereas $t^{bc}$ is based at $A$. One context for van Kampen diagrams is clarified by the notion of {\it shelling} of such a diagram. This is a sequence of 2-dimensional subcomplexes $K_0,K_1, \ldots, K_n$ each of which is formed from a union of 2-dimensional cells, with $K_0$ consisting of a chosen basepoint $*$, $K_1$ being a 2-cell $s_1$ with $*$ on its boundary, and such that for $i=3D2, \ldots, n$, $K_i$ is obtained from $K_{i-1}$ by adding a 2-cell $s_i$ such that $s_i \cap K_{i-1}$ is a non empty union of 1-cells which form a connected and 1-connected set, i.e. a path. Such a shelling will yield a formula for the boundary of $K_n$ in terms of the boundaries of each individual cell, provided each cell is given a base point and orientation. Here is a clear way of getting the formula (explained by Chris Wensley): Choose $* =3D K_0$ as base point for all the $K_i$. The relator for $K_0$ is the trivial word. If $B_1$ is the base point for $s_1$ and $P_1$ is the anticlockwise path around $s_1$ from $B_1$ to $*$ and $w_1$ is the word in the generators read off along $P_1$, then the relator for $K_1$ is = $\delta({s_1}^{w_1})$. For $i \geqslant 2$, let $B_i$ be the base point for $s_i$, and let $U_i, V_i$ be the first and last vertices in the intersection $s_i \cap K_{i-1}$ met when traversing the boundary of $K_{i-1}$ in a clockwise direction (so that the intersection is a path $U_i \ldots V_i$). Then if $B_i$ lies on $U_i \ldots V_i$ let $P_i$ be the path $B_i \ldots U_i \ldots *$, otherwise let $P_i$ be the path $B_i \ldots V_i \ldots U_i \ldots *$ (traversing the boundary of $s_i$ in an anticlockwise direction and the boundary of $K_{i-1}$ clockwise). If $w_i$ is the word in the generators read off along $P_i$ then $$ (\text{relator for } K_i) =3D (\text{relator for } K_{i-1}).\delta({s_i}^{w_i}). $$ In Example 2, $w_2 =3D bc$. \noindent {\sc Example 3:} The next example is the non obvious fact that the relators $$r=3D x^2yxy^3,\;\; s=3D y^2xyx^3$$ have $x^7$ as a consequence. This follows from the next picture. We leave it as an exercise to check that base points and orientations can be assigned, and, harder, to give $x^7$ as a consequence of $r,s$. On the other hand, it is not clear what the use of such a formula would be. $$\def\labelstyle{\textstyle} \xymatrix@M=3D0.1pc = @C=3D2.7pc@R=3D1.3pc{&&&&\circ \ar [dr] |y \ar [ddllll] |x &&&& \\ &&& \circ \ar [ur] |y && \circ \ar [dr] |y&&& \\ \circ \ar [ddddddd] _x&& \circ\ar [ur] |x\ar @{} [rrrr] |r&&&& \circ\ar [dr] |x && \circ \ar [uullll] _x \\ & \circ \ar [ur] |y \ar [dr] |x &&&&&& \circ \ar@{-} [llllll]|(0.7)\tip = ^x \ar [dddddd] ^y& \\ &&\circ \ar [dr] |y \ar @{} [rrrr] |{s^{-1}} & &&& \circ \ar [ur] |x && = \\ \ar @{} [r] |{s^{-1}}&&& \circ \ar [dr] |y && \circ \ar [ur] |y &&\ar = @{}[r] |{s^{-1}}&\\ &\ar @{} [rrr] |r&&& \circ \ar [dl] |y \ar [ur] |x &\ar @{} [rr] |r&&& = \\ && &\circ \ar [dl] |x && \circ \ar [ul] |x &&& \\ && \circ \ar [dl]|x \ar @{} [rrrr] |{s^{-1}} &&& &\circ \ar [ul]|y &&\\ \circ \ar [r] _x & \circ \ar [uuuuuu] ^y\ar [rrrrrr] _x &&&&&& \circ \ar [r] _x \ar [ul] |y & \circ\ar [uuuuuuu] _x \\ &&&&&&&& } $$ These examples are from David Johnson's book on `Combinatorial group theory'. Other examples on van Kampen diagrams are in that book, and may also be found by a web search. The geometric and metric analysis of van Kampen diagrams has proved important in aspects of combinatorial group theory. There are in the literature van Kampen diagrams which are not shellable. The general context for this can be put as follows. A {\it complete generalised van Kampen diagram} is a finite regular $CW$-structure $K$ on a compact subset of the sphere $S^2$. {\it Regularity} here means that each attaching map $f_s: (S^1,1) \to (K^1,K^0)$ of a 2-cell $s$ is a homeomorphism into. By omitting one 2-cell $s_\infty$ from $K$ and using stereographic projection we can also regard $K\setminus s_\infty$ as a subset of the plane $\mathbb{R}^2$. The projection of $K\setminus s_\infty$ gives a planar van Kampen diagram. Whitehead's theorem says essentially that $\Pi(K,K^1,K^0)$ is the free crossed $\pi_1(K^1,K^0)$-module on the characteristic maps of the 2-cells of $K$.=20 \end{document} \setlength{\unitlength}{1mm} \begin{picture}(50,30)(10,10) \linethickness{1pt} \put(90,0){\circle{20}} \put(90,10){\circle*{1}} \put(100,){\circle*{1}} \put(90,-10){\circle*{1}} \spline(90,10)(94,15)(102,8)(104,4)(100,0) \end{picture} > Can one formulate the shelling to give a formula? If the cells added = are > s_1, ...,s_n then you still need to choose a path from * to the base = point > of s_2 after going round s_1, and the idea is to use the intersection = of s_1 > and s_2. .... Yes - here is the formula: Choose * =3D B_1 =3D base point for s_1 as base point for all the K_i. Then relator for K_1 =3D \delta(s_1). If B_i is the base point for s_i, U_i is the first vertex in the intersection met when traversing the boundary of K_{i-1} in a clockwise direction, V_i is the last (traversing clockwise) vertex in the intersection (so that the intersection is a path from U_i to V_i) then if B_i lies on U_i..V_i let P_i be the path B_i..U_i..* otherwise let P_i be the path B_i..V_i..U_i..* (traversing the boundary of s_i in an anticlockwise direction and the boundary of K_{i-1} clockwise) and let w_i be the word in the generators read off along P_i. Then (relator for K_i) =3D (relator for K_{i-1}).\delta(s_i^{w_i}) In your example 2, w_2 =3D bc. Chris