From MAILER-DAEMON Thu Jul 3 14:59:14 2008 Date: 03 Jul 2008 14:59:14 -0300 From: Mail System Internal Data Subject: DON'T DELETE THIS MESSAGE -- FOLDER INTERNAL DATA Message-ID: <1215107954@mta.ca> X-IMAP: 1209945225 0000000041 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 Sun May 4 17:07:08 2008 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 04 May 2008 17:07:08 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1JskGG-00050s-He for categories-list@mta.ca; Sun, 04 May 2008 16:52:40 -0300 Date: Sat, 03 May 2008 21:42:34 +0100 To: categories@mta.ca Subject: categories: Computability in Europe 2008 - early registration reminder MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit From: A.Beckmann@swansea.ac.uk (Arnold Beckmann) Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 1 [Apologies for multiple copies] **************************************************************** Computability in Europe 2008: Logic and Theory of Algorithms University of Athens, June 15-20 2008 http://www.cs.swan.ac.uk/cie08/ REMINDER: EARLY REGISTRATION ENDS 11 May 2008 We would like to remind participants that registration is only complete once we have received the payment form. In order to give participants who have not yet send their payment form time to react to this reminder we decided to extend the early registration deadline to 11 May 2008. Registration for CiE 2008: http://www.cs.swan.ac.uk/cie08/registration.php You can also use the registration process to book accommodation: http://www.cs.swan.ac.uk/cie08/accommodation.php SOME DETAILS OF THE PROGRAMME ============================= TUTORIALS will be given by: John V. Tucker (Swansea) Moshe Y. Vardi (Houston, TX) PLENARY SPEAKERS will include: Keith Devlin (Stanford, CA) Rosalie Iemhoff (Utrecht) Antonina Kolokolova (Vancouver, BC) Janos Makowsky (Haifa) Dag Normann (Oslo) Prakash Panangaden (Montreal, QC) Christos Papadimitriou (Berkeley, CA) Jan van Leeuwen (Utrecht) & Jiri Wiedermann (Prague) See http://www.cs.swan.ac.uk/cie08/invited.php for more informations on Plenary Speakers. SPECIAL SESSIONS Algorithms in the history of mathematics (organized by J. Hoyrup, Roskilde, and K. Chemla, Paris) Formalising mathematics and extracting algorithms from proofs (organized by H. Barendregt, Nijmegen, and M. Seisenberger, Swansea) Higher type recursion theory and applications (organized by U. Berger, Swansea, and D. Normann, Oslo) Algorithmic game theory (organized by E. Koutsoupias, Athens, and B. von Stengel, London) Quantum algorithms and complexity (organized by V. Kendon, Leeds, and B. Coecke, Oxford) Biology and computation (organized by N. Jonoska, Tampa FL, and G. Mauri, Milano) See http://www.cs.swan.ac.uk/cie08/special.php for more informations on special sessions. ACCEPTED PAPERS The list of accepted papers can be found at http://www.cs.swan.ac.uk/cie08/give-page.php?18 From rrosebru@mta.ca Mon May 5 18:25:52 2008 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 05 May 2008 18:25:52 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1Jt80R-00009A-3L for categories-list@mta.ca; Mon, 05 May 2008 18:13:55 -0300 Date: Mon, 5 May 2008 08:27:35 -0600 From: ICLP 08 Message-Id: <200805051427.m45ERZYd015481@pippo.cs.nmsu.edu> Subject: categories: ICLP'08 CALL FOR PAPERS To: undisclosed-recipients:; Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 2 CALL FOR PAPERS ICLP'08 24th International Conference on Logic Programming Udine, Italy, December 9th-13th, 2008 http://iclp08.dimi.uniud.it CONFERENCE SCOPE ---------------- Since the first conference held in Marseilles in 1982, ICLP has been the premier international conference for presenting research in logic programming. Contributions (papers, position papers, and posters) are sought in all areas of logic programming including but not restricted to: * Theory: Semantic Foundations, Formalisms, Nonmonotonic Reasoning, Knowledge Representation. * Implementation: Compilation, Memory Management, Virtual Machines, Parallelism. * Environments: Program Analysis, Program Transformation, Validation and Verification, Debugging, Profiling, Integration. * Language Issues: Extensions, Integration with Other Paradigms, Concurrency, Modularity, Objects, Coordination, Mobility, Higher Order, Types, Modes, Programming Techniques. * Related Paradigms: Abductive Logic Programming, Inductive Logic Programming, Constraint Logic Programming, Answer-Set Programming. * Applications: Databases, Data Integration and Federation, Software Engineering, Natural Language Processing, Web and Semantic Web, Agents, Artificial Intelligence, Bioinformatics The three broad categories for submissions are: (1) Technical papers, providing novel research contributions, innovative perspectives on the field, and/or novel integrations across different areas; (2) Application papers, describing innovative uses of logic programming technology in real-world application domains; (3) Posters, ideal for presenting and discussing current work, not yet ready for publication, for PhD thesis summaries and research project overviews. A separate session dedicated to the celebration of the 20th anniversary of stable model semantics will also be part of the program. Accepted papers and posters will be allocated time for presentation during the conference. At least one author of each accepted submission is expected to register and participate in the event. In addition to papers and posters, the technical program will include invited talks, advanced tutorials, specialized sessions, workshops, and a Doctoral Student Consortium. Details, as they become available will be posted at: http://iclp08.dimi.uniud.it PAPERS AND POSTERS ------------------ Papers and posters must describe original, previously unpublished research, and must not be simultaneously submitted for publication elsewhere. Emphasis will be placed on the novelty and innovative nature of the results (even if not completely polished and refined). All submissions will be peer-reviewed by an international panel. Submissions MUST contain substantial original, unpublished material. All submissions must be written in English. Technical papers and application papers must not exceed 15 pages in the Springer LNCS format (see http://www.springeronline.com/lncs/) The limit for posters is 5 pages in the same format. The primary means of submission will be electronic, through the Easychair submission system. The submission page is available at http://www.easychair.org/conferences/?conf=ICLP08 PUBLICATION ----------- The proceedings of the conference will be published by Springer-Verlag in the LNCS series. All accepted papers and posters will be included in the proceedings. WORKSHOPS --------- The ICLP'08 program will include several workshops. They are perhaps the best place for the presentation of preliminary work, novel ideas, and new open problems to a more focused and specialized audience. Workshops also provide a venue for presenting specialised topics and opportunities for intensive discussions and project collaboration in any areas related to logic programming, including cross-disciplinary areas. DOCTORAL CONSORTIUM ------------------- The Doctoral Consortium (DC) on Logic Programming is the 4th Doctoral consortium to provide doctoral students with the opportunity to present and discuss their research directions, and to obtain feedback from both peers and word-renown experts in the field. The DC will also offer invited speakers and panel discussions. Accepted participants will receive partial financial support to attend the event and the main conference. The best paper and presentation from the DC will be given the opportunity to present in special session of the main ICLP conference. CELEBRATING 20th YEARS OF STABLE MODEL SEMANTICS ------------------------------------------------ The year 2008 marks the 20th anniversary of the publication that introduced the stable model semantics for logic programs with negation. The paper titled "The stable semantics for logic programs" by Michael Gelfond and Vladimir Lifschitz was presented at ICLP-1988. It was a momentous event that gave rise to a vibrant subfield of logic programming known now as the answer-set programming. Its distinguishing aspects are close connections to the fields of knowledge representation, satisfiability and constraint satisfaction, ever faster computational tools, and a growing list of successful applications. To celebrate the stable-model semantics, there will be a special session at ICLP 2008 dedicated to answer-set programming. The session will feature talks by Michael Gelfond and Vladimir Lifschitz. as well as by other major contributions to the field, presenting personal perspectives on the stable-model semantics, its impact and its future. There will be a panel discussion, and regular accepted ICLP papers falling into the answer-set programming area will complete the program. CONFERENCE VENUE ---------------- The conference will be held in the city of Udine, the capital of the historical region of Friuli, Italy. Located between the Adriatic sea and the Alps, close to Venice, Austria and Slovenia, Udine is a city of Roman origins, funded by Emperor Otto in 983. Rich of historical sites, Udine is also famous for its commercial and shopping opportunities and its outstanding wine and culinary traditions. SUPPORT SPONSORING AND AWARDS ----------------------------- The conference is sponsored by the Association for Logic Programming (ALP). The ALP has funds to assist financially disadvantaged participants. The ALP is planning to sponsor two awards for ICLP 2008: for the best technical paper and for the best student paper. IMPORTANT DATES --------------- Papers Posters Abstract submission deadline June 2nd n/a Submission deadline June 9th August 15th Notification of authors August 1st September 1st Camera-ready copy due September 15th September 15th 20 Years of Stable Models TBA Doctoral Consortium TBA Workshop Proposals June 2nd Early-bird Registration TBA Conference December 9-13, 2008 ICLP'2008 ORGANIZATION ---------------------- General Chair: Agostino Dovier (University of Udine) Program Co-Chairs: Maria Garcia de la Banda (Monash University) Enrico Pontelli (New Mexico State University) Workshop Chair: Tran Cao Son (New Mexico State University) Doctoral Student Consortium: David Warren (SUNY Stony Brook) Tom Schrijvers (K.U.Leuven) Publicity Co-Chairs: Marcello Balduccini (Kodak Research Labs) Alessandro Dal Palu' (University of Parma) Programming Competition Chair: Bart Demoen (K.U.Leuven) 20 Years of Stable Models: Mirek Truszczynski (University of Kentucky) Andrea Formisano (University of Perugia) Program Committee: Salvador Abreu Sergio Antoy Pedro Barahona Chitta Baral Gerhard Brewka Manuel Carro Michael Codish Alessandro Dal Palu' Bart Demoen Agostino Dovier John Gallagher Michael Gelfond Carmen Gervet Gopal Gupta Manuel Hermenegildo Andy King Michael Maher Juan Moreno Navarro Alberto Pettorossi Brigitte Pientka Gianfranco Rossi Fariba Sadri Vitor Santos Costa Tran Cao Son Paolo Torroni Frank Valencia Mark Wallace Web Master: Raffaele Cipriano Local Arrangements Committee: Alberto Casagrande Elisabetta De Maria Luca Di Gaspero Carla Piazza ---------------------------------------------------- For further information: iclp08@cs.nmsu.edu http://iclp08.dimi.uniud.it From rrosebru@mta.ca Tue May 6 20:42:46 2008 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 06 May 2008 20:42:46 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1JtWVY-0004e8-VZ for categories-list@mta.ca; Tue, 06 May 2008 20:23:41 -0300 Date: Tue, 06 May 2008 19:44:43 +0200 From: Joachim Kock Subject: categories: Workshop on Categorical Groups, second announcement To: categories@mta.ca, algtop-l@lists.lehigh.edu 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: 3 This is the second announcement of the WORKSHOP ON CATEGORICAL GROUPS June 16 to 20, 2008 Institut de Matem=E0tica de la Universitat de Barcelona an event within the CRM thematic year on Homotopy Theory=20 and Higher Categories (http://www.crm.cat/hocat/). The workshop will focus on recent developments in the theory=20 of categorical groups and related topics, as well as their=20 applications to higher-order geometry and theoretical physics. The following have agreed to give keynote talks: - John Baez (University of California at Riverside) - Andr=E9 Joyal (Universit=E9 du Qu=E9bec =E0 Montr=E9al) - Behrang Noohi (Florida State University) - Tim Porter (National University of Ireland and Bangor University) - Enrico Vitale (Universit=E9 Catholique de Louvain) Further information will gradually be made available at http://mat.uab.cat/~kock/crm/hocat/cat-groups/. The deadline for registration is May 31, 2008. The organisers, Pilar Carrasco Josep Elgueta Joachim Kock Antonio Rodr=EDguez Garz=F3n From rrosebru@mta.ca Wed May 7 09:42:35 2008 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 07 May 2008 09:42:35 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1JtiuM-0000GG-MQ for categories-list@mta.ca; Wed, 07 May 2008 09:38:06 -0300 Date: Wed, 7 May 2008 13:42:25 +0200 From: "Sanjeevi Krishnan" To: categories@mta.ca Subject: categories: Second Call for Papers: ATMCS III, Paris France July 7-11, 2008 MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Content-Disposition: inline Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 4 My apologies for duplicate copies of this annoucement. ATMCS III Algebraic Topological Methods in Computer Science Paris, France 7-11 July 2008 http://www.lix.polytechnique.fr/~sanjeevi/atmcs/ (poster available for download here) ***SECOND CALL FOR PAPERS*** (New) deadline for abstract submissions: 22 May 2008 Notification of acceptance: 5 June 2008 Deadline for registration: 15 June 2008 Conference: 7-11 July 2008 contact information: atmcs08@lix.polytechnique.fr Recent research has shown that techniques from algebraic topology adapt strikingly well in studying computational systems and other subjects within Computer Science. This third ATMCS conference hopes to bring together researchers employing geometric/topological methods in both abstract and concrete areas of computer science. The week-long conference will feature some invited talks, several accepted talks, a poster session, and countless opportunities for informal collaboration; we plan to publish our proceedings in a refereed journal, pending approval. All authors submitting an abstract by the deadline will have an opportunity, at the least, to present a (refereed) poster at the poster session. ***SCOPE*** Areas of interest include, but are not limited to, concurrency theory, distributed computing and complexity, rewriting systems, image analysis, and sensor networks. ***INVITED SPEAKERS*** A current (and incomplete) list of plenary speakers includes: John Baez, University of California Riverside, U.S.A. Gunnar Carlsson, Stanford University, U.S.A. Herbert Edelsbrunner, Duke University, U.S.A. Robin Forman, Rice University, U.S.A. Philippe Gaucher, University of Paris 7 and CNRS, France Marco Grandis, University of Genova, Italy Emmanuel Haucourt, CEA and Ecole Polytechnique, France Maurice Herlihy, Brown University, U.S.A. Rick Jardine, University of Western Ontario, Canada Louis Kauffman, University of Illinois at Chicago, U.S.A. Sanjeevi Krishnan, CEA and Ecole Polytechnique, France Claudia Landi, University of Modena e Reggio Emilia, Italy Francois Metayer, University of Paris 7 and CNRS, France Konstantin Mischaikow, Rutgers University, U.S.A. Francis Sergeraert, University of Grenoble 1, France Krzysztof Worytkiewicz, AGH University of Science and Technology, Poland ***INSTRUCTIONS FOR SUBMISSIONS*** Authors are invited to submit extended abstracts summarizing current work that explores connections between algebraic topology and computer science. All abstracts should be written in English and should not exceed 1 single-spaced page. Although abstracts preferrably should be submitted at http://atlas-conferences.com/cgi-bin/abstract/submit/caxd-01, abstracts also can be emailed to atmcs08@lix.polytechnique.fr or mailed to the following postal address: Sanjeevi Krishnan DRT LIST DTSI SOL MEASI CEA Saclay 91191 Gif sur Yvette Cedex, France In all cases, submission materials must arrive by May 22, 2008. ***PROGRAM COMMITTEE*** Gunnar Carlsson, Stanford University, U.S.A. Pierre Louis Curien, CNRS and University of Paris 7, France Massimo Ferri, Bologna University, Italy Eric Goubault, CEA and Ecole Polytechnique, France Maurice Herlihy, Brown University, Providence, U.S.A. Yves Lafont, Universite de la Mediterrannee, France Pedro Real, University of Sevilla, Spain Sincerely, The Organizing Committee of ATMCS III From rrosebru@mta.ca Wed May 7 09:42:35 2008 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 07 May 2008 09:42:35 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1JtitD-0000AH-Px for categories-list@mta.ca; Wed, 07 May 2008 09:36:55 -0300 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed To: Categories list From: David Roberts Subject: categories: Strictifying monoidal functors Date: Wed, 7 May 2008 16:29:08 +0930 Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 5 Hi all, While we can make all monoidal categories strict, I was wondering how strict we can make monoidal functors. More precisely, given a strong monoidal functor F:(C,@,I) --> (D,*,1) between strict monoidal categories, it has the data m_xy: F(x)*F(y) ---> F(x@y) (natural) u:1 ---> F(I). Is F naturally isomorphic to a strong monoidal functor such that u is the identity? In Baez-Lauda HDA 5 it is an exercise to the reader in the proof of Proposition 8.3.6 to do this for weak monoidal categories. Cheers, David From rrosebru@mta.ca Sat May 10 10:15:15 2008 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 10 May 2008 10:15:15 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1Juohz-0003xF-UX for categories-list@mta.ca; Sat, 10 May 2008 10:01:51 -0300 From: Andrei Sabelfeld To: categories@mta.ca Subject: categories: IEEE CSF 2008 call for participation MIME-Version: 1.0 Content-Type: text/plain Date: Fri, 9 May 2008 13:48:59 +0200 (MEST) Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 6 Call For Participation 21st IEEE Computer Security Foundations Symposium (CSF) Pittsburgh, PA, USA, June 23-25, 2008 The registration is now open. Early registration ends on June 1. Online late registration is open June 2-10. The specialty of this year is co-location with IEEE LICS 2008. There are a few joint CSF/LICS activities to look forward to, including a joint invited talk by David Basin, joint regular- and short-talk sessions and 8 workshops related to security foundations and logic. Further information (including a detailed program) is on the CSF 2008 web site: http://www.cylab.cmu.edu/CSF2008/ Hope to see you in Pittsburgh! Anupam Datta (General Chair) and Andrei Sabelfeld (Program Chair) From rrosebru@mta.ca Sat May 10 10:15:15 2008 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 10 May 2008 10:15:15 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1Juoih-0003yb-3U for categories-list@mta.ca; Sat, 10 May 2008 10:02:35 -0300 Date: Fri, 9 May 2008 08:16:42 -0600 From: ICLP 08 Subject: categories: ICLP'08 CALL FOR APPLICATION PAPERS To: undisclosed-recipients:; Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 7 ICLP'08 Solicitation for Application Papers 24th International Conference on Logic Programming Udine, Italy, December 9th-13th, 2008 http://iclp08.dimi.uniud.it Within the scope of the general call for papers for the upcoming 24th International Conference on Logic Programming, we would like to draw the attention of researchers and practitioners on the opportunity to submit manuscripts to the Application Track of the conference. Application papers, are expected to describing complex and/or real-world applications that rely in an essential manner on the use of logic programming technology. Description of innovative applications as well as engineering solutions leveraging logic programming technology are solicited. SUBMISSION: ----------- Papers must describe original, previously unpublished results, and must not be simultaneously submitted for publication elsewhere. Submissions MUST contain substantial original, unpublished material. All submissions must be written in English. Application papers should be structured to emphasize: * the application domain, in terms understandable by a layman * the specific problem addressed within the application domain, stressing importance and complexity * a clear discussion of the unique need for logic programming technology to address the problem * a clear description of the application developed and its evaluation. Application papers must not exceed 15 pages in the Springer LNCS format (see http://www.springeronline.com/lncs/) The primary means of submission will be electronic, through the Easychair submission system. The submission page is available at: http://www.easychair.org/conferences/?conf=ICLP08 REVIEW PROCESS: --------------- All submissions will be peer-reviewed by an international panel. Application papers will be reviewed separately from regular technical papers. Accepted papers will be allocated time for presentation during the conference. At least one author of each accepted submission is expected to register and participate in the event. PUBLICATION ----------- The proceedings of the conference will be published by Springer-Verlag in the LNCS series. All accepted papers and posters will be included in the proceedings. IMPORTANT DATES --------------- Abstract submission deadline June 2nd Submission deadline June 9th Notification of authors August 1st Camera-ready copy due September 15th Early-bird Registration TBA Conference December 9-13, 2008 --- For further information: iclp08@cs.nmsu.edu http://iclp08.dimi.uniud.it From rrosebru@mta.ca Sat May 10 10:15:15 2008 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 10 May 2008 10:15:15 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1JuohI-0003uw-DO for categories-list@mta.ca; Sat, 10 May 2008 10:01:08 -0300 From: Tom Hirschowitz MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Date: Fri, 9 May 2008 10:32:14 +0200 To: categories@mta.ca Subject: categories: Postdoc position at University of Savoy Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 8 Dear categorists, There is a one year postdoc position opening at University of Savoy, http://www.univ-savoie.fr/Portail starting next october. My team (computer science, logic, and discrete maths) http://www.lama.univ-savoie.fr/index.php?use=membres&equipe=logique&lang=en in the math lab http://www.lama.univ-savoie.fr/index.php would welcome and put forward any good candidate in category theory, or using categories to do logic or computer science. The deadline is June, 18th, and the administrative burden is minimal (cv plus short description of the scientific project), so don't hesitate to apply. Please contact me for any further question, Tom From rrosebru@mta.ca Sun May 11 11:06:10 2008 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 11 May 2008 11:06:10 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1JvBv0-0000Vy-0r for categories-list@mta.ca; Sun, 11 May 2008 10:48:50 -0300 Date: Sat, 10 May 2008 10:01:28 -0700 From: "Zhaohua Luo" Subject: categories: FW: Hyperalgebras To: 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: O X-Status: X-Keywords: X-UID: 9 Hyperalgebras http://www.algebraic.net/cag/hyperalgebra.html Zhaohua Luo (5/2008) Part I Abstract: A hyperalgebra is an algebra of type (0, 0, ..., 2, 3, 4, ...) satisfying three axioms. Finitary hyperalgebras form a coreflective full subcategory of the variety of hyperalgebras, which is equivalent to the opposite of the category of varieties. Thus any subvariety of the variety of hyperalgebras may be viewed as a hypervariety, i.e. a variety of varieties in the sense of W. D. Neumann. Definition. A hyperalgebra is a nonempty set A together with a sequence X = {x_1, x_2, ...} of elements of A and a sequence S = {s_1, s_2, ...} of operations s_n: A^{n+1} -> A, which satisfies the following axioms for M, M_1, ..., M_m, N_1, ..., N_n in A: Write M[M_1, ..., M_n] for s_n(M, M_1, ..., M_n). A1. x_n[M_1, ..., M_m] = M_n if n < m + 1. A2. (M[M_1, ..., M_m])[N_1, ..., N_n] = M[M_1[N_1, ..., N_n], ..., M_m[N_1, ..., N_n]]. A3. M[M_1, ..., M_m] = M[M_1, ..., M_m, M_m]. A hyperalgebra A is finitary if for any M in A there is n > 0 such that M = M[x_1, ..., x_n]. Let A be a hyperalgebra. A model of A is a set D together with a sequence U = {u_1, u_2,...} of operations u_n: A x D^n -> D, which satisfying the following axioms for M, M_1, ..., M_m in A and a_1, ..., a_n in D: Write M[a_1, ..., a_n] for u_n(M, a_1, ..., a_n). B1. x_n[a_1, ..., a_m] = a_n if n < m + 1. B2. (M[M_1, ..., M_m])[a_1, ..., a_n] = M[M_1[a_1, ..., a_n], ..., M_m[a_1, ..., a_n]]. B3. M[a_1, ..., a_n] = M[a_1, ..., a_n, a_n]. Define homomorphisms of models in an obvious way. Denote by Mod(A) the category of models of A. Theorem. 1. If V is a variety and T(V) is the free algebra of V over X, then T(V) is naturally a finitary hyperalgebra, and V is equivalent to Mod(T(V)) as concrete categories over Set . 2. If A is a hyperalgebra then the class Mod(A) forms a variety. If A is a finitary hyperalgebra then it is isomorphic to T(Mod(A)). 3. The correspondences A -> Mod(A) and V -> T(V) establish an equivalence between the category of finitary hyperalgebras and the opposite of the category of varieties. From rrosebru@mta.ca Mon May 12 12:07:44 2008 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 12 May 2008 12:07:44 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1JvZMk-0005yn-5A for categories-list@mta.ca; Mon, 12 May 2008 11:51:02 -0300 Date: Mon, 12 May 2008 08:34:18 -0400 (EDT) From: Michael Barr To: Categories list Subject: categories: Further to my question on adjoints 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: 10 In March I asked a question on adjoints, to which I have received no correct response. Rather than ask it again, I will pose what seems to be a simpler and maybe more manageable question. Suppose C is a complete category and E is an object. Form the full subcategory of C whose objects are equalizers of two arrows between powers of E. Is that category closed in C under equalizers? (Not, to be clear, the somewhat different question whether it is internally complete.) In that form, it seems almost impossible to believe that it is, but it is surprisingly hard to find an example. When E is injective, the result is relatively easy, but when I look at examples, it has turned out to be true for other reasons. Probably there is someone out there who already knows an example. Michael From rrosebru@mta.ca Tue May 13 14:15:08 2008 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 13 May 2008 14:15:08 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1Jvxq6-0005p2-NJ for categories-list@mta.ca; Tue, 13 May 2008 13:58:58 -0300 Subject: categories: Re: Further to my question on adjoints From: Eduardo Dubuc Date: Mon, 12 May 2008 12:43:55 -0300 (ART) To: categories@mta.ca (Categories list) 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: O X-Status: X-Keywords: X-UID: 11 Consider the dual finitary question: In universal algebra in order to show that finitely presented objects are closed under coequalizers it is essential that a amorphism of finitely presented objects lift to a morphism between the free. Is this the only way to prove it ? : " but when I look at examples, it has turned out to be true for other reasons." greetings e.d. > > In March I asked a question on adjoints, to which I have received no > correct response. Rather than ask it again, I will pose what seems to be > a simpler and maybe more manageable question. Suppose C is a complete > category and E is an object. Form the full subcategory of C whose objects > are equalizers of two arrows between powers of E. Is that category closed > in C under equalizers? (Not, to be clear, the somewhat different question > whether it is internally complete.) > > In that form, it seems almost impossible to believe that it is, but it is > surprisingly hard to find an example. When E is injective, the result is > relatively easy, but when I look at examples, it has turned out to be true > for other reasons. Probably there is someone out there who already knows > an example. > > Michael > > From rrosebru@mta.ca Tue May 13 14:15:07 2008 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 13 May 2008 14:15:07 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1JvxqY-0005s1-1p for categories-list@mta.ca; Tue, 13 May 2008 13:59:26 -0300 Date: Mon, 12 May 2008 11:51:53 -0400 (EDT) From: Michael Barr To: Categories list Subject: categories: Re: Further to my question on adjoints In-Reply-To: Message-ID: References: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed X-PMX-Version: 5.4.0.320885, Antispam-Engine: 2.5.2.313940, Antispam-Data: 2008.4.7.44415 X-McGill-WhereFrom: Internal X-PMX-Version: 5.4.2.338381, Antispam-Engine: 2.6.0.325393, Antispam-Data: 2008.5.12.83751 X-PerlMx-Spam: Gauge=IIIIIII, Probability=7%, Report='BODY_SIZE_2000_2999 0, BODY_SIZE_5000_LESS 0, __BOUNCE_CHALLENGE_SUBJ 0, __CT 0, __CT_TEXT_PLAIN 0, __HAS_MSGID 0, __MIME_TEXT_ONLY 0, __MIME_VERSION 0, __SANE_MSGID 0' Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: X-Keywords: X-UID: 12 No. For example, in the category of topological abelian groups, Z is far from injective. Nonetheless, if you say that a group is Z-compact when it is an equalizer of two maps between powers of Z, then an equalizer of two maps between Z-compact abelian groups is again Z-compact. The proof is not direct. As it happens, I am talking on this in our seminar tomorrow. Even though the reals are not injective in hausdorff spaces, a space is realcompact iff it is a closed subspace of a power of R, which turns out to be equivalent to being an equalizer of two maps between powers of R (that is a cokernel pair of such a closed inclusion has enough real-valued functions to separate points) and it is clear that a closed subspace of a realcompact space is again realcompact. Same thing for N-compact. In fact, for every example I have looked at sufficiently closely. Michael On Mon, 12 May 2008, Eduardo Dubuc wrote: > Consider the dual finitary question: In universal algebra in order to show > that finitely presented objects are closed under coequalizers it is > essential that a amorphism of finitely presented objects lift to a > morphism between the free. Is this the only way to prove it ? : > > " but when I look at examples, it has turned out to be true > for other reasons." > > greetings e.d. > > >> >> In March I asked a question on adjoints, to which I have received no >> correct response. Rather than ask it again, I will pose what seems to be >> a simpler and maybe more manageable question. Suppose C is a complete >> category and E is an object. Form the full subcategory of C whose objects >> are equalizers of two arrows between powers of E. Is that category closed >> in C under equalizers? (Not, to be clear, the somewhat different question >> whether it is internally complete.) >> >> In that form, it seems almost impossible to believe that it is, but it is >> surprisingly hard to find an example. When E is injective, the result is >> relatively easy, but when I look at examples, it has turned out to be true >> for other reasons. Probably there is someone out there who already knows >> an example. >> >> Michael >> >> > From rrosebru@mta.ca Tue May 13 14:15:08 2008 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 13 May 2008 14:15:08 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1JvxtW-000693-6n for categories-list@mta.ca; Tue, 13 May 2008 14:02:30 -0300 From: "George Janelidze" To: "Categories list" Subject: categories: Re: Further to my question on adjoints Date: Mon, 12 May 2008 20:42: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: RO X-Status: X-Keywords: X-UID: 13 Dear Michael, Let C be the category of commutative rings (with 1), let t be the unique positive real number with tttt = 2 (if I knew TeX better, I would probably write t^4 = 2), and E be the smallest subfield in the field of real numbers that contains t. Then: (a) Every power of E has exactly one element x such that xx = 2 and there exists y with x = yy. Let us call this x the positive square root of 2. (b) Every morphism between powers of E preserves the positive square root of 2. (c) Therefore every equalizer of two arrows between powers of E has an element x with xx = 2 (note that I am not saying anything about the existence of y, since y above is not determined uniquely!). (d) Therefore the field Q of rational numbers cannot be presented as an equalizer of two arrows between powers of E. (e) On the other hand Q can be presented as an equalizer of two arrows between two objects in C that are equalizers of two arrows between powers of E. Indeed: the equalizer of the identity morphism of E and the unique non-identity morphism of E is the subfield D in E generated by tt (which is just the square root of 2); and the equalizer of the identity morphism of D and the unique non-identity morphism of D is Q. (f) This also gives negative answer to the question about "internally complete", since no arrow of our subcategory composed with the two morphisms D ---> D above will give the same result. This story is of course based on the fact that there are Galois field extensions L/K and M/L, for which M/K is not a Galois extension. Best regards, George ----- Original Message ----- From: "Michael Barr" To: "Categories list" Sent: Monday, May 12, 2008 2:34 PM Subject: categories: Further to my question on adjoints > In March I asked a question on adjoints, to which I have received no > correct response. Rather than ask it again, I will pose what seems to be > a simpler and maybe more manageable question. Suppose C is a complete > category and E is an object. Form the full subcategory of C whose objects > are equalizers of two arrows between powers of E. Is that category closed > in C under equalizers? (Not, to be clear, the somewhat different question > whether it is internally complete.) > > In that form, it seems almost impossible to believe that it is, but it is > surprisingly hard to find an example. When E is injective, the result is > relatively easy, but when I look at examples, it has turned out to be true > for other reasons. Probably there is someone out there who already knows > an example. > > Michael > > > From rrosebru@mta.ca Tue May 13 14:15:07 2008 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 13 May 2008 14:15:07 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1JvxuK-0006EG-7u for categories-list@mta.ca; Tue, 13 May 2008 14:03:20 -0300 Date: Mon, 12 May 2008 15:27:40 -0400 (EDT) From: Michael Barr To: Categories list Subject: categories: Re: Further to my question on adjoints 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: 14 I have checked this carefully and it works. To summarize, let F = Q[2^{1/2}] and E = Q[2^{1/4}]. Then any power of E contains a square whose square is a square root of 2 and any ring homomorphism between powers of E preserves it. (Incidentally, although it may help your intuition to take the positive fourth of 2, the various fourth roots of 2 are indistinguishable algebraically.) Thus any ring in EqP(E) contains a square root of 2 (although not necessarily a fourth root). Now F is the equalizer of the two distinct maps E to E, while Q is the equalizer of the two distinct maps F to F. This now gives a counter-example for my original question. Let C be the category of commutative rings, F = Hom(-,E) : C ---> Set\op and U = E^{-}: Set\op ---> C are adjoint. If T is the resultant triple, then F ---> E ===> E is an equalizer between two values of U, while not being the canonical equalizer. TF = E x E and T^2F = E x E x E x E. I haven't done the computation, but I believe the equalizer of TF ===> T^2 is F x F. Thanks George, Michael On Mon, 12 May 2008, George Janelidze wrote: > Dear Michael, > > Let C be the category of commutative rings (with 1), let t be the unique > positive real number with tttt = 2 (if I knew TeX better, I would probably > write t^4 = 2), and E be the smallest subfield in the field of real numbers > that contains t. Then: > > (a) Every power of E has exactly one element x such that xx = 2 and there > exists y with x = yy. Let us call this x the positive square root of 2. > > (b) Every morphism between powers of E preserves the positive square root of > 2. > > (c) Therefore every equalizer of two arrows between powers of E has an > element x with xx = 2 (note that I am not saying anything about the > existence of y, since y above is not determined uniquely!). > > (d) Therefore the field Q of rational numbers cannot be presented as an > equalizer of two arrows between powers of E. > > (e) On the other hand Q can be presented as an equalizer of two arrows > between two objects in C that are equalizers of two arrows between powers of > E. Indeed: the equalizer of the identity morphism of E and the unique > non-identity morphism of E is the subfield D in E generated by tt (which is > just the square root of 2); and the equalizer of the identity morphism of D > and the unique non-identity morphism of D is Q. > > (f) This also gives negative answer to the question about "internally > complete", since no arrow of our subcategory composed with the two morphisms > D ---> D above will give the same result. > > This story is of course based on the fact that there are Galois field > extensions L/K and M/L, for which M/K is not a Galois extension. > > Best regards, George > > ----- Original Message ----- > From: "Michael Barr" > To: "Categories list" > Sent: Monday, May 12, 2008 2:34 PM > Subject: categories: Further to my question on adjoints > > >> In March I asked a question on adjoints, to which I have received no >> correct response. Rather than ask it again, I will pose what seems to be >> a simpler and maybe more manageable question. Suppose C is a complete >> category and E is an object. Form the full subcategory of C whose objects >> are equalizers of two arrows between powers of E. Is that category closed >> in C under equalizers? (Not, to be clear, the somewhat different question >> whether it is internally complete.) >> >> In that form, it seems almost impossible to believe that it is, but it is >> surprisingly hard to find an example. When E is injective, the result is >> relatively easy, but when I look at examples, it has turned out to be true >> for other reasons. Probably there is someone out there who already knows >> an example. >> >> Michael >> >> >> > From rrosebru@mta.ca Tue May 13 14:15:09 2008 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 13 May 2008 14:15:09 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1Jvxv5-0006JF-Uq for categories-list@mta.ca; Tue, 13 May 2008 14:04:08 -0300 MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable Subject: categories: RE: Further to my question on adjoints Date: Tue, 13 May 2008 08:38:30 +1000 From: "Stephen Lack" To: "Categories list" Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: RO X-Status: X-Keywords: X-UID: 15 Dear Michael, I do not remember your original question, but here is an answer to this. Let C be Cat^op and E be the arrow category 2. It's easier to work in Cat itself. Then we are interested in the full subcategory consisting of all categories X which admit a presentation=20 I.2 --> J.2 --> X --> =20 where I and J are sets, and "." is cotensor: e.g. J.2 denotes the=20 coproduct of J copies of 2. But a category admits such a presentation if and only if it is free on=20 a graph, and the free categories are of course not closed under coequalizers. Steve. > -----Original Message----- > From: cat-dist@mta.ca [mailto:cat-dist@mta.ca] On Behalf Of=20 > Michael Barr > Sent: Monday, May 12, 2008 10:34 PM > To: Categories list > Subject: categories: Further to my question on adjoints >=20 > In March I asked a question on adjoints, to which I have=20 > received no correct response. Rather than ask it again, I=20 > will pose what seems to be a simpler and maybe more=20 > manageable question. Suppose C is a complete category and E=20 > is an object. Form the full subcategory of C whose objects=20 > are equalizers of two arrows between powers of E. Is that=20 > category closed in C under equalizers? (Not, to be clear,=20 > the somewhat different question whether it is internally complete.) >=20 > In that form, it seems almost impossible to believe that it=20 > is, but it is surprisingly hard to find an example. When E=20 > is injective, the result is relatively easy, but when I look=20 > at examples, it has turned out to be true for other reasons. =20 > Probably there is someone out there who already knows an example. >=20 > Michael >=20 >=20 >=20 From rrosebru@mta.ca Tue May 13 14:15:08 2008 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 13 May 2008 14:15:08 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1Jvxvp-0006NG-5C for categories-list@mta.ca; Tue, 13 May 2008 14:04:53 -0300 From: "George Janelidze" To: "Categories list" Subject: categories: re: Further to my question on adjoints Date: Tue, 13 May 2008 01:43: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: RO X-Status: X-Keywords: X-UID: 16 Dear Michael, Sorry to say, I have no time now - so, just briefly: I know that "positive" is just an illusion and I only used it to make things seem more obvious. Moreover, "fields" is also an illusion, since all the rings involved are (quasi-) separable Q-algebras - and in fact one should put things inside the dual category of G-sets, where, say, G is a finite group that has a subgroup whose normalizer is a normal subgroup in G different from G itself. This would imply that the phenomenon you were looking for can even be found in a category dual to a Boolean topos. However I still have to study what you say in the second paragraph of your message... Thank you for an interesting question- George ----- Original Message ----- From: "Michael Barr" To: "George Janelidze" Cc: "Categories list" ; "John F. Kennison" ; "Bob Raphael" Sent: Monday, May 12, 2008 9:27 PM Subject: Re: categories: Further to my question on adjoints > I have checked this carefully and it works. To summarize, let F = > Q[2^{1/2}] and E = Q[2^{1/4}]. Then any power of E contains a square > whose square is a square root of 2 and any ring homomorphism between > powers of E preserves it. (Incidentally, although it may help your > intuition to take the positive fourth of 2, the various fourth roots of 2 > are indistinguishable algebraically.) Thus any ring in EqP(E) contains a > square root of 2 (although not necessarily a fourth root). Now F is the > equalizer of the two distinct maps E to E, while Q is the equalizer of the > two distinct maps F to F. > > This now gives a counter-example for my original question. Let C be the > category of commutative rings, F = Hom(-,E) : C ---> Set\op and U = E^{-}: > Set\op ---> C are adjoint. If T is the resultant triple, then F ---> E > ===> E is an equalizer between two values of U, while not being the > canonical equalizer. TF = E x E and T^2F = E x E x E x E. I haven't done > the computation, but I believe the equalizer of TF ===> T^2 is F x F. > > Thanks George, > > Michael > > > On Mon, 12 May 2008, George Janelidze wrote: > > > Dear Michael, > > > > Let C be the category of commutative rings (with 1), let t be the unique > > positive real number with tttt = 2 (if I knew TeX better, I would probably > > write t^4 = 2), and E be the smallest subfield in the field of real numbers > > that contains t. Then: > > > > (a) Every power of E has exactly one element x such that xx = 2 and there > > exists y with x = yy. Let us call this x the positive square root of 2. > > > > (b) Every morphism between powers of E preserves the positive square root of > > 2. > > > > (c) Therefore every equalizer of two arrows between powers of E has an > > element x with xx = 2 (note that I am not saying anything about the > > existence of y, since y above is not determined uniquely!). > > > > (d) Therefore the field Q of rational numbers cannot be presented as an > > equalizer of two arrows between powers of E. > > > > (e) On the other hand Q can be presented as an equalizer of two arrows > > between two objects in C that are equalizers of two arrows between powers of > > E. Indeed: the equalizer of the identity morphism of E and the unique > > non-identity morphism of E is the subfield D in E generated by tt (which is > > just the square root of 2); and the equalizer of the identity morphism of D > > and the unique non-identity morphism of D is Q. > > > > (f) This also gives negative answer to the question about "internally > > complete", since no arrow of our subcategory composed with the two morphisms > > D ---> D above will give the same result. > > > > This story is of course based on the fact that there are Galois field > > extensions L/K and M/L, for which M/K is not a Galois extension. > > > > Best regards, George > > > > ----- Original Message ----- > > From: "Michael Barr" > > To: "Categories list" > > Sent: Monday, May 12, 2008 2:34 PM > > Subject: categories: Further to my question on adjoints > > > > > >> In March I asked a question on adjoints, to which I have received no > >> correct response. Rather than ask it again, I will pose what seems to be > >> a simpler and maybe more manageable question. Suppose C is a complete > >> category and E is an object. Form the full subcategory of C whose objects > >> are equalizers of two arrows between powers of E. Is that category closed > >> in C under equalizers? (Not, to be clear, the somewhat different question > >> whether it is internally complete.) > >> > >> In that form, it seems almost impossible to believe that it is, but it is > >> surprisingly hard to find an example. When E is injective, the result is > >> relatively easy, but when I look at examples, it has turned out to be true > >> for other reasons. Probably there is someone out there who already knows > >> an example. > >> > >> Michael > >> > >> > >> > > > From rrosebru@mta.ca Tue May 13 14:15:07 2008 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 13 May 2008 14:15:07 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1JvxwM-0006QN-L1 for categories-list@mta.ca; Tue, 13 May 2008 14:05:26 -0300 Mime-Version: 1.0 (Apple Message framework v624) Content-Type: text/plain; charset=US-ASCII; format=flowed Content-Transfer-Encoding: 7bit From: Paul Taylor Subject: categories: Equalisers of power Date: Tue, 13 May 2008 09:20:47 +0100 To: Categories list Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 17 Michael Barr asked, > Suppose C is a complete category and E is an object. By which I understand that C has all finite limits and powers of E, although I usually write Sigma instead of E. > Form the full subcategory of C whose objects are equalizers of two > arrows between powers of E. This full subcategory consists of the objects that I call "sober". > Is that category closed in C under equalizers? Yes. Write $X for the exponential E^X. Then $ is a self-adjoint contravariant endofunctor of the category C, and the covariant functor $$ is part of a monad. For any object X there is a diagram with equal composites eta $$ X eta X ---------> X ------> $$ X $$$$ X ---------> $$ eta X and X is by definition "sober" if this is an equaliser. Any sober object in this sense belongs to Mike's subcategory. Any $Y is sober, because eta $Y is split by $ eta Y (see the chapter on Beck's triplability theorem in "Toposes, Triples and Theories", for example, for details). Now if Y and Z are sober and X >---> Y ====> Z is an equaliser, we can form a 3x3 square of objects, whose rows and columns (with one a priori exception) are equalisers, and then check that the last is an equaliser too, ie X is sober. In other words, Mike's subcategory is closed under equalisers and consists of the sober objects. [] I don't remember the details of the papers in question, but investigations of this kind go back to Lambek & Rattray c1975. Then in Synthetic Domain Theory (SDT) c1990, Rosolini, Phoa, Hyland and I looked at various properties that select "predomains" as special objects of a topos. One of these was Hyland's notion of "repleteness", which Rosolini, Fiore and Makkai showed to be slightly weaker than sobriety, when you chararacterise these things in particular concrete categories. Conceptually, though, they amount to the same thing. Streicher also looked looked at sobriety in a concrete setting. I would say that it is a mistake to see sobriety as a property of objects in a category that has been given in advance. It should really be seen as a property of the category: that the functor $ reflects invertibility. Alternatively, we may see it is an axiom in a richer logic, where it has the concrete interpretation that - N is sober iff it admits definition by description and - R is sober iff it is Dedekind complete. See S 14 of "The Dedekind Reals in ASD" by Bauer and me for details www.PaulTaylor.EU/ASD/dedras The idea of Abstract Stone Duality came out of my earlier involvement in SDT, and was also motivated by Pare's theorem that $ (now the contravariant powerset functor) is monadic in any elementary topos. Mathematically, the most important consequence of this hypothesis is the Heine--Borel theorem, that [0,1] subset R is compact in the "finite open subcover" sense. I gave a summary of this in my posting to "categories" on 18 August 2007. The monadic hypothesis led to an account of (computably based) locally compact spaces, from which it is very difficult to escape. Stepping back from monadicity, and almost going back to Mike Barr's question, the Heine--Borel theorem is a consequence of having "the right" relationship between $ (powers of the Sierpinski space) and equalisers. Within the category of "topological spaces" as found in the textbooks, or that of locales, this relationship is called either the "subspace topology" or "injectivity of Sierpinski". However, I have a counterexample (which I am not willing to spell out in ASCII) to show that this cannot extend verbatim to cartesian closed categories of spaces. I shall present this, the weaker property that I think should generalise it, my syntactic proof that this property is consistent (I have no concrete model) and some of its applications, at CT08 in Calais next month (assuming, of course, that the programme committee accepts my submission). Paul Taylor From rrosebru@mta.ca Fri May 16 08:24:09 2008 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 16 May 2008 08:24:09 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1Jwxx2-0007lQ-AW for categories-list@mta.ca; Fri, 16 May 2008 08:18:16 -0300 Mime-Version: 1.0 (Apple Message framework v624) Content-Type: text/plain; charset=US-ASCII; format=flowed Content-Transfer-Encoding: 7bit From: Paul Taylor Subject: categories: Equalisers of powers - correction Date: Wed, 14 May 2008 20:52:27 +0100 To: Categories list Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 18 I am sure that you will have gathered that I interpreted the "powers" in Mike Barr's question in a different way from the others that replied, and indeed from the way in which he intended it. His "powers" were set-indexed products of the object with itself, whilst mine were in the sense of a cartesian closed category. Nevertheless, it is interesting that we have two conflicting answers. Those who are more familiar with the algebraic examples that Eduardo Dubuc, George Janelidze and Stev Lack have discussed may like to consider where the differences lie, notwithstanding what I am about to say.. Unfortunately, as Mike pointed out to me privately, there was first carelessness, and then an actual error, in what I wrote: > Now if Y and Z are sober and X >---> Y ====> Z is an equaliser, > we can form a 3x3 square of objects, whose rows and columns (with > one a priori exception) are equalisers, and then check that the > last is an equaliser too, ie X is sober. The carelessness was that I only intended the top row and two columns to be equalisers, not five rows/columns. The error was that $$X--->$$Y apparently needs to be mono. The proof, in all its gory ASCII detail, follows. I apologise for the error. I was reciting results from ASD without checking that all of the relevant hypotheses were present. The correct ASD results are that this is true when either i:X>-->Y is a Sigma-split inclusion, so $i is split epi and $$i is split mono or we have the more general structure that I intend to talk about in Calais. Mike also asked me for a reference for the relationship between my abstract notion of sobriety and the traditional one that every irreducible closed subset is the closure of a unique point. This is discussed (as you might have guessed) in "Sober Spaces and Continuations" TAC 2002 www.PaulTaylor.EU/ASD However, the relationship is conceptual and not extensional. The point is that a sober "space" is one whose points agree with the "primes" of the corresponding algebra, under some Stone-type duality. The paper makes some attempt to set up an extensional equivalence, but such a thing is really not meaningful. Gamma ....................... | : | __________ h _________________________ | | : f | | | i v ----------------> v | X >-------------> Y g Z | | v ----------------> v | | | | | |eta U |eta Y |eta Z | | | | | | | $$ f | | v $$ i v -------------> v |----> $$ X -----------> $$ Y $$ g $$ Z | | | | -------------> | | eta $$ X | | eta$$Y| | eta$$Z| | | |$$etaX | |$$etaY | |$$etaZ | | | | | | | | | | $$$$ f | | v v $$$$ i v v -------------> v v $$$$ X ---------> $$$$ Y $$$$ g $$$$ Z -------------> Suppose that the top row and Y and Z columns are equalisers, i;f = h = i;g and Gamma-->$$X has equal composites to $$$$ X, and therefore continuing to $$$$ Y. (We'll consider $$$$ Z later.) Since eta$$ and $$eta are natural (wrt i), the two squares from $$X to $$$$Y commute. Therefore Gamma-->$$X-->$$Y has equal composites as far as $$$$Y. In other words, it tests the equaliser Y>-->$$Y===>$$$$Y, so there is a unique fill-in (dotted) Gamma-->Y that makes a commutative kite at $$Y. Now, ignore the fact that we have parallel maps f and g etc, and just consider their composite h:Z-->Z with i. By exactly the same argument as we have just used for Y and i, the map Gamma-->$$X-->$$Z has equal composites at $$$$Z, ie it tests Y as the equaliser, and has a uniqe fill-in Gamma-->Z that makes a commutative kite at $$Z. Now, there are two other candidates for the fill-in Gamma-->Z, namely the two composites Gamma--->Y===>Z, so these are all equal. This tests the equaliser X>--->Y====Z, so there is a unique fill-in Gamma-->X. Now here was my error: why should the composite Gamma-->X-->$$X be equal the original map? Well, it is, so long as $$X-->$$Y is mono. Paul Taylor From rrosebru@mta.ca Fri May 16 08:24:09 2008 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 16 May 2008 08:24:09 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1Jwxxx-000006-Rz for categories-list@mta.ca; Fri, 16 May 2008 08:19:13 -0300 Mime-Version: 1.0 (Apple Message framework v753) To: categories@mta.ca From: Domains IX Subject: categories: Workshop Domains IX [ Call for Abstracts ] Date: Thu, 15 May 2008 12:00:23 +0100 Content-Transfer-Encoding: 7bit Content-Type: text/plain;charset=US-ASCII;delsp=yes;format=flowed Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 19 ------------------------------------------------------------------------ -------------------- C A L L F O R A B S T R A C T S Workshop DOMAINS IX http://www.informatics.sussex.ac.uk/events/domains9/ University of Sussex, Brighton, 22-24 September 2008 ------------------------------------------------------------------------ -------------------- INTRODUCTION The Workshop on Domains is aimed at computer scientists and mathematicians alike who share an interest in the mathematical foundations of computation. The workshop will focus on domains, their applications and related topics. Previous meetings were held in Darmstadt (94,99,04), Braunschweig (96), Munich (97), Siegen (98), Birmingham (02) and Novosibirsk (07). FORMAT The emphasis is on the exchange of ideas between participants similar in style to Dagstuhl seminars. In particular, talks on subjects presented at other conferences and workshops are acceptable. INVITED SPEAKERS (confirmed) Andrew Pitts Cambridge University John Longley University of Edinburgh Martin Hyland Cambridge University Jean Goubault-Larrecq LSV/ENS Cachan & CNRS More speakers to be announced nearer to the time. SCOPE Domain theory has had applications to programming language semantics and logics (lambda-calculus, PCF, LCF), recursion theory (Kleene-Kreisel countable functionals), general topology (injective spaces, function spaces, locally compact spaces, Stone duality), topological algebra (compact Hausdorff semilattices) and analysis (measure, integration, dynamical systems). Moreover, these applications are related - for example, Stone duality gives rise to a logic of observable properties of computational processes. As such, domain theory is highly interdisciplinary. Topics of interaction with domain theory for this workshop include, but are not limited to: program semantics program logics probabilistic computation exact computation over the real numbers lambda calculus games models of sequential computation constructive mathematics recursion theory realizability real analysis and computability topology, metric spaces and domains locale theory category theory topos theory type theory SUBMISSION OF ABSTRACTS _*One-page* abstracts should be submitted now to domains9@sussex.ac.uk Shortly after an abstract is submitted (usually one or two weeks), the authors will be notified by the programme committee. The criterion for acceptance is relevance to the meeting. In particular, talks on subjects presented at other conferences and workshops are acceptable. *** Abstracts will be dealt with on a first-come/first-served basis! *** *** So please submit soon to avoid disappointment. *** DEADLINE 1 July 2008 REGISTRATION Further details about the local arrangements will be provided soon. PhD students or participants from Eastern Europe who think they need financial support to be able to attend should contact the PC. Depending on the funding, subsistence costs might be (partially) covered for those participants. ACCOMMODATION The workshop will be held at the University of Sussex at Falmer, Brighton. Newly built halls of residence will be available to workshop participants. Further information on travel, accommodation and places of local interest will be provided at a later date. PROGRAMME COMMITTEE Martin Escardo University of Birmingham Achim Jung (Co-Chair) University of Birmingham Klaus Keimel (Co-Chair) Darmstadt University Bernhard Reus (Co-Chair) University of Sussex Thomas Streicher Darmstadt University ORGANIZATION COMMITTEE Bernhard Reus University of Sussex PUBLICATION We plan to publish proceedings of the workshop in a journal. There will be a call for papers after the workshop. The papers will be refereed according to normal publication standards. URL http://www.informatics.sussex.ac.uk/events/domains9/ From rrosebru@mta.ca Fri May 16 20:30:45 2008 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 16 May 2008 20:30:45 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1Jx9KW-0000Vv-Js for categories-list@mta.ca; Fri, 16 May 2008 20:27:16 -0300 Subject: categories: FMCS 2008, Halifax, next weekend To: categories@mta.ca (Categories List) Date: Fri, 16 May 2008 18:02:06 -0300 (ADT) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit From: selinger@mathstat.dal.ca (Peter Selinger) Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: RO X-Status: X-Keywords: X-UID: 20 FMCS 2008 16th Workshop on Foundational Methods in Computer Science Dalhousie University, Halifax, Canada May 30 - June 1, 2008 http://www.mathstat.dal.ca/~selinger/fmcs2008/ LAST ANNOUNCEMENT * * * Foundational Methods in Computer Science is an annual workshop bringing together researchers in mathematics and computer science with a focus on the application of category theory in computer science. This year's meeting will be hosted in the Department of Mathematics and Statistics at Dalhousie University in Halifax, Canada. There will be an informal welcoming reception in the evening of May 29, starting at 5:30. The scientific program starts on May 30, and consists of four tutorials aimed at students and newcomers to category theory, as well as a day and a half of research talks. The meeting ends at mid-day on June 1. TUTORIAL LECTURES: Pieter Hofstra (Ottawa), "Fibrations and proofs" Ernie Manes (Massachusetts), "Recurrence" Paul-Andre Mellies (Paris 7), TBA Andrea Schalk (Manchester), "Building *-autonomous categories" SPECIAL SESSION HONORING ERNIE MANES'S 65TH BIRTHDAY: Philip Mulry (Colgate), "Welcome to special session" Stephen Bloom (Stevens), "Conway and iteration semirings" Robin Cockett (Calgary), "Ernie and adding complements" Fred Linton (Wesleyan), "A double cover of Heath's V-space admitting no global section" Bob Pare (Dalhousie), "Double triples" Bill Lawvere (SUNY Buffalo), "Extensivity and rig geometry" CONTRIBUTED TALKS: Brendan Cordy (McGill), "Constructing final coalgebras with modal logic" Emily Diepenveen (Ottawa), "Relational models of the untyped lambda calculus" Brett Giles (Calgary), "Reversible computation - a restriction category view" Joachim de Lataillade (Ottawa), "Strachey parametricity and game semantics" Toby Kenney (Dalhousie), "Codistributive diads" John MacDonald (UBC), "Street orientals and Steiner n-categories" Octavio Malherbe (Ottawa), "Presheaf models of quantum lambda calculus" Dorette Pronk (Dalhousie), TBA Brian Redmond (Calgary), "Safe recursion revisited" Peter Selinger (Dalhousie), "Fibonacci objects" Benoit Valiron (Ottawa), "Semantics of higher order quantum computation" Richard Wood (Dalhousie), "Partial products" PROGRAM: A preliminary program is available at the conference website. There will be a welcoming reception on Thursday, May 29 in the Chase building, room 319. The reception will start at 5:30, and continue until 8, or as long as there are people. LOCATION AND ARRIVAL: The workshop will take place at: Chase Building, Room 319 Department of Mathematics and Statistics Dalhousie University Halifax, Nova Scotia B3H 3J5 Canada A campus map, showing the Chase building as C280, can be found at: http://www.mathstat.dal.ca/~selinger/fmcs2008/01studleymap.pdf From the airport, the most economic way to get to Halifax is by the Halifax Airporter Shuttle . This shuttle runs many times per day and reservations are not required. The one-way fare is $18. You can get off at the Lord Nelson Hotel on Spring Garden Road (a short walk to the university; see the map on the conference website). Alternatively, you can catch a taxi from the airport for $53. ACCOMMODATIONS: We have reserved a block of rooms at the King's College residences. The rate, including taxes, are $37.37 per night for a single room, and $56.04 for a double room. Reservations can be made by sending an e-mail to conferences@admin.ukings.ns.ca and mentioning "FMCS 2008". A reservation form is available from the workshop website. For those wishing to stay in a hotel or bed & breakfast, some information is available on the conference website. REGISTRATION: Please register for the meeting by emailing fmcs2008@mathstat.dal.ca. There will be an on-site registration fee of $120 to cover meeting costs. A discounted registration fee of $40 is available for students and for researchers without grant. MAPS AND LOCAL INFORMATION: Local information, including maps, is available from the conference website, http://www.mathstat.dal.ca/~selinger/fmcs2008/ PREVIOUS MEETINGS: Previous FMCS meetings were held in Pullman (1992), Portland (1993), Vancouver (1994), Kananaskis (1995), Pullman (1996), Portland (1998), Kananaskis (1999), Vancouver (2000), Spokane (2001), Hamilton (2002), Ottawa (2003), Kananaskis (2004), Vancouver (2005), Kananaskis (2006), and Hamilton (2007). ORGANIZING COMMITTEE: Robin Cockett (Calgary) John MacDonald (UBC) Phil Mulry (Colgate) Dorette Pronk (Dalhousie) Robert Seely (McGill) Peter Selinger (Dalhousie) LOCAL ORGANIZERS: Dorette Pronk (Dalhousie) Peter Selinger (Dalhousie) * From rrosebru@mta.ca Fri May 16 20:30:46 2008 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 16 May 2008 20:30:46 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1Jx9Ht-0000QF-1M for categories-list@mta.ca; Fri, 16 May 2008 20:24:33 -0300 From: Tom Hirschowitz MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Date: Fri, 16 May 2008 14:00:09 +0200 To: categories@mta.ca Subject: categories: post doc Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 21 Hi everyone, I was surprised to receive several applications for the post doc position at University of Savoy. Since at most one candidate will be hired, I thought I might draw attention to another postdoc offer in Marseille http://choco.pps.jussieu.fr/postdoc which is focused on concurrency theory. Sorry for two non mathematical messages, Tom From rrosebru@mta.ca Fri May 16 20:30:46 2008 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 16 May 2008 20:30:46 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1Jx9Ls-0000ZH-Tz for categories-list@mta.ca; Fri, 16 May 2008 20:28:40 -0300 Date: Fri, 16 May 2008 17:04:54 -0400 (EDT) From: Michael Barr To: Categories list Subject: categories: Has anyone seen this condition? 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: 22 In our (John Kennison, Bob Raphael, and I) work, the following condition has arisen. Has anyone seen or named it? Say that an object E of a category is a ???? if it is a cogenerator and if whenever f: A ---> B is not an epimorphism and g: B ---> C is a regular monomorphism, then there are two maps h,k: C ---> E s.t. hg is unequal to kg, while hgf = kgf. This is related to the questions Paul Taylor and I have raised recently. Theorem. If E satisfies ????, then whenever A has an extremal monomorphism into a power of E, then A ---> TA ===> T^2A is an equalizer where T is the triple from the adjoint pair Hom(-,E) and E^{(-)}. What's interesting is that while it is obvious that any injective cogenerator satisfies ????, it is also the case that any cogenerator that contains an injective cogenerator also satisfies ????. Thus, in completely regular spaces, the interval is a cogenerator and both it and the real line (and many, many other spaces) also satisfy ????. Michael From rrosebru@mta.ca Sat May 17 10:54:56 2008 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 17 May 2008 10:54:56 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1JxMgy-00013T-Lo for categories-list@mta.ca; Sat, 17 May 2008 10:43:20 -0300 Subject: categories: FMCS 2008, Halifax, weekend *after* next To: categories@mta.ca (Categories List) Date: Fri, 16 May 2008 23:22:41 -0300 (ADT) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit From: selinger@mathstat.dal.ca (Peter Selinger) Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 23 The subject line of my previous message suggested that FMCS is next weekend - in fact it is in two weeks. Sorry for the confusion! -- Peter From rrosebru@mta.ca Wed May 21 20:28:26 2008 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 21 May 2008 20:28:26 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1JyxSz-000749-RN for categories-list@mta.ca; Wed, 21 May 2008 20:11:29 -0300 Date: Fri, 16 May 2008 13:57:40 -0700 From: Toby Bartels To: categories@mta.ca Subject: categories: Re: A small cartesian closed concrete category 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: 24 Peter easthope wrote in part: >http://carnot.pathology.ubc.ca/FLcategory.jpg >If anyone can point out an error, that will help. This says that there is a map from 1 to 0. Surely that is a mistake? --Toby From rrosebru@mta.ca Thu May 22 21:43:57 2008 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 22 May 2008 21:43:57 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1JzL95-0000S8-G3 for categories-list@mta.ca; Thu, 22 May 2008 21:28:31 -0300 Date: Thu, 22 May 2008 09:27:08 -0700 From: PETER EASTHOPE Subject: categories: Re: A small cartesian closed concrete category To: categories@mta.ca MIME-version: 1.0 Content-type: text/plain; charset=us-ascii Content-language: en Content-transfer-encoding: 7bit Content-disposition: inline Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 25 Folk, At Fri, 16 May 2008 00:29:16 -0700 Robert L Knighten wrote, ... no morphism from 1 to 0 -- these are sets after all ... At Fri, 16 May 2008 13:57:40 -0700 Toby Bartels wrote, ... map from 1 to 0. Surely ... a mistake? Right oh, thanks. The diagram is patched. http://carnot.yi.org/FLcategory.jpg Sorry for the poor quality. I kept the file small for sake of anyone using an old modem. How about someone suggesting a name for this category. Seems worth posting as a SVG or PostScript for benefit of other novices such as me. Thanks, ... Peter E. -- http://carnot.yi.org/ http://carnot.pathology.ubc.ca/ http://members.shaw.ca/peasthope/ From rrosebru@mta.ca Sat May 24 09:47:59 2008 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 24 May 2008 09:47:59 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1JzsrI-00078C-EE for categories-list@mta.ca; Sat, 24 May 2008 09:28:24 -0300 Mime-Version: 1.0 (Apple Message framework v624) Content-Type: text/plain; charset=US-ASCII; format=flowed Content-Transfer-Encoding: 7bit From: Paul Taylor Subject: categories: discussion on Replacement at CT08 Date: Fri, 23 May 2008 22:05:36 +0100 To: Categories list Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 26 A couple of months ago, there was a discussion in this forum about categorical formulations of the Axiom-Scheme of Replacement. From this, no fewer than four approaches emerged, as follows: (1) Steve Awodey considered Algebraic Set Theory (2) Colin McLarty considered an Elementary Theory of the Category of Sets (3) Thomas Streicher considered Universes (4) I (Paul Taylor) considered iterations of a functor indexed by a well founded coalgebra. (I was going to write a one-paragraph summary of each of these, but decided that the risk of error was too great.) Following the public discussion, the four of us, together with Mike Shulman, who had raised the question in the first place, continued it in private for a while. What I wanted to achieve from this was some agreement on a metalanguage for the classes (such as a Heyting pretopos) and a statement of each formulation within this metalanguage. Then someone (else) could compare the definitions, and ask to what extent they are equivalent. (I don't want to re-open the substantive discussion at the moment, but I should point out that the objective of my formulation was to avoid the need for such a metalanguage, although this is needed to compare my view with the others.) We didn't manage to do this, but the five of us adjourned our discussion, with an agreement to re-open it later. One possibility is the Category Theory meeting in Calais next month, and I suggested to the Programme Committee that they might set aside a room for a parallel session devoted to this topic. In their response, they seem to have interpreted the proposal in a rather more formal way than we had intended. Also, it turns out that, of the five, only Steve and I will be present. So, to get to the point, Steve and I invite anyone who would like to take part in a discussion (of whatever degree of formality) about Replacement during the course of the conference to contact us privately, so that we can make arrangements with the programme committee. Paul Taylor pt08@PaulTaylor.EU Steve Awodey awodey@cmu.edu From rrosebru@mta.ca Sun May 25 10:00:43 2008 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 25 May 2008 10:00:43 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1K0Fb9-0004UL-FM for categories-list@mta.ca; Sun, 25 May 2008 09:45:15 -0300 From: Conor McBride Subject: categories: MSFP 2008: call for participation Date: Sat, 24 May 2008 17:23:39 +0100 To: conor@strictlypositive.org Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 27 +*->+*->+*->+*->+*->+*->+*->+*->+*->+*->+*->+*->+*->+*->+*->+*->+*->+*-> 2nd Workshop on MATHEMATICALLY STRUCTURED FUNCTIONAL PROGRAMMING +*->+*->+*->+*->+*->+*->+*->+*->+*->+*->+*->+*->+*->+*->+*->+*->+*->+*-> 6 July 2008 Reykjavik, Iceland co-located with ICALP 2008 http://msfp.org.uk Call for Participation **early workshop registration ends 5 June** registration via http://www.ru.is/icalp08/ The workshop on Mathematically Structured Functional Programming is devoted to the derivation of functionality from structure. It is a celebration of the direct impact of Theoretical Computer Science on programs as we write them today. Modern programming languages, and in particular functional languages, support the direct expression of mathematical structures, equipping programmers with tools of remarkable power and abstraction. Monadic programming in Haskell is the paradigmatic example, but there are many more mathematical insights manifest in programs and in programming language design: Freyd-categories in reactive programming, symbolic differentiation yielding context structures, and comonadic presentations of dataflow, to name but three. This workshop is a forum for researchers who seek to reflect mathematical phenomena in data and control. INVITED SPEAKERS *Andrej Bauer* (http://andrej.com/) of the Faculty of Mathematics and Physics, University of Ljubljana, the Institute of Mathematics, Physics and Mechanics, Slovenia, and the Mathematics and Computation weblog (http://=20 math.andrej.com/), *Dan Piponi* (http://homepage.mac.com/sigfpe/) of Industrial Light and Magic, Academy Award winner, and author of the weblog A Neighbourhood of Infinity (http://=20 sigfpe.blogspot.com/) ACCEPTED PAPERS (to appear in ENTCS) A Partial Type Checking Algorithm for System U Andreas Abel and Thorsten Altenkirch What is a Categorical Model of Arrows? Robert Atkey Yet another implementation of attribute evaluation Eric Badouel, Bernard Fotsing, and Rodrigue Tchougong Algebraic Specialization of Generic Functions for Recursive Types Alcino Cunha and Hugo Pacheco Modularity and Implementation of Mathematical Operational Semantics Mauro Jaskelioff, Neil Ghani, and Graham Hutton Idioms are oblivious, arrows are meticulous, monads are promiscuous Sam Lindley, Jeremy Yallop, and Philip Wadler Simulating Finite Eilenberg Machines with a Reactive Engine Benoit Razet The recursion scheme from the cofree recursive comonad Tarmo Uustalu and Varmo Vene PROGRAMME COMMITTEE Yves Bertot, INRIA, Sophia-Antipolis Venanzio Capretta (co-chair), Radboud University, Nijmegen Jacques Carette, McMaster University, Ontario Thierry Coquand, Chalmers University, G=F6teborg Andrzej Filinski, K=F8benhavns Universitet Jean-Christophe Filli=E2tre, LRI, Universit=E9 Paris Sud Jeremy Gibbons, Oxford University Andy Gill, Galois Peter Hancock, University of Nottingham Oleg Kiselyov, FNMOC Paul Blain Levy, University of Birmingham Andres L=F6h, Utrecht University Marino Miculan, Universit=E0 di Udine Conor McBride (co-chair), Alta Systems, Northern Ireland James McKinna, Radboud University, Nijmegen Alex Simpson, University of Edinburgh Tarmo Uustalu, Institute of Cybernetics, Tallinn We're delighted to be able to present such a strong line-up of invited and contributed talks, and we warmly invite you to come and enjoy the fun. Early workshop registration closes on 5 June, and Iceland gets busy in the summer, so do book now to avoid disappointment. Looking forward to seeing you in Iceland Venanzio Capretta Conor McBride From rrosebru@mta.ca Sun May 25 10:00:43 2008 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 25 May 2008 10:00:43 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1K0Faa-0004TB-RJ for categories-list@mta.ca; Sun, 25 May 2008 09:44:40 -0300 Date: Thu, 22 May 2008 22:49:22 +0200 (MEST) To: LICS List From: Kreutzer + Schweikardt Subject: categories: LICS 2008 Call for Participation Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 28 LICS 2008 - CALL FOR PARTICIPATION The twenty-third annual IEEE symposium on logic in computer science (LICS 2008) will be held at Carnegie Mellon University in Pittsburgh, Pennsylvania, USA, June 24th-27th 2008. It will be colocated with the IEEE Computer Security Foundations Symposium (CSF). The LICS 2008 program includes invited talks by David Basin (ETH Zurich), Martin Grohe (Humboldt University Berlin), Dexter Kozen (Cornell University), and Yiannis Moschovakis (UCLA and University of Athens). Registration for LICS 2008 is open. The deadline for early registration is June 1, 2008. Late registration (at higher cost) will be available until June 10, after which registration requires special arrangement with the conference organizers. A link to the online registration form can be found on the LICS 2008 webpage at http://www.informatik.hu-berlin.de/lics/lics08/ The online registration page can also be used to reserve a room in the CMU campus dormitories, if required. The LICS 2008 webpage further contains information about reserving a hotel room if you prefer that option. Blocks of hotels for LICS participants are being held until June 2, so if you plan to reserve a hotel room please do so before then. From rrosebru@mta.ca Sun May 25 10:00:43 2008 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 25 May 2008 10:00:43 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1K0Fbx-0004WD-9Z for categories-list@mta.ca; Sun, 25 May 2008 09:46:05 -0300 Date: Sun, 25 May 2008 09:54:14 +0200 From: Andree Ehresmann To: categories@mta.ca Subject: categories: Cahiers are online MIME-Version: 1.0 Content-Type: text/plain;charset=ISO-8859-1;DelSp="Yes";format="flowed" Content-Disposition: inline Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 29 I am pleased to inform you that all the former volumes of the "Cahiers" are now freely available on the NUMDAM site: http://www.numdam.org/numdam-bin/feuilleter?j=CTGDC (for volumes from VIII to XLVII (2006) and http://www.numdam.org/numdam-bin/feuilleter?j=SE (under the title "Seminaire Ehresmann") for Volumes I to VIII. From now on, all the papers will be so available less than 2 years after the printed publication. Hoping this will be useful for readers and authors, Sincerely Andree C. Ehresmann From rrosebru@mta.ca Mon May 26 20:15:55 2008 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 26 May 2008 20:15:55 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1K0ldy-0007Me-15 for categories-list@mta.ca; Mon, 26 May 2008 19:58:18 -0300 Date: Sun, 25 May 2008 11:10:51 -0400 (EDT) From: Michael Barr To: categories@mta.ca Subject: categories: Re: Cahiers are online 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: 30 Let me congratulate Andree for having done this. My attitude is that the more mathematics is freely available online, the more the profession will benefit. That is why all my own papers that I can find online (many the result of McGill's subscription and not generally available) can be found at ftp.math.mcgill.ca/pub/barr/pdffiles. I am, of course, violating copyrights in doing so, so sue me. I will add my Cahiers papers to the collection as soon as I have time. Michael On Sun, 25 May 2008, Andree Ehresmann wrote: > I am pleased to inform you that all the former volumes of the > "Cahiers" are now freely available on the NUMDAM site: > http://www.numdam.org/numdam-bin/feuilleter?j=CTGDC > (for volumes from VIII to XLVII (2006) > and > http://www.numdam.org/numdam-bin/feuilleter?j=SE > (under the title "Seminaire Ehresmann") for Volumes I to VIII. > From now on, all the papers will be so available less than 2 years > after the printed publication. > > Hoping this will be useful for readers and authors, > > Sincerely > Andree C. Ehresmann > > > > From rrosebru@mta.ca Mon May 26 20:15:55 2008 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 26 May 2008 20:15:55 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1K0lff-0007Rc-5J for categories-list@mta.ca; Mon, 26 May 2008 20:00:03 -0300 Date: Sun, 25 May 2008 21:27:51 +0200 From: lamarche@loria.fr To: categories@mta.ca Subject: categories: Workshop on Deep Inference, Nancy 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: 31 (a reminder for many, an announcement for others, and perhaps something v= erging on spam for some, with apologies) The workshop Deep Inference, its Algebra, Geometry and Syntax Will be held in Nancy, France on June 18 2008. As the title implies the main theme of the workshop is deep inference, but talks on related subjects like the the improvement and abstract theory of proof formalisms are most welcome. The workshop will be held at the Loria computer science lab on Wednesday June 18 2008, starting at 10:30, so as to ensure an easy commute from Paris (there is a Paris-Nancy TGV that leaves Gare de l'Est at 8:12 and the last return train leaves Nancy at 20:15). The webpage http://www.loria.fr/~lamarche/deepinf.html contains a few more details, including suggestions for accomodation. Please contact me if you intend to attend and/or give a talk. Fran=E7ois Lamarche From rrosebru@mta.ca Mon May 26 20:15:55 2008 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 26 May 2008 20:15:55 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1K0leh-0007P3-RE for categories-list@mta.ca; Mon, 26 May 2008 19:59:03 -0300 Date: Sun, 25 May 2008 11:50:22 -0400 From: "Fred E.J. Linton" To: Subject: categories: Re: A small cartesian closed concrete category 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: 32 Is it worth noting, in this jpeg, that the arithmetical > max(1-A, B) = for B^A coincides here with the Boolean > {not}-A or B = for the classical B =3D> A? Cheers, -- Fred ------ Original Message ------ Received: Thu, 22 May 2008 08:54:54 PM EDT From: PETER EASTHOPE To: categories@mta.ca Subject: categories: Re: A small cartesian closed concrete category > Folk, > = > At Fri, 16 May 2008 00:29:16 -0700 Robert L Knighten wrote, > .. no morphism from 1 to 0 -- these are sets after all ... > = > At Fri, 16 May 2008 13:57:40 -0700 Toby Bartels wrote, > .. map from 1 to 0. Surely ... a mistake? > = > Right oh, thanks. The diagram is patched. > http://carnot.yi.org/FLcategory.jpg > = > Sorry for the poor quality. I kept the file small for sake > of anyone using an old modem. > = > How about someone suggesting a name for this category. > Seems worth posting as a SVG or PostScript for benefit > of other novices such as me. > = > Thanks, ... Peter E. > = > -- = > http://carnot.yi.org/ > http://carnot.pathology.ubc.ca/ > http://members.shaw.ca/peasthope/ From rrosebru@mta.ca Tue May 27 09:25:00 2008 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 27 May 2008 09:25:00 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1K0y8M-0004Xv-AV for categories-list@mta.ca; Tue, 27 May 2008 09:18:30 -0300 Date: Tue, 27 May 2008 10:01:43 +0200 (MEST) From: Patrik Eklund To: categories@mta.ca Subject: categories: Post doc position 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: 33 A postdoc position (2 years) in AI will be announced now very soon at Umea University, Department of Computing Science. We look forward also to applications from logicians with a strong categorical background. Applications are developed e.g. within health care. For further information, please send a message. Best regards, Patrik From rrosebru@mta.ca Tue May 27 09:25:00 2008 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 27 May 2008 09:25:00 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1K0y97-0004bP-TS for categories-list@mta.ca; Tue, 27 May 2008 09:19:17 -0300 Date: Mon, 26 May 2008 09:29:35 -0600 From: ICLP 08 Subject: categories: ICLP'08 CALL FOR PAPERS To: undisclosed-recipients:; Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 34 CALL FOR PAPERS ICLP'08 24th International Conference on Logic Programming Udine, Italy, December 9th-13th, 2008 http://iclp08.dimi.uniud.it CONFERENCE SCOPE ---------------- Since the first conference held in Marseilles in 1982, ICLP has been the premier international conference for presenting research in logic programming. Contributions (papers, position papers, and posters) are sought in all areas of logic programming including but not restricted to: * Theory: Semantic Foundations, Formalisms, Nonmonotonic Reasoning, Knowledge Representation. * Implementation: Compilation, Memory Management, Virtual Machines, Parallelism. * Environments: Program Analysis, Program Transformation, Validation and Verification, Debugging, Profiling, Integration. * Language Issues: Extensions, Integration with Other Paradigms, Concurrency, Modularity, Objects, Coordination, Mobility, Higher Order, Types, Modes, Programming Techniques. * Related Paradigms: Abductive Logic Programming, Inductive Logic Programming, Constraint Logic Programming, Answer-Set Programming. * Applications: Databases, Data Integration and Federation, Software Engineering, Natural Language Processing, Web and Semantic Web, Agents, Artificial Intelligence, Bioinformatics The three broad categories for submissions are: (1) Technical papers, providing novel research contributions, innovative perspectives on the field, and/or novel integrations across different areas; (2) Application papers, describing innovative uses of logic programming technology in real-world application domains; (3) Posters, ideal for presenting and discussing current work, not yet ready for publication, for PhD thesis summaries and research project overviews. A separate session dedicated to the celebration of the 20th anniversary of stable model semantics will also be part of the program. Accepted papers and posters will be allocated time for presentation during the conference. At least one author of each accepted submission is expected to register and participate in the event. In addition to papers and posters, the technical program will include invited talks, advanced tutorials, specialized sessions, workshops, and a Doctoral Student Consortium. Details, as they become available will be posted at: http://iclp08.dimi.uniud.it PAPERS AND POSTERS ------------------ Papers and posters must describe original, previously unpublished research, and must not be simultaneously submitted for publication elsewhere. Emphasis will be placed on the novelty and innovative nature of the results (even if not completely polished and refined). All submissions will be peer-reviewed by an international panel. Submissions MUST contain substantial original, unpublished material. All submissions must be written in English. Technical papers and application papers must not exceed 15 pages in the Springer LNCS format (see http://www.springeronline.com/lncs/) The limit for posters is 5 pages in the same format. The primary means of submission will be electronic, through the Easychair submission system. The submission page is available at http://www.easychair.org/conferences/?conf=ICLP08 APPLICATION PAPERS ------------------ Within the scope of the general call for papers for the upcoming 24th International Conference on Logic Programming, we would like to draw the attention of researchers and practitioners on the opportunity to submit manuscripts to the Application Track of the conference. Application papers, are expected to describing complex and/or real-world applications that rely in an essential manner on the use of logic programming technology. Description of innovative applications as well as engineering solutions leveraging logic programming technology are solicited. Papers must describe original, previously unpublished results, and must not be simultaneously submitted for publication elsewhere. Submissions MUST contain substantial original, unpublished material. All submissions must be written in English. Application papers should be structured to emphasize: * the application domain, in terms understandable by a layman * the specific problem addressed within the application domain, stressing importance and complexity * a clear discussion of the unique need for logic programming technology to address the problem * a clear description of the application developed and its evaluation. PUBLICATION ----------- The proceedings of the conference will be published by Springer-Verlag in the LNCS series. All accepted papers and posters will be included in the proceedings. WORKSHOPS --------- The ICLP'08 program will include several workshops. They are perhaps the best place for the presentation of preliminary work, novel ideas, and new open problems to a more focused and specialized audience. Workshops also provide a venue for presenting specialised topics and opportunities for intensive discussions and project collaboration in any areas related to logic programming, including cross-disciplinary areas. DOCTORAL CONSORTIUM ------------------- The Doctoral Consortium (DC) on Logic Programming is the 4th Doctoral consortium to provide doctoral students with the opportunity to present and discuss their research directions, and to obtain feedback from both peers and word-renown experts in the field. The DC will also offer invited speakers and panel discussions. Accepted participants will receive partial financial support to attend the event and the main conference. The best paper and presentation from the DC will be given the opportunity to present in special session of the main ICLP conference. CELEBRATING 20th YEARS OF STABLE MODEL SEMANTICS ------------------------------------------------ The year 2008 marks the 20th anniversary of the publication that introduced the stable model semantics for logic programs with negation. The paper titled "The stable semantics for logic programs" by Michael Gelfond and Vladimir Lifschitz was presented at ICLP-1988. It was a momentous event that gave rise to a vibrant subfield of logic programming known now as the answer-set programming. Its distinguishing aspects are close connections to the fields of knowledge representation, satisfiability and constraint satisfaction, ever faster computational tools, and a growing list of successful applications. To celebrate the stable-model semantics, there will be a special session at ICLP 2008 dedicated to answer-set programming. The session will feature talks by Michael Gelfond and Vladimir Lifschitz. as well as by other major contributions to the field, presenting personal perspectives on the stable-model semantics, its impact and its future. There will be a panel discussion, and regular accepted ICLP papers falling into the answer-set programming area will complete the program. CONFERENCE VENUE ---------------- The conference will be held in the city of Udine, the capital of the historical region of Friuli, Italy. Located between the Adriatic sea and the Alps, close to Venice, Austria and Slovenia, Udine is a city of Roman origins, funded by Emperor Otto in 983. Rich of historical sites, Udine is also famous for its commercial and shopping opportunities and its outstanding wine and culinary traditions. SUPPORT SPONSORING AND AWARDS ----------------------------- The conference is sponsored by the Association for Logic Programming (ALP). The ALP has funds to assist financially disadvantaged participants. The ALP is planning to sponsor two awards for ICLP 2008: for the best technical paper and for the best student paper. IMPORTANT DATES --------------- Papers Posters Abstract submission deadline June 2nd n/a Submission deadline June 9th August 15th Notification of authors August 1st September 1st Camera-ready copy due September 15th September 15th 20 Years of Stable Models TBA Doctoral Consortium TBA Workshop Proposals June 2nd Early-bird Registration TBA Conference December 9-13, 2008 ICLP'2008 ORGANIZATION ---------------------- General Chair: Agostino Dovier (University of Udine) Program Co-Chairs: Maria Garcia de la Banda (Monash University) Enrico Pontelli (New Mexico State University) Workshop Chair: Tran Cao Son (New Mexico State University) Doctoral Student Consortium: David Warren (SUNY Stony Brook) Tom Schrijvers (K.U.Leuven) Publicity Co-Chairs: Marcello Balduccini (Kodak Research Labs) Alessandro Dal Palu' (University of Parma) Programming Competition Chair: Bart Demoen (K.U.Leuven) 20 Years of Stable Models: Mirek Truszczynski (University of Kentucky) Andrea Formisano (University of Perugia) Program Committee: Salvador Abreu Sergio Antoy Pedro Barahona Chitta Baral Gerhard Brewka Manuel Carro Michael Codish Alessandro Dal Palu' Bart Demoen Agostino Dovier John Gallagher Michael Gelfond Carmen Gervet Gopal Gupta Manuel Hermenegildo Andy King Michael Maher Juan Moreno Navarro Alberto Pettorossi Brigitte Pientka Gianfranco Rossi Fariba Sadri Vitor Santos Costa Tran Cao Son Paolo Torroni Frank Valencia Mark Wallace Web Master: Raffaele Cipriano Local Arrangements Committee: Alberto Casagrande Elisabetta De Maria Luca Di Gaspero Carla Piazza ---------------------------------------------------- For further information: iclp08@cs.nmsu.edu http://iclp08.dimi.uniud.it From rrosebru@mta.ca Wed May 28 10:03:27 2008 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 28 May 2008 10:03:27 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1K1L6c-0002pO-Fa for categories-list@mta.ca; Wed, 28 May 2008 09:50:14 -0300 Date: Tue, 27 May 2008 19:39:23 +0100 From: Maria Manuel Clementino MIME-Version: 1.0 To: categories@mta.ca Subject: categories: Post doc grants Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 35 Our national Foundation for Sciences and Technology (http://alfa.fct.mctes.pt/ ) accepts applications for post doc grants. The Regulations can be found at http://alfa.fct.mctes.pt/apoios/bolsas/regulamento2008 [in Portuguese]. In order to apply the candidate needs the support of a supervisor, working in a Portuguese university. For further information, please send a message. Regards, Maria Manuel Clementino From rrosebru@mta.ca Thu May 29 08:30:43 2008 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 29 May 2008 08:30:43 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1K1gC6-0007j8-Ge for categories-list@mta.ca; Thu, 29 May 2008 08:21:18 -0300 From: rlc3@mcs.le.ac.uk (Roy L. Crole) To: categories@mta.ca, types@cis.upenn.edu Subject: categories: Funded PhD Student (GTA) positions Date: Thu, 29 May 2008 10:33:15 +0100 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: 36 Dear Colleagues, The Department of Computer Science in the University of Leicester, UK, is offering two new Graduate Teaching Assistant (GTA) positions. The deadline for applications is June 16th. The application forms and further details are here: http://www.le.ac.uk/personnel/supportjobs/s3759a.html A GTA is a funded PhD student who is expected to undertake teaching duties during the ten week teaching periods of each of our two annual semesters (roughly, subsets of October to December and January to March). These positions should be of special interest to readers of the Categories and Types mailing lists, with both of these research areas being very active within the Department. Roy Crole. From rrosebru@mta.ca Thu May 29 08:30:43 2008 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 29 May 2008 08:30:43 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1K1gBY-0007hJ-50 for categories-list@mta.ca; Thu, 29 May 2008 08:20:44 -0300 Mime-Version: 1.0 (Apple Message framework v753) Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed To: categories@mta.ca From: Sam Staton Subject: categories: General notions of equivalence and exactness Date: Thu, 29 May 2008 10:01:31 +0100 Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 37 Hello. In a category with pullbacks, say that a binary relation X <- R -> Y is "z-closed" if it satisfies the following axiom (interpreted as usual): If x R y and x' R y and x' R y' then x R y'. (The "z" in "z-closed" refers to the pattern of variables in the premise.) Z-closedness seems to be a sensible generalization of "equivalence" to relations between two different objects. (e.g. In computer science, it is common to relate the state spaces of two different systems.) Note that an endorelation is an equivalence relation if and only if it is z-closed and reflexive. Also note that, in an abelian category, every relation is z-closed. The [z-closed v. equivalence] connection seems to extend to [pullbacks v. kernel pairs]. Every span that arises from a pullback is a z-closed relation. Say that a category is "z-effective" if every z-closed relation arises as a pullback. - every abelian category is straightforwardly z-effective; - in a topos, every z-closed relation arises as a pullback span. Indeed, an extensive regular category has effective equivalence relations if and only if it is z-effective. These notions and ideas seem quite elementary, even fundamental, and I would be surprised if no-one had thought of them before. I borrowed the terminology "z-closed" from a paper by Erik de Vink and Jan Rutten (Theoret Comput Sci, 221:271-293, 1999) but I couldn't find any other references. Have I missed something? I'd be grateful for any observations or suggestions. Sam PS. I'd like to take the opportunity to acknowledge the helpful replies (public and private) to my question about W-types, a few months ago. From rrosebru@mta.ca Thu May 29 15:59:39 2008 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 29 May 2008 15:59:39 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1K1nA9-0004Zv-9w for categories-list@mta.ca; Thu, 29 May 2008 15:47:45 -0300 From: Nick Benton To: Sam Staton , "categories@mta.ca" Date: Thu, 29 May 2008 05:43:57 -0700 Subject: categories: RE: General notions of equivalence and exactness Content-Language: en-US Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 38 Hi Sam, These "zigzag closed" relations are called "difunctional". Some old referen= ces are: [1] J Riguet. Relations binaries, fermetures, correspondances de Galois (19= 48) [2] J Riguet. Quelques proprieties des relations difonctionelles (1950) [3] Katuzi Ono. On some properties of binary relations (1957). and once one knows what to search for, it turns out they're well-known. An interesting characterization (which is how we(*) discovered them) is tha= t in sets, they're the TT-closed relations, where if x,x'\in A, x(R^TT)x' i= f forall k k' : A->2, (forall y y', yRy' -> k y =3D k y') -> k x =3D k x' ([4] M Abadi. TT-closed relations and admissibility (2000) considers the situation in cpos). Nick (*) Martin Hofmann, Andrew Kennedy, Lennart Beringer and I. Martin initiall= y called these Quasi-PERs. -----Original Message----- From: cat-dist@mta.ca [mailto:cat-dist@mta.ca] On Behalf Of Sam Staton Sent: 29 May 2008 10:02 To: categories@mta.ca Subject: categories: General notions of equivalence and exactness Hello. In a category with pullbacks, say that a binary relation X <- R -> Y is "z-closed" if it satisfies the following axiom (interpreted as usual): If x R y and x' R y and x' R y' then x R y'. (The "z" in "z-closed" refers to the pattern of variables in the premise.) Z-closedness seems to be a sensible generalization of "equivalence" to relations between two different objects. (e.g. In computer science, it is common to relate the state spaces of two different systems.) Note that an endorelation is an equivalence relation if and only if it is z-closed and reflexive. Also note that, in an abelian category, every relation is z-closed. The [z-closed v. equivalence] connection seems to extend to [pullbacks v. kernel pairs]. Every span that arises from a pullback is a z-closed relation. Say that a category is "z-effective" if every z-closed relation arises as a pullback. - every abelian category is straightforwardly z-effective; - in a topos, every z-closed relation arises as a pullback span. Indeed, an extensive regular category has effective equivalence relations if and only if it is z-effective. These notions and ideas seem quite elementary, even fundamental, and I would be surprised if no-one had thought of them before. I borrowed the terminology "z-closed" from a paper by Erik de Vink and Jan Rutten (Theoret Comput Sci, 221:271-293, 1999) but I couldn't find any other references. Have I missed something? I'd be grateful for any observations or suggestions. Sam PS. I'd like to take the opportunity to acknowledge the helpful replies (public and private) to my question about W-types, a few months ago. From rrosebru@mta.ca Thu May 29 15:59:40 2008 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 29 May 2008 15:59:40 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1K1nBO-0004hO-Je for categories-list@mta.ca; Thu, 29 May 2008 15:49:02 -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: Marco Grandis Subject: categories: Re: General notions of equivalence and exactness Date: Thu, 29 May 2008 15:24:59 +0200 Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 39 In Genoa, in the late 60's and after, our group was studying categories of relations. I was interested in relations on abelian categories, for homological algebra, while Gabriele Darbo, Franco Parodi and others were more interested - after the general construction - in relations on sets, and even more in "corelations on sets" (relations on Set^op), called "transductors". (It is the dual construction, based on equivalence classes of cospans of sets, i.e. quotients of the sum of domain and codomain; used to simulate electric connections between two sets of terminals [see how they compose], and as a formal basis for a general "theory of devices".) At that time, a category with involution u |--> u* (typically, a category of relations in some sense) was called "von Neumann regular" if the condition u.u*.u = u holds for every arrow (plainly related to von Neumann regularity of semigroups and rings). The category of relations of sets is not vN-regular, the simplest counterexample being likely the Z-shaped relation which transgresses your condition: R: {x, y} --> {x', y'} x R y, x' R y, x' R y' This relation was precisely called "Z" in the paper [Pa] F. Parodi, Simmetrizzazioni di una categoria II, Sem. Mat. Univ. Padova, 44 (1970), 223-262. http://archive.numdam.org/ARCHIVE/RSMUP/RSMUP_1970__44_/ RSMUP_1970__44__223_0/RSMUP_1970__44__223_0.pdf On the other hand, as you say, category of relations on abelian categories are von Neumann regular (which is a crucial fact in studying subquotients, see Mac Lane's text on Homology). But, interestingly, the category of CORELATIONS on sets is also von Neumann regular, see the paper above [Pa]. Best regards Marco Grandis On 29 May 2008, at 11:01, Sam Staton wrote: > Hello. In a category with pullbacks, say that a binary relation > X <- R -> Y > is "z-closed" if it satisfies the following axiom (interpreted as > usual): > > If x R y and x' R y and x' R y' then x R y'. > > (The "z" in "z-closed" refers to the pattern of variables in the > premise.) > > Z-closedness seems to be a sensible generalization of "equivalence" > to relations between two different objects. (e.g. In computer > science, it is common to relate the state spaces of two different > systems.) Note that an endorelation is an equivalence relation if and > only if it is z-closed and reflexive. Also note that, in an abelian > category, every relation is z-closed. > > The [z-closed v. equivalence] connection seems to extend to > [pullbacks v. kernel pairs]. Every span that arises from a pullback > is a z-closed relation. Say that a category is "z-effective" if every > z-closed relation arises as a pullback. > > - every abelian category is straightforwardly z-effective; > - in a topos, every z-closed relation arises as a pullback span. > Indeed, an extensive regular category has effective equivalence > relations if and only if it is z-effective. > > These notions and ideas seem quite elementary, even fundamental, and > I would be surprised if no-one had thought of them before. I borrowed > the terminology "z-closed" from a paper by Erik de Vink and Jan > Rutten (Theoret Comput Sci, 221:271-293, 1999) but I couldn't find > any other references. > > Have I missed something? I'd be grateful for any observations or > suggestions. > > Sam > > PS. I'd like to take the opportunity to acknowledge the helpful > replies (public and private) to my question about W-types, a few > months ago. > > > From rrosebru@mta.ca Thu May 29 15:59:40 2008 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 29 May 2008 15:59:40 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1K1nAj-0004eF-Vn for categories-list@mta.ca; Thu, 29 May 2008 15:48:22 -0300 Subject: categories: Re: General notions of equivalence and exactness (fwd) To: categories@mta.ca Date: Thu, 29 May 2008 10:16:00 -0300 (ADT) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit From: rjwood@mathstat.dal.ca (RJ Wood) Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 40 Dear Sam I believe that you'll find `Frobenius objects in cartesian bicategories' by Bob Walters and me, #3 in volume 20 of TAC, interesting. It is precisely this closing of Z-configurations to give an X-configuration that translates the Frobenius condition in the cartesian bicategory of profunctors. It has been known for a long time, but I think unpublished until our paper appeared, that the Frobenius objects in profunctors are groupoids. The paper by Bob W and me shows that this admits considerable generalization. Best regards Richard Wood Hello. In a category with pullbacks, say that a binary relation X <- R -> Y is "z-closed" if it satisfies the following axiom (interpreted as usual): If x R y and x' R y and x' R y' then x R y'. (The "z" in "z-closed" refers to the pattern of variables in the premise.) Z-closedness seems to be a sensible generalization of "equivalence" to relations between two different objects. (e.g. In computer science, it is common to relate the state spaces of two different systems.) Note that an endorelation is an equivalence relation if and only if it is z-closed and reflexive. Also note that, in an abelian category, every relation is z-closed. The [z-closed v. equivalence] connection seems to extend to [pullbacks v. kernel pairs]. Every span that arises from a pullback is a z-closed relation. Say that a category is "z-effective" if every z-closed relation arises as a pullback. - every abelian category is straightforwardly z-effective; - in a topos, every z-closed relation arises as a pullback span. Indeed, an extensive regular category has effective equivalence relations if and only if it is z-effective. These notions and ideas seem quite elementary, even fundamental, and I would be surprised if no-one had thought of them before. I borrowed the terminology "z-closed" from a paper by Erik de Vink and Jan Rutten (Theoret Comput Sci, 221:271-293, 1999) but I couldn't find any other references. Have I missed something? I'd be grateful for any observations or suggestions. Sam PS. I'd like to take the opportunity to acknowledge the helpful replies (public and private) to my question about W-types, a few months ago. From rrosebru@mta.ca Sat May 31 08:17:42 2008 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 31 May 2008 08:17:42 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1K2OrS-0003Ac-G2 for categories-list@mta.ca; Sat, 31 May 2008 08:02:58 -0300 From: Peter Freyd Date: Fri, 30 May 2008 14:34:01 -0400 To: categories@mta.ca Subject: categories: Mal'cev allegories 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: 41 Sam Staton asks about relations with the property: If x R y and x' R y and x' R y' then x R y'. Given an equational theory all relations in its category of models satisfy this property iff there's a Mal'cev operator,(a favorite topic among "universal algebraists"). Years ago I used the phrase Mal'cev property (MP) to mean that all relations in an allegory satisfy the condition. Some easy lemmas: MP implies all reflexive relations are symmetric (RIS). RIS implies equivalence relations commute (ERC). MP implies all reflexive relations are transitive (RIT). RIT implies ERC. ERC implies that the smallest equivalence relation containing a given pair of equivalence relations is their composition and that easily implies that the lattice of equivalence relations on any object is a modular lattice. ERC does not imply MP (there are simple examples for RIS not implying RIT and RIT not implying RIS). But in an allegory in which every relation is spanned by a pair of maps (in particular, in the calculus of relations arising from any regular category) it's easy to see that ERC does implies MP. For the record: txyz is defined to be a Mal'cev operator if it satisfies the two equations txxz = z txzz = x. In any theory that includes the theory of groups xy^{-1}z is such. For Heyting algebras take txyz = ((x -> y) -> z) ^ ((z -> y) -> z). That generalizes to a one-object division allegory: tPQR = (R/(1 ^ (R\Q))) ^ (R/(1 ^ (P\Q))). The provably simplest Mal'cev theory has one binary operation x*y and one equation x*(y*x) = y (e.g. in the presence of a group structure x*y = x^{-1}y^{-1}). Take txyz = (x*x)*(z*(x*y)). There are another 23 Mal'cev terms of the same size. If one weakens the theory of groups to the theory of quasigroups: that is, three binary relations and four equations (x/y)y = x x(x\y) = y (xy)/y = x x\(xy) = y then txyz = (x/x)\((x/y)z) is a Mal'cev operator. If we stick to terms of the same size there are 72 versions. Heavenly. But this one uses only the first and fourth equation (and, consequently, its mirror image uses only the second and third equations). The fact that the existence of a Mal'cev operator implies that congruence lattices are modular was well known by universal algebraists.