From rrosebru@mta.ca Thu Apr 1 14:24:46 2004 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 01 Apr 2004 14:24:46 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1B96pj-0006qu-00 for categories-list@mta.ca; Thu, 01 Apr 2004 14:22:31 -0400 From: Todd Wilson MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <16491.20549.171326.902250@localhost.localdomain> Date: Wed, 31 Mar 2004 15:12:05 -0800 To: categories@mta.ca Subject: categories: Re: on the axiom of infinity In-Reply-To: <200403291603.i2TG3UX6000400@saul.cis.upenn.edu> References: <200403291603.i2TG3UX6000400@saul.cis.upenn.edu> Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: X-Keywords: X-UID: 1 On Mon, 29 Mar 2004, Peter Freyd wrote: > There's a particular operator that keeps popping up for me. > > In an arbitrary heyting algebra define x << y to mean that not only > is x less than or equal to y, but the value of y -> x is as small > as it can be, that is, y -> x = x. In a complete heyting algebra > define an order-preserving, inflationary unary operation s by > > sx = inf{ y | x << y }. > > E.g.: on a linearly ordered set if { y | x < y } has a least element > then that's what sx is. If there is no smallest element above x, > then sx = x (even without the completeness hypothesis). In > particular, note, there no assertion that x << sx. > > The subobject classifier in an elementary topos is complete in the > relevant sense: s is definable. A quick description of the > construction to follow is that we're going to turn s into the > successor operation on an NNO. > > DIVERSION: The definition I just gave is the first I came across. The > next incarnation for me was when I wanted a measure of the failure of > booleaness. In any topos, *A*, there's a largest subterminator B > with the property that the slice category *A*/B is boolean. But > given any subterminator, U, we have its "closed sheaves", *A*_(U), the > full subcat of objects A such that AxU --> U is an iso. (This is a > subcategory of sheaves for a Lawvere-Tierney topology. Starting with > a space X then Sheaves(X)_(U) may be identified with Sheaves(U'), > where U' denotes the complement of U.) Note that the lattice of > subterminators in *A*_(U) is isomorphic to the interval of > subterminators in *A* from U up. We can define BU to be the > largest subterminator in *A*_(U) such that *A*_(U)/BU is boolean. > The interval of subterminators in *A* from U up to BU is boolean > and in the relevant internal sense, BU is the largest such > subterminator. We can, of course, translate this all to a unary > operation on Omega. > > It's the same operator s. > > When one specializes this to a space X it becomes historically > familiar if we dualize it it to a deflationary operator on closed > subsets. It's the operation that removes isolated points. The very > operation that got Cantor started. Hence the word "historically". I haven't yet digested the rest of Freyd's post, but all of the above, including the notation x << y, the connection with collapsing maximal Boolean intervals, the "historical" connection with Cantor, and a lot more, can be found in a series of papers of Harold Simmons: H. Simmons, "The Cantor-Bendixson analysis of a frame", Seminaire de mathematique pure, Rapport no. 92, Institut de Mathematique Pure, Universite Catholique de Louvain, January 1980. H. Simmons, "An algebraic version of Cantor-Bendixson analysis", in Categorial Aspects of Toplogy and Analysis, pp. 310-323, Springer LNM 915, 1982. H. Simmons, "Near-discreteness of modules and spaces as measured by Gabriel and Cantor", J. Pure and Appl. Alg. 56 (1989), 119-162. H. Simmons, "Separating the discrete from the continuous by iterating derivatives", Bull. Soc. Math. Belg. 41 (1989), 417-463. The operation Freyd is calling s (and the associated relation <<) arose in connection with the so-called Reflection Problem for Frames, namely to characterize those frames that have a reflection into the category of complete Boolean algebras. When such reflections exist, they can be found by iterating the functor A |-> N(A), which freely complements the elements of A (and is also the frame of nuclei on A, ordered pointwise), until it "terminates": A -> N(A) -> N^2(A) -> ... -> N^a(A) -> ... (a in ORD). (These maps are all both mono and epi and are components of natural transformations between iterates of N). A basic result here is that N(A) is Boolean iff x << sx for all x in A. The general reflection problem remains open. -- Todd Wilson A smile is not an individual Computer Science Department product; it is a co-product. California State University, Fresno -- Thich Nhat Hanh From rrosebru@mta.ca Thu Apr 1 14:24:46 2004 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 01 Apr 2004 14:24:46 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1B96nn-0006iA-00 for categories-list@mta.ca; Thu, 01 Apr 2004 14:20:31 -0400 From: Thomas Streicher Message-Id: <200403311859.UAA31390@fb04209.mathematik.tu-darmstadt.de> Subject: categories: Re : on the axiom of infinity To: categories@mta.ca Date: Wed, 31 Mar 2004 20:59:03 +0200 (CEST) X-Mailer: ELM [version 2.4ME+ PL66 (25)] MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 2 Dear Peter, this story about ``infinity without infinity axiom'' is a bit confusing from a (traditional) ``logical point of view''. Is the following reformulation in accordance with what you mean? In intutionistic higher order arithmetic (HAH), i.e. the logic of toposes with NNO, it is consistent to assume that N is a subobject of P^2(Om). Even more it is consistent to assume (as explained in the last section of part D of the Elephant) that N is (isomorphic to) the orbit Orb(Phi) arising from the Phi : P^2(Om) -> P^2(Om) whose least fixpoint is K(Om) \in P^2(Om) (the Kuratowski finite subsets of Om). In a logical formula one would formulate this as (InF) Phi has no fixpoint in Orb((Phi) where InF stands for ``Infinity `a la Freyd''. Evidently HAH does not prove (InF) because it is inconsistent with classical HAH. But, of course, in HAH + InF one can construct a NNO as a subobject of P^2(Om). In other words T/InF has a NNO (where T is the free topos without arithmetic). For me HOL + InF (where HOL is *pure* higher order intuit.logic) looks like a strengthening of HAH which is inconsistent with classical logic rather than ``getting infinity out of pure logic'' (as the logicists were aiming at). Of course, you get more than mere consistency of HOL + InF because you have that Gamma(Orb(Phi)) is actually the rig of natural numbers in Set (where Gamma = T(1,-) : T -> Set) but inside T one hasn't access to this nice fact and, therefore, cannot really make use of it. There arises the question to which extent HOL + InF (or equivalently HAH + InF) is conservative over HAH. Is it the case that every formula of HA (i.e. intuit. first order arithmetic) is provable already in HAH whenever it is provable in HAH + InF? Clearly, w.r.t. higher order arithmetic formulas HAH + Inf is not conservative over HAH because InF is not provable in HAH. But, of course, one might ask whether HAH + InF is conservative over HAH w.r.t. 2nd order formulas of arithmetic. (These are a good measure because up to some (admittedly somewhat nasty) coding a fair amount of analysis is expressible in this fragment.) There is no end to questions like these because one might also ask whether HAH + InF is conservative over HAH w.r.t. formulas of HA^\omega, i.e. first order intuit. logic over G\"odel's T. (HA^\omega is a typical system employed by people doing constructive analysis.) But first things first. Does it follow from your result(s) whether HAH + InF is conservative over HAH w.r.t. first order arithmetic formulas? Best, Thomas From rrosebru@mta.ca Thu Apr 1 14:32:55 2004 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 01 Apr 2004 14:32:55 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1B96zX-00004y-00 for categories-list@mta.ca; Thu, 01 Apr 2004 14:32:39 -0400 Date: Wed, 31 Mar 2004 20:59:37 -0600 Message-Id: <200404010259.i312xbe08737@johann.math.tulane.edu> From: Mike Mislove To: categories@mta.ca Subject: categories: MFPS: Last day to submit title and abstract Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 4 Dear Colleagues, This is to remind you that April 1 is the last day to submit a title and abstract for a contributed talk at this year's MFPS meeting. The meeting will be held on the campus of Carnegie Mellon University from May 23 to May 26. There are a number of special events planned, including six special sessions, each with a plenary lecture by a leading researcher. The meeting is co-located with the annual Association of Symbolic Logic meeting, which will take place from May 19 through midday, May 23. Finally, there will be a very special event on the evening of May 22. Cliff Jones (Newcastle), John McCarthy (Stanford), John Reynolds (CMU) and Dana Scott (CMU) will participate in discussions and reminiscences about how the area of programming languages arose and how it has evolved over the years. Please plan to attend the meeting, and submit a title and abstract for a contributed talk if you wish to present one. The available slots will be allocated on a first come, first served basis. You can find instructions about how to submit a title and abstract, as well as detailed information about the MFPS meeting and a link to the online registration form at the MFPS XX URL http://www.math.tulane.edu/~mfps/mfps20.htm Best regards, Mike Mislove =============================================== Professor Michael Mislove Phone: +1 504 862-3441 Department of Mathematics FAX: +1 504 865-5063 Tulane University URL: http://www.math.tulane.edu/~mwm New Orleans, LA 70118 USA =============================================== From rrosebru@mta.ca Thu Apr 1 21:52:14 2004 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 01 Apr 2004 21:52:14 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1B9DqJ-0000gB-00 for categories-list@mta.ca; Thu, 01 Apr 2004 21:51:35 -0400 Date: Fri, 2 Apr 2004 00:54:57 +0300 (EEST) From: Stephane Foldes To: categories@mta.ca Subject: categories: research positions for doctoral students Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 5 RESEARCH POSTIONS FOR DOCTORAL STUDENTS Call for expressions of interest Applicants sought in discrete mathematics The Tampere Graduate School in Information Science and Engineering (TISE), a graduate school affiliated with the Tampere University of Technology (TUT) and the University of Tampere, expects to have research position openings for doctoral students. The positions are renewable for up to four years. Applications require faculty support from a TISE-affiliated university. For general information see www.cs.tut.fi/tise/. The Institute of Mathematics at TUT is interested in supporting TISE applications in the area of discrete mathematics and theoretical computer science, broadly conceived as including relevant areas of algebra, in particular of categorical algebra, as well as of geometry and other subjects. Within the spectrum of priorities represented in TISE and the Institute of Mathematics at TUT, the emphasis of the present call for expressions of interest is on theoretical rather than applied research and on structural rather than algorithmic aspects of discrete mathematics. TISE expects to issue a call for formal applications in or around September 2004, and positions would be available starting January 2005. At the present time expressions of interest are invited in the areas indicated, to be sent to the undersigned, in order to explore the possibility of faculty support. The sine qua non prerequisite, in addition to general TISE requirements, is authorship of an independent research paper in mathematics (other than co-authored papers), of publishable content, whether actually published or unpublished. Please transmit the relevant material only by postal mail. Informal enquiries are welcome. Stephan Foldes Professor of Mathematics Tampere University of Technology, PL 553, 33101 Tampere, Finland Tel: ++358 3 3115 2427 Fax: ++358 3 3115 3549 E-mail: stephan.foldes@tut.fi From rrosebru@mta.ca Thu Apr 1 21:52:14 2004 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 01 Apr 2004 21:52:14 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1B9Dp6-0000cQ-00 for categories-list@mta.ca; Thu, 01 Apr 2004 21:50:20 -0400 Message-ID: <406BE98A.3303D7C5@loria.fr> Date: Thu, 01 Apr 2004 12:06:02 +0200 From: Didier Galmiche Organization: LORIA UMR 7503 X-Mailer: Mozilla 4.76 [en] (X11; U; SunOS 5.7 sun4u) X-Accept-Language: en MIME-Version: 1.0 To: categories@mta.ca Subject: categories: 2nd call Workshop on Logics for Resources, Processes and Programs Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 6 ================================================================== SECOND CALL FOR PAPERS Workshop on Logics for Resources, Processes, and Programs (affiliated with LICS 2004 and ICALP 2004) July 13, 2004, Turku, Finland Web page: http://www.loria.fr/~galmiche/LRPP04.html =================================================================== ***NEW*** - New submission deadline : April 24, 2004. - There will be a Special Issue of the Journal of Logic and Computation Semantics Corner after the workshop (subject to the usual JLC refereeing standards). =================================================================== A one day workshop on Logics for Resources, Processes, and Programs will be held in July 2004 in conjunction with LICS 2004 (http://www.dcs.ed.ac.uk/home/als/lics/lics04/) and ICALP 2004 (http://www.math.utu.fi/ICALP04/) conferences in Turku, Finland. The organizers and co-chairmen are Didier Galmiche, Peter O'Hearn and David Pym. Hardcopies of the preliminary proceedings will be distributed at the workshop and a Special Issue of a Journal on these topics is expected after the workshop. TOPICS The notion of resource is a basic one in many fields, but it appears as central in computer science. Various logics, typically involving substructural connectives, have been proposed in order to provide a logical analysis of this notion from different viewpoints. Examples include linear logic (number-of-uses reading), the bunched implications logic (sharing interpretations), so-called separation and spatial logics (pointer logic and local reasoning, logics for concurrency, logics for data structures such as trees). Logics such as these, which may include a wide range of modalities and domain-specific operators, allow the description of properties of systems, of process calculi, and of programs, and so provide bases for specification and theorem-proving tools. The objective of the workshop to provide a forum for discussion between researchers interested in logics of resources (from foundations to related calculi and applications) and researchers interested in languages and methods for specification of mobile, distributed, concurrent systems and their verification. Topics of interest, in this context, include but are not restricted to the following: - Logics for resources: semantics and proof theory; - Process calculi, concurrency, resource-distribution; - Reasoning about programs and systems; - Extensions of logics, e.g. with modalities; - Languages of assertions, languages based on resource logics (query languages, pointers, trees, and graphs) and reasoning; - Theorem proving and model checking in resource logics: decision procedures, strategies, complexity results. SUBMISSIONS Researchers interested in presenting their works are invited to send an extended abstract (up to 10 pages) by e-mail submissions of Postscript files to D. Galmiche (Didier.Galmiche@loria.fr) before April 24, 2004. Papers will be reviewed by peers, typically members of the Programme Committee. The cover page should include a return mailing address and, if possible, an electronic mail address and a fax number. Additional information will be available through WWW address: http://www.loria.fr/~galmiche/LRPP04.html PROGRAM COMMITTEE L. Caires (UNL Lisbon, Portugal) D. Galmiche (LORIA, France) P. O'Hearn (QM London, UK) D. Pym (HP Labs and Bath, UK) V. Sassone (Sussex, UK) P. Schroeder-Heister (Tuebingen, GR) D. Walker (Princeton, USA) IMPORTANT DATES Submissions: April 24, 2004 Notifications: May 17, 2004 Final papers: June 7, 2004 Workshop date: July 13, 2004 From rrosebru@mta.ca Sun Apr 4 15:19:01 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 04 Apr 2004 15:19:01 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BACBE-0000Gc-00 for categories-list@mta.ca; Sun, 04 Apr 2004 15:17:12 -0300 Message-ID: <29817.62.242.61.181.1081003740.squirrel@secure.itu.dk> Date: Sat, 3 Apr 2004 16:49:00 +0200 (CEST) Subject: categories: CTCS 2004: Final CFP and Deadline Extension From: hilde@itu.dk To: categories@mta.ca User-Agent: SquirrelMail/1.4.2 MIME-Version: 1.0 Content-Type: text/plain;charset=iso-8859-1 Content-Transfer-Encoding: quoted-printable Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 7 [Apologies if you receive this more than once] ---> CTCS 2004 FINAL CALL FOR PAPERS and DEADLINE EXTENSION <--- 10th CONFERENCE ON CATEGORY THEORY AND COMPUTER SCIENCE (CTCS'04) August 12-14, 2004 and FIRST GRADUATE STUDENT SUMMER SCHOOL August 9-11, 2004 and 3rd WORKSHOP ON CATEGORICAL METHODS FOR CONCURRENCY, INTERACTION AND MOBILITY (CMCIM 2004) August 11, 2004 ---------------------------------------------------------------- New Information since last call: - Extended Submission Deadline: April 16th, 2004 - Thomas Streicher gives an invited talk entitled "A Universal Model for Infinitary CPS Language" (see abstract on the conference webpage, and other invited speakers below) - Deadline passed for student grant applications - Accomodation information (important deadlines at May 15th and July 1st) ---------------------------------------------------------------- CTCS 2004 is held at the new campus of the IT University of Copenhagen, from Thursday August 12th to Saturday August 14th, 2004. Just before the conference, Monday 9th - Wednesday 11th, there will be a graduate student summer school with lectures on: - Coalgebras, Modal Logic and Stone Duality (Lecturer: Alexander Kurz) - Game Semantics (Lecturer: Guy McCusker) - Operational Semantics (Lecturer: Pawel Sobocinski) - Categorical Models for Concurrency (Lecturer: Thomas Hildebrandt) In between the summer school and the workshop the 3rd CMCIM workshop. See the conference webpage and below for more details on these events. ----------------------------------------------------------------- The purpose of the CTCS conference series is the advancement of the foundations of computing using the tools of category theory. Previous meetings have been held in Guildford (Surrey), Edinburgh (twice), Manchester, Paris, Amsterdam, Cambridge, S. Margherita Ligure (Genova), and Ottawa. The emphasis is upon applications of category theory, but it is recognized that the area is highly interdisciplinary. Typical topics of interest include, but are not limited to, category-theoretic aspects of the following: Coalgebras and computing, Concurrent and distributed systems, Constructive mathematics, Declarative programming and term rewriting, Domain theory and topology, Foundations of computer security, Linear logic, Modal and temporal logics, Models of computation, Program logics, data refinement, and specification, Programming language semantics, Type theory The proceedings of the conference will be published as a special issue of ENTCS (Electronic Notes in Theoretical Computer Science). ----------------------------------------------------------------- INVITED SPEAKERS Francois Bergeron (Quebec) Martin Hyland (Cambridge) Robin Milner (Cambridge) Andrew Pitts (Cambridge) Thomas Streicher (Darmstadt) ----------------------------------------------------------------- PROGRAMME COMMITTEE Lars Birkedal, Chair (IT University of Copenhagen) Marcelo Fiore (University of Cambridge) Masahito Hasegawa (Kyoto University) Bart Jacobs (University of Nijmegen) Ugo Montanari (University of Pisa) Valeria de Paiva (Palo Alto Research Center) Dusko Pavlovic (Kestrel Institute) John Power (University of Edinburgh) Edmund Robinson (Queen Mary, University of London) Peter Selinger (University of Ottawa) ----------------------------------------------------------------- ORGANIZING COMMITTEE E. Moggi, Chair, (Genova) S. Abramsky (Oxford) P. Dybjer (Chalmers) B. Jay (Sydney) A. Pitts (Cambridge) Local organizing committee: C. Butz T. Hildebrandt A.L. Moerk ----------------------------------------------------------------- SUBMISSION OF PAPERS Papers should be submitted, preferably in electronic form, to ctcs04@itu.dk. Papers are limited to 15 pages, and must be submitted in dvi, postscript, or pdf format, possibly gzipped and/or uuencoded, or sent as a standard email attachment. All submissions must be received by April 16th, 2004 (notice extended deadline). If you cannot submit your paper electronically, please contact the program chair at ctcs04@itu.dk. ----------------------------------------------------------------- IMPORTANT DATES: - April 16th, 2004: Submission deadline (extended from April 9th) - June 1st, 2004: Notification of authors of accepted papers - July 1st, 2004: Registration deadline, and Revised papers due ----------------------------------------------------------------- Associated events: FIRST GRADUATE STUDENT SUMMER SCHOOL, August 9-11. Inspired by the success of the graduate student preconference of CTCS'02 in Ottawa, the CTCS of this year will have a graduate student summer school from August 9-11, sponsored by the FIRST graduate school (www.first.dk). The goal is to prepare students (with basic knowledge of category theory) for CTCS, through mini-courses in the basic areas underlying some of the fields of the conference. The school will offer the following mini-courses (5 lectures each): * Coalgebras, Modal Logic and Stone Duality (Lecturer: Alexander Kurz= ) * Game Semantics (Lecturer: Guy McCusker) * Operational Semantics (Lecturer: Pawel Sobocinski) * Categorical Models for Concurrency (Lecturer: Thomas Hildebrandt) The program for the summer school can be found at: http://www.itu.dk/research/theory/ctcs2004/summerschool.html Registration Deadline: July 1st. CMCIM WORKSHOP, August 11. In between the summer school and the CTCS conference, August 11th, there will be a half-day workshop on Categorical Methods in Concurrency, Interaction and Mobility. The workshop has previously been held in connection with CONCUR 2002 and CONCUR 2003. We invite submissions of extended abstracts (less than 5 pages), presenting recent results, challenges or work in progress. There will be no formal proceedings of the workshop, informal proceedings will be distributed at the workshop. Thus, accepted material may be published elsewhere at a later date. Workshop participation is *free*, but requires registration. Registration is done by sending an email to hilde@itu.dk, containing `CMCIM2004-registration' in the subject, and your full name and institution in the body. Submissions should be sent as PostScript files to: hilde@itu.dk, containing `CMCIM-submission' in the subject, and in the body the full names of the author(s), title, and a text-only abstract. Workshop Organizers: Thomas Hildebrandt Alexander Kurz CMCIM Workshop Registration Deadline: July 1st. CMCIM Workshop Submission Deadline: June 21th. ----------------------------------------------------------------- ACCOMODATION OPTIONS We have pre-booked a number of rooms for the conference and negotiated a special rate for CTCS'04 participants in a number of hotels, conveniently situated in the center of Copenhagen, but close to the metro that takes you to the ITU in a few minutes. Please note that you must make a final reservation for one of these rooms prior to July 1st in order to benefit from the pre-booking and the special rates. Cheaper accomodation is possible at a nearby youth hostel during the summer school and conference. Book before May 15th to be sure to get a room. See http://www.itu.dk/research/theory/ctcs2004/accomodation.html ----------------------------------------------------------------- CONFERENCE, SUMMER SCHOOL and WORKSHOP HOMEPAGE Updated information is available from Conference: http://www.itu.dk/research/theory/ctcs2004/ Summer School: http://www.itu.dk/research/theory/ctcs2004/summerschool.html ----------------------------------------------------------------- SPONSORSHIP The CTCS conference and summer school are APPSEM-II events, sponsored by the FIRST graduate school (www.first.dk) and the Theory Department at the IT University of Copenhagen (www.itu.dk/English/research/theory/) ----------------------------------------------------------------- POSTER http://www.itu.dk/research/theory/ctcs2004/plakata4.pdf From rrosebru@mta.ca Sun Apr 4 15:19:01 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 04 Apr 2004 15:19:01 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BAC9H-00006H-00 for categories-list@mta.ca; Sun, 04 Apr 2004 15:15:11 -0300 Message-ID: <406C5848.7080709@cs.york.ac.uk> Date: Thu, 01 Apr 2004 18:58:32 +0100 From: Ian Miguel User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.4) Gecko/20030707 X-Accept-Language: en-us, en MIME-Version: 1.0 To: undisclosed-recipients:; Subject: categories: CP Newsletter Vol 0, Number 1 Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 8 [from moderator: this item will be posted once only, if you want to subscribe see the text] With apologies for multiple copies: Constraint Programming News volume 0, number 1, 2004 Full version at http://www.math.unipd.it/cp-online/newsletter Subscribe at http://www.math.unipd.it/cp-online/register Editors: Jimmy Lee (events, career news), Eric Monfroy (profiles, publications) Toby Walsh (news, reports). CONTENTS - news: CP05, CP06, CP elections .. - events: forthcoming conferences and workshops - career news: job adverts - publications: PhD theses, recent books - reports: AI&Maths 04 - profiles: Nantes NEWS Welcome to the first number of CP News, an initiative of the CP organizing committee. We aim to provide a comprehensive summary of important news in the area of constraint programming. The newsletter will be published quarterly on 1st January, 1st April, 1st July, 1st October. Please email the relevant editor with any news, event, report or profile you want published. To subscribe, please visit http://www.math.unipd.it/cp-online/register The CP organizing committee recently decided that CP-2005 will be held in Sitges (near Barcelona) October 1st to 5th 2005. The conference will be co-located with ICLP. Pedro Meseguer and Javier Larrosa will be local chairs. Peter van Beek will be the program chair. The local organizers have already arranged for an Annular Solar Eclipse to take place in Spain during the conference. The CP organizing committee also decided that CP-2006 will be held in Nantes in 2006. Eric Monfroy and Frederic Benhamou will be the local chairs. Each year, the CP community has the opportunity to elect two new members to serve on the CP organizing committe. The committee consists of 10 members: 6 elected members, and 4 members drawn from the current and past local and program chairs. If you wish to stand in this year's election, please send your name and a short election statement to the Secretary of the Organizing Committee, Toby Walsh (tw@4c.ucc.ie) by 1st June 2004. The electronic elections will be held over the summer and the results announced at CP-2004. Finally, don't forget. April 19th is the deadline to apply for the CP 2004 Doctoral Programme .This is a forum held during the CP conference to give PhD students visibility and an opportunity to discuss research and career objectives with established researchers. More details at http://ai.uwaterloo.ca/~cp2004/cfdc.html PUBLICATIONS PhD theses: Santiago Macho Gonzalez, "Open Constraint Satisfaction", EPFL http://liawww.epfl.ch/People/akira.html Zeynep Kiziltan, "Symmetry breaking ordering constraints", Uppsala University http://publications.uu.se/theses/abstract.xsql?dbid=3991 Charlotte Truchet. Constraints, local search and computer assisted composition. University Paris 7. http://www-poleia.lip6.fr/~truchet/These/index-eng.html Recent books K.R. Apt Principles of Constraint Programming, Cambridge University Press (August 2003), xiv + 407 pages. ISBN: 0521825830. Rina Dechter Constraint Processing Morgan Kaufmann (May 2003) , 480 pages. ISBN: 1558608907. Thom Fruhwirth, Slim Abdennadher Essentials of Constraint Programming Series: Cognitive Technologies, Springer Verlag (2003), IX, 145 p. 27 illus., ISBN: 3-540-67623-6. EVENTS CP-AI-OR'04, International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimisation Problems. 20-22 April 2004, Nice, France. http://www-sop.inria.fr/coprin/cpaior04/ First Workshop on Constraint Handling Rules. May 10 - May 14, 2004, University of Ulm, Germany. http://www.informatik.uni-ulm.de/pm/veranstaltungen/chr2004/ SAT 2004, Seventh International Conference on Theory and Applications of Satisfiability Testing. 10-13 May 2004, Vancouver, Canada http://www.satisfiability.org/SAT04/ FLAIRS 2004, Special Track on Constraint Solving and Programming. 17-19 May, 2004, Miami Beach, Florida, USA. http://www.cs.ucc.ie/~osullb/flairs2004/ CORS/INFORMS 2004 Joint International Meeting, 16-19 May 2004, Banff, Alberta, Canada. http://www.informs.org/Conf/CORS/ ICAPS 2004, 14Th International Conference on Automated Planning & Scheduling. June 3-7 2004, Whistler, British Columbia, Canada. http://www.cc.gatech.edu/fac/Sven.Koenig/icaps/icaps04/ CDB 2004, 1st International Symposium on Applications of Constraint Databases (in conjunction with SIGMOD-PODS 2004). June 12 - 13, 2004, Paris, France. http://alpha.luc.ac.be/~lucp1265/cdb04.html PADL'04, Sixth International Symposium on Practical Aspects of Declarative Languages 2004. Jun 18-19, 2004, Dallas, Texas, USA. http://www.cse.buffalo.edu/PADL04 CSCLP 2004: Joint Annual Workshop of ERCIM/CoLogNet on Constraint Solving and Constraint Logic Programming, 23-25 June 2004, EPFL, Lausanne, Switzerland Paper submission deadline: 10 May. http://liawww.epfl.ch/Events/ercim04/ AAAI 2004, The Nineteenth National Conference on Artificial Intelligence. July 25 - 29, 2004, San Jose, California, USA. http://www.aaai.org/Conferences/National/2004/aaai04.html ECAI 2004 workshop on "Modelling and Solving Problems with Constraints", 22 August 2004, Valencia, Spain. Paper submission deadline: 4 May http://4c.ucc.ie/~brahim/ecai04ws/ ECAI 2004 workshop on "Constraint Satisfaction Techniques for Planning and Scheduling Problems", 23 August 2004, Valencia, Spain. Paper submission deadline: 15 April. http://www.dsic.upv.es/~msalido/workshop-ecai04/index.html ECAI 2004 workshop on "Configuration", 23-24 August 2004, Valencia, Spain. Paper submission deadline: 1 April. http://www.ifi.uni-klu.ac.at/Conferences/ECAI04-Configuration-Workshop ECAI 2004 tutorial on "Constraint Processing", Pedro Meseguer, Thomas Schiex 24 August 2004, Valencia, Spain. STAIRS 2004, 2nd European Starting AI Researcher Symposium. August 23-24, 2004, Valencia, Spain. Paper submission deadline: April 7, 2004. http://www.dsic.upv.es/ecai2004/stairs2004/cfp/style.html ECAI 2004, 16th European Conference on Artificial Intelligence (2004). 22-27 August, 2004, Valencia, Spain. http://www.dsic.upv.es/ecai2004/ CICLOPS'04, Colloquium on Implementation of Constraint and LOgic Programming Systems (held in conjunction with ICLP'04). 6-10 September, 2004, Saint-Malo, France. Paper submission deadline: April 26, 2004. http://clip.dia.fi.upm.es/Conferences/CICLOPS-2004/ COLOPS'04, 2nd International Workshop on COnstraint & LOgic Programming in Security (held in conjunction with ICLP'04). 6-10 September, 2004, Saint-Malo, France. Workshop Coordination: Frank Valencia (Frank.Valencia@it.uu.se) MultiCPL 2004, 3rd International Workshop on Multiparadigm Constraint Programming Languages (held in conjunction with ICLP'04). 6-10 September, 2004, Saint-Malo, France. Paper submission deadline: May 9, 2004. http://uebb.cs.tu-berlin.de/MultiCPL04 ICLP'04, Twentieth International Conference on Logic Programming. 6-10 September, 2004, Saint-Malo, France. http://www.irisa.fr/manifestations/2004/ICLP04/ KI2004, 27th GERMAN CONFERENCE ON ARTIFICIAL INTELLIGENCE. September 20-24, Ulm, Germany. Paper submission deadline: April 8. http://ki2004.uni-ulm.de/ AISC 2004, 7th International Conference on ARTIFICIAL INTELLIGENCE AND SYMBOLIC COMPUTATION. September 22-24, 2004, RISC (Research Institute for Symbolic Computation), Castle of Hagenberg, Austria. Paper submission deadline: May 1, 2004. http://www.risc.uni-linz.ac.at/conferences/aisc2004/ CP 2004, Tenth International Conference on Principles and Practice of Constraint Programming, 27 September - 1 October 2004, Toronto, Canada Paper submission deadline: 16 April. http://ai.uwaterloo.ca/~cp2004/ MOZ 2004, Second International Mozart/Oz Conference (MOZ 2004). 7-8 Oct, 2004, Charleroi, Belgium. Paper submission deadline: 9 July. http://www.cetic.be/moz2004. ICAPS 2006, 16Th International Conference on Automated Planning & Scheduling. Call for Proposals deadline: 21 May 2004. Information about previous ICAPS conferences is available at http://www.icaps-conference.org/. CAREER NEWS Research Assistant (planning with incomplete knowledge). M.Sc. or Ph.D. degree or equivalent in computer science. Initially for two years, with a possible extension to a third year. Salary is class 2a in the German BAT scale (about 1500 euro a month after taxes for an unmarried person of age 26. More if you are older or married.) Dr. Jussi Rintanen Institut fuer Informatik Albert-Ludwigs-Universitaet Freiburg email: rintanen@informatik.uni-freiburg.de AI Engineers (advanced configuration and ordering technology) Edgenet Inc, Nashview, TN, USA http://www.edgenet.com Please email your resume to rajeshATedgenetDOTcom (replace AT by @ and DOT by .) REPORTS Eighth International Symposium on Artificial Intelligence and Mathematics. Program Chairs: Fahiem Bacchus and Peter van Beek. 4-6 January 2004 http://rutcor.rutgers.edu/~amai/aimath04/ The online newsletter contains a full report about this conference, which featured sessions on constraints, preferences, satisfiability, portfolio design, and game theory. http://www.math.unipd.it/cp-online/newsletter PROFILES The Nantes CP community is composed of researchers from two institutions: -the CoCoA group (Continuous Constraints and Applications) of the University of Nantes (http://www.sciences.univ-nantes.fr/lina/) -the CD group (Discrete Constraints) of the Ecole des Mines de Nantes (http://www.emn.fr/) These two themes are grouped together in the new CNRS common research structure: the LINA. All together, this amounts to 13 faculties. Our main goal is to develop techniques, languages, and tools for discrete and continuous constraints. A longer profile of the activities of the Nantes CP community can be found in the online newsletter. http://www.math.unipd.it/cp-online/newsletter From rrosebru@mta.ca Sun Apr 4 15:19:01 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 04 Apr 2004 15:19:01 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BACA0-00008x-00 for categories-list@mta.ca; Sun, 04 Apr 2004 15:15:56 -0300 Message-Id: Date: Fri, 2 Apr 2004 14:24 +0200 From: femke@few.vu.nl (Femke van Raamsdonk) To: categories@mta.ca Subject: categories: RTA'04: call for participation Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 9 ************************************* * * * RTA'04 CALL FOR PARTICIPATION * * * ************************************* The 15th International Conference on REWRITING TECHNIQUES AND APPLICATIONS http://www-i2.informatik.rwth-aachen.de/RTA04/ and the workshops * HOR 2nd int. workshop on higher-order rewriting * RULE 5th int. workshop on rule-based programming * WFLP 13th int. workshop on functional and (constraint) logic programming * WRS 4th int. workshop on reduction strategies in rewriting and programming * WST 7th int. workshop on termination * WG 1.6 IFIP working group 1.6 on term rewriting together form the Federated Conference on Rewriting, Deduction and Programming (RDP'04). RDP'04 takes place in Aachen, Germany, in the period May 31 - June 5, 2004. Registration for RTA and the workshops is now open ! The deadline for early registration is APRIL 30, 2004. Please see the webpage for further information. INVITED TALKS will be given at RTA'04 by: * Neil Jones (Copenhagen) * Aart Middeldorp (Innsbruck) * Robin Milner (Cambridge) For further questions please contact the conference chair: RTA'04 CONFERENCE CHAIR: Juergen Giesl RWTH Aachen giesl@informatik.rwth-aachen.de From rrosebru@mta.ca Wed Apr 7 21:31:41 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 07 Apr 2004 21:31:41 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BBNOW-0000uX-00 for categories-list@mta.ca; Wed, 07 Apr 2004 21:27:48 -0300 Message-ID: <32834.62.252.132.136.1081274520.squirrel@mail.maths.gla.ac.uk> Date: Tue, 6 Apr 2004 19:02:00 +0100 (BST) Subject: categories: preprint: Are operads algebraic theories? From: "Tom Leinster" To: X-Priority: 3 Importance: Normal X-Mailer: SquirrelMail (version 1.2.10) MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 10 The following article (7 pages) is available: "Are operads algebraic theories?" I exhibit a pair of non-symmetric operads that, although not themselves isomorphic, induce isomorphic monads. The existence of such a pair implies that if 'algebraic theory' is understood as meaning 'monad', operads cannot be regarded as algebraic theories of a special kind. http://arxiv.org/abs/math.CT/0404016 Best wishes, Tom From rrosebru@mta.ca Wed Apr 7 21:31:41 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 07 Apr 2004 21:31:41 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BBNQ7-00012z-00 for categories-list@mta.ca; Wed, 07 Apr 2004 21:29:27 -0300 To: categories@mta.ca Subject: categories: Re: arithmetical and geometric reals in (models of) SDG Reply-To: Andrej Bauer References: <200403261407.PAA29318@fb04209.mathematik.tu-darmstadt.de> From: Andrej Bauer Date: Wed, 07 Apr 2004 15:00:23 +0200 Message-ID: <834qrw0wpk.fsf@haka.fmf.uni-lj.si> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 11 Thomas Streicher writes: > > Recently I was asking myself what is the relation between the arithmetical > (Dedekind) reals in a topos and a ring R satisfying the usual SDG axioms > (i.e. at least the Kock-Lawvere) axiom. Perhaps it is worth mentioning that in the ring of smooth reals R the sequence a_k = 2^(-k) is Cauchy but has many "limits" because every infinitesimal dx satisfies the condition "dx is the limit of a_k". This shows that R is not Cauchy complete, not because limits of Cauchy sequences are missing but because there are too many. I once thought the above observation implied there can be no isometric embedding of a Cauchy-complete field (e.g. the Dedekind reals) into R, but now I am not convinced anymore. Andrej Bauer Department of Mathematics and Physics University of Ljubljana http://andrej.com From rrosebru@mta.ca Wed Apr 7 21:31:41 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 07 Apr 2004 21:31:41 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BBNOv-0000wL-00 for categories-list@mta.ca; Wed, 07 Apr 2004 21:28:13 -0300 Date: Tue, 6 Apr 2004 12:27:00 -0700 (PDT) From: John MacDonald To: categories@mta.ca Subject: categories: International Category Theory Conference(CT04) Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: X-Keywords: X-UID: 12 FOURTH ANNOUNCEMENT INTERNATIONAL CATEGORY THEORY CONFERENCE (CT04) July 18-24, 2004 University of British Columbia Vancouver, Canada This conference will be held on the University of British Columbia campus. It will begin with a reception at 6pm on Sunday July 18, 2004, and will end at 1pm on Saturday July 24, 2004. All those interested in category theory and its applications are welcome. Following is the first draft of the CT04 Participant List. If your name does not appear on the list and you think that you will attend or may attend, then please send a note to johnm@math.ubc.ca with the words "will attend" or "may attend", as appropriate. Information about deadlines for abstracts, registration and accommodation may be found at the end of this letter as well as on the course website http://www.pims.math.ca/science/2004/CT04 CT04 Participant List: Jiri Adamek, University of Braunschweig, Germany Steve Awodey, Carnegie Mellon University, USA Michael Barr, McGill University, Canada Michael Batanin, Macquarie University, Australia Dominique Bourn, Universite du Littoral, France Pilar Carrasco, University of Granada, Spain Claudia Centazzo, Louvain-la-Neuve, Belgium Maria Manuel Clementino, University of Coimbra, Portugal Robin Cockett, University of Calgary, Canada Ana Isabel Dias, Fluminense University, Brazil Eduardo Dubuc, University of Buenos Aires, Argentina John Duskin, University at Buffalo, USA Peter Freyd, University of Pennsylvania, USA Dale Garraway, Eastern Washington University, USA Marino Gran, Universite du Littoral, France Marco Grandis, University of Genoa, Italy Xiuzhan Guo, University of Calgary, Canada Michael J. Healy, University of Washington, USA Dana Harrington, University of Calgary, Canada Michel Hebert, American University, Cairo, Egypt David Holgate, University of Stellenbosch, South Africa George Janelidze, Capetown, South Africa Zurab Janelidze, Tbilisi State University, Georgia Michael Johnson, Macquarie University, Australia Peter Johnstone, Cambridge University, UK Yefim Katsov, Hanover, Indiana, USA Max Kelly, University of Sydney, Australia Anders Kock, Aarhus University, Denmark Steve Lack, University of Western Sydney, Australia F. William Lawvere, University at Buffalo, USA Tom Leinster, University of Glasgow, UK John MacDonald, University of British Columbia, Canada Stefan Milius, University of Braunschweig, Germany Susan Niefield, Union College, USA Robert Pare, Dalhousie University, Canada Craig Pastro, University of Calgary, Canada Tim Porter, University of Wales, UK Vaughan Pratt, Stanford University, USA Dorette Pronk, Dalhousie University, Canada Keith Rogers, University of Calgary, Canada Bob Rosebrugh, Mount Allison University, Canada Jiri Rosicky, Masaryk University, Czech Republic Phil Scott, University of Ottawa, Canada Christoph Schubert, University of Bremen, Germany Robert Seely, McGill University, Canada Priti Sinha, Indian Institute of Technology, Delhi, India Art Stone, Vancouver, Canada Ross Street, Macquarie University, Australia Isar Stubbe, Louvain-la-Neuve, Belgium Javad Tavakoli, Okanagan University College, Canada Michel Thiebaud, College de Stael, Carouge, Switzerland Christopher Townsend, Open University, UK Tim Van der Linden, Vrije University, Brussels, Belgium Enrico Vitale, Louvain-la-Neuve, Belgium Walter Tholen, York University, Canada Liam Wagner, University of Queensland, Australia Michael Warren, Carnegie Mellon University, USA Ralph Wojtowicz, University of Illinois, USA R. J. Wood, Dalhousie University, Canada Joao Xarez, University of Aveiro, Portugal Noson Yanofsky, City University of New York, USA Ma Zizhu, Zhejiang University, China Some important deadlines are as follows: Abstracts - May 31, 2004. Please use the form from the website. Registration Deposit or Early Registration payment - May 31, 2004 Accommodation - June 18, 2004. After this date the block of rooms reserved for CT04 will be released to the general public, although reservations can still be made if space is available. Early booking is recommended, especially for those with accompanying persons. Extra spaces for the excursion or banquet for accompanying persons - June 30, 2004. The excursion and banquet for delegates is included in the conference fee. CT04 Advisory Committee: Jiri Adamek, University of Braunschweig, Germany Michael Barr, McGill University, Canada Eduardo Dubuc, University of Buenos Aires, Argentina Marco Grandis, University of Genoa, Italy George Janelidze, Capetown, South Africa Michael Johnson, Macquarie University, Australia P. T. Johnstone, Cambridge University, UK F. W. Lawvere, University at Buffalo, USA J. MacDonald, University of British Columbia, Canada S. Niefield, Union College, USA T. Porter, University of Wales, UK Jiri Rosicky, Masaryk University, Czech Republic Phil Scott, University of Ottawa, Canada Robert Seely, McGill University, Canada Art Stone, Vancouver, Canada Ross Street, Macquarie University, Australia Enrico Vitale, Louvain-la-Neuve, Belgium Walter Tholen, York University, Canada R. J. Wood, Dalhousie University, Canada This conference is being organized with the help of the Pacific Institute of Mathematics(PIMS}. Please let me know of any errors, omissions or suggestions for changes that you may have. John MacDonald, Vancouver From rrosebru@mta.ca Thu Apr 8 10:41:13 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 08 Apr 2004 10:41:13 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BBZka-00049d-00 for categories-list@mta.ca; Thu, 08 Apr 2004 10:39:24 -0300 Message-Id: <200404080138.i381cCV24825@math-ws-n09.ucr.edu> Subject: categories: quantum quandaries - a category-theoretic perspective To: categories@mta.ca (categories) Date: Wed, 7 Apr 2004 18:38:12 -0700 (PDT) From: "John Baez" X-Mailer: ELM [version 2.5 PL6] MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 13 Dear Categorists - Some of you may enjoy this paper. It's written for philosophers of physics, so I take it a bit easy on the category theory, but it does explain why I think the *-category of Hilbert spaces and bounded linear operators is more important in physics than the mere category of Hilbert spaces and bounded linear operators. Best, jb ................................................................. http://math.ucr.edu/home/baez/quantum/ Quantum Quandaries: A Category-Theoretic Perspective John C. Baez To appear in _Structural Foundations of Quantum Gravity_, eds. Steven French, Dean Rickles and Juha Saatsi, Oxford U. Press. Abstract: General relativity may seem very different from quantum theory, but work on quantum gravity has revealed a deep analogy between the two. General relativity makes heavy use of the category nCob, whose objects are (n-1)-dimensional manifolds representing "space" and whose morphisms are n-dimensional cobordisms representing "spacetime". Quantum theory makes heavy use of the category Hilb, whose objects are Hilbert spaces used to describe "states", and whose morphisms are bounded linear operators used to describe "processes". Moreover, the categories nCob and Hilb resemble each other far more than either resembles Set, the category whose objects are sets and whose morphisms are functions. In particular, both Hilb and nCob but not Set are *-categories with a noncartesian monoidal structure. We show how this accounts for many of the famously puzzling features of quantum theory: the failure of local realism, the impossibility of duplicating quantum information, and so on. We argue that these features only seem puzzling when we try to treat Hilb as analogous to Set rather than nCob, so that quantum theory will make more sense when regarded as part of a theory of spacetime. Also available at http://www.arxiv.org/abs/quant-ph/0404040 From rrosebru@mta.ca Thu Apr 8 22:33:43 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 08 Apr 2004 22:33:43 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BBkr6-00046N-00 for categories-list@mta.ca; Thu, 08 Apr 2004 22:30:52 -0300 Date: Thu, 8 Apr 2004 17:08:14 -0700 From: Vaughan Pratt Message-Id: <200404090008.i3908Ev2029550@coraki.Stanford.EDU> To: categories@mta.ca Subject: categories: Re: quantum quandaries - a category-theoretic perspective Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 14 Good morning -- very, what with not just one but two very interesting papers, from Tom Leinster and John Baez. The following from John's abstract got my immediate attention: >We argue that these features only seem puzzling when we try to treat Hilb >as analogous to Set rather than nCob, so that quantum theory will make more >sense when regarded as part of a theory of spacetime. This calls for an immediate response. I've argued elsewhere (perhaps not sufficiently forcefully?) that Set is _very_ analogous to Hilb, _as part of a *-category_. The easily made mistake with Set is to view it as an autonomous category in its own right (ok, so that's not a mistake in many contexts, but it is when proposing to incorporate Set into a Theory of Everything). A much better view is Girard's (which he applies to logic, but logic is, or should be, a reflection of reality). Girard starts out with a *-autonomous universe (of propositions if doing logic, of objects if doing mathematics). He obtains comonoids (intuitionistic logic if doing logic, sets or related objects forming a CCC if doing mathematics) by finding them in a smaller cartesian closed retract of the big universe, via bang, of-course. (One can in fact have a hierarchy of bangs, with the bigger bangs delivering dyadic, ..., n-adic comonoids and the smaller ones delivering posets, sets, finite sets, finite sets of even cardinality, etc.) This view of intuitionistic logic as a fragment of the bigger linear logic, and of comonoid objects such as sets as a fragment of a bigger mathematical universe, has the following benefits. 1. It locates signature in the object. Traditionally signature is determined by context. Typical contexts are a theory such as the theories of groups, vector spaces, Boolean algebras, etc., or a category such as the categories of any of these. The signature thus resides not in the objects but in the theories or categories of those objects. Instead I propose to view all structure of an object, including its signature, as an intrinsic property of that object independently of what signature and structure other objects in the same universe might have. This then permits dispensing with either theories or categories, at least in their role as specifiers of either signature or structure. To this end, organize each object A as a set of subjects, a set of predicates, and an inference rule for taking A out of the loop in order to get straight to the truth about the structure of A. The only context needed is a tensor unit I and its dual \Omega. Subjects: the arrows I->A Predicates: the arrows A->\Omega Rule: The compositions I->\Omega that bypass A, taking it out of the loop This is a way of looking at Chu(Set,\Omega). A Chu space (A,r,X) is a set A of subjects, a set X of predicates, and a rule r:AxX -> \Omega giving the value r(a,x) of predicate x at subject a directly. A Chu space has no other signature or structure. The Chu construction embeds any autonomous category V with pullbacks autonomously into the *-autonomous category Chu(V,k), via an arbitrary selection of object k of V. Chu(Set,\Omega) embeds Set autonomously---no need to abandon the autonomous structure on Set, and it is located in the broader context of a universe whose properties can be considered "puzzling features" in John's sense. While this simple representation might not seem capable of accommodating much structure, an impressively wide variety of structures for objects are achievable with it. For example, the structure of a Hilbert space, as Lafont and Streicher point out, is representable as a Chu space simpy by taking \Omega to be the set of complex numbers, without committing \Omega to any particular properties of or operations on the complex numbers, simply taking it to be a pure set. (Actually L&S only embed Vct, but Hilb is easily embedded as well simply by disallowing a few predicates in their Vct embedding; also they don't actually say "Chu" and "*-autonomous," but they could have.) Chu(Set,\Omega) embeds Set autonomously into the same *-autonomous universe that also embeds Hilb. Any difference between sets and Hilbert spaces is internal to those objects, as opposed to being determined by context as done traditionally. 2. It furnishes a strikingly simple explanation for the "puzzling features" John alludes to. Once the place of Set in the grander scheme of things is seen, these "puzzling features" that are traditionally accounted for in terms of Hilbert spaces can really be seen as having a more fundamental origin: structure. (As a slight digression on whether it is fair to characterize sets as really being devoid of structure, certainly their *elements* are discretely organized, but their *predicates* are highly organized. The discreteness is really a result of emphasizing the elements over the predicates; the same object viewed from the dual perspective interchanging these is heavily structured!) Granted Hilbert spaces give rise to puzzling features, but complete semilattices give rise to essentially the same puzzling features. It is not Hilbert spaces or complete semilattices that are doing this, it is the much broader notion that *structure* is doing this. Hilbert spaces are just structured objects; so are complete semilattices; so are sets. My views on the role of structure in creating the strangeness of quantum mechanics appeared in an early form in 1992 in "Linear Logic for Generalized Quantum Mechanics," without Chu spaces however, available as http://boole.stanford.edu/pub/ql.pdf >From the abstract: "In this extension [of quantum reasoning] the uncertainty tradeoff [of complementary or dual quantities] emerges via the structure veil." The paper argues that the basis for Heisenberg uncertainty is the structure veil as an unavoidable phenomenon on one side of the duality or the other attributable to Stone duality, not just qualitatively but even quantitatively to some extent. Shortly thereafter I realized that Chu spaces was the perfect framework for these ideas, and described the idea at the 1992 Cosener's House (Abingdon) meeting on domain theory and games, where I characterized Chu(Set,K) as "A Theory of Everything dual to a Model of Everything." Subsequent papers further developed the theme, e.g. "Rational Mechanics and Natural Mathematics" (TEMPUS'94 notes), "Chu Spaces: Automata with Quantum Aspects" (PhysComp'94), and "The Stone Gamut" (LICS'95). In these more recent papers I tightened up the quantitative aspect of structural uncertainty result by furnishing every Chu space with its own "Planck's constant" defined as the reciprocal of the area of the Chu space, which works beautifully! I've largely neglected this QM relationship lately, partly due to competing interests, but also from a sense that, for whatever reason, the idea simply was not taking hold. Something was wrong: the idea, the audience, the timing, the exposition, ... I knew neither what to fix nor how fix it. If I ever find out I'll certainly be more than happy to write further on the notion of quantum mechanics as the reflection in nature of pure structure, as opposed to the conventional wisdom that ties it to specific structures such as Hilbert space. If anyone would like to argue against this, i.e. that pure structure is *not* a good basis for quantum mechanics, the title "A Critique of Pure Structure" has been taken only in the context of "The Limits of Rationality and Culture in the Transition from Feudalism to Capitalism." Anyway, on to point 3: 3. It saves mathematics from Cantor's paradise. In the *-autonomous view of Set as part of something bigger, a set A has not just elements but also predicates. Whereas the elements are structured discretely, the predicates are structured logically, e.g. as a Boolean algebra. Forming the power set of A as \Omega^A or A-o\Omega means not the production of an exponentially larger set, but instead the swapping of the elements and predicates of A. It is natural to want to repeat this as \Omega^\Omega^A or (A-o\Omega)-o\Omega, but (as I mentioned in a post a couple of weeks ago), as long as one remembers that power sets are heavily structured then one simply recovers the original set A after the second swap. "Doubly exponential" then has its involutory connotation as in logic rather than its hugeness connotation as in set theory or combinatorics. We all want to go to paradise eventually, some just sooner than others. Combinatorialists and others sometimes want these huge numbers now. This is accomplished with bang. Replacing the Boolean algebra B having 2^n elements and n predicates (aka ultrafilters) with !B leaves the elements unchanged while greatly increasing the number of predicates from n to 2^2^n, a double whammy right there with one bang! (This assumes \Omega=2 and Set bang; other choices of \Omega and bang will give different cardinalities but the general idea remains the same.) One should measure combinatorial growth neither by the number of iterations of exponentiation (which is an involution), nor by the number of bangs (which is idempotent at least for little chu), but by the number of *alternations* of exponentiation and bang. Apropos of the "hierarchy of bangs" mentioned above, I'll be talking next month in X'ian about using comonoids to generalize CPOs so that they work more like logic. CPOs are designed for the passage from A to A-and-B, whereas logic caters not only for that passage but also the other direction, from A to A-or-B. The CCC of comonoids addresses both directions, and moreover symmetrically. I would *love* to know whether all T1 comonoids are discrete. This question applied to the special case of DCPOs is positively answered as an obvious consequence of how one topologizes DCPOs, and the same holds for Lamarche's larger CCC of "casuistries." Neither of these enjoys the above-mentioned up-down symmetry of logic however. For the yet larger CCC of comonoids, where this symmetry kicks in, the question seems to be dauntingly difficult, and I've been posing it to people for eight years. A year ago I decided it was high time to offer some sort of bounty on the problem, currently at $2,000, see http://thue.stanford.edu/puzzle.html for more details. Vaughan Pratt From rrosebru@mta.ca Fri Apr 9 19:13:20 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 09 Apr 2004 19:13:20 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BC4DP-0001Ic-00 for categories-list@mta.ca; Fri, 09 Apr 2004 19:11:11 -0300 From: Topos8@aol.com Message-ID: <130.2d716cd9.2da83e89@aol.com> Date: Fri, 9 Apr 2004 13:59:37 EDT Subject: categories: Omega categories paper from Carl Futia To: categories@mta.ca MIME-Version: 1.0 Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 15 I've just completed a paper entitled "Omega Categories I". The abstract appears below. I am trying to post this paper on the math archive but haven't yet succeeded because I lack an adademic affiliation. In the meantime anyone who would like a copy may obtain one from me upon request. I'll send it to you as an uncompressed Postscript file attached to an e-mail message. Carl Futia ********************************************************************* ABSTRACT: We develop a theory of weak omega categories that will be accessible to anyone who is familiar with the language of categories and functors and who has encountered the definition of a strict 2-category. The most remarkable feature of this theory is its simplicity. We build upon an idea due to Jaques Penon by defining a weak omega category to be a span of omega magmas with certain properties. (An omega magma is a reflexive, globular set with a system of partially defined, binary composition operations which respects the globular structure.) Categories, bicategories, strict omega categories and Penon's weak omega categories are all instances of our weak omega categories. We offer a heuristic argument to justify the claim that Batanin's weak omega categories also fit into our framework. We show that the Baez-Dolan stabilization hypothesis is a direct consequence of our definition of weak omega categories. We define a natural notion of a psuedo-functor between weak omega categories and show that it includes the classical notion of a homomorphism between bicategories. In any weak omega category the operation of composition with a fixed 1-cell defines such a psuedo-functor. Finally, we define a notion of weak equivalence between weak omega categories which generalizes the standard definition of an equivalence between ordinary categories. From rrosebru@mta.ca Fri Apr 9 19:13:20 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 09 Apr 2004 19:13:20 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BC4CG-0001Eb-00 for categories-list@mta.ca; Fri, 09 Apr 2004 19:10:00 -0300 Date: Fri, 9 Apr 2004 11:56:18 +0100 (BST) From: Paul B Levy To: categories@mta.ca Subject: categories: Re: quantum quandaries - a category-theoretic perspective In-Reply-To: <200404090008.i3908Ev2029550@coraki.Stanford.EDU> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 16 Hi Vaughan, > This view of intuitionistic logic as a fragment of the bigger linear logic, is widely held but I don't agree with it. A model of (propositional) intuitionistic logic is a bicartesian closed category. (I'm assuming we want to model proofs, not just provability.) But a model of linear logic doesn't, as far as I'm aware, give rise to a bicartesian closed category. So there's no translation (at the level of proofs, rather than provability) from intuitionistic logic to linear logic. Paul From rrosebru@mta.ca Fri Apr 9 19:14:29 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 09 Apr 2004 19:14:29 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BC4Eq-0001SM-00 for categories-list@mta.ca; Fri, 09 Apr 2004 19:12:40 -0300 Message-Id: <200404092118.i39LIdJp024467@coraki.Stanford.EDU> To: categories@mta.ca Subject: categories: Re: quantum quandaries - a category-theoretic perspective Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Date: Fri, 09 Apr 2004 14:18:39 -0700 From: Vaughan Pratt Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 17 Hi, Paul, >> This view of intuitionistic logic as a fragment of the bigger linear logic, >is widely held but I don't agree with it. What's to disagree with? Girard's ! admits bicartesian models. >But a model of linear logic doesn't, as far as I'm aware, give rise to a >bicartesian closed category. "Give rise to"? Granted the LL axioms don't stipulate that the image of bang be bicartesian (have sum in addition to product), but neither do they disallow it. The interpretations of ! encountered in LL applications tend to be bicartesian closed, in particular the one that my message was all about, namely Set. >So there's no translation (at the level of proofs, rather than >provability) from intuitionistic logic to linear logic. Perhaps so, but then that's your problem, you're the one who's insisting on a different definition of "intuitionistic" from the one Girard had in mind when he axiomatized !. If he'd wanted bicartesian closed, the axioms for ! would have said so. Since you're the one who wants it, the responsibility for axiomatizing ! accordingly is yours, not Girard's. Vaughan Pratt From rrosebru@mta.ca Sat Apr 10 12:08:00 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 10 Apr 2004 12:08:00 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BCK19-0003MD-00 for categories-list@mta.ca; Sat, 10 Apr 2004 12:03:35 -0300 From: Marcus Kracht Reply-To: kracht@humnet.ucla.edu Organization: UCLA To: kracht@humnet.ucla.edu Subject: categories: NASSLLI04 Call for Participation Date: Fri, 9 Apr 2004 16:49:27 -0700 User-Agent: KMail/1.5.4 MIME-Version: 1.0 Content-Disposition: inline Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Message-Id: <200404091649.28003.kracht@humnet.ucla.edu> X-Probable-Spam: no X-Spam-Hits: 0 X-Scanned-By: vscan.smtp.ucla.edu Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 18 [Apologies for multiple postings!] NASSLLI04 (North American Summer School of Logic, Language and Information) UCLA, Los Angeles, June 21-25, 2004 (http://www.linguistics.ucla.edu/nasslli04/index.html) Call for Participation The mission of the summer school is to foster exchange of ideas across disciplines in the areas of logic, language, and information. This year the following courses are offered: COURSES Matthias Baaz (Technical University of Vienna): "The Generalization of Proofs and Calculations" Roberto Di Cosmo and Delia Kesner (University of Paris 7): "Introduction to Linear Logic and Sequent Calculus" (to be confirmed) Tim Fernando (Trinity College, Dublin): "Natural Language Semantic Representations as Types" Hans-Martin Gaertner (ZAS, Berlin): "Embedded Root Phenomena: Linguistic, Formal and Philosophical Aspects" Valentin Goranko (Rand Afrikaans University, Johannesburg): "Temporal Logics of Computations" Jason Hickey and Aleksey Nogin (California Institute of Technology, Pasadena): "Introduction into Formal Computer-Aided Reasoning and the MetaPRL Theorem Prover" James Higginbotham (University of Southern California, Los Angeles): "Speaking of Events" Gerhard Jaeger (Stanford University and University of Potsdam) and Rob van Rooy (University of Amsterdam): "Language Games and Evolution" Larry Moss (Indiana University, Bloomington): "Logic, Language and Information" Carl Pollard (The Ohio State University, Columbus): "Higher Order Grammar" James Rogers (Earlham College, Richmond): "Formal Foundations of Model-Theoretic Syntax" Thomas Ede Zimmermann (University of Frankfurt): "Classical Montague Grammar" REGISTRATION Visit http://www.linguistics.ucla.edu/nasslli04/index.html for all details. Basically, all participants need to make their own hotel reservations. The web site gives you a list of hotels. You may try to email them, but some only book rooms if you call them. TRAVEL AND HOTEL INFORMATION The web site also contains information on how to reach UCLA. The conference office will be in the linguistics department, the location of the lecture halls in philosophy (5mins walk). For further information feel free to contact us at Marcus Kracht . -- Marcus Kracht Department of Linguistics, UCLA 3125 Campbell Hall PO Box 951543 Los Angeles, CA 90095-1543 kracht@humnet.ucla.edu From rrosebru@mta.ca Sat Apr 10 12:08:01 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 10 Apr 2004 12:08:01 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BCJzS-0003H5-00 for categories-list@mta.ca; Sat, 10 Apr 2004 12:01:50 -0300 Date: Fri, 9 Apr 2004 21:24:21 -0400 (EDT) From: Michael Barr To: Categories list Subject: categories: My ftp site Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 19 Nearly every paper I have published (or in one case, not) since 1986 is now available on my ftp site: ftp.math.mcgill.ca/pub/barr/pdffiles where they can be read by anyone with an Adobe reader. There is also an index file (called 0index.pdf so it will appear first). Eventually, I may add abstracts to the index file. Michael From rrosebru@mta.ca Sun Apr 11 18:37:48 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 11 Apr 2004 18:37:48 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BCmZR-0007Yr-00 for categories-list@mta.ca; Sun, 11 Apr 2004 18:32:53 -0300 To: categories@mta.ca Subject: categories: Re:arithmetical and geometric reals in (models of) SDG Date: Sat, 10 Apr 2004 18:28:20 -0400 From: wlawvere@buffalo.edu Message-ID: <1081636100.4078750448ac1@mail2.buffalo.edu> X-Mailer: University at Buffalo WebMail Cyrusoft SilkyMail v1.1.10 24-January-2003 MIME-Version: 1.0 Content-Type: text/plain Content-Transfer-Encoding: 8bit X-Originating-IP: 128.205.249.126 X-Originator-Info: login-id=wlawvere, server=buffalo.edu Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: X-Keywords: X-UID: 20 The map from Euler reals to Dedekind reals is not injective (1) The rig of uppercuts in Q serves as value-space for metrics; call it the Dedekind reals for short. (Mapping a ring to the Dedekind reals would only hit two-sided cuts, but that is a separate issue. If Q denotes the nonnegative rationals, then the term "arithmetic reals" would be justified, but for the issue addressed here, Q might as well be "the constant reals" coming from a lower topos). (2) Euler affirmed that a real should be determined as a ratio between infinitesimals. Adopting a rational definition of "ratios", and conservatively interpreting the appropriate space T of infinitesimals as the representing object for the tangent-bundle functor, I call Euler reals the part R of the function-space T^T that preserves the base point. (T is regarded as given as a reflection of physical experience, so not every topos has one. R typically has a unique addition compatible with the obvious multiplication. If we define D as the part of R of square 0, the Kock-Lawvere axiom would require that there exist units of time, i.e., isomorphisms T->D, or equivalently certain non-unique semigroup structures on T itself (in contrast with the canonical multiplication on our R)). (3) Philosophically, the Euler reals serve not only to parameterize motion but also to provide a means to express a cause of motion; the cause operates at each single time, as is reflected in the fact that T has a unique point. By contrast, the Dedekind reals serve to measure, by Q-approximations, the changes resulting from motion between pairs of times. Measuring, like photographing, kills the particular motion; thus the map from Euler reals to Dedekind reals, should not be expected to be injective. That map needs to be understood in any smooth topos of interest,. (a) Of course, measuring can still derive information, perhaps even enough information, about the causes of motion too: we can pass to another moving quantity, e.g. velocity via a speedometer, and then measure that via rational approximation. There is an analogy with algebraic topology: pizero is a very crude measure of a space, it would seem, but as Sammy liked to point out, if you apply an appropriate geometrical endofunctor first, then pizero can deliver lots of useful information.) (b) Any given object in a smooth topos will induce a function presheaf on finite-dimensional varieties; since continuous functions are not usually smooth functions, it is unlikely that the Dedekind reals (even two-sided) will be included in R.) (4) However, an inclusion Q->R of constants is to be expected; it forms one ingredient for constructing the map under discussion. The other ingredient is an ordering on R, inducing in the obvious way the map from R to parts of Q. Several treatments of SDG postulate such an ordering, but it always seems to turn out that the ordering is not anti-symmetric (in particular that any closed interval is closed under the addition of infinitesimals), illustrating the non-injectivity of the map. (In some cases there seem to be ways to construct the ordering "synthetically", i.e., by categorical operations, such as pizero(Aut(T)), applied ultimately to the object T.) I hope this will suggest some clarification of the questions raised by Thomas and Andrej. Bill Lawvere From rrosebru@mta.ca Tue Apr 13 08:23:44 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 13 Apr 2004 08:23:44 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BDLwR-0002lN-00 for categories-list@mta.ca; Tue, 13 Apr 2004 08:18:59 -0300 Date: Fri, 9 Apr 2004 22:28:36 -0700 (PDT) From: Galchin Vasili Subject: categories: Robert Goldblatt's notion of a bundle To: cat group MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: RO X-Status: X-Keywords: X-UID: 21 Hello, Is Goldblatt's notion of a bundle just a degenerate case of a sheaf with the topology being the discrete topology? Regards, Bill Halchin From rrosebru@mta.ca Wed Apr 14 14:23:10 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 14 Apr 2004 14:23:10 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BDo2m-0004Qx-00 for categories-list@mta.ca; Wed, 14 Apr 2004 14:19:24 -0300 From: Topos8@aol.com Message-ID: Date: Tue, 13 Apr 2004 08:29:46 EDT Subject: categories: Preprint: Omega Categories I To: categories@mta.ca MIME-Version: 1.0 Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: X-Keywords: X-UID: 22 I have managed to post my paper "Omega Categories I" on the math archive: http://front.math.ucdavis.edu/math.CT/0404216 A number of small changes have been made as compared with the undated version of the paper which many of you have: spelling errors and some notational errors have been corrected, the diagram associated with the definition of omega pseudo-functor on page 36 has been corrected, section 9.3 has been shortened and strengthened while a new but obvious result has been added to section 9.5 Carl Futia From rrosebru@mta.ca Wed Apr 14 14:23:10 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 14 Apr 2004 14:23:10 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BDo3P-0004Ue-00 for categories-list@mta.ca; Wed, 14 Apr 2004 14:20:03 -0300 Date: Tue, 13 Apr 2004 20:35:42 +0200 From: ICCL Summer School Message-Id: <200404131835.i3DIZg8M027749@spock.inf.tu-dresden.de> To: categories@mta.ca Subject: categories: ICCL Summer School 2004 Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: X-Keywords: X-UID: 23 ICCL Summer School 2004 Proof Theory and Automated Theorem Proving ------------------------------------------ PCC Workshop 2004 ------------------------------- Technische Universitaet Dresden June 14-26, 2004 Call for Participation ---------------------- This two-week meeting consists of two integrated parts, a summer school and a workshop, aimed at graduate students and researchers. The themes for the summer school are proof theory and automated theorem proving, the workshop is about proof, computation and complexity. As in the summer schools at TU Dresden in 2002 and 2003 and in the previous editions of the PCC workshop, people from distinct but communicating communities will gather in an informal and friendly atmosphere. We ask for a participation fee of 200 EUR. We request registration before May 10, 2004; please send an email to , making sure you include a very brief bio (5-10 lines) stating your experience, interests, home page (if available), etc. It will be possible for some students to present their work: please indicate in your application if you would like to do so and give us some information about your proposed talk. We will select applicants in case of excessive demand. A limited number of grants covering all expenses is available, please indicate in your application if the only possibility for you to participate is via a grant. Applications for grants must include an estimate of travel costs and they should be sent together with the registration. We will provide assistance in finding an accommodation in Dresden. Week 1, June 14-18: courses on Term Rewriting Systems Franz Baader (TU Dresden) Deep Inference and the Calculus of Structures Alessio Guglielmi (TU Dresden) Game Semantics and Its Applications C.-H. L. Ong (Oxford) Automated Theorem Proving for Classical Logics Andrei Voronkov (Manchester) Week 2 June 21-22: workshop; for more details, please consult the workshop web page June 23-26: courses on Deduction Modulo Claude Kirchner (Loria & INRIA, Nancy) Logic Considered as a Branch of Geometry Francois Lamarche (Loria & INRIA, Nancy) Proofs as Programs Michel Parigot (CNRS - Universite' Paris 7) Automated Reasoning for Substructural Logics John Slaney (NICTA, Canberra) Venue ----- Dresden, on the river Elbe, is one of the most important art cities of Germany. You can find world-class museums and wonderful architecture and surroundings. We will organize trips and social events. Organization ------------ This event is organized by the International Center for Computational Logic (ICCL), Paola Bruscoli, Birgit Elbl, Sylvia Epp, Bertram Fronhoefer, Axel Grossmann, Alessio Guglielmi, Steffen Hoelldobler, Reinhard Kahle and Mariana Stantcheva; it is sponsored by Deutscher Akademischer Austausch Dienst (DAAD) under the program `Deutsche Sommer-Akademie'. Please distribute this message broadly. From rrosebru@mta.ca Wed Apr 14 14:23:10 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 14 Apr 2004 14:23:10 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BDo1Y-0004I5-00 for categories-list@mta.ca; Wed, 14 Apr 2004 14:18:08 -0300 To: categories@mta.ca Subject: categories: "well-copowered" ? From: Ivar Rummelhoff Date: Tue, 13 Apr 2004 14:03:58 +0200 Message-ID: Lines: 10 User-Agent: Gnus/5.090005 (Oort Gnus v0.05) Emacs/21.1 (i686-pc-linux-gnu) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: X-Keywords: X-UID: 24 Dear everyone, I have a question about terminology: What would you call a regular category in which every object has an essentially small category of quotients (the full subcategory of the coslice category consisting of regular epis)? I suppose "well-copowered"/"cowellpowered" refers to _all_ epis? -- Best regards, Ivar Rummelhoff From rrosebru@mta.ca Thu Apr 15 09:01:15 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 15 Apr 2004 09:01:15 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BE5Tr-0000rE-00 for categories-list@mta.ca; Thu, 15 Apr 2004 08:56:31 -0300 Date: Thu, 15 Apr 2004 17:27:57 +1000 (EST) From: maxk@maths.usyd.edu.au (Max Kelly) Message-Id: <200404150727.i3F7Rv684520@milan.maths.usyd.edu.au> To: categories@mta.ca, ivarru@math.uio.no Subject: categories: Re: "well-copowered" ? Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 25 Ivar Rummelhoff correctly observes that "cowellpowered" connotes the (essential) smallness of the set of ALL epimorphisms with a given domain. It is reasonable to use "weakly cowellpowered" for the corresponding smallness of the set of STRONG epimorphisms; and these coincide with the regular epimorphisms in his case of a regular category. In situations more general than this, one had better explain one's meaning in unambiguous words. Max Kelly. From rrosebru@mta.ca Fri Apr 16 08:46:07 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 16 Apr 2004 08:46:07 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BERju-0001Ki-00 for categories-list@mta.ca; Fri, 16 Apr 2004 08:42:34 -0300 Date: Thu, 15 Apr 2004 15:55:31 +0200 (CEST) From: Simeoni Marta To: categories@mta.ca Subject: categories: ICGT 2004: last 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 Status: O X-Status: X-Keywords: X-UID: 26 [Apologies for multiple copies of this announcement] LAST CALL FOR PAPERS ICGT 2004 2nd International Conference on Graph Transformation Roma (Italy), September 28 - October 2, 2004 The second International Conference on Graph Transformation ICGT 2004, along with several satellite events, will be held in Roma at the end of September 2004. It follows the first ICGT 2002 (Barcelona, October 2002) and a series of six international workshops on graph transformation with applications in computer science held from 1978 to 1998 in Europe and the USA. The conference takes place under the auspices of EATCS, EASST, and IFIP WG 1.3. The proceedings will appear in the Lecture Notes in Computer Science series by Springer-Verlag. The conference is co-located with IEEE Symposium on Visual Languages and Human Centric Computing (VL/HCC) September 26-29, 2004. Scope. Graphical structures of various kinds (like graphs, diagrams, visual sentences and others) are very useful to describe complex structures and systems in a direct and intuitive way. These structures are often augmented by formalisms which add to the static description a further dimension modelling the evolution of systems via any kind of transformation of such graphical structures. The field of Graph Transformation is concerned with the theory, applications and implementation issues of all these formalisms. The theory is strongly related to areas such as graph theory and graph algorithms, formal language and parsing theory, theory of concurrency and distributed systems, formal specification and verification, logic and semantics. The application areas include all those fields of Computer Science, Information Processing, Engineering and Natural Sciences where static and dynamic modeling by graphical structures and graph transformations, respectively, play an important role. Topics of interest include, but are not limited to, the following. On the more theoretical side: - General models of graph transformation - Node-, edge-, and hyperedge replacement graph grammars - Concurrency, distribution, and formal semantics - Term graph rewriting - Network computing - High-level replacement systems - Hierarchical graphs and decompositions of graphs - Logic expression of graph transformation properties - Graph theoretical properties of graph languages - Geometrical and topological aspects of graph transformation - Automata on graphs and parsing of graph languages - Analysis of graph transformation systems - Structuring and modularization concepts - Semantics of UML and other visual modelling techniques On the more applied side: - Specification languages - Implementation of programming languages - Design of visual programming environments - Massively parallel computing - Bioinformatics - Software engineering and modular systems - Development of meta CASE tools - Software architecture - Information security - Visual languages - Bio-computing - Actor systems and Petri nets - Rule- and knowledge-based systems - Pattern generation and picture processing - Pattern matching - Tool support - Graph exchange formats - Layout algorithms Invited speakers. Andy Evans (York, UK) Margaret-Anne Storey (Victoria, BC Canada) (joint speaker with VL/HCC) Program committee. M.Bauderon (FR), D.Blostein (CA), A.Corradini (IT), H.Ehrig (DE), G.Engels (co-chair; DE), R.Heckel (DE), D.Janssens (BE), H.-J.Kreowski (DE), B.Koeni= g (DE), B.Meyer (AU), U.Montanari (IT), M.Nagl (DE), F.Orejas (ES), F.Parisi-Presicce (co-chair; USA/IT), M.Pezze` (IT), J.Pfaltz (USA), R.Plasmeijer (NL), D.Plump (UK), L.Ribeiro (BR), G.Rozenberg (NL), A.Schuer= r (DE), G.Taentzer (DE), G.Tortora (IT), G.Valiente (ES) Important dates. Submission of title and abstract: April 19, 2004 Submission of complete paper: April 26, 2004 Notification of acceptance: June 15, 2004 Final version due: June 30, 2004 Main conference: September 29 -- October 1, 200= 4 Conference including satellite events: September 28 -- October 2, 200= 4 General organizing committee. Paolo Bottoni (Roma, Italy), Hartmut Ehrig (chair; Berlin, Germany), Gregor Engels (Paderborn, Germany), Francesco Parisi-Presicce (Roma, Italy)= , Grzegorz Rozenberg (Leiden, The Netherlands) Local organizing committee. Paolo Bottoni (chair), Francesco Parisi-Presicce, Marta Simeoni (publicity chair) More details concerning ICGT 2004 including the main conference, satellite events, the procedure for the submission of papers, local information on th= e conference site, and travel information can be found on the website of ICGT 2004, http://icgt2004.dsi.uniroma1.it For further information, you may also contact Paolo Bottoni (bottoni@dsi.uniroma1.it), Gregor Engels (engels@uni-paderborn.de) or Francesco Parisi-Presicce (parisi@dsi.uniroma1.it / fparisip@gmu.edu) Conference address. ICGT 2004 Francesco Parisi-Presicce / Paolo Bottoni Universit=E0 degli Studi di Roma La Sapienza Dipartimento di Informatica Via Salaria 113 (III piano), I-00198 Roma, Italy Tel: +39 06 4991-8426, Fax: +39 06 8541842 Satellite events. GRA-TRA TUTORIAL Tutorial on Foundations and Applications of Graph Transformation Date: Sept. 28 (afternoon) Organizers, contact and further information: Luciano Baresi (Milano, Italy, baresi@elet.polimi.it), Reiko Heckel (Paderborn, Germany, reiko@upb.de) http://www.upb.de/cs/ag-engels/Conferences/ICGT04/Tutorial DNA & GRA-TRA 2004 Tutorial on DNA Computing and Graph Transformation Date: Sept. 28 (all day) Organizers: Tero Harju (Turku, Finland), Ion Petre (Turku, Findland), Grzegorz Rozenberg (Leiden, The Netherlands) Contact and further information: rozenber@liacs.nl PNGT 2004 Workshop on Petri Nets and Graph Transformations Date: Oct. 1 (afternoon) -2 (morning) Organizers: Grzegorz Rozenberg (Leiden, The Netherlands), Hartmut Ehrig (Berlin, Germany), Julia Padberg (Berlin, Germany) Contact and further information: padberg@cs.tu-berlin.de TERMGRAPH 2004 International Workshop on Term Graph Rewriting Date: Oct. 2 Organizers, contact and further information: Maribel Fernandez (London, UK, maribel@dcs.kcl.ac.uk), Andrea Corradini (Pisa, Italy, andrea@di.unipi.it) http://www.dcs.kcl.ac.uk/staff/maribel/TERMGRAPH.html GraBaTs 2004 International Workshop on Graph-Based Tools Date: Oct. 1 (afternoon) - Oct. 2 Organizers: Tom Mens (Mons, Belgium), Andy Schuerr (Darmstadt, Germany), Gabriele Taentzer (Berlin, Germany) Contact and further information: gabi@cs.tu-berlin.de http://tfs.cs.tu-berlin.de/grabats LOGIC, GRAPH TRANSFORMATIONS, FINITE AND INFINITE STRUCTURES Workshop with invited lectures and short contributions Date: Oct. 1 (afternoon) - Oct. 2 Organizers: Bruno Courcelle (Bordeaux, France), David Janin (Bordeaux, Fran= ce) Contact and further information: courcell@labri.fr, http://www.labri.fr/Perso/~courcell/LogicIcgt.html SETra 2004 2nd Workshop on Software Evolution through Transformations: Model-based vs. Implementation-level Solutions Date: Oct. 2 Organizers: Reiko Heckel (Paderborn, Germany), Dirk Janssens (Antwerp, Belgium), Tom Mens (Brussels, Belgium), Michel Wermelinger (Lisboa, Portugal) Contact and further information: reiko@upb.de http://www.upb.de/cs/ag-engels/Conferences/ICGT04/SET04/ From rrosebru@mta.ca Fri Apr 16 08:46:39 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 16 Apr 2004 08:46:39 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BERmR-0001TH-00 for categories-list@mta.ca; Fri, 16 Apr 2004 08:45:11 -0300 Date: Thu, 15 Apr 2004 20:54:50 +0200 (MEST) From: Ulrich Fahrenberg To: Subject: categories: CfP: GETCO 04 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Scanned-By: MIMEDefang 2.24 (www . roaringpenguin . com / mimedefang) Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 27 [Apologies if you should receive multiple copies of this:] Sixth workshop on Geometric and Topological Methods in Concurrency and Distributed Computing GETCO 2004 Affiliated with DISC 2004 Venue: Amsterdam, the Netherlands Conference dates: DISC: 4-8 October 2004 GETCO: 4 October 2004 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 modelled 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 the 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, contact 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 file to both the addresses raussen@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 28 June 2004. Important Dates * Deadline for submission: 28 June 2004 * Notification of acceptance: 2 August 2004 * Final version (for the preproceedings): 23 August 2004 * DISC: 4-8 October 2004 * GETCO: 4 October 2004 Publication Contacts have been taken so that accepted papers will be made available in the BRICS Notes series. Contacts have been taken with Electronic Notes in Theoretical Computer Science to publish the proceedings of the workshop - full papers only - in a special volume. The programme committee will decide upon necessary revisions and acceptance of papers to this volume after the workshop. Contact Additional information can be obtained from the GETCO website at http://www.math.aau.dk/~uli/getco04 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 From rrosebru@mta.ca Fri Apr 16 08:48:07 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 16 Apr 2004 08:48:07 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BERnv-0001YR-00 for categories-list@mta.ca; Fri, 16 Apr 2004 08:46:43 -0300 Date: Thu, 15 Apr 2004 20:15:29 -0400 (EDT) From: F W Lawvere Reply-To: wlawvere@acsu.buffalo.edu To: categories@mta.ca Subject: categories: Re: Topos cohomology, context and technical questions In-Reply-To: <5.2.0.9.0.20040315075042.01c306e8@pop.cwru.edu> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 28 Colin had asked about cohomology theory for not necessarily Grothendieck toposes. A specific question concerning topos cohomology is the following: Does every geometric morphism have right-derived functors on abelian objects? In principle, this would not require enough injectives since the universal property requested does not involve any specific kind of resolution. Bill On Mon, 15 Mar 2004, Colin McLarty wrote: > Thanks to Christopher Townsend and Carsten Butz for help on cohomology in > an elementary topos. It seems the general theory is not much advanced > beyond what it was in Johnstone 1977. > > My question came out of a conversation with algebraic geometers several > years ago, which I have taken up again lately. Deligne, for example, > describes toposes as one of Grothendieck's great ideas (one of > Grothendieck's four "idees maitresses"). But for him and many other > geometers their value lies in organizing cohomology. Insofar as > Grothendieck toposes support a simple general theory of cohomology, and > elementary toposes do not, these people find only Grothendieck toposes > interesting. > > Certainly there is a lot to say for elementary topos theory even from that > perspective: The elementary topos axioms organize the theory of > Grothendieck toposes. Elementary toposes have some cohomology theory > though not so simple and general. And elementary toposes have other > roles. > > What interests me, now, is how far elementary topos theory helps with > cohomology per se. > > One approach is to notice: The elementary theory of "a topos whose > Abelian groups have enough injectives" supports a considerable general > theory of cohomology via injective resolutions. But I have not worked out > how far it really goes. (People with foundational interests will notice > the exact result depends on whether and how this theory works with > infinite complexes. There are various approaches depending on what you > mean by "elementary".) > > > This raises my first technical question: > > SGA 4 proves inverse image functors preserve flat modules, but the > transparent proof assumes enough points (Exp. V Prop. 1.7). Deligne gives > a far from transparent proof, for all (Grothendieck) toposes, in an > appendix on "local inductive limits". He urges the reader "to avoid, as a > matter of principle, reading this appendix". Is the result proved more > simply somewhere? Do "local inductive limits" survive today in some form? > In short, can we follow Deligne's advice on not reading this appendix, and > still prove his result? I have made no progress on the appendix yet, as > the opening definition is full of typos. If there is a cleaner exposition > I'd rather start with that. > > The second question: > > The IHES version of SGA 4 gives a faulty proof that, in every > (Grothendieck) topos, rings admit a standard kind of resolution over any > cover by tensoring with a resolution of the integers. This is Prop. 1.4 > of Expose V. The Springer-Verlag version corrects the mistake by proving > the result only when the topos has enough points (Prop 1.11 Exp. V). > Johnstone 1977 recovers the theorem for the case of a presheaf topos > (Lemma 8.2) which is the case of interest and easily extends to any topos > with enough points. > > Is that version optimal, in some easy to prove sense? Is there an easy > example of a ring in a Grothendieck topos where the resolution > fails? Is it known to be optimal in any sense? > > best, Colin From rrosebru@mta.ca Fri Apr 16 14:54:31 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 16 Apr 2004 14:54:31 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BEXUo-0001F9-00 for categories-list@mta.ca; Fri, 16 Apr 2004 14:51:22 -0300 Date: Fri, 16 Apr 2004 08:09:13 -0400 (EDT) From: Peter Freyd Message-Id: <200404161209.i3GC9DrD024437@saul.cis.upenn.edu> To: categories@mta.ca Subject: categories: right-derived functors Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: X-Keywords: X-UID: 29 Bill asks: Does every geometric morphism have right-derived functors on abelian objects? In principle, this would not require enough injectives since the universal property requested does not involve any specific kind of resolution. I think not. In my new Foreword to Abelian Categories on TAC (www.tac.mta.ca/tac/reprints/articles/3/foreword.pdf), specifically in the comments about pages 131-132, I recall the description of a locally small topos in which Ext(A,B) wants to have proper classes as values. From rrosebru@mta.ca Fri Apr 16 14:55:10 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 16 Apr 2004 14:55:10 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BEXY6-0001Wb-00 for categories-list@mta.ca; Fri, 16 Apr 2004 14:54:46 -0300 X-Mailer: exmh version 2.6.3 04/04/2003 with nmh-1.0.4 To: categories@mta.ca Subject: categories: Conditions for "Basis convexity" (?) of a theory Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Date: Fri, 16 Apr 2004 08:47:01 -0700 From: Vaughan Pratt Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 30 Dear UACTers, Luca Aceto asked me yesterday, in the context of results of his about theories of parallel composition, about conditions for a finitely based theory to remain so after removal of any operation. It occurred to me that his question could be usefully formulated in terms of a suitable notion of basis convexity. Call a theory *basis convex* when its axiom rank (minimum size of axiomatization, e.g. fewest axioms in the case of equational theories) is no smaller than that of any theory it conservatively extends. Useful variants or extensions would involve cardinality conditions or restrictions, e.g. only allowing limit ordinals for axiom rank in order to immunize the notion against mere finite increases in rank. This seems like a simple and natural notion. For example the equational theory of regular expressions, viewed as a monotonic fixpoint logic with a conjunction ab, a disjunction a+b, and a fixpoint operator *, is not finitely based (Redko 1964, Conway 1971), but its conservative extension with (nonmonotonic) implication x->y is, proved by borrowing Tarski and Ng's axiom (x\x)* < x\x for their system RAT, RA with transitive closure. Had this adjective occurred to me (slaps forehead with flat of hand) when I wrote this up for JELIA'90, not only could whole sentences have been shrunk down to just this adjective, the result could have been title of the paper: "The Theory of Conditional Regular Expressions is Not Basis Convex." Does this concept exist already? If so what is known about it, e.g. necessary or sufficient conditions? And does it relate to other convexity notions such as what Joyal calls softness and the Nelson-Oppen-Shostak theorem-proving crowd calls convexity? This is the condition: if a&b -> cvd is in the theory, then so is one of a -> c, a -> d, b -> c, or b -> d. (In the classical case with a,b,c,d literals it is enough to require just a&b -> c or a&b -> d, true for Nelson-Oppen but not for Joyal.) Orthomodularity might be another candidate for some kind of nonconvexity (concavity?), by analogy with regular expressions -- neither metrical completeness of inner product spaces (Goldblatt, JSL 1984) nor transitive closure of binary relations as respective associated dual notions are elementary, a phenomenon that could conceivably play a role in basis convexity. Vaughan Pratt From rrosebru@mta.ca Sun Apr 18 08:50:08 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 18 Apr 2004 08:50:08 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BFAjc-0004w9-00 for categories-list@mta.ca; Sun, 18 Apr 2004 08:45:16 -0300 Message-Id: <200404161955.i3GJt8dK029840@coraki.Stanford.EDU> X-Mailer: exmh version 2.6.3 04/04/2003 with nmh-1.0.4 To: categories@mta.ca Subject: categories: Feferman colloquium talk of interest to SF Bay Area categorists Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Date: Fri, 16 Apr 2004 12:55:08 -0700 From: Vaughan Pratt Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 31 (I won't promise to pass on specific questions at question time, but I'd be happy to try to condense suggested questions into one or two suitable ones if I can do the necessary processing in real time to make them germane to the actual talk. Always hard to know what to ask in advance of hearing a talk. In any event the lesson of Ireland, Iraq, UACT, etc. is that the TV ads promising that you can learn harmony overnight are to be taken with a grain of salt, it takes a lot of patience. -vp) Dept. of Mathematics Colloquium Thursday April 22, 4:15 PM, Room 380:380W Speaker: Solomon Feferman, Stanford Title: What foundations for category theory? Abstract. Naive category theory leads to certain constructions such as "the category of all categories" and "the category of all functors between two given categories", that border on inconsistency and necessitate consideration of foundations for the subject. Even applications of category theory to homological algebra, for example, raise problems. Two kinds of set-theoretical foundations for category theory have been proposed by Mac Lane and Grothendieck, but each has its drawbacks. In this talk I will describe a more logically sophisticated set-theoretical foundation that improves on these by means of reflective universes. Tea in advance, Bldg. 380 2nd floor lounge. From rrosebru@mta.ca Sun Apr 18 08:50:09 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 18 Apr 2004 08:50:09 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BFAmP-0005BA-00 for categories-list@mta.ca; Sun, 18 Apr 2004 08:48:09 -0300 Date: Fri, 16 Apr 2004 18:40:02 -0700 From: Vaughan Pratt Message-Id: <200404170140.i3H1e2Gt004732@coraki.Stanford.EDU> To: categories@mta.ca Subject: categories: Geometry of 2x2 real matrices Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 32 I'm writing about applications to commonplace physics phenomena of "the other 4D Clifford algebra", namely R(2), the 2x2 real matrices. (The quaternions H of course being the prototype to which this is "the other". The only other Clifford algebras this size or smaller are smaller, namely R, C, and the hyperbolic plane, call it J since we've already deducted H on line 3.) (If anyone actually knows of such applications I'm all ears.) Since a good many categorists are (were?) primarily motivated by geometry, and particularly algebraic topology, I'm hoping this is a good place to ask the following. The geometry of the quaternions, certainly for its vector part (zero real part), seems clear enough, namely that of ordinary Euclidean 3-space. If x,y are unit vectors with 1,x,y,xy linearly independent then x,y,xy is a right-handed coordinate system. (But is there a coherent notion of handedness for a triple like i,1,j or j,k,1 and if so what's it good for? Should 3D subspaces that include the real axis be considered simply connected with a flat Euclidean metric like the physical 3D vector space spanned by i,j,k? Does 360 degree rotation work the same there as in the vector subspace?) Whereas the geometry of the quaternions feels like 3-space plus a perceptual axis (or something like that), the geometry of R(2) feels more like the four walls of a room. The hands of clocks on the north and south walls rotate through circular angles while those on the east and west walls rotate through hyperbolic angles. Clocks not parallel to some wall seem to rotate through both kinds of angles simultaneously, at relative rates that depend on the angle to the walls. (This is the general idea but when I try to flesh out the details too intuitively I find myself injecting too much Euclidean geometry at first.) In the Erlangen spirit I'm trying to come to grips with the geometrical invariants for R(2). The metrical invariants are more or less clear enough. (That said, computing the geodesics seems painful---is there a simple distillation that isn't equivalent to being dragged through the calculus of variations? An elementary guide to the Lie algebra for R(2) would be great. I actually need to calculate those circular-to-hyperbolic angle ratios as smoothly varying quantities along geodesics so any software that does this could be very insightful.) Where I'm running into serious trouble is with the topological invariants. For example what's supposed to happen near the light cone? For quaternions the only choices for the light cone (depending on what you're using quaternions for) are x^2 = y^2+v^2+w^2 and x^2+y^2+v^2+w^2=0. The former is a real cone, the vector part (x=0) of which is just the origin, while the latter (the roots of the Euclidean squared norm for the quaternions) is the origin regardless of the real part. R(2) moves y^2 (y being a measure of asymmetry, 0 for symmetric matrices) over to the other side, making the choices x^2+y^2=v^2+w^2 and x^2+y^2+v^2+w^2=0. While the second hasn't changed, the first becomes y^2=v^2+w^2 when x=0. Now what? For example what are the pros and cons of compactly topologizing the unit sphere y^2+v^2+w^2 <= 1 (not <) when you want to treat the cone y^2=v^2+w^2 as unreachable from points on either side of it within that sphere other than through the origin? What is the physical significance if any of a path through the origin? One can always improvise answers but this is a time-consuming and unreliable process that is greatly inferior to working out of a well-debugged cookbook. An account of the topology of R(2) addressed to us Bears of Little Brain would be very helpful. Everything I've found to date about getting from quaternions to other Clifford algebras goes straight to arbitrary Clifford algebras over arbitrary fields, which is about as useful as telling kids that ice cream comes from dairy farms -- academically interesting but operationally useless when you just want one ice cream. Vaughan Pratt From rrosebru@mta.ca Mon Apr 19 11:48:49 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 19 Apr 2004 11:48:49 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BFa26-0003Dv-00 for categories-list@mta.ca; Mon, 19 Apr 2004 11:46:02 -0300 Date: Mon, 19 Apr 2004 07:49:37 +0200 (CEST) From: Philippe Gaucher To: categories@mta.ca Subject: categories: preprint: Flow does not model flows up to weak dihomotopy Message-ID: <20040419074828.Q32510-100000@helium.pps.jussieu.fr> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 33 Title: Flow does not model flows up to weak dihomotopy Abstract: We prove that the category of flows cannot be the underlying category of a model category whose corresponding homotopy types are the flows up to weak dihomotopy. Some hints are given to overcome this problem. In particular, a new approach of dihomotopy involving simplicial presheaves over an appropriate small category is proposed. This small category is obtained by taking a full subcategory of a locally presentable version of the category of flows. Comments: 16pages, 3 figures Url: http://www.pps.jussieu.fr/~gaucher/ and ArXiv. From rrosebru@mta.ca Wed Apr 21 09:10:49 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 21 Apr 2004 09:10:49 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BGGTw-0006VC-00 for categories-list@mta.ca; Wed, 21 Apr 2004 09:05:36 -0300 Date: Tue, 20 Apr 2004 21:11:09 -0700 From: Vaughan Pratt Message-Id: <200404210411.i3L4B9i8006766@coraki.Stanford.EDU> To: categories@mta.ca Subject: categories: Consistency of the category of all categories Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 34 Having thought about this consistency issue for the "category of all categories" from time to time over the years, I had not seen any satisfactory resolution save that of resolving to stop worrying about it. But then Sol's talk was advertised for this Thursday, renewing my interest. One thing was clear: the "category" of all categories is in fact the 2-category 1-CAT (or just CAT) of all categories. There is no reason to expect every 2-category to show up in the category of all 1-categories (though all the large 2-discrete ones will, where "large" is the cardinality bound for categories). Furthermore the category n-CAT of all n-categories had to be bigger than any n-category, since n-categories had no evident property letting one circumvent Russell's paradox differently from the case n=0 where one concludes that Set is bigger than any set. But (n-1)-CAT is an n-category. Hence we *must* have a strict hierarchy. But how much bigger? Well, certainly an exponential gap between n-CAT and (n+1)-CAT (meaning the latter being at least the power set of the former) suffices to dispose of Russell's paradox. Can one reliably do better and just take *any* strictly increasing sequence of cardinals? I'm not sure how one would argue that. But in any event the cardinals scattered in between the beth numbers beth_0,beth_1,beth_2,... constituting Cantor's beanstalk are merely nematodes on the beanstalk produced by the Cohen nematode factory, and it's not clear to me what additional benefit derives from basing the spacing of the n-CAT hierarchy on artificially manufactured nematodes. This is all the more clear when one considers that exponential gaps are to inaccessible cardinals as nuclear radii are to intergalactic space. A billion of them, or even epsilon_0 of them, are no more than the layers creating the iridescence in a butterfly wing. These are tiny gaps, and it is pointless trying to shrink them down based on fictional entities if they can't be shrunk all the way to zero. It may be distressing that one can't take all n-CAT's to be uniformly the same size. But a rate of growth just sufficient to ward off Russell's paradox is so tiny in the grand scheme of things axiomatized via ZFC, Grothendieck, or whoever, that one can practically think of them that way. I can understand that not everyone necessarily cares about cardinality issues, considering it unhealthy to take them too seriously or examine them too closely. Among those on this list that do care, is the above attitude reasonable? If so, can it be further elaborated and improved? If not, what is wrong with it? Vaughan Pratt From rrosebru@mta.ca Thu Apr 22 12:14:26 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 22 Apr 2004 12:14:26 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BGfpi-00049G-00 for categories-list@mta.ca; Thu, 22 Apr 2004 12:09:46 -0300 From: "JELIA'04" Subject: categories: CFP: JELIA'04 - 9th European Conference on Logics in Artificial In= Message-Id: Bcc: Date: Thu, 22 Apr 2004 12:09:46 -0300 Status: O X-Status: X-Keywords: X-UID: 35 telligence To: categories@mta.ca Content-Type: text/plain;iso-8859-1 Reply-To: jelia04@di.fct.unl.pt Date: Mon, 19 Apr 2004 20:00:27 +0100 X-Priority: 3 X-Library: Indy 8.0.25 Message-ID: X-OriginalArrivalTime: 19 Apr 2004 19:00:31.0796 (UTC) FILETIME=3D[96802740= :01C42640] Sender: cat-dist@mta.ca Precedence: bulk /------------------------------------------------------------------/ CALL FOR PAPERS 9th European Conference on Logics in Artificial Intelligence JELIA'04 Lisbon, Portugal, September 27-30 http://centria.di.fct.unl.pt/~jelia2004 Submission deadline: May 9th (abstracts due May 6th) /------------------------------------------------------------------/ INTRODUCTION Logics have, for many years, laid claim to providing a formal basis for the study and development of applications and systems in Artificial Intelligence. With the depth and maturity of formalisms, methodologies and logic-based systems today, this claim is stronger than ever. The European Conference on Logics in Artificial Intelligence (or Journ=E9es Europ=E9ennes sur la Logique en Intelligence Artificielle - JELIA) began back in 1988, as a workshop, in response to the need for a European forum for the discussion of emerging work in this field. Since then, JELIA has been organised biennially, with English as official language, and with proceedings published in Springer-Verlag's Lecture Notes in Artificial Intelligence. Previous meetings took place in Roscoff, France (1988), Amsterdam, Netherlands (1990), Berlin, Germany (1992), York, U.K. (1994), =C9vora, Portugal (1996), Dagstuhl, Germany (1998), M=E1laga, Spain (2000) and Cosenza, Italy (2002). The increasing interest in this forum, its international level with growing participation from researchers outside Europe, and the overall technical quality, has turned JELIA into a major biennial forum for the discussion of logic-based approaches to artificial intelligence. AIM AND SCOPE The aim of the 9th European Conference on Logics in Artificial Intelligence, JELIA'04, is to bring together active researchers interested in all aspects concerning the use of logics in artificial intelligence to discuss current research, results, problems and applications of both a theoretical and practical nature. JELIA strives to foster links and facilitate cross-fertilisation of ideas among researchers from various disciplines, among researchers from academia and industry, and between theoreticians and practitioners. Authors are invited to submit papers presenting original and unpublished research in all areas related to the use of Logics in AI. A non-exhaustive list of topics of interest includes: -Abductive and inductive reasoning -Applications of logic-based systems -Automated reasoning and theorem proving -Computational complexity and expressiveness in AI -Description logics -Foundations of logic programming and knowledge-based systems -Hybrid reasoning systems -Knowledge representation and reasoning -Logic based AI systems -Logic based applications to the Semantic Web -Logic based planning and diagnosis -Logic programming and nonmonotonic reasoning -Logics and multi-agent systems -Logics in machine learning -Modal, temporal, spacial and hybrid logics -Non-classical logics -Nonmonotonic reasoning, belief revision and updates -Reasoning about actions, causal reasoning and causation -Uncertain and probabilistic reasoning SUBMISSIONS Papers should be written in English, formatted according to the Springer LNCS style, and not exceed 13 pages including figures, references, etc. Please refer to the conference web pages for further instructions concerning the submission procedures. IMPORTANT DATES Abstract Submission: May 6th, 2004 Paper Submission: May 9th, 2004 Notification: June 21st, 2004 Camera Ready Copy: July 5th, 2004 PROCEEDINGS Proceedings will be published by Springer-Verlag as a volume of the Lecture Notes on Artificial Intelligence series. Extended versions of selected papers presented at the conference will be published in a special issue of the Journal of Applied Logic. INVITED LECTURES Franz Baader, TU Dresden, Germany Bernhard Nebel, Universit=E4t Freiburg, Germany Francesca Rossi, University of Padova, Italy SYSTEM PRESENTATIONS There will be a special session devoted to the presentation of implemented systems. Please refer to the conference web pages for further information. CONFERENCE OFFICIALS Conference Chair: Jo=E3o Leite, Universidade Nova de Lisboa, Portugal Program Chair: Jos=E9 J=FAlio Alferes, Universidade Nova de Lisboa, Portuga= l PROGRAM COMMITTEE -Jos=E9 J=FAlio Alferes, Universidade Nova de Lisboa, Portugal -Franz Baader, TU Dresden, Germany -Salem Benferhat, Universit=E9 d'Artois, France -Alexander Bochman, Holon Academic Institute of Technology, Israel -Gerhard Brewka, University of Leipzig, Germany -Walter Carnielli, Universidade Estadual de Campinas, Brazil -Luis Fari=F1as del Cerro, Universit=E9 Paul Sabatier, France -James Delgrande, Simon Fraser University, Canada -J=FCrgen Dix, TU Clausthal, Germany -Roy Dyckhoff, University of St Andrews, UK -Thomas Eiter, TU Wien, Austria -Patrice Enjalbert, Universit=E9 de Caen, France -Michael Fisher, University of Liverpool, UK -Ulrich Furbach, University Koblenz-Landau, Germany -Michael Gelfond, Texas Tech University, USA -Sergio Greco, Universit=E0 della Calabria, Italy -Jo=E3o Leite, Universidade Nova de Lisboa, Portugal -Maurizio Lenzerini, Universit=E0 di Roma "La Sapienza", Italy -Nicola Leone, Universit=E0 della Calabria, Italy -Vladimir Lifschitz, University of Texas at Austin, USA -Maarten Marx, Universiteit van Amsterdam, The Netherlands -John-Jules Meyer, Universiteit Utrecht, The Netherlands -Bernhard Nebel, Universit=E4t Freiburg, Germany -Ilkka Niemel=E4, Helsinki University of Technology, Finland -Manuel Ojeda-Aciego, Universidad de M=E1laga, Spain -David Pearce, Universidad Rey Juan Carlos, Spain -Lu=EDs Moniz Pereira, Universidade Nova de Lisboa, Portugal -Henry Prakken, Universiteit Utrecht, The Netherlands -Luc de Raedt, Universit=E4t Freiburg, Germany -Ken Satoh, National Institute of Informatics, Japan -Renate Schmidt, University of Manchester, UK -Terrance Swift, SUNY at Stony Brook, USA -Mirek Truszczynski, University of Kentucky, USA -Wiebe van der Hoek, University of Liverpool, UK -Toby Walsh, University College Cork, Ireland -Mary-Anne Williams, The University of Technology, Sydney, Australia -Michael Zakharyaschev, King's College, UK CONTACT Send your questions and comments to jelia04@di.fct.unl.pt From rrosebru@mta.ca Thu Apr 22 16:50:29 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 22 Apr 2004 16:50:29 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BGkAP-0007Kr-00 for categories-list@mta.ca; Thu, 22 Apr 2004 16:47:25 -0300 Date: Wed, 21 Apr 2004 23:15:13 -0700 From: Vaughan Pratt Message-Id: <200404220615.i3M6FDx1030384@coraki.Stanford.EDU> To: categories@mta.ca Subject: categories: Getting rid of cardinality as an issue Cc: pratt@cs.Stanford.EDU Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 36 Encouraged by the lack of objections to my previous message about why Russell's Paradox should not be a big deal, I had a shot at shrinking the position I spelled out there down to one paragraph, as follows. ------------ We shall axiomatize certain 1-categories using 2-categories. We avoid Russell's paradox by treating any aggregation of $n$-categories as an $(n+1)$-category, and allowing for the possibility that the $(n+1)$-category $n$-$\CAT$ of all $n$-categories might be exponentially larger than any of its members. We impose no other size constraints besides the obvious one of keeping things small enough to remain consistent. Sets are defined as usual as 0-categories and categories as 1-categories. ------------ While I'm happy to field objections like "too flippant", I'm more concerned as to whether there are any technical flaws, and to a lesser extent philosophical or religious concerns. (I would not want to be held responsible for guns being brought to the next UACT meeting if ever there is one.) Makkai and Pare address the same issue in AMS CM 104 (Accessible Categories) with a hierarchy of Grothendieck universes (three, since they like me stop at 2-categories for the application at hand). Now the Grothendieck hierarchy is stepped through via ZF rather than Z, with Fraenkel's Replacement axiom doing the heavy hitting. This creates gaps mind-bogglingly larger than my teensy exponential gaps above. The general idea seems to be that these gaps ought to be large enough to take care of Russell while still not running headlong into inconsistency. However gaps this large do entail a certain amount of finger-crossing, and one might question the logic of hitting Russell with a nuclear weapon that might send some fallout your way when a harmless little tack-hammer will take him out. One objection I can readily imagine to the above is that I've conflated the n-category hierarchy with Russell's proposal for a ramified types hierarchy. I would disagree with that. All I have done is to insist on two things that seem to me to be independent. 1. I have proposed to call aggregations of n-categories (n+1)-categories. Now morphisms between n-categories are n-functors, and where there are n-functors there are n-natural transformations, so this is hardly a bold proposal. 2. *Some* gap is needed between n-CAT and (n+1)-CAT, starting with the requirement that Set be bigger than any set. Russell's paradox is no respecter of n, applying just as effectively to an (n+1)-category of n-categories as it does to a 1-category of sets. Certainly I have juxtaposed 1 and 2, but that is not the same thing as conflating them. Their mere juxtaposition provides sufficient armor against both Russell's paradox and the Icarus risk of flying too close to an inconsistently large cardinal. The "prior art" for dealing with these issues has given rise to the adjectives "small", "large," "superlarge", etc. and the nouns "set" and "class." A good test for any revolution is the amount of blood it needs to shed. The following definitions are aimed at minimal upheaval through maximum compatibility with the status quo. * An object is n-small when it belongs to an n-category. * Small = 1-small, large = 2-small, superlarge = 3-small, etc. * A set is a discrete 1-category. * A class is a discrete n-category for unspecified n. Hopefully Sol Feferman will give an even simpler solution in his talk tomorrow. Vaughan Pratt From rrosebru@mta.ca Thu Apr 22 17:02:56 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 22 Apr 2004 17:02:56 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BGkNl-0000g5-00 for categories-list@mta.ca; Thu, 22 Apr 2004 17:01:13 -0300 Date: Wed, 21 Apr 2004 23:15:13 -0700 From: Vaughan Pratt Message-Id: <200404220615.i3M6FDx1030384@coraki.Stanford.EDU> To: categories@mta.ca Subject: categories: Getting rid of cardinality as an issue (correction) Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 37 [Note from moderator: apologies to Vaughan for missing his requested change: 1 has been changed to 0 5 lines from bottom, so it reads: `discrete 0-category'.] Encouraged by the lack of objections to my previous message about why Russell's Paradox should not be a big deal, I had a shot at shrinking the position I spelled out there down to one paragraph, as follows. ------------ We shall axiomatize certain 1-categories using 2-categories. We avoid Russell's paradox by treating any aggregation of $n$-categories as an $(n+1)$-category, and allowing for the possibility that the $(n+1)$-category $n$-$\CAT$ of all $n$-categories might be exponentially larger than any of its members. We impose no other size constraints besides the obvious one of keeping things small enough to remain consistent. Sets are defined as usual as 0-categories and categories as 1-categories. ------------ While I'm happy to field objections like "too flippant", I'm more concerned as to whether there are any technical flaws, and to a lesser extent philosophical or religious concerns. (I would not want to be held responsible for guns being brought to the next UACT meeting if ever there is one.) Makkai and Pare address the same issue in AMS CM 104 (Accessible Categories) with a hierarchy of Grothendieck universes (three, since they like me stop at 2-categories for the application at hand). Now the Grothendieck hierarchy is stepped through via ZF rather than Z, with Fraenkel's Replacement axiom doing the heavy hitting. This creates gaps mind-bogglingly larger than my teensy exponential gaps above. The general idea seems to be that these gaps ought to be large enough to take care of Russell while still not running headlong into inconsistency. However gaps this large do entail a certain amount of finger-crossing, and one might question the logic of hitting Russell with a nuclear weapon that might send some fallout your way when a harmless little tack-hammer will take him out. One objection I can readily imagine to the above is that I've conflated the n-category hierarchy with Russell's proposal for a ramified types hierarchy. I would disagree with that. All I have done is to insist on two things that seem to me to be independent. 1. I have proposed to call aggregations of n-categories (n+1)-categories. Now morphisms between n-categories are n-functors, and where there are n-functors there are n-natural transformations, so this is hardly a bold proposal. 2. *Some* gap is needed between n-CAT and (n+1)-CAT, starting with the requirement that Set be bigger than any set. Russell's paradox is no respecter of n, applying just as effectively to an (n+1)-category of n-categories as it does to a 1-category of sets. Certainly I have juxtaposed 1 and 2, but that is not the same thing as conflating them. Their mere juxtaposition provides sufficient armor against both Russell's paradox and the Icarus risk of flying too close to an inconsistently large cardinal. The "prior art" for dealing with these issues has given rise to the adjectives "small", "large," "superlarge", etc. and the nouns "set" and "class." A good test for any revolution is the amount of blood it needs to shed. The following definitions are aimed at minimal upheaval through maximum compatibility with the status quo. * An object is n-small when it belongs to an n-category. * Small = 1-small, large = 2-small, superlarge = 3-small, etc. * A set is a discrete 0-category. * A class is a discrete n-category for unspecified n. Hopefully Sol Feferman will give an even simpler solution in his talk tomorrow. Vaughan Pratt From rrosebru@mta.ca Fri Apr 23 08:46:02 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 23 Apr 2004 08:46:02 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BGz6V-0000U2-00 for categories-list@mta.ca; Fri, 23 Apr 2004 08:44:23 -0300 Message-ID: <408830B9.8050605@kestrel.edu> Date: Thu, 22 Apr 2004 13:53:13 -0700 From: Dusko Pavlovic MIME-Version: 1.0 To: categories@mta.ca Subject: categories: Re: Getting rid of cardinality as an issue References: <200404220615.i3M6FDx1030384@coraki.Stanford.EDU> In-Reply-To: <200404220615.i3M6FDx1030384@coraki.Stanford.EDU> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 38 i think the question of foundations needs to be considered together with the meta-question: why working mathematicians don't care for foundations? a trivial part of the answer is that it's a matter of taste: some people organize their diet following the pyramid of "so much fruit so much vegetables so much meat", other people smoke and drink coffee and eat chocolate. the less trivial part of the answer is that the world of working mathematics is not built on top of a static foundation. the questions and the meta-questions are asked together. categories are foundations of categories. russell's paradox and hilbert's idea that math should have a static foundation are old. a lot has happened. sets are not so rigid any more. starting from models of untyped lambda calculus, people built all kinds of reflective universes, even containing small complete categories. the category of small categories can probably be a small 2-category in such a universe. the set of all sets can hardly be a set because of the variance, but i think that the set of all sets of sets can be a set in some models. my 2p, -- dusko Vaughan Pratt wrote: >Encouraged by the lack of objections to my previous message about why >Russell's Paradox should not be a big deal, I had a shot at shrinking the >position I spelled out there down to one paragraph, as follows. > >------------ >We shall axiomatize certain 1-categories using 2-categories. We avoid >Russell's paradox by treating any aggregation of $n$-categories as an >$(n+1)$-category, and allowing for the possibility that the >$(n+1)$-category >$n$-$\CAT$ of all $n$-categories might be exponentially larger than any of >its members. We impose no other size constraints besides the obvious >one of keeping things small enough to remain consistent. Sets are defined >as usual as 0-categories and categories as 1-categories. >------------ > >While I'm happy to field objections like "too flippant", I'm more concerned as >to whether there are any technical flaws, and to a lesser extent philosophical >or religious concerns. (I would not want to be held responsible for guns >being brought to the next UACT meeting if ever there is one.) > >Makkai and Pare address the same issue in AMS CM 104 (Accessible Categories) >with a hierarchy of Grothendieck universes (three, since they like me stop at >2-categories for the application at hand). > >Now the Grothendieck hierarchy is stepped through via ZF rather than Z, with >Fraenkel's Replacement axiom doing the heavy hitting. This creates gaps >mind-bogglingly larger than my teensy exponential gaps above. The general >idea seems to be that these gaps ought to be large enough to take care of >Russell while still not running headlong into inconsistency. However gaps >this large do entail a certain amount of finger-crossing, and one might >question the logic of hitting Russell with a nuclear weapon that might send >some fallout your way when a harmless little tack-hammer will take him out. > >One objection I can readily imagine to the above is that I've conflated >the n-category hierarchy with Russell's proposal for a ramified types >hierarchy. I would disagree with that. All I have done is to insist >on two things that seem to me to be independent. > >1. I have proposed to call aggregations of n-categories (n+1)-categories. >Now morphisms between n-categories are n-functors, and where there are >n-functors there are n-natural transformations, so this is hardly a bold >proposal. > >2. *Some* gap is needed between n-CAT and (n+1)-CAT, starting with the >requirement that Set be bigger than any set. Russell's paradox is no >respecter of n, applying just as effectively to an (n+1)-category of >n-categories as it does to a 1-category of sets. > >Certainly I have juxtaposed 1 and 2, but that is not the same thing as >conflating them. Their mere juxtaposition provides sufficient armor >against both Russell's paradox and the Icarus risk of flying too close to >an inconsistently large cardinal. > >The "prior art" for dealing with these issues has given rise to the adjectives >"small", "large," "superlarge", etc. and the nouns "set" and "class." >A good test for any revolution is the amount of blood it needs to shed. >The following definitions are aimed at minimal upheaval through maximum >compatibility with the status quo. > >* An object is n-small when it belongs to an n-category. > >* Small = 1-small, large = 2-small, superlarge = 3-small, etc. > >* A set is a discrete 1-category. > >* A class is a discrete n-category for unspecified n. > >Hopefully Sol Feferman will give an even simpler solution in his talk >tomorrow. > >Vaughan Pratt > > > > > > From rrosebru@mta.ca Fri Apr 23 08:49:47 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 23 Apr 2004 08:49:47 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BGzAw-0000lj-00 for categories-list@mta.ca; Fri, 23 Apr 2004 08:48:58 -0300 Message-Id: <200404222120.i3MLKtIj009503@coraki.Stanford.EDU> X-Mailer: exmh version 2.6.3 04/04/2003 with nmh-1.0.4 To: categories@mta.ca Subject: categories: Re: Getting rid of cardinality as an issue (correction) Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Date: Thu, 22 Apr 2004 14:20:55 -0700 From: Vaughan Pratt Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: A X-Keywords: X-UID: 39 >[Note from moderator: apologies to Vaughan for missing his requested >change: 1 has been changed to 0 5 lines from bottom, so it reads: >`discrete 0-category'.] Just for the record, the change I requested was from "discrete 1-category" to just "0-category" without the "discrete" (being redundant). Vaughan From rrosebru@mta.ca Fri Apr 23 08:50:36 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 23 Apr 2004 08:50:36 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BGzBy-0000ri-00 for categories-list@mta.ca; Fri, 23 Apr 2004 08:50:02 -0300 Date: Thu, 22 Apr 2004 15:41:18 -0700 From: Toby Bartels To: categories@mta.ca Subject: categories: Re: Getting rid of cardinality as an issue (correction) Message-ID: <20040422224118.GA11242@math-rs-n03.ucr.edu> References: <200404220615.i3M6FDx1030384@coraki.Stanford.EDU> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <200404220615.i3M6FDx1030384@coraki.Stanford.EDU> User-Agent: Mutt/1.4i Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 40 Vaughan Pratt wrote: >[Note from moderator: apologies to Vaughan for missing his requested >change: 1 has been changed to 0 5 lines from bottom, so it reads: >`discrete 0-category'.] And this is the line in question: >* A set is a discrete 0-category. Just to check, the word "discrete" here is redundant, right? You just put it in to contrast with the next line, where it's necessary: >* A class is a discrete n-category for unspecified n. -- Toby From rrosebru@mta.ca Sat Apr 24 15:24:15 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 24 Apr 2004 15:24:15 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BHRn4-0002hK-00 for categories-list@mta.ca; Sat, 24 Apr 2004 15:22:14 -0300 Subject: categories: Re: Re: Getting rid of cardinality as an issue From: Eduardo Dubuc To: categories@mta.ca Date: Fri, 23 Apr 2004 17:56:27 -0300 (ART) In-Reply-To: <408830B9.8050605@kestrel.edu> from "Dusko Pavlovic" at Apr 22, 2004 01:53:13 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: <20040423205635Z435405-14045+2640@mate.dm.uba.ar> Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 41 Dusko Pavlovic wrote: "why working mathematicians don't care for foundations?" very simple anwer: foundations is just an area within mathematics the working mathemeticians who care about foundations are those who work in foundations why do not ask the question: "why working mathematicians don't care for ring theory?" well, because we think that those who work in ring theory are working mathematicians but there are a lot who do not work in ring theory, and do not care either for foundations it is the same thing why we give foundations a different status ? saludos eduardo dubuc From rrosebru@mta.ca Sat Apr 24 15:24:15 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 24 Apr 2004 15:24:15 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BHRm2-0002do-00 for categories-list@mta.ca; Sat, 24 Apr 2004 15:21:10 -0300 Message-ID: <408922D7.6000408@unt.edu> Date: Fri, 23 Apr 2004 09:06:15 -0500 From: Mike Oliver User-Agent: Mozilla/5.0 (Windows; U; WinNT4.0; en-US; rv:1.4) Gecko/20030624 Netscape/7.1 (ax) X-Accept-Language: en-us, en MIME-Version: 1.0 To: categories@mta.ca Subject: categories: Re: Getting rid of cardinality as an issue References: <200404220615.i3M6FDx1030384@coraki.Stanford.EDU> In-Reply-To: <200404220615.i3M6FDx1030384@coraki.Stanford.EDU> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit X-Authentication-Info: Submitted using SMTP AUTH at out010.verizon.net from [4.34.142.171] at Fri, 23 Apr 2004 09:06:15 -0500 Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 42 Vaughan Pratt wrote: > While I'm happy to field objections like "too flippant", I'm more concerned as > to whether there are any technical flaws, and to a lesser extent philosophical > or religious concerns. (I would not want to be held responsible for guns > being brought to the next UACT meeting if ever there is one.) > [...] > Now the Grothendieck hierarchy is stepped through via ZF rather than Z, with > Fraenkel's Replacement axiom doing the heavy hitting. This creates gaps > mind-bogglingly larger than my teensy exponential gaps above. The general > idea seems to be that these gaps ought to be large enough to take care of > Russell while still not running headlong into inconsistency. However gaps > this large do entail a certain amount of finger-crossing, and one might > question the logic of hitting Russell with a nuclear weapon that might send > some fallout your way when a harmless little tack-hammer will take him out. I'm not entirely sure I follow what Vaughan's project is here, so this may come out as a non sequitur, but: Surely, from time to time, categorists must care about genuinely ultra-first-order notions, such as (say) the metric completeness of the real numbers? To me the natural way of getting such notions right is to make sure that each of your universes is closed under the (true) powerset operation. That would require the cardinality of your universes to be, at least, strong limit cardinals. Having them closed under ranges of functions also seems natural enough; at that point you need inaccessibles. It's by no means clear that inaccessibles are sufficient. What happens when you want to be closed under the operation of finding the next larger inaccessible? From rrosebru@mta.ca Sat Apr 24 15:24:15 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 24 Apr 2004 15:24:15 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BHRoc-0002mL-00 for categories-list@mta.ca; Sat, 24 Apr 2004 15:23:50 -0300 Date: Fri, 23 Apr 2004 23:45:19 -0700 From: Vaughan Pratt Message-Id: <200404240645.i3O6jJxJ017210@coraki.Stanford.EDU> To: categories@mta.ca Subject: categories: Modeling infinitesimals with 2x2 matrices Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: X-Keywords: X-UID: 43 At some point I'll try to collect my thoughts on Sol Feferman's Thursday lecture on his alternative to Grothendieck universes, which he objected to as entailing an infinity of inaccessible cardinals. (What was Grothendieck's view of inaccessible cardinals vis a vis his universes?) During the lecture it struck me that his approach was quite like Robinson's approach to infinitesimals, in that it constructed lots of models of what was needed, took the common theory, then constructed a single model from the many, using techniques of Vaught and others to avoid losing too much of the common spirit of the many guided by the common theory (not sure if that captures the idea completely faithfully, but it's something like that). Thus distracted, I found myself wondering yet again why the d^2 = 0 property was so difficult for an infinitesimal d. Having been mulling over the quaternions lately, it seemed to me there was something of an analogy there, some property so built into our very psyche that we can't let go of it. Hamilton finally dropped commutativity, along with any reservations he might have harbored about vandalizing stone bridges in his own town. For the quaternions, d^2 = 0 implies d = 0, so this doesn't help. However the quaternions have a sibling algebra, just as noncommutative, and of exactly the same vector space dimension (in fact the only Clifford such, i.e. the only other real 4D vector space for which ij+ji=0 for all orthogonal vectors i,j having no real component), that is even better known than the quaternions (imagine that). Namely the Clifford algebra of 2x2 real matrices, as a 4D real vector space, made an algebra with matrix multiplication. Why not model d as the matrix 0 1 0 0? This is a perfectly good quantity, adding and scaling just like any real, e.g. 2d = 0 2 0 0. And obviously d^2 = 0. Standard reals x would have the form x 0 0 x 1+d would therefore be 1 1 0 1 (1+d)^2 then becomes 1 2 0 1 as common sense would indicate. The determinant of d being 0, one can't divide by it. But who in their right mind would want to divide by a quantity infinitesimally close to zero? Obviously that's going to produce an infinitely large quantity; if you want to do that, why not just go ahead and divide by zero itself? As Douglas Adams pointed out, you may think the store down the road is a fair way away, but other galaxies are even further away. To a nematode they're all far away. On the other hand 1 2 0 1 has a perfectly good reciprocal, namely 1 -2 0 1 again as suggested by common sense. So the proposal is to base calculus on a field-like object that is a field in the large, but zero divide errors set in when one gets infinitesimally close to zero. Basically what happens with IEEE floating point arithmetic, but modeled with 2x2 real matrices rather than 64-bit numbers. Oh, but what about the noncommutativity of 2x2 matrices, might that mess something up? Actually no, this two-dimensional algebra consisting of matrices of the form a b 0 a is commutative. So only the zero divisors really close to 0 constitute any departure at all from the field axioms. The diagonal element a is the standard real part and the off-diagonal element b in the upper right gives the infinitesimal displacement. So we have a real commutative associative algebra of refined numbers, having a real part and an infinitesimal part, whose only zero divisors are the infinitesimals. We don't *have* to think of them as matrices because we can just write its elements as x+yd by analogy with x+iy, where d is the above matrix representing the prototypical infinitesimal. The square of i is -1, and the square of d is 0. Moreover x and y in x+yd can be complex. We then have numbers x+iy+ud+ivd, which can parsed as either refined complex numbers, namely complex numbers with refined coefficients x+ud+i(y+vd), or complex refined numbers, namely refined numbers with complex coefficients x+iy+(u+iv)d. This is still a real associative algebra, which through force of habit people will no doubt want to call a complex commutative associative algebra, but it could just as legitimately be called a refined associative algebra. Ok, what about commutative? Well, the complex numbers are commutative and the refined numbers are commutative, so how could refining complex numbers make any difference? Well, the reason I wrote x+yd rather than x+dy is that, even though the *natural* thing to do is to make i commute with d, if instead we make id+di=0, the defining condition for Clifford algebras, then we can fit the whole thing into 2x2 *real* matrices! Here I'm using the following 2x2 real matrices for i and d respectively: (0 -1) (0 1) (1 0) (0 0) But now notice that the matrices for 1,i,d,id form a basis for all the 2x2 matrices. In fact *any* 2x2 matrix [[a,b],[c,d]] can be decomposed as (d -c) + (a-d b+c) (c d) ( 0 0 ) (I'd appreciate feedback from anyone for whom the above doesn't typeset readably.) So to read an arbitary 2x2 real matrix as a refined complex number, take the bottom row reversed as the complex part and the departure of the top row from the usual matrix representation of complex numbers as the infinitesimal part, taking care to get both signs right. How did I notice this? Simple. I knew (i) that id+di=0 would make it a Clifford algebra, (ii) there are only two 4D Clifford algebras, and (iii) d^2 = 0 -> d = 0 in the quaternions. This narrows things down to the 2x2 real matrices, there are no other associative algebras with these properties. Getting the above decomposition was then just a matter of solving some trivial linear equations. This is so simple, and the infinitesimals have been worried at for so long, that this *has* to be known already. But then it would really bug me to have been the last to learn about it -- why wasn't I told, as they say? Vaughan Pratt From rrosebru@mta.ca Sun Apr 25 18:07:55 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 25 Apr 2004 18:07:55 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BHqk7-0005dZ-00 for categories-list@mta.ca; Sun, 25 Apr 2004 18:00:51 -0300 Message-Id: <200404242246.i3OMkeOq031856@coraki.Stanford.EDU> X-Mailer: exmh version 2.6.3 04/04/2003 with nmh-1.0.4 To: categories@mta.ca Subject: categories: Re: Modeling infinitesimals with 2x2 matrices Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Date: Sat, 24 Apr 2004 15:46:40 -0700 From: Vaughan Pratt Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 44 Correction to my suggestion id+di = 0. Don't do it. id = di is fine as it stands for refined complex numbers, which should be represented in C(2) = 2x2 complex matrices (embeddable in R(4) - 4x4 real matrices) as the obvious extension of the refined reals x+yd. I shouldn't have been so smug about 4D Clifford algebras, this algebra of refined complex numbers doesn't satisfy d^4 = 1, needed if d is to be a Clifford generator. And in fact although di = 1 0 0 0 we have id = 0 0 0 1 (I should have checked that more carefully.) I thought about trying to make the infinitesimals points on the "light cone" of R(2) (the singular matrices) but couldn't get that to work. So 2x2 complex matrices with id = di is the best I could think of. This works for modeling the refined complex numbers (barring any other errors), but with nothing left to motivate id+di = 0. The representation x+iy+dv+idw is fine, with idw = diw = wid etc., all is commutative. (I was hoping too hard for the excitement of noncommutativity, this is boringly noninteractive as it stands.) Vaughan From rrosebru@mta.ca Sun Apr 25 18:07:55 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 25 Apr 2004 18:07:55 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BHqmL-0005rz-00 for categories-list@mta.ca; Sun, 25 Apr 2004 18:03:09 -0300 Mime-Version: 1.0 (Apple Message framework v613) Content-Type: text/plain; charset=US-ASCII; format=flowed Message-Id: <5094C5F9-965C-11D8-B304-0003938AD038@math.tulane.edu> Content-Transfer-Encoding: 7bit From: Michael Mislove Subject: categories: MFPS Program Now Available - Deadline for Reduced Hotel Rates Date: Sat, 24 Apr 2004 21:00:24 -0500 To: categories@mta.ca X-Mailer: Apple Mail (2.613) Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 45 Dear Colleagues, With apologies for multiple copies, the program for MFPS 20 is available at http://www.math.tulane.edu/~mfps/mfps20prog.html It also can be accessed from the MFPS 20 home page http://www.math.tulane.edu/~mfps/mfps20.htm Registration for the meeting can be done online at http://www.math.tulane.edu/~mfps/regform20.html Those interested in attending the meeting should note that the conference hotel will hold a block of rooms at the conference rate ONLY UNTIL MAY 1. After that date, the conference rate will no longer be available. Best regards, Mike Mislove =============================================== Professor Michael Mislove Phone: +1 504 862-3441 Department of Mathematics FAX: +1 504 865-5063 Tulane University URL: http://www.math.tulane.edu/~mwm New Orleans, LA 70118 USA =============================================== From rrosebru@mta.ca Sun Apr 25 18:09:43 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 25 Apr 2004 18:09:43 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BHqnn-00060G-00 for categories-list@mta.ca; Sun, 25 Apr 2004 18:04:39 -0300 Message-Id: <200404250658.i3P6wdYo009866@coraki.Stanford.EDU> X-Mailer: exmh version 2.6.3 04/04/2003 with nmh-1.0.4 To: categories@mta.ca Subject: Re: categories: Modeling infinitesimals with 2x2 matrices Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Date: Sat, 24 Apr 2004 23:58:39 -0700 From: Vaughan Pratt Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 46 I'm told that Bell's "microlinear calculus" in his 1998 book on infinitesimals is equivalent to the matrix approach I suggested, so that was not new after all, other than perhaps its formulation in terms of 2x2 matrices. On the other hand it is apparently mixed in with Bell's strongly intuitionistic outlook, whereas it would seem intuitively that something so simple as a model of d^2 = 0 should transcend whether one is working intuitionistically or classically. A more classical version of Bell's account might be of interest (perhaps to relatively few people on the categories mailing list though, which seems to have a strongly intuitionistic slant). Meanwhile I received the April issue of Mathematics Magazine just now, and it has an article on pp. 118-129 on "Geometry of Generalized Complex Numbers" by Anthony and Joseph Harkin. The microlinear calculus, under the names "Study product" and "parabolic complex numbers," apparently dates back to Study's 1903 book Geometrie der Dynamen. The Harkins associate i^2 = -1,0,1 with respectively Ordinary (i.e. complex) product, Study product, and Clifford product (though Clifford algebras include ordinary product as well, the quaternions being a Clifford algebra). The article makes no mention of infinitesimals, and it would be interesting to try to find the appropriate infinitesimal interpretations of the geometric properties of the parabolic complex plane. One approach I very much like to infinitesimals that I haven't seen in the nonstandard analysis/infinitesimal literature (but would certainly appreciate pointers) is one that does all the work with what one might call finitesimals. A finitesimal h is just a positive real that you plan one day to reduce to zero, and thus organize everything around it to that end. Polynomials in R[x] of degree d form a (d+1)-dimensional vector space. The usual basis for this space is the d+1 monomials x^i for i in 0..d. However if one fixes h > 0 and takes the basis to be 1, x, x(x-h), x(x-h)(x-2h),... then Boole's difference calculus works essentially identically to the infinitesimal calculus for polynomials represented in the monomial basis. Since h is a free variable throughout the development, one can do all the work first and then drive h to 0 uniformly everywhere at the end. Expressions such as x^i (Knuth writes an underbar under the i and calls it "x to the falling i") mention h only implicitly and hence don't change (as symbolic expressions) as h changes, though their numerical values at any given x change. The Stirling numbers of the first and second kind, organized as matrices, constitute linear transformations from the bases for h=1 to h=0 and back again, respectively. I've looked from time to time at how one might extend this to exponentials and logarithms, but have never been satisfied with the results. It would be nice to know how to deal exactly with exp(it) for nonzero h. If this were possible it might give an even nicer constructive treatment of infinitesimals than the others, and one that didn't care at all whether one was classically or intuitionistically inclined. Vaughan Pratt From rrosebru@mta.ca Sun Apr 25 18:12:25 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 25 Apr 2004 18:12:25 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BHqqo-0006DM-00 for categories-list@mta.ca; Sun, 25 Apr 2004 18:07:46 -0300 Message-Id: <200404251354.i3PDs6i0022718@coraki.Stanford.EDU> X-Mailer: exmh version 2.6.3 04/04/2003 with nmh-1.0.4 To: categories@mta.ca Subject: categories: Re: Getting rid of cardinality as an issue Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Date: Sun, 25 Apr 2004 06:54:06 -0700 From: Vaughan Pratt Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: X-Keywords: X-UID: 48 >From: Mike Oliver >Surely, from time to time, >categorists must care about genuinely ultra-first-order notions, such as >(say) the metric completeness of the real numbers? To me the natural >way of getting such notions right is to make sure that each of your >universes is closed under the (true) powerset operation. Yes, which was why I formulated the exponential gap only as a lower bound. The idea was that if you needed more, take it. In retrospect I should have included the Russell paradox, viewed constructively as a set factory rather than mysteriously as a bogeyman under the bed, as something one might or might not need for some purpose, e.g. as a successor function. This reclassification (as a shift only in my personal outlook) prompts me to withdraw my suggestion (made as much for my benefit as anyone's but as such good to bounce off people) of imposing any lower bound at all on size of gaps between successive n-CAT categories. Size can certainly be an issue, whether involving rates of growth of functions on the integers, or large cardinals. In their CM104 book, Makkai and Pare treat the first order model theory (as opposed to first order logic) of accessible categories, where the goal is to characterize the behavior of categories independently of their size as far as possible, and where not possible to characterize the dependencies on size. Such an enterprise is not ordinary mathematics but foundations, and as such is *about* these gaps. Their results (presumably with the help of a consultant) should allow those on the consuming side of foundations, i.e. those doing ordinary mathematics (if there really is such a thing), to judge for themselves whether a given construction is in danger of colliding with a size paradox. One would hope that a few simple rules of thumb would minimize dependence on consultants, though it did not seem to me that CM104 was organized with that economy clearly in mind; this might be corrected with a short cheat sheet as an addendum. Not all paradoxes concern size. The liar paradox and the division-by-infinitesimal paradoxes can be turned into size paradoxes via a suitable encoding, but they are not intrinsically size-related; well, in the case of infinitesimals, not large sizes anyway. Perhaps it just reflects my old-fashioned upbringing, but the foundational role intended for CM104 is way clearer to me than any of the several topos texts currently scattered around my desk. Not with regard to the definitions, examples, and (to the extent I understand their motivation) the theorems of topos theory. The elementary definition of a topos is crystal clear (not to mention incredibly beautiful), as are the basic examples of toposes. Where I run into problems is in placing topos theory as a foundation beside say accessible categories. I can go repeatedly through the topos texts and just not get it. Is there some finely honed sentence or paragraph that explains this relationship? I get the feeling there should be a sentence or paragraph to the effect that one brings size under control (or makes it a non-issue) by passing from the external logic of accessible categories to the internal logic of toposes. Is some such clear and succinct story (not necessarily that one since it might be totally wrong) told somewhere? If so, one could deal with idiots like me who rant about size as an issue by pointing them at that story, by way of indicating how to stop worrying about inaccessible cardinals by embracing someone else's internal logic (and making it one's own?). Or whatever the story actually is. What about Remark 7.1.14 in Paul Taylor's Practical Mathematics, for example? Is this tangential, on point, or core? What about the preface to Borceux' Volume 3? Does Peter Johnstone's nonconstructive theorem "There exists an elephant" in his preface have a succinctly summarized constructive counterpart somewhere, a sort of sharply focused photo of an elephant taken from 50 feet away? (Actually I suppose a sharply focused photo of a real elephant would have very close to the same number of megabytes of data as in the two volumes, so maybe I mean an elephant icon.) Or is this all just a misunderstanding or misinterpretation of the real goals of topos theory, with the truth being that there is ultimately no way mathematicians can avoid large cardinals if they expect to be able to prove certain theorems, even those of an ostensibly combinatorial flavor? This is certainly the sermon that Harvey Friedman has been preaching for a number of years; is Harvey wrong about this? There seem to be some sunglasses and rose-colored glasses lying around but I can't tell who they belong to. Surely they're not all mine. Vaughan Pratt From rrosebru@mta.ca Tue Apr 27 16:54:05 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 27 Apr 2004 16:54:05 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BIYbu-00070h-00 for categories-list@mta.ca; Tue, 27 Apr 2004 16:51:18 -0300 Message-Id: <5.2.0.9.0.20040425221849.01aaaeb8@pop.cwru.edu> X-Sender: cxm7@pop.cwru.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.2.0.9 Date: Sun, 25 Apr 2004 22:58:28 -0400 To: categories@mta.ca From: Colin McLarty Subject: categories: Extensions of Z+Z by Z Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 49 After calculating the group extensions of Z+Z by Z, with constant action, I am curious whether the groups have any more natural form than I found. I mean extension of Z+Z by Z in this sense, as a sequence of groups where E need not be commutative: 0 --> Z --> E --> Z+Z --> 0 and the kernel is in the center of E. The form I found is parametrized by the integers this way: For any integer c, the group E_c has triples of integers (i,,j,k) as elements and the multiplication rule is coordinate-wise addition plus an extra bit in the first coordinate. (i,,j,k).(q,r,s) = ( (i+j+c.(kr)), j+r, k+s) When c=0 this is commutative and is just the coproduct Z+Z+Z. In any group E_c, the element (c,0,0) is the commutator of (0,0,1) and (0,1,0). The Baer sum of extensions corresponds to addition of the parameters c as integers. So I understand the group of extensions. Of course I understood it before I calculated it, since it is the second cohomology group of the torus. That is why I tried the algebraic calculation. But is there a natural way to think about each group E_c, for non-zero values of c? Do these groups appear in any other natural way? thanks, colin From rrosebru@mta.ca Tue Apr 27 16:54:42 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 27 Apr 2004 16:54:42 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BIYf7-0007CC-00 for categories-list@mta.ca; Tue, 27 Apr 2004 16:54:38 -0300 X-Mailer: exmh version 2.6.3 04/04/2003 with nmh-1.0.4 To: categories@mta.ca Subject: categories: Re: Modeling infinitesimals with 2x2 matrices In-Reply-To: Message from Steve Vickers of "Mon, 26 Apr 2004 09:47:38 BST." <408CCCAA.9090404@cs.bham.ac.uk> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Date: Mon, 26 Apr 2004 09:54:31 -0700 From: Vaughan Pratt Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: RO X-Status: X-Keywords: X-UID: 50 From: Steve Vickers >I thought that was the whole reason for contemplating infinitesimals in >the first place - 0/0 cannot be meaningful, but d/d is 1, ed/d is e etc. Well, you're not alone in thinking that way. This was the basis for Robinson's invention of nonstandard analysis: the belief that a/b has to be defined for all nonzero b in order to make infinitesimals nonparadoxical. Instead of formulating division a/b as an operation, go back to its motivating formulation as a system in search of a solution, in this case the system consisting of the one linear equation a = bx in one unknown. Had the system been one of ordinary or partial differential equations, there would be no argument that the solution space could turn out quite oddly shaped. Now when a and b are reals the solution space is a rectangle: only the column indexed by b=0 is undefined. This remains true when a and b are extended to the complex numbers, or even to the quaternions. But if you extend the domain to the algebra R(2) of 2x2 real matrices, the columns indexed by singular matrices now lose some of their entries. But not all, and so the solution space ceases to be rectangular. Robinson believed that the way to make infinitesimals safe for analysis was to make the solution space for a = bx rectangular. Today's logicians are magicians with logic: if logic indicates the impossibility of a rectangular solution space, no need to abandon that goal, just bend logic until the solution space does become rectangular. The students will bend with you, at least those who've approached nonstandard analysis with the proper upbeat spirit about how much simpler analysis becomes when infinitesimals can be objectified. Power tools are wonderful. To answer your question (or comment), in the system of refined numbers I described, if b is infinitesimal and nonzero, a = bx is solvable if and only if a is infinitesimal. The division table is no longer rectangular. So what? One might grumble that a = bx can't have an infinitesimal part when a and b are both infinitesimals, but in the simple cases that's a plus. In more complicated cases, 2x2 matrices aren't enough, you need nxn matrices, with distance of nonzero entries from the diagonal measuring the degree of their infinitesimality (if that's a word). In this case d^n = 0 only for higher n's. After thinking along those lines for a bit more the other day, I decided that even though I liked this approach better than throwing ultrafilters at it, it still wasn't as good as doing analysis in Boole's finite difference calculus with h remaining unbound throughout, the approach I'd used since the early 1970's. That approach has the great advantage of being able to use the same analysis in classical and quantum physics by setting h=0 to interpret a result classically and setting it to Planck's constant to interpret the same result quantumly. As a case in point, the same integration formulas can deliver areas under smooth curves and discrete summations of e.g. n^3, the latter with h=1. (I already wrote a bit about that two or three messages ago.) The right power tools are even more wonderful. Vaughan Pratt From rrosebru@mta.ca Tue Apr 27 16:55:16 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 27 Apr 2004 16:55:16 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BIYfh-0007ET-00 for categories-list@mta.ca; Tue, 27 Apr 2004 16:55:13 -0300 Date: Tue, 27 Apr 2004 08:39:28 -0700 From: Vaughan Pratt Message-Id: <200404271539.i3RFdSUW007359@coraki.Stanford.EDU> To: categories@mta.ca Subject: categories: The proposition O=H Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: X-Keywords: X-UID: 51 Anyone who's subscribed to this list long enough knows that I've been sufficiently bothered by the disjunction "Sets or categories" as to pester the list with my botherment periodically. I bothered the FOM mailing list with the same question for some years, with rather less civilized responses on occasion -- that was quite a wild list for a while, but Martin Davis seems to have done a good job of stabilizing it, too late unfortunately for those of us who found the repartee counterproductive and moved on before his administration. My pestering is not so much to make a nuisance of myself as to get a satisfactory answer. So far the answers, on either side, have struck me as entailing a certain acceptance of the local lore and wisdom bordering on religion. I would like to propose a middle ground on which set theorists and category theorists can meet amicably. The middle ground is expressed by the proposition O=H, that objects and homobjects are of the same type. One of "mathematics" or "short" is defined by the proposition that all short definitions have been made, all short questions asked already, and all short theorems either previously proved or now famous open problems. Before pursuing this line of thought any further I'd like to ask whether O=H is short in the above sense. Has it been brought up before, and if so what are the prevailing views on it? Vaughan Pratt From rrosebru@mta.ca Wed Apr 28 13:58:40 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 28 Apr 2004 13:58:40 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BIsMH-00079o-00 for categories-list@mta.ca; Wed, 28 Apr 2004 13:56:29 -0300 From: "Ronald Brown" To: References: <5.2.0.9.0.20040425221849.01aaaeb8@pop.cwru.edu> Subject: Re: categories: Extensions of Z+Z by Z Date: Wed, 28 Apr 2004 07:27:54 +0100 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit X-Priority: 3 Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: RO X-Status: X-Keywords: X-UID: 52 Try the Heisenberg group of upper triangular matrices with 1's on the diagonal and the integers i,j,k in the upper non diagonal entries. 1 k i 0 1 j 0 0 1 This should give the case c=1, but your formula is not quite correct as the RHS does not involve q. Should it be q + j + c.(kr)? Ronnie Brown http://www.bangor.ac.uk/~mas010 ----- Original Message ----- From: "Colin McLarty" To: Sent: Monday, April 26, 2004 3:58 AM Subject: categories: Extensions of Z+Z by Z > After calculating the group extensions of Z+Z by Z, with constant action, I > am curious whether the groups have any more natural form than I found. I > mean extension of Z+Z by Z in this sense, as a sequence of groups where E > need not be commutative: > > 0 --> Z --> E --> Z+Z --> 0 > > and the kernel is in the center of E. > > The form I found is parametrized by the integers this way: For any integer > c, the group E_c has triples of integers (i,,j,k) as elements and the > multiplication rule is coordinate-wise addition plus an extra bit in the > first coordinate. > > (i,,j,k).(q,r,s) = ( (i+j+c.(kr)), j+r, k+s) > > When c=0 this is commutative and is just the coproduct Z+Z+Z. In any group > E_c, the element (c,0,0) is the commutator of (0,0,1) and (0,1,0). The > Baer sum of extensions corresponds to addition of the parameters c as > integers. So I understand the group of extensions. Of course I understood > it before I calculated it, since it is the second cohomology group of the > torus. That is why I tried the algebraic calculation. > > But is there a natural way to think about each group E_c, for non-zero > values of c? Do these groups appear in any other natural way? > > thanks, colin > > > From rrosebru@mta.ca Wed Apr 28 13:58:41 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 28 Apr 2004 13:58:41 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BIsNr-0007UR-00 for categories-list@mta.ca; Wed, 28 Apr 2004 13:58:07 -0300 Date: Wed, 28 Apr 2004 16:48:56 +0200 From: "Frank D. Valencia" Subject: categories: CoLoPS04: Call for Papers To: categories@mta.ca Message-id: <20040428144856.GA18568@ir> MIME-version: 1.0 Content-type: text/plain; charset=us-ascii Content-transfer-encoding: 7BIT Content-disposition: inline User-Agent: Mutt/1.5.5.1+cvs20040105i Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: X-Keywords: X-UID: 53 [[ -- Apologies for multiple copies of this message -- ]] =================================================================== CoLoPS 2004 International Workshop on COnstraint & LOgic Programming in Security December 5-11th, 2004 - Saint-Malo, France Satellite Workshop to ICLP 2004 ==================================================================== Scope of the workshop: Due to its practical relevance and complexity, the study of security has become a serious challenge involving several disciplines of computer science. A noteworthy aspect is that in several instances this study has used directly or indirectly tools and techniques from (Concurrent) Constraint Programming and (Linear) Logic Programming. For example, constraint solving has successfully been used for verifying security protocols, and several process algebras for modelling cryptographic protocols (e.g., recent variants of the spi calculus, SPL) have remarkable similarities with Concurrent Constraint Programming. Also (Linear) Logic Programming has been used as a framework for security protocols, and one of its central notions, unification, has been used for the symbolic execution of cryptographic calculi. CoLoPS aims at getting a broader perspective on the role of Constraint and Logic Programming in the study of security. Topics of interest include (but are not restricted to) frameworks for security using algorithms, verification techniques, process algebras or programming languages, with a Constraint or Logic Programming flavor. Submission and publication: Paper submissions should not exceed 15 pages. Submissions should be sent as a PDF or Postscript le via email to Frank D. Valencia (frankv@it.uu.se). The email should have: 1. "COLOPS Submission" as subject, 2. submission title and authors' relevant information as body, and 3. submission le as an attachment. The accepted papers will be included in the workshop proceedings as a research report of Uppsala University. Accepted papers will be published in an ENTCS (Electronic Notes in Theoretical Computer Science) volume dedicated to ICLP 2004 workshops. Papers describing ongoing work or already published are also welcome but will not be part of the proceedings. Please mark your paper accordingly. Program Committee: Elvira Albert (UC Madrid, Spain) Maria Alpulente (UP Valencia, Spain) Stefano Bistarelli (ITT-CNR, Italy) Martin Leucker (TU Munich, Germany) Sebastian Moedersheim (ETH Zurich, Switzerland) Ugo Montanari (Universita di Pisa, Italy) Catuscia Palamidessi (INRIA, France) Justin Pearson (Uppsala University, Sweden) Fred Spiessens (Universit e catholique de Louvain, Belgium) Frank D. Valencia (Uppsala University, Sweden) Pascal Van Hentenryck (Brown University, USA) Vijay Saraswat (IBM, USA) Bjorn Victor (Uppsala University, Sweden) Alicia Villanueva (UP Valencia, Spain) Organizing Committee: Martin Leucker (TU Munich, Germany), Justin Pearson (Uppsala University, Sweden), Fred Spiessens (Universit e catholique de Louvain, Belgium), Frank D. Valencia (Uppsala University, Sweden) Important dates: Submission deadline: June 27, 2004 Notification of acceptance: July 18, 2004 Final version: August 15, 2004 Workshop: September 5th or 11th, 2004 (Dependent on ICLP organizers) For more and up-to-date information see the www page http://www.info.ucl.ac.be/people/fsp/colops2004/ From rrosebru@mta.ca Wed Apr 28 13:58:41 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 28 Apr 2004 13:58:41 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BIsN4-0007Eo-00 for categories-list@mta.ca; Wed, 28 Apr 2004 13:57:18 -0300 X-Sender: ces@pop.cs.stir.ac.uk Message-Id: Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Date: Wed, 28 Apr 2004 15:07:39 +0100 To: AMAST04 mailing list:;;@cs.stir.ac.uk From: Carron Shankland Subject: categories: AMAST 04: Call for Participation X-MailScanner-Information: Please contact the ISP for more information Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 54 ******** AMAST 2004 ******** ** Call for participation ** **************************** 10th International Conference on Algebraic Methodology and Software Technology July 12th - 16th 2004 Stirling, Scotland, UK http://www.cs.stir.ac.uk/events/amast2004/ ********************************************************************* 20 EPSRC supported places for UK based students first come, first served - apply now and avoid disappointment! ********************************************************************* Keynote Speakers: * Roland Backhouse (Nottingham) * Don Batory (Texas) * Michel Bidoit (CNRS) * Muffy Calder (Glasgow) * Bart Jacobs (Nijmegen) * JJ Meyer (Utrecht) ********************************************************************* AMAST promotes research that may lead to the setting of software technology on a firm, mathematical basis. This goal is achieved by a large international cooperation with contributions from both academia and industry. AMAST 2004 will include keynote talks by leaders in the fields of software/system correctness, software development, including extensible and adaptive software, and evolutionary systems. The main programme consists of presentations of refereed technical papers on leading-edge research. AMAST 2004 is co-located with MPC 2004 (Mathematics of Program Construction) ARTS 2004 (AMAST Real Time Workshop). Participants for AMAST will be able to attend talks of both these events for free (and vice versa). AMAST 2004 is being held in Stirling, a historic city located in the heart of Scotland. The conference venue and accommodation are all based on the University campus, which is convenient for visiting the ancient castle and Wallace monument, or for going further afield and exploring the beautiful countryside. Social events include a civic reception, an afternoon excursion to Loch Lomond, and dinner in a quaint Scottish village. ********************************************************************** Book early for cheaper registration and guaranteed accommodation Deadline: 29th May 2004 http://www.cs.stir.ac.uk/events/amast2004/ ********************************************************************** -- The University of Stirling is a university established in Scotland by charter at Stirling, FK9 4LA. Privileged/Confidential Information may be contained in this message. If you are not the addressee indicated in this message (or responsible for delivery of the message to such person), you may not disclose, copy or deliver this message to anyone and any action taken or omitted to be taken in reliance on it, is prohibited and may be unlawful. In such case, you should destroy this message and kindly notify the sender by reply email. Please advise immediately if you or your employer do not consent to Internet email for messages of this kind. From rrosebru@mta.ca Thu Apr 29 12:40:55 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 29 Apr 2004 12:40:55 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BJDZc-0004A5-00 for categories-list@mta.ca; Thu, 29 Apr 2004 12:35:40 -0300 To: categories Subject: categories: Re: Modeling infinitesimals with 2x2 matrices Date: Tue, 27 Apr 2004 22:13:13 -0700 From: Vaughan Pratt Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 55 >But if you extend the domain to the algebra R(2) of 2x2 real matrices, >the columns indexed by singular matrices now lose some of their entries. >But not all, and so the solution space ceases to be rectangular. On reflection this is not so simple in the case when b in a/b is infinitesimal. First, noting that R(2) is noncommutative, the requirement should be phrased as two equations, a = bx and a = xb to prevent multiple solutions whose diagonal is not constant. But while this duplication then determines a unique real part (the diagonal), the two equations fail to pin down the infinitesimal part (the upper right entry). That's the sort of thing that happens with matrices of less than full rank. When there is no solution, certainly a/b should be considered undefined. But when there are multiple solutions, the question arises as to whether to punt completely (as with 0/0) or do something creative such as setting the undefined infinitesimal part to 0 (as with the ratio of two infinitesimals). One test is whether the "dominant" term is fixed, but this breaks down for 0/b. A better test would be to use the rank of b to decide how much of the quotient a/b to ignore---if b has rank 1 (a nonzero infinitesimal) then ignore the infinitesimal part of a/b. --------------- One virtue of Robinson's approach is its universality with respect to all first-order definable functions; this however is not sufficient to compensate for its more counterintuitive aspects. Now that I'm starting to see that the zero-divisor approach is less easily managed than I'd first thought, I'm not so sold on it either at this point (but maybe all its difficulties have been overcome somewhere...?). Meanwhile I remain convinced that Boole's finite difference approach to handling infinitesimals is superior (recall the trick here: setting h=0 instead of some positive quantity like 1 or Planck's constant introduces no artificial singularities with Boole's method). His 1860 *A Treatise on the Calculus of Finite Differences," substantially revised by J.F. Moulton for the 1872 edition after Boole's death, is 336 pages of inspired analysis. (You can get second hand copies for $10 from Amazon; my very second hand copy has "F.S. Curry, Trin. Coll., Feb. 1881" written on the inside cover.) The preface to the first edition starts out, "In the following exposition of the Calculus of Finite Differences, particular attention has been paid to the connexion of its methods with those of the Differential Calculus---a connexion which in some instances involves far more than a merely formal analogy. Indeed the work is in some measure designed as a sequel to my *Treatise on Differential Equations*. And it has been composed on the same plan." An updated version of this book incorporating the greatly matured perspective on linear algebra since then could be a worthwhile project for someone interested in improving on the existing explications of infinitesimals as real objects. While Boole's system beats the current crop hands down in principle (in my view anyway), in outlook it is showing its age. Category theory creatively applied might also help. I confess to having no idea how intuitionistic logic could be brought to bear effectively though. I can see that not cancelling certain double negations might preserve certain nuances that convey certain constructively motivated notions, but to my untrained eye these come across as nuances with a capital N when their contribution is assessed in the larger picture of alternative approaches to constructivizing infinitesimals. That makes me either a beer guzzler at a wine tasting or the owner of a screwdriver in a room full of hammer owners depending on one's outlook. :) YBMV (Your biases may vary.) Vaughan Pratt -------------------------- From rrosebru@mta.ca Thu Apr 29 12:40:55 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 29 Apr 2004 12:40:55 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BJDcM-0004Kk-00 for categories-list@mta.ca; Thu, 29 Apr 2004 12:38:30 -0300 Message-Id: <200404290018.i3T0I9Y21150@math-ws-n09.ucr.edu> Subject: categories: re: Extensions of Z+Z To: categories@mta.ca (categories) Date: Wed, 28 Apr 2004 17:18:09 -0700 (PDT) From: "John Baez" X-Mailer: ELM [version 2.5 PL6] MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 56 Ronnie Brown writes: > Colin McLarty wrote: > > After calculating the group extensions of Z+Z by Z, with constant action, > > I am curious whether the groups have any more natural form than I found. > > I mean extension of Z+Z by Z in this sense, as a sequence of groups where > > E need not be commutative: > > > > 0 --> Z --> E --> Z+Z --> 0 > > > > and the kernel is in the center of E. > > > > The form I found is parametrized by the integers this way: For any > > integer c, the group E_c has triples of integers (i,j,k) as elements and > > the multiplication rule is coordinate-wise addition plus an extra bit > > in the first coordinate. > Try the Heisenberg group of upper triangular matrices with 1's on the > diagonal and the integers i,j,k in the upper non diagonal entries. > > 1 k i > 0 1 j > 0 0 1 > > This should give the case c=1 [...] The name "Heisenberg" hints that anyone with a physics bone in their body can't resist thinking about this sort of extension in terms of quantum mechanics. In this context, the constant that parametrizes the central extension, which Colin and Ronnie are calling "c", is called "Planck's constant", or "hbar" for short. The original Heisenberg groups were the central extensions of R^2 by U(1) (the unit complex numbers). To get these, we represent any element (a,b) in R^2 as a unitary operator on L^2(R): U(a,b) = exp(iaq + ibp) where q and p are the self-adjoint "position" and "momentum" operators on L^2(R): q = multiplication by x p = -i hbar d/dx These unitary operators U(a,b) fail to commute because [p,q] = - i hbar so the group they generate is not R^2, except in the "classical" case where hbar = 0. Instead, they generate a group of operators that is a central extension of R^2 by U(1). We get all the central extensions of R^2 by U(1) this way. Central extensions of R^2 by R work similarly; you get one for each real number hbar. Apparently central extensions of Z^2 by Z also work similarly! Best, jb From rrosebru@mta.ca Thu Apr 29 12:43:07 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 29 Apr 2004 12:43:07 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BJDfL-0004Vv-00 for categories-list@mta.ca; Thu, 29 Apr 2004 12:41:35 -0300 Message-Id: <200404290054.i3T0s1P21354@math-ws-n09.ucr.edu> Subject: categories: Modeling infinitesimals with 2x2 matrices To: categories@mta.ca (categories) Date: Wed, 28 Apr 2004 17:54:01 -0700 (PDT) From: "John Baez" X-Mailer: ELM [version 2.5 PL6] MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 57 Vaughan Pratt writes: > Why not model d as the matrix > > 0 1 > 0 0 ? > > This is a perfectly good quantity, adding and scaling just like any > real, e.g. > > 2d = 0 2 > 0 0. > > And obviously d^2 = 0. Part of this idea is implicit in the usual algebraic geometry treatment of infinitesimals as nilpotents. In addition to the usual "point", such that complex functions on this space form the commutative ring C, algebraic geometers like to think about the "point with nth-order nilpotent fuzz", such that complex functions on this space form the commutative ring C[d]/. They visualize this as a space slightly bigger than a point: just big enough to tell the difference between the function 0 and the function whose first n-1 derivatives equal zero! To deal with this sort of "space" in a precise way, someone like Grothendieck invented the category of affine schemes, which is just the opposite of the category of commutative rings. But affine schemes are happier as part of a larger category of schemes... and thus topos theory was brought kicking and screaming into the world. To see how this led to a really nice treatment of infinitesimals, see: F. William Lawvere, Outline of synthetic differential geometry, available at http://www.acsu.buffalo.edu/~wlawvere/downloadlist.html or Anders Kock, Synthetic Differential Geometry, Cambridge U. Press, Cambridge, 1981. But, it's also tempting to embed the commutative ring C[d]/ into the noncommutative ring of nxn complex matrices, by letting d be a slightly off-diagonal matrix, like this: 0 1 0 0 0 0 1 0 (in the case n = 4) 0 0 0 1 0 0 0 0 (Vaughan is considering the case n = 2.) And this is more like how Alain Connes thinks of infinitesimals: as part of the bigger world of noncommutative geometry! Best, jb From rrosebru@mta.ca Thu Apr 29 12:43:22 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 29 Apr 2004 12:43:22 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BJDga-0004ba-00 for categories-list@mta.ca; Thu, 29 Apr 2004 12:42:52 -0300 Date: Thu, 29 Apr 2004 07:02:08 -0700 From: Vaughan Pratt Message-Id: <200404291402.i3TE28ai017713@coraki.Stanford.EDU> To: categories@mta.ca Subject: categories: A situation in search of terminology Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 58 I'm looking for language advice on dealing with the following "St. Ives" problem, as a 2-categorical down-sizing of the 4-categorical original. I have a 2-category CAT^{\pm} (arising from a 2-monad C\pm1 analogous to the monad X+1) that is disconnected in the sense that it is representable as a sum of connected 2-categories. Each summand has homcats that are similarly disconnected, being representable as a sum of connected homcats. If I take a summand 2-category, and from each of its homcats coherently take a summand 1-category, I end up with a 2-category with an initial and a final category serving as respectively the syntax and the semantics of a certain 2-theory (of linearly distributive but not self-dual categories of dually typed objects, but that's another story I'm hoping Myles Tierney will like better than the Chu story). I don't think it's caused by my doing anything wrong--the situation appears to have arisen naturally and I've found no way of making it go away. Has this situation arisen before? If so, what is the proposed terminology for this kind of finality and its associated uniqueness? If not, I'm happy to make up my own conventions, but I don't want to reinvent the wheel here. Vaughan Pratt From rrosebru@mta.ca Mon May 3 05:48:17 2004 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 03 May 2004 05:48:17 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1BKZ2l-0006gt-00 for categories-list@mta.ca; Mon, 03 May 2004 05:43:19 -0300 Date: Fri, 30 Apr 2004 17:37:43 -0400 (EDT) Subject: categories: Categories: Re: Extensions of Z+Z by Z From: "Stephen Urban Chase" To: categories@mta.ca User-Agent: SquirrelMail/1.4.2 MIME-Version: 1.0 Content-Type: text/plain;charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Priority: 3 Importance: Normal Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 59 I've often come across such central extensions when studying various topics in algebra. For reasons which are obvious from the messages of Ronnie Brown and John Baez, I've been calling such extensions "Heisenberg extensions". The general construction is the following: Let A and C be abelian groups, and f:AxA ----> C be bilinear. Then f is a 2-cocycle for the trivial action of A on C, and the corresponding central extension has the form E = CxA with composition law given by the usual formula: (c,a)(c',a') = (c+c'+f(a,a'), a+a'). The classes of such extensions form a subgroup of the group of all classes of central extensions of A by C, but in general is not the whole group. If C is uniquely divisible by 2, then these extensions have the property that they split over every cyclic subgroup of A. The analogous construction for finite group schemes plays a role in certain questions in Galois theory and related matters; see, e.g., my paper, "On a variant of the Witt and Brauer groups", in "Brauer Groups (Evanston 1975)", Springer LNM 549 (pp 148-187). Also, relatively free groups for certain varieties of nilpotent groups of class 2 can be constructed as Heisenberg extensions. In particular, the integral Heisenberg group is the 2-generator relatively free group for the variety of all nilpotent groups of class 2. Steve Chase ---------------------------- Original Message ---------------------------- Subject: categories: Extensions of Z+Z by Z From: "Colin McLarty" Date: Sun, April 25, 2004 10:58 pm To: categories@mta.ca -------------------------------------------------------------------------- After calculating the group extensions of Z+Z by Z, with constant action, I am curious whether the groups have any more natural form than I found. I mean extension of Z+Z by Z in this sense, as a sequence of groups where E need not be commutative: 0 --> Z --> E --> Z+Z --> 0 and the kernel is in the center of E. The form I found is parametrized by the integers this way: For any integer c, the group E_c has triples of integers (i,,j,k) as elements and the multiplication rule is coordinate-wise addition plus an extra bit in the first coordinate. (i,,j,k).(q,r,s) = ( (i+j+c.(kr)), j+r, k+s) When c=0 this is commutative and is just the coproduct Z+Z+Z. In any group E_c, the element (c,0,0) is the commutator of (0,0,1) and (0,1,0). The Baer sum of extensions corresponds to addition of the parameters c as integers. So I understand the group of extensions. Of course I understood it before I calculated it, since it is the second cohomology group of the torus. That is why I tried the algebraic calculation. But is there a natural way to think about each group E_c, for non-zero values of c? Do these groups appear in any other natural way? thanks, colin