From MAILER-DAEMON Fri May 18 09:17:05 2007 Date: 18 May 2007 09:17:05 -0300 From: Mail System Internal Data Subject: DON'T DELETE THIS MESSAGE -- FOLDER INTERNAL DATA Message-ID: <1179490625@mta.ca> X-IMAP: 1172947689 0000000066 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 Thu Mar 1 23:18:44 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 01 Mar 2007 23:18:44 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HMy8G-0003El-Ub for categories-list@mta.ca; Thu, 01 Mar 2007 23:08:32 -0400 Date: Thu, 01 Mar 2007 09:21:55 +0000 From: "V. Schmitt" MIME-Version: 1.0 To: categories Subject: categories: Re: terminology: dagger and involution Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 1 John Baez wrote: >Marco wrote: > > > >>what you are calling a "dagger-category", i.e. >> >> a category equipped with a contravariant involutive >> endofunctor, which is the identity on objects, >> >>has been called "a category with involution", at least from Burgin >>1969 to Lambek 2001. "Involutive category" has also been used, if >>less. >> >>I think it would be better to come back to the old term, which is >>meaningful, translatable, and old. >> >> > >There's also a body of work, mainly from mathematical physics, that >calls these categories "star-categories". > >But, by now there's enough literature using the term "dagger-categories" >that the genie is out of the bottle. > >Best, >jb > > > > > > Dear John, just my view: this is not a good argument. I do not know about these dagger categories though i read about the compact closed ones. So may be I miss the point but, if this is the case, why introducing a new terminology if the concepts are not? That just creates confusion. Best, Vincent From rrosebru@mta.ca Fri Mar 2 17:27:49 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 02 Mar 2007 17:27:49 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HNFBy-0003UD-3T for categories-list@mta.ca; Fri, 02 Mar 2007 17:21:30 -0400 Date: Thu, 1 Mar 2007 19:34:24 -0800 From: John Baez To: categories Subject: categories: terminology: dagger and involution Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 2 On Thu, Mar 01, 2007 at 09:21:55AM +0000, V. Schmitt wrote: > John Baez wrote: > >by now there's enough literature using the term "dagger-categories" > >that the genie is out of the bottle. > Dear John, just my view: this is not a good argument. It's not an argument - I'm just reporting on what I see. I don't really like the term "dagger-categories", and I gently tried to get people to stop using it, but it didn't work. They're already comfortable with it. > I do not know about these dagger categories though > i read about the compact closed ones. > So may be I miss the point but, if this is the case, why > introducing a new terminology if the concepts are not? > That just creates confusion. I hope this is clear: "dagger-categories" are completely different from "compact closed categories". We need *some* term for them; we're just arguing about whether to call them "star-categories", "dagger-categories", or "categories with involution". I like "star-categories", because in analysis and quantum topology the special case of "C*-categories" is very important. But, I doubt we'll reach any sort of agreement! Best, jb From rrosebru@mta.ca Sat Mar 3 14:25:59 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 03 Mar 2007 14:25:59 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HNYk8-0006Xe-B3 for categories-list@mta.ca; Sat, 03 Mar 2007 14:14:04 -0400 Date: Fri, 2 Mar 2007 16:53:58 -0500 (EST) From: Robert Seely To: categories Subject: categories: Re: terminology: dagger and involution MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 3 On Thu, 1 Mar 2007, John Baez wrote: > I hope this is clear: "dagger-categories" are completely different > from "compact closed categories". We need *some* term for them; > we're just arguing about whether to call them "star-categories", > "dagger-categories", or "categories with involution". I like > "star-categories", because in analysis and quantum topology the > special case of "C*-categories" is very important. But, I doubt > we'll reach any sort of agreement! You are completely right, of course - but one thing was clear from the start: naming a structure from the notation used is rarely a smart move; instead one should try to capture the essence of the structure in the name. (For that reason, "star-categories" isn't a whole lot better than "dagger-categories", though admittedly, it's hard to think of a worse name! However, "star-categories" is likely to make folks think "dagger = star", and that would be unhelpful. That is probably partially why getting a good name was tricky - after all, "dagger- categories" sounds like the act of a desparate person failing to come up with a good name.) But by now, too many folks are probably unwilling to change (and there isn't really an obvious better name anyway), and their collegues and students will probably follow suit, making a name revision even less likely. Pity though ... -= rags =- -- From rrosebru@mta.ca Sat Mar 3 14:25:59 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 03 Mar 2007 14:25:59 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HNYkb-0006Zb-SD for categories-list@mta.ca; Sat, 03 Mar 2007 14:14:33 -0400 Date: Fri, 02 Mar 2007 18:52:43 -0800 From: Dusko Pavlovic MIME-Version: 1.0 To: categories Subject: categories: Re: dagger and involution Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 4 deciding whether the involution on a category should be written as a dagger or as a star sounds to me a bit like deciding whether a polynomial should be in x or in y. i worked with people who use the dagger, and didnt work with people who use the star, but it would be good if i could keep my options open. but anyway, denoting the math structures by the typographic symbols used in them sounds like an amusing idea. after a hundred years of progress in creating new structures, and metafonting new symbols for them, we'll probably be in possession of a fairly rich new language of hieroglyphs. -- dusko John Baez wrote: > [snip] > >I hope this is clear: "dagger-categories" are completely different >from "compact closed categories". We need *some* term for them; >we're just arguing about whether to call them "star-categories", >"dagger-categories", or "categories with involution". I like >"star-categories", because in analysis and quantum topology the >special case of "C*-categories" is very important. But, I doubt >we'll reach any sort of agreement! > >Best, >jb > > > > > From rrosebru@mta.ca Sat Mar 3 14:25:59 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 03 Mar 2007 14:25:59 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HNYlT-0006dQ-SD for categories-list@mta.ca; Sat, 03 Mar 2007 14:15:28 -0400 Subject: categories: Re: terminology: dagger and involution Date: Sat, 3 Mar 2007 01:15:45 -0400 (AST) To: categories@mta.ca (categories) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit From: selinger@mathstat.dal.ca (Peter Selinger) Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 5 Hi Marco and John, thanks for your comments. Although I am not sure how many people this will interest, I should probably try to defend my choice of terminology. I originally invented the term "dagger category" because I was looking for a flexible term that could be used both as an adjective and an adverb. I wanted a term that could be applied not just to categories, but also to many other categorical notions ("dagger categories", "dagger functor", "dagger biproducts", "dagger subobject", "dagger idempotent", "to dagger-split" etc). Abramsky and Coecke had used the term "strongly compact closed category", but "strongly" couldn't be applied in most of these contexts. If I had known about Burgin's erstwhile term "involutive category", I would have probably used it. As it is, I have now been publicly using the term "dagger categories" for over two years, including on this list (first 8 Jun 2005), and the terminology has not drawn any criticism until now (except from John Baez, see below). By now, the term has found its way into published papers, and other have picked it up. So, as John has already pointed out, the proverbial genie has left the bottle. Despite due respect for historical terminology, I have to say that I don't much like the term "involutive category". Most importantly, this leaves no good terminology for categories with an involution that is not identity-on-objects, or not contravariant. I don't much like terminologies that use the name "A" to mean "has properties A, B, and C", just because the first example someone studied happened to have those additional properties. Also, a functor between involutive categories cannot be called an "involutive functor" for obvious reasons. Similarly, one cannot say "involutive idempotent", "involutive biproduct", etc. I think the "dagger" terminology is elegant. As John Baez has pointed out, the term "star category" has ample precedent, and indeed, this shares all the useful grammatical properties of "dagger category". Aside from the fact that star categories are often assumed to satisfy additional properties, the two terminologies are equivalent to each other. The difference comes about because mathematicians write "f^*" for the adjoint of a linear map, whereas physicists write "f^\dagger". So why am I siding with the physicists? The choice was forced by the fact that category theorists have long ago decided to write f^* : B^* -> A^* for the transpose of a linear map f : A -> B (in compact closed categories). This is good notation, because functors should be written the same way on objects as on morphisms. However, this makes it impossible to also write f^* for the adjoint B -> A. So one has no choice but to use f^\dagger : B -> A. The difference between the transpose f^* : B^* -> A^* and the adjoint f^\dagger : B -> A is probably the single most common source of confusion about Hilbert spaces for category theorists and others. Both functors are contravariant, and they have little else in common. Sticking to the term "*-category" would have compounded these problems. Fortunately, the symbol $\dagger$ doesn't already have other meanings in related contexts. So its adoption, at least, should not contradict existing terminology. It is better to have two names for one concept than to have one name for two different concepts. Moreover, since $\dagger$ is only a symbol, and not a dictionary word, there is nothing that prevents it from being pronounced differently by different people. I propose that $\dagger$ can be pronounced (and even translated) as "involutive" by those who prefer to do so. This way, time-honored terminology can be used without a change of notation. -- Peter John Baez wrote: > > On Thu, Mar 01, 2007 at 09:21:55AM +0000, V. Schmitt wrote: > > > John Baez wrote: > > > >by now there's enough literature using the term "dagger-categories" > > >that the genie is out of the bottle. > > > Dear John, just my view: this is not a good argument. > > It's not an argument - I'm just reporting on what I see. > > I don't really like the term "dagger-categories", and I gently > tried to get people to stop using it, but it didn't work. They're > already comfortable with it. > > > I do not know about these dagger categories though > > i read about the compact closed ones. > > So may be I miss the point but, if this is the case, why > > introducing a new terminology if the concepts are not? > > That just creates confusion. > > I hope this is clear: "dagger-categories" are completely different > from "compact closed categories". We need *some* term for them; > we're just arguing about whether to call them "star-categories", > "dagger-categories", or "categories with involution". I like > "star-categories", because in analysis and quantum topology the > special case of "C*-categories" is very important. But, I doubt > we'll reach any sort of agreement! > > Best, > jb > > > From rrosebru@mta.ca Mon Mar 5 15:44:16 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 05 Mar 2007 15:44:16 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HOIwr-0002Lc-7G for categories-list@mta.ca; Mon, 05 Mar 2007 15:34:17 -0400 Date: Mon, 05 Mar 2007 13:14:51 +0100 From: Aldo Ursini Subject: categories: Workshop (Dedicated to J-Y. Girard) To: categories@mta.ca Message-id: <01MDV0AM2OU295NKXA@mailsrv.unisi.it> MIME-version: 1.0 Content-type: text/plain; charset="us-ascii"; format=flowed Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 6 >>Workshop on >>Linear Logic, Ludics, Implicit Complexity and Operator Algebras. >>Dedicated to Jean-Yves Girard on his 60th birthday. >> >>University of Siena (Italy) at the Certosa di Pontignano, May 17-20, >>2007. >> >> >>www.unisi.it/eventi/LOGIC NEW: the deadline for contributed papers (extended abstract) submission is updated to MARCH 18, 2007. **************************************************************************** INVITED SPEAKERS: Patrick Baillot, Univ. Paris 13, http://www-lipn.univ-paris13.fr/~baillot/ Pierre-Louis Curien, Univ. Paris 7, www.pps.jussieu.fr/~curien/ Ugo Dal Lago, Univ. Bologna, www.cs.unibo.it/~dallago/ Claudia Faggian, Univ. Paris 7, www.math.unipd.it/~claudia/ Jean-Yves Girard, Univ. Marseille, http://iml.univ-mrs.fr/~girard/ Paul-Andre Mellies, Univ. Paris 7, www.pps.jussieu.fr/~mellies/ Michele Pagani, Univ. Roma 3, http://logica.uniroma3.it/~pagani/ Laurent Regnier, Univ. Marseille, http://iml.univ-mrs.fr/~regnier/ Kazushige Terui, National Institute of Informatics, Tokyo , http://research.nii.ac.jp/~terui/ Prof. Aldo Ursini, Dipartimento di Scienze Matematiche ed Informatiche "Roberto Magari", Universita' di Siena, Pian dei Mantellini 44 53100 SIENA, Italy tel.(+39) 0577 233754 fax(+39) 0577 233701 e-mail: ursini at unisi dot it From rrosebru@mta.ca Mon Mar 5 15:44:16 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 05 Mar 2007 15:44:16 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HOIw0-0002Eb-3u for categories-list@mta.ca; Mon, 05 Mar 2007 15:33:24 -0400 Date: Sun, 4 Mar 2007 13:49:40 -0500 From: "Zinovy Diskin" To: categories Subject: categories: Re: dagger and involution MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Content-Disposition: inline Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 7 On 3/2/07, Robert Seely wrote: > > > But by now, too many folks are probably unwilling to change (and there > isn't really an obvious better name anyway), and their collegues and > students will probably follow suit, making a name revision even less > likely. Pity though ... synonyms (and even homonyms) are widely spread in natural languages simply because they are convenient. In reasonable doses they could be useful in math too. It would be worse if their use were implicit but if daggerists and involutists know that they speak about the same thing, then why not? I do not want to say that both terms are equally good, or equally bad... what I'm trying to say is that so far we simply do not know. It will be seen later whether the community will prefer one over the other, or will continue to use both... Language is normally regulated by usage rather than by directives. The current discussion is quite useful if it is about usage, but I'm afraid that it would be less useful if it takes the modality of prescribing one and proscribing the other. --zd From rrosebru@mta.ca Mon Mar 5 15:44:16 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 05 Mar 2007 15:44:16 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HOIxJ-0002ON-J6 for categories-list@mta.ca; Mon, 05 Mar 2007 15:34:45 -0400 Date: Mon, 5 Mar 2007 07:38:35 -0500 From: tholen@mathstat.yorku.ca To: categories@mta.ca Subject: categories: dagger vs involutive MIME-Version: 1.0 Content-Type: text/plain;charset=ISO-8859-1;format="flowed" Content-Disposition: inline Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 8 Here is an outsider's view on the debate which is all about a formalistic (not to say meaningless) vs a meaningful name. There seem to be only very few occasions in mathematics when the formalistic name won, C*-algebras being a prominent example. In category theory, one is reminded of the hot debate of triples vs monads of the 60s and 70s. I guess that at the time of the "Zurich triple book" (SLNM 80) most people would have predicted that triples had already won the race. Mac Lane's book CWM appeared only 2 or 3 years later, after a vast amount of literature on triples. But he consistently used the meaningful name monad, even though (as far as I know) he had never directly published on the subject. You be the judge who won! Walter Tholen. From rrosebru@mta.ca Mon Mar 5 22:05:45 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 05 Mar 2007 22:05:45 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HOOxa-0000Qf-MZ for categories-list@mta.ca; Mon, 05 Mar 2007 21:59:26 -0400 Subject: categories: Re: dagger vs involutive From: Eduardo Dubuc Date: Mon, 5 Mar 2007 19:19:05 -0300 (ART) To: categories@mta.ca MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 9 > > In category theory, one is > reminded of the hot debate of triples vs monads of the 60s and 70s. I > guess that at the time of the "Zurich triple book" (SLNM 80) most > people would have predicted that triples had already won the race. Mac > Lane's book CWM appeared only 2 or 3 years later, after a vast amount > of literature on triples. But he consistently used the meaningful name > monad, even though (as far as I know) he had never directly published > on the subject. You be the judge who won! > > Walter Tholen. > "after a vast amount of literature on triples" you should recall that also after a vast amount of literature on monads e.d. From rrosebru@mta.ca Mon Mar 5 22:05:45 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 05 Mar 2007 22:05:45 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HOOyg-0000WA-4j for categories-list@mta.ca; Mon, 05 Mar 2007 22:00:34 -0400 Date: Mon, 5 Mar 2007 16:58:31 -0600 From: Peter May To: cat-dist@mta.ca Subject: categories: Mac Lane Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 10 I do hope monads won! But I thought I'd share the story of that. At the same time Saunders was writing CWM, I was introducing operads. I coined that word as a portmanteau (look up Lewis Carrol) of operations and monads, and I persuaded Saunders to switch from triple to monad to go along. He was not an easy man to persuade. Peter May From rrosebru@mta.ca Mon Mar 5 22:05:45 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 05 Mar 2007 22:05:45 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HOOzn-0000ax-Bj for categories-list@mta.ca; Mon, 05 Mar 2007 22:01:43 -0400 From: "Philip Mulry" To: Subject: categories: FMCS 2007 - Call for Participation Date: Mon, 5 Mar 2007 15:58:40 -0500 MIME-Version: 1.0 Content-Type: text/plain;charset="iso-8859-1" Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 11 First Announcement FMCS 2007 Hamilton, N.Y. June 8 - 10, 2007 Local Organizer: Philip Mulry Foundational Methods in Computer Science 2007 will be held on the campus of Colgate University in Hamilton N.Y. Dates: Arrival on Thursday June 7, 2007 (Reception in the evening). Scientific Program Friday June 8 - Sunday June 10 (ends mid-day). The workshop is an annual meeting meant to bring together researchers in mathematics and computer science with a focus on the application of category theory in computer science. The meeting will begin with a day of research tutorials, followed by a day and a half of research talks. Graduate student participation is particularly encouraged at FMCS 2007. Further details on the meeting can be found at: http://cs.colgate.edu/faculty/mulry/FMCS2007/FMCS2007.html If you are interested in attending or giving a talk, you can send an email to fmcs2007@cs.colgate.edu From rrosebru@mta.ca Mon Mar 5 22:05:45 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 05 Mar 2007 22:05:45 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HOOyA-0000Tc-R9 for categories-list@mta.ca; Mon, 05 Mar 2007 22:00:02 -0400 Date: Mon, 5 Mar 2007 23:06:10 +0000 (GMT) From: "Prof. Peter Johnstone" To: categories@mta.ca Subject: categories: Re: dagger vs involutive MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 12 Walter is of course quite right about triples vs. monads. But it is interesting to compare that with the truly awful example of the term "comma category" (and of course the 2-categorical notion of "comma object" which it has spawned). The awfulness derives from the fact that the term is derived not just from a particular notation, but from an obsolete notation (Mac Lane, for example, despite his sterling efforts to kill off "triple", uses the term "comma category" in his book, even though his notation for it doesn't involve a comma). How is it that we have never managed to find a more descriptive name for this concept? While I'm on the subject, does anyone out there know who invented the terms "pullback" and "pushout"? They have always seemed to me to be splendid examples of descriptive terminology, but I've never seen them attributed to a particular person. (And yes, I know that Peter Freyd invented "Doolittle diagram"; but that joke wouldn't have been possible if "pullback" and "pushout" hadn't already been established terminology.) Peter Johnstone On Mon, 5 Mar 2007 tholen@mathstat.yorku.ca wrote: > Here is an outsider's view on the debate which is all about a > formalistic (not to say meaningless) vs a meaningful name. There seem > to be only very few occasions in mathematics when the formalistic name > won, C*-algebras being a prominent example. In category theory, one is > reminded of the hot debate of triples vs monads of the 60s and 70s. I > guess that at the time of the "Zurich triple book" (SLNM 80) most > people would have predicted that triples had already won the race. Mac > Lane's book CWM appeared only 2 or 3 years later, after a vast amount > of literature on triples. But he consistently used the meaningful name > monad, even though (as far as I know) he had never directly published > on the subject. You be the judge who won! > > Walter Tholen. > > > From rrosebru@mta.ca Tue Mar 6 21:39:55 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 06 Mar 2007 21:39:55 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HOkyi-0001Td-SM for categories-list@mta.ca; Tue, 06 Mar 2007 21:30:04 -0400 Date: Tue, 6 Mar 2007 17:55:29 -0600 From: Peter May To: categories@mta.ca Subject: categories: Details Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 13 1971, not 1982, was when operads were defined. Certainly I did not know multicategories, but they only correspond to non-sigma operads, operads without permutations, and I would not have bothered inventing a word just for them. Precisely, multicategories are the many object version of non-sigma operads. The point is that the applications for which operads were invented depend vitally on the permutations. Peter May From rrosebru@mta.ca Tue Mar 6 21:39:55 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 06 Mar 2007 21:39:55 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HOkvt-0001GY-De for categories-list@mta.ca; Tue, 06 Mar 2007 21:27:09 -0400 Mime-Version: 1.0 (Apple Message framework v752.2) Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed Content-Transfer-Encoding: 7bit From: Marco Grandis Subject: categories: meaningful and formalistic names Date: Tue, 6 Mar 2007 11:05:23 +0100 To: categories@mta.ca Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 14 Dear colleagues, I apologise for commenting a third time on this point. I think I can suggest a solution which could solve most of the problems mentioned in this line (not all of them), and can be used in various similar situations. We have a meaningful name for a concept, say involutive category (or category with involution). This term is even well established in category theory (see (*) below). Its main drawback is that the attribute "involutive" is not as flexible as we would like it to be, in order to develop a theory of such things: an involution-preserving functor cannot be called an "involutive functor", as Peter Selinger points out; and so on. On the other hand, typographical prefixes, like dagger or star, are already used in the same sense. They are flexible (you can say dagger category, dagger functor, and so on) and their authors do not want to give up the terminology of their previous works. Their big drawback - even forgetting about the fact that "category with involution" is an old, well established term - is that, being meaningless (or formalistic, as Walter Tholen prefers to say), nobody would search for them unless (s)he is already aware of this use. Thus, papers using such a terminology are often confined to some restricted domain; and this terminology will be reinvented again and again, with other acronyms or typographical signs. The solution I suggest: One can call such structures with a double name, a meaningful (possibly well established) name and a flexible one. In the present case this might be: - involutive categories (say), alias "prefix"-categories, - involution-preserving functors (say), alias "prefix"-functors, where "prefix" stays for the letter or acronym or typographical sign preferred by the author. In a title one would only use the meaningful terms, which can be easily retrieved in a search. In the body of a paper, one would use both terminologies in the main definitions and the short, adaptable prefix most of the time. --- (*) Searching in MathSciNet, under "Anywhere", I find: - category with involution: 41 items, starting with 1969 - involutive category: 5 items - dagger category: 0 items (including variants, like $\dagger$-category - star category: 1 item (all variants I can think of give the same item) (Of course, various dagger- or star- papers might be not yet on MathSciNet.) With best regards Marco Grandis From rrosebru@mta.ca Tue Mar 6 21:39:55 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 06 Mar 2007 21:39:55 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HOkxh-0001OS-0E for categories-list@mta.ca; Tue, 06 Mar 2007 21:29:01 -0400 Date: Tue, 6 Mar 2007 14:37:30 -0500 From: "Zinovy Diskin" To: categories@mta.ca Subject: categories: Re: dagger vs involutive MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Content-Disposition: inline Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 15 On 3/5/07, tholen@mathstat.yorku.ca wrote: > > Here is an outsider's view on the debate which is all about a > formalistic (not to say meaningless) vs a meaningful name. There seem > to be only very few occasions in mathematics when the formalistic name > won, C*-algebras being a prominent example. In category theory, one is why only few? Recall the Poisson bracket, or Dirac's delta-function, or quaternions (though as a shorthand for 4D complex number it's probably more meaningful than triples) or, say, derivative, which is a basic notion in calculus yet is, in fact, quite a formalistic name. If to talk about general tendencies, then it seems the winner would be a formalistic term (unfortunately). Consider a competition between a meaningful yet too long, or hard to pronounce, or not smooth in some sense term and a meaningless yet short and energetic term, who would win? Many attempts to make terminology and notation in a particular domain entirely consistent failed as soon as they went beyond some reasonable level of consistency. Zinovy Diskin And aren't left-right adjoints, vertical-horizontal morphisms in fibrations of purely typographical ("blackboardial") origin? reminded of the hot debate of triples vs monads of the 60s and 70s. I > guess that at the time of the "Zurich triple book" (SLNM 80) most > people would have predicted that triples had already won the race. Mac > Lane's book CWM appeared only 2 or 3 years later, after a vast amount > of literature on triples. But he consistently used the meaningful name > monad, even though (as far as I know) he had never directly published > on the subject. You be the judge who won! > > Walter Tholen. > > > From rrosebru@mta.ca Tue Mar 6 21:39:56 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 06 Mar 2007 21:39:56 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HOkzB-0001W0-E6 for categories-list@mta.ca; Tue, 06 Mar 2007 21:30:33 -0400 Date: Tue, 06 Mar 2007 17:11:31 -0800 From: David Karapetyan MIME-Version: 1.0 To: categories@mta.ca Subject: categories: monic epics Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 16 Hi, I've been trying to learn some category theory and I came upon the example of a monic, epic in the category of monoids given by the inclusion function of (N,0,+) into (Z,0,+). I know that in monoids every monic arrow is also an injective function but the inclusion function of N into Z provides a counterexample of every epic arrow being a surjective function. I noticed that N is just a "folded" version of Z, where by "folded" I mean take Z and throw away all the inverses of the natural numbers. So does every monic, epic arrow determine such a "folding" or are there monic, epics that can't be characterized in such a way? From rrosebru@mta.ca Tue Mar 6 21:39:56 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 06 Mar 2007 21:39:56 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HOkzh-0001Yi-VR for categories-list@mta.ca; Tue, 06 Mar 2007 21:31:06 -0400 From: Juergen Koslowski Subject: categories: more dagger problems To: categories@mta.ca Date: Wed, 7 Mar 2007 02:21:22 +0100 (CET) MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: quoted-printable Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 17 Besides their funny name, dagger-compact categories present, or rather expose, another terminological dilemma: what's an adjoint? Although the notion of dagger-compact category (dcc) was originally defined for symmetric monoidal categories, let's try to makes sense of it without symmetry. In fact, this should work in a (linear) bicategory or even a poly-bicategory. - The dagger operation flips 2-cells vertically (in view of the picture calculus). f^{\dagger} is called the ``adjoint'' of f, which matches the terminology of functional analysis and physics. In case of a linear bicategory, the two 1-cell compositions \tensor for the domain 1-cells and \par for the codomain 1-cells get interchanged as well. - The definition of a dcc also calls for ``duals'' A^* of 1-cells, which in graphical terms flips 1-cells horizontally.=20 - Finally, there are``units'' (or ``Bell states'' in physics terms)=20 \eta_A: I_Y =3D=3D> A^*\tensor A, when A:X --> Y. The axioms for a symmetric dcc turn the ``duals'' turn into categorical adjoints with unit \eta_A and counit (\eta_A)^{\dagger} (the ``adjoint'' of the unit). This seems to require symmetry, but it really does not. The correct interpretation of A^* should be that of a 2-sided (categorical) adjoint for A (linear adjoint in the case of poly-bicategories), i.e., A^* -| A -| A^*. Hence there are 2 categorical adjunctions and hence 2 units, besides \eta_A also \eta_A^*: I_X =3D=3D> A\tensor A^*. Without symmetry (\eta_A)^{\dagger} cannot be the counit for the adjunction A^* -| A, but for the other adjunction A -| A^*. Unfortunately, the functional analysis terminology would refer to the counit of the second adjunction as the adjoint of the first adjunction's unit, which I find rather confusing. This bicategorical view also clarifies that the star operation is an involution on 1-cells, while dagger is an involution on 2-cells. While the name ``{1,2}-involutive bicategory'' may be adequate, ``{1,2}-involutive monoidal category'' is quite a mouthful. I seem to recall reading not too long ago that Kahn did _not_ pursue an (often rumoured) analogy with functional analysis when introducing (categorical) adjunctions, and here we see the actual mismatch. -- J=FCrgen --=20 Juergen Koslowski If I don't see you no more on this world ITI, TU Braunschweig I'll meet you on the next one koslowj@iti.cs.tu-bs.de and don't be late! http://www.iti.cs.tu-bs.de/~koslowj Jimi Hendrix (Voodoo Child, SR) From rrosebru@mta.ca Tue Mar 6 21:39:56 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 06 Mar 2007 21:39:56 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HOky9-0001R5-Pv for categories-list@mta.ca; Tue, 06 Mar 2007 21:29:30 -0400 From: Peter Freyd Date: Tue, 06 Mar 2007 17:12:31 -0500 To: categories@mta.ca Subject: categories: the term "pushout" MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 18 Peter Johnstone asks who coined the term "pushout". On page 156 of Abelian Categories I wrote (43 years ago!): The word "pullback" and the ubiquity of the concept I learned from Lang, who also pointed out the pullback theorem and its importance. I plead guilty to "pushout"... (www.tac.mta.ca/tac/reprints/articles/3/tr3abs.html) MathSciNet lists Alex Heller's review of Abelian Categories as its second oldest use of the term "pullback" and its oldest use of "pushout". (Its first use of "pullback" is in Alex's review of John Gray's 1962 paper "Category-valued sheaves" -- no the stalks were not categoies.) It was my impression that Serge Lang invented the term "pullback" (his term for the dual notion was "co-pullback"). Note that I refrained from stating this impression. But I do claim to have invented the term "pushout" -- indeed, I've been know to cite this as my most visible contribution to mathematics. From rrosebru@mta.ca Wed Mar 7 13:54:29 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 07 Mar 2007 13:54:29 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HP0FT-0001IY-6y for categories-list@mta.ca; Wed, 07 Mar 2007 13:48:23 -0400 Date: Tue, 06 Mar 2007 21:09:33 -0500 From: "Fred E.J. Linton" To: Subject: categories: Re: pullback ... Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 19 Greetings! As regards Peter Johnstone's query, = = > ... does anyone out there know who invented the > terms "pullback" and "pushout"? ..., while I can't speak directly to the question of who invented those = terms, I do recall that, in the late '50s already, fiber bundles = were being "pulled back" along maps to their base spaces. And I can = still hear the late Serge Lang, bless his soul, intoning "pooll-back" = and "poosh-out" in his characeristic French accent, in Columbia = courses and seminars from the late '50s and early '60s. So the terms were pretty well established (and pull-back, anyway, = pretty well motivated), at least at Columbia, that early. Cheers, -- Fred From rrosebru@mta.ca Wed Mar 7 13:54:30 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 07 Mar 2007 13:54:30 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HP0HA-0001Tg-FP for categories-list@mta.ca; Wed, 07 Mar 2007 13:50:08 -0400 Mime-Version: 1.0 (Apple Message framework v752.3) Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed Content-Transfer-Encoding: 7bit From: Lawrence Stout Subject: categories: Re: monic epics Date: Tue, 6 Mar 2007 21:41:21 -0600 To: categories@mta.ca Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 20 The Goguen category of L-fuzzy sets on a lattice L (Objects are pairs (A,\alpha) where \alpha:A\to L and morphisms are functions f:A\to B such that \beta{f(a)) >= \alpha(a)) has all functions whose underlying set function is an isomorphism both epic and monic, but not, in general, isomorphisms, which must preserve the lattice valued membership on the nose. Since these monic, epic maps are the ones which give the right subobjects to consider for fuzzy logic they are of interest. They do not determine a "folding" like the one you describe. On Mar 6, 2007, at 7:11 PM, David Karapetyan wrote: > So does every monic, epic arrow determine such a > "folding" or are there monic, epics that can't be characterized in > such > a way? > > Lawrence Stout Professof of Mathematics Illinois Wesleyan University From rrosebru@mta.ca Wed Mar 7 13:54:30 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 07 Mar 2007 13:54:30 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HP0Hp-0001YI-6n for categories-list@mta.ca; Wed, 07 Mar 2007 13:50:49 -0400 Mime-Version: 1.0 (Apple Message framework v752.3) Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed To: categories@mta.ca From: Lawrence Stout Subject: categories: re: dagger? Date: Tue, 6 Mar 2007 21:51:22 -0600 Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 21 I have a sneaking suspicion that dagger categories might be of interest in some work I'm doing, but the term means absolutely nothing to me. Category with involution does have a meaning, which is why I think they might be interesting. Could someone please post a definition of a dagger category and a reference for typical useful examples? For other examples of a notations promoted to the name of a concept: K theory, L functions, p matrices, H spaces (OK, that one is a bit of a cheat, since it comes from the first letter of a name instead of from the arbitrary choice of symbol), \lambda calculus. Lawrence Stout Professof of Mathematics Illinois Wesleyan University From rrosebru@mta.ca Wed Mar 7 13:54:30 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 07 Mar 2007 13:54:30 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HP0GG-0001Na-Tk for categories-list@mta.ca; Wed, 07 Mar 2007 13:49:12 -0400 Date: Tue, 06 Mar 2007 20:06:35 -0700 From: Robin Cockett MIME-Version: 1.0 To: categories@mta.ca Subject: categories: Re: bigger dagger problems Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: quoted-printable Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 22 Ah ... and do the larger dagger problems of a linear dagger bicategory=20 give a sword bicategory? These little daggers are no match for this one! -robin Juergen Koslowski wrote: > In fact, this should work in a (linear) > bicategory or even a poly-bicategory ... > > > -- J=FCrgen > > =20 From rrosebru@mta.ca Wed Mar 7 19:29:32 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 07 Mar 2007 19:29:32 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HP5Xe-0002aE-72 for categories-list@mta.ca; Wed, 07 Mar 2007 19:27:30 -0400 Date: Wed, 7 Mar 2007 07:40:40 -0500 (EST) From: Michael Barr To: categories@mta.ca Subject: categories: Re: monic epics References: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 23 Category theory is too abstract for any such statement to be true (or even make sense). For example, in the category denoted . ---> . (with two objects and one non-identity map), that map is monic and epic for want of any test maps. More concretely, the inclusion of Z into R is both in the category of commtative rings. In fact the following a characterization of monic/epics in commutative rings is this: a subring R \inc S is epic iff every element of of S can be written s = vAw where for some n, v is an n-dimensional row vector, w is an n-dimensional column vector and A is an n x n matrix of elements of S such that the entries of A, vA, and Aw all belong to R. In general, very little can be said about monic/epics. On Tue, 6 Mar 2007, David Karapetyan wrote: > Hi, I've been trying to learn some category theory and I came upon the > example of a monic, epic in the category of monoids given by the > inclusion function of (N,0,+) into (Z,0,+). I know that in monoids every > monic arrow is also an injective function but the inclusion function of > N into Z provides a counterexample of every epic arrow being a > surjective function. I noticed that N is just a "folded" version of Z, > where by "folded" I mean take Z and throw away all the inverses of the > natural numbers. So does every monic, epic arrow determine such a > "folding" or are there monic, epics that can't be characterized in such > a way? > > -- Any society that would give up a little liberty to gain a little security will deserve neither and lose both. Benjamin Franklin From rrosebru@mta.ca Wed Mar 7 19:29:32 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 07 Mar 2007 19:29:32 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HP5YR-0002zt-Rw for categories-list@mta.ca; Wed, 07 Mar 2007 19:28:20 -0400 Date: Wed, 7 Mar 2007 15:13:58 +0000 (GMT) From: Paul B Levy To: categories@mta.ca Subject: categories: Re: dagger vs involutive MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 24 Oh dear, I think I might have recently increased the set of synonyms. A couple of years ago, in conversation with Weng Kin Ho, I suggested the following terminology. Involutive category: a category C, with a functor c : C^op --> C and an isomorphism alpha : c^2 --> id_C Strictly involutive category: a category C with a functor c : C^op --> C such that c^2 = id_C Locally involutive category: a category C with an identity-on-objects functor c : C^op --> C such that c^2 = id_C. Weng Kin used this terminology in his PhD thesis (pp 17-18) http://www.cs.bham.ac.uk/~wkh/papers/thesis.pdf I wasn't aware of the other terminologies. Paul From rrosebru@mta.ca Wed Mar 7 19:29:32 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 07 Mar 2007 19:29:32 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HP5X0-0002Bu-L9 for categories-list@mta.ca; Wed, 07 Mar 2007 19:26:51 -0400 Date: Wed, 07 Mar 2007 11:47:06 +0000 From: Steve Vickers MIME-Version: 1.0 To: categories@mta.ca Subject: categories: Re: monic epics Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 25 Dear David, There are more complicated examples. Here's one. Take A to be the semigroup {0,a,b,c} in which x0=0x=0 for all x, aa=a, cc=c, ab = bc = b, and all other products are 0. (This of this as being derived from a category with two objects and three morphisms, so a and c represent the two identities and b is a morphism between the two objects. 0 takes care of products of non-composable pairs.) Take B = A u {d}, with cd = da = d, bd=a, db=c and all other binary products involving d give 0. (Think of adjoining an inverse to b in the category.) Now the inclusion A -> B is a semigroup epi. To see this, suppose f: A -> C is a semigroup homomorphism, and x in C satisfies xf(a) = f(c)x = x f(b)x = f(a) xf(b) = f(c) Then x is the unique such. For if x' is another then x' = x'f(a) = x'f(b)x = f(c)x = x If g: B -> C is a semigroup homomorphism agreeing with f on A, then g(d) does satisfy those equations for x, and so any two such g's must be equal. This semigroup example can be easily turned into monoids by adjoining a unit element. There is still the same idea that B is got by adjoining inverses to elements of A, but they are not inverses in the monoid sense and it is not clear to me in general how one would formalize the idea that they are inverses when embedded in some category. There is a related epi in rings: the inclusion of upper triangular 2x2 matrices (over any ring) into all 2x2 matrices. Regards, Steve Vickers. David Karapetyan wrote: > Hi, I've been trying to learn some category theory and I came upon the > example of a monic, epic in the category of monoids given by the > inclusion function of (N,0,+) into (Z,0,+). I know that in monoids every > monic arrow is also an injective function but the inclusion function of > N into Z provides a counterexample of every epic arrow being a > surjective function. I noticed that N is just a "folded" version of Z, > where by "folded" I mean take Z and throw away all the inverses of the > natural numbers. So does every monic, epic arrow determine such a > "folding" or are there monic, epics that can't be characterized in such > a way? > > From rrosebru@mta.ca Wed Mar 7 19:29:32 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 07 Mar 2007 19:29:32 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HP5VJ-0001OC-FZ for categories-list@mta.ca; Wed, 07 Mar 2007 19:25:05 -0400 Date: Tue, 6 Mar 2007 21:30:06 -0800 (PST) Message-Id: <200703070530.l275U6ak000843@melipona.ucdavis.edu> Subject: categories: Re: monic epics From: "David Karapetyan" To: categories@mta.ca Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: X-Keywords: X-UID: 26 > Yes. Another common example of a morphism that is both a monomorphis and > an > epimorphism but not an isomorphism is the inclusion of the rational > numbers > into the real numbers in the category of topological spaces. i understand that such arrows exist and i'm trying to get an intuitive feel for why they are epic. one way i think of a surjective function is that it is a map that entirely covers the codomain so any two function that agree on all of the codomain must be the same. it is not the case with epic arrows that they cover the entire codomain as set functions but that is i think because most categories are much more structured than the category of sets so it is enough to cover certain parts of the codomain and the rest of the structure can be recovered. i think that is what happens with the inclusion of the rationals into the reals because the reals are defined as equivalence classes of sequences of rationals so if two functions agree on the rationals and they are continuous then they automatically agree on the reals. From rrosebru@mta.ca Wed Mar 7 19:29:32 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 07 Mar 2007 19:29:32 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HP5UF-0000Kl-5L for categories-list@mta.ca; Wed, 07 Mar 2007 19:23:59 -0400 Date: Tue, 6 Mar 2007 20:44:58 -0800 From: John Baez To: categories Subject: categories: more dagger problems Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 27 Juergen Koslowski wrote: >This bicategorical view also clarifies that the star operation is an >involution on 1-cells, while dagger is an involution on 2-cells. >While the name ``{1,2}-involutive bicategory'' may be adequate, >``{1,2}-involutive monoidal category'' is quite a mouthful. I call them "monoidal categories with duals". If you only have your "star", I often call them "monoidal categories with duals for objects". If you only have your "dagger", I often call them "monoidal categories with duals for morphisms". They're a special case of a fascinating notion, "k-tuply monoidal n-categories with duals", which so far only been precisely defined for low values of n and k. The "tangle hypothesis" proposes a nice topological description of the free k-tuply monoidal n-category with duals on one object. Here are some places to read about this stuff: John Baez and James Dolan, Higher-dimensional algebra and topological quantum field theory, http://arxiv.org/abs/q-alg/9503002 John Baez and Laurel Langford, Higher-dimensional algebra IV: 2-Tangles, http://arxiv.org/abs/math.QA/9811139 John Baez, Quantum computation and symmetric monoidal categories, http://golem.ph.utexas.edu/category/2006/08/quantum_computation_and_symmet.html One can also listen to lectures: Eugenia Cheng, n-categories with duals and TQFT, http://www.fields.utoronto.ca/audio/#crs-ncategories The cases that have been precisely defined include: n = 1, k = 0 categories with duals n = 1, k = 1 monoidal categories with duals n = 1, k = 2 braided monoidal categories with duals n = 1, k = 3 symmetric monoidal categories with duals n = 2, k = 0 weak 2-categories with duals n = 2, k = 1 semistrict monoidal 2-categories with duals n = 2, k = 2 semistrict braided monoidal 2-categories with duals Here "weak 2-categories" means "bicategories" and "semistrict monoidal 2-categories" means "one-object Gray-categories". For n = 1 we have up to 2 layers of duality (your "stars" and "daggers"), while for n = 2 we have up to 3. Best, jb From rrosebru@mta.ca Wed Mar 7 19:30:47 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 07 Mar 2007 19:30:47 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HP5a4-0003nM-S3 for categories-list@mta.ca; Wed, 07 Mar 2007 19:30:01 -0400 Date: Wed, 7 Mar 2007 13:45:56 -0500 (EST) Subject: categories: Re: epic monics From: Flinton@wesleyan.edu To: categories@mta.ca MIME-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: 8bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 28 For David Karapetyan, who asked, > ... the inclusion function of > N into Z provides a counterexample [to] every epic arrow being a > surjective function. I noticed that N is just a "folded" version of Z, > where by "folded" I mean take Z and throw away all the inverses of the > natural numbers. So does every monic, epic arrow determine such a > "folding" or are there monic, epics that can't be characterized in such > a way? let me offer two further examples of monic epic arrows, not surjective (and both pretty standard): 1) in Hausdorff topological spaces, the inclusion of the rationals in the reals; 2) in boolean rngs (i.e., units not required, and not necessarily preserved when present) with countable intersections, and boolean homomorphisms preserving those intersections, the inclusion of the boolean rng of finite subsets of N in the whole power-set of N (this is epic because boolean homomorphisms (between such boolean rngs) that preserve countable intersections will also preserve whatever countable joins may be available, and every subset of N is the join of all its finite subsets). Does your "folding" insight still stand up? Or must it be modified? -- Fred Linton From rrosebru@mta.ca Wed Mar 7 19:31:37 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 07 Mar 2007 19:31:37 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HP5ao-0004D2-N3 for categories-list@mta.ca; Wed, 07 Mar 2007 19:30:47 -0400 To: categories@mta.ca Subject: categories: Assoc. Professorship Opening From: Lars Birkedal Date: Wed, 07 Mar 2007 20:31:08 +0100 MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 29 Associate Professorship in Programming, Logic and Semantics at the IT University of Copenhagen, Denmark. The IT University of Copenhagen invites applications for a position as Associate Professor in the Programming, Logic, and Semantics Group. The position is available from August 2007. The Programming, Logic and Semantics (PLS) group at the IT University of Copenhagen conducts research in semantics of logics and programming languages; models for concurrent, mobile and distributed systems; logical frameworks, modular software verification; programming language implementation techniques; program analysis; and programming language technology for distributed and mobile applications, in particular for context-aware mobile computing. The successful candidate must document internationally recognized research in the research areas of the PLS group. Moreover, the applicant should be willing and able to teach in a wide variety of courses at all levels. Please see http://www1.itu.dk/sw58262.asp for the full official announcement. Application deadline is April 16, 2007. Best wishes, Lars Birkedal From rrosebru@mta.ca Wed Mar 7 19:33:14 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 07 Mar 2007 19:33:14 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HP5cP-0004lT-Ba for categories-list@mta.ca; Wed, 07 Mar 2007 19:32:25 -0400 Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: 8bit From: "Dr. Cyrus F Nourani" To: Subject: categories: Re: pullback ... Date: Wed, 07 Mar 2007 15:18:56 -0500 (EST) MIME-Version: 1.0 Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 30 Hello, there might be references on a paper I had written with
late Prof. Joseph Goguen U California and Oxford on that subject,
UCLA 1978.
When was that invented?
Cyrus







---------[ Received Mail Content ]----------

Subject : categories: Re: pullback ...

Date : Tue, 06 Mar 2007 21:09:33 -0500

From : "Fred E.J. Linton" <fejlinton@usa.net>

To : <categories@mta.ca>



Greetings!



As regards Peter Johnstone's query,



> ... does anyone out there know who invented the

> terms "pullback" and "pushout"? ...,



while I can't speak directly to the question of who invented those

terms, I do recall that, in the late '50s already, fiber bundles

were being "pulled back" along maps to their base spaces. And I can

still hear the late Serge Lang, bless his soul, intoning "pooll-back"

and "poosh-out" in his characeristic French accent, in Columbia

courses and seminars from the late '50s and early '60s.



So the terms were pretty well established (and pull-back, anyway,

pretty well motivated), at least at Columbia, that early.



Cheers,



-- Fred From rrosebru@mta.ca Wed Mar 7 19:34:13 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 07 Mar 2007 19:34:13 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HP5dK-0005aa-QK for categories-list@mta.ca; Wed, 07 Mar 2007 19:33:23 -0400 Date: Wed, 07 Mar 2007 12:23:25 -0800 From: David Karapetyan MIME-Version: 1.0 To: categories@mta.ca Subject: categories: Re: monic epics Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 31 Steve Vickers wrote: > Dear David, > > There are more complicated examples. Here's one. > > Take A to be the semigroup {0,a,b,c} in which x0=0x=0 for all x, aa=a, > cc=c, ab = bc = b, and all other products are 0. (This of this as > being derived from a category with two objects and three morphisms, so > a and c represent the two identities and b is a morphism between the > two objects. 0 takes care of products of non-composable pairs.) > > Take B = A u {d}, with cd = da = d, bd=a, db=c and all other binary > products involving d give 0. (Think of adjoining an inverse to b in > the category.) > > Now the inclusion A -> B is a semigroup epi. To see this, suppose f: A > -> C is a semigroup homomorphism, and x in C satisfies > > xf(a) = f(c)x = x > f(b)x = f(a) > xf(b) = f(c) > > Then x is the unique such. For if x' is another then > > x' = x'f(a) = x'f(b)x = f(c)x = x > > If g: B -> C is a semigroup homomorphism agreeing with f on A, then > g(d) does satisfy those equations for x, and so any two such g's must > be equal. > > This semigroup example can be easily turned into monoids by adjoining > a unit element. > > There is still the same idea that B is got by adjoining inverses to > elements of A, but they are not inverses in the monoid sense and it is > not clear to me in general how one would formalize the idea that they > are inverses when embedded in some category. > > There is a related epi in rings: the inclusion of upper triangular 2x2 > matrices (over any ring) into all 2x2 matrices. > > Regards, > > Steve Vickers. > i like the example of the semigroups. i think in some sense the addition of d does not add enough information to our monoid so if we have two semigroup homomorphisms that agree on A then by using the properties of semigroup homomorphisms we are forced to define how they behave on d in only one way. i'm still trying to incorporate the inclusion of the 2x2 upper triangular matrices into all 2x2 matrices and Michael Barr's example into this framework. From rrosebru@mta.ca Wed Mar 7 19:35:23 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 07 Mar 2007 19:35:23 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HP5eV-0006A2-Ol for categories-list@mta.ca; Wed, 07 Mar 2007 19:34:35 -0400 Date: Wed, 07 Mar 2007 12:53:00 -0800 From: David Karapetyan MIME-Version: 1.0 To: categories@mta.ca Subject: categories: Re: monic epics Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 32 Michael Barr wrote: > Category theory is too abstract for any such statement to be true (or > even make sense). For example, in the category denoted . ---> . (with > two objects and one non-identity map), that map is monic and epic for > want of any test maps. More concretely, the inclusion of Z into R is > both in the category of commtative rings. In fact the following a > characterization of monic/epics in commutative rings is this: a > subring R \inc S is epic iff every element of of S can be written s = > vAw where for some n, v is an n-dimensional row vector, w is an > n-dimensional column vector and A is an n x n matrix of elements of S > such that the entries of A, vA, and Aw all belong to R. In general, > very little can be said about monic/epics. > ok i got it. in all the examples given the subobjects given by the monics are "generators" for the object, where by "generators" i mean the elements of the subobject in some way determine the elements of the bigger object. so how about this then: any time we have the situation described above the monic arrow will also be epic. From rrosebru@mta.ca Thu Mar 8 17:01:59 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 08 Mar 2007 17:01:59 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HPPaR-0001uJ-MQ for categories-list@mta.ca; Thu, 08 Mar 2007 16:51:43 -0400 From: "Charles Wells" To: Content-Type: text/plain; charset="ISO-8859-1" MIME-Version: 1.0 Subject: categories: Re: Re: monic epics Date: Thu, 08 Mar 2007 10:13:09 -0500 Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 33 It seems to me that Isbell's notion of "dominions" are something like a precise way of saying "a complete set of generators" for the case of epimorphisms in Cat. Look at "Epimorphisms and Dominions III" by John Isbell, American Journal of Mathematics, 1968. That paper has references to earlier papers about the case for semigroups and other categories. Charles Wells > ok i got it. in all the examples given the subobjects given by the > monics are "generators" for the object, where by "generators" i mean the > elements of the subobject in some way determine the elements of the > bigger object. so how about this then: any time we have the situation > described above the monic arrow will also be epic. > > -- Charles Wells abstract math website: http://www.abstractmath.org/MM//MMIntro.htm professional website: http://www.cwru.edu/artsci/math/wells/home.html personal website: http://www.abstractmath.org/Personal/index.html genealogical website: http://familytreemaker.genealogy.com/users/w/e/l/Charles-Wells/ NE Ohio Sacred Harp website: http://www.abstractmath.org/fasola/index.html From rrosebru@mta.ca Thu Mar 8 17:01:59 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 08 Mar 2007 17:01:59 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HPPbL-00021B-E2 for categories-list@mta.ca; Thu, 08 Mar 2007 16:52:39 -0400 From: "Charles Wells" To: Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="ISO-8859-1" MIME-Version: 1.0 Subject: categories: Addendum re epis in cat Date: Thu, 08 Mar 2007 10:17:53 -0500 Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 34 I just discovered the following paper through Google Scholar: "On Functors which are lax epimorphisms" bu Jiri Adamek, Robert El Bashir, Manuelas Sobral and Jiri Velebril, in Theory and Applications of Categories, Vol. 8, No. 20, 2001, pp. 509=96521. Charles Wells -- Charles Wells abstract math website: http://www.abstractmath.org/MM//MMIntro.htm professional website: http://www.cwru.edu/artsci/math/wells/home.html personal website: http://www.abstractmath.org/Personal/index.html genealogical website: http://familytreemaker.genealogy.com/users/w/e/l/Char= les-Wells/ NE Ohio Sacred Harp website: http://www.abstractmath.org/fasola/index.html From rrosebru@mta.ca Thu Mar 8 17:01:59 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 08 Mar 2007 17:01:59 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HPPcQ-00026Y-JZ for categories-list@mta.ca; Thu, 08 Mar 2007 16:53:46 -0400 Date: Thu, 8 Mar 2007 12:31:00 -0500 (EST) Subject: categories: Final Announcement-Traces Workshop From: rblute@uottawa.ca To: categories@mta.ca MIME-Version: 1.0 Content-Type: text/plain;charset=iso-8859-1 Content-Transfer-Encoding: 8bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 35 This is a final announcement for A Field's Institute Sponsored Workshop, entitled: Applications of traces to algebra, analysis and categorical logic to be held at the University of Ottawa from April 28-30, 2007. It will be hosted by the Ottawa Logic and Foundations of Computing Group. The local organizers are Rick Blute, Pieter Hofstra and Phil Scott. A description of the purpose of the conference is below, and can be found on the conference website http://aix1.uottawa.ca/~scpsg/Fields07/workshop.html . The conference will begin with tutorials, including a minicourse on traced monoidal categories, and an introduction to various notions of trace in functional analysis. We will have the following invited speakers: Samson Abramsky (Oxford) Robin Cockett (Calgary) Andre Joyal (UQAM) Louis Kauffman (Illinois) Claus Koestler (Carleton) Paul-Andre Mellies (Paris7) Matthias Neufang (Carleton) Timothy Porter (Bangor) as well as contributed talks from various researchers, including Rick Blute (Ottawa) Greg Meredith (Oxford) Prakash Panangaden (McGill) Eric Paquette (U.Montreal) Tarmo Uustalu (Tallinn University of Technology) We note the following new information: 1) We have room for a few more contributed talks. Anyone interested should contact the organizers. 2) We have a very small number of rooms on campus still available. These are in the university dorms, but are suites, rather than typical rooms. They are 80 dollars per night, and hold either one or two people. Anyone interested should contact Rick Blute immediately. 3) We ask that anyone attending please notify us by April 10th, so we may order food. Rick Blute, 613-562-5800, ext. 3535 (rblute@mathstat.uottawa) Pieter Hofstra, 613-562-5800, ext. 3494 (phofstra@uottawa.ca) Philip Scott, 613-562-5800, ext. 3502 (phil@site.uottawa.ca) From rrosebru@mta.ca Thu Mar 8 17:01:59 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 08 Mar 2007 17:01:59 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HPPar-0001xU-TS for categories-list@mta.ca; Thu, 08 Mar 2007 16:52:09 -0400 Date: Thu, 8 Mar 2007 15:15:57 +0000 (GMT) From: John Stell To: categories@mta.ca Subject: categories: relations on graphs MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 36 For a set, X, relations on X are equivalent to join-preserving functions on the powerset P(X). If we replace X by a graph, the usual notion of a relation on a graph is a pair of relations one on edges and one on nodes subject to an obvious compatibility condition. However such relations are not as general as the join-preserving functions on the bi-Heyting algebra of subgraphs (consider for example the one node, one edge graph). If we mean relations in this more general sense could there be a notion of converse? (anything for which R** = R, and 1* = 1, and (RS)* = S*R*) Is there any literature which discusses different possible notions for relations on graphs? John Stell From rrosebru@mta.ca Thu Mar 8 17:02:00 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 08 Mar 2007 17:02:00 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HPPjR-0002oI-JW for categories-list@mta.ca; Thu, 08 Mar 2007 17:01:01 -0400 Date: Thu, 08 Mar 2007 13:37:29 -0500 From: michaeln.gurski@yale.edu To: categories@mta.ca Subject: categories: Tricategories MIME-Version: 1.0 Content-Type: text/plain;charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 37 Dear colleagues - After taking far too long, I have made a modified version of my thesis entitled "An algebraic theory of tricategories" available at www.math.yale.edu/~mg622/tricats.pdf. If you have questions, comments, find more typos, or anything of that sort, I encourage you to write to me at michaeln.gurski@yale.edu. Thanks to everyone who bugged me about making this available, and thanks for being patient. Nick Gurski From rrosebru@mta.ca Fri Mar 9 09:17:46 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 09 Mar 2007 09:17:46 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HPesJ-0007Dg-Tc for categories-list@mta.ca; Fri, 09 Mar 2007 09:11:12 -0400 Subject: categories: Re: dagger? Date: Thu, 8 Mar 2007 23:31:45 -0400 (AST) To: categories@mta.ca MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit From: selinger@mathstat.dal.ca (Peter Selinger) Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 38 Lawrence Stout wrote: > > Could someone please post a definition of a dagger category and a > reference for typical useful examples? For reference: an involutive category (or dagger category) is a category C equipped with a contravariant, involutive, identity-on-objects functor "+" (my ASCII rendition of the TeX symbol $\dagger$). The main reason to consider dagger structure is that it allows the following definitions (and other similar ones): * a morphism f:A->B is _unitary_ if f is invertible and f^{-1} = f^+ * a morphism f:A->A is _hermitian_ if f = f^+. * a morphism f:A->A is _hermitian positive_ if there exists some object B and g:A->B such that f = g^+ o g. * a morphism f:A->B is called an _isometry_ if f^+ o f = id. ("Isometry" is to "unitary" like "mono" to "iso"). The main example is the category of finite-dimensional Hilbert spaces. In it, for a map f : A -> B, the map f^+ : B -> A is given as the adjoint of f (in the linear-algebra sense). Note that the definition of the adjoint requires inner products, hence *Hilbert* and not just vector spaces. The category of finite-dimensional Hilbert spaces is additionally compact closed, so that for a morphism f : A -> B, we also have f^* : B^* -> A^*. While the functor (-)^* is also contravariant and involutive, it is not to be confused with the dagger structure. A^* is the dual space, which is not naturally isomorphic to A. Also, relative to chosen bases, the matrix of f^* is the transpose of that of f, whereas the matrix of f^+ is the adjoint (complex conjugate transpose). Dagger compact closed categories were axiomatized by Abramsky and Coecke [LICS 2004], and also by Baez and Dolan [ArXiV:q-alg/9503002, 1995]. One requires the following compatibilities between the two structures: * (f tensor g)^+ = f^+ tensor g^+, * the structural natural isomorphisms (associativity, symmetry, etc) are unitary, * the maps I -> (A^* tensor A) and (A^* tensor A) -> I are each other's adjoints. As Abramsky and Coecke have shown, many interesting constructions from Hilbert spaces can be done in a dagger compact closed category. Another example of a dagger compact closed category is the category of sets and relations, but it is degenerate, in the sense that A^* = A and f^* = f^+. -- Peter From rrosebru@mta.ca Fri Mar 9 09:17:46 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 09 Mar 2007 09:17:46 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HPetI-0007Ii-0N for categories-list@mta.ca; Fri, 09 Mar 2007 09:12:12 -0400 Date: Fri, 9 Mar 2007 10:01:41 +0000 From: "Jamie Vicary" Subject: categories: Re: relations on graphs To: categories@mta.ca MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Content-Disposition: inline Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 39 > Is there any literature which discusses different > possible notions for relations on graphs? In any regular category, and certainly any topos, there is a well defined notion of relation, where a relation between two objects is a subobject of their product. These admit a * operation and compose in a well-behaved way; look towards the end of McLarty's category theory textbook for info on this. The category of directed graphs is certainly such a category, being regular. The category of graphs is not a topos, I believe, but might still be regular. Jamie Vicary. From rrosebru@mta.ca Fri Mar 9 14:32:45 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 09 Mar 2007 14:32:45 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HPjq1-00060S-HF for categories-list@mta.ca; Fri, 09 Mar 2007 14:29:09 -0400 Date: Fri, 09 Mar 2007 09:02:23 -0800 From: Vaughan Pratt MIME-Version: 1.0 To: categories@mta.ca Subject: categories: Re: relations on graphs Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: RO X-Status: X-Keywords: X-UID: 40 > The category of directed graphs is certainly such a category, being > regular. The category of graphs is not a topos, I believe, but might > still be regular. Suitably defined the category of undirected graphs is indeed a topos. As came up a year ago on this list (thread beginning with my 2/27/06 inquiry about the history of the presheaf category of undirected graphs), undirected or symmetric graphs can be defined as M-sets for the monoid M = Set(2,2), endomorphisms of the doubleton in Set, aka the four unary Boolean operations. Of the latter, x and not-x together denote the two directions of edge x while 0(x) and 1(x) denote its two vertices (as self-loops). One might imagine some sort of asymmetry between x and not-x that makes x the primary direction, but x and not-x always travel together as a group (quite literally: S_2) under graph homomorphism and their inseparability justifies the view of the two as forming a single undirected edge having two directed names, x and not-x. The singleton splits 0 and 1 to make those self-loops vertices in their own right, so by Morita equivalence the full subcategory of Set with objects the positive cardinals up to 2 canonically represents the same presheaf category up to equivalence. Dusko Pavlovic, "A categorical setting for the 4-color theorem," JPAA 102, 1, 75--88 (1995), organizes undirected graphs as the above topos. Section 10.3 (pp. 176--180) of Lawvere and Rosebrugh, Sets for Mathematics, CUP 2003, develops this topos in more detail, pointing out the two distinguished loops, an idiosyncrasy of this representation of undirected graphs. All this lifts readily to the topos of higher dimensional graphs: simplicial sets in the directed case, symmetric simplicial sets in the undirected. Marco Grandis, in Finite sets and symmetric simplicial sets, Theory Appl. Categ. 8 (2001), No. 8, 244-252, identified the presheaves on FinSet with the undirected or symmetric simplicial sets, which as Clemens Berger pointed out had been encountered much earlier in another guise by Daniel Kan (Amer. J. Math. 79 (1957) 449-476 as the barycentric subdivision of a simplicial set. Vaughan From rrosebru@mta.ca Fri Mar 9 14:32:45 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 09 Mar 2007 14:32:45 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HPjr9-00067C-8y for categories-list@mta.ca; Fri, 09 Mar 2007 14:30:19 -0400 From: "Ronnie Brown" To: Subject: categories: Re: relations on graphs Date: Fri, 9 Mar 2007 17:49:27 -0000 MIME-Version: 1.0 Content-Type: text/plain;format=flowed; charset="iso-8859-1";reply-type=response Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 41 Jamie Vicary states `the category of graphs is not a topos'. The situation is not so simple, and is discussed for the combinatorially minded reader in 06.04 BROWN, R., MORRIS, I., SHRIMPTON, J. & WENSLEY, C.D. Graphs of morphisms of graphs http://www.informatics.bangor.ac.uk/public/mathematics/research/preprints/06/cathom06.html#06.04 There are categories of undirected graphs which are not toposes. But ... Ronnie Brown ----- Original Message ----- From: "Jamie Vicary" To: Sent: Friday, March 09, 2007 10:01 AM Subject: categories: Re: relations on graphs >> Is there any literature which discusses different >> possible notions for relations on graphs? > > In any regular category, and certainly any topos, there is a well > defined notion of relation, where a relation between two objects is a > subobject of their product. These admit a * operation and compose in a > well-behaved way; look towards the end of McLarty's category theory > textbook for info on this. > > The category of directed graphs is certainly such a category, being > regular. The category of graphs is not a topos, I believe, but might > still be regular. > > Jamie Vicary. > From rrosebru@mta.ca Fri Mar 9 14:32:45 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 09 Mar 2007 14:32:45 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HPjoU-0005pl-GX for categories-list@mta.ca; Fri, 09 Mar 2007 14:27:35 -0400 Date: Fri, 9 Mar 2007 15:33:12 +0000 From: "Jamie Vicary" To: categories@mta.ca Subject: categories: Re: relations on graphs MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Content-Disposition: inline Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: RO X-Status: X-Keywords: X-UID: 42 On 3/9/07, Jamie Vicary wrote: > > Is there any literature which discusses different > > possible notions for relations on graphs? > > In any regular category, and certainly any topos, there is a well > defined notion of relation, where a relation between two objects is a > subobject of their product. These admit a * operation and compose in a > well-behaved way; look towards the end of McLarty's category theory > textbook for info on this. > > The category of directed graphs is certainly such a category, being > regular. The category of graphs is not a topos, I believe, but might > still be regular. Dear all, before the flood of complaints begins: I should make it clear that I am differentiating between the category of directed graphs, which is certainly a topos, and the category of graphs (i.e. edges have no orientation) which, as I have just managed to convince myself, is certainly _not_ a topos. The original poster was enquiring about the category of graphs, I believe, rather than the category of directed graphs. JAmie. From rrosebru@mta.ca Fri Mar 9 16:56:00 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 09 Mar 2007 16:56:00 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HPm2k-0004lu-Va for categories-list@mta.ca; Fri, 09 Mar 2007 16:50:27 -0400 From: Thomas Streicher Subject: categories: relations on graphs To: categories@mta.ca Date: Fri, 9 Mar 2007 20:10:58 +0100 (CET) MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 43 If one allows multiple edges with the same source and target then they certainly form a topos, namely that of presheaves over the category with 2 objects and 2 parallel nontrivial arrows. The \neg\neg-separated objects in this topos are precisely those graphs where there is at most one edge from one node to another one. The latter category is not a topos but a quasitopos. The non-full monos in this category are typical examples of epic monos which are not isos. All this can be found in Lawvere's "Qualitative distinctions between toposes of graphs". Thomas Streicher From rrosebru@mta.ca Fri Mar 9 20:08:33 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 09 Mar 2007 20:08:33 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HPp1c-0000yF-4I for categories-list@mta.ca; Fri, 09 Mar 2007 20:01:28 -0400 Date: Fri, 9 Mar 2007 22:40:46 +0000 (GMT) From: Richard Garner To: categories@mta.ca Subject: categories: Re: relations on graphs MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 44 While we're on the topic of directed graphs, can anyone provide a satisfactory conceptual explanation for the following curiosity? Let Ar(Set) be the arrow category of Set, and let DGph be directed multigraphs, i.e., presheaves over the parallel pair category as per Thomas' message. Prop: DGph is comonadic over Ar(Set) Proof: We have an adjunction U -| C as follows. U: DGph -> Ar(Set) sends a directed graph s, t : A -> V to the coproduct injection V -> V + A. C: Ar(Set) -> DGph sends an arrow f : X -> Y to the directed graph \pi_1, \pi_2 : X*X*Y -> X. It's easy to check that this is an adjunction, and so we induce a comonad T = UC on Ar(Set), the functor part of which sends f: X --> Y to the coproduct injection X --> X + X*X*Y. Thus a coalgebra structure f --> Tf consists of specifying a map p: Y --> X + X*X*Y satisfying three axioms. These axioms force f: X --> Y to be an injection, and the map p to be defined by cases: those y in Y which lie in the image of f are sent to f^-1(y) in the left-hand copy of X, whilst those y in Y that are not in X are sent to some element (s(y), t(y), y) of X*X*Y. Thus giving a T-coalgebra structure on f:X --> Y is equivalent to giving a directed graph structure s, t : Y \setminus f(X) --> X: and this assignation extends to a functor T-Coalg --> DGph which together with the canonical comparison functor DGph --> T-Coalg gives us an equivalence of categories, Q.E.D. -- Richard Garner --On 09 March 2007 20:10 Thomas Streicher wrote: > If one allows multiple edges with the same source and target then > they certainly form a topos, namely that of presheaves over the > category with 2 objects and 2 parallel nontrivial arrows. > The \neg\neg-separated objects in this topos are precisely those > graphs where there is at most one edge from one node to another one. > The latter category is not a topos but a quasitopos. > The non-full monos in this category are typical examples of > epic monos which are not isos. > > All this can be found in Lawvere's "Qualitative distinctions between > toposes of graphs". > > Thomas Streicher > > > From rrosebru@mta.ca Fri Mar 9 20:08:33 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 09 Mar 2007 20:08:33 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HPoz5-0000qF-PC for categories-list@mta.ca; Fri, 09 Mar 2007 19:58:51 -0400 Date: Fri, 09 Mar 2007 14:22:47 -0800 From: Vaughan Pratt MIME-Version: 1.0 To: categories list Subject: categories: Early CT problems that are still open Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 45 What early problems in category theory remain open today? Who first posed them, and when and where? Context: In December the Journal of the AMS rejected the solution of the half-century-old lattice theory problem of whether the congruence lattices of lattices are exactly the distributive algebraic lattices. Since these two classes coincide for all algebraic lattices with up to aleph_1 compact generators [Huhn 1989], one would imagine that surely the equivalence must extend to all cardinalities. Fred Wehrung recently showed it doesn't, refined by Pavel Ruzicka to show that they diverge exactly at aleph_2. For two such naturally defined classes it's very unusual to first diverge at such a high cardinal. (For elementary classes it's impossible: if they're still together at aleph_0 they're the same.) Now JAMS doesn't ordinarily cater to either lattice theory or category theory. Yet its mission statement declares JAMS to be "devoted to ... all areas of pure and applied mathematics." The general feeling among lattice theorists is that, whatever JAMS might think of those areas it is unaccustomed to serving, rejecting the solution to so celebrated an open problem is beyond the pale given their mission statement. There is no likelihood of their being overwhelmed with such so space can't be a reason. More on this at http://clp.stanford.edu . My interest here in early open CT problems is to get a sense of how comparable CT's situation is with lattice theory's. On the one hand it might seem insane for either category theorists or lattice theorists to bother the JAMS audience if they're not interested. On the other, if it's a really neat result then why hide it under a bushel? The mathematical community at large ought to be sufficiently open-minded as to appreciate such an achievement. If a category theorist were to publish the solution to a long-standing CT problem in JAMS, it would reflect well on CT, and it would lend support to JAMS's mission statement. Vaughan From rrosebru@mta.ca Sat Mar 10 14:34:44 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 10 Mar 2007 14:34:44 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HQ6KB-0004v6-GM for categories-list@mta.ca; Sat, 10 Mar 2007 14:29:47 -0400 Date: Sat, 10 Mar 2007 15:58:29 +0000 (GMT) From: "Prof. Peter Johnstone" To: Categories mailing list Subject: categories: further on Garner's question MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 46 A further attempt to provide a general context for Richard's observation: let f: C --> D be a functor between small categories having a right multi-adjoint in the sense of Diers, i.e. such that, for each object b of D, the comma category (f \downarrow b) is a disjoint union of categories with terminal objects. (Note that this is always the case when C is discrete, as in the example considered by Richard, since then the (f \downarrow b) are also discrete.) Then the left Kan extension functor f_!: [C,Set] --> [D,Set] can be constructed using only coproducts rather than more general colimits, from which it follows easily that it is faithful and preserves equalizers. Hence it is comonadic. (I suspect that this may be a necessary as well as a sufficient condition for comonadicity of f_!, but I don't yet have a proof.) Incidentally, note that if C and D are any two categories with the same set of objects, we can construct a comonadic adjunction (in either direction) between [C,Set] and [D,Set], by `interposing' the discrete category with the same objects, in the manner of Richard's example. Indeed, we don't even need the categories to have the same objects: all we need is to find a set which surjects onto both ob C and ob D. Peter Johnstone On Sat, 10 Mar 2007, Prof. Peter Johnstone wrote: > Here's at least a partial conceptual explanation of > Richard Garner's "curiosity". There are really three > categories involved, all of them toposes: they are > the functor categories [2,Set] where 2 denotes the > discrete two-object category, [I,Set] where I denotes the > category (* --> *) and [G,Set] where G has two objects and > two parallel arrows between them. The inclusions > f: 2 --> I and g: 2 --> G of course induce essential > geometric morphisms (strings of three adjoint functors) > > f g > [I,Set] <--- [2,Set] ---> [G,Set] > > and Richard's functors are simply the composites > g_*f^* and f_!g^*. So it's no surprise that they > should be adjoint: also, the adjunction (g^* -| g_*) > is comonadic, because g is surjective on objects. > The only oddity is that (f_! -| f^*) is also > comonadic (it's obviously monadic, again because f > is surjective on objects). As far as I can see, this is > just an isolated fact: it isn't a particular case of any > general result that I know. > > Peter Johnstone > > On Fri, 9 Mar 2007, Richard Garner wrote: > > > > > While we're on the topic of directed graphs, can > > anyone provide a satisfactory conceptual > > explanation for the following curiosity? > > > > Let Ar(Set) be the arrow category of Set, and let > > DGph be directed multigraphs, i.e., presheaves over > > the parallel pair category as per Thomas' message. > > > > Prop: DGph is comonadic over Ar(Set) > > > > Proof: We have an adjunction U -| C as follows. > > > > U: DGph -> Ar(Set) sends a directed graph > > s, t : A -> V to the coproduct injection V -> V + A. > > > > C: Ar(Set) -> DGph sends an arrow f : X -> Y to the > > directed graph \pi_1, \pi_2 : X*X*Y -> X. > > > > It's easy to check that this is an adjunction, and > > so we induce a comonad T = UC on Ar(Set), the > > functor part of which sends f: X --> Y to the > > coproduct injection X --> X + X*X*Y. Thus a > > coalgebra structure f --> Tf consists of specifying > > a map p: Y --> X + X*X*Y satisfying three axioms. > > > > These axioms force f: X --> Y to be an injection, > > and the map p to be defined by cases: those y in Y > > which lie in the image of f are sent to f^-1(y) in > > the left-hand copy of X, whilst those y in Y that > > are not in X are sent to some element (s(y), t(y), > > y) of X*X*Y. Thus giving a T-coalgebra structure on > > f:X --> Y is equivalent to giving a directed graph > > structure s, t : Y \setminus f(X) --> X: and this > > assignation extends to a functor T-Coalg --> DGph > > which together with the canonical comparison > > functor DGph --> T-Coalg gives us an equivalence of > > categories, Q.E.D. > > > > -- > > > > Richard Garner > From rrosebru@mta.ca Sat Mar 10 14:34:44 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 10 Mar 2007 14:34:44 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HQ6JJ-0004s6-7A for categories-list@mta.ca; Sat, 10 Mar 2007 14:28:53 -0400 Date: Sat, 10 Mar 2007 11:49:41 +0000 (GMT) From: "Prof. Peter Johnstone" To: Categories mailing list Subject: categories: Re: Garner's question MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 47 Here's at least a partial conceptual explanation of Richard Garner's "curiosity". There are really three categories involved, all of them toposes: they are the functor categories [2,Set] where 2 denotes the discrete two-object category, [I,Set] where I denotes the category (* --> *) and [G,Set] where G has two objects and two parallel arrows between them. The inclusions f: 2 --> I and g: 2 --> G of course induce essential geometric morphisms (strings of three adjoint functors) f g [I,Set] <--- [2,Set] ---> [G,Set] and Richard's functors are simply the composites g_*f^* and f_!g^*. So it's no surprise that they should be adjoint: also, the adjunction (g^* -| g_*) is comonadic, because g is surjective on objects. The only oddity is that (f_! -| f^*) is also comonadic (it's obviously monadic, again because f is surjective on objects). As far as I can see, this is just an isolated fact: it isn't a particular case of any general result that I know. Peter Johnstone On Fri, 9 Mar 2007, Richard Garner wrote: > > While we're on the topic of directed graphs, can > anyone provide a satisfactory conceptual > explanation for the following curiosity? > > Let Ar(Set) be the arrow category of Set, and let > DGph be directed multigraphs, i.e., presheaves over > the parallel pair category as per Thomas' message. > > Prop: DGph is comonadic over Ar(Set) > > Proof: We have an adjunction U -| C as follows. > > U: DGph -> Ar(Set) sends a directed graph > s, t : A -> V to the coproduct injection V -> V + A. > > C: Ar(Set) -> DGph sends an arrow f : X -> Y to the > directed graph \pi_1, \pi_2 : X*X*Y -> X. > > It's easy to check that this is an adjunction, and > so we induce a comonad T = UC on Ar(Set), the > functor part of which sends f: X --> Y to the > coproduct injection X --> X + X*X*Y. Thus a > coalgebra structure f --> Tf consists of specifying > a map p: Y --> X + X*X*Y satisfying three axioms. > > These axioms force f: X --> Y to be an injection, > and the map p to be defined by cases: those y in Y > which lie in the image of f are sent to f^-1(y) in > the left-hand copy of X, whilst those y in Y that > are not in X are sent to some element (s(y), t(y), > y) of X*X*Y. Thus giving a T-coalgebra structure on > f:X --> Y is equivalent to giving a directed graph > structure s, t : Y \setminus f(X) --> X: and this > assignation extends to a functor T-Coalg --> DGph > which together with the canonical comparison > functor DGph --> T-Coalg gives us an equivalence of > categories, Q.E.D. > > -- > > Richard Garner From rrosebru@mta.ca Sat Mar 10 14:34:44 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 10 Mar 2007 14:34:44 -0400 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HQ6Il-0004qB-4c for categories-list@mta.ca; Sat, 10 Mar 2007 14:28:19 -0400 Mime-Version: 1.0 (Apple Message framework v752.3) Content-Type: text/plain; charset=ISO-8859-1; delsp=yes; format=flowed Content-Transfer-Encoding: quoted-printable From: Pierre-Louis Curien Subject: categories: Position announcement in Paris 7 University Date: Sat, 10 Mar 2007 11:49:45 +0100 To: types-announce@lists.seas.upenn.edu, categories@mta.ca Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 48 Following a preannouncement posted last October, > A position of Maitre de Conferences (permanent position, more or less > equivalent to "associate professor", or "lecturer") > > ** in mathematics** > > is opened at Paris 7 University. > The hired candidate will work in the laboratory PPS (Preuves, > Programmes et Systemes), which spreads its interests on both sides of > the correspondence between proofs and programs, covering work on > language design and implementation, rewriting, semantics (and game > semantics in particular), categories, linear logic, realizability, > probabilistic and topological methods, etc... See =20 > www.pps.jussieu.fr. > > Th deadline for application is ** March 31 (see more specific info in French below) **, > with decisions taken > around May 2007, and job starting in October 2007. The applicant must have gone through the qualification procedure (cf. =20= preannouncement). > A certain fluency in French is required for the position. The teaching > will be in the mathematics department, so some experience in teaching > mathematics (rather than computer science) is welcome. Teaching is in > French. > > I invite candidates to contact me. > Best regards, > > Pierre=3DLouis Curien > > curien@pps.jussieu.fr > **** More practical info (in French) **** Ma=EEtres de conf=E9rences 25=E8 section : Universit=E9 Paris-VII : math=E9matiques des preuves et des programmes : = =20 0648. POUR ACCEDER AU TEXTE INTEGRAL DU J.O. par internet : http://www.legifrance.gouv.fr Arr=EAt=E9 du 16 f=E9vrier 2007 portant d=E9claration de vacance = d'emplois de =20 professeur des universit=E9s offerts =E0 la mutation, au d=E9tachement = et, =20 en application du 1=B0 de l'article 46 du d=E9cret n=B0 84-431 du 6 juin = =20 1984 modifi=E9, au recrutement (1re session 2007) NOR: MENH0700337A Arr=EAt=E9 du 16 f=E9vrier 2007 portant d=E9claration de vacance = d'emplois de =20 ma=EEtre de conf=E9rences offerts =E0 la mutation, au d=E9tachement et, = en =20 application du 1=B0 de l'article 26-I du d=E9cret n=B0 84-431 du 6 juin =20= 1984 modifi=E9, au recrutement (1re session 2007) NOR: MENH0700341A Cl=F4ture des inscriptions dans l'application ANTARES : le 30 mars 2007 =20= =E0 16h heure de Paris (et non pas le 27 mars comme indiqu=E9 par erreur = =20 aux articles 8 et 13 de l'arr=EAt=E9 relatif aux professeurs) http://www.education.gouv.fr rubrique =AB Concours, emplois, carri=E8res = =20 =BB puis =AB Personnel enseignant du sup=E9rieur et chercheurs =BB puis = =AB les =20 enseignants-chercheurs =BB Le dossier papier devra =EAtre envoy=E9 au plus tard le 30 mars =E0 = minuit =20 (cachet de la poste faisant foi) au service du personnel de =20 l'=E9tablissement affectataire de l'emploi. From rrosebru@mta.ca Mon Mar 12 15:14:43 2007 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 12 Mar 2007 15:14:43 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HQouD-0007L6-UD for categories-list@mta.ca; Mon, 12 Mar 2007 15:05:58 -0300 Date: Mon, 12 Mar 2007 15:38:43 +0100 (CET) From: Lutz Strassburger To: categories@mta.ca Subject: categories: Post Doc Position in Paris MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 49 -------------------------------------------------------- Postdoc Positions on Proof Theory in Paris -------------------------------------------------------- I am pleased to announce the opening of a postdoc position which is financed by the ANR within the project INFER This project is a grouping of three teams through their common interest for a new approach to proof theory, called deep inference, that has been developed during the last seven years. We aim at refining its enormous potential and at applying it to problems related to the foundations of logic and to more practical questions in the algorithmics of deductive systems. The working place of the postdoc will be in the suburbs of Paris at the Ecole Polytechnique which is one of the "Grand Ecoles" in the French education system. Applicants must have a Ph.D. or equivalent in computer science or mathematics, and should have a strong background in proof theory and/or related topics. The principal responsibility of the postdoc will be to carry out research in the area of deep inference. There are no teaching duties. For more information, please contact: Lutz Strassburger Applications should be sent via email to Lutz Strassburger , and should include a CV, a short research proposal (1-2 pages), and one or two recommendation letters. The position is open now, and applications are considered until the position is filled. Furthermore, I'd like to draw the attention to an INRIA postdoc offer on a related topic: http://www.talentsplace.com/syndication1/inria/ukpostdoc/details.html?id=PNGFK026203F3VBQB6G68LOE1&LOV5=4508&LOV2=4493&LOV6=4514&LG=EN&Resultsperpage=20&nPostingID=1124&nPostingTargetID=3132&option=52&sort=DESC&nDepartmentID=19 For this applications have to made online via the INRIA webpage (deadline 31 March). Nonetheless, potential applicants should contact me via email. Best regards, Lutz Strassburger From rrosebru@mta.ca Mon Mar 12 15:14:43 2007 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 12 Mar 2007 15:14:43 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HQotf-0007Gx-6g for categories-list@mta.ca; Mon, 12 Mar 2007 15:05:23 -0300 Date: Mon, 12 Mar 2007 09:23:16 +0000 (GMT) From: Richard Garner To: Categories mailing list Subject: categories: Re: further on Garner's question MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 50 Very interesting! I was aware that one could construct such comonadic adjunctions in a limited variety of other cases, but that one can do so for essentially any pair of presheaf categories is (at least to me) a little surprising. Of course, even in the case where C and D have the same objects, there is nothing "canonical" about the comonadic adjunction [C, Set] -| [D, Set] which we construct in the way Peter has indicated, since we have first to choose a bijection between the objects of C and the objects of D. Richard Garner --On 10 March 2007 15:58 Prof. Peter Johnstone wrote: > A further attempt to provide a general context for Richard's > observation: let f: C --> D be a functor between small > categories having a right multi-adjoint in the sense of Diers, > i.e. such that, for each object b of D, the comma category > (f \downarrow b) is a disjoint union of categories with > terminal objects. (Note that this is always the case when > C is discrete, as in the example considered by Richard, since > then the (f \downarrow b) are also discrete.) Then the left > Kan extension functor > f_!: [C,Set] --> [D,Set] can be constructed using only > coproducts rather than more general colimits, from which it > follows easily that it is faithful and preserves equalizers. > Hence it is comonadic. (I suspect that this may be a > necessary as well as a sufficient condition for comonadicity > of f_!, but I don't yet have a proof.) > > Incidentally, note that if C and D are any two categories with > the same set of objects, we can construct a comonadic > adjunction (in either direction) between [C,Set] and [D,Set], > by `interposing' the discrete category with the same objects, in the > manner of Richard's example. Indeed, we don't even need the > categories to have the same objects: all we need is to find a > set which surjects onto both ob C and ob D. > > Peter Johnstone > > On Sat, 10 Mar 2007, Prof. Peter Johnstone wrote: > >> Here's at least a partial conceptual explanation of >> Richard Garner's "curiosity". There are really three >> categories involved, all of them toposes: they are >> the functor categories [2,Set] where 2 denotes the >> discrete two-object category, [I,Set] where I denotes the >> category (* --> *) and [G,Set] where G has two objects and >> two parallel arrows between them. The inclusions >> f: 2 --> I and g: 2 --> G of course induce essential >> geometric morphisms (strings of three adjoint functors) >> >> f g >> [I,Set] <--- [2,Set] ---> [G,Set] >> >> and Richard's functors are simply the composites >> g_*f^* and f_!g^*. So it's no surprise that they >> should be adjoint: also, the adjunction (g^* -| g_*) >> is comonadic, because g is surjective on objects. >> The only oddity is that (f_! -| f^*) is also >> comonadic (it's obviously monadic, again because f >> is surjective on objects). As far as I can see, this is >> just an isolated fact: it isn't a particular case of any >> general result that I know. >> >> Peter Johnstone >> >> On Fri, 9 Mar 2007, Richard Garner wrote: >> >>> >>> While we're on the topic of directed graphs, can >>> anyone provide a satisfactory conceptual >>> explanation for the following curiosity? >>> >>> Let Ar(Set) be the arrow category of Set, and let >>> DGph be directed multigraphs, i.e., presheaves over >>> the parallel pair category as per Thomas' message. >>> >>> Prop: DGph is comonadic over Ar(Set) >>> >>> Proof: We have an adjunction U -| C as follows. >>> >>> U: DGph -> Ar(Set) sends a directed graph >>> s, t : A -> V to the coproduct injection V -> V + A. >>> >>> C: Ar(Set) -> DGph sends an arrow f : X -> Y to the >>> directed graph \pi_1, \pi_2 : X*X*Y -> X. >>> >>> It's easy to check that this is an adjunction, and >>> so we induce a comonad T = UC on Ar(Set), the >>> functor part of which sends f: X --> Y to the >>> coproduct injection X --> X + X*X*Y. Thus a >>> coalgebra structure f --> Tf consists of specifying >>> a map p: Y --> X + X*X*Y satisfying three axioms. >>> >>> These axioms force f: X --> Y to be an injection, >>> and the map p to be defined by cases: those y in Y >>> which lie in the image of f are sent to f^-1(y) in >>> the left-hand copy of X, whilst those y in Y that >>> are not in X are sent to some element (s(y), t(y), >>> y) of X*X*Y. Thus giving a T-coalgebra structure on >>> f:X --> Y is equivalent to giving a directed graph >>> structure s, t : Y \setminus f(X) --> X: and this >>> assignation extends to a functor T-Coalg --> DGph >>> which together with the canonical comparison >>> functor DGph --> T-Coalg gives us an equivalence of >>> categories, Q.E.D. >>> >>> -- >>> >>> Richard Garner >> > > > From rrosebru@mta.ca Mon Mar 12 17:51:22 2007 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 12 Mar 2007 17:51:22 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HQrQz-00055i-5v for categories-list@mta.ca; Mon, 12 Mar 2007 17:47:57 -0300 Mime-Version: 1.0 (Apple Message framework v752.2) Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed Content-Transfer-Encoding: 7bit From: Michael Mislove Subject: categories: MFPS 23 Call for Participation Date: Mon, 12 Mar 2007 14:41:04 -0500 To: categories@mta.ca Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 51 Dear Colleagues, This is a Call for Participation for the 23rd Conference on the Mathematical Foundations of Programming Semantics. The meeting will take place on the campus of Tulane University in New Orleans, LA from April 11 through April 14. The meeting will include invited lectures by Stephen Brookes (CMU), Jane Hillston (Edinburgh), John Mitchell (Stanford), Gordon Plotkin (Edinburgh) and John Power (Edinburgh). In addition there will be a special session honoring Gordon Plotkin on the 60th birthday, as well as special sessions on Security, on Systems Biology and on Physics, Information and Computation. The balance of the program is made up of papers submitted in response to the Call for Papers that was circulated last fall. A copy of the full program is available at http://www.math.tulane.edu/~mfps/program23.htm In addition to the conference, there will be a Tutorial Day on Domain Theory on April 10, with lectures by Achim Jung (Birmingham), Alex Simpson (Edinburgh), Andrej Bauer (Slovenia) and Giuseppe Rosolini (Genoa). To find out more about the meeting and to register, point your browser at http://www.math.tulane.edu/~mfps/mfps23.htm The deadline for booking a room at the conference hotel is this Friday, March 16. Best regards, Mike Mislove =============================================== Professor Michael Mislove Phone: +1 504 862-3441 Department of Mathematics FAX: +1 504 865-5063 Tulane University URL: http://www.math.tulane.edu/~mwm New Orleans, LA 70118 USA =============================================== From rrosebru@mta.ca Tue Mar 13 20:05:47 2007 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 13 Mar 2007 20:05:47 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HRFu7-0004ag-0A for categories-list@mta.ca; Tue, 13 Mar 2007 19:55:39 -0300 Date: Mon, 12 Mar 2007 17:14:43 -0400 From: Jacques Carette MIME-Version: 1.0 To: categories Subject: categories: Programming Languages and Mechanized Mathematics Workshop Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: quoted-printable Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 52 [This might be of interest to the members of this list, as many=20 approaches to both programming language semantics and of mechanizing=20 mathematics are deeply categorical]. Programming Languages for Mechanized Mathematics Workshop As part of Calculemus 2007=20 Hagenberg, Austria [http://www.cas.mcmaster.ca/plmms07/] The intent of this workshop is to examine more closely the intersection=20 between programming languages and mechanized mathematics systems (MMS).=20 By MMS, we understand computer algebra systems (CAS), [automated]=20 theorem provers (TP/ATP), all heading towards the development of fully=20 unified systems (the MMS), sometimes also called universal mathematical=20 assistant systems (MAS) (see Calculemus 2007=20 ). There are various ways in which these two subjects of /programming=20 languages/ and /systems for mathematics/ meet: * Many systems for mathematics contain a dedicated programming language. For instance, most computer algebra systems contain a dedicated language (and are frequently built in that same language); some proof assistants (like the Ltac language for Coq) also have an embedded programming language. Note that in many instances this language captures only algorithmic content, and /declarative/ or /representational/ issues are avoided. * The /mathematical languages/ of many systems for mathematics are very close to a functional programming language. For instance the language of ACL2 is just Lisp, and the language of Coq is very close to Haskell. But even the mathematical language of the HOL system can be used as a functional programming language that is very close to ML and Haskell. On the other hand, these languages also contain very rich specification capabilities, which are rarely available in most computation-oriented programming languages. And even then, many specification languages ((B, Z, Maude, OBJ3, CASL, etc) can still teach MMSes a trick or two regarding representational power. * Conversely, functional programming languages have been getting "more mathematical" all the time. For instance, they seem to have discovered the value of dependent types rather recently. But they are still not quite ready to 'host' mathematics (the non-success of docon being typical). There are some promising languages on the horizon (Epigram , Omega ) as well as some hybrid systems (Agda , Focal ), although it is unclear if they are truly capable of expressing the full range of ideas present in mathematics. * Systems for mathematics are used to prove programs correct. (One method is to generate "correctness conditions" from a program that has been annotated in the style of Hoare logic and then prove those conditions in a proof assistant.) An interesting question is what improvements are needed for this both on the side of the mathematical systems and on the side of the programming languages. We are interested in all these issues. We hope that a certain synergy=20 will develop between those issues by having them explored in parallel. These issues have a very colourful history. Many programming language=20 innovations first appeared in either CASes or Proof Assistants, before=20 migrating towards more mainstream languages. One can cite (in no=20 particular order) type inference, dependent types, generics,=20 term-rewriting, first-class types, first-class expressions, first-class=20 modules, code extraction, and so on. However, a number of these=20 innovations were never aggressively pursued by system builders, letting=20 them instead be developped (slowly) by programming language researchers.=20 Some, like type inference and generics have flourished. Others, like=20 first-class types and first-class expressions, are not seemingly being=20 researched by anyone. We want to critically examine what has worked, and what has not. Why are=20 all the current ``popular'' computer algebra systems untyped? Why are=20 the (strongly typed) proof assistants so much harder to use than a=20 typical CAS? But also look at question like what forms of polymorphism=20 exists in mathematics? What forms of dependent types exist in=20 mathematics? How can MMS regain the upper hand on issues of=20 'genericity'? What are the biggest barriers to using a more mainstream=20 language as a host language for a CAS or an ATP? This workshop will accept two kinds of submissions: full research papers=20 as well as position papers. Research papers should be nore more than 15=20 pages in length, and positions papers no more than 3 pages. Submission=20 will be through _EasyChair_. An informal version of the proceedings will=20 be available at the workshop, with a more formal version to appear=20 later. We are looking into having the best papers completed into full=20 papers and published as a special issue of a Journal (details to follow). Important Dates April 25, 2007: Submission Deadline June 29-30, 2007: Workshop Program Committee Lennart Augustsson [Credit Suisse= ] Wieb Bosma [Radboud University=20 Nijmegen, Netherlands] Jacques Carette (co-Chair)=20 [McMaster University, Canada] David Delahaye [CNAM, France] Jean-Christophe Filli=E2tre [CNRS and=20 Universit=E9 de Paris-Sud, France] John Harrison [Intel Corporation, USA= ] Markus (Makarius) Wenzel [Technische=20 Universit=E4t M=FCnchen, Germany] Freek Wiedijk (co-Chair) [Radboud=20 University Nijmegen, Netherlands] Wolfgang Windsteiger =20 [University of Linz, Austria] Location and Registration Location and registration information can be found on the Calculemus=20 web=20 site. From rrosebru@mta.ca Tue Mar 13 21:11:01 2007 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 13 Mar 2007 21:11:01 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HRH1c-0002gR-6L for categories-list@mta.ca; Tue, 13 Mar 2007 21:07:28 -0300 Subject: categories: Re: monic epics Date: Mon, 12 Mar 2007 09:37:12 +1100 From: Agnes Boskovitz To: categories@mta.ca Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 53 Hi You might be interested in the Masters thesis I wrote in 1980 called "Epimorphisms in Algebraic and Some Other Categories", which might have some relevant information in it for you. You can get it from the McGill University library, or from Library and Archives Canada, or I can email you a copy if you wish. Agnes Boskovitz David Karapetyan wrote: > Hi, I've been trying to learn some category theory and I came upon the > example of a monic, epic in the category of monoids given by the > inclusion function of (N,0,+) into (Z,0,+). I know that in monoids every > monic arrow is also an injective function but the inclusion function of > N into Z provides a counterexample of every epic arrow being a > surjective function. I noticed that N is just a "folded" version of Z, > where by "folded" I mean take Z and throw away all the inverses of the > natural numbers. So does every monic, epic arrow determine such a > "folding" or are there monic, epics that can't be characterized in such > a way? > > From rrosebru@mta.ca Wed Mar 14 10:48:29 2007 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 14 Mar 2007 10:48:29 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HRTkL-00070d-M1 for categories-list@mta.ca; Wed, 14 Mar 2007 10:42:29 -0300 Mime-Version: 1.0 (Apple Message framework v752.2) Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: quoted-printable From: Francois Lamarche Subject: categories: Postdoctoral Fellowship in France Date: Wed, 14 Mar 2007 09:33:55 +0100 To: categories@mta.ca Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: RO X-Status: X-Keywords: X-UID: 54 POSTDOCTORAL FELLOWSHIP We would like to announce an offer for a one-year postdoctoral fellowship, extensible potentially to two years. The candidate will work in Nancy, in the east of France, under the supervision of Fran=E7ois Lamarche in the INRIA project Calligramme. Deadline for submission is MARCH 31 1007. Applications should be done through the web, via http://www.inria.fr/travailler/opportunites/postdoc/postdoc.en.html under the category "symbolic systems". There more instructions are given about the requirements. The principal constraint is that the candidate's doctoral thesis should have been defended after May 2006, and if it is still pending, that there should an official guarantee that it will be defended before September 2007. Fran=E7ois Lamarche Francois.Lamarche@loria.fr http://www.loria.fr/~lamarche ******************************************************************* PROOF NETS FOR CLASSICAL LOGIC AND DIFFERENTIAL INTERACTION NETS. This project aims at obtaining a better understanding of the computational character of the proof nets for classical propositional logic that were introduced in [1,2]. Their current execution semantics is based on the "interaction formula" of the Geometry of Interaction, but we are still missing reduction techniques on these nets based on graph rewriting. Differential interaction nets [4], obtained from a denotational semantics based on topological vector spaces [5] share several properties with "classical" nets: both involve bialgebras in their semantics, and thus both are equiped with with a "superposition" (or convolution) operation on proofs. The aim of this project is to leverage the experience and results already obtained about the computational meaning of differential nets in the field of "classical" proof nets. Several questions are considered, but in particular -- Is it possible to apply the non-deterministic character of differential nets (visible in the interpretations of the pi-calculus that they give rise to) to "classical" nets? In other words, can the convolution operation of classical nets be given an interpretation in terms of superposition of possibilities? How far can we (or must we) push non-determinism, only in the execution process itself, or as far as the possibility of having variation in the final result of the execution? Several technical difficulties have to be overcome. We see in particular the fact that the superposition operation in "classical" nets does not have a zero. We must see how far the simile can be pushed. This is a theoretical research project, and it is impossible to give a detailed work plan. The candidate will be working in project-team Calligramme, where researchers have competence in category theory, proof nets and lambda-mu calculus and other computational models of classical logic. The candidate will also be able to interact with members of project-teams Cartes (complexity, light linear logic) and Protheo (rewriting, rho calculus). - Profile sought: We are expecting from the candidate experience in denotational semantics AND (proof, interaction) nets. Skills in category theory are also a big plus. [1] F. Lamarche and L. Strassburger: Naming proofs in classical logic. TLCA 2005 [2] F. Lamarche and L. Strassburger: Constructing free Boolean categories. LICS 2005 [3] Girard, J.-Y.: Geometry of Interaction I: Interpretation of System F. Logic Colloquium 88, North-Holland. [4] Th. Ehrhard and Laurent Regnier: Differential Interaction Nets. Theor. Comp. Sci., to appear, available on the authors' home page. [5] Th. Ehrhard: On K=F6the sequence spaces and linear logic: Math. Struct. in Comp. Sci, 12, 2002. - contact (t=E9l et e-mail) : lamarche@loria.fr, +33 (0)3 54 95 84 10 - http:www.loria.fr/~lamarche ************* From rrosebru@mta.ca Sat Mar 17 21:05:08 2007 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 17 Mar 2007 21:05:08 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HSikx-0000Vn-76 for categories-list@mta.ca; Sat, 17 Mar 2007 20:56:15 -0300 From: "Ronnie Brown" To: Subject: categories: Out of Line Date: Sat, 17 Mar 2007 17:52:34 -0000 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 55 My old popularisation paper (1993) `Out of line' has now been made into = a web version by Marcus Brown, and is available from http://www.bangor.ac.uk/~mas010/outofline/out-home.html as pdf and html. I'll also mention=20 math.AT/0702677 A new higher homotopy groupoid: the fundamental globular = omega-groupoid of a filtered space which in a sense fills a gap in the construction of such higher homotopy = groupoids, where the classical crossed complex, the cubical case, and = the simplicial case had already been done by 1978.=20 Ronnie Brown School of Computer Science, University of Wales,=20 Bangor, Gwynedd LL57 1UT From rrosebru@mta.ca Sat Mar 17 21:05:08 2007 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sat, 17 Mar 2007 21:05:08 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HSik1-0000TV-MW for categories-list@mta.ca; Sat, 17 Mar 2007 20:55:17 -0300 Date: Fri, 16 Mar 2007 22:52:45 +0000 (GMT) From: S B Cooper To: categories@mta.ca Subject: categories: CiE 2007 - Call for informal presentations MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 56 ************************************************************ CiE'07: COMPUTABILITY IN EUROPE 2007 http://www.mat.unisi.it/newsito/cie07.html University of Siena Siena, 18 - 23 June 2007 CALL FOR INFORMAL PRESENTATIONS DEADLINE: 27 April, 2007 * THERE IS A REMARKABLE DIFFERENCE in conference style between computer science and mathematics conferences. Mathematics conferences allow for informal presentations that are prepared very shortly before the conference and inform the participants about current research and work in progress. The format of computer science conferences with pre-produced proceedings volumes is not able to accommodate this form of scientific communication. Continuing the tradition established at CiE 2005 in Amsterdam, and at CiE 2006 in Swansea, the 2007 conference in Siena endeavours to get the best of both worlds. * IN ADDITION TO THIS YEAR'S RECORD NUMBER of formal presentations based on our projected LNCS and local proceedings volumes, we invite researchers to present informal presentations. For this, please send us a brief description of your talk (up to and approaching one page in length) before 27 April 2007. * PLEASE SUBMIT YOUR ABSTRACT via the online Submission Form at: http://www.amsta.leeds.ac.uk/~pmt6sbc/cie07.ipform.html * If you submit an informal presentation, you will get an e-mail with a decision on acceptance or rejection within two weeks of your submission. * Let us add that there will be four post-conference special issues of journals for CiE 2007. See: http://www.amsta.leeds.ac.uk/~pmt6sbc/cie07.jour.html * All speakers, including the speakers of informal presentations, are eligible to be invited to submit a full journal version of their talk to one of the post-conference publications. PLENARY AND TUTORIAL SPEAKERS: Pieter Adriaans (Amsterdam) Yaakov Benenson (Harvard) Anne Condon (Vancouver) Stephen Cook (Toronto) Yuri Ershov (Novosibirsk) Wolfgang Maass (Graz) Sophie Laplante (Paris) Anil Nerode (Cornell) George Odifreddi (Turin) Roger Penrose (Oxford) Michael Rathjen (Leeds) Dana Scott (Carnegie Mellon) Robert I. Soare (Chicago) Philip Welch (Bristol) SPECIAL SESSIONS SPEAKERS: Eric Allender (Rutgers) Andrej Bauer (Ljubljana) Vasco Brattka (Cape Town) Douglas Bridges (Canterbury, NZ) John Case (Newark, Delaware) Pieter Collins (Amsterdam) Thierry Coquand (Goeteborg) Felix Costa (Lisbon) Barbara F. Csima (Waterloo) Abbas Edalat (London) Martin Escardo (Birmingham) Joerg Flum (Freiburg) Sergey S. Goncharov (Novosibirsk) Hajime Ishihara (Tokyo) Natasha Jonoska (Tampa, Florida) Michal Koucky (Prague) James Ladyman (Bristol) Maria Emilia Maietti (Padua) Giancarlo Mauri (Milan) Klaus Meer (Odense) Itamar Pitowsky (Jerusalem) Robert Rettinger (Hagen) Grzegorz Rozenberg (Leiden) Frank Stephan (Singapore) Neil Thapen (Prague) Giuseppe Trautteur (Naples) Heribert Vollmer (Hannover) Osamu Watanabe (Tokyo) Jiri Wiedermann (Prague) Damien Woods (Cork) Liang Yu (Nanjing) Martin Ziegler (Paderborn) WOMEN IN COMPUTABILITY WORKSHOP in association with the Computer Research Association's Committee on the Status of Women in Computing Research (CRA-W) Organisers: Paola Bonizzoni, Elvira Mayordomo. Speakers: Anne Condon (Vancouver), Natasha Jonoska (Florida), Carmen Leccardi (Milan), and others CONFIRMED SPONSORS OF CiE 2007: AILA (Associazione Italiana di Logica e Applicazioni), EATCS (European Association for Theoretical Computer Science), ASL (Association for Symbolic Logic), EACSL (European Association for Computer Science Logic), FoLLI (The Association of Logic, Language and Information), GNSAGA-INdAM (Gruppo Nazionale per le Strutture Algebriche e Geometriche e loro Applicazioni-Istituto NAzionale di Alta Matematica) and The University of Siena. * CiE 2007 will be co-located with CCA 2007, the annual CCA (Computability and Complexity in Analysis) Conference: http://cca-net.de/cca2007/ ************************************************************ From rrosebru@mta.ca Wed Mar 21 12:20:58 2007 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 21 Mar 2007 12:20:58 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HU2TG-0001Oc-PE for categories-list@mta.ca; Wed, 21 Mar 2007 12:11:26 -0300 To: categories@mta.ca Subject: categories: functions and polynomials From: Paul Taylor Date: Wed, 21 Mar 2007 11:06:44 +0000 Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: RO X-Status: X-Keywords: X-UID: 57 How widely applicable is the following idea? Let f: Z x Z -> Z be a binary FUNCTION (in the sense of sets) on the integers, with the property that - for each x:Z, f(x,-) : Z -> Z is a (agrees with a unique) POLYNOMIAL, whose coefficients are functions of x; and similarly - for each y:Z, f(-,y) : Z -> Z is also a polynomial. Then f(x,y) was itself a polynomial in two variables. This generalises to a disjoint union of sets of variables, ie to functions Z^X x Z^Y -> Z that are polynomials in one set of variables for each value of the other, and vice versa. The (possible) categorical generalisation is this: Let T be a strong monad on a topos, CCC or even a symmetric monoidal closed category, and K=T0 its free algebra. Then there is a natural transformation r_X: T X ---> K^(K^X), which we suppose to be mono. (How widely is this the case?) Then the above result states that (in that case) the square (K^Y) T (X + Y) >---------> TX V | V | | | | ----- | K^Y | | r_X | K^X | V r_Y V (K^X) >--------> (K^X x K^Y) TY K is a pullback (in fact, an intersection). I am primarily concerned with the case where T encodes the theory of frames over either Set or Dcpo, though if the result extends to commutative rings or other algebraic theories, that would be very interesting too. Paul Taylor From rrosebru@mta.ca Wed Mar 21 13:56:59 2007 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 21 Mar 2007 13:56:59 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HU44Q-00061J-Qw for categories-list@mta.ca; Wed, 21 Mar 2007 13:53:54 -0300 Content-Type: text/plain; charset=ISO-8859-1; delsp=yes; format=flowed Content-Transfer-Encoding: quoted-printable From: Francois Lamarche Subject: categories: Thesis Fellowship in Theoretical Computer Science Date: Wed, 21 Mar 2007 17:53:57 +0100 To: categories@mta.ca Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 58 THESIS FELLOWSHIP IN COMPUTER SCIENCE A three-year fellowship is available for a thesis in Computer Science, to be done in Nancy, in the east fo France, under the supervision of Francois Lamarche http://www.loria.fr/~lamarche SEMANTICS OF PROOFS IN CLASSICAL LOGIC During the last 2-3 years great progress has been made in our understanding of the semantics of proofs in classical logic [1][2][3], but there is still a lot to be done. The general theme of this this thesis project is the exploitation of the fruitful interaction between denotational semantics and syntax, an direction of research which began with the work of Dana Scott on the untyped lambda calculus, and has seen the invention of linear logic through Girard's observation of the category of coherence spaces and linear maps. The primary aim is to - first develop and write up a simple interpretation of classical logic in a category of posets, which is an unpublished byproduct of the denotational semantics given in [2], - then apply some of the insights given by that semantics to new approaches to proof nets for classical logic. Thus there is already some amount of material which simply has to be written up as a springboard, and should help the student pick up momentum before doing truly original research (we hasten to mention that a full mastery of the rather formidable [2] is not necessary at first for doing so). But the real interest of a thesis is to give students the occasion to prove their mettle, and we foresee plenty of openings here for doing that, with several open questions on correctness criteria, complexity, proof search, etc. In particular there is the tantalizing possibility of using non-commutative logics (that use braidings) to give a practical solution to the difficult problem of counting the number of axiom links that are used in a classical proof, which has connections to deep problems in complexity theory. Work and study environment The student would be registered at the Computer Science department one of the universities (or engineering school) which belong to the joint graduate studies program of the IAEM doctoral school. A sizeable proportion of the students registered in that school come from outside of France and Europe. Students are required to follow a moderate number of graduate courses, which are usually given in French. There are special programs aimed specifically atforeign graduate students, to help them learn French. Work will be done at the Loria laboratory of computer science http://www.loria.fr in Nancy, on the science campus. The student will be part of the Calligramme research project at INRIA-Lorraine. The student will be able to interact with everal research projects dealing with theoretical issues in computer science. The fellowship guarantees financing for three years; the student who does not complete the thesis work in that time span will be able to extend his/her stay through teaching contracts; but theses that last more than four years are exceptional and not encouraged by the authorities. Profile sought The candidate is required to have a Master's degree in Mathematics or Computer Science, with an orientation towards theoretical computer science. More precisely we expect experience in one or several of the the following topics: linear logic, the theory of {interaction, proof} nets, category theory, denotational semantics. An acquaintance with basics of deep inference is also a big plus. Procedure Putative candidates are requested to send an email to Fran=E7ois Lamarche for further enquiry (look at http://www.loria.fr/~lamarche for exact email address and http://www.loria.fr/~lamarche/TheseEnglish.html for the html version of this announcement.) [1] C. Fuhrmann and D. Pym: Order-enriched categorical models of the classical sequent calculus. *J. Pure and App. Algebra 204(1)*. [2] F. Lamarche: Exploring the gap between linear and classical logic. *Accepted for publication in Theory and Applications of Categories*. [3] F. Lamarche and L. Strassburger: Naming proofs in classical =20 logic, *TLCA 2005, in SLNCS 3461* From rrosebru@mta.ca Wed Mar 21 19:03:15 2007 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 21 Mar 2007 19:03:15 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HU8m1-0003fR-LL for categories-list@mta.ca; Wed, 21 Mar 2007 18:55:13 -0300 To: categories@mta.ca Subject: categories: functions not polynomials From: Paul Taylor Date: Wed, 21 Mar 2007 16:39:55 +0000 Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 59 Let f: Z x Z -> Z be a binary FUNCTION (in the sense of sets) on the integers, with the property that - for each x:Z, f(x,-) : Z -> Z is a (agrees with a unique) POLYNOMIAL, whose coefficients are functions of x; and similarly - for each y:Z, f(-,y) : Z -> Z is also a polynomial. Then f(x,y) was itself a polynomial in two variables. "You just use Newton's difference method to find the co..." .... unterexample. Taking N for simplicity first, consider the binomial coefficient (x,n) as an nth degree polynomial in x, ie (x,0) = 1 (x,1) = x (x,2) = x(x-1)/2 (x,3) = x(x-1)(x-2)/3! and so on. Newton's finite difference method provides the coefficients of these generating polynomials by taking successive differences (the finite analogue of successive derivatives). But then sum_n (x,n)(y,n) is a function NxN->N that is a polynomial in x for each y and vice versa but isn't itself a polynomial. None of the web pages that I found about this method was especially clear, so I'm not going to recommend any, but they are there if you want to look for them yourself. The more general method (as described on these pages, which is why I didn't think they were that good) takes differences from any sequence of points, not just 0, 1, 2, .... Hence, given any enumeration of a countable field K (this probably works for Z too) we can generalise both the method of fitting polynomials and the counterexample. Of course, since I'm a categorist, it was the categorical formulation that interests me. Any thoughts on that would be appreciated, despite the above failure of the simple example. In fact, I'd quite like to hear from any students of universal algebra out there who also know how monads encode algebraic theories, and might be willing to help as sparring partners for my present mad scheme. Paul Taylor From rrosebru@mta.ca Thu Mar 22 14:54:04 2007 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 22 Mar 2007 14:54:04 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HURLQ-0003Dh-VR for categories-list@mta.ca; Thu, 22 Mar 2007 14:45:00 -0300 Date: Wed, 21 Mar 2007 22:56:28 -0700 From: Vaughan Pratt MIME-Version: 1.0 To: categories@mta.ca Subject: categories: Re: functions not polynomials Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 60 The counterexample Paul cites of a function f(x,y) that is a univariate polynomial in x and y separately but not a bivariate polynomial in x and y jointly has the following "degree growth" property: (*) For each d in N, f(-,d) and f(d,-) are polynomials of degree <= d. As anyone who's played around with bicubic patches for computer graphics knows, the degree has to grow for such a counterexample since any global bound on the degree of f(x,-) and f(-,y) separately suffices for f(x,y) to be a polynomial in x and y jointly with the same degree bound (taking the degree of x^3 y^2 to be 3 rather than 5). The class of all functions of the above degree-growing form has the following nice characterization if we take real-valued rather than integer-valued functions (or any other algebraically closed field), still defined on N and NxN however. Let U be that subset of NxN --> R whose functions enjoy the above degree growth property (*). Define W: (NxN --> R) --> (N --> R) by Wf(x) = f(x,x) for all x in N. Theorem. The restriction of W to U is a bijection. (So if W is in some sense natural we have a natural bijection, about as close as I'm going to get to anything sounding at all categorical here.) Proof. Let g: N --> R be an arbitrary sequence of reals. We show by induction on the d in (*) that there exists a unique f in U for which Wf = g. Take the induction hypothesis to be that f(-,i) and f(i,-) are uniquely determined polynomials of degree at most d for all natural numbers i <= d. If the induction hypothesis holds for all d in N we have completely determined f. Base case. f(-,0) and f(0,-) are constant functions, whence for all natural numbers x,y, necessarily f(x,0) = f(0,y) = f(0,0) = g(0). Inductive step. Assuming the induction hypothesis for d, take f(d+1,d+1) = g(d+1). This determines f(i,d+1) and f(d+1,i) for all i from 0 to d+1, which in turn uniquely determines f(-,d+1) and f(d+1,-) as polynomials of degree d+1 (exactly one polynomial of degree d+1 passes through d+2 points). The induction hypothesis therefore holds for d+1. QED Corollary. The members of U are symmetric: f(x,y) = f(y,x). So the symmetry in Paul's example was not just an isolated artifact but an inevitable consequence of his rate of degree growth. QUESTION: For which g does W^{-1}(g) (of type NxN --> R) extend "nicely" to RxR --> R, for any given notion of niceness? For example if g is a polynomial of degree d then so is W^{-1}(g), giving the obvious extension to RxR as the same polynomial. What if g is periodic, ultimately constant, ultimately periodic, etc.? Vaughan Paul Taylor wrote: > Let f: Z x Z -> Z be a binary FUNCTION (in the sense of sets) > on the integers, with the property that > > - for each x:Z, f(x,-) : Z -> Z is a (agrees with a unique) > POLYNOMIAL, whose coefficients are functions of x; and similarly > > - for each y:Z, f(-,y) : Z -> Z is also a polynomial. > > Then f(x,y) was itself a polynomial in two variables. > > "You just use Newton's difference method to find the co..." > > .... unterexample. > > Taking N for simplicity first, consider the binomial coefficient > (x,n) as an nth degree polynomial in x, ie > (x,0) = 1 > (x,1) = x > (x,2) = x(x-1)/2 > (x,3) = x(x-1)(x-2)/3! > and so on. Newton's finite difference method provides the coefficients > of these generating polynomials by taking successive differences (the > finite analogue of successive derivatives). > > But then sum_n (x,n)(y,n) > is a function NxN->N that is a polynomial in x for each y and vice versa > but isn't itself a polynomial. From rrosebru@mta.ca Fri Mar 23 10:49:33 2007 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 23 Mar 2007 10:49:33 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HUk3B-0001pq-8k for categories-list@mta.ca; Fri, 23 Mar 2007 10:43:25 -0300 Date: Fri, 23 Mar 2007 10:37:09 +0000 From: Monika Seisenberger MIME-Version: 1.0 To: undisclosed-recipients:; Subject: categories: 2cfc: CALCO-jnr 2007: CALCO Young Researchers Workshop, Bergen, Norway Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 61 [Apologies for multiple copies] !!! PLEASE FORWARD TO PHD STUDENTS AND YOUNG RESEARCHERS !!! *------------------------------------------------------------------* * 2nd call for contributions * * * * CALCO-jnr 2007 * * * * CALCO-jnr: CALCO Young Researchers Workshop * * August 20, 2007, Bergen, Norway * * * * * * part of * * 2nd Conference on Algebra and Coalgebra in Computer Science * * August 20-24, 2007, Bergen, Norway * * * *------------------------------------------------------------------* * Abstract submission: April 10, 2007 * * Author notification: April 30, 2007 * * Final abstract due: May 16, 2007 * * Full paper submission: September 30, 2007 * *------------------------------------------------------------------* * http://www.ii.uib.no/calco07/ * *------------------------------------------------------------------* CALCO 2007 will be preceded by the CALCO Young Researchers Workshop, CALCO-jnr, dedicated to presentations by PhD students and young researchers at the beginning of their carriers. CALCO brings together researchers and practitioners to exchange new results related to foundational aspects and both traditional and emerging uses of algebras and coalgebras in computer science. The study of algebra and coalgebra relates to the data, process and structural aspects of software systems. This is a high-level, bi-annual conference formed by joining the forces and reputations of CMCS (the International Workshop on Coalgebraic Methods in Computer Science), and WADT (the Workshop on Algebraic Development Techniques). The first, and very successful, CALCO conference took place 2005 in Swansea, Wales. The second event will take place 2007 in Bergen, Norway. The CALCO Young Researchers Workshop, CALCO-jnr, is a CALCO satellite workshop dedicated to presentations by PhD students and by those who have completed their doctoral studies within the past few years. Attendance at the workshop is open to all - it is anticipated that many CALCO conference participants will want to attend the CALCO-jnr workshop (and vice versa). CALCO-jnr presentations will be selected according to originality, significance, and general interest, on the basis of submitted 2-page abstracts, by the organisers. A booklet with the abstracts of the accepted presentations will be available at the workshop. After the workshop, the author(s) of each presentation will be invited to submit a full 10-15 page paper on the same topic. They will also be asked to write (anonymous) reviews of papers submitted by other authors on related topics. Additional reviewing and the final selection of papers will be carried out by the CALCO-jnr PC. The volume of selected papers from the workshop will be published as a Department of informatics, University of Bergen, technical report, and it will also be made available in an open access database searchable from http://oaister.umdl.umich.edu/o/oaister/. Authors will retain copyright, and are also encouraged to disseminate the results reported at CALCO-jnr by subsequent publication elsewhere. Topics of Interest ------------------ The CALCO Young Researchers Workshop will invite submissions on the same topics as the CALCO conference: reporting results of theoretical work on the mathematics of algebras and coalgebras, the way these results can support methods and techniques for software development, as well as experience with the transition of resulting technologies into industrial practise. In particular, the workshop will encourage submissions included or related to the topics listed below. * Abstract models and logics - Automata and languages, - Categorical semantics, - Modal logics, - Relational systems, - Graph transformation, - Term rewriting, - Adhesive categories * Specialised models and calculi - Hybrid, probabilistic, and timed systems, - Calculi and models of concurrent, distributed, mobile, and context-aware computing, - General systems theory and computational models (chemical, biological, etc) * Algebraic and coalgebraic semantics - Abstract data types, - Inductive and coinductive methods, - Re-engineering techniques (program transformation), - Semantics of conceptual modelling methods and techniques, - Semantics of programming languages * System specification and verification - Algebraic and coalgebraic specification, - Formal testing and quality assurance, - Validation and verification, - Generative programming and model-driven development, - Models, correctness and (re)configuration of hardware/middleware/architectures, - Process algebra Submission ---------- Submission is by e-mail to calco-jnr@ii.uib.no Important Dates (all dates in 2007) ----------------------------------- 10 April Firm deadline for 2-page abstract submission 30 April Notification of abstract selection decision 16 May Final version of abstract due Early registration ends 20 August CALCO Young Researchers Workshop 21-24 August CALCO conference technical program 30 September Firm deadline for 10-15 page paper submission 15 November Notification of paper selection decision 30 November Final version of paper due Program Committee ----------------- * Magne Haveraaen, University of Bergen, Norway http://www.ii.uib.no/~magne/ * John Power, University of Edinburgh, UK http://www.inf.ed.ac.uk/people/staff/John_Power.html * Monika Seisenberger, University of Wales Swansea, UK http://www.cs.swan.ac.uk/~csmona/ -- http://www.ii.uib.no/calco07/ From rrosebru@mta.ca Tue Mar 27 08:56:35 2007 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 27 Mar 2007 08:56:35 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HWA8i-0000Li-5E for categories-list@mta.ca; Tue, 27 Mar 2007 08:47:00 -0300 Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed Content-Transfer-Encoding: 7bit From: Marco Grandis Subject: categories: A preprint on Weak cubical categories Date: Tue, 27 Mar 2007 11:30:29 +0200 To: categories@mta.ca Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 62 The following preprint is available on my server: M. Grandis, Higher cospans and weak cubical categories (Cospans in Algebraic Topology, I) Dip. Mat. Univ. Genova, Preprint 552 (2007). in pdf and ps: http://www.dima.unige.it/~grandis/wCub.pdf http://www.dima.unige.it/~grandis/wCub.ps Comments and suggestions are appreciated. Marco Grandis ---------------------- Abstract. We define a notion of weak cubical category, abstracted from the structure of n-cubical cospans x: \Lambda^n ---> X in a category X, where \Lambda is the 'formal cospan' category. These diagrams form a cubical set with compositions in all directions, which are computed with pushouts and behave 'categorically' in a weak sense, up to suitable comparisons. Actually, we work with a 'symmetric cubical structure', which includes the transposition symmetries, because this allows for a strong simplification of the coherence conditions. These notions will be used in subsequent papers to study topological cospans and their use in Algebraic Topology, from tangles to cobordisms of manifolds. We also introduce the more general notion of a multiple category, where - to start with - arrows belong to different sorts, varying in a countable family and symmetries must be dropped. The present examples seem to show that the symmetric cubical case is better suited for topological applications. Mathematics Subject Classifications: 18D05, 55U10 Key words: weak cubical category, multiple category, double category, cubical sets, spans, cospans. ---------------------- From rrosebru@mta.ca Tue Mar 27 08:56:36 2007 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 27 Mar 2007 08:56:36 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HWA7D-0000Fm-SZ for categories-list@mta.ca; Tue, 27 Mar 2007 08:45:27 -0300 Date: Mon, 26 Mar 2007 12:26:07 -0700 From: Vaughan Pratt MIME-Version: 1.0 To: categories@mta.ca Subject: categories: Re: functions not polynomials Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 63 A couple of days ago, in response to a post to this list by Paul Taylor, I showed that W: (NxN --> R) --> (N --> R), defined as W(f)(x) = f(x,x), is bijective on the subset U of NxN --> R consisting of those f: NxN --> R for which f(-,d) and f(d,-) are polynomials of degree d for each d in N. As an afterthought I raised the question, for which g: N --> R can W^{-1}(g): NxN --> R be extended to RxR --> R? To get some idea of what could happen I wrote the following program wttmo.c (W To The Minus One). =====wttmo.c===== > #include > > int main(int argc, char *argv[]) > { > int i, j, m, n; > double a[100], f[100][100]; > n = argc - 1; > for (i = 0; i < n; i++) /* Input */ > f[i][i] = atof(argv[i+1]); > for (m = 0; m < n-1; m++) { /* Process */ > for (i = 0; i <= m; i++) > a[i] = f[m][i]; > for (i = 0; i < m; i++) > for (j = 0; j < m-i; j++) > a[j] = a[j+1] - a[j]; > for (i = m+1; i < n; i++) { > for (j = 0; j < m; j++) > a[j+1] += a[j]; > f[i][m] = f[m][i] = a[m]; > } > } > for (i = 0; i < n; i++) { /* Output */ > for (j = 0; j < n; j++) > printf("%-7.3f ", f[i][j]); > printf("\n"); > } > } ================= (Note that this program gives a well-defined result not just for the reals but for any group, even a nonabelian one, since the only operations performed are addition and subtraction. This generality can be reconciled with the original problem, and with my proof of bijectivity of W on U, by saying that a sequence s obeys a polynomial law of degree (at most) d just when the d-th finite difference D^d(s) is a constant sequence, where the finite difference operator D(s) replaces each s_i by s_{i+1}-s_i in s.) This program is run from the command line with n real parameters constituting the first n elements g(0), g(1), ..., g(n-1) of a sequence g. The output is W^{-1}(g), laid out as an nxn matrix with the entry at row i and column j (numbering from 0) giving W^{-1}(g)(i,j) for i and j from 0 to n-1. Applying it to the polynomial 2 + 3x^2 gives the following result, $ wttmo 2 5 14 29 50 77 110 149 194 2.000 2.000 2.000 2.000 2.000 2.000 2.000 2.000 2.000 2.000 5.000 8.000 11.000 14.000 17.000 20.000 23.000 26.000 2.000 8.000 14.000 20.000 26.000 32.000 38.000 44.000 50.000 2.000 11.000 20.000 29.000 38.000 47.000 56.000 65.000 74.000 2.000 14.000 26.000 38.000 50.000 62.000 74.000 86.000 98.000 2.000 17.000 32.000 47.000 62.000 77.000 92.000 107.000 122.000 2.000 20.000 38.000 56.000 74.000 92.000 110.000 128.000 146.000 2.000 23.000 44.000 65.000 86.000 107.000 128.000 149.000 170.000 2.000 26.000 50.000 74.000 98.000 122.000 146.000 170.000 194.000 consistent with producing f(x,y) = 2 + 3xy. This of course extends in the usual way to RxR --> R. Nudging the first two elements very slightly $ wttmo 2.001 5.001 14 29 50 77 110 149 194 2.001 2.001 2.001 2.001 2.001 2.001 2.001 2.001 2.001 2.001 5.001 8.001 11.001 14.001 17.001 20.001 23.001 26.001 2.001 8.001 14.000 19.998 25.995 31.991 37.986 43.980 49.973 2.001 11.001 19.998 29.000 38.015 47.051 56.116 65.218 74.365 2.001 14.001 25.995 38.015 50.000 61.796 73.156 83.740 93.115 2.001 17.001 31.991 47.051 61.796 77.000 96.220 127.420 184.595 2.001 20.001 37.986 56.116 73.156 96.220 110.000 5.480 -531.865 2.001 23.001 43.980 65.218 83.740 127.420 5.480 149.000 4915.055 2.001 26.001 49.973 74.365 93.115 184.595 -531.865 4915.055 194.000 really shakes things up (look at f(i+1)(i), especially the region 38.015,61.796,96.220,5.480,4915.055 which used to be 38,62,92,128,170). The prospects for extending this evidently chaotic function NxN --> R to RxR --> R "nicely" look pretty bad -- at the very least it would seem to require a very liberal notion of "nice". In my previous post I claimed that W^{-1} maps polynomials to polynomials, but realized later that the only polynomials for which this was the case were those of the form g(x) = a + bx^2 for arbitrary constants a and b, for which W^{-1}(g) is f(x,y) = a + bxy. The simplest polynomial not mapped to a polynomial is the identity function, g(x) = x: $ wttmo 0 1 2 3 4 5 6 7 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 1.000 2.000 3.000 4.000 5.000 6.000 7.000 0.000 2.000 2.000 0.000 -4.000 -10.000 -18.000 -28.000 0.000 3.000 0.000 3.000 24.000 75.000 168.000 315.000 0.000 4.000 -4.000 24.000 4.000 -280.000 -1176.000 -3164.000 0.000 5.000 -10.000 75.000 -280.000 5.000 5910.000 28595.000 0.000 6.000 -18.000 168.000 -1176.000 5910.000 6.000 -171528.000 0.000 7.000 -28.000 315.000 -3164.000 28595.000 -171528.000 7.000 Very unfunctorial of wttmo. :) In GF(2) (suitably modifying the program, including writing # for 1 and space for 0 in the output for better contrast), wttmo maps the identity polynomial x = 0,1,0,1,0,1,... to xy, which is as one would expect given that x = x^2 in GF(2). More interestingly it maps the sequence 1,0,0,0,0,... to the Sierpinski gasket, shown here for the top left 32x32 elements of f. ################################ # # # # # # # # # # # # # # # # ## ## ## ## ## ## ## ## # # # # # # # # #### #### #### #### # # # # # # # # ## ## ## ## # # # # ######## ######## # # # # # # # # ## ## ## ## # # # # #### #### # # # # ## ## # # ################ # # # # # # # # ## ## ## ## # # # # #### #### # # # # ## ## # # ######## # # # # ## ## # # #### # # ## # It is tempting to infer the fractal nature of wttmo from this. However the Sierpinski gasket also arises as Pascal's triangle mod 2, so perhaps one shouldn't read too much into this. Vaughan Pratt From rrosebru@mta.ca Thu Mar 29 23:28:10 2007 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 29 Mar 2007 23:28:10 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HX6gy-0003ZN-9K for categories-list@mta.ca; Thu, 29 Mar 2007 23:18:16 -0300 From: Rob van Glabbeek and Matthew Hennessy To: categories@mta.ca Date: Thu, 29 Mar 2007 11:05:41 +1000 Subject: categories: SOS 2007 - Final Call for Papers Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 64 Structural Operational Semantics 2007 An Affiliated Workshop of LICS 2007 and ICALP 2007 July 9, 2007, Wroclaw, Poland http://www.cse.unsw.edu.au/~rvg/SOS2007 Aim: Structural operational semantics (SOS) provides a framework for giving operational semantics to programming and specification languages. A growing number of programming languages from commercial and academic spheres have been given usable semantic descriptions by means of structural operational semantics. Because of its intuitive appeal and flexibility, structural operational semantics has found considerable application in the study of the semantics of concurrent processes. Moreover, it is becoming a viable alternative to denotational semantics in the static analysis of programs, and in proving compiler correctness. Recently, structural operational semantics has been successfully applied as a formal tool to establish results that hold for classes of process description languages. This has allowed for the generalisation of well-known results in the field of process algebra, and for the development of a meta-theory for process calculi based on the realization that many of the results in this field only depend upon general semantic properties of language constructs. This workshop aims at being a forum for researchers, students and practitioners interested in new developments, and directions for future investigation, in the field of structural operational semantics. One of the specific goals of the workshop is to establish synergies between the concurrency and programming language communities working on the theory and practice of SOS. Moreover, it aims at widening the knowledge of SOS among postgraduate students and young researchers worldwide. Specific topics of interest include (but are not limited to): * programming languages * process algebras * higher-order formalisms * rule formats for operational specifications * meaning of operational specifications * comparisons between denotational, axiomatic and SOS * compositionality of modal logics with respect to operational specifications * congruence with respect to behavioural equivalences * conservative extensions * derivation of proof rules from operational specifications * software tools that automate, or are based on, SOS. Papers reporting on applications of SOS to software engineering and other areas of computer science are welcome. History: The first SOS Workshop took place on the 30th of August 2004 in London as one of the satellite workshops of CONCUR 2004. Subsequently, SOS 2005 occurred on the 10th of July 2005 in Lisbon as a satellite workshop of ICALP 2005, and SOS 2006 on the 26th of August 2006 in Bonn as a satellite workshop of CONCUR 2006. A special issue of the Journal of Logic and Algebraic Programming on Structural Operational Semantics appeared in 2004; a special issue of Theoretical Computer Science dedicated to SOS 2005 is in press, and a special issue of Information & Computation on Structural Operational Semantics inspired by SOS 2006 is in preparation. INVITED SPEAKER: Pawel Sobocinski (Cambridge, UK) PAPER SUBMISSION: We solicit unpublished papers reporting on original research on the general theme of SOS. Prospective authors should register their intention to submit a paper by uploading a title and abstract via the workshop web page by: *** Friday 6 April 2007. *** Papers should take the form of a pdf file in ENTCS format [http://www.entcs.org/], whose length should not exceed 15 pages (not including an optional "Appendix for referees" containing proofs that will not be included in the final paper). We will also consider 5-page papers describing tools to be demonstrated at the workshop. Proceedings: Preliminary proceedings will be available at the meeting. The final proceedings of the workshop will appear as a volume in the ENTCS series. We may decide to arrange a special issue of an archival journal devoted to full versions of selected papers from the workshop. IMPORTANT DATES: * Submission of abstract: Friday 6 April 2007 * Submission: Sunday 15 April 2007 * Notification: Wednesday 9 May 2007 * Final version: Friday 25 May 2007 * Workshop: Monday 9 July 2007 * Final ENTCS version: Friday 10 August 2007. PROGRAMME COMMITTEE Luca Aceto (Aalborg, DK; Reykjavik, IS) Rocco De Nicola (Florence, IT) Rob van Glabbeek (NICTA, AU, co-chair) Reiko Heckel (Leicester, UK) Matthew Hennessy (Sussex, UK, co-chair) Bartek Klin (Warsaw, PL) Ugo Montanari (Pisa, IT) MohammadReza Mousavi (Eindhoven, NL; Reykjavik, IS) Prakash Panangaden (Montreal, CA) Grigore Rosu (Urbana-Champaign, IL, USA) Simone Tini (Insubria, I) Shoji Yuen (Nagoya, JP) CONTACT: sos2007@cs.stanford.edu WORKSHOP ORGANISERS: Rob van Glabbeek National ICT Australia Locked Bag 6016 University of New South Wales Sydney, NSW 1466 Australia Matthew Hennessy Department of Informatics University of Sussex Falmer, Brighton, BN1 9QN United Kingdom From rrosebru@mta.ca Thu Mar 29 23:28:10 2007 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Thu, 29 Mar 2007 23:28:10 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HX6he-0003cv-6X for categories-list@mta.ca; Thu, 29 Mar 2007 23:18:58 -0300 Date: Wed, 28 Mar 2007 20:47:27 -0700 From: Vaughan Pratt MIME-Version: 1.0 To: categories list Subject: categories: Re: functions not polynomials Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 65 Paul Taylor's example of an f(x,y) that is polynomial separately in x and y but not jointly was sum_n (x,n)(y,n) (where (x,n) denotes the binomial coefficient x!/(n!(x-n)!)). After mulling over that example some more it occurred to me that it can be analyzed via the observation that W^{-1} maps the polynomial P_n(x) = (x(x-1)(x-2)...(x-(n-1)))^2 to the polynomial xy(x-1)(y-1)(x-2)(y-2)...(x-(n-1))(y-(n-1)). This contradicts my earlier claim that the only polynomials in x that W^{-1} maps to polynomials in x and y are the linear combinations of 1 and x^2. These two are easily seen to be the only *monomials* so mapped, but (the linearity of W^{-1} notwithstanding) it does not follow that the only *polynomials* so mapped are the linear combinations of these two monomials. W^{-1} maps sum_n P_n(x)/(n!)^2 to Paul's example. The coefficient 1/(n!)^2 of P_n(x) seems to play no role here, and any coefficients should do as long as infinitely many are nonzero (to make f(x,y) not a polynomial). To extend the example (as a function on N^2) directly (via the constituent polynomials) to a function on the positive reals however, the coefficients would need to grow somewhat slower than 4^n, |P_n(x)| being bounded above by at best about 1/4^n for 0 < x < n (the half-integer points for x in that range give a good approximation of the bound). 1/(n!)^2 is more than slow enough for this purpose. A simpler example is g(x) = (2x,x) (again the binomial coefficient), which W^{-1} maps to f(x,y) = (x+y,x), polynomial separately in x and y but not jointly. That is, Pascal's triangle is a sufficient counterexample for Paul's purposes. Moreover the Gamma function gives a nicer (log-convex in fact) extension of f(x,y) to the upper right quadrant of R^2. Vaughan Pratt From rrosebru@mta.ca Fri Mar 30 19:12:30 2007 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 30 Mar 2007 19:12:30 -0300 Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HXPDR-0002mB-00 for categories-list@mta.ca; Fri, 30 Mar 2007 19:05:01 -0300 Date: Fri, 30 Mar 2007 18:44:37 +0100 From: Robin Houston To: Categories List Subject: categories: Full and faithful Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Sender: cat-dist@mta.ca Precedence: bulk Message-Id: Status: O X-Status: X-Keywords: X-UID: 66 A functor F: C -> D is full and faithful just when, for all categories X and functors G, H: X -> C, the whiskering action of F induces a bijection between [G, H] and [FG, FH] (where [G, H] denotes the set of natural transformations from G to H). Clearly this formulation makes sense in any bicategory. Is there a name for 1-cells with this property? Thanks! Robin