From rrosebru@mta.ca Tue Aug 1 21:48:45 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 01 Aug 2006 21:48:45 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1G84lB-0003AD-4v for categories-list@mta.ca; Tue, 01 Aug 2006 21:38:53 -0300 Date: Tue, 1 Aug 2006 09:18:32 -0400 (EDT) From: Richard Blute To: categories@mta.ca Subject: categories: Octoberfest-Preliminary Announcement MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: RO X-Status: X-Keywords: X-UID: 1 Preliminary Announcement-Octoberfest 2006 +++++++++++++++++++++++++++++++++++++++++ The Category Theory Octoberfest has been a great tradition among category theorists for several decades now. For the second consecutive year, it will be held at the University of Ottawa. It will be hosted by the Logic and Foundations of Computing group (LFC). See our website at www.site.uottawa.ca/~phil/lfc/. The conference will be held on the weekend of October 21st and 22nd. A webpage for the conference will be available shortly. We will be asking for submissions for talks in early September. But we wanted to give people information on lodging now, as Ottawa can be busy that time of year. We have booked a block of rooms at: Quality Hotel Downtown Ottawa 290 Rideau Street Ottawa, ON K1N 5Y3 (P) 613-789-7511 These rooms are held for Friday and Saturday nights. The group number is 105626 and the group name is "Ottawa U-Math Dept". The rate is $99.00 plus tax. Guests may phone the hotel directly at 613-789-7511 to reserve and may quote either the group name or number to get the preferred rate. The cutoff for this special rate is September 20th, but we strongly advise you not to wait that long. Here is a list of B&B's near Ottawa U, in random order: Home Sweetland Home B&B: 62 Sweetland Avenue, Ottawa, ON K1N 7T6 Phone: (613) 234-1871 Reservations: 1-877-299-3499 (web: http://www.homesweetlandhome.ca) Benners B&B 541 Besserer 613-789-8320 (web: http://www.bennersbedandbreakfast.com) Gasthaus Switzerland Inn 89 Daly Avenue Ottawa ON K1N6E6 613-237-0335 (www.gasthausswitzerlandinn.com) Ottawa Centre Bed and Breakfast 62 Stewart Street Ottawa, Ontario K1N 6J1 Phone: 613-237-9494 Toll Free: 866-240-4659 (web: http://www.ottawacenterbnb.com) Hope to see you all then: Rick Blute Phil Scott -- From rrosebru@mta.ca Wed Aug 2 13:21:07 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 02 Aug 2006 13:21:07 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1G8JPC-0003P4-QF for categories-list@mta.ca; Wed, 02 Aug 2006 13:17:10 -0300 From: J=FCrgen Koslowski Subject: categories: PSSL84, first announcement To: categories@mta.ca (categories list) Date: Wed, 2 Aug 2006 14:32:06 +0200 (CEST) MIME-Version: 1.0 Content-Type: text/plain; charset=3Diso-8859-1 Content-Transfer-Encoding: quoted-printable Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: RO X-Status: X-Keywords: X-UID: 2 PERIPATETIC SEMINAR ON SHEAVES AND LOGIC 84th meeting - first announcement Dear Colleagues, The 84th meeting of the seminar will be held at the Department of Theoretical Computer Science of the Technical University Braunschweig, Germany, over the weekend of October 14-15, 2006. As always, he seminar welcomes talks using or addressing category theory or logic, either explicitly or implicitly, in the study of any aspect of mathematics or science. Following the positive experience at PSSL83 in Glasgow earlier this year, Samson Abramsky and Bob Coecke have agreed to jointly give a three talk overview of recent developments in the categorical approach to quantum informatics. We hope that professor Reinhard Werner, mathematical physicist at the TU Braunschweig with special interest in quantum informatics, can be present as well. Braunschweig is located about 60 km East of Hannover and about 200 km West of Berlin. It can easily be reached by car or train. The closest airport is in Hannover; the airport bus to the Hannover train station takes about 20 minutes, and the train from there to Braunschweig takes about 40 minutes or less. Further information on the location of the seminar, along with details on local travel and accommodation together with an online registration form can be found at =09http://www.iti.cs.tu-bs.de/TI-INFO/koslowj/PSSL84.html Best regards, Jiri Adamek J=3DFCrgen Koslowski Stefan Milius --=3D20 Juergen Koslowski If I don't see you no more on this world ITI, TU Braunschweig I'll meet you on the next one koslowj@iti.cs.tu-bs.de and don't be late! http://www.iti.cs.tu-bs.de/~koslowj Jimi Hendrix (Voodoo Child, SR) From rrosebru@mta.ca Thu Aug 3 21:12:08 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 03 Aug 2006 21:12:08 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1G8nAN-00049T-OW for categories-list@mta.ca; Thu, 03 Aug 2006 21:03:51 -0300 From: J=FCrgen Koslowski Subject: categories: CT2006 pictures online! To: categories@mta.ca (categories list) Date: Thu, 3 Aug 106 21:03:01 +0200 (MEST) MIME-Version: 1.0 Content-Type: text/plain; charset=3DUS-ASCII Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: RO X-Status: X-Keywords: X-UID: 3 Dear Colleagues, The pictures I took at CT2006 in White Point now are online. The numbers keep growing at each conference... ;-) http://www.iti.cs.tu-bs.de/~koslowj/cgi-bin/pC333?CT06-0/idx&256 http://www.iti.cs.tu-bs.de/~koslowj/PHOTOS/CT06/ (group picture) As usual, if someone doesn't like her or his picture, I'll take it off. Also, if someone needs a larger file for a print or other purpose, just just let me know. I'll be happy to send you larger files. If you want to copy pictures off the web-page, be sure to add the extension ".jpg" manually! There are some people I have not been able to identify; any help is appreciated. Also, I don't know the first names of various significant others that appear on pictures shot during the dinner, nor do I know the exact status of the relationship. Using first and last names might get around that issue... Also, I apologize in case I have misspellt someone's name. Best regards, -- Juergen --=20 Juergen Koslowski If I don't see you no more on this world ITI, TU Braunschweig I'll meet you on the next one koslowj@iti.cs.tu-bs.de and don't be late! http://www.iti.cs.tu-bs.de/~koslowj Jimi Hendrix (Voodoo Child, SR) From rrosebru@mta.ca Mon Aug 7 21:41:21 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 07 Aug 2006 21:41:21 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GAFal-0003tp-Rb for categories-list@mta.ca; Mon, 07 Aug 2006 21:37:07 -0300 Date: Mon, 7 Aug 2006 14:36:32 +0100 (BST) Subject: categories: Laws From: "Tom Leinster" To: categories@mta.ca MIME-Version: 1.0 Content-Type: text/plain;charset=iso-8859-15 Content-Transfer-Encoding: 8bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 4 Dear category theorists, Here's something that I don't understand. People sometimes talk about algebraic structures "satisfying laws". E.g. let's take groups. Being abelian is a law; it says that the equation xy = yx holds. A group G "satisfies no laws" if whenever X is a set and w, w' are distinct elements of the free group F(X) on X, there exists a homomorphism f: F(X) ---> G such that f(w) and f(w') are distinct. For example, an abelian group cannot satisfy no laws, since you could take X = {x, y}, w = xy, and w' = yx. There are various interesting examples of groups that satisfy no laws. To be rather concrete about it, you could define a "law satisfied by G" to be a triple (X, w, w') consisting of a set X and elements w, w' of F(X), such that every homomorphism F(X) ---> G sends w and w' to the same thing. A law is "trivial" if w = w'. Then "satisfies no laws" means "satisfies only trivial laws". You could then say: given a group G, consider the groups that satisfy all the laws satisfied by G. (E.g. if G is abelian then all such groups will be abelian.) This is going to be a new algebraic theory. What bothers me is that I feel there must be some categorical story I'm missing here. Everything above is very concrete; for instance, it's heavily set-based. What's known about all this? In particular, what's known about the process described in the previous paragraph, whereby any theory T and T-algebra G give rise to a new theory? Thanks, Tom From rrosebru@mta.ca Mon Aug 7 21:41:21 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 07 Aug 2006 21:41:21 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GAFYW-0003lr-Hf for categories-list@mta.ca; Mon, 07 Aug 2006 21:34:48 -0300 Content-Transfer-Encoding: 7bit From: "IFIP WG2.2 2006" Subject: categories: IFIP WG2.2 anniversary meeting: Last Call for Participation Date: Mon, 7 Aug 2006 15:20:23 +0200 To: ifip06@dimi.uniud.it Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 5 *********************************************** Note: the meeting is rather exceptional, both for the quality of the speakers and the form of the talks (mostly reflections on history and development of concepts) *********************************************** LAST CALL FOR PARTICIPATION FORMAL DESCRIPTION OF PROGRAMMING CONCEPTS: IFIP WG 2.2 Anniversary Meeting 11-13 September 2006 Udine, Italy http://www.dimi.uniud.it/ifip06/ Registration ~~~~~~~~~~~~ Registration page: http://www.dimi.uniud.it/ifip06/ registration.html Registration deadline: 31 August 2006. The meeting fee is 150 Euros. The workshop fee includes lunches, coffee-breaks, the social dinner and the excursion on Sunday afternoon. About the WG 2.2 ~~~~~~~~~~~~ The IFIP Working Group 2.2 was established in 1965 as one of the first IFIP Working Groups. The primary aim of the WG is to explain programming concepts through the development, examination and comparison of various formal models of these concepts. The WG thus explores the theory and the practice of formal methods for the specification, verification and the design of software and systems. Earliest members of the WG included Dana Scott, Erwin Engeler, Jaco de Bakker, Raymond Abrial, Peter Lauer, Manfred Paul, Erich Neuhold, Maurice Nivat, Ed Blum. Throughout the years, members of the WG shaped various styles of semantics, comprising denotational, operational, algebraic, and logical semantics. About the meeting ~~~~~~~~~~~~ The anniversary meeting commemorates the 40-th birthday of WG. In the meeting, a number of keynote speakers and current members of the WG will give tutorial presentations on topics relevant to the WG, focusing on history (of these topics, or of the WG), but also on current outlook and future developments. Keynote speakers: Amir Pnueli, Igor Walukiewicz, and Ernst-Rudiger Olderog (as current WG members), Dana Scott, Manfred Paul, and Hans Langmaack (as founding WG members), Leslie Lamport and Gordon Plotkin (as past WG members) . Programme and Speakers ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Sunday 10 September, afternoon Excursion: San Daniele countryside (and ham) Monday 11 September * 09.00-10.00: Amir Pnueli * 10.00-10.30: coffee break * 10.30-11.30: Hans Langmaack * 11.30-12.00: Maciej Koutny * 12.00-14.00: lunch * 14.00-15.00: Igor Walukiewicz * 15.00-15.30: coffee break * 15.30-16.30: Ugo Montanari * 16.30-17.00: Catuscia Palamidessi * 17.00-17.30: Andrzej Tarlecki * 17.30-18.00: Rocco De Nicola Tuesday 12 September * 09.00-10.00: Gordon Plotkin * 10.00-10.30: coffee break * 10.30-11.30: local speaker * 11.30-12.00: Mariangiola Dezani * 12.00-14.00: lunch * 14.00-15.00: Dana Scott * 15.00-15.30: coffee break * 15.30-16.30: Egon Boerger * 16.30-17.00: Markus Muller-Olm * 20.00- : Social Dinner Wednesday 13 September * 09.00-10.00: Leslie Lamport * 10.00-10.30: coffee break * 10.30-11.00: Manfred Paul * 11.00-11.30: J Strother Moore * 11.30-12.00: Peter Mosses * 12.00-14.00: lunch * 14.00-15.00: Ernst-Rudiger Olderog * 15.00-15.30: coffee break * 15.30-16.30: Shigeru Igarashi * 16.30-17.00: Stephan Merz * 17.00-17.30: Anders P. Ravn * 17.30-18.00: Philippe Darondeau *********************************************** From rrosebru@mta.ca Tue Aug 8 08:51:11 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 08 Aug 2006 08:51:11 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GAQ5C-0007Zz-2Z for categories-list@mta.ca; Tue, 08 Aug 2006 08:49:14 -0300 From: "George Janelidze" To: Subject: categories: Re: Laws Date: Tue, 8 Aug 2006 13:28:12 +0200 Content-Type: text/plain; charset="iso-8859-15" Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 6 Dear Tom, "Any theory"?... If it is about Lawvere theories, we go back to classical universal algebra: Let V be a variety of universal algebras, X be a fixed infinite set and F(X) the free algebra on X. A pair (w,w') holds in an algebra A in V if, for every map f : X ---> A, the induced homomorphism f* : F(X) ---> A makes f*(w) = f*(w'); and in this case we write A |= (w,w'). Thus |= becomes a relation between V and F(X)xF(X) (where x is used as the cartesian product symbol). As every relation does, |= determines a Galois connection between the subsets in V and the subsets in F(X)xF(X). Galois closed subsets in V are exactly subvarieties (by definition), and Galois closed subsets in F(X)xF(X) are called algebraic theories. Now, as every universal-algebraist knows, every algebra A in V has its theory T(A) - the one corresponding to the subvariety in V generated by A. By a classical theorem, due to Garrett Birkhoff, is the smallest subclass in V containing A and closed under products, subalgebras, and quotients. Moreover, there is also a well-known completeness theorem for algebraic logic, according to which T(A) can be described directly (i.e. without using any algebras other then A and F(X); in the language of universal algebra it is the fully invariant congruence on F(X) generated by the intersection of all congruences determined by homomorphisms F(X) ---> A). If we now move from classical universal algebra to the more elegant language of Lawvere theories, and begin with such a theory T, then it is better not to fix X and instead of the pairs (w,w') above talk about pairs of parallel morphisms in T - and the story above can be easily modified accordingly. And in the new story T(A) is in fact not set-based anymore: Indeed, if C is a category with finite products, A an internal T-algebra in C, and (t,t') a pair of parallel morphisms in T, then A |= (t,t') should be understood as A(t) = A(t') (elegant indeed!). And then T(A) can be defined as "the largest quotient theory" of T obtained by making t = t' whenever A |= (t,t'). The only thing to have in mind is that not every C is "good enough" to get the "C-completeness" theorem. Moving further from Lawvere theories to other kinds of theories, we will only need to know if "the largest quotient theory" does exist. On the other hand, moving back to, say, classical (non-categorical) first order logic, we are in the well known situation again: if T is a first order theory and A a model of T, everybody knows what is the elementary theory of A. What I do not know is if anyone ever considered any kind of logic (categorical or not) where one cannot do this. I think Michael Makkai is the right person to be asked. Best regards, George ----- Original Message ----- From: "Tom Leinster" To: Sent: Monday, August 07, 2006 3:36 PM Subject: categories: Laws > Dear category theorists, > > Here's something that I don't understand. People sometimes talk about > algebraic structures "satisfying laws". E.g. let's take groups. Being > abelian is a law; it says that the equation xy = yx holds. A group G > "satisfies no laws" if > > whenever X is a set and w, w' are distinct elements of the free > group F(X) on X, there exists a homomorphism f: F(X) ---> G > such that f(w) and f(w') are distinct. > > For example, an abelian group cannot satisfy no laws, since you could take > X = {x, y}, w = xy, and w' = yx. There are various interesting examples > of groups that satisfy no laws. > > To be rather concrete about it, you could define a "law satisfied by G" to > be a triple (X, w, w') consisting of a set X and elements w, w' of F(X), > such that every homomorphism F(X) ---> G sends w and w' to the same thing. > A law is "trivial" if w = w'. Then "satisfies no laws" means "satisfies > only trivial laws". > > You could then say: given a group G, consider the groups that satisfy all > the laws satisfied by G. (E.g. if G is abelian then all such groups will > be abelian.) This is going to be a new algebraic theory. > > What bothers me is that I feel there must be some categorical story I'm > missing here. Everything above is very concrete; for instance, it's > heavily set-based. What's known about all this? In particular, what's > known about the process described in the previous paragraph, whereby any > theory T and T-algebra G give rise to a new theory? > > Thanks, > Tom > > > > > From rrosebru@mta.ca Tue Aug 8 08:51:12 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 08 Aug 2006 08:51:12 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GAQ40-0007Vc-PS for categories-list@mta.ca; Tue, 08 Aug 2006 08:48:01 -0300 Date: Tue, 8 Aug 2006 09:38:02 +0100 (BST) From: "Prof. Peter Johnstone" To: categories@mta.ca Subject: categories: Re: Laws MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 7 The following seems so obvious that I suspect it's not what Tom is really asking for; but it seems to me to be an answer to his question. A law in Tom's sense is just a parallel pair of arrows F(X) \rightrightarrows F(1) in the algebraic theory T under consideration (thinking of T as the dual of the category of finitely-generated free algebras). To get the theory of algebras satisfying a given set S of laws, you just need to construct the product-respecting congruence on T generated by S (i.e., the usual closure conditions for a congruence, plus the condition that f ~ f' and g ~ g' imply f x g ~ f' x g'), and factor out by it. Now any T-algebra A (in a category C, say) corresponds to a product- preserving functor F: T --> C; and the set of laws satisfied by A is just the (necessarily product-respecting) congruence generated by F, i.e. the set of parallel pairs in T having the same image under F. Is there anything more to it than that? Peter Johnstone ------------ On Mon, 7 Aug 2006, Tom Leinster wrote: > Dear category theorists, > > Here's something that I don't understand. People sometimes talk about > algebraic structures "satisfying laws". E.g. let's take groups. Being > abelian is a law; it says that the equation xy = yx holds. A group G > "satisfies no laws" if > > whenever X is a set and w, w' are distinct elements of the free > group F(X) on X, there exists a homomorphism f: F(X) ---> G > such that f(w) and f(w') are distinct. > > For example, an abelian group cannot satisfy no laws, since you could take > X = {x, y}, w = xy, and w' = yx. There are various interesting examples > of groups that satisfy no laws. > > To be rather concrete about it, you could define a "law satisfied by G" to > be a triple (X, w, w') consisting of a set X and elements w, w' of F(X), > such that every homomorphism F(X) ---> G sends w and w' to the same thing. > A law is "trivial" if w = w'. Then "satisfies no laws" means "satisfies > only trivial laws". > > You could then say: given a group G, consider the groups that satisfy all > the laws satisfied by G. (E.g. if G is abelian then all such groups will > be abelian.) This is going to be a new algebraic theory. > > What bothers me is that I feel there must be some categorical story I'm > missing here. Everything above is very concrete; for instance, it's > heavily set-based. What's known about all this? In particular, what's > known about the process described in the previous paragraph, whereby any > theory T and T-algebra G give rise to a new theory? > > Thanks, > Tom > > > > > From rrosebru@mta.ca Tue Aug 8 08:51:12 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 08 Aug 2006 08:51:12 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GAQ3N-0007SV-2a for categories-list@mta.ca; Tue, 08 Aug 2006 08:47:21 -0300 Date: Tue, 8 Aug 2006 02:30:20 -0400 (EDT) Subject: categories: Re: Laws From: flinton@wesleyan.edu To: categories@mta.ca MIME-Version: 1.0 Content-Type: text/plain;charset=UTF-8 Content-Transfer-Encoding: 8bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 8 To respond to Leinster's inquiry, "Laws" (or "equations"), as the set-based universal algebraists understand them, are ordered pairs of members of free algebras (i.e., pairs e = (e_1, e_2) in F x F, for F an algebra free on some set of "free generators." Actually, far more often than not, the variety of algebras these F are free in is presented by means of operations only, and the F are then called "absolutely free." A given equation e "holds" in an algebra A with the given operations iff under each homomorphism from F to A the elements e_1 and e_2 of F are shipped to some same value in A. >From this perspective the Abelianness equation xy=yx is the pair (xy, yx) in F2 x F2 (F2 denoting the absolutely free algebra on the two free generators x & y based on, say, three operations, one binary (multiplication), one unary (inversion), one nullary (choice of base point). The associativity equation x(yz) = (xy)z is another equation in this sense. One need not, of course, insist dogmatically on taking as equations ONLY pairs in absolutely free algebras: no harm in considering pairs in free algebras of any variety. Thus, for example, (xy, yx) is still a reasonable equation for groups. But (x(yz), (xy)z) doesn't do what you think: the RHS and LHS are ALREADY equal in every group, and the pair is simply the diagonal entry (xyz, xyz) (the INTENDED associativity is already a FACT for groups, not, like commutativity, a condition that, capable of failing, may meaningfully be imposed). If these comments don't fully address the concerns raised, please let me know. In any event, the laws most UAers speak of refer to equations in absolutely free algebras coming from the "lawless" variety whose algebras use the same operations as another variety one is more interested in, but are subject to the imposition of no equations at all. -- Fred Tom Leinster had written: > Dear category theorists, > > Here's something that I don't understand. People sometimes talk about > algebraic structures "satisfying laws". E.g. let's take groups. Being > abelian is a law; it says that the equation xy = yx holds. A group G > "satisfies no laws" if > > whenever X is a set and w, w' are distinct elements of the free > group F(X) on X, there exists a homomorphism f: F(X) ---> G > such that f(w) and f(w') are distinct. > > For example, an abelian group cannot satisfy no laws, since you could take > X = {x, y}, w = xy, and w' = yx. There are various interesting examples > of groups that satisfy no laws. > > To be rather concrete about it, you could define a "law satisfied by G" to > be a triple (X, w, w') consisting of a set X and elements w, w' of F(X), > such that every homomorphism F(X) ---> G sends w and w' to the same thing. > A law is "trivial" if w = w'. Then "satisfies no laws" means "satisfies > only trivial laws". > > You could then say: given a group G, consider the groups that satisfy all > the laws satisfied by G. (E.g. if G is abelian then all such groups will > be abelian.) This is going to be a new algebraic theory. > > What bothers me is that I feel there must be some categorical story I'm > missing here. Everything above is very concrete; for instance, it's > heavily set-based. What's known about all this? In particular, what's > known about the process described in the previous paragraph, whereby any > theory T and T-algebra G give rise to a new theory? > > Thanks, > Tom > > > > From rrosebru@mta.ca Tue Aug 8 08:51:12 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 08 Aug 2006 08:51:12 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GAQ2T-0007Pf-LP for categories-list@mta.ca; Tue, 08 Aug 2006 08:46:25 -0300 Subject: categories: Re: Laws Date: Tue, 8 Aug 2006 02:08:40 -0300 (ADT) To: categories@mta.ca MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit From: selinger@mathstat.dal.ca (Peter Selinger) Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 9 Hi Tom, a lot is known about this. I will leave it to more qualified others to give the category-theoretic account. In set-like language, the answer to your question is provided by universal algebra. Denote by Th(G) the theory associated to a particular algebra G (over a given signature). More generally, to a class of algebras S (all over the same, from now on fixed, signature), associate Th(S), the theory of all those equations satisfied by all the algebras in S. Also, to a given theory T, let V(T) be the class of all algebras satisfying the equations in T (also called a variety of algebras). Birkhoff's HSP theorem states that a class C of algebras is of the form V(T), for some T, if and only if C is closed under isomorphism, and under the operations of taking quotient algebras, subalgebras, and cartesian products. (HSP stands for "homomorphic image, subalgebra, product"). As a direct consequence, let C=V(Th(G)), the class of all groups satisfying those equations that a particular group G satisfies. Then C is precisely the class of groups that can be obtained, up to isomorphism, from G by repeatedly taking quotients, subalgebras, and cartesian products. [Proof: certainly, the right-hand side is contained in C. Conversely, by the HSP theorem, the right-hand side class is of the form V(T), for some T. Since G is in the class, T can only contain equations that hold in G, thus T is a subset of Th(G). By contravariance of the "V" operation, it follows that C=V(Th(G)) is a subset of V(T)]. Moreover, since a subalgebra of a quotient is a quotient of a subalgebra, and a cartesian product of quotients [subalgebras] is a quotient [subalgebra] of a cartesian product, the three HSP operations can be taken in this particular order: Thus, a group satisfies all the equations that G satisfies, if and only if it is isomorphic to a quotient of a subalgebra of some (possibly infinite) product G x ... x G. There are generalizations to properties other than equational ones, but I don't remember them as well. A "Horn clause" is an implication between equations, or more precisely a property of the form (forall x1...xn)(P1 and ... and Pn => Q), where P1,...,Pn,Q are equations. Of course, every equation is trivially a Horn clause (for n=0), but not the other way around. A typical example of a Horn clause is cancellability, the property xz=yz => x=y. (This holds in groups, but not in monoids, and cannot be expressed equationally in monoids, because it is not preserved under quotients). If you want to consider the class of algebras (in general smaller than V(Th(G))) that satisfy all the Horn clauses that G satisfies, then you have to drop the homomorphic images. I believe that the algebras in question will be precisely the subalgebras of products of G, but someone might correct me if I remember this wrongly. -- Peter Tom Leinster wrote: > > Dear category theorists, > > Here's something that I don't understand. People sometimes talk about > algebraic structures "satisfying laws". E.g. let's take groups. Being > abelian is a law; it says that the equation xy = yx holds. A group G > "satisfies no laws" if > > whenever X is a set and w, w' are distinct elements of the free > group F(X) on X, there exists a homomorphism f: F(X) ---> G > such that f(w) and f(w') are distinct. > > For example, an abelian group cannot satisfy no laws, since you could take > X = {x, y}, w = xy, and w' = yx. There are various interesting examples > of groups that satisfy no laws. > > To be rather concrete about it, you could define a "law satisfied by G" to > be a triple (X, w, w') consisting of a set X and elements w, w' of F(X), > such that every homomorphism F(X) ---> G sends w and w' to the same thing. > A law is "trivial" if w = w'. Then "satisfies no laws" means "satisfies > only trivial laws". > > You could then say: given a group G, consider the groups that satisfy all > the laws satisfied by G. (E.g. if G is abelian then all such groups will > be abelian.) This is going to be a new algebraic theory. > > What bothers me is that I feel there must be some categorical story I'm > missing here. Everything above is very concrete; for instance, it's > heavily set-based. What's known about all this? In particular, what's > known about the process described in the previous paragraph, whereby any > theory T and T-algebra G give rise to a new theory? > > Thanks, > Tom > > > > From rrosebru@mta.ca Wed Aug 9 17:32:36 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 09 Aug 2006 17:32:36 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GAuee-00027l-CQ for categories-list@mta.ca; Wed, 09 Aug 2006 17:27:52 -0300 Message-ID: <12277.81.66.248.65.1155095761.squirrel@mail.maths.gla.ac.uk> Date: Wed, 9 Aug 2006 04:56:01 +0100 (BST) Subject: categories: More laws From: "Tom Leinster" To: categories@mta.ca MIME-Version: 1.0 Content-Type: text/plain;charset=iso-8859-15 Content-Transfer-Encoding: 8bit Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 10 Thanks very much to the many people who provided helpful, expert replies. To recap, I asked (among other things): given an algebra A for some theory, what can be said about the algebras obeying all the equational laws that A obeys? The question was posed in the context of finitary algebraic theories, and in that context, there's a straightforward description of such algebras: they are exactly the quotients of subalgebras of (possibly infinite) powers of A. As explained by Peter Selinger and George Janelidze, this comes from Birkhoff's Theorem. I wanted to understand this particular situation - finitary algebraic theories and their equational laws - and I do understand it better than I did before. However, what I ultimately want to understand is something slightly different and more general, which I'll now describe. This will take a while, so I'll start with the punchline: we get some very simple universal characterizations of some quite sophisticated objects. For example, we'll get a characterization of the Stone spaces among all topological spaces, and a construction of the space of Borel probability measures on a compact space. Here goes. Take an algebraic theory and write F for the free algebra functor. Any equational law w = w' in a set X of variables generates a congruence ~ on FX (identify w and w'), hence a quotient map e: FX ---> (FX)/~. An algebra A obeys this law iff e is orthogonal to A, i.e. every map FX ---> A factors uniquely through e. All such maps e encoding laws are regular epi (and more besides). However, let's consider *all* maps whose domain is a free object. I also want to consider all adjunctions, not just those arising from an algebraic theory - although they will provide important examples. So the general set-up is this. Fix an adjunction U: D ---> C, F: C ---> D (F left adjoint to U). A *law* is an arrow e: FX ---> E where X is in C and E is in D. An object A of D *obeys* the law e if e is orthogonal to A. An object B of D is *A-complete* if B obeys every law that A obeys. The *A-completion* B[A] of B is the free A-complete object on B, assuming it exists. Note that "law" now means something more general than it did before; we're no longer just interested in *equational* laws. For instance, if the adjunction is the usual one between D = Group and C = Set, torsion-freeness is defined by laws, whereas it's not defined by equational laws (is it?). Indeed, a group is torsion-free iff it obeys the law 1 ---> Z/pZ for every prime p. Examples (without proofs): 1. Take C = D = Set and the identity adjunction. Write n for an n-element set. The 0-complete objects are 0 and 1. The only 1-complete object is 1. If |A| > 1 then every set is A-complete, since A obeys "no laws" (i.e. only those laws that are isomorphisms). (If we were just using equational laws then 0 would be 1-complete too.) 2. Take the usual adjunction between D = abelian groups and C = sets. Let k be either the field of rational numbers or the field of p elements for some prime p; these fields have the property that an abelian group can be a k-vector space in at most one way. Then an abelian group is k-complete iff it is a k-vector space. 3. Take D to be a v-semilattice and C to be the terminal category. Let a be in D. Then an element b of D is a-complete iff b >= a, so b[a] = a v b. This might suggest that in general, B[A] should be functorial in A (as well as in B), but it's not. You can use example (1) to show this. 4. Take the discrete-space/point-set adjunction between D = Top and C = Set. Write 2 for the discrete 2-point space. Then a space is 2-complete iff it is a Stone space, i.e. compact Hausdorff totally disconnected. So if B is any space, B[2] is the reflection of B into Stone spaces. It's striking that the adjunction between Top and Set, together with the simple space 2, give rise to the notion of Stone space. Poetically, "the theory of the 2-point space is the theory of Stone spaces". All of this remains true if 2 is replaced by any other Stone space with > 1 element. (But it's most dramatic if you use 2.) 5. This is the most substantial example, and it's what started me off on all this. It's from work of Matthias Schroeder and Alex Simpson: see Simpson's talk "Probabilistic Observations and Valuations" at http://homepages.inf.ed.ac.uk/als/Talks/ Let D be the category of topological spaces equipped with a binary operation and C = Top, with the obvious adjunction between them. Let I = [0, 1] with topology generated by all the subintervals (x, 1], and the midpoint (mean) operation. Schroeder and Simpson prove, among other things, that if X is a compact Hausdorff space then (FX)[I] is the space of regular Borel probability measures on X, equipped with the weak topology (and the obvious midpoint operation). Using the universal property of (FX)[I], this also gives the definition of integration on X. I'd be interested to know what other people make of this. Perhaps, for instance, someone knows a good way to describe which properties can be defined by "laws" in the sense above, and perhaps someone can shed some light on the non-functoriality noted in (3). Thanks for reading, Tom From rrosebru@mta.ca Wed Aug 9 17:32:36 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 09 Aug 2006 17:32:36 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GAubj-0001wp-29 for categories-list@mta.ca; Wed, 09 Aug 2006 17:24:51 -0300 Date: Tue, 8 Aug 2006 15:19:29 -0400 (EDT) From: F W Lawvere To: categories@mta.ca Subject: categories: Laws 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: 11 A simple answer to Tom Leinster's question involves the Galois connection well-analyzed by Michel Hebert at Whitepoint (2006): in a fixed category an object A can "satisfy" a morphism q: F->Q iff q*: (Q,A) -> (F,A) is a bijection. Then for any class of objects A there is the class of "laws" q satisfied by all of them, and reciprocally. If the category itself is mildly exact, one could instead of morphisms q consider their kernels as reflexive pairs. For example, if there is a free notion, a reflexive pair F' =>F has a coequalizer which could be taken as a law q. However, the "categorical story" that Tom was missing is not told well by the "Universal Algebra" of 75 years ago. Unfortunately, Galois connections in the sense of Ore are not "universal" enough to explicate the related universal phenomena in algebra, algebraic geometry, and functional analysis. The mere order-reversing maps between posets of classes are usually restrictions of adjoint functors between categories, and noting this explicitly gives further information. For example, Birkhoff's theorem does not apply well to the question: "Do groups form a variety of monoids?" Indeed, does the word "variety" mean a kind of category or a kind of inclusion functor? In algebraic geometry, an analogous question concerns whether an algebraic space that is a subspace of another one is closed (i.e. definable by equations) or not. Often instead it is defined by inverting some global functions, giving an open subscheme, not a subvariety, but still a good subspace. The analogy goes still further; a typical open subspace of X is actually a closed subspace of X x R, and of course the category of groups does become a variety if we adjoin an additional operation to the theory of monoids. In my thesis (1963) (now available on-line as a TAC Reprint, and extensively elaborated on by Linton and others in SLNM 80) I isolated an adjoint pair "Structure/Semantics" strictly analogous to the basic "Function algebra/Spectrum) pairs occurring in algebraic geometry and in functional analysis. In that context, note that the epimorphisms in the category of theories (categories with finite products) include both surjections (laws given by equations, dual semantically to Birkhoff subvarieties) as well as localizations (laws given by adjoining inverses to previously given operations, semantically corresponding to "open" algebraic subcategories). Can these "open" inclusions between algebraic categories be characterized semantically? The technical notion "Structure of" was motivated by the example of cohomology operations: in general, the totality of natural operations on the values of a given functor involves both more operations and more laws than those of the codomain category. The example illustrates that such adjoints are of much broader interest than the mere perfect duality that one might obtain by restricting both sides (one does not expect to recover a space from its cohomology, and the category of spaces studied is not even an algebraic category). As an important further example of a large adjoint which specializes both to Galois connections in each space as well as to a perfect duality on suitable subcategories, consider Stone's study of the relation between spaces and real commutative algebras; for computational purposes, the spaces of the form C(X) need to receive morphisms from algebras A (like polynomial algebras) that are not of that form; such homomorphisms are by adjointness equivalent to continuous maps X --> Spec(A), where Spec(A) would map further to R^n if n were a chosen parameterizer for generators of A in a presentation. Best wishes to all. Bill ************************************************************ 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 Wed Aug 9 17:32:36 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 09 Aug 2006 17:32:36 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GAud2-00021R-PN for categories-list@mta.ca; Wed, 09 Aug 2006 17:26:12 -0300 Mime-Version: 1.0 (Apple Message framework v752.2) Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed Content-Transfer-Encoding: 7bit From: Rob Goldblatt Subject: categories: Re: Laws Date: Wed, 9 Aug 2006 14:24:01 +1200 To: categories@mta.ca Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 12 One aspect of the categorisation of "equation" is the approach of Banaschewski and Herrlich. This replaces an equation as a pair (s,t) of terms that belong to some free algebra F by the least quotient (coequaliser) e: F -->> F/E identifying s and t. An algebra A satisfies equation (s,t) precisely when every homomorphism F --> A lifts across e to a homomorphism F/E --> A. Thus the notion of an equation becomes that of a regular epi e with free domain, and an object satisfies such an e when it is injective for e. To obtain a notion intrinsic to a given category, the free domains were replaced by domains that are regular-projective, i.e. projective for all regular epis, this being a property enjoyed by free algebras in categories of universal algebras. The approach has been dualised in the coalgebra literature, with a "coequation" being defined as a regular mono with regular-injective codomain, and a "covariety" as the class of coalgebras that are projective for some given class of coequations. Some (not all) relevant references are below. cheers, Rob @Article{ bana:subc76, author = "B. Banaschewski and H. Herrlich", title = "Subcategories Defined by Implications", journal = "Houston Journal of Mathematics", year = "1976", volume = "2", number = "2", pages = "149--171" } @Article{ adam:vari03, author = {Ji{\v{r}}{\'\i} Ad{\'a}mek and Hans-E. Porst}, title = "On Varieties and Covarieties in a Category", journal = "Mathematical Structures in Computer Science", year = "2003", volume = {13}, pages = "201-232" } @Techreport{ awod:coal00, author = "Steve Awodey and Jesse Hughes", title = "The Coalgebraic Dual of {B}irkhoff's Variety Theorem", institution = "Department of Philosophy, Carnegie Mellon University", year = "2000", number = "CMU-PHIL-109", note = "\url{http://phiwumbda.org/~jesse/papers/ index.html}" } On 8/08/2006, at 1:36 AM, Tom Leinster wrote: > Dear category theorists, > > Here's something that I don't understand. People sometimes talk about > algebraic structures "satisfying laws". E.g. let's take groups. > Being > abelian is a law; it says that the equation xy = yx holds. A group G > "satisfies no laws" if > > whenever X is a set and w, w' are distinct elements of the free > group F(X) on X, there exists a homomorphism f: F(X) ---> G > such that f(w) and f(w') are distinct. > > For example, an abelian group cannot satisfy no laws, since you > could take > X = {x, y}, w = xy, and w' = yx. There are various interesting > examples > of groups that satisfy no laws. > > To be rather concrete about it, you could define a "law satisfied > by G" to > be a triple (X, w, w') consisting of a set X and elements w, w' of F > (X), > such that every homomorphism F(X) ---> G sends w and w' to the same > thing. > A law is "trivial" if w = w'. Then "satisfies no laws" means > "satisfies > only trivial laws". > > You could then say: given a group G, consider the groups that > satisfy all > the laws satisfied by G. (E.g. if G is abelian then all such > groups will > be abelian.) This is going to be a new algebraic theory. > > What bothers me is that I feel there must be some categorical story > I'm > missing here. Everything above is very concrete; for instance, it's > heavily set-based. What's known about all this? In particular, > what's > known about the process described in the previous paragraph, > whereby any > theory T and T-algebra G give rise to a new theory? > > Thanks, > Tom > > > > From rrosebru@mta.ca Wed Aug 9 17:32:36 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 09 Aug 2006 17:32:36 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GAucT-0001zF-S0 for categories-list@mta.ca; Wed, 09 Aug 2006 17:25:37 -0300 Date: Wed, 9 Aug 2006 09:31:48 +1000 (EST) Subject: categories: Re: Laws From: "Jon Cohen" To: categories@mta.ca MIME-Version: 1.0 Content-Type: text/plain;charset=iso-8859-1 Content-Transfer-Encoding: quoted-printable Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 13 Hi, > If you want to consider the class of algebras (in general smaller than > V(Th(G))) that satisfy all the Horn clauses that G satisfies, then you > have to drop the homomorphic images. I believe that the algebras in > question will be precisely the subalgebras of products of G, but > someone might correct me if I remember this wrongly. Isomorphic images of subalgebras of products and ultraproducts, I believe - the standard notation for this seems to be $ISP_U$. Further, there is the interesting result that TH(G) =3D Th(H) for any fre= e nonabelian groups G and H. The following paper gives a summary of this result and a discussion of equations in free groups: http://www.math.mcgill.ca/olga/V00228H7.pdf best, Jon -- http://rsise.anu.edu.au/~jon From rrosebru@mta.ca Thu Aug 10 20:37:10 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 10 Aug 2006 20:37:10 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GBJyq-0007Lu-Lm for categories-list@mta.ca; Thu, 10 Aug 2006 20:30:24 -0300 Date: Thu, 10 Aug 2006 16:13:13 +0100 (BST) Subject: categories: Jobs in Glasgow From: "Tom Leinster" To: categories@mta.ca MIME-Version: 1.0 Content-Type: text/plain;charset=iso-8859-15 Content-Transfer-Encoding: 8bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 14 Once again, we're hiring. There are two positions available, Lecturer and Senior Lecturer/Reader. See the forwarded mail below. For those not familiar with British academic terminology, these are all tenured jobs. Lecturer is the basic position (e.g. that's what I am). Senior Lecturer and Reader are more senior. Professors are relative rarities; it's perfectly normal to finish one's career as a SL or Reader, without ever becoming a Professor. I should point out that this huge wave of hiring has not been brought about by mass desertion. It's mainly for demographic reasons (lots of people retiring), and in this case because of a couple of people moving from teaching to pure research roles. The blurb says that "preference may be given to" those with an interest in analysis, geometry or topology. However, (a) in the past we've tended to be quite open-minded about appointing people outside our specifically targetted areas, and (b) for certain reasons, I think that now could be quite a favourable time for a category theorist to apply. If you want any further informal information, feel free to get in touch. Tom > UNIVERSITY of GLASGOW > Department Of Mathematics > > Two positions: > Lecturer In Pure Mathematics > Senior Lecturer/Reader in Pure Mathematics > > You should have a commitment to enhancing the strong research profile of > the Pure Mathematics Group in the Department. Preference may be given to > those with research interests that will strengthen our activity in > Analysis and in Geometry and Topology. You will participate fully in the > research > and teaching of a dynamic and broad-based department. The posts are > available from 1 January 2007 or as soon as possible thereafter. > > For further information about the department and application procedures > see http://www.maths.gla.ac.uk/ From rrosebru@mta.ca Thu Aug 10 20:37:10 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 10 Aug 2006 20:37:10 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GBK0N-0007QP-Ir for categories-list@mta.ca; Thu, 10 Aug 2006 20:31:59 -0300 Date: Thu, 10 Aug 2006 17:19:05 -0400 From: "Stephen Davies" To: Subject: categories: gentle introduction to CT? Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Content-Disposition: inline Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 15 Hello all, I'm a complete novice to Category Theory, and I'm looking for some kind of tutorial or other introductory material that would help me at least get up to speed with the basics. Maybe something that assumed some discrete math and abstract algebra, and proceeded to develop the topic for beginners. Are there any intro texts like that out there? (And if not, would someone please write and publish one? :->) Thanks, - Stephen Davies (stephen@umw.edu) From rrosebru@mta.ca Thu Aug 10 20:37:10 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 10 Aug 2006 20:37:10 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GBJxg-0007JI-Pp for categories-list@mta.ca; Thu, 10 Aug 2006 20:29:12 -0300 Mime-Version: 1.0 (Apple Message framework v752.2) Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed Content-Transfer-Encoding: 7bit From: Michael Mislove Subject: categories: MFPS 23 Preliminary Announcement Date: Thu, 10 Aug 2006 03:58:43 -0500 To: categories@mta.ca Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: RO X-Status: X-Keywords: X-UID: 16 MFPS 23 Preliminary Announcement The 23rd Conference on the Mathematical Foundations of Programming Semantics (MFPS 23) will take place in New Orleans, LA USA from April 11 to April 14, 2007. The Conference will be held on the campus of Tulane University, as has been the case with previous MFPS meetings in New Orleans. This is a preliminary announcement to provide important dates for submissions to the conference. MFPS 23 will feature six invited addresses by programming semantics, its mathematical and logical underpinnings, and in related areas. There also will be a number of special sessions, and a Tutorial Day on April 10 will precede the meeting. Among the special sessions will be one honoring Gordon Plotkin on his many contributions to the area. This session will be organized by Samson Abramsky (Oxford). The MFPS 23 Program Committee will be chaired by Marcelo Fiore (Cambridge). The important dates are: Friday, December 15 - Deadline for submission of titles and short abstracts of intended submissions Friday, December 22 - Deadline for submission of full papers Friday, February 9 - Announcement of accepted papers Friday, March 2 - Deadline for submission of accepted papers in final form As was done this year, the Proceedings of the meeting will be published in final form at the time of the meeting, in hard copy and online in the ENTCS series. In addition, there will be a special journal issue composed of selected papers from the meeting, compiled after the meeting takes place. A full Call for Papers will be forthcoming around September 15, including the list of PC members, the names of the invited speakers, the full list of special sessions and their organizers, and specifics about the Tutorial Day activities. More information about the MFPS series can be found at its web site http://www.math.tulane/edu/~mfps/ mfps.html =============================================== Professor Michael Mislove Phone: +1 504 862-3441 Department of Mathematics FAX: +1 504 865-5063 Tulane University URL: http://www.math.tulane.edu/~mwm New Orleans, LA 70118 USA =============================================== From rrosebru@mta.ca Thu Aug 10 20:37:10 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 10 Aug 2006 20:37:10 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GBJzo-0007Oz-OI for categories-list@mta.ca; Thu, 10 Aug 2006 20:31:24 -0300 Date: Thu, 10 Aug 2006 16:14:46 -0400 (EDT) From: Michael Barr To: Categories list Subject: categories: Linear--structure or property? 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: 17 Bill Lawvere uses "linear" for a category enriched over commutative semigroups. Obviously, if the category has finite products, this is a property. What about in the absence of finite products (or sums)? Could you have two (semi)ring structures on the same set with the same associative multiplication? Robin Houston's startling (to me, anyway) proof that a compact *-autonomous category with finite products is linear starts by proving that 0 = 1. Suppose the category has only binary products? Well, I have an example of one that is not linear: Lawvere's category that is the ordered set of real numbers has a compact *-autonomous structure. Tensor is + and internal hom is -. Product is inf and sum is sup, but there are no initial or terminal objects and the category is not linear. From rrosebru@mta.ca Thu Aug 10 20:37:11 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 10 Aug 2006 20:37:11 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GBJw7-0007EH-W8 for categories-list@mta.ca; Thu, 10 Aug 2006 20:27:36 -0300 From: "George Janelidze" To: Subject: categories: Re: Laws Date: Thu, 10 Aug 2006 02:19:51 +0200 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 18 Dear All, What Tom says now, and what Bill calls a simple answer referring to Miche= l Hebert, also suggests to mention [H. Andr=E9ka and I. N=E9meti, Los lemma holds in every category, Stud. S= ci. Math. Hung. 13, 1978, 361-376] (although a previous paper of the same authors would be needed, I think). And I am sure many other people also considered many other candidates for the concept of a "law" producing a suitable Galois connection. And - no doubt - many such constructions would produce interesting Galois closed classes. However, I think "the Universal Algebra of 75 years ago" gave a beautiful and fundamental example, were the Galois closed classes are fully and beautifully described (that Galois connection deals with subvarieties of = a fixed variety, with fixed "basic operators" and so there is no problem wi= th "What is a variety?" of course). This does not mean that I am trying to argue with Bill: Of course it is t= rue that Bill's thesis was a great further enlightenment, and of course it is true that TODAY seeing only those Galois connections and not seeing adjunctions containing them and much more (also in Galois theory itself!)= is too bad! George Janelidze From rrosebru@mta.ca Fri Aug 11 14:04:15 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 11 Aug 2006 14:04:15 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GBaMO-0003Om-Ge for categories-list@mta.ca; Fri, 11 Aug 2006 13:59:48 -0300 Date: Fri, 11 Aug 2006 10:35:32 -0400 (EDT) From: F W Lawvere To: Categories list Subject: categories: RE: Linear--structure or property? In-Reply-To: <039A7CE5BC8F554C81732F2505D511720290F225@BONHAM.AD.UWS.EDU.AU> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 19 Sorry Mike, I believe you misunderstood my definition of "Linear category". It is in my paper "Categories of Space and of Quantity" International Symposium on Structures in Mathematical Theories, San Sebastian (1990), published in the Book "The Space of Mathamtics. Philosophical, Epistemological and Historical Explorations. DeGruyter, Berlin (1992), 14-30. Namely, because "additive" was already established standard usage that included negatives, and because the importance in algebraic geometry etc. of rigs other than rings and distributive lattices had been historically underestimated, I chose the name "linear" because it would at least have an intuitive resonance with physicists and computer scientists and others who routinely apply linear algebra to positive and other contexts. Thus, the definition is simply a category with finite products and coproducts which agree (i.e. there is a zero object which permits the definition of identity matrices, which are required to be invertible). Of course this implies enrichment in additive monoids. However, the question of whether a multiplicative monoid has a unique addition is of interest. I believe it was resolved in the negative by the Tarski school of universal algebra, although I cannot recall the reference, nor whether their examples were as straightforward as Steve Lack's. In ambient categories other than abstract sets, that question has been of interest to me in particular in connection with the foundations of smooth geometry and calculus. Euler's definition of real numbers as ratios of infinitesimals leads immediately to a definition of multiplication as composition of pointed endomorphisms of an infinitesimal object T. This endomorphism monoid R of course has a zero element and hence there are two canonical injections from it into R x R and the requirement on an addition is that it be R-homogeneous and restrict to the identity along both those injections. In classical algebraic geometry, where T is coordinatized as the spectrum of the dual numbers, this addition is unique. In a forthcoming paper I try to approach that result from a conceptual standpoint, by invoking expected functorial properties of integration or differentiation. The matter still needs to be clarified. Concerning Mike's example of the real numbers as a *-autonomous category under addition, I found it useful to note, in my 1983 Minnesota Report on the existence of semi-continuous entropy functions, that the system of extended real numbers, including both positive and negative infinity, is also a closed monoidal category (even though not all objects are reflexive). There are actually two such structures, depending on which sense of the ordering one takes as the arrows of the category; the definition of addition (which is to be the tensor product) must preserve colimits in each variable (where colimits has the two possible meanings). Besides its utility in freely performing certain operations in analysis, this structure strikingly illustrates a point often made to young students: subtraction is just addition of negatives, provided one is in a group like the real numbers; however, in general the binary operation of subtraction can be merely adjoint to addition and, in fact, the condition that A is a "compact" object in a SMC for all B, A* @ B --> hom(A,B)is invertible precisely characterizes the finite real numbers. Best wishes, Bill ------------------------------------------ On Fri, 11 Aug 2006, Stephen Lack wrote: > It's a structure. > > Consider the following category C. > Two objects x and y, with hom-categories > C(x,x)=C(y,y)={0,1} > C(y,x)={0} > C(x,y)=M > with composition defined so that each 1 is an > identity morphism and each 0 a zero morphism, > and with M an arbitrary set. Any commutative > monoid structure on M makes C into a linear category. > > Steve. > > > -----Original Message----- > From: cat-dist@mta.ca on behalf of Michael Barr > Sent: Fri 8/11/2006 6:14 AM > To: Categories list > Subject: categories: Linear--structure or property? > > Bill Lawvere uses "linear" for a category enriched over commutative > semigroups. Obviously, if the category has finite products, this is a > property. What about in the absence of finite products (or sums)? Could > you have two (semi)ring structures on the same set with the same > associative multiplication? > > Robin Houston's startling (to me, anyway) proof that a compact > *-autonomous category with finite products is linear starts by proving > that 0 = 1. Suppose the category has only binary products? Well, I have > an example of one that is not linear: Lawvere's category that is the > ordered set of real numbers has a compact *-autonomous structure. > Tensor is + and internal hom is -. Product is inf and sum is sup, but > there are no initial or terminal objects and the category is not linear. > > > > > > > > From rrosebru@mta.ca Fri Aug 11 14:04:15 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 11 Aug 2006 14:04:15 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GBaNp-0003UN-UA for categories-list@mta.ca; Fri, 11 Aug 2006 14:01:17 -0300 From: "George Janelidze" To: "Categories list" Subject: categories: Re: Linear--structure or property? Date: Fri, 11 Aug 2006 16:53:04 +0200 MIME-Version: 1.0 Content-Type: text/plain;charset="iso-8859-1" Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 20 Dear Steve, It is true that constructing such examples with more than one object is even easier in a sense. However your example needs a minor correction: What is 1+1 in C(x,x) and in C(y,y)? If it is 0, them M must be a Z/2Z-module, since for every element u in M we have u+u = 1u+1u = (1+1)u = 0u = 0. If it is 1, them M must be idempotent (as before: u+u = 1u+1u = (1+1)u = 1u = u). If it is 1 in C(x,x) and 0 in C(y,y), then M becomes trivial, which destroys the example. And... why did not you and I just take the monoid {0,1}, which becomes a commutative semiring for both additions?! More generally, take any non-degenerated Boolean algebra. It has multiplication=intersection=meet, and at least two additions (symmetric difference and union=join) both good for that multiplication. George ----- Original Message ----- From: "Stephen Lack" To: "Categories list" Sent: Friday, August 11, 2006 12:49 PM Subject: categories: RE: Linear--structure or property? It's a structure. Consider the following category C. Two objects x and y, with hom-categories C(x,x)=C(y,y)={0,1} C(y,x)={0} C(x,y)=M with composition defined so that each 1 is an identity morphism and each 0 a zero morphism, and with M an arbitrary set. Any commutative monoid structure on M makes C into a linear category. Steve. -----Original Message----- From: cat-dist@mta.ca on behalf of Michael Barr Sent: Fri 8/11/2006 6:14 AM To: Categories list Subject: categories: Linear--structure or property? Bill Lawvere uses "linear" for a category enriched over commutative semigroups. Obviously, if the category has finite products, this is a property. What about in the absence of finite products (or sums)? Could you have two (semi)ring structures on the same set with the same associative multiplication? Robin Houston's startling (to me, anyway) proof that a compact *-autonomous category with finite products is linear starts by proving that 0 = 1. Suppose the category has only binary products? Well, I have an example of one that is not linear: Lawvere's category that is the ordered set of real numbers has a compact *-autonomous structure. Tensor is + and internal hom is -. Product is inf and sum is sup, but there are no initial or terminal objects and the category is not linear. From rrosebru@mta.ca Fri Aug 11 09:50:38 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 11 Aug 2006 09:50:38 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GBWPf-00075j-RR for categories-list@mta.ca; Fri, 11 Aug 2006 09:46:56 -0300 Content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain;charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Subject: categories: RE: Linear--structure or property? Date: Fri, 11 Aug 2006 20:49:15 +1000 Message-ID: <039A7CE5BC8F554C81732F2505D511720290F225@BONHAM.AD.UWS.EDU.AU> From: "Stephen Lack" To: "Categories list" Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 21 It's a structure. Consider the following category C. Two objects x and y, with hom-categories C(x,x)=3DC(y,y)=3D{0,1} C(y,x)=3D{0} C(x,y)=3DM with composition defined so that each 1 is an=20 identity morphism and each 0 a zero morphism, and with M an arbitrary set. Any commutative=20 monoid structure on M makes C into a linear category.=20 Steve. -----Original Message----- From: cat-dist@mta.ca on behalf of Michael Barr Sent: Fri 8/11/2006 6:14 AM To: Categories list Subject: categories: Linear--structure or property? =20 Bill Lawvere uses "linear" for a category enriched over commutative semigroups. Obviously, if the category has finite products, this is a property. What about in the absence of finite products (or sums)? = Could you have two (semi)ring structures on the same set with the same associative multiplication? Robin Houston's startling (to me, anyway) proof that a compact *-autonomous category with finite products is linear starts by proving that 0 =3D 1. Suppose the category has only binary products? Well, I = have an example of one that is not linear: Lawvere's category that is the ordered set of real numbers has a compact *-autonomous structure. Tensor is + and internal hom is -. Product is inf and sum is sup, but there are no initial or terminal objects and the category is not linear. From rrosebru@mta.ca Fri Aug 11 09:50:38 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 11 Aug 2006 09:50:38 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GBWNc-0006xJ-W2 for categories-list@mta.ca; Fri, 11 Aug 2006 09:44:49 -0300 From: "George Janelidze" To: "Categories list" Subject: categories: Re: Linear--structure or property? Date: Fri, 11 Aug 2006 11:12:38 +0200 MIME-Version: 1.0 Content-Type: text/plain;charset="iso-8859-1" Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 22 Dear Michael, I have a trivial comment to the first paragraph of your message. You ask: "...Could you have two (semi)ring structures on the same set with the same associative multiplication?" Take any (semi)ring R with a multiplicative automorphism f that is not an additive automorphism, and transport the structure along f. For instance, both in the semiring of natural numbers and in the ring of integers, any non-identity permutation of (positive) prime numbers determines such an f. An example for students: take, say, f(2) = 3, f(3) = 2, and f(p) = p for all primes p different from 2 and 3. Then, denoting the new addition by *, we calculate (usung the fact that f coincides with its inverse) 1*1 = f(f(1)+f(1)) = f(2+2) = f(2x2) = f(2)xf(2) = 3x3 = 9. Best regards, George ----- Original Message ----- From: "Michael Barr" To: "Categories list" Sent: Thursday, August 10, 2006 10:14 PM Subject: categories: Linear--structure or property? > Bill Lawvere uses "linear" for a category enriched over commutative > semigroups. Obviously, if the category has finite products, this is a > property. What about in the absence of finite products (or sums)? Could > you have two (semi)ring structures on the same set with the same > associative multiplication? > > Robin Houston's startling (to me, anyway) proof that a compact > *-autonomous category with finite products is linear starts by proving > that 0 = 1. Suppose the category has only binary products? Well, I have > an example of one that is not linear: Lawvere's category that is the > ordered set of real numbers has a compact *-autonomous structure. > Tensor is + and internal hom is -. Product is inf and sum is sup, but > there are no initial or terminal objects and the category is not linear. > > > > From rrosebru@mta.ca Sat Aug 12 09:28:25 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 12 Aug 2006 09:28:25 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GBsQC-0007BR-6U for categories-list@mta.ca; Sat, 12 Aug 2006 09:16:56 -0300 Date: Sat, 12 Aug 2006 00:18:24 +0100 (BST) Subject: Re: categories: Laws From: "Tom Leinster" To: categories@mta.ca MIME-Version: 1.0 Content-Type: text/plain;charset=iso-8859-15 Content-Transfer-Encoding: 8bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 23 Thanks to Bill Lawvere for pointing out the close connection between the questions I was asking and the recent work of Jiri Adamek, Michel Hebert and Lurdes Sousa, presented at both CT06 and the Glasgow PSSL. It must have lodged itself in my mind in some subliminal way; apologies for not mentioning it earlier. Perhaps the following is rather basic, but I'm failing to understand one of the points in Bill's message. As I read it, he's saying that the Galois connection of traditional universal algebra (connecting sets of laws and varieties of algebras) is contained within the structure-semantics adjunction of his thesis. I don't see how this works. I *do* understand the following points: 1. Traditional universal algebra - given a signature S, one has the set E of equations between S-terms and the class V of S-algebras, and the relation "satisfaction" gives a Galois connection between the power-sets/classes P(E) and P(V). A Galois connection is, of course, a contravariant adjunction on the right between posets. 2. Categorical algebra - structure and semantics form a contravariant adjunction on the right between the category Th of Lawvere theories and (roughly speaking) the category K of categories over Set. One is a section of the other: if T is a theory then Struc(Sem(T)) = T. 3. If T is a theory, any equation between the operations in T can be construed as a pair of parallel arrows in T, and so induces a map from T to the quotient theory T' obtained by imposing this equation. Such a map T ---> T' is an epimorphism, although not every epi in the category of theories arises in this way. 4. Given a contravariant adjunction on the right, both functors turn colimits into limits, hence epis into monos. In particular, any set of equations between the operations of a theory T induces an epi T ---> T', hence a mono Sem(T') ---> Sem(T) between the categories of models, which may perhaps be the inclusion of a full subcategory. This makes it look as if there's going to be a Galois connection between the poset of quotient objects of T (i.e. epis out of T) and subobjects of Sem(T), for every theory T. But there seem to be two problems: (i) the functors in an adjunction on the right don't in general turn monos into epis, so I don't see why the structure-semantics adjunction is going to turn subcategories of Sem(T) into quotient theories of T; (ii) even if this did work, epis out of T are more general than equations, and monos into Sem(T) are more general than full subcategories, so it wouldn't exactly recover the classical Galois connection of universal algebra. I guess I've made a wrong turn somewhere; can someone put me right? Thanks, Tom > A simple answer to Tom Leinster's question involves the Galois connection > well-analyzed by Michel Hebert at Whitepoint (2006): in a fixed category an object A can "satisfy" a morphism q: F->Q iff q*: (Q,A) -> (F,A) is a > bijection. Then for any class of objects A there is the class of "laws" q > satisfied by all of them, and reciprocally. If the category itself is mildly exact, one could instead of morphisms q consider their kernels as reflexive pairs. For example, if there is a free notion, a reflexive pair > F' =>F has a coequalizer which could be taken as a law q. > > However, the "categorical story" that Tom was missing is not told well by the "Universal Algebra" of 75 years ago. Unfortunately, Galois connections in the sense of Ore are not "universal" enough to explicate the related universal phenomena in algebra, algebraic geometry, and functional analysis. The mere order-reversing maps between posets of classes are usually restrictions of adjoint functors between categories, and noting this explicitly gives further information. For example, Birkhoff's theorem does not apply well to the question: > > "Do groups form a variety of monoids?" > > Indeed, does the word "variety" mean a kind of category or a kind of inclusion functor? In algebraic geometry, an analogous question concerns whether an algebraic space that is a subspace of another one is closed (i.e. definable by equations) or not. Often instead it is defined by inverting some global functions, giving an open subscheme, not a subvariety, but still a good subspace. The analogy goes still further; a typical open subspace of X is actually a closed subspace of X x R, and of > course the category of groups does become a variety if we adjoin an additional operation to the theory of monoids. > > In my thesis (1963) > (now available on-line as a TAC Reprint, and extensively > elaborated on by Linton and others in SLNM 80) I isolated an adjoint pair > "Structure/Semantics" strictly analogous to the basic "Function > algebra/Spectrum) pairs occurring in algebraic geometry and in functional > analysis. In that context, note that the epimorphisms in the category of theories (categories with finite products) include both surjections (laws > given by equations, dual semantically to Birkhoff subvarieties) as well as > localizations (laws given by adjoining inverses to previously given operations, semantically corresponding to "open" algebraic subcategories). > Can these "open" inclusions between algebraic categories be characterized > semantically? > > The technical notion "Structure of" was motivated by the example of cohomology operations: in general, the totality of natural operations on the values of a given functor involves both more operations and more laws > than those of the codomain category. The example illustrates that such adjoints are of much broader interest than the mere perfect duality that one might obtain by restricting both sides (one does not expect to recover > a space from its cohomology, and the category of spaces studied is not even an algebraic category). > > As an important further example of a large adjoint which specializes both > to Galois connections in each space as well as to a perfect duality on suitable subcategories, consider Stone's study of the relation between spaces and real commutative algebras; for computational purposes, the spaces of the form C(X) need to receive morphisms from algebras A (like polynomial algebras) that are not of that form; such homomorphisms are by adjointness equivalent to continuous maps X --> Spec(A), where Spec(A) would map further to R^n if n were a chosen parameterizer for generators of A in a presentation. > > Best wishes to all. > > Bill > > > ************************************************************ > 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 Sat Aug 12 09:28:25 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 12 Aug 2006 09:28:25 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GBsPX-0007A2-F4 for categories-list@mta.ca; Sat, 12 Aug 2006 09:16:15 -0300 From: "George Janelidze" To: "Categories" ,"Lengyel, Florian" Subject: categories: Re: Linear--structure or property? Date: Fri, 11 Aug 2006 23:47:34 +0200 MIME-Version: 1.0 Content-Type: text/plain;charset="iso-8859-1" Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 24 FW: categories: Re: Linear--structure or property?Dear Florian, > 1*2 = f(f(1)+f(2)) = f(1+3) = f(4) = f(2x2) = f(2)xf(2) = 3x3 = 9. You are right, and thank you the correction (I think I thought of 3*3 = f(f(3)+f(3)) = f(2+2) =..., but does not matter of course). Dear Bill, Having two structures in {0,1} (with 1+1 = 0 and with 1+1 = 1) makes what you say about the Tarski school funny (sorry!) Best regards to all- George From rrosebru@mta.ca Sat Aug 12 20:37:34 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 12 Aug 2006 20:37:34 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GC2za-0006Fu-93 for categories-list@mta.ca; Sat, 12 Aug 2006 20:34:10 -0300 Date: Sat, 12 Aug 2006 13:56:29 GMT From: Oege.de.Moor@comlab.ox.ac.uk Message-Id: <200608121356.k7CDuTd3012559@mercury.comlab.ox.ac.uk> To: Subject: categories: aosd 2007 Content-Type: text Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 25 AOSD 2007: CALL FOR RESEARCH PAPERS 6th Conference on Aspect-Oriented Software Development http://www.aosd.net/2007/cfc/research.php >> on-line submission is now open << Deadline September 22 ------------------------------------------------------ The program committee especially welcomes submissions from category theorists on any topic relating to given a model of language X, construct a model of AspectX From rrosebru@mta.ca Sat Aug 12 20:37:34 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 12 Aug 2006 20:37:34 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GC30I-0006HW-QR for categories-list@mta.ca; Sat, 12 Aug 2006 20:34:54 -0300 Date: Sat, 12 Aug 2006 11:37:26 -0400 (EDT) From: F W Lawvere To: categories@mta.ca Subject: categories: Re: Laws MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 26 The thoughts being developed by Tom Leinster give renewed hope that results of 40 years ago are being further developed, beyond mere icons, into tools for actual analysis of algebraic problems *. I should perhaps have mentioned Lourdes Sousa's very interesting talk at White Point. She and Michel Hebert had divided the presentation of the work into existential (or injective) logic, and uniquely existential logic, and the latter is more directly relevant to the present discussion. The fact that a contravariant adjoint pair gives rise to Galois connections at each object is important in many different situations, for example in the classical study of rings of continuous functions on topological spaces. The information inherent in this remark is less visible if one arbitrarily restricts consideration to general epis and general monos (it was here that Tom made a "wrong turn" in his items 4.(i) and 4.(ii) ). To recover the classical Galois connection of universal algebra one must apply adjointness, and then take surjective (or regular epimorphic) images. The above general remark depends on the availability of operations like image in the categories that are being confronted in the adjointness. Again, I emphasize that in the classical case of continuous functions, it is important to consider algebras A which are not of the form C(Y). A possibly useful remark is that, under suitable restrictions on the category of spaces, the Stone-Weierstrass theorem can be interpreted as the statement that A --> C(X) is an epimorphism of rings iff its mate X --> Spec(A) is a monomorphism. But then by restricting the kind of epimorphisms and monomorphisms considered one obtains Galois connections which were originally considered by Stone in the 1930s before the more general functorial formulation which many of us learned from J.L. Kelley's General Topology. If one considers a tractable functor X --> Sem(T) from a very general category X into a very special kind of category of the classical universal algebra type, (i.e. where T is from the special doctrine of categories with finite products, etc.) then the structure functor Str assigns to the composite functor X --> Sets a definite algebraic theory Str(X) with a morphism of theories T -->Str(X). The surjective image of the latter morphism, of course, is the embodiment of the classical construction in the special case where the original tractable functor was a full inclusion. However, there are many full inclusions for which one has X = Sem(Str(X)), i.e. X is an algebraic category even though it is not a variety in Sem(T). Remark: The difference between an object (in this case an algebraic category) and an inclusion map (in this discussion a full inclusion functor) is of course not eliminated by restricting to the case where T is a free theory. It seems reasonable to use the classical term "variety" to refer to those inclusion functors fixed under Birkhoff's Galois correspondence, i.e. to those for which not only is X equal to the semantics of its structure, but for which moreover the morphism of theories T --> Str(X) is already surjective (which of course it is not in the example mentioned of groups in monoids). There are several local studies possible within the context of a given global adjoint. It seems to be an open problem to describe those full inclusions X --> Sem(T) for which T --> Str(X) is a localization (in which case the inclusion, if fixed, might be called "open" in contrast to the Birkhoff subvarieties which are clearly analogous to "closed" subspaces). A further problem: "locally closed" is a kind of inclusion of interest in geometry, so why should it not be also here? * see also the paper "Some Algebraic Problems..." following the Thesis in the TAC Reprints. On Sat, 12 Aug 2006, Tom Leinster wrote: > Thanks to Bill Lawvere for pointing out the close connection between the > questions I was asking and the recent work of Jiri Adamek, Michel Hebert > and Lurdes Sousa, presented at both CT06 and the Glasgow PSSL. It must > have lodged itself in my mind in some subliminal way; apologies for not > mentioning it earlier. > > Perhaps the following is rather basic, but I'm failing to understand one > of the points in Bill's message. As I read it, he's saying that the > Galois connection of traditional universal algebra (connecting sets of > laws and varieties of algebras) is contained within the > structure-semantics adjunction of his thesis. I don't see how this works. > > I *do* understand the following points: > > 1. Traditional universal algebra - given a signature S, one has the set E > of equations between S-terms and the class V of S-algebras, and the > relation "satisfaction" gives a Galois connection between the > power-sets/classes P(E) and P(V). A Galois connection is, of course, a > contravariant adjunction on the right between posets. > > 2. Categorical algebra - structure and semantics form a contravariant > adjunction on the right between the category Th of Lawvere theories and > (roughly speaking) the category K of categories over Set. One is a > section of the other: if T is a theory then Struc(Sem(T)) = T. > > 3. If T is a theory, any equation between the operations in T can be > construed as a pair of parallel arrows in T, and so induces a map from T > to the quotient theory T' obtained by imposing this equation. Such a map > T ---> T' is an epimorphism, although not every epi in the category of > theories arises in this way. > > 4. Given a contravariant adjunction on the right, both functors turn > colimits into limits, hence epis into monos. In particular, any set of > equations between the operations of a theory T induces an epi T ---> T', > hence a mono Sem(T') ---> Sem(T) between the categories of models, which > may perhaps be the inclusion of a full subcategory. > > This makes it look as if there's going to be a Galois connection between > the poset of quotient objects of T (i.e. epis out of T) and subobjects of > Sem(T), for every theory T. But there seem to be two problems: > > (i) the functors in an adjunction on the right don't in general turn monos > into epis, so I don't see why the structure-semantics adjunction is going > to turn subcategories of Sem(T) into quotient theories of T; > > (ii) even if this did work, epis out of T are more general than equations, > and monos into Sem(T) are more general than full subcategories, so it > wouldn't exactly recover the classical Galois connection of universal > algebra. > > I guess I've made a wrong turn somewhere; can someone put me right? > > Thanks, > Tom > > > > A simple answer to Tom Leinster's question involves the Galois > connection > > well-analyzed by Michel Hebert at Whitepoint (2006): in a fixed category > an object A can "satisfy" a morphism q: F->Q iff q*: (Q,A) -> (F,A) is a > > bijection. Then for any class of objects A there is the class of "laws" > q > > satisfied by all of them, and reciprocally. If the category itself is > mildly exact, one could instead of morphisms q consider their kernels as > reflexive pairs. For example, if there is a free notion, a reflexive pair > > F' =>F has a coequalizer which could be taken as a law q. > > > > However, the "categorical story" that Tom was missing is not told well > by the "Universal Algebra" of 75 years ago. Unfortunately, Galois > connections in the sense of Ore are not "universal" enough to explicate > the related universal phenomena in algebra, algebraic geometry, and > functional analysis. The mere order-reversing maps between posets of > classes are usually restrictions of adjoint functors between categories, > and noting this explicitly gives further information. For example, > Birkhoff's theorem does not apply well to the question: > > > > "Do groups form a variety of monoids?" > > > > Indeed, does the word "variety" mean a kind of category or a kind of > inclusion functor? In algebraic geometry, an analogous question concerns > whether an algebraic space that is a subspace of another one is closed > (i.e. definable by equations) or not. Often instead it is defined by > inverting some global functions, giving an open subscheme, not a > subvariety, but still a good subspace. The analogy goes still further; a > typical open subspace of X is actually a closed subspace of X x R, and of > > course the category of groups does become a variety if we adjoin an > additional operation to the theory of monoids. > > > > In my thesis (1963) > > (now available on-line as a TAC Reprint, and extensively > > elaborated on by Linton and others in SLNM 80) I isolated an adjoint > pair > > "Structure/Semantics" strictly analogous to the basic "Function > > algebra/Spectrum) pairs occurring in algebraic geometry and in > functional > > analysis. In that context, note that the epimorphisms in the category of > theories (categories with finite products) include both surjections (laws > > given by equations, dual semantically to Birkhoff subvarieties) as well > as > > localizations (laws given by adjoining inverses to previously given > operations, semantically corresponding to "open" algebraic > subcategories). > > Can these "open" inclusions between algebraic categories be > characterized > > semantically? > > > > The technical notion "Structure of" was motivated by the example of > cohomology operations: in general, the totality of natural operations on > the values of a given functor involves both more operations and more laws > > than those of the codomain category. The example illustrates that such > adjoints are of much broader interest than the mere perfect duality that > one might obtain by restricting both sides (one does not expect to recover > > a space from its cohomology, and the category of spaces studied is not > even an algebraic category). > > > > As an important further example of a large adjoint which specializes > both > > to Galois connections in each space as well as to a perfect duality on > suitable subcategories, consider Stone's study of the relation between > spaces and real commutative algebras; for computational purposes, the > spaces of the form C(X) need to receive morphisms from algebras A (like > polynomial algebras) that are not of that form; such homomorphisms are by > adjointness equivalent to continuous maps X --> Spec(A), where > Spec(A) would map further to R^n if n were a chosen parameterizer for > generators of A in a presentation. > > > > Best wishes to all. > > > > Bill > > > > > > ************************************************************ > > 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 Sat Aug 12 20:37:34 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 12 Aug 2006 20:37:34 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GC329-0006Kz-2T for categories-list@mta.ca; Sat, 12 Aug 2006 20:36:49 -0300 Date: Sat, 12 Aug 2006 12:35:47 -0400 (EDT) From: F W Lawvere To: "\"Categories\"" Subject: categories: Re: Linear--structure or property? MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 27 Beyond simple counter examples to general statements, the Tarski school also pursued conditions on particular monoids which might imply uniqueness of a ring structure, or a definite range of ring structures. As I suggested, that open problem takes on a deeper significance if we consider it within categories of cohesion, not just within the category of abstract sets. Best wishes to all. Bill ************************************************************ On Fri, 11 Aug 2006, George Janelidze wrote: > FW: categories: Re: Linear--structure or property?Dear Florian, > > > 1*2 = f(f(1)+f(2)) = f(1+3) = f(4) = f(2x2) = f(2)xf(2) = 3x3 = 9. > > You are right, and thank you the correction (I think I thought of 3*3 = > f(f(3)+f(3)) = f(2+2) =..., but does not matter of course). > > Dear Bill, > > Having two structures in {0,1} (with 1+1 = 0 and with 1+1 = 1) makes what > you say about the Tarski school funny (sorry!) > > Best regards to all- > > George > > > > From rrosebru@mta.ca Sat Aug 12 20:37:34 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 12 Aug 2006 20:37:34 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GC310-0006J2-KB for categories-list@mta.ca; Sat, 12 Aug 2006 20:35:38 -0300 Date: Sat, 12 Aug 2006 18:03:21 +0200 (CEST) From: Peter Schuster To: Categories Subject: categories: Book Announcement: "From Sets and Types to Topology and Analysis" MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 28 Dear All, Please allow me to bring to your attention the edition, by Laura Crosilla and me, of the volume "From Sets and Types to Topology and Analysis. Towards Practicable Foundations for Constructive Mathematics.", xix+376 pp., Oxford Logic Guides 48, Oxford University Press, 2005, ISBN 0-19-856651-4. For details, including a list of contributions, see http://www.oup.co.uk/isbn/0-19-856651-4 All the best, Peter Schuster Mathematisches Institut, Universitaet Muenchen http://www.mathematik.uni-muenchen.de/~pschust --- From rrosebru@mta.ca Mon Aug 14 18:05:37 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 14 Aug 2006 18:05:37 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GCjTK-0000WY-K4 for categories-list@mta.ca; Mon, 14 Aug 2006 17:55:42 -0300 Subject: categories: Re: gentle introduction to CT? From: "Brett G. Giles" To: categories@mta.ca Content-Type: text/plain Date: Sun, 13 Aug 2006 21:13:40 -0600 Mime-Version: 1.0 Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 29 Hi Stephen There are numerous books on Category Theory, but only one I can think of fits your criteria. You may want to look at: Conceptual Mathematics by F.W. Lawvere and S. H. Schanuel ISBN 0-521-47817-0 (paperback) It gives a good thorough intro to the subject. Online and free is "A Gentle Introduction to Category Theory" by Maarten Fokkinga at http://wwwhome.cs.utwente.nl/~fokkinga/mmf92b.html Depending on your math background, you may find the second a little fast paced. Good luck On Thu, 2006-08-10 at 17:19 -0400, Stephen Davies wrote: > Hello all, I'm a complete novice to Category Theory, and I'm looking for > some kind of tutorial or other introductory material that would help me > at least get up to speed with the basics. Maybe something that assumed > some discrete math and abstract algebra, and proceeded to develop the > topic for beginners. Are there any intro texts like that out there? > (And if not, would someone please write and publish one? :->) > > Thanks, > > > - Stephen Davies > (stephen@umw.edu) > From rrosebru@mta.ca Wed Aug 23 12:12:00 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 23 Aug 2006 12:12:00 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GFuGc-0004v6-BR for categories-list@mta.ca; Wed, 23 Aug 2006 12:03:42 -0300 Date: Tue, 22 Aug 2006 14:05:16 +0200 (CEST) From: Peter Schuster To: Categories Subject: categories: [3WFTop] Third Workshop on Formal Topology. First Announcement. Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 30 3WFTop First Announcement: THIRD WORKSHOP ON FORMAL TOPOLOGY Accademia Galileiana, Padua (Italy) 9-12 May 2007 workshop 7-8 May 2007 tutorials This is the third of a series of successful meetings on the development of Formal Topology and its connections with related approaches. The first two have been held in Padua, 1997, and Venice, 2002. For more information on 3WFTop see http://www.3wftop.math.unipd.it/ What is formal topology When topology is developed in a strictly constructive way, for instance over Martin-Loef's type theory, points cannot be given primitively and the pointfree approach is fundamental. This is the reason why it is called formal. Formal topology has now become an important tool in constructive mathematics. More on formal topology: http://www.3wftop.math.unipd.it/formal-topology.html Invited speakers Invited speakers include Andre' Joyal, Per Martin-Loef and many other prominent scholars: http://www.3wftop.math.unipd.it/invited-speakers.html Tutorials Before the workshop, two days of extensive and coordinated tutorials are planned, given by Bernhard Banaschewski and other pioneers: http://www.3wftop.math.unipd.it/tutorials.html Contacts If you wish to be kept updated with information about 3WFTop, please send an e-mail to: fortop@math.lmu.de with KEEP ME UPDATED in the subject. the Scientific Committee Thierry Coquand Giovanni Sambin Peter Schuster From rrosebru@mta.ca Wed Aug 23 12:12:00 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 23 Aug 2006 12:12:00 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GFuFh-0004qo-E2 for categories-list@mta.ca; Wed, 23 Aug 2006 12:02:45 -0300 Date: Mon, 21 Aug 2006 23:54:42 -0700 From: John Baez To: categories Subject: categories: lectures on n-categories and cohomology Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 31 Some of you may enjoy this: Lectures on n-Categories and Cohomology John Baez and Michael Shulman http://arxiv.org/abs/math.CT/0608420 The goal of these talks was to explain how cohomology and other tools of algebraic topology are seen through the lens of n-category theory. Special topics include nonabelian cohomology, Postnikov towers, the theory of "n-stuff", and n-categories for n = -1 and -2. The talks were very informal, and so are these notes. A lengthy appendix clarifies certain puzzles and ventures into deeper waters such as higher topos theory. For readers who want more details, we include an annotated bibliography. From rrosebru@mta.ca Wed Aug 23 12:12:00 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 23 Aug 2006 12:12:00 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GFuEz-0004ne-9n for categories-list@mta.ca; Wed, 23 Aug 2006 12:02:01 -0300 Date: Mon, 21 Aug 2006 08:29:44 -0700 From: Vaughan Pratt To: categories list Subject: categories: Attribution re no membership-respecting morphisms Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 32 I've attributed the third saying at http://boole.stanford.edu/dotsigs.html to Mike Barr. If there's an earlier attribution I should be using please let me know. Vaughan Pratt From rrosebru@mta.ca Sat Aug 26 23:31:04 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 26 Aug 2006 23:31:04 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GHAK1-0003PV-Lu for categories-list@mta.ca; Sat, 26 Aug 2006 23:24:25 -0300 Mime-Version: 1.0 (Apple Message framework v752.2) Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed To: categories From: David Roberts Subject: categories: classifying functor and colimits Date: Thu, 24 Aug 2006 15:29:15 +0930 Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 33 Dear category theorists, I have been plagued by the following question: does the classifying space functor commute with (co)limits? In particular, I have a system of compact topological groups G_i indexed by the natural numbers, and a whole lot of inclusions. Is B colim G_i homotopic to colim BG_i ? I have a hint that this should be so in my particular situation (in a letter of Serre to Grothendieck), but I'd like to know how the general case goes. Cheers, ------------------------------------------------------------------------ -- David Roberts School of Mathematical Sciences University of Adelaide SA 5005 ------------------------------------------------------------------------ -- droberts@maths.adelaide.edu.au www.maths.adelaide.edu.au/~droberts www.trf.org.au From rrosebru@mta.ca Sat Aug 26 23:31:04 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 26 Aug 2006 23:31:04 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GHAHd-0003Ll-CH for categories-list@mta.ca; Sat, 26 Aug 2006 23:21:57 -0300 Date: Wed, 23 Aug 2006 08:28:21 -0700 From: John Baez To: categories Subject: categories: The n-Category Cafe Message-ID: <20060823152821.GA27812@math.ucr.edu> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 34 Dear Categorists - David Corfield, Urs Schreiber and I have started a group blog on math, physics and philosophy called The n-Category Cafe: http://golem.ph.utexas.edu/category/ You're all invited to come over, order an espresso and chat. We'll talk about lots of things besides n-category theory, but that's one of our shared interests, so we'll probably talk a lot about that. One interesting feature of this blog is that it lets you use TeX. Best, jb From rrosebru@mta.ca Sat Aug 26 23:31:04 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 26 Aug 2006 23:31:04 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GHAKx-0003Qr-QD for categories-list@mta.ca; Sat, 26 Aug 2006 23:25:23 -0300 Date: Fri, 25 Aug 2006 10:49:18 +0200 (CEST) From: Jiri Adamek To: categories net Subject: categories: Re: Laws MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 35 Back from holidays I am slowly working through the various interesting e-mails of Tom Leinster. The examples he presents in his e-mail on August 9 seem to lead to the following question: given on object A characterize the full subcategory L_A of all objects satisfying all "laws" that A satisfies. The algebraic case ("law" meaning equation) has two obvious generalizations: orthogonality and injectivity. For both of them the answer to the above question is nice and easy. INJECTIVITY: let H be the class of morphisms generated by {A} in the Galois connection "to be injective to". (That is, H consists of all morphisms to which A is injective.) The opposite class L_A = Inj H of all objects injective w.r.t. H consists of precisely all split subobjects of powers of A. This holds in every category with powers. Proof: injectivity classes are clearly closed under product and split subobject. Conversely, if B lies in Inj H, then it is a split subobject of the power of A to hom(B,A). In fact, the canonical morphism m from B to the power of A to hom(B,A) lies in H: given a morphism f: B -> A, then f factorizes through m via the projection of A^hom(B,A) corresponding to f. Consequently, B is injective w.r.t. m, and since B is the domain of m, this implies trivially that m is a split mono. ORTHOGONALITY: let K be the class of morphisms generated by {A} in the Galois connection "to be orthogonal to". The opposite class L_A = Ort K of all objects orthogonal to K is the closure of {A} under limits. This holds in every complete and cowellpowered category. Proof: orthogonality classes are clearly closed under limit, thus, Ort K contains the limit closure L of {A}. To prove the opposite inclusion observe that L is a reflective subcategory due to Freyd's SAFT: A is easily seen to be a cogenerator of L. For every object B in Ort K a reflection r: B -> B' in L lies in K (since A lies in L). Thus, B is orthogonal to r. This implies that r is a split mono. Now L contains B' and is closed under split subobjects, thus B lies in L. FINITARY LAWS The algebraic case has another feature: every equation, when translated as injectivity or orthogonality w.r.t. a morphism e:A-> B, has the property that both A and B are finitely presentable. We can thus decide to restrict our attention to finitary morphisms, i.e., morhisms with finitely presentable domains and codomains, as our "laws". If H is the class of all finitary morphisms to which A is injective, then the injectivity class Inj H is the closure of {A} under product, filtered colimit and pure subobject. This was proved by J. Rosicky, F. Borceux and myself in TAC 10 (2002), 148-161. If K is the class of all finitary morphisms to which A is orthogonal, then the orthogonality class Ort K is the closure of {A} under product, filtered colimit and A-pure subobject as proved by L. Sousa and myself in JPAA 276 (2004), 685-705. (The concept of A-pure subobject is a bit artificial, but unfortunately the above result is false if one substitutes it with pure morphism. Surprisingly, when generalizing finitary morphisms to k-ary morphisms for uncountable cardinals k, the corresponding result does hold with pure subobjects: see M. Hebert and J. Rosicky, Bull. London Math. Soc 33 (2001) 685-688.) xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx alternative e-mail address (in case reply key does not work): J.Adamek@tu-bs.de xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx From rrosebru@mta.ca Sat Aug 26 23:31:04 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 26 Aug 2006 23:31:04 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GHAJC-0003OL-PI for categories-list@mta.ca; Sat, 26 Aug 2006 23:23:34 -0300 Date: Wed, 23 Aug 2006 11:47:39 -0400 (EDT) From: Michael Barr To: categories list Subject: categories: Re: Attribution re no membership-respecting morphisms MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 36 Here is what the site actually says: Monotone functions respect order, group homomorphisms respect the group operation, linear transformations respect linear combinations, and gangsters respect membership in the Cosa Nostra, but what morphism has ever respected membership in a set? It is sheer hubris for a relation that can't get no respect to claim to support all of mathematics. (Old argument of category theorist Mike Barr, new polemics.) That is not a bad rendition (save for the reference to Cosa Nostra) of what I actually said which was that we create these elaborate structures of well-founded trees subject to the rule that two chidren of the same leaf cannot be isomorphic. But then, unlike all other structures that we build, we make no hypothesis that functions preserve the structure. Indeed, I think a structure-preserving map must be the inclusion of a subset. And there are no non-identity endomorphisms. On Mon, 21 Aug 2006, Vaughan Pratt wrote: > I've attributed the third saying at > > http://boole.stanford.edu/dotsigs.html > > to Mike Barr. If there's an earlier attribution I should be using > please let me know. > > Vaughan Pratt > > From rrosebru@mta.ca Mon Aug 28 14:33:46 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 28 Aug 2006 14:33:46 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GHksh-00012d-3y for categories-list@mta.ca; Mon, 28 Aug 2006 14:26:39 -0300 Subject: categories: Re: classifying functor and colimits From: Tom Leinster To: categories@mta.ca Content-Type: text/plain Date: Mon, 28 Aug 2006 13:45:07 +0100 Mime-Version: 1.0 Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 37 Dear David, > I have been plagued by the following question: does the classifying > space functor commute with (co)limits? The classifying space functor (from Cat to Top) does preserve finite products. It doesn't preserve all infinite products, e.g. let A be the discrete category with two objects and consider the product of infinitely many copies of A. Nor does it preserve all colimits, as the following example shows. Let 1 be the terminal category, 2 the category consisting of a single arrow, and 3 the category consisting of a commutative triangle: 1 = . 2 = . --> . 3 = . --> . --> . Take the two different functors from 1 to 2. The pushout of the diagram in Cat formed by these functors is 3, and B3 is Delta^2, the standard topological 2-simplex. However, B1 is the one-point space and B2 is the unit interval, so the pushout of B1 and B2 is an interval of length 2, which is not homeomorphic to Delta^2. This doesn't answer your question about sequential colimits, but maybe it gives some helpful context. Best wishes, Tom > > In particular, I have a system of compact topological groups G_i > indexed by the natural numbers, and a whole lot of inclusions. > > Is B colim G_i homotopic to colim BG_i ? > > I have a hint that this should be so in my particular situation (in a > letter of Serre to Grothendieck), but I'd like to know how the > general case goes. > > Cheers, > > ------------------------------------------------------------------------ > -- > David Roberts > School of Mathematical Sciences > University of Adelaide SA 5005 > ------------------------------------------------------------------------ > -- > droberts@maths.adelaide.edu.au > www.maths.adelaide.edu.au/~droberts > www.trf.org.au > > > > > > -- Tom Leinster From rrosebru@mta.ca Mon Aug 28 14:33:46 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 28 Aug 2006 14:33:46 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GHkrt-0000yY-82 for categories-list@mta.ca; Mon, 28 Aug 2006 14:25:49 -0300 From: "Ronnie Brown" To: "categories" Subject: categories: Re: lectures on n-categories and cohomology; Grothendieck comments Date: Mon, 28 Aug 2006 11:49:38 +0100 MIME-Version: 1.0 Content-Type: text/plain;format=flowed;charset="iso-8859-1";reply-type=original Content-Transfer-Encoding: quoted-printable Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 38 John, in his very nice notes with Shulman, quotes from a letter to Quille= n=20 which formed the start of Alexander Grothendieck's `Pursuing Stacks'. Sin= ce=20 this explicitly mentions Bangor, it could be useful to readers to read a= n=20 extract from a later letter to me. I'll put a pdf file on my web site in = due=20 course. `Pursuing Stacks' is to be published in Documents Math\'ematiques= ,=20 with various correspondence as an Appendix, edited by Georges Maltsinioti= s. A recent arXiv paper by Jo=E3o Faria Martins and Tim Porter math.QA/0608484 [abs, ps, pdf, other] : Title: On Yetter's Invariant and an Extension of the Dijkgraaf-Witten=20 Invariant to Categorical Groups seems also relevant to the theme of the Baez-Shulman notes. Ronnie Brown Extract from a letter Alexander Grothendieck to Ronnie Brown, 06/ 09/1983 It is all too evident I am not an expert on homotopy theory, and the books I am bold enough to write now on foundational matters are very likely to be looked at as ``rubbish" too by most experts, unless I show up with $\pi_{147}(S^{123}$ as a by-product (whereas it is for the least doubtful I will...). At the very least, you should give me some hints as to the kind of things I could reasonably say in a ``formal note of support", besides how nice it would be to have a better understanding of the foundational matters. This makes me think by the way that (much to my surprise, I confess) I never got a line from Quillen in reply to my long letter from February. I guess since that time he should have gotten that letter, maybe you even gave him a copy time ago if I remember it right. As two letters for me in the Faculty mail got lost lately, it isn't wholly impossible that he did reply and I didn't get it. In case you should know something on this behalf, please tell me. I realize somewhat belatedly that I should apologize for the mistaken impression I got, from a quick glance through the heap of reprints you sent me a year or so ago, and which I somewhat bluntly expressed in my first letter to you I believe - namely that you had little or no background in so-called ``geometry". It would be more accurate, it seems, to say that your background and mine don't overlap too much. My own background has been somewhat moving for the last ten or twelve years, since I withdrew rather abruptly from the mathematical milieu. Thus my interest in the Teichm\"{u}ller (or mapping class) group has developed mainly, in two steps, during the last two years and a half. It came quite as a surprise that you have come to some contact with these groups, too - and I would be quite interested to get a reference on this ``amazing finite presentation" you are speaking of (and I can well imagine it must be tied up with the Mumford-Deligne compactification of the relevant modular multiplicity, whose $\pi_1$ is the group we are looking at). I was under the impression that to give an explicit presentation of the group, rather than of the groupoid, would be kind of inextricable, and it is surely an interesting fact it is not. Still, I am pretty sure for the ``arithmetical'' theory I am interested in, that one just cannot possibly dispense from working with groupoids, rather than just groups. A few times in your letter you stop to ask what of all you're saying would make sense with spaces replaced by topoi, and wondering if it would be a long way to do those things in the wider context. If you are just interested in homotopy types (more accurately, prohomotopy types) of topoi, it seems to me that Artin-Mazur have developed more or less all the machinery needed, in order for any result in semisimplicial homotopy theory, say, to carry over more or less automatically to topoi. This isn't really the most interesting thing they did, but rather what could be considered as the routine part of their work, which they develop by standard semisimplicial homotopy techniques. What they were really after was giving various ``profinite" variants of homotopy types and a formalism of ``profinite completion" of usual (pro )homotopy types, relevant when working with \'etale cohomology of schemes, and using this, stating and proving a few key theorems, a typical one being that for a proper and smooth morphism of schemes $[f]$ and taking profinite completions (of homotopy types) ``prime to the residue characteristics", the theoretical ``homotopy fiber" of the map $[f]$ can be identified with the (prohomotopy type of the) actual schematic geometric fibers of the map $[f]$. It turns out that the algebraic machinery reduces these statements to corresponding statements about cohomology with torsion coefficients (including non-commutative cohomology in dimension 1), which had all been proved in the SGA4 seminar by Artin and me. I think within the next day I am going to read through your preprint ``An introduction to simplicial T-complexes", as you suggested, maybe I'll write again if I have any questions. For the time being, I guess I'll stop. And thank you again very much for your patient help. Very affectionately Alexander ----- Original Message -----=20 From: "John Baez" To: "categories" Sent: Tuesday, August 22, 2006 7:54 AM Subject: categories: lectures on n-categories and cohomology > Some of you may enjoy this: > > Lectures on n-Categories and Cohomology > John Baez and Michael Shulman > http://arxiv.org/abs/math.CT/0608420 > > The goal of these talks was to explain how cohomology and other > tools of algebraic topology are seen through the lens of n-category > theory. Special topics include nonabelian cohomology, Postnikov > towers, the theory of "n-stuff", and n-categories for n =3D -1 and -2. > The talks were very informal, and so are these notes. A lengthy > appendix clarifies certain puzzles and ventures into deeper waters > such as higher topos theory. For readers who want more details, > we include an annotated bibliography. > > > > > > > > --=20 > Internal Virus Database is out-of-date. > Checked by AVG Free Edition. > Version: 7.1.394 / Virus Database: 268.10.4/402 - Release Date: 27/07/2= 006 > >=20 From rrosebru@mta.ca Mon Aug 28 21:56:34 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 28 Aug 2006 21:56:34 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GHrrd-0001tH-Bn for categories-list@mta.ca; Mon, 28 Aug 2006 21:54:01 -0300 Date: Mon, 28 Aug 2006 17:16:09 -0500 From: Peter May To: categories@mta.ca Subject: categories: Classifying spaces Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 39 On colimits of classifying spaces. This topologist may be missing something, but the conclusion seems obviously true, at least in reasonable situations. With a countable system of inclusions of spaces, unless the situation is fairly bizarre, the system will be filtered and we can find a countable cofinal sequence. But finite products commute with sequential colimits in reasonable categories of spaces. Since the usual classifying space of G is constructed as the geometric realization of a simplicial space whose space of q-simplices is G^q, and since geometric realization certainly commutes with sequential colimits, the conclusion seems clear. It is used all the time in algebraic topology, in such familiar examples as BU = colim BU(n), BTop = colim BTop(n), BF = colim BF(n), etc, the last being a system of monoids rather than groups. In the standard classical statement that BU classifies stable complex vector bundles, we are using the first listed special case. While the groups are compact in that case, compactness is not relevant to the argument and fails for the groups Top(n), for example. In more complicated equivariant situations, one has countable systems that are not naturally sequential, but again the conclusion is familiar and in common use. Peter From rrosebru@mta.ca Mon Aug 28 21:56:35 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 28 Aug 2006 21:56:35 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GHrqf-0001ov-64 for categories-list@mta.ca; Mon, 28 Aug 2006 21:53:01 -0300 Subject: categories: Re: classifying functor and colimits Date: Tue, 29 Aug 2006 07:45:46 +1000 From: "Stephen Lack" To: Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 40 Dear David, The classifying space functor is the composite of the nerve functor N:Cat-->SSet and the geometric realization functor SSet-->Top, and it makes sense to consider them separately. The nerve functor preserves all limits (since it is a right adjoint) but not all colimits. It does preserve=20 sequential colimits, since it is given by homming out of the finite ordinals, which are finitely presentable.=20 More explicitly, the nerve NC of a category C is the simplicial set whose set (NC)_n of n-simplices is the set of all functors from [n] to C, where [n] is the category {0<1<...Top) and=20 so preserves all colimits, but relatively few limits. It does, as Tom Leinster observes, preserve finite products. Putting these facts together, one sees that the classifying=20 space functor preserves coproducts, filtered colimits, and finite = products. Steve Lack. -----Original Message----- From: cat-dist@mta.ca on behalf of Tom Leinster Sent: Mon 8/28/2006 10:45 PM To: categories@mta.ca Subject: categories: Re: classifying functor and colimits =20 Dear David, > I have been plagued by the following question: does the classifying > space functor commute with (co)limits? The classifying space functor (from Cat to Top) does preserve finite products. It doesn't preserve all infinite products, e.g. let A be the discrete category with two objects and consider the product of infinitely many copies of A. Nor does it preserve all colimits, as the following example shows. Let 1 be the terminal category, 2 the category consisting of a single arrow, and 3 the category consisting of a commutative triangle: 1 =3D . 2 =3D . --> . 3 =3D . --> . --> . Take the two different functors from 1 to 2. The pushout of the diagram in Cat formed by these functors is 3, and B3 is Delta^2, the standard topological 2-simplex. However, B1 is the one-point space and B2 is the unit interval, so the pushout of B1 and B2 is an interval of length 2, which is not homeomorphic to Delta^2. This doesn't answer your question about sequential colimits, but maybe it gives some helpful context. Best wishes, Tom > > In particular, I have a system of compact topological groups G_i > indexed by the natural numbers, and a whole lot of inclusions. > > Is B colim G_i homotopic to colim BG_i ? > > I have a hint that this should be so in my particular situation (in a > letter of Serre to Grothendieck), but I'd like to know how the > general case goes. > > Cheers, > > = ------------------------------------------------------------------------ > -- > David Roberts > School of Mathematical Sciences > University of Adelaide SA 5005 > = ------------------------------------------------------------------------ > -- > droberts@maths.adelaide.edu.au > www.maths.adelaide.edu.au/~droberts > www.trf.org.au > > > > > > --=20 Tom Leinster From rrosebru@mta.ca Wed Aug 30 18:35:23 2006 -0300 Status: X-Status: X-Keywords: Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 30 Aug 2006 18:35:23 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GIXYv-0001Nq-J4 for categories-list@mta.ca; Wed, 30 Aug 2006 18:25:29 -0300 Date: Mon, 28 Aug 2006 18:01:21 -0700 From: John Baez To: categories Subject: categories: Martins-Porter paper Mime-Version: 1.0 Content-Type: text/plain; charset=3Diso-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 8bit User-Agent: Mutt/1.4.2.1i Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Interesting letter from Grothendieck! Ronnie Brown writes: >A recent arXiv paper by Jo=E3o Faria Martins and Tim Porter >math.QA/0608484 >Title: On Yetter's Invariant and an Extension of the Dijkgraaf-Witten >Invariant to Categorical Groups > > seems also relevant to the theme of the Baez-Shulman notes. Yes; we didn't get into TQFTs at all in our notes, but Martins and Porter use the classifying space of a discrete 2-group (=3D categorical group =3D crossed module =3D gr-category) in their construction, and that's quite relevant. I wrote a little introduction to the Martins-Porter paper and its antecedents at the n-category cafe: http://golem.ph.utexas.edu/category/2006/08/categorifying_the_dijkgraafwit.= html Best, jb From rrosebru@mta.ca Thu Aug 31 09:42:37 2006 -0300 Status: X-Status: X-Keywords: Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 31 Aug 2006 09:42:37 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GIlnZ-0007d6-F3 for categories-list@mta.ca; Thu, 31 Aug 2006 09:37:33 -0300 Date: Wed, 30 Aug 2006 23:02:51 -0700 From: John Baez To: categories Subject: categories: Martins-Porter paper Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Sender: cat-dist@mta.ca Precedence: bulk Message-Id: jim stasheff wrote: > link didn't work > even if I tacked the html onto the = Sorry, the equals sign should not be there. Here's the link to the Martins-Porter paper on categorifying the Dijkgraaf-Witten model: http://golem.ph.utexas.edu/category/2006/08/categorifying_the_dijkgraafwit.html and here, just for fun, is a letter from Grothendieck to Ronnie Brown: http://golem.ph.utexas.edu/category/2006/08/letter_from_grothendieck.html Best, jb