July 2004 - Categories - categories.org.au

Re: limits of finite sets
by Tom Leinster 03 Aug '04

03 Aug '04

I asked for an explanation of the following result: > the limit in Set of any diagram > > ... ---> S_3 ---> S_2 ---> S_1 > > of finite nonempty sets is nonempty Thanks very much to all who replied. I'll summarize some of the points made to me in private replies: 1. This is called Koenig's Lemma, and is usually stated in the form "any finitely-branching infinite tree contains an infinite (positively oriented) path". 2. This also follows from a general result in topology by regarding each S_n as a discrete space. The general result is that any "suitably-shaped" limit of nonempty compact Hausdorff spaces is nonempty. For Bourbaki (General Topology), "suitably-shaped" means indexed by a directed poset. More generally still, it could be any componentwise cofiltered limit, i.e. any limit for which each connected-component of the indexing category I is cofiltered (or equivalently, every finite connected diagram in I admits a cone). The proof of the general topological result specializes to give a nice topological proof of Koenig. For each n, let V_n be the subset of the product \prod_n S_n consisting of those sequences whose first n terms are compatible; then \lim_n S_n is the intersection of the (V_n)s. But with the discrete topology on each S_n, Tychonoff says that \prod_n S_n is compact, and (V_n) is a nested sequence of nonempty closed subsets so has nonempty intersection. Tom

3 2

Limit of finite sets
by Tom Leinster 01 Aug '04

01 Aug '04

I've recently come across the following curious little result. I know how to prove it and have a use for it, but my question is: can anyone supply a wider context or explanation? The result is that the limit in Set of any diagram ... ---> S_3 ---> S_2 ---> S_1 of finite nonempty sets is nonempty. Note that finiteness cannot be dropped: for instance, take each S_n to be the natural numbers and each map to be addition of 1. Thanks, Tom

6 6

Book: Higher Operads, Higher Categories
by Tom Leinster 30 Jul '04

30 Jul '04

Fifteen months ago I announced to the list that my book, Higher Operads, Higher Categories, was available on the web. It is now out in traditional form too, in the blue-green LMS Lecture Note Series (Cambridge University Press). Details of both versions can be found at http://www.maths.gla.ac.uk/~tl/book.html The free web version will remain available permanently. Those of you who came to my talk at CT04 will know that there is a mistake on the front cover: take out your blue-green Tippex and paint over the words "Edited by". Tom

1 0

Whitehead's problem
by Colin McLarty 29 Jul '04

29 Jul '04

Does anyone here know the origin of the "Whitehead conjecture"? I mean the one saying every group G with Ext(G,Z)=0 is free. Did Whitehead himself consider this, or did it arise by generalizing his ideas? Did he expect it to be true, or just wonder about it? best, Colin

2 1

Proceedings, Fields Inst Meeting Dept 2002
by Walter Tholen 28 Jul '04

28 Jul '04

The proceedings of the conference held in September 2002 at the Fields Institute in Toronto are now available with the AMS. The 570-page volume is entitled "Galois Theory, Hopf Algebras, and Semiabelian Categories" (edited by George Janelidze, Bodo Pareigis, and Walter Tholen). See http://www.ams.org/bookstore?fn=20&arg1=whatsnew&item=FIC-43 for more information. A much smaller collection of papers especially devoted to categorical descent theory will appear (hopefully later this year) as an issue of "Applied Categorical Structures" (Kluwer). Walter Tholen.

1 0

SOS2004: Call for Participation
by iu3＠mcs.le.ac.uk 27 Jul '04

27 Jul '04

CALL FOR PARTICIPATION Structural Operational Semantics http://www.cs.auc.dk/~luca/SOS-WORKSHOP/ A Satellite Workshop of CONCUR 2004 30 August, 2004, London, United Kingdom EARLY REGISTRATION DEADLINE: 30th July 2004. Please refer to http://www.doc.ic.ac.uk/concur2004/registrationindex.html STUDENT GRANT DEADLINE: 6th August 2004. Please see below. The SOS workshop aims to be 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. The workshop will also mark the publication of a special issue of the Journal of Logic and Algebraic Programming, devoted to SOS. Together with original research papers on SOS, this special issue will feature a definitive version of Gordon Plotkin's 1981 DAIMI memo on SOS, together with a piece by Plotkin on the origins of SOS. Preliminary Scientific Programme: * Andrew Pitts: Equivariant and Nominal SOS (invited talk) * David Sands Representing and Manipulating Contexts: a Tool for Operational Reasoning (tutorial) * Matthias Mann Congruence of Bisimulation in a Non-Deterministic Call-By-Need Lambda Calculus * Bartek Klin Congruence Formats from Bialgebraic Semantics * Rob van Glabbeek The Meaning of Negative Premises: Part II (tutorial) * Olivier Tardieu A Deterministic Logical Semantics for Esterel * Peter Mosses Modular Structural Operational Semantics * Marija Kulas Toward the Concept of Backtracking Computation * Ralf Laemmel Evolution Scenarios for Language-based Functionality Sponsorship: The workshop is partly sponsored by the Engineering and Physical Sciences Research Council (EPSRC). Student Grants: Thanks to the support of the EPSRC, we have fifteen small grants available to the U.K.-based PhD students to attend the SOS workshop. A typical grant will cover the costs of travel and subsistence, and in special cases the accommodation for one night in London. Full details on how to apply will soon appear on the workshop Web pages but, in short, if you are a PhD student researching at the U.K.-based academic institution, you can apply for the grant by emailing Irek Ulidowski (iu3 AT mcs.le.ac.uk) the following information: 1. Full name 2. Affiliation 3. Topic of research 4. Supervisor's details 5. Estimate of cost of travel and accommodation (if really necessary) 6. Short statement on how the SOS Workshop will benefit your present and future research We also recommend that you supply us with a short supporting letter from your supervisor. The student GRANT DEADLINE is 6th August 2004. Please, copy your email to Luca Aceto (luca AT cs.auc.dk) and Wan Fokkink (wan AT cwi.nl). Program Committee: Luca Aceto (BRICS, Aalborg, Denmark, co-chair) Wan Fokkink (CWI, The Netherlands, co-chair) Rob van Glabbeek (NICTA, Sydney, Australia) Ralf Laemmel (CWI, The Netherlands) Peter Mosses (BRICS, Aarhus, Denmark) David Sands (Chalmers, Sweden) Alex Simpson (Edinburgh, United Kingdom) Simone Tini (Insubria, Italy) Irek Ulidowski (Leicester, United Kingdom, co-chair) Erik de Vink (Eindhoven, The Netherlands) Organizing Committee: Luca Aceto, email: luca AT cs.auc.dk, (BRICS, Aalborg, Denmark) Wan Fokkink, email: wan AT cwi.nl, (CWI, The Netherlands) Irek Ulidowski, email iu3 AT mcs.le.ac.uk (Leicester, United Kingdom)

1 0

Proof nets
by Robin Houston 19 Jul '04

19 Jul '04

Dear categorists, The category of ordinary MLL proof nets (where an object is a term, and a morphism X -> Y is a cut-free proof net for |- X^, Y) is the free unitless *-autonomous category generated by the literals. Does the corresponding result hold for MALL? The Hughes-van Glabeek notion of MALL proof net has the ring of truth about it, and indeed they claim to have proven (theorem 4.22) that "two cut-free MALL proofs translate to the same proof net iff they can be converted into each other by a series of rule commutations". Of course the category of MALL proof nets is a unitless *-autonomous category with binary products and coproducts, but nowhere (to my knowledge) is it described as the *free* such category. Is that because it isn't, or merely because it isn't (yet) known to be? Enlightenment will be much appreciated. Yours, Robin

1 0

relationship between existential/universal quantifiers and adjoints??
by Galchin Vasili 16 Jul '04

16 Jul '04

Hello Cat Community, I would like a clear exposition of the relationship between quantifiers and their corresponding adjoints (so I can understand this relationship). In particular, I would to understand how Lawvere came to this insight. Which book, publication. etc. will best help me to understand this very important relationship? Regards, Bill Halchin

1 0

algebraic set theory site
by Steve Awodey 15 Jul '04

15 Jul '04

Dear Colleagues, This is to inform you that a small website has been created for the purpose of collecting and distributing research devoted to algebraic set theory. Following on the Joyal & Moerdijk monograph by the same name, people in several different locations have begun pursuing related research. It is hoped that linking these efforts will encourage collaboration and make it easier for those new to the field to gain easy access. The site is located at: http://www.phil.cmu.edu/projects/ast/ We hope to make more of the papers listed in the bibliography available on the site soon, and to augment the listings with brief descriptions. Please contact me or "webmaster" Michael Warren <mwarren(a)andrew.cmu.edu> if you would like to have your name, homepage, and/or research listed. See (some of) you in Vancouver! Steve Awodey

1 0

Roy
by Peter Freyd 12 Jul '04

12 Jul '04

The Grothendieck discussion has moved a bit far from the main reason for this list but, if I may, a couple of points: First -- in answer to Max's query -- Roy Lisker tells me that almost all of Grothendieck's autobiography in the original French has been transcribed onto www.grothendieck-circle.org. Second, who is Roy Lisker? I've valued him as a resource for over 40 years. He was a student at Penn and a few years later I was a character witness in his trial for draft-card burning. Yep. And he served a 6 month sentence. Among other mathematicians who support his efforts are Lou Kauffman and Mike Barr (Mike has known him longer than I have). Take a look at www.fermentmagazine.org. First you might want to read: Commonweal 02/09/2001 Stop the Presses by Richard Alleva I enter the Russell Public Library of Middletown, Connecticut, just around the corner from Wesleyan University. Walking past the circulation desk, I turn left and enter a publisher's office. No, wait, it's not a publisher's office but the library's reference department. But, behold, in one corner, publishing is indeed in progress. Crouched over a computer keyboard is a middle-aged man with a pate appropriately monkish and a face appropriately gnomic, for like any good writer he coaxes his thoughts onto the page with the humble intensity of a monk decorating a manuscript or the greedy intensity of a gnome counting his gold. He has slipped his complete works onto some disks which he carries to and from the library. With the aid of a benevolent library computer technician, he has installed a wide variety of typefonts on the hard drive which not only he but any other library patron can employ (thereby making our writer not only the beneficiary but the benefactor of the library), and once he has written at least a couple of drafts in longhand, he chooses the most appropriate font for the story or essay in progress, types it, revises again and again until satisfied, prints, photocopies, turns the results over to a bindery, and winds up with the latest of several handsome booklets with blue or purple or red covers, puckishly decorated by their author. Presto, a twenty-first-century descendant of the Elizabethan chapbook. The contents? Modern variations of Greek and Indian myths, "cynical" (but actually quite poignant) Christmas stories, short fiction about Americans in Paris in the 1960s, factual reports on scientific conferences, ruminations on the state of current academia, horror stories of the homeless, book reviews, farces, musings on the latest developments in physics, and one of the most unsparing and tacitly poignant autobiographies I have ever read. Whose autobiography? That of Roy Lisker, onetime math prodigy, ex-wandering musician, contributor to JeanPaul Sartre's Les Temps Modernes, and local character in a succession of places (mostly university communities), political protestor and prankster, and indefatigable self-publisher. Unless you are Noam Chomsky or historian Howard Zinn or composers Milton Babbitt and John Harbison or one of the other subscribers to Lisker's monthly publication, Ferment, you will have to take my word for it that Roy is worth reading for the way he can make a fictional character as rooted in the real world as the subject of a New Yorker profile, while endowing a real-life academic with the fabulousness of a character in Dickens. If there were any literary justice in the world, Linker's story, "Sam, The Messiah Man," about a violinist who devotes his entire career to perfecting the violin passages of a Handel oratorio, would be as renowned as Borges's fable about another artistic specialist, "Pierre Menard, Author of the Quixote." But what really concerns me here is to point out how tenaciously Lisker reverts to the seemingly outmoded notion of the writer as local character and streetcorner vendor of news, satire, and fantasy. To be sure, Lisker has been conventionally published (his academic satire, Getting That Meal Ticket, was published in Paris by Rend Juliard in 1972), but he now confines his energies to using his private printing press in the Russell Library, hawking his wares on the Wesleyan campus, giving readings at local bookstores, and mailing his publications to subscribers who are all over the country because Roy, in his youth, had been all over the country befriending and bugging people while enacting his role of academic-mathematician- wandering minstrel. [For the whole thing: www.fermentmagazine.org/Commonweal.html]

1 0