From MAILER-DAEMON Mon Mar 31 09:43:14 2003 Date: 31 Mar 2003 09:43:14 -0400 From: Mail System Internal Data Subject: DON'T DELETE THIS MESSAGE -- FOLDER INTERNAL DATA Message-ID: <1049118194@mta.ca> X-IMAP: 1046710820 0000000018 Status: RO This text is part of the internal format of your mail folder, and is not a real message. It is created automatically by the mail system software. If deleted, important folder data will be lost, and it will be re-created with the data reset to initial values. From rrosebru@mta.ca Mon Mar 3 11:52:52 2003 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 03 Mar 2003 11:52:52 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 18ps9t-0004vH-00 for categories-list@mta.ca; Mon, 03 Mar 2003 11:47:17 -0400 Message-ID: <3E6323AE.80107@tzi.de> Date: Mon, 03 Mar 2003 10:43:10 +0100 From: Lutz Schroeder User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.0.1) Gecko/20020903 X-Accept-Language: en-us, en MIME-Version: 1.0 To: categories@mta.ca Subject: categories: Inductive datatypes in toposes References: <20030225195501.74658.qmail@web12001.mail.yahoo.com> <002001c2dd81$55acc1a0$b1e493d9@rmi.acnet.ge> X-Enigmail-Version: 0.63.3.0 X-Enigmail-Supports: pgp-inline, pgp-mime Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: quoted-printable Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 1 Dear categorists, is there a good reference for the construction of inductive datatypes (lists, trees etc.) in a topos with nno (assuming that my guess that such a construction is indeed possible is correct)? Thanks a lot, Lutz Schr=F6der --=20 -------------------------------------------------------------------------= ---- Lutz Schroeder Phone +49-421-218-4683 Dept. of Computer Science Fax +49-421-218-3054 University of Bremen lschrode@informatik.uni-bremen.de P.O.Box 330440, D-28334 Bremen http://www.informatik.uni-bremen.de/~lschrode -------------------------------------------------------------------------= ---- From rrosebru@mta.ca Mon Mar 3 15:56:37 2003 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 03 Mar 2003 15:56:37 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 18pvzi-0002XH-00 for categories-list@mta.ca; Mon, 03 Mar 2003 15:53:02 -0400 Date: Mon, 3 Mar 2003 16:00:50 +0100 (CET) From: "I. Moerdijk" Reply-To: "I. Moerdijk" Subject: categories: master class in noncommutative geometry To: categories@mta.ca MIME-Version: 1.0 Content-Type: TEXT/plain; charset=us-ascii X-Mailer: dtmail 1.3.0 @(#)CDE Version 1.4.2 SunOS 5.8 sun4u sparc Message-Id: <20030303150049.11419520C5@mail.math.uu.nl> X-Virus-Scanned: by AMaViS snapshot-20020300 Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 2 Dear colleagues, during the next academic year, 2003-2004, we will organise a special programme under the general heading of "noncommutative geometry" at Utrecht. The lectures cover a range of topics, including homological algebra, theory of C*-algebras, foliations, and cyclic homology, and are intended for students who would like to enter a PhD programme in the subsequent year. There are some student grants available. If you know of any students who might be interested, would you please direct them to the following web page? http://www.math.uu.nl/mri/education/master_0304.html A brochure containing information on how to apply can be obtained from there. With best regards, Ieke Moerdijk. From rrosebru@mta.ca Mon Mar 3 15:56:37 2003 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 03 Mar 2003 15:56:37 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 18pw0W-0002cF-00 for categories-list@mta.ca; Mon, 03 Mar 2003 15:53:52 -0400 Message-ID: <3E63818A.48AE09CB@labri.fr> Date: Mon, 03 Mar 2003 17:23:38 +0100 From: Luigi Santocanale Organization: LaBRI X-Mailer: Mozilla 4.78 [fr] (X11; U; Linux 2.4.9-31 i686) X-Accept-Language: en MIME-Version: 1.0 To: categories@mta.ca Subject: categories: Re: Inductive datatypes in toposes References: <20030225195501.74658.qmail@web12001.mail.yahoo.com> <002001c2dd81$55acc1a0$b1e493d9@rmi.acnet.ge> <3E6323AE.80107@tzi.de> Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: quoted-printable X-Virus-Scanned: by amavisd-new Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 3 Lutz Schroeder a =E9crit : >=20 > Dear categorists, >=20 > is there a good reference for the construction of inductive datatypes > (lists, trees etc.) in a topos with nno (assuming that my guess that > such a construction is indeed possible is correct)? Here are those I know: =1F @incollection {MR81f:18019, AUTHOR =3D {Johnstone, Peter T. and Wraith, Gavin C.}, TITLE =3D {Algebraic theories in toposes}, BOOKTITLE =3D {Indexed categories and their applications}, SERIES =3D {Lecture Notes in Math.}, VOLUME =3D {661}, PAGES =3D {141--242}, PUBLISHER =3D {Springer}, ADDRESS =3D {Berlin}, YEAR =3D {1978}, MRCLASS =3D {18B25 (18C10)}, MRNUMBER =3D {81f:18019}, } @article {MR48:8597, AUTHOR =3D {Lesaffre, Brigitte}, TITLE =3D {Structures alg\'ebriques dans les topos \'el\'ementaires}= , JOURNAL =3D {C. R. Acad. Sci. Paris S\'er. A-B}, VOLUME =3D {277}, YEAR =3D {1973}, PAGES =3D {A663--A666}, MRCLASS =3D {18C10 (02H10)}, MRNUMBER =3D {48 \#8597}, MRREVIEWER =3D {Andreas Blass}, } For a subtopos structure: @incollection {MR95h:68133, AUTHOR =3D {Jay, C. Barry and Cockett, J. R. B.}, TITLE =3D {Shapely types and shape polymorphism}, BOOKTITLE =3D {Programming languages and systems---ESOP '94 (Edinburgh, 1994)}, SERIES =3D {Lecture Notes in Comput. Sci.}, VOLUME =3D {788}, PAGES =3D {302--316}, PUBLISHER =3D {Springer}, ADDRESS =3D {Berlin}, YEAR =3D {1994}, MRCLASS =3D {68Q65 (68N15)}, MRNUMBER =3D {95h:68133}, } Best, Luigi --=20 Luigi Santocanale http://www.labri.fr/~santocan/ From rrosebru@mta.ca Mon Mar 3 15:57:03 2003 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 03 Mar 2003 15:57:03 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 18pw2K-0002lH-00 for categories-list@mta.ca; Mon, 03 Mar 2003 15:55:44 -0400 From: Thomas Streicher Message-Id: <200303031730.SAA17354@fb04209.mathematik.tu-darmstadt.de> Subject: categories: Re: Inductive datatypes in toposes In-Reply-To: <3E6323AE.80107@tzi.de> from Lutz Schroeder at "Mar 3, 2003 10:43:10 am" To: categories@mta.ca Date: Mon, 3 Mar 2003 18:30:18 +0100 (CET) X-Mailer: ELM [version 2.4ME+ PL66 (25)] MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit X-MailScanner: Found to be clean Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 4 concerning the question > is there a good reference for the construction of inductive datatypes > (lists, trees etc.) in a topos with nno (assuming that my guess that > such a construction is indeed possible is correct)? The situation appears to me as follows. I those toposes where IZF (intuitionistic Zermelo Fraenkel set theory) is available (as e.g. Grothendieck and realizability toposes) business is as usual for functors preserving \omega-colimits: you simply construct mu(F) as colim_{n \in \omega} F^n(0). Notice, however, that there is a tacit appeal to the axiom of replacement when constructing the family (F^n(0))_{n\in\omega}. In general there is no reason why this family should exist. Of course, for the above mentioned examples like lists, trees etc. you can construct such inductive data types because both List(A) and Tree(A) appear as inductively defined subsets of P(\tilde{A}^N) where \tilde{A} is the partial map classifier. The reason is that trees and lists over A can be coded as partial maps from N to A. The point is that toposes (due to their impredicative nature) support inductive definitions of predicates on a type A given in advance. However, they don't support construction of inductively defined types as one cannot define sufficiently many families of types. It is not clear to me to which extent one can characterise those inductive types that can be reduced to inductively defined predicates in HAH. However, one knows that assuming W-types (`a la Martin-Loef) one can reduce most inductive types to W-types in extensional type theory. As far as I understand that's the reason why Moerdijk and Palmgren introduced lccc's with W-types as sort of ``predicative toposes''. Thomas From rrosebru@mta.ca Tue Mar 4 07:58:12 2003 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 04 Mar 2003 07:58:12 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 18qAx3-0001hQ-00 for categories-list@mta.ca; Tue, 04 Mar 2003 07:51:17 -0400 From: Alex Simpson X-Authentication-Warning: topper.inf.ed.ac.uk: apache set sender to als@localhost using -f To: categories@mta.ca Subject: categories: Re: Inductive datatypes in toposes Message-ID: <1046742576.3e640630a95fb@mail.inf.ed.ac.uk> Date: Tue, 04 Mar 2003 01:49:36 +0000 (GMT) References: <200303031730.SAA17354@fb04209.mathematik.tu-darmstadt.de> In-Reply-To: <200303031730.SAA17354@fb04209.mathematik.tu-darmstadt.de> MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit User-Agent: IMP/PHP IMAP webmail program 2.2.8 X-Originating-IP: 130.54.16.90 Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 5 Lutz Schroeder asked: > > is there a good reference for the construction of inductive > datatypes > > (lists, trees etc.) in a topos with nno (assuming that my guess that > > such a construction is indeed possible is correct)? Thomas Streicher replied: > It is not clear to me to which extent one can characterise those > inductive > types that can be reduced to inductively defined predicates in HAH. > However, one knows that assuming W-types (`a la Martin-Loef) one can > reduce > most inductive types to W-types in extensional type theory. As far as > I > understand that's the reason why Moerdijk and Palmgren introduced lccc's > with > W-types as sort of ``predicative toposes''. Just to point out that "assuming W-types" here is no extra assumption. Moerdijk and Palmgren observe that every elementary topos with nno has W-types. This observation more than answers Schroeder's original question affirmatively. See Moerdijk and Palmgren, "Well-founded trees in categories", APAL 104, 2000, for the observation. I'm not sure whether they include the details (I don't have the paper to hand), but it's not a hard exercise. Alex Simpson Alex Simpson, LFCS, Division of Informatics, Univ. of Edinburgh Email: Alex.Simpson@ed.ac.uk Tel: +44 (0)131 650 5113 Web: http://www.dcs.ed.ac.uk/home/als Fax: +44 (0)131 667 7209 From rrosebru@mta.ca Tue Mar 4 18:36:54 2003 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 04 Mar 2003 18:36:54 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 18qKwF-0005lt-00 for categories-list@mta.ca; Tue, 04 Mar 2003 18:31:07 -0400 From: Thomas Streicher Message-Id: <200303041644.RAA25697@fb04305.mathematik.tu-darmstadt.de> Subject: categories: W-types in toposes To: categories@mta.ca Date: Tue, 4 Mar 2003 17:44:17 +0100 (CET) X-Mailer: ELM [version 2.4ME+ PL66 (25)] MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit X-MailScanner: Found to be clean Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 6 Alex S. pointed out quite correctly that toposes with NNO allow one to construct W-types Wx:A.B(x) for all b : B -> A (where B(x) is a shorthand for b^{-1}(x)). The idea is as follows: elements of Wx:A.B(x) are thought of as well-founded terms over the signature A where B(a) is the arity of operation with name a. Thus, possibly infinite terms over this signature can be coded up as partial maps t : List(B) \parr A satisfying the conditions (i) the domain of t is prefix closed (ii) if t(s) is defined and equal a then t(s^y) is defined iff and only if y \in B(a) The term t is ``reachable'' iff dom(t) is an element of the least subset T_B of P(List(B)) satisfying the closure conditions - {<>} in T_B - if a \in A and f : B(a) -> T_B then {<>} \cup { b^s | b \in B(a) & s \in f(b) } Notice that ``reachable'' is more restrictive than well-founded in a constructive setting. Claiming that "well-founded entails reachable" is known as "bar induction". Generally, W-types capture inductive types which are of the type "free term algebra" albeit for very general signatures as given by a family of types. It certainly contains all and more than what one thinks of in C.S. usually when using the word inductive type. However, necessarily "inductive type" is an "open" notion and heavily syntax-dependent. There is the categorical generalization of inductive type as initial fixpoint of a covariant functor F : EE->EE where EE is the ambient topos or model of type theory. In a sense this a vacuous notion as you can get every type A as initial fixpoint of F(X)=A. On the other hand, even in Set not every covariant functor F : Set->Set needs to have a fixpoint (e.g. if F is the covariant powerset functor). However, sometimes in categories different from Set functor of the form F(X) = S^(S^X) do have fixpoints for particular nontrivial S (for Sierpinski space). The reason why I mentioned axiom of replacement is that in the business of solving recursive domain equations the axiom of relacement is needed (see Alex Simpson's paper from LICS02). But in any case for constructing free term algebras we don't need it. Nevertheless, there is still a nagging question about the relationship between inductive predicates and inductive types. Can one characterise those syntactically given covaraint functors F (constructed, say, from parameters using sum, cartesian product and exponentiation) for which HAH proves the existence of a fixpoint, in other words which inductive types are ensured by higher order arithmetic? Thomas S. From rrosebru@mta.ca Thu Mar 6 15:10:11 2003 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 06 Mar 2003 15:10:11 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 18r0ed-00001v-00 for categories-list@mta.ca; Thu, 06 Mar 2003 15:03:43 -0400 To: categories@mta.ca Subject: categories: BCTCS 19 X-Mailer: mh-e 6.1; nmh 1.0.4+dev; Emacs 21.2 Date: Thu, 06 Mar 2003 14:41:34 +0000 From: N Ghani Message-Id: Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 7 **** **** Please can you publicise this amongst your colleagues and particularly PhD students who could take advantage of our grants for accommodation etc +---------------------------------------------------------------------+ CALL FOR PARTICIPATION British Colloquium on Theoretical Computer Science 7th - 9th April 2003 Leicester, United Kingdom http://www.mcs.le.ac.uk/events/bctcs19/ The British Colloquium for Theoretical Computer Science (BCTCS) is an annual conference providing a forum for research in all areas of theoretical computer science. As such, it aims to provide an informal setting within which researchers can meet and discuss recent developments and results in the broad swathe of the subject rather than in just their own area of specialty. The BCTCS is also dedicated to the development and training of postgraduate research students. Indeed, the relaxed nature of the conference provides an excellent environment where postgraduate students may gain the experience of presenting their work to their colleagues and benefit from contact with established researchers in the community. A number of grants are available to fund the accommodation and registration costs of postgraduate students who are willing to give talks. This year, we are pleased to have invited talks in the areas of programming language semantics, category theory, algorithms, formal languages and automata theory given by Prof A. Jung, University of Birmingham, UK Prof F.W. Lawvere, State University of New York, USA Prof K. Mehlhorn, Universitaet des Saarlandes, Germany Dr S. Muthukrishnan, Rutgers University, USA and AT&T Prof. J. Pin, Universite Paris Denis Diderot et CNRS, France Further details of the program etc will be available from the website http://www.mcs.le.ac.uk/events/bctcs19/ and registration, travel, costs etc can be found at http://www.le.ac.uk/conference/bctcs/ For any other issues, please contact bctcs19@mcs.le.ac.uk Neil Ghani Dr Conference Organiser +---------------------------------------------------------------------+ | Dr Neil Ghani Email : ng13@mcs.le.ac.uk | | Dept of Maths and Computer Science Web : www.mcs.le.ac.uk/~ng13 | | University of Leicester | | University Rd, | | Leicester LE1 7RH Phone : +44 (0)116 252 3807 | | United Kingdom Fax : +44 (0)116 252 3915 | +---------------------------------------------------------------------+ From rrosebru@mta.ca Mon Mar 10 11:45:24 2003 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 10 Mar 2003 11:45:24 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 18sPJg-0001Ix-00 for categories-list@mta.ca; Mon, 10 Mar 2003 11:35:52 -0400 To: categories@mta.ca Subject: categories: Sets for Mathematics, new book available Date: Sun, 09 Mar 2003 21:00:01 -0500 From: wlawvere@buffalo.edu Message-ID: <1047261601.3e6bf1a1a5d1c@mail2.buffalo.edu> X-Mailer: University at Buffalo WebMail Cyrusoft SilkyMail v1.1.10 24-Janua= Status: RO X-Status: X-Keywords: X-UID: 8 The book SETS FOR MATHEMATICS by F.W. Lawvere and R.Rosebrugh which is listed in the Cambridge University Press catalogue, is finally actually available. The main text is based on courses given several times at Buffalo and Sackville for third-year students of mathematics, computer science, and other mathematical sciences. Although more advanced than the book Conceptual Mathematics by Lawvere and Schanuel (which is aimed at total beginners) this text develops from scratch the theory of the category of abstract sets and certain other toposes with examples from elementary algebra, differential equations, and automata theory. Among the reasons offered in the appendix for developing an explicit foundation is the need to have a basis for studying such works as Eilenberg-Steenrod on algebraic topology and Grothendieck on functional analysis and algebraic geometry. Indeed, the appendix lays down a challenging definition of "foundation" which the book itself can only begin to fulfill. The basic concepts are treated with detailed explanations and with many examples, both in the text and in exercises. After the basics are available, some old topics can be treated in a unifying contemporary spirit, for example (1) The standard tools for analyzing an arbitrary map are the induced equivalence relation, co-equivalence relation, graph and cograph (cographs have been very frequently pictured in practice but only rarely recognized explicitly); all four of these are shown to arise inevitably as Kan quantifications, along the two possible interpretations of the generic map as half of the splitting of a generic idempotent. (2) The so-called "measurable" cardinals can be excluded from a topos by the intuitive demand that space and quantity have a good duality, made explicit =E0 la Isbell via the requirement that there is a fixed automaton such that the monad obtained by double-dualizing into it is the identity. The authors hope that this work will serve as one of the springboards to the development and teaching of a foundation suitable for twenty-first century mathematics. Meanwhile the suggestions, criticisms and corrections that colleagues may offer are eagerly awaited. Corrections will be posted on the book home page at http://www.mta.ca/~rrosebru/setsformath From rrosebru@mta.ca Tue Mar 11 14:16:17 2003 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 11 Mar 2003 14:16:17 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 18soBR-00028Q-00 for categories-list@mta.ca; Tue, 11 Mar 2003 14:09:01 -0400 Date: Mon, 10 Mar 2003 15:02:55 GMT From: Jeremy Gibbons To: categories@mta.ca Subject: categories: jobs: Postdoc & PhD positions in Datatype-Generic programming Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 9 [We apologize if you receive multiple copies of this announcement.] Postdoctoral research fellow (University of Nottingham) Doctoral studentship (University of Oxford) in DATATYPE-GENERIC PROGRAMMING The Universities of Nottingham and Oxford have positions available to work on an EPSRC-supported project entitled "Datatype-Generic Programming", running for three years and starting on or shortly after 1st August 2003. There is a postdoctoral research fellowship at Nottingham, and a DPhil studentship at Oxford. The project is to develop a novel mechanism for parametrizing programs, namely parametrization by a datatype or type constructor. The mechanism is related to parametric polymorphism, but of higher order. We aim to develop a calculus for constructing datatype-generic programs, with the ultimate goal of improving the state of the art in generic object-oriented programming, as occurs for example in the C++ Standard Template Library. Further details of the project can be obtained from the contacts listed below. Applicants for the postdoctoral fellowship should have completed (or be about to complete) a PhD degree. Preference will be given to applicants with an excellent knowledge of the calculational style of reasoning. Expertise in functional programming, object-oriented programming and the mathematics of program construction is required. Send a detailed curriculum vitae and the names and addresses of two referees to Professor Roland Backhouse, School of Computer Science and Information Technology, University of Nottingham, Jubilee Campus, Wollaton Road, Nottingham NG8 1BB, UK, rcb@cs.nott.ac.uk, www.cs.nott.ac.uk/~rcb, from whom further details can also be obtained. Electronic applications should be sent in PDF format; other formats will not be accepted. The ideal applicant for the DPhil studentship would have (or be about to obtain) a first- or upper-second class honours degree or equivalent in computer science, with expertise in functional programming, object-oriented programming and the mathematics of program construction. The studentship pays for all university and college fees, in addition to the standard EPSRC maintenance grant. Applicants should follow the procedure described at www.comlab.ox.ac.uk/oucl/courses/grad02-03/dphil/requirements.html, but should also mention this position in the application. For further details contact Dr Jeremy Gibbons, Oxford University Computing Laboratory, Wolfson Building, Parks Road, Oxford OX1 3QD, UK, jeremy.gibbons@comlab.ox.ac.uk, www.comlab.ox.ac.uk/oucl/people/jeremy.gibbons.html. The closing date for applications for both positions is Monday 14th April 2003. Roland Backhouse Jeremy Gibbons -- Jeremy.Gibbons@comlab.ox.ac.uk Oxford University Computing Laboratory, TEL: +44 1865 283508 Wolfson Building, Parks Road, FAX: +44 1865 273839 Oxford OX1 3QD, UK. URL: http://www.comlab.ox.ac.uk/oucl/people/jeremy.gibbons.html From rrosebru@mta.ca Mon Mar 17 11:18:29 2003 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 17 Mar 2003 11:18:29 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 18uwHp-0006QA-00 for categories-list@mta.ca; Mon, 17 Mar 2003 11:12:25 -0400 Message-ID: <3E75DFCF.30607@cs.mcgill.ca> Date: Mon, 17 Mar 2003 09:46:39 -0500 From: Prakash PANANGADEN Organization: McGill University Computer Science Dept. User-Agent: Mozilla/5.0 (X11; U; FreeBSD i386; en-US; rv:1.0.0) Gecko/20020911 X-Accept-Language: en-us, en MIME-Version: 1.0 To: categories@mta.ca Subject: categories: MFPS Call for participation Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: quoted-printable Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 10 You are invited to participate in the 19th Mathematical Foundations of=20 Programming Semantics held at the Centre de Recherche of Universit=E9 de=20 Montreal from Wednesday March 19th 2:00 pm to Saturday 22nd March 6pm.=20 The registration fees are $100 (CAN $160) for regular participants and $50 (CAN $ 80) for=20 students. Details of the programme, registration information and other details may=20 be found at http://www.crm.umontreal.ca/MFPS03 The general announcement for MFPS may be found at: http://www.math.tulane.edu/~mfps/mfps19.htm --=20 Prakash Panangaden = =20 School of Computer Science McGill University prakash@cs.mcgill.ca = =20 From rrosebru@mta.ca Thu Mar 20 09:56:17 2003 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 20 Mar 2003 09:56:17 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 18w0Pu-0004gc-00 for categories-list@mta.ca; Thu, 20 Mar 2003 09:49:10 -0400 Message-ID: From: icalp2003@TUE.nl To: categories@mta.ca Subject: categories: list accepted papers for ICALP 2003 Date: Wed, 19 Mar 2003 14:36:56 +0100 X-Message-Flag: Follow up MIME-Version: 1.0 X-Mailer: Internet Mail Service (5.5.2656.59) Content-Type: text/plain; Status: RO X-Status: X-Keywords: X-UID: 11 =09charset=3D"iso-8859-1" Sender: cat-dist@mta.ca Precedence: bulk ------------------------------------------------------------------------- We apologize for the reception of multiple copies of this message. ---------------------------------------------------------------------------= - ---------------------------- =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D List of papers accepted for ICALP'2003, Track A and Track B Eindhoven, The Netherlands, June 30 - July 4, 2003 http://www.win.tue.nl/icalp2003/ =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D Vincent Blondel, Paul Van Dooren Similarity matrices for pairs of graphs Arnold Schoenhage Adaptive raising strategies optimizing relative efficiency Sergei Bespamyatnikh, Michael Segal Dynamic algorithms for approximating interdistances Amos Korman, David Peleg Labeling schemes for dynamic tree networks Geraud Senizergues The equivalence problem for t-turn DPDA is co-NP John Hitchcock, Jack Lutz, Elvira Mayordomo Scaled dimension and nonuniform complexity Yossi Matias, Ely Porat Efficient pebbling for list traversal synopses Alexander Ageev, Yinyu Ye, Jiawei Zhang Improved combinatorial approximation algorithms for the k-level facility location problem Markus Blaeser An improved approximation algorithm for the asymmetric TSP with strengthene= d triangle inequality Susanne Albers, Rob van Stee A study of integrated document and connection caching Amihood Amir, Yonatan Aumann, Richard Cole, Moshe Lewenstein, Ely Porat Function matching: algorithms, applications, and a lower bound Eyal Even-Dar, Alex Kesselman, Yishay Mansour Convergence time to Nash equilibria Amin Coja-Oghlan, Cristopher Moore, Vishal Sanwalani MAX k-CUT and approximating the chromatic number of random graphs Jiri Fiala, Daniel Paulusma The computational complexity of the role assignment problem Vipul Bansal, Aseem Agrawal, Varun Malhotra Stable marriages with multiple partners: efficient search for an optimal solution Juraj Hromkovic, Georg Schnitger Pushdown automata and multicounter machines, a comparison of computation mode Jens Jaegerskuepper Analysis of a simple evolutionary algorithm for minimization in Euclidean spaces Noam Berger, Bela Bollobas, Christian Borgs, Jennifer Chayes, Oliver Riorda= n Degree distribution of the FKP network model Luisa Gargano, Mikael Hammar There are spanning spiders in dense graphs (and we know how to find them) Annalisa De Bonis, Leszek Gasieniec, Ugo Vaccaro Generalized framework for selectors with applications in optimal group testing Michael Elkin, Guy Kortsarz Approximation algorithm for the directed telephone multicast problem Sanjeev Arora, Kevin Chang Approximation schemes for degree-restricted MST and red-blue separation problem Surender Baswana, Sandeep Sen A simple linear time algorithm for computing a (2k-1)-Spanner of O(n^{1+1/k}) size in weighted graphs Chandra Chekuri, Marcelo Mydlarz, Bruce Shepherd Multicommodity demand flow in a tree Randeep Bhatia, Julia Chuzhoy, Ari Freund, Joseph Naor Algorithmic aspects of bandwidth trading Chandra Chekuri, Sudipto Guha, Joseph Naor Approximating Steiner k-cuts Endre Boros, Khaled Elbassioni, Vladimir Gurvich, Leonid Khachiyan, Kazuhis= a Makino An intersection inequality for discrete distributions and related generatio= n problems Erik Demaine, Fedor Fomin, MohammadTaghi Hajiaghayi, Dimitrios Thilikos Fixed-parameter algorithms for the (k,r)-center in planar graphs and map graphs Gianni Franceschini, Roberto Grossi Optimal cache-oblivious implicit dictionaries Anna Gal, Peter Bro Miltersen The cell probe complexity of succinct data structures, Alex Hall, Steffen Hippler, Martin Skutella Multicommodity flows over time: efficient algorithms and complexity Rene Sitters, Leen Stougie, Willem Paepe A competitive algorithm for the general 2-server problem Luis Antunes, Lance Fortnow Sophistication revisited Peter Hoyer, Michele Mosca, Ronald de Wolf Quantum search on bounded-error inputs Dimitris Fotakis On the competitive ratio for online facility location Satoshi Ikeda, Izumi Izumi Kubo, Norihiro Okumoto, Masafumi Yamashita Impact of local topological information on random walks on finite graphs Pilu Crescenzi, Giorgio Gambosi, Gaia Nicosia, Paolo Penna, Walter Unger On-line load balancing made simple: greedy strikes back Seffi Naor, Hadas Shachnai, Tami Tamir Real-time scheduling with a budget Mark Cieliebak, Paola Flocchini, Giuseppe Prencipe, Nicola Santoro Solving the robots gathering problem Rainer Feldmann, Martin Gairing, Thomas Luecking, Burkhard Monien, Manuel Rode Nashification and the coordination ratio for a selfish routing game Brian Dean, Michel Goemans Improved approximation algorithms for minimum-space advertisement schedulin= g Baruch Awerbuch, Andre Brinkmann, Christian Scheideler Anycasting in adversarial systems: routing and admission control Jianer Chen, Iyad Kanj, Ljubomir Perkovic, Eric Sedgwick, Ge Xia Genus characterizes the complexity of graph problems: some tight results Markus Holzer, Martin Kutrib Flip-pushdown automata: k+1 pushdown reversals are better than k Manuel Bodirsky, Clemens Gr=F6pl, Mihyun Kang Generating labeled planar graphs uniformly at random Rajiv Gandhi, Eran Halperin, Samir Khuller, Guy Kortsarz, Aravind Srinivasa= n An improved approximation algorithm for vertex cover with hard capacities Dominique Poulalhon, Gilles Schaeffer Optimal coding and sampling of triangulations Ian Munro, Rajeev Raman, Venkatesh Raman, Srinivasa Rao Satti Succinct representations of permutations Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen A direct sum theorem in communication complexity via message compression Rajeev Raman, Srinivasa Rao Succinct dynamic dictionaries and trees Daniel Bleichenbacher, Aggelos Kiayias, Moti Yung Decoding of interleaved Reed Solomon codes over noisy data, Juha K=E4rkk=E4inen, Peter Sanders Simple linear work suffix array construction Manfred Droste, Dietrich Kuske Skew and infinitary formal power series Ernst-Erich Doberkat Semi-pullbacks and bisimulations in categories of stochastic relations Stefan Blom, Wan Fokkink, Sumit Nain On the axiomatizability of ready traces, ready simulation and failure trace= s Juraj Hromkovic, Georg Schnitger Nondeterminisn versus determinism for two-way finite automata: generalizations of Sipser's separation Daniele Gorla, Rosario Pugliese Resource access and mobility control with dynamic privileges acquisition Jan Johannsen, Martin Lange CTL+ is complete for double exponential time Davide Ancona, Sonia Fagorzi, Eugenio Moggi, Elena Zucca Mixin modules and computational effects Thierry Cachat Higher order pushdown automata, the Caucal hierarchy of graphs and parity games Gaoyan Xie, Zhe Dang, Oscar Ibarra A solvable class of quadratic Diophantine equations with applications to verification of infinite state systems Alexander Okhotin Decision problems for language equations with Boolean operations Roberto Bruni, Jose Meseguer Generalized rewrite theories Salvatore La Torre, Margherita Napoli, Mimmo Parente, Gennaro Parlato Hierarchical and recursive state machines with context-dependent properties Cindy Eisner, Dana Fisman, John Havlicek, Anthony McIsaac, David Van Campenhout The definition of a temporal clock operator Nadia Busi, Maurizio Gabbrielli, Gianluigi Zavattaro Replication vs. recursive definitions in channel based calculi Richard Mayr Undecidability of weak bisimulation equivalence for 1-counter processes Felix Klaedtke, Harald Ruess Monadic second-order logics with cardinalities Orna Kupferman, Moshe Vardi Pi_2 intersected Sigma_2 equals AFMC Alexander Rabinovich Quantitative analysis of probabilistic lossy channel systems Massimo Merro, Francesco Zappa Nardelli Bisimulation proof methods for mobile ambients Tatiana Rybina, Andrei Voronkov Upper bounds for a theory of queues Zena Ariola, Hugo Herbelin Minimal classical logic and control operators Arnaud Carayol, Thomas Colcombet On equivalent representations of infinite structures Philippe Schnoebelen Oracle circuits for branching-time model checking Luca de Alfaro, Thomas A. Henzinger, Rupak Majumdar Discounting the future in systems theory Thomas Henzinger, Ranjit Jhala, Rupak Majumdar Counterexample guided control Jo Hannay Axiomatic criteria for quotients and subobjects for higher-order data types Francois Denis, Yann Esposito Residual languages and probabilistic automata Francisco Gutierrez, Blas Ruiz Expansion postponement via cut elimination in sequent calculi for pure type systems Michele Bugliesi, Silvia Crafa, Amela Prelic, Vladimiro Sassone Secrecy in untrusted networks Luca de Alfaro, Marco Faella Information flow in concurrent games Marielle Stoelinga , Frits Vaandrager A testing scenario for probabilistic automata Arkadev Chattopadhyay, Denis Therien Locally commutative categories =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D From rrosebru@mta.ca Fri Mar 21 11:33:36 2003 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 21 Mar 2003 11:33:36 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 18wOOg-0004lz-00 for categories-list@mta.ca; Fri, 21 Mar 2003 11:25:30 -0400 Date: Wed, 19 Mar 2003 20:26:56 -0800 (PST) From: Galchin Vasili Subject: categories: Alexandrov topology and Scott topology To: categories@mta.ca 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: 12 Hello, A common example of a Heyting Algebra is one defined on an arbitrary topology. In the cases of an Alexandrov topology and a Scott topology, are either of these Boolean Algebras (special case of a HA) or purely Heyting Algebras? Regards, Bill Halchin From rrosebru@mta.ca Sat Mar 22 16:28:39 2003 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 22 Mar 2003 16:28:39 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 18wpUl-0002f7-00 for categories-list@mta.ca; Sat, 22 Mar 2003 16:21:35 -0400 From: "C.F.Townsend" To: "'categories@mta.ca'" Subject: categories: Prime Ideal Theorem implies Excluded Middle? Date: Sat, 22 Mar 2003 14:39:08 -0000 MIME-Version: 1.0 X-Mailer: Internet Mail Service (5.5.2448.0) Content-Type: text/plain; charset="iso-8859-1" Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 13 Dear all, does anyone know a reference for the question: Prime Ideal Theorem implies the Excluded Middle ? Certainly, Axiom of Choice implies Excluded Middle, but I have convinced myself that the weaker statement is true and would be grateful for any pointers. Regards, Christopher Townsend PS there are definitely formulations of the PIT that do not use negation. E.g. it is equivalent to the statement that for every Boolean alg. B if x in B has the property that f(x)=0 for every Boolean alg. homomorphism f:B->Omega, then x=0. From rrosebru@mta.ca Sat Mar 22 17:35:11 2003 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 22 Mar 2003 17:35:11 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 18wqcR-0007Pc-00 for categories-list@mta.ca; Sat, 22 Mar 2003 17:33:35 -0400 From: "Prof. Peter Johnstone" To: categories Subject: categories: Re: Prime Ideal Theorem implies Excluded Middle? In-Reply-To: Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Scanner: exiscan for exim4 (http://duncanthrax.net/exiscan/) *18wqVj-0002Q7-00*b.ZHBlOdy.g* Sender: cat-dist@mta.ca Precedence: bulk Date: Sat, 22 Mar 2003 17:33:35 -0400 Status: RO X-Status: X-Keywords: X-UID: 14 On Sat, 22 Mar 2003, C.F.Townsend wrote: > Dear all, does anyone know a reference for the question: > > Prime Ideal Theorem implies the Excluded Middle ? > My paper "Another condition equivalent to De Morgan's Law" (Commun Alg. 7 (1979), 1309-1312) shows that the statement "Every maximal ideal is prime" for distributive lattices (or for Boolean algebras) is equivalent to De Morgan's law. In a localic Set-topos (assuming AC in Set) the Maximal Ideal Theorem holds; hence in the topos of sheaves on an extremally disconnected locale the Prime Ideal Theorem holds (cf. Elephant, D4.6.15). But such a topos needn't be Boolean. Peter Johnstone From rrosebru@mta.ca Mon Mar 24 12:10:31 2003 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 24 Mar 2003 12:10:31 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 18xUPf-0002ID-00 for categories-list@mta.ca; Mon, 24 Mar 2003 12:03:03 -0400 Date: Mon, 24 Mar 2003 11:38:13 +0100 (CET) From: Benno van den Berg Reply-To: Benno van den Berg Subject: categories: Peripatetic Seminar on Sheaves and Logic To: categories@mta.ca MIME-Version: 1.0 Content-Type: TEXT/plain; charset=us-ascii Content-MD5: BewHqF+XLZZOrmtZR8iX5g== X-Mailer: dtmail 1.3.0 @(#)CDE Version 1.4.2 SunOS 5.8 sun4u sparc Message-Id: <20030324103812.C1803520C5@mail.math.uu.nl> Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 15 Dear all, A PSSL will be organized by the University of Utrecht (in the Netherlands) in the weekend of the 28th and 29th of June. I will launch a webpage where the necessary information can be found. You will be informed as soon as it is finished. With best regards, Benno -- Benno van den Berg - Mathematisch Instituut, UU vdberg@math.uu.nl - P.O.box 80.010, 3508 TA Utrecht, NL From rrosebru@mta.ca Wed Mar 26 10:50:43 2003 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 26 Mar 2003 10:50:43 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 18yCA1-0001fa-00 for categories-list@mta.ca; Wed, 26 Mar 2003 10:45:49 -0400 Message-ID: <3E808ED6.6A831058@cmi.univ-mrs.fr> Date: Tue, 25 Mar 2003 18:16:06 +0100 From: Organization: Laboratoire d'Informatique Fondamentale de Marseille X-Mailer: Mozilla 4.78 [fr] (X11; U; Linux 2.4.8-34.1mdk i686) X-Accept-Language: en MIME-Version: 1.0 To: categories@mta.ca Subject: categories: CONCUR 2003 - Call for papers - Marseille, France Content-Type: text/plain; charset=iso-8859-1 X-MailScanner: Found to be clean Content-Transfer-Encoding: quoted-printable X-MIME-Autoconverted: from 8bit to quoted-printable by gyptis.univ-mrs.fr id h2PHXB013862 Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: X-Keywords: X-UID: 16 We apologize if you receive multiple copies of this message. ********************************************************** ********************************************************** *** *** *** CONCUR 2003 *** *** *** *** September, 3-5, 2003 *** *** Marseille, France *** *** *** *** CALL FOR PAPERS *** *** *** ********************************************************** ********************************************************** CONCUR 2003, the 14th international conference on concurrency theory, is organized by the Laboratoire d'Informatique Fondamentale de Marseille (LI= F). The purpose of the CONCUR conferences is to bring together researchers, developers and students in order to advance the theory of concurrency, an= d promote its applications. Interest in this topic is continuously growing,= as a consequence of the importance and ubiquity of concurrent systems and th= eir applications, and of the scientific relevance of their foundations.=20 Submissions are solicited in all areas of semantics, logics and verificat= ion techniques for concurrent systems. Principal topics include (but are not limited to): - Basic models and logics of concurrent and distributed computation (such as process algebras, Petri nets, domain theoretic or game theoretic models, modal and temporal logics).=20 - Specialized or enriched models (such as circuits, synchronous systems, real time and hybrid systems, stochastic systems, data bases, mobile and migrating systems, parametric protocols, security protocols).=20 - Related verification techniques and tools (such as state-space exploration, model-checking, synthesis, abstraction, automated deduction, testing).=20 - Related programming models (such as distributed, constraints or object oriented, graph rewriting, as well as associated type syste= ms, static analyses, abstract machines, and environments).=20 Authors are invited to submit an extended abstract not exceeding 15 pages electronically via the web submission form at the conference's web site. Submissions will be evaluated by the program committee for inclusion in t= he proceedings, which will be published by Springer-Verlag in the Lecture No= tes in Computer Science series. Papers must contain original contributions, be c= learly written, and include appropriate reference to and comparison with related= work. Simultaneous submissions to other conferences are not allowed.=20 Important dates=20 Submission: April 4, 2003 --> There will be no deadline extension. Notification: May 26, 2003=20 Final version: June 10, 2003=20 Workshops: September 2,6, and 7, 2003=20 Program committee=20 Roberto Amadio, chair (Marseille) Denis Lugiez, co-chair (Marseil= le)=20 David Basin (Zurich) Madhavan Mukund (Chennai)=20 Julian Bradfield (Edinburgh) Doron Peled (Austin)=20 Witold Charatonik (Wroclaw) Jean-Fran=E7ois Raskin (Brussel= s)=20 Alessandro Cimatti (Trento) Roberto Segala (Verona)=20 Philippa Gardner (London) Eugene Stark (Stony-Brook)=20 Patrice Godefroid (Murray-Hill) Peter Van Roy (Louvain-la-Neuve= )=20 Holger Hermanns (Twente) Thomas Wilke (Kiel)=20 Naoki Kobayashi (Tokyo) Glynn Winskel (Cambridge)=20 Kim Larsen (Aalborg)=20 Invited speakers=20 Albert Benveniste (Rennes) Nancy Lynch (Boston)=20 Luca De Alfaro (Santa-Cruz) Andre Scedrov (Philadelphia)=20 More informations available at the conference's web site http://concur03.univ-mrs.fr From rrosebru@mta.ca Sun Mar 30 15:36:57 2003 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 30 Mar 2003 15:36:57 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 18ziUa-0002fl-00 for categories-list@mta.ca; Sun, 30 Mar 2003 15:29:20 -0400 Date: Fri, 28 Mar 2003 15:48:27 -0500 (EST) From: Peter Freyd Message-Id: <200303282048.h2SKmRVN022142@saul.cis.upenn.edu> To: categories@mta.ca Subject: categories: categorist makes good? Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 17 Copyright 2003 Vietnam News Briefs Vietnam News Briefs March 28, 2003 LENGTH: 95 words HEADLINE: SOCIAL & CULTURAL ISSUES: FEMALE VIETNAMESE SCIENTISTS RECEIVE FRENCH ORDER BODY: The French Government has awarded the French Order of Academic Palms to two Vietnamese scientists, Le Hong Sam and Hoang Xuan Sinh, for their contributions to boosting cooperation in culture and science between the two nations. Ms Sam is a researcher on French literature and currently works for the National University of Social Sciences & Humanities in Hanoi. Ms Sinh, a mathematician, is the principal of the Thang Long Open University in Hanoi. The presentation ceremony was held at the French Embassy in Hanoi on March 25. ********************************************************************** Her papers, as adapted from MathSciNet: Hoang Xuan Sinh Gr-categories strictes. (French) Acta Math. Vietnam. 3 (1978), no. 2, 47--59. 18D10 (20J05 20L10) A Gr-category is a groupoid P which is a monoidal category with product and unit such that each object X of P has an inverse (X', t, p), where t:X'*X -> 1 and p:X*X' -> 1. It is called a strict Gr-category if it is a strict monoidal category and t and p are identities for every X. The main theorem of this paper states that every Gr-category is Gr-equivalent to a strict Gr-category...The proof of this theorem uses a result of the author's thesis at the University of Paris VII, 1975 which is that every Gr-category P is determined up to a Gr-equivalence by two groups...As an application of the results of this paper, the author proves Lemma 9.1 of S. Eilenberg and S. Mac Lane [Ann. of Math. (2) 48 (1947), 326--341; MR 9, 7] on the realization of a 3-cocycle as the obstruction of a problem of extension. Reviewed by J. L. Williams Hoang Xuan Sinh Categories de Picard restreintes. (French) [Restricted Picard categories] Acta Math. Vietnam. 7 (1982), no. 1, 117--122 (1983). 18E99 >From the text: "A Picard category is a Gr-category equipped with a commutativity constraint compatible with its associativity constraint. A Picard category P is said to be restricted if its commutativity constraint c satisfies c_{x,x}= identity for all objects x. We represent every Picard category by a complex of chains and we deduce that the classification of restricted prefastened (`preepinglees') Picard categories of type (M,N) is trivial." From rrosebru@mta.ca Sun Mar 30 15:36:57 2003 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 30 Mar 2003 15:36:57 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 18ziY5-0002rD-00 for categories-list@mta.ca; Sun, 30 Mar 2003 15:32:57 -0400 Date: Sat, 29 Mar 2003 17:34:26 -0500 (EST) From: F W Lawvere X-Sender: wlawvere@hercules.acsu.buffalo.edu Reply-To: wlawvere@acsu.buffalo.edu To: categories@mta.ca Subject: categories: Grothendieck's 1973 Buffalo Colloquium 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: 18 Thierry Coquand recently asked me > In your "Comments on the Development of Topos Theory" you refer > to a simpler alternative definition of "scheme" due to Grothendieck. > Is this definition available at some place?? Otherwise, it it possible > to describe shortly the main idea of this alternative definition?? Since several people have asked the same question over the years, I prepared the following summary which, I hope, will be of general interest: The 1973 Buffalo Colloquium talk by Alexander Grothendieck had as its main theme that the 1960 definition of scheme (which had required as a prerequisite the baggage of prime ideals and the spectral space, sheaves of local rings, coverings and patchings, etc.), should be abandoned AS the FUNDAMENTAL one and replaced by the simple idea of a good functor from rings to sets. The needed restrictions could be more intuitively and more geometrically stated directly in terms of the topos of such functors, and of course the ingredients from the "baggage" could be extracted when needed as auxiliary explanations of already existing objects, rather than being carried always as core elements of the very definition. Thus his definition is essentially well-known, and indeed is mentioned in such texts as Demazure-Gabriel, Waterhouse, and Eisenbud; but it is not carried through to the end, resulting in more complication, rather than less. I myself had learned the functorial point of view from Gabriel in 1966 at the Strasbourg-Heidelberg-Oberwolfach seminar and therefore I was particularly gratified when I heard Grothendieck so emphatically urging that it should replace the one previously expounded by Dieudonne' and himself. He repeated several times that points are not mere points, but carry Galois group actions. I regard this as a part of the content of his opinion (expressed to me in 1989) that the notion of topos was among his most important contributions. A more general expression of that content, I believe, is that a generalized "gros" topos can be a better approximation to geometric intuition than a category of topological spaces, so that the latter should be relegated to an auxiliary position rather than being routinely considered as "the" default notion of cohesive space. (This is independent of the use of localic toposes, a special kind of petit which represents only a minor modification of the traditional view and not even any modification in the algebraic geometry context due to coherence). It is perhaps a reluctance to accept this overthrow that explains the situation 30 years later, when Grothendieck's simplification is still not widely considered to be elementary and "basic". To recall some well-known ingredients, let A be the category of finitely-presented commutative algebras over k (or a larger category closed under the symmetric algebra functor, for some purposes). Then the underlying set functor R on A serves as the "line", and any system of polynomial equations with coefficients in k determines also a functor (sub space of Rn) in the well-known way; in fact, the idea of spec is simply identified with the Yoneda embedding of A^op. For example, R has a subfunctor U of invertible elements and another U' such that U'(A) = {f|f in A, 1/1-f in A}. The Grothendieck topology for which U and U' together cover R yields a subtopos Z known as the gros Zariski topos, which turns out to be the classifying topos for local k-algebras in any topos. This Z contains all algebraic schemes over k, but also function spaces Y^X and distribution spaces Hom(R^X,R) for all X,Y in Z. A basic open subspace of any space X is determined as the pullback U sub f of U under any map f: X-->R. One has obviously U sub f intersection U sub g = U sub fg and the intrinsic notion of epimorphism in Z gives a notion of covering. Thus for a space (functor) to have a finite open covering, each piece of which is representable, is a restrictive notion available when needed. A point of X is a map spec(L) --> X where L is a field extension of k.Thus the "points functor" on spaces goes not to the category of abstract sets but rather is just the restriction operation to the category of functors on fields only. This is part of what Grothendieck seems to have had in mind. A serious discontinuity is introduced by passing to the single underlying set traditionally considered, which is the inductive limit of the functor of fields. The fact that the latter process does not preserve products, and hence for example that an algebraic group "is not a group", was already for Cartier an indication that the traditional foundation had an unnatural ingredient, but before topos theory one tried to live with it (for example, I recall great geometers from the 1950s struggling to accept the new wisdom that +i and -i is one "point"). The acceptance of the view that, for non-algebraically-closed k, the appropriate base topos consists not of pure sets but rather of sheaves on just the simple objects in A, has in fact many simplifying conceptual and technical advantages; for example this base (in some sense due to Galois!) is at least qd in the sense of Johnstone, and even atomic Boolean in the sense of Barr. (Technically, to verify that the above limitation to "algebraic" A gives the usual results requires the use of a Birkhoff Nullstellensatz which guarantees that there are "enough" algebras which are finitely-generated as k-modules. The use of a larger A, insuring for example that spaces of distributions are often themselves representable, is quite possible, but the precise description of the kind of double structure which is then topos-theoretically classified needs to be worked out. Gaeta's notes of Grothendieck's lecture series at Buffalo point out that A is more closely suited than most categories to serve as a site for a geometric category, because it is what is now called "extensive" ) I believe that Grothendieck's point of view could be applied to real algebraic geometry as well, in several ways, including the following: Noting that within any topos the adjoint is available which assigns the ring R[-1] to any rig R, let us concentrate on the needed nature of positive quantities R. To include the advantages of differential calculus based on nilpotent elements, let us allow that the ideal of all elements having negatives can be non-trivial, and indeed include many infinitesimals, without disqualifying R from being "nonnegative". The ring generated by R might appear in a more geometric way as the fiber of R^T, where T is the representor for the tangent-bundle functor. The classifying topos for the theory of "real rigs", i.e., those for which 1/1+x is a given global operation, contains the classifying topos for "really local rigs" in the following sense (where "really" has the double meaning of (1) a strengthening of localness, but also (2) a concept appropriate to a real (as opposed to complex) environment): The subspace U of invertible elements in the generic algebra R has a classifying map R --> omega which of course as above preserves products; but the distributive lattice omega is in particular also a rig like R, so we can require that the classifying map be a rig homomorphism (i.e., also take + to "union"). (Of course, this elementary condition can be phrased in terms of subspaces of R and of R^2 without involving omega if desired.) The preservation of addition is a strengthening, possible for positive quantities, of the usual notion of localness (which on truth values was only an inequality). Does the right adjoint to ( )^T restrict to this really local rig classifier? ************************************************************ F. William Lawvere Mathematics Department, State University of New York 244 Mathematics Building, Buffalo, N.Y. 14260-2900 USA Tel. 716-645-6284 HOMEPAGE: http://www.acsu.buffalo.edu/~wlawvere ************************************************************ From rrosebru@mta.ca Mon Mar 31 09:43:29 2003 -0400 Status: X-Status: X-Keywords: Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 31 Mar 2003 09:43:29 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 18zzXw-0003vo-00 for categories-list@mta.ca; Mon, 31 Mar 2003 09:41:56 -0400 Date: Sun, 30 Mar 2003 21:22:43 -0500 From: Colin McLarty Subject: categories: Re: Grothendieck's 1973 Buffalo Colloquium In-reply-to: X-Sender: cxm7@pop.cwru.edu (Unverified) To: categories@mta.ca Message-id: <5.2.0.9.0.20030330210746.00b33d90@pop.cwru.edu> MIME-version: 1.0 X-Mailer: QUALCOMM Windows Eudora Version 5.2.0.9 Content-type: text/plain; charset=iso-8859-1; format=flowed Content-transfer-encoding: quoted-printable Sender: cat-dist@mta.ca Precedence: bulk I was just looking at Grothendieck's statement about schemes in EGA 3: Pour obtenir un langage qui ``colle" sans effort =E0 l'intuition=20 g\'{e}om\'{e}trique, et \'{e}viter des circonlocutions insupportables \`{a} la longue, nous identifions toujours un=20 pr\'{e}sch\'{e}ma $X$ sur un autre $S$ au foncteur \mbox{\clarrow{(\mathrm{Sch}/S)^\mathrm{o}}{\mathrm{Ens}}} qu'il=20 repr\'{e}sente, "To make the language stick to geometric intuition, and to avoid finally=20 unbearable circumlocutions, we will always identify a scheme X over another= =20 S, with the functor from Sch/S to Set that it represents." This quote is from the Springer Verlag edition page VI. This edition was=20 printed in 1970. I do not yet know if it is printed in the earlier IHES=20 edition. The IHES edition of EGA chapter 0, printed in 1960, does urge the=20 functorial rather than topological space conception of a sheaf. "We=20 systematically abstain from using espaces etales ... we never consider a=20 sheaf a topological space" (p. 25). best, Colin ___________________________________________________________ t 17:34 29/03/2003 -0500, Lawvere wrote: >Thierry Coquand recently asked me > > > In your "Comments on the Development of Topos Theory" you refer > > to a simpler alternative definition of "scheme" due to Grothendieck. > > Is this definition available at some place?? Otherwise, it it possible > > to describe shortly the main idea of this alternative definition?? > >Since several people have asked the same question over the years, I >prepared the following summary which, I hope, will be of general interest: > > The 1973 Buffalo Colloquium talk by Alexander Grothendieck had as >its main theme that the 1960 definition of scheme (which had required as a >prerequisite the baggage of prime ideals and the spectral space, sheaves >of local rings, coverings and patchings, etc.), should be abandoned AS the >FUNDAMENTAL one and replaced by the simple idea of a good functor from >rings to sets. The needed restrictions could be more intuitively and more >geometrically stated directly in terms of the topos of such functors, and >of course the ingredients from the "baggage" could be extracted when >needed as auxiliary explanations of already existing objects, rather than >being carried always as core elements of the very definition.. From rrosebru@mta.ca Mon Mar 31 09:46:08 2003 -0400 Status: X-Status: X-Keywords: Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 31 Mar 2003 09:46:08 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 18zzbq-0004Pt-00 for categories-list@mta.ca; Mon, 31 Mar 2003 09:45:58 -0400 Date: Sun, 30 Mar 2003 12:19:28 -0500 (EST) From: "NASSLLI'03 Bloomington, Indiana" X-Sender: nasslli@lear.ucs.indiana.edu Reply-To: "NASSLLI'03 Bloomington, Indiana" To: Undisclosed recipients: ; Subject: categories: NASSLLI 2003. Registration is open now. Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Registration for NASSLLI 2003 is now open. For details, please visit http://www.indiana.edu/~nasslli/registration.html ------------------------------------------------------------------------- NASSLLI 2003 http://www.indiana.edu/~nasslli The main focus of NASSLLI is on the interface between linguistics, logic, and computation, broadly conceived, and on related fields. NASSLLI is a week-long summer school featuring courses on many topics of interest to students and researchers. Some of the course topics are introductory, while others are advanced courses that bring students to areas of active research. The instructors are leading researchers who like teaching in interdisciplinary settings. Three of the courses involve work in computer labs as well. Please join us for a week of learning! ----------------------------------------------------------------------------- Registration Registration does not include accommodations. We have arranged rooms in a renovated, air-conditioned dormitory at the rate of $37/night/person + 11% tax. These are single rooms with a bathroom shared between two rooms. You will need to pay for this when you are here with cash, check, MasterCard or Visa. To reserve one of these rooms please send an e-mail to nasslli@indiana.edu , detailing for which days you will need the room. In addition, our page on hotels lists some other housing options. http://www.indiana.edu/~nasslli/hotels.html -------------------------------------------------------------------------------- Register for NASSLLI alone Before May 1 After May 1 Full-time Student $135 $150 Academic $200 $225 Industrial $280 $315 -------------------------------------------------------------------------------- Register for MoL alone To register for MoL alone, without NASSLLI: $43. -------------------------------------------------------------------------------- Register for TARK alone To register for TARK alone, without NASSLLI: For students: $100 For others: $150 -------------------------------------------------------------------------------- Register for NASSLLI + TARK Before May 1 After May 1 Full-time Student $210 $225 Academic $325 $350 Industrial $405 $440 From rrosebru@mta.ca Mon Mar 31 16:58:46 2003 -0400 Status: R X-Status: X-Keywords: Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 31 Mar 2003 16:58:46 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 1906FX-0001ka-00 for categories-list@mta.ca; Mon, 31 Mar 2003 16:51:23 -0400 Mime-Version: 1.0 X-Sender: duskin@mail.buffnet.net Message-Id: Date: Mon, 31 Mar 2003 15:11:39 -0500 To: categories@mta.ca From: John Duskin Subject: categories: Vietnamese Mathematician Content-Type: text/plain; charset="us-ascii" ; format="flowed" Sender: cat-dist@mta.ca Precedence: bulk -- The mathematician from Hanoi recently honored by the French , Hoang Xuan Sinh, was a student of Grothendieck. Her thesis was on Gr-categories.