From MAILER-DAEMON Wed Aug 19 13:47:29 2009 Date: 19 Aug 2009 13:47:29 -0300 From: Mail System Internal Data Subject: DON'T DELETE THIS MESSAGE -- FOLDER INTERNAL DATA Message-ID: <1250700449@mta.ca> X-IMAP: 1243871509 0000000124 Status: RO This text is part of the internal format of your mail folder, and is not a real message. It is created automatically by the mail system software. If deleted, important folder data will be lost, and it will be re-created with the data reset to initial values. From rrosebru@mta.ca Mon Jun 1 12:48:22 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 01 Jun 2009 12:48:22 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MB9kI-0004RD-AF for categories-list@mta.ca; Mon, 01 Jun 2009 12:48:18 -0300 MIME-Version: 1.0 Date: Mon, 01 Jun 2009 16:15:43 +0300 From: Panagis Karazeris To: Subject: categories: preprint announcement Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Sender: categories@mta.ca Precedence: bulk Reply-To: Panagis Karazeris Message-Id: Status: RO X-Status: X-Keywords: X-UID: 1 Dear all, I would like to announce that the following preprint is available as http://arxiv.org/abs/0905.4883 as well as from my webpage www.math.upatras.gr/~pkarazer Final Coalgebras in Accessible Categories, by Panagis Karazeris, Apostolos Matzaris and Jiri Velebil Abstract: We give conditions on a finitary endofunctor of a finitely accessible category to admit a final coalgebra. Our conditions always apply to the case of a finitary endofunctor of a locally finitely presentable (l.f.p.) category and they bring an explicit construction of the final coalgebra i= n this case. On the other hand, there are interesting examples of final coalgebras beyond the realm of l.f.p. categories to which our results apply. We rely on ideas developed by Tom Leinster for the study of self-similar objects in topology.=20 Best regards, Panagis Karazeris [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Wed Jun 3 11:47:36 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 03 Jun 2009 11:47:36 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MBrkF-0006y5-Ju for categories-list@mta.ca; Wed, 03 Jun 2009 11:47:11 -0300 From: Hasse Riemann To: Category mailing list Subject: categories: Famous unsolved problems in ordinary category theory Date: Tue, 2 Jun 2009 16:31:32 +0000 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Sender: categories@mta.ca Precedence: bulk Reply-To: Hasse Riemann Message-Id: Status: O X-Status: X-Keywords: X-UID: 2 =20 Hello categorists =20 I don't know what to make of the silence to my question. This is the easiest question i have. I can't believe it is so difficult. It is not like i am asking you to solve the problems. =20 There must be some important open problems in ordinary category theory. There are plenty of them in the theory of algebras and in representation theory=2C so there should be more of them in category the= ory. =20 Especially if you broaden the boundaries a bit of what ordinary category th= eory is. Take for instance: model categories=2C categorical logic=2C categorical quantization=2C topos theory-locales-sheaves. But i had originally pure category theory in mind. =20 Best regards Rafael Borowiecki [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Wed Jun 3 11:47:37 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 03 Jun 2009 11:47:37 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MBrjM-0006rM-Cl for categories-list@mta.ca; Wed, 03 Jun 2009 11:46:16 -0300 Date: Tue, 2 Jun 2009 11:38:55 +0100 (BST) From: Dusko Pavlovic To: Till Mossakowski , categories@mta.ca Subject: categories: Re: patenting colimits? MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed Sender: categories@mta.ca Precedence: bulk Reply-To: Dusko Pavlovic Message-Id: Status: O X-Status: X-Keywords: X-UID: 3 thanks. our tools can be just as freely downloaded, eg http://www.kestrel.edu/home/projects/pda/ -- dusko On Tue, 2 Jun 2009, Till Mossakowski wrote: > Dusko, > > let me just notice that we are maintaining a *free software* tool > that actually is built upon categorical ideas (using Goguen's > and Burstall's institutions) and that computes colimits > (there is a menu Edit -> Proofs -> Compute Colimit > > http://www.dfki.de/sks/hets > > It is published under a free license, so you can freely download > the binaries, the source, modify the source, and republish your > improvements under the license. > > Best, > Till [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Wed Jun 3 11:47:37 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 03 Jun 2009 11:47:37 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MBriJ-0006lD-UV for categories-list@mta.ca; Wed, 03 Jun 2009 11:45:11 -0300 Date: Tue, 02 Jun 2009 10:51:22 +0200 From: Till Mossakowski MIME-Version: 1.0 To: Dusko Pavlovic , categories@mta.ca Subject: categories: Re: patenting colimits? Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Sender: categories@mta.ca Precedence: bulk Reply-To: Till Mossakowski Message-Id: Status: O X-Status: X-Keywords: X-UID: 4 Dusko, let me just notice that we are maintaining a *free software* tool that actually is built upon categorical ideas (using Goguen's and Burstall's institutions) and that computes colimits (there is a menu Edit -> Proofs -> Compute Colimit http://www.dfki.de/sks/hets It is published under a free license, so you can freely download the binaries, the source, modify the source, and republish your improvements under the license. Best, Till Dusko Pavlovic schrieb: > [sorry, i just noticed this] > > On May 26, 2009, at 8:29 PM, Zinovy Diskin wrote: > >> impressive examples, such as the extremely successful Eclipse project >> http://www.eclipse.org, (btw, Eclipse is partly based on categorical >> ideas that engineers developed/reinvented from scratch). > > i designed two tools which people who built them built on top of > eclipse, and i must admint that i managed to completely miss those > categorical ideas. eclipse is very handy, but some simple class > hierarchies often become unrecognizable in its straitjacket. i am > probably not the only one who would be curious to learn more about > category theory behind eclipse :) > [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Wed Jun 3 11:48:59 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 03 Jun 2009 11:48:59 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MBrlu-0007A8-Lz for categories-list@mta.ca; Wed, 03 Jun 2009 11:48:54 -0300 MIME-Version: 1.0 Date: Wed, 3 Jun 2009 13:10:21 +0200 Subject: categories: Decidability of the theory of a monad From: Andrej Bauer To: categories list Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit Sender: categories@mta.ca Precedence: bulk Reply-To: Andrej Bauer Message-Id: Status: O X-Status: X-Keywords: X-UID: 5 Consider the theory of a monad, i.e., the axioms are those of a category and a monad given as a triple: an operation T on objects, for each object A a morphism eta_A : A -> T A, and an operation lift_{A,B} which maps morphisms f : A -> T B to lift f : T A -> T B. Concretely, the axioms are (where lift f is written f* and composition is juxtaposition): id f = f f id = f (f g) h = f (g h) eta* = id f* eta = f (f* g)* = f* g* Presumably, the equational theory (with partial operations) of such a triple is decidable. Is this known? If we ignore the types and partiality, we can attempt to turn the above equations into a confluent terminating rewrite system using the Knuth-Bendix algorithm, but it gets stuck (on various orderings I tried). A more categorical way of asking the same question is: what is a concrete description of the free "monad on a category" (is this the same as "free monad" on "free category"?). With kind regards, Andrej [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Wed Jun 3 11:49:31 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 03 Jun 2009 11:49:31 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MBrmR-0007E1-Oq for categories-list@mta.ca; Wed, 03 Jun 2009 11:49:27 -0300 Date: Wed, 3 Jun 2009 15:41:54 +0100 (BST) From: Bob Coecke To: categories@mta.ca Subject: categories: 3 year Lectureship at Oxford in Categories/Quantum MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed Sender: categories@mta.ca Precedence: bulk Reply-To: Bob Coecke Message-Id: Status: O X-Status: X-Keywords: X-UID: 6 Oxford University Computing Laboratory has a vacancy for a fixed-term 3 year Departmental Lectureship starting October 1st and ending September 30th 2012. The successful candidate will be expected to lecture two courses per year, namely: * Categories, Proofs and Processes http://web.comlab.ox.ac.uk/teaching/courses/20082009/catsproofsprocs/ * Quantum Computer Science http://web.comlab.ox.ac.uk/teaching/courses/20082009/quantum/ Each of these courses involves twenty hours of lecturing per year. He will carry out research, including supervision, in a group under joint direction of Samson Abramsky and Bob Coecke: http://web.comlab.ox.ac.uk/activities/quantum/ More details are available form: http://www.comlab.ox.ac.uk/news/documents/CatsQCSLectureship-fps.pdf and you can contact Samson Abramsky and Bob Coecke . [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Thu Jun 4 21:09:33 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 04 Jun 2009 21:09:33 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MCMzl-0006Up-7L for categories-list@mta.ca; Thu, 04 Jun 2009 21:09:17 -0300 MIME-Version: 1.0 Date: Thu, 4 Jun 2009 00:08:28 +0200 Subject: categories: Re: Decidability of the theory of a monad From: Andrej Bauer To: categories list Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit Sender: categories@mta.ca Precedence: bulk Reply-To: Andrej Bauer Message-Id: Status: O X-Status: X-Keywords: X-UID: 7 I thank eveyone who answered my question so quickly. For reference I post a summary of the answers. Bill Lawvere answered that "the theory of a monad is just that of ordinal addition of 1 on the augmented simplicial category Delta considered as a (non-commutative) monoidal category wrt ordinal addition." A relevant reference in this regard is his "Ordinal Sums and Equational Doctrines" which was part of the Zurich Triples Book, available online as TAC Reprints 18. Similarly, Jaap van Oosten pointed out that the free "monad on a category" on one generator is the simplicial category \Delta (nonempty finite ordinals and monotone functions). It follows from these observations that the theory of a monad is decidable. Todd Wilson kindly pointed me to a thesis by Wolfgang Gehrke, see http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.7087 , which contains a complete set of rewrite rules (page 40, Proposition 20) for the theory of a monad: id f ==> f f id ==> f (f g) h ==> f (g h) eta* ==> id f* eta ==> f f* g* ==> (f* g)* f* (eta g) ==> f g f* (g* h) ==> (f* g)* h The last two rules are extra, compared to the original equations. So the next time you wonder whether an equation holds of a general monad, just use the above rewrite rules on both sides of the equation. With kind regards, Andrej [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Thu Jun 4 21:09:33 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 04 Jun 2009 21:09:33 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MCMzA-0006S7-Tt for categories-list@mta.ca; Thu, 04 Jun 2009 21:08:40 -0300 From: "Ronnie Brown" To: "Hasse Riemann" , Subject: categories: Re: Famous unsolved problems in ordinary category theory Date: Wed, 3 Jun 2009 21:30:17 +0100 MIME-Version: 1.0 Content-Type: text/plain;format=flowed;charset="iso-8859-1";reply-type=original Content-Transfer-Encoding: 7bit Sender: categories@mta.ca Precedence: bulk Reply-To: "Ronnie Brown" Message-Id: Status: O X-Status: X-Keywords: X-UID: 8 In reply to Hasse Riemann's question (see below): I remember being asked this kind of question at a Topology conference in Baku in 1987. It is worth discussing the background to this, as someone who has never gone for a `famous problem', but found myself trying to develop some mathematics to express some basic intuitions. Saul Ulam remarked to me in 1964 at my first international conference (Syracuse, Sicily) that a young person may feel the most ambitious thing to do is to tackle a famous problem; but this may distract that person from developing the mathematics most appropriate to them. It was interesting that this remark came from someone as good as Ulam! G.-C. Rota writes in `Indiscrete thoughts' (1997): What can you prove with exterior algebra that you cannot prove without it?" Whenever you hear this question raised about some new piece of mathematics, be assured that you are likely to be in the presence of something important. In my time, I have heard it repeated for random variables, Laurent Schwartz' theory of distributions, ideles and Grothendieck's schemes, to mention only a few. A proper retort might be: "You are right. There is nothing in yesterday's mathematics that could not also be proved without it. Exterior algebra is not meant to prove old facts, it is meant to disclose a new world. Disclosing new worlds is as worthwhile a mathematical enterprise as proving old conjectures. " It is like the old military question: do you make a frontal attack; or find a way of rendering the obstacle obsolete? I was early seduced (see my first two papers) by the idea of looking for questions satisfying 3 criteria: 1) no-one had previously asked it; 2) the question was technically easy to answer; 3) the answer was important. Usually it has been 2) which failed! Of course you do not find such questions where everyone is looking! It could be interesting to investigate how such questions arise, perhaps by pushing a point of view as far as it will go, or seeing a new analogy. "If at first, the idea is not absurd, then there is no hope for it." Albert Einstein It could be interesting to investigate historically: if (let us suppose) category theory has advanced without a fund of famous open problems, how then has it advanced? One aim of mathematics is understanding, making difficult things easy, seeing why something is true. Thus improved exposition is an important part of the progress of mathematics (even if this is ignored by Research Assessment Exercises). R. Bott said to me (1958) that Grothendieck was prepared to work very hard to make something tautological. By contrast, a famous algebraic topologist replied to a question of mine about his graduate text by asking: `Is the function not continuous?' He never gave me a proof! And I never found it! (Actually the function was not well defined, but that I could fix!) Grothendieck wrote to me in 1982: `The introduction of the cipher 0 or the group concept was general nonsense too, and mathematics was more or less stagnating for thousands of years because nobody was around to take such childish steps ...'. See also http://www.bangor.ac.uk/~mas010/Grothendieck-speculation.html The point I am trying to make is that the question on `open problems' raises issues on the nature of, on professionalism in, and so on the methodology of, mathematics. It is a good question to start with. Hope that helps. Ronnie Brown ----- Original Message ----- From: "Hasse Riemann" To: "Category mailing list" Sent: Tuesday, June 02, 2009 5:31 PM Subject: categories: Famous unsolved problems in ordinary category theory Hello categorists I don't know what to make of the silence to my question. This is the easiest question i have. I can't believe it is so difficult. It is not like i am asking you to solve the problems. There must be some important open problems in ordinary category theory. There are plenty of them in the theory of algebras and in representation theory, so there should be more of them in category theory. Especially if you broaden the boundaries a bit of what ordinary category theory is. Take for instance: model categories, categorical logic, categorical quantization, topos theory-locales-sheaves. But i had originally pure category theory in mind. Best regards Rafael Borowiecki [For admin and other information see: http://www.mta.ca/~cat-dist/ ] -------------------------------------------------------------------------------- No virus found in this incoming message. Checked by AVG - www.avg.com Version: 8.5.339 / Virus Database: 270.12.51/2151 - Release Date: 06/02/09 17:53:00 [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Thu Jun 4 21:09:33 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 04 Jun 2009 21:09:33 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MCMxT-0006Ni-9H for categories-list@mta.ca; Thu, 04 Jun 2009 21:06:55 -0300 MIME-Version: 1.0 Date: Wed, 3 Jun 2009 11:45:09 -0500 Subject: categories: Re: Famous unsolved problems in ordinary category theory From: Michael Shulman To: Hasse Riemann , Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Sender: categories@mta.ca Precedence: bulk Reply-To: Michael Shulman Message-Id: Status: O X-Status: X-Keywords: X-UID: 9 Probably people are going to jump on me for saying this, but it seems to me that category theory is different from much of mathematics in that often the difficulty is in the definitions rather than the theorems, and in the questions rather than the answers. Thus, there are probably many unsolved problems in category theory, but we don't know what they are yet, because figuring out what they are is the main aspect of them that is unsolved. (-: Mike On Tue, Jun 2, 2009 at 11:31 AM, Hasse Riemann wrote: > > > > Hello categorists > > I don't know what to make of the silence to my question. > This is the easiest question i have. I can't believe it is so difficult. > It is not like i am asking you to solve the problems. > > There must be some important open problems in ordinary category theory. > There are plenty of them in the theory of algebras and > in representation theory, so there should be more of them in category theory. > > Especially if you broaden the boundaries a bit of what ordinary category theory is. > Take for instance: > model categories, > categorical logic, > categorical quantization, > topos theory-locales-sheaves. > But i had originally pure category theory in mind. > > Best regards > Rafael Borowiecki > > > [For admin and other information see: http://www.mta.ca/~cat-dist/ ] > [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Thu Jun 4 21:10:14 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 04 Jun 2009 21:10:14 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MCN0d-0006YW-2I for categories-list@mta.ca; Thu, 04 Jun 2009 21:10:11 -0300 Date: Thu, 04 Jun 2009 08:29:11 +1000 Subject: categories: Re: Decidability of the theory of a monad From: Steve Lack To: Andrej Bauer , Mime-version: 1.0 Content-type: text/plain; charset="US-ASCII" Content-transfer-encoding: 7bit Sender: categories@mta.ca Precedence: bulk Reply-To: Steve Lack Message-Id: Status: O X-Status: X-Keywords: X-UID: 10 Dear Andrej, The free monad on a category has a well-known simple concrete description. Let Ordf be the category of finite ordinals and order-preserving maps. --> 0 --> 1 <-- 2 ... --> (This is sometimes called the algebraicist's simplicial category - it contains the topologist's simplicial category as the full subcategory of non-empty finite ordinals. Ordf is simply called Delta in Categories for the Working Mathematician.) Ordinal sum makes Ordf into a strict monoidal category. The object 1 is a monoid in this monoidal category, and in fact is the "free monoid in a monoidal category", in the sense that for any strict monoidal category C, there is a bijection between monoids in C and strict monoidal functors from Ordf to C. (There is also a non-strict version of this fact.) The free "category with a monad" on a category A is the Ordf x A, with monad having endofunctor part (n,a) |-> (n+1,a), with the obvious multiplication. More generally, the monoidal category Ordf can be regarded as a one-object 2-category mnd, and 2-functors mnd-->K for a 2-category K, are in bijection with monads in K. Freely adding a monad to an object of K can be seen as left Kan extension along the unique 2-functor 1-->mnd. Regards, Steve Lack. On 3/06/09 9:10 PM, "Andrej Bauer" wrote: > Consider the theory of a monad, i.e., the axioms are those of a > category and a monad given as a triple: an operation T on objects, for > each object A a morphism eta_A : A -> T A, and an operation lift_{A,B} > which maps morphisms f : A -> T B to lift f : T A -> T B. Concretely, > the axioms are (where lift f is written f* and composition is > juxtaposition): > > id f = f > f id = f > (f g) h = f (g h) > eta* = id > f* eta = f > (f* g)* = f* g* > > Presumably, the equational theory (with partial operations) of such a > triple is decidable. Is this known? If we ignore the types and > partiality, we can attempt to turn the above equations into a > confluent terminating rewrite system using the Knuth-Bendix algorithm, > but it gets stuck (on various orderings I tried). > > A more categorical way of asking the same question is: what is a > concrete description of the free "monad on a category" (is this the > same as "free monad" on "free category"?). > > With kind regards, > > Andrej > > [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Thu Jun 4 21:11:34 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 04 Jun 2009 21:11:34 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MCN1u-0006eI-DI for categories-list@mta.ca; Thu, 04 Jun 2009 21:11:30 -0300 Date: Thu, 04 Jun 2009 11:52:16 +0200 From: Sergey Goncharov MIME-Version: 1.0 To: categories@mta.ca Subject: categories: Re: Decidability of the theory of a monad Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: quoted-printable Sender: categories@mta.ca Precedence: bulk Reply-To: Sergey Goncharov Message-Id: Status: O X-Status: X-Keywords: X-UID: 11 Hi! not touching the partiality issue the answer to the question about=20 decidability is positive. Decidability follows from the results, proved=20 in our paper "Kleene Monads: Handling Iteration in a Framework of=20 Generic Effects", accepted for the upcoming CALCO conference. The paper=20 should be soon available on my homepage:=20 http://www.informatik.uni-bremen.de/~sergey/papers_e.htm It does contain a confluent and strongly normalising rewrite system but=20 the proof details will show up (hopefully) only in the journal version.=20 The proofs are also included into my PhD thesis, which is under=20 development and thus still unpublished but in case of interest I can=20 make available some parts of it containing the proofs under discussion. Best regards, -------------------------------------- Sergey Goncharov Junior Researcher DFKI Bremen=09 Safe and Secure Cognitive Systems Cartesium, Enrique-Schmidt-Str. 5 D-28359 Bremen phone: +49-421-218-64276 Fax: +49-421-218-9864276 mail: Sergey.Goncharov@dfki.de www.dfki.de/sks/staff/sergey -------------------------------------- ------------------------------------------------------------- Deutsches Forschungszentrum f=C3=BCr K=C3=BCnstliche Intelligenz GmbH Firmensitz: Trippstadter Strasse 122, D-67663 Kaiserslautern Gesch=C3=A4ftsf=C3=BChrung: Prof. Dr. Dr. h.c. mult. Wolfgang Wahlster (Vorsitzender) Dr. Walter Olthoff Vorsitzender des Aufsichtsrats: Prof. Dr. h.c. Hans A. Aukes Amtsgericht Kaiserslautern, HRB 2313 ------------------------------------------------------------- [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Thu Jun 4 21:12:12 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 04 Jun 2009 21:12:12 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MCN2W-0006hQ-88 for categories-list@mta.ca; Thu, 04 Jun 2009 21:12:08 -0300 Date: Thu, 04 Jun 2009 11:59:12 +0100 From: Steve Vickers MIME-Version: 1.0 To: Andrej Bauer , Subject: categories: Re: Decidability of the theory of a monad Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit Sender: categories@mta.ca Precedence: bulk Reply-To: Steve Vickers Message-Id: Status: O X-Status: X-Keywords: X-UID: 12 Dear Andrej, It seems to me that the monad-on-a-category freely generated by one object should be the simplicial category Delta, following from the facts that Delta contains the universal monoid and a monad on C is a monoid in C^C - see Mac Lane Cats for Working Mathematician Section VII.5, VII.6. The object n of Delta will correspond to T^n(X) where T is the (functor for the) monad and X the generating object. If I've got that right then I would presume it's already known and proved carefully somewhere. After that, the monad-on-a-category freely generated by a category C would seem to be CxDelta. (Object (X,n) represents T^n(X), morphism (f,s): (X,m) -> (Y,n) corresponds to T^m(f);s(Y): T^m(X) -> T^m(Y) -> T^n(Y) and using naturality of T to deduce that s(Y);T^n(g) = T^m(g);s(Z) so the f's can always be shunted to the left.) Again, if I've got that right then it wouldn't surprise me to find it's already known. This would suggest that C |-> CxDelta is a monad on Cat. Then a monad on C is a structure morphism CxDelta -> C, i.e. Delta -> C^C with appropriate properties, which looks like a monoid in C^C, which we knew already. I don't know Knuth-Bendix well enough to understand the issues there. But since you mention various orderings, that reminds me of Freyd's trick in "essentially algebraic" presentations of these cartesian theories. (Amongst theories of partial operators, it is the cartesian theories that have good universal algebraic properties.) That involves ordering the operators so that, for each one, its domain of definition is defined by equations involving "earlier" operators. (Ultimately that comes down to total operators, for which no equations are needed.) Then the equations s = t are understood in the sense "if s and t are both defined, then they are equal". I don't know if that can be accommodated in Knuth-Bendix as it stands. In particular, I don't know how amenable K-B is to incorporating conditional rewrites. Conditional equations seem inevitable in cartesian theories; the essentially algebraic formulation reduces them to definedness explicitly conditional on equations, and equations implicitly conditional on definedness. You might want to look at my paper with Palmgren, which unifies them by identifying definedness with self-equality. You ask whether a free "monad on a category" is the same as a "free monad" on "free category". Of course, in using the word "free" one ought to be careful what kind of structure these are free over, but generally speaking if the forgetful functors compose then so will their left adjoints, the free functors. Best wishes, Steve. Andrej Bauer wrote: > Consider the theory of a monad, i.e., the axioms are those of a > category and a monad given as a triple: an operation T on objects, for > each object A a morphism eta_A : A -> T A, and an operation lift_{A,B} > which maps morphisms f : A -> T B to lift f : T A -> T B. Concretely, > the axioms are (where lift f is written f* and composition is > juxtaposition): > > id f = f > f id = f > (f g) h = f (g h) > eta* = id > f* eta = f > (f* g)* = f* g* > > Presumably, the equational theory (with partial operations) of such a > triple is decidable. Is this known? If we ignore the types and > partiality, we can attempt to turn the above equations into a > confluent terminating rewrite system using the Knuth-Bendix algorithm, > but it gets stuck (on various orderings I tried). > > A more categorical way of asking the same question is: what is a > concrete description of the free "monad on a category" (is this the > same as "free monad" on "free category"?). > > With kind regards, > > Andrej > > > [For admin and other information see: http://www.mta.ca/~cat-dist/ ] [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Fri Jun 5 14:04:59 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 05 Jun 2009 14:04:59 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MCcqB-0007Xq-T1 for categories-list@mta.ca; Fri, 05 Jun 2009 14:04:27 -0300 Date: Thu, 4 Jun 2009 21:53:10 -0400 From: tholen@mathstat.yorku.ca To: Michael Shulman , categories@mta.ca, Subject: categories: Re: Famous unsolved problems in ordinary category theory MIME-Version: 1.0 Content-Type: text/plain;charset=ISO-8859-1; format="flowed" Content-Disposition: inline Content-Transfer-Encoding: 7bit Sender: categories@mta.ca Precedence: bulk Reply-To: tholen@mathstat.yorku.ca Message-Id: Status: RO X-Status: X-Keywords: X-UID: 13 Finding the "right" questions and notions is certainly a prominent theme in category theory, perhaps more prominently than in other fields. Still, just like in other fields, solving open problems was always part of the agenda. For example, half a century ago people asked whether every "standard construction" (=monad) is induced by an adjunction, and it took a few years to have two interesting answers. And there is ceratinly a string of examples leading all the way to today. I don't know whether there are any >famous< unsolved problems in ordinary category theory, but there are certainly non-trivial questions. Here is one that we formulated in an article with Reinhard B"orger (Can. J. Math 42 (1990) 213-229) two decades ago: A category A is total (Street-Walters) if its Yoneda embedding A ---> Set^{A^{op}} has a left adjoint. Then 1. A has small colimits, and 2. any functor A-->B that preserves all existing colimits of A has a right adjoint. Do properties 1 and 2 imply totality for A? I must admit that, after formulating the question we never considered it again, so there may well be a known or quick answer. So don't hold back please, especially since I plan to incorporate several questions of this type in my CT09 talk. Walter. Quoting Michael Shulman : > Probably people are going to jump on me for saying this, but it seems to > me that category theory is different from much of mathematics in that > often the difficulty is in the definitions rather than the theorems, and > in the questions rather than the answers. Thus, there are probably many > unsolved problems in category theory, but we don't know what they are > yet, because figuring out what they are is the main aspect of them > that is unsolved. (-: > > Mike > [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Fri Jun 5 14:04:59 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 05 Jun 2009 14:04:59 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MCcpH-0007Tv-Vc for categories-list@mta.ca; Fri, 05 Jun 2009 14:03:32 -0300 From: Hasse Riemann To: Category mailing list Subject: categories: unsolved problems Date: Fri, 5 Jun 2009 01:25:12 +0000 MIME-Version: 1.0 Content-Type: text/plain; charset="windows-1256" Content-Transfer-Encoding: quoted-printable Sender: categories@mta.ca Precedence: bulk Reply-To: Hasse Riemann Message-Id: Status: O X-Status: X-Keywords: X-UID: 14 =20 Hello categorists =20 To those who have replied on my question and others. =20 First i want to thank for the suggestions of problems. =20 Since i am new here some people assume that i seek a problem to solve so = i can quickly become famous. I am in fact much more interested in the structure and foundation of math= ematics than solving math problems. I just felt i should know these problems since they are fa= mous, but almost none came to mind. =20 A reason for this is that the proofs i have seen have mostly been "not wa= ter tight", they miss some things (mostly in the logic). And, they are not spelled out in full but are very "cut down" in their ar= guments. This makes them too time consuming to follow. I don't want to read a proof to recreate half of it = but to understand why something is true. =20 "A mathematical theory is not to be considered complete until you have ma= de it so clear that you can explain it to the first man whom you meet on = the street" -David Hilbert =20 I argue that the same is true for proofs. Something to think about next t= ime you write a proof. =20 In Dyson Freemans terminology i am a bird and not a frog. As a bird i mus= t say that it is sad that about 90% of mathematicians are frogs. This giv= e an inbalance in mathematics. =20 To answer Michael Shulman: Yes, there is something different about category theory. It is at the top= of mathematics. A perfect place for a bird :) =20 Now to my question. =20 After some intensive work and help from people on the mailing list i have= found some problems that are interesting in ordinary category theory :) =20 You just have to learn to see them. Some won't be stated even as problems= to solve. =20 To illustrate my point: How many categories of n objects are there up to categorical equivalence = for n a natural number? If it can not be given directly, can it be expressed by other counting fu= nctions? Maby the pattern is easier than that for groups. =20 A simplified version of the problem is to count only finite categories wi= th at most 1 morphism between any objects. This suggests the NC(r,s)-problem: What is the number of categories with r objects and at most s morphisms (= in one direction) between any two objects. =20 Specialized versions of these are to count model categories, toposes (def= ined as categories and not as 2-categories),... Correct me if it is not so, but i don't know of any theorem that model ca= tegories or toposes must be infinite. =20 Another example first stated by John Baez that i call the no-go quantizat= ion conjecture: There is no functor from the symplectic category (symplectic manifolds an= d symplectomorphisms) to the Hilbert category (Hilbert spaces and unitary= operators) that preserves positivity. I.e. a one-parameter group of symp= lectic transformations generated by a positive Hamiltonian is mapped to a= one-parameter group of unitary operators with a positive generator. =20 That maby helps to find the problems. Not that i am trying to popularize = them. If you know some you can still e-mail them to me. =20 Now from the question to the mysterious Hasse Riemann! =20 It seems that people wonder about me so here i go. This is written from a 15 year old gymnasium account from the time of the= beginning of internet. Bernhard Riemann was my hero then because of riemannian geometry and riem= ann surfaces. Actually i have still not managed to replace Riemann! Hasse is just a name that i think fits me more than Rafael. Since everyone i e-mail knows me by this pseudo i have decided not to cha= nge it. =20 It took me 20 years of studying mathematics to find category theory. It is a long time but it was hardly wasted time. I actually went into category theory 3 times before (not so deep), but no= t until this fourth time i understood what category theory really is and that it is precisely what= i was looking for :) ,and hence decided to stay here for a long while. The first year in category theory went with a blazing speed. Now, a half year after that i have more questions than facts. I happen to be seated in Stockholm. It is not a bad place but there are n= o category theorists in Sweden! Hence i'm counting on you people. =20 Best regards Rafael Borowiecki =20 [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Fri Jun 5 14:05:06 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 05 Jun 2009 14:05:06 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MCcql-0007an-Kt for categories-list@mta.ca; Fri, 05 Jun 2009 14:05:03 -0300 From: Hasse Riemann To: Category mailing list Subject: categories: Re: Famous unsolved problems in ordinary category theory Date: Fri, 5 Jun 2009 02:42:52 +0000 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Sender: categories@mta.ca Precedence: bulk Reply-To: Hasse Riemann Message-Id: Status: O X-Status: X-Keywords: X-UID: 15 =20 Dear Ronnie =20 This is what stuck with me from the e-mail =20 > One aim of mathematics is understanding=2C making difficult things easy= =2C > seeing why something is true. Thus improved exposition is an important pa= rt > of the progress of mathematics (even if this is ignored by Research > Assessment Exercises).=20 =20 Indeed they don't teach you this at the university=2C but somehow i always = knew it. It was obvious from the start=2C then i had to resist everyone trying to te= ll me otherwise. I am glad that there are other who see this as well. =20 > Grothendieck wrote to me in 1982: `The introduction of the cipher 0 or th= e > group concept was general nonsense too=2C and mathematics was more or les= s > stagnating for thousands of years because nobody was around to take such > childish steps ...'. =20 I like this quote since i like structuralizing mathematics. Something to think about if you want to take the next step. Fill in the void with a precise mathematical void. =20 Best regards Rafael Borowiecki [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Fri Jun 5 14:06:13 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 05 Jun 2009 14:06:13 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MCcrp-0007gs-DY for categories-list@mta.ca; Fri, 05 Jun 2009 14:06:09 -0300 Date: Thu, 4 Jun 2009 22:54:45 -0400 From: John Iskra MIME-Version: 1.0 To: Ronnie Brown Subject: categories: Re: Famous unsolved problems in ordinary category theory Content-Type: text/plain; charset="ISO-8859-1"; format=flowed Content-Transfer-Encoding: 7bit Sender: categories@mta.ca Precedence: bulk Reply-To: John Iskra Message-Id: Status: O X-Status: X-Keywords: X-UID: 16 One of my favorite quotes: The question you raise ``how can such a formulation lead to computations'' doesn't bother me in the least! Throughout my whole life as a mathematician, the possibility of making explicit, elegant computations has always come out by itself, as a byproduct of a thorough conceptual understanding of what was going on. Thus I never bothered about whether what would come out would be suitable for this or that, but just tried to understand -- and it always turned out that understanding was all that mattered. A. Grothendieck Raoul Bott reinforced this in a talk I had the privilige to hear back in 98. He said that mathematics, done well, never required the placing of your oar in the water (he probably put it better than that...). The idea I think is that if you continually ask and answer the questions that occur to you, and, thus, gain understanding, then you will inevitably make progress. And that is what matters, really. So often the person credited with solving a 'famous' problem only takes the final step in a hard journey of a thousand miles made by a thousand others. Glory and fame - such as it is in the world of mathematics - are nice, but they are not, in the end, mathematics. I think it is of high importance to avoid confusing them. John Iskra Ronnie Brown wrote: > In reply to Hasse Riemann's question (see below): > > I remember being asked this kind of question at a Topology conference in > Baku in 1987. It is worth discussing the background to this, as someone who > has never gone for a `famous problem', but found myself trying to develop > some mathematics to express some basic intuitions. > > Saul Ulam remarked to me in 1964 at my first international conference > (Syracuse, Sicily) that a young person may feel the most ambitious thing to > do is to tackle a famous problem; but this may distract that person from > developing the mathematics most appropriate to them. It was interesting that > this remark came from someone as good as Ulam! > ... > > > > > > > > ----- Original Message ----- > From: "Hasse Riemann" > To: "Category mailing list" > Sent: Tuesday, June 02, 2009 5:31 PM > Subject: categories: Famous unsolved problems in ordinary category theory > > > > > > Hello categorists > > I don't know what to make of the silence to my question. > This is the easiest question i have. I can't believe it is so difficult. > It is not like i am asking you to solve the problems. > > There must be some important open problems in ordinary category theory. > There are plenty of them in the theory of algebras and > in representation theory, so there should be more of them in category > theory. > > Especially if you broaden the boundaries a bit of what ordinary category > theory is. > Take for instance: > model categories, > categorical logic, > categorical quantization, > topos theory-locales-sheaves. > But i had originally pure category theory in mind. > > Best regards > Rafael Borowiecki > > > [For admin and other information see: http://www.mta.ca/~cat-dist/ ] > > > -------------------------------------------------------------------------------- > > > > No virus found in this incoming message. > Checked by AVG - www.avg.com > Version: 8.5.339 / Virus Database: 270.12.51/2151 - Release Date: 06/02/09 > 17:53:00 > > > > [For admin and other information see: http://www.mta.ca/~cat-dist/ ] > . > > [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Fri Jun 5 14:06:49 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 05 Jun 2009 14:06:49 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MCcsQ-0007kj-A1 for categories-list@mta.ca; Fri, 05 Jun 2009 14:06:46 -0300 MIME-Version: 1.0 Date: Thu, 4 Jun 2009 21:10:14 -0700 Subject: categories: Famous unsolved problems in ordinary category theory From: John Baez To: categories Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit Sender: categories@mta.ca Precedence: bulk Reply-To: John Baez Message-Id: Status: O X-Status: X-Keywords: X-UID: 17 Rafael Borowiecki wrote: > I don't know what to make of the silence to my question. > This is the easiest question i have. I can't believe it is so difficult. > It is not like i am asking you to solve the problems. > > There must be some important open problems in ordinary category theory. I think the reason for the silence is that category theory is a bit different than other branches of mathematics. Other branches of mathematics get very excited about patterns that may exist, but may not. So when mathematicians hear the phrase "famous unsolved problems", that's the sort of thing that comes to mind: for example, Goldbach's conjecture, the twin prime conjecture, the Riemann hypothesis or the Hodge conjecture. On the other hand, category theorists tend to get excited about taking already partially understood patterns in mathematics and making them very clear. So, the most important open problems often aren't of the form "Is this statement true or false?" Instead, they tend to be a bit more open-ended, like "Develop a workable theory of n-categories." So, they don't have names. I've tried to encourage people to work on n-categories by emphasizing five "hypotheses": the homotopy hypothesis, the stabilization hypothesis, the cobordism hypothesis, the tangle hypothesis, and the generalized tangle hypothesis. I didn't want to call them "conjectures", because they're a bit open-ended. But they're precise enough that someone can claim to have proved one, and people can probably agree on whether this has occurred. For example, Jacob Lurie claims to have proved the cobordism hypothesis: http://arxiv.org/abs/0905.0465 http://lab54.ma.utexas.edu:8080/video/lurie.html and when he provides the full details, people should be able to decide if he has. Best, jb [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Fri Jun 5 14:08:44 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 05 Jun 2009 14:08:44 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MCcuF-0000CY-HN for categories-list@mta.ca; Fri, 05 Jun 2009 14:08:39 -0300 Mime-Version: 1.0 (Apple Message framework v624) Content-Type: text/plain; charset=US-ASCII; format=flowed Content-Transfer-Encoding: 7bit From: Paul Taylor Subject: categories: Famous unsolved problems in ordinary category theory Date: Fri, 5 Jun 2009 09:41:32 +0100 To: Categories list Sender: categories@mta.ca Precedence: bulk Reply-To: Paul Taylor Message-Id: Status: O X-Status: X-Keywords: X-UID: 18 Rafael Borowiecki, under the alias Hasse Riemann, asked, > Are there any famous unsolved problems in category theory? Ronnie Brown's posting in response to this is a classic, and deserves to be printed out and pinned up in every graduate student's office! I particularly like the military analogy with the choice between a frontal assault and making the obstacle obsolete. The following point is especially important: > I was early seduced (see my first two papers) by the idea of > looking for questions satisfying 3 criteria: > 1) no-one had previously asked it; > 2) the question was technically easy to answer; > 3) the answer was important. > **** Usually it has been 2) which failed! **** I sent (a version of) the following reply to "categories" when Rafael first asked the question, but then asked Bob to withdraw it as I thought I could write it better. I put off doing so because other topics were under discussion, but by his posting Ronnie has obliged me to send it, since otherwise I would just be a chicken. So here goes: Do I hear taunts of "do you have a Fields Medal?"? These are a bit like those of "do you have a girlfriend?". Well, no, I admit it. I don't. I have a boyfriend (Richard), and some of you have met him. If you bear with me, you will see that this is not a completely frivolous answer, even though it is a personal one. My point is that there are analogies between being a gay man and being a conceptual--constructive mathematician: - They both involve long periods of self-doubt and pretence in the face of real and perceived discrimation. This is very much still real in the mathematical case, as evidenced by that fact that categorists and consructivists are largely to be found in computer science departments, excluded from mathematics in case they might corrupt the youth. - The result of this is a significantly delayed adolescence -- I have met gay men going through adolescence in the 50s or 70s. - Finally, there is pride in being who you are, and the recognition of "Honi soit qui mal y pense" -- that it is the people who think ill of it that have the problem. In the words of a song from "La Cage aux Folles" that is known as the "sweet potato song", "I yam what I yam!". Before I came out as a categorist, I pretended to be interested in difficult puzzles, I was in the British team in the International Mathematical Olympiad in 1979, but didn't do very well. I started a magazine called QARCH, whose total output in 30 years amounts to less than one of my papers now. I was taught as an undergraduate by the Hungarian analyst and graph theorist Bela Bollobas. He set problems for first year students problems that took three weeks to solve, if at all. (Bela is a mathematician of considerable stature -- so great that it took me five years to notice that he is 10cm shorter than me -- and I remember him with great affection, in case he gets to read this.) However, I hope that Bela (along with Andrej Bauer, Imre Leader and Dorette Pronk, who help organise IMO things in Slovenia, Britain and Canada nowadays), will forgive me if I say that there is something fundamentally unsatisfying about IMO problems. Once you have the solution, that is it. They are like crosswords or jigsaws or sudoku. After that I had my delayed adolescence (with an unsuitable boyfriend). I studied continuous posets instead of algebraic ones and categories instead of posets, just to show that I could. Somebody should have told me to get a proper job as a programmer, but they didn't have the guts to say it to me. (If graduate students ask me for advice nowadays, I do tell them to get proper jobs, and not surprisingly they (mis)interpret this personally.) Long after this, the first paper on Abstract Stone Duality was published on my 40th birthday, more or less. According to G H Hardy's depressing "Mathematician's Apology", and to the rules for getting a Fields Medal, I was officially finished as a mathematician. But it is pretty clear that I have been doing my best mathematics during my fifth decade. On the other hand, all of those gratuitously difficult problems had gone into the mix. Before I return to the question. please refer to number 6 in en.wikipedia.org/wiki/Hilbert's_problems which asks for the axiomatisation of physics. Even in this most famous collection of gratuitously difficult problems, we find a conceptual question. The first of Hilbert's problems is called the "continuum hypothesis", but is about smashing the continuum into dust. Elsewhere, he said "no-one shall expell us from Cantor's Paradise", but I regard it as a dystopia. I dream of some eventual escape, returning to the Euclidean paradise. There we would actually talk about lines, circles, compact subsets or whatever, instead of families of subsets or arcane algebra (or, indeed, category theory). I am looking for a language for mathematics that would look like "set theory" (as mathematicians, not set theorists, perceive it) but would yields computable continua instead of dust. More categorically, I believe that there is some notion of category that is very similar to an elementary topos, but in which all morphisms are continuous (in particular Scott continuous with respect to an intrinsic order). I also believe that these ideas are applicable to other subjects. When I have made the appropriate tools, I hope to be able to understand algebraic geometry, which was a complete mystery to me as a student. I am in princple capable of doing this, BECAUSE I am a categorist, by following the analogy between frames and rings. One version of this problem that I still cannot solve is a question that Eugenio Moggi asked me in April 1993, although I forget the exact words. We wanted a class of monos (I said they should be the equalisers targetted at power of Sigma) that was closed under composition and application of the Sigma^2 functor (ie taking the exponential Sigma^(-) twice). Another is how to embed the category of locales in a CCC WITHOUT using illegitimate presheaves (Vickers and Townsend) or the axiom of collection (Heckmann). When I wrote the original version of this posting a couple of weeks back, I thought I could solve this one. I am still hopeful, but it turns out to be a powerful question, cf Ronnie's (2) above. Notice that I give the principal formulation of the question in vague language, not as a Diophantine equation. The more specific the question, the more likely it is to have been the WRONG one. Asking an impertinent question is the best way of getting a pertinent answer. This still involves very difficult problems and hundreds of journal pages of formal proofs. But for me the problems serve the concepts rather than the other way round. This is the essence of what it is to be a conceptual mathematician. Ronnie Brown has told you a different story of his own, but with the same message. Many other experienced categorists (including the ones in higher dimensions, which Rafael excluded from his original question, for some reason) would do likewise. What about Fields Medals? People will get them, using my work, two or three generations down the line. Paul Taylor [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Fri Jun 5 14:09:22 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 05 Jun 2009 14:09:22 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MCcur-0000HW-0l for categories-list@mta.ca; Fri, 05 Jun 2009 14:09:17 -0300 From: Thorsten Altenkirch To: categories List Content-Type: text/plain; charset=US-ASCII; format=flowed; delsp=yes Content-Transfer-Encoding: 7bit Mime-Version: 1.0 (Apple Message framework v930.3) Subject: categories: Re: Decidability of the theory of a monad Date: Fri, 5 Jun 2009 09:58:21 +0100 Sender: categories@mta.ca Precedence: bulk Reply-To: Thorsten Altenkirch Message-Id: Status: O X-Status: X-Keywords: X-UID: 19 Hi, Sam Lindley and Ian Stark proved that Moggi's computational Metalanguage (\lambda_ML) is decidable - this is simply typed lambda calculus with a monad. If I am not mistaken your theory can be faithfully encoded in \lambda_ML. Actually, isn't it the case that the continuation monad is actually the free monad. Hence, using this result decidability of \lambda_ML should follow from the decidability of simply typed lambda calculus. Cheers, Thorsten http://www.springerlink.com/content/y44yn0fg76dthfnn/ On 3 Jun 2009, at 12:10, Andrej Bauer wrote: > Consider the theory of a monad, i.e., the axioms are those of a > category and a monad given as a triple: an operation T on objects, for > each object A a morphism eta_A : A -> T A, and an operation lift_{A,B} > which maps morphisms f : A -> T B to lift f : T A -> T B. Concretely, > the axioms are (where lift f is written f* and composition is > juxtaposition): > > id f = f > f id = f > (f g) h = f (g h) > eta* = id > f* eta = f > (f* g)* = f* g* > > Presumably, the equational theory (with partial operations) of such a > triple is decidable. Is this known? If we ignore the types and > partiality, we can attempt to turn the above equations into a > confluent terminating rewrite system using the Knuth-Bendix algorithm, > but it gets stuck (on various orderings I tried). > > A more categorical way of asking the same question is: what is a > concrete description of the free "monad on a category" (is this the > same as "free monad" on "free category"?). > > With kind regards, > > Andrej [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Fri Jun 5 14:10:30 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 05 Jun 2009 14:10:30 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MCcvw-0000P3-WA for categories-list@mta.ca; Fri, 05 Jun 2009 14:10:25 -0300 From: "Ronnie Brown" To: "John Iskra" , Subject: categories: Re: Famous unsolved problems in ordinary category theory Date: Fri, 5 Jun 2009 12:07:17 +0100 MIME-Version: 1.0 Content-Type: text/plain;format=flowed;charset="iso-8859-1";reply-type=original Content-Transfer-Encoding: 7bit Sender: categories@mta.ca Precedence: bulk Reply-To: "Ronnie Brown" Message-Id: Status: RO X-Status: X-Keywords: X-UID: 20 John, Glad you liked it! Thanks for the references to Raoul Bott. Mind you there was a serious point: how to turn abstract mathematics into machine computation? I have discussed this often with Larry Lambe. Ronnie ----- Original Message ----- From: "John Iskra" To: "Ronnie Brown" Cc: "Hasse Riemann" ; Sent: Friday, June 05, 2009 3:54 AM Subject: Re: categories: Re: Famous unsolved problems in ordinary category theory > One of my favorite quotes: > > The question you raise ``how can such a formulation lead to > computations'' doesn't bother me in the least! Throughout my whole life > as a mathematician, the possibility of making explicit, elegant > computations has always come out by itself, as a byproduct of a thorough > conceptual understanding of what was going on. Thus I never bothered > about whether what would come out would be suitable for this or that, > but just tried to understand -- and it always turned out that > understanding was all that mattered. > > A. Grothendieck > > > Raoul Bott reinforced this in a talk I had the privilige to hear back in > 98. He said that mathematics, done well, never required the placing of > your oar in the water (he probably put it better than that...). The > idea I think is that if you continually ask and answer the questions > that occur to you, and, thus, gain understanding, then you will > inevitably make progress. And that is what matters, really. So often > the person credited with solving a 'famous' problem only takes the final > step in a hard journey of a thousand miles made by a thousand others. > > Glory and fame - such as it is in the world of mathematics - are nice, > but they are not, in the end, mathematics. I think it is of high > importance to avoid confusing them. > > John Iskra > [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Fri Jun 5 14:11:02 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 05 Jun 2009 14:11:02 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MCcwV-0000SF-4y for categories-list@mta.ca; Fri, 05 Jun 2009 14:10:59 -0300 From: Thomas Streicher Date: Fri, 5 Jun 2009 16:17:01 +0200 To: Hasse Riemann , categories@mta.ca Subject: categories: Re: Famous unsolved problems in ordinary category theory MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Sender: categories@mta.ca Precedence: bulk Reply-To: Thomas Streicher Message-Id: Status: O X-Status: X-Keywords: X-UID: 21 Dear Rafael, here is a list of problems from categorical logic that I find difficult to solve and don't know the answer yet. Certainly they are more on the logical side but categories are involved in all of them. I don't claim that these problems are generally important for category theory but they simply do bother me. I write this mail to show that there are technically hard problems and with the salient hope that someone may come up with an answer. Nevertheless I am aware that the subsequent list of problems might easly get a prize for the "best collection of most misleading problems". (1) In their booklet "Algebraic Set Theory" Joyal and Moerdijk defined for every strongly inaccessible cardinal \kappa a class of \kappa-small maps inside the effective topos. Does there exist a "generic" \kappa-small map such that all other maps can be obtained as pullbacks from this generic one? In their book the authors show the existence of a weakly generic one but this doesn't imply the existence of a generic one and I suspect there is none. (2) Does there exist a model for Martin-L\"of's Intensional Type Theory which validates Church's Thesis? This question is due to M.Maietti and G.Sambin. Notice that type theory validates the axiom of choice and, accordingly, the statement is much stronger than saying that for every function from N to N there exists a code for an algorithm computing this function. (3) In my habilitation thesis (www.mathematik.tu-darmstadt.de/~streicher/HabilStreicher.pdf) I showed that the sconing of the effective topos (i.e. glueing Gamma : Eff -> Set) gives rise to a model of INTENSIONAL Martin-Loef type theory faithfully reflecting most of the weakness compared to EXTENSIONAL type theory. Martin Hofmann and I showed that the groupoid model refutes the principle UIP saying that all elements of identity types are equal. This has recently generalised to \omega-groupoids by M.Warren and there is recently some activity of constructing models based on abstract homotopy. Can one construct a categorical model model serving both purposes? This is an issue since the groupoid model and related ones constructed more recently have the defect that all types over N are fairly extensional and thus don't do the job which sconing of the effective topos does. (4) Is the realizability model for the polymorphic lambda calculus parametric in the sense of Reynolds? It needn't be realizability over natural numbers. Would be interesting already for some pca! Thomas [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Fri Jun 5 14:45:57 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 05 Jun 2009 14:45:57 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MCdTr-0003ua-VI for categories-list@mta.ca; Fri, 05 Jun 2009 14:45:28 -0300 From: "Ronnie Brown" To: Subject: categories: Nonabelian algebraic topology: full draft Date: Fri, 5 Jun 2009 17:39:39 +0100 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Sender: categories@mta.ca Precedence: bulk Reply-To: "Ronnie Brown" Message-Id: Status: O X-Status: X-Keywords: X-UID: 22 This is to announce that a full hyperref pdf of the current version of = this book is available from=20 www.bangor.ac.uk/r.brown/nonab-a-t-.html (4.2MB, xx+496 pp)=20 Comments welcome; we are aware of minor faults but hope this version = will be useful as a big step towards the final version, and even = stimulate further work!=20 Ronnie Brown [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Sat Jun 6 18:49:13 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 06 Jun 2009 18:49:13 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MD3jd-00032x-2d for categories-list@mta.ca; Sat, 06 Jun 2009 18:47:29 -0300 From: "Ronnie Brown" To: , Subject: categories: Draft of book- apologies Date: Fri, 5 Jun 2009 22:13:34 +0100 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Sender: categories@mta.ca Precedence: bulk Reply-To: "Ronnie Brown" Message-Id: Status: O X-Status: X-Keywords: X-UID: 23 It has been pointed out that I got the url wrong! It should be=20 www.bangor.ac.uk/r.brown/nonab-a-t.html I grow old! I grow old!=20 I wear the bottoms of my trousers rolled.=20 Ronnie Brown=20 [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Sat Jun 6 18:49:13 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 06 Jun 2009 18:49:13 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MD3ip-00030l-1A for categories-list@mta.ca; Sat, 06 Jun 2009 18:46:39 -0300 Date: Fri, 05 Jun 2009 16:36:23 -0400 To: categories@mta.ca From: "Ellis D. Cooper" Subject: categories: Fundamental Theorem of Category Theory? Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Sender: categories@mta.ca Precedence: bulk Reply-To: "Ellis D. Cooper" Message-Id: Status: O X-Status: X-Keywords: X-UID: 24 Dear category theory community, There are Fundamental Theorems of Arithmetic, Algebra, Calculus, and indeed, many more. My question is, What would be candidates for the Fundamental Theorem of Category Theory? Yoneda Lemma comes to my mind. What do you think? Best, Ellis D. Cooper Ellis D. Cooper, Ph.D. 978-546-5228 (LAND) 978-853-4894 (CELL) XTALV1@NETROPOLIS.NET [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Sat Jun 6 18:49:13 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 06 Jun 2009 18:49:13 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MD3kI-00034A-Rf for categories-list@mta.ca; Sat, 06 Jun 2009 18:48:11 -0300 Date: Fri, 05 Jun 2009 16:36:59 -0600 From: Robin Cockett MIME-Version: 1.0 To: Hasse Riemann , Subject: categories: Re: Famous unsolved problems in ordinary category theory Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Sender: categories@mta.ca Precedence: bulk Reply-To: Robin Cockett Message-Id: Status: O X-Status: X-Keywords: X-UID: 25 A student asked them twice "Aren't problems just so nice? They get stuck in your hair And the last one's just so rare .." "Like lice." said they with a grin "Our hair is all gone and thin ... And Categories we espouse Rather than such vermin house!" -very anon [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Sat Jun 6 18:49:40 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 06 Jun 2009 18:49:40 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MD3lg-00038y-SH for categories-list@mta.ca; Sat, 06 Jun 2009 18:49:36 -0300 From: Hasse Riemann To: , Subject: categories: Famous unsolved problems in ordinary category theory Date: Sat, 6 Jun 2009 01:35:11 +0000 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Sender: categories@mta.ca Precedence: bulk Reply-To: Hasse Riemann Message-Id: Status: O X-Status: X-Keywords: X-UID: 26 =20 Hi Paul =20 I still think you are getting me wrong=2C as did Ronnie. But never mind=2C = i am used to it since i don't follow the mainstream science ways to specialize=2C solve pro= blems=2C publish=2C repeat. Yet the problems interest will pass very soon. I now know 19 ordinary categ= ory problems (if you explain this one) vs. at least 23 in higher category theory. This explains why i re= stricted to ordinary categories.=20 =20 >From the good side i should be thankful that you and Ronnie trie to direct = me towards "true mathematics"=2C but i have already found my "true mathematics". A big part of the process t= o get there was precisely to ask own quastions and finding the answers to them. But some people just got= irritated when i asked them questions (in their field!) they didn't have the answer to. =20 > Another is how to embed the category of locales in a CCC WITHOUT > using illegitimate presheaves (Vickers and Townsend) or the axiom > of collection (Heckmann).=20 =20 I don't follow to the end here. Why should presheaves be illegitimate? Then=2C i suppose the axiom of collection is valid at least in the CCC. But what is so bad about the axiom of collection in this case? Do the embedding get bad? =20 Best regards Rafael Borowiecki [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Sat Jun 6 18:50:14 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 06 Jun 2009 18:50:14 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MD3mF-0003B6-GY for categories-list@mta.ca; Sat, 06 Jun 2009 18:50:11 -0300 From: Hasse Riemann To: Category mailing list Subject: categories: Timeline of category theory and related mathematics Date: Sat, 6 Jun 2009 02:31:23 +0000 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Sender: categories@mta.ca Precedence: bulk Reply-To: Hasse Riemann Message-Id: Status: RO X-Status: X-Keywords: X-UID: 27 =20 Hello categorists =20 As a small project many months ago i started http://en.wikipedia.org/wiki/T= imeline_of_category_theory_and_related_mathematics. Not only because there was none but to write a little piece of what i have = learned so others can benefit from it. In fact i often look in it for detai= ls. Since i am not a real expert in category theory (which is huge!) yet=2C= could you see if there are errors=2C inaccuracies=2C bad explanation or wo= rding etc.? It is so sad when you get wrong facts from wikipedia. Just edit= =2C no e-mails needed. Additions are just as good :) =20 At the time there was no nLab. If there was i would maby have written it th= ere. If you want and there is a need to i could start transfering the timeline to nLab. I th= ink you like more to edit nLab than wikipedia. =20 Best Regards Rafael Borowiecki =20 [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Sat Jun 6 18:51:02 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 06 Jun 2009 18:51:02 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MD3mz-0003En-Qi for categories-list@mta.ca; Sat, 06 Jun 2009 18:50:57 -0300 From: "Bhupinder Singh Anand" To: "'Ronnie Brown'" , Subject: categories: Re: Famous unsolved problems in ordinary category theory Date: Sat, 6 Jun 2009 09:29:46 +0530 MIME-Version: 1.0 Content-Type: text/plain;charset="us-ascii" Content-Transfer-Encoding: 7bit Sender: categories@mta.ca Precedence: bulk Reply-To: "Bhupinder Singh Anand" Message-Id: Status: O X-Status: X-Keywords: X-UID: 28 On Friday, June 05, 2009 4:37 PM, Ronnie Brown wrote in categories@mta.ca: RB>> Mind you there was a serious point: how to turn abstract mathematics into machine computation? < Envelope-to: categories-list@mta.ca Delivery-date: Sat, 06 Jun 2009 18:52:27 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MD3oK-0003Ku-6B for categories-list@mta.ca; Sat, 06 Jun 2009 18:52:20 -0300 Date: Sat, 6 Jun 2009 11:18:12 +0200 (CEST) Subject: categories: Re: Famous unsolved problems in ordinary category theory From: soloviev@irit.fr To: "Thomas Streicher" , categories@mta.ca MIME-Version: 1.0 Content-Type: text/plain;charset=utf-8 Content-Transfer-Encoding: quoted-printable Sender: categories@mta.ca Precedence: bulk Reply-To: soloviev@irit.fr Message-Id: Status: O X-Status: X-Keywords: X-UID: 29 Dear All - Here a question related to categorical logic (or categorical proof theory= ) of a very different type. I would like to put it here because it is an illustration of another part of the field and also because it is technically difficult and interesting. It is well known that certain systems of propositional logic have a natural structure of free category for certain classes of categories with structure. For example, we have a structure of free Symmetric Monoidal Closed Category on the Intuitionistic Multiplicative Linear Logic. In thi= s structure formulas are objects and equivalence classes of derivations of the sequents A -> B are morphisms. Free SMCC (in presence of "tensor unit" I) is not "fully coherent": there are non-commutative diagrams. For example, one has the Mac Lane's example A*** -> B*** (called "triple dual diagram"). In terms of IMLL there exist two non-equivalent derivations of ((A-oI)-oI)-o I -> ((A-oI)-oI)-o I w.r.t. the equivalence of free SMCC on the derivations of IMLL. One derivation is identity, another derivation is obtained in obvious way using the derivability of ((A-oI)-oI)-o I -> A-o I. Let us denote these derivations 1 and f respectively. (For the sequent ((A-oI)-oI)-o I -> ((A-oI)-oI)-o I every derivation is equivalent to 1 or to f.) The "triple dual conjecture" says that if we declare f\equiv 1 then all the derivations with the same final sequent in IMLL will become equivalent. I.e. the stronger categorical structure than SMCC (obtained b= y adding this new axiom for equivalence/ commutativity of diagrams) will be "fully coherent". If it is true we would have an interesting new variety of categories (subvariety of SMCCs) in the sense of Universal Algebra. Proof-theoretically, the study of this conjecture requires to study the equivalence relations on derivations of IMLL between the relation of free SMCC and the relation that identifies all derivations with the same final sequent. In my paper S. Soloviev. On the conditions of full coherence in closed categories. Journal of Pure and Applied Algebra, 69:301-329, 1990. it was shown that - if the "triple dual diagram" is commutative w.r.t. some equivalence relation ~ (containing the relation of free SMCC) - and the following additional condition holds: [a-oI/a] h ~ [a-oI/a] g =3D> h~g for any two derivations of the same sequent, then all the derivations of the same sequent in IMLL become equivalent. The additional condition is a) difficult to verify b) has the form different form the equational form ("commutativity of a diagram") require= d from the point of view of Universal Algebra approach. All the attempts to prove "pure" triple dual conjecture (by myself and others) did not yet succeed. One may mention that it is known that some intermediate equivalence relations between the relation of free SMCC and the "total" relation of derivations do exist: L. Mehats, S. Soloviev. Coherence in SMCCs and equivalences on deriva- tions in IMLL with unit. Annals of Pure and Applied Logic, v.147, 3, p. 127-179, august 2007. but all known intermediate relations are contained in the relation generated by commutativity of triple dual diagram. My ph.d. student Antoine El Khoury has checked also that the commutativity of triple dual diagram (equivalence of 1 and f) implies equivalence of derivations of the balanced sequents with 1, 2 or 3 variables (commutativity of corresponding diagrams in SMCC). Remark. Obviosly, the commutativity of triple dual diagram implies A*** isomorphe to A*. Best regards to all Sergei Soloviev [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Sun Jun 7 19:12:58 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 07 Jun 2009 19:12:58 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MDQZh-0004lq-TQ for categories-list@mta.ca; Sun, 07 Jun 2009 19:10:45 -0300 Date: Sat, 6 Jun 2009 19:37:55 -0400 (EDT) From: Andrew Salch To: categories@mta.ca Subject: categories: categories fibered in small categories MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed Sender: categories@mta.ca Precedence: bulk Reply-To: Andrew Salch Message-Id: Status: O X-Status: X-Keywords: X-UID: 31 I have a question for the categories list: it is well-known (and proven e.g. in Hollander's PhD thesis) that categories fibered in groupoids over a small category C are equivalent to lax presheaves of groupoids on C. I would like to use the generalization of this result in which the word "groupoids" is replaced throughout by "small categories." It is not hard to write out how this proof goes, but I suspect there is some vast generalization of this, e.g. with the word "groupoids" replaced by "quasicategories" or something of that nature, which somebody has already proven, and in that case I would prefer to cite the more general result. Does anyone know if something like this is already in the literature? Thanks, Andrew S. [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Sun Jun 7 19:12:58 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 07 Jun 2009 19:12:58 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MDQZB-0004kQ-75 for categories-list@mta.ca; Sun, 07 Jun 2009 19:10:13 -0300 Date: Sat, 6 Jun 2009 23:22:52 +0100 From: Miles Gould To: categories@mta.ca Subject: categories: Re:Fundamental Theorem of Category Theory? Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Sender: categories@mta.ca Precedence: bulk Reply-To: Miles Gould Message-Id: Status: O X-Status: X-Keywords: X-UID: 32 On Fri, Jun 05, 2009 at 04:36:23PM -0400, Ellis D. Cooper wrote: > There are Fundamental Theorems of Arithmetic, Algebra, Calculus, and > indeed, many more. > > My question is, What would be candidates for the Fundamental Theorem > of Category Theory? My suggestion would be the theorem that left adjoints preserve colimits, and right adjoints preserve limits. This may not be the deepest theorem in category theory, but (a) it's pretty darn deep, (b) it describes a beautiful connection between two fundamental notions in the subject, (c) it admits a huge variety of applications in "ordinary" mathematics. I've occasionally referred to this theorem as the Fundamental Theorem of Category Theory by way of emphasizing its importance while teaching, but I've always immediately clarified that it's only me who uses this term :-) Miles -- Sometimes it's best to do nothing, if it's the right sort of nothing. -- The Doctor [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Sun Jun 7 19:12:59 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 07 Jun 2009 19:12:59 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MDQbD-0004ps-IO for categories-list@mta.ca; Sun, 07 Jun 2009 19:12:19 -0300 Mime-Version: 1.0 (Apple Message framework v753.1) Content-Type: multipart/alternative; boundary=Apple-Mail-1--257933298 To: categories Subject: categories: Categorical problems From: Ross Street Date: Sun, 7 Jun 2009 11:13:58 +1000 Content-Transfer-Encoding: 7bit Content-Type: text/plain;charset=US-ASCII;delsp=yes;format=flowed Sender: categories@mta.ca Precedence: bulk Reply-To: Ross Street Message-Id: Status: O X-Status: X-Keywords: X-UID: 33 Walter Tholen's recent message reminded me of a conjecture. Perhaps we have been too shy about stating our conjectures because, even among mathematicians, they may have seemed too technical. I seem to remember Peter Freyd saying once that the problem in category theory of proving sets were small (to find adjoints to functors for example) was analogous to finding numerical bounds in mathematical analysis. Surely by now, there are as many people who understand what a sheaf is as understand what the Riemann Hypothesis asserts (for example, local to global versus analytic continuation). So here is a problem I came up with in the 1970s. As with Fermat's Last Theorem, I don't particularly remember having any application for it. However, similar solved problems were used by Rosebrugh-Wood to characterize the category of sets in terms of adjoint strings involving the Yoneda embedding. By locally small I mean having homs in a chosen category Set of small sets. Problem. Suppose A is a locally small site whose category E of Set- valued sheaves is also locally small. Is E a topos? == Ross [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Sun Jun 7 19:12:59 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 07 Jun 2009 19:12:59 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MDQaM-0004nO-La for categories-list@mta.ca; Sun, 07 Jun 2009 19:11:26 -0300 Date: Sat, 06 Jun 2009 21:09:25 -0400 From: "Fred E.J. Linton" To: "Ellis D. Cooper" , Subject: categories: Re: Fundamental Theorem of Category Theory? Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Sender: categories@mta.ca Precedence: bulk Reply-To: "Fred E.J. Linton" Message-Id: Status: O X-Status: X-Keywords: X-UID: 34 On Sat, 06 Jun 2009 05:51:38 PM EDT, "Ellis D. Cooper" asked: > There are Fundamental Theorems of Arithmetic, Algebra, Calculus, and > indeed, many more. > = > My question is, What would be candidates for the Fundamental Theorem > of Category Theory? > = > Yoneda Lemma comes to my mind. What do you think? Perhaps that, yes; or, perhaps, the characterization of representable functors. Cheers, -- Fred [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Sun Jun 7 19:13:11 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 07 Jun 2009 19:13:11 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MDQbz-0004sl-Sm for categories-list@mta.ca; Sun, 07 Jun 2009 19:13:07 -0300 Subject: categories: Re: preprint announcement From: Vincenzo Ciancia To: Panagis Karazeris , categories@mta.ca Content-Type: text/plain; charset="UTF-8" Date: Sun, 07 Jun 2009 21:15:11 +0200 Mime-Version: 1.0 Sender: categories@mta.ca Precedence: bulk Reply-To: Vincenzo Ciancia Message-Id: Status: O X-Status: X-Keywords: X-UID: 35 Il giorno lun, 01/06/2009 alle 16.15 +0300, Panagis Karazeris ha scritto: > Dear all, >=20 > I would like to announce that the following preprint is available as >=20 > http://arxiv.org/abs/0905.4883 >=20 > as well as from my webpage >=20 > www.math.upatras.gr/~pkarazer >=20 > Final Coalgebras in Accessible Categories, > by Panagis Karazeris, Apostolos Matzaris and Jiri Velebil >=20 > Abstract: > We give conditions on a finitary endofunctor of a finitely accessible > category to admit a final coalgebra. Our conditions always apply to the > case of a finitary endofunctor of a locally finitely presentable (l.f.p= .) > category and they bring an explicit construction of the final coalgebra= in > this case. On the other hand, there are interesting examples of final > coalgebras beyond the realm of l.f.p. categories to which our results > apply. We rely on ideas developed by Tom Leinster for the study of > self-similar objects in topology.=20 >=20 > Best regards, > Panagis Karazeris >=20 I do not see the following paper in the references; would it be worth to provide a comparison? http://www.sciencedirect.com/science?_ob=3DArticleURL&_udi=3DB75H1-4G7MXP= F-4&_user=3D144492&_rdoc=3D1&_fmt=3D&_orig=3Dsearch&_sort=3Dd&view=3Dc&_a= cct=3DC000012038&_version=3D1&_urlVersion=3D0&_userid=3D144492&md5=3D5760= 58372d432ade83f476c43b8b466a Terminal sequences for accessible endofunctors=20 James Worrell Abstract: We consider the behaviour of the terminal sequence of an accessible endofunctor T on a locally presentable category K. The preservation of monics by T is sufficient to imply convergence, necessarily to a terminal coalgebra. We can say much more if K is Set, and =CE=BA is =CF=89= . In that case it is well known that we do not necessarily get convergence at =CF=89, however we show that to ensure convergence we don't need to go to= a higher cardinal, just to the next limit ordinal, =CF=89 + =CF=89. For an =CF=89-accessible endofunctor T on Set the construction of the terminal coalgebra can thus be seen as a two stage construction, with each stage being finitary. The first stage obtains the Cauchy completion of the initial T-algebra as the =CF=89-th object in the terminal sequence= A=CF=89. In the second stage this object is pruned to get the final coalgebra A=CF= =89 +=CF=89. We give an example where A=CF=89 is the solution of the correspo= nding domain equation in the category of complete ultra-metric spaces. Thanks Vincenzo [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Mon Jun 8 11:36:10 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 08 Jun 2009 11:36:10 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MDfvp-00025W-NZ for categories-list@mta.ca; Mon, 08 Jun 2009 11:34:37 -0300 Mime-Version: 1.0 (Apple Message framework v753.1) To: categories Subject: categories: Categorical problems From: Ross Street Date: Sun, 7 Jun 2009 11:13:58 +1000 Content-Transfer-Encoding: 7bit Content-Type: text/plain;charset=US-ASCII;delsp=yes;format=flowed Sender: categories@mta.ca Precedence: bulk Reply-To: Ross Street Message-Id: Status: RO X-Status: X-Keywords: X-UID: 36 [From moderator: Resent with apologies to those who received an empty message body...] Walter Tholen's recent message reminded me of a conjecture. Perhaps we have been too shy about stating our conjectures because, even among mathematicians, they may have seemed too technical. I seem to remember Peter Freyd saying once that the problem in category theory of proving sets were small (to find adjoints to functors for example) was analogous to finding numerical bounds in mathematical analysis. Surely by now, there are as many people who understand what a sheaf is as understand what the Riemann Hypothesis asserts (for example, local to global versus analytic continuation). So here is a problem I came up with in the 1970s. As with Fermat's Last Theorem, I don't particularly remember having any application for it. However, similar solved problems were used by Rosebrugh-Wood to characterize the category of sets in terms of adjoint strings involving the Yoneda embedding. By locally small I mean having homs in a chosen category Set of small sets. Problem. Suppose A is a locally small site whose category E of Set- valued sheaves is also locally small. Is E a topos? == Ross [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Mon Jun 8 14:14:04 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 08 Jun 2009 14:14:04 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MDiOt-0007bT-VL for categories-list@mta.ca; Mon, 08 Jun 2009 14:12:48 -0300 From: Hasse Riemann To: Category mailing list Subject: categories: =?windows-1256?Q?Famous_uns?= =?windows-1256?Q?olved_prob?= =?windows-1256?Q?lems_in_or?= =?windows-1256?Q?dinary_cat?= =?windows-1256?Q?egory_theo?= =?windows-1256?Q?ry=FE?= Date: Mon, 8 Jun 2009 01:34:10 +0000 Content-Type: text/plain; charset="windows-1256" MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Sender: categories@mta.ca Precedence: bulk Reply-To: Hasse Riemann Message-Id: Status: O X-Status: X-Keywords: X-UID: 37 =20 Hi categorists =20 OK, here is the beuty of collecting and spreading problems that many seem= to miss. It just took me a few days to change my mood from the depressing answers not to look for problems. Again i am much more for structuring of mathema= tics. =20 Usually you only get to know what is proved and not what is unproved. Problems complete this by letting you know what to not to look for. They also answer your questions even if it is by saying unkown or a conje= cture. Then, on the other hand, they are good research projects so they should b= e widely known. Just maby someone undertakest them and happens to find the solution. But often he must first see the problem. =20 The problems Ross Street put forward are so beautiful i have decided to p= ost 2 problems i have learned from him, unedited. =20 1) Fermat's Last Theorem is about the category of finite sets. Is there a ca= tegorical proof? Can we characterize those categories C in which x^n + y^n isomorphic to z= ^n has only trivial solutions for n> 2? =20 2) The category of finite sets is a concrete form of the set N of natural nu= mbers. What are concrete forms of Z, Q, R and C? If anyone know some problems of these sort below let me know. =20 * characterization problems * inherit properties problems * every category/functor/... of type A is a category/functor/... of type = B =20 =20 I also foregot to mention before that i know and more than like Grothendi= ecks philosophy of dissolving problems by developing a proper framework for rhem. =20 Best regards Rafael Borowiecki [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Mon Jun 8 14:14:04 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 08 Jun 2009 14:14:04 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MDiPi-0007iO-Nq for categories-list@mta.ca; Mon, 08 Jun 2009 14:13:38 -0300 MIME-Version: 1.0 Date: Mon, 8 Jun 2009 07:13:41 +0200 Subject: categories: Re: categories fibered in small categories From: Urs Schreiber To: Andrew Salch , categories@mta.ca Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Sender: categories@mta.ca Precedence: bulk Reply-To: Urs Schreiber Message-Id: Status: O X-Status: X-Keywords: X-UID: 38 On Sun, Jun 7, 2009 at 1:37 AM, Andrew Salch wrote: > it is well-known (and proven > e.g. in Hollander's PhD thesis) that categories > fibered in groupoids over a small category C > are equivalent to lax presheaves of groupoids on C. [...] >I suspect there is some vast generalization of > this, e.g. with the word "groupoids" replaced by > "quasicategories" or something of that nature, > which somebody has already proven, and in that > case I would prefer to cite the more general result. > Does anyone know if something like this is already > in the literature? Yes, see section 3.3.2 of Jacob Lurie's "Higher Topos Theory" for the statement for "quasicategory valued presheaves". [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Mon Jun 8 14:14:35 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 08 Jun 2009 14:14:35 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MDiQa-0007nH-S4 for categories-list@mta.ca; Mon, 08 Jun 2009 14:14:32 -0300 From: "Ronnie Brown" To: "Miles Gould" , Subject: categories: Re:Fundamental Theorem of Category Theory? Date: Mon, 8 Jun 2009 10:06:12 +0100 MIME-Version: 1.0 Content-Type: text/plain;format=flowed;charset="iso-8859-1";reply-type=original Content-Transfer-Encoding: 7bit Sender: categories@mta.ca Precedence: bulk Reply-To: "Ronnie Brown" Message-Id: Status: O X-Status: X-Keywords: X-UID: 39 Limits, colimits, and adjoints: I go along with this: it is the result of general category theory that I have used most in studying colimits of forms of multiple groupoids, for homotopical applications. It really does come under `categories for the working mathematician'. I have also been attracted in the same vein by fibrations and cofibrations of categories: see a recent paper in TAC. I well remember a remark of Henry Whitehead in response to a visiting lecturer saying: `The proof is trivial.' JHCW: `It is the snobbishness of the young to suppose that a theorem is trivial because the proof is trivial.' (There was and is no answer to that!) (His example was Schroder-Bernstein.) The leads to the interesting question of what makes a theorem nontrivial? Good discussion topic for the young (at heart). Ronnie Brown [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Mon Jun 8 14:15:18 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 08 Jun 2009 14:15:18 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MDiRG-000043-Tl for categories-list@mta.ca; Mon, 08 Jun 2009 14:15:14 -0300 From: vxc@Cs.Nott.AC.UK To: categories@mta.ca Subject: categories: PhD position in Nottingham Date: 08 Jun 2009 10:08:16 +0100 Mime-Version: 1.0 Content-Type: text/plain; format=flowed; charset=ISO-8859-1 Sender: categories@mta.ca Precedence: bulk Reply-To: vxc@Cs.Nott.AC.UK Message-Id: Status: O X-Status: X-Keywords: X-UID: 40 PhD position in Type Theory at Nottingham ----------------------------------------- A new PhD position is available in the Functional Programming Laboratory at the University of Nottingham. The topic of research for the project is "Programming and Reasoning with Infinite Structures": it consists in the theoretical study and development of software tools for coinductive types and structured corecursion. The candidate must be a UK resident with an excellent degree in Computer Science or Mathematics at MSc (preferred) or BSc level (first class or equivalent). The applicant should have a good background in mathematical logic, theoretical computer science or functional programming. (S)he should be interested doing research in type theory, constructive mathematics, category theory and foundations of formal reasoning. We offer: PhD place with living expenses (standard UK level) for 3 years. The grants also provide laptops and travel expenses for conference and workshop visits. Nottingham University provides a vibrant research environment in the Functional Programming Laboratory. Deadline for applications: 20 June 2009. Send a cover letter and your CV to Venanzio Capretta (vxc@cs.nott.ac.uk). Please contact me for any additional information that you need. [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Mon Jun 8 14:16:18 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 08 Jun 2009 14:16:18 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MDiSE-0000BC-9G for categories-list@mta.ca; Mon, 08 Jun 2009 14:16:14 -0300 Date: Mon, 8 Jun 2009 07:44:40 -0400 From: tholen@mathstat.yorku.ca To: Miles Gould , categories@mta.ca Subject: categories: Re: Fundamental Theorem of Category Theory? MIME-Version: 1.0 Content-Type: text/plain;charset=ISO-8859-1;format="flowed" Content-Disposition: inline Content-Transfer-Encoding: 7bit Sender: categories@mta.ca Precedence: bulk Reply-To: tholen@mathstat.yorku.ca Message-Id: Status: O X-Status: X-Keywords: X-UID: 41 You could make your choice more comprehensive: Freyd's General and Special Adjoint Functor Theorems give a more complete picture of the fundamental relationship between limit preservation and adjointness. Regards, Walter. Quoting Miles Gould : > On Fri, Jun 05, 2009 at 04:36:23PM -0400, Ellis D. Cooper wrote: >> There are Fundamental Theorems of Arithmetic, Algebra, Calculus, and >> indeed, many more. >> >> My question is, What would be candidates for the Fundamental Theorem >> of Category Theory? > > My suggestion would be the theorem that left adjoints preserve colimits, > and right adjoints preserve limits. > ... [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Tue Jun 9 07:54:24 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 09 Jun 2009 07:54:24 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MDywn-0000jB-16 for categories-list@mta.ca; Tue, 09 Jun 2009 07:52:53 -0300 Date: Mon, 8 Jun 2009 21:33:28 +0100 From: Miles Gould To: categories@mta.ca Subject: categories: Re: Fundamental Theorem of Category Theory? Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Sender: categories@mta.ca Precedence: bulk Reply-To: Miles Gould Message-Id: Status: O X-Status: X-Keywords: X-UID: 42 On Mon, Jun 08, 2009 at 07:44:40AM -0400, tholen@mathstat.yorku.ca wrote: > You could make your choice more comprehensive: Freyd's General and > Special Adjoint Functor Theorems give a more complete picture of the > fundamental relationship between limit preservation and adjointness. Indeed. I think there's an analogy to be made between these theorems and the Fundamental Theorem of Calculus: one side is very simply stated, and the other requires more care. Compare * d/dx (integral f(x) dx) = f(x), * integral (d/dx f(x)) dx = f(x) [up to constant offset...] with * all right adjoints preserve limits, * all limit-preserving functors [satisfying some caveats...] are right adjoints. Miles [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Tue Jun 9 07:54:24 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 09 Jun 2009 07:54:24 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MDyvk-0000hV-Gn for categories-list@mta.ca; Tue, 09 Jun 2009 07:51:48 -0300 Date: Mon, 08 Jun 2009 15:30:05 -0300 From: "Eduardo J. Dubuc" MIME-Version: 1.0 To: Ross Street , Subject: categories: Re: Categorical problems Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Sender: categories@mta.ca Precedence: bulk Reply-To: "Eduardo J. Dubuc" Message-Id: Status: O X-Status: X-Keywords: X-UID: 43 Ross Street wrote: > Problem. Suppose A is a locally small site whose category E of Set- > valued sheaves is also locally small. Is E a topos? (see (*) below) This is one of (probably) many problems of Girau topoi [satisfy all conditions in Girau's Theorem exept (may be) the set of generators] which are not known to be a topos. Another, the Etale "topos" in the sense of Joyal's axiomatic theory of etal maps (which is even a subcategory of a topos). Another (solved), to show the existence of colimits in the category of topoi, the only hard part is to get the generators. Concerning the other thread (not Ross question) > > My question is, What would be candidates for the Fundamental Theorem > > of Category Theory? > > > > Yoneda Lemma comes to my mind. What do you think? Of course, Yoneda Lemma, at the birth of category theory, is the fundamental result that makes of category theory something more than a convenient language. Related to this, the definition of category should include small hom sets, and categories with large hom sets should be called "illegitimate" (in the manner of the definition of topoi, which include generators, the others being illegitimate or "faux" in Grothendieck's terminology). (*) It seems Not: Take a Girau (really faux but locally small) topos E, with the canonical topology. Then the topos of sheaves should be E again, which is not a topos (am I missing something ?). [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Tue Jun 9 07:55:08 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 09 Jun 2009 07:55:08 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MDyyt-0000pC-Vc for categories-list@mta.ca; Tue, 09 Jun 2009 07:55:04 -0300 Mime-Version: 1.0 (Apple Message framework v624) Content-Type: text/plain; charset=US-ASCII; format=flowed Content-Transfer-Encoding: 7bit From: Paul Taylor Subject: categories: Famous unsolved problems etc Date: Tue, 9 Jun 2009 10:52:20 +0100 To: Categories list Sender: categories@mta.ca Precedence: bulk Reply-To: Paul Taylor Message-Id: Status: O X-Status: X-Keywords: X-UID: 44 I had wanted to give more careful consideration to this question before posting about it again, but an emergency has arisen: My website (paultaylor.eu) is likely to be out of action for the rest of this week. Apparently the hosting company was badly hacked, and even their own webpage doesn't exist at the moment. However, email gets through to me by a backup route, so please do not try to second guess my email address. You can access my papers etc by adding site:paultaylor.eu to a Google query and using their cached versions. The version of my diagrams package on CTAN was out of date (sorry). I have uploaded a new release (V3,93) and asked them to install it quickly. The package now automatically recognises when it is running under XeTeX, as it has done with PDFTeX for some time. I would like to thank Apostolos Syropoulos for his help in implementing this, which he wanted to use to combine my diagrams with Greek text in Unicode. --- I would like to thank all of the people who sent supportive responses to my autobiographical comments. However, it seems that people read these rather more literally than was intended, whilst incorrectly interpreting the "inappropriate boyfriend" as a metaphor. I was certainly not suggesting that I had a relevation about constructive categorical logic during puberty (which would have coincided with the invention of elementary toposes) and that this was suppressed by my mathematical teachers until my rebellion! Of course, this was exactly my point: conceptual and constructive thinking (which are by no means coincident) require mathematical and personal maturity. My reaction to Ellis Cooper's question about "Fundamental Theorems" was that Ronnie Brown and others had answered this question under the "famous unsolved problems" heading. Notwithstanding the occurrence of the phrases "fundamental theorem of algebra" and "fundamental theorem of interval analysis" on my (dormant) website, I would say that they demonstrate a fundamental lack of appreciation of the breadth of mathematics, and are only appropriate for schoolteachers to shoehorn the subject into a restrictive curriculum. The adjoint functor theorem and the Yoneda Lemma are the two obvious candidates for the title "fundamental theorem of category theory", but I have to say that I am somewhat alarmed by prospect that the apparent consensus about this might become "legislated" into someone's lecture notes, curriculum or textbook. I think that Ronnie Brown and other people have given the right answer to the question about famous unsolved problems. Category theory is not a collection of miscellaneous problems like combinatorics, but a way of thinking about mathematics. Rafael Borowiecki, alias Hasse Riemann, did not seem to be satisfied with these answers, so what I said to him privately is this: It would help people to give better answers if he, along with students and non-academics who ask questions on "categories", gave some clearer indication of their mathematical background. If you read the archives of "categories", you will find that people discuss topics from many areas in mathematics, physics and computer science. You may find amongst this something that interests you, in which case you should look up the web pages and papers of the people who post on that topic. Academics are not very responsive to completely uninformed questions, but they usually are very happy to help if you show some background. It is also a good idea to flatter them by indicating that you have looked at their papers. Finally, Rafael queried some of the technical points about "illegitimate presheaves on locales" that I made at the end of my "autobiography". I will publish my private reply another time, as I have some other things to say about locale theory. Sorry for the hurried response. Paul Taylor [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Wed Jun 10 21:25:43 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 10 Jun 2009 21:25:43 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MEY5J-0000GM-D5 for categories-list@mta.ca; Wed, 10 Jun 2009 21:24:01 -0300 From: "Reinhard Boerger" To: Subject: categories: Famous unsolved problems in ordinary category theory Date: Tue, 9 Jun 2009 15:35:31 +0200 MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable Sender: categories@mta.ca Precedence: bulk Reply-To: "Reinhard Boerger" Message-Id: Status: O X-Status: X-Keywords: X-UID: 45 Dear categorists, When I read the question for the first time, I did not know such a = problem. Moreover, my impression was that in category theory one often finds new results, which had not been conjectured before. Sometimes an important = part of the work is even to develop the right notions. This may explain that there are less important well-known problems in category theory than in other areas. Nevertheless, I remember a problem that can be easily formulated in pure category and is still unsolved as far as I know. Bur it does not seem = vastly distributed. Cantor's diagonal says that says that the power set always = is of larger cardinality as the original set. Gavin Wraith suggested the following generalization to topoi: If for two objects A,B there is a monomorphism A^B>->B, is there also a monomorphism A>->1? This looks = like a meaningful analogue, and I have not seen an answer in the meantime. The question can even be asked not only in a topos, but in every cartesian closed category. Does anybody know anything about progress? Greetings Reinhard [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Wed Jun 10 21:25:43 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 10 Jun 2009 21:25:43 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MEY4I-0000Cz-2T for categories-list@mta.ca; Wed, 10 Jun 2009 21:22:58 -0300 Date: Tue, 9 Jun 2009 13:51:32 +0200 (CEST) Subject: categories: New deadline - Special Volumes in honour of F. Borceux and D. Bourn From: "Marino Gran" To: categories@mta.ca MIME-Version: 1.0 Content-Type: text/plain;charset=iso-8859-1 Content-Transfer-Encoding: quoted-printable Sender: categories@mta.ca Precedence: bulk Reply-To: "Marino Gran" Message-Id: Status: O X-Status: X-Keywords: X-UID: 46 Dear Colleagues, The deadline for the Cahiers volume in Honour of Francis Borceux and the TAC volume in Honour of Dominique Bourn has been postponed to July 31 since a number of potential contributors asked for a postponement. Please find the information concerning submissions in the message copied below. With best regards, Jiri Adamek, Andr=E9e Ehresmann, Marino Gran, George Janelidze, Rudger Kieboom, Jiri Rosicky, Walter Tholen and Enrico Vitale SPECIAL VOLUMES IN HONOUR OF FRANCIS BORCEUX AND OF DOMINIQUE BOURN ON TH= E OCCASION OF THEIR SIXTIETH BIRTHDAY Last year Francis Borceux and Dominique Bourn celebrated their 60th birthday, and an international meeting in their honour took place at the Royal Academy in Brussels last October (see http://www.math.ua.ac.be/bbdays/). We are glad to announce that there will be a Special Volume of the Cahier= s de Topologie et G=E9om=E9trie Diff=E9rentielle Cat=E9goriques dedicated t= o Francis Borceux, and a Special Volume of Theory and Applications of Categories dedicated to Dominique Bourn. Submission of papers on areas in which Francis Borceux and Dominique Bour= n have worked are particularly encouraged. The deadline for submission for both volumes is 31 May 2009. Please find the instructions for submission of papers below. With our best wishes for the New Year, Jiri Adamek, Andr=E9e Ehresmann, Marino Gran, George Janelidze, Rudger Kieboom, Jiri Rosicky, Walter Tholen and Enrico Vitale =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D - SPECIAL VOLUME FOR FRANCIS BORCEUX (CAHIERS): Please email your submission to Marino Gran (marino.gran@uclouvain.be) as an attached PDF file: you may suggest one of the Guest Editors Jiri Adamek Andr=E9e Ehresmann Marino Gran George Janelidze Rudger Kieboom for this Special Volume to be assigned to your paper. Please be sure that you receive an e-mail acknowledging the receipt of your submission. All papers will be carefully refereed following the standards of Cahiers de Topologie et G=E9om=E9trie Diff=E9rentielle Cat=E9goriques. =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D - SPECIAL VOLUME FOR DOMINIQUE BOURN (TAC): Please email your submission to Enrico Vitale (enrico.vitale@uclouvain.be) as an attached PDF file: you may suggest one of the Guest Editors Andr=E9e Ehresmann George Janelidze Jiri Rosicky Walter Tholen Enrico Vitale for this Special Volume to be assigned to your paper. Please be sure that you receive an e-mail acknowledging the receipt of your submission. All papers will be carefully refereed following the standards of Theory and Applications of Categories. [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Wed Jun 10 21:25:43 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 10 Jun 2009 21:25:43 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MEY6C-0000Jb-E6 for categories-list@mta.ca; Wed, 10 Jun 2009 21:24:56 -0300 Date: Tue, 9 Jun 2009 14:44:02 +0100 (BST) From: "Prof. Peter Johnstone" To: "Eduardo J. Dubuc" , categories@mta.ca Subject: categories: Re: Categorical problems MIME-Version: 1.0 Content-Type: TEXT/PLAIN; format=flowed; charset=US-ASCII Sender: categories@mta.ca Precedence: bulk Reply-To: "Prof. Peter Johnstone" Message-Id: Status: O X-Status: X-Keywords: X-UID: 47 On Mon, 8 Jun 2009, Eduardo J. Dubuc wrote: > Ross Street wrote: > >> Problem. Suppose A is a locally small site whose category E of Set- >> valued sheaves is also locally small. Is E a topos? (see (*) below) > > This is one of (probably) many problems of Girau topoi [satisfy all > conditions > in Girau's Theorem exept (may be) the set of generators] which are not known > to be a topos. > > (*) It seems Not: Take a Girau (really faux but locally small) topos E, with > the canonical topology. Then the topos of sheaves should be E again, which is > not a topos (am I missing something ?). > I presume that Ross was using the word "topos" to mean "elementary topos". But in any case, Eduardo was missing something: the proof that, if E is an \infty-pretopos (my preferred name for what he calls a "Girau(d) topos"), then every canonical sheaf on E is representable, requires the existence of a generating set (see C2.2.7 in the Elephant). For a counterexample in the absence of generators, let G be the "large" group of all functions from the ordinals to {0,1} having finite support, the group operation being pointwise addition mod 2 (or, if you prefer, the group of finite subsets of the ordinals under symmetric difference), and let E be the (elementary) topos of G-sets. For each ordinal \alpha, let A_\alpha be the set {0,1} with G acting via its \alpha-th factor; then any G-set admits morphisms into only a set of the A_\alpha, from which it follows that the coproduct of all the A_\alpha exists as a (set-valued) canonical sheaf on E, though it clearly isn't a set. Moreover, this coproduct admits a proper class of maps to itself, so the category of sheaves on E isn't locally small; hence it doesn't violate Ross's conjecture. Peter Johnstone [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Wed Jun 10 21:25:51 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 10 Jun 2009 21:25:51 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MEY72-0000Lk-19 for categories-list@mta.ca; Wed, 10 Jun 2009 21:25:48 -0300 Date: Tue, 09 Jun 2009 16:47:15 +0100 From: Steve Vickers MIME-Version: 1.0 To: Hasse Riemann , categories@mta.ca Subject: categories: Re: Famous unsolved problems in ordinary category theory Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Sender: categories@mta.ca Precedence: bulk Reply-To: Steve Vickers Message-Id: Status: O X-Status: X-Keywords: X-UID: 48 Dear Hasse, The presheaves that Townsend and I used are on the category Loc of locales. The fact that Loc is large may be seen as a problem, but another illegitimacy is the way a presheaf is a functor to Sets. This means, for instance, that for a representable presheaf y(X), where X is a locale, we take y(X)(W) = Loc(W,X) to be a _set_ for any pair of locales X and W, and that is foundationally tendentious. Whatever kind of collection Loc(W,X) is (if W is locally compact then we can take it to be another locale, but otherwise not), the ability to extract a "set of points" from it is sensitive to the foundations. We tried to be foundationally conservative in what we did with the presheaves, and you can see come remarks on this in the conclusions of our paper. (I should stress that we did not claim to have embedded Loc in a CCC, and we tried not to make use of any particular categorical properties of Presh(Loc).) Insofar as the representable presheaves y(X) can be acceptable, then so too are their exponentials y(Y)^y(X), since y(Y)^y(X)(W) = Loc(WxX,Y). What we showed is that then the exponential y($)^(y($)^y(X)) also exists (where $ = the Sierpinski locale), and in fact is representable of the form y(PP(X)) where PP(X) is the "double powerlocale" on X. Thus PP(X) has a claim to be thought of as $^($^X) even when X is not exponentiable (locally compact). PP is a foundationally robust construction, available in both topos-valid locale theory and predicative formal topology. Regards, Steve Vickers. Hasse Riemann wrote: >> Another is how to embed the category of locales in a CCC WITHOUT >> using illegitimate presheaves (Vickers and Townsend) or the axiom >> of collection (Heckmann). > > I don't follow to the end here. > Why should presheaves be illegitimate? [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Wed Jun 10 21:27:25 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 10 Jun 2009 21:27:25 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MEY8W-0000TF-QA for categories-list@mta.ca; Wed, 10 Jun 2009 21:27:20 -0300 Mime-Version: 1.0 (Apple Message framework v624) Content-Type: text/plain; charset=US-ASCII; format=flowed Content-Transfer-Encoding: 7bit From: Paul Taylor Subject: categories: aspects of locale theory Date: Tue, 9 Jun 2009 17:44:07 +0100 To: Categories list Sender: categories@mta.ca Precedence: bulk Reply-To: Paul Taylor Message-Id: Status: O X-Status: X-Keywords: X-UID: 49 Steve Vickers has bounced me into replying to the questions about locales that Rafael Borowiecki (aka Hasse Riemann) asked, even though I had said that I would do so when I was ready with some other comments on that subject. The following also includes the answer to a question that I myself raised last year, which has further consequences for the appropriateness of locale theory as an account of general topology, but I am not going to say what these are until I am actually ready. In my "autobiography", I had said, > Another [problem] is how to embed the category of locales in a CCC > WITHOUT using illegitimate presheaves (Vickers and Townsend) or > the axiom of collection (Heckmann). When I wrote the original version > of this posting a couple of weeks back, I thought I could solve this > one. I am still hopeful, but it turns out to be a powerful question, > cf Ronnie's (2) above. Rafael asked me, > Why should presheaves be illegitimate? I am not saying that presheaves in general are illegitimate in the plain English sense of the word. The work that I was referring to uses the category of all functors from the opposite of the category of locales to the category of sets. Since the category of locales is "large", this functor-category is super-large or "illegitimate", where the quoted words have a technical meaning. As Steve Vickers has already explained, he goes to some trouble to avoid the problems, essentially by exploring only a tiny part of the presheaf category. He really only uses the exponentials Sigma^X of locales, which are the functors Loc(-xX,Sigma). The rest of the comments concern the paper @article{HeckmannR:carcec, title={A Cartesian Closed Extension of the Category of Locales}, author={Heckmann, Reinhold}, journal={Mathematical Structures in Computer Science}, year={2006}, volume={16}, pages={231--253}} which was inspired by Dana Scott's equilogical space construction. However, Reinhold's "equivalence relations" are what the presheaf category provides. So a relation on a single locale requires data from every object in the category. (The details are rather complicated, and I don't recall them exactly at the moment.) The collection of morphisms between two equilocales is defined as the image of a class in a set. > Then, i suppose the axiom of collection is valid at least in the CCC. No. The axiom of collection says roughly that, given a function from a class to a set, its image is a set. This is quite a strong axiom of set theory, and is certainly not valid in something as logically weak as a CCC. > But what is so bad about the axiom of collection in this case? The vast majority of ordinary mathematics can be done in an elementary topos with a natural number object, maybe together with assumptions of excluded middle or the axiom of choice. This is roughly but not quite equivalent to Zermelo's set theory -- NOT ZFC, which adds the substantially more powerful axiom-scheme of replacement. Rather than using sledgehammers (adding more and more powerful axioms), most categorists would prefer to re-examine the problem to look for more delicate ways of doing things. On a different aspect of locale theory, I asked on 22 July 2008, > Where can I find a published proof that > if X --->> Y is a (not necessarily regular) epi of locales > then so is X x Z --->> Y x Z for any locale Z? > NB (I know that) this is not true for general pullbacks of locales! Peter Johnstone told me, essentially, that I was assuming excluded middle, in the form that every locale is open (as he would say) or overt (using my word). In fact, the answer is negative even with excluded middle, as Till Plewe pointed out to me. (Till no longer studies categories or locales, but is still doing academic research in Japan, or at least was last year when I was in touch with him.) The (basis of the) counterexample that Till pointed out is described in Peter's book (Stone Spaces) in section II 2.14. It is the locale QE of rationals with the Euclidean topology, that is, the frame of open subsets of the reals, quotiented by their effect on the rationals, so for example (3,pi)v(pi,4) = (3,4) in QE since pi is irrational. I also write QD for the rationals with the discrete topology, so QD is homeomorphic to N. The point is that QE has enough points, indeed QD-->>QE is epi, but QExQE doesn't. This means that QDxQE --> QExQE is not epi. Paul [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Wed Jun 10 21:27:53 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 10 Jun 2009 21:27:53 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MEY90-0000W1-HM for categories-list@mta.ca; Wed, 10 Jun 2009 21:27:50 -0300 Date: Wed, 10 Jun 2009 01:42:39 +0100 (BST) From: Bob Coecke To: categories@mta.ca Subject: categories: Categories, Quanta, Concepts talks now available MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed Sender: categories@mta.ca Precedence: bulk Reply-To: Bob Coecke Message-Id: Status: O X-Status: X-Keywords: X-UID: 50 All talks delivered at the conference Categories, Quanta, Concepts, which took place last week at the Perimeter Institute for Theoretical Physics, are now available at http://pirsa.org/C09008 They span a series of topics involving category theory and foundational physics. [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Wed Jun 10 21:28:33 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 10 Jun 2009 21:28:33 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MEY9a-0000Z8-R8 for categories-list@mta.ca; Wed, 10 Jun 2009 21:28:26 -0300 From: Hasse Riemann To: , Category mailing list Subject: categories: RE: Fundamental Theorem of Category Theory? Date: Wed, 10 Jun 2009 02:29:07 +0000 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Sender: categories@mta.ca Precedence: bulk Reply-To: Hasse Riemann Message-Id: Status: O X-Status: X-Keywords: X-UID: 51 =20 =20 Dear Ellis =20 I also had this question when i started with category theory but i was satisfied with the Yoneda lemma. Now thanks to your question i know more theorems to answer this. I don't think you can get a better answer than the replied suggestions. =20 However there is also higher category theory. The interesting point would now be to generalize: =20 What are the coresponding theorems for strict/weak n-categories? =20 I plan to at least ask for and suggest a higher dimensional Yoneda lemma. =20 The other adjoints preserving limits theorem is also interesting to generalize. But here as far as i know there is no concept of adjoint for 3-categories and higher up. I am more uncertain as to limits=2C but i have not seen limits in n-categories defined in the graceful style of limits in 1-categories. =20 Best regards Rafael Borowiecki =20 =20 [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Wed Jun 10 21:29:22 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 10 Jun 2009 21:29:22 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MEYAQ-0000ev-2Y for categories-list@mta.ca; Wed, 10 Jun 2009 21:29:18 -0300 MIME-Version: 1.0 Date: Wed, 10 Jun 2009 03:42:30 -0500 Subject: categories: database theory based on Heyting algebra instead of Boolean algebra From: "Vasili I. Galchin" To: Categories mailing list Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Sender: categories@mta.ca Precedence: bulk Reply-To: "Vasili I. Galchin" Message-Id: Status: O X-Status: X-Keywords: X-UID: 52 Hello, I'm sorry that this a bit off topic (but both algebras are categories), but I don't know where to post in order to get an intelligent answer. Is there any research to base data base queries on Heyting algebra, i.e. intuistionistic logic? Thanks, Vasili [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Wed Jun 10 21:30:13 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 10 Jun 2009 21:30:13 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MEYBE-0000jk-8D for categories-list@mta.ca; Wed, 10 Jun 2009 21:30:08 -0300 From: Hasse Riemann To: Category mailing list Subject: categories: RE: unsolved problems Date: Wed, 10 Jun 2009 09:39:48 +0000 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Sender: categories@mta.ca Precedence: bulk Reply-To: Hasse Riemann Message-Id: Status: O X-Status: X-Keywords: X-UID: 53 =20 Hi David =20 Since i could not e-mail you directly=2C i got delivery failure=2C i send m= y response here. =20 >One thing that I have found is that one has to develop one's own feeling f= or categories. >I wouldn't say I am terribly good at abstract category theory (monads and = algebras and >Kan extensions and so forth)=2C but I work with categories more in the sty= le of Ehresmann >- my thesis is essentially on homotopy ideas. =20 I have developed many perspectives on categories =20 As the study of algebraic structures with several objects As the study of primitive mathematical universe or space (not as fancy as a= topos) As an unifying tool in mathematics As a foundation of mathematics (that is structural) As an abstarction of an abstarction of an abstarction of ... (if you go to = higher categories) As a generalized theory of representations=20 If i have missed someone please let me know. =20 I don't think i understand in what style Ehresmann worked in. =20 > Here is a real=2C famous unsolved problem=2C which Michael Batanin is on = his way to solving: > Prove the homotopy theory of \infty-groupoids is equivalent to the homoto= py theory of > spaces and the related =20 Should it not be weak oo-groupoids? I think you also mean homotopy category of spaces instead of "homotopy theory of spaces andthe related". Spaces is a bit vague but i encounter this sometimes in category theory. Usually in such statements it is ment a topological space. Is there a categorical definition of a space (not a topological space)? =20 > But I am sure someone has already mentioned these > Prove the homotopy theory of n-groupoids is equivalent to the homotopy th= eory > of n-types =20 I have seen similar problems and maby this one also. John Baez mentioned a bunch of such problems on an internet page and Ronnie Brown also in explaining pursuing stacks. Thank you for the problems. =20 Best regards Rafael Borowiecki [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Thu Jun 11 10:12:23 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 11 Jun 2009 10:12:23 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MEk4A-000045-Ae for categories-list@mta.ca; Thu, 11 Jun 2009 10:11:38 -0300 Date: Thu, 11 Jun 2009 00:01:55 -0400 (EDT) From: Robert Seely To: Categories List Subject: categories: Makkaifest: banquet deadline MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed Sender: categories@mta.ca Precedence: bulk Reply-To: Robert Seely Message-Id: Status: O X-Status: X-Keywords: X-UID: 55 Due to the requirements of the restaurant, we have to place a deadline for letting us know you intend to attend the banquet 19 July, during the Makkaifest 18 - 20 June 2009 in Montreal. http://www.crm.umontreal.ca/Makkaifest09/index_e.php If you plan to attend the banquet, please let us know *BEFORE* Wednesday noon (GMT) (17 June 2009). Requests after that time may be impossible to meet. If you register, there is a place on the online form where you can indicate your intentions; otherwise email me directly. (If you have already done so, no worries!) The banquet will be held at the Musee des Beaux Arts, and will cost around $55 - 60 each (tax & tip included, wine extra), to be paid at the restaurant. (They will provide receipts.) If you have special dietary requirements, please let me know - the restaurant is very accommodating about such requests, as long as they know in advance. This includes vegetarian meals, allergies, etc. The main course will consist of a choice of beef or salmon. -= rags =- -- [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Thu Jun 11 10:12:23 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 11 Jun 2009 10:12:23 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MEk3V-0007my-NC for categories-list@mta.ca; Thu, 11 Jun 2009 10:10:57 -0300 Date: Wed, 10 Jun 2009 23:34:06 -0400 (EDT) From: Robert Seely To: Categories List Subject: categories: Makkaifest: Deadline for student funding MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed Sender: categories@mta.ca Precedence: bulk Reply-To: Robert Seely Message-Id: Status: O X-Status: X-Keywords: X-UID: 56 Due to official budgetary restrictions, we have to place a deadline on requests for funding from students who wish to attend the Makkaifest 18 - 20 June 2009 in Montreal. http://www.crm.umontreal.ca/Makkaifest09/index_e.php Any requests received after midnight (GMT) Monday 15 June will have to be refused. Students wishing to apply for funding should register on the meeting homepage, and fill out the funding request to be found there. (Funding is limited, and will only be "partial" - anyone wanting more information is invited to email me directly.) -= rags =- -- [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Thu Jun 11 10:12:48 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 11 Jun 2009 10:12:48 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MEk5F-0000Bp-DM for categories-list@mta.ca; Thu, 11 Jun 2009 10:12:45 -0300 MIME-Version: 1.0 Date: Wed, 10 Jun 2009 23:39:02 -0700 Subject: categories: Re: database theory based on Heyting algebra instead of Boolean algebra From: Greg Meredith To: "Vasili I. Galchin" , Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Sender: categories@mta.ca Precedence: bulk Reply-To: Greg Meredith Message-Id: Status: RO X-Status: X-Keywords: X-UID: 57 Vasili, Are you familiar with the use of monads as an approach to modeling storage semantics and access? The most high profile of these efforts is LINQ. XQuery's FLWOR expressions are also based around this. i've been investigating a very rich generalization. You get a logic out of the following data: - a distributive law, d, between - a monad, T, representing the algebra of your term language (think what's described by the DB schema) - a monad, S, representing some notion of collection (set, list, tree, graph...) The distributive law, d : ST -> TS is showing how collections of terms ST are representable as terms over collections, TS. Then SELECT-FROM-WHERE is precisely a comprehension which as Wadler shows maps clearly onto monadic semantics. The generalization allows you to consider collections that have notions of state. As a toy example, if your notion of collection is a quantale, then you get a (not very convincing) notion of update. This is closely related to current experiments factoring transactional semantics through a monadic presentation. In fact, i've recently been helping folks looking at the JTA specification arrived at a comprehension-based presentation. (Check out the Scala and Lift mailing lists for that thread.) i've written up and coded examples of how this works for 3 different term languages: the usual notion of tuples (resulting in what one would expect, a relational calculus), a graph algebra (resulting in a query language for graphs), and a process algebra. You can find a blog entry about it, with pointers to working code here . Another nice thing about this approach is that it factors nicely through languages with reduction semantics such as lambda calculi or process calculi. So, you can extend the query semantics to include symbolic reduction. In some sense, you turn a model-checker into a query engine allowing you to add Hennessy-Milner-style modal operators to the query language. Best wishes, --greg On Wed, Jun 10, 2009 at 1:42 AM, Vasili I. Galchin wrote: > Hello, > > I'm sorry that this a bit off topic (but both algebras are > categories), but I don't know where to post in order to get an intelligent > answer. Is there any research to base data base queries on Heyting algebra, > i.e. intuistionistic logic? > > Thanks, > > Vasili > [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Thu Jun 11 10:13:29 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 11 Jun 2009 10:13:29 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MEk5t-0000Hr-1z for categories-list@mta.ca; Thu, 11 Jun 2009 10:13:25 -0300 Date: Thu, 11 Jun 2009 13:30:55 +0200 From: Jaap van Oosten MIME-Version: 1.0 To: Reinhard Boerger , categories@mta.ca Subject: categories: Re: Famous unsolved problems in ordinary category theory Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Sender: categories@mta.ca Precedence: bulk Reply-To: Jaap van Oosten Message-Id: Status: O X-Status: X-Keywords: X-UID: 58 Reinhard Boerger wrote: > Dear categorists, > > When I read the question for the first time, I did not know such a problem. > Moreover, my impression was that in category theory one often finds new > results, which had not been conjectured before. Sometimes an important part > of the work is even to develop the right notions. This may explain that > there are less important well-known problems in category theory than in > other areas. > > Nevertheless, I remember a problem that can be easily formulated in pure > category and is still unsolved as far as I know. Bur it does not seem vastly > distributed. Cantor's diagonal says that says that the power set always is > of larger cardinality as the original set. Gavin Wraith suggested the > following generalization to topoi: If for two objects A,B there is a > monomorphism A^B>->B, is there also a monomorphism A>->1? This looks like a > meaningful analogue, and I have not seen an answer in the meantime. The > question can even be asked not only in a topos, but in every cartesian > closed category. Does anybody know anything about progress? > Dear Professor Boerger, there are counterexamples to this in elementary topoi. In the effective topos there are nontrivial objects X such that 2^X is isomorphic to 2 (for example, one can take the object R of real numbers for X; this gives a mono 2^R>->R), and the inclusion N-->N^{P(N)} is an isomorphism (giving a mono N^{P(N)}>->P(N) , where P(N) is the power object of N). I believe the example of 2^R>->R also holds in sheaf toposes where (internally) the object of functions R^R coincides with the object of continuous functions (since R is always connected). Best, Jaap van Oosten > Greetings > Reinhard > > > > [For admin and other information see: http://www.mta.ca/~cat-dist/ ] > [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Thu Jun 11 10:14:10 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 11 Jun 2009 10:14:10 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MEk6Y-0000ND-6n for categories-list@mta.ca; Thu, 11 Jun 2009 10:14:06 -0300 Date: Thu, 11 Jun 2009 14:03:11 +0100 From: Steve Vickers MIME-Version: 1.0 To: "Vasili I. Galchin" , Subject: categories: Re: database theory based on Heyting algebra instead of Boolean algebra Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Sender: categories@mta.ca Precedence: bulk Reply-To: Steve Vickers Message-Id: Status: RO X-Status: X-Keywords: X-UID: 59 Dear Vasili, I'm not sure how much this will answer your questions, but there was some research towards the end of the last century relating databases and powerdomains. In a sense, then, the associated logic of database queries is that of the open sets of the domain, i.e. geometric logic, and hence (at least in its finitary form) a fragment of intuitionistic logic. The names I associate with this work are Carl Gunter and Peter Buneman. I wrote a 1992 paper "Geometric Theories and Databases" that was inspired by them, though its main content was a topos-theoretic construction. Regards, Steve Vickers. Vasili I. Galchin wrote: > Hello, > > I'm sorry that this a bit off topic (but both algebras are > categories), but I don't know where to post in order to get an intelligent > answer. Is there any research to base data base queries on Heyting algebra, > i.e. intuistionistic logic? > > Thanks, > > Vasili > > [For admin and other information see: http://www.mta.ca/~cat-dist/ ] [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Sat Jun 13 09:32:27 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 13 Jun 2009 09:32:27 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MFSML-0001sy-Dx for categories-list@mta.ca; Sat, 13 Jun 2009 09:29:21 -0300 Date: Thu, 11 Jun 2009 23:17:19 +0200 From: Uwe.Wolter@ii.uib.no To: Category mailing list Subject: categories: Re: unsolved problems MIME-Version: 1.0 Content-Type: text/plain;charset=ISO-8859-1;DelSp="Yes";format="flowed" Content-Disposition: inline Content-Transfer-Encoding: quoted-printable Sender: categories@mta.ca Precedence: bulk Reply-To: Uwe.Wolter@ii.uib.no Message-Id: Status: O X-Status: X-Keywords: X-UID: 60 Hi Rafael, > I have developed many perspectives on categories > > As the study of algebraic structures with several objects > As the study of primitive mathematical universe or space (not as =20 > fancy as a topos) > As an unifying tool in mathematics > As a foundation of mathematics (that is structural) > As an abstarction of an abstarction of an abstarction of ... (if you =20 > go to higher categories) > As a generalized theory of representations > > > If i have missed someone please let me know. I came from Algebraic Specifications to Category Theory. When my =20 students (computer science, software engineering) ask me about the =20 benefit of categories I'm referring often to the "Categorical =20 Manifesto" of Jo Goguen. If they insist more and ask "Be honest! What is the REAL reason that =20 some theoreticians like categories so much?" Then I'm trying to be =20 honest and say: Because categories are the winner of the competition =20 "What mathematical structure is closed under the maximal number of =20 "reasonable" constructions". They have just the right amount of =20 structure - not too few, as graphs for example, and not to much, as =20 cpo's for example. And if there is time I'm telling them about the =20 "Erlanger Programm" of Felix Klein. Of course we can turn this statement and say: If a construction =20 doesn't provide a category when the "inputs" are categories, then this =20 construction can not be considered to be a "reasonable construction". Best regards Uwe Wolter [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Mon Jun 15 18:05:26 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 15 Jun 2009 18:05:26 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MGJJ5-0005up-FN for categories-list@mta.ca; Mon, 15 Jun 2009 18:01:31 -0300 From: Makoto Hamana To: categories , "Ellis D. Cooper" Subject: categories: Re: Fundamental Theorem of Category Theory? Mime-Version: 1.0 (generated by tm-edit 7.100) Content-Type: text/plain; charset=US-ASCII Date: Mon, 15 Jun 2009 00:08:58 +0900 (JST) Sender: categories@mta.ca Precedence: bulk Reply-To: Makoto Hamana Message-Id: Status: O X-Status: X-Keywords: X-UID: 61 Dear Ellis, On Fri, 5 June 2009 16:36:23 -0400, Ellis D. Cooper wrote: | There are Fundamental Theorems of Arithmetic, Algebra, Calculus, and | indeed, many more. | My question is, What would be candidates for the Fundamental Theorem | of Category Theory? | Yoneda Lemma comes to my mind. What do you think? I have asked Prof. Yoneda many years ago why Yoneda Lemma is called "Lemma", not "Theorem". He said that perhaps it was a bit about internal of category theory rather than insisting on applications to other mathematics. Doesn't Yoneda Lemma satisfy (c) in Mile Gould's post? I don't know how much Yoneda Lemma is useful in other areas of mathematics, and I have wanted to know it. On Sat, 6 June 2009 23:22:52 +0100, Miles Gould wrote: | My suggestion would be the theorem that left adjoints preserve colimits, | and right adjoints preserve limits. | This may not be the deepest theorem in category theory, but | (a) it's pretty darn deep, | (b) it describes a beautiful connection between two fundamental notions | in the subject, | (c) it admits a huge variety of applications in "ordinary" mathematics. Best Regards, Makoto Hamana [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Mon Jun 15 18:05:26 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 15 Jun 2009 18:05:26 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MGJKe-00061M-S1 for categories-list@mta.ca; Mon, 15 Jun 2009 18:03:08 -0300 From: Ana.Cavalcanti@cs.york.ac.uk Subject: categories: ICFEM 2009: Last Call for Papers - one month to go before the abstract submission deadline To: categories@mta.ca Date: Mon, 15 Jun 2009 02:11:02 +0100 Sender: categories@mta.ca Precedence: bulk Reply-To: Ana.Cavalcanti@cs.york.ac.uk Message-Id: Status: O X-Status: X-Keywords: X-UID: 62 *************************************************************** ICFEM 2009 11th International Conference on Formal Engineering Methods *** Call For Papers *** December 9-12, 2009 Rio de Janeiro, Brazil http://icfem09.inf.puc-rio.br *************************************************************** ICFEM brings together those interested in the application of formal engineering methods to computer systems. Researchers and practitioners, from industry, academia, and government, are encouraged to attend, and to help advance the state of the art. We are interested in work that has been incorporated into real production systems, and in theoretical work that promises to bring practical, tangible benefit. The topics of the conference include, but are not limited to, the following. Formal model-based development and code generation Abstraction and refinement Specification, verification and validation Formal testing approaches Integrated methods and theories for different programming paradigms Formal methods for object and component systems Tool development and integration Experiments involving verified systems Applications of formal methods There will be a special track on UML (but in the scope of the ICFEM remit as described above). ICFEM'09 will have a five-day technical programme, including two days for tutorials and workshops, and three days for a conference. INVITED SPEAKERS Manfred Broy, Germany - FME Invited Lecture Augusto Sampaio, Brazil SUBMISSION AND PUBLICATION Submissions to the conference must not have been published or be concurrently considered for publication elsewhere. All submissions will be judged on the basis of originality, contribution to the field, technical and presentation quality, and relevance to the conference. The proceedings will be published in the Springer Lecture Notes in Computer Science series. Authors of a selection of the accepted papers will be invited to submit an extended version of their work to a SPECIAL ISSUE OF SCIENCE OF COMPUTER PROGRAMMING. Papers should be written in English and not exceed 20 pages in LNCS format (see http://www.springer.de/comp/lncs/authors.html for details). Papers will be processed through the EasyChair conference management system. To submit your paper, please visit http://www.easychair.org/conferences/?conf=icfem09. All queries should be sent to the e-mail address icfem09@inf.puc-rio.br. IMPORTANT DATES Abstract submission deadline: 13 July, 2009 Full-paper submission deadline: 20 July, 2009 Acceptance notification: 8 September, 2009 Final version due: 21 September, 2009 STEERING COMMITTEE Keijiro Araki, Japan Jin Song Dong, Singapore Chris George, China He Jifeng (Chair), China Mike Hinchey, Republic of Ireland Shaoying Liu, Japan John McDermid, UK Tetsuo Tamai, Japan Jim Woodcock, UK ORGANISING COMMITTEE Karin Breitman, Brazil Paulo Rosa, Brazil Vera Werneck, Brazil Jim Woodcock, UK (Conference chair) PROGRAM COMMITTEE Luca Aceto, Iceland Nazareno Aguirre, Argentina Bernhard Aichernig, Austria Keijiro Araki, Japan Karin Breitman, Brazil (Chair) Michael Butler, UK Andrew Butterfield, Republic of Ireland Ana Cavalcanti, UK (Chair) Rance Cleaveland, USA Jim Davies, UK Jin Song Dong, Singapore Neil Evans, UK Colin Fidge, Australia John Fitzgerald, UK Joaquim Gabarro, Spain Alex Garcia, Brazil Stefania Gnesi, Italy James Harland, Australia Hermann Haeusler, Brazil Mike Hinchey, Republic of Ireland Thierry Jeron, France Steve King, UK Kim Larsen, Denmark K. Rustan M. Leino, USA Michael Leuschel, Germany Shaoying Liu, Japan Zhiming Liu, China Patricia Machado, Brazil Tiziana Margaria, Germany Tom Maibaum, Canada Ana Melo, Brazil Dominique Mery, France David Naumann, USA Ken Robinson, Australia Markus Roggenbach, UK Helen Treharne, UK T.H. Tse, China Mark Utting, New Zealand Marcel Verhoef, The Netherlands Farn Wang, Taiwan Heike Wehrheim, Germany Wang Yi, Sweden Fatiha Zaidi, France [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Tue Jun 16 13:02:21 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 16 Jun 2009 13:02:21 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MGb4q-0005vE-W1 for categories-list@mta.ca; Tue, 16 Jun 2009 13:00:01 -0300 Date: Mon, 15 Jun 2009 14:58:59 -0700 From: Vaughan Pratt MIME-Version: 1.0 To: categories Subject: categories: Re: Fundamental Theorem of Category Theory? Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Sender: categories@mta.ca Precedence: bulk Reply-To: Vaughan Pratt Message-Id: Status: O X-Status: X-Keywords: X-UID: 63 Apropos of the Yoneda Lemma, is there some reason why it is usually stated on its own rather than as one direction of a characterization of categories of presheaves on J? Unless I've overlooked or misunderstood something it seems to me that the Yoneda Lemma should state that C is a category of presheaves on J if and only if there exists a full, faithful, and dense functor from J to C. This should generalize the characterization of an Archimedean field as any dense extension of the rationals. Vaughan Pratt [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Tue Jun 16 13:07:26 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 16 Jun 2009 13:07:26 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MGbBF-0006VM-UM for categories-list@mta.ca; Tue, 16 Jun 2009 13:06:37 -0300 Date: Mon, 15 Jun 2009 18:02:53 -0400 To: Makoto Hamana ,categories@mta.ca From: "Ellis D. Cooper" Subject: categories: Fundamental Theorem of Category Theory? Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Sender: categories@mta.ca Precedence: bulk Reply-To: "Ellis D. Cooper" Message-Id: Status: O X-Status: X-Keywords: X-UID: 64 Dear Makoto, At 11:08 AM 6/14/2009, you wrote: >I don't know how much Yoneda Lemma is useful in other areas of >mathematics, and >I have wanted to know it. The Yoneda Lemma came to mind partly because of M. Barr and C. Wells book "Toposes, Triples and Theories." Its Preface recounts that in the sense of Lawvere's insight -- a mathematical theory corresponds "roughly to the definition of a class of mathematical objects" -- toposes, triples, and theories are beautifully connected fundamental notions. Barr-Wells write that the Yoneda Embeddings Theorem, "the first of several important consequences" of the Yoneda Lemma, "in one way or another is used in practically every mathematical argument in this book." (p. 27) Perhaps subscribers to this list would care to comment on how specific results in this book apply or relate to computer science, other areas of mathematics, logic, or physics. All the best, Ellis D. Cooper [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Tue Jun 16 13:08:07 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 16 Jun 2009 13:08:07 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MGbC5-0006ZA-JS for categories-list@mta.ca; Tue, 16 Jun 2009 13:07:29 -0300 Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed Content-Transfer-Encoding: 7bit From: Ross Street Subject: categories: Re: Fundamental Theorem of Category Theory Date: Tue, 16 Jun 2009 08:35:34 +1000 To: categories Sender: categories@mta.ca Precedence: bulk Reply-To: Ross Street Message-Id: Status: O X-Status: X-Keywords: X-UID: 65 Dear All The Fundamental Theorem of Category Theory, to my mind, encompasses all the facts surrounding the fact that the presheaf category PA is the bicategorically free small-cocompletion of a small category A. With my students I have always called it: "The Whole Kan Business". It can be expressed something like this: Theorem. For each small category A and small-cocomplete category X, left Kan extension along the Yoneda embedding y_A : A --> PA provides an equivalence of categories [A,X] --> Cocts[PA,X] where the codomain is the full subcategory of the functor category [PA,X] consisting of the small-colimit-preserving functors. Moreover, the value of the equivalence at j : A --> X has a right adjoint given by x |--> X(j-,x). Ross [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Tue Jun 16 13:09:08 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 16 Jun 2009 13:09:08 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MGbD2-0006fC-KX for categories-list@mta.ca; Tue, 16 Jun 2009 13:08:28 -0300 From: Hasse Riemann To: Category mailing list Subject: categories: Existence of very high categories Date: Tue, 16 Jun 2009 07:48:49 +0000 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Sender: categories@mta.ca Precedence: bulk Reply-To: Hasse Riemann Message-Id: Status: O X-Status: X-Keywords: X-UID: 66 =20 Hi all categorists =20 I am not an expert on oo-categories but i am sure there is a structure to the "class" of all omega-categories. I hope all this will not depend on the definition of an oo-category. 6> Is the "class" of oo-categories of a certain recursive depth always an oo-category of depth one higher than the previous depth? I think yes for both strict and weak oo-categories. =20 What should the "class" of all n-categories in Makkais foundation be called to describe it technically accurately? An oo-cosmos? in the categorical sense of a cosmos. I am not sure but this "class" maby also contain all oo-categories. =20 Are there different strict/weak n-categories with n any infinite ordinal number omega? omega does remind of an ordinal number. The category need not to be accessible by forming categories of categories= =2C just satisfy some axioms of an strict/weak oo-category for oo=3Domega. There might be a better definition of an omega-category if it is necessary at all=2C i don't know. =20 Best regards Rafael Borowiecki [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Wed Jun 17 10:08:10 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 17 Jun 2009 10:08:10 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MGuqq-0006e1-Ke for categories-list@mta.ca; Wed, 17 Jun 2009 10:06:52 -0300 Date: Wed, 17 Jun 2009 07:58:36 +1000 Subject: categories: Re: Fundamental Theorem of Category Theory? From: Steve Lack To: Vaughan Pratt , categories Mime-version: 1.0 Content-type: text/plain; charset="US-ASCII" Content-transfer-encoding: 7bit Sender: categories@mta.ca Precedence: bulk Reply-To: Steve Lack Message-Id: Status: O X-Status: X-Keywords: X-UID: 67 Dear Vaughan, Your proposed characterization is actually a characterization of full subcategories of [J^op,Set] containing the representables. To get the whole presheaf category you should add that C is cocomplete, and that homming out of objects in J is cocontinuous (i.e. C(j,-) is cocontinuous for all j in J). Steve. On 16/06/09 7:58 AM, "Vaughan Pratt" wrote: > Apropos of the Yoneda Lemma, is there some reason why it is usually > stated on its own rather than as one direction of a characterization of > categories of presheaves on J? Unless I've overlooked or misunderstood > something it seems to me that the Yoneda Lemma should state that C is a > category of presheaves on J if and only if there exists a full, > faithful, and dense functor from J to C. > > This should generalize the characterization of an Archimedean field as > any dense extension of the rationals. > > Vaughan Pratt > [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Wed Jun 17 10:08:10 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 17 Jun 2009 10:08:10 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MGupf-0006Xg-6Q for categories-list@mta.ca; Wed, 17 Jun 2009 10:05:39 -0300 Date: Tue, 16 Jun 2009 20:34:26 +0100 (BST) From: "Prof. Peter Johnstone" To: Makoto Hamana , Subject: categories: Re: Fundamental Theorem of Category Theory? MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed Sender: categories@mta.ca Precedence: bulk Reply-To: "Prof. Peter Johnstone" Message-Id: Status: O X-Status: X-Keywords: X-UID: 68 On Mon, 15 Jun 2009, Makoto Hamana wrote: > I have asked Prof. Yoneda many years ago why Yoneda Lemma is > called "Lemma", not "Theorem". He said that perhaps it was a > bit about internal of category theory rather than insisting > on applications to other mathematics. Doesn't Yoneda Lemma > satisfy (c) in Mile Gould's post? I don't know how much > Yoneda Lemma is useful in other areas of mathematics, and > I have wanted to know it. > When I lecture on category theory to first-year graduate students, I tell them there are two things they should remember about the Yoneda Lemma: it isn't a lemma, and it was never published by Yoneda. In this respect it resembles that bulwark of the British constitution, the Lord Privy Seal (who is none of the three things that his title claims). Peter Johnstone [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Wed Jun 17 10:08:10 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 17 Jun 2009 10:08:10 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MGuq7-0006a3-GZ for categories-list@mta.ca; Wed, 17 Jun 2009 10:06:07 -0300 Date: Tue, 16 Jun 2009 16:23:59 -0400 To: categories@mta.ca From: "Ellis D. Cooper" Subject: categories: Fundamental Theorem of Category Theory? Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Sender: categories@mta.ca Precedence: bulk Reply-To: "Ellis D. Cooper" Message-Id: Status: O X-Status: X-Keywords: X-UID: 69 The archived file of this list http://www.mta.ca/~cat-dist/archive/1992/92-08.txt contains comments by Colin McLarty, Michael Barr, and Jim Lambek about the Yoneda lemma. Also, Peter Freyd gives an account of the connection (via Mac Lane and Barry Mitchell) between Prof. Yoneda and the eponymous lemma. Ellis D. Cooper [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Wed Jun 17 10:20:35 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 17 Jun 2009 10:20:35 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MGv3s-0000Ae-Nm for categories-list@mta.ca; Wed, 17 Jun 2009 10:20:20 -0300 Date: Tue, 16 Jun 2009 19:32:33 -0300 (ADT) From: Bob Rosebrugh To: categories Subject: categories: Easik 2.0: categorical database design and manipulation MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: categories@mta.ca Precedence: bulk Reply-To: Bob Rosebrugh Message-Id: Status: RO X-Status: X-Keywords: X-UID: 70 Version 2.0 of Easik has been released. Easik is a Java application with a graphical environment for database design, and data entry and manipulation using Entity-Attribute (EA) sketches. EA sketches are the syntactic basis for the categorical Sketch Data Model which extends and enhances the standard Entity-Relationship-Attribute data model. In the graphical interface, Easik supports design of EA sketches and their export to an SQL database schema. The exported schema has triggers and procedures to enforce the graphically specified constraints. Easik also provides connectivity to the common open-source database management systems MySQL and PostgreSQL Version 2.0 enhancements include: - multiple sketch editing through an overview - support for views (subject to SQL limitations) - data entry and manipulation from the the graphical interface. The application is available at http://mathcs.mta.ca/research/rosebrugh/Easik or follow the link from http://www.mta.ca/~rrosebru/ Downloads include: - user instructions - an executable Java archive (jar) file - Java source code - example designs The contributors to Easik are Robert Fletcher, Kevin Green, Vera Ranieri, Jason Rhinelander, Andrew Wood and Robert Rosebrugh with support from NSERC Canada and Mount Allison University. Extensive information about the Sketch Data Model is in articles available from the web pages of the poster and Michael Johnson. We look forward to receiving comments and reports from users. Bob Rosebrugh [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Wed Jun 17 10:21:01 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 17 Jun 2009 10:21:01 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MGv4T-0000Du-LU for categories-list@mta.ca; Wed, 17 Jun 2009 10:20:57 -0300 Date: Tue, 16 Jun 2009 20:28:28 -0700 From: Vaughan Pratt MIME-Version: 1.0 To: categories Subject: categories: Re: Fundamental Theorem of Category Theory? Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Sender: categories@mta.ca Precedence: bulk Reply-To: Vaughan Pratt Message-Id: Status: O X-Status: X-Keywords: X-UID: 71 Steve Lack wrote: > Your proposed characterization is actually a characterization of full > subcategories of [J^op,Set] containing the representables. Right, that's what I meant by "*a* category of presheaves on J" (as opposed to *the* category of all presheaves on J), the point of my analogy with Archimedean fields (as opposed to the field of all reals). > To get the whole > presheaf category you should add that C is cocomplete, Right, just as to get all of the reals one should say that the Archimedean field is complete. For situations where one doesn't need the whole thing it is convenient to be able to characterize the categorical counterpart of an Archimedean field, with J in place of Q, as any full, faithful and dense extension of J. Density serves to keep the extension inside [J^op,Set], just as it keeps Archimedean fields inside R. > and that homming out > of objects in J is cocontinuous (i.e. C(j,-) is cocontinuous for all j in > J). Am I missing something? I was thinking that followed from density of J in C. Vaughan [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Wed Jun 17 10:22:00 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 17 Jun 2009 10:22:00 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MGv5P-0000Jp-Qa for categories-list@mta.ca; Wed, 17 Jun 2009 10:21:55 -0300 From: "Reinhard Boerger" To: "'Ellis D. Cooper'" , Subject: categories: Re: Fundamental Theorem of Category Theory? Date: Wed, 17 Jun 2009 09:29:46 +0200 MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Sender: categories@mta.ca Precedence: bulk Reply-To: "Reinhard Boerger" Message-Id: Status: O X-Status: X-Keywords: X-UID: 72 Dear all, I strongly agree to Ellis Gould's quote of Bill Lawvere's remark on the Yoneda Lemma: > -- a mathematical theory corresponds "roughly to > the definition of a class > of mathematical objects" One of the most important points in category theory are universal properties. The existence of universal solutions is equivalent to the representability of certain functors - at least under reasonable smallness conditions. This is closely related to the Yoneda Lemma; therefore it is really one of the fundamental theorems to me. Greetinge Reinhard [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Wed Jun 17 10:23:18 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 17 Jun 2009 10:23:18 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MGv6e-0000Ur-LU for categories-list@mta.ca; Wed, 17 Jun 2009 10:23:12 -0300 To: categories@mta.ca Subject: categories: FICS'09 2nd Call for papers - Fixed Points in Computer Science (CSL'09 workshop) Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: quoted-printable Date: Wed, 17 Jun 2009 12:26:45 +0300 From: Tarmo Uustalu Sender: categories@mta.ca Precedence: bulk Reply-To: Tarmo Uustalu Message-Id: Status: O X-Status: X-Keywords: X-UID: 73 2nd Call for Papers (Extended Abstracts) 6th Workshop on Fixed Points in Computer Science, FICS 2009 Coimbra, Portugal, 12-13 September 2009, a satellite workshop of CSL 2009, colocated with PPDP 2009, LOPSTR 2009 http://cs.ioc.ee/fics09/ Background Fixed points play a fundamental role in several areas of computer science and logic by justifying induction and recursive definitions. The construction and properties of fixed points have been investigated in many different frameworks such as: design and implementation of programming languages, program logics, databases. The aim of the workshop is to provide a forum for researchers to present their results to those members of the computer science and logic communities who study or apply the theory of fixed points. Previous workshops where held in Brno (1998, MFCS/CSL workshop), Paris (2000, LC workshop), Florence (2001, PLI workshop), Copenhagen (2002, LICS (FLoC) workshop), Warsaw (2003, ETAPS workshop). Topics include, but are not restricted to: * categorical, metric and ordered fixed point models * fixed points in algebra and coalgebra * fixed points in languages and automata * fixed points in programming language semantics * the mu-calculus and fixed points in modal logic * fixed points in process algebras and process calculi * fixed points in the lambda-calculus, = functional programming and type theory * fixed points in relation to dataflow and circuits * fixed points in logic programming and theorem proving * finite model theory, descriptive complexity theory, = fixed points in databases Invited speakers Javier Esparza (Technische Universit=E4t M=FCnchen) Yde Venema (Universiteit van Amsterdam) a 3rd invited speaker tba Contributed talks Selection of contributed talks is based on extended abstracts/short papers of 3..6 pp formatted with easychair.cls. Submission is via EasyChair by 30 June 2009. The authors will be notified of acceptance/rejection by 21 July 2009. Camera-ready versions of the accepted contributions, due by 11 August 2009, will be published for distribution at the workshop as a technical report. If the number and quality of submissions and accepted talks warrant this, EDP Sciences will publish a special issue of Theoretical Informatics and Applications. The special issues of the previous editions of FICS appeared in the same journal. Programme committee Yves Bertot (INRIA Sophia Antipolis) Anuj Dawar (University of Cambridge) Peter Dybjer (Chalmers University of Technology) Zolt=E1n =C9sik (University of Szeged) Masahito Hasegawa (Kyoto University) Anna Ing=F3lfsd=F3ttir (Reykjavik University) Ralph Matthes (IRIT, Toulouse) (co-chair) Jan Rutten (CWI and Vrije Universiteit Amsterdam) Luigi Santocanale (LIF, Marseille) Alex Simpson (University of Edinburgh) Tarmo Uustalu (Institute of Cybernetics, Tallinn) (co-chair) Igor Walukiewicz (LaBRI, Bordeaux) Sponsors EXCS, Estonian Centre of Excellence in Computer Science [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Wed Jun 17 20:19:12 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 17 Jun 2009 20:19:12 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MH4OB-0005vY-Jr for categories-list@mta.ca; Wed, 17 Jun 2009 20:17:55 -0300 Date: Wed, 17 Jun 2009 16:42:58 -0300 From: Dietmar Schumacher MIME-Version: 1.0 To: categories@mta.ca, Reinhard.Boerger@FernUni-Hagen.de Subject: categories: universality Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Sender: categories@mta.ca Precedence: bulk Reply-To: Dietmar Schumacher Message-Id: Status: O X-Status: X-Keywords: X-UID: 74 Hi Reinhard, when I entered category theory I must have gotten on the nerves of a student of logic who found it necessary to point out to me that universality is as good as one knows the ambient universe. That remark came around to bite me once more when I recently pontificated that under the same assumptions on a category S, under which NNO's in S imply that the category of categories in S is monadic over the category of directed graphs in S, the converse would be true. Dietmar (Schumacher) [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Wed Jun 17 20:19:12 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 17 Jun 2009 20:19:12 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MH4Nj-0005uD-3Q for categories-list@mta.ca; Wed, 17 Jun 2009 20:17:27 -0300 Date: Wed, 17 Jun 2009 13:04:56 -0400 From: "Fred E.J. Linton" To: Subject: categories: Re: Fundamental Theorem of Category Theory? Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Sender: categories@mta.ca Precedence: bulk Reply-To: "Fred E.J. Linton" Message-Id: Status: O X-Status: X-Keywords: X-UID: 75 Once, long, long ago, I looked up the Yoneda paper = then cited as source for the Y.L. = Agreed: not there. = But, in another Yoneda paper ("On Ext and exact sequences", perhaps, I'm relying on memory alone, here), it *is* there, not called Y.L., of course, but describing, as I recall, = the connection between n.t.(hom(A, -), hom(B, -)) and = hom(B, A) in the case that the hom-sets are the = Ext equivalence classes (the only case of interest = for that paper). It didn't take much, either, to see the underlying = Y.L. structure in the main proof there. Cheers (and more detail, if called for, once I'm back from Montrreal), = -- Fred ------ Original Message ------ Received: Wed, 17 Jun 2009 09:22:42 AM EDT From: "Prof. Peter Johnstone" To: Makoto Hamana , Subject: categories: Re: Fundamental Theorem of Category Theory? > On Mon, 15 Jun 2009, Makoto Hamana wrote: > = > > I have asked Prof. Yoneda many years ago why Yoneda Lemma is > > called "Lemma", not "Theorem". He said that perhaps it was a > > bit about internal of category theory rather than insisting > > on applications to other mathematics. Doesn't Yoneda Lemma > > satisfy (c) in Mile Gould's post? I don't know how much > > Yoneda Lemma is useful in other areas of mathematics, and > > I have wanted to know it. > > > When I lecture on category theory to first-year graduate students, I > tell them there are two things they should remember about the > Yoneda Lemma: it isn't a lemma, and it was never published by Yoneda. > In this respect it resembles that bulwark of the British constitution, > the Lord Privy Seal (who is none of the three things that his title > claims). > = > Peter Johnstone > = [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Wed Jun 17 20:19:12 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 17 Jun 2009 20:19:12 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MH4P4-0005zE-9I for categories-list@mta.ca; Wed, 17 Jun 2009 20:18:50 -0300 Date: Wed, 17 Jun 2009 22:03:42 +0100 (BST) From: James Worrell To: categories@mta.ca Subject: categories: Two Fully Funded PhD Positions at Oxford University Computing Laboratory MIME-Version: 1.0 Content-Type: TEXT/PLAIN; CHARSET=ISO-8859-1; FORMAT=flowed Content-ID: Content-Transfer-Encoding: quoted-printable Sender: categories@mta.ca Precedence: bulk Reply-To: James Worrell Message-Id: Status: O X-Status: X-Keywords: X-UID: 76 The Verification Research Group is offering two D.Phil studentships in Ox= ford=20 University's Computing Laboratory (web.comlab.ox.ac.uk). These positions= are=20 associated with the EPSRC project "Model Checking Real-Time Systems: Algo= rithms=20 and Complexity'' under the supervision of Dr James Worrell, which will de= al=20 with a logical and automata-theoretic framework for model checking real-t= ime=20 systems. The studentships are fully funded at EU fees level (non-EU candidates wil= l need=20 supplementary funding) for 3 =C2=BD years from 1st October 2009. Students= admitted with a later start date (but not later than April 1st 2010) will receive = a=20 guarantee of 3 years funding. Each studentship includes a stipend of at = least=20 =C2=A313290 per year as well as provision for travel to conferences. The studentships will suit candidates with a strong background in theoret= ical=20 computer science, including at least one of the following areas: algorith= ms,=20 automata theory, complexity theory and logic. Please contact James Worrell (jbw@comlab.ox.ac.uk) for further details. [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Wed Jun 17 20:19:39 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 17 Jun 2009 20:19:39 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MH4Po-00062c-Fo for categories-list@mta.ca; Wed, 17 Jun 2009 20:19:36 -0300 Date: Thu, 18 Jun 2009 08:45:25 +1000 Subject: categories: Re: Fundamental Theorem of Category Theory? From: Steve Lack To: Vaughan Pratt , categories Mime-version: 1.0 Content-type: text/plain; charset="US-ASCII" Content-transfer-encoding: 7bit Sender: categories@mta.ca Precedence: bulk Reply-To: Steve Lack Message-Id: Status: O X-Status: X-Keywords: X-UID: 77 On 17/06/09 1:28 PM, "Vaughan Pratt" wrote: > Steve Lack wrote: >> Your proposed characterization is actually a characterization of full >> subcategories of [J^op,Set] containing the representables. > > Right, that's what I meant by "*a* category of presheaves on J" (as > opposed to *the* category of all presheaves on J), the point of my > analogy with Archimedean fields (as opposed to the field of all reals). > Hmm. Not sure if you mean you're allowing any full subcategory of [J^op,Set]; if so then you should drop the requirement that J-->C be fully faithful. >> To get the whole >> presheaf category you should add that C is cocomplete, > > Right, just as to get all of the reals one should say that the > Archimedean field is complete. For situations where one doesn't need > the whole thing it is convenient to be able to characterize the > categorical counterpart of an Archimedean field, with J in place of Q, > as any full, faithful and dense extension of J. Density serves to keep > the extension inside [J^op,Set], just as it keeps Archimedean fields > inside R. > >> and that homming out >> of objects in J is cocontinuous (i.e. C(j,-) is cocontinuous for all j in >> J). > > Am I missing something? I was thinking that followed from density of J > in C. > No. The category Setf of finite sets has a fully faithful dense inclusion in to the (presheaf) category Set of all sets, but Set is not [Setf^op,Set]. Steve. [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Thu Jun 18 06:43:02 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 18 Jun 2009 06:43:02 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MHE7e-000558-BG for categories-list@mta.ca; Thu, 18 Jun 2009 06:41:30 -0300 Date: Wed, 17 Jun 2009 19:27:34 -0500 (CDT) From: Matsuoka Takuo To: Makoto Hamana cc: categories , "Ellis D. Cooper" Subject: categories: Re: Fundamental Theorem of Category Theory? MIME-Version: 1.0 Content-Type: TEXT/PLAIN; format=flowed; charset=US-ASCII Sender: categories@mta.ca Precedence: bulk Reply-To: Matsuoka Takuo Message-Id: Status: O X-Status: X-Keywords: X-UID: 78 Dear categorists, > I have asked Prof. Yoneda many years ago why Yoneda Lemma is > called "Lemma", not "Theorem". He said that perhaps it was a > bit about internal of category theory rather than insisting > on applications to other mathematics. Doesn't Yoneda Lemma > satisfy (c) in Mile Gould's post? I don't know how much > Yoneda Lemma is useful in other areas of mathematics, and > I have wanted to know it. > | (c) it admits a huge variety of applications in "ordinary" mathematics. I find this intersting, but I do not quite agree with Prof. Yoneda! In order to challenge his claim, I would like to try making a list (which I fear will not be "huge in variety") of some instances I know of in mathematics where representable functors play central roles, and hope some other people could do similar. While I know that I am not a particularly well qualified person to write the part I am taking, I view this as a great opportunity to share ideas from various different fields! (I hope this is not off the topic of the list.) - Given a category C of some mathematical objects, it is often equipped with a "forgetful" functor C -> Set, so objects of C can be thought of as sets equipped with some specific sort of structure. Let us call it a C-structure. Then a C-structure on an object X of _any_ category can be defined as a way to factorize the functor [ ,X], represented by X, through the forgetful functor C -> Set. If C is the category of groups, then The Lemma implies that giving a group structure on X is the same as giving structure maps on X which are in analogy with the group operations for an ordinary group. This readily generalizes for any sort of algebraic structure, and this is related to Lawvere's notion of algebraic theories. One can further replace the category Set with some other closed category such as that of Abelian groups, using the language of enriched category theory. - Schemes in algebraic geometry can fruitfully be viewed as sheaves on the opposite category Aff of that of commutative rings. Those schemes actually represented by rings are called affine schemes. Thus, the category of affine schemes is opposite to the category of rings, and is fully embedded in the category of all schemes. The Yoneda lemma is a basic tool for the study of schemes. - Some presheaves on the category of (affine) schemes which fail to be sheaves can more naturally be thought of as a groupoid-valued (rather than set-valued) presheaves which can be represented by geometric objects called algebraic stacks (which generalize schemes). - Let G be a group (in a suitable category of "spaces"). In the theory of principal bundles, the functor which assigns to a space X, the set of principal G-bundles over X, modulo isomorphism, is represented (in the homotopy category of spaces) by the so called classifying space BG of G. That is, BG "classifies" principal G-bundles. Then The Lemma implies a fundamental theorem that characteristic classes for bundles are the same as cohomology classes of the classifying space. - Similarly, one can consider the classifying stack of a group scheme (i.e. scheme with group structure), in particular a finite group, G. - Every spectrum, in the sense of stable homotopy theory, represents a so-called generalized cohomology theory, and vice versa. The Lemma then gives a way to compute natural operations between theories. The results of computation of the algebra formed by operations on the "ordinary" cohomology theory (with coefficients in a prime field), known by the name the Steenrod algebra, is the input of the Adams spectral sequence, which in turn computes (in principle) the stable homotopy groups of spheres, which is of central interest in the field. - On the category of commutative ring spectra, which are 'by definition' spectra with commutative ring structure, the (covariant) functor classifying characteristic classes, or "orientations", in the associated multiplicative (because of the ring structure) generalized cohomology theories is represented by the so-called Thom spectrum. Quillen pointed out that the variant MU of Thom spectrum, classifying Chern classes, or orientations for complex vector bundles, corresponds to the moduli stack of formal groups (i.e. the stack classifying formal groups) thus discovering a deep connection between homotopy theory and algebraic geometry. MU has since been a key object in stable homotopy theory. - One of the greatest recent achievements in algebraic topology is the construction of a spectrum called tmf, the topological modular forms. It is the global section of a certain sheaf of commutative ring spectra over the moduli stack of elliptic curves. From this sheaf, one can recover the Adams-type spectral sequence associated to tmf. According to Lurie, this sheaf is actually the structure sheaf of the moduli stack classifying "oriented elliptic curves" over commutative ring spectra, or, to be in the correct variance, over derived affine schemes, in the world of derived algebraic geometry. This extremely beautiful viewpoint enlightens the meaning of Quillen's discovery just mentioned. The disputed proposition (whether it is a theorem or a lemma) or its appropriate generalization applies to any of these situations. Another family of examples of representable functors would be supplied by those represented by "dualizing objects" appearing in various contexts. However, at this moment, I only have a vague idea of how the Yoneda lemma would imply something useful in this situation. I think experts out there are well in order to help me with this! Concerning the discussion on the "fundamental theorem" of category theory, it might worth remarking that preservation of limits by right adjoints (and its dual) are a corollary of the more fundamental fact that adjoints compose, granted uniqueness of the adjoint functor. The last is notably one of the important consequences of The "Lemma". Also, in addition to the claimed prominent applicability in mathematics, the Yoneda lemma has remarkably neat and witty statement: "Every presheaf represents itself." Best wishes, Takuo On Mon, 15 Jun 2009, Makoto Hamana wrote: > Dear Ellis, > > On Fri, 5 June 2009 16:36:23 -0400, Ellis D. Cooper wrote: > | There are Fundamental Theorems of Arithmetic, Algebra, Calculus, and > | indeed, many more. > | My question is, What would be candidates for the Fundamental Theorem > | of Category Theory? > | Yoneda Lemma comes to my mind. What do you think? > > I have asked Prof. Yoneda many years ago why Yoneda Lemma is > called "Lemma", not "Theorem". He said that perhaps it was a > bit about internal of category theory rather than insisting > on applications to other mathematics. Doesn't Yoneda Lemma > satisfy (c) in Mile Gould's post? I don't know how much > Yoneda Lemma is useful in other areas of mathematics, and > I have wanted to know it. > > On Sat, 6 June 2009 23:22:52 +0100, Miles Gould wrote: > | My suggestion would be the theorem that left adjoints preserve colimits, > | and right adjoints preserve limits. > | This may not be the deepest theorem in category theory, but > | (a) it's pretty darn deep, > | (b) it describes a beautiful connection between two fundamental notions > | in the subject, > | (c) it admits a huge variety of applications in "ordinary" mathematics. > > Best Regards, > Makoto Hamana > > > > [For admin and other information see: http://www.mta.ca/~cat-dist/ ] > [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Thu Jun 18 06:43:02 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 18 Jun 2009 06:43:02 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MHE8m-00058A-K3 for categories-list@mta.ca; Thu, 18 Jun 2009 06:42:40 -0300 Date: Thu, 18 Jun 2009 01:33:58 -0700 From: Vaughan Pratt MIME-Version: 1.0 To: categories Subject: categories: Re: Fundamental Theorem of Category Theory? Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Sender: categories@mta.ca Precedence: bulk Reply-To: Vaughan Pratt Message-Id: Status: O X-Status: X-Keywords: X-UID: 79 On 6/17/2009 3:45 PM, Steve Lack wrote: > Hmm. Not sure if you mean you're allowing any full subcategory of > [J^op,Set]; if so then you should drop the requirement that J-->C be fully > faithful. By "category of presheaves on J" I had in mind retaining J as part of it. >> Am I missing something? I was thinking that followed from density of J >> in C. >> > > No. The category Setf of finite sets has a fully faithful dense inclusion in > to the (presheaf) category Set of all sets, but Set is not [Setf^op,Set]. Oops, right, I was mixing up cocomplete and cocompletion-of. (Actually I don't think in terms of either, I find it easier to think of [J^op,Set] as the maximal dense extension of J up to equivalence, in the sense that all dense extensions of J are full subcategories of it.) Vaughan [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Fri Jun 19 16:48:04 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 19 Jun 2009 16:48:04 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MHk2s-00057S-1D for categories-list@mta.ca; Fri, 19 Jun 2009 16:46:42 -0300 From: Matsuoka Takuo To: categories Subject: categories: Re: Fundamental Theorem of Category Theory? MIME-Version: 1.0 Content-Type: TEXT/PLAIN; format=flowed; charset=US-ASCII Sender: categories@mta.ca Precedence: bulk Reply-To: Matsuoka Takuo Message-Id: Date: Fri, 19 Jun 2009 16:46:42 -0300 Status: O X-Status: X-Keywords: X-UID: 80 Dear categorists, Although I know this thread is basically over, I would like to thank Paul Taylor for (earlier than my previous post) pointing out that not every subject of mathematics has or should have its single "fundamental theorem". While I think one theorem can be more important than another, what may more worth discussing (still not necessarily here on the list) could be what fundamental theorems are wanted for the future. Best wishes, Takuo [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Fri Jun 19 16:48:04 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 19 Jun 2009 16:48:04 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MHk1h-000533-CR for categories-list@mta.ca; Fri, 19 Jun 2009 16:45:29 -0300 Date: Fri, 19 Jun 2009 10:26:13 +0100 From: Steve Vickers MIME-Version: 1.0 To: Categories Subject: categories: Topology on cohomology groups Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Sender: categories@mta.ca Precedence: bulk Reply-To: Steve Vickers Message-Id: Status: O X-Status: X-Keywords: X-UID: 81 A cohomology group can easily be an infinite power of the coefficient group. But such a group has a natural non-discrete topology, namely the compact-open (which in this case is also the product topology). Are there approaches to cohomology that, as part of the process, also supply topologies on the cohomology groups? [I'm trying to understand the topos-theoretic account of cohomology as in Johnstone's "Topos Theory". But it looks heavily dependent on having a classical base topos, since it uses the classical proof of sufficiency of injectives (together with the existence of Barr covers) to deduce the same property internally in any Grothendieck topos. For a more fully constructive theory I wonder if one needs to take better care of the topologies.] Steve Vickers. [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Sun Jun 21 14:41:15 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 21 Jun 2009 14:41:15 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MIR1v-0006TC-LN for categories-list@mta.ca; Sun, 21 Jun 2009 14:40:35 -0300 Mime-Version: 1.0 (Apple Message framework v753.1) Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed To: categories@mta.ca From: David Spivak Subject: categories: monad: (k-Set \downarrow -): Set -->Set Date: Fri, 19 Jun 2009 15:33:03 -0700 Sender: categories@mta.ca Precedence: bulk Reply-To: David Spivak Message-Id: Status: O X-Status: X-Keywords: X-UID: 82 Dear Categorists, Does anyone know a name for the monad described below and/or whether it has been studied? Let k-Set denote the category of k-small sets (for some small regular cardinal k). For a set S, we denote by T(S)=(k-Set \downarrow {S}) the set whose elements are pairs (K,f), where K is a k-small set and f:K-->S is a function. This construction is functorial in S. I claim that the endo-functor T: Set -->Set is a monad. The identity transformation S-->T(S) is given by "singleton set" and the multiplication transformation TT(S)-->T(S) is given by Grothendieck construction. (There is a similar monad on Cat, where we replace k-Set with k-Cat.) Does this monad T have a name? Has it been studied? Thank you, David [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Sun Jun 21 14:41:15 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 21 Jun 2009 14:41:15 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MIR0y-0006QR-9j for categories-list@mta.ca; Sun, 21 Jun 2009 14:39:36 -0300 Date: Fri, 19 Jun 2009 17:39:57 -0400 (EDT) From: Andrew Salch To: Steve Vickers , Subject: categories: Re: Topology on cohomology groups MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed Sender: categories@mta.ca Precedence: bulk Reply-To: Andrew Salch Message-Id: Status: O X-Status: X-Keywords: X-UID: 83 This certain does happen--if E^* is a generalized cohomology theory, and X is an infinite complex, we often want to topologize E^*(X) by the inverse limit of the E-cohomology of the finite skeleta of X. This is why, for example, if E is a complex-oriented cohomology theory, the E-cohomology of infinite-dimensional complex projective space is a power series ring (and not merely a polynomial ring), in one variable, over the coefficient ring E^*. This is sometimes important and useful in topology (for example, in the situation above, where one uses the above description of E^*(CP^{\infty}) to associate a 1-dimensional formal group law to E), and sometimes it's more just a hassle: for example, the early papers on the Adams-Novikov spectral sequence used MU-cohomology (i.e., complex cobordism), and this necessarily meant keeping track of the topology on MU^*(X) of various spectra E, since for example MU^*(MU), the ring of stable natural transformations of MU^*, has infinite homogeneous sums, and one had to handle completed tensor products of MU^*(MU)-modules; the modern way is to use generalized homology instead of generalized cohomology for these generalized Adams spectral sequences, which does away with the topologies and the need for completed tensor products (of course, the price one pays is that one is then, in the case of MU, dealing with MU_*(MU)-comodules rather than (topological) MU^*(MU)-modules, and computing Cotor rather than Ext; but this seems to be worth it). There's some discussion of this in Ravenel's green book. The paper on unstable operations by Boardman, Johnson, and Wilson in the Handbook of Algebraic Topology also includes some discussion and some nice manipulations of topologies (again, coming from the finite skeleta of an infinite complex) on some generalized cohomology rings and modules. There are also generalized homology theories, like the Morava E-theories, which occur as completions of other generalized homology theories, and so E_*(X) naturally has a topology (coming from the completion) when E is one of these theories; recent developments in stable homotopy theory make it seem likely that there will be more such theories in our future. Hope this is useful to you, Andrew S. On Fri, 19 Jun 2009, Steve Vickers wrote: > A cohomology group can easily be an infinite power of the coefficient > group. But such a group has a natural non-discrete topology, namely the > compact-open (which in this case is also the product topology). > > Are there approaches to cohomology that, as part of the process, also > supply topologies on the cohomology groups? > > [I'm trying to understand the topos-theoretic account of cohomology as > in Johnstone's "Topos Theory". But it looks heavily dependent on having > a classical base topos, since it uses the classical proof of sufficiency > of injectives (together with the existence of Barr covers) to deduce the > same property internally in any Grothendieck topos. For a more fully > constructive theory I wonder if one needs to take better care of the > topologies.] > > Steve Vickers. > [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Sun Jun 21 14:41:15 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 21 Jun 2009 14:41:15 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MIQzs-0006N6-KQ for categories-list@mta.ca; Sun, 21 Jun 2009 14:38:28 -0300 Date: Fri, 19 Jun 2009 22:50:42 +0200 From: Andrew Stacey To: Steve Vickers , Subject: categories: Re: Topology on cohomology groups MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Sender: categories@mta.ca Precedence: bulk Reply-To: Andrew Stacey Message-Id: Status: O X-Status: X-Keywords: X-UID: 84 On Fri, Jun 19, 2009 at 10:26:13AM +0100, Steve Vickers wrote: > A cohomology group can easily be an infinite power of the coefficient > group. But such a group has a natural non-discrete topology, namely the > compact-open (which in this case is also the product topology). > > Are there approaches to cohomology that, as part of the process, also > supply topologies on the cohomology groups? > I'm not sure if this is quite what you are looking for, but the topology on cohomology theories is given as an inverse limit (if I have my limits the correct way round) over the finite skeleta. This has an impact, for example, in the correct statement of the Kunneth theorem on cohomology of products (one has to complete the tensor product with respect to the topology). A fairly comprehensive and detail account is in Boardman and Boardman+Johnson+Wilson in the Handbook of Algebraic Topology: MR1361889 and MR1361900 (though it was known well before that). These papers are available online from Steve Wilson's homepage: http://www.math.jhu.edu/~wsw/ (scan right down to the bottom). Sarah Whitehouse and I also look at this in our paper 'The Hunting of the Hopf Ring' (arxiv:0711.3722, to appear in HHA). Andrew Stacey [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Sun Jun 21 14:41:43 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 21 Jun 2009 14:41:43 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MIR2y-0006WD-5p for categories-list@mta.ca; Sun, 21 Jun 2009 14:41:40 -0300 Date: Sat, 20 Jun 2009 06:32:46 -0400 (EDT) From: Michael Barr To: Steve Vickers , Subject: categories: Re: Topology on cohomology groups MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed Sender: categories@mta.ca Precedence: bulk Reply-To: Michael Barr Message-Id: Status: O X-Status: X-Keywords: X-UID: 85 Very tentatively, I have a memory that Lefschetz in the 30s invented linearly compact vector spaces (and proved that the "category" of them was dual to the "category" of discrete vector space (this was before categories) for the purpose of making cohomology more closely dual to homology. Michael On Fri, 19 Jun 2009, Steve Vickers wrote: > A cohomology group can easily be an infinite power of the coefficient > group. But such a group has a natural non-discrete topology, namely the > compact-open (which in this case is also the product topology). > > Are there approaches to cohomology that, as part of the process, also > supply topologies on the cohomology groups? > > [I'm trying to understand the topos-theoretic account of cohomology as > in Johnstone's "Topos Theory". But it looks heavily dependent on having > a classical base topos, since it uses the classical proof of sufficiency > of injectives (together with the existence of Barr covers) to deduce the > same property internally in any Grothendieck topos. For a more fully > constructive theory I wonder if one needs to take better care of the > topologies.] > > Steve Vickers. > [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Sun Jun 21 14:46:54 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 21 Jun 2009 14:46:54 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MIR7p-0006lo-Bo for categories-list@mta.ca; Sun, 21 Jun 2009 14:46:41 -0300 Content-Type: text/plain; charset=US-ASCII; format=flowed Content-Transfer-Encoding: 7bit From: Paul Taylor Subject: categories: applications of the Yoneda embedding Date: Sat, 20 Jun 2009 16:45:01 +0100 To: Categories list Sender: categories@mta.ca Precedence: bulk Reply-To: Paul Taylor Message-Id: Status: O X-Status: X-Keywords: X-UID: 86 Having been cast in the role of Brutus -- saving the Republic of Category Theory from the crowning of a Fundamental Theorem -- I would like to say that it's "Not that I lov'd Caesar less, but that I lov'd Rome more". Takuo Matsuoka, whom I thank for the undeserved compliment, gave an excellent list of some of the applications of the Yoneda embedding as a way of enriching categories in various mathematical disciplines. The first of these was about schemes in Algebraic Geometry, which he has been explaining to me privately, despite my long-term mental block on this subject. Some of the following was part of my response to him, but I don't want to put him under pressure to be the spokesman for a subject that, as I discovered later, is not actually his own. So, this posting is addressed to algebraic geometers, synthetic differential geometers, and others, to give a sketch of some of the categorical techniques that have been developed for general topology by domain theorists over the past two decades. Whilst their subjects manifestly have a richer history than domain theory did, we now have a few new tricks that they seem to have missed. However, I shall start with some textbook material. The Yoneda Lemma is to category theory what Cayley's Theorem is to groups. An object of a category can be REPRESENTED by the collection of all INCOMING morphisms (from all of the other objects), just as a group can be represented by its permutation action on itself. This representation is faithful for the tremendous but trite reason that an object is represented by its own identity map. Here is a syntactic example: a type X in a lambda calculus is represented by all of its terms, possibly involving free variables. One such term is the single variable x:X, which is the identity in the category. The other objects of the category are the other types, or, given that there may be many free variables, the CONTEXTS, which are lists of typed variables. In proof theory the letter Gamma is used for a typical context. This yields a presheaf whose value at Gamma is the set of terms Gamma |- a:X of type X, using only the variables from Gamma, subject to the equivalence defined by the theory. It defines a contravariant functor in which the morphisms act by substitution. This example is spelt out in detail in my book, "Practical Foundations of Mathematics", in particular in Section 7.7, which describes categorical methods for proving normalisation, conservativity, consistency, etc. I use the letter Gamma for a typical object of ANY base category (not just for a syntactic context but also for a topological space or affine variety) over whose categories we may want to consider presheaves. In so far as there was a previous convention, it was to use "U" (Juergen Koslowski suggested to me that this stood for "Umgebung" = neighbourhood), "I" (for "index") or "-". Since a presheaf is a family of SETS subject to some bookkeeping, the huge advantage of the Yoneda embedding is that we can bring the power of SET THEORY to bear on categorical problems. (Rest assured, you will see that I have not gone over to the Dark Side.) For example, let f,g:X==>Y be parallel maps in a category C. The object X is represented by the SETS C(Gamma,X) of incoming maps, so we can consider the SUBSET ---- f ----> E(Gamma)={x|f.x=g.x} >---> C(Gamma, X) C(Gamma,Y) ---- g ----> of maps x:Gamma-->X that have equal composites with f and g. Notice that these are the data for the universal propery of an equaliser. Indeed, the equaliser E>-->X==>Y exists in C iff the presheaf E(-) is REPRESENTABLE, ie it is of the form C(-,E) for some object E of C, which is unique up to unique isomorphism. For this reason I also use the letter Gamma as the test object FROM which maps come in any universal property. I would urge students to work through this method for exponentials too, first writing down either their universal property or their introduction and elimination rules. In topos theory, another interesting presheaf is given by the set Sub(Gamma) of "sieves" on an object Gamma. This presheaf is representable iff the category C is a topos, and the representing object is the subobject classifier Omega. I this case, I invite you to work backwards from the definition of the subobject classifier to find out what a "sieve" is. In general, the Yoneda embedding preserves universal properties such as limits that are given by maps FROM a generic object Gamma. However, it completely DESTROYS the colimits in C, giving it new ones instead. Indeed, we can think of a presheaf as a "formal" colimit diagram. Now sheaf theory was invented to "PATCH" things together, that is, to add COLIMITS such as pushouts. But usually we don't want to scrap the old colimits altogether, because some of them were "already correct". So, we specify which ones we want to keep, and such a specification is called a GROTHENDIECK TOPOLOGY. Then, instead of using ALL presheaves, we just keep the ones that respect our chosen "correct" colimits, and call them SHEAVES. In particular, we are quite often happy with the existing COPRODUCTS in the base category. In particular, these will be stable and disjoint in any topos, but not the same under one Grothendieck topology as under another, so if the ones that we have in the original category already have this property then they are probably correct. Nowadays, a category with nice finite coproducts is called EXTENSIVE; topological spaces, locales and affine varieties all enjoy this property. Therefore, the colimits that we want to change are usually the epis, coequalisers pushouts and filtered (=purely infinite) ones. Presheaves may be adapted directly to the task of adding colimits of a particular kind. For example, Peter Johnstone describes the "IND" construction that adds filtered colimits in Section VI.1 of "Stone Spaces". In the dual category, this is how we obtain profinite objects, which often come with a compact Hausdorff but totally disconnected topology. A Grothendieck topos is therefore a truly magnificent beast, but it is a SET THEORY, whereas sheaves were originally introduced to study algebraic topology and algebraic geometry. I want to consider some ways in which it might be adapted to the construction of a category that is actually like whichever subject we wanted to study. For various reasons we consider that the category of affine varieties (the formal opposite of the category of commutative rings) and the traditional category of topological spaces are not rich enough for the requirements of their subjects. For example, they are not cartesian closed. So we introduce SCHEMES and (for example) EQUILOGICAL SPACES to do a better job. (Recall that I don't actually know what a scheme is, though I have my guesses, and the reason for spelling out all of this general category theory is to elicit a definition that I can understand, in return for some new techniques that algebraic geometers might find useful.) It is not altogether surprising that the new categories are represented as subcategories of the category of presheaves on the old categories. Since the NEW objects are conceived as "patched together" from old ones, they are, by design, faithfully represented by the incoming maps from (all of) the OLD objects. Steve Vickers' posting of 9 June concerned presheaves on the category of locales. (Locales have very strong formal analogies with affine varieties, being the formal opposite of a category of algebras.) My posting on the same day about "Aspects of locale theory" is also relevant to this Rather more people have studied subcategories of presheaves on the category of topological spaces. Pino Rosolini gave an excellent survey of these categories in his 2000 paper on "Equilogical spaces and filter spaces". You can obtain this and several other papers that provide many of the details of what I am about to say from his webpage www.disi.unige.it/person/RosoliniG/biblio.html Analogously to the "ind" construction above, Dana Scott's equilogical spaces formally adjoin quotients of equivalence relations to topological spaces, whilst Reinhold Heckmann's construction of "equilocales" does the same for locales. A Grothendieck topos is a set theory, but what in the construction makes it so? It is the requirement on the "correct colimits" (Grothendieck topology) that they be stable under all PULLBACKS. The SHEAFIFICATION functor that reflects presheaves to sheaves also preserves all finite limits. If we just want a CARTESIAN CLOSED category, rather than a topos, it is enough that the data and reflection functor be preserved by PRODUCTS, rather than general pullbacks. The categories that I shall describe all contain the base category but are contained in the smallest category of sheaves, so it becomes irrelevant whether we consider sheaves as intermediaries or go straight from presheaves to the smaller category. Along with several other people in the 1990s, Rosolini and I studied ways of defining and constructing categories like these, under the heading of SYNTHETIC DOMAIN THEORY (SDT). This was inspired by synthetic differential geometry, and I think Dana Scott is responsible for the name. However, most of the other people who worked under this banner were interested in realisability toposes rather than sheaf toposes, which was part of the reason why I changed to a different name. Key to this is the object SIGMA. Like Omega, this classifies subobjects, but now just OPEN ones in topology, or RECURSIVELY ENUMERABLE ones in computation. Rosolini identified the abstract properties of a class of monos (or "dominion") and its classifier ("dominance") in his PhD thesis. My "Euclidean principle", Fx & x = FT & x, puts it in an algebraic form -- see "Geometric and Higher Order Logic" on my webpage at www.PaulTaylor.EU/ASD/. However, if algebraic or differential geometers want to pick this idea up, they should not be misled by the idea of classifying subobjects of any kind. It is the algebraic property that matters. As a ring, Sigma should be the ring of polynomials in one variable. As an affine variety, it is the geometric incarnation of the ground field. This means that, for an affine variety X, the set of maps X->Sigma is (the underlying set of) the corresponding ring. Similarly, in topology it is the set of open subsets, ie the corresponding frame. The idea of ASD is that this "set" of maps should itself be a space, but I don't know what this is for algebraic varieties. Sigma is the spider at the centre of the web. Considered as a space, it carries the relevant algebraic structure (a lattice or a ring), and maps X-->Sigma determine the structure of other spaces X. (Notice that this is the opposite way from the maps Gamma-->X that motivated the category of presheaves.) In synthetic domain theory we devised various properties, involving maps X-->Sigma, that would say whether the presheaf X was to be regarded as a "domain". I am going to stick to those that can be expressed in pure category theory and generalised to other subjects. The weakest one, a kind of T0 property, was that X >---> Sigma^Y, ie that the presheaf X be a subobject (family of subsets) of some exponential. (Recall that you constructed exponential presheaves as an exercise earlier!) A stronger one is that X >---> Sigma^Y ====> Sigma^Z as an equaliser of such exponentials. Usually there is a reflection functor from all presheaves to the "domains", and this preserves products. I forget exactly what was in each of Rosolini's papers, but he studied the analogy between this reflection functor and sheafification, and also what happens in presheaf categories over various interesting concrete categories. Even with this modification of the notion of sheaf topos, the Yoneda embedding and Grothendieck toposes have at best been given the status of a "constitutional monarchy", so it is time to introduce some genuinely republican ideas. My programme "Abstract Stone Duality" moves away from the models based on toposes to a direct axiomatisation of the subject that we actually want to study. This axiomatisation consists of two parts -- some pure category theory and some specifically topological axioms on top of it. The reason why I believe ASD could be adapted to other subjects is that the topological axioms say little more than that Sigma is a lattice, so this could be replaced by a ring. MOST of the work is done by the underlying category theory, and this will be even more strongly so in the developments of the theory that I am currenly studying. In ASD, I concentrate on powers of Sigma, rather than of general objects, and other structure that can be defined in these terms. The version of my theory that is reasonably well established starts from the hypothesis that the adjunction Sigma^(-) -| Sigma^(-) be MONADIC. The result of this is an account of computably based locally compact spaces and computable continuous functions. I applied this to elementary real analysis, and obtained a computable construction of the Dedekind reals in which [0,1] is compact --- contrary to the received wisdom of Russian Recursive Analysis that this is impossible, and to Bishop's constructive analysis, which develops a lot of the subject in a "can do" fashion but without using compactness of [0,1]. The problem with this theory is that, rather than enlarging the traditional category to a cartesian closed one that is embedded in a category of presheaves, it cuts down to locally compact spaces. However, I am currently writing up a new technique that replaces the monadic assumption. In one manifestation, it gives an account of all sober topological spaces and continuous functions. However, since it says that products preserve epis, it doesn't work for locales, because of the counterexample that I gave in my "aspects of locale theory" posting. On the other hand, this DOES work for affine varieties -- over a field, because the same problem with locales arises if you try to work over a general commutative ring. (It comes down to whether modules are FLAT, ie tensor product with them preserves monos.) I talked about "illegitimate" presheaves in my "categories" posting on "aspects of locale theory", and Steve Vickers said something on the same topic. Set-theoretic issues aside, presheaves are "heavyweight" gadgets in that you have to give data pertaining to every object of the base category, so a scheme is defined by its relationship to ALL rings. I am offering a much more "lightweight" construction. In this, to give an object of the new category (a "scheme", maybe) would involve only a handful of objects and morphisms of the original one (rings). This "lightweight" construction will give an account of equilogical spaces (with some of their more set-theoretic features removed). I would like to know what the relationship is between the analogous result that I have for algebraic varieties, and whatever the official definition of SCHEME is in algebraic geometry. My category of "schemes" (if that is what it is) would be embedded in the presheaf category and closed therein under finite limits and exponentials. It would contain all affine varieties, along with their products, equalisers, pullbacks, coproducts and epis but not coequalisers (coproducts, coequalisers, pushouts, products and monos but not equalisers of rings). The (possible) difference from the existing notion of scheme is that I would give you the SMALLEST category of presheaves that has these properties. Along with this would come a "synthetic" and computable axiomatisation similar to the one that I give for elementary real analysis in www.paultaylor.eu/ASD/lamcra/elemcalc Finally, why is the Yoneda Lemma not a Theorem? Because Lemmas do the work in mathematics, whilst Theorems, like royalty, just take the credit. Thank you for listening. Paul Taylor www.PaulTaylor.EU [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Mon Jun 22 10:14:10 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 22 Jun 2009 10:14:10 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MIjL0-0000VP-L2 for categories-list@mta.ca; Mon, 22 Jun 2009 10:13:30 -0300 Date: Sun, 21 Jun 2009 22:38:30 +0100 (BST) From: "Prof. Peter Johnstone" To: David Spivak , categories@mta.ca Subject: categories: Re: monad: (k-Set \downarrow -): Set -->Set MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed Sender: categories@mta.ca Precedence: bulk Reply-To: "Prof. Peter Johnstone" Message-Id: Status: O X-Status: X-Keywords: X-UID: 87 On Fri, 19 Jun 2009, David Spivak wrote: > Dear Categorists, > > Does anyone know a name for the monad described below and/or whether > it has been studied? > > Let k-Set denote the category of k-small sets (for some small regular > cardinal k). For a set S, we denote by > > T(S)=(k-Set \downarrow {S}) > > the set whose elements are pairs (K,f), where K is a k-small set and > f:K-->S is a function. This construction is functorial in S. I > claim that the endo-functor T: Set -->Set is a monad. The identity > transformation S-->T(S) is given by "singleton set" and the > multiplication transformation TT(S)-->T(S) is given by Grothendieck > construction. > I don't think this construction works at the level of sets rather than categories. The problem is that k-Set is a category, not a set, so T(S) also has a category structure, and you can't simply "forget" this. If you do, then you have the problem "*which* singleton set?" for the unit (i.e., which singleton set do you choose as the domain of the functions 1 --> S which you identify with elements of S?), and whichever choice you make you are going to run into problems verifying the monad identities. > (There is a similar monad on Cat, where we replace k-Set with k-Cat.) > This is correct, and it's well-known: it is the monad which freely adjoins k-small coproducts to a category. Peter Johnstone [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Mon Jun 22 10:14:11 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 22 Jun 2009 10:14:11 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MIjKH-0000R2-78 for categories-list@mta.ca; Mon, 22 Jun 2009 10:12:45 -0300 Date: Sun, 21 Jun 2009 22:20:03 +0100 (BST) From: "Prof. Peter Johnstone" To: Andrew Stacey , categories@mta.ca Subject: categories: Re: Topology on cohomology groups MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed Sender: categories@mta.ca Precedence: bulk Reply-To: "Prof. Peter Johnstone" Message-Id: Status: O X-Status: X-Keywords: X-UID: 88 On Fri, 19 Jun 2009, Andrew Stacey wrote: > I'm not sure if this is quite what you are looking for, but the topology on > cohomology theories is given as an inverse limit (if I have my limits the > correct way round) over the finite skeleta. Not really a contribution to the mathematical question, but I'm struck by the fact that both Andrew Salch and Andrew Stacey, in their replies to Steve Vickers, use the plural "skeleta". I used to do that when I was a student, as a way of winding-up my teachers, but it isn't justifiable. The English word "skeleton" is indeed derived from a Greek root (the past participle of the verb "skellein", to wither or dry up), but it doesn't exist as a noun in Greek. There is therefore no justification for giving it an imagined Greek plural. Having in my time devoted some effort to fighting the bogus (but in fact more justifiable) Greek plural "topoi", I feel bound to protest against this one too. Peter Johnstone [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Mon Jun 22 10:15:09 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 22 Jun 2009 10:15:09 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MIjMW-0000f2-U4 for categories-list@mta.ca; Mon, 22 Jun 2009 10:15:05 -0300 Date: Mon, 22 Jun 2009 13:56:11 +0200 (CEST) Subject: categories: Re: monad: (k-Set \downarrow -): Set -->Set From: Mark.Weber@pps.jussieu.fr To: "David Spivak" , categories@mta.ca MIME-Version: 1.0 Content-Type: text/plain;charset=iso-8859-1 Content-Transfer-Encoding: quoted-printable Sender: categories@mta.ca Precedence: bulk Reply-To: Mark.Weber@pps.jussieu.fr Message-Id: Status: O X-Status: X-Keywords: X-UID: 89 Dear David I'm not sure whether your specific construction has been looked at or named, but it is a "submonad" of something very well known. Let's work with 2 universes of sets, your "Set" being the topos of small sets, and SET being a topos of sets large enough to include {arrows of Set} as an object. For those not so comfortable doing this, fix two regular cardinals far enough part, read "Set" as "the category of sets of cardinality less than the smaller cardinal", and "SET" as "the category o= f sets of cardinality less than the bigger one", and far enough apart means Set is a category internal to SET. Now the 2-category CAT (of category objects in SET) contains Set as an object so one may form the slice 2-category CAT/Set in the strictest sense (1-cells being triangles commuting on the nose). The big brother of your monad is a 2-monad on this 2-category. The endofunctor part does the following: S:A-->Set |--> Set \downarrow S --> Set This is the underlying monad of what could be called the "fibration" 2-monad. That is applying to a functor produces the free split fibration on what you started with. This construction works at the following generality: replace CAT by any 2-category with comma objects and Set by any object therein, and the first paper to see fibrations as algebras of = a monad in this way was R. Street "Fibrations and yoneda's lemma in a 2-category" SLNM 420 1974 The relation between your monad and this one is that there's a canonical inclusion Set --> CAT/Set which regards any Set S as a functor S:1-->Set, and this functor is the 1-cell data for a monad morphism (in the sense of Street: "Formal theory of monads") from your monad to the monad I described. With best regards Mark Weber > Dear Categorists, > > Does anyone know a name for the monad described below and/or whether > it has been studied? > > Let k-Set denote the category of k-small sets (for some small regular > cardinal k). For a set S, we denote by > > T(S)=3D(k-Set \downarrow {S}) > > the set whose elements are pairs (K,f), where K is a k-small set and > f:K-->S is a function. This construction is functorial in S. I > claim that the endo-functor T: Set -->Set is a monad. The identity > transformation S-->T(S) is given by "singleton set" and the > multiplication transformation TT(S)-->T(S) is given by Grothendieck > construction. > > (There is a similar monad on Cat, where we replace k-Set with k-Cat.) > > Does this monad T have a name? Has it been studied? > > Thank you, > David [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Mon Jun 22 10:15:47 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 22 Jun 2009 10:15:47 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MIjN9-0000jk-TE for categories-list@mta.ca; Mon, 22 Jun 2009 10:15:44 -0300 Date: Mon, 22 Jun 2009 12:31:48 +0000 (GMT) From: claudio pisani Subject: categories: Re: Fundamental Theorem of Category Theory? To: categories MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Sender: categories@mta.ca Precedence: bulk Reply-To: claudio pisani Message-Id: Status: O X-Status: X-Keywords: X-UID: 90 The Yoneda Lemma is in fact a particular case of the reflections of Cat/X i= n discrete (op)fibrations over X (the reflection of an object x:1->X gives = the slice X/x -> X, which corresponds to the representable X(-,x)); another particular case (X=3D1), gives the components of a category. The above reflections are a consequence of the "comprehensive" factorizatio= n systems (final functors, discrete fibrations) and (initial functors, disc= rete opfibrations) on Cat. It turns out that several aspects of category theory can be developed in an= y finitely complete category C with two factorization systems properly rela= ted (the main axiom is "reciprocal stability"). Thus category theory can be indeed founded on (a generalization of) the Yon= eda Lemma; in particular, in this perspective, universal properties inside = C depend on the universal properties which follow from the factorization sy= stems. Best regards Claudio Pisani =0A=0A=0A [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Mon Jun 22 10:16:45 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 22 Jun 2009 10:16:45 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MIjO5-0000qN-OU for categories-list@mta.ca; Mon, 22 Jun 2009 10:16:41 -0300 Date: Mon, 22 Jun 2009 13:17:58 +0200 From: Jiri Rosicky To: categories@mta.ca Subject: categories: research positions MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-2 Content-Disposition: inline Sender: categories@mta.ca Precedence: bulk Reply-To: Jiri Rosicky Message-Id: Status: O X-Status: X-Keywords: X-UID: 91 Eduard Cech center had been established in 2005 as the national research center focusing its attention to interactions between algebra, geometry, and logic (and their applications in cryptology, computer science, etc.). It is jointly operated by mathematicians from Masaryk University in Brno, Charles University in Prague and Academy of Sciences of the Czech Republic, with offices both in Brno and Prague. The Center invites applications for several research positions for the year 2010 commencing at the date depending on mutual agreement. The candidates must be recent PhD's that obtained their degree not earlier than 2 years before submitting this application. Candidates should submit a letter of application accompanied by a CV, list of publications and an outline of their research project to Professor Jan Slovak (slovak@muni.cz) not later than August 10, 2009. They should also arrange for at least 2 letters of recommendation (one can be from a Czech mathematician) to be mailed directly to slovak@muni.cz before August 20, 2009. The successful applicants will be notified as soon as possible, we hope the decision will be taken by September 20, 2009. Further information about the Eduard Cech Center can be found at http://ecc.sci.muni.cz [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Mon Jun 22 21:14:26 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 22 Jun 2009 21:14:26 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MItdF-0001bp-AL for categories-list@mta.ca; Mon, 22 Jun 2009 21:13:01 -0300 From: Barney Hilken To: categories Content-Type: text/plain; charset=US-ASCII; format=flowed; delsp=yes Content-Transfer-Encoding: 7bit Mime-Version: 1.0 (Apple Message framework v935.3) Subject: categories: Triquotient assignments for geometric morphisms Date: Mon, 22 Jun 2009 16:48:54 +0100 Sender: categories@mta.ca Precedence: bulk Reply-To: Barney Hilken Message-Id: Status: O X-Status: X-Keywords: X-UID: 92 Has anyone generalised the theory of (weak) triquotient assignments from locale maps to geometric morphisms? In particular, does the pullback (assuming boundedness) of a geometric morphism with a triquotient assignment have a unique triquotient assignment satisfying the Beck-Chevalley condition? Also, if f:X->Y is a continuous function between topological spaces, are there any reasonable conditions (other than openness) under which the interior of the direct image along f is a weak triquotient assignment for the inverse image map? Thanks, Barney. [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Mon Jun 22 21:14:26 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 22 Jun 2009 21:14:26 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MIteA-0001eU-HE for categories-list@mta.ca; Mon, 22 Jun 2009 21:13:58 -0300 Date: Mon, 22 Jun 2009 18:54:27 +0200 From: Anders Kock MIME-Version: 1.0 To: categories@mta.ca Subject: categories: Re: monad: (k-Set \downarrow -): Set -->Set Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: quoted-printable Sender: categories@mta.ca Precedence: bulk Reply-To: Anders Kock Message-Id: Status: O X-Status: X-Keywords: X-UID: 93 As Peter Johnstone also emphasized in his reply, the construction which =20 David Spivak describes, namely "T(S)=3D(k-Set \downarrow {S})", is really a part of a well known= =20 "monad" on the category of categories: if S is any category, T(S) is the=20 free cocompletion of S under k-small coproducts. It is only a monad up=20 to canonical isomorphisms, because coproducts are not in general=20 strictly associative. This cocompletion "monad" under coproducts has=20 been widely studied under the name "Fam" (because T(S) is the category=20 of k-small Families of objects in S). It is an example of a KZ monad. However, replacing k-Set by k-Cat provides a monad on Cat which is not=20 KZ; David observes: "(There is a similar monad on Cat, where we replace k-Set with k-Cat.)" and Peter's reply to this: "This is correct, and it's well-known: it is the monad which freely adjoi= ns k-small coproducts to a category. " does not apply here (it slipped into the wrong place of his reply):=20 rather, David's "similar monad" is trying to provide free cocompletion=20 under colimits indexed by k-small categories, but does not, until you=20 make a category-of-fractions construction on its values. My University=20 of Chicago thesis (1967) described this way of making free cocompletions. This "similar monad" (before doing the fractions-part) has been studied=20 by Guitart, he calls it this monad DIAG. Reference: Guitart, Ren=E9,=20 Remarques sur les machines et les structures. Cahiers de Topologie et=20 G=E9om=E9trie Diff=E9rentielle Cat=E9goriques, 15 no. 2 (1974), p. 113-14= 4=20 (available electronically in NUMDAM). Anders Kock [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Mon Jun 22 21:14:26 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 22 Jun 2009 21:14:26 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MItcS-0001aI-HM for categories-list@mta.ca; Mon, 22 Jun 2009 21:12:12 -0300 Subject: categories: Re: monad: (k-Set \downarrow -): Set -->Set To: dspivak@uoregon.edu, categories@mta.ca Date: Mon, 22 Jun 2009 11:37:01 -0300 (ADT) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit From: selinger@mathstat.dal.ca (Peter Selinger) Sender: categories@mta.ca Precedence: bulk Reply-To: selinger@mathstat.dal.ca (Peter Selinger) Message-Id: Status: O X-Status: X-Keywords: X-UID: 94 David Spivak wrote: > > Dear Categorists, > > Does anyone know a name for the monad described below and/or whether > it has been studied? > > Let k-Set denote the category of k-small sets (for some small regular > cardinal k). For a set S, we denote by > > T(S)=(k-Set \downarrow {S}) > > the set whose elements are pairs (K,f), where K is a k-small set and > f:K-->S is a function. This construction is functorial in S. I > claim that the endo-functor T: Set -->Set is a monad. The identity > transformation S-->T(S) is given by "singleton set" and the > multiplication transformation TT(S)-->T(S) is given by Grothendieck > construction. > > (There is a similar monad on Cat, where we replace k-Set with k-Cat.) > > Does this monad T have a name? Has it been studied? I assume you mean to take such pairs (K,f) up to isomorphism, or else, as Peter Johnstone has already pointed out, your construction will not be well-defined. For instance, even the finite sets may form a proper class, depending on your underlying set theory. In the case where k=omega, T is the well-known finite multiset monad, which associates to each S the free commutative monoid generated by S (whose elements are also known as finite multisets in S). For other k, I would call this the "monad of multisets of size less than k". I think this works for any infinite small cardinal, not just regular ones. -- Peter [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Mon Jun 22 21:14:53 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 22 Jun 2009 21:14:53 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MItf0-0001hl-57 for categories-list@mta.ca; Mon, 22 Jun 2009 21:14:50 -0300 Mime-Version: 1.0 (Apple Message framework v624) Content-Type: text/plain; charset=US-ASCII; format=flowed Content-Transfer-Encoding: 7bit From: Paul Taylor Subject: categories: no fundamental theorems please Date: Mon, 22 Jun 2009 22:07:47 +0100 To: categories , claudio pisani Sender: categories@mta.ca Precedence: bulk Reply-To: Paul Taylor Message-Id: Status: O X-Status: X-Keywords: X-UID: 95 I see that Takuo and I have still not overcome the "royalist" forces. Claudio, Vaughan, Ross and others have mentioned various more "sophisticated" versions of the Yoneda Lemma. However, I contend that the more sophisticated the result is, the LESS it deserves to be called "the fundamental theorem of category theory". I particularly like Euclid's algorithm for the highest common factor as a historical and methodological example, Without meaning to dictate to number theorists how their subject should be organised, let me suggest for the sake of argument that it is a pretty good candidate for being called the "fundamental theorem of number theory". Gauss used the same idea to factorise polynomials, and no doubt number theorists have many more "sophisticated" developments of it. But the principal idea was Euclid's (or one of his colleagues), not Gauss's, and definitely not that of any subsequent number theorist! Saunders Mac Lane said something about "the right" generality, as opposed to the greatest generality. As I say, I like Euclid's algorithm because the idea has survived many many revolutions in the "official" foundations of mathematics. Theorems, like royalty, are rightly the victims of revolutions, because the way in which we encapsulate a piece of theory as a "theorem" depends as much on our current cultural prejudices as it does on the real underlying mathematics. For example, there is Cantor's "theorem" about a powerset being strictly bigger than a set. This belongs entirely to the dogma of set theory. When set theory is overturned, this miserable and wholely misguided "theorem" will go in the dustbin of mathematical history with it. But Euclid's algorithm will live forever. And the Yoneda Lemma will survive as long as Category Theory does in a recognisable form. But it still shouldn't be called the "fundamental theorem"! Paul [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Tue Jun 23 09:47:23 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 23 Jun 2009 09:47:23 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MJ5No-0005Yp-KJ for categories-list@mta.ca; Tue, 23 Jun 2009 09:45:52 -0300 Date: Tue, 23 Jun 2009 06:43:55 +0200 (CEST) Subject: categories: Re: monad: (k-Set \downarrow -): Set -->Set From: Mark.Weber@pps.jussieu.fr To: categories@mta.ca MIME-Version: 1.0 Content-Type: text/plain;charset=iso-8859-1 Content-Transfer-Encoding: quoted-printable Sender: categories@mta.ca Precedence: bulk Reply-To: Mark.Weber@pps.jussieu.fr Message-Id: Status: O X-Status: X-Keywords: X-UID: 96 Peter Johnstone is right -- the monad David described doesn't exist, thus neither does the monad morphism I described in my other post (... sorry!)= . Perhaps the fibrations monad is still of interest. One could fix a skeleton of Set_k, and for k =3D cardinality of natural numbers this works fine, and the monad on Set you get is the monoid monad= . However for bigger k you're likely to run into problems when trying to do this sort of thing. However it isn't true that the monad >> (... on Cat, where we replace k-Set with k-Cat.) is the k-coproduct completion monad -- you need to keep k-Set but work in Cat and take lax slices, ie take the monad on Cat which has underlying endofunctor X |-> k-Set // X (where // means "lax slice") to get the k-coproduct completion monad. Mark Weber [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Tue Jun 23 09:47:23 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 23 Jun 2009 09:47:23 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MJ5OY-0005c3-57 for categories-list@mta.ca; Tue, 23 Jun 2009 09:46:38 -0300 Date: Tue, 23 Jun 2009 02:00:49 -0400 From: "Fred E.J. Linton" To: Subject: categories: Re: Topology on cohomology groups Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Sender: categories@mta.ca Precedence: bulk Reply-To: "Fred E.J. Linton" Message-Id: Status: O X-Status: X-Keywords: X-UID: 97 On Mon, 22 Jun 2009 09:17:05 AM EDT, "Prof. Peter Johnstone" = in response to: Andrew Stacey wrote, in part= : > On Fri, 19 Jun 2009, Andrew Stacey wrote: > = > > ... over the finite skeleta. > = > Not really a contribution to the mathematical question, but I'm struck = by > the fact that both Andrew Salch and Andrew Stacey, in their replies to > Steve Vickers, use the plural "skeleta". I used to do that when I was a= > student, as a way of winding-up my teachers, but it isn't justifiable. > = > The English word "skeleton" is indeed derived from a Greek root (the > past participle of the verb "skellein", to wither or dry up), but it > doesn't exist as a noun in Greek. There is therefore no justification > for giving it an imagined Greek plural. Having in my time devoted some > effort to fighting the bogus (but in fact more justifiable) Greek > plural "topoi", I feel bound to protest against this one too. ... The generic-seeming example "phenomenon/phenomena" certainly *suggests* a parallel "skeleton/skeleta" -- but it would also suggest "polygon/polyg= a", which I think we all would agree is nonsense. Peter is merely (justifiabl= y) pointing out that "skeleton/skeleta" is as much nonsense as "polygon/poly= ga", and I'm with him 100% on that score. [As for the plural of "topos", I guess I'm in the mugwump camp that would= *write* it as "topoi" (pace Peter), but *pronounce* it as "toposes" :-) .= English was never very strong at phonetic consistency of pronunciation; witness GBShaw's "phonetic" spelling of FISH: "ghotip".] Cheers, -- Fred PS: "ghotip"? "gh" as in COUGH, "o" as in WOMEN, = "ti" as in NATION, and "p" (silent) as in PNEUMONIA. [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Tue Jun 23 09:47:33 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 23 Jun 2009 09:47:33 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MJ5PO-0005gL-7n for categories-list@mta.ca; Tue, 23 Jun 2009 09:47:30 -0300 Content-class: urn:content-classes:message MIME-Version: 1.0 Subject: categories: RE: Triquotient assignments for geometric morphisms Date: Tue, 23 Jun 2009 08:27:41 +0100 From: "Townsend, Christopher" To: "Barney Hilken" , Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Sender: categories@mta.ca Precedence: bulk Reply-To: "Townsend, Christopher" Message-Id: Status: O X-Status: X-Keywords: X-UID: 98 Barney As far as I am aware, no generalisation of localic triquotient assignments = to geometric morphisms has been developed. That's not for want of trying on= my part! A na=EFve approach would be to define a weak triquotient assignment on a ge= ometric morphism f:F->E to be a filtered colimit preserving functor that is= required to interact with the inverse image of f in a manner that mimics t= he localic case. For this approach to work in a way that is similar to what= happens for locales we would need to have a similar way of characterising = such filtered colimit preserving functors which, as far as I am aware, is n= ot available (essentially due to the technical difficulty that sheafificati= on is 'two step' for toposes, but only 'one step' for locales). The technic= al problems here are, in my mind, the same as the more well known problems = associated with constructing an upper power topos.=20 My current view on how to solve this problem is to use localic representati= ons of geometric morphisms. This requires us to re-state the theory of geom= etric morphisms as adjunctions between categories of locales and to develop= 'topos theory' relative to these adjunctions. For example 'Grothendick top= os' becomes 'category of localic diagrams of a localic groupoid' in this pa= radigm. The lower power topos construction should guide us to see how its a= ction effects (the category of actions of) localic groupoids; then by upper= /lower symmetry we know what the 'upper' case should be (and hence to weak = triquotient assignments on geometric morphisms). Unfortunately getting the = symmetry to work even at the much simpler level of bounded geometric morphi= sms is proving a headache.=20 If you would like any further detail, please feel free to get in touch.=20 Regards, Christopher=20 -----Original Message----- From: categories@mta.ca [mailto:categories@mta.ca] On Behalf Of Barney Hilk= en Sent: 22 June 2009 16:49 To: categories Subject: categories: Triquotient assignments for geometric morphisms Has anyone generalised the theory of (weak) triquotient assignments from locale maps to geometric morphisms? In particular, does the pullback (assuming boundedness) of a geometric morphism with a triquotient assignment have a unique triquotient assignment satisfying the Beck-Chevalley condition? Also, if f:X->Y is a continuous function between topological spaces, are there any reasonable conditions (other than openness) under which the interior of the direct image along f is a weak triquotient assignment for the inverse image map? Thanks, Barney. [For admin and other information see: http://www.mta.ca/~cat-dist/ ] _______________________________________________________________________ This email is intended only for the use of the individual(s) to whom it is addressed and may be privileged and confidential. Unauthorised use or disclosure is prohibited. If you receive this e-mail in error, please advise immediately and delete the original message without copying, using, or telling anyone about its contents. This message may have been altered without your or our knowledge and the sender does not accept any liability for any errors or omissions in the message. This message does not create or change any contract. Royal Bank of Canada and its subsidiaries accept no responsibility for damage caused by any viruses contained in this email or its attachments. Emails may be monitored. RBC Capital Markets is a business name used by branches and subsidiaries of Royal Bank of Canada, including Royal Bank of Canada, London branch and Royal Bank of Canada Europe Limited. In accordance with English law requirements, details regarding Royal Bank of Canada Europe Limited are set out below: ROYAL BANK OF CANADA EUROPE LIMITED Registered in England and Wales 995939 Registered Address: 71 Queen Victoria Street, London, EC4V 4DE. Authorised and regulated by the Financial Service Authority. Member of the London Stock Exchange [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Tue Jun 23 09:48:09 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 23 Jun 2009 09:48:09 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MJ5Px-0005jQ-H3 for categories-list@mta.ca; Tue, 23 Jun 2009 09:48:05 -0300 Date: Tue, 23 Jun 2009 10:27:36 +0100 From: Miles Gould To: categories Subject: categories: Re: no fundamental theorems please Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Sender: categories@mta.ca Precedence: bulk Reply-To: Miles Gould Message-Id: Status: O X-Status: X-Keywords: X-UID: 99 I expected my term to be slightly controversial, but didn't realise what depth of feeling existed on the subject! So, while I thank everyone for the very enlightening discussion of Yoneda's Lemma, and Paul for his thoughts on Fundamental Theorems, I'd like to ask: is there another name I can use for the theorem that right adjoints preserve limits and left adjoints preserve colimits that's (a) a bit less of a mouthful than that and (b) emphasises the result's importance and applicability? Miles [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Tue Jun 23 09:48:56 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 23 Jun 2009 09:48:56 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MJ5Qj-0005nx-FZ for categories-list@mta.ca; Tue, 23 Jun 2009 09:48:53 -0300 Date: Tue, 23 Jun 2009 10:28:04 +0100 From: Martin Escardo MIME-Version: 1.0 To: categories , Paul Taylor Subject: categories: Re: no fundamental theorems please Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Sender: categories@mta.ca Precedence: bulk Reply-To: Martin Escardo Message-Id: Status: O X-Status: X-Keywords: X-UID: 100 I am sure several other readers of this list will have the same reply to this specific point of Paul's message: Paul Taylor wrote: > For example, there is Cantor's "theorem" about a powerset being > strictly bigger than a set. This belongs entirely to the dogma > of set theory. When set theory is overturned, this miserable > and wholely misguided "theorem" will go in the dustbin of > mathematical history with it. There is a very nice paper by Lawvere that shows that the essence of Cantor's theorem is fundamental and beautiful: Originally published in: Diagonal arguments and cartesian closed categories, Lecture Notes in Mathematics, 92 (1969), 134-145. Reprinted in TAC: http://www.tac.mta.ca/tac/reprints/articles/15/tr15abs.html There is also a post by Andrej Bauer in his Mathematics and Computation blog: http://math.andrej.com/2007/04/08/on-a-proof-of-cantors-theorem/ Martin [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Tue Jun 23 09:49:45 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 23 Jun 2009 09:49:45 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MJ5RU-0005t7-Om for categories-list@mta.ca; Tue, 23 Jun 2009 09:49:40 -0300 Date: Tue, 23 Jun 2009 11:27:17 +0100 (BST) From: Richard Garner To: Peter Selinger , dspivak@uoregon.edu, categories@mta.ca Subject: categories: Re: monad: (k-Set \downarrow -): Set -->Set MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed Sender: categories@mta.ca Precedence: bulk Reply-To: Richard Garner Message-Id: Status: O X-Status: X-Keywords: X-UID: 101 > In the case where k=omega, T is the well-known finite multiset monad, > which associates to each S the free commutative monoid generated by S > (whose elements are also known as finite multisets in S). > > For other k, I would call this the "monad of multisets of size less > than k". I think this works for any infinite small cardinal, not just > regular ones. You really do need the regularity. Otherwise removing brackets from a k-small multiset of k-small multisets might yield something bigger than a k-small multiset, and then one cannot define a multiplication for the monad. Richard [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Tue Jun 23 09:50:58 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 23 Jun 2009 09:50:58 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MJ5Sf-00061o-Rp for categories-list@mta.ca; Tue, 23 Jun 2009 09:50:53 -0300 Date: Tue, 23 Jun 2009 11:40:49 +0100 From: Steve Vickers MIME-Version: 1.0 To: Barney Hilken , Subject: categories: Re: Triquotient assignments for geometric morphisms Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Sender: categories@mta.ca Precedence: bulk Reply-To: Steve Vickers Message-Id: Status: O X-Status: X-Keywords: X-UID: 102 Dear Barney, The weak triquotient assignments go along with the double powerlocale monad PP, since a weak triquotient assignment for f: X -> Y is a map g: Y -> PP(X) satisfying certain conditions that relate to the strength of PP. I believe Townsend has published some work on this. This is similar to how open maps go along with the lower powerlocale P_L (see my "Locales are not pointless"), though with P_L it is made tighter using an adjunction that is not available in the PP case, so the open analogue of triquotient assignment, the map from Y to P_L(X), is characterized uniquely. For open maps we know of a trivial generalization to toposes: a geometric morphism is open if its localic part is an open locale map. You could probably play the same trick with triquotient assignments, and then I think your stability property follows from stability of the hyperconnected-localic factorization. However, there is also a more interesting generalization in the case of open maps, got by generalizing P_L to the symmetric topos construction M. (This is described in the Elephant, but also, in much more detail, in the Bunge-Funk book "Singular coverings of toposes". See also my paper "Cosheaves and connectedness in formal topology".) In fact, Bunge and Funk have proved that for a locale X, P_L(X) is the localic reflection of M(X). The relationship between P_L and open maps transfers to one between M and locally connected geometric morphisms. Since PP is the composite of (commuting) monads P_U and P_L, where P_U is the upper powerlocale, one natural approach to a topos generalization would be try also to generalize P_U. This generalization seems to be missing in our current state of knowledge, though I've had some thoughts about it and firmly believe that it exists. Regards, Steve. Barney Hilken wrote: > Has anyone generalised the theory of (weak) triquotient assignments > from locale maps to geometric morphisms? In particular, does the > pullback (assuming boundedness) of a geometric morphism with a > triquotient assignment have a unique triquotient assignment satisfying > the Beck-Chevalley condition? > > Also, if f:X->Y is a continuous function between topological spaces, > are there any reasonable conditions (other than openness) under which > the interior of the direct image along f is a weak triquotient > assignment for the inverse image map? > > Thanks, > > Barney. > [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Tue Jun 23 09:51:52 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 23 Jun 2009 09:51:52 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MJ5TV-00066b-BI for categories-list@mta.ca; Tue, 23 Jun 2009 09:51:45 -0300 Mime-Version: 1.0 (Apple Message framework v624) Content-Type: text/plain; charset=US-ASCII; format=flowed Content-Transfer-Encoding: 7bit From: Paul Taylor Subject: categories: Lemmas and Theorems Date: Tue, 23 Jun 2009 11:48:38 +0100 To: categories list Sender: categories@mta.ca Precedence: bulk Reply-To: Paul Taylor Message-Id: Status: O X-Status: X-Keywords: X-UID: 103 > I am sure several other readers of this list will have the same reply > to this specific point of Paul's message: I'm sorry, Martin, did I post to FOM instead of "categories" by mistake? > There is a very nice paper by Lawvere that shows that the essence > of Cantor's theorem is fundamental and beautiful: Yes, and this illustrates the distinction that I am trying to make between Lemmas that do the work and Theorems that take the credit. Lawvere's argument is a Lemma about fixed points that has many uses elsewhere. I might even stretch to crediting Cantor with a good idea, since it reappeared as Turing's insolubility of the halting problem and Goedel's incompleteness theorem. As a Theorem, on the other hand, Cantor's result was the basis of the theory of cardinality, which was more or less immediately recognised as being completely useless for ordinary mathematical purposes such as distinguishing between R^2 and R^3. It is dogma. As I said, we use "Theorems" to summarise how a piece of work fits into the currently prevailing mathematical dogma. When that dogma changes, the Theorems go out of the window, but the Lemmas survive, being reorganised in a new way according to the new dogma. To give an example in category theory, it is a Theorem that a certain structure is the "classifying category" or "classifying topos" for some theory, because this terminology comes from a particular world view. However, the same underlying calculations have been organised in different ways under different names (such as "clone" and "Lawvere theory") in the past, and will be reorganised in other ways in the future. The thing that makes Mathematics interesting is that there is something there that is essentially independent of the world view according to which it is currently organised. In approaching a particular topic, you can choose the Definitions one way and then have to prove a particular Theorem, or go round the circle the other way, rewriting the Theorem as the Definition and proving a different Theorem. But when you look carefully at the two versions, you realise that the same Lemma is there either way. I used to illustrate this with Galois Theory, but I regret that I can no longer remember that beautiful subject sufficiently clearly to do so now. Instead, I gave a more prosaic example in Section 1,2 of my book, called the Lineland Army. (As a Theorem, it is the free monad on a monoid.) You can approach it as a pure mathematician would, using equivalence classes, in which case the Theorem says that its binary operation is associative. Or you can approach it as a theoretical computer scientist would, and prove a normalisation Theorem. But either way there is the same Lemma. In a particular topic, therefore, rather than in a whole discipline such as category theory, there may well be a Fundamental Lemma -- the one thing that you have to prove, whichever way you go round the circle. But I think we should wrap up this thread now. > There is also a post by Andrej Bauer in his Mathematics and > Computation blog: > http://math.andrej.com/2007/04/08/on-a-proof-of-cantors-theorem/ Funny you should mention this, because I was going to cite it for a completely different reason. Andrej originally posted this to FOM, but it was censored, and he received a "referee's report" from the "editorial board". Those who have been anywhere near FOM will know of its notoriety. For example, two categorical logicians who attempted to engage with set theorists there c1998 were on the receiving end of a lot of personal abuse from one specific person. I have heard similar stories from about four other sources in completely unrelated disciplines. In particular, some of us recently attempted to discuss some points of constructive real analysis there. I have to be careful in posing my question, otherwise I will get a mailbox full of examples of dogma, abuse and censorship. On "categories" we ask questions, advertise our work and discuss issues of research and professional matters. Set theorists appear to do the same on FOM, but the list is called "Foundations of Mathematics" and not "Set Theory". In both cases I expect that there are isolated graduate students for whom these lists are their one contact with the outside world and source of information about mathematical research. FOM ought to provide them with a diversity of points of view, as "categories" does. Has anyone EVER managed to discuss constructive mathematics, type theory, categorical logic, or any other "heretical" topic, on FOM, in a professional way, without being shouted down or censored? Please reply privately, and don't copy long postings or "referee's reports" to me. Just tell me briefly the month in which the exchange took place and who participated in it, then I can look it up myself in the FOM archive. Paul Taylor [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Tue Jun 23 09:53:18 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 23 Jun 2009 09:53:18 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MJ5Ut-0006Dr-St for categories-list@mta.ca; Tue, 23 Jun 2009 09:53:11 -0300 Date: Tue, 23 Jun 2009 07:46:41 -0400 (EDT) From: Michael Barr To: Paul Taylor , , claudio pisani Subject: categories: Re: no fundamental theorems please MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed Sender: categories@mta.ca Precedence: bulk Reply-To: Michael Barr Message-Id: Status: O X-Status: X-Keywords: X-UID: 104 Let me second Paul's observation. Going from the Yoneda lemma to a more sophisticated version would be analogous to saying that the Fundamental Theorem of calculus is "really" Stokes's theorem in its most general form (that the integral of form over the boundary of an n-dimensional compact region is the integral of the differential of the form over the region). The point of fundamental theorems is that they are easy to state and somehow capture something essential about the subject. The original Yoneda lemma states that all the properties of an object are present in its homfunctor. Thus objects are really captured by the morphisms. That it then leads to very sophisticated extensions is the point, but it, not they, are the basis for it all. Michael On Mon, 22 Jun 2009, Paul Taylor wrote: > I see that Takuo and I have still not overcome the "royalist" forces. > > Claudio, Vaughan, Ross and others have mentioned various more > "sophisticated" versions of the Yoneda Lemma. > > However, I contend that the more sophisticated the result is, > the LESS it deserves to be called "the fundamental theorem of > category theory". > ... > And the Yoneda Lemma will survive as long as Category Theory > does in a recognisable form. > > But it still shouldn't be called the "fundamental theorem"! > > Paul > [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Tue Jun 23 17:00:23 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 23 Jun 2009 17:00:23 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MJC8x-0002vt-5j for categories-list@mta.ca; Tue, 23 Jun 2009 16:58:59 -0300 Date: Tue, 23 Jun 2009 15:09:26 +0200 (CEST) From: Johannes Huebschmann To: "Fred E.J. Linton" , categories@mta.ca Subject: categories: Re: Topology on cohomology groups MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: quoted-printable Sender: categories@mta.ca Precedence: bulk Reply-To: Johannes Huebschmann Message-Id: Status: RO X-Status: X-Keywords: X-UID: 105 [From moderator: This issue is fun, but off-topic... so it should be closed. Categories posting will be intermittent until July 7, after CT2009.] Dear All To add to the confusion: There is a difference between skeleton and polygon: skeletos, etc. is a participle polygon is a noun polygonon in ancient Greek polygono in modern Greek plural form polygona in ancient Greek >From my recollections: as a participle (I would have to check this): skeletos, skeletae, skeleton etc., the neutrum participle "skeleton" also has plural forms: skeleta (nominativ) skeleton (genitiv) (long o, i.e. omega) skeletois (dativ) skeleta (accusativ) I cannot check details right now since I cannot chek my ancient Greek sources right now to confirm. Best regards Johannes HUEBSCHMANN Johannes Professeur de Math=C3=A9matiques USTL, UFR de Math=C3=A9matiques UMR 8524 Laboratoire Paul Painlev=C3=A9 59 655 VILLENEUVE d'ASCQ C=C3=A9dex/France http://math.univ-lille1.fr/~huebschm TEL. (33) 3 20 43 41 97 (33) 3 20 43 42 33 (s=C3=A9cr=C3=A9tariat) (33) 3 20 43 48 50 (s=C3=A9cr=C3=A9tariat) Fax (33) 3 20 43 43 02 Johannes.Huebschmann@math.univ-lille1.fr On Tue, 23 Jun 2009, Fred E.J. Linton wrote: > On Mon, 22 Jun 2009 09:17:05 AM EDT, "Prof. Peter Johnstone" > > in response to: Andrew Stacey wrote, in pa= rt: > >> On Fri, 19 Jun 2009, Andrew Stacey wrote: >> >>> ... over the finite skeleta. >> >> Not really a contribution to the mathematical question, but I'm struck= by >> the fact that both Andrew Salch and Andrew Stacey, in their replies to >> Steve Vickers, use the plural "skeleta". I used to do that when I was = a >> student, as a way of winding-up my teachers, but it isn't justifiable. >> >> The English word "skeleton" is indeed derived from a Greek root (the >> past participle of the verb "skellein", to wither or dry up), but it >> doesn't exist as a noun in Greek. There is therefore no justification >> for giving it an imagined Greek plural. Having in my time devoted some >> effort to fighting the bogus (but in fact more justifiable) Greek >> plural "topoi", I feel bound to protest against this one too. ... > > The generic-seeming example "phenomenon/phenomena" certainly *suggests* > a parallel "skeleton/skeleta" -- but it would also suggest "polygon/pol= yga", > which I think we all would agree is nonsense. Peter is merely (justifia= bly) > pointing out that "skeleton/skeleta" is as much nonsense as "polygon/po= lyga", > and I'm with him 100% on that score. > > [As for the plural of "topos", I guess I'm in the mugwump camp that wou= ld > *write* it as "topoi" (pace Peter), but *pronounce* it as "toposes" :-)= . > English was never very strong at phonetic consistency of pronunciation; > witness GBShaw's "phonetic" spelling of FISH: "ghotip".] > > Cheers, -- Fred > > PS: "ghotip"? "gh" as in COUGH, "o" as in WOMEN, > "ti" as in NATION, and "p" (silent) as in PNEUMONIA. > > > > > [For admin and other information see: http://www.mta.ca/~cat-dist/ ] > ---1463771056-1253283172-1245762566=:5534-- [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Tue Jun 23 17:00:23 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 23 Jun 2009 17:00:23 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MJC9d-0002zN-Dj for categories-list@mta.ca; Tue, 23 Jun 2009 16:59:41 -0300 MIME-Version: 1.0 Date: Tue, 23 Jun 2009 16:47:18 +0200 Subject: categories: Re: no fundamental theorems please From: Andrej Bauer To: Miles Gould , Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit Sender: categories@mta.ca Precedence: bulk Reply-To: Andrej Bauer Message-Id: Status: O X-Status: X-Keywords: X-UID: 106 On Tue, Jun 23, 2009 at 11:27 AM, Miles Gould wrote: > is there another name I can use for the theorem that right > adjoints preserve limits and left adjoints preserve colimits My teacher of category theory calls the first of these two theorems RAPL. Maybe he can explain whether he picked it up from someone. Somehow, LAPC does not sound so good. Andrej [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Tue Jun 23 17:00:28 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 23 Jun 2009 17:00:28 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MJCAK-00033N-Vw for categories-list@mta.ca; Tue, 23 Jun 2009 17:00:25 -0300 From: Barney Hilken To: "Townsend, Christopher" Content-Type: text/plain; charset=US-ASCII; format=flowed; delsp=yes Content-Transfer-Encoding: 7bit Mime-Version: 1.0 (Apple Message framework v935.3) Subject: categories: Re: Triquotient assignments for geometric morphisms Date: Tue, 23 Jun 2009 16:40:28 +0100 Sender: categories@mta.ca Precedence: bulk Reply-To: Barney Hilken Message-Id: Status: O X-Status: X-Keywords: X-UID: 107 Hi Christopher & Steve, thanks for your replies. The version I need is the generalisation of open & proper morphisms (i.e. some kind of map f_*\Omega_F -> \Omega_E) rather than the generalisation of locally connected & tidy morphisms (some kind of functor F -> E). As Steve says, I think the results I want follow from the stability of the hyperconnected-localic factorisation, but I was hoping someone had written out the details in the style of sections C3.1 & C3.2 of the Elephant. Looks like I'll have to do it myself. Barney. [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Tue Jun 23 17:00:53 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 23 Jun 2009 17:00:52 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MJCAj-00036L-Kq for categories-list@mta.ca; Tue, 23 Jun 2009 17:00:49 -0300 Date: Tue, 23 Jun 2009 18:19:49 +0200 From: Anders Kock MIME-Version: 1.0 To: categories@mta.ca Subject: categories: Re: monad: (k-Set \downarrow -): Set -->Set Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Sender: categories@mta.ca Precedence: bulk Reply-To: Anders Kock Message-Id: Status: O X-Status: X-Keywords: X-UID: 108 Mark Weber says rightly about David Spivak's "monad" (and it applies to its natural extension to the "cocompletion under k-small coproducts-monad" on Cat as well): "One could fix a skeleton of Set_k, and for k = cardinality of natural numbers this works fine, and the monad on Set you get is the monoid monad. However for bigger k you're likely to run into problems when trying to do this sort of thing." Yes, you do run into problems; however, they can be solved, as I showed in my Chicago thesis 1967. Namely, take for Set_k the (small) full subcategory of Sets whose objects are the ORDINAL numbers of cardinality less than the regular cardinal k. Ordinal sum formation then allows you to get the multiplication of the monad to be strictly associative. Similarly for the "similar monad" mentioned by David (based on the Grothendieck-construction of categories) - this monad is also in my thesis, and Lawvere reports on it in his "Ordinal sums and equational doctrines", (Seminar on Triples, SLN 80 (1969), see p.152-153. ). However, these cunning tricks to get strict associativity were in the 1960s forced on us, for historical reasons: at that time we did not have the notion of 2-dimensional category well enough established to see these cocompletion "monads" in their true 2-dimensional nature. The "similar monads", based on a suitable Cat_k, are also reported on in loc.cit.; and Cat_k could be replaced by any small category Cat_0 of categories which is stable under the Grothendieck construction, like the category of k-small posets, or of k-small directed categories. (I called these monads "prelimit monads"; Lawvere calls them Dir_Cat_0. They also appear in Guitart's 1974-article, as referenced in my previous posting.) Anders Kock [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Tue Jun 23 17:01:45 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 23 Jun 2009 17:01:45 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MJCBZ-0003Bu-Fq for categories-list@mta.ca; Tue, 23 Jun 2009 17:01:41 -0300 Date: Tue, 23 Jun 2009 11:58:26 -0700 From: Vaughan Pratt MIME-Version: 1.0 To: categories Subject: categories: Re: no fundamental theorems please Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Sender: categories@mta.ca Precedence: bulk Reply-To: Vaughan Pratt Message-Id: Status: O X-Status: X-Keywords: X-UID: 109 On 6/22/2009 2:07 PM, Paul Taylor wrote: > Claudio, Vaughan, Ross and others have mentioned various more > "sophisticated" versions of the Yoneda Lemma. I don't see how supplying the missing half of an if-and-only-if is "more sophisticated." The Yoneda Lemma usually states that J embeds (meaning fully) in [J^op,Set], but it could just as well state this for any factor C between J and [J^op,Set]. In such situations it is natural to ask whether the converse holds; it doesn't, but if one adds to full-and-faithful the (very natural) requirement of density then it does: the dense extensions of J are precisely the categories of presheaves on J, by which I mean the full subcategories of [J^op,Set] that retain J as a full subcategory (the sense of "on"). I don't call that sophisticated. > However, I contend that the more sophisticated the result is, > the LESS it deserves to be called "the fundamental theorem of > category theory". Indeed. Any branch of mathematics that does so only contributes to the image of mathematics as a difficult subject. > I particularly like Euclid's algorithm for the highest common > factor as a historical and methodological example, Without > meaning to dictate to number theorists how their subject should > be organised, let me suggest for the sake of argument that it > is a pretty good candidate for being called the "fundamental > theorem of number theory". That's an algorithm. The relevant theorem is also called the fundamental theorem of arithmetic. One could state the essential idea in sophisticated language as "Z is a principal ideal domain" but the more usual statement about uniqueness of factorization of positive integers makes number theory a more accessible subject. > As I say, I like Euclid's algorithm because the idea has > survived many many revolutions in the "official" foundations > of mathematics. > [...] Cantor's "theorem" about a powerset being > strictly bigger than a set. This belongs entirely to the dogma > of set theory. When set theory is overturned, this miserable > and wholely misguided "theorem" will go in the dustbin of > mathematical history with it. I like Cantor's theorem because, like Euclid's algorithm, it will survive the revolution Paul is trying to foment here. > But Euclid's algorithm will live forever. As will diagonalization arguments like Cantor's. > But [Yoneda's Lemma] still shouldn't be called the "fundamental theorem"! Unlike the Fundamental Theorems of Arithmetic and of Algebra, the Yoneda Lemma has not yet established itself as *the* fundamental theorem of category theory. Nor will it unless a reasonable consensus to that effect emerges. I suggest waiting a few years before coming to any conclusion about whether CT has an FT, and if so what it is. Vaughan Pratt [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Fri Jun 26 04:39:25 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 26 Jun 2009 04:39:25 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MK5zO-0005sL-64 for categories-list@mta.ca; Fri, 26 Jun 2009 04:36:50 -0300 Date: Wed, 24 Jun 2009 13:52:41 +0000 (GMT) From: claudio pisani Subject: categories: Re: no fundamental theorems please To: Michael Barr , categories@mta.ca, Paul Taylor MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: quoted-printable Sender: categories@mta.ca Precedence: bulk Reply-To: claudio pisani Message-Id: Status: O X-Status: X-Keywords: X-UID: 110 Of course, the proof that the object x:1->X (of Cat/X) has the slice X/x -= > X as a reflection in df/X (and its final object as reflecton map) is esse= ntially the same of that of the standard Yoneda lemma, and the general case= only requires a little more effort. My point is that this formulation seems to me more in the "categorical spir= it", stating a universal property that relates categories over X and discre= te fibrations. In fact the paradigm "categories, functors and natural transformations" can= be in part replaced by "categories, functors and discrete (op)fibrations";= for instance a colimit x of the object p:P -> X of Cat/X is a reflection o= f p in slices over X, where the reflection map p -> X/x in Cat/X is the col= imiting cone, and so on. Furthermore, there is a clear analogy (which can be made precise with the p= roper choice of factorization system on posets) with the reflection of the = subsets of a poset X in lower or upper sets of X (the principal sieves bein= g a particular case). Best regards Claudio [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Fri Jun 26 04:39:25 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 26 Jun 2009 04:39:25 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MK61c-0005vU-6I for categories-list@mta.ca; Fri, 26 Jun 2009 04:39:08 -0300 Date: Wed, 24 Jun 2009 16:17:02 +0100 From: Steve Vickers MIME-Version: 1.0 To: Vaughan Pratt , Categories Subject: categories: Re: no fundamental theorems please Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Sender: categories@mta.ca Precedence: bulk Reply-To: Steve Vickers Message-Id: Status: O X-Status: X-Keywords: X-UID: 111 Vaughan Pratt wrote: > ... The Yoneda Lemma usually states that J embeds (meaning > fully) in [J^op,Set], ... Dear Vaughan, The usual statement is significantly stronger than that (see e.g. Mac Lane, Mac Lane and Moerdijk, or Wikipedia). It says that, for contravariant functors F: C -> Set, the elements of FX are in bijection with transformations to F from the representable functor for X. Your statement can be deduced by considering the particular case where F too is representable. (To put it another way, the representable presheaf for X is freely generated - as presheaf - by a single element (the identity morphism) at X. This then allows you to calculate the left adjoint of the forgetful functor from presheaves over C to ob(C)-indexed families of sets.) There can be no doubt that this strong Yoneda Lemma is vitally important when calculating with presheaves - for example, it shows immediately how to calculate exponentials and powerobjects. If F and G are two presheaves, then the exponential G^F is calculated by G^F(X) = nt(Y(X), G^F) (by Yoneda's Lemma) = nt(Y(X) x F, G) (by definition of exponential) I don't think you can get it and its useful consequences from your weaker statement, even if you start strengthening yours in the way you suggest by supplying converses. Another closely related and important result, though not known as Yoneda's Lemma as far as I know, is that the presheaf category over C is a free cocompletion of C, and the Yoneda embedding is the injection of generators. (By the way, I agree that category theory doesn't have to have a Fundamental Theorem. I haven't see any compelling reason to appoint one.) Regards, Steve. [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Fri Jun 26 04:39:25 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 26 Jun 2009 04:39:25 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MK60W-0005uF-W2 for categories-list@mta.ca; Fri, 26 Jun 2009 04:38:01 -0300 Date: Wed, 24 Jun 2009 09:55:05 -0400 To: categories@mta.ca From: "Ellis D. Cooper" Subject: categories: Proofs from THE BOOK Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Sender: categories@mta.ca Precedence: bulk Reply-To: "Ellis D. Cooper" Message-Id: Status: O X-Status: X-Keywords: X-UID: 112 Dedicated to the memory of Paul Erdos, Martin Aigner and Gunter M. Ziegler's book (with the Subject title) offers examples of proofs with "brilliant ideas, clever insights and wonderful observations." They include chapters on Number Theory, Geometry, Analysis, Combinatorics, and Graph Theory. My question is, what would likely be included if there were a chapter on Category Theory? Ellis D. Cooper [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Fri Jun 26 04:39:54 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 26 Jun 2009 04:39:54 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MK62I-0005xA-Ti for categories-list@mta.ca; Fri, 26 Jun 2009 04:39:50 -0300 Date: Wed, 24 Jun 2009 12:18:10 -0400 From: jim stasheff MIME-Version: 1.0 To: Categories list Subject: categories: query Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Sender: categories@mta.ca Precedence: bulk Reply-To: jim stasheff Message-Id: Status: O X-Status: X-Keywords: X-UID: 113 Mac Lane coherence can be deduced from the simple connectivity of the associahedron Is it written that way anywhere? jim [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Fri Jun 26 04:41:39 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 26 Jun 2009 04:41:39 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MK63z-00061u-4Q for categories-list@mta.ca; Fri, 26 Jun 2009 04:41:35 -0300 MIME-Version: 1.0 Date: Thu, 25 Jun 2009 12:48:23 -0700 Subject: categories: Can you spot a flaw in this argument? From: Meredith Gregory To: Categories Content-Type: text/plain; charset=ISO-8859-7 Content-Transfer-Encoding: quoted-printable Sender: categories@mta.ca Precedence: bulk Reply-To: Meredith Gregory Message-Id: Status: O X-Status: X-Keywords: X-UID: 114 All, This is an argument about effective theories and so i would love to hear from the topos-theory crowd. i'll state the argument in lowly computational terms, using two distinct proposals for foundational models of computing: the lambda calculus and the =F0-calculus. Both the lambda calculus and the =F0-calculus suffer a dependence on a theory of names (aka variables). Both require two things of whatever theory of names is provided to them: - at least countably infinitely many names - an effective equality on names Now, to this recent proposals[1] add a third constraint, namely - names are atomic -- they have no internal structure To my way of thinking these three constraints are incompatible. i cannot se= e how to make an effective equality on a countably infinite set of entities that have no internal structure on which to rest the equality check. It seems to me that the only possible expression of the equality is an infinit= e table which states the results of comparing every single pair of atoms -- which is not going to fit into any realizable model of computation of which i'm aware and understand. Is there a way around this? If there is, i would be eternally grateful to b= e enlightened. The reason i focus on foundational proposals for theories of computation is that one could drop the atomic requirement and allow names to have internal structure, but because of the other two constraints one is dangerously clos= e to sneaking into a supposedly foundational account a theory of names that i= s -- itself -- already sufficiently rich to model computation. (For example, in many implementations of lambda or =F0-calculus, names are ultimately represented as integers.) This would appear to undermine the foundational character of the model of computation in question. This has led me to constructions in which the internal structure of names *reflects* the structure of computations. In fact, this idea has a simple monadic characterization, but that's for another discussion. i've already posted to this list an intuitive account of red/black set theories that also side-step the issue of atoms with no structure which allows to recast the FM-Set-Theory-based accounts of names onto what appear= s to me to be the only construction that meets all the requirements mentioned above: sufficiently many names, effective equality, restricting internal structure of names to the structure of the proposal at hand. Again, if ther= e is a way to skate around this argumentation or debunk it, please consider this a sincere call for help to do so. Best wishes, --greg [1] See the Gabbay-Pitts papers on using FM-Set Theory for an account of fresh names and alpha-equivalence. --=20 L.G. Meredith Managing Partner Biosimilarity LLC 1219 NW 83rd St Seattle, WA 98117 +1 206.650.3740 http://biosimilarity.blogspot.com [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Sat Jun 27 04:18:02 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 27 Jun 2009 04:18:02 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MKS86-0001ue-Jz for categories-list@mta.ca; Sat, 27 Jun 2009 04:15:18 -0300 Date: Fri, 26 Jun 2009 09:32:47 +0100 (BST) From: "Prof. Peter Johnstone" To: Meredith Gregory , Subject: categories: Re: Can you spot a flaw in this argument? MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed Sender: categories@mta.ca Precedence: bulk Reply-To: "Prof. Peter Johnstone" Message-Id: Status: O X-Status: X-Keywords: X-UID: 115 Dear Gregory, I think the problem resides in what you mean by "no internal structure". If by this you mean that the *set* of names has no internal structure, then it's obviously impossible -- to require the set to have decidable equality is to impose internal structure on it. But it's still possible for the names themselves to be atomic: you can identify the set of names with the set of natural numbers (which has lots of internal structure, including decidable equality) without identifying the individual names with von Neumann-style natural numbers (or Russell-style cardinals, or ...) Peter Johnstone On Thu, 25 Jun 2009, Meredith Gregory wrote: > All, > > This is an argument about effective theories and so i would love to hear > from the topos-theory crowd. i'll state the argument in lowly computational > terms, using two distinct proposals for foundational models of computing: > the lambda calculus and the ?-calculus. Both the lambda calculus and the > ?-calculus suffer a dependence on a theory of names (aka variables). Both > require two things of whatever theory of names is provided to them: > > - at least countably infinitely many names > - an effective equality on names > > Now, to this recent proposals[1] add a third constraint, namely > > - names are atomic -- they have no internal structure ... [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Sat Jun 27 04:18:34 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 27 Jun 2009 04:18:34 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MKSA4-0001vx-3r for categories-list@mta.ca; Sat, 27 Jun 2009 04:17:20 -0300 Mime-Version: 1.0 (Apple Message framework v624) Content-Type: text/plain; charset=US-ASCII; format=flowed Content-Transfer-Encoding: 7bit From: Paul Taylor Subject: categories: Equideductive categories and their logic Date: Fri, 26 Jun 2009 09:54:10 +0100 To: categories list Sender: categories@mta.ca Precedence: bulk Reply-To: Paul Taylor Message-Id: Status: O X-Status: X-Keywords: X-UID: 116 "Equideductive categories and their logic" www.PaulTaylor.EU/ASD/extension Under the heading "Locally cartesian closed categories", on 8 October 2007, I asked whether anybody had investigated to what extent the true statement but an incorrect definition > Any topos is a CCC with an internal Heyting algebra, actually gives rise to interesting structure. However, I didn't get much response. I went on > Suppose that the category has all FINITE LIMITS (terminal object, > finite products and equalisers) and POWERS Sigma^X of an internal > DISTRIBUTIVE LATTICE (Sigma, top, bot, meet, join). Maybe there > is also a natural numbers object N and joins Sigma^N->Sigma with > the Frobenius law. (I would also like this to obey the monadic > and Phoa principles of ASD, but I'm not going to spell them out here.) > > Maps X->Sigma give rise to a "geometric logic" of "open" subspaces. > > Then the order relation between maps X->Sigma^Y leads to a richer > logic of "general" subspaces, with => and forall_Y. > > A logical formula of the more general form consists of geometric > sub-formulae joined together with => and forall, to which we might > add the other first order connectives as "syntactic sugar", defined > in the usual classical way. If a geometric sub-formula is immediately > enclosed in forall_K or exists_N, where K happens to be compact or > N overt, then this a priori more general quantifier may be considered > to be part of the geometric sub-formula. The draft paper advertised above investigates these ideas. This work was part of a re-formulation of Dana Scott's equilogical space construction about which you can find three sets of slides at www.PaulTaylor.EU/slides/ and the details will follow shortly. My lengthy posting on "Applications of the Yoneda embedding" on 20 June 2009 also provides background material for this. However, it has turned out to be very fruitful to leave the CCC aside and first consider the properties of a category that "lies nicely" within its cartesian closed extensions. The categories of sets, of sober topological spaces (in the textbook sense) and of affine varieties have the appropriate properties. However, because of the counterexample that I gave in "Aspects of locale theory" on 9 June 2009, the category of locales does not (products do not preserve epis). As I suggested in 2007, the key idea is to study equalisers targeted at exponentials. In terms of the Yoneda embedding, if we have a pair of maps from a representable presheaf to the exponential (Sigma^-) of another representable, is the equaliser representable too? We can reformulate this in the original category, without using presheaves, as a (kind of) PARTIAL PRODUCT. The categories of sets, topological spaces and affine varieties have these partial products. (I would like to thank Andrea Schalk, Mike Barr and possibly Robin Cockett for joining me in banging our heads against the brick wall of trying to find out whether locales have them too. Probably they don't, but I'm not sure whether it is this or something else that goes wrong.) An EQUIDEDUCTIVE CATEGORY is one that has finite limits, (my) partial products, an object Sigma that is injective wrt the monos that arise from partial products, and enough injectives. It turns out that those objects A that have exponentials Sigma^A are SOBER in my abstract sense, and the adjunction Sigma^- -| Sigma^- on this subcategory is monadic. In other words we have the characteristic properties of the subcategory of locally compact spaces within the category of sober topological spaces, without assuming any structure on Sigma such as being a lattice. EQUIDEDUCTIVE LOGIC captures this categorical structure in symbolic form. It is a predicate calculus whose object language is the sober lambda calculus. The chief feature is a quantified implication that justifies the (recursive) notation E = { x:A | All y:B. q(y) => fxy=gxy } for the equaliser E >--> A ====> Sigma^Y where Y = {b:B | q(y)}. Note that the predicates that are defined by this logic are general subobjects, not terms of type Sigma^A. Using quantification over terms of type Sigma^A, one can define an "existential quantifier". This is the most striking aspect of equideductive logic: although this is an old idea (maybe due to Russell) from higher order logic, it turns out to characterise the EPIs in the category, which have to be preserved by products. Of course, epis need not be surjective. For example N-->>X is epi amongst sober spaces, where X is the domain of ascending natural numbers, with T=oo. This means that one has to be EXTREMELY careful in using this quantifier -- it only has a restricted Frobenius law and doesn't allow substitution -- but I think that it will turn out to be very useful. For example, Scott continuity can be expressed in the form that, for phi:Sigma^N, "there exists" a finite set S such that phi n <=> n in S. What this means is that it is sufficient to test this case when proving equality of terms of type Sigma. We recover topology (in the style of ASD) by requiring SOME of these quantifiers to agree with structure on Sigma. That is, a space {x:A|p(x)} is compact or overt if the PREDICATE given by quantification of a term of type Sigma^A agreed with another term of type Sigma. On the other hand, and coming back to the question at the top of this posting, we recover set theory (ie an elementary topos) by requiring ALL quantifiers to agree with operators on Sigma. I trust that I will not hear any further repetition of the claim that ASD is restricted to locally compact spaces. This paper essentially replaces "Subspaces in ASD" and the monadic lambda calculus. It also fills in several gaps in other papers, such as allowing equational hypotheses and constructing the compact and overt subspaces that are described by modal operators. Paul Taylor [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Sat Jun 27 04:20:03 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 27 Jun 2009 04:20:03 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MKSBU-0001yN-5h for categories-list@mta.ca; Sat, 27 Jun 2009 04:18:48 -0300 From: "Noson S. Yanofsky" To: "'Categories list'" Subject: categories: RE: query Date: Fri, 26 Jun 2009 06:47:07 -0400 MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Sender: categories@mta.ca Precedence: bulk Reply-To: "Noson S. Yanofsky" Message-Id: Status: O X-Status: X-Keywords: X-UID: 117 > -----Original Message----- > From: categories@mta.ca [mailto:categories@mta.ca] On Behalf Of jim > stasheff > Sent: Wednesday, June 24, 2009 12:18 PM > To: Categories list > Subject: categories: query > > Mac Lane coherence can be deduced from the simple connectivity of the > associahedron > Is it written that way anywhere? > > jim Hi, Yes. My thesis. "Obstructions to Coherence: Natural Noncoherent Associativity and Tensor Functors", City University of New York, 1996. The part about the associahedron was published in Obstructions to Coherence: Noncoherent Associativity The Journal of Pure & Applied Algebra. 147 no. 2, Pgs 175 - 213. (2000). or http://xxx.lanl.gov/abs/math.QA/9804106 The second part about the tensor functors was never published. I look at the fundamental group of the associahedra thought of as groupoids (called the "Catalan groupoids"). They are all trivial. But then I ask, what if the pentagons do not commute? The fundamental group of the Mac Lane non-commuting pentagon is Z. And I get generators and relations for all the higher non-commuting associahedra. They are not free groups from n=7 on. I do a similar thing for non-coherent tensor functors (monoidal functors). All the best, Noson [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Sat Jun 27 04:22:49 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 27 Jun 2009 04:22:49 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MKSE4-00024W-05 for categories-list@mta.ca; Sat, 27 Jun 2009 04:21:28 -0300 Date: Fri, 26 Jun 2009 09:45:23 -0400 (EDT) From: Michael Barr To: "Ellis D. Cooper" Subject: categories: Re: Proofs from THE BOOK MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed Sender: categories@mta.ca Precedence: bulk Reply-To: Michael Barr Message-Id: Status: O X-Status: X-Keywords: X-UID: 118 Well, you might want to look at this: \item (With. M.-A. Knus), Extensions of Derivations. Proc. Amer. Math. Soc. {\bf 28} (1971), 313--314. This is more homological algebra than category theory. The story is that someone had done this in a special case (where the center was local I think) in a dozen pages and someone else had extended it to semilocal and Knus was lecturing at the ETH on his extension to arbitrary centers (but the ambient ring was always semi-simple = Hochschild dimension 0). As Knus was lecturing I said to myself that there had to be a better way. And there was. It took only a paragraph and use only Hochschild dimension 1 besides. The rest of the two pages was intro and bibliography. Although it isn't category theory it exemplifies the categorical way of thinking, dealing with generic properties and the like. Incidentally, the paper was originally rejected. The referee's report said, "The only possible reason for publishing this is that it has been so badly handled in the literature"! I would have thought that an excellent reason to publish it. Only the fact that the editor was a personal friend who said he would publish it if I insisted, allowed it to see the light of day. But I have long thought it a "proof from the book". Michael On Wed, 24 Jun 2009, Ellis D. Cooper wrote: > Dedicated to the memory of Paul Erdos, Martin Aigner and Gunter M. > Ziegler's book (with the Subject title) offers examples of proofs > with "brilliant ideas, clever insights and wonderful observations." > They include chapters on Number Theory, Geometry, Analysis, > Combinatorics, and Graph Theory. My question is, what would likely be > included if there were a chapter on Category Theory? > > Ellis D. Cooper > > > > [For admin and other information see: http://www.mta.ca/~cat-dist/ ] > > [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Sat Jun 27 04:23:59 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 27 Jun 2009 04:23:59 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MKSFJ-00026J-Di for categories-list@mta.ca; Sat, 27 Jun 2009 04:22:45 -0300 MIME-Version: 1.0 Date: Fri, 26 Jun 2009 08:51:11 -0500 Subject: categories: Re: no fundamental theorems please From: Michael Shulman To: claudio pisani Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Sender: categories@mta.ca Precedence: bulk Reply-To: Michael Shulman Message-Id: Status: O X-Status: X-Keywords: X-UID: 119 On Wed, Jun 24, 2009 at 8:52 AM, claudio pisani wrote: > Of course, the proof that the object x:1->X (of Cat/X) has the slice > =A0X/x -> X as a reflection in df/X (and its final object as > reflecton map) is essentially the same of that of the standard > Yoneda lemma, and the general case only requires a little more > effort. This is indeed a very nice statement of the ordinary Yoneda lemma, but it doesn't seem capable of capturing all incarnations of the Yoneda lemma, such as that in enriched category theory. Mike [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Sat Jun 27 04:24:54 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 27 Jun 2009 04:24:54 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MKSGH-00028T-4o for categories-list@mta.ca; Sat, 27 Jun 2009 04:23:45 -0300 Date: Fri, 26 Jun 2009 16:51:56 +0100 (BST) From: Tom Leinster To: jds@math.upenn.edu Subject: categories: Re: query MIME-Version: 1.0 Content-Type: TEXT/PLAIN; format=flowed; charset=US-ASCII Sender: categories@mta.ca Precedence: bulk Reply-To: Tom Leinster Message-Id: Status: O X-Status: X-Keywords: X-UID: 120 Dear Jim, On Wed, 24 Jun 2009, jim stasheff wrote: > Mac Lane coherence can be deduced from the simple connectivity of the > associahedron Surely that's not true, assuming that by "Mac Lane coherence" you mean Mac Lane's coherence theorem for monoidal categories. The associahedra (and in particular the pentagon) say nothing about the unit coherence isomorphisms, X \otimes I ----> X <---- I \otimes X. To make it true, surely you need to weaken Mac Lane's theorem to a statement about "semigroupal" categories, i.e. monoidal categories without unit...? Best wishes, Tom [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Sat Jun 27 04:27:13 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 27 Jun 2009 04:27:13 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MKSIO-0002Fe-HR for categories-list@mta.ca; Sat, 27 Jun 2009 04:25:56 -0300 Date: Fri, 26 Jun 2009 07:59:42 -0300 (ADT) From: Toby Kenney To: categories@mta.ca Subject: categories: Injective objects in topoi. MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: categories@mta.ca Precedence: bulk Reply-To: Toby Kenney Message-Id: Status: O X-Status: X-Keywords: X-UID: 121 Dear Category theorists, I'm sure the following lemma is either known, or I've made some mistake in proving it: Lemma: If I is an injective object in a topos, then for any monomorphism I>---m--->A, the object of splittings of m, i.e. S={f:I^A|(\forall i:I)(f(m(i))=i)} is also injective. Could someone let me know of a reference to it. Thanks a lot. Toby [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Sun Jul 5 12:17:51 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 05 Jul 2009 12:17:51 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MNTR1-0006UL-Ge for categories-list@mta.ca; Sun, 05 Jul 2009 12:15:19 -0300 Date: Sun, 28 Jun 2009 21:11:02 -0700 From: Vaughan Pratt MIME-Version: 1.0 To: Categories Subject: categories: Yoneda Theorem < Yoneda Lemma < Dense Yoneda Theorem Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Sender: categories@mta.ca Precedence: bulk Reply-To: Vaughan Pratt Message-Id: Status: O X-Status: X-Keywords: X-UID: 122 (This continues the "no fundamental theorems please" thread under a more apropos heading.) On 6/24/2009 8:17 AM, Steve Vickers wrote: > Vaughan Pratt wrote: >> ... The Yoneda Lemma usually states that J embeds (meaning >> fully) in [J^op,Set], ... > The usual statement is significantly stronger than that (see e.g. Mac > Lane, Mac Lane and Moerdijk, or Wikipedia). It says that, for > contravariant functors F: C -> Set, the elements of FX are in bijection > with transformations to F from the representable functor for X. Your > statement can be deduced by considering the particular case where F too > is representable. Quite right, I should have used something other than "lemma" for that weaker statement. Misplaced force of habit. Googling "Theorem 5.1 (Yoneda)" returns section 5, on full completeness, of Phil Scott's nice Handbook of Algebra chapter. Phil introduces that section with "The most basic representation theorem of all is the Yoneda embedding: Theorem 5.1 (Yoneda) If J is locally small, the Yoneda functor Y: J --> [J^op,Set], where Y(j) = J(-,j), is a fully faithful embedding." (Phil's A is my J, which I'll use throughout as the base whether small or not in order to make it easier to compare theorems.) If "theorem" is good enough for Phil it's good enough for me. For definiteness let's name the theorems as follows. YT (Yoneda Theorem): [J^op,Set] fully extends J. YL (Yoneda Lemma): For any functor F: J^op --> Set and object j of J, F(j) is in bijection with [J^op,Set](J(-,j),F). (This replaces C in Steve's version with J^op.) DYT (Dense Yoneda Theorem): C is equivalent to a category of presheaves on a *small* category J if and only if C densely extends J. Here a category of presheaves on J means a full subcategory of [J^op,Set] containing the functors J(-,j) for all objects j of J (that is, "on J" qualifies not just the individual presheaves but the whole category of them, as in "free group on X"(*)). C densely extends J just when there exists a full, faithful, and dense functor K: J --> C. (If someone has a use for a broader notion of dense extension I wouldn't object to saying "fully densely extends.") For now assume "dense" is defined as in X.6 of CWM, namely that every object of C arises as a colimit of FP for the evident functor P: (K,c) --> J, (K,c) being the comma category whose morphisms are of the form Kj-->c, j in ob(J). (I'll consider equivalent ways of defining density in a followup message.) This has the effect of representing each object c of C as the presheaf C(K-,c): J^op --> Set (namely C(Kj,c) is the set of morphisms of (K,c) of the form Kj-->c) and each homset C(c,d) as [J^op,Set](C(K-,c),C(K-,d)) (that is, Nat(C(K-,c),C(K-,d)) in the CWM notation Steve is using), via the adjunction defining "colimit." The homsets [J^op,Set](J(-,j),F) used by YL (and hence YT) are always small even if J isn't. DYT however deals with arbitrary homsets [J^op,Set](F,G), which may be large when J is, whence DYT's requirement that J be small. (Steve Lack would be the person to ask what form DYT might take for large J.) The applicability of YL and YT to large J makes them incomparable with DYT. However if we require J to be small then we have YT < YL < DYT in the sense that each of them represents entities by using progressively more of [J^op,Set]. YT uses just the image of the Yoneda embedding to represent J, YL takes one step beyond YT by using all the homsets from that image to an arbitrary presheaf in [J^op,Set] to represent carriers of algebras with unary operations (aka presheaves), and DYT takes one more step than YL by using homsets between more general presheaves of [J^op,Set] to represent *all* homsets of C. Replacing "equivalent to" by "representable as" in DYT makes more explicit the sense in which DYT is unambiguously a representation theorem for certain abstractly defined categories, namely dense extensions of a small category, which are of greater generality than the categories contemplated in YT or YL. > There can be no doubt that this strong Yoneda Lemma is vitally important > when calculating with presheaves - for example, it shows immediately how > to calculate exponentials and powerobjects. If F and G are two > presheaves, then the exponential G^F is calculated by > > G^F(X) = nt(Y(X), G^F) (by Yoneda's Lemma) > = nt(Y(X) x F, G) (by definition of exponential) I would only buy that reasoning for small J (otherwise why should G^F be a functor to Set?), where YL isn't benefiting from the additional generality of YL over DYT. Is there any other reason to prefer YL to DYT? It doesn't seem a very natural candidate for theorem-hood (perhaps that's why it's relegated to the status of a lemma). It's hard to argue for it as the fundamental theorem of CT when it's sandwiched in between YT and DYT, both of which *do* come across as real theorems (the reason I'm comfortable calling both of them theorems). Anyone remember the history of why YL rose to the top? > I don't think you can get it and its useful consequences from your > weaker statement, even if you start strengthening yours in the way you > suggest by supplying converses. Don't underestimate the power of the converse. YL < DYT because it's only a partial converse, DYT is the whole thing. > Another closely related and important result, though not known as > Yoneda's Lemma as far as I know, is that the presheaf category over C is > a free cocompletion of C, and the Yoneda embedding is the injection of > generators. The colimit-based definition of dense functor shows that this is pretty much equivalent to DYT and therefore stronger than YL in what I take to be the sense in which you consider YL stronger than YT. (Is there a stronger sense of "stronger," e.g. a natural nonstandard model in which YT is true and YL false, or YL true and DYT false?) Michael Shulman's comment about the enriched case is apropos here: defining cocompletion for conical (co)limits isn't sufficient when V doesn't permit them (for want of diagonal functors). This limitation can be avoided with left Kan extensions as treated in Chapter 4 of Kelly, "Basic Concepts of Enriched Category Theory." Kelly arrives at the notion of free cocompletion 15 pages into Chapter 4 and long after indexed (nowadays weighted) colimits (Chapter 3) as a satisfactory generalization of conical colimits. (Incidentally, of what use are non-free cocompletions? Is there any reason not to define "cocompletion" to make it free? I seem to recall people being happy to drop "free" in this context. Who ordered "free"?) This post is quite long enough already so I'll stop it here with the interesting question (to me anyway), what is the earliest point in the development of (ordinary or unenriched) category theory at which one can introduce either cocompletion or density in order to have functors that are dense, full, and faithful? Can either be usefully introduced before functor categories, for example? And can this be done with sufficient generality to carry over essentially unchanged to the enriched case? I imagine this would reduce to just avoiding conical colimits. Vaughan Pratt (*) But not as in "free beer on Stallman." [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Sun Jul 5 12:17:51 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 05 Jul 2009 12:17:51 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MNTS8-0006Ys-QS for categories-list@mta.ca; Sun, 05 Jul 2009 12:16:28 -0300 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Subject: categories: Re: Proofs from THE BOOK Date: Mon, 29 Jun 2009 10:49:23 -0400 From: "Wojtowicz, Ralph" To: Sender: categories@mta.ca Precedence: bulk Reply-To: "Wojtowicz, Ralph" Message-Id: Status: O X-Status: X-Keywords: X-UID: 123 The proof of Proposition 2.7.1 on page 59 in Volume I of "Handbook of = Categorical Algebra" by Francis Borceux may be a candidate. John Gray = once told me that the proof is due to Peter Freyd. When I was studying = category theory in graduate school, proofs of this proposition, the = Adjoint Functor Theorem, and some other results in "Categories, = Allegories" struck me as demonstrating a creative, original, and = insightful use of limits and colimits. Best wishes, Ralph Wojtowicz Metron, Inc. 1818 Library Street, Suite 600 Reston, VA 20190 On Wed, 24 Jun 2009, Ellis D. Cooper wrote: > Dedicated to the memory of Paul Erdos, Martin Aigner and Gunter M. > Ziegler's book (with the Subject title) offers examples of proofs > with "brilliant ideas, clever insights and wonderful observations." > They include chapters on Number Theory, Geometry, Analysis, > Combinatorics, and Graph Theory. My question is, what would likely be > included if there were a chapter on Category Theory? > > Ellis D. Cooper > [For admin and other information see: http://www.mta.ca/~cat-dist/ ] From rrosebru@mta.ca Sun Jul 5 12:17:58 2009 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 05 Jul 2009 12:17:58 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MNTTT-0006bl-Qs for categories-list@mta.ca; Sun, 05 Jul 2009 12:17:51 -0300 From: Thomas Streicher Date: Tue, 30 Jun 2009 15:26:00 +0200 To: categories@mta.ca Subject: categories: separable locale MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Sender: categories@mta.ca Precedence: bulk Reply-To: Thomas Streicher Message-Id: Status: O X-Status: X-Keywords: X-UID: 124 Recently rereading Fourman's "Continuous Truth" I came across the term "separable locale" but could nowhere find an explanation. Does it mean a cHa A for which there exists a countable subset B such that ever a in A is the supremum of those b in B with b leq a. This would be the point free account of "second countable", i.e. having a countable basis. Of course, second countable T_) spaces are separable, i.e. have a countable dense set. Is this reading the "usual" one? Thomas [For admin and other information see: http://www.mta.ca/~cat-dist/ ]