*mbx* 42cf5ac300000000 1-Mar-2005 14:31:32 -0400,7235;000000000001-00000000 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 01 Mar 2005 14:31:32 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.44) id 1D6C3F-0001wY-CU for categories-list@mta.ca; Tue, 01 Mar 2005 14:24:57 -0400 Mime-Version: 1.0 (Apple Message framework v619.2) Content-Type: text/plain; charset=ISO-8859-1; format=flowed Message-Id: <5dd05e721c34764e0f7bbb28072fcd59@iiia.csic.es> Content-Transfer-Encoding: quoted-printable Reply-To: mathlog From: mathlog@ub.edu Subject: categories: ALGEBRAIC AND TOPOLOGICAL METHODS IN NON-CLASSICAL LOGICS II (Second announcement) Date: Tue, 1 Mar 2005 10:48:26 +0100 To: Carles Noguera X-Mailer: Apple Mail (2.619.2) Sender: cat-dist@mta.ca Precedence: bulk (apologies for multiple posting) Second announcement ALGEBRAIC AND TOPOLOGICAL METHODS IN NON-CLASSICAL LOGICS II Barcelona, 15-18 June 2005 This meeting shares the goals of the Tbilisi conference with the same=20 title, held in July 2003, as well as those of the Patras conference on=20= many-valued logics and residuated structures, held in June 2004. In recent years the interest in non-classical logics has been growing.=20= Motivations from computer science, natural language reasoning and=20 linguistics have played a significant role in this development. The=20 semantic study of non-classical logics is a field where no single=20 overarching paradigm has been established, and where a variety of=20 techniques are currently being explored. An important goal of this=20 meeting is to promote the cross-fertilization of the fundamental ideas=20= connected with these approaches. Thus, we aim to bring together=20 researchers from various fields of non-classical logics and=20 applications, as well as from lattice theory, universal algebra,=20 category theory and general topology, in order to foster collaboration=20= and further research. The scientific programme of the congress will include a few invited=20 lectures and will provide ample time for contributed papers and=20 interaction between participants. Researchers whose interests fit the=20 general aims of the conference are encouraged to participate. The=20 featured areas include, but are not limited to, the following (in=20 alphabetical order): - Algebraic logic - Coalgebraic semantics - Categorical semantics in general - Dynamic logic and dynamic algebras - Fuzzy and many-valued logics - Lattices with operators - Modal logics - Ordered topological spaces - Ordered algebraic structures - Residuated structures - Substructural logics - Topological semantics of modal logic INVITED SPEAKERS Guram Bezhanishvili, New Mexico State University, Las Cruces (USA) Robert Goldblatt, Victoria University, Wellington (New Zealand) Ian Hodkinson, King's College London (UK) Peter Jipsen, Chapman University, Orange (USA) Franco Montagna, Universit=E0 di Siena (Italy) Hilary Priestley, St. Anne's College, University of Oxford (UK) James Raftery, University of Natal, Durban (South Africa) PROGRAMME COMMITTEE Leo Esakia, Georgian Academy of Sciences Mai Gehrke, New Mexico State University Petr H=E1jek, Academy of Sciences of the Czech Republic Ramon Jansana, Universitat de Barcelona Hiroakira Ono, Japan Advanced Institute for Science and Technology=20 (chair) Constantine Tsinakis, Vanderbilt University Yde Venema, Universiteit van Amsterdam Michael Zacharyaschev, King's College London ORGANIZING COMMITTEE Josep Maria Font, Universitat de Barcelona (chair) =C0ngel Gil, Universitat Pompeu Fabra (Barcelona) Jos=E9 Gil, Universitat de Barcelona Joan Gispert, Universitat de Barcelona Carles Noguera, Institut d'Investigaci=F3 en Intel=B7lig=E8ncia = Artificial=20 (Bellaterra) Antoni Torrens, Universitat de Barcelona Ventura Verd=FA, Universitat de Barcelona SPONSORING INSTITUTIONS Ministry of Education and Science (Spanish government) Department of Universities, Research and Information Society of the=20 Generalitat de Catalunya (Catalan government) Faculty of Mathematics of the University of Barcelona Faculty of Philosophy of the University of Barcelona Catalan Mathematical Society With the collaboration of IMUB (Institute of Mathematics, University of=20= Barcelona) and IIIA (Artificial Intelligence Research Institute, CSIC). CONTRIBUTED PAPERS Participants who wish to present a talk should submit an abstract=20 through the Atlas service (http://atlas-conferences.com/) before 31=20 March 2005. The abstract should be written in TeX (or in plain,=20 non-formatted text without formulas) and be at most 2 pages long.=20 Authors will be notified before 30 April 2005 whether their submission=20= has been accepted for presentation. Participants needing early=20 acceptance are advised to submit their abstract as soon as possible and=20= inform the organizers of the situation. TRAVEL GRANTS We hope to provide some funding to partially cover travel expenses of=20 students and recent Ph.D.'s without grant support, as well as of active=20= researchers from countries with developing economies. The number and=20 amount of these grants will depend on the funding available, and will=20 be paid in cash during the meeting. Applications should be sent to mathlog@ub.edu before 31 March 2005. To=20= apply send a message with your personal data, a short CV, a description=20= of your research area and its relation with the topics of the meeting.=20= Students and recent Ph.D.'s should also ask their supervisor to send a=20= letter of support to the same address. CONGRESS VENUE The meeting will take place at the Facultat de Matem=E0tiques of the=20 Universitat de Barcelona, a 19th century building located in the city=20 centre. The address is: Gran Via de les Corts Catalanes 585, 08007=20 Barcelona, Spain. The building is on the square known as Pla=E7a de la=20= Universitat (University square). The lecture rooms are on the ground=20 floor of the building. Participants will be able to use a nearby=20 computer room with Internet access. No Wi-Fi coverage or free Ethernet=20= plugs are planned. REGISTRATION Participants must register to attend the meeting. The registration fee=20= is Euro 30 (approx. $ 39 as of March 1st), to be paid upon arrival.=20 Registration includes conference materials, coffee breaks and snacks,=20 and a special price for Saturday's dinner. Abstracts of accepted=20 contributed papers by registered participants will be included in the=20 congress' booklet. DEADLINES Submission of contributed papers: 31 March 2005 Acceptance of contributed papers: 30 April 2005 Travel grant applications: 31 March 2005 MORE INFORMATION Further details about registration, hotels, schedule, etc., will be=20 posted at the congress' web page http://www.mat.ub.edu/~logica/meeting2005/ For more information on the meeting, please visit this page, or write=20 to mathlog@ub.edu. =A0 2-Mar-2005 10:45:01 -0400,3580;000000000000-00000000 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 02 Mar 2005 10:45:01 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.44) id 1D6V32-0005Mu-1p for categories-list@mta.ca; Wed, 02 Mar 2005 10:42:00 -0400 From: Peter Selinger Message-Id: <200503020237.j222bl617316@quasar.mathstat.uottawa.ca> Subject: categories: 2nd CFP: Quantum Programming Languages Workshop To: categories@mta.ca (Categories List) Date: Tue, 1 Mar 2005 21:37:47 -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 SECOND CALL FOR PAPERS 3nd International Workshop on Quantum Programming Languages (QPL2005) June 30 - July 1, 2005, Chicago Affiliated with LICS 2005 http://quasar.mathstat.uottawa.ca/~selinger/qpl2005/ * * * The goal of this workshop is to bring together researchers working on mathematical foundations 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 design 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, abstract models for quantum computation, properties of quantum computing resources and primitives, concurrent and distributed quantum computation, compilation of quantum programs, semantical methods in quantum information theory, and categorical models for quantum computation. Previous workshops in this series were held in Ottawa (2003) and Turku (2004). INVITED SPEAKER: Louis H. Kauffman (Illinois, Chicago) PROGRAM COMMITTEE: Bob Coecke (Oxford) Simon Gay (Glasgow) Philippe Jorrand (Grenoble) Peter Selinger (Ottawa) SUBMISSION PROCEDURE: The workshop will be a 2-day workshop. Prospective speakers should submit a detailed abstract (or extended abstract) of 5-12 pages. Submissions of works in progress are encouraged, but must be more substantial than a research proposal. Submissions must provide sufficient detail to allow the program committee to assess the merits of the paper. Submissions should be in Postscript or PDF format, and should be sent to selinger@mathstat.uottawa.ca by April 4 (please put "workshop submission" in the subject line). Receipt of all submissions will be acknowledged by return email. PROCEEDINGS: The workshop proceedings will be published in Electronic Notes in Theoretical Computer Science (ENTCS). A printed copy of the preliminary proceedings will be distributed to participants at the workshop. IMPORTANT DATES/DEADLINES: Submissions: April 4, 2005 Notification of acceptance: April 25, 2005 Paper for printed proceedings: May 9, 2005 Workshop: June 30 - July 1, 2005 ENTCS revised paper: November 1, 2005 (tentative) CONTACT INFORMATION: Organizer: Peter Selinger University of Ottawa, Canada Email: selinger@mathstat.uottawa.ca (revised Mar 1, 2005) 2-Mar-2005 10:45:01 -0400,3539;000000000000-00000000 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 02 Mar 2005 10:45:01 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.44) id 1D6V2J-0005In-Az for categories-list@mta.ca; Wed, 02 Mar 2005 10:41:15 -0400 Date: Wed, 2 Mar 2005 08:33:32 +1100 (EST) Message-Id: <200503012133.j21LXWWM005527@cooper.uws.edu.au> From: "Stephen Lack" To: categories@mta.ca Subject: categories: Conference for the 60th birthday of Ross Street MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Sender: cat-dist@mta.ca Precedence: bulk This is a second announcement of the conferences on Categories in Algebra, Geometry and Mathematical Physics (the "Streetfest") organized to mark the 60th birthday of Ross Street, and taking place at Macquarie University in Sydney, Australia during the period 11-16 July. In order to recognize the broad influence of Ross' work there will be a large number of invited speakers, and consequently only a few contributed talks. People wishing to give a talk should submit a title and abstract before March 15, via the conference website at . Login by clicking on your name and then using the password "streetfest". If your name is not on the list, you will need to email either Michael Batanin or Steve Lack . It will also be possible to present a poster at the conference. Information on visas and accommodation can be found on the conference website; further enquiries about these matters should be directed to Victoria Benning . Accommodation not reserved by 15 April will be the responsibility of the individual. Note also that all international participants will need a visa to enter the country. We would also like to announce that we are planning a workshop "Categorical methods in Algebra, Geometry and Mathematical Physics" at the Australian National University (ANU in Canberra, 300 kilometers south from Macquarie) from 18 to 21 July as a satellite event for the Streetfest, and for the workshop on non-commutative geometry and index theory at the ANU. The workshop will be more oriented towards applications, and will cover four basic topics: 1. Categories in algebra and algebraic geometry, derived categories. 2. Categories in topology, homotopy theory and geometry. 3. Categories in mathematical physics. 4. Higher dimensional categories including A_{\infty}-categories, quasicategories, Segal categories. The following people have already expressed their interest in participating in this activity: John Baez, Alexei Bondal, Charles-Denis Cesinski, James Dolan, Jurgen Fuchs, Ezra Getzler, Andre Joyal, Michael Kapranov, Ludmil Katzarkov, Andrey Lazarev, Jean-Louis Loday, Georges Maltsiniotis, Randy McCarthy, Taras Panov, Ingo Runkel, Pedro Resende, Ross Street, Alexander Voronov, Mark Weber. The program for the workshop and the details of accommodation are still being sorted out. If you intend to participate, please let us know about your interest before 15 March. More details about this workshop will appear on our website after 15 March. Michael Batanin, Alexei Davydov, Michael Johnson, Steve Lack, Amnon Neeman. -- Stephen Lack School of Quantitative Methods and Mathematical Sciences University of Western Sydney Locked Bag 1797 Penrith South DC NSW 1797 AUSTRALIA Phone: +61 2 4736 0072 Office: Kingswood I222 3-Mar-2005 12:31:47 -0400,6652;000000000000-00000000 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 03 Mar 2005 12:31:47 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.44) id 1D6t5x-0007HY-3y for categories-list@mta.ca; Thu, 03 Mar 2005 12:22:37 -0400 Message-Id: <200503030324.j233O5s09696@synaphai.kurims.kyoto-u.ac.jp> X-Authentication-Warning: synaphai.kurims.kyoto-u.ac.jp: hassei@localhost didn't use HELO protocol To: categories@mta.ca cc: tlca05org@kurims.kyoto-u.ac.jp Subject: categories: TLCA 2005 Call for Participation Date: Thu, 03 Mar 2005 12:24:05 +0900 From: Hasegawa Masahito Sender: cat-dist@mta.ca Precedence: bulk ======================================================================= TLCA 2005 Seventh International Conference on Typed Lambda Calculi and Applications 21-23 April 2005, Nara, Japan http://www.kurims.kyoto-u.ac.jp/rdp05/tlca/ CALL FOR PARTICIPATION ** Early Registration Deadline: 31 March 2005 ** ======================================================================= The TLCA series of conferences serves as a forum for presenting original research results that are broadly relevant to the theory and applications of typed lambda calculi and related systems. This 7th TLCA Conference will consist of 3 invited talks and 27 refereed talks (see the programme below). TLCA'05 will be held as part of the Federated Conference on Rewriting, Deduction and Programming (RDP'05), jointly with the 16th International Conference on Rewriting Techniques and Applications (RTA'05) and several workshops. Now the registration and hotel booking procedures for RDP'05 are open; please follow the link to the registration page from the RDP'05 top page http://www.kurims.kyoto-u.ac.jp/rdp05/ to complete your registration. There also are links to web pages providing some travel and local information. Please remember that the number of hotel rooms is limited. Requests will be processed on a first come first served basis and will be subject to availability. RDP'05 will take place at the Nara-Ken New Public Hall which is located in the centre of the beautiful Nara National Park, within 20 minutes walk from the Kintestu Nara Station. CONTACT Enquiries regarding the registration and hotel booking should be sent to the RDP'05 organizers . Enquiries regarding the TLCA conference should be sent to the TLCA'05 organizers . FURTHER INFORMATION RDP'05 website: http://www.kurims.kyoto-u.ac.jp/rdp05/ TLCA'05 website: http://www.kurims.kyoto-u.ac.jp/rdp05/tlca/ ======================================================================= PROGRAMME of TLCA 2005 Thursday, 21st April 08:30-09:00 Registration 09:00-10:00 Amy Felty (invited speaker, joint with RTA) A Tutorial Example of the Semantic Approach to Foundational Proof-Carrying Code 10:00-10:30 Tea Break 10:30-11:00 Olivier Hermant Semantic Cut Elimination in the Intuitionistic Sequent Calculus 11:00-11:30 Rene David and Karim Nour Arithmetical Proofs of Strong Normalization Results for the Symmetric Lambda-mu-calculus 11:30-12:00 Francois Lamarche and Lutz Strassburger Naming Proofs in Classical Propositional Logic 12:00-12:30 Francois-Regis Sinot Call-by-Name and Call-by-Value as Token-Passing Interaction Nets 12:30-14:00 Lunch 14:00-14:30 Andreas Abel and Thierry Coquand Untyped Algorithmic Equality for Martin-Lof's Logical Framework with Surjective Pairs 14:30-15:00 Hugo Herbelin On the Degeneracy of Sigma-types in Presence of Computational Classical Logic 15:00-15:30 Ken-etsu Fujita Galois Embedding from Polymorphic Types into Existential Types 15:30-17:00 Social Event (Guided City Walk) 17:30-22:30 Drink, Entertainments, Conference Dinner Friday, 22nd April 09:00-10:00 Susumu Hayashi (invited speaker) Can Proofs be Animated by Games? 10:00-10:30 Tea Break 10:30-11:00 Carsten Schurmann, Adam Poswolsky, Jeffrey Sarnat The $\nabla$-Calculus. Functional Programming with Higher-order Encodings 11:00-11:30 Christian Urban and James Cheney Avoiding Equivariance in Alpha-Prolog 11:30-12:00 Peter Selinger and Benoit Valiron A Lambda-calculus for Quantum Computation with Classical Control 12:00-12:30 Greg Morrisett, Amal Ahmed, Matthew Fluet L^3: A Linear Language with Locations 12:30-14:00 Lunch 14:00-14:30 John Power and Miki Tanaka Binding Signatures for Generic Contexts 14:30-15:00 Sam Lindley and Ian Stark Reducibility and TT-lifting for Computation Types 15:00-15:30 Nick Benton and Benjamin Leperchey Relational Reasoning in a Nominal Semantics for Storage 15:30-16:00 Coffee Break 16:00-16:30 Paolo Coppola, Ugo Dal Lago and Simona Ronchi Della Rocca Elementary Linear Logics and the Call-by-value Lambda Calculus 16:30-17:00 Patrick Baillot and Kazushige Terui A Feasible Algorithm for Typing in Elementary Affine Logic 17:00-17:30 Ferruccio Damiani Rank-2 Intersection and Polymorphic Recursion 17:30-18:30 Business Meeting Saturday, 23rd April 09:00-10:00 Thierry Coquand (invited speaker) Completeness Theorems and $\lambda$-calculus 10:00-10:30 Tea Break 10:30-11:00 Yves Bertot Filters on Co-Inductive Streams: An Application to Eratosthenes' Sieve 11:00-11:30 Virgile Prevosto and Sylvain Boulme Proof Contexts with Late Binding 11:30-12:00 Stan Matwin, Amy Felty, Istvan Hernadvolgyi, and Venanzio Capretta Privacy in Data Mining Using Formal Methods 12:00-12:30 Damiano Zanardini Higher-Order Abstract Non-Interference 12:30-14:00 Lunch 14:00-14:30 Klaus Aehlig, Jolie G de Miranda, Luke Ong The Monadic Second Order Theory of Trees Given by Arbitrary Level Two Recursion Schemes Is Decidable 14:30-15:00 Paula Severi and Fer-Jan de Vries Continuity and Discontinuity in Lambda Calculus 15:00-15:30 Jim Laird The Elimination of Nesting in SPCF 15:30-16:00 Coffee Break 16:00-16:30 Ana Bove and Venanzio Capretta Recursive Functions with Higher Order Domains 16:30-17:00 Gilles Barthe, Benjamin Gregoire, Fernando Pastawski Practical Inference for Typed-based Termination in a Polymorphic Setting 17:00-17:30 Roberto Di Cosmo, Francois Pottier, Didier Remy Subtyping Recursive Types Modulo Associative Commutative Products ======================================================================= 4-Mar-2005 17:34:35 -0400,4454;000000000001-00000000 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 04 Mar 2005 17:34:35 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.44) id 1D7KJk-0003cb-L9 for categories-list@mta.ca; Fri, 04 Mar 2005 17:26:40 -0400 Message-Id: Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Date: Fri, 4 Mar 2005 12:11:59 +0100 To: categories@mta.ca From: Marco Grandis Subject: categories: lax transformations of 2-functors Sender: cat-dist@mta.ca Precedence: bulk Dear categorists, Is there a good terminology for "relaxed transformations" between 2-functors and the "relaxed adjunctions" where they appear as unit/counit? Generally, I find the Kelly-Street terminology (LNM 420, 1974) for 2-dimensional category theory very convenient: clear, elegant and as simple as possible. However, I have problems in the cases recalled above. 1. Let us agree, with Kelly-Street, that a LAX functor F (between 2-categories, to simplify things) has comparison cells F(g).F(f) --> F(gf), while an OP-LAX one has comparison cells the other way round. (It is quite reasonable to take the first notion as the leading one, since it is related with LIMITS and MONADS, while the opposite is related with COLIMITS and COMONADS). 2. Now, let us say for the moment that an "XXX-transformation" phi: F --> G has comparison cells (corresponding to maps a: A --> B in the domain) phi(a): phi(B).Fa --> Ga.phi(A), while an "op-XXX-transformation" has reversed comparison cells. Let us also speak of an "XXX-adjunction" (between strict 2-functors, to simplify things) to mean that its unit and counit are XXX-transformations; similarly for op-XXX-adjunctions (examples below, point 4). Such notions (and precise definitions) were introduced in the 70's. An XXX-transformation is called: - a "quasi-natural transformation" in Bunge LNM 195 (1971) and Trans. AMS (1974); - a "quasi_d natural transformation" in Gray LNM 391 (1974) ("d" for down); - an "op-lax natural transformation" in Kelly, On clubs and doctrines, LNM 420 (1974). An XXX-adjunction is called a "formal lax adjunction" in Bunge, Trans. AMS. An op-XXX-adjunction is called a "weak quasi-adjunction" in Gray. 3. Here, I find the term "lax" or "op-lax" misleading, since LAX functors can have both XXX- and op-XXX-transformations. Moreover, "lax adjunction" would seem to point to the functors rather than to unit & counit. 4. A few simple examples of XXX- and op-XXX-adjunctions can be of help in clarifying things. Take the strict 2-functors p: RelAb --> 1, i: 1 --> RelAb, sending the one object to the null group 0. We have: (a) an XXX-adjunction p -| i, with XXX unit 1 --> ip, sending an object A to the greatest relation A --> 0 (and trivial counit pi = 1); (b) an op-XXX-adjunction p -| i, with op-XXX unit 1 --> ip, sending an object A to the least relation A --> 0; (c) an XXX-adjunction i -| p, with XXX counit ip --> 1, sending an object A to the least relation 0 --> A; (d) an op-XXX-adjunction i -| p, with XXX unit ip --> 1, sending an object A to the greatest relation 0 --> A. These examples also show (perhaps) some motivation for taking the XXX notion as the leading one: - (a) shows the null group as an XXX-terminal object via the TERMINAL relation to it, - (c) shows the null group as an XXX-initial object via the INITIAL relation from it. 5. Now we are left with finding a good term for "XXX". (a) I would avoid "lax", as already motivated. (b) "weak" should probably be avoided as well, as is often used in the same sense of "pseudo", i.e. with reference to invertible comparisons; moreover, "weak terminal" means a different thing in 1-category theory. (c) "quasi" might be acceptable? It would give "quasi transformation" (or quasi natural transformation") , "op-quasi transformation", "quasi adjunction", "op-quasi adjunction", "quasi terminal",... _________ I would appreciate comments, criticism and suggestions. Best regards to all Marco Grandis Dipartimento di Matematica Universita` di Genova via Dodecaneso 35 16146 GENOVA, Italy e-mail: grandis@dima.unige.it tel: +39.010.353 6805 fax: +39.010.353 6752 http://www.dima.unige.it/~grandis/ 4-Mar-2005 17:34:35 -0400,2194;000000000001-00000000 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 04 Mar 2005 17:34:35 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.44) id 1D7KIK-0003Mp-67 for categories-list@mta.ca; Fri, 04 Mar 2005 17:25:12 -0400 Date: Thu, 3 Mar 2005 17:45:39 -0800 (PST) From: John MacDonald To: categories@mta.ca Subject: categories: FMCS05 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed Sender: cat-dist@mta.ca Precedence: bulk First Announcement FMCS05 Foundational Methods in Computer Science JUNE 2nd - 5th, 2005 The Department of Mathematics at the University of British Columbia in cooperation with the Pacific Institute for Mathematical Sciences is hosting the Foundational Methods in Computer Science workshop from June 2nd to June 5th, 2005, on the University of British Columbia Campus in Vancouver, B.C., Canada The workshop is an informal meeting to bring together researchers in mathematics and computer science with a focus on the application of category theory in computer science. The meeting begins with a reception at 6pm in the Ruth Blair room in Walter Gage Towers on the UBC campus on Thursday June 2, 2005. This is followed by a day of tutorials aimed at students and newcomers to computer science applications of category theory, followed by a day and a half of research talks. The meeting ends at 1pm on Sunday June 5. There will be a few invited presentations, but the majority of the talks are solicited from the participants. Student participation is particularly encouraged at FMCS. There are still a few places on the program left for research presentations of 20 to 30 minutes. To receive further information about FMCS05 as it becomes available, including information about housing and registration, please send email to johnm@math.ubc.ca with subject heading FMCS05 - WILL ATTEND or FMCS05 - MAY ATTEND. John MacDonald Local organizer, FMCS05 9-Mar-2005 08:44:43 -0400,1417;000000000000-00000000 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 09 Mar 2005 08:44:43 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.44) id 1D90PG-0004te-Am for categories-list@mta.ca; Wed, 09 Mar 2005 08:35:18 -0400 To: categories@mta.ca Date: Tue, 8 Mar 2005 16:05:25 GMT Message-Id: <200503081605.j28G5PwY029675@balmullo.inf.ed.ac.uk> From: Alex Simpson Subject: categories: LICS 2005: Call for Short Presentations Sender: cat-dist@mta.ca Precedence: bulk Twentieth Annual IEEE Symposium on LOGIC IN COMPUTER SCIENCE (LICS 2005) June 26th-29th, 2005, Chicago, Illinois http://www.lfcs.informatics.ed.ac.uk/lics/ CALL FOR SHORT PRESENTATIONS The LICS Symposium is an annual international forum on theoretical and practical topics in computer science that relate to logic broadly construed. LICS 2005 will have a session of short (5-10 minutes) presentations. This session is intended for descriptions of work in progress, student projects, and relevant research being published elsewhere; other brief communications may be acceptable. Submissions for these presentations, in the form of short abstracts (1 or 2 pages long), should be entered at the LICS 2005 submission site between 19th March and 25th March 2005. Authors will be notified of acceptance or rejection by 1st April 2005. 11-Mar-2005 13:01:40 -0400,1466;000000000000-00000000 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 11 Mar 2005 13:01:40 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.44) id 1D9nN3-0004TZ-R9 for categories-list@mta.ca; Fri, 11 Mar 2005 12:52:17 -0400 From: Topos8@aol.com Message-ID: Date: Wed, 9 Mar 2005 13:47:46 EST Subject: categories: Categories as a "foundation" for math 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 In the 1966 La Jolla conference volume appeared Lawvere's paper "The category of categories as a foundation for mathematics". Is it known just how much mathematics can be done using Lawvere's axiom scheme? My confusion on this point arises partly from a remark by Gray in his paper "The categorical comprehension scheme" in which he asserted that Lawvere's axioms couldn't do all that was claimed for them. Of course all of this predates the recognition that an elementary topos (with nn object) can be treated as a "universe of sets". I know that there has been some work (e.g. Joyal and Moerdijk) on constructing models of ZF set theory within categories with special properties. Can such categories be constructed using Lawvere's axioms? I hope this question makes sense but my skills in set theory and logic are pretty limited. Carl Futia 11-Mar-2005 13:01:41 -0400,22182;000000000001-00000000 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 11 Mar 2005 13:01:41 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.44) id 1D9nNg-0004X0-1J for categories-list@mta.ca; Fri, 11 Mar 2005 12:52:56 -0400 Message-Id: <200503101753.j2AHrJc05052@math-cl-n03.ucr.edu> Subject: categories: Bott periodicity and an octagon of functors To: categories@mta.ca (categories) Date: Thu, 10 Mar 2005 09:53:18 -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 Dear Categorists - Though it's not really news, I only recently realized that Bott periodicity is all about an octagonal diagram with functors circling around clockwise, all with ambidextrous adjoints circling around the other way. Maybe some of you will be interested.... Best, jb ......................................................................... Also available at http://math.ucr.edu/home/baez/week211.html March 6, 2005 This Week's Finds in Mathematical Physics - Week 211 John Baez The last time I wrote an issue of this column, the Huyghens probe was bringing back cool photos of Titan. Now the European "Mars Express" probe is bringing back cool photos of Mars! 1) Mars Express website, http://www.esa.int/SPECIALS/Mars_Express/index.html There are some tantalizing pictures of what might be a "frozen sea" - water ice covered with dust - near the equator in the Elysium Planitia region: 2) Mars Express sees signs of a "frozen sea", http://www.esa.int/SPECIALS/Mars_Express/SEMCHPYEM4E_0.html Ice has already been found at the Martian poles - it's easily visible there, and Mars Express is getting some amazing closeups of it now - here's a here's a view of some ice on sand at the north pole: 3) Glacial, volcanic and fluvial activity on Mars: latest images, http://www.esa.int/SPECIALS/Mars_Express/SEMLF6D3M5E_1.html What's new is the possibility of large amounts of water in warmer parts of the planet. Now for some math. It's always great when two subjects you're interested in turn out to be bits of the same big picture. That's why I've been really excited lately about Bott periodicity and the "super-Brauer group". I wrote about Bott periodicity in "week105", and about the Brauer group in "week209", but I should remind you about them before putting them together. Bott periodicity is all about how math and physics in n+8-dimensional space resemble math and physics in n-dimensional space. It's a weird and wonderful pattern that you'd never guess without doing some calculations. It shows up in many guises, which turn out to all be related. The simplest one to verify is the pattern of Clifford algebras. You're probably used to the complex numbers, where you throw in just *one* square root of -1, called i. And maybe you've heard of the quaternions, where you throw in *two* square roots of -1, called i and j, and demand that they anticommute: ij = -ji This implies that k = ij is another square root of -1. Try it and see! In the late 1800s, Clifford realized there's no need to stop here. He invented what we now call the "Clifford algebras" by starting with the real numbers and throwing in n square roots of -1, all of which anticommute with each other. The result is closely related to rotations in n+1 dimensions, as I explained in "week82". I'm not sure who first worked out all the Clifford algebras - perhaps it was Cartan - but the interesting fact is that they follow a periodic pattern. If we use C_n to stand for the Clifford algebra generated by n anticommuting square roots of -1, they go like this: C_0 R C_1 C C_2 H C_3 H + H C_4 H(2) C_5 C(4) C_6 R(8) C_7 R(8) + R(8) where R(n) means n x n real matrices, C(n) means n x n complex matrices, and H(n) means n x n quaternionic matrices. All these become algebras with the usual addition and multiplication of matrices. Finally, if A is an algebra, A + A consists of pairs of guys in A, with pairwise addition and multiplication. What happens next? Well, from then on things sort of "repeat" with period 8: C_{n+8} consists of 16 x 16 matrices whose entries lie in C_n! So, you can remember all the Clifford algebras with the help of this eight-hour clock: 0 R 7 1 R+R C 6 R H 2 C H+H 5 3 H 4 To use this clock, you have to remember to use matrices of the right size to get C_n to have dimension 2^n. So, when I write "R + R" next to the "7" on the clock, I don't mean C_7 is really R + R. To get C_7, you have to take R + R and beef it up until it becomes an algebra of dimension 2^7 = 128. You do this by taking R(8) + R(8), since this has dimension 8 x 8 + 8 x 8 = 128. Similarly, to get C_{10}, you note that 10 is 2 modulo 8, so you look at "2" on the clock and see "H" next to it, meaning the quaternions. But to get C_{10}, you have to take H and beef it up until it becomes an algebra of dimension 2^{10} = 1024. You do this by taking H(16), since this has dimension 4 x 16 x 16 = 1024. This "beefing up" process is actually quite interesting. For any associative algebra A, the algebra A(n) consisting of n x n matrices with entries in A is a lot like A itself. The reason is that they have equivalent categories of representations! To see what I mean by this, remember that a "representation" of an algebra is a way for its elements to act as linear transformations of some vector space. For example, R(n) acts as linear transformations of R^n by matrix multiplication, so we say R(n) has a representation on R^n. More generally, for any algebra A, the algebra A(n) has a representation on A^n. More generally still, if we have any representation of A on a vector space V, we get a representation of A(n) on V^n. It's less obvious, but true, that *every* representation of A(n) comes from a representation of A this way. In short, just as n x n matrices with entries in A form an algebra A(n) that's a beefed-up version of A itself, every representation of A(n) is a beefed-up version of some representation of A. Even better, the same sort of thing is true for maps between representations of A(n). This is what we mean by saying that A(n) and A have equivalent categories of representations. If you just look at the categories of representations of these two algebras as abstract categories, there's no way to tell them apart! We say two algebras are "Morita equivalent" when this happens. It's fun to study Morita equivalence classes of algebras - say algebras over the real numbers, for example. The tensor product of algebras gives us a way to multiply these classes. If we just consider the invertible classes, we get a *group*. This is called the "Brauer group" of the real numbers. The Brauer group of the real numbers is just Z/2, consisting of the classes [R] and [H]. These correspond to the top and bottom of the Clifford clock! Part of the reason is that H tensor H = R(4) so when we take Morita equivalence classes we get [H] x [H] = [R] But, you may wonder where the complex numbers went! Alas, the Morita equivalence class [C] isn't invertible, so it doesn't live in the Brauer group. In fact, we have this little multiplication table for tensor prod algebras: tensor R C H ---------------------- R | R C H | C | C C+C C(2) | H | H C(2) R(4) Anyone with an algebraic bone in their body should spend an afternoon figuring out how this works! But I won't explain it now. Instead, I'll just note that the complex numbers are very aggressive and infectious - tensor anything with a C in it and you get more C's. That's because they're a field in their own right - and that's why they don't live in the Brauer group of the real numbers. They do, however, live in the *super-Brauer* group of the real numbers, which is Z/8 - the Clifford clock itself! But before I explain that, I want to show you what the categories of representations of the Clifford algebras look like: 0 real vector spaces 7 1 split real vector spaces complex vector spaces 6 real vector spaces quaternionic vector spaces 2 complex vector spaces split quaternionic vector spaces 5 3 quaternionic vector spaces 4 You can read this information off the 8-hour Clifford clock I showed you before, at least if you know some stuff: A real vector space is just something like R^n A complex vector space is just something like C^n A quaternionic vector space is just something like H^n and a "split" vector space is a vector space that's been written as the direct sum of two subspaces. Take C_4, for example - the Clifford algebra generated by 4 anticommuting square roots of -1. The Clifford clock tells us this is H + H. And if you think about it, a representation of this is just a pair of representations of H. So, it's two quaternionic vector spaces - or if you prefer, a "split" quaternionic vector space. Or take C_7. The Clifford clock says this is R + R... or at least Morita equivalent to R + R: it's actually R(8) + R(8), but that's just a beefed-up version of R + R, with an equivalent category of representations. So, the category of representations of C_7 is *equivalent* to the category of split real vector spaces. And so on. Note that when we loop all the way around the clock, our Clifford algebra becomes 16 x 16 matrices of what it was before, but this is Morita equivalent to what it was. So, we have a truly period-8 clock of categories! But here's the really cool part: there are also arrows going clockwise and counterclockwise around this clock! Arrows between categories are called "functors". Each Clifford algebra is contained in the next one, since they're built by throwing in more and more square roots of -1. So, if we have a representation of C_n, it gives us a representation of C_{n-1}. Ditto for maps between representations. So, we get a functor from the category of representations of C_n to the category of representations of C_{n-1}. This is called a "forgetful functor", since it "forgets" that we have representations of C_n and just thinks of them as representations of C_{n-1}. So, we have forgetful functors cycling around counterclockwise! Even better, all these forgetful functors have "left adjoints" going back the other way. I talked about left adjoints in "week77", so I won't say much about them now. I'll just give an example. Here's a forgetful functor: forget complex structure complex vector spaces ---------------------------> real vector spaces which is one of the counterclockwise arrows on the Clifford clock. This functor takes a complex vector space and forgets your ability to multiply vectors by i, thus getting a real vector space. When you do this to C^n, you get R^{2n}. This functor has a left adjoint: complexify complex vector spaces <-------------------------- real vector spaces where you take a real vector space and "complexify" it by tensoring it with the complex numbers. When you do this to R^n, you get C^n. So, we get a beautiful version of the Clifford clock with forgetful functors cycling around counterclockwise and their left adjoints cycling around clockwise! When I realized this, I drew a big picture of it in my math notebook - I always carry around a notebook for precisely this sort of thing. Unfortunately, it's a bit hard to draw this chart in ASCII, so I won't include it here. Instead, I'll draw something easier. For this, note the following mystical fact. The Clifford clock is symmetrical under reflection around the 3-o'clock/7-o'clock axis: 0 real vector spaces 7 1 split real vector spaces complex vector spaces \ \ \ \ 6 real vector spaces \ quaternionic vector spaces 2 \ \ \ \ complex vector spaces split quaternionic vector spaces 5 3 quaternionic vector spaces 4 It seems bizarre at first that it's symmetrical along *this* axis instead of the more obvious 0-o'clock/4-o'clock axis. But there's a good reason, which I already mentioned: the Clifford algebra C_n is related to rotations in n+1 dimensions. I would be very happy if you had enough patience to listen to a full explanation of this fact, along with everything else I want to say. But I bet you don't... so I'll hasten on to the really cool stuff. First of all, using this symmetry we can fold the Clifford clock in half... and the forgetful functors on one side perfectly match their left adjoints on the other side! So, we can save space by drawing this "folded" Clifford clock: split real vector spaces | ^ forget splitting | | double v | real vector spaces | ^ complexify | | forget complex structure v | complex vector spaces | ^ quaternionify | | forget quaternionic structure v | quaternionic vector spaces | ^ double | | forget splitting v | split quaternionic vector spaces The forgetful functors march downwards on the right, and their left adjoints march back up on the left! The arrows going between 7 o'clock and 0 o'clock look a bit weird: split real vector spaces | ^ forget splitting | | double V | real vector spaces Why is "forget splitting" on the left, where the left adjoints belong, when it's obviously an example of a forgetful functor? One answer is that this is just how it works. Another answer is that it happens when we wrap all the way around the clock - it's like how going from midnight to 1 am counts as going forwards in time even though the number is getting smaller. A third answer is that the whole situation is so symmetrical that the functors I've been calling "left adjoints" are also "right adjoints" of their partners! So, we can change our mind about which one is "forgetful", without getting in trouble. But enough of that: I really want to explain how this stuff is related to the super-Brauer group, and then tie it all in to the *topology* of Bott periodicity. We'll see how far I get before giving up in exhaustion.... What's a super-Brauer group? It's just like a Brauer group, but where we use superalgebras instead of algebras! A "superalgebra" is just physics jargon for a Z/2-graded algebra - that is, an algebra A that's a direct sum of an "even" or "bosonic" part A_0 and an "odd" or "fermionic" part A_1: A = A_0 + A_1 such that multiplying a guy in A_i and a guy in A_j gives a guy in A_{i+j}, where we add the subscripts mod 2. The tensor product of superalgebras is defined differently than for algebras. If A and B are ordinary algebras, when we form their tensor product, we decree that everybody in A commutes with everyone in B. For superalgebras we decree that everybody in A "supercommutes" with everyone in B - meaning that ab = ba if either a or b are even (bosonic) while ab = -ba if a and b are both odd (fermionic). Apart from these modifications, the super-Brauer group works almost like the Brauer group. We start with superalgebras over our favorite field - here let's use the real numbers. We say two superalgebras are "Morita equivalent" if they have equivalent categories of representations. We can multiply these Morita equivalence classes by taking tensor products, and if we just keep the invertible classes we get a group: the super-Brauer group. As I've hinted already, the super-Brauer group of the real numbers is Z/8 - just the Clifford algebra clock in disguise! Here's why: The Clifford algebras all become superalgebras if we decree that all the square roots of -1 that we throw in are "odd" elements. And if we do this, we get something great: C_n tensor C_m = C_{n + m} The point is that all the square roots of -1 we threw in to get C_n *anticommute* with those we threw in to get C_m. Taking Morita equivalence classes, this mean [C_n] [C_m] = [C_{n+m}] but we already know that [C_{n+8}] = [C_n] so we get the group Z/8. It's not obvious that this is *all* the super-Brauer group, but it actually is - that's the hard part. Now let's think about what we've got. We've got the super-Brauer group, Z/8, which looks like an 8-hour clock. But before that, we had the categories of representations of Clifford algebras, which formed an 8-hour clock with functors cycling around in both directions. In fact these are two sides of the same coin - or clock, actually. The super-Brauer group consists of Morita equivalence classes of Clifford algebras, where Morita equivalence means "having equivalent categories of representations". But, our previous clock just shows their categories of representations! This suggests that the functors cycling around in both directions are secretly an aspect of the super-Brauer group. And indeed they are! The functors going clockwise are just "tensoring with C_1", since you can tensor a representation of C_n with C_1 and get a representation of C_{n+1}. And the functors going counterclockwise are "tensoring with C_{-1}"... or C_7 if you insist, since C_{-1} doesn't strictly make sense, but 7 equals -1 mod 8, so it does the same job. Hmm, I think I'm tired out. I didn't even get to the topology yet! Maybe that'll be good as a separate little story someday. If you can't wait, just read this: 4) John Milnor, Morse Theory, Princeton U. Press, Princeton, New Jersey, 1963. You'll see here that a representation of C_n is just the same as a vector space with n different anticommuting ways to "rotate vector by 90 degrees", and that this is the same as a real inner product space equipped with a map from the n-sphere into its rotation group, with the property that the north pole of the n-sphere gets mapped to the identity, and each great circle through the north pole gives some action of the circle as rotations. Using this, and stuff about Clifford algebras, and some Morse theory, Milnor gives a beautiful proof that Omega^8(SO(infinity)) ~ SO(infinity) or in English: the 8-fold loop space of the infinite-dimensional rotation group is homotopy equivalent to the infinite-dimensional rotation group! The thing I really like, though, is that Milnor relates the forgetful functors I was talking about to the process of "looping" the rotation group. That's what these maps from spheres into the rotation group are all about... but I want to really explain it all someday! I learned about the super-Brauer group here: 5) V. S. Varadarajan, Supersymmetry for Mathematicians: An Introduction, American Mathematical Society, Providence, Rhode Island, 2004. though the material here on this topic is actually a summary of some lectures by Deligne in another book I own: 6) P. Deligne, P. Etingof, D.S. Freed, L. Jeffrey, D. Kazhdan, J. Morgan, D.R. Morrison and E. Witten, Quantum Fields and Strings: A Course For Mathematicians 2 vols., American Mathematical Society, Providence, 1999. Notes also available at http://www.math.ias.edu/QFT/ Varadarajan's book doesn't go as far, but it's much easier to read, so I recommend it as a way to get started on "super" stuff. ----------------------------------------------------------------------- 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 12-Mar-2005 15:39:41 -0400,2197;000000000000-00000000 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 12 Mar 2005 15:39:41 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.44) id 1DACKO-0004pu-7G for categories-list@mta.ca; Sat, 12 Mar 2005 15:31:12 -0400 From: Organization: FernUniversitaet To: categories@mta.ca Date: Sat, 12 Mar 2005 09:49:38 +0200 MIME-Version: 1.0 Content-type: text/plain; charset=US-ASCII Content-transfer-encoding: 7BIT Subject: categories: Re: Categories as a "foundation" for math Message-ID: <4232BB31.14303.209BD6@localhost> Sender: cat-dist@mta.ca Precedence: bulk Hello, Carl Futia wrote: > Is it known just how much mathematics can be done using Lawvere's > axiom scheme? My confusion on this point arises partly from a remark > by Gray in his paper "The categorical comprehension scheme" in which > he asserted that Lawvere's axioms couldn't do all that was claimed for > them. Of course all of this predates the recognition that an > elementary topos (with nn object) can be treated as a "universe of > sets". As I see it, the problem is with the replacement scheme. Even if you start with ZF and classical logic, you have problems to express replacement in terms of first-order properties of the category of sets. An infinite cardinal a is called a strong limit cardinal, if b Envelope-to: categories-list@mta.ca Delivery-date: Sat, 12 Mar 2005 19:27:06 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.44) id 1DAFyS-0006Uh-6k for categories-list@mta.ca; Sat, 12 Mar 2005 19:24:48 -0400 Date: Sat, 12 Mar 2005 11:11:09 -0800 From: Vaughan Pratt Reply-To: pratt@cs.stanford.edu Organization: Stanford University User-Agent: Mozilla Thunderbird 0.9 (Windows/20041103) To: Subject: categories: Re: Categories as a "foundation" for math References: <42330471.1060204@cs.stanford.edu> In-Reply-To: <42330471.1060204@cs.stanford.edu> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Besides Carl Futia's question as to the expressiveness of categories (if I understood its drift) there is also the less judgmental question of what it feels like to use category theoretic methods at any given level of sophistication, from the viewpoint of a classically trained mathematician, scientist, engineer, or technologist. Bill Lawvere's early pre-topos (in the nontechnical sense) work on the categorical axiomatization of sets creates something of a straw to grasp at for non-category theorists looking for insights into this question. But while it is natural to view topos theory as a maturation of this program, there is a bifurcation in the maturation process that should be kept in mind. Toys are the natural playthings of the institution of childhood. Maturation can shift the focus of that energy either to more sophisticated toys (and I lump preoccupation with fast cars together with love of good engineering or architectural design here) or to the support of institutions -- teaching, management, etc. This is not purely bimodal but is something of a spectrum, with entrepreneurs, technology visionaries, research university professors, and project team leaders occupying intermediate positions along it. Taking ordinary sets as the toys of late 19th century foundations, it seems to me that set theory and algebra stand in an analogous relationship. Set theory continues the early preoccupation with sets at a far more mature and technically demanding level. I'm not suggesting that set theory's motto should be "he who dies with the largest cardinal wins," but rather that its success has created a certain technically focused inertia that has sustained set theory for over a century in close to its original form as conceived by its founders. Algebra is more institutional in its outlook. Whereas set theory sits patiently inside the same house it was born in, algebra can view that house from outside if it wishes. In this regard I lump category theory together with algebra, with category theory strongly supporting the inside-out perspective via the Duality Principle as generalized from posets to categories (reverse the arrows -- the Duality Principle is like glass, so transparent as to make its substance invisible). This is actually easier for algebra as it was not born in that house, predating set theory by half a century. The symmetric group of finite order n is more easily seen to have an underlying set than say a Lie algebra, and one might even take the view that Lie algebras have been unjustly dragged into the house and taken hostage by set theory, with pointset topology intervening to prevent their torture. Isbell's example of the intersection of the rationals and the irrationals as a nonvacuous locale makes the point that a faithful functor to Set^op, as a house on the other side of the street, might offer a more hospitable home than the Set house for some denizens of mathematics. The fact that many algebraists still have a strongly set-theoretic view of their world is more inertial than intrinsic, as evidenced by an increasing willingness of the mainstream algebra community to accept categorical perspectives as a legitimate point of view. This is not to say a set theoretic outlook on algebra is bad, rather that it puts traditional algebraists in a middle position not unlike that of technology visionaries or team leaders. But without recognition of the Duality Principle, a geometer such as Bill Thurston, who as then-director of MSRI kicked off the 1989 UACT meeting with the insightful confession that he felt ill contemplating Set^op, is missing a major part of the big picture, just as is the visionary entrepreneur who fails to see the need for marketing expertise. It should be a rite of passage to category theory that the initiate be told that a topos is not intended as a universe of sets so much as of institutions (again in a non-technical sense) of a particular character. Even those who insist that a graph is a set (on the ground that everything is a set) will surely allow that it is a set with structure. And in fact they would not object to calling a graph a pair of sets V and E of vertices and edges as long as you humored them by allowing that it was therefore the set {{V,E},{V}}, as the von Neumann encoding of the pair (V,E) as a single set. But if you could put this encoding in perspective for them as being less central (in whatever sense impresses them: pedagogical, natural, etc.) to the graph concept than the basic sets V and E themselves, you are off to a good start explaining what toposes are about. If this post had been directed to non-category theorists it would be necessary to make it somewhat longer. The present audience should need nothing beyond the distinction between sets per se such as V and E vs. presheaves of sets to continue it to its intended conclusion (though it's a nice question how many conclusions might result). Those with experience of hostile appointment and promotion committees may already have had some practice with that. Simplicial complex theory as an extension of reflexive graph theory (both as petits toposes) is a nice next step avoiding the implication that graphs constitute the core paradigm here. The same needs to be pointed out concerning the role of reflexive graphs as the algebraic stepping stone from sets to categories, which is only the beginning of that story when one looks ahead to n-categories. While I'm still unclear as to the optimal order of things for training the working mathematician in category theory, a short introduction to category theory for the benefit of the other kind of mathematician might profitably organize itself around a manageable part of the background material presumed by the above point of view, with the goal being insight into why presheaves are not sets and how toposes abstract them. Unless of course you're one of those rugged left-field individualists who believe that linearly distributive categories are more important than toposes. ;) Vaughan Pratt 14-Mar-2005 11:01:08 -0400,3248;000000000000-00000000 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 14 Mar 2005 11:01:08 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.44) id 1DAqxJ-0001zr-UA for categories-list@mta.ca; Mon, 14 Mar 2005 10:54:06 -0400 Date: Sat, 12 Mar 2005 14:48:53 -0800 From: Vaughan Pratt Reply-To: pratt@cs.stanford.edu Organization: Stanford University User-Agent: Mozilla Thunderbird 0.9 (Windows/20041103) X-Accept-Language: en-us, en MIME-Version: 1.0 To: categories@mta.ca Subject: categories: Re: Categories as a "foundation" for math References: <4232BB31.14303.209BD6@localhost> In-Reply-To: <4232BB31.14303.209BD6@localhost> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: > An infinite cardinal a is called a strong limit > cardinal, if b category of all sets of cardinality < a is en elementary topos, In the definition of strong limit cardinal (with 2^b < a of course), some authors set a lower bound of either nonzero or uncountable on strong limit cardinals, seemingly arbitrarily. In view of the above connection, presumably a toposopher would argue for the former lower bound and against the latter. (One certainly wouldn't want to overlook the topos of finite sets, and, lacking Omega, the empty category cannot be a topos.) The inclusion of "nonzero" somewhere in the definition of strong limit cardinal would therefore nail down that detail at least for topos theory. That goes for Elephant A.2.1.2, which overlooks the case \kappa=0 by giving the above as the definition of what Peter J. calls a "limit power cardinal." (This seems an odd name for "strong limit cardinal" btw, given that no strong limit cardinal can be a power cardinal in the sense of arising as 2^a for some cardinal a. "Power limit cardinal" maybe, but why proliferate terminology?) If one were looking for differences in outlook between set theory and topos theory, the stranger notion of limit cardinal might be a more fruitful object to contemplate. A limit cardinal is defined as for a strong limit cardinal with a+ in place of 2^a, where a+ denotes the least cardinal strictly greater than a. Whereas 2^a is a perfectly good notion in a topos, with Cantor's theorem making it a fine successor operation for transfinite cardinals, a+ is the sort of thing I would have thought only a fan of ZFC could love. Or is there in fact a constructively acceptable notion of limit cardinal that is weaker than strong limit cardinal? For a constructivist the very need for "strong" in the definition of limit cardinal seems like a bad hangover from set theory. On the relevance of replacement to the relationship between set theory and category theory, how much better off are "working mathematicians" with replacement as a tool of their trade than with category theory? My impression is that category theory is used increasingly more in applied mathematics these days. Is there a comparable trend for replacement? Vaughan Pratt 14-Mar-2005 20:16:35 -0400,1428;000000000001-00000000 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 14 Mar 2005 20:16:35 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.44) id 1DAzhu-000365-Pq for categories-list@mta.ca; Mon, 14 Mar 2005 20:14:46 -0400 Date: Mon, 14 Mar 2005 20:10:49 -0400 (AST) From: Bob Rosebrugh To: categories Subject: categories: TAC: New Editors Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk The editors of Theory and Applications of Categories are pleased to announce that Professors Richard Blute of the University ot Ottawa, Ezra Getzler of Northwestern University and Brooke Shipley of the University of Illinois at Chicago have joined the Editorial Board. Articles for consideration by TAC may be submitted to any member of the Editorial Board. Professor John Baez has resigned from the Editorial Board, and the editors thank him for his service over the past ten years. best wishes, Bob Rosebrugh =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= Robert Rosebrugh, Professor Department of Mathematics and Computer Science Mount Allison University 67 York Street Sackville, NB E4L 1E6 Canada rrosebrugh@mta.ca www.mta.ca/~rrosebru +1-506-364-2530 fax: -364-2583 14-Mar-2005 20:16:35 -0400,1965;000000000001-00000000 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 14 Mar 2005 20:16:35 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.44) id 1DAzfu-0002y4-K3 for categories-list@mta.ca; Mon, 14 Mar 2005 20:12:42 -0400 Date: Mon, 14 Mar 2005 18:13:19 +0000 (GMT) From: Paul B Levy To: categories@mta.ca Subject: categories: Re: Categories as a "foundation" for math In-Reply-To: Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk > > An infinite cardinal a is called a strong limit > > cardinal, if b > category of all sets of cardinality < a is en elementary topos, > > In the definition of strong limit cardinal (with 2^b < a of course), > some authors set a lower bound of either nonzero or uncountable on > strong limit cardinals, seemingly arbitrarily. In view of the above > connection, presumably a toposopher would argue for the former lower > bound and against the latter. (One certainly wouldn't want to overlook > the topos of finite sets, and, lacking Omega, the empty category cannot > be a topos.) The inclusion of "nonzero" somewhere in the definition of > strong limit cardinal would therefore nail down that detail at least for > topos theory. While we're about it, let's include "greater than 1" in the definition of regular cardinal please, so that 2 and omega are regular but 0 and 1 are not. This would ensure that, for each regular cardinal kappa, the endofunctor on Set taking A to the set of subsets (or nonempty subsets) of A of size < kappa is a monad. To put it another way, regularity means in essence "closed under dependent sum", and singleton is the unit of dependent sum. Paul 16-Mar-2005 11:16:08 -0400,5626;000000000000-00000000 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 16 Mar 2005 11:16:08 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.44) id 1DBaFE-0001OK-MJ for categories-list@mta.ca; Wed, 16 Mar 2005 11:15:36 -0400 Date: Tue, 15 Mar 2005 22:00:28 +0100 To: paola.bruscoli@Inf.TU-Dresden.DE From: Paola Bruscoli Subject: categories: Structures and Deduction Workshop 2nd cfp - ICALP'05 Satellite Content-Type: text/plain; charset="us-ascii" ; format="flowed" Sender: cat-dist@mta.ca Precedence: bulk Message-Id: (ICALP Workshop-Lisbon July 16-17, 2005) STRUCTURES AND DEDUCTION The quest for the essence of proofs http://www.prooftheory.org/sd05 Submissions page is now open! http://www.easychair.org/SD05/submit/ This meeting is about new algebraic and geometric methods in proof theory, with the aim of expanding our ability to manipulate proofs, eliminate bureaucracy from deductive systems, and ultimately provide: 1) a satisfying answer to the problem of identity of proofs and 2) tools for improving our ability to implement logics. Stimulated by computer science, proof theory is progressing at fast pace. However, it is becoming very technical, and runs the risk of splitting into esoteric specialties. The history of science tells us that this has happened several times before, and that these centrifugal tendencies are very often countered by conceptual reunifications, which occur when one is looking at a field after having taken a few steps back. Some emerging ideas are showing their unifying potential. Deep inference's atomization of deductions simplifies and unifies the design of deduction systems; it provides unprecedented plasticity to proofs and has injected new impetus into the theory of proof nets. New proof nets, and new associated semantics, are giving surprising insight about the very subtle relationship between categories and proofs, for example in the formerly intractable case of classical logic. The field of deduction modulo, which turns out to be very much in the spirit of deep inference, decreases our dependency on the syntactic presentation of functional objects, and brings us closer to their intrinsic nature, even from the computational point of view. After studying all those trees for years we at last have the impression of looking at the forest. The core topics are organised along the axis: algebraic semantics deduction of proofs deep inference modulo game semantics operads and specification <--> structads <--> proof nets proof search calculus of deductive structures implementations proof nets This workshop aims at being a meeting point for all those who are interested in decreasing the dependency of logic from low-level syntax. The list of topics above is not exhaustive: if you feel you can contribute to the discussion along the broad lines outlined above, please submit your contribution. SUBMISSION, IMPORTANT DATES AND PUBLICATION Contributions such as work in progress, programmatic/position papers, tutorials, as well as regular papers are more than welcome. We will favor the former over regular papers that seem to us to be minor contributions, although we will definitely not reject major contributions! Submissions should be formatted with the LNCS LaTeX style, and should take between two and fifteen pages, to allow the committee to assess their merits with reasonable effort. This limit can be relaxed for the versions that will be presented at the workshop, depending on the total bulk of the accepted contributions. We want to make clear that contributions from members of the PC are allowed. Contributions should be submitted electronically at the following site (powered by EasyChair, thanks to Andrei Voronkov): http://www.easychair.org/SD05/submit/ submission: 15.4.2005 notification: 22.5.2005 final version: 10.6.2005 The volume of proceedings will be made available elctronically, allowing authors to keep their copyrights. The issue of printed proceedings is still under discussion. INVITED SPEAKERS Martin Hyland (Cambridge) Claude or Helene Kirchner (LORIA & INRIA Lorraine, Nancy) Dale Miller (INRIA Futurs and LIX, Paris) David Pym (Bath and HP Labs) PROGRAM COMMITTEE Paola Bruscoli (Dresden) Pietro Di Gianantonio (Udine) Gilles Dowek (LIX & Ecole Polytechnique, Paris) Roy Dyckhoff (St Andrews) Rajeev Gore' (NICTA and ANU, Canberra) Francois Lamarche (LORIA & INRIA Lorraine, Nancy) -- Chair Luke Ong (Oxford) Prakash Panangaden (McGill) Michel Parigot (CNRS, Paris) Charles Stewart (Dresden) Thomas Streicher (Darmstadt) LOCATION Lisbon, July 16-17, 2005; the workshop is a satellite of the ICALP 2005 conference. HOW TO REGISTER A registration fee for attending the workshop will be paid to the ICALP Workshop general chair; no fee for participating in the main conference should be necessary, while participation in both conference and workshop should entitle to special discounts. Please visit the ICALP web site for up-to-date, precise information: ORGANISERS Paola Bruscoli (Dresden) Francois Lamarche (LORIA & INRIA Lorraine, Nancy) -- Chair Charles Stewart (Dresden) 16-Mar-2005 11:16:08 -0400,1933;000000000000-00000000 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 16 Mar 2005 11:16:08 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.44) id 1DBa91-0000Ee-TW for categories-list@mta.ca; Wed, 16 Mar 2005 11:09:11 -0400 Date: Mon, 14 Mar 2005 22:14:37 -0800 From: Toby Bartels To: categories@mta.ca Subject: categories: Re: Categories as a "foundation" for math Message-ID: <20050315061437.GA4323@math-rs-n03.ucr.edu> References: <4232BB31.14303.209BD6@localhost> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: Sender: cat-dist@mta.ca Precedence: bulk Vaughan Pratt wrote in part: >A limit cardinal is defined as for a >strong limit cardinal with a+ in place of 2^a, where a+ denotes the >least cardinal strictly greater than a. Whereas 2^a is a perfectly good >notion in a topos, with Cantor's theorem making it a fine successor >operation for transfinite cardinals, a+ is the sort of thing I would >have thought only a fan of ZFC could love. Without using any form of Choice (not even Excluded Middle), you can define X+ (for any set X) as the set of ordinal numbers (where an ordinal number is a set equipped with a well founded, transitive, extensive binary relation; modulo isomorphism) that can be injected (as sets) into X; this is a quotient set (as we mod out by isomorphism of sets equipped with binary relations) of a subset (as we pick only the well founded, transitive, extensive binary relations) of the power set of X + X^2 (as we pick a subset of X and a binary relation on X that we restrict to the chosen subset). There is a big analogy that runs like this: a+ : 2^a :: aleph : beth :: Burali-Forti : Cantor :: more? X+ is the _Hartogs_number_ of X. -- Toby 16-Mar-2005 11:18:09 -0400,5075;000000000001-00000000 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 16 Mar 2005 11:18:09 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.44) id 1DBaHU-0001ib-AN for categories-list@mta.ca; Wed, 16 Mar 2005 11:17:56 -0400 Date: Wed, 16 Mar 2005 09:24:25 -0500 From: Nath Rao Reply-To: rao.3@osu.edu User-Agent: Mozilla Thunderbird 1.0 (Macintosh/20041206) X-Accept-Language: en-us, en MIME-Version: 1.0 To: categories@mta.ca Subject: categories: Re: Categories as a "foundation" for math References: <4232BB31.14303.209BD6@localhost> In-Reply-To: <4232BB31.14303.209BD6@localhost> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Reinhard.Boerger@FernUni-Hagen.de wrote: > As I see it, the problem is with the replacement scheme. Even if > you start with ZF and classical logic, you have problems to > express replacement in terms of first-order properties of the > category of sets. An infinite cardinal a is called a strong limit > cardinal, if b category of all sets of cardinality < a is en elementary topos, > regardless whether a is regular or not; regular strong lomit > cardinals are inaccessible cardinals. Replacement should yield > regularity of a, but how to express it? I have always wondered why when talking about toposes from sets, people only mention "all sets of cardinality < something". Unless you have classes of some kind (with the attendant problem of making sense of categories of categories), it doesn't even make sense. If a is any limit ordinal, the category of all sets of rank < a is a topos. [for those who might have forgotten: Define V_a for >ordinals< a by transfinite induction as V_0 is the empty set, V_{a+1} is the power set of V_a, if a is a limit ordinal V_a is the union of V_b for b < a. Rank is very different from cardinality: {V_a} has rank a+1, which can be very large, but has cardinality 1, as small as it can get for any non-empty set.] [Another parenthetical remarks may be in order: I am making the customary intentional distinction between the >ordinal< omega and the >cardinal< aleph_0. This is useful notationally as omega*2 refers to ordinal multiplication (so it has the same order type as omega \times 2 with lexicographic order) and should not confused with cardinal multiplication aleph_0 * 2, which of course is just aleph_0. I mention this explicitly because, once, I saw V_{omega*2} taken to be as "the 'set' of all sets of cardinality < omega*2", whatever that may mean. Also, recently I noticed that in "Sketches of an Elephant", the first infinite cardinal referred to as $\omega$.] If a is a limit ordinal, but not the first, then V_a has a natural number object. So, in some sense V_{omega*2} is (very) small boolean topos with a natural number object. I find it useful to keep this example in mind when thinking about boolean toposes. For example, I would be very surprised if anything like Adams completion or Bousefield completion exist V_{omega*2}. [Bousfield completion can be made functorial before passing to the homotopy category. This is an useful fact. But the original aim can be expressed without functors: For any space X, there is a map X \to Y such that ...] So, I find the claim that mathematics that does not refer to 'all sets' etc can be done in toposes. Switching back to the original topic: Given ZF(C) - replacement, Fraenkel's version of replacement will prove the same theorems (just about sets) as reflection: To ZF(C) - replacement, add the assumption of an internal universe V that is elementarily equivalent to the 'whole universe'. It would be interesting to look at a topos theoretic version, but I have no idea of what the language of an internal topos means, much less how to say such things as "the natural number object of the internal topos T is the natural number object of the containing topos' [perhaps it is "N \times T \to T" is a small fibration, and the corresponding internal category of T is the natural number of object of T", but what is an internal category of an internal category?] Note that in the above, V will be an V_a, but a need not be a cardinal; for all I know, it may be consistent for a to have cofinality omega as an ordinal of the "big universe". Thus inaccessibility is a red herring when talking about a universe of sets that satisfy ZFC. BTW, do we know if Fraenkels' version of replacement (replacement for predicative functions as opposed to replacement for arbitrary functions) is inadequate for theorems "in the wild" that talk only about sets? [So theorems about "the category of all ...", or, say, model categories where the factorizations need not be given by predicative functions, do not count.] In other words, does mathematics really need Grothendieck universes? Nath Rao 16-Mar-2005 11:19:02 -0400,7295;000000000000-00000000 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 16 Mar 2005 11:19:02 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.44) id 1DBaIL-0001oO-Lg for categories-list@mta.ca; Wed, 16 Mar 2005 11:18:49 -0400 Date: Tue, 15 Mar 2005 11:08:35 -0500 (EST) From: F W Lawvere X-Sender: wlawvere@joxer.acsu.buffalo.edu Reply-To: wlawvere@acsu.buffalo.edu To: categories@mta.ca Subject: categories: replacement In-Reply-To: <4232BB31.14303.209BD6@localhost> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Dear colleagues, Reinhard Boerger has appropriately raised (as others before) the question of the relation of "replacement" with categories of sets. As stated in my 1964 - 1965 papers and as understood already before 1920 (1) closure under exponentiation is sufficient for a foundation for mathematics if by mathematics one means algebraic geometry, functional analysis, dynamical systems, partial differential equations, combinatorics, etc.; (2) but closure under exponentiation is not sufficient for certain speculations in which set theorists had developed an interest; if one wished, one could introduce stronger axioms. From the standpoint of a theory in the Frege-Peano style, it might appear that the replacement schema is the principal means for justifying those speculations. However, the left adjoint (Ua incl b iff a incl Pb) to the power set operation P is equally important, exploiting as it does the hidden structure as a FAMILY of sets that any set of such a theory has. The usual "image" version of the replacement operation does not give directly any sets of cardinality larger than its inputs; only in the case where the set it produces is "really" a family (of increasingly large sets, even if few) the union axiom can then give a larger result. On the other hand (assuming the axiom of choice) it is through producing larger cardinals that stronger axioms can express their strength. Thus, for a principle combining the union and replacement principles in a context where families are explicitly recognized as such, I proposed: If E ---> B is such that B exists and the fibers E sub b exist for each b, then E exists. Note that the usual way in geometry (hence in topos theory) for expressing a family indexed by B is by such a fibration over B. (In case the sets in the family are given as subsets of a set X, their union is a quotient of E modulo the usual "nerve" resolution.) Most families that arise in mathematics are easily put into this form, i.e. are not abstractly imposed from outside and hence do not need extra axioms to insure their existence; therefore the "internal limits and colimits" in topos theory can work well as tools for geometrical construction: they are honest adjoints but applied only to "internal families" and universal among internal families. The above existence principle is intended to have several interpretations, depending on how many and what kind of families are to be representable as fibers in the geometrical way. Besides the tautological "internal" answer (sufficient for most purposes) there are two distinct kinds of answers to the question: "From where do we take the families E to which we want to apply the "existence" assertion?" The subjective answer, attributed to Fraenkel and followed by most books on set theory is that we take E from the world of formulas. (For category theory we need to consider formulas of category theory (not epsilon theory), having one free variable ranging over points of B and another ranging over objects of the category and enjoying the "function" hypothesis up to isomorphism.) The other (objective) answer, similar in spirit to the (finitely axiomatizable) Bernays-Goedel theory, is that E lives initially in another category into which the one we are describing is embedded (either as a subcategory or as an internal category object). Such an embedding may or may not be full; when it is, then our objective "replacement" principle is revealed as equivalent to inaccessibility (of the category). As explained in the Appendix of the book "Sets for Mathematics" the demand for more sets has its source in the need to objectively parameterize mathematical objects. I can only recall two occasions where topos theorists needed more parameterizers than those obviously guaranteed by exponentiation and boundedness of geometric morphisms; in such situations one can explicitly assume more about the toposes under investigation (guided by available experience in avoiding inconsistencies). The best context for discussing these matters is the category of categories. However, assumptions of large cardinal strength can be applied equally to a category of categories and to the corresponding topos of discrete categories, since categories can be represented as finite diagrams of discrete categories. Greetings, Bill Lawvere REFERENCES: Elementary Theory of the Category of Sets, Proceedings of the National Academy of Science 52, No. 6 (December 1964), 1506-1511. An Elementary Theory of the Category of Sets, Preprint, University of Chicago, 1965, 32 pages. The Category of Categories as a Foundation for Mathematics, La Jolla Conference on Categorical Algebra, Springer Verlag (1966), 1 - 20. "Sets for Mathematics" with Robert Rosebrugh Cambridge University Press, 2003. On Sat, 12 Mar 2005 Reinhard.Boerger@FernUni-Hagen.de wrote: > Hello, > > Carl Futia wrote: > > > Is it known just how much mathematics can be done using Lawvere's > > axiom scheme? My confusion on this point arises partly from a remark > > by Gray in his paper "The categorical comprehension scheme" in which > > he asserted that Lawvere's axioms couldn't do all that was claimed for > > them. Of course all of this predates the recognition that an > > elementary topos (with nn object) can be treated as a "universe of > > sets". > > As I see it, the problem is with the replacement scheme. Even if > you start with ZF and classical logic, you have problems to > express replacement in terms of first-order properties of the > category of sets. An infinite cardinal a is called a strong limit > cardinal, if b category of all sets of cardinality < a is en elementary topos, > regardless whether a is regular or not; regular strong lomit > cardinals are inaccessible cardinals. Replacement should yield > regularity of a, but how to express it? The easiest way to find a > singular strong limit cardinal a is to start with an arbitrary infinite > cardinal b(0), define b(n+1):=2^b(n), and a the sum of al b(n) for all > natural number n. Then a is obviously singular because it is > uncountable but the sum of countably many strictly smaller > cardinals; a is a strong limit cardial because every cardinal > > Greetings > Reinhard 17-Mar-2005 17:13:39 -0400,2360;000000000000-00000000 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 17 Mar 2005 17:13:39 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.44) id 1DC2BA-0004Mx-NZ for categories-list@mta.ca; Thu, 17 Mar 2005 17:05:16 -0400 Date: Wed, 16 Mar 2005 16:30:20 +0000 (GMT) From: Paul B Levy To: categories@mta.ca Subject: categories: PhD studentships Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Dear all, Funding is available for PhD studentships in theory/semantics at the University of Birmingham. We have a vibrant group of researchers across the spectrum from programming languages to mathematical foundations. Our work includes game, domain, effect, pointer and categorical semantics, logic, topology and much else besides; and the funding is not tied to particular projects. As our current students will confirm, we have a lively and friendly atmosphere. The group is burgeoning right now, and includes - Martin Escardo (domain theory, topology, semantics and more) - Dan Ghica (interaction models of computation and applications to software analysis) - Achim Jung (domain theory, semantics, topology) - Paul Blain Levy (denotational semantics and its problems) - Uday Reddy (programming logic and formal methods, object-oriented programming) - Eike Ritter (type theory, computational logic, automatic verification) - Hayo Thielecke (types and logics for effects in programming languages) - Steve Vickers (relating topology, computer science and logic, especially using toposes and locales) This year, we're hosting both Midlands Graduate School and Mathematical Foundations of Progamming Semantics. It's all happening here - come and be part of it! Please don't hesitate to send us any queries, whether about research, money or anything else. Application information is at http://www.cs.bham.ac.uk/study/postgraduate-research/research_applications.html regards Paul -- Paul Blain Levy email: pbl@cs.bham.ac.uk School of Computer Science, University of Birmingham Birmingham B15 2TT, U.K. tel: +44 121-414-4792 http://www.cs.bham.ac.uk/~pbl 17-Mar-2005 17:13:39 -0400,3995;000000000000-00000000 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 17 Mar 2005 17:13:39 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.44) id 1DC2De-0004We-PL for categories-list@mta.ca; Thu, 17 Mar 2005 17:07:50 -0400 From: Thomas Streicher Message-Id: <200503171210.j2HCAfot025530@fb04305.mathematik.tu-darmstadt.de> Subject: categories: replacemnt To: categories@mta.ca Date: Thu, 17 Mar 2005 13:10:40 +0100 (CET) X-Mailer: ELM [version 2.4ME+ PL100 (25)] MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk As the topic of Replacement versus topos logic (i.e. higher order intuitionistic arithmetic) has come up (again) it might be appropriate to point at a paper of mine (which has been accepted for the proceedings of "From Sets and Types to Topology and Analysis: Towards Practicable Foundations for Constructive Mathematics" (L.~Crosilla, P.~Schuster, eds.), Oxford University Press, forthcoming) and can be found at www.mathematik.tu-darmstadt.de/~streicher/NOTES/UniTop.ps.gz In this paper I discuss how to extend the notion of toposes in order to capture the relevant part of the set-theoretic Replacement Axiom. I suggest to add so called universes to toposes which allow one to quantify over small sets (the elements of the universe). This notion of universe has been developed (in a predicative setting) by Martin-Loef in the early 70ies and in the 2nd half of the eighties there was quite some activity to give semantics to such universes using categorical notions. Actually, the categorical notion of universe was introduced already in J. B'enabou "Problemes dans les topos" (Louvain-la-Neuve Report, 1973) My conclusion is that most of the uses of replacement are to define (by recursion) families of sets indexed by some index set (e.g. P^n(X) for n \in N) which is impossible in toposes. Alas, in my note it is not settled whether this notion of universe allows one to build models for IZF as in Joyal and Moerdijk's "Algebraic Set Theory" where they use a slightly different notion of universe (see dicussion on p.12 of my note for more details). Of course, I agree that for most mathematics higher order arithmetic suffices (and actually subsystems of 2nd order arithmetic suffice!). In classical mathematics theorems requiring Replacement are typically from Descriptive Set Theory as e.g. Borel Determinacy (BD). The situation is that ZF proves BD but Z (i.e. ZF without replacement) does not. However, for IZF (intuit. set theory) such examples are not known (Set validates BD but the realizability model for IZF does not!). However, there is a very nice example from Computer Science due to Alex Simpson in "Computational Adequacy for Recursive Types in Models of Intuitionistic Set Theory" In Annals of Pure and Applied Logic, 130:207-275, 2004 where he shows that relative to the axioms of SDT (Synthetic Domain Theory) IZF proves the existence of solutions of recursive domain equations whereas higher order arithmetic doesn't. (The reason is that for solutions of such recursive domain equations one has to construct by recursion families of domains which are not a priori contained in an already given domain). But for this pleasant example the existence of a universe (hosting all domains) would already be sufficient. But existence of solutions of domain equations cannot be formulated in the language of higher order arithmetic itself. Thus, from this point of view it is still open whether there exist (purely "mathematical") statements expressible in the language of higher order arithmetic (like e.g. Borel determinacy) which can be proved in IZF but not in intuit.(!) higher order arithmetic. I would be most grateful if anyone could tell me such an example! Thomas 23-Mar-2005 21:52:32 -0400,973;000000000000-00000000 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 23 Mar 2005 21:52:32 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.44) id 1DEHPc-00072o-D4 for categories-list@mta.ca; Wed, 23 Mar 2005 21:45:28 -0400 Message-Id: <6.1.2.0.1.20050321173953.01a23a50@mat.uc.pt> X-Sender: picado@mat.uc.pt X-Mailer: QUALCOMM Windows Eudora Version 6.1.2.0 Date: Mon, 21 Mar 2005 17:43:18 +0000 To: categories@mta.ca From: Jorge Picado Subject: categories: 81st PSSL: reminder Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Sender: cat-dist@mta.ca Precedence: bulk 81st Peripatetic Seminar on Sheaves and Logic University of Coimbra, Portugal April 9-10, 2005 Abstract submission deadline: March 22, 2005 Web page: http://www.mat.uc.pt/~categ/events/pssl.html The organisers, Manuela Sobral Maria Manuel Clementino Jorge Picado Lurdes Sousa 23-Mar-2005 21:52:32 -0400,5344;000000000000-00000000 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 23 Mar 2005 21:52:32 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.44) id 1DEHQh-00076s-SM for categories-list@mta.ca; Wed, 23 Mar 2005 21:46:35 -0400 Date: Tue, 22 Mar 2005 21:19:43 +0100 (CET) From: Uli Fahrenberg To: categories@mta.ca Subject: categories: First CfP: GETCO 2005 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=iso-8859-15; format=flowed Content-Transfer-Encoding: quoted-printable Sender: cat-dist@mta.ca Precedence: bulk Seventh workshop on Geometric and Topological Methods in Concurrency GETCO 2005 Affiliated with CONCUR 2005 Venue: San Francisco, California Conference dates: CONCUR: 23-26 August 2005 GETCO: 21 August 2005 Call for Papers Scope The main mathematical disciplines that have been used in computer science are discrete mathematics (especially graph theory and ordered structures), logics (mostly proof theory for all kinds of logics, classical, intuitionistic, modal etc.) and category theory (cartesian closed categories, topoi etc.). General Topology has also been used for instance in denotational semantics, with relations to ordered structures in particular. Recently, ideas and notions from mainstream "geometric" topology and algebraic topology have entered the scene in Concurrency Theory and Distributed Systems Theory (some of them based on older ideas). They have been applied in particular to problems dealing with coordination of multi-processor and distributed systems (see the historical note ). Among those are techniques borrowed from algebraic and geometric topology: Simplicial techniques have led to new theoretical bounds for coordination problems. Higher dimensional automata have been modeled as cubical complexes with a partial order reflecting the time flows, and their homotopy properties allow to reason about a system's global behaviour. The GETCO workshops aim at bringing together researchers from both th= e mathematical (geometry, topology, algebraic topology etc.) and computer scientific side (concurrency theorists, semanticians, algorithmicians, researchers in distributed systems etc.) with an active interest in these or related developments. Topics include (but are not limited to): * Algorithmics for Concurrent or Distributed Systems * Fault-tolerant Protocols for Distributed Systems * Semantics * Concurrency Theory * Model-checking * Abstract Interpretation * Geometric/Topological models * Applications of algebraic topology * Category theory Paper submission Submissions to the workshop may be of two forms: * Short abstracts: up to 4 pages, in format A4, typeset 11 points * Full papers: up to 12 pages, in format A4, typeset 11 points (excluding bibliography and technical appendices) Both forms of submission should include a separate page with the following information: title, author(s), corresponding author, contac= t information and a 12-15 lines summary. Simultaneous submission to other conferences or journals is only allowed for short abstracts. Electronic submission is strongly encouraged. The paper or abstract should be sent by e-mail in the form of a postscript or PDF file to both the addresses uli@math.aau.dk and Haucourt@cea.fr. The accompanying page should be sent in a separate email message. If surface mail has to be used, then 3 copies of the paper/abstract should be sent to: Emmanuel Haucourt, DTSI/SLA, bat. 528, CEA Saclay, 91191 Gif-sur-Yvette, France. The deadline for submissions is 1 June 2005. Important Dates * Deadline for submission: 1 June 2005 * Notification of acceptance: 7 July 2005 * Final version (for the preproceedings): 27 July 2005 * CONCUR: 23-26 August 2005 * GETCO: 27 August 2005 Publication We expect that as in the years before, the preliminary proceedings of the workshop will published in the BRICS Notes series, and the proceedings with Electronic Notes in Theoretical Computer Science. Programme Committee * Patrick Cousot, Ecole Normale Sup=E9rieure, France * Lisbeth Fajstrup, Aalborg University, Denmark * Eric Goubault, Commissariat =E0 l'Energie Atomique, France * Maurice Herlihy, Brown University, Providence, RI, USA * Kim G. Larsen, Aalborg University, Denmark * Martin Raussen, Aalborg University, Denmark Contact Additional information can be obtained from the GETCO website at http://www.math.aau.dk/~uli/getco05 or by taking contact to Ulrich Fahrenberg Department of Mathematical Sciences, Aalborg University Fredrik Bajers Vej 7G 9220 Aalborg East Phone: +45 96 35 88 00 Fax: +45 98 15 81 29 Email: uli@math.aau.dk 23-Mar-2005 21:52:32 -0400,4687;000000000000-00000000 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 23 Mar 2005 21:52:32 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.44) id 1DEHOu-0006zv-2N for categories-list@mta.ca; Wed, 23 Mar 2005 21:44:44 -0400 Date: Mon, 21 Mar 2005 10:07:20 +0000 (GMT) From: Andrzej Murawski To: Andrzej Murawski Subject: categories: CSL'05 Final Call for Papers Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=X-UNKNOWN Content-Transfer-Encoding: QUOTED-PRINTABLE Sender: cat-dist@mta.ca Precedence: bulk CALL FOR PAPERS CSL'05, University of Oxford, 22-25 August 2005 http://web.comlab.ox.ac.uk/oucl/conferences/CSL05/ THE EVENT Computer Science Logic (CSL) is the annual conference of the European Association for Computer Science Logic (EACSL). The 14th Annual Conference (and 19th International Workshop), CSL2005, will take place in the week 22 - 25 August 2005; it will be organised by the Computing Laboratory at the University of Oxford. SCOPE The conference is intended for computer scientists whose research activities involve logic, as well as for logicians working on issues significant for computer science. Suggested topics of interest include: automated deduction and interactive theorem proving, constructive mathematics and type theory, equational logic and term rewriting, modal and temporal logic, model checking, logical aspects of computational complexity, finite model theory, computational proof theory, logic programming and constraints, lambda calculus and combinatory logic, categorical logic and topological semantics, domain theory, database theory, specification, extraction and transformation of programs, logical foundations of programming paradigms, linear logic, higher-order logic. INVITED SPEAKERS Matthias Baaz (U. of Technology, Vienna) Ulrich Berger (U. of Wales, Swansea) Maarten Marx (U. of Amsterdam) Anatol Slissenko (Universit=E9 Paris 12) SUBMISSION The proceedings will be published in the Springer Lecture Notes in Computer Science. Papers accepted by the Programme Committee must be presented at the conference by one of the authors, and final copy prepared according to Springer's guidelines. Submitted papers must be in Springer's LNCS style and of no more than 15 pages, presenting work not previously published. They must not be submitted concurrently to another conference with refereed proceedings. The PC chair should be informed of closely related work submitted to a conference or journal by 1 April 2005. Papers authored or coauthored by members of the Programme Committee are not allowed. Submitted papers must be in English and provide sufficient detail to allow the programme committee to assess the merits of the paper. Full proofs may appear in a technical appendix which will be read at the reviewer's discretion. The title page must contain: title and author(s), physical and e-mail addresses, identification of the corresponding author, an abstract of no more than 200 words, and a list of keywords. IMPORTANT DATES Deadline for abstracts 25 March, 2005 Deadline for papers=09 1 April, 2005 Notification=09=09 15 May, 2005 Final versions due=09 1 June, 2005 ACKERMANN AWARD The EACSL Board has decided to launch the Ackermann Award: The EACSL Outstanding Dissertation Award for Logic in Computer Science. The first awards will be presented to the recipients at CSL'05. Further details of the Award can be found at =09 http://www.dimi.uniud.it/~eacsl/award.html PROGRAMME COMMITTEE Albert Atserias (Universitat Polit=E8cnica de Catalunya) David Basin (Eidgen=F6ssische Technische Hochschule Z=FCrich) Martin Escardo (U. of Birmingham) Zoltan Esik (U. of Szeged) Martin Grohe (Humboldt-Universitat zu Berlin) Ryu Hasegawa (U. of Tokyo) Martin Hofmann (Ludwig-Maximilians-Universit=E4t M=FCnchen) Ulrich Kohlenbach (Darmstadt U. of Technology) Orna Kupferman (Hebrew U. of Jerusalem) Paul-Andre Mellies (CNRS / Universit=E9 Paris 7) Aart Middeldorp (U. of Innsbruck, Austria) Dale Miller (INRIA / Ecole Polytechnique) Damian Niwinski (U. of Warsaw) Peter O'Hearn (Queen Mary, U. of London) Luke Ong (U. of Oxford, Chair) Alexander Rabinovich (U. of Tel Aviv) Thomas Schwentick (Philipps-Universit=E4t Marburg) Alex Simpson (U. of Edinburgh) Nicolai Vorobjov (U. of Bath) Andrei Voronkov (U. of Manchester) 23-Mar-2005 21:52:32 -0400,2349;000000000000-00000000 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 23 Mar 2005 21:52:32 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.44) id 1DEHRg-0007AW-4k for categories-list@mta.ca; Wed, 23 Mar 2005 21:47:36 -0400 Message-Id: Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Date: Wed, 23 Mar 2005 14:34:04 +0100 To: categories@mta.ca From: Marco Grandis Subject: categories: Preprint: Modelling fundamental 2-categories for directed homotopy Sender: cat-dist@mta.ca Precedence: bulk The following preprint is available. It is a sequel of my previous work on the fundamental category of a directed space, announced on this list in May 2004. M. Grandis Modelling fundamental 2-categories for directed homotopy Dip. Mat. Univ. Genova, Preprint 527 (2005), 34 p. Abstract. Directed Algebraic Topology is a recent field, deeply linked with ordinary and higher dimensional Category Theory. A 'directed space', e.g. an ordered topological space, has directed homotopies (generally non reversible) and fundamental n-categories (replacing the fundamental n-groupoids of the classical case). Finding a simple model of the latter is a non-trivial problem, whose solution gives relevant information on the given 'space'; a problem which is also of interest in general Category Theory, as it requires equivalence relations wider than categorical equivalence. Taking on a previous work on "The shape of a category up to directed homotopy", we study now the fundamental 2-category of a directed space. All the notions of 2-category theory used here are explicitly reviewed. http://www.dima.unige.it/~grandis/Shp2.pdf http://www.dima.unige.it/~grandis/Shp2.ps ________________ The first paper, "The shape of a category up to directed homotopy", can also be downloaded: Abstract: http://www.dima.unige.it/~grandis/Shp.Abs.html Paper: http://www.dima.unige.it/~grandis/Shp.pdf http://www.dima.unige.it/~grandis/Shp.ps ________________ Marco Grandis Dipartimento di Matematica Universita` di Genova via Dodecaneso 35 16146 GENOVA, Italy e-mail: grandis@dima.unige.it tel: +39.010.353 6805 fax: +39.010.353 6752 http://www.dima.unige.it/~grandis/ 24-Mar-2005 13:53:44 -0400,6340;000000000001-00000000 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 24 Mar 2005 13:53:44 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.44) id 1DEWSY-0004xx-N9 for categories-list@mta.ca; Thu, 24 Mar 2005 13:49:30 -0400 Mime-Version: 1.0 (Apple Message framework v619) Content-Type: text/plain; charset=US-ASCII; format=flowed Message-Id: Content-Transfer-Encoding: 7bit Reply-To: lacl@labri.fr From: maxime ambard Subject: categories: [LACL] Call For participation Date: Thu, 24 Mar 2005 10:40:10 +0100 Sender: cat-dist@mta.ca Precedence: bulk Apologies for multiple copies / please redistribute ************************************************** L A C L 2 0 0 5 Fifth International Conference on Logical Aspects of Computational Linguistics --- 28-29-30 april 2005, Bordeaux (France) http://lacl.labri.fr/ CNRS - INRIA - University of Bordeaux 1 & 3 ************************************************** CALL FOR PARTICIPATION LACL conference series ---------------------- LACL-2005 is the 5th edition of a series of international conferences on logical and formal methods in computational linguistics. It addresses in particular the use of proof theoretic and model theoretic methods for describing natural language syntax and semantics, as well as the implementation of natural language processing software relying on such models. Student Session ---------------------- A student session will be organize. For more informations, see our web site http://lacl.labri.fr/student_session Registration ------------ Registration for LACL 2005 is open. You can access the registration form from the LACL website http://lacl.labri.fr/registration.html Travel ------ Bordeaux has an airport with direct flights from Paris (both Charles de Gaulle and Orly), Amsterdam, London Gatwick and several other major European destinations. There is also an hourly TGV service from Paris Montparnasse. Accommodation ------------- We have reserved rooms in serveral hotels close to the conference site. You can find information and a booking form at. http://lacl.labri.fr/hotels.html Conference Site --------------- LACL will take place at the conference room of the Musee d'Aquitaine, a few steps away from the stop `Musee d'Aquitaine' of tramline B. Practical inquiries ------------------- Joan Busquets busquets@u-bordeaux3.fr Richard Moot moot@labri.fr Brigitte Larue-Bourdon +33 5 40 00 69 30 Preliminary Program ------------------- Thursday 28 April 09:00-09:30 Coffee/Registration 09:30-10:30 Invited Talk: Ruth Kempson - A Grammar Formalism for Dialogue Modelling? 10:30-10:45 Coffee Break 10:45-11:15 Ryo Yoshinaka and Makoto Kanazawa - The Complexity and Generative Capacity of Lexicalized Abstract Categorial Grammars 11:15-11:45 Allan Third - The Expressive Power of Restricted Fragments of English 11:45-12:15 Peter Ljunglof - A Polynomial Time Extension of Parallel Multiple Context-Free Grammar 12:15-14:00 Lunch 14:00-14:30 Roberto Bonato - Towards a Computational Treatment of Binding Theory 14:30-15:00 Joachim Niehren and Mateu Villaret - Describing Lambda Terms in Context Unification 15:00-15:30 Bassam Haddad and Mustafa Yaseen - A Compositional Approach Towards Semantic Representation and Construction of Arabic 15:30-16:00 Benoit Sagot - Linguistic facts as predicates over ranges of the sentence 16:00-16:30 Coffee Break 16:30-17:00 Evelyne Jacquey - Un cas de "polysemie logique" 17:00-18:00 Industrial Session - APIL 18:00-20:00 Wine Tasting Friday 29 April 09:00-09:30 Coffee 09:30-10:30 Invited Talk: Gerard Huet - TBA 10:30-10:45 Coffee Break 10:45-11:15 Erwan Moreau - Learnable classes of general combinatory grammar 11:15-11:45 Isabelle Tellier - When Categorial Grammar meet Regular Grammatical Inference 11:45-12:15 Denis Bechet and Annie Foret - k-Valued Non-Associative Lambek Grammars (without Product) Form a Strict Hierarchy of Languages 12:15-14:00 Lunch 14:00-14:30 Richard Zuber - More algebras for determiners 14:30-15:00 Nissim Francez - Lambek-Calculus with General Elimination rules and Continuation Semantics 15:00-15:30 Areski Nait Abdallah and Alain Lecomte - On expressing vague quantification and scalar implicatures in the logic of partial information 15:30-16:00 Marcelo da S. Correa and E. Hermann Haeusler - On the Selective Lambek Calculus 16:00-16:15 Coffee Break 16:15-16:45 Student Session 16:45-17:15 Djame Seddah and Bertrand Gaiffe - How to Build Argumental graphs Using TAG Shared Forest : a view from control verbs 17:15-17:45 Claire Gardent and Yannick Parmentier - Large scale semantic construction for Tree Adjoining Grammars 21:00-23:00 Conference Diner Saturday 30 April 09:00-09:30 Coffee 09:30-10:00 Anne Preller and Joachim Lambek - Categorical semantics for pregroup grammars 10:00-10:30 Denis Bechet, Alexander Dikovsky and Annie Foret - Dependency Structure Grammars 10:30-10:45 Coffee Break 10:45-11:15 Veit Reuer and Kai-Uwe Kuehnberger - Feature Constraint Logic and Error Detection in ICALL Systems 11:15-11:45 David A. Burke and Kristofer Johannisson - Translating Formal Software Specifications to Natural Language. A Grammar-Based Approach 11:45-12:15 Benoit Crabbe - Grammatical Development with XMG 12:15-14:00 Lunch 14:00-14:30 John T. Hale and Edward P. Stabler - Strict Deterministic Aspects of Minimalist Grammars 14:30-15:00 Jens Michaelis and Hans-Martin Gaertner - A Note on the Complexity of Constraint Interaction: Locality Conditions and Minimalist Grammars 15:00-16:00 Invited Talk: Carl Pollard - TBA ======================================================================== LACL 2005 web site: http://lacl.labri.fr 25-Mar-2005 09:32:41 -0400,802;000000000000-00000000 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 25 Mar 2005 09:32:41 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.44) id 1DEoma-0001qs-Ow for categories-list@mta.ca; Fri, 25 Mar 2005 09:23:24 -0400 Date: Fri, 25 Mar 2005 12:20:45 +0000 From: Robin Houston To: categories@mta.ca Subject: categories: Enriching over a promonoidal base Message-ID: <20050325122045.GB16218@rpc142.cs.man.ac.uk> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Sender: cat-dist@mta.ca Precedence: bulk Dear Categorists, Who first defined categories enriched over a _promonoidal_ base? I'd particularly like references, but any information would be welcome. Robin 28-Mar-2005 11:19:48 -0400,1613;000000000001-00000000 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 28 Mar 2005 11:19:48 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.44) id 1DFvss-0002qv-PN for categories-list@mta.ca; Mon, 28 Mar 2005 11:10:30 -0400 Date: Sun, 27 Mar 2005 21:27:14 +0100 From: Robin Houston To: categories@mta.ca Subject: categories: Re: Enriching over a promonoidal base Message-ID: <20050327202714.GE3697@rpc142.cs.man.ac.uk> References: <20050325122045.GB16218@rpc142.cs.man.ac.uk> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20050325122045.GB16218@rpc142.cs.man.ac.uk> User-Agent: Mutt/1.4i Sender: cat-dist@mta.ca Precedence: bulk On Fri, Mar 25, 2005 at 12:20:45PM +0000, Robin Houston wrote: > Who first defined categories enriched over a _promonoidal_ base? > I'd particularly like references, but any information would be welcome. Many thanks to everyone who replied off-list. I get the impression that there may be no published account of this. There is a short remark in _Categories enriched on two sides_ by Kelly, Labella, Schmitt and Street: "We note, without going into details here, that we can repeat the above with monoidal categories replaced by the more general promonoidal categories of [D1]" (where [D1] is a reference to Day's _On closed categories of functors_ and "the above" is a precis of enriched category theory.) One respondent said the idea is due to Day and Street. Can anyone confirm that? Thanks again. Robin 28-Mar-2005 11:19:48 -0400,3787;000000000000-00000000 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 28 Mar 2005 11:19:48 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.44) id 1DFvs0-0002me-Md for categories-list@mta.ca; Mon, 28 Mar 2005 11:09:36 -0400 Subject: categories: Re: Enriching over a promonoidal base From: Stefan Forcey To: categories@mta.ca Date: Sun, 27 Mar 2005 13:39:12 -0500 (EST) In-Reply-To: <20050325122045.GB16218@rpc142.cs.man.ac.uk> from "Robin Houston" at Mar 25, 2005 12:20:45 PM X-Mailer: ELM [version 2.5 PL2] MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-Id: <20050327183925Z28441-27498+188@calvin.math.vt.edu> Sender: cat-dist@mta.ca Precedence: bulk > Who first defined categories enriched over a _promonoidal_ base? Dear Robin, I don't think I can directly answer your question; if it has a direct answer I would very much like to know it as well. However, I have spent some time thinking about this and related questions and know of some resources that might help. Promonoidal categories over a closed symmetric monoidal V are monoids in V-Mod, and thus a promonoidal structure on a V-category A is a V-functor P:A^op \otimes A^op \otimes A -> V. ( My favourite source is section 7 of the paper by Brian Day and Ross Street. Monoidal Bicategories and Hopf Algebroids; advances in mathematics 129, 99-157 (1997)) Unlike for a monoidal V-category (monoid in V-Cat) this does not as far as I can see immediately provide a monoidal structure on the underlying category of A. But there are two indirect possibilities for the meaning of enrichment over a promonoidal base. One is to enrich over the functor category [A,V] , which is automatically monoidal. See the original paper by Brian Day. { B.J. Day, On closed categories of functors, Lecture Notes in Math 137 (Springer, 1970) 1-38.} The other is in the special case of a closed promonoidal category in which we have an additional functor *:A \otimes A^op -> A for which P(a,b,c) = A(b, a*c) the latter being the appropriate hom-object of A in V. Thus we could conceivably define a category B enriched over A as having hom objects B(x,y) in A and composition morphisms in V given by M:I-> P(B(y,z), B(x,y), B(x,z)). This should reduce to being the same as enriching over the underlying category of A, but I have yet to straighten out the details, especially the correct locations of ^op! Again, if someone else has done so I would like to see the source as well. (The idea of (bi)closed promonoidal is introduced by Day in the context of probicategories in a preprint: "Biclosed bicategories: localization of convolution" in the Maquarie Mathematics Reports, which really ought to be published at some point.) Of further interest is the generalization of promonoidal categories in the form of substitudes, which are also a little more general than multicategories. See the preprint of Street and Day: (available from Ross's website) Abstract substitution in enriched categories; Brian Day and Ross Street. Whether there is a theory of enrichment over these very appealing objects is a question for the authors. Perhaps there is an additional enrichment facilitating requirement on substitudes which generalizes the closed promonoidal concept and/or is along the lines of Tom Leinster's generalized enrichment over T-multicategories (see his papers on the arxiv.) Hope some of this helps, Stefan Forcey Robin Houston writes: > > Dear Categorists, > > Who first defined categories enriched over a _promonoidal_ base? > > I'd particularly like references, but any information would be welcome. > > Robin > > 29-Mar-2005 12:56:27 -0400,2742;000000000001-00000000 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 29 Mar 2005 12:56:27 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.44) id 1DGJtj-00033a-GG for categories-list@mta.ca; Tue, 29 Mar 2005 12:48:59 -0400 Date: Mon, 28 Mar 2005 13:30:44 -0800 (PST) From: John MacDonald To: categories@mta.ca Subject: categories: FMCS05 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed Sender: cat-dist@mta.ca Precedence: bulk Second Announcement FMCS05 Foundational Methods in Computer Science JUNE 2nd - 5th, 2005 FMCS05 now has a website where one can register and also reserve accommodation online. The address is http://www.pims.math.ca/science/2005/05fmcs I would urge you and your students, if any are attending, to book accommodation early since the housing office will not guarantee booking for our group past May 1. They will, however continue to book if space is available. The third announcement will contain a list of participants so if you have not previously indicated to me that you will or may attend and if you would like to have your name on the participant list, then please send email to johnm@math.ubc.ca with subject heading FMCS05 - WILL ATTEND or FMCS05 - MAY ATTEND. The following paragraphs repeat the information from the first announcement. The Department of Mathematics at the University of British Columbia in cooperation with the Pacific Institute for Mathematical Sciences is hosting the Foundational Methods in Computer Science workshop from June 2nd to June 5th, 2005, on the University of British Columbia Campus in Vancouver, B.C., Canada The workshop is an informal meeting to bring together researchers in mathematics and computer science with a focus on the application of category theory in computer science. The meeting begins with a reception at 6pm in the Ruth Blair room in Walter Gage Towers on the UBC campus on Thursday June 2, 2005. This is followed by a day of tutorials aimed at students and newcomers to computer science applications of category theory, followed by a day and a half of research talks. The meeting ends at 1pm on Sunday June 5. There will be a few invited presentations, but the majority of the talks are solicited from the participants. Student participation is particularly encouraged at FMCS. There are still a few places on the program left for research presentations of 20 to 30 minutes. John MacDonald Local organizer, FMCS05 29-Mar-2005 12:56:27 -0400,1630;000000000001-00000000 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 29 Mar 2005 12:56:27 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.44) id 1DGJtA-00031E-7K for categories-list@mta.ca; Tue, 29 Mar 2005 12:48:24 -0400 Date: Mon, 28 Mar 2005 21:10:58 +0100 From: Robin Houston To: categories@mta.ca Subject: categories: Re: Enriching over a promonoidal base Message-ID: <20050328201058.GB7547@rpc142.cs.man.ac.uk> References: <20050325122045.GB16218@rpc142.cs.man.ac.uk> <20050327183925Z28441-27498+188@calvin.math.vt.edu> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20050327183925Z28441-27498+188@calvin.math.vt.edu> User-Agent: Mutt/1.4i Sender: cat-dist@mta.ca Precedence: bulk In reply to Stefan's message, it is certainly possible to define V-categories for a general promonoidal V. Let V be a promonoidal category, with tensor functor P: C^op x C^op x C -> Set, and unit functor J: C -> Set. A V-category C consists of: a set obC of objects; a hom object C(A,B) in V for every (A,B) in obC^2; an identity element id_A in J(C(A,A)) for every A in obC; a composition element M_A,B,C in P(C(B,C),C(A,B),C(A,C)) for every (A,B,C) in obC^3; subject to associativity and unit axioms that can be expressed as the commutativity of three smallish diagrams that involve coends. I think it's equivalent to ask for a ([V,Set]^op)-category all of whose hom objects are representable. (Of course it is possible that this is not what Kelly et al. had in mind.) Robin 30-Mar-2005 11:10:59 -0400,2336;000000000001-00000000 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 30 Mar 2005 11:10:59 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.44) id 1DGeli-00010j-EF for categories-list@mta.ca; Wed, 30 Mar 2005 11:06:06 -0400 X-Mailer: QUALCOMM Windows Eudora Version 6.2.1.2 Date: Wed, 30 Mar 2005 12:42:59 +0100 To: categories@mta.ca From: Maria Manuel Clementino Subject: categories: Postdoctoral Research Positions Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Postdoctoral Research Positions The Centre for Mathematics of the University of Coimbra (CMUC) accepts applications for one-year postdoctoral positions in all areas of Mathematics. CMUC has been recently classified as a research unit of excellence by an international funding panel. In particular, the Centre welcomes applications in the following areas: Computational Mathematics & Scientific Computing. Group and Algebras Representations. Category Theory. Multilinear Algebra, Matrix Theory & Combinatorics. Nonparametric Statistics. Nonlinear Time-Series Modelling. Partial Differential Equations. Quantum Groups. Symplectic and Poisson Geometry. Stochastic Analysis. Mathematics of Finance. The positions obey to the portuguese scholarship system (http//www.fct.mces.pt). The salary will be determined by the candidate's qualifications and experience and can vary between 17940 and 24720 EUR a year (tax free). The positions include benefits and a professional travel allowance. There are no teaching duties associated to the positions, which should start by September/October 2005. Applicants must have (or soon have) a Ph.D. in Mathematics and a good command of english. Applications will be accepted until April 30, 2005. Applicants should send a curriculum vitae (publication list included), a statement of research interests (one page maximum), and at least two letters of recommendation (or names of references) by regular mail or e-mail to: Centre for Mathematics - University of Coimbra Apartado 3008, 3001-454 Coimbra, Portugal cmuc@mat.uc.pt http://www.mat.uc.pt/~cmuc 1-Apr-2005 13:34:34 -0400,2387;000000000001-00000000 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 01 Apr 2005 13:34:34 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.44) id 1DHPzK-0000VY-3L for categories-list@mta.ca; Fri, 01 Apr 2005 13:31:18 -0400 Message-Id: <200503312110.j2VL9udK019473@imgw1.cpsc.ucalgary.ca> Date: Thu, 31 Mar 2005 14:09:56 -0700 (MST) From: robin@cpsc.ucalgary.ca Reply-To: robin@cpsc.ucalgary.ca Subject: categories: Preliminary announcement of events 2006 To: categories@mta.ca MIME-Version: 1.0 Content-Type: TEXT/plain; charset=us-ascii Sender: cat-dist@mta.ca Precedence: bulk Preliminary announcement of Categorical events -- PLEASE PLAN TO COME! Where: Calgary, Alberta, Canada When: June 3rd - 9th What: (1) Canadian Mathematical Society Summer Meeting 2006 Calgary, June 3-5th 2006 (Saturday - Monday) Category Theory Session: (local organizer: Robin Cockett) We are proposing three general themes: Session 1: Algebraic Set theory (Steve Awodey) Session 2: Applications of Categorical Proof Theory and Logic (Phil Scott/Rick Blute) Session 3: Partial Maps, Inverse Semigrous, and Restriction Categories (Ernie Manes) These themes should not be regarded as being exclusive and the organizers will be happy to host talks in Category Theory which would be of general interest. If we cannot accomodate you in this meeting please stay on and participate in: (2) FMC2006: Foundational Methods in Computer Science 2006 (local organizer: Robin Cockett) Planned in the Kananaskis (at a forestry field station) immediately after the CMS meeting (transport from Calgary available). June 7-9th 2004 (Wednesday - Friday) This workshop is an informal meeting to bring together researchers in Mathematics and Computer Science with a focus on the applications of Category Theory in Computer Science. It is a three day meeting starting with a day of tutorials followed by a day and a half of contributed research talks. Student participation is strongly encouraged. [NOTE: FMCS2006 year will *not* be a weekend meeting ....] Enquiries to any of the above including robin@cpsc.ucalgary.ca. 1-Apr-2005 13:34:34 -0400,3121;000000000000-00000000 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 01 Apr 2005 13:34:34 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.44) id 1DHPy0-0000Nx-KC for categories-list@mta.ca; Fri, 01 Apr 2005 13:29:56 -0400 To: FLoC 2006 List From: Kreutzer + Schweikardt Subject: categories: FLoC 2006 Preliminary Announcement Reply-To: floc@informatik.hu-berlin.de Message-Id: <20050331194248.CD561372CF@paris.informatik.hu-berlin.de> Date: Thu, 31 Mar 2005 21:42:48 +0200 (CEST) X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on mx1.mta.ca X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.2 Sender: cat-dist@mta.ca Precedence: bulk Preliminary Announcement --- FLoC'06 The 2006 Federated Logic Conference Seattle, Washington, USA August 10 -- August 22, 2006 http://research.microsoft.com/projects/FLoC2006/home.html http://research.microsoft.com/floc06/ In 1996, as part of its Special Year on Logic and Algorithms, DIMACS hosted the first Federated Logic Conference (FLoC). It was modeled after the successful Federated Computer Research Conference (FCRC), and synergetically brought together conferences that apply logic to computer science. The second Federated Logic Conference (FLoC'99) was held in Trento, Italy, in 1999, and the third (FLoC'02) was held in Copenhagen, Denmark, in 2002. We are pleased to announce the fourth Federated Logic Conference (FLoC'06) to be held in Seattle, Washington, in August 2006, at the Seattle Sheraton (http://www.sheraton.com/seattle). The following conferences will participate in FLoC. Int'l Conference on Computer-Aided Verification (CAV) Int'l Conference on Rewriting Techniques and Applications (RTA) IEEE Symposium on Logic in Computer Science (LICS) Int'l Conference on Logic Programming (ICLP) Int'l Conference on Theory and Applications of Satisfiability Testing (SAT) Int'l Joint Conference on Automated Reasoning (IJCAR) Pre-conference workshops will be held on August 10-11. LICS, RTA, and SAT will be held in parallel on August 12-15, to be followed by mid-conference workshops and excursions on August 15-16. CAV, ICLP, and IJCAR will be held in parallel on August 16-21, to be followed by post-conference workshops on August 21-22. Plenary events involving all the conferences are planned. Calls for papers and call for workshop proposals will be issued in the near future. For additional information regarding the participating meetings, please check the FLoC web page (see above) later this summer. FLoC'06 Steering Committee Moshe Y. Vardi (General Chair) Jakob Rehof (Conference Chair) Edmund Clarke (CAV) Reiner Hahnle (IJCAR) Manuel Hermenegildo (ICLP) Phokion Kolaitis (LICS) Henry Kautz (SAT) Aart Middeldorp (RTA) Andrei Voronkov (IJCAR) 31-Mar-2005 17:20:23 -0400,1097;000000000000-00000000 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 31 Mar 2005 17:20:23 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.44) id 1DH6xk-0006W9-ER for categories-list@mta.ca; Thu, 31 Mar 2005 17:12:24 -0400 Date: Thu, 31 Mar 2005 11:27:06 +0100 From: Robin Houston To: categories@mta.ca Subject: categories: Re: Enriching over a promonoidal base Message-ID: <20050331102706.GA20819@rpc142.cs.man.ac.uk> References: <20050325122045.GB16218@rpc142.cs.man.ac.uk> <20050327183925Z28441-27498+188@calvin.math.vt.edu> <20050328201058.GB7547@rpc142.cs.man.ac.uk> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20050328201058.GB7547@rpc142.cs.man.ac.uk> User-Agent: Mutt/1.4i Sender: cat-dist@mta.ca Precedence: bulk Dear people, In case anyone other than me is interested, the best information I have currently is that the idea can be traced to RJ Wood's PhD thesis _Indical Methods for Relative Categories_ (Dalhousie, 1976). Robin