From MAILER-DAEMON Thu Nov 14 22:44:48 2002 Date: 14 Nov 2002 22:44:48 -0400 From: Mail System Internal Data Subject: DON'T DELETE THIS MESSAGE -- FOLDER INTERNAL DATA Message-ID: <1037328288@mta.ca> X-IMAP: 1037328280 0000000142 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 Wed Oct 31 20:06:40 2001 -0400 >From cat-dist@mta.ca Wed Oct 31 20:06:40 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 31 Oct 2001 20:06:40 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 15z5Hz-0002Ek-00 for categories-list@mta.ca; Wed, 31 Oct 2001 20:00:55 -0400 Message-ID: <3BE08AB3.969A3A84@it.uts.edu.au> Date: Thu, 01 Nov 2001 10:35:15 +1100 From: Barry Jay X-Mailer: Mozilla 4.77 [en] (X11; U; SunOS 5.8 sun4u) X-Accept-Language: en MIME-Version: 1.0 To: categories@mta.ca Subject: categories: Re: Computing with Category Theory References: <3BE0262D.8020805@bu.edu> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Content-Transfer-Encoding: 7bit Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: X-Keywords: X-UID: 1 Dear Saul, I can envisage at least two distinct ways of computing with categories. One is for category theorists to use computers to do their calculation or perhaps even provide formal proofs of theorems. The second is to use ideas from category theory as a guide to the design of programming languages. For example, the use of monads to control computational effects. One strand of the latter approach is to incorporate into programming the use of functors, and their associated operations, like mapping. This began with Charity (Cockett and Fukushima). Since then functors have been represented in Haskell using a type class, have appeared in the type system in Functorial ML (Belle, Jay and Moggi) and most recently the constructor calculus (Jay). In the latter all data structures, including those defined by users, can be represented using a fixed, finite set of constructors, derived from basic categorical concepts. Then polymorphic functions for mapping, folding etc. can be defined by pattern-matching over the basic constructors. Details can be found in my recent paper at Typed Lambda-Calculi and their Applications, or in the technical report at http://www-staff.it.uts.edu.au/~cbj/Publications/constructors.ps. These ideas have been realised in a new language FISh2 currently under development. Yours, Barry Jay Saul Youssef wrote: > > Greetings to all, > > I'm a big fan of category theory, but doesn't it seem strange > that after all this time > there is no programming language that let's you organize things around > categorical ideas? > I've semi-seriously tried to find out about this ( > http://physics.bu.edu/~youssef/aldor/aldor.html ) > but I basically don't have an answer. I'd be very interested to hear if > anyone > is working in this direction or comments about why this hasn't happened. > > Saul Youssef > http://physics.bu.edu/~youssef/ -- Associate Professor C.Barry Jay, Phone: (61 2) 9514 1814 Associate Dean (RPP), Faculty of IT www-staff.it.uts.edu.au/~cbj University of Technology, Sydney. CRICOS Provider 00099F From rrosebru@mta.ca Thu Nov 1 16:31:35 2001 -0400 >From cat-dist@mta.ca Thu Nov 01 16:31:35 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 01 Nov 2001 16:31:35 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 15zOJt-00055m-00 for categories-list@mta.ca; Thu, 01 Nov 2001 16:20:10 -0400 Message-ID: <3BE10074.9090400@bu.edu> Date: Thu, 01 Nov 2001 02:57:40 -0500 From: Saul Youssef Organization: Boston University User-Agent: Mozilla/5.0 (X11; U; Linux 2.2.17-14 i686; en-US; rv:0.9.1) Gecko/20010607 Netscape6/6.1b1 X-Accept-Language: en-us MIME-Version: 1.0 To: categories@mta.ca Subject: categories: Re: Computing with Category Theory References: <3BE0262D.8020805@bu.edu> <3BE08AB3.969A3A84@it.uts.edu.au> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 2 Hi Barry & Phil, Thanks for the answers. I knew about Charity and ML but not Fish & Fish2 or CAML (the word "category" does not appear on either the Fish or CAML web pages!). Barry Jay wrote: >Dear Saul, > >I can envisage at least two distinct ways of computing with categories. >One is for category theorists to use computers to do their calculation >or perhaps even provide formal proofs of theorems. The second is to use >ideas from category theory as a guide to the design of programming >languages. For example, the use of monads to control computational >effects. > I didn't explain what I'm interested in very well, but I don't think that it's either of your distinct ways above. I'm not thinking about automatic diagram chasing or proof assistance or something like that. I'm also don't have in mind regular functional languages that are defined using category theory (although I can see that these things are quite neat). Maybe it's best if I put it this way. There are lots of people around doing mathematical software in, say, C++, Maple or Mathematica or home grown systems. These systems are fine for, say, defining integers or functions or vector spaces or groups, but are essentially hopeless for categories, functors, adjoints, etc. Even the most basic constructions of category theory are very awkward to deal with at best. This, it seems to me, is a crippling limitation of these systems compared to what would be possible if you could only define categories and functors with the ease that you define matrices and functions. I guess I'm asking for a language where you could mix "regular math stuff" and category theory with ease as is done in mathematics on paper. A language or system suitable for writing large general purpose math libraries, say, that use category theory concepts at least as the high level organizing principles. Wouldn't that be nice? This wasn't a problem before, but now that I know some category theory, it pains me greatly! I also find it strange that this isn't a big priority, in, for instance, the CS community. I'll have a look at your technical report too. Cheers, Saul Youssef From rrosebru@mta.ca Fri Nov 2 16:45:40 2001 -0400 >From cat-dist@mta.ca Fri Nov 02 16:45:40 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 02 Nov 2001 16:45:40 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 15zkyc-0003jl-00 for categories-list@mta.ca; Fri, 02 Nov 2001 16:31:42 -0400 Message-ID: <619D900E4E53D41199CF00062939E601029D4225@mrh_mail.sbhd.com> From: WMorris@mhs-net.com To: categories@mta.ca Subject: categories: Relations, Functions, Operations. Date: Fri, 2 Nov 2001 10:06:36 -0500 MIME-Version: 1.0 X-Mailer: Internet Mail Service (5.5.2653.19) Content-Type: text/plain; charset="iso-8859-1" Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 3 I don't know if this is the correct site for this question. If not, if anyone has info on general math bulletin boards, it would be greatly appreciated. thanks!! I understand a relation is a set, and you can have an ordered pair, ie (V,E), where E is a binary relation on V. This of course is a graph. Functions are just a type of relation, with the added specifics that each element of a set S must correspond with another unique element in S or say another set T. Hence a function is also a set of these pairings, ie f:S->T. What are operations, though? Are these sets as well? Can they be described as a set. If I look closely at the definition, an operation C on sets, C:A->A is just like a function. Is an operation just a specialized function with the added requirement that the mapping be from set A to itself, ie closure? If this is the case, then, are all operations functions, and all functions relations?? Finally, does the general definition of operation require closure on the set?? From rrosebru@mta.ca Mon Nov 5 10:03:57 2001 -0400 >From cat-dist@mta.ca Mon Nov 05 10:03:57 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 05 Nov 2001 10:03:57 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 160kAR-0006JT-00 for categories-list@mta.ca; Mon, 05 Nov 2001 09:51:59 -0400 Message-ID: <20011104231930.83794.qmail@web12206.mail.yahoo.com> Date: Sun, 4 Nov 2001 15:19:30 -0800 (PST) From: Galchin Vasili Subject: categories: Subobject classifier and non-classical logic (intuistionistic) To: categories@mta.ca Cc: bhalchin@hotmail.com MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 4 Hello Cat Community, I have been reading Goldblatt's book on topoi and also a paper by Peter Johnstone on subobject classifiers. Please "school" me .... In both places it says that in general a subobject classifier's "elements" are used as logic "values'. E.g. in the topos Set, I can see that the s.c. (subobject classifier) {0, 1} is a set of logic values that defines a Boolean algebra. In the topos of Graph we also can come up with a set of logical values. These examples of s.c. all clearly are sets or structured sets .. hence have elements. I don't see how in a totally general case of a topos we can say that "elements" of it's s.c. define a set of logic values .... after all the guiding principle of category theory is that objects are opaque. Thanks, Bill Halchin From rrosebru@mta.ca Mon Nov 5 11:47:42 2001 -0400 >From cat-dist@mta.ca Mon Nov 05 11:47:42 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 05 Nov 2001 11:47:42 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 160luG-0006Ou-00 for categories-list@mta.ca; Mon, 05 Nov 2001 11:43:25 -0400 Date: Mon, 5 Nov 2001 07:06:48 -0800 From: Toby Bartels To: categories@mta.ca Subject: categories: Re: Subobject classifier and non-classical logic (intuistionistic) Message-ID: <20011105070647.C14677@math-cl-n03.ucr.edu> References: <20011104231930.83794.qmail@web12206.mail.yahoo.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.2.5i In-Reply-To: <20011104231930.83794.qmail@web12206.mail.yahoo.com>; from vngalchin@yahoo.com on Sun, Nov 04, 2001 at 03:19:30PM -0800 Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 5 Galchin Vasili wrote: >I have been reading Goldblatt's book on topoi and >also a paper by Peter Johnstone on subobject >classifiers. Please "school" me .... In both places it >says that in general a subobject classifier's >"elements" are used as logic "values". [...] >[...] I don't see >how in a totally general case of a topos we can say >that "elements" of it's s.c. define a set of logic >values .... after all the guiding principle of >category theory is that objects are opaque. In a topos (or any closed monoidal category C with unit object 1), an "element" of an object X is a morphism from 1 to X. Think of the functor Hom(1,.): C -> _Set_ as the "forgetful functor" that defines the category C as sets with extra structure. Of course, it will only be *really* valid to think of C as sets with extra structure if this functor is faithful. A topos C is called "well pointed" when this holds. -- Toby Bartels toby@math.ucr.edu From rrosebru@mta.ca Tue Nov 6 06:26:52 2001 -0400 >From cat-dist@mta.ca Tue Nov 06 06:26:52 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 06 Nov 2001 06:26:52 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 1613RK-0003jX-00 for categories-list@mta.ca; Tue, 06 Nov 2001 06:26:42 -0400 To: categories@mta.ca Subject: categories: Weighted limits From: Mark Hovey Date: 05 Nov 2001 13:23:24 -0500 Message-ID: Lines: 16 User-Agent: Gnus/5.070095 (Pterodactyl Gnus v0.95) Emacs/20.3 MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: X-Keywords: X-UID: 6 What are the standard references for weighted limits and colimits in enriched categories? I know about Borceux, volume 2, chapter 6, but that does not go far enough. More precisely, I want to know how functorial the weighted colimit is in the weight. Given a V-natural transformation F --> F', presumably I get some kind of map from colim_F G to colim_F' G (or the other way around). I would like a reference for this fact and related functoriality facts. Presumably the weighted colimit is a bifunctor in the weight and the functor one is taking the colimit of, and presumably this bifunctor has various good properties. Has anybody ever written these down? Thanks in advance for any help you can give me. Mark Hovey From rrosebru@mta.ca Tue Nov 6 06:23:31 2001 -0400 >From cat-dist@mta.ca Tue Nov 06 06:23:31 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 06 Nov 2001 06:23:31 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 1613Lt-0004Lh-00 for categories-list@mta.ca; Tue, 06 Nov 2001 06:21:05 -0400 Message-ID: <3BE6B67E.B944CBE8@bangor.ac.uk> Date: Mon, 05 Nov 2001 15:55:42 +0000 From: Ronnie Brown X-Mailer: Mozilla 4.77 [en] (Win98; U) X-Accept-Language: en MIME-Version: 1.0 To: categories@mta.ca Subject: categories: embeddability Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 8 I am embarrassed that I did not reply to kind and helpful messages to a query I put on July 10 about embedability of a cartesian closed category in a topos. The problem was that I got too many distractions (health, holidays, family, other jobs) but really I did not explain the origin of the question. So here goes. I am writing an invited article on k-spaces for an Encyclopaedia of general topology to be published by Elsevier, and of course k-spaces and also sequential spaces form a cartesian closed category. I want to make a nod in the direction of topos methods in order to be able to indicate how to deal with spaces of partial maps, and fibred exponential laws. There is quite a bit of literature on these in algebraic topology but so far they do not go the whole hog and use toposes. Again in analysis, there is the book by Moerdijk and Reyes, and also the later book by Kriegl and Michor `A convenient setting for global analysis' which has the former book in its bibliography but does not have the word topos in the index. There is a lot of general topology work on hyperspaces, and also from a different approach on spaces of partial maps, but one would like to know if this can all be subsumed under topos work, or at least suggest it as a topic for investigation. I realise as Peter Jonstone wrote that he has embedded the category of sequential spaces in a topos, and I think Kock and Reyes have some work on on embedding convenient vector spaces in a topos, but does this work for k-spaces, or for the Kriegl and Michor situation? All this is not really my area but I would like to give helpful remarks in this direction. For those interested I attach a dvi file of the current draft and comments would be welcomed. Many thanks in anticipation and apologies again for not getting back on this earlier. Best wishes Ronnie From rrosebru@mta.ca Tue Nov 6 06:31:24 2001 -0400 >From cat-dist@mta.ca Tue Nov 06 06:31:24 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 06 Nov 2001 06:31:24 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 1613Vi-00048y-00 for categories-list@mta.ca; Tue, 06 Nov 2001 06:31:14 -0400 Message-Id: Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Date: Tue, 6 Nov 2001 08:43:17 +0100 To: categories@mta.ca From: grandis@dima.unige.it (Marco Grandis) Subject: categories: preprint: 'Directed homotopy theory, I' Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: X-Keywords: X-UID: 9 The following preprint is available on line: Marco Grandis, 'Directed homotopy theory, I. The fundamental category' Abstract. Directed Algebraic Topology is beginning to emerge from various applications. The basic structure we shall use for such a theory, a 'd-space', is a topological space equipped with a family of 'directed paths', closed under some operations. This allows for 'directed homotopies', generally non reversible, represented by a cylinder and cocylinder functors. The existence of 'pastings' (colimits) yields a geometric realisation of cubical sets as d-spaces, together with homotopy constructs which will be developed in a sequel. Here, the 'fundamental category' of a d-space is introduced and a 'Seifert - van Kampen' theorem proved; its homotopy invariance rests on 'directed homotopy' of categories. In the process, new shapes appear, for d-spaces but also for small categories, their elementary algebraic model. Applications of such tools are briefly considered or suggested, for objects which model a directed image, or a portion of space-time, or a concurrent process. Dip. Mat. Univ. Genova, Preprint 443 (October 2001). 26 pages. Available at: http://www.dima.unige.it/~grandis/ ftp://www.dima.unige.it/Home/grandis/public/Dht1.ps http://arXiv.org/abs/math.AT/0111048 _____________ Marco Grandis Dipartimento di Matematica Universita' di Genova via Dodecaneso 35 16146 GENOVA, Italy e-mail: grandis@dima.unige.it tel: +39.010.353 6805 fax: +39.010.353 6752 http://www.dima.unige.it/~grandis/ ftp://www.dima.unige.it/Home/grandis/public/ From rrosebru@mta.ca Wed Nov 7 09:45:51 2001 -0400 >From cat-dist@mta.ca Wed Nov 07 09:45:51 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 07 Nov 2001 09:45:51 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 161T01-0003ES-00 for categories-list@mta.ca; Wed, 07 Nov 2001 09:44:13 -0400 Message-ID: <58B6DA1B98AA9149B13B029976A48BCC068F1324@xch-nw-31.nw.nos.boeing.com> From: "Williamson, Keith" To: "'categories@mta.ca'" Subject: categories: query Date: Tue, 6 Nov 2001 09:59:07 -0800 MIME-Version: 1.0 X-Mailer: Internet Mail Service (5.5.2650.21) Content-Type: text/plain; charset="iso-8859-1" Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: X-Keywords: X-UID: 10 Greetings. I am new to the categories list. I would like to receive any pointers to work that has been done applying category theory to computer security. I realize this is perhaps a broad query, but any information would be great! Thanks! Keith Williamson Mathematics & Computing Technology Boeing Phantom Works, Seattle WA From rrosebru@mta.ca Wed Nov 7 09:45:54 2001 -0400 >From cat-dist@mta.ca Wed Nov 07 09:45:54 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 07 Nov 2001 09:45:54 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 161Stu-0002TD-00 for categories-list@mta.ca; Wed, 07 Nov 2001 09:37:54 -0400 Message-ID: <3BE7FA95.4D9DFC0D@bangor.ac.uk> Date: Tue, 06 Nov 2001 14:58:29 +0000 From: Ronnie Brown X-Mailer: Mozilla 4.77 [en] (Win98; U) X-Accept-Language: en MIME-Version: 1.0 To: "categories@mta.ca" Subject: categories: booby on embedability Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 11 I forgot that of course the dvi file on my previous message would not go out to the list! So here is a url of a draft on k-spaces - comments welcome. http://www.bangor.ac.uk/~mas010/k-spaces2.pdf (7 pages) While I'm writing, I have some other material in pdf format as follows. http://www.bangor.ac.uk/~mas010/multiple-apj.pdf This is a revised version of the paper with Al-Agl and Steiner on the equivalence of the cubical and globular approach to strict multiple categories. It is provisionally accepted for Advances in Math. (44 pages) http://www.bangor.ac.uk/~mas010/probamtx.pdf `Some problems in non-abelian homotopical and homological algebra'. This is LateX version of a paper from a 1988 homotopy theory conference published in 1999. It contains 35 problems or problem areas and a few comments now on what has been solved since then. Is it all old hat? (26 pages) http://www.bangor.ac.uk/~mas010/korea3.pdf Free crossed resolutions for graph products and amalgamated sums of groups (Brown, Bullejos, Porter) (18 pages) This uses free crossed resolutions to calculate higher homotopical syzygies, using also homotopy colimits and generalised Van Kampen Theorems. Ronnie -- Prof R. Brown, School of Informatics, Mathematics Division, University of Wales, Bangor Dean St., Bangor, Gwynedd LL57 1UT, United Kingdom Tel. direct:+44 1248 382474|office: 382681 fax: +44 1248 361429 World Wide Web: home page: http://www.bangor.ac.uk/~mas010/ (Links to survey articles: Higher dimensional group theory Groupoids and crossed objects in algebraic topology) Raising Public Awareness of Mathematics CDRom Version 1.1 http://www.bangor.ac.uk/~mas010/CDadvert.html Symbolic Sculpture and Mathematics: http://www.cpm.informatics.bangor.ac.uk/sculmath/ Centre for the Popularisation of Mathematics http://www.cpm.informatics.bangor.ac.uk/ From rrosebru@mta.ca Wed Nov 7 09:46:23 2001 -0400 >From cat-dist@mta.ca Wed Nov 07 09:46:23 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 07 Nov 2001 09:46:23 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 161T0w-00046I-00 for categories-list@mta.ca; Wed, 07 Nov 2001 09:45:10 -0400 Date: Tue, 6 Nov 2001 14:45:29 -0500 (Eastern Standard Time) From: Walter Tholen To: categories@mta.ca cc: tholen@mathstat.yorku.ca Subject: categories: Open maps of locales Message-ID: X-X-Sender: tholen@pascal.math.yorku.ca MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: X-Keywords: X-UID: 12 I need help with respect to the following question. With the help of M.M. Clementino and J. Picado, I understood that an open morphism f: X --> Y in the category of locales (dual to the category of frames) has the property that taking inverse images (pullbacks) along f commutes with taking closures of sublocales: f*[cl(N)] = cl(f*[N]) for all sublocales N of Y. Conversely, does this property force f to be open (as it does for topological spaces)? If not, is the answer positive when f is the embedding of a sublocale? I appreciate any suggestions/answers that you may have. Thanks, Walter Tholen. From rrosebru@mta.ca Wed Nov 7 09:47:30 2001 -0400 >From cat-dist@mta.ca Wed Nov 07 09:47:30 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 07 Nov 2001 09:47:30 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 161T1k-0002XX-00 for categories-list@mta.ca; Wed, 07 Nov 2001 09:46:00 -0400 Date: Tue, 6 Nov 2001 15:05:27 -0500 (Eastern Standard Time) From: Walter Tholen To: categories@mta.ca cc: tholen@mathstat.yorku.ca Subject: categories: job opening Message-ID: X-X-Sender: tholen@pascal.math.yorku.ca MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: X-Keywords: X-UID: 13 A tenure-track position in "Algebra, Logic, or related areas" at the assistant professor level is advertised at York University in Toronto. For details see http://www.math.yorku.ca/Hiring/t_track_math.htm . While spreading this info here I hasten to add that I have no indication whether the department would welcome applications from category theorists. Being on sabbatical I would in any event have no influence whatsoever on the selection procedure. Walter Tholen. From rrosebru@mta.ca Wed Nov 7 09:48:18 2001 -0400 >From cat-dist@mta.ca Wed Nov 07 09:48:18 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 07 Nov 2001 09:48:18 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 161T35-0003nk-00 for categories-list@mta.ca; Wed, 07 Nov 2001 09:47:23 -0400 Message-ID: <3BE87718.41C6@maths.usyd.edu.au> Date: Wed, 07 Nov 2001 10:49:44 +1100 From: Max Kelly Organization: School of Mathematics and Statistics, University of Sydney X-Mailer: Mozilla 3.01Gold (X11; I; OSF1 V5.1 alpha) MIME-Version: 1.0 To: categories@mta.ca Subject: categories: Re: Weighted limits References: Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: X-Keywords: X-UID: 14 In his letter below, Mark Harvey asks about the functoriality of the weighted colimit F*G where we are dealing with V-categories and say F: K --> V and G: K --> A. The matter is dealt with at length in my book ["Basic Concepts of Enriched Category Theory", London Math Soc. Lecture Notes Series 64, Cambridge University Press, 1982.]. (The book uses the older terminology "indexed limit" for "weighted limit" and so on. See Chapter 3, and the work in Chapter 4 on final and initial weights. Max Kelly. _______________ Subject: categories: Weighted limits Date: 05 Nov 2001 13:23:24 -0500 From: Mark Hovey To: categories@mta.ca Mark Hovey wrote: > > What are the standard references for weighted limits and colimits in > enriched categories? I know about Borceux, volume 2, chapter 6, but > that does not go far enough. > > More precisely, I want to know how functorial the weighted colimit is in > the weight. Given a V-natural transformation F --> F', presumably I get > some kind of map from colim_F G to colim_F' G (or the other way > around). I would like a reference for this fact and related functoriality > facts. > > Presumably the weighted colimit is a bifunctor in the weight and the > functor one is taking the colimit of, and presumably this bifunctor has > various good properties. Has anybody ever written these down? > > Thanks in advance for any help you can give me. > Mark Hovey From rrosebru@mta.ca Wed Nov 7 09:49:46 2001 -0400 >From cat-dist@mta.ca Wed Nov 07 09:49:46 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 07 Nov 2001 09:49:46 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 161T4z-0003Jg-00 for categories-list@mta.ca; Wed, 07 Nov 2001 09:49:21 -0400 X-Originating-IP: [158.59.40.195] From: "Keith Harbaugh" To: hovey@picard.math.wesleyan.edu Subject: categories: Re: Weighted limits Date: Wed, 07 Nov 2001 02:48:09 +0000 Mime-Version: 1.0 Content-Type: text/plain; format=flowed Message-ID: X-OriginalArrivalTime: 07 Nov 2001 02:48:10.0221 (UTC) FILETIME=[A2E9C9D0:01C16736] Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: X-Keywords: X-UID: 15 Perhaps a useful reference on weighted (there called indexed) limits is Chapter 3 of Basic Concepts of Enriched Category Theory by Max Kelly, containing your desired result and much more. BTW, Peter Johnstone wrote a rather nice (and amusing) review of BCECT in the Bulletin of the London Mathematical Society, supplementing the helpful, accurate, but not very farseeing (in terms of potential applications for ECs) BAMS review by Gray and Linton's short antidote to Gray in MR. Regards, Keith Harbaugh _________________________________________________________________ Get your FREE download of MSN Explorer at http://explorer.msn.com/intl.asp From rrosebru@mta.ca Fri Nov 9 13:33:39 2001 -0400 >From cat-dist@mta.ca Fri Nov 09 13:33:39 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 09 Nov 2001 13:33:39 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 162FQT-0002MB-00 for categories-list@mta.ca; Fri, 09 Nov 2001 13:26:45 -0400 Message-ID: <3BE994A1.24291F16@kestrel.edu> Date: Wed, 07 Nov 2001 12:08:01 -0800 From: Dusko Pavlovic X-Mailer: Mozilla 4.77 [en] (X11; U; Linux 2.4.9-6 i686) X-Accept-Language: en MIME-Version: 1.0 To: "'categories@mta.ca'" Subject: categories: Re: query References: <58B6DA1B98AA9149B13B029976A48BCC068F1324@xch-nw-31.nw.nos.boeing.com> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: X-Keywords: X-UID: 16 "Williamson, Keith" wrote: > I would like to receive any pointers to work that has been done > applying category theory to computer security. there is a paper by nancy durgin, john mitchell and me, describing a process calculus and logic for reasoning about security protocols. it should be on my web page http://www.kestrel.edu/home/people/pavlovic/ . the process calculus induces an action category, which is very briefly described in the paper. the point is that the categorical structure captures the static (design-time) composition of protocols. in a way, the category thus displays some sort of denotations of protocols. the analysis then proceeds by attaching axiomatic semantics to the morphisms. -- dusko From rrosebru@mta.ca Fri Nov 9 13:33:42 2001 -0400 >From cat-dist@mta.ca Fri Nov 09 13:33:42 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 09 Nov 2001 13:33:42 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 162FUw-0000D9-00 for categories-list@mta.ca; Fri, 09 Nov 2001 13:31:22 -0400 Message-ID: <20011108014126.86104.qmail@web12203.mail.yahoo.com> Date: Wed, 7 Nov 2001 17:41:26 -0800 (PST) From: Galchin Vasili Subject: categories: Topoi, Heyting algebra and Lawvevre's CAT book To: categories@mta.ca MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: X-Keywords: X-UID: 17 Hello, This is a followup question to my other question about topoi and intuistionistic logic. On page 350, Lawvere is talking about logical operations (in a Heyting algebra I think??). In particular I having trouble understanding the narrative on the implication operation "=>" in the sense 1) I don't understand what . (e.g. is alpha meant to be an element: alpha:1->omega?) 2) also what alpha "subset" beta is! Please help me. Thanks and regards, Bill Halchin From rrosebru@mta.ca Fri Nov 9 13:33:45 2001 -0400 >From cat-dist@mta.ca Fri Nov 09 13:33:45 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 09 Nov 2001 13:33:45 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 162FNg-0002Qq-00 for categories-list@mta.ca; Fri, 09 Nov 2001 13:23:52 -0400 Date: Wed, 7 Nov 2001 17:37:43 +0000 (GMT) From: "Dr. P.T. Johnstone" To: categories@mta.ca Subject: categories: Re: Open maps of locales In-Reply-To: Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Scanner: exiscan *161We2-0004mF-00*kp8YtdKRmZM* http://duncanthrax.net/exiscan/ Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: X-Keywords: X-UID: 18 On Tue, 6 Nov 2001, Walter Tholen wrote: > I need help with respect to the following question. > With the help of M.M. Clementino and J. Picado, I understood that an open > morphism f: X --> Y in the category of locales (dual to the category of > frames) has the property that taking inverse images (pullbacks) along > f commutes with taking closures of sublocales: f*[cl(N)] = cl(f*[N]) for > all sublocales N of Y. > Conversely, does this property force f to be open (as it does for > topological spaces)? If not, is the answer positive when f is the > embedding of a sublocale? > > I appreciate any suggestions/answers that you may have. Thanks, > > Walter Tholen. > The answer is no: for any locale Y, the embedding of the smallest dense sublocale of Y has this property. Of course, if X is the smallest dense sublocale of Y, then any sublocale of X is closed (since the frame corresponding to X is Boolean); so this is tantamount to saying that, given any sublocale N of Y, N and its closure have the same intersection with X. This in turn is equivalent to the assertion that if we have elements U and V of a frame satisfying V \leq U and ((U => 0) => 0) = U, then we also have ((U => V) => V) = U. The verification of this is left as an exercise for the reader. Peter Johnstone From rrosebru@mta.ca Fri Nov 9 13:34:24 2001 -0400 >From cat-dist@mta.ca Fri Nov 09 13:34:24 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 09 Nov 2001 13:34:24 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 162FWs-0001Gd-00 for categories-list@mta.ca; Fri, 09 Nov 2001 13:33:22 -0400 Message-Id: To: categories-list@mta.ca Date: Thu, 8 Nov 2001 01:45:26 -0800 (PST) From: Posina Venkata Rayudu Subject: categories: papers on category theory To: categories@mta.ca MIME-Version: 1.0 Content-Type: text/plain; charset=3Dus-ascii Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 81 Hi, I would very much appreciate information regarding any papers on category theory (comprehensive reviews, overviews=85) published in a peer-reviewed journal during the month of November 2001. I would like to highlight category theory as a tool for cognitive neuroscience for possible publication in Nature Reviews Neuroscience (NRN). NRN has announced a Highlights competition. One of the rules is: Highlights should be written on papers published in any peer-reviewed scientific journal between 1 November and 1 December 2001. Selected Highlights will be published in January 2002 issue and they give one-year free subscription. Thanks so much for your help. Thanking you, Sincerely, Posina venkata rayudu =3D=3D=3D=3D=3D Posina Venkata Rayudu C/o: Sri. S. S. Chalam Advocate & Notary Public H.No: 39-4-10, Innespeta Rajahmundry =96 533102 Andhra Pradesh, India Phone: 91 (0883) 444232 __________________________________________________ Do You Yahoo!? Find a job, post your resume. http://careers.yahoo.com From rrosebru@mta.ca Fri Nov 9 13:55:34 2001 -0400 >From cat-dist@mta.ca Fri Nov 09 13:55:34 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 09 Nov 2001 13:55:34 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 162FrR-0002g8-00 for categories-list@mta.ca; Fri, 09 Nov 2001 13:54:37 -0400 X-Received: from zent.mta.ca ([138.73.101.4]) by mailserv.mta.ca with smtp (Exim 3.33 #2) id 161EWf-0001DT-00 for cat-dist@mta.ca; Tue, 06 Nov 2001 18:16:57 -0400 X-Received: FROM siv.maths.usyd.edu.au BY zent.mta.ca ; Tue Nov 06 18:16:35 2001 -0400 X-Received: from milan.maths.usyd.edu.au (stevel(.pmstaff;2406.2002)@milan.maths.usyd.edu.au) [129.78.69.163] by siv.maths.usyd.edu.au via smtpdoor V13.1 id 22689 for cat-dist@mta.ca; Wed, 7 Nov 2001 09:16:18 +1100 From: Steve Lack MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <15336.24881.626303.900796@milan.maths.usyd.edu.au> Date: Wed, 7 Nov 2001 09:16:17 +1100 To: cat-dist@mta.ca Subject: categories: weighted limits X-Mailer: VM 6.90 under 21.1 (patch 7) "Biscayne" XEmacs Lucid Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: X-Keywords: X-UID: 82 Mark Hovey writes: > What are the standard references for weighted limits and colimits in > enriched categories? I know about Borceux, volume 2, chapter 6, but > that does not go far enough. Have a look at Chapter 3 of Max Kelly's book ``The basic concepts of enriched category theory'', LMS lecture note series 64. > > More precisely, I want to know how functorial the weighted colimit is in > the weight. Given a V-natural transformation F --> F', presumably I get > some kind of map from colim_F G to colim_F' G (or the other way > around). I would like a reference for this fact and related functoriality > facts. Yes, it is functorial in F, in the way that you have written above. > > Presumably the weighted colimit is a bifunctor in the weight and the > functor one is taking the colimit of, and presumably this bifunctor has > various good properties. Has anybody ever written these down? Once again, yes. There's quite a lot in the reference above. Kelly writes F*G for what you have called colim_F G, and {F,G} for what you would presumably call lim_F G. He develops results based on the intuition that * is a kind of tensor product, and {-,-} a kind of internal hom, and proves results like the associativity of * and {F*G,H}={F,{G,H}}. Of course this sounds a bit odd, because the F and the G live in different categories, but you can actually make sense of these things. There is even an isomorphism F*G=G*F in the case of colimits in V itself. There's another approach, which probably goes back to Street and Walters, Yoneda structures on 2-categories, J. Algebra 50:350-379, 1978 and has been developed by Street and many others since. In this approach you define a bicategory, often called V-Prof or V-Mod, in which an object is a V-category, and a morphism from A to B, often written A-|->B is a V-functor from A to [B^op,V], and a 2-cell is a natural transformation. (This direction of the 1-cells and 2-cells in this definition is not universally adopted.) Then composition is given by colimit, in the sense that if f:A-|->B and g:B-|->C, then gf:A-|->C is defined by gf(a,c)=g(-,c)*f(a,-). Then associativity (up to isomorphism) of composition in this bicategory is the associaitivity of * referred to above. In fact this bicategory is closed, in the sense that composition has an adjoint, constructed using {-,-}. Steve Lack. From rrosebru@mta.ca Mon Nov 12 09:49:47 2001 -0400 >From cat-dist@mta.ca Mon Nov 12 09:49:47 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 12 Nov 2001 09:49:47 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 163HIM-0002Ui-00 for categories-list@mta.ca; Mon, 12 Nov 2001 09:38:38 -0400 Mime-Version: 1.0 X-Sender: paonico@primus.ca@pop.primus.ca Message-Id: Date: Wed, 7 Nov 2001 01:46:51 -0500 To: categories@mta.ca, types@cis.upenn.edu From: Nicola Santoro Subject: categories: CFP: TCS 2002 Content-Type: text/plain; charset="iso-8859-1" ; format="flowed" Content-Transfer-Encoding: quoted-printable Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: X-Keywords: X-UID: 83 ----------------------------------------------------------------- CALL FOR PAPERS ----------------------------------------------------------------- 2nd IFIP International Conference on THEORETICAL COMPUTER SCIENCE (TCS 2002) Montreal, August 25-30, 2002 ----------------------------------------------------------------- co-sponsored by EATCS and ACM SIGACT ----------------------------------------------------------------- The program of of the conference will be composed of two tracks: Track 1 - Algorithms, Complexity and Models of Computation Track 2 - Logic, Semantics, Specification and Verification. ----------------------------------------------------------------- Important Dates: December 3, 2001: Submissions =46ebruary 20, 2002: Notifications ----------------------------------------------------------------- Conference Chair ---------------- Nicola Santoro, Carleton University (santoro@scs.carleton.ca) Conference Co-Chairs ---------------------- Track (1) Ricardo Baeza-Yates, University of Chile (rbaeza@dcc.uchile.cl) Track (2) Ugo Montanari, University of Pisa, Italy (ugo@di.unipi.it) Program Committee ----------------- Track (1) Eric Allender (allender@aramis.rutgers.edu) Jos=C8 Balcazar (balqui@lsi.upc.es) Andrej Brodnik (Andrej.Brodnik@IMFM.Uni-Lj.SI) Volker Diekert (diekert@informatik.uni-stuttgart.de) David Fernandez-Baca (fernande@cs.iastate.edu) Kazuo Iwama (iwama@i.kyoto-u.ac.jp) John D. Kececioglu (kece@CS.Arizona.EDU) Jan van Leeuwen (jan@cs.uu.nl) Xuemin Lin (lxue@cse.unsw.EDU.AU) Alberto Marchetti Spaccamela (alberto@dis.uniroma1.it) David Peleg (peleg@wisdom.weizmann.ac.il) Prabhakar Raghavan (pragh@verity.com) Venkatesh Raman (vraman@imsc.ernet.in) Siang Song (song@ime.usp.br) Paul Spirakis (spirakis@cti.gr) Luca Trevisan (luca@eecs.berkeley.edu) Brigitte Vall=CBe (Brigitte.Vallee@info.unicaen.fr) Alfredo Viola (viola@fing.edu.uy) Manfred Warmuth (manfred@cse.ucsc.edu) Sue Whitesides (sue@cs.mcgill.ca) Peter Widmayer (widmayer@inf.ethz.ch) Jiri Wiederman (wieder@uivt.cas.cz) Track (2) Gabriel Baum (gbaum@info.unlp.edu.ar) Luca Cardelli (luca@microsoft.com) Frank DeBoer (frankb@cs.ruu.nl) Ursula Goltz (u.goltz@tu-bs.de) Roberto Gorrieri (gorrieri@cs.unibo.it) Jieh Hsiang (hsiang@csie.ntu.edu.tw) Takayasu Ito (ito@ito.ecei.tohoku.ac.jp) Alexander Letichevsky (letichev@carrier.kiev.ua) Jean-Jacques Levy (Jean-Jacques.Levy@inria.fr) Huimin Lin (lhm@ox.ios.ac.cn) Kim Marriott (marriott@csse.monash.edu.au) Narciso Marti-Oliet (narciso@eucmos.sim.ucm.es) John Mitchell (mitchell@cs.stanford.edu) Luis Monteiro (lm@fct.unl.pt) Peter Mosses (pdmosses@daimi.aau.dk) Prakash Panangaden (prakash@cs.mcgill.ca) Benjamin Pierce (bcpierce@cis.upenn.edu) Amir Pnueli (amir@wisdom.weizmann.ac.il) Leila Ribeiro (leila@inf.ufrgs.br) Gheorghe Stefanescu (ghstef@funinf.math.unibuc.ro) Andrzej Tarlecki (tarlecki@mimuw.edu.pl) P.S. Thiagarajan (pst@smi.ernet.in) Organizing Committee -------------------- Michel Barbeau (barbeau@scs.carleton.ca) -- Chair Amiya Nayak (nayak@nortelnetworks.com) Giuseppe Prencipe (prencipe@di.unipi.it) Web Site -------- http://www.scs.carleton.ca/~santoro/TCS2002/indexTCS2002.html ----------------------------------------------------------------- SPECIAL FOCUS Foundations of IT in the Era of Network and Mobile Computing ------------------------------------------------------- ------------------------------------------------------------------- Original and significant contributions on the special focus and on foundatio= nal questions are sought from all areas of theoretical computer science. ------------------------------------------------------------------- SUBMISSIONS A submission should consist of: 1) a cover page, including the track name, the title of the paper, names and affiliations of authors, an abstract up to 300 words, and the contact author's name, address, phone number, fax number, and email address; 2) the paper, which should provide a summary of the main results and their details to allow the program committee to assess their merits and significance, including references and comparisons. Submissions are limited to 14 A4-size pages, in 11 point or larger font. Proofs omitted due to space constraints must be put into a clearly marked appendix. The result of the paper must be unpublished and not submitted for publicatio= n elsewhere, including journals and the proceedings of other symposia or workshops. One author of each accepted paper should present it at the conference. The Proceedings will be published by Kluwer, the official publisher of IFIP. Authors are strongly encouraged to submit electronically. A detailed description of the electronic submission process will be found at the conference web site. Unprintable Postscript and Postscript submissions not formatted for 8.5x11 inch paper will be rejected without consideration of their merits= =2E Authors who do not wish to submit electronically are invited to submit hard copies by the following procedure: (a) The authors must first send an e-mail to the relevant Vice-chair to state the intention of submitting hard copies by November 25, 2001; (b) The authors must send 10 copies (printed double-sided if possible) of the submission, INDICATING the conference title= , to the address below to be received by December 3, 2001. (c) Authors from locations where access to reproduction facilities is severely limited may a= sk for permission of submitting a single copy by first sending an e-mail to the relevant Vice-chair at or before November 25, 2001. Mailing Address: WCC2002 550 Sherbrooke Street West Suite 355, West Tower Montreal(Quebec) H3A 1B9 ------------------------------------------------------------------- INVITED SPEAKERS (preliminary) Andy Gordon ( http://research.microsoft.com/~adg/ ) Jozef Gruska gruska@informatics.muni.cz Carl Gunter ( http://www.cis.upenn.edu/~gunter/wip.html ) Jon Kleinberg ( http://www.cs.cornell.edu/home/kleinber/kleinber.html ) ------------------------------------------------------------------- AREAS Track (1): Algorithms, Complexity and Models of Computation Analysis and design of algorithms Automata and formal languages Cellular automata and systems Combinatorial, graph and optimization algorithms Computational and mathematical finance Computational learning theory Continuous algorithms and complexity Computational complexity Computational geometry Cryptography Distributed computing Descriptional complexity Evolutionary and genetic computing Experimental algorithms Mobile computing Molecular computing and algorithmic aspects of bioinformatics Network computing Neural computing Parallel and distributed algorithms Probabilistic and randomized algorithms Quantum computing Structural information and communication complexity Track (2): Logic, Semantics, Specification and Verification Bridging semantics and complexity Concurrency theory Constructive and non-standard logics in computer science =46oundations of global computing =46oundations of mobile computing =46oundations of security =46oundations of system specification =46oundations of wide area programming Logic and semantics for programs and languages Logic, specification and verification of hybrid and real-time systems Proofs and specifications in computer science Term rewriting systems Theoretical aspects of software concepts Theoretical aspects of specification, and verification of hardware and softw= are Theoretical foundations of databases Theoretical foundations of open systems Theory of Internet languages and systems Theory of parallel and distributed systems Type and category theory in computer science ----------------------------------------------------------------- SPONSORS --------- TCS2002 conference is sponsored by -- IFIP TC1 (Technical Committee on Foundations of Computer Science) in cooperation with -- EATCS (European Association for Theoretical Computer Science) -- ACM SIGACT (Special Interest Group on Algorithm and Computation Theory) IFIP TC1 Steering Committee --------------------------- Giorgio Ausiello (U. of Roma "La Sapienza", Italy) - CHAIR - Wilfried Brauer (TU Munchen, Germany) Takayasu Ito (Tohoku University, Japan) Michael O. Rabin (Harvard University, USA) Joseph Traub (Columbia University, USA) ------------------------------------------------------------------- LOCATION --------- The conference will be held in Montreal, August 25-30, 2002, as part of the 17th IFIP World Computer Congress (http://www.wcc2002.org). Ten conferences will take place at the same time, in addition to workshops, tutorials, and joint sessions. ---------- LINKAGE SESSION : "Autonomous Agents-Control and Security" A join invited session co-organized by TCS 2002 and IIP 2002 Autonomous software agents provide a fascinating metaphor for complex software systems in a networked society. Leading researchers from three different IT communities, represented by TC1 (Foundations of Computer Science), TC9 (Relationship between Computers and Society) and TC12 (Artificial Intelligence), will give a comprehensive overview of foundations, societal aspects and AI contributions. From rrosebru@mta.ca Mon Nov 12 09:50:35 2001 -0400 >From cat-dist@mta.ca Mon Nov 12 09:50:35 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 12 Nov 2001 09:50:35 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 163HR4-0001Jq-00 for categories-list@mta.ca; Mon, 12 Nov 2001 09:47:38 -0400 Date: Thu, 8 Nov 2001 10:57:26 GMT Message-Id: <200111081057.fA8AvQY02272@toolo.dcs.ed.ac.uk> X-Authentication-Warning: toolo.dcs.ed.ac.uk: csl02 set sender to csl02+calls@dcs.ed.ac.uk using -f From: CSL02 To: CSL distribution list:; Subject: categories: CFP: Computer Science Logic 2002 (CSL'02) announcement Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: X-Keywords: X-UID: 84 [ We apologize for the inevitable multiple copies of this announcement. If you receive this call inappropriately, please contact csl02+calls@dcs.ed.ac.uk so that we can adjust our mailing list. ] Annual Conference of the European Association for Computer Science Logic CSL'02 22--25 September 2002, Edinburgh, UK Computer Science Logic (CSL) is the annual conference of the European Association for Computer Science Logic (EACSL). The conference is intended for computer scientists whose research activities involve logic, as well as for logicians working on issues significant for computer science. Suggested topics of interest include: automated deduction and interactive theorem proving, constructive mathematics and type theory, equational logic and term rewriting, linear logic, logical aspects of computational complexity, finite model theory, higher order logic, logic programming and constraints, lambda and combinatory calculi, logical foundations of programming paradigms, modal and temporal logics, model checking, functions of program development (specification, extraction, transformation...), categorical logic and topological semantics, domain theory, database theory. The following have agreed to deliver invited lectures: Susumu HAYASHI (Kobe) Frank NEVEN (Limburg) Damian NIWINSKI (Warsaw) The proceedings will be published in the Sprinter Lecture Notes in Computer Science. Submitted papers must describe work not previously published. They must not be submitted concurrently to a journal or to another conference. Papers authored or coauthored by members of the Programme Committee are not allowed. Papers should not exceed 15 pages in Springer LNCS style. Further details of the submission requirements will be available at the conference web page (see below). The provisional key dates for the conference are: Submission: 29 March 2002 Notification: 2 June 2002 Final copy due: 21 June 2002 Intending authors should check the conference Web page for any subsequent changes to these dates. Further information on all aspects of the conference will be found on the conference Web page: http://www.dcs.ed.ac.uk/csl02/ Programme Committee: Thorsten Altenkirch (U. Nottingham); Rajeev Alur (U. Pennsylvania); Michael Benedikt (Bell Labs); Julian Bradfield (U. Edinburgh (Chair)); Anuj Dawar (U. Cambridge); Yoram Hirshfeld (U. Tel Aviv); Ulrich Kohlenbach (U. Aarhus); Johann Makowsky (Technion Haifa); Dale Miller (Pennsylvania State U.); Luke Ong (U. Oxford); Frank Pfenning (Carnegie Mellon U.); Philippe Schnoebelen (ENS Cachan); Luc Segoufin (INRIA Rocquencourt); Alex Simpson (U. Edinburgh); Thomas Streicher (T.U. Darmstadt). From rrosebru@mta.ca Mon Nov 12 09:56:15 2001 -0400 >From cat-dist@mta.ca Mon Nov 12 09:56:15 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 12 Nov 2001 09:56:15 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 163HZ8-00076z-00 for categories-list@mta.ca; Mon, 12 Nov 2001 09:55:58 -0400 Message-Id: <4.3.1.2.20011108220246.00da1640@flinton.mail.wesleyan.edu> X-Sender: flinton@flinton.mail.wesleyan.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 4.3.1 Date: Thu, 08 Nov 2001 22:22:15 -0500 To: categories@mta.ca From: "Fred E.J. Linton" Subject: categories: Surprise travel plans Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed X-ECS-MailScanner: Found to be clean Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: X-Keywords: X-UID: 85 I've let myself be tempted by the recent astonishingly low prices for trans-Atlantic air tickets, and booked myself to Europe for the 10 days of the North American Thanksgiving break (16-26 Nov.). Now I wonder: any little "peripatetic"s going on that I might join? In a bit more detail, my arrival/departure airport will be Frankfurt, and I imagine passing (by rail) along the "circle" passing through Frankfurt, Cologne/Aachen, Belgium (Liege/Louvain/Brussels/Antwerp), France (Amiens/Paris/Lyon), Italy (Torino/Milano), Freiburg, Frankfurt -- maybe "counterclockwise" as listed above, or maybe clockwise instead. Nor any guarantee I'll actually pass through all of the places mentioned. But if you are in or near one of them and would like to have me try to visit, do let me know, please, before my departure 11/16/2001. For contact during the period 17-25.11.2001 while I'm in Europe, a GSM phone-call or SMS will reach me, if you use +1 203 606 3131, as will e-mail to <2036063131@voicestream.net> , which gets retransmitted to the phone as an SMS (so: best stay under 125 char.). Very short notice, I know -- until the tickets reached me, yesterday, I wasn't really sure I'd be doing this, after all. Hope to see some of you! From rrosebru@mta.ca Mon Nov 12 10:13:51 2001 -0400 >From cat-dist@mta.ca Mon Nov 12 10:13:51 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 12 Nov 2001 10:13:51 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 163Hpy-00048n-00 for categories-list@mta.ca; Mon, 12 Nov 2001 10:13:22 -0400 Date: Fri, 9 Nov 2001 20:16:38 -0800 (PST) From: Bill Rowan Message-Id: <200111100416.fAA4GcI25705@transbay.net> To: categories@mta.ca Subject: categories: Nonsymmetric closed categories Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: X-Keywords: X-UID: 86 I have been finding some nonsymmetric closed category structures on some important categories. By this, I mean a monoidal category, not necessarily symmetric, such that each functor -\square b has a right adjoint. For example, I found a nice such structure on the category of locally closed topological spaces, that is, spaces such that the filter of neighborhoods of each point has a base of closed neighborhoods. I'm probably going to write this and some other examples up and put it online somewhere. Does anyone know of previous work which would be relevant? In Mac Lanes CWM he talks about compactly generated spaces, which I have looked at carefully, but this is a somewhat different approach to moving beyond the locally compact Hausdorff spaces, which of course form a cartesian closed category. In my example, of course, the \square operation is not the product of topological spaces, although it has a continuous map onto it. Bill Rowan From rrosebru@mta.ca Mon Nov 12 10:17:14 2001 -0400 >From cat-dist@mta.ca Mon Nov 12 10:17:14 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 12 Nov 2001 10:17:14 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 163Hsz-00009c-00 for categories-list@mta.ca; Mon, 12 Nov 2001 10:16:29 -0400 Message-ID: <3BEF425D.41C6@maths.usyd.edu.au> Date: Mon, 12 Nov 2001 14:30:38 +1100 From: Max Kelly Organization: School of Mathematics and Statistics, University of Sydney X-Mailer: Mozilla 3.01Gold (X11; I; OSF1 V5.1 alpha) MIME-Version: 1.0 To: categories@mta.ca Subject: categories: category theory applied to computer security Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: X-Keywords: X-UID: 87 Keith Williamson asked about the above. Stefano Kasangian and I have written something on this: S. Kasangian and Max Kelly, A bicategorical approach to information flow and security, in Categorical Studies in Italy, = Rendiconti del Circolo Matematico di Palermo, 64 (2000), 99 -- 122. Max Kelly (= G.M. Kelly) From rrosebru@mta.ca Mon Nov 12 10:17:45 2001 -0400 >From cat-dist@mta.ca Mon Nov 12 10:17:45 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 12 Nov 2001 10:17:45 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 163Htz-0001cs-00 for categories-list@mta.ca; Mon, 12 Nov 2001 10:17:31 -0400 From: baez@math.ucr.edu Message-Id: <200111120355.fAC3tZP16139@math-cl-n04.ucr.edu> Subject: categories: nice category of "smooth spaces"? To: categories@mta.ca (categories) Date: Sun, 11 Nov 2001 19:55:35 -0800 (PST) X-Mailer: ELM [version 2.5 PL2] MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: X-Keywords: X-UID: 88 Dear Categorists - I'm getting really annoyed at how the category Diff of smooth manifolds and smooth maps isn't complete and cocomplete. Is there some category of "smooth spaces" that repairs these defects? Ideally I would like a category S with a bunch of properties like: 1) Diff is a full subcategory of S 2) There is a faithful functor F: S -> CGHaus, so we can think of smooth spaces as nice topological spaces (compactly generated Hausdorff spaces) equipped with some extra structure. 3) S has small limits and colimits 4) F preserves limits and colimits 5) The obvious functor from the category of simplices to CGHaus factors through F, with the resulting smooth structure on a simplex having reasonable properties (everyone knows what a smooth function from a simplex to a manifold should be). I can imagine asking much more, but this should give the idea. I don't know much about schemes or synthetic differential geometry, so I don't know whether they achieve these goals. I also don't know much about Pawel Gajer's "differential spaces". Apparently Gajer has made K(Z,n) into a "differential space" for all n; this should be pretty easy if the category "differential spaces" has properties like 1)-5). In case anyone wants to read his stuff, here are the references: Pawel Gajer, Geometry of Deligne cohomology, Invent. Math. 127 (1997), 155-207. Pawel Gajer, Higher holonomies, geometric loop groups and smooth Deligne cohomology, Advances in Geometry, Birkhauser, Boston, 1999, pp. 195-235. While I'm at it, has anyone formulated a good notion of a "category internal to Diff"? I.e. a gadget with a manifold of objects, a manifold of morphisms, composition being a smooth map, and so on? This would be a snap if Diff had finite limits, but it doesn't... which is one reason I'm getting annoyed! Should I discard Diff and work with something better instead? Best, John Baez From rrosebru@mta.ca Mon Nov 12 16:43:43 2001 -0400 >From cat-dist@mta.ca Mon Nov 12 16:43:43 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 12 Nov 2001 16:43:43 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 163NpY-0007Bp-00 for categories-list@mta.ca; Mon, 12 Nov 2001 16:37:20 -0400 Subject: categories: Re: nice category of "smooth spaces"? From: Eduardo Dubuc To: categories@mta.ca (categories) Date: Mon, 12 Nov 2001 17:33:01 -0300 (ARST) In-Reply-To: <200111120355.fAC3tZP16139@math-cl-n04.ucr.edu> from "baez@math.ucr.edu" at Nov 11, 2001 07:55:35 PM X-Mailer: ELM [version 2.5 PL2] MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-Id: <20011112203304Z434950-28554+480@mate.dm.uba.ar> Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 89 > > Dear Categorists - > > I'm getting really annoyed at how the category Diff of smooth > manifolds and smooth maps isn't complete and cocomplete. > Is there some category of "smooth spaces" that repairs these > defects? Ideally I would like a category S with a bunch of > properties like: > > 1) Diff is a full subcategory of S > 2) There is a faithful functor F: S -> CGHaus, so we can think > of smooth spaces as nice topological spaces (compactly generated > Hausdorff spaces) equipped with some extra structure. > 3) S has small limits and colimits > 4) F preserves limits and colimits > 5) The obvious functor from the category of simplices to CGHaus > factors through F, with the resulting smooth structure on a simplex > having reasonable properties (everyone knows what a smooth function > from a simplex to a manifold should be). > > I can imagine asking much more, but this should give the idea. > I don't know much about schemes or synthetic differential geometry, > so I don't know whether they achieve these goals. I also don't > know much about Pawel Gajer's "differential spaces". Apparently > Gajer has made K(Z,n) into a "differential space" for all n; this > should be pretty easy if the category "differential spaces" has > properties like 1)-5). In case anyone wants to read his stuff, > here are the references: > > Pawel Gajer, Geometry of Deligne cohomology, Invent. Math. 127 > (1997), 155-207. > > Pawel Gajer, Higher holonomies, geometric loop groups and smooth Deligne > cohomology, Advances in Geometry, Birkhauser, Boston, 1999, pp. 195-235. > > While I'm at it, has anyone formulated a good notion of a > "category internal to Diff"? I.e. a gadget with a manifold > of objects, a manifold of morphisms, composition being a > smooth map, and so on? This would be a snap if Diff had > finite limits, but it doesn't... which is one reason I'm > getting annoyed! > > Should I discard Diff and work with something better instead? > > Best, > John Baez > Consider the following: CC = open sets of RR^n, all n, and all smooth maps in between. Let DD be the category of sets X furnished with a notion of Admisible maps from any object U in CC. Add(U, X) subset Allmaps(U, X) For each X, Add(U, X) should be a presheaf on U, and a sheaf for the open coverings in CC. DD is not only complete, cocomplete and cartesian closed, but also it is a Quasitopos. Of course, it is the subcategory of separated sheaves of the topos of sheafs on CC for the canonical topology. Have a full and faithfull embedding Diff --> DD defined by: Given a manifold M: Add(U, M) = Diff(U, M). There is also a faithful functor F: DD ---> EGHaus (topological haussdorf spaces generated by open sets of euclidean spaces, like the manifolds) Inspect this category, probably it has the properties you mention in your msage. This category is very much related with the well adapted models I introduced for SDG. It is of no use for SDG since it lacks infinitesimals. This is due to the fact that bad limits that exists in Diff (the non transversal ones) are preserved by the embedding Diff --> DD. In well adapted model of SDG, Diff --> EE, only the transversal limits are preserved. best, eduardo dubuc From rrosebru@mta.ca Tue Nov 13 19:44:42 2001 -0400 >From cat-dist@mta.ca Tue Nov 13 19:44:42 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 13 Nov 2001 19:44:42 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 163n42-00018e-00 for categories-list@mta.ca; Tue, 13 Nov 2001 19:33:58 -0400 From: Steve Lack MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <15344.43502.897123.950513@milan.maths.usyd.edu.au> Date: Tue, 13 Nov 2001 16:04:46 +1100 To: categories@mta.ca Subject: categories: pullbacks of toposes X-Mailer: VM 6.90 under 21.1 (patch 7) "Biscayne" XEmacs Lucid Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 90 Can anyone tell me what is known about the existence of pullbacks in the 2-category of elementary toposes, geometric morphisms, and natural transformations? I know (from Peter Johnstone's book) that pullbacks along bounded morphisms exist. (I presume that when I say pullback I really mean bipullback, but if I should mean something else then do please do let me know!) Steve Lack. From rrosebru@mta.ca Wed Nov 14 13:55:43 2001 -0400 >From cat-dist@mta.ca Wed Nov 14 13:55:43 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 14 Nov 2001 13:55:43 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 16447b-0005Js-00 for categories-list@mta.ca; Wed, 14 Nov 2001 13:46:47 -0400 Message-ID: <3BF120A2.B5A17D99@cwi.nl> Date: Tue, 13 Nov 2001 14:31:14 +0100 From: Alexander Kurz Organization: CWI X-Mailer: Mozilla 4.75 [en] (X11; U; SunOS 5.6 sun4u) X-Accept-Language: en MIME-Version: 1.0 To: categories@mta.ca Subject: categories: Coalgebras and Modal Logic Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: X-Keywords: X-UID: 91 The lecture notes of my ESSLLI'01 course are now available in a revised version at http://www.cwi.nl/~kurz/cml-esslli01.html The main aim of this course has been to sketch some current approaches to modal logics for coalgebras (Chapter 4) and to explain the duality of modal and equational logic (Chapter 5). To make the course as self-contained as possible, I have also included brief introductions to applications of coalgebras in computer science, to some categorical constructions on coalgebras, and to modal logic. Alexander Kurz From rrosebru@mta.ca Wed Nov 14 13:55:46 2001 -0400 >From cat-dist@mta.ca Wed Nov 14 13:55:46 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 14 Nov 2001 13:55:46 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 16446y-0001Xc-00 for categories-list@mta.ca; Wed, 14 Nov 2001 13:46:08 -0400 X-Authentication-Warning: camaragibe.cin.ufpe.br: ruy owned process doing -bs Date: Tue, 13 Nov 2001 10:50:35 -0200 (EDT) From: Ruy de Queiroz X-X-Sender: To: categories@mta.ca Subject: categories: CFP: WoLLIC'2002 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=ISO-8895-1 Content-Transfer-Encoding: QUOTED-PRINTABLE Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: X-Keywords: X-UID: 92 [please post. apologies for multiple postings] Call for Papers 9th Workshop on Logic, Language, Information and Computation (WoLLIC'2002) July 30 to August 2, 2002 Scientific Co-Sponsorship: IGPL, FoLLI, ASL, SBC, SBL Rio de Janeiro, Brazil (NEW: PROCEEDINGS AS AN ENTCS VOLUME) THE EVENT The "9th Workshop on Logic, Language, Information and Computation" (WoLLIC'2002), the nineth version of a series of workshops which started in 1994 with the aim of fostering interdisciplinary research in pure and applied logic, will be held in Rio de Janeiro, Brazil, from July 30 to August 2, 2002. SCOPE Contributions are invited in the form of short papers (12 A4 10pt pages) in all areas related to logic, language, information and computation, including: pure logical systems, proof theory, model theory, algebraic logic, type theory, category theory, constructive mathematics, lambda and combinatorial calculi, program logic and program semantics, logics and models of concurrency, logic and complexity theory, proof complexity, foundations of cryptography (zero-knowledge proofs), descriptive complexity, nonclassical logics, nonmonotonic logic, logic and language, discourse representation, logic and artificial intelligence, automated deduction, foundations of logic programming, logic and computation, and logic engineering. SCIENTIFIC SPONSORSHIP The 9th WoLLIC'2002 has the scientific sponsorship of the Association for Symbolic Logic (ASL), the Interest Group in Pure and Applied Logics (IGPL), the European Association for Logic, Language and Information (FoLLI), the Sociedade Brasileira de Computao (SBC), and the Sociedade Brasileira de Logica (SBL). GUEST SPEAKERS There will be a number of guest speakers, including: Ricardo Bianconi (Univ de Sao Paulo, Brazil) Erich Graedel (RWTH Aachen, Germany) (TO BE CONFIRMED) Gopalan Nadathur (University of Minnesota, USA) Rohit Parikh (City University of New York, USA) Natacha Portier (ENS-Lyon, France) Igor Walukiewicz (Bordeaux University, France) SUBMISSION Papers (up to 12 pages A4 10pt, sent preferably in postscript format by e-mail to wollic@cin.ufpe.br, or in 5(five) copies to postal address) must be RECEIVED by FEBRUARY 22, 2002 by one of the Co-Chairs of the Organising Committee. Papers must be ANONYMOUS (a separate identification page must be included), written in English and give enough detail to allow the programme committee to assess the merits of the work. Papers should start with a brief statement of the issues, a summary of the main results, and a statement of their significance and relevance to the workshop. References and comparisons with related work is also expected. Technical development directed to the specialist should follow. Results must be unpublished and not submitted for publication elsewhere, including the proceedings of other symposia or workshops. One author of each accepted paper will be expected to attend the conference in order to present it. Authors will be notified of acceptance by APRIL 1, 2002, and final versions will have to be delivered (in LaTeX format) by MAY 1, 2002. The abstracts of the papers will be published in a "Conference Report" section of the Logic Journal of the IGPL (ISSN 1367-0751) (Oxford Univ Press, web page: http://www.oup.co.uk/igpl) as part of the meeting report The proceedings will appear as a volume in the Elsevier series "Electronic Notes in Theoretical Computer Science" (http://www.elsevier.nl/locate/entcs) Full version of papers will be refereed again for publication in a special issue of the Logic Journal of the IGPL. STUDENT GRANTS WoLLIC'2002 will make available modest grants to graduate students in logic and to recent PhDs so that they may attend the meeting in Rio de Janeiro. To be considered for a grant, please (1) send a letter of application, and (2) ask your thesis supervisor to send a brief recommendation letter. The application letter should be brief (one page) and should include (1) your name, (2) your home institution, (3) your thesis supervisor's name, (4) a one-paragraph description of your studies and work in logic, (5) your estimate of the travel expenses you will incur, (6) (for citizens or residents of Brazil) citizenship or visa status, and (7) (voluntary) indication of your gender and minority status. Only modest grants will be possible, partially covering travel costs and perhaps some of the living expenses during the meeting. Women and members of minority groups are strongly encouraged to apply. In addition to funds provided by WoLLIC, it is expected that this program of student grants will be supported by a grant from the Brazilian National Council for the Scientific and Technological Development (CNPq); CNPq funds may be awarded only to students at Brazilian universities and to citizens and permanent residents of Brazil. Application by email is encouraged; put "WoLLIC grant application" in the subject line of your message. Applications and recommendations should be received before the deadline of MARCH 1st, 2002, by one of the Co-Chairs of the Organising Committee. IMPORTANT DATES Submission: FEBRUARY 22, 2002 Notification of acceptance/rejection: APRIL 1, 2002 Delivery of final (in LaTeX): MAY 1, 2002 PROGRAMME COMMITTEE Mauricio Ayala-Rincon (Univ de Brasilia, Brazil) Mario Benevides (Univ Federal do Rio de Janeiro, Brazil) Anuj Dawar (Cambridge Univ, England) Philippe de Groote (LORIA, France) Roger Maddux (Iowa State Univ, USA) Toni Pitassi (Toronto Univ, Canada) Bruno Poizat (Univ Claude Bernard - Lyon I, France) Alberto Policriti (Univ di Udine, Italy) Glynn Winskel (Cambridge Univ, England) ORGANISING COMMITTEE Edward Hermann Haeusler (PUC-Rio) Claus Akira Matsushigue (IME-USP) Anjolina G. de Oliveira (UFPE) Luiz Carlos Pereira (PUC-Rio) (Co-Chair) Ruy de Queiroz (UFPE) (Co-Chair) Jorge Petr=FAcio Viana (UFF/UFRJ) FURTHER INFORMATION Contact one of the Co-Chairs of the Organising Committee: Ruy de Queiroz, Centro de Informatica, Univ. Federal de Pernambuco, Av. Prof. Luis Freire s/n, Cidade Universitaria, 50740-540 Recife, PE, Brazil. E-mail: ruy@cin.ufpe.br, tel. +55 81 3271-8430 fax +55 81 3271-848. Luiz Carlos Pereira, Departamento de Filosofia, Pontificia Universidade Catolica do Rio de Janeiro, R. Marques de Sao Vicente 225, Rio de Janeiro, RJ, Brazil. E-mail: luiz@inf.puc-rio.br. WEB PAGE http://www.cin.ufpe.br/~wollic/wollic2002/ ------- From rrosebru@mta.ca Wed Nov 14 13:57:35 2001 -0400 >From cat-dist@mta.ca Wed Nov 14 13:57:35 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 14 Nov 2001 13:57:35 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 1644FC-0003pZ-00 for categories-list@mta.ca; Wed, 14 Nov 2001 13:54:39 -0400 Date: Wed, 14 Nov 2001 10:21:45 +0000 (GMT) From: "Dr. P.T. Johnstone" To: categories@mta.ca Subject: categories: Re: pullbacks of toposes In-Reply-To: <15344.43502.897123.950513@milan.maths.usyd.edu.au> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Scanner: exiscan *163xAx-0003bM-00*y32lcZetp7I* http://duncanthrax.net/exiscan/ Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: X-Keywords: X-UID: 93 On Tue, 13 Nov 2001, Steve Lack wrote: > Can anyone tell me what is known about > the existence of pullbacks in the 2-category > of elementary toposes, geometric morphisms, > and natural transformations? I know (from > Peter Johnstone's book) that pullbacks along > bounded morphisms exist. > > (I presume that when I say pullback I really > mean bipullback, but if I should mean something > else then do please do let me know!) > > Steve Lack. > As far as I know, the position is this. The (bi)pullback of two morphisms f and g exists if either f or g is bounded. It seems very likely that some such restriction is necessary, but as far as I'm aware nobody has constructed an example of a pair of morphisms for which the pullback is definitely known not to exist (though there are pairs for which the pullback is not known to exist). If anyone has such an example, please let me know! Peter Johnstone From rrosebru@mta.ca Wed Nov 14 14:00:09 2001 -0400 >From cat-dist@mta.ca Wed Nov 14 14:00:08 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 14 Nov 2001 14:00:09 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 1644IR-00044C-00 for categories-list@mta.ca; Wed, 14 Nov 2001 13:57:59 -0400 Message-Id: <5.1.0.14.1.20011112170946.009f5d10@mailx.u-picardie.fr> X-Sender: ehres@mailx.u-picardie.fr X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Wed, 14 Nov 2001 17:31:11 +0100 To: categories@mta.ca From: Andree Ehresmann Subject: categories: Re: nice category of "smooth spaces"? In-Reply-To: <200111120355.fAC3tZP16139@math-cl-n04.ucr.edu> Mime-Version: 1.0 Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 94 In answer to John Baez >has anyone formulated a good notion of a "category internal to Diff"? Already in the fifties, Charles Ehresmann has introduced and extensively studied categories internal to Diff (which he called "categories differentiables") in his development of Differential Geometry. His first paper essentially devoted to differentiable categories and to their relation to locally trivial fibred spaces is "Categories topologiques et categories differentiables", Coll. Geom. Diff. Globale Bruxelles, CBRM (1959), 137-150. This paper is reprinted in "Charles Ehresmann: Oeuvres completes et commentees", Part I (ed. Andree C. Ehresmann), Amiens 1983. In this volume of "Oeuvres" several other papers by Charles develop this question, and there are numerous comments by different authors giving more information. Remark that at that early time, the general notion of an internal category did not yet exist, and differentiable categories were one of the examples which motivated Charles to introduce the notion of what he called then a "structured category" (later renamed internal categories) in 1963 in the paper: "Categories structurees", Ann. Ecole Norm. Sup. 80, Pqaris (1963), 349-426. This paper, as well as the long series of his following papers where the notion is refined and extensively studied, is reprinted in the same "Oeuvres", Part III. Though the papers are in French I have added many comments in English with links to more recent papers of other authors. >the category Diff of smooth manifolds and smooth maps isn't complete and >cocomplete. Is there some category of "smooth spaces" that repairs these >defects? This is also a problem my husband and I have much studied. At this effect, Charles has given some abstract constructions to extend a concrete category into a concrete one with "enough" limits; in particular, in the paper: "Prolongements universels d'un foncteur par adjonction de limites", Dissertationes Math. LXIV Varsovie (1969), 1-72. This paper is also reprinted in the "Oeuvres" Part IV, and I have added comments in English. His construction as well as some done by others have been unified .in a short paper I have written after his death: "Partial completions of concrete functors", Cahiers Top. et Geom. Diff. XXII-3 (1981), 315-327. The more strict problem of embedding Diff in a "good" cartesian closed category has been handled by several authors; the first construction is in the paper (written under my maiden name Bastiani): "Applications differentiables et varietes de dimension infine", J. Ana. Math. Jerusalem XIII (1964), 1-114. In the eighties, there are been several other constructions, e.g. the "convenient spaces" of Frolicher. Sincerely Andree C. Ehresmann From rrosebru@mta.ca Thu Nov 15 09:17:09 2001 -0400 >From cat-dist@mta.ca Thu Nov 15 09:17:09 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 15 Nov 2001 09:17:09 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 164MDu-0007hF-00 for categories-list@mta.ca; Thu, 15 Nov 2001 09:06:30 -0400 From: Colin Stirling MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <15347.44403.304981.532301@tatties.dcs.ed.ac.uk> Date: Thu, 15 Nov 2001 11:56:35 +0000 To: concurrency@cwi.nl, categories@mta.ca, linear@cs.stanford.edu, types@cis.upenn.edu Subject: categories: PhD Studentships: Edinburgh University X-Mailer: VM 6.89 under 21.1 (patch 14) "Cuyahoga Valley" XEmacs Lucid Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 95 The Laboratory for Foundations of Computer Science, Edinburgh University has PhD studentships for next academic year, October 2002. See http://www.lfcs.informatics.ed.ac.uk/research/students.html Colin Stirling From rrosebru@mta.ca Mon Nov 19 10:33:47 2001 -0400 >From cat-dist@mta.ca Mon Nov 19 10:33:47 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 19 Nov 2001 10:33:47 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 165pLL-0002YN-00 for categories-list@mta.ca; Mon, 19 Nov 2001 10:24:17 -0400 Message-ID: From: S.J.Vickers@open.ac.uk To: categories@mta.ca Cc: univalg@yahoogroups.com Subject: categories: Operads Date: Mon, 19 Nov 2001 09:56:13 -0000 MIME-Version: 1.0 X-Mailer: Internet Mail Service (5.5.2653.19) Content-Type: text/plain; charset="iso-8859-1" Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 96 There's some discussion on the Universal Algebra list at present on operads. I'm not very familiar with them. What I understand from the discussion is they capture single sorted algebraic theories with respect to a symmetric monoidal product ox. For each natural number n an object of n-ary operators O_n is given, and an algebra A has operations O_n ox A^(n) -> A where A^(n) is A ox ... ox A n times. If you do this sort of thing with respect to categorical product, then it already contains the information of the Lawvere theory category (for single-sorted finitary algebraic theories), since hom(m,n) is hom(m,1)^n and you take hom(m,1) to be O_m. But with a monoidal product this doesn't work. It seemed to me that for proper generality the operad ought to have objects O_mn (m, n natural numbers) representing the object of operations from A^(m) to A^(n). Is there a name for that? Steve Vickers Department of Pure Maths Faculty of Maths and Computing The Open University ----------- Tel: 01908-653144 Fax: 01908-652140 Web: http://mcs.open.ac.uk/sjv22 From rrosebru@mta.ca Mon Nov 19 14:31:04 2001 -0400 >From cat-dist@mta.ca Mon Nov 19 14:31:04 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 19 Nov 2001 14:31:04 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 165t4n-0002fs-00 for categories-list@mta.ca; Mon, 19 Nov 2001 14:23:25 -0400 Subject: categories: Re: Operads To: categories@mta.ca Date: Mon, 19 Nov 2001 18:17:09 +0000 (GMT) X-Mailer: ELM [version 2.5 PL5] MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-Id: From: Tom Leinster X-Scanner: exiscan *165syk-0002td-00*dqSFIidbSpM* http://duncanthrax.net/exiscan/ Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 97 Steve Vickers wrote re operads: > What I understand from the discussion is they capture single sorted > algebraic theories with respect to a symmetric monoidal product ox. I'd agree. You could say that an operad is exactly an algebraic theory for which it makes sense to take models in a monoidal category. That should be qualified/explained a bit. By "algebraic theory" I mean to exclude *co*algebraic and *bi*algebraic theories: e.g. I do count the theory of monoids, but not those of comonoids or bimonoids. And just as monoidal categories can come equipped with symmetries or not, so operads can come equipped with symmetric group actions or not; the choice of flavours is yours. (So if you're using operads with symmetries, you should also use monoidal categories with symmetries.) And if the objects O_n are objects of some monoidal category other than Set, then you're talking about "enriched algebraic theories". > For each natural number n an object of n-ary operators O_n is given, and an > algebra A has operations O_n ox A^(n) -> A where A^(n) is A ox ... ox A n > times. > If you do this sort of thing with respect to categorical product, then it > already contains the information of the Lawvere theory category (for > single-sorted finitary algebraic theories), since hom(m,n) is hom(m,1)^n and > you take hom(m,1) to be O_m. But with a monoidal product this doesn't work. > It seemed to me that for proper generality the operad ought to have objects > O_mn (m, n natural numbers) representing the object of operations from A^(m) > to A^(n). Is there a name for that? Yes: it's a PRO or a PROP (depending on whether you don't or do have symmetries: the final P is for "permutations"). Formally, a PRO(P) is a (symmetric) strict monoidal category whose underlying monoid of objects is the natural numbers. If you want your O_mn's to be objects of an arbitrary symmetric monoidal category V (rather than just sets), then insert "V-enriched" into the last sentence. As far as I know, PROPs were first thought about by Adams and Mac Lane, and subsequently developed by Boardman and Vogt. A model for a PRO(P) is a monoidal functor from it into some other monoidal category. So, for instance, there's a PRO whose models are monoids, and another whose models are comonoids, and there's a PROP whose algebras are bimonoids. Thus PRO(P)s capture both the algebraic and the coalgebraic, whereas operads only capture the algebraic. I wouldn't interpret this as saying that PRO(P)s exist at a more "proper" level of generality than operads - just a different one. (Incidentally, there's a PROP whose algebras are Hopf algebras (=bimonoids with antipode), and an algebra for this PROP in (Set,x,1) is precisely a group. This contradicts the notion that it's impossible to formulate a definition of "group" which makes sense in an arbitrary monoidal category, although you do need your mon cat to have symmetries.) Tom From rrosebru@mta.ca Mon Nov 19 14:47:53 2001 -0400 >From cat-dist@mta.ca Mon Nov 19 14:47:53 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 19 Nov 2001 14:47:53 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 165tQJ-0006oH-00 for categories-list@mta.ca; Mon, 19 Nov 2001 14:45:39 -0400 From: baez@math.ucr.edu Message-Id: <200111191835.fAJIZnZ12032@math-cl-n03.ucr.edu> Subject: categories: Re: Operads To: categories@mta.ca (categories) Date: Mon, 19 Nov 2001 10:35:49 -0800 (PST) X-Mailer: ELM [version 2.5 PL2] MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 98 Steve Vickers writes: > There's some discussion on the Universal Algebra list at present on operads. > > I'm not very familiar with them. What I understand from the discussion is > they capture single sorted algebraic theories with respect to a symmetric > monoidal product ox. For each natural number n an object of n-ary operators > O_n is given, and an algebra A has operations O_n ox A^(n) -> A where A^(n) > is A ox ... ox A n times. > > If you do this sort of thing with respect to categorical product, then it > already contains the information of the Lawvere theory category (for > single-sorted finitary algebraic theories), since hom(m,n) is hom(m,1)^n and > you take hom(m,1) to be O_m. But with a monoidal product this doesn't work. > It seemed to me that for proper generality the operad ought to have objects > O_mn (m, n natural numbers) representing the object of operations from A^(m) > to A^(n). Is there a name for that? These are called PROPs. People in homotopy theory have been using operads and PROPs since the 1970's. As you note, there's no big difference between operads and PROPs in a Cartesian category, but there is in a more general symmetric monoidal category. A nice example occurs if we use Vect with its tensor product. We can describe coalgebras as algebras of a PROP, but not of an operad. Nonetheless, every PROP has an underlying operad, and I believe that if your symmetric monoidal category has colimits, every operad freely generates a PROP, giving an adjunction. I always forget what "PROP" is an acronym for - something like "projection and permutation". We can also formulate things like operads and PROPs in the context of a monoidal category, and they are sometimes called "planar operads" and "PROs". Best, jb From rrosebru@mta.ca Mon Nov 19 15:55:29 2001 -0400 >From cat-dist@mta.ca Mon Nov 19 15:55:29 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 19 Nov 2001 15:55:29 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 165uS3-00009o-00 for categories-list@mta.ca; Mon, 19 Nov 2001 15:51:32 -0400 Date: Mon, 19 Nov 2001 14:37:51 +0100 From: ecole@pps.jussieu.fr (Ecole d'ete 2001) Message-Id: <200111191337.fAJDbpF03413@foobar.pps.jussieu.fr> To: categories@mta.ca Subject: categories: 30th Spring School Theorical Computer Science - Early Registration MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: quoted-printable X-MIME-Autoconverted: from 8bit to quoted-printable by shiva.jussieu.fr id fAJDUqic016134 Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: X-Keywords: X-UID: 99 30th SPRING SCHOOL THEORETICAL COMPUTER SCIENCE 24 - 29 March, 2002 in AGAY (VAR, FRANCE) EARLY REGISTRATION [Apologies for multiple copies] This spring school aims at bringing together students and researchers eager to learn about the fundamental questions which language designers and implementors are facing those days, and on the most up-to-date=20 tools that theoreticians have developed or are in the process of=20 developing (such as games and ludics, or realisability for classical=20 logic and set theory). Denotational semantics was born some thirty years ago from the=20 encounter of computer scientists who aimed at implementation independent definitions of programming constructs on one hand, and=20 logicians who provided mathematical tools to this aim (domain theory)=20 on the other hand. Algebraic tools such as initial algebra semantics=20 were also instrumental to the birth of this subject. Thirty years later, the subject has enriched considerably, both in=20 tools (including connections with proof theory and category theory) and in coverage and applications (functional programming, state, control,=20 objects, parallelism, mobility,...). Concepts and constructs that have=20 arisen in the design of programming languages have found counterparts=20 in logic, logical systems have found their way to applications in the=20 form of proof assistants, etc... The rapid development of new=20 programming paradigms, in which distributed computation takes a more=20 and more important part, infers a strong demand on theory, more than=20 ever. With the rise of quite specialized subcommunities (like type theory, linear logic, pi-calculus, functional programming, etc...), it is=20 important to keep an eye on more comprehensive training events, that=20 can address the interrelations between research areas in rapid growth, and between theory-oriented research work and more goal-oriented one, with the prospect of solving problems or of improving our understanding in one domain using tools of another domain. The diversity of the=20 proposed lectures, combined with their conceptual overall unity (as=20 witnessed by the very limited number of core formal systems:=20 lambda-calculus, linear logic, pi-calculus) addresses this issue. LECTURES Denotational semantics and games semantics (5 hours) : Thomas Ehrhard , Guy McCusker Ludics (4 hours) : Pierre-Louis Curien, Jean-Yves Girard Realisability (4 hours) : Vincent Danos, Jean-Louis Krivine Continuations (4 hours) : Olivier Danvy Compilation, objects, modules (4 hours) : Xavier Leroy Mobility (5 hours) : Luca Cardelli, Cedric Fournet Security (5 hours) : Martin Abadi, Francois Pottier CONTACT, FURTHER IMFORMATION & EARLY REGISTRATION An early registration form can be filled at the following web address : http://www.pps.jussieu.fr/~ecole/ email: ecole@pps.jussieu.fr Equipe Preuves Programmes et Syst=E8mes Universit=E9 Denis Diderot Case 7014 2 Place Jussieu 75251 PARIS Cedex 05 FRANCE From rrosebru@mta.ca Tue Nov 20 12:57:30 2001 -0400 >From cat-dist@mta.ca Tue Nov 20 12:57:29 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 20 Nov 2001 12:57:30 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 166E5I-0000DY-00 for categories-list@mta.ca; Tue, 20 Nov 2001 12:49:20 -0400 Date: Tue, 20 Nov 2001 17:50:47 +0100 Message-Id: <200111201650.fAKGol115859@foobar.pps.jussieu.fr> From: Paul LEVY To: categories@mta.ca Subject: categories: adjoint equivalence MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: quoted-printable X-MIME-Autoconverted: from 8bit to quoted-printable by shiva.jussieu.fr id fAKGhWic007320 Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: X-Keywords: X-UID: 100 Hi, I have a question. If P and Q are objects in a 2-category C, and the= re is an equivalence between them, must there be an adjoint equivalence (= an adjunction whose unit and counit are both isomorphisms) between them? = Mac Lane answers this affirmatively in the case C =3D Cat, but, as far a= s I can tell, his proof doesn't generalize. Thanks for your help Paul --=20 Paul Blain Levy Universit=E9 Paris 7 http://www.pps.jussieu.fr/~levy From rrosebru@mta.ca Tue Nov 20 20:35:20 2001 -0400 >From cat-dist@mta.ca Tue Nov 20 20:35:20 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 20 Nov 2001 20:35:20 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 166LIh-0006o0-00 for categories-list@mta.ca; Tue, 20 Nov 2001 20:31:39 -0400 Mime-Version: 1.0 X-Sender: street@hera.ics.mq.edu.au Message-Id: In-Reply-To: <200111201650.fAKGol115859@foobar.pps.jussieu.fr> References: <200111201650.fAKGol115859@foobar.pps.jussieu.fr> Date: Wed, 21 Nov 2001 10:14:29 +1100 To: categories@mta.ca From: Ross Street Subject: categories: Re: adjoint equivalence Content-Type: text/plain; charset="us-ascii" ; format="flowed" Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 101 >Hi, I have a question. If P and Q are objects in a 2-category C, >and there is an equivalence between them, must there be an adjoint >equivalence (an adjunction whose unit and counit are both >isomorphisms) between them? The answer is yes. Let f : Q --> P and u : P --> Q be arrows in a 2-category K with an invertible 2-cell e : f u --> 1 and some invertible 2-cell q : 1 --> u f (some say f is quasi-inverse to u). The existence of q implies that the functor K(X,f) is fully faithful for all objects X of K. We define the unit n : 1 --> u f by the condition that f n should be the inverse of e f (using fullness of K(Q,f)). So one adjunction triangle is satisfied. The other follows by the faithfulness of K(P,f). An application of this is that a pseudonatural transformation (between pseudofunctors) which is a pointwise equivalence has a quasi-inverse pseudonatural transformation. --Ross From rrosebru@mta.ca Tue Nov 20 20:35:23 2001 -0400 >From cat-dist@mta.ca Tue Nov 20 20:35:23 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 20 Nov 2001 20:35:23 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 166LJR-0003yo-00 for categories-list@mta.ca; Tue, 20 Nov 2001 20:32:25 -0400 From: baez@math.ucr.edu Message-Id: <200111201901.fAKJ1A213798@math-cl-n05.ucr.edu> Subject: categories: re: adjoint equivalence To: categories@mta.ca (categories) Date: Tue, 20 Nov 2001 11:01:10 -0800 (PST) X-Mailer: ELM [version 2.5 PL2] MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 102 Paul Levy writes: > Hi, I have a question. If P and Q are objects in a 2-category C, and > there is an equivalence between them, must there be an adjoint > equivalence (an adjunction whose unit and counit are both isomorphisms) > between them? Yes, and constructing this adjoint equivalence is an incredibly fun exercise in playing around with diagrams for 2-morphisms in your 2-category! The proof must appear in the literature, but I don't know where, and it's really much better to do this sort of thing oneself. Knowing that it's possible should give you the gumption to do it. But if you get stuck, you can find the basic trick in the proof of Prop. 27 in my paper "Higher-dimensional algebra II: 2-Hilbert Spaces", which is available at http://xxx.lanl.gov/abs/q-alg/9609018 Ignore the rather complicated context and just stare at the formulas. Best, jb From rrosebru@mta.ca Wed Nov 21 14:43:12 2001 -0400 >From cat-dist@mta.ca Wed Nov 21 14:43:11 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 21 Nov 2001 14:43:12 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 166cC8-0002pu-00 for categories-list@mta.ca; Wed, 21 Nov 2001 14:34:01 -0400 Date: Wed, 21 Nov 2001 08:57:24 +0000 (GMT) From: "Dr. P.T. Johnstone" To: categories@mta.ca Subject: categories: Open maps of locales Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Scanner: exiscan *166TC9-0001zF-00*oVoj1FH9xvg* http://duncanthrax.net/exiscan/ Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 103 A couple of weeks ago, Walter Tholen asked whether, if a map of locales f: X --> Y has the property that pulling back along f preserves closures of sublocales, then f is necessarily open. (The converse is true, and the corresponding condition for spaces is equivalent to openness.) I found a counterexample, and posted it on this mailing list. Subsequently Walter asked me a supplementary question: if f stably has the property above (i.e. all pullbacks of f have the property), is it necessarily open? I now have a positive answer to this question, which may be of interest to people who read my earlier posting; so here it is. To prove the result for spaces, one argues as follows: given an open U \subseteq X, consider the complement V of the image f_!U in Y. The inclusion V \subseteq cl V is dense, so it must pull back to a dense inclusion; but f^*V \cap U is empty, so this implies f^*(cl V) \cap U is empty, i.e. cl V is disjoint from f_!U. So V = cl V is closed, and hence f_!U is open. The reason why this argument doesn't work for locales is, of course, that f_!U need not have a complement in the lattice of sublocales of Y. However, if we know that f_!U is a closed sublocale of Y, then the argument works exactly as for spaces, since closed sublocales are complemented. So the trick is to pull back along a morphism \tilde{Y} --> Y such that the pullback of f_!U becomes closed; specifically, we take the frame {\cal O}(\tilde{Y}) to be the subframe of the assembly of Y (the frame of all nuclei on Y) generated by the closed nuclei together with the nucleus j corresponding to f_!U. We need an explicit description of the elements of this frame: but it is easy to see that they are all nuclei of the form (j \cap c(V)) \cup c(W), where V and W are opens of Y (and we may as well assume V \supseteq W, i.e. c(V) \geq c(W)). Then we observe that j acquires a complement in this frame iff there exist V and W such that 0 = j \cap ((j\cap c(V))\cup c(W)) = j\cap c(V) and 1 = j \cup ((j\cap c(V))\cup c(W)) = j\cup c(W) (where 0 and 1 denote the bottom and top elements of the frame of nuclei). But this is equivalent to saying that j is already open as a nucleus on {\cal O}(Y). In other words, if f_!U becomes open when pulled back to a sublocale of \tilde{Y}, then it was already open as a sublocale of Y. Of course, it needs checking that, in the square \tilde{U} -------> \tilde{f_!U} | | | | | | v v \tilde{X} -------> \tilde{Y} obtained by pulling back along \tilde{Y} --> Y, the top edge is an epimorphism, so that \tilde{f_!U} is the image of \tilde{U} under \tilde{f}. But this follows easily from the fact that, for any g: Z --> Y, \tilde{Z} is the locale corresponding to the frame obtained from {\cal O}(Z) by `declaring g^*(f_!U) to be closed'. For we have f^*(f_!U) \supseteq U, and hence \tilde{U} --> U is an isomorphism, as is \tilde{f_!U} --> f_!U. Peter Johnstone From rrosebru@mta.ca Wed Nov 21 14:43:14 2001 -0400 >From cat-dist@mta.ca Wed Nov 21 14:43:14 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 21 Nov 2001 14:43:14 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 166cGu-0007yH-00 for categories-list@mta.ca; Wed, 21 Nov 2001 14:38:57 -0400 Date: Wed, 21 Nov 2001 09:49:49 -0800 From: Vaughan Pratt Message-Id: <200111211749.JAA10983@coraki.Stanford.EDU> To: categories@mta.ca Subject: categories: Characterizing FinSet up to equivalence Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 104 Rosebrugh and Wood [Proc AMS 122(2), 409-413, 1994] characterized Set up to equivalence as the only category with a string of four adjoints to the left of its Yoneda embedding. A slew of questions about infinite sets being up for grabs, such as the number of infinite cardinals less than 2^N, it is clear that any such on-the-nose characterization must smuggle in much if not all of what it sets out to characterize. Finite sets do not raise these sorts of questions, removing the above argument for the inevitability of smuggling set-theoretic knowledge into a characterization of FinSet. Now some logicians such as Sol Feferman, and one imagines at least a few category theorists, view category theory as built on set theory. An alternative viewpoint is that the basic notions of category theory exist independently of the category of sets. Where one sits in this spectrum is presumably correlated with how strongly one feels that set theory has been smuggled into the following. For ignorance of the correct name I'll call an object b "strongly indecomposable" when Hom(b,-) preserves binary sums. "Successor object" seems like a reasonable name for an object of the form b+1 (1 the final object). Write FinC for the full subcategory of C whose objects have finitely many elements (morphisms from 1). Claim. Let C be a category with finite sums and final object 1. If 1 is a strongly indecomposable generator and every object is either initial or a successor, then FinC is equivalent to FinSet. (Set, FinSet, and Stone all meet these conditions on C, which could be weakened without changing the conclusion by replacing "finite sums" by "sums with 1" and "strongly indecomposable" (SI) by the requirement that b+1 have exactly one element not an element of b. Or, the dichotomy condition could be strengthened to "For all a,b there exists c such that either a ~ b+c or b ~ a+c.") Proof: Given b in FinC, use dichotomy to shed its n elements sequentially yielding b = 0+1+...+1. SI prevents loss or repetition of any element. For any c (in FinC or not), |0=>c| = 1 since 0 is initial, and by induction on n, |b=>c| >= |c|^n. But 1 generates so |b=>c| <= |c|^n. Pointers to previous appearances of this would be appreciated. Do other familiar categories besides finite sets have a similarly short and elementary characterization, e.g. finite Boolean algebras, finite Abelian groups, finite posets, finite monoids, etc? Finite Boolean algebras are easily characterized as dual finite sets. Specifically, for any category C with finite products and initial object 2, if 2 is a strongly coindecomposable cogenerator and every object is either final or of the form 2xb, then FinC is equivalent to FinBool. Bool, FinBool, and CABA all satisfy these conditions on C. ("2 strongly coindecomposable" means of course that Hom(-,2) sends finite products to finite sums; equivalently, every predicate q:axb->2 on axb factors through exactly one of the projections p1:axb->a, p2:axb->b, i.e. it acts as a predicate on one of a or b and is constant on the other.) Have we smuggled Boolean algebra into this argument? Is category theory based on set theory to any greater extent than on Boolean algebra? And is there any essential difference between this argument and its mate for FinSet? Sets and Boolean algebras would seem to deserve equal credit for their foundational role in both. My own view, first articulated in LICS'95, 444-454, is that mathematics is a catenary, the "Stone Gamut," held up at each end by the twin categories Set and CABA. The catenary is created from their interaction. Any suggestions for characterizing finite Abelian groups? Vaughan Pratt From rrosebru@mta.ca Wed Nov 21 14:43:18 2001 -0400 >From cat-dist@mta.ca Wed Nov 21 14:43:18 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 21 Nov 2001 14:43:18 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 166cFV-0004Dt-00 for categories-list@mta.ca; Wed, 21 Nov 2001 14:37:30 -0400 From: Philippe Gaucher Message-Id: <200111211627.fALGRGG12715@math.u-strasbg.fr> Subject: categories: About internal 1-categories To: categories@mta.ca Date: Wed, 21 Nov 101 17:27:16 +0100 (MET) X-Mailer: ELM [version 2.4 PL25] Content-Type: text Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 105 Hello I would need please a bibliographical reference for the following theorem : "consider a complete cocomplete cartesian closed category C. Then the category of internal 1-categories of C is complete cocomplete and ccartesian closed". I need it for the redaction of a proof. Thanks in advance. pg. From rrosebru@mta.ca Wed Nov 21 14:43:22 2001 -0400 >From cat-dist@mta.ca Wed Nov 21 14:43:22 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 21 Nov 2001 14:43:22 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 166cIB-00035L-00 for categories-list@mta.ca; Wed, 21 Nov 2001 14:40:16 -0400 Message-Id: Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Date: Wed, 21 Nov 2001 19:16:29 +0100 To: categories@mta.ca From: grandis@dima.unige.it (Marco Grandis) Subject: categories: Exact adjunctions Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 106 There is a nice lemma on adjoint functors, purely 2-categorical, and certainly known to various colleagues. As I need it in a paper on homotopy, I would like to know if it is *published with proof*, somewhere. I also like to "advertise" it here, because I think it deserves to be known more widely. LEMMA. If,in an adjunction, any one of the four natural transformations which appear in the triangle identities is invertible, so are the other three. [Proof below.] A few years ago I was considering such adjunctions, which I was calling "connections" because adjunctions between ordered sets ("covariant Galois connections") are always of this type. Renato Betti was also considering them, under the name of "exact adjunctions" (which I now prefer, also because "connection" has already too many meanings). I learnt from him that "one condition is sufficient". At my knowledge, the above result appears in two works. It is cited without proof in - R.Betti, Adjointness in descent theory, JPAA 116 (1997), 41-47. It also appears, with a proof and in a more general formulation (for biadjoints), in a preprint: - R.Betti, D. Schumacher and R. Street, Factorizations in bicategories, Dip. Mat. Politecnico di Milano n. 22/R, 1999. ___ Proof. Write F -| G the adjunction; u: 1 -> GF the unit; v: FG -> 1 the counit. The triangle identities say that (a) vF.Fu = idF, (b) Gv.uG = idG. Assume that Fu is invertible, so that also vF is so and it is sufficient to prove that: (c) uG.Gv = id(GFG). This commposite occurs in the upper row of the following commutative diagram (vertical arrows down) Gv uG GFG ----> G ----> GFG uGFG | |uG |uGFG GFGFG ----> GFG ----> GFGFG GFGv GFuG Now, the lower row is the identity, because G(Fu)G is invertible and the "other composite", GF(Gv.uG) is an identity, by (b). Since the vertical arrow uGFG has a left inverse, by (b) again, "cancelling it from the outer rectangle" we get (c). [Perhaps it can be simplified; I did not spent much time for that.] ___ From rrosebru@mta.ca Wed Nov 21 14:43:25 2001 -0400 >From cat-dist@mta.ca Wed Nov 21 14:43:25 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 21 Nov 2001 14:43:25 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 166cEU-0003Qr-00 for categories-list@mta.ca; Wed, 21 Nov 2001 14:36:26 -0400 Date: Wed, 21 Nov 2001 13:30:33 +0100 Message-Id: <200111211230.fALCUX123586@foobar.pps.jussieu.fr> From: Paul LEVY To: categories@mta.ca Subject: categories: Re: adjoint equivalence References: <200111201650.fAKGol115859@foobar.pps.jussieu.fr> MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: quoted-printable X-MIME-Autoconverted: from 8bit to quoted-printable by shiva.jussieu.fr id fALCNJic071253 Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 107 "If P and Q are objects in a 2-category C, and there is an equivalence between them, must there be an adjoint equivalence (an adjunction whose unit and counit are both isomorphisms) between them?" Thanks Richard, Ross and John for your affirmative answer. I would have preferred a counterexample, but that's life. I'm trying to make an argument that the natural 2-categorical analogue of isomorphism is adjoint equivalence rather than equivalence, but your result suggests that it doesn 't matter. What about automorphism groups? Say we have an object P in a 2-category C. We can either consider the category (strict monoidal with inverses) of auto - adjoint equivalences on P and transformations between them, or we can consider the category (strict monoidal with inverses) of auto - equivalences on P and transformations between them. Must these be equivalent? Thanks Paul -- Paul Blain Levy Universite Paris 7 http://www.pps.jussieu.fr/~levy From rrosebru@mta.ca Wed Nov 21 14:43:28 2001 -0400 >From cat-dist@mta.ca Wed Nov 21 14:43:28 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 21 Nov 2001 14:43:28 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 166cAx-0002s3-00 for categories-list@mta.ca; Wed, 21 Nov 2001 14:32:47 -0400 Date: 20 Nov 2001 18:44:31 -0800 Message-ID: <20011121024431.5964.cpmta@c015.snv.cp.net> X-Sent: 21 Nov 2001 02:44:31 GMT Content-Type: text/plain Content-Disposition: inline Mime-Version: 1.0 To: categories@mta.ca From: Al Vilcius X-Mailer: Web Mail 3.9.3.5 X-Sent-From: remote@vilcius.com Subject: categories: alg-coalg duality Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 108 If F:C-->C is a functor with opposite F*:C*-->C* then (F-algebras)* is trivially equivalent to (F*)-coalgebras. Can this duality be induced by a schizophrenic object? From rrosebru@mta.ca Wed Nov 21 15:19:51 2001 -0400 >From cat-dist@mta.ca Wed Nov 21 15:19:51 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 21 Nov 2001 15:19:51 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 166csE-0005eS-00 for categories-list@mta.ca; Wed, 21 Nov 2001 15:17:31 -0400 Date: Wed, 21 Nov 2001 20:20:04 +0100 Message-Id: <200111211920.fALJK4N27303@foobar.pps.jussieu.fr> From: Paul LEVY To: categories@mta.ca Subject: categories: Re: adjoint equivalence References: <200111201650.fAKGol115859@foobar.pps.jussieu.fr> Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: X-Keywords: X-UID: 109 Hi, I just found the result I asked for yesterday in Blackwell, Kelly, Power, Journal of Pure and Applied Algebra vol. 59. I hadn't noticed it. Looking at the discussion in that paper, I see that I should have been more precise in phrasing my question today. By "equivalence from C to D" I meant "a 4-tuple (f,g,eta,mu) such that...". I didn't mean "an f such that there exists g,eta,mu such that...", as I belong to the "don't put existential quantifiers in categorical definitions" school of thought. Sorry for any confusion Paul From rrosebru@mta.ca Wed Nov 21 19:57:36 2001 -0400 >From cat-dist@mta.ca Wed Nov 21 19:57:36 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 21 Nov 2001 19:57:36 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 166hBE-0000Gu-00 for categories-list@mta.ca; Wed, 21 Nov 2001 19:53:24 -0400 Date: Wed, 21 Nov 2001 22:27:06 +0000 (GMT) From: "Dr. P.T. Johnstone" To: Marco Grandis Subject: categories: Re: Exact adjunctions In-Reply-To: Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Scanner: exiscan *166fpk-0005bt-00*7zsnNXW/.6o* http://duncanthrax.net/exiscan/ Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 110 On Wed, 21 Nov 2001, Marco Grandis wrote: > There is a nice lemma on adjoint functors, purely 2-categorical, and > certainly known to various colleagues. > > As I need it in a paper on homotopy, I would like to know if it is > *published with proof*, somewhere. > I also like to "advertise" it here, because I think it deserves to be known > more widely. > > LEMMA. > > If,in an adjunction, any one of the four natural transformations which > appear in the triangle identities is invertible, so are the other three. > [Proof below.] > > A few years ago I was considering such adjunctions, which I was calling > "connections" because adjunctions between ordered sets ("covariant Galois > connections") are always of this type. > Renato Betti was also considering them, under the name of "exact > adjunctions" (which I now prefer, also because "connection" has already too > many meanings). > I learnt from him that "one condition is sufficient". > I can't provide a reference for this result, but my ex-students will testify that it has been an exercise on the problem sets for my first-year graduate course in category theory for at least the last ten years. Also, in my review of Francis Borceux' "Handbook of Categorical Algebra" for the Bulletin of the London Math Soc., I referred to the result as a "shibboleth" for testing whether someone is a genuine category theorist: if he recognizes it as something he's always known, then he is a true category-theorist, otherwise not. (This in the context that Borceux appeared not to be aware of the result.) Incidentally, "idempotent adjunction" seems to me a better name than "exact adjunction". Peter Johnstone From rrosebru@mta.ca Thu Nov 22 12:56:44 2001 -0400 >From cat-dist@mta.ca Thu Nov 22 12:56:44 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 22 Nov 2001 12:56:44 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 166x4h-0001JC-00 for categories-list@mta.ca; Thu, 22 Nov 2001 12:51:49 -0400 Date: Wed, 21 Nov 2001 19:08:48 -0500 (EST) From: F W Lawvere Reply-To: wlawvere@acsu.buffalo.edu To: categories@mta.ca Subject: categories: k-spaces and Hurewicz Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 111 In response to Ronnie Brown's inquiries about "embeddability" and cartesian closed categories, the following three publications may be of interest: F.W. Lawvere Volterra's Functionals and the Covariant Cohesion of Space Rendiconti del Circolo Matematico di Palermo (2) Supplemento No. 64, 2000, pp 201-204. This paper is partly about the history of the problem with which Ronnie is concerned, but I only later became aware of the significance of the following two papers: Ralph H. Fox On Topologies for Function Spaces Bulletin of the American Mathematical Society, vol. 51, 1945, pp 429-432 This paper is often cited, but note that it states explicitly that it was written in response to a question in a letter by W. Hurewicz. David Gale Compact Sets of Functions and Function Rings Proceedings of the American Mathematical Society, vol. 1, 1950, pp 303-308 Here David Gale states that the definition of k-space was due to W. Hurewicz. Thus it appears that both the statement of the problem, as well as its standard solution were given by W. Hurewicz. The relevance to homotopy theory as well as to functional analysis was recognized over fifty years ago. There are actually many similar categories; an axiomatic approach (rather than a pragmatic one) is required in order to systematize the relation between them. They can be "normalized", as Peter Johnstone did for the sequential case, to become toposes; this should clarify the comparisons as well as provide categories with much more "convenient" exactness properties. Bill Lawvere ************************************************************ F. William Lawvere Mathematics Department, State University of New York 244 Mathematics Building, Buffalo, N.Y. 14260-2900 USA Tel. 716-645-6284 HOMEPAGE: http://www.acsu.buffalo.edu/~wlawvere ************************************************************ From rrosebru@mta.ca Thu Nov 22 12:56:53 2001 -0400 >From cat-dist@mta.ca Thu Nov 22 12:56:53 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 22 Nov 2001 12:56:53 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 166x6f-00064Q-00 for categories-list@mta.ca; Thu, 22 Nov 2001 12:53:50 -0400 Message-Id: <3.0.5.32.20011122124801.0082eda0@TESLA.open.ac.uk> X-Sender: sjv22@TESLA.open.ac.uk X-Mailer: QUALCOMM Windows Eudora Light Version 3.0.5 (32) Date: Thu, 22 Nov 2001 12:48:01 +0000 To: categories@mta.ca From: S Vickers Subject: categories: Re: Characterizing FinSet up to equivalence In-Reply-To: <200111211749.JAA10983@coraki.Stanford.EDU> Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 112 Vaughan Pratt writes: >Now some logicians such as Sol Feferman, and one imagines at least a >few category theorists, view category theory as built on set theory. >... Where one sits in this spectrum is >presumably correlated with how strongly one feels that set theory has been >smuggled into the following. > >... > >Claim. Let C be a category with finite sums and final object 1. If 1 is >a strongly indecomposable generator and every object is either initial or >a successor, ... > >(Set, FinSet, and Stone all meet these conditions on C, ... Set theory has been smuggled into the whole argument in an all-pervading way, and moreover in a specifically classical form. This causes problems when you start exploring more adventurously the nature of sethood. The argument about finiteness is then much less help than it might have appeared at first. As a particular example that category theory helps us to explore, we know there are benefits to be had from thinking of sheaves as sets (continuously parametrized by points of spaces, but the trick is to keep the parameter under wraps). They are benefits that do not depend on having recourse to some fixed classical notion of "actual" sets, unparametrized. There are important notions of finiteness for sheaves that require investigation. For instance, "Kuratowski finiteness" underlies the logically important notion of finitely bounded universal quantification. But the categories of sheaves do not in general get off the ground with Vaughan's results, since we do not have that every sheaf is either initial or a successor. Hence the results make little contribution to understanding finiteness for sheaves. Let me present another concrete set theory that, to my mind, provides foundations just as good as those of classical set theory. Buy a lorry load of ready-mixed concrete. Spread it evenly over your front drive. Wade into the middle of it and wait for it to set. Now if you want to explore beyond the margins of your front drive you will be safe, because you have a good solid bit of concrete to support you. Harsh? To bring the sheaves into classical set theory requires quite cumbersome machinery. We do better to find out what really makes the sheaves work rather than insistently reducing them to a notion of set that we know to be ill-matched. Only then can we, as the psalm puts it, "return with songs of joy, carrying sheaves with us". Steve Vickers. From rrosebru@mta.ca Thu Nov 22 12:57:08 2001 -0400 >From cat-dist@mta.ca Thu Nov 22 12:57:08 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 22 Nov 2001 12:57:08 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 166x56-00056t-00 for categories-list@mta.ca; Thu, 22 Nov 2001 12:52:14 -0400 Message-ID: <3BFC51A2.B31DB43C@kestrel.edu> Date: Wed, 21 Nov 2001 17:15:14 -0800 From: Dusko Pavlovic X-Mailer: Mozilla 4.77 [en] (X11; U; Linux 2.4.9-6 i686) X-Accept-Language: en MIME-Version: 1.0 To: categories@mta.ca Subject: categories: Re: Exact adjunctions References: Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 113 the following is in the appendix of my paper Maps II ftp://ftp.kestrel.edu/pub/papers/pavlovic/mapsII.ps.gz Lemma. Let R be a bicategory. Suppose we are given 0-cells A and B, 1-cells F:A->B and G:B->A and 2-cells h:id_A --> FG and e:GF -->id_B. Then F is left adjoint to G if and only if the 2-cells hF;Fe : F --> FGF --> F Gh;eG : G --> GFG --> G are both split epi (or split mono). the paper was published in 1996, but this particular lemma (with the proof) was announced on this list shortly after i arrived to mcgill, probably in january or february of 1992. -- dusko From rrosebru@mta.ca Thu Nov 22 12:57:17 2001 -0400 >From cat-dist@mta.ca Thu Nov 22 12:57:17 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 22 Nov 2001 12:57:17 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 166x5Q-0005Fj-00 for categories-list@mta.ca; Thu, 22 Nov 2001 12:52:33 -0400 Date: Thu, 22 Nov 2001 11:02:46 +0000 From: Jules Bean To: categories@mta.ca Subject: categories: Re: Exact adjunctions Message-ID: <20011122110246.D13950@blueberry.jellybean.co.uk> References: Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.2.5i In-Reply-To: ; from P.T.Johnstone@dpmms.cam.ac.uk on Wed, Nov 21, 2001 at 10:27:06PM +0000 Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 114 On Wed, Nov 21, 2001 at 10:27:06PM +0000, Dr. P.T. Johnstone wrote: > On Wed, 21 Nov 2001, Marco Grandis wrote: > > I can't provide a reference for this result, but my ex-students will > testify that it has been an exercise on the problem sets for my first-year > graduate course in category theory for at least the last ten years. Also, I so testify. Example sheet 2, question 3. As I recall, I couldn't do it at the time :-( Surprisingly, the result doesn't seem to be in CWM (Mac Lane). It is, however, in Lambek & Scott (Introduction to Higher Order Categorical Logic), in their brief introductory section. It is the content of Proposition 4.2 and Lemma 4.3, as far as I can see. Jules From rrosebru@mta.ca Thu Nov 22 12:59:38 2001 -0400 >From cat-dist@mta.ca Thu Nov 22 12:59:38 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 22 Nov 2001 12:59:38 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 166xC2-0005Di-00 for categories-list@mta.ca; Thu, 22 Nov 2001 12:59:18 -0400 From: "Walter Tholen" Message-Id: <1011122103833.ZM75326@pascal.math.yorku.ca> Date: Thu, 22 Nov 2001 10:38:33 -0500 In-Reply-To: grandis@dima.unige.it (Marco Grandis) "categories: Exact adjunctions" (Nov 21, 7:16pm) References: X-Mailer: Z-Mail (4.0.1 13Jan97) To: categories@mta.ca, Subject: categories: re: Exact adjunctions MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 115 Hi Marco - I learned about the fact that you are alluding to when I took my first course on category theory with Nico Pumpluen in 1969 at the University of Muenster, and this is documented in his extended and mimeographed lecture notes (as "Satz 4.4") that I was in charge of producing when he gave the course again in 1972. It may have been "folklore" knowledge already at that time. Nico called such adjunctions Galois adjunctions, but I agree with Peter that idempotent adjunction is the better name. Well, all this may not really be an answer to your question, depending on what you call "published", in which case you can take this as background information. Best regards, Walter. On Nov 21, 7:16pm, Marco Grandis wrote: > Subject: categories: Exact adjunctions > There is a nice lemma on adjoint functors, purely 2-categorical, and > certainly known to various colleagues. > > As I need it in a paper on homotopy, I would like to know if it is > *published with proof*, somewhere. > I also like to "advertise" it here, because I think it deserves to be known > more widely. > > LEMMA. > > If,in an adjunction, any one of the four natural transformations which > appear in the triangle identities is invertible, so are the other three. > [Proof below.] > > A few years ago I was considering such adjunctions, which I was calling > "connections" because adjunctions between ordered sets ("covariant Galois > connections") are always of this type. From rrosebru@mta.ca Fri Nov 23 20:01:02 2001 -0400 >From cat-dist@mta.ca Fri Nov 23 20:01:02 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 23 Nov 2001 20:01:02 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 167Q7V-0002Ci-00 for categories-list@mta.ca; Fri, 23 Nov 2001 19:52:33 -0400 From: baez@math.ucr.edu Message-Id: <200111222115.fAMLF4u16736@math-cl-n03.ucr.edu> Subject: categories: Characterizing FinSet up to equivalence To: categories@mta.ca (categories) Date: Thu, 22 Nov 2001 13:15:04 -0800 (PST) X-Mailer: ELM [version 2.5 PL2] MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 116 Vaughan Pratt writes: >For ignorance of the correct name I'll call an object b "strongly >indecomposable" when Hom(b,-) preserves binary sums. I've heard this called "connected", which seems very nice, since that's what it amounts to in Top. >"Successor object" seems >like a reasonable name for an object of the form b+1 (1 the final object). >Write FinC for the full subcategory of C whose objects have finitely many >elements (morphisms from 1). > >Claim. Let C be a category with finite sums and final object 1. If 1 is >a strongly indecomposable generator and every object is either initial or >a successor, then FinC is equivalent to FinSet. Since the concept of "finite set" is sitting right in the definition of FinC, we have to know all about finite sets to use this characterization of FinSet... but I wouldn't be surprised if that annoying circularity is inevitable. I wonder if anyone knows a reference to this characterization, which is simpler and perhaps more blatantly circular: Claim: FinSet is the free category with finite sums on one object. This is supposed to be a short way of saying that if C is a category with finite sums containing an object x, there is a finite-sum-preserving functor F: FinSet -> C, unique up to natural isomorphism, such that F(1) = x. It's a categorification of the fact that the natural numbers are the free commutative monoid on one generators. I think it's even true. I think this is also true: Claim: FinSet is the free biCartesian category on nothing. This is supposed to be a short way of saying that if C is a category with finite sums and finite products, the latter distributing over the former, then there is is a finite-sum-and- product-preserving functor F: FinSet -> C, unique up to natural isomorphism. It's a categorification of the fact that the natural numbers are the free commutative rig on no generators. Personally I find this sort of characterization a bit more illuminating than Vaughan's. Throughout math, as soon as you define some nice sort of gadget, you instantly focus on the free gadgets of this sort - which are probably the ones you knew about before you even made the definition! It's a circular business, but that's life. Best, John Baez From rrosebru@mta.ca Fri Nov 23 20:01:05 2001 -0400 >From cat-dist@mta.ca Fri Nov 23 20:01:05 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 23 Nov 2001 20:01:05 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 167QAo-000265-00 for categories-list@mta.ca; Fri, 23 Nov 2001 19:55:58 -0400 Message-Id: <5.1.0.14.1.20011123172042.009ef2f0@mailx.u-picardie.fr> X-Sender: ehres@mailx.u-picardie.fr X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Fri, 23 Nov 2001 17:35:48 +0100 To: categories@mta.ca From: Andree Ehresmann Subject: categories: Cartesian closed categories of internal categories Mime-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1"; format=flowed Content-Transfer-Encoding: quoted-printable Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 117 In answer to Philippe Gaucher who asks for >a bibliographical reference for the following theorem : "consider a complete >cocomplete cartesian closed category C. Then the category of internal 1- >categories of C is complete cocomplete and cartesian closed". This theorem (and also a more general one for models of a sketch in a category ) has been proved in our paper: "Categories of sketched structures", by Andree Bastiani (my maiden name) and Charles Ehresmann, Cahiers de Top. et Geom. Diff. XIII-2 (1972), 1-107, reprinted in "Charles Ehresmann; Oeuvres completes et commentees" Part IV-2, pp. 407-517. In particular, in Sections 12 and 13 we give two constructions, one valid for all sketches, the other particular to the case of internal categories. This last construction generalizes a construction we had given in a preceding paper: "Categories de foncteurs structures", Cahiers TGD XI-3 (1969), 329-384, reprinted in the Oeuvres Part IV-1 in the case of categories internal to a concrete category. Hoping these old references may be of some help, Sincerely Professeur Andree C. Ehresmann Faculte de Mathematique et Informatique 33 rue Saint-Leu F-80039 Amiens. France Directeur des "Cahiers de Topologie et Geometrie Differentielle categoriques" e-mail: ehres@u-picardie.fr Site Internet: http://perso.wanadoo.fr/vbm-ehr From rrosebru@mta.ca Sun Nov 25 19:34:26 2001 -0400 >From cat-dist@mta.ca Sun Nov 25 19:34:26 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 25 Nov 2001 19:34:26 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 1688gz-00025k-00 for categories-list@mta.ca; Sun, 25 Nov 2001 19:28:09 -0400 From: Peter Selinger Message-Id: <200111241838.fAOIcLE01423@quasar.mathstat.uottawa.ca> Subject: categories: Re: Characterizing FinSet up to equivalence To: categories@mta.ca (categories) Date: Sat, 24 Nov 2001 13:38:21 -0500 (EST) In-Reply-To: <200111222115.fAMLF4u16736@math-cl-n03.ucr.edu> from "baez@math.ucr.edu" at Nov 22, 2001 01:15:04 PM X-Mailer: ELM [version 2.5 PL3] MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 118 baez@math.ucr.edu wrote: > > Claim: FinSet is the free category with finite sums on one object. I wonder what happens in the case of more than one generator. For instance, the free category with finite sums on two objects is FinSet x FinSet. In the case where the set of generators is discrete, it does not make a difference if one also adds coequalizers, e.g. FinSet is the free category with finite colimits on one object. What about the case where one has morphisms on the generators? From [Mac Lane], we know: If D is any diagram (small category), then its free co-completion is the Yoneda category Set^{D^op}. Is this still true when inserting the word "finite"? If D is any diagram, then its free completion under finite colimits is FinSet^{D^op}? And what happens if one drops the coequalizers? Does the free completion of a diagram D under coproducts have a Yoneda-like characterization? -- Peter From rrosebru@mta.ca Sun Nov 25 19:34:29 2001 -0400 >From cat-dist@mta.ca Sun Nov 25 19:34:29 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 25 Nov 2001 19:34:29 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 1688fU-0008Fb-00 for categories-list@mta.ca; Sun, 25 Nov 2001 19:26:36 -0400 Message-Id: <200111241622.IAA30068@coraki.Stanford.EDU> To: categories@mta.ca (categories) Subject: categories: Re: Characterizing FinSet up to equivalence In-Reply-To: Your message of "Thu, 22 Nov 2001 13:15:04 PST." <200111222115.fAMLF4u16736@math-cl-n03.ucr.edu> Date: Sat, 24 Nov 2001 08:22:09 -0800 From: Vaughan Pratt Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 119 In response to John Baez and Steve Vickers, let me put my question more directly. What categories of "finite" (in any sense of finite you like) objects can be characterized up to equivalence as the finite objects (again feel free to define this notion yourself) common to all categories of some elementary class? I showed that finite sets and finite Boolean algebras could be so characterized. What about finite Abelian groups, or finitely presented (by generators and relators) Abelian groups, or finite dimensional vector spaces over some field? Once an appropriate notion of finiteness is settled on, these become straightforward yes-no questions. A related question is, what categories can be characterized up to equivalence by purely elementary means? I hope it's clear why I asked what I did and not this. (Loewenheim-Skolem and all that.) Like John Baez, I like free algebras and cofree coalgebras as methods of characterization. (Why else would Dusko Pavlovic and I bother to characterize the continuum as a cofree coalgebra?) I would immediately withdraw whatever I said that conveyed the opposite if I knew what it was. In asking about definability in a given framework (here first order logic plus cardinality restrictions) I had not intended to imply even endorsement of that framework, let alone rejection of other frameworks. In defense of sets, I very much like them as a foundational concept, in considerable part because one can reach a larger audience by starting from sets than from sheaves. I was impressed that anyone would dislike sets so much as to compare starting from them to standing in wet concrete until it sets (or were you just making a pun about sets, Steve?). Sheaves as a starting point is fine for category theorists, who are equipped to benefit from its greater generality, but they are singularly inappropriate for most other mathematical audiences, for most of whom experience with adding up the restaurant bill has made natural numbers much more familiar than sheaves. I'm not objecting to crash courses on sheaves here, just to talks for a general mathematical audience that start out "Ladies and gentlemen, let S be a sheaf." Mentioning categories on Steve Simpson's FOM mailing list typically brings on a diatribe from someone railing against categories. It would be nice if one could mention sets on this mailing list without the analogous response. John Baez makes exactly the right connection between sets and the free monoid on one generator (Peter Selinger made a related remark to me privately about the free cocomplete category on one generator satisfying FinC ~ FinSet). The categorification of the semiring of natural numbers yielding the distributive category of sets is natural, simple, beautiful, and easily understood. However I disagree that the assumption of finiteness constitutes smuggling in FinSet. A tiny part of it, fine, but that's a long way from smuggling in the whole notion of function. The notion of linear order with endpoints can be characterized elementarily up to isomorphism if one restricts attention to countable linear orders, but how much of the notion of linear order does countability smuggle in here? Cardinality restrictions as an axiomatization strategy convey no substantial structural information, and are one of the mildest possible excursions outside first order logic when such is unavoidable. They have a long and distinguished history in logic. Vaughan Pratt From rrosebru@mta.ca Mon Nov 26 16:25:55 2001 -0400 >From cat-dist@mta.ca Mon Nov 26 16:25:55 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 26 Nov 2001 16:25:55 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 168SGn-00019h-00 for categories-list@mta.ca; Mon, 26 Nov 2001 16:22:25 -0400 From: Boerger Organization: FernUniversitaet To: categories@mta.ca Date: Mon, 26 Nov 2001 11:27:24 +0100 MIME-Version: 1.0 Content-type: text/plain; charset=US-ASCII Content-transfer-encoding: 7BIT Subject: categories: Re: Characterizing FinSet up to equivalence In-reply-to: <200111211749.JAA10983@coraki.Stanford.EDU> X-mailer: Pegasus Mail for Win32 (v2.54DE) Message-Id: Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 120 Hello, what kind of characterization do you want? If you accept ZFC as "outside world", then there is no elementary characterization of FinSet (in the sense of finitary first-order logic) because every ultrapower of FinSet satisfies the same (finitary) first-order sentences. Greetings Reinhard From rrosebru@mta.ca Mon Nov 26 16:25:58 2001 -0400 >From cat-dist@mta.ca Mon Nov 26 16:25:58 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 26 Nov 2001 16:25:58 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 168SGW-0002Ro-00 for categories-list@mta.ca; Mon, 26 Nov 2001 16:22:09 -0400 Message-ID: From: S.J.Vickers@open.ac.uk To: categories@mta.ca Subject: categories: Re: Characterizing FinSet up to equivalence Date: Mon, 26 Nov 2001 10:09:52 -0000 MIME-Version: 1.0 X-Mailer: Internet Mail Service (5.5.2653.19) Content-Type: text/plain; charset="iso-8859-1" Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 121 > In defense of sets, I very much like them as a foundational concept, in > considerable part because one can reach a larger audience by starting from > sets than from sheaves. I was impressed that anyone would dislike sets so > much as to compare starting from them to standing in wet concrete until it > sets (or were you just making a pun about sets, Steve?). No, I was in earnest. Having over quite a few years now seen for myself the possibilities of using constructive reasoning to _simplify_ mathematics, so that it now seems very obvious, I get overquickly distressed when other people still haven't seen it. However, I should explain that I was not criticizing sets as pedagogic foundations, where you start from when you're explaining to a large audience, nor as (if I may use Paul Taylor's phrase) practical foundations, since the naive concepts of sets (albeit non-classical ones) underly the way one reasons in toposes. The parable about concrete concerned philosophical foundations, trying to fix on classical set theory as the deep unifying account of what mathematics depends on. Maybe in any case Vaughan wasn't thinking so much about such philosophical diversions. There is a pragmatic message. There are a number of different characterizations of finiteness. Classically they are all equivalent, but it has been known to topos theorists for quite a while now that if you start considering non-classical sets (such as sheaves) or computational structures you find they are inequivalent. My belief is that the explanations of the differences can be understood in naive set theoretic terms, though to see why they are genuine differences and not just presentational you need to know a bit more about sheaves and such. A particular message (really arising out of geometric logic) is that finiteness is _structure_ on a set, and not just a property: How do you know a set is finite? There is something there in its structure that tells you. I've tried to bring this out in my paper "Strongly algebraic = SFP (topically)", soon to appear in Math. Structures in Computer Science, and also available through my web page http://mcs.open.ac.uk/sjv22. In particular you see there discussed Kuratowski finiteness (you can list of all the elements but can't necessarily remove duplicates), finite decidable (in addition you can detect inequality between elements and so can remove duplicates) and finite ordinals (there is a canonical list that thereby puts an ordering on the elements). Consequently, when giving (as Vaughan did) a categorical characterization of finiteness, it's worth pausing to consider which kind of finiteness you are characterizing. Some will be more fruitful than others in terms of how successfully they can generalize to the non-classical sets - with some you will be stuck in your concrete, with others you can explore further afield. The particular one Vaughan described was closely tied to the classical set theory, but that is a limitation that is not inherent in the broad questions he was asking. That's a bit more subtle than saying "finite sets" are now characterized, and treating "finite sheaves" as an interesting topic of further study along with "finite Abelian groups" and so on. There is virtue in finding answers for "finite sets" that also apply to "finite sheaves". > Mentioning categories on Steve Simpson's FOM mailing list typically brings > on a diatribe from someone railing against categories. It would be nice > if one could mention sets on this mailing list without the analogous response. Sorry if I railed. The categories list has the big advantage that its readership is very well informed about both sets and categories, and fully in a position to base their opinions on the mathematics and not the railing. All the best, Steve Vickers. From rrosebru@mta.ca Mon Nov 26 16:26:01 2001 -0400 >From cat-dist@mta.ca Mon Nov 26 16:26:01 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 26 Nov 2001 16:26:01 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 168SEl-0002Cm-00 for categories-list@mta.ca; Mon, 26 Nov 2001 16:20:19 -0400 From: baez@math.ucr.edu Message-Id: <200111252345.fAPNj1B08882@math-cl-n05.ucr.edu> Subject: categories: adjoint equivalence To: categories@mta.ca (categories) Date: Sun, 25 Nov 2001 15:45:00 -0800 (PST) X-Mailer: ELM [version 2.5 PL2] MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 122 Here's some stuff James Dolan and I talked about last Friday when discussing Paul Levy's question about the difference between an equivalence and an adjoint equivalence. Pardon the glitzy writing style: this is part of my column "This Week's Finds", where I can't count on people staying awake for category theory unless I spice it up a bit. You can find the whole column here: http://math.ucr.edu/home/baez/week173.html Best, jb ........................................................................... First, consider the "Platonic idea of an equivalence". By this, I mean the 2-category Equiv which is freely generated by objects a and b, morphisms L: a -> b and R: b -> a, and isomorphisms i: 1_b => RL and e: LR => 1_a. Why do I call this the "Platonic idea of an equivalence"? Well, any equivalence in any 2-category C is just the same as a 2-functor F: Equiv -> C The functor F turns the "abstract" equivalence in Equiv into a "concrete" equivalence in C! This is reminiscent of Plato's theory of ideas and how they get manifested in concrete situations. We can think of Equiv as the unadorned idea of an adjunction without any contamination by accidental extra features. I should add that James, less of an intellectual snob than I, calls Equiv the "walking equivalence". After all, if someone has really big bushy eyebrows, so that when you see him walking down the street you first notice his eyebrows and only later realize there's a person attached, you call him a "walking pair of eyebrows". The person is basically just the life support system for the eyebrows! Similarly, in Equiv we have a 2-category which is just the life support system for an adjunction: no more and no less. Anyway, the walking equivalence is a weak 2-groupoid: a 2-category where every 2-morphism is invertible and every morphism is invertible up to 2-isomorphism. Weak 2-groupoids are secretly the same thing as homotopy 2-types: roughly speaking, topological spaces whose homotopy groups vanish above dimension 2. And there's a pretty easy way to turn a weak 2-groupoid into a homotopy 2-type. First you turn it into a simplicial set, called its "nerve", and then you take the geometric realization of that. Eh? Well, I talked about geometric realization in part E of "week116", and I talked about the nerve of a 1-category in part J of "week117", so the only thing I need to do is say a bit about the nerve of a 2-category. This is a simplicial set where the 0-simplices correspond to objects: x the 1-simplices correspond to morphisms: x ------F-------> y the 2-simplices correspond to 2-morphisms: y / \ F: x -> y / \ G: y -> z / || \ H: x -> z F || G a: FG => H / ||a \ / \/ \ x------H----->z and the higher-dimensional simplices correspond to equations, "equations between equations", and so on. Anyway, if you use this trick to turn the walking equivalence into a space, what space do you get? The 2-sphere! It's pretty easy to see... I'd draw it for you on paper if I could, but you'll have to do it yourself. It helps if you have a globe: a is the North Pole, b is the South Pole, L: a -> b is the Greenwich Meridian running from north to south, R: b -> a is the International Date Line running from south to north, i: 1_a => LR is the Eastern Hemisphere, and e: RL => 1_b is the Western Hemisphere! (More precisely, we just get the 2-sphere up to homotopy equivalence: there is a whole bunch of higher-dimensional flab which I'm ignoring here. But that's okay, since we're doing homotopy theory.) We can also play this game for the "walking adjoint equivalence", AdEquiv. This is just like the walking equivalence, except we put in extra relations: the triangle equations. How does this affect the space we get? It's very beautiful: the extra equations fill in the 2-sphere to give us a 3-ball! Now, the 3-ball is contractible, so as a homotopy type it's really the same as a point. And a point is exactly the space we'd get from playing the same game starting with the "walking object": the 2-category with one object, its identity morphism, and the identity 2-morphism of that. To the eyes of a homotopy theorist, a point and 3-ball are the same, but the 2-sphere is not. Similarly, to the eyes of an n-category theorist, the walking object and the walking adjoint equivalence are "the same", but the walking equivalence is not! We could make this very precise with a suitable notion of "sameness" for 2-categories. But instead, let's jump straight to the punchline: having an adjoint equivalence in a 2-category is "the same" as having an object.... but having an equivalence is not! There's even more fun to be had here. Since every adjoint equivalence is an equivalence, there's a 2-functor I: Equiv -> AdEquiv But I also said every equivalence can be massaged to obtain an adjoint equivalence! In fact, I said it could be done in two equally good ways. Either of these gives a 2-functor P: AdEquiv -> Equiv Now, we can ask what these become when we turn them into maps between spaces.... It turns out that I is just the inclusion of the 2-sphere into the 3-ball, while P is the map that squashes the 3-ball down to either the eastern or western hemisphere of the sphere! By the way, it is irresistible to predict generalizations to higher dimensions. For any n, we will have weak n-groupoids called Equiv, the "walking n-equivalence", and AdEquiv, the "walking adjoint n-equivalence". The geometric realization of the nerve of Equiv will be homotopy equivalent to the n-sphere, while that of AdEquiv will be homotopy equivalent to the (n+1)-ball. (Note that for n = 1, Equiv will be the category with objects a and b and isomorphisms L: a -> b, R: b -> a. In AdEquiv, there will be extra relations saying that R is the inverse of L. In this sense, it is really an adjoint equivalence rather than an equivalence which is the proper generalization of an isomorphism!) From rrosebru@mta.ca Mon Nov 26 16:26:05 2001 -0400 >From cat-dist@mta.ca Mon Nov 26 16:26:05 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 26 Nov 2001 16:26:05 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 168SG5-0003la-00 for categories-list@mta.ca; Mon, 26 Nov 2001 16:21:44 -0400 Date: Sun, 25 Nov 2001 17:45:27 -0800 From: Toby Bartels To: categories Subject: categories: Re: Characterizing FinSet up to equivalence Message-ID: <20011125174527.B7300@math-cl-n03.ucr.edu> References: <200111222115.fAMLF4u16736@math-cl-n03.ucr.edu> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.2.5i In-Reply-To: <200111222115.fAMLF4u16736@math-cl-n03.ucr.edu>; from baez@math.ucr.edu on Thu, Nov 22, 2001 at 01:15:04PM -0800 Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 123 John Baez wrote in part: >Claim: FinSet is the free biCartesian category on nothing. What is the justification for including in the term "biCartesian" that the products distribute over the coproducts? If you add that the Cartesian product is closed (which it is in FinSet), *then* you get this, of course. So FinSet is either the free biCartesian category where products distribute over coproducts on nothing, or else the free Cartesian closed coCartesian category on nothing. It would be nice to have a single term like "biCartesian" for either of these concepts, but I don't see the justification, especially since the concept isn't very symmetric. -- Toby toby@math.ucr.edu From rrosebru@mta.ca Mon Nov 26 16:26:08 2001 -0400 >From cat-dist@mta.ca Mon Nov 26 16:26:08 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 26 Nov 2001 16:26:08 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 168SFK-0008BM-00 for categories-list@mta.ca; Mon, 26 Nov 2001 16:20:54 -0400 Date: Sun, 25 Nov 2001 17:39:01 -0800 From: Toby Bartels To: categories Subject: categories: Re: Characterizing FinSet up to equivalence Message-ID: <20011125173901.A7300@math-cl-n03.ucr.edu> References: <200111222115.fAMLF4u16736@math-cl-n03.ucr.edu> <200111241622.IAA30068@coraki.Stanford.EDU> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.2.5i In-Reply-To: <200111241622.IAA30068@coraki.Stanford.EDU>; from pratt@CS.Stanford.EDU on Sat, Nov 24, 2001 at 08:22:09AM -0800 Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 124 Vaughan Pratt wrote in part: >However I disagree that the assumption of finiteness constitutes smuggling >in FinSet. A tiny part of it, fine, but that's a long way from smuggling in >the whole notion of function. Indeed, so long as category theory begins with , then some set theory can't help but be smuggled in. If you say , then you're asking Mor(D) to be a finite set (where D is the diagram in a limit being considered), but you already have to ask Mor(D) to be a set, so this doesn't smuggle in any more set theory than was already there. -- Toby Bartels toby@math.ucr.edu From rrosebru@mta.ca Mon Nov 26 20:24:27 2001 -0400 >From cat-dist@mta.ca Mon Nov 26 20:24:27 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 26 Nov 2001 20:24:27 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 168W0J-0006NF-00 for categories-list@mta.ca; Mon, 26 Nov 2001 20:21:39 -0400 Message-ID: <3BFF90A1.2FC94B24@csc.liv.ac.uk> Date: Sat, 24 Nov 2001 12:20:49 +0000 From: Peter McBurney X-Mailer: Mozilla 4.77 [en] (X11; U; Linux 2.4.3-12 i686) X-Accept-Language: en MIME-Version: 1.0 To: CATEGORIES LIST Subject: categories: CFP: Visual Representations and Interprations VRI2002 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: quoted-printable X-MIME-Autoconverted: from 8bit to quoted-printable by ribble.server.csc.liv.ac.uk id MAA06242 Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 125 WITH APOLOGIES FOR MULTIPLE POSTINGS PRELIMINARY CALL FOR PAPERS 2nd International Conference on VISUAL REPRESENTATIONS AND INTERPRETATIONS Liverpool, UK, September 9 - 12, 2002 Contributions are invited for a multi-disciplinary workshop on Visual Representations and Interpretations. This will be a multi-disciplinary meeting exploring all aspects of visual images, their interpretation, representation and modeling, and their relationships to other forms of human knowledge and activities. SCOPE AND AIMS OF THE WORKSHOP The value of multi-disciplinary research, the exchanging of ideas and methods across traditional discipline boundaries, is well recognised.=20 It could be argued that many of the advances in science and engineering take place because the ideas, methods and the tools of thought from one discipline become re-applied in others. The topic of "the visual" has become increasingly important as advances in technology have led to multi-media and multi-modal representations, and extended the range and scope of visual representation and interpretation in our lives. Under this broad heading there are many different perspectives and approaches, from across the entire spectrum of human knowledge and activity. The development of advanced graphics for computer games and film animations, for example, has drawn on and led developments in computational geometry. Even outside the technological sphere, recent controversies over artworks which some have considered to be blasphemous show the power of the visual to manifest wildly different interpretations, and to become a topic of everyday conversation and a focus of political activity. One goal of this workshop on Visual Representations and Interpretations is to break down cross-disciplinary barriers, by bringing together people working in a wide variety of disciplines where visual representations and interpretations are exploited. The first Workshop on Visual Representations and Interpretations was held in Liverpool in 1998. Contributions to the workshop came from researchers actively investigating visual representations and interpretations in a wide variety of areas including: art, architecture, biology, chemistry, clinical medicine, cognitive science, computer science, education, engineering, graphic design, linguistics, mathematics, philosophy, physics, psychology and social science. VRI2002 aims to build on this good beginning, and to provide a forum for wide-ranging and multi-disciplinary discussion on visual representations and interpretations. Contributions on any aspect of visual representations and interpretations are welcomed, including, though of course not limited to: - visual representation languages - film and photographic interpretation - art as argument - diagrams and sketches - the philosophy, sociology and politics of art and images - formalization and representation of images - visual human-machine interaction - connections between visual and other human senses - computational geometry - diagrammatic reasoning - the modeling of patterns and form - blueprints and scale models - visual metaphors and knowledge discovery SUBMISSIONS Contributions in the form of original research papers are invited. Papers should be a maximum of 12 pages in length. There will be the opportunity to edit accepted papers after the Workshop for inclusion in the final published proceedings. Paper submissions should be sent to: Grant Malcolm (Conference Chair) Department of Computer Science University of Liverpool Chadwick Building Peach Street Liverpool L69 7ZF UK Papers can also be submitted by email, PROVIDED THEY ARE IN PDF OR POSTSCRIPT FORMAT,in which case they can be sent to: grant@csc.liv.ac.uk IMPORTANT DATES Submission of contributions: 1 April 2002 Notification of Acceptance: 15 May 2002 Submission deadline for pre-proceedings: 20 July 2002 VRI-2002 Conference: 9-12 September 2002 Submission deadline for Elsevier volume: 30 September 2002 The edited proceedings of the workshop will be published after the event by Elsevier Science in a volume entitled "Multidisciplinary Studies of Visual Representations and Interpretations" Submissions will be refereed by two or more members of the Program Committee: PROGRAMME COMMITTEE Caroline Baillie (Liverpool, UK) Michael Biggs (Hertfordshire, UK) Ernst Binz (Mannheim, Germany) Nicola Dioguardi (Milan, Italy) Andr=E9e Ehresmann (Amiens, France) Paul Fishwick (Gainesville, USA) Jean-Louis Giavitto (Evry, France) Peter Giblin (Liverpool, UK) Joseph Goguen (San Diego, USA) David Goodsell (La Jolla, USA) Leo Groarke (Waterloo, Canada) Rom Harr=E9 (Oxford, UK, and Washington, USA) Robin Hendry (Durham, UK) Mike Holcombe (Sheffield, UK) John Lee (Edinburgh, UK) Charles Lund (Newcastle, UK) Michael Leyton (New York, USA) Peter McBurney (Liverpool, UK) Grant Malcolm (Liverpool, UK) Mary Meyer (Los Alamos, USA) Arthur Miller (London, UK)=20 Irene Neilson (Liverpool, UK) Ray Paton (Liverpool, UK)=20 Walter Schempp (Seigen, Germany) Travel and accommodation details will be posted in due course on the conference web-page: http://www.csc.liv.ac.uk/~vri2/ Questions and inquiries should be directed to: Ray Paton Department of Computer Science University of Liverpool Email: R.C.Paton@csc.liv.ac.uk **************************************************************** =20 Peter McBurney =20 Agent Applications, Research and Technology (Agent ART) Group =20 Department of Computer Science =20 University of Liverpool =20 Liverpool L69 7ZF =20 U.K. =20 =20 Tel: + 44 151 794 6768 =20 Email: P.J.McBurney@csc.liv.ac.uk =20 Web page: www.csc.liv.ac.uk/~peter/ =20 = =20 **************************************************************** From rrosebru@mta.ca Mon Nov 26 20:24:31 2001 -0400 >From cat-dist@mta.ca Mon Nov 26 20:24:31 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 26 Nov 2001 20:24:31 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 168Vx7-0005jr-00 for categories-list@mta.ca; Mon, 26 Nov 2001 20:18:21 -0400 Date: Fri, 23 Nov 2001 11:10:53 +0100 (MET) From: Marc Bezem Reply-To: Marc Bezem Subject: categories: job: PhD positions in Informatics, Bergen University, Norway To: categories@mta.ca MIME-Version: 1.0 Content-Type: TEXT/plain; charset=us-ascii Content-MD5: A6hAg8KwriGBN+hEvgUTBw== X-Mailer: dtmail 1.3.0 @(#)CDE Version 1.4.2 SunOS 5.8 sun4u sparc Message-Id: Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 126 2 PhD positions Institute for Informatics University of Bergen, Norway 1. The project. --------------- MoSIS is a IKT project funded by the Norwegian Science Council (NFR) for the period 2002-2005. Its descriptive full title is: Modularity in large Software and Information Systems Modularization techniques are essential for mastering the complexity of large systems. There are many approaches: agents, components, libraries, ... The overall aim of the project is to develop a conceptual and formal framework for the composition and interaction of software modules at various levels of abstraction. The two relevant subprojects aim at applying formal techniques based on type theory, algebra and/or category theory to programming `in the large'. For more information on the project, see http://www.ii.uib.no/MoSIS 2. The profile of the candidates. --------------------------------- You have a Master degree (or equivalent) in Computer Science, Informatics, Mathematics or Logic. You enjoy working in an internationally oriented, English speaking research environment. 3. The jobs. ------------ The positions are opening up in 2002 and last for three years. There are in principle no teaching duties. There is a perspective for prolongation of at most one year as a research associate. The salary is about EUR 32.000 per year. 4. Information and how to apply. -------------------------------- More information can be obtained from Prof.Dr. M.A. Bezem (bezem@ii.uib.no). You are invited to send an application letter by e-mail, together with a curriculum vitae and the names and addresses of two references, before 21 December 2001. Applicants from outside the European Economic Area (EEA) will be considered. In a later stage of the procedure we may ask you to write a formal application to the faculty. 5. Bergen, Norway. ------------------ Bergen is the second-largest city in Norway, beautifully situated between 7 mountains (up to 600m) and fjords. Bergen has about 230.000 inhabitants and all facilities, including a nearby airport. The climate (including tax pressure) is milder than most people expect, but it can rain quite hard, indeed. For more information on - Bergen, see http://www.bergen-guide.com/ - Bergen University, see http://www.uib.no/ - Institute for Informatics, see http://www.ii.uib.no/ - Marc Bezem, see http://www.ii.uib.no/~bezem From rrosebru@mta.ca Mon Nov 26 20:24:34 2001 -0400 >From cat-dist@mta.ca Mon Nov 26 20:24:34 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 26 Nov 2001 20:24:34 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 168Vu9-0008C5-00 for categories-list@mta.ca; Mon, 26 Nov 2001 20:15:18 -0400 Date: Thu, 22 Nov 2001 19:17:35 +0000 (GMT) From: "Zhaohui.Luo" X-Sender: dcs0zl@altair.dur.ac.uk Reply-To: "Zhaohui.Luo" To: categories@mta.ca Subject: categories: PhD Studentship Message-ID: MIME-Version: 1.0 Content-ID: Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 127 EPSRC CASE PhD Studentship Department of Computer Science University of Durham, U.K. Applications are invited from students with good undergraduate or MSc degrees in computer science, mathematics or a related subject to study for a PhD degree. A U.K. EPSRC CASE Award (a research studentship with extra industrial funding for maintenance) is available for a suitably qualified candidate. It covers the tuition fees and the enhanced maintenance for three years. (For non-EU applicants, please note that the studentship does not cover the overseas fees, which are usually payable.) The successful candidate is expected to start as soon as possible and to work in the Computer-Assisted Reasoning Group (http://www.dur.ac.uk/CARG/), and in particular on the EPSRC-funded project `Epigram: Innovative Programming via Inductive Families' (http://www.dur.ac.uk/CARG/epigram.html). The project is about development of the theory and pragmatics of programming with dependent types. The collaborators are the ALTA Systems Ltd. and the Centre for Educational Measurement from the Queen's University of Belfast. Further enquiries and applications (with a CV and the names of at least two referees) can be sent to Prof. Zhaohui Luo, Dept. of Computer Science, Durham University, South Road, Durham DH1 3LE, U.K. Email: Zhaohui.Luo@durham.ac.uk Phone: +44 (0)191 374 3657 Fax: +44 (0)191 374 2560 URL: http://www.dur.ac.uk/~dcs0zl/ Application forms can be obtained either from the above address or the office of the Department of Computer Science (http://www.dur.ac.uk/~dcs0www/) of the Durham University. A web version of this advertisement can be found at http://www.dur.ac.uk/CARG/studentship.epigram.html From rrosebru@mta.ca Tue Nov 27 15:32:03 2001 -0400 >From cat-dist@mta.ca Tue Nov 27 15:32:03 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 27 Nov 2001 15:32:03 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 168nu0-0004oZ-00 for categories-list@mta.ca; Tue, 27 Nov 2001 15:28:20 -0400 To: categories@mta.ca From: Richard Blute Date: Mon, 26 Nov 2001 12:33:22 -0500 (EST) Subject: categories: CFP: CTCS'02 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: X-Keywords: X-UID: 128 CATEGORY THEORY AND COMPUTER SCIENCE (CTCS'02) AUGUST 15-17, 2002 University of Ottawa FIRST CALL FOR PAPERS CTCS '02 is the 9th Conference on Category Theory and Computer Science. The purpose of the conference series is the advancement of the foundations of computing using the tools of category theory. The emphasis is upon applications of category theory, but it is recognized that the area is highly interdisciplinary. Typical topics of interest include, but are not limited to, category-theoretic aspects of the following: coalgebras and computing concurrent and distributed systems constructive mathematics declarative programming and term rewriting domain theory and topology foundations of computer security linear logic modal and temporal logics models of computation program logics, data refinement, and specification programming language semantics type theory Previous meetings have been held in Guildford (Surrey), Edinburgh (twice), Manchester, Paris, Amsterdam, Cambridge, and S. Margherita Ligure (Genova). This is the first time CTCS will be held in North America. One new feature that CTCS will have this year is a "preconference", during which we will offer courses in the basic areas underlying the field of the conference. The goal is to prepare students to be able to attend and participate in CTCS. So anyone who has graduate students or advanced undergraduates who they think would be interested in attending should contact us. We anticipate having some funding from Centre de Recherches Mathematiques (CRM) to cover part of the costs. PROGRAMME COMMITTEE Rick Blute, Chair (Ottawa) Robin Cockett (Calgary) Thierry Coquand (Chalmers) Andrea Corradini (Pisa) Thomas Ehrhard (Luminy) Ryu Hasegawa (Tokyo) Martin Hofmann (Munich) Bart Jacobs (Nijmegen) Michael Johnson (Macquarie) Dusko Pavlovic (Kestrel Institute) Alex Simpson (Edinburgh) ORGANIZING COMMITTEE E. Moggi, Chair, (Genova) S. Abramsky (Oxford) P. Dybjer (Chalmers) B. Jay (Sydney) A. Pitts (Cambridge) LOCAL ORGANIZING COMMITTEE R. Blute (Ottawa) P. Scott (Ottawa) Further details on submission and the publication forum will be given in the second call for papers. IMPORTANT DATES March 25th, 2002 Submission deadline May 20th, 2002 Notification of authors of accepted papers From rrosebru@mta.ca Tue Nov 27 15:32:06 2001 -0400 >From cat-dist@mta.ca Tue Nov 27 15:32:06 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 27 Nov 2001 15:32:06 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 168nvr-0007YO-00 for categories-list@mta.ca; Tue, 27 Nov 2001 15:30:15 -0400 Message-ID: From: S.J.Vickers@open.ac.uk To: categories@mta.ca Subject: categories: preprint: A new paper on locales and powerlocales Date: Tue, 27 Nov 2001 14:33:28 -0000 MIME-Version: 1.0 X-Mailer: Internet Mail Service (5.5.2653.19) Content-Type: text/plain; charset="iso-8859-1" Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 129 I have just put a new paper of mine on the web at http://mcs.open.ac.uk/sjv22/PPandExp.ps Steve Vickers. Details: "The double powerlocale and exponentiation: A case study in geometric logic" Steven Vickers. If X is a locale, then its double powerlocale PP(X) is defined to be P_U(P_L(X)) where P_U and P_L are the upper and lower powerlocale constructions. We prove various results relating it to exponentiation of locales, including the following. First, if X is a locale for which the exponential $^X exists (where $ is the Sierpinski locale), then PP(X) is an exponential $^($^X). Second, if in addition W is a locale for which PP(W) is homeomorphic to $^X, then X is an exponential $^W. The work uses geometric reasoning, i.e. reasoning stable under pullback along geometric morphisms, and this enables the locales to be discussed in terms of their points as though they were spaces. It relies on a number of geometricity results including those for locale presentations and for powerlocales. From rrosebru@mta.ca Tue Nov 27 19:48:12 2001 -0400 >From cat-dist@mta.ca Tue Nov 27 19:48:12 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 27 Nov 2001 19:48:12 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 168rnV-0005jy-00 for categories-list@mta.ca; Tue, 27 Nov 2001 19:37:53 -0400 From: Steve Lack MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <15364.5271.920374.231050@milan.maths.usyd.edu.au> Date: Wed, 28 Nov 2001 09:32:55 +1100 To: categories@mta.ca Subject: categories: free-living/platonic/walking equivalences and adjunctions X-Mailer: VM 6.90 under 21.1 (patch 7) "Biscayne" XEmacs Lucid Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 130 John Baez described the ``platonic idea of an equivalence'' or ``walking equivalence''. (This has also been called the ``free-living equivalence''.) He also describes the free-living adjoint equivalence, and the homotopy-theoretic relationship between the two. Similarly, one can construct the free-living adjunction. This was done in S. Schanuel and R. Street, The free adjunction, Cah. Top. Geom. Diff. 27:81-83, 1986. John also points out that one can consider not just equivalences, but 2-equivalences, 3-equivalences, and so on. The free-living pseudo-adjunction was constructed in Stephen Lack, A coherent approach to pseudomonads, Adv. Math. 152:179-202, 2000. from a rather different point of view to that of Schanuel and Street. Steve Lack. From rrosebru@mta.ca Tue Nov 27 19:48:16 2001 -0400 >From cat-dist@mta.ca Tue Nov 27 19:48:16 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 27 Nov 2001 19:48:16 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 168rn8-0005TK-00 for categories-list@mta.ca; Tue, 27 Nov 2001 19:37:30 -0400 From: Steve Lack MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <15364.4308.871059.716559@milan.maths.usyd.edu.au> Date: Wed, 28 Nov 2001 09:16:52 +1100 To: categories@mta.ca Subject: categories: distributive(``bicartesian'' categories) X-Mailer: VM 6.90 under 21.1 (patch 7) "Biscayne" XEmacs Lucid Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 131 Toby Bartels writes: > John Baez wrote in part: > > >Claim: FinSet is the free biCartesian category on nothing. > > What is the justification for including in the term "biCartesian" > that the products distribute over the coproducts? > If you add that the Cartesian product is closed > (which it is in FinSet), *then* you get this, of course. > So FinSet is either the free biCartesian category > where products distribute over coproducts on nothing, > or else the free Cartesian closed coCartesian category on nothing. > It would be nice to have a single term like "biCartesian" > for either of these concepts, but I don't see the justification, > especially since the concept isn't very symmetric. > These categories are often called distributive. For an introduction to them, and their relationship with extensive categories, see the paper: Aurelio Carboni, Stephen Lack, and R.F.C. Walters, Introduction to extensive and distributive categories, J. Pure Appl. Alg. 84(1993), 145-158. Steve Lack. From rrosebru@mta.ca Thu Nov 29 14:54:42 2001 -0400 >From cat-dist@mta.ca Thu Nov 29 14:54:42 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 29 Nov 2001 14:54:42 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 169WHX-0005tS-00 for categories-list@mta.ca; Thu, 29 Nov 2001 14:51:46 -0400 From: baez@math.ucr.edu Message-Id: <200111291827.fATIR7I19410@math-cl-n03.ucr.edu> Subject: categories: the walking adjunction and biadjunction To: categories@mta.ca (categories) Date: Thu, 29 Nov 2001 10:27:07 -0800 (PST) X-Mailer: ELM [version 2.5 PL2] MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 132 Here's some more stuff some of you might like, taken from http://math.ucr.edu/home/baez/week174.html Again, pardon the tone - it's written for nonexperts. If any of you know literature on the "walking biadjunction", I'd be interested! Best, jb ....................................................................... Now I'm going to dive in and pick up right where I left off in my discussion of the ideas behind this paper: 2) Michael Mueger, From subfactors to categories and topology I: Frobenius algebras in and Morita equivalence of tensor categories, available at math.CT/0111204. My ultimate goal is to take you to an elegant understanding of Frobenius algebras by means of a 2-category called the "walking biadjunction", but first I'll play around a bit with a simpler but more famous 2-category called the "walking adjunction". This may sound scary, but if you can stick with it, you'll see that I'm really just using these 2-categories to describe fun games that you can play with certain 2-dimensional pictures. Even if you don't read the words, please stare at the pictures - I spend my Thanksgiving weekend drawing them, and I don't want that work to go to waste! Category theorists love to talk about adjoint functors, but 2-category theorists know that these are just a special example of an "adjunction". An adjunction is something that makes sense in any 2-category; if we take the 2-category to be Cat we get adjoint functors. There are lots of other nice examples that make this generalization worthwhile. For example, in "week83" I explained how a pair of dual vector spaces is also an example of an adjunction. To study adjunctions, it suffices to study the "walking adjunction". This is a little 2-category containing exactly the stuff any adjunction in any 2-category must have: not a jot more, not a tiddle less! It was first studied by Schanuel and Street: 3) Stephen Schanuel and Ross Street, The free adjunction, Cah. Top. Geom. Diff. 27 (1986), 81-83. In a bit more detail, the walking adjunction is the 2-category freely generated by two objects: a and b, two morphisms: L: a -> b and R: b -> a, and two 2-morphisms, called the "unit" and "counit": i: 1_a => LR and e: RL => 1_b satisfying two relations, called the "triangle equations". I wrote down these equations already last week, but let me do it again using "string diagrams", as explained in "week79" and "week92". In a 2-categorical string diagram, objects are denoted by 2d regions in the plane, morphisms are denoted by 1d edges, and 2-morphisms are denoted by 0d points. If the dimensions look sort of upside-down, you're right - that's exactly the point! Instead of explaining the whole theory, I'll just plunge in with the example at hand. The unit i looks like this: i / \ L R / \ a / b \ a while the counit e looks like this: b \ a / b R L \ / \ / e Note that as you cross a line labelled "L" from left to right, you go from region a to region b, which is our way of saying that L: a -> b. Similarly, as you cross a line labelled "R" from left to right, you go from region b to region a, since R: b -> a. In terms of string diagrams, the triangle equations just say that we can straighten out a zig-zag: | | i | | / \ L | a / \ | | / \ | | | R / = a L b | \ / | L \ / b | | e | | | or a zag-zig: | | | i | R / \ | | / \ a | | / \ | \ L | = b R a \ / | | b \ / R | e | | | | We can build any 2-morphism in the walking adjunction by vertically and horizontally composing units and counits, which corresponds to sticking together string diagrams in a vertical or horizontal way. Thus, a typical 2-morphism looks like this: \ \ a / \ a / / | \ R L R L / i | \ \ / \ / / / \ L \ \ / \ / / a / R | b \ e e / / \ | a L R \ \ / \ b / i \ \ / \ / / \ L e \ / L R \ \ / / b \ \ By the triangle equations, we could straighten out the zig-zag without changing the 2-morphism. As you may know, the word "anaranjado" means "orange" in Spanish - there was no word in English for "orange" before people in England started importing oranges from Spain. And this is a nice mnemonic, because if we take the above picture and paint the regions labelled "a" orange, and paint the regions labelled "b" black, the above picture has a roughly tiger-striped appearance. In fact, these tiger stripes tell you everything you need to know about the 2-morphism! For example, starting from just this: \ \ a / \ a / / | \ \ / \ / / _ | \ \ / \ / / / \ | \ \_/ \_/ / a / \ | b \ / / \ | a \ / \ \ / \ b / _ \ \_/ \ / / \ \ \ / / \ \ \ / / b \ \ you can figure out where everything else should go. By the way, note that orange stripes can disappear can appear as we go down the page, and they can split, but they can't appear or merge. Black stripes can appear or merge, but they can't disappear or split. As a result, there can never be any orange or black *spots*. We'll change these rules later, when we talk about the "walking biadjunction". Okay, so we've got this 2-category, the walking adjunction: let's call it Ad for short. It's pretty simple. How can we understand it better? Well, for any two objects a and b in a 2-category we get a "hom-category" hom(a,b), whose objects are the morphisms from a to b, and whose morphisms are the 2-morphisms between those. If we work out these hom-categories in Ad, we get some cool stuff. First let's look at the hom-category hom(a,a). In this category, the objects are 1_a, LR, LRLR, LRLRLR, .... and all the morphisms are built by sticking these two basic generators together vertically or horizontally: \ \ a / / \ \ / / L R L R \ \ / / a \ \ / / a \ e / \ / | b | | | L R | | | | and i / \ a | | a | b | | | L R | | | | In tiger language, we're talking about pictures of black stripes on an orange background. The two basic generators are the merging of two black stripes and the appearance of a black stripe. If you read "week89", you'll know another way to describe this! Our ability to stick together pictures vertically and horizontally makes hom(a,a) into a "monoidal category". LR is a "monoid object", with merging of two black stripes being "multiplication", and the appearance of a black stripe being the "multiplicative identity". Being a "monoid object" simply means that these operations satisfy the left unit law: / / | | / / | | / / | | /\ / / | | \ \ / / | | \ \ / / | | \ \ / / a | | \ \/ / |b| | / = | | a | | | | a | | | | |b| | | | | a | | | | | | | | | | | | | | and its mirror image, called the right unit law, together with the associative law: \ \ a / / / / \ \ \ \ a / / \ \ / / a / / \ \ a \ \ / / \ \/ / / / \ \ \ \/ / \ / / / \ \ \ / \ \ / / \ \ / / \ \_/ / \ \_/ / \ / \ / | | | | a | | a a | | a | | = | | |b| |b| | | | | | | | | | | | | | | | | There aren't any other laws, so hom(a,a) is the "free monoidal category on a monoid object", or if you prefer, the "walking monoid"! I touched upon the immense consequences of this fact for algebraic topology in "week117" and "week118". They mainly rely on another way of thinking about hom(a,a): it's the category of order-preserving maps between finite ordinals! For example, these black tiger stripes on an orange background: 0 1 2 3 -------------------------------------------------------- | \ \ a | | a / / | | | | \ \ | | / / _ | | | | \ \ | | / / / \ | | | | \ \_/ \_/ / a / \ | | | | \ / \ \ | | | | a \ / \ \ / / | | \ b / _ \ \_/ / | | \ / / \ \ / | | \ / / b \ \ b / a | | \ / / \ \ | | -------------------------------------------------------- 0 1 2 correspond to the order-preserving map f: {0,1,2,3} -> {0,1,2} with f(0) = 0, f(1) = 0, f(2) = 0, f(3) = 2. Just read the stripes down! A more geometrical way to say the same thing is to call hom(a,a) the category of "simplices", usually denoted Delta. Here the object |---n+1 of them---| LRLR..........LRLR corresponds to the n-simplex, and these morphisms: -i.LRLR--> --i.LR-> -LR.i.LR-> 1_a --i--> LR --LR.i-> LRLR -LRLR.i--> LRLRLR ... <-L.e.R- <-L.e.RLR- <-LRL.e.R- are the basic "face" and "degeneracy" maps between simplices, which you'll find in any book on algebraic topology. The n-simplex is a face of the (n+1)-simplex in n+1 ways, and there are n basic degenerate ways to map the (n+1)-simplex down to the n-simplex. These aren't *all* the morphisms; just enough to generate all the rest by composition - i.e., sticking together pictures vertically, but *not* horizontally. Perhaps I should explain the notation here a bit more. Readers of "week80" will know that I use a dot to denote horizontal composition of 2-morphisms. For example, when we have a couple of 2-morphisms like this: f f' ---->---- ---->---- / || \ / || \ S: f => g x || S y || T z T: f' => g' \ \/ / \ \/ / ---->---- ---->---- g g' we get a 2-morphism like this: ff' -------->------- / || \ x || S.T z S.T: ff' => gg' \ \/ / -------->------- gg' But sometimes we can also horizontally compose a morphism and a 2-morphism! We can do it whenever our morphism f looks like a little "whisker" f sticking out of the 2-morphism T: f' ---->---- f / || \ x----->-----y || T z T: f' => g' \ \/ / ---->---- g' and what we get is a 2-morphism f.S like this: ff' -------->------- / || \ x || f.T z f.T: ff' => fg' \ \/ / -------->------- fg' This process, called "whiskering", is not really a new operation. f.S is really just the horizontal composite of these 2-morphisms: f f' ---->---- ---->---- / || \ / || \ x ||1_f y || S z \ \/ / \ \/ / ---->---- ---->---- f g' Similarly we can define T.f in this sort of situation: f' ---->---- / || \ f T: f' => g' x || T y----->-----z T.f: f'f => g'f \ \/ / ---->---- g' Anyway, once you're an expert on this 2-categorical yoga, you can easily see that these morphisms in hom(a,a), which are really 2-morphisms in Ad: -i.LRLR--> --i.LR-> -LR.i.LR-> 1_a --i--> LR --LR.i-> LRLR -LRLR.i--> LRLRLR ... <-L.e.R- <-L.e.RLR- <-LRL.e.R- are obtained by taking our basic tiger stripe operations - the "merging of two black stripes", or L.e.R, and the "appearance of a black stripe", or i - and drawing some extra black stripes on both sides. That's what those LR's are for. After all, no tiger is complete without whiskers! Okay. Now, having understood hom(a,a) in all these ways, let's turn to hom(b,b). Luckily, this is very similar! Here the objects are 1_b, RL, RLRL, RLRLRL, .... and morphisms are pictures of *orange* stripes on a *black* background: \ a / \ a / / | \ / \ / / _ | \ / \ / / / \ | \_/ \_/ / a / \ | b / / \ | / \ \ / b / _ \ \_/ / / \ \ / / \ \ / / b \ \ These orange stripes can only split: | | | | R L | | | a | / \ / i \ b / / \ \ b / / \ \ R L R L / / \ \ / / b \ \ or disappear: | | b | a | b | | R L | | | | \ / e as we march down the page. This means is that hom(b,b) is Delta^{op}: the *opposite* of the category of simplices, the *opposite* of the category of finite ordinals, or the walking *comonoid* - which is just like a monoid, only upside down! Here is another picture of hom(b,b): --R.i.LRL-> --R.i.L-> --RLR.i.L-> 1_b <--e-- RL <--e.RL-- RLRL <--e.RLRL-- RLRLRL ... <--RL.e-- <--RL.e.RL- <--RLRL.e-- If you're a devoted reader of This Week's Finds, you'll know I secretly drew this category already in section N of "week118". There I was talking about specific adjoint functors instead of the walking adjunction, so as not to prematurely blow your mind. I was also writing horizontal composites backwards, for certain old-fashioned reasons. But the idea is exactly the same! The morphisms above give the usual "face and degeneracy maps" we always have in a simplicial set, since a simplicial set is a functor F: Delta^{op} -> Set. By the way, you may have noticed that to get from hom(a,a) to hom(b,b), we had to switch the colors orange and black AND read the pictures upside-down. The reason is that if we turn around all the 1-morphisms AND 2-morphisms in the walking adjunction, we get the walking adjunction again. Ponder that! We can summarize what we've learned so far using the "Platonic idea" jargon I introduced last week: The Platonic idea of a monoid and the Platonic idea of a comonoid are the hom-categories hom(a,a) and hom(b,b) sitting inside the Platonic idea of an adjunction! (By the way, to round this off we should really describe hom(a,b) and hom(b,a), too. I think hom(a,b) is the Platonic idea of "an object with a left action of a monoid and a right coaction of a comonoid, in a compatible way". If so, hom(b,a) would be the Platonic idea of "an object with a right action of a monoid and a left coaction of a comonoid, in a compatible way". By "compatible" I'm saying that we can act on one side and coact on the other side in either order, and get the same thing. Filling in the details requires concepts I'm not eager to discuss right now, so I leave this as an exercise for the highly energetic reader. The less energetic reader can just study the tiger-stripe descriptions of these categories.) Finally, here's Mueger's new twist on all these ideas! Better than an adjunction is a "biadjunction". This has some extra structure, which turns out to explain all sorts of fancy-sounding stuff people look at in the study of subfactors and TQFTs and the like.... But what's a "biadjunction"? A biadjunction is where you have a morphism L: a -> b in a 2-category that is both left and right adjoint to R: b -> a. More precisely, a "biadjunction" is a setup (a,b,L,R,i,e,j,f) where (a,b,L,R,i,e) and (b,a,R,L,j,f) are both adjunctions. In terms of string diagrams, our generating 2-morphisms look like this: i j / \ / \ L R R L / \ / \ a / b \ a b / a \ b b \ a / b a \ b / a R L L R \ / \ / \ / \ / e f and the triangle equations say all possible zig-zags can be straightened out. Now let's study the "walking biadjunction", BiAd. As before, 2-morphisms in BiAd can be described using pictures with orange and black stripes - but now *both* kinds of stripes can appear, disappear, merge or split as we march down the page: ------------------------------------------------------- | \ \ a | | a / / | | | \ \ | | / / | | | \ \__/ \__/ / a | | | \ _____ / _____ | | | \ / a \ / / \ | | | a / / ___ \ / / \ / | | / / / \ \ / / __ \_/ | | / / \ b / / / / / \ | | / b \ \_/ / / / / a \ b | | / \ / / / / \ | ------------------------------------------------------- This allows for quite arbitrary ways of cutting up a rectangle into regions of orange and black, with piecewise linear boundaries, subject to the condition that each vertical border has the same color all along it. The triangle equations and the rules for 2-categories say that we can warp such a picture around without changing the 2-morphism that it defines... I don't want to be too precise here, since it would be boring. Hopefully you get the idea: BiAd has a purely topological description! Now for the punchline: in BiAd, what is the category hom(a,a) like? As in Ad, the objects are 1_a, LR, LRLR, LRLRLR, ... but now the object LR is equipped not only with multiplication: \ \ a / / \ \ / / L R L R \ \ / / a \ \ / / a \ e / multiplication: \ / L.e.R: LRLR => LR | b | | | L R | | | | and multiplicative identity: i / \ a | | a multiplicative | b | identity: | | i: 1_a => LR L R | | | | but also a "comultiplication": | | | | L R | | | b | / \ / j \ comultiplication: a / / \ \ a L.j.R: LR => LRLR / / \ \ L R L R / / \ \ / / b \ \ and "comultiplicative coidentity": | | a | b | a | | comultiplicative L R coidentity: | | f: LR => 1_a | | \ / f which make it into a monoid object *and* a comonoid object. Even better, there are some extra relations between the multiplication and comultiplication, which make LR into a so-called "Frobenius object"! In short, hom(a,a) is the walking Frobenius object! So is hom(b,b), since there is no real asymmetry between the objects a and b in a biadjunction, as there was with an adjunction. I haven't thought much about hom(a,b) and hom(b,a) yet, but one obvious thing is that they're isomorphic. Next time I'll talk about examples of Frobenius objects and why they are so important in subfactors, TQFTs and the like. This is what Mueger is really interested in. Right now, I want to wrap up by saying exactly what it means to say LR is a "Frobenius object". What are the extra relations between multiplication and comultiplication? There are various ways of describing these relations. Mueger uses a pair of equations that are popular in the TQFT literature: \ \ / / | | | | \ \ / / | | | | \ \_/ / | | | | \ / | \ a | | | | | \ | | a | | a a | |\ \ | | a | | | | \ \ | | |b| | | \ \ | | | | = | | \ \ | | | | | | \ \ | | | | | | a \ \| | | | | | \ | / _ \ | | \ b| / / \ \ | | | | / / \ \ | | | | / / \ \ | | | | and its mirror image. People sometimes call these the "I = N" equations, for the obvious reason. So: one definition of a "Frobenius object" in a monoidal category is that it's a monoid object / comonoid object satisfying the I = N equations. Where can you read about this? Well, besides Mueger's paper, there are these: 4) Frank Quinn, Lectures on axiomatic quantum field theory, in Geometry and Quantum Field Theory, Amer. Math. Soc., Providence, RI, 1995. 5) Lowell Abrams, Two-dimensional topological quantum field theories and Frobenius algebras, J. Knot Theory and its Ramifications 5 (1996), 569-587. The I = N equations are cute, but personally I prefer a more conceptual description of a Frobenius object. This may be a bit mindblowing to the uninitiated, so if you're just barely hanging on, please stop now. Hmm! If you're still reading this, you must be brave! Okay - don't say I didn't warn you. Let's start by pondering LR a bit more. This guy is its own adjoint, with the unit and counit as follows: _ a / \ | | | | unit for LR = | b | multiplicative identity composed with / _ \ comultiplication / / \ \ / / \ \ / / a \ \ \ \ a / / \ \ / / \ \_/ / counit for LR = \ / multiplication composed with a | b | comultiplicative coidentity | | | | \_/ It's easy to check the triangle equations by straightening out the relevant zig-zags. Now, whenever a monoid object has a right or left adjoint, that right or left adjoint automatically becomes a comonoid object, by the magic of duality. But if a monoid object is its *own* adjoint, it becomes a comonoid object in *two* ways, because it is both its own left *and* right adjoint! So, our guy LR is a comonoid object in *three* ways! Huh? Well, we already knew LR was a comonoid object before this devilish paragraph began, but since LR is its own adjoint, it becomes a comonoid object in two other ways. Amazingly, the I = N equations are equivalent to the fact that all three comonoid structures agree! I leave this as an exercise for the insanely energetic reader... I've worked it out before, and I rechecked it this morning in bed. I don't know if a proof exists in the literature, but from what Mueger writes, I suspect maybe you can catch glimpses of it in Appendix A3 of this book: 6) L. Kadison, New Examples of Frobenius Extensions, University Lecture Series #14, Amer. Math. Soc., Providence RI, 1999. Anyway, the upshot is that we can equivalently define a Frobenius object in a monoidal category as follows: it's a monoid object / comonoid object which becomes its own adjoint by letting unit = multiplicative identity composed with comultiplication counit = multiplication composed with comultiplicative coidentity and has the property that the resulting 3 comonoid structures agree. Or, equivalently, that the resulting 3 monoid structures agree! There is much more to say about this, but let's stop here. From rrosebru@mta.ca Thu Nov 29 14:03:35 2001 -0400 >From cat-dist@mta.ca Thu Nov 29 14:03:35 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 29 Nov 2001 14:03:35 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 169VKu-0002bw-00 for categories-list@mta.ca; Thu, 29 Nov 2001 13:51:00 -0400 From: baez@math.ucr.edu Message-Id: <200111280020.fAS0KBg01302@math-cl-n05.ucr.edu> Subject: categories: free-living/platonic/walking equivalences and adjunctions To: categories@mta.ca (categories) Date: Tue, 27 Nov 2001 16:20:11 -0800 (PST) X-Mailer: ELM [version 2.5 PL2] MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 133 Steve Lack writes: > John Baez described the ``platonic idea of an equivalence'' or > ``walking equivalence''. (This has also been called the ``free-living > equivalence''.) He also describes the free-living adjoint equivalence, > and the homotopy-theoretic relationship between the two. > > Similarly, one can construct the free-living adjunction. This was > done in > > S. Schanuel and R. Street, The free adjunction, Cah. Top. Geom. > Diff. 27:81-83, 1986. Thanks! In the next issue of This Week's Finds I'm giving a long introduction to the "walking adjunction", followed by a translation of Michael Mueger's paper >From subfactors to categories and topology I: Frobenius algebras in and Morita equivalence of tensor categories, available at math.CT/0111204 into facts about the "walking biadjunction". I knew someone had studied the walking adjunction but didn't know the reference, and had been meaning to ask here. > The free-living pseudo-adjunction was constructed in > > Stephen Lack, A coherent approach to pseudomonads, Adv. Math. > 152:179-202, 2000. Right! Thanks for reminding me! I'll mention that too. Also: has anyone here written about the "walking biadjunction"? It's actually very interesting. Best, jb From rrosebru@mta.ca Thu Nov 29 14:03:39 2001 -0400 >From cat-dist@mta.ca Thu Nov 29 14:03:39 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 29 Nov 2001 14:03:39 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 169VU7-0000k5-00 for categories-list@mta.ca; Thu, 29 Nov 2001 14:00:31 -0400 From: Boerger Organization: FernUniversitaet To: categories@mta.ca Date: Thu, 29 Nov 2001 11:26:37 +0100 MIME-Version: 1.0 Content-type: text/plain; charset=US-ASCII Content-transfer-encoding: 7BIT Subject: categories: Re: Characterizing FinSet up to equivale X-mailer: Pegasus Mail for Win32 (v2.54DE) Message-Id: Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 134 Hello, the simplest characterization of FinSet known to me is as the free category with initial object and binary coproducts on one object. In the usual world existence of these types of coproducts is equivalent to finite coproducts, but restriction to nullary and binary ones avoids the need for an a priori notion of finiteness. Somehow this reminds me of Kuratowski's definition of finiteness. Greetings Reinhard From rrosebru@mta.ca Thu Nov 29 14:03:42 2001 -0400 >From cat-dist@mta.ca Thu Nov 29 14:03:42 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 29 Nov 2001 14:03:42 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 169VUK-0002le-00 for categories-list@mta.ca; Thu, 29 Nov 2001 14:00:44 -0400 Date: Thu, 29 Nov 2001 11:34:51 +0100 (MET) From: Jiri Adamek X-Sender: adamek@lisa To: categories@mta.ca Subject: categories: address of T. Plewe Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: A X-Keywords: X-UID: 135 Can anyone provide me with the current e-mail address of T. Plewe? This is urgent becuse of outsanding page proofs of a paper of his, thanks for your help, J. Adamek xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx alternative e-mail address (in case reply key does not work): J.Adamek@tu-bs.de xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx From rrosebru@mta.ca Thu Nov 29 14:04:01 2001 -0400 >From cat-dist@mta.ca Thu Nov 29 14:04:01 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 29 Nov 2001 14:04:01 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 169VVF-0000U9-00 for categories-list@mta.ca; Thu, 29 Nov 2001 14:01:41 -0400 Date: Thu, 29 Nov 2001 11:58:42 +0100 (MET) From: Jiri Adamek X-Sender: adamek@lisa To: categories net Subject: categories: Re: alg-coalg duality Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 136 Al Vilcius asked: >If F:C-->C is a functor with opposite F*:C*-->C>* >then (F-algebras)* is trivially equivalent to (F*)-coalgebras. >Can this duality be induced by a schizophrenic object? The answer is, in general, negative: every duality, where C has a terminal object, is of the above type, just take the constant functor of value 1. J. Adamek From rrosebru@mta.ca Fri Nov 30 10:03:26 2001 -0400 >From cat-dist@mta.ca Fri Nov 30 10:03:26 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 30 Nov 2001 10:03:26 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 169oAj-000369-00 for categories-list@mta.ca; Fri, 30 Nov 2001 09:57:45 -0400 Message-Id: <3.0.5.32.20011129214334.008394b0@TESLA.open.ac.uk> X-Sender: sjv22@TESLA.open.ac.uk X-Mailer: QUALCOMM Windows Eudora Light Version 3.0.5 (32) Date: Thu, 29 Nov 2001 21:43:34 +0000 To: categories@mta.ca From: S Vickers Subject: categories: Re: Characterizing FinSet up to equivale In-Reply-To: Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 137 At 11:26 29/11/01 +0100, you wrote: >Hello, > >the simplest characterization of FinSet known to me is as the free >category with initial object and binary coproducts on one object. In >the usual world existence of these types of coproducts is equivalent >to finite coproducts, but restriction to nullary and binary ones >avoids the need for an a priori notion of finiteness. Somehow this >reminds me of Kuratowski's definition of finiteness. > > > Greetings > Reinhard No, I don't think you get the Kuratowski finite sets that way. A set X is Kuratowski finite iff it is in the subsemilattice (under nullary and binary union) of PX generated by the singletons. The definition proposed looks as though it characterizes finite ordinals, which are Kuratowski finite with a decidable total ordering. The two are different. "Kuratowski finite" includes sets where you can give a finite enumeration (indexed by a finite ordinal) of the elements but can't guarantee to eliminate duplicates from the enumeration. The category of Kuratowski finite sets is equivalent to the ind completion of the category of finite ordinals with surjections as the morphisms. Steve Vickers. From rrosebru@mta.ca Fri Nov 30 10:03:29 2001 -0400 >From cat-dist@mta.ca Fri Nov 30 10:03:29 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 30 Nov 2001 10:03:29 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 169oAz-0000XY-00 for categories-list@mta.ca; Fri, 30 Nov 2001 09:58:01 -0400 Message-Id: <200111292151.NAA19929@coraki.Stanford.EDU> To: categories@mta.ca Subject: categories: Re: Characterizing FinSet up to equivalence (fwd) Date: Thu, 29 Nov 2001 13:51:20 -0800 From: Vaughan Pratt Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 138 >From: Boerger >the simplest characterization of FinSet known to me is as the free >category with initial object and binary coproducts on one object. Intuitively initiality seems like a bigger hammer than finiteness. This is confirmed by the observation that, although both initiality and finiteness properly extend first order logic as a specification methodology, initiality *guarantees* uniqueness up to whatever. With the assumption only of finiteness of objects, uniqueness is not so easily obtained (cf linear orders without endpoints, an alpha-null-categorical theory). It's like driving to work vs. riding a bicycle. Driving is faster and more convenient, the bicycle shifts more of the responsibility to the rider. >In the usual world existence of these types of coproducts is equivalent >to finite coproducts, but restriction to nullary and binary ones avoids >the need for an a priori notion of finiteness. A nice point and I did consider writing "with binary sums and an initial object" in place of "with finite sums" at the time. Given the brevity of the latter it might be preferable to consider it defined as the former by default, indicating any exceptions explicitly. >Somehow this reminds me of Kuratowski's definition of finiteness. I thought Kuratowski's idea was that when a shepherd verifies that he has only finitely many sheep by completing the process of branding them all, it is not necessary when branding a given sheep to first check whether it has already been branded. All that matters (to both the shepherd and the sheep) is that the branding eventually stop. Here's a definition for traditionalist physicists etc. who believe that God created the continuum while the natural numbers are the work of mankind. ** A set of points is finite just when its members can be positioned with equal ** nonzero spacing in a straight line across an A4 sheet of paper. This is the appropriate converse to the Archimedean axiom, violated only for those physicists who view the continuum as including infinitesimals. Pace Joe Shipman, any physicist demonstrating this deserves a Nobel prize. Somehow this reminds me of how many angels can fit on the head of a pin. Vaughan From rrosebru@mta.ca Fri Nov 30 10:06:46 2001 -0400 >From cat-dist@mta.ca Fri Nov 30 10:06:46 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 30 Nov 2001 10:06:46 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 169oIT-0002NF-00 for categories-list@mta.ca; Fri, 30 Nov 2001 10:05:45 -0400 Date: Thu, 29 Nov 2001 18:03:12 -0500 (EST) From: Oswald Wyler To: categories Subject: categories: Re: the walking adjunction and biadjunction In-Reply-To: <200111291827.fATIR7I19410@math-cl-n03.ucr.edu> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 139 The walking adjunction is much older than the 1986 paper by Schanuel and Street. Back in 1970, Pumpl\"un published a paper: Eine Bemerkung \"uber Monaden und adjungierte Funktoren, Math. Annalen 185 (1970), 329-377. The small bicategory "walking adjunction" definitely was in that paper, but I don't recall whether it was explicitly formulated or not. From rrosebru@mta.ca Fri Nov 30 10:08:22 2001 -0400 >From cat-dist@mta.ca Fri Nov 30 10:08:22 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 30 Nov 2001 10:08:22 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 169oJL-00028q-00 for categories-list@mta.ca; Fri, 30 Nov 2001 10:06:39 -0400 Date: Thu, 29 Nov 2001 15:55:45 -0800 (PST) From: jdolan@math.ucr.edu Message-Id: <200111292355.fATNtjQ29951@math-cl-n01.ucr.edu> To: categories@mta.ca Subject: categories: Re: the walking adjunction and biadjunction Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 140 are you sure everyone will be happy with the name "biadjunction" for the thing that you're talking about? i'm just vaguely wondering whether it might unintentionally evoke ideas about "bicategories". "walking ____" on the other hand is of course entirely transparent and aptly descriptive. From rrosebru@mta.ca Fri Nov 30 10:10:51 2001 -0400 >From cat-dist@mta.ca Fri Nov 30 10:10:51 2001 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 30 Nov 2001 10:10:51 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 3.33 #2) id 169oLV-0001fE-00 for categories-list@mta.ca; Fri, 30 Nov 2001 10:08:53 -0400 Message-ID: <3C07726B.76CA6143@cs.auc.dk> Date: Fri, 30 Nov 2001 12:50:03 +0100 From: Zoltan Esik X-Mailer: Mozilla 4.78 [en] (X11; U; SunOS 5.8 sun4u) X-Accept-Language: en MIME-Version: 1.0 To: categories@mta.ca Subject: categories: CFP: FICS 02, a satellite workshop to LICS 02 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: X-Keywords: X-UID: 141 ============================================================= FICS'2002 Fixed Points in Computer Science A Satellite Workshop to LICS'2002 July 20--21, 2002, Copenhagen, Denmark http://floc02.diku.dk/FICS/ PRELIMINARY CALL FOR PAPERS Aim: Fixed points play a fundamental role in several areas of computer science and logic by justifying induction and recursive definitions. The construction and properties of fixed points have been investigated in many different frameworks. The aim of the workshop is to provide a forum for researchers to present their results to those members of the computer science and logic communities who study or apply the fixed point operation in the different fields and formalisms. Previous workshops were held in 1998 in Brno, in 2000 in Paris, and in 2001 in Florence. Topics include, but are not restricted to: Construction and reasoning about properties of fixed points, categorical, metric and ordered fixed point models, continuous algebras, relation algebras, fixed points in process algebras and process calculi, regular algebras of finitary and infinitary languages, formal power series, tree automata and tree languages, infinite trees, the mu-calculus and other programming logics, fixed points in relation to dataflow and circuits, fixed points and the lambda calculus, fixed points in logic programming and data bases. Paper submission: Authors are invited to send three copies of an abstract not exceeding three pages to the PC cochair Anna Ingolfsdottir. Electronic submissions in the form of uuencoded postscript files are encouraged and can be sent to annai@cs.auc.dk. Submissions are to be received before April 15, 2002. Authors will be notified of acceptance by May 31, 2002. Proceedings: Preliminary proceedings containing the abstracts of the talks will be available at the meeting. Final proceedings will be published after the meeting as a special issue of the journal Theoretical Informatics and Application} (http://www.edpsciences.org/docinfos/ITA/). Invited speakers: L. Aceto (Aalborg), D. Kozen (Cornell), A. Labella (Rome), G. Winskel (Cambridge, provisional). Program Committee: J. Adamek (Braunschweig), R. Backhouse (Nottingham), S. Bloom (Hoboken NJ), J. Bradfield (Edinburgh), R. De Nicola (Florence), Z. Esik (cochair, Szeged), I. Guessarian (Paris), A. Ingolfsdottir (cochair, Aalborg), W. Kuich (Vienna), A. Labella (Rome), M. Mislove (Tulane), D. Niwinski (Warsaw). The meeting will be organised in affiliation to LICS'02: http://www.dcs.ed.ac.uk/home/grohe/lics/lics02/ FICS'02 is partially supported by BRICS (Basic Research in Computer Science): http://www.brics.dk/ and the Computer Science Department of Aalborg University: http://cs.auc.dk/. More information} is available at the web site http://floc02.diku.dk/FICS/