From MAILER-DAEMON Wed Nov 8 14:26:00 2006 Date: 08 Nov 2006 14:26:00 -0400 From: Mail System Internal Data Subject: DON'T DELETE THIS MESSAGE -- FOLDER INTERNAL DATA Message-ID: <1163010360@mta.ca> X-IMAP: 1159800537 0000000050 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 Oct 2 11:47:01 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 02 Oct 2006 11:47:01 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GUOpE-00050Z-Vi for categories-list@mta.ca; Mon, 02 Oct 2006 11:31:21 -0300 Mime-Version: 1.0 Message-Id: Date: Mon, 2 Oct 2006 15:38:21 +0200 To: categories@mta.ca From: giovanni sambin Subject: categories: grants for foreign PhD students in Padua Content-Type: text/plain; charset="us-ascii" Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: X-Keywords: X-UID: 1 The University of Padua (Italy) is offering 10 grants for study in one of the PhD programs, beginning January 2007. The grants are for all doctorate programs, and they are reserved to non-Italian citizens. More information (in Italian and English) on the grants and on the university can be found at the website: http://www.unipd.it/studenti/Dopo_laurea/dottorati_ricerca/bandi_dottorato_grad/bandidottoratograduatorie.htm Please note that the deadline is October 25, and that the application must reach the office by that date. The doctorate school on Mathematical Sciences includes a curriculum in logic. Before sending the official application, any prospective applicant is suggested to get in contact with: Bruno Chiarellotto, director of the school bruno.chiarellotto@unipd.it or directly with Giovanni Sambin, professor of logic giovanni.sambin@unipd.it In fact, the application must include a research objective. Some information on research in logic in Padua can be found at www.math.unipd.it/~logic and www.math.unipd.it/~sambin G. Sambin From rrosebru@mta.ca Wed Oct 4 15:40:35 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 04 Oct 2006 15:40:35 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GVBX7-00073J-EH for categories-list@mta.ca; Wed, 04 Oct 2006 15:31:53 -0300 Date: Tue, 3 Oct 2006 10:58:59 +0100 (BST) From: S B Cooper To: categories@mta.ca Subject: categories: CiE 2007 - Preliminary Announcement MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: RO X-Status: X-Keywords: X-UID: 2 ********************************************************************** PRELIMINARY ANNOUNCEMENT CiE 2007 http://www.mat.unisi.it/newsito/cie07.html Computability in Europe 2007: Computation and Logic in the Real World Department of Mathematics and Computer Science "Roberto Magari" University of Siena Siena, 18-23 June 2007 IMPORTANT DATES: Submission of papers: Jan. 12, 2007 Notification of authors: Feb. 16, 2007 Deadline for final revisions: Mar. 9, 2007 The Third Conference CiE 2007, organised by CiE (Computability in Europe) will take place at the University of Siena, June 18-23 2007. CiE is a European network of mathematicians, logicians, computer scientists, philosophers, theoretical physicists and others interested in new developments in computability and in their underlying significance for the real world. CiE 2007 will address various aspects of the ways computability and theoretical computer science enable scientists and philosophers to deal with mathematical and real world issues, ranging through problems related to logic, mathematics, physical processes, real computation and learning theory. At the same time it will focus on different ways in which computability emerges from the real world, and how this affects our way of thinking about everyday computational issues. CiE 2007 will be co-located with the annual CCA (Computability and Complexity in Analysis) Conference (Siena, College Santa Chiara, June 16-18, 2007): http://cca-net.de/cca2007/ CiE 2007 conference topics include, but not exclusively - * Admissible sets * Analog computation * Artificial intelligence * Automata theory * Classical computability and degree structures * Complexity classes * Computability theoretic aspects of programs * Computable analysis and real computation * Computable structures and models * Computational and proof complexity * Computational learning and complexity * Concurrency and distributed computation * Constructive mathematics * Cryptographic complexity * Decidability of theories * Derandomization * DNA computing * Domain theory and computability * Dynamical systems and computational models * Effective descriptive set theory * Finite model theory * Formal aspects of program analysis * Formal methods * Foundations of computer science * Games * Generalized recursion theory * History of computation * Hybrid systems * Higher type computability * Hypercomputational models * Infinite time Turing machines * Kolmogorov complexity * Lambda and combinatory calculi * L-systems and membrane computation * Mathematical models of emergence * Molecular computation * Neural nets and connectionist models * Philosophy of science and computation * Physics and computability * Probabilistic systems * Process algebra * Programming language semantics * Proof mining * Proof theory and computability * Quantum computing and complexity * Randomness * Reducibilities and relative computation * Relativistic computation * Reverse mathematics * Swarm intelligence * Type systems and type theory * Uncertain Reasoning * Weak systems of arithmetic and applications We particularly welcome submissions in emergent areas, such as bioinformatics and natural computation, where they have a basic connection with computability. Contributed papers will be selected from submissions received by the PROGRAM COMMITTEE consisting of: M. Agrawal (Kanpur) M. Arslanov (Kazan) G. Ausiello (Roma) A. Bauer (Ljubljana) A. Beckmann (Swansea) U. Berger (Swansea) A. Cantini (Firenze) B. Cooper (Leeds, co-chair) L. Crosilla (Firenze) J. Diaz (Barcelona) C. Dimitracopoulos (Athens) F. Ferreira (Lisbon) S. Goncharov (Novosibirsk) P. Gruenwald (Amsterdam) D. Harel (Rehovot) A. Hodges (Oxford) J. Kempe (Paris) G. Longo (Paris) B. Loewe (Amsterdam) J. Makowsky (Haifa) E. Mayordomo (Zaragoza) W. Merkle (Heidelberg) F. Montagna (Siena) D. Normann (Oslo) T. Pheidas (Heraklion) G. Rozenberg (Leiden) G. Sambin (Padova) H. Schwichtenberg (Muenchen) W. Sieg (Carnegie Mellon) A. Sorbi (Siena, co-chair) I. Soskov (Sofia) P. van Emde Boas (Amsterdam). The PROGRAMME COMMITTEE cordially invites all researchers (European and non-European) in computability related areas to submit their papers (in PDF-format, max 10 pages) for presentation at CiE 2007. We particularly invite papers that build bridges between different parts of the research community. The CONFERENCE PROCEEDINGS will be published by LNCS, Springer Verlag. There will also be journal special issues, collecting invited contributions related to the conference. The conference is sponsored by EATCS, ASL, EACSL, and AILA (Italian Association of Logic and Applications). ********************************************************************** From rrosebru@mta.ca Wed Oct 4 15:40:35 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 04 Oct 2006 15:40:35 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GVBXl-00078S-RD for categories-list@mta.ca; Wed, 04 Oct 2006 15:32:33 -0300 Date: Tue, 03 Oct 2006 14:27:32 +0100 From: Alexander Kurz MIME-Version: 1.0 To: categories@mta.ca Subject: categories: PhD Studentship available Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 3 ----------------------------------------- Please distribute to potential candidates ----------------------------------------- The Department of Computer Science of the University of Leicester offers a PhD studentship (GTA). The GTA scheme involves some teaching and runs for 4 years. Unfortunately, the university waives the fees only for EU nationals. The PhD student will join Nick Bezhanishvili and myself in our current work on "Coalgebras, Modal Logic, and Stone Duality". Colleagues in Leicester working on related topics include Roy Crole, Reiko Heckel, Vincent Schmitt, Emilio Tuosto, and Fer-Jan de Vries. Moreover, there will be close collaboration with the logic groups at the University of Amsterdam (in particular with the VICI-project directed by Yde Venema at ILLC) and at the University of Oxford (Hilary Priestley, Alexandru Baltag). For more information on the topic see http://www.cs.le.ac.uk/people/akurz/ The official announcement and application form is available at (Ref S2995) http://www.le.ac.uk/personnel/supportjobs/index.html The applications should be submitted no later than 20 October 2006. If you have any questions please send me an email. Best wishes, Alexander From rrosebru@mta.ca Wed Oct 4 15:40:35 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 04 Oct 2006 15:40:35 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GVBYA-0007Ay-KG for categories-list@mta.ca; Wed, 04 Oct 2006 15:32:58 -0300 To: categories@mta.ca Subject: categories: TLCA '07 - Preliminary Call for Papers Date: Wed, 04 Oct 2006 10:25:22 +0900 From: Hasegawa Masahito Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: RO X-Status: X-Keywords: X-UID: 4 Preliminary Call for Papers Eight International Conference on Typed Lambda Calculi and Applications (TLCA '07) Paris, June 26-28, 2007 Part of RDP 07 (http://www.lsv.ens-cachan.fr/rdp07/) The TLCA series of conferences serves as a forum for presenting original research results that are broadly relevant to the theory and applications of typed calculi. The following list of topics is non-exhaustive: * Proof-theory: Natural deduction and sequent calculi, cut elimination and normalisation, linear logic and proof nets, type-theoretic aspects of computational complexity * Semantics: Denotational semantics, game semantics, realisability, categorical models * Implementation: Abstract machines, parallel execution, optimal reduction, type systems for program optimisation * Types: Subtypes, dependent types, type inference, polymorphism, types in theorem proving * Programming: Foundational aspects of functional and object-oriented programming, proof search and logic programming, connections between and combinations of functional and logic programming, type checking The programme of TLCA will consist of three invited talks and about 25 papers selected from original contributions. Accepted papers will be published as a volume of Springer Lecture Notes in Computer Science series (http://www.springer.de/comp/lncs/index.html). Submissions: The submitted papers should describe original work and should allow the Programme Committee to assess the merits of the contribution: in particular references and comparisons with related work should be included. Submission of material already published or submitted to other conferences with published proceedings is not allowed. Papers should not exceed 15 pages in Springer LNCS format (http://www.springer.de/comp/lncs/authors.html). Instructions for submissions will appear soon. Program Committee * Chantal Berline (CNRS, France) * Peter Dybjer (Chalmers, Sweden) * Healfdene Goguen (Google, USA) * Robert Harper (Carnegie Mellon University, USA) * Olivier Laurent (CNRS, France) * Simone Martini (University of Bologna, Italy) * Simona Ronchi Della Rocca (University of Torino, Italy), chair * Peter Selinger (University of Dalhousie, Canada) * Paula Severi (University of Leicester, UK) * Kazushige Terui (University of Sokendai, Japan) * Pawel Urzyczyn (University of Warsaw, Poland) Important Dates December 22 Title and abstract due January 2 Deadline for submission March 10-15 Author review period March 25 Notification of acceptance-rejection April 20 Deadline for the final version Steering Committe Samson Abramsky, Oxford, chair Henk Barendregt, Nijmegen Mariangiola Dezani-Ciancaglini, Turin Roger Hindley, Swansea Martin Hofmann, Munich Pawel Urzyczyn, Warsaw Publicity Chair Masahito Hasegawa From rrosebru@mta.ca Thu Oct 5 16:21:27 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 05 Oct 2006 16:21:27 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GVYej-0001uH-6H for categories-list@mta.ca; Thu, 05 Oct 2006 16:13:17 -0300 To: LiCS 2006 List From: Kreutzer + Schweikardt Subject: categories: LICS 2007 - Call for Workshop Proposals Date: Thu, 5 Oct 2006 19:57:38 +0200 (CEST) Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: RO X-Status: X-Keywords: X-UID: 5 LICS 2007 Call for Workshop Proposals The Twenty-Second IEEE Symposium on Logic in Computer Science (LICS 2007) will be held in Wroclaw, Poland, July 10-14, 2007. It will be colocated with two other meetings: the International Colloquium on Automata, Languages, and Programming (ICALP'07) July 9-13, 2007, and also the European Logic Colloquium (ELC 2007), July 14-19. Workshops are planned for July 8, 9 and July 15 (possibly the afternoon of 14th). LICS workshops have traditionally been an important and exciting part of the program. They introduce either newest research in traditional areas of the LICS community, recent interdisciplinary and applied areas of general theory, or emerging directions that already have some substantial overlap with LICS community interests. Researchers and practitioners are invited to submit proposals for workshops on topics relating logic - broadly construed - to computer science or related fields. Typically, LICS workshops feature a mix of invited speakers and contributed presentations. LICS workshops do not produce formal proceedings. However, in the past there have been special issues of journals based in part on certain LICS workshops. Proposals should include: -- A short scientific summary and justification of the proposed topic. This should include a discussion of the particular benefits of the topic to the LICS community. -- A discussion of the proposed format and agenda. -- Procedures for selecting participants and papers. -- Expected number of participants. (This is important!) -- Potential invited speakers. -- Plans for dissemination (for example, special issues of journals). -- For workshops of potential interest to ICALP participants, whether the workshop should be considered as a possible joint LICS/ICALP workshop. -- Tell us the timeframe you would prefer: 1 day, 1.5 or 2 days, either before LICS (July 8,9) or after LICS (July 15). Alas, some overlap with either ICALP or ELC is inevitable. Proposals are due Nov. 15, 2006, and should be submitted electronically to: Philip Scott Workshops Chair, LICS 2007 phil@site.uottawa.ca Workshops will be chosen by a committee that consists of the LICS General Chair, LICS Workshop Chair, LICS 2007 PC Chair, and LICS 2007 Conference Chair. In the case of potential joint workshops, these will be discussed with colleagues from ICALP. A decision will be made by the end of November. From rrosebru@mta.ca Sat Oct 7 09:41:34 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 07 Oct 2006 09:41:34 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GWBLQ-0004qv-MU for categories-list@mta.ca; Sat, 07 Oct 2006 09:31:56 -0300 Mime-Version: 1.0 (Apple Message framework v606) Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset=US-ASCII; format=flowed To: categories@mta.ca From: Pierre-Louis Curien Subject: categories: Position preannouncement in Paris 7 (REMINDER, qualification deadline 16/10/06) Date: Sat, 7 Oct 2006 11:16:56 +0200 Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 6 **** REMINDER **** Deadline for the "qualification procedure is 16 October, strictly. ******************************** POSITION PRE-ANNOUNCEMENT A position of Maitre de Conferences (permanent position, more or less equivalent to "associate professor", or "lecturer") ** in mathematics** is likely to be opened next year at Paris 7 University. The hired candidate will work in the laboratory PPS (Preuves, Programmes et Systemes), which spreads its interests on both sides of the correspondence between proofs and programs, covering work on language design and implementation, rewriting, semantics (and game semantics in particular), categories, linear logic, realizability, probabilistic and topological methods, etc... See www.pps.jussieu.fr. The position will be opened around February 2007, with decisions taken around May 2007, and job starting in September 2007. But there is a preliminary phase called ** qualification **, through which all candidates to academic positions in France have to go. This procedure consists of an evaluation of both research and teaching experience of candidates in view of their potential application to a position in a French university. The first phase of this (rather light) procedure is opened on September 11, 2006, and *** closes on October 16, 2006 *** and is entirely electronical (http://www.education.gouv.fr/personnel/enseignant_superieur/ enseignant_chercheur/calendrier_qualification.htm). The section of qualification should be preferably number 25 (mathe'matiques), but candidates interested in multiple applications in France, including in CS departments, may also apply for qualification in section 27 (informatique) simultaneously. This approaching first deadline is the main reason for the present early announcement. A certain fluency in French is required for the position. The teaching will be in the mathematics department, so some experience in teaching mathematics (rather than computer science) is welcome Teaching is in French. I invite potential candidates to contact me, and I also encourage colleagues to point me to interesting potential candidates fitting the criteria. Best regards, Pierre=Louis Curien curien@pps.jussieu.fr From rrosebru@mta.ca Mon Oct 9 09:49:31 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 09 Oct 2006 09:49:31 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GWuQU-0002KX-0S for categories-list@mta.ca; Mon, 09 Oct 2006 09:40:10 -0300 Date: Mon, 9 Oct 2006 11:14:34 +0100 (BST) From: Richard Garner To: categories@mta.ca Subject: categories: Reflexive coequalizers MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 7 Dear categorists, I have a proof that the indiscrete category functor Set -> Cat preserves reflexive coequalizers which, although straightfoward, uses the explicit description of colimits in Cat. Is this necessary, or can I deduce the result from general principles? [Also, I'm sure this result must appear somewhere but I can't find a reference for it. If anyone knows of one, I'd be grateful.] Many thanks, Richard From rrosebru@mta.ca Mon Oct 9 21:26:34 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 09 Oct 2006 21:26:34 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GX5Pl-0005Jv-RR for categories-list@mta.ca; Mon, 09 Oct 2006 21:24:09 -0300 Date: Mon, 09 Oct 2006 11:36:46 +0100 To: categories@mta.ca From: Jorge Picado Subject: categories: CT2007 - first announcement Mime-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1"; format=flowed Content-Transfer-Encoding: quoted-printable Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: RO X-Status: X-Keywords: X-UID: 8 CT2007 INTERNATIONAL CATEGORY THEORY CONFERENCE Hotel Tivoli Almansor, Carvoeiro (Algarve), Portugal 17-23 June 2007 In the tradition of previous meetings held in White Point (2006), Vancouver= =20 (2004), Como (2000), Coimbra (1999), Vancouver (1997), Halifax (1995),=20 Tours (1994), Isle of Thorns (1992), Montreal (1991) and Como (1990), a=20 Conference on Category Theory will be held in Hotel Tivoli Almansor=20 (http://www.algarvetivolialmansor.com/), Carvoeiro, a village near the sea= =20 in the region of Algarve (south of Portugal), from June 17 until June 23,=20 2007. We will take this occasion to celebrate the 70th birthday of F.=20 William Lawvere. The arrival day is Sunday June 17. The scientific programme will begin=20 Monday morning, June 18, and will finish before lunch on Saturday June 23.= =20 The programme will consist of conferences delivered by invited speakers and= =20 contributed talks. Scientific Committee: Samson Abramsky (Oxford, UK) Jir=ED Ad=E1mek (Braunschweig, Germany) Francis Borceux (Louvain, Belgium) George Janelidze (Cape Town, South Africa) Steven Lack (Sydney, Australia) Michael Makkai (Montreal, Canada) Manuela Sobral (Coimbra, Portugal) Ross Street (Sydney, Australia) Walter Tholen (Toronto, Canada) Updated information will be provided in the conference web page=20 http://www.mat.uc.pt/~categ/ct2007/ The Organizing Committee, Diana Rodelo, University of Algarve (drodelo@ualg.pt) Manuela Sobral, University of Coimbra (sobral@mat.uc.pt) Maria Manuel Clementino, University of Coimbra (mmc@mat.uc.pt) Jorge Picado, University of Coimbra (picado@mat.uc.pt) Lurdes Sousa, IPViseu (sousa@infante.ipv.pt) Maria Jo=E3o Ferreira, University of Coimbra (mjrf@mat.uc.pt) Gon=E7alo Gutierres, University of Coimbra (ggutc@mat.uc.pt) From rrosebru@mta.ca Mon Oct 9 21:26:34 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 09 Oct 2006 21:26:34 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GX5OG-0005DQ-2D for categories-list@mta.ca; Mon, 09 Oct 2006 21:22:36 -0300 Date: Mon, 9 Oct 2006 14:37:24 +0100 (BST) From: "Prof. Peter Johnstone" To: categories@mta.ca Subject: categories: Re: Reflexive coequalizers In-Reply-To: Message-ID: References: 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: 9 On Mon, 9 Oct 2006, Richard Garner wrote: > > Dear categorists, > > I have a proof that the indiscrete category functor > Set -> Cat preserves reflexive coequalizers which, > although straightfoward, uses the explicit > description of colimits in Cat. Is this necessary, > or can I deduce the result from general > principles? > It certainly follows from the fact that reflexive coequalizers commute with finite products in Set (or in any cartesian closed category). This is a result that some people attribute to me, since the first place it was explicitly written down seems to have been my PhD thesis, though I'm sure it was known well before that. Peter Johnstone From rrosebru@mta.ca Mon Oct 9 21:26:34 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 09 Oct 2006 21:26:34 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GX5RV-0005Qj-Vd for categories-list@mta.ca; Mon, 09 Oct 2006 21:25:58 -0300 Date: Mon, 9 Oct 2006 16:47:42 +0200 (CEST) From: Jiri Adamek To: categories@mta.ca Subject: categories: Re: Reflexive coequalizers MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 10 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx On Mon, 9 Oct 2006, Richard Garner wrote: > > I have a proof that the indiscrete category functor > Set -> Cat preserves reflexive coequalizers which, > although straightfoward, uses the explicit > description of colimits in Cat. Is this necessary, > or can I deduce the result from general > principles? > xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx This is a nice example of an algebraically exact functor: for varieties Alg T, where T is an algebraic theory (and Alg T is the category of all finite-product preserving functors in [T, Set]), all theory morphisms F: T -> S induce functors Alg F: Alg S -> Alg T given by precomposing with F; they are called algebraically exact. These are precisely the right adjoints between varieties which preserve sifted colimits- and reflexive coequalizers are special sifted colimits. This all is a part of the duality between varieties and algebraic theories (described by F.W.Lawvere, J. Rosicky and myself, Algebra Universalis 49 (2003), 1-45). Consider the "obvious" algebraic theory S of Set, the dual of finite sets, and the "obvious" theory C of Cat, the dual of finitely presentable cats. The functor F: C -> S which forgets morphisms induces the indiscrete category functor as Alg F. From rrosebru@mta.ca Mon Oct 9 21:28:46 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 09 Oct 2006 21:28:46 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GX5U2-0005bm-Mk for categories-list@mta.ca; Mon, 09 Oct 2006 21:28:34 -0300 From: "George Janelidze" To: Subject: categories: Re: Reflexive coequalizers Date: Mon, 9 Oct 2006 20:40:20 +0200 MIME-Version: 1.0 Content-Type: text/plain;charset="iso-8859-1" Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 11 Dear Richard, If we were asking the same question about the category SimplSet of simplicial sets instead of Cat, the answer would be obvious since: (*) The functor Set ---> Set sending X to X^n preserves reflexive coequalizers for each natural n. This (very simple) fact should be considered as well known since it is involved in one of several well-known proofs of monadicity of varieties of universal algebras over Set. (**) Since SimplSet is a Set-valued functor category, all colimits in it reduce to colimits in Set. For those who are familiar with the standard adjunction between SimplSet and Cat, the result for SimplSet will immediately imply the result for Cat (since the fundamental category functor being the left adjoint in that adjunction preserves all colimits and obviously sends "indiscrete simplicial sets" to indiscrete categories). One could also use various (not too much) truncated simplicial sets instead of the simplicial sets of course (e.g. what I once called "precategories"). I mean, I do not remember any reference, but I would not need the explicit description of colimits in Cat. George Janelidze ----- Original Message ----- From: "Richard Garner" To: Sent: Monday, October 09, 2006 12:14 PM Subject: categories: Reflexive coequalizers > > Dear categorists, > > I have a proof that the indiscrete category functor > Set -> Cat preserves reflexive coequalizers which, > although straightfoward, uses the explicit > description of colimits in Cat. Is this necessary, > or can I deduce the result from general > principles? > > [Also, I'm sure this result must appear somewhere > but I can't find a reference for it. If anyone > knows of one, I'd be grateful.] > > Many thanks, > > Richard > > > From rrosebru@mta.ca Mon Oct 9 21:30:11 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 09 Oct 2006 21:30:11 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GX5VP-0005iZ-IV for categories-list@mta.ca; Mon, 09 Oct 2006 21:29:59 -0300 Date: Mon, 9 Oct 2006 21:09:46 +0100 (BST) From: Richard Garner To: categories@mta.ca Subject: categories: Re: Reflexive coequalizers MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 12 Ah yes, I see now. I had observed that the underlying diagram of indiscrete graphs was still a coequalizer -- which unfortunately is to truncate one's simplicial sets a little too much! Many thanks for the enlightenment. Richard --On 09 October 2006 20:40 George Janelidze wrote: > Dear Richard, > > If we were asking the same question about the category SimplSet of > simplicial sets instead of Cat, the answer would be obvious since: > > (*) The functor Set ---> Set sending X to X^n preserves reflexive > coequalizers for each natural n. This (very simple) fact should be > considered as well known since it is involved in one of several well-known > proofs of monadicity of varieties of universal algebras over Set. > > (**) Since SimplSet is a Set-valued functor category, all colimits in it > reduce to colimits in Set. > > For those who are familiar with the standard adjunction between SimplSet and > Cat, the result for SimplSet will immediately imply the result for Cat > (since the fundamental category functor being the left adjoint in that > adjunction preserves all colimits and obviously sends "indiscrete simplicial > sets" to indiscrete categories). > > One could also use various (not too much) truncated simplicial sets instead > of the simplicial sets of course (e.g. what I once called "precategories"). > > I mean, I do not remember any reference, but I would not need the explicit > description of colimits in Cat. > > George Janelidze > > ----- Original Message ----- > From: "Richard Garner" > To: > Sent: Monday, October 09, 2006 12:14 PM > Subject: categories: Reflexive coequalizers > > >> >> Dear categorists, >> >> I have a proof that the indiscrete category functor >> Set -> Cat preserves reflexive coequalizers which, >> although straightfoward, uses the explicit >> description of colimits in Cat. Is this necessary, >> or can I deduce the result from general >> principles? >> >> [Also, I'm sure this result must appear somewhere >> but I can't find a reference for it. If anyone >> knows of one, I'd be grateful.] >> >> Many thanks, >> >> Richard >> >> >> > > From rrosebru@mta.ca Tue Oct 10 22:08:33 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 10 Oct 2006 22:08:33 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GXSPr-0005gj-Uh for categories-list@mta.ca; Tue, 10 Oct 2006 21:57:48 -0300 Subject: categories: Paper: The Euler characteristic of a category From: Tom Leinster To: categories@mta.ca Content-Type: text/plain Date: Tue, 10 Oct 2006 10:36:18 +0100 Mime-Version: 1.0 Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 13 The following paper is available. It is the full version of the talk I gave at CT06. "The Euler characteristic of a category" The Euler characteristic of a finite category is defined and shown to be compatible with Euler characteristics of other types of object, including orbifolds. A formula is proved for the cardinality of a colimit of sets, generalizing the classical inclusion-exclusion formula. Both rest on a generalization of Mobius-Rota inversion from posets to categories. http://arxiv.org/abs/math.CT/0610260 Best wishes, Tom -- Tom Leinster From rrosebru@mta.ca Tue Oct 10 22:08:33 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 10 Oct 2006 22:08:33 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GXSRh-0005rB-V7 for categories-list@mta.ca; Tue, 10 Oct 2006 21:59:41 -0300 Date: Tue, 10 Oct 2006 13:48:06 -0700 From: Ashish Tiwari To: tiwari@csl.sri.com Subject: categories: RTA'07: First Call for Papers Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 14 ************************************ * * * RTA'07 FIRST CALL FOR PAPERS * * * ************************************ http://www.lsv.ens-cachan.fr/rdp07/rta.html June 26-28, 2007 Paris, France The 18th International Conference on Rewriting Techniques and Applications (RTA'07) is organized as part of the Federated Conference on Rewriting, Deduction, and Programming (RDP'07), which comprises, in addition to RTA'07= , the conference on Typed Lambda Calculi and Applications (TLCA'07) and eight workshops (HOR, PATE, RULE, SecReT, UNIF, WFLP, WRS, and WST). IMPORTANT DATES: Jan 26, 2007: Deadline for electronic submission of title and abstract Jan 31, 2007: Deadline for electronic submission of papers Apr 02, 2007: Notification of acceptance of papers Apr 23, 2007: Deadline for final versions of accepted papers RTA is the major forum for the presentation of research on all aspects of rewriting. Typical areas of interest include (but are not limited to): * Applications: case studies; rule-based (functional and logic) programmin= g; symbolic and algebraic computation; theorem proving; system synthesis an= d verification; analysis of cryptographic protocols; proof checking; reaso= ning about programming languages and logics; program transformation; * Foundations: matching and unification; narrowing; completion techniques; strategies; constraint solving; explicit substitutions; tree automata; termination; combination; * Frameworks: string, term, graph, and proof rewriting; lambda-calculus an= d higher-order rewriting; proof nets; constrained rewriting/deduction; categorical and infinitary rewriting; integration of decision procedures= ; * Implementation: compilation techniques; parallel execution; rewrite tool= s; termination checking; * Semantics: equational logic; rewriting logic; rewriting models of progra= ms. BEST PAPER AWARD: An award is given to the best paper or papers as decided = by the program committee. RTA'07 PROGRAM COMMITTEE CHAIR: * Franz Baader (Dresden, Germany) RTA'07 PROGRAM COMMITTEE: * Alessandro Armando (Genova, Italy) * Franz Baader (Dresden, Germany) * Roberto Di Cosmo (Paris, France) * J=FCrgen Giesl (Aachen, Germany) * Deepak Kapur (Albuquerque, USA) * H=E9l=E8ne Kirchner (Nancy, France) * Barbara K=F6nig (Duisburg, Germany) * Salvador Lucas (Valencia, Spain) * Narciso Mart=ED-Oliet (Madrid, Spain) * Tobias Nipkow (Munich, Germany) * Femke van Raamsdonk (Amsterdam, The Netherlands) * Aaron Stump (St. Louis, USA) * Sophie Tison (Lille, France) * Ralf Treinen (Cachan, France) RTA'07 CONFERENCE CHAIRS: * Ralf Treinen (Cachan, France) * Xavier Urbain (Paris, France) RTA PUBLICITY CHAIR: * Ashish Tiwari (Menlo Park, USA) RTA'07 SUBMISSIONS: Submissions must be original and not submitted for publication elsewhere. Submission categories include regular research papers and system descriptio= ns. Problem sets and submissions describing interesting applications of rewriti= ng techniques are also welcome. The page limit for submissions is 15 pages in Springer LNCS style (10 pages for system descriptions). The submission Web page will be made available beginning of December. As usual, the proceeding= s of RTA'07 will be published in the Springer LNCS series. Please consult the RTA'07 conference Web page for further information: http://www.lsv.ens-cachan.fr/rdp07/rta.html From rrosebru@mta.ca Wed Oct 11 14:06:24 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 11 Oct 2006 14:06:24 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GXhQG-0004pL-8k for categories-list@mta.ca; Wed, 11 Oct 2006 13:59:12 -0300 Date: Wed, 11 Oct 2006 13:02:09 -0400 (EDT) From: Richard Blute To: categories@mta.ca Subject: categories: Octoberfest schedule MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 15 Hi everyone, Here is the schedule for Octoberfest 06. Abstracts will appear on the website shortly, which can be found at http://www.site.uottawa.ca/~phil/lfc/ cheers Rick Blute Saturday, October 21st 8:45-9:15 Registration and Welcome 9:15-9:45 Robin Cockett (Calgary) 9:50-10:20 Pieter Hofstra (Calgary) 10:20-10:50 Break 10:50-11:20 Derek Wise (UC Riverside) 11:25-11:55 Eric Paquette (UQAM) 12:00-12:30 Benoit Valiron (Dalhousie) 12:30-2:00 Lunch 2:00-3:00 Plenary Speaker-Ben Steinberg (Carleton) 3:00-3:30 Break 3:30-4:00 Jonathan Scott (Ottawa) 4:05-4:35 Paul-Eugene Parent (Ottawa) 4:40-5:20 Nick Gurski (Yale) 5:25-5:55 Gabor Lukacs (Manitoba) Sunday, October 22nd 9:00-9:30 Bob Rosebrugh (Mount Allison) 9:35-10:05 Marta Bunge (McGill) 10:10-10:40 Brian Redmond (Ottawa) 10:40-11:10 Break 11:10-11:40 Michael Winter (Brock) 11:45-12:15 Fred Linton (Wesleyan) 12:20-12:50 Jim Lambek (McGill) Titles (abstracts will appear on website) ++++++ Robin Cockett-Seely categories revisited Pieter Hofstra-Models of more than the lambda calculus Derek Wise-Volumetric Field Theory Eric Paquette-The classical world from quantum theory Benoit Valiron-On a fully abstract model for a quantum linear lambda calculus Ben Steinberg-Ordered 2-complexes and inverse semigroups Jonathan Scott-Operads and iterated loop spaces Paul-Eugene Parent-Towards an adjoint to a Connes-Moscovici construction Nick Gurski-Eckman-Hilton arguments in dimensions 1 and 2 Gabor Lukacs-Duality theory of locally precompact groups Bob Rosebrugh-Implementing database design categorically (System demonstration) Marta Bunge-Locally quasiconnected toposes Brian Redmond-Soft linear logic Michael Winter-Cardinality in allegories Fred Linton-On Algebras over the Banach unit disc monad Jim Lambek-Towards a Feynman category for the standard model. -- From rrosebru@mta.ca Fri Oct 13 12:48:11 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 13 Oct 2006 12:48:11 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GYP8U-0005vt-Gi for categories-list@mta.ca; Fri, 13 Oct 2006 12:39:46 -0300 Date: Thu, 12 Oct 2006 22:25:04 -0500 (CDT) From: "Francisco Marmolejo (314)" To: categories@mta.ca Subject: categories: Leopoldo Roman MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: RO X-Status: X-Keywords: X-UID: 16 Dear Category theorists, It is with great sadness that I must tell you of Leopoldo Roman's untimely death. I do not have any details at the moment, all I know is that this happened earlier today (Wednesday). Leopoldo was the first to seriously talk to me about Category Theory, and he was the one that sent me in the direction of Dalhousie University; I will thank him for ever for both. Francisco Marmolejo From rrosebru@mta.ca Sun Oct 15 09:51:29 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 15 Oct 2006 09:51:29 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GZ5KI-00012t-50 for categories-list@mta.ca; Sun, 15 Oct 2006 09:42:46 -0300 Date: Sun, 15 Oct 2006 09:38:19 -0300 (ADT) From: Bob Rosebrugh To: categories Subject: categories: Power outage in Buffalo 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: 18 Dear Colleagues, Bill Lawvere has asked me to let you know that he will be unable to respond to email for up to eight days due to a power outage. As some of you know, Buffalo experienced an unseasonable and severe snow storm Thursday night while leaves were still on trees. The resulting damage to electrical service will take several days to repair. Telephones are working and all are reported safe, if not warm. Best wishes, Bob Rosebrugh From rrosebru@mta.ca Sun Oct 15 21:07:08 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 15 Oct 2006 21:07:08 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GZFwd-0004oN-Sd for categories-list@mta.ca; Sun, 15 Oct 2006 21:03:03 -0300 Date: Sun, 15 Oct 2006 14:23:37 -0400 (EDT) From: Michael Barr To: Categories list Subject: categories: Available on my ftp site MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 19 I have redone my ftp site to a certain extent. Available now are the latest version of TTT (a small number of corrections, plus one place where some incomprehensible equations were replaced by equivalent diagrams) and a couple of my older papers that I found on Jstor. I really do not understand the copyright issues on the latter. Clearly Jstor deserves something (but they earned a fee when I downloaded them). In the olden days (say 25 years ago and older) the publishers did not ask for any copyright form signed, but just registered a copyright. They act as if I have no rights, but I believe that without a piece of paper, they cannot really stop me. I have not signed over my rights since before 1995 (including two papers in 1995 in JPAA, where I gave them only a right-to-print). So there is a ten or 15 year period where I really did sign over the copyright. So be warned. Incidentally, Charles and I have full rights to TTT and this is posted with Charles's permission. My ftp site is ftp.math.mcgill.ca/pub/barr/pdffiles Michael From rrosebru@mta.ca Mon Oct 16 12:18:56 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 16 Oct 2006 12:18:56 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GZU7M-0004ZN-FN for categories-list@mta.ca; Mon, 16 Oct 2006 12:11:04 -0300 From: "Erzsebet Csuhaj-Varju" To: Subject: categories: FCT 2007 - First Announcement Date: Mon, 16 Oct 2006 14:20:10 +0200 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-2" Content-Transfer-Encoding: quoted-printable Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 20 __________________________________________________________ FIRST ANNOUNCEMENT ____________________________________________________________ =20 CALL FOR PAPERS FCT 2007 16th International Symposium on Fundamentals of Computation Theory Budapest, Hungary August 27-30, 2007 URL: http://www.conferences.hu/fct2007 E-mail: fct2007@conferences.hu ORGANIZING INSTITUTIONS: Computer and Automation Research Institute, Hungarian Academy of = Sciences Department of Computer Science, University of Szeged The Symposium on Fundamentals of Computation Theory was established in 1977 for researchers interested in all aspects of theoretical computer science, in particular in algorithms, complexity, formal and logical methods. It is a biennial series of conferences previously held in = Poznan (1977), Wendisch-Rietz (1979), Szeged (1981), Borgholm (1983), Cottbus (1985), Kazan (1987), Szeged (1989), Gosen-Berlin (1991), Szeged = (1993), Dresden (1995), Krak=F3w (1997), Iasi (1999), Riga (2001), Malm=F6 = (2003), and L=FCbeck (2005). TOPICS: Authors are invited to submit papers presenting original unpublished research in all areas of theoretical computer science. Topics of interest include (but not limited to): automata and formal languages design and analysis of algorithms computational and structural complexity semantics logic, algebra and categories in computer science circuits and networks learning theory specification and verification parallel and distributed systems concurrency theory cryptography and cryptographic protocols approximation and randomized algorithms computational geometry quantum computation and information bio-inspired computation INVITED SPEAKERS:=20 Ahmed Bouajjani (Paris, France) Oscar H. Ibarra (Santa Barbara, CA, USA) L=E1szl=F3 Lov=E1sz (Budapest, Hungary) Philip Scott (Ottawa, Canada) STEERING COMMITTEE: Bogdan Chlebus (Warsaw/Denver, Poland/USA) Zolt=E1n =C9sik (Szeged, Hungary) Marek Karpinski (Bonn, Germany) - chair Andrzej Lingas (Lund, Sweden) Miklos Santha (Paris, France) Eli Upfal (Providence, RI, USA) Ingo Wegener (Dortmund, Germany) PROGRAMME COMMITTEE: Jiri Adamek (Braunschweig, Germany) Giorgio Ausiello (Rome, Italy) Jean Berstel (Marne-la-Vall=E9e, France) Flavio Corradini (Camerino, Italy) Erzs=E9bet Csuhaj-Varj=FA (Budapest, Hungary) - co-chair Zolt=E1n =C9sik (Szeged, Hungary) - co-chair Jozef Gruska (Brno, Czech Republic) Masahito Hasegawa (Kyoto, Japan) Juraj Hromkovic (Zurich, Switzerland) Anna Ingolfsdottir (Reykjavik, Iceland) Masami Ito (Kyoto, Japan) Frederic Magniez (Paris, France) Catuscia Palamidessi (Palaiseau, France) Gheorghe Paun (Bucharest/Seville, Romania/Spain) Jean-Eric Pin (Paris, France) R. Ramanujam (Chennai, India) Alexander Rabinovich (Tel-Aviv, Israel) Grzegorz Rozenberg (Leiden, The Netherlands) Wojciech Rytter (Warsaw, Poland) Arto Salomaa (Turku, Finland) David A. Schmidt (Manhattan, KS, USA) Alex Simpson (Edinburgh, UK) Michael Sipser (Cambridge, MA, USA) Colin Stirling (Edinburgh, UK) Howard Straubing (Boston, MA, USA) Gy=F6rgy Tur=E1n (Chicago, IL, USA) Thomas Wilke (Kiel, Germany) SUBMISSION: Authors are invited to submit a draft of a full paper with at most 12 pages in LNCS style. The paper should provide sufficient detail to allow the Programme = Committee to evaluate its validity, quality, and relevance. If appropriate, then detailed proofs can be attached as an appendix. Simultaneous submission = to other conferences with published proceedings is not allowed. Only electronic submissions are accepted, PLEASE FOLLOW the = INSTRUCTIONS on the CONFERENCE WEB SITE: http://www.conferences.hu/fct2007 IMPORTANT DATES: Deadline for submissions: March 5, 2007 Notification to the authors: April 20, 2007 Final version : May 20, 2007 Symposium: August 27-30, 2007 PROCEEDINGS: We anticipate that the proceedings will be published in the Lecture = Notes in Computer Science series of Springer Verlag, and that a special issue of Theoretical Computer Science will be devoted to selected papers presented at the conference. PLEASE CONTACT: Programme: Dr. Erzs=E9bet Csuhaj-Varj=FA Computer and Automation Research Institute Hungarian Academy of Sciences H-1111, Budapest Kende u.13-17, Hungary E-mail: csuhaj@sztaki.hu LOCAL ARRANGEMENTS: Mrs. Mariann Kindl Computer and Automation Research Institute Hungarian Academy of Sciences H-1111 Kende u.13-17, Hungary Phone: +36-1-279-6188 Fax: +36-1-386-9378 Email: fct2007@conferences.hu From rrosebru@mta.ca Tue Oct 17 08:25:37 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 17 Oct 2006 08:25:37 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GZn0N-0007M3-4o for categories-list@mta.ca; Tue, 17 Oct 2006 08:21:07 -0300 To: categories@mta.ca Subject: categories: Lawvere-metrics and Banach spaces From: Paul Taylor Date: Tue, 17 Oct 2006 11:19:21 +0100 Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 21 There is a widely cited paper by Bill Lawvere called "Metric spaces, generalised logic and closed catgeories" in which he shows how metric spaces are examples of enriched categories. The enriching structure consists of the nonnegative reals, with "greater than" as the morphisms and addition as the tensor product. Using this one can generalise the notion of metric space by substituting other structures in place of R. An obvious question is - what happens when we follow through this idea for Banach spaces? What becomes of the $\ell_p$ spaces and of dual spaces? Do families of semi-norms naturally fit into this pattern? Paul Taylor From rrosebru@mta.ca Tue Oct 17 20:13:34 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 17 Oct 2006 20:13:34 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GZy1O-0006gu-E0 for categories-list@mta.ca; Tue, 17 Oct 2006 20:06:54 -0300 Date: Tue, 17 Oct 2006 10:46:47 -0400 (EDT) From: Michael Barr To: categories@mta.ca Subject: categories: Re: Lawvere-metrics and Banach spaces MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 22 I would like to remind the categorical community that Lawvere's paper is now generally available as a TAC Reprints #1. On Tue, 17 Oct 2006, Paul Taylor wrote: > There is a widely cited paper by Bill Lawvere called "Metric spaces, > generalised logic and closed catgeories" in which he shows how metric > spaces are examples of enriched categories. The enriching structure > consists of the nonnegative reals, with "greater than" as the morphisms > and addition as the tensor product. Using this one can generalise > the notion of metric space by substituting other structures in place of R. > > An obvious question is - what happens when we follow through this idea > for Banach spaces? What becomes of the $\ell_p$ spaces and of dual spaces? > Do families of semi-norms naturally fit into this pattern? > > Paul Taylor > > > From rrosebru@mta.ca Wed Oct 18 19:30:52 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 18 Oct 2006 19:30:52 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GaJrf-0002Hm-S5 for categories-list@mta.ca; Wed, 18 Oct 2006 19:26:19 -0300 Date: Tue, 17 Oct 2006 11:17:03 +0330 From: "darush aghababayee.dehkordi" Subject: categories: from darush.aghababayeedehkordi MIME-Version: 1.0 To: categories Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: RO X-Status: X-Keywords: X-UID: 23 in R-module category congugate of aR- module as same as opposit of this R-module but i dont see general definition of conjugation of a category conjugatify of an r-module is dulify of r-module (this example exist in homologybook of sunders maclane) darush.aghababayeedehkordi From rrosebru@mta.ca Wed Oct 18 19:30:52 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 18 Oct 2006 19:30:52 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GaJtQ-0002Pt-57 for categories-list@mta.ca; Wed, 18 Oct 2006 19:28:08 -0300 Date: Wed, 18 Oct 2006 11:17:41 +0200 From: metere@mat.unimi.it To: categories@mta.ca Subject: categories: Milan Workshop in categorical algebra: Third announcement MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 24 ******************************************** * INTERNAL ACTIONS and INTERNAL STRUCTURES * * * * WORKSHOP in CATEGORICAL ALGEBRA * * * ******************************************** Third announcement: Important Notice and Schedule. Dear Colleagues, the Workshop will be held at the Department of Mathematics, via Saldini 50, Milano. IMPORTANT NOTICE. If you have registered using the web-form, and you did not receive ANY confirmation Email, maybe your registration have been lost in the internet. So, if this is the case, please send us an Email to "milanworkshop.06@gmail.com". Here is a preliminary program. Thursday 26th October 2006 9:00 - 9.45 > registration 9:45 - 10:30 > Marino Gran "Internal groupoids and crossed modules" (Ia) 10:45 - 11:15 > coffee break 11:15 - 12:15 > Marino Gran (Ib) 13:00 - 14:30 > Lunch 14:30 - 15:00 > Communications 15:15 - 16:00 > Dominique Bourn "Split extension classifier, actions representation and associated classification properties" (Ia) 16:15 - 16:45 > coffee break 16:45 - 17:45 > Dominique Bourn (Ib) 18.00 - 18:30 > Communications Friday 27th October 9:30 - 10:15 > Marino Gran (IIa) 10:30 - 11:00 > coffee break 11:00 - 12:00 > Marino Gran (IIb) 13:00 - 14:30 > Lunch 14:30 - 15:00 > Communications 15:15 - 16:00 > Dominique Bourn (IIa) 16:15 - 16:45 > coffee break 16:45 - 17:45 > Dominique Bourn (IIb) 18.00 - 18:30 > Communications Saturday 28th October 9:30 - 10:15 > Enrico Vitale "Schreier theory and obstruction theory via categorical groups" (a) 10:30 - 11:00 > coffee break 11:00 - 12:00 > Enrico Vitale (b) The web pages http://users.mat.unimi.it/users/mantovani/workshopMi06.htm contain the abstracts of the lectures. Best regards, Stefano Kasangian Sandra Mantovani Beppe Metere ---------------------------------------------------------------- From rrosebru@mta.ca Mon Oct 23 09:09:24 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 23 Oct 2006 09:09:24 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GbyUm-0003ax-Fj for categories-list@mta.ca; Mon, 23 Oct 2006 09:01:32 -0300 Date: Sun, 22 Oct 2006 18:26:06 -0700 From: John Baez To: categories Subject: categories: cartesian closed categories and holodeck games Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 26 Dear Categorists - This contains a popularization of Dolan and Trimble's work on game theory and the free cartesian closed category on one object. It also has links to more detais. Best, jb .................................................................... Also available as http://math.ucr.edu/home/baez/week240.html October 22, 2006 This Week's Finds in Mathematical Physics (Week 240) John Baez [stuff deleted] In my seminar this year, we're focusing on two topics: quantization and cohomology, and classical versus quantum computation. I'm trying out something new: not only are the notes available on the web, there's also a blog entry for each class, where you can ask questions, make comments and correct my mistakes! 4) John Baez, Fall 2006 seminars: Quantization and cohomology, and Classical versus quantum computation. Notes by Derek Wise, homeworks and blog entries available at http://math.ucr.edu/home/baez/qg-fall2006/ I hope more people blend teaching with blogging. It's not too much work if someone with legible handwriting takes notes and the lectures can actually be followed from the notes. You can use blogging to interactively teach people scattered all over the planet! This week, James Dolan gave a talk on something he's been working on for a long time: games and cartesian closed categories. Lately he's been making a lot of progress with Todd Trimble. Let me introduce you to what they did, because it's really cool. Let's play a game. I have a set X in my pocket, and I'm not telling you what it is. Can you pick an element of X in a systematic way? No, of course not: you don't have enough information. X could even be empty, in which case you're clearly doomed! But even if it's nonempty, if you don't know anything about it, you can't pick an element in a systematic way. So, you lose. Okay, let's play another game. Can you pick an element of X^X in a systematic way? Here A^B means the set of functions from B to A. So, I'm asking if you can pick a function from X to itself in a systematic way. Yes! You can pick the identity function! This sends each element of X to itself: x |-> x You don't need to know anything about X to describe this function. X can even be empty. So, you win. Are there any other ways to win? No. Now let's play another game. Can you pick an element of X^(X^X) in a systematic way? An element in here takes functions from X to itself and turns them into elements of X. When X is the set of real numbers, people call this sort of thing a "functional", so let's use that term. A functional eats functions and spits out elements. You can scratch your head for a while trying to dream up a systematic way to pick a functional for any set X. But, there's no way. So, you lose. Let's play another game. Can you pick an element of (X^X)^(X^X) in a systematic way? An element in here eats functions and spits out functions. When X is the set of real numbers, people often call this sort of thing an "operator", so let's use that term. Given an unknown set X, can you pick an operator in a systematic way? Sure! You can pick the identity operator. This operator eats any function from X to itself and spits out the same function. We can write any function from X to itself as x |-> y, where y is something depending on x. So, we can write the identity operator as (x |-> y) |-> (x |-> y) Anyway: you win. Are there any other ways to win? Yes! There's an operator that takes any function and spits out the identity function: (x |-> y) |-> (z |-> z) This is a bit funny-looking, but I hope you get what it means: you put in any function x |-> y, and out pops the identity function z |-> z. This arrow notation is very powerful. It's usually called the "lambda calculus", since when Church invented it in the 1930s, he wrote it using the Greek letter lambda instead of an arrow: instead of x |-> y he wrote lambda x.y But this just makes things more confusing, so let's not do it. Are there more ways to win this game? Yes! There's also an operator that takes any function f from X to itself and "squares" it - in other words, does it twice. If we write the result as f^2, this operator is f |-> f^2 But, we can express this operator without using any special symbol for squaring. If we write our function f as (x |-> y) and apply it to some element z, we get (x |-> y)(z) So, if we apply f^2 to z, we get (x |-> y)((x |-> y)(z)) So, the function f^2 does this: z |-> (x |-> y)((x |-> y)(z)) and our squaring operator f |-> f^2 does this: (x |-> y) |-> (z |-> (x |-> y)((x |-> y)(z))) This looks pretty complicated. But, it shows that our systematic way of choosing an element of (X^X)^(X^X) can still be expressed using just the lambda calculus. Now that you know "squaring" is a way to win this particular game, you'll immediately guess a bunch of other ways: "cubing", and so on. It turns out all the winning strategies are of this form! We can list them all using the lambda calculus: (x |-> y) |-> (z |-> z) (x |-> y) |-> (z |-> (x |-> y)(z)) (x |-> y) |-> (z |-> (x |-> y)((x |-> y)(z))) (x |-> y) |-> (z |-> (x |-> y)((x |-> y)((x |-> y)(z)))) etc. Note that the second one is just a longer name for the identity operator. The longer name makes the pattern clear. The moral of this game is that all systematic methods for picking an element of (X^X)^(X^X) for an unknown set X can be written using the lambda calculus. So, from now on, we'll take this as our *definition* of a "systematic way". Now let's play another game. Can you pick an element of X^(X^(X^X)) in a systematic way? An element in here eats functionals and spits out elements of X. So, it's called a "functionalal" on X. At least that's what Jim calls it. If I have an unknown set in my pocket, can you pick a functionalal on this set in a systematic way? Yes! You just need to pick a recipe that takes functionals on X and turns them into elements of X. Here's one recipe: take any functional and evaluate it on the *identity* function, getting an element of x. In lambda calculus notation, this recipe looks like this: ((x |-> y) |-> z) |-> ((x |-> y) |-> z)(w |-> w) Can you think of other ways to win this game? I hope so: there are infinitely many! Jim and Todd figured out a systematic way to list them all. Now let's play another game. Can you pick an element of X^(X^(X^(X^X))) in a systematic way? Such a thing eats functionalals and spits out elements of X, so it's called a "functionalalal". So, can you find a functionalalal on an unknown set in some systematic way? The answer is no: you lose. How about picking an element of ((X^X)^(X^X))^((X^X)^(X^X)) in a systematic way? Such a thing eats operators and spits out operators, so it's called an "operatorator". The answer is yes: there are lots of ways to win this game. The real challenge is listing them! This is the sort of question Dolan and Trimble's work answers: for any game of this sort, it lets you list all the ways to win. In fact, instead of moving on to functionalators, operatorals, operatoralatorals, and so on, let me just tell you trick for instantly deciding which of all these games you can win. You just take your game, like this: ((X^X)^(X^X))^((X^X)^(X^X)) and evaluate it by setting X = 0. If you get 0, there's no way to win. If you get 1, there's at least one way to win. To use this trick, you need to know that 0^0 = 1 This is something they don't teach in school! In analysis, X^Y can approach anything between 0 and 1 when X and Y approach 0. So, teachers like to say 0^0 is undefined. But X^X approaches 1 when X -> 0. More importantly, in set theory, A^B stands for the set of functions from B to A, and the number of elements in this set is |A^B| = |A|^|B| When A and B are empty, there's just one function from B to A, namely the identity. So, for our purposes we should define 0^0 = 1. Consider the case of functionals, which are elements of X^(X^X). If we evaluate this at X = 0 we get 0^(0^0) = 0^1 = 0 So, there are no functionals when X is the empty set. So, you can't pick a functional on a unknown set in a systematic way. That's why you lose when your game evaluates to 0. It's more interesting to prove that for games evaluating to 1, there's a way to win. But we'd really like to understand *all* the ways to win. And for this, Dolan and Trimble needed the theory of holodeck games. In Star Trek, the "holodeck" is a virtual reality environment where you can play various games. On the holodeck, if you regret a move you made, you can back up to any earlier point in the game and make a new move. Actually I'm deviating from the technical specifications of the holodeck on Star Trek, as explained here: 6) Wikipedia, Holodeck, http://en.wikipedia.org/wiki/Holodeck So, if you're a Star Trek purist, it's better to imagine a video game where you can save your game at any state of play, and go back to these saved games whenever you want. And, you have to imagine being so paranoid that you *always* save your game before making a move. This allows games to go on forever, so we only say you have a winning strategy if you can win in a finite number of moves, no matter what the other player does. To make this completely precise, we consider two-player games where the players take turns making moves. When a player can't make a move, they lose. Any such game can be written as a "game tree", like this: | \/ \ | / \|/ In this example, the first player has three choices for her first move. If she picks the middle branch, the second player has one choice for his first move. Then the first player has one choice for her second move. Then the second player has no choice for his second move - so he loses. So, in this particular example the second player has no winning strategy. A cool thing about such a game is that we can take its game tree and turn it into an expression built from some variable X using products and exponentials. To do this, just put an X at each vertex of the tree except the root: X X X | \/ X X X \ | / X X X \|/ Then blow on the tree with a strong westerly wind, so strong that the branches blow away and only the X's are left: X XX X X X X X X This is just a way of writing an expression built from X using products and exponentials: X^X X^(X^X) X^(X^(XX)) Conversely, any such expression can be turned back into a tree, at least after we simplify it using these rules: (AB)^C = A^C B^C (A^B)^C = A^(BC) For example, consider the set of operators: (X^X)^(X^X) If we simplify this, we get X^(X X^X) or X X X X giving the tree X / X X \ / X | or in other words / \ / | And here's a cool fact: if you take any expression built from X using products and exponentials, and evaluate it at X = 0, you can tell which player has a winning strategy for the game described by the corresponding tree! If you get 1, the second player has a winning strategy; if you get 0, they don't. It's pretty easy to prove: try it. But if you've been paying attention, you'll have noticed something weird. I've told you TWO ways to get a game from any expression built from X using products and exponentials. First, the game of systematically picking an element of the resulting set. Second, the game we get by turning this expression into a game tree, like I just did. For *both* these games, you can decide if there's a winning strategy by evaluating the expression at X = 0. But are they the same game? No! One is the holodeck version of the other! Let's look at the familiar example of operators: (X^X)^(X^X) = X^(X X^X) This evaluates to 1 at X = 0. So, if we turn it into a tree / \ / | we get a game where the second player has a winning strategy. This game is not very exciting, but it becomes more exciting if you call it "The Lady or the Tiger". In this game, the first player has only one first move: he takes the second player to a room with two doors, corresponding to the two branches of the above tree. Then it's the second player's turn. If he opens the left door, a beautiful lady pops out and they instantly get married and live happily ever after. If he opens the right door, the first player opens a tiger cage. Then the tiger jumps out and eats the second player. In this game, the second player has just ONE winning strategy: on his first move he should choose the left door. Next look at the game of defining an element of (X^X)^(X^X) = X^(X X^X) using the lambda calculus. We've seen there are INFINITELY MANY strategies for winning this: (x |-> y) |-> (z |-> z) (x |-> y) |-> (z |-> (x |-> y)(z)) (x |-> y) |-> (z |-> (x |-> y)((x |-> y)(z))) (x |-> y) |-> (z |-> (x |-> y)((x |-> y)((x |-> y)(z)))) and so on. These correspond to 2nd-player winning strategies for the *holodeck version* of The Lady or the Tiger. What are these strategies? One is just to play the game and win by choosing the left door. Another is to choose the right door - and then, just when the tiger is about to eat you, back up and choose the left door! Another is to choose the right door - and then, just when the tiger is about to eat you, back up and choose... the right door! Whoops! Then, when the tiger is about to devour you again, back up again, and this time choose the left door. And so on: for each n, there's a strategy where you choose the right door n times before wising up and choosing the left door. Now, if you want a really nice math project, ponder the pattern relating all these strategies to the corresponding lambda calculus expressions: (x |-> y) |-> (z |-> z) (x |-> y) |-> (z |-> (x |-> y)(z)) (x |-> y) |-> (z |-> (x |-> y)((x |-> y)(z))) (x |-> y) |-> (z |-> (x |-> y)((x |-> y)((x |-> y)(z)))) etc. Then, figure out how to prove Dolan and Trimble's "Fundamental Theorem". This sets up a 1-1 correspondence between winning second-person strategies for the holodeck verson of any 2-person game, say: | \/ \ | / \|/ and ways of using the lambda calculus to define elements of the corresponding set: X^X X^(X^X) X^(X^(XX)) If you get stuck, first try these notes from Dolan's talk, and then Trimble's more rigorous, technical treatment: 7) James Dolan, Holodeck strategies and cartesian closed categories, lecture at UCR, notes by John Baez, Oct. 19, 2006, available at http://math.ucr.edu/home/baez/qg-fall2006/f06week03b.pdf 8) Todd Trimble, Holodeck games and CCCs, available at http://math.ucr.edu/home/baez/trimble/holodeck.html Dolan's talk also explains some other fun stuff, like how to multiply and exponentiate games. So, if you read these notes, you'll learn how to play chess x go and chess^{go} at least after chess and go have been "improved" so games never last forever and the last player able to make a move wins. But, if you're planning to study this stuff, I'd better admit now that Dolan and Trimble formalize the concept of "systematically picking an element of an unknown set" with the help of cartesian closed categories. A category is "cartesian" if it has finite products - or in other words, binary products and a terminal object. It's "cartesian closed" if it also has exponentials. All these terms are carefully defined in the week 2 and week 3 notes of my classical versus quantum computation course, so let me just illustrate them with an example: the category of sets. Here the product A x B of two sets A and B is their usual Cartesian product. The exponential A^B is the set of functions from B to A. Any 1-element set is a terminal object. What Dolan and Trimble really study is the "free cartesian closed category on one object x", which I like to call CCC[x]. Any object in CCC[x] is built from the object x by means of binary products, exponentials and the terminal object. For example, we have objects like this: x^1 1^(x^x) (x x)^(x 1 x^(x^x)) where I've omitted the times symbols for products. However, every object is isomorphic to one in "tree form". For example, the above object is isomorphic to x x^(x x^(x^x)) x^(x x^(x^x)) which we can draw as a tree: x x | / x x x x \| |/ x x x \|/ Dolan and Trimble consider the set of elements of any object in CCC[x], where an "element" is a morphism from the terminal object, e.g. f: 1 -> x x^(x x^(x^x)) x^(x x^(x^x)) And, they show these elements are in 1-1 correspondence with second-player winning strategies for the holodeck version of the game whose tree is constructed as above. If we pick any set X, the universal property of CCC[x] gives a functor F: CCC[x] -> Set This maps elements of any object in CCC[x] to elements of the corresponding object in Set: F(f): 1 -> X X^(X X^(X^X)) X^(X X^(X^X)) So, the element f gives a "systematic way of picking elements" of any set built from any arbitrary set X using finite products and exponentials. There might be *other* things that deserve to be called "systematic ways of picking elements", but while that's an interesting question, it's not really the point here. By the way, in a cartesian closed category, there's a 1-1 correspondence between morphisms f: B -> A and elements f: 1 -> A^B So, Dolan and Trimble's work really gives a complete description of objects and morphisms in the free cartesian closed category on one object! They also can describe *composition* in terms of games, and maybe Jim will talk about this next Tuesday. So, they have a complete description of CCC[x] in terms of games. Now let me give you some references on cartesian closed categories, the lambda calculus, categorical semantics, and games. It's an interesting network of subjects. Categorical semantics was born in Lawvere's celebrated 1963 thesis on algebraic theories: 9) F. William Lawvere, Functorial Semantics of Algebraic Theories, Dissertation, Columbia University, 1963. Also available at available at http://www.tac.mta.ca/tac/reprints/articles/5/tr5abs.html Semantics deals with theories and their models. Dual to the concept of semantics is the concept of "syntax", which deals with proofs. In the case of algebraic theories, the syntax was studied before Lawvere in the subject called "universal algebra": 10) Stanley Burris and H.P. Sankappanavar, A Course in Universal Algebra, available at http://www.math.uwaterloo.ca/~snburris/htdocs/ualg.html Lawvere modernized universal algebra by realizing that an algebraic theory is just a cartesian category, and a model is a product-preserving functor from this theory into Set or some other cartesian category - hence his thesis title, "Functorial Semantics". I explained this in much more detail back in "week200". The relevance of all this to computer science becomes visible when we note that a proof in universal algebra can be seen as a rudimentary form of computation. The "input" of the computation is a set of assumptions, while the "output" is the equation to be proved. Treating proofs as computations may seem strained, but it becomes less so when we move to richer formalisms which allow for more complex logical reasoning. One of best-known of these is the lambda calculus, invented by Church and Kleene in the 1930s as a model of computation. Any function computable by the lambda calculus is also computable by a Turing machine, and according to the Church-Turing thesis these are all the functions computable by any sort of systematic process. Moreover, computations in the lambda calculus can actually be seen as proofs. The usefulness of this way of thinking was brought out in Landin's classic paper: 11) P. Landin, A correspondence between ALGOL 60 and Church's lambda-notation, Comm. ACM 8 (1965), 89-101, 158-165. This began a long and fruitful line of research - see for example this: 12) H. Barendregt, The Lambda Calculus, its Syntax and Semantics, North-Holland, 1984. The power of the lambda calculus is evident in the textbook developed for MIT's introductory course in computer science, which is available online: 13) H. Abelson, G. J. Sussman and J. Sussman, Structure and Interpretation of Computer Programs, available at http://www-mitpress.mit.edu/sicp/ It cites pioneers like Haskell Curry, and it even has a big "lambda" on the cover! Students call it "the wizard book", because the cover also features a picture of a wizard. It's used at over 100 colleges and universities, and it has spawned a semi-mythical secret society called The Knights of the Lambda Calculus, whose self-referential emblem celebrates the ability of the lambda calculus to do recursion. In 1980, Lambek made a great discovery: 14) Joachim Lambek, From lambda calculus to Cartesian closed categories, in To H. B. Curry: Essays on Combinatory Logic, Lambda Calculus and Formalism, eds. J. P. Seldin and J. Hindley, Academic Press, 1980, pp. 376-402. He showed that just as algebraic theories can be regarded as cartesian categories, theories formulated in the lambda calculus can be regarded as cartesian closed categories (or CCCs, for short). Lambek's discovery introduced a semantics for the lambda calculus, since it lets us to speak of "models" of theories formulated in the lambda calculus, just as we could for algebraic theories. In computer programming, the importance of a model is that it gives a picture of what a program actually accomplishes. A model in the category of Sets, for example, sends any program to an actual function between sets. There's no way to list all the interesting references to CCCs and the lambda-calculus, but here are some online places to get going on them, starting out easy and working up to the harder ones: 15) Wikipedia, Lambda calculus, available at http://en.wikipedia.org/wiki/Lambda_calculus 16) Mark Chu-Carroll, Lambda calculus, available at http://goodmath.blogspot.com/2006/06/lamda-calculus-index.html Mark Chu-Carroll, Category theory, available at http://scienceblogs.com/goodmath/goodmath/category_theory/ 17) Peter Selinger, Lecture notes on the lambda calculus, available at http://www.mscs.dal.ca/~selinger/papers.html#lambdanotes 18) Phil Scott, Some aspects of categories in computer science, available at http://www.site.uottawa.ca/~phil/papers/handbook.ps and here's a classic: 19) Joachim Lambek and Phil Scott, Introduction to Higher Order Categorical Logic, volume 7 of Cambridge Studies in Advanced Mathematics, Cambridge U. Press, 1986. Dolan and Trimble are not the first to study the relation between games and categories. In the 1970s, Conway invented a wonderful theory of games and surreal numbers: 20) John H. Conway, On Numbers and Games, Academic Press, New York, 1976. Second edition: A. K. Peters, Wellesley, Massachusetts, 2001. 21) Elwyn Berlekamp, John H. Conway, Richard Guy, Winning Ways, vols. 1-2, Aadmic Press, New York, 1982. Second edition, vols. 1-4, A. K. Peters, Wellelsey, Massachusetts, 2001-2004. 22) Dierk Schleicher and Michael Stoll, An introduction to Conway's games and numbers, available as math.CO/0410026. In 1977, Joyal modified Conway's work a bit and related it explicitly to category theory: 23) Andre Joyal, Remarques sur la theorie des jeux a deux personnes, Gazette des Sciences Mathematiques du Quebec, Vol I no 4 (1977), 46-52. For an online version in English, try: 24) Andre Joyal, trans. Robin Houston, Remarks on the theory of two-person games, 2003. Available at http://www.ma.man.ac.uk/~rhouston/Joyal-games.ps I don't know the subsequent history very well - I'm no expert on any of this stuff! - but by 1990 Martin Hyland was giving lectures on Conway games and linear logic, and I think this triggered a lot of work on "game semantics" for logic, where propositions are interpreted as games and proofs are winning strategies: 25) Samson Abramsky and Radha Jagadeesan, Games and full completeness for multiplicative linear logic, Journal of Symbolic Logic, 59 (1994), 543 - 574. Also available at http://citeseer.ist.psu.edu/564168.html 26) Martin Hyland and C.-H. L. Ong, Fair games and full completeness for multiplicative linear logic without the MIX-rule, available at http://citeseer.ist.psu.edu/hyland93fair.html For a good introduction to all this work, try these: 27) Robin Houston, Categories of Games, M.Sc. thesis, U. Manchester, 2003. Available at http://www.cs.man.ac.uk/~houstorx/msc.pdf Robin Houston, Mathematics of Games, continuation report, U. Manchester, 2004. Available at http://www.cs.man.ac.uk/~houstorx/continuation.pdf Finally, for more on categories, intuitionistic logic, and linear logic, see "week227". ---------------------------------------------------------------------- Previous issues of "This Week's Finds" and other expository articles on mathematics and physics, as well as some of my research papers, can be obtained at http://math.ucr.edu/home/baez/ For a table of contents of all the issues of This Week's Finds, try http://math.ucr.edu/home/baez/twfcontents.html A simple jumping-off point to the old issues is available at http://math.ucr.edu/home/baez/twfshort.html If you just want the latest issue, go to http://math.ucr.edu/home/baez/this.week.html From rrosebru@mta.ca Mon Oct 23 21:00:50 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 23 Oct 2006 21:00:50 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1Gc9fO-00021w-R4 for categories-list@mta.ca; Mon, 23 Oct 2006 20:57:14 -0300 Date: Mon, 23 Oct 2006 13:59:25 -0700 From: John Baez To: categories Subject: categories: cartesian closed categories and holodeck games Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 27 Dominic Hughes writes: > This "backtracking game" characterisation has been known since around > '93-'94, in the work of Hyland and Ong .... Thanks for filling me in on the history! I apologize to everyone whose work I slighted in "week240". I've tried to update the web version to more accurately say who did what first: http://math.ucr.edu/home/baez/week240.html People may also be interested in joining the discussion here: http://golem.ph.utexas.edu/category/2006/10/classical_vs_quantum_computati_3.html#comments Best, jb From rrosebru@mta.ca Mon Oct 23 21:00:50 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 23 Oct 2006 21:00:50 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1Gc9gH-000278-HK for categories-list@mta.ca; Mon, 23 Oct 2006 20:58:09 -0300 Date: Mon, 23 Oct 2006 13:53:52 +0100 From: Monika Seisenberger MIME-Version: 1.0 To: CALCO 2007 Subject: categories: 1cfc: CALCO-jnr (Conference on Algebra and Coalgebra in Computer Science), Bergen, Norway Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 28 [Apologies for multiple copies] !!! PLEASE FORWARD TO PHD STUDENTS AND YOUNG RESEARCHERS !!! *------------------------------------------------------------------* * 1st call for contributions * * * * CALCO-jnr 2007 * * * * CALCO-jnr: CALCO Young Researchers Workshop * * August 20, 2007, Bergen, Norway * * * * * * part of * * 2nd Conference on Algebra and Coalgebra in Computer Science * * August 20-24, 2007, Bergen, Norway * * * *------------------------------------------------------------------* * Abstract submission: April 10, 2007 * * Author notification: April 30, 2007 * * Final abstract due: May 16, 2007 * * Full paper submission: September 30, 2007 * *------------------------------------------------------------------* * http://www.ii.uib.no/calco07/ * *------------------------------------------------------------------* CALCO 2007 will be preceded by the CALCO Young Researchers Workshop, CALCO-jnr, dedicated to presentations by PhD students and young researchers at the beginning of their careers. CALCO brings together researchers and practitioners to exchange new results related to foundational aspects and both traditional and emerging uses of algebras and coalgebras in computer science. The study of algebra and coalgebra relates to the data, process and structural aspects of software systems. This is a high-level, bi-annual conference formed by joining the forces and reputations of CMCS (the International Workshop on Coalgebraic Methods in Computer Science), and WADT (the Workshop on Algebraic Development Techniques). The first, and very successful, CALCO conference took place 2005 in Swansea, Wales. The second event will take place 2007 in Bergen, Norway. The CALCO Young Researchers Workshop, CALCO-jnr, is a CALCO satellite workshop dedicated to presentations by PhD students and by those who have completed their doctoral studies within the past few years. Attendance at the workshop is open to all - it is anticipated that many CALCO conference participants will want to attend the CALCO-jnr workshop (and vice versa). CALCO-jnr presentations will be selected according to originality, significance, and general interest, on the basis of submitted 2-page abstracts, by the organisers. A booklet with the abstracts of the accepted presentations will be available at the workshop. After the workshop, the author(s) of each presentation will be invited to submit a full 10-15 page paper on the same topic. They will also be asked to write (anonymous) reviews of papers submitted by other authors on related topics. Additional reviewing and the final selection of papers will be carried out by the CALCO-jnr PC. The volume of selected papers from the workshop will be published as a Department of informatics, University of Bergen, technical report, and it will also be made available in an open access database searchable from http://oaister.umdl.umich.edu/o/oaister/. Authors will retain copyright, and are also encouraged to disseminate the results reported at CALCO-jnr by subsequent publication elsewhere. Topics of Interest ------------------ The CALCO Young Researchers Workshop will invite submissions on the same topics as the CALCO conference: reporting results of theoretical work on the mathematics of algebras and coalgebras, the way these results can support methods and techniques for software development, as well as experience with the transition of resulting technologies into industrial practice. In particular, the workshop will encourage submissions included or related to the topics listed below. * Abstract models and logics - Automata and languages, - Categorical semantics, - Modal logics, - Relational systems, - Graph transformation, - Term rewriting, - Adhesive categories * Specialised models and calculi - Hybrid, probabilistic, and timed systems, - Calculi and models of concurrent, distributed, mobile, and context-aware computing, - General systems theory and computational models (chemical, biological, etc) * Algebraic and coalgebraic semantics - Abstract data types, - Inductive and coinductive methods, - Re-engineering techniques (program transformation), - Semantics of conceptual modelling methods and techniques, - Semantics of programming languages * System specification and verification - Algebraic and coalgebraic specification, - Formal testing and quality assurance, - Validation and verification, - Generative programming and model-driven development, - Models, correctness and (re)configuration of hardware/middleware/architectures, - Process algebra Important Dates (all dates in 2007) ----------------------------------- 10 April Firm deadline for 2-page abstract submission 30 April Notification of abstract selection decision 16 May Final version of abstract due Early registration ends 20 August CALCO Young Researchers Workshop 21-24 August CALCO conference technical program 30 September Firm deadline for 10-15 page paper submission 15 November Notification of paper selection decision 30 November Final version of paper due Program Committee ----------------- * Magne Haveraaen, University of Bergen, Norway http://www.ii.uib.no/~magne/ * John Power, University of Edinburgh, UK http://www.inf.ed.ac.uk/people/staff/John_Power.html * Monika Seisenberger, University of Wales Swansea, UK http://www.cs.swan.ac.uk/~csmona/ -- http://www.ii.uib.no/calco07/ From rrosebru@mta.ca Mon Oct 23 21:00:50 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 23 Oct 2006 21:00:50 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1Gc9ec-0001y1-3h for categories-list@mta.ca; Mon, 23 Oct 2006 20:56:26 -0300 Date: Mon, 23 Oct 2006 10:39:12 -0700 (PDT) From: Dominic Hughes To: categories Subject: categories: Re: cartesian closed categories and holodeck games 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: 29 This "backtracking game" characterisation has been known since around '93-'94, in the work of Hyland and Ong: M. Hyland and L. Ong. On full abstraction for PCF. Information and Computation, Volume 163, pp. 285-408, December 2000. [Under review for 6 years!] ftp://ftp.comlab.ox.ac.uk/pub/Documents/techpapers/Luke.Ong/pcf.ps.gz (PCF is an extension of typed lambda calculus.) My D.Phil. thesis extended the lambda calculus (free CCC) characterisation to second-order, published in: Games and Definability for System F. Logic in Computer Science, 1997 http://boole.stanford.edu/~dominic/papers/ To characterise the free CCC on an *arbitrary* set {Z,Y,X,...} of generators (rather than a single generator, as you discuss), one simply adds the following Copycat Condition: (*) Whenever first player plays an occurrence of X, the second player must play an occurrence of X. [Try it: see how X -> Y -> X has just one winning strategy.] Although the LICS'97 paper cited above appears to be the first place the Copycat Condition appears in print, I like to think it was already understood at the time by people working in the area. Technically speaking, winning strategies correspond to eta-expanded beta-normal forms. See pages 5-7 of my thesis for an informal description of the correspondence. It sounds like you've reached the point of trying to figure out how composition should work. Proving associativity is fiddly. Hyland and Ong give a very elegant treatment, via a larger CCC of games in which *both* players can backtrack. The free CCC subcategory is carved out as the so-called *innocent* strategies. This composition is almost identical to that presented by Coquand in: A semantics of evidence for classical arithmetic. Thierry Coquand. Proceedings of the CLICS workshop, Aarhus, 1992. Dominic PS A game-theoretic characterisation with an entirely different flavour (winning strategies less "obviously" corresponding to eta-long beta-normal forms) is: Abramsky, S., Jagadeesan, R. and Malacaria, P., Full Abstraction for PCF. Info. & Comp. 163 (2000), 409-470. http://web.comlab.ox.ac.uk/oucl/work/samson.abramsky/pcf.pdf [Announced concurrently with Hyland-Ong, around '93-'94.] On Sun, 22 Oct 2006, John Baez wrote: > Dear Categorists - > > This contains a popularization of Dolan and Trimble's work on > game theory and the free cartesian closed category on one object. > It also has links to more detais. > > Best, > jb > > .................................................................... > > Also available as http://math.ucr.edu/home/baez/week240.html > From rrosebru@mta.ca Mon Oct 23 22:23:09 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 23 Oct 2006 22:23:09 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GcAx8-0001HC-NF for categories-list@mta.ca; Mon, 23 Oct 2006 22:19:38 -0300 Date: Fri, 20 Oct 2006 16:14:09 +0100 From: Miles Gould To: categories@mta.ca Subject: categories: Decomposability of monads Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: RO X-Status: X-Keywords: X-UID: 30 Dear categorists, The free ring monad (on, say, Set) may be decomposed into the free monoid monad and the free abelian group monad, connected by a distributive law. Is it known which monads can be decomposed into "simpler" ones (whatever that means), connected by distributive laws? I'm particularly interested in the case of monads describing algebraic theories. Thanks, Miles -- Amazing! You type random strings of letters, and it does what you want! -- Rhiannon Mogridge, on vi From rrosebru@mta.ca Tue Oct 24 09:35:08 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 24 Oct 2006 09:35:08 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GcLMO-00026c-QL for categories-list@mta.ca; Tue, 24 Oct 2006 09:26:24 -0300 Date: Mon, 23 Oct 2006 23:24:23 -0700 From: John Baez To: categories Subject: categories: Re: cartesian closed categories and holodeck games Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 31 On Mon, Oct 23, 2006 at 11:15:04PM -0700, Vaughan Pratt wrote: > In your Week 240 post to categories, you said > > > The moral of this game is that all systematic methods for picking > > an element of (X^X)^(X^X) for an unknown set X can be written > > using the lambda calculus. > What is unsystematic about the contagious-fixpoint functional? This is the > functional that maps those functions that have any fixpoints to the identity > function (the function that makes every element a fixpoint) and functions > without fixpoints to themselves (thus preserving the absence of fixpoints). Whoops. I got carried away there. Later I admitted that by "systematic method" I just meant "definable using the lambda calculus". I'll have to fix this. Thanks! Best, jb From rrosebru@mta.ca Tue Oct 24 09:35:09 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 24 Oct 2006 09:35:09 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GcLLh-00022L-Oa for categories-list@mta.ca; Tue, 24 Oct 2006 09:25:42 -0300 To: categories Subject: categories: Re: cartesian closed categories and holodeck games Date: Mon, 23 Oct 2006 23:15:04 -0700 From: Vaughan Pratt Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 32 Hi, John, In your Week 240 post to categories, you said > The moral of this game is that all systematic methods for picking > an element of (X^X)^(X^X) for an unknown set X can be written > using the lambda calculus. What is unsystematic about the contagious-fixpoint functional? This is the functional that maps those functions that have any fixpoints to the identity function (the function that makes every element a fixpoint) and functions without fixpoints to themselves (thus preserving the absence of fixpoints). It's a perfectly good functional that is equally well defined for all sets X, its statement in no way depends on X, and conceptually the concept of contagious fixpoints is even intuitively natural, but how do you write it using the lambda calculus? Many more examples in this vein at JPAA 128, 33-92 (Pare and Roman, Dinatural numbers, 1998). The above is the case K = {0} of Freyd's (proper) class of examples. Vaughan From rrosebru@mta.ca Tue Oct 24 21:44:53 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 24 Oct 2006 21:44:53 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GcWpI-0002G5-Va for categories-list@mta.ca; Tue, 24 Oct 2006 21:41:01 -0300 Date: Tue, 24 Oct 2006 19:58:57 +0200 Content-Type: text/plain; charset=US-ASCII; format=flowed Subject: categories: laws and equations From: Enrico Vitale To: categories@mta.ca Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 33 Dear Colleagues, Recently, Bill Lawvere proposed parallel pairs of morphisms in an algebraic theory as the categorical concept of "equational law". We have just observed that this is, for many sorted theories, the first definition that makes sense! For example, the following variant of Birkhoff's Variety Theorem holds for many-sorted algebras: a full subcategory is equationally presentable (in Bill's sense) iff it is closed under products, subobjects, regular quotients and directed unions. If equation is "traditionally" understood as a pair of terms (elements of a free algebra of the given signature) of the same sort, then Birkhoff's theorem is not true: Example. Consider algebras on two sorts (say, a,b) with no operations - that is, consider the category Set x Set. Take the full subcategory V of all objects (A,B) such that either A is empty or B has at most 1 element. This is an HSP subcategory of Set x Set, but there does not exist any equation that only works with one of the sorts such that all the objects of V satisfy it. But in the theory which is a free completion of the discrete category {a,b} under finite products the parallel pair of projections p_2, p_3: a x b x b -> b specifies V. If, on the other hand, equations are understood as pairs of terms together with a many-sorted set of variables (encoding the universal quantification), the following example demonstrates that we are beyond the realm of finitary logic: Example. Consider algebras on infinitely many sorts with no operations. The full subcategory of all objects which are either subobjects of the terminal object, or have all but finitely many sorts empty, is an HSP class. But it is not closed under directed unions, and thus cannot be described in finitary logic. Best regards Jiri Adamek and Enrico Vitale From rrosebru@mta.ca Thu Oct 26 10:34:33 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 26 Oct 2006 10:34:33 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1Gd5EZ-0007Eu-6s for categories-list@mta.ca; Thu, 26 Oct 2006 10:25:23 -0300 Date: Thu, 26 Oct 2006 10:56:40 +0200 From: Andrej Bauer MIME-Version: 1.0 To: categories@mta.ca Subject: categories: Characterization of integers as a commutative ring with unit Content-Type: text/plain; charset=ISO-8859-2; format=flowed Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: RO X-Status: X-Keywords: X-UID: 34 For the purposes of defining the data structure of integers in a Coq-like system, I am looking for an _algebraic_ characterization of integers Z as a commutative ring with unit. (The one-element ring is a ring.) Some possible characterizations which I don't much like: 1) Z is the free group generated by one generator. I want the ring structure, not the group structure. 2) Z is the free ring generated by the semiring of natural numbers. This just translates the problem to characterization of the semiring of natural numbers. 3) Z is the initial non-trivial ring. This is no good because "non-trivial" is an inequality "0 =/= 1" rather than an equality. 4) Let R be the free commutative ring with unit generated by X. Then Z is the image of the homomorphism R --> R which maps X to 0. This is just ugly and there must be something better. I feel like I am missing something obvious. Surely Z appears as a prominent member of the category of commutative rings with unit, does it not? Best regards, Andrej From rrosebru@mta.ca Thu Oct 26 21:39:04 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 26 Oct 2006 21:39:04 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GdFg2-0002qY-4p for categories-list@mta.ca; Thu, 26 Oct 2006 21:34:26 -0300 Date: Thu, 26 Oct 2006 11:21:55 -0400 From: Fred E.J.Linton To: categories@mta.ca Subject: categories: Re: Characterization of integers as a commutative ring with unit Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 35 What is not to like about Z being the initial ring-with-unit? No need to impose 0 {/ne} 1 -- it follows. Cheers, -- Fred. From rrosebru@mta.ca Thu Oct 26 21:39:05 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 26 Oct 2006 21:39:05 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GdFhE-0002wc-Ta for categories-list@mta.ca; Thu, 26 Oct 2006 21:35:41 -0300 Date: Thu, 26 Oct 2006 22:26:17 +0200 From: Andrej Bauer MIME-Version: 1.0 To: categories@mta.ca Subject: categories: Re: Characterization of integers as a commutative ring with unit Content-Type: text/plain; charset=ISO-8859-2; format=flowed Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 36 I would like to thank all 11 people who pointed out that Z _is_ the initial unital ring. I forgot to take into account that homomorphisms of unital rings map 1 to 1, so the trivial ring is not initial (and Z is). Thank you for being kind even though I asked a trivial questions. Andrej From rrosebru@mta.ca Thu Oct 26 21:39:05 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 26 Oct 2006 21:39:05 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GdFef-0002lZ-Jl for categories-list@mta.ca; Thu, 26 Oct 2006 21:33:01 -0300 Mime-Version: 1.0 (Apple Message framework v752.2) Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed To: categories@mta.ca Content-Transfer-Encoding: 7bit From: Steve Vickers Subject: categories: Re: Characterization of integers as a commutative ring with unit Date: Thu, 26 Oct 2006 15:48:52 +0100 Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 37 Dear Andrej, Z is the initial ring with unit. (Doesn't matter whether you require commutativity.) It's not clear to me why you felt the need to say "non-trivial" in (3). Regards, Steve. On 26 Oct 2006, at 09:56, Andrej Bauer wrote: > For the purposes of defining the data structure of integers in a > Coq-like system, I am looking for an _algebraic_ characterization of > integers Z as a commutative ring with unit. (The one-element ring is a > ring.) > > Some possible characterizations which I don't much like: > > 1) Z is the free group generated by one generator. I want the ring > structure, not the group structure. > > 2) Z is the free ring generated by the semiring of natural numbers. > This > just translates the problem to characterization of the semiring of > natural numbers. > > 3) Z is the initial non-trivial ring. This is no good because > "non-trivial" is an inequality "0 =/= 1" rather than an equality. > > 4) Let R be the free commutative ring with unit generated by X. Then Z > is the image of the homomorphism R --> R which maps X to 0. This is > just > ugly and there must be something better. > > I feel like I am missing something obvious. Surely Z appears as a > prominent member of the category of commutative rings with unit, > does it > not? > > Best regards, > > Andrej > > From rrosebru@mta.ca Thu Oct 26 21:39:38 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 26 Oct 2006 21:39:38 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GdFkJ-0003CX-Je for categories-list@mta.ca; Thu, 26 Oct 2006 21:38:51 -0300 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Subject: categories: RE: Characterization of integers as a commutative ring with unit Date: Fri, 27 Oct 2006 10:01:28 +1000 From: "Stephen Lack" To: Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: RO X-Status: X-Keywords: X-UID: 38 Dear Andrej, I take it by unit you mean identity (1). Then in the category of = commutative rings with 1, you presumably want the 1 to be preserved. So Z is = initial, and the trivial ring is terminal. On the category of commutative rings without 1 (i.e. not necessarily = having a 1), there is a monoidal structure, formed by tensoring the underlying = abelian groups, and equipping this with the usual multiplication. (This would be the = coproduct in the category of commutative rings with 1, but it is not the coproduct = here.) If you allow yourself to use this extra structure, then Z is = characterized as the unit object for the tensor product. The category of commutative rings with 1, but homomorphisms not = necessarily=20 preserving it, seems rather unnatural, but for what it's worth, the = tensor=20 product of the previous paragraph restricts to this category, and so can = be used to characterize Z once again. Regards, Steve Lack. -----Original Message----- From: cat-dist@mta.ca on behalf of Andrej Bauer Sent: Thu 10/26/2006 6:56 PM To: categories@mta.ca Subject: categories: Characterization of integers as a commutative ring = with unit =20 For the purposes of defining the data structure of integers in a Coq-like system, I am looking for an _algebraic_ characterization of integers Z as a commutative ring with unit. (The one-element ring is a ring.) Some possible characterizations which I don't much like: 1) Z is the free group generated by one generator. I want the ring structure, not the group structure. 2) Z is the free ring generated by the semiring of natural numbers. This just translates the problem to characterization of the semiring of natural numbers. 3) Z is the initial non-trivial ring. This is no good because "non-trivial" is an inequality "0 =3D/=3D 1" rather than an equality. 4) Let R be the free commutative ring with unit generated by X. Then Z is the image of the homomorphism R --> R which maps X to 0. This is just ugly and there must be something better. I feel like I am missing something obvious. Surely Z appears as a prominent member of the category of commutative rings with unit, does it not? Best regards, Andrej From rrosebru@mta.ca Fri Oct 27 09:39:37 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 27 Oct 2006 09:39:37 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GdQwe-0004wl-PW for categories-list@mta.ca; Fri, 27 Oct 2006 09:36:20 -0300 From: "George Janelidze" To: Subject: categories: Re: Characterization of integers as a commutative ring with unit Date: Fri, 27 Oct 2006 11:29:29 +0200 MIME-Version: 1.0 Content-Type: text/plain;charset="iso-8859-1" Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 39 Dear Steve, Thank you for your kind words. I have mentioned my paper with Aurelio only because there are too many details that I could not describe in a brief email message. But if it comes to "...I should have mentioned explicitly your work with Aurelio...", I can say the same about myself: I should have mentioned your (very important!) paper [A. Carboni, S. Lack, and R. F. C. Walters, Introduction to extensive and distributive categories, Journal of Pure and Applied Algebra 84, 1993, 145-158] and Bill Lawvere's original question about commutative rings and many other things that Aurelio did mention in his CT1999 talk. (In any case, I hope you do not assume that I know what "Coq" is, do you?) Yours- George ----- Original Message ----- From: "Stephen Lack" To: "George Janelidze" ; Cc: "Andrej Bauer" Sent: Friday, October 27, 2006 9:51 AM Subject: RE: categories: RE: Characterization of integers as a commutative ring with unit Dear George, I remember well your lovely talk and paper, and indeed I had this in mind when I wrote. I shouldn't have used the words "extra structure" (in fact I said this really because I don't know what "Coq" is) and I should have mentioned explicitly your work with Aurelio. Sorry. Steve. From rrosebru@mta.ca Fri Oct 27 09:39:37 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 27 Oct 2006 09:39:37 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GdQvr-0004sO-TX for categories-list@mta.ca; Fri, 27 Oct 2006 09:35:31 -0300 Content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain;charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Subject: categories: RE: Characterization of integers as a commutative ring with unit Date: Fri, 27 Oct 2006 17:51:43 +1000 From: "Stephen Lack" To: Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 40 Dear George, I remember well your lovely talk and paper, and indeed I had this in mind when I wrote. I shouldn't have used the words "extra structure" (in fact I said this really because I don't know what "Coq" is) and I=20 should have mentioned explicitly your work with Aurelio. Sorry. Steve. -----Original Message----- From: George Janelidze [mailto:janelg@telkomsa.net] Sent: Fri 10/27/2006 5:23 PM To: categories@mta.ca; Stephen Lack Cc: Andrej Bauer Subject: Re: categories: RE: Characterization of integers as a = commutative ring with unit =20 Dear Steve, In your message of October 27 to Andrej Bauer you say: "On the category of commutative rings without 1 (i.e. not necessarily = having a 1), there is a monoidal structure, formed by tensoring the underlying = abelian groups, and equipping this with the usual multiplication. (This would be the coproduct in the category of commutative rings with 1, but it is not the coproduct here.) If you allow yourself to use this extra structure, then Z is = characterized as the unit object for the tensor product." But no, this is not an extra structure, which, explained properly, has = some obvious and some non-obvious aspects - see [A. Carboni and G. Janelidze, Smash product of pointed objects in lextensive categories, Journal of = Pure and Applied Algebra 183, 2003, 27-43] (I also gave a talk about this = called "Abstract commutative algebra I: Associativity of tensor (=3Dco-smash) products (12.12.2001)" on Australian Category Seminar). In simple words: tensor product of commutative rings of A and B without = 1 is nothing but their co-smash product (=3Dthe kernel of the canonical = morphism A+B ---> AxB), and therefore Z is the unit object of the smash product. = This observation itself might be infinitely old - simply because it is = simple! But the reason of the associativity of the smash product and the very definition of associativity is a different story (e.g. the associativity isomorphism itself is not an extra structure as it happens in a general monoidal category). Let me also point out that the co-smash product is to be investigated in = any semi-abelian category. Note that: In any semi-abelian category the canonical morphism A+B ---> AxB is a regular=3Dnormal epimorphism for each two objects A and B. Therefore the co-smash product of A and B is not merely its kernel - IT IS THE MEASURE = OF NONADDITIVITY. And you can define an abelian category as a semi-abelian category with trivial co-smash products. In this sense the category CR = of commutative rings without 1 is "very nonabelian" - since instead of = having trivial co-smash products it has a unit object for the co-smash product (this is like a monoid with zero versus a semigroup with zero and zero multiplication). On the other hand this makes CR "almost abelian" since = it is one of the very few semi-abelian categories where the co-smash = product is associative (it is not the case for groups, not for non-commutative = rings, etc.). George Janelidze From rrosebru@mta.ca Fri Oct 27 09:39:37 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 27 Oct 2006 09:39:37 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GdQv6-0004o1-Gq for categories-list@mta.ca; Fri, 27 Oct 2006 09:34:44 -0300 From: "George Janelidze" To: , Subject: categories: Re: Characterization of integers as a commutative ring with unit Date: Fri, 27 Oct 2006 09:23:35 +0200 MIME-Version: 1.0 Content-Type: text/plain;charset="iso-8859-1" Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 41 Dear Steve, In your message of October 27 to Andrej Bauer you say: "On the category of commutative rings without 1 (i.e. not necessarily having a 1), there is a monoidal structure, formed by tensoring the underlying abelian groups, and equipping this with the usual multiplication. (This would be the coproduct in the category of commutative rings with 1, but it is not the coproduct here.) If you allow yourself to use this extra structure, then Z is characterized as the unit object for the tensor product." But no, this is not an extra structure, which, explained properly, has some obvious and some non-obvious aspects - see [A. Carboni and G. Janelidze, Smash product of pointed objects in lextensive categories, Journal of Pure and Applied Algebra 183, 2003, 27-43] (I also gave a talk about this called "Abstract commutative algebra I: Associativity of tensor (=co-smash) products (12.12.2001)" on Australian Category Seminar). In simple words: tensor product of commutative rings of A and B without 1 is nothing but their co-smash product (=the kernel of the canonical morphism A+B ---> AxB), and therefore Z is the unit object of the smash product. This observation itself might be infinitely old - simply because it is simple! But the reason of the associativity of the smash product and the very definition of associativity is a different story (e.g. the associativity isomorphism itself is not an extra structure as it happens in a general monoidal category). Let me also point out that the co-smash product is to be investigated in any semi-abelian category. Note that: In any semi-abelian category the canonical morphism A+B ---> AxB is a regular=normal epimorphism for each two objects A and B. Therefore the co-smash product of A and B is not merely its kernel - IT IS THE MEASURE OF NONADDITIVITY. And you can define an abelian category as a semi-abelian category with trivial co-smash products. In this sense the category CR of commutative rings without 1 is "very nonabelian" - since instead of having trivial co-smash products it has a unit object for the co-smash product (this is like a monoid with zero versus a semigroup with zero and zero multiplication). On the other hand this makes CR "almost abelian" since it is one of the very few semi-abelian categories where the co-smash product is associative (it is not the case for groups, not for non-commutative rings, etc.). George Janelidze From rrosebru@mta.ca Fri Oct 27 09:39:37 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 27 Oct 2006 09:39:37 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GdQuV-0004km-PS for categories-list@mta.ca; Fri, 27 Oct 2006 09:34:07 -0300 Date: Thu, 26 Oct 2006 21:09:40 -0400 (EDT) From: Josh Nichols-Barrer To: categories@mta.ca Subject: categories: Re: Characterization of integers as a commutative ring with unit MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 42 Hi Andrej, Isn't Z the initial /ring/? 0 isn't initial, as 0=1 holds only in itself (Spec Z is the terminal scheme, Spec 0 the empty scheme, so the initial scheme). -Josh On Thu, 26 Oct 2006, Andrej Bauer wrote: > For the purposes of defining the data structure of integers in a > Coq-like system, I am looking for an _algebraic_ characterization of > integers Z as a commutative ring with unit. (The one-element ring is a > ring.) > > Some possible characterizations which I don't much like: > > 1) Z is the free group generated by one generator. I want the ring > structure, not the group structure. > > 2) Z is the free ring generated by the semiring of natural numbers. This > just translates the problem to characterization of the semiring of > natural numbers. > > 3) Z is the initial non-trivial ring. This is no good because > "non-trivial" is an inequality "0 =/= 1" rather than an equality. > > 4) Let R be the free commutative ring with unit generated by X. Then Z > is the image of the homomorphism R --> R which maps X to 0. This is just > ugly and there must be something better. > > I feel like I am missing something obvious. Surely Z appears as a > prominent member of the category of commutative rings with unit, does it > not? > > Best regards, > > Andrej > > From rrosebru@mta.ca Sun Oct 29 19:17:44 2006 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 29 Oct 2006 19:17:44 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GeJnS-0003nS-70 for categories-list@mta.ca; Sun, 29 Oct 2006 19:10:30 -0400 From: Peter Freyd Date: Sun, 29 Oct 2006 09:57:15 -0500 To: categories@mta.ca Subject: categories: this week's nonsense MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: RO X-Status: X-Keywords: X-UID: 43 The math advisers from CalTech had a little fun on Friday's episode of "Numb3rs". The Mathematician and the Physicist are looking at a dead person's notebook. They're dead serious. MATHEMATICIAN: it's a category-based approach to I don't know what, but it's a forcasting system. Right?. It's very sophisticated. PHYSICIST: [In awe at what he sees] Oh, no, no. no. This is more than sophisticated. You know what this reminds me of? A topos approach to Bach's music. MATHEMATICIAN: I said: very sophisticated. FBI AGENT: Yes -- you did. Be assured that neither the page we see from the notebook nor the rest of the program had anything to do with categories, topoi or Bach. From rrosebru@mta.ca Sun Oct 29 19:17:44 2006 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 29 Oct 2006 19:17:44 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GeJjR-0003TB-B6 for categories-list@mta.ca; Sun, 29 Oct 2006 19:06:21 -0400 Date: Sat, 28 Oct 2006 16:13:55 -0400 (EDT) From: F W Lawvere To: categories@mta.ca Subject: categories: Re: Lawvere-Metrics and Banach Spaces MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 44 Dear colleagues, Here are a few thoughts on the recent discussion of metric spaces: The whole general theory of enriched categories should in particular be focused on metric spaces and relatives. For example, enriched functor categories have a uniform definition, which in the case of metric spaces yields the sup metric. Of course, this does involve subtracting distances (but not in the sense of abelian groups, rather subtraction is the hom in the enriching category itself.) Dividing distances would be a dimensional mistake: the enriching category should be visualized as a possible conception of actual physical distance (not of numbers that might measure it), the addition and ordering being independent of any choice of unit. The same idea applies to the equivalent notion of nearness, as appropriate to the intrinsic measuring of convex sets (n(x,y)n(y,z) less than or equal to n(x,z), often complicated by using d = exp(-n/u) where u is a unit). With either point of view, there is no further definable operation on distance with respect to which to "divide". But on monoidal functors instead, there is of course the operation of composition. Not only categorists are enlightened by lax monoidal functors and such; subadditive functions are familiar to analysts. In their 1965 paper Eilenberg and Kelly included a definite "laxity" in the definition of monoidal (or closed) functor, since the goal was to induce good 2-functors between categories of enriched categories. For example, why should an additive category ever be considered as an ordinary category? - because the functor from abelian groups to sets is accompanied by a comparison transformation between tensor product and cartesian product. In other cases where the analogous comparison is an isomorphism, one might speak of strict monoidal functors. To deal with the fibered category of metric spaces whose morphisms have general Lipschitz constants (not just less than or equal to 1), the base monoid is conceived as acting by strict monoidal functors on distances. In particular, the hom of Banach spaces is normed in THIS monoid, not in the original one. The more general monoidal endofunctors yield much more refined notions of Lipschitz (and more refined notions of Hausdorff dimension) wherein they replace the special numbers as indices. But indices occur in another way: The Orlicz family forms a more natural parameterizable class of reflexive Banach spaces than the Lebesgue family. Here we encounter the important fact that the adjoint of a monoidal functor is not usually monoidal. The square root function is monoidal, but squaring is not. This suggests inverting the system of parameterizing the Lebesgue spaces (or more generally), so that the parameter for Hilbert space is the square root function, not 2. Since the origin of Hilbert space is in the Pythagorean metric on the product of two metric spaces, it is suggested to consider an infinite family of products. The first product that occurs to a category theorist for the category of enriched categories with given value category, is the tensor product which extends the given tensor product in the value category. This leads to the "sum" metric on the product of two metric spaces (this functor's right adjoint is the sup metric on distance-decreasing functions as mentioned above). Of course, there is also the cartesian product which in our case leads to the "max" metric. Infinite versions of these two products are a staple of analysis, but so are many intermediate products, which, as suggested above, should be parameterized by the monoidal endofunctors of the category of distance-values. Computational aspects might be approached in the following two traditional ways, which could even be combined. Paul Taylor's ascending reals seem to be related to the study of metric spaces in a topos, where the object of semi-continuous or one-sided Dedekind reals, the inf-completion of the non-negative rationals, is often the appropriate recipient of norms for continuously varying Banach spaces (even though the scalar multipliers remain the two-sided continuous Dedekind reals). The other, even older, idea was to replace closed sets by "located" sets which are actually Lipschitz functions, that is, objects in the enriched functor category that plays the role of the power set in generalized logic. Bill Lawvere ************************************************************ 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 Sun Oct 29 19:17:44 2006 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 29 Oct 2006 19:17:44 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GeJla-0003fb-Vi for categories-list@mta.ca; Sun, 29 Oct 2006 19:08:35 -0400 Date: Sat, 28 Oct 2006 22:58:44 -0400 (EDT) From: flinton@wesleyan.edu To: categories@mta.ca MIME-Version: 1.0 Content-Type: text/plain;charset=UTF-8 Content-Transfer-Encoding: 8bit Subject: categories: Re: co-smash product (was: categories: Re: Characterization... Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: RO X-Status: X-Keywords: X-UID: 45 Remarking on George Janelidze's comment, > ... tensor product of commutative rings of A and B without 1 is > nothing but their co-smash product (=the kernel of the canonical > morphism A+B ---> AxB), and therefore Z is the unit object of the smash > product. This observation itself might be infinitely old - simply > because it is simple! Infinitely old the following isn't, but certainly the s.e.s. tensor product --> coproduct --> product made an appearance, for Boolean rngs (boolean algebras w/o unit), in my 1963 Columbia dissertation. Here -- that is, for Boolean rngs -- what's noteworthy is that the tensor product is the same, whether one thinks "as abelian groups, with induced rng structure," "as Z_2-modules, with induced rng structure," or "as the object that represents 'bilinear maps,' i.e., functions on the cartesian product that, for each choice of fixed member of either factor, are homomorphisms on the other factor." [That the third perspective is as valid as the first two comes about because of the idempotence -- xx=x -- of multiplication in Boolean rngs; it surely won't be valid for commutative rngs generally.] On another point, viz., George's comment, > ... co-smash product is associative ... not the case for groups ... what exactly are the relations among group-theoretic co-smash product, group-theoretic tensor product (in the spirit of Hassler Whitney's study from circa 1938 (the very year I was born!)), and group- theoretic commutator constructions? [I recall that Whitney's tensor product of two groups, though defined in terms of representing "bilinear maps," worked out to coincide with the usual tensor product of the groups' abelianizations.] Cheers, -- Fred From rrosebru@mta.ca Mon Oct 30 13:56:50 2006 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 30 Oct 2006 13:56:50 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GebGQ-0005QK-9Y for categories-list@mta.ca; Mon, 30 Oct 2006 13:49:34 -0400 Date: Mon, 30 Oct 2006 17:30:26 GMT From: Jeremy.Gibbons@comlab.ox.ac.uk To: categories@mta.ca Subject: categories: University of Oxford: Lectureships in Software Engineering Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 46 UNIVERSITY OF OXFORD Software Engineering Programme Kellogg College THREE UNIVERSITY LECTURERSHIPS IN SOFTWARE ENGINEERING Applications are invited for three new University Lecturerships in Software Engineering. The successful applicants will join the staff of the University's Software Engineering Programme in teaching and researching the application of scientific principles to the development of software systems. The salary will be on a scale up to GBP50,589 per annum. An advanced degree in a related subject, proven teaching ability, and a strong research record - of international standing - are all essential requirements. Applications are particularly welcome from those with expertise in software and systems security, service-oriented architectures, or model-driven development. The appointments will be associated with fellowships at Kellogg College, Oxford and the appointees will be members of the Governing Body of the college. The closing date for applications is 27th November 2006. For further information, including full details of the application procedure and selection criteria, see http://www.softeng.ox.ac.uk/jobs/ From rrosebru@mta.ca Tue Oct 31 19:19:17 2006 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 31 Oct 2006 19:19:17 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1Gf2kp-0000dP-DB for categories-list@mta.ca; Tue, 31 Oct 2006 19:10:47 -0400 Date: Tue, 31 Oct 2006 08:58:17 -0500 (EST) From: F W Lawvere To: categories@mta.ca Subject: categories: Amendment/Commentary 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: 47 Re: Commentary of Adjointness in Foundations in TAC Reprints Dear colleagues, I have taken advantage of the useful possibility for post-publication amendments to add two sentences to my commentary for the TAC Reprint no. 16, Adjointness in Foundations. Matias Menni has made several advances concerning the connection between tractability of proof theory and classical logic of the meta theory. His recent works contain important concepts and precise versions which update the formulations given in my commentary. Thanks to Bob Rosebrugh and Mike Barr. Bill Lawvere ************************************************************ 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 Tue Oct 31 19:19:17 2006 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 31 Oct 2006 19:19:17 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1Gf2lD-0000fL-EG for categories-list@mta.ca; Tue, 31 Oct 2006 19:11:11 -0400 Date: Tue, 31 Oct 2006 18:07:26 +0000 (GMT) From: "Prof. Peter Johnstone" To: Categories mailing list Subject: categories: Artin glueing for quasitoposes MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 48 Given a subobject of 1 in a topos, it's well known that one can `split' the topos into complementary open and closed subtoposes, and reconstruct the topos (up to equivalence) by applying Artin glueing to these two subtoposes. Hands up, all those of you who thought that the same thing works for quasitoposes ... I thought so! It isn't true, as I have just discovered. Certainly, given a strong subobject U >--> 1 in a quasitopos E, one can construct the `closed complement' of the open subquasitopos E/U, in exactly the same way as one does for a topos: let's denote it by C(U). It's also true that one has a `fringe functor' from E/U to C(U), and that one gets a comparison functor from E to the quasitopos obtained by glueing along this functor (again, the glueing construction works for quasitoposes just as it does for toposes). But, for this comparison to be an equivalence, one needs to know that the inverse image functors E --> E/U and E --> C(U) are (not just jointly faithful, but) jointly isomorphism-reflecting. And that can fail: I have a counterexample in a slice of the quasitopos of Frechet spaces (Elephant, A2.6.4(c). Has anyone noticed this failure before? If so, has anyone actually written it up? Peter Johnstone From rrosebru@mta.ca Tue Oct 31 19:19:17 2006 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 31 Oct 2006 19:19:17 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1Gf2jN-0000Vk-BR for categories-list@mta.ca; Tue, 31 Oct 2006 19:09:17 -0400 To: LiCS 2006 List From: Kreutzer + Schweikardt Subject: categories: LICS 2007 Call for Workshop Proposals Date: Tue, 31 Oct 2006 13:30:23 +0100 (CET) Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 49 LICS 2007 CALL FOR WORKSHOP PROPOSALS The Twenty-Second IEEE Symposium on Logic in Computer Science (LICS 2007) will be held in Wroclaw, Poland, July 10-14, 2007. It will be colocated with two other meetings: the International Colloquium on Automata, Languages, and Programming (ICALP'07) July 9-13, 2007, and also the European Logic Colloquium (ELC 2007), July 14-19. Workshops are planned for July 8, 9 and July 15 (possibly the afternoon of 14th). Detailed information can be found on the LICS 2007 webpage at http://www.informatik.hu-berlin.de/lics/lics07/ LICS workshops have traditionally been an important and exciting part of the program. They introduce either newest research in traditional areas of the LICS community, recent interdisciplinary and applied areas of general theory, or emerging directions that already have some substantial overlap with LICS community interests. Researchers and practitioners are invited to submit proposals for workshops on topics relating logic - broadly construed - to computer science or related fields. Typically, LICS workshops feature a mix of invited speakers and contributed presentations. LICS workshops do not produce formal proceedings. However, in the past there have been special issues of journals based in part on certain LICS workshops. Proposals should include: - A short scientific summary and justification of the proposed topic. This should include a discussion of the particular benefits of the topic to the LICS community. - A discussion of the proposed format and agenda. - Procedures for selecting participants and papers. - Expected number of participants. (This is important!) - Potential invited speakers. - Plans for dissemination (for example, special issues of journals). - For workshops of potential interest to ICALP participants, whether the workshop should be considered as a possible joint LICS/ICALP workshop. - Tell us the timeframe you would prefer: 1 day, 1.5 or 2 days, either before LICS (July 8,9) or after LICS (July 15). Alas, some overlap with either ICALP or ELC is inevitable. Proposals are due Nov. 15, 2006, and should be submitted electronically to: Philip Scott Workshops Chair, LICS 2007 phil@site.uottawa.ca Workshops will be chosen by a committee that consists of the LICS General Chair, LICS Workshop Chair, LICS 2007 PC Chair, and LICS 2007 Conference Chair. In the case of potential joint workshops, these will be discussed with colleagues from ICALP. A decision will be made by the end of November. From rrosebru@mta.ca Tue Oct 31 19:19:17 2006 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 31 Oct 2006 19:19:17 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1Gf2m3-0000jw-Qe for categories-list@mta.ca; Tue, 31 Oct 2006 19:12:03 -0400 Date: Tue, 31 Oct 2006 22:47:09 +0000 (GMT) From: "Prof. Peter Johnstone" To: Categories mailing list Subject: categories: Re: Artin glueing for quasitoposes MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 50 Here are the details of the counterexample mentioned in my earlier e-mail, for anyone who wants to see them. Let E be the quasitopos of Frechet spaces (called subsequential spaces in my paper "On a topological topos"): all you need to know about this category is that it contains the category S of sequential spaces as a full subcategory, closed under limits (not under all colimits, but in fact all colimits that occur in the following discussion are preserved). All the action takes place inside S. Let N be the discrete space of natural numbers, and N+ its one-point compactification N \cup \{\infty\}. Let A be the space obtained from the disjoint union of two copies of N+ by identifying the two copies of \infty, and let A' be the disjoint union of N and N+. Clearly, there is a morphism A' \to A which is bijective on points (hence, both monic and epic) but not an isomorphism. However, if we regard A and A' as spaces over N+ in the obvious way, the morphism A' \to A becomes an isomorphism when we pull it back along the inclusion N \to N+, and also when we form the pushouts of A x N -------> A(') N+ | | v N since both such pushouts are isomorphic to N+. This says that, if we work in the quasitopos E/N+, the morphism A' \to A is mapped to an isomorphism in both the open subquasitopos E/N and its closed "complement". I should say that I came to consider this question as a result of a seminar talk today by Pawel Sobocinski, which raised the question of whether quasitoposes are quasi-adhesive categories. This example shows that the quasitopos of Frechet spaces is not quasi-adhesive. Peter Johnstone