November 2001 - Categories - categories.org.au

Only two SMC structures on Cat?
by Jason C Reed 27 Jul '02

27 Jul '02

Power, A.J. and Robinson, E.P. Premonoidal categories and notions of computation (ftp://ftp.dcs.qmw.ac.uk/pub/lfp/edmundr/premoncat.ps.gz) in section 2 asserts that there is excatly one symmetric monoidal closed structure on Cat besides the cartesian one. Does anyone know [the location of] a proof? ---Jason

3 2

paperback announcement: Categorical Logic and Type Theory
by Bart Jacobs 16 Mar '02

16 Mar '02

Dear Colleague, I am happy to announce that Elsevier has now published a paperback version of my book B. Jacobs, Categorical Logic and Type Theory Studies in Logic and the Foundations of Mathematics 141, North Holland, Elsevier, 1999. 780 pages. The regular price of the paperback is NLG 150 / Euro 68.07 / US$ 74 Elsevier now offers a discount of 25% for this paperback if you order before 31 july 2001, using the attached form. In that case the price is: NLG 112.50 / Euro 51 / US$ 55.50. If you wish to use this special offer, please fill in the form, and send it in time to Andy Deelen at Elsevier (precise address at bottom of the form). Do not send it to me. The book gives a survey of categorical logic and type theory starting from the unifying concept of a fibration. Its intended audience consists of logicians, type theorists, category theorists and (theoretical) computer scientists. It contains the following chapters. Prospectus Introduction to fibred category theory Simple type theory Equational Logic First order predicate logic Higher order predicate logic The effective topos Internal category theory Polymorphic type theory Advanced fibred category theory First order dependent type theory Higher order dependent type theory References Notation index Subject index More information can be obtained from the authors webpage: http://www.cs.kun.nl/~bart/CLT/bookinfo.html Bart Jacobs, Dep. Comp. Sci., Univ. Nijmegen, P.O. Box 9010, 6500 GL Nijmegen, The Netherlands. Email: bart(a)cs.kun.nl PS. Please pass this information on to your institute's librarian.

2 1

the walking adjunction and biadjunction
by baez＠math.ucr.edu 06 Dec '01

06 Dec '01

Here's some more stuff some of you might like, taken from http://math.ucr.edu/home/baez/week174.html Again, pardon the tone - it's written for nonexperts. If any of you know literature on the "walking biadjunction", I'd be interested! Best, jb ....................................................................... Now I'm going to dive in and pick up right where I left off in my discussion of the ideas behind this paper: 2) Michael Mueger, From subfactors to categories and topology I: Frobenius algebras in and Morita equivalence of tensor categories, available at math.CT/0111204. My ultimate goal is to take you to an elegant understanding of Frobenius algebras by means of a 2-category called the "walking biadjunction", but first I'll play around a bit with a simpler but more famous 2-category called the "walking adjunction". This may sound scary, but if you can stick with it, you'll see that I'm really just using these 2-categories to describe fun games that you can play with certain 2-dimensional pictures. Even if you don't read the words, please stare at the pictures - I spend my Thanksgiving weekend drawing them, and I don't want that work to go to waste! Category theorists love to talk about adjoint functors, but 2-category theorists know that these are just a special example of an "adjunction". An adjunction is something that makes sense in any 2-category; if we take the 2-category to be Cat we get adjoint functors. There are lots of other nice examples that make this generalization worthwhile. For example, in "week83" I explained how a pair of dual vector spaces is also an example of an adjunction. To study adjunctions, it suffices to study the "walking adjunction". This is a little 2-category containing exactly the stuff any adjunction in any 2-category must have: not a jot more, not a tiddle less! It was first studied by Schanuel and Street: 3) Stephen Schanuel and Ross Street, The free adjunction, Cah. Top. Geom. Diff. 27 (1986), 81-83. In a bit more detail, the walking adjunction is the 2-category freely generated by two objects: a and b, two morphisms: L: a -> b and R: b -> a, and two 2-morphisms, called the "unit" and "counit": i: 1_a => LR and e: RL => 1_b satisfying two relations, called the "triangle equations". I wrote down these equations already last week, but let me do it again using "string diagrams", as explained in "week79" and "week92". In a 2-categorical string diagram, objects are denoted by 2d regions in the plane, morphisms are denoted by 1d edges, and 2-morphisms are denoted by 0d points. If the dimensions look sort of upside-down, you're right - that's exactly the point! Instead of explaining the whole theory, I'll just plunge in with the example at hand. The unit i looks like this: i / \ L R / \ a / b \ a while the counit e looks like this: b \ a / b R L \ / \ / e Note that as you cross a line labelled "L" from left to right, you go from region a to region b, which is our way of saying that L: a -> b. Similarly, as you cross a line labelled "R" from left to right, you go from region b to region a, since R: b -> a. In terms of string diagrams, the triangle equations just say that we can straighten out a zig-zag: | | i | | / \ L | a / \ | | / \ | | | R / = a L b | \ / | L \ / b | | e | | | or a zag-zig: | | | i | R / \ | | / \ a | | / \ | \ L | = b R a \ / | | b \ / R | e | | | | We can build any 2-morphism in the walking adjunction by vertically and horizontally composing units and counits, which corresponds to sticking together string diagrams in a vertical or horizontal way. Thus, a typical 2-morphism looks like this: \ \ a / \ a / / | \ R L R L / i | \ \ / \ / / / \ L \ \ / \ / / a / R | b \ e e / / \ | a L R \ \ / \ b / i \ \ / \ / / \ L e \ / L R \ \ / / b \ \ By the triangle equations, we could straighten out the zig-zag without changing the 2-morphism. As you may know, the word "anaranjado" means "orange" in Spanish - there was no word in English for "orange" before people in England started importing oranges from Spain. And this is a nice mnemonic, because if we take the above picture and paint the regions labelled "a" orange, and paint the regions labelled "b" black, the above picture has a roughly tiger-striped appearance. In fact, these tiger stripes tell you everything you need to know about the 2-morphism! For example, starting from just this: \ \ a / \ a / / | \ \ / \ / / _ | \ \ / \ / / / \ | \ \_/ \_/ / a / \ | b \ / / \ | a \ / \ \ / \ b / _ \ \_/ \ / / \ \ \ / / \ \ \ / / b \ \ you can figure out where everything else should go. By the way, note that orange stripes can disappear can appear as we go down the page, and they can split, but they can't appear or merge. Black stripes can appear or merge, but they can't disappear or split. As a result, there can never be any orange or black *spots*. We'll change these rules later, when we talk about the "walking biadjunction". Okay, so we've got this 2-category, the walking adjunction: let's call it Ad for short. It's pretty simple. How can we understand it better? Well, for any two objects a and b in a 2-category we get a "hom-category" hom(a,b), whose objects are the morphisms from a to b, and whose morphisms are the 2-morphisms between those. If we work out these hom-categories in Ad, we get some cool stuff. First let's look at the hom-category hom(a,a). In this category, the objects are 1_a, LR, LRLR, LRLRLR, .... and all the morphisms are built by sticking these two basic generators together vertically or horizontally: \ \ a / / \ \ / / L R L R \ \ / / a \ \ / / a \ e / \ / | b | | | L R | | | | and i / \ a | | a | b | | | L R | | | | In tiger language, we're talking about pictures of black stripes on an orange background. The two basic generators are the merging of two black stripes and the appearance of a black stripe. If you read "week89", you'll know another way to describe this! Our ability to stick together pictures vertically and horizontally makes hom(a,a) into a "monoidal category". LR is a "monoid object", with merging of two black stripes being "multiplication", and the appearance of a black stripe being the "multiplicative identity". Being a "monoid object" simply means that these operations satisfy the left unit law: / / | | / / | | / / | | /\ / / | | \ \ / / | | \ \ / / | | \ \ / / a | | \ \/ / |b| | / = | | a | | | | a | | | | |b| | | | | a | | | | | | | | | | | | | | and its mirror image, called the right unit law, together with the associative law: \ \ a / / / / \ \ \ \ a / / \ \ / / a / / \ \ a \ \ / / \ \/ / / / \ \ \ \/ / \ / / / \ \ \ / \ \ / / \ \ / / \ \_/ / \ \_/ / \ / \ / | | | | a | | a a | | a | | = | | |b| |b| | | | | | | | | | | | | | | | | There aren't any other laws, so hom(a,a) is the "free monoidal category on a monoid object", or if you prefer, the "walking monoid"! I touched upon the immense consequences of this fact for algebraic topology in "week117" and "week118". They mainly rely on another way of thinking about hom(a,a): it's the category of order-preserving maps between finite ordinals! For example, these black tiger stripes on an orange background: 0 1 2 3 -------------------------------------------------------- | \ \ a | | a / / | | | | \ \ | | / / _ | | | | \ \ | | / / / \ | | | | \ \_/ \_/ / a / \ | | | | \ / \ \ | | | | a \ / \ \ / / | | \ b / _ \ \_/ / | | \ / / \ \ / | | \ / / b \ \ b / a | | \ / / \ \ | | -------------------------------------------------------- 0 1 2 correspond to the order-preserving map f: {0,1,2,3} -> {0,1,2} with f(0) = 0, f(1) = 0, f(2) = 0, f(3) = 2. Just read the stripes down! A more geometrical way to say the same thing is to call hom(a,a) the category of "simplices", usually denoted Delta. Here the object |---n+1 of them---| LRLR..........LRLR corresponds to the n-simplex, and these morphisms: -i.LRLR--> --i.LR-> -LR.i.LR-> 1_a --i--> LR --LR.i-> LRLR -LRLR.i--> LRLRLR ... <-L.e.R- <-L.e.RLR- <-LRL.e.R- are the basic "face" and "degeneracy" maps between simplices, which you'll find in any book on algebraic topology. The n-simplex is a face of the (n+1)-simplex in n+1 ways, and there are n basic degenerate ways to map the (n+1)-simplex down to the n-simplex. These aren't *all* the morphisms; just enough to generate all the rest by composition - i.e., sticking together pictures vertically, but *not* horizontally. Perhaps I should explain the notation here a bit more. Readers of "week80" will know that I use a dot to denote horizontal composition of 2-morphisms. For example, when we have a couple of 2-morphisms like this: f f' ---->---- ---->---- / || \ / || \ S: f => g x || S y || T z T: f' => g' \ \/ / \ \/ / ---->---- ---->---- g g' we get a 2-morphism like this: ff' -------->------- / || \ x || S.T z S.T: ff' => gg' \ \/ / -------->------- gg' But sometimes we can also horizontally compose a morphism and a 2-morphism! We can do it whenever our morphism f looks like a little "whisker" f sticking out of the 2-morphism T: f' ---->---- f / || \ x----->-----y || T z T: f' => g' \ \/ / ---->---- g' and what we get is a 2-morphism f.S like this: ff' -------->------- / || \ x || f.T z f.T: ff' => fg' \ \/ / -------->------- fg' This process, called "whiskering", is not really a new operation. f.S is really just the horizontal composite of these 2-morphisms: f f' ---->---- ---->---- / || \ / || \ x ||1_f y || S z \ \/ / \ \/ / ---->---- ---->---- f g' Similarly we can define T.f in this sort of situation: f' ---->---- / || \ f T: f' => g' x || T y----->-----z T.f: f'f => g'f \ \/ / ---->---- g' Anyway, once you're an expert on this 2-categorical yoga, you can easily see that these morphisms in hom(a,a), which are really 2-morphisms in Ad: -i.LRLR--> --i.LR-> -LR.i.LR-> 1_a --i--> LR --LR.i-> LRLR -LRLR.i--> LRLRLR ... <-L.e.R- <-L.e.RLR- <-LRL.e.R- are obtained by taking our basic tiger stripe operations - the "merging of two black stripes", or L.e.R, and the "appearance of a black stripe", or i - and drawing some extra black stripes on both sides. That's what those LR's are for. After all, no tiger is complete without whiskers! Okay. Now, having understood hom(a,a) in all these ways, let's turn to hom(b,b). Luckily, this is very similar! Here the objects are 1_b, RL, RLRL, RLRLRL, .... and morphisms are pictures of *orange* stripes on a *black* background: \ a / \ a / / | \ / \ / / _ | \ / \ / / / \ | \_/ \_/ / a / \ | b / / \ | / \ \ / b / _ \ \_/ / / \ \ / / \ \ / / b \ \ These orange stripes can only split: | | | | R L | | | a | / \ / i \ b / / \ \ b / / \ \ R L R L / / \ \ / / b \ \ or disappear: | | b | a | b | | R L | | | | \ / e as we march down the page. This means is that hom(b,b) is Delta^{op}: the *opposite* of the category of simplices, the *opposite* of the category of finite ordinals, or the walking *comonoid* - which is just like a monoid, only upside down! Here is another picture of hom(b,b): --R.i.LRL-> --R.i.L-> --RLR.i.L-> 1_b <--e-- RL <--e.RL-- RLRL <--e.RLRL-- RLRLRL ... <--RL.e-- <--RL.e.RL- <--RLRL.e-- If you're a devoted reader of This Week's Finds, you'll know I secretly drew this category already in section N of "week118". There I was talking about specific adjoint functors instead of the walking adjunction, so as not to prematurely blow your mind. I was also writing horizontal composites backwards, for certain old-fashioned reasons. But the idea is exactly the same! The morphisms above give the usual "face and degeneracy maps" we always have in a simplicial set, since a simplicial set is a functor F: Delta^{op} -> Set. By the way, you may have noticed that to get from hom(a,a) to hom(b,b), we had to switch the colors orange and black AND read the pictures upside-down. The reason is that if we turn around all the 1-morphisms AND 2-morphisms in the walking adjunction, we get the walking adjunction again. Ponder that! We can summarize what we've learned so far using the "Platonic idea" jargon I introduced last week: The Platonic idea of a monoid and the Platonic idea of a comonoid are the hom-categories hom(a,a) and hom(b,b) sitting inside the Platonic idea of an adjunction! (By the way, to round this off we should really describe hom(a,b) and hom(b,a), too. I think hom(a,b) is the Platonic idea of "an object with a left action of a monoid and a right coaction of a comonoid, in a compatible way". If so, hom(b,a) would be the Platonic idea of "an object with a right action of a monoid and a left coaction of a comonoid, in a compatible way". By "compatible" I'm saying that we can act on one side and coact on the other side in either order, and get the same thing. Filling in the details requires concepts I'm not eager to discuss right now, so I leave this as an exercise for the highly energetic reader. The less energetic reader can just study the tiger-stripe descriptions of these categories.) Finally, here's Mueger's new twist on all these ideas! Better than an adjunction is a "biadjunction". This has some extra structure, which turns out to explain all sorts of fancy-sounding stuff people look at in the study of subfactors and TQFTs and the like.... But what's a "biadjunction"? A biadjunction is where you have a morphism L: a -> b in a 2-category that is both left and right adjoint to R: b -> a. More precisely, a "biadjunction" is a setup (a,b,L,R,i,e,j,f) where (a,b,L,R,i,e) and (b,a,R,L,j,f) are both adjunctions. In terms of string diagrams, our generating 2-morphisms look like this: i j / \ / \ L R R L / \ / \ a / b \ a b / a \ b b \ a / b a \ b / a R L L R \ / \ / \ / \ / e f and the triangle equations say all possible zig-zags can be straightened out. Now let's study the "walking biadjunction", BiAd. As before, 2-morphisms in BiAd can be described using pictures with orange and black stripes - but now *both* kinds of stripes can appear, disappear, merge or split as we march down the page: ------------------------------------------------------- | \ \ a | | a / / | | | \ \ | | / / | | | \ \__/ \__/ / a | | | \ _____ / _____ | | | \ / a \ / / \ | | | a / / ___ \ / / \ / | | / / / \ \ / / __ \_/ | | / / \ b / / / / / \ | | / b \ \_/ / / / / a \ b | | / \ / / / / \ | ------------------------------------------------------- This allows for quite arbitrary ways of cutting up a rectangle into regions of orange and black, with piecewise linear boundaries, subject to the condition that each vertical border has the same color all along it. The triangle equations and the rules for 2-categories say that we can warp such a picture around without changing the 2-morphism that it defines... I don't want to be too precise here, since it would be boring. Hopefully you get the idea: BiAd has a purely topological description! Now for the punchline: in BiAd, what is the category hom(a,a) like? As in Ad, the objects are 1_a, LR, LRLR, LRLRLR, ... but now the object LR is equipped not only with multiplication: \ \ a / / \ \ / / L R L R \ \ / / a \ \ / / a \ e / multiplication: \ / L.e.R: LRLR => LR | b | | | L R | | | | and multiplicative identity: i / \ a | | a multiplicative | b | identity: | | i: 1_a => LR L R | | | | but also a "comultiplication": | | | | L R | | | b | / \ / j \ comultiplication: a / / \ \ a L.j.R: LR => LRLR / / \ \ L R L R / / \ \ / / b \ \ and "comultiplicative coidentity": | | a | b | a | | comultiplicative L R coidentity: | | f: LR => 1_a | | \ / f which make it into a monoid object *and* a comonoid object. Even better, there are some extra relations between the multiplication and comultiplication, which make LR into a so-called "Frobenius object"! In short, hom(a,a) is the walking Frobenius object! So is hom(b,b), since there is no real asymmetry between the objects a and b in a biadjunction, as there was with an adjunction. I haven't thought much about hom(a,b) and hom(b,a) yet, but one obvious thing is that they're isomorphic. Next time I'll talk about examples of Frobenius objects and why they are so important in subfactors, TQFTs and the like. This is what Mueger is really interested in. Right now, I want to wrap up by saying exactly what it means to say LR is a "Frobenius object". What are the extra relations between multiplication and comultiplication? There are various ways of describing these relations. Mueger uses a pair of equations that are popular in the TQFT literature: \ \ / / | | | | \ \ / / | | | | \ \_/ / | | | | \ / | \ a | | | | | \ | | a | | a a | |\ \ | | a | | | | \ \ | | |b| | | \ \ | | | | = | | \ \ | | | | | | \ \ | | | | | | a \ \| | | | | | \ | / _ \ | | \ b| / / \ \ | | | | / / \ \ | | | | / / \ \ | | | | and its mirror image. People sometimes call these the "I = N" equations, for the obvious reason. So: one definition of a "Frobenius object" in a monoidal category is that it's a monoid object / comonoid object satisfying the I = N equations. Where can you read about this? Well, besides Mueger's paper, there are these: 4) Frank Quinn, Lectures on axiomatic quantum field theory, in Geometry and Quantum Field Theory, Amer. Math. Soc., Providence, RI, 1995. 5) Lowell Abrams, Two-dimensional topological quantum field theories and Frobenius algebras, J. Knot Theory and its Ramifications 5 (1996), 569-587. The I = N equations are cute, but personally I prefer a more conceptual description of a Frobenius object. This may be a bit mindblowing to the uninitiated, so if you're just barely hanging on, please stop now. Hmm! If you're still reading this, you must be brave! Okay - don't say I didn't warn you. Let's start by pondering LR a bit more. This guy is its own adjoint, with the unit and counit as follows: _ a / \ | | | | unit for LR = | b | multiplicative identity composed with / _ \ comultiplication / / \ \ / / \ \ / / a \ \ \ \ a / / \ \ / / \ \_/ / counit for LR = \ / multiplication composed with a | b | comultiplicative coidentity | | | | \_/ It's easy to check the triangle equations by straightening out the relevant zig-zags. Now, whenever a monoid object has a right or left adjoint, that right or left adjoint automatically becomes a comonoid object, by the magic of duality. But if a monoid object is its *own* adjoint, it becomes a comonoid object in *two* ways, because it is both its own left *and* right adjoint! So, our guy LR is a comonoid object in *three* ways! Huh? Well, we already knew LR was a comonoid object before this devilish paragraph began, but since LR is its own adjoint, it becomes a comonoid object in two other ways. Amazingly, the I = N equations are equivalent to the fact that all three comonoid structures agree! I leave this as an exercise for the insanely energetic reader... I've worked it out before, and I rechecked it this morning in bed. I don't know if a proof exists in the literature, but from what Mueger writes, I suspect maybe you can catch glimpses of it in Appendix A3 of this book: 6) L. Kadison, New Examples of Frobenius Extensions, University Lecture Series #14, Amer. Math. Soc., Providence RI, 1999. Anyway, the upshot is that we can equivalently define a Frobenius object in a monoidal category as follows: it's a monoid object / comonoid object which becomes its own adjoint by letting unit = multiplicative identity composed with comultiplication counit = multiplication composed with comultiplicative coidentity and has the property that the resulting 3 comonoid structures agree. Or, equivalently, that the resulting 3 monoid structures agree! There is much more to say about this, but let's stop here.

7 8

ESSLLI 2002 Student Session
by Malvina Nissim 01 Dec '01

01 Dec '01

!!! Concerns all students in Logic, Linguistics and Computer Science !!! !!! Please circulate and post among students !!! We apologise if you receive this message more than once. ESSLLI-2002 STUDENT SESSION FIRST CALL FOR PAPERS August 5-16 2002, Trento, Italy Deadline: February 25th, 2002 www.iccs.informatics.ed.ac.uk/~malvi/esslli02 We are pleased to announce the Student Session of the 14th European Summer School in Logic, Language and Information (ESSLLI-2002) organised by the Centre for scientific and technological research (ITC-irst) in Trento and by the University of Trento, under the auspices of the European Association for Logic, Language and Information (FoLLI). ESSLLI-2002 will be held in Trento from August 5-16 2002. We invite submission of papers for presentation at the ESSLLI-2002 Student Session and for appearance in the proceedings. PURPOSE: This seventh ESSLLI Student Session will provide, like the other editions, an opportunity for ESSLLI participants who are students to present their own work in progress and get feedback from senior researchers and fellow-students. The ESSLLI Student Session encourages submissions from students at any level, from undergraduates (before completion of the Master Thesis) as well as postgraduates (before completion of the PhD degree). Papers co-authored by non-students will not be accepted. Papers may be accepted for full presentation (30 minutes including 10 minutes of discussion) or for a poster presentation. All the accepted papers will be published in the ESSLLI-2002 Student Session proceedings, which will be made available during the summer school. KLUWER BEST PAPER AWARD: As in previous years, the best paper will be selected by the programme committee and will be offered a prize by Kluwer Academic Publishers to be spent on books. REQUIREMENTS: The Student Session papers should describe original, unpublished work, completed or in progress that demonstrates insight, creativity, and promise. No previously published papers should be submitted. Note that the ESSLLI02 school will be focussed on the three main interdisciplinary areas (Logic & Language, Logic & Computation, and Language & Computation), while the single areas have been dropped. Given the high interest shown over the years, the Student Session will keep two of the single areas, namely Logic and Language, welcoming thus submissions within the following topics: Logic, Language, Logic & Language, Logic & Computation, Language & Computation. FORMAT OF SUBMISSION: Student authors should submit an anonymous full paper headed by the paper title, not to exceed 7 pages of length exclusive of references and send a separate identification page (see below). Note that the length of the final version of the accepted papers will not be allowed to exceed 10 pages. Since reviewing will be blind, the body of the abstract should omit author names and addresses. Furthermore, self-references that reveal the author's identity (e.g., "We previously showed (Smith, 1991)... ") should be avoided. It is possible to use instead references like "Smith (1991) previously showed...". For any submission, a plain ASCII text version of the identification page should be sent separately, using the following format: Title: title of the submission First author: firstname lastname Address: address of the first author ...... Last author: firstname lastname Address: address of the last author Short summary: abstract (5 lines) Subject area (one of): Logic | Language | Logic and Language | Logic and Computation | Language and Computation If necessary, the program committee may reassign papers to a more appropriate subject area. The submission of the extended abstract should be in one of the following formats: PostScript, PDF, RTF, or plain text. But note that, in case of acceptance, the final version of the paper has to be submitted in LaTeX format. Please, use A4 size pages, 11pt or 12pt fonts, and standard margins. Submissions outside the specified length and formatting requirements may be subject to rejection without review. The paper and separate identification page must be sent by e-mail to: malvi(a)cogsci.ed.ac.uk by FEBRUARY 25th 2002 ESSLLI-2002 INFORMATION: In order to present a paper at ESSLLI-2002 Student Session, at least one student author of each accepted paper has to register as a participant at ESSLLI-2002. The authors of accepted papers will be eligible for reduced registration fees. For all information concerning ESSLLI-2002, please consult the ESSLLI-2002 web site at www.esslli2002.it IMPORTANT DATES: Deadline for submission of abstracts: February 25, 2002. Authors Notifications: April 22, 2002. Final version due: May 20, 2002. ESSLLI-2002 Student Session: August 5-16, 2002. PROGRAMME COMMITTEE: David Ahn, University of Rochester (Language and Computation) Carlos Areces, University of Amsterdam (Logic) Reinhard Blutner, University of Berlin (Language) Kees van Deemter, University of Brighton (Language and Computation) Paul Dekker, University of Amsterdam (Logic and Language) Juergen Dix, University of Manchester (Logic and Computation) Marta Garcia-Matos, University of Helsinki (Logic) Juan Heguiabehere, University of Amsterdam (Logic and Computation) Elsi Kaiser, University of Pennsylvania (Language) Malvina Nissim, University of Edinburgh (Chair) Rick Nouwen, University of Utrecht (Logic and Language) For any specific question concerning ESSLLI-2002 Student Session, please, do not hesitate to contact me: Malvina Nissim ICCS, University of Edinburgh 2 Buccleuch Place, Edinburgh EH8 9LW, UK phone: +44 +(0)131 +650 4630 fax: +44 +(0)131 +650 6626 e-mail: malvi(a)cogsci.ed.ac.uk

1 0

CFP: FICS 02, a satellite workshop to LICS 02
by Zoltan Esik 30 Nov '01

30 Nov '01

============================================================= FICS'2002 Fixed Points in Computer Science A Satellite Workshop to LICS'2002 July 20--21, 2002, Copenhagen, Denmark http://floc02.diku.dk/FICS/ PRELIMINARY CALL FOR PAPERS Aim: Fixed points play a fundamental role in several areas of computer science and logic by justifying induction and recursive definitions. The construction and properties of fixed points have been investigated in many different frameworks. The aim of the workshop is to provide a forum for researchers to present their results to those members of the computer science and logic communities who study or apply the fixed point operation in the different fields and formalisms. Previous workshops were held in 1998 in Brno, in 2000 in Paris, and in 2001 in Florence. Topics include, but are not restricted to: Construction and reasoning about properties of fixed points, categorical, metric and ordered fixed point models, continuous algebras, relation algebras, fixed points in process algebras and process calculi, regular algebras of finitary and infinitary languages, formal power series, tree automata and tree languages, infinite trees, the mu-calculus and other programming logics, fixed points in relation to dataflow and circuits, fixed points and the lambda calculus, fixed points in logic programming and data bases. Paper submission: Authors are invited to send three copies of an abstract not exceeding three pages to the PC cochair Anna Ingolfsdottir. Electronic submissions in the form of uuencoded postscript files are encouraged and can be sent to annai(a)cs.auc.dk. Submissions are to be received before April 15, 2002. Authors will be notified of acceptance by May 31, 2002. Proceedings: Preliminary proceedings containing the abstracts of the talks will be available at the meeting. Final proceedings will be published after the meeting as a special issue of the journal Theoretical Informatics and Application} (http://www.edpsciences.org/docinfos/ITA/) Invited speakers: L. Aceto (Aalborg), D. Kozen (Cornell), A. Labella (Rome), G. Winskel (Cambridge, provisional). Program Committee: J. Adamek (Braunschweig), R. Backhouse (Nottingham), S. Bloom (Hoboken NJ), J. Bradfield (Edinburgh), R. De Nicola (Florence), Z. Esik (cochair, Szeged), I. Guessarian (Paris), A. Ingolfsdottir (cochair, Aalborg), W. Kuich (Vienna), A. Labella (Rome), M. Mislove (Tulane), D. Niwinski (Warsaw). The meeting will be organised in affiliation to LICS'02: http://www.dcs.ed.ac.uk/home/grohe/lics/lics02/ FICS'02 is partially supported by BRICS (Basic Research in Computer Science): http://www.brics.dk/ and the Computer Science Department of Aalborg University: http://cs.auc.dk/. More information} is available at the web site http://floc02.diku.dk/FICS/

1 0

Re: Characterizing FinSet up to equivalence (fwd)
by Vaughan Pratt 30 Nov '01

30 Nov '01

>From: Boerger <Reinhard.Boerger(a)FernUni-Hagen.de> >the simplest characterization of FinSet known to me is as the free >category with initial object and binary coproducts on one object. Intuitively initiality seems like a bigger hammer than finiteness. This is confirmed by the observation that, although both initiality and finiteness properly extend first order logic as a specification methodology, initiality *guarantees* uniqueness up to whatever. With the assumption only of finiteness of objects, uniqueness is not so easily obtained (cf linear orders without endpoints, an alpha-null-categorical theory). It's like driving to work vs. riding a bicycle. Driving is faster and more convenient, the bicycle shifts more of the responsibility to the rider. >In the usual world existence of these types of coproducts is equivalent >to finite coproducts, but restriction to nullary and binary ones avoids >the need for an a priori notion of finiteness. A nice point and I did consider writing "with binary sums and an initial object" in place of "with finite sums" at the time. Given the brevity of the latter it might be preferable to consider it defined as the former by default, indicating any exceptions explicitly. >Somehow this reminds me of Kuratowski's definition of finiteness. I thought Kuratowski's idea was that when a shepherd verifies that he has only finitely many sheep by completing the process of branding them all, it is not necessary when branding a given sheep to first check whether it has already been branded. All that matters (to both the shepherd and the sheep) is that the branding eventually stop. Here's a definition for traditionalist physicists etc. who believe that God created the continuum while the natural numbers are the work of mankind. ** A set of points is finite just when its members can be positioned with equal ** nonzero spacing in a straight line across an A4 sheet of paper. This is the appropriate converse to the Archimedean axiom, violated only for those physicists who view the continuum as including infinitesimals. Pace Joe Shipman, any physicist demonstrating this deserves a Nobel prize. Somehow this reminds me of how many angels can fit on the head of a pin. Vaughan

1 0

Re: Characterizing FinSet up to equivale
by Boerger 30 Nov '01

30 Nov '01

Hello, the simplest characterization of FinSet known to me is as the free category with initial object and binary coproducts on one object. In the usual world existence of these types of coproducts is equivalent to finite coproducts, but restriction to nullary and binary ones avoids the need for an a priori notion of finiteness. Somehow this reminds me of Kuratowski's definition of finiteness. Greetings Reinhard

2 1

alg-coalg duality
by Al Vilcius 29 Nov '01

29 Nov '01

If F:C-->C is a functor with opposite F*:C*-->C* then (F-algebras)* is trivially equivalent to (F*)-coalgebras. Can this duality be induced by a schizophrenic object?

2 1

address of T. Plewe
by Jiri Adamek 29 Nov '01

29 Nov '01

Can anyone provide me with the current e-mail address of T. Plewe? This is urgent becuse of outsanding page proofs of a paper of his, thanks for your help, J. Adamek xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx alternative e-mail address (in case reply key does not work): J.Adamek(a)tu-bs.de xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

1 0

free-living/platonic/walking equivalences and adjunctions
by Steve Lack 28 Nov '01

28 Nov '01

John Baez described the ``platonic idea of an equivalence'' or ``walking equivalence''. (This has also been called the ``free-living equivalence''.) He also describes the free-living adjoint equivalence, and the homotopy-theoretic relationship between the two. Similarly, one can construct the free-living adjunction. This was done in S. Schanuel and R. Street, The free adjunction, Cah. Top. Geom. Diff. 27:81-83, 1986. John also points out that one can consider not just equivalences, but 2-equivalences, 3-equivalences, and so on. The free-living pseudo-adjunction was constructed in Stephen Lack, A coherent approach to pseudomonads, Adv. Math. 152:179-202, 2000. from a rather different point of view to that of Schanuel and Street. Steve Lack.

2 1