September 2007 - Categories - categories.org.au

Foundations?
by F W Lawvere 03 Sep '10

03 Sep '10

Down with "Foundations"! Up with algebra! Dear Friends, Presumably I am among those who are being "vilified" as "lovers of categories as foundation". By avoiding any precise definition, such a formulation might appeal to the widespread justified boredom induced by the past hundred years of "foundations as justification". Whenever I used the word "foundation" in my writings over the past forty years, I have explicitly rejected that reactionary use of the term and instead used the definition implicit in the work of my teachers Truesdell and Eilenberg. Namely, an important component of mathematical practice is the careful study of historical and contemporary analysis, geometry, etc. to extract the essential recurring concepts and constructions; making those concepts and constructions (such as homomorphism, functional, adjoint functor, etc.) explicit provides powerful guidance for further unified development of all mathematical subjects, old and new. What is the primary tool for such summing up of the essence of ongoing mathematics? Algebra! Nodal points in the progress of this kind of research occur when, as is the case with the finite number of axioms for the metacategory of categories, all that we know so far can be expressed in a single sort of algebra. I am proud to have participated with Eilenberg, Mac Lane, Freyd, and many others, in bringing about the contemporary awareness of Algebra as Category Theory Had it not been for the century of excessive attention given to the alleged possibility that mathematics is inconsistent, with the accompanying degradation of the F-word, we would still be using it in the sense known to the general public: the search for what is "basic". We, who supposedly know the explicit algebra of homomorphisms, functionals, etc. are long remiss in our duty to find ways to utilize those concepts also in guiding high school calculus. Best wishes, Bill Bibliography: - The Category of Categories as a Foundation for Mathematics, La Jolla conference 1965, Springer (1966) - Adjointness in Foundations, Dialectica, (1969), to be reprinted in TAC - Foundations and Applications: Axiomatization and Education, Bulletin of Symbolic Logic, (2003) vol 9, pp 213-224 - Sets for Mathematics, w/ Bob Rosebrugh, Cambridge Univ. Press, (2003) ************************************************************ F. William Lawvere Mathematics Department, State University of New York 244 Mathematics Building, Buffalo, N.Y. 14260-2900 USA Tel. 716-645-6284 HOMEPAGE: http://www.acsu.buffalo.edu/~wlawvere ************************************************************

2 1

PEPM 2008: abstracts due Oct 12
by Oege.de.Moor＠comlab.ox.ac.uk 05 Oct '07

05 Oct '07

PEPM 2008 ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation January 7-8, 2008, San Francisco Keynotes by Ras Bodik (Berkeley) and Monica Lam (Stanford) Co-located with POPL http://www.program-transformation.org/PEPM08/WebHome PEPM is a leading venue for the presentation of cutting-edge research in program analysis, program generation and program transformation. Its proceedings are published by ACM Press; full details of the scope, submission process, and program committee can be found at the above URL. The program committee would particularly welcome submissions from category theorists on any topic relating to categorical justification of program fusion rules Abstracts are due on October 12, and the deadline for full paper submission is October 17. Prospective authors are welcome to contact the program chairs, Robert Glueck (glueck(a)acm.org) and Oege de Moor (oege(a)comlab.ox.ac.uk) with any queries they might have.

1 1

The division lattice as a category: is 0 prime?
by Vaughan Pratt 30 Sep '07

30 Sep '07

Has the division lattice been organized as a category somewhere in the literature in a way that accounts somehow for 0? A simplistic construction is [FinSet^N] denoting the finitary finite-set-valued functors from the discrete category N. ("Finitary" in the sense of being zero almost everywhere.) Interpreting N as indexing the primes and coproduct as numeric multiplication, product becomes gcd and the pushout of (a,b) over its gcd is its lcm. It is simplistic by virtue of omitting (numeric) 0, which is standardly placed at the top of the division lattice. Unlike the rest of the lattice 0 is not generated from the primes by finite coproducts, suggesting it needs to feature in some sort of basis for the complete lattice. The natural thing would be to remove all but the primes and 0 from the division lattice and then try to put them back finitarily. This makes the starting point the inverted flat CPO N^* where N consists of the primes and "bottom" * is now at the top, denoting 0. (That convention makes N_* the usual flat CPO of natural numbers.) If I'm not mistaken the completion of N^* under finite coproducts has as objects two copies of the natural numbers. Below * is [FinSet^N] understood as previously. Above * is FinSet, which was created from * by completion under coproducts. This amounts to FinSet + [FinSet^N] joined at the hip with a shared initial object (numeric 1) and a shared final object (numeric 0, or *). From the Yoneda standpoint the objects are functors from N_* (the usual CPO) to FinSet. The ones below are the functors that are 0 at * and cofinitely many elements of N. The ones above are 0 at N, with * unconstrained. Yoneda's hands are a bit tied here because we are only taking coproducts. Closing under finite colimits presumably frees up Yoneda to produce FinSet x [FinSet^N] = [FinSet^{N_*}]. This might come in handy when one wants a system of pairs of numbers (m,n) for which (m,n)+(m',n') = (m+m',nxn'). Is there some abstract nonsense reason why coproducts produced the sum (actually pushout over the initial and final objects) while colimits produced the product? I arrived at all this after Steve Vickers mentioned on the univalg mailing list that ring theorists define 0 to be a prime number because then they could define n to be prime just when the ring Z/nZ extends to a field. This got me to wondering how this could be reflected in the division lattice, which has 0 at the top without however being considered a prime. I personally am too old to believe that 0 is a prime, but I can see where a younger generation could be hoodwinked. Even with the above understanding however I don't see how 0 can be understood as just another ordinary prime, any more than bottom is just another ordinary number in N_*. Vaughan Pratt

3 4

continuous lattices for analysts??
by Paul Taylor 29 Sep '07

29 Sep '07

As you will have gathered from my previous posting to "categories", over the past three years I have been applying Abstract Stone Duality to the foundations of (constructive) analysis. This means that I have been bringing not only ASD itself but categorical ideas more generally to a new audience. However, my new friends are not very familiar with some of the ideas that I normally take for granted. Two things in particular have turned out to be difficult. One of these, not surprisingly, is my use of LAMBDA CALCULUS to define open subspaces. I have found notational ways to sugar this pill, such as defining functions WITH arguments (as in most programming languages), so avoiding lambda-abstraction unless absolutely necessary, and simply writing "..." instead of the usual name "Gamma" for a context or list of parameters. I see this as part of the programme of relating formal logical notation to the idioms of vernacular of mainstream mathematics, as in Charles Wells' "Handbook of Mathematical Discourse", and sections 1.6 and 6.5 of my own book, "Practical Foundations of Mathematics", where I explain the phrase "there exists" and the usual manipulation of finite sets. However, there is another problem that is not simply a matter of unfamiliar notation. I had understood that the theory of CONTINUOUS LATTICES had grown out of half a dozen different disciplines (represented by the authors of the "Compendium"), and in particular that on of these had been the concept of SEMI-CONTINUITY in real analysis. I had expected to find at least a basic awareness of continuous lattices amongst analysts, but I was mistaken. However, it would not be appropriate to include an introduction to them in ASD, since it does not build directly on the standard theory of continuous lattices. Instead, it abstracts ideas from them (in particular the paper "Computably based locally compact spaces" has an abstract "way below" relation), and one of its basic principles is to hide Scott continuity in the foundations. I would like to be able to cite an introduction to continuous lattices that is written for (and ideally by) real analysts. So far, my enquiries amongst the experts on continuous lattices have drawn a blank, but maybe some analyst has had occasion to use them, or maybe teach a graduate course about them. To generalise the question, is there a good account of non-Hausdorff topology apart from those written for domain theory in theoretical computer science? My specific context is to rewrite Section 7 of "A lambda calculus for real analysis", which was presented at "Computability and Complexity in Analysis" in Kyoto in August 2005. Paul Taylor www.PaulTaylor.EU

3 3

10th Asian Logic Conference, Kobe, Japan, 2008 (first announcement)
by Peter Schuster 28 Sep '07

28 Sep '07

The 10th Asian Logic Conference will be held at Kobe University, Kobe, Japan during September 1-6, 2008. Several short course lectures (four hours each), plenary invited talks (one hour each) and special sessions are planned apart from contributed talks. The Asian Logic Conference has occurred every three years in Asia-Pacific region since 1981, Singapore. The purpose of the conference is to facilitate interaction between researchers interested in mathematical logic, logic in computer science, and philosophical logic. It aims at promoting activities in mathematical logic in the Asia-Pacific so that logicians both from within Asia and elsewhere would get together and exchange information and ideas. Call for papers will begin in the coming winter, and the registration in an early spring, 2008. Please write down in your notebook as 'ALC, Kobe, Sep. 1-6, 2008'. Thank you, Toshiyasu Arai Graduate School of Engineering Kobe University Rokko-dai, Nada-ku, Kobe, 657-8501, Japan

1 0

category position
by Walter Tholen 27 Sep '07

27 Sep '07

York University <http://www.yorku.ca/yorkweb/index.htm> CATEGORY THEORY AND ITS APPLICATIONS Applications are invited for one tenure-track appointment at the Assistant Professor level in the Department of Mathematics and Statistics to commence July 1, 2008. Candidates in the area of Category Theory and its applications to mathematics, computer science or physics will be considered. The successful candidate must have a Ph.D. in hand or near completion (expected in 2008), a proven record of independent research excellence, and superior teaching ability. The successful candidate must be eligible for prompt appointment to the Faculty of Graduate Studies. Preference will be given to candidates who can strengthen existing areas of present and ongoing research activity. Applications must be received by January 15, 2008. Applicants should send resumes and arrange for three signed letters of recommendation (one of which should address teaching) to be sent directly to: Pure Mathematics Search Committee Department of Mathematics and Statistics N520 Ross, York University 4700 Keele Street Toronto, Ontario Canada M3J 1P3 E-mail: puremath.recruit(a)mathstat.yorku.ca <mailto:puremath.recruit@mathstat.yorku.ca>, Website: www.math.yorku.ca/Hiring <http://www.math.yorku.ca/Hiring> All positions at York are subject to budgetary approval. York University is an Affirmative Action Employer. The Affirmative Action Program can be found on York's website at www.yorku.ca/acadjobs <http://www.yorku.ca/acadjobs> or a copy can be obtained by calling the affirmative action office at 416-736-5713. All qualified candidates are encouraged to apply; however, Canadian citizens and Permanent Residents will be given priority.

1 0

LICS Newsletter 111
by Kreutzer + Schweikardt 21 Sep '07

21 Sep '07

Newsletter 111 September 10, 2007 ******************************************************************* * Past issues of the newsletter are available at http://www.informatik.hu-berlin.de/lics/newsletters/ * Instructions for submitting an announcement to the newsletter can be found at http://www.informatik.hu-berlin.de/lics/newsletters/inst.html * To unsubscribe, send an email with "unsubscribe" in the subject line to lics(a)informatik.hu-berlin.de ******************************************************************* TABLE OF CONTENTS * BOOK ANNOUNCEMENTS Reactive Systems - Aceto, Ingolfsdottir, Larsen, and Srba * CONFERENCES AND WORKSHOPS LICS 2008 - Call for Workshop Proposals M4M-5 ICALP 2008 - Second Call for Workshop Proposals PODS 2008 - Call for Papers SAT 2008 - Call for Papers REACTIVE SYSTEMS: MODELLING, SPECIFICATION AND VERIFICATION by Luca Aceto, Anna Ingolfsdottir, Kim G. Larsen and Jiri Srba Cambridge University Press, ISBN-13: 9780521875462. * A textbook providing a balanced introduction to the theory and practice of concurrency for advanced undergraduates and graduate students. It describes various approaches for the modelling, specification and verification of reactive systems, their strengths and weaknesses, and when they are best used. The book has arisen from various courses taught in Iceland, Denmark and elsewhere, and is designed to give students a broad introduction to the area, with exercises throughout. * Preface; Part I. A Classic Theory of Reactive Systems: 1. Introduction; 2. The language CCS; 3. Behavioural equivalences; 4. Theory of fixed points and bisimulation equivalence; 5. Hennessy-Milner logic; 6. Hennessy-Milner logic with recursive definitions; 7. Modelling and analysis of mutual exclusion algorithms; Part II. A Theory of Real-Time Systems: 8. Introduction; 9. CCS with time delays; 10. Timed automata; 11. Timed behavioural equivalences; 12. Hennessy-Milner logic with time; 13. Modelling and analysis of Fischer's algorithm; Appendix; Bibliography; Index. * For more information, please visit: http://www.cambridge.org/uk/catalogue/catalogue.asp?isbn=3D9780521875462 http://www.cs.aau.dk/rsbook/ IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS 2008) Call for Workshop Proposals 24th=E2=80=9327th June 2008, Pittsburgh, Pennsylvania, USA * The Twenty-Third IEEE Symposium on Logic In Computer Science (LICS 2008) (see http://www2.informatik.hu-berlin.de/lics/lics08 ) will be held in Pittsburgh, Pennsylvania (USA) June 24--27, 2008. It will be colocated with CSF (IEEE Computer Security Foundations). * Possible dates for workshops are June 21-23 (i.e. up to three days before LICS). * Researchers and practitioners are invited to submit proposals for workshops on topics relating logic - broadly construed - to computer science or related fields. Typically, LICS workshops feature a number of invited speakers and a smaller number of contributed presentations. LICS workshops do not produce formal proceedings. However, in the past there have been special issues of journals based in part on certain LICS workshops. * Proposals should include: - A short scientific summary and justification of the proposed topic. This should include a discussion of the particular benefits of the topic to the LICS community. - A discussion of the proposed format and agenda. - The proposed duration, which is typically one to two days, and your preferred dates. (important!) - Let us know if you would like your workshop to be a joint workshop with CSF. - Procedures for selecting participants and papers. - Expected number of participants (this is important!) - Potential invited speakers. - Plans for dissemination (for example, special issues of journals). * Proposals are due Nov. 20, 2007 and should be submitted electronically to both of us: Adriana Compagnoni abc(a)cs.stevens.edu Philip Scott phil(a)site.uottawa.ca Workshops Chairs, LICS 2008 * Please specify if you wish to have a 1 or 2 day workshop. And your preferred dates. * Workshops will be chosen by a committee consisting of the LICS General Chair, LICS Workshop Chairs, LICS 2008 PC Chair and LICS 2008 Conference Chair. 5th WORKSHOP ON "METHODS FOR MODALITIES" (M4M-5) November 29-30, 2007, Cachan, France http://m4m.loria.fr/M4M5 * The workshop ``Methods for Modalities'' (M4M) aims to bring together researchers interested in developing algorithms, verification methods and tools based on modal logics. Here the term ``modal logics'' is conceived broadly, including temporal logic, description logic, guarded fragments, conditional logic, temporal and hybrid logic, etc. To stimulate interaction and transfer of expertise, M4M will feature a number of invited talks by leading scientists, research presentations aimed at highlighting new developments, and submissions of system demonstrations. We strongly encourage young researchers and students to submit papers and posters, especially for experimental and prototypical software tools which are related to modal logics. * Invited speakers: Ahmed Bouajjani (University of Paris 7), Patricia Bouyer (OUCL, Oxford - LSV, ENS Cachan), Balder ten Cate (University of Amsterdam), Koen Claessen (Chalmers University of Technology), Wiebe van der Hoek (University of Liverpool) * Important dates: Deadline for submissions: September 7th, 2007 Notification: October 10, 2007 Camera ready versions: November 5, 2007 Workshop dates: November 29-30, 2007 * Paper Submissions: Authors are invited to submit papers in the following three categories. - Regular papers up to 15 pages, describing original results, work in progress, or future directions of research. - System descriptions of up to 12 pages, describing new systems or significant upgrades of existing ones. - Presentation-only papers, describing work recently published or submitted (no page limit). These will not be included in the proceedings, but pre-prints or post-prints can be made available to participants. * Final versions of accepted papers will be published online in an Elsevier ENTCS volume. A preliminary version of the proceedings will also be available at the workshop. 35TH INTERNATIONAL COLLOQUIUM ON AUTOMATA, LANGUAGES AND PROGRAMMING Second Call for Affiliated Workshops ICALP 2008 Reykjavik - Iceland * Conference Dates: July 7-11, 2008 Affiliated Workshop Dates: July 6, 12, and 13, 2008 * Researchers and practitioners are invited to submit proposals for workshops on topics related to the conference tracks, namely: Algorithms, Automata, Complexity and Games (track A); Logic, Semantics, and Theory of Programming (track B); and Security and Cryptography Foundations (track C). * The purpose of the workshops is to provide participants with a forum for presenting and discussing novel ideas in a small and interactive atmosphere. * The main responsibility of organising a workshop goes to the chairperson of the workshop. The format of each workshop is determined by its organisers. * The workshop proposals will be selected by the ICALP organization, under advice of the ICALP PC chairs and EATCS. * Registrations for the workshops affiliated with ICALP 2008 will be handled by the ICALP organizing committee. * Proposals should include: - Name and duration (from half a day to two days) of the proposed workshop. - Preference for a pre- or post-conference workshop, if any. (Note, however, that the final choice of the day when the workshop will be held and other logistic aspects will be decided by the organizing committee.) - A short scientific summary of the topic, including a discussion on the relation with the ICALP topics. - A description of past versions of the workshop, if any, including dates, organisers, submission and acceptance counts, attendance. - Procedures for selecting participants and papers, and expected number of participants. - Plans for dissemination (for example, published proceedings or special issues of journals). * IMPORTANT DATES: October 31, 2007: Deadline for submitting workshop proposals November 21, 2007: Notification of acceptance * Workshop proposals must be submitted in plain text, PDF or Postscript format by e-mail to icalp08(a)ru.is * For further information consult the ICALP 2008 web site: http://www.ru.is/icalp08 or contact the ICALP 2008 Workshops Chairs: - Bjarni V. Halldorsson <bjarnivh at ru.is> - MohammadReza Mousavi <M.R.Mousavi at tue.nl> 27TH ACM SIGMOD-SIGACT-SIGART SYMPOSIUM ON PRINCIPLES OF DATABASE SYSTEMS PODS 2008 Call for Papers June 9-11, 2008, Vancouver, Canada http://www.sigmod08.org/ * The PODS symposium series, held in conjunction with the SIGMOD conference series, provides a premier annual forum for the communication of new advances in the theoretical foundation of database systems. For the 27th edition, original research papers providing new insights in the specification, design, or implementation of data management tools are called for. * Topics that fit the interests of the symposium include the following (as they pertain to databases): algorithms; complexity; computational model theory; concurrency; constraints; data exchange; data integration; data mining; data modeling; data on the Web; data streams; data warehouses; distributed databases; information retrieval; knowledge bases; logic; multimedia; physical design; privacy; quantitative approaches;query languages; query optimization; real-time data; recovery; scientific data; security; semantic Web; semi-structured data; spatial data; temporal data; transactions; updates; views; Web services; workflows; XML. * Important Dates: Abstracts submission due: 28 Nov 2007; Paper submission: 5 Dec 2007; Notification: 26 Feb 2008. 11TH INTERNATIONAL CONFERENCE ON THEORY AND APPLICATIONS OF SATISFIABILITY TESTING (SAT 2008) Call for Papers May 12 - 15, 2008 Guangzhou, P. R. China http://www.upb.de/cs/SAT08 * The International Conference on Theory and Applications of Satisfiability Testing is the primary annual meeting for researchers studying the propositional satisfiability problem (SAT). SA5DT08 is the eleventh SAT conference. SAT08 features the SAT Race, the Max-SAT Evaluation, and the QBFEVAL. * SCOPE Many hard combinatorial problems can be encoded into SAT. Therefore improvements on heuristics on the practical side, as well as theoretical insights into SAT apply to a large range of real-world problems. More specifically, many important practical verification problems can be rephrased as SAT problems. This applies to verification problems in hardware and software. Thus SAT is becoming one of the most important core technologies to verify secure and dependable systems. The topics of the conference span practical and theoretical research on SAT and its applications and include but are not limited to proof systems, proof complexity, search algorithms, heuristics, analysis of algorithms, hard instances, randomized formulae, problem encodings, industrial applications, solvers, simplifiers, tools, case studies and empirical results. SAT is interpreted in a rather broad sense: besides propositional satisfiability, it includes the domain of quantified boolean formulae (QBF), constraints programming techniques (CSP) for word-level problems and their propositional encoding and particularly satisfiability modulo theories (SMT). * SUBMISSION Submissions should contain original material and can either be regular research papers up to 14 pages or short papers up to 6 pages. Double submissions including submissions as short and long papers will be rejected. Submissions should use the Springer LNCS style. All appendices, tables, figures and the bibliography must fit into the page limit. Submissions deviating from these requirements may be rejected without review. All accepted papers including short papers will be published in the proceedings of the conference. The conference proceedings will be published within Springer LNCS series. The submission page is http://www.easychair.org/SAT2008. Papers have to be submitted electronically as PDF files. * IMPORTANT DATES January 11, 2008 Abstract Submission January 18, 2008 Paper Submission February 18, 2008 Author Notification February 25, 2008 Final Version * PROGRAM CHAIRS Hans Kleine B=C3=BCning, University of Paderborn, Germany Xishun Zhao, Sun Yat-Sen University, Guangzhou, P.R. China * Further information on SAT Race, Max-SAT Evaluation, and QBFEVAL will be published also on the SAT08 conference web page.

1 0

unital weak functor?
by Josh Nichols-Barrer 21 Sep '07

21 Sep '07

Hi everyone, Is there a name for a weak functor between bicategories which takes identity 1-morphisms to identity 1-morphisms? "Unital weak functor" would seem an apt name, but if there is another with more precedent I'll just use that instead. Best, Josh

5 5

Commutative diagrams go public!
by Robert J. MacG. Dawson 21 Sep '07

21 Sep '07

Members of the Cat Group may be interested to see an example of a commutative diagram in public signage: http://cs.stmarys.ca/~dawson/CommDiag.html Not exactly cutting-edge mathematics, but it's a start! -Robert Dawson

1 0

CT07 pictures
by Juergen Koslowski 20 Sep '07

20 Sep '07

Dear CT07 Participants, Pictures of the conference are also available on my home page http://www.iti.cs.tu-bs.de/~koslowj/cgi-bin/pE333?CT07-0/idx&256 http://www.iti.cs.tu-bs.de/~koslowj/PHOTOS/CT07 (group picture) As usual, I'm missing some names. So please send me a mail if you can identify someone with a question mark instead of a name. However, I'm presently travelling in Vietnam and Cambodia, so I will only be able do fix the names after my return (October 14). Best regards, -- Juergen -- 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(a)iti.cs.tu-bs.de and don't be late! http://www.iti.cs.tu-bs.de/~koslowj Jimi Hendrix (Voodoo Child, SR)

1 0