May 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

hyperdoctrines and cylindric algebras
by Alexander Kurz 01 Jun '07

01 Jun '07

There clearly is a connection between hyperdoctrines and cylindric algebras. Does anybody knows work that relates the two? Or that makes use of a result from one area to prove something in the other? I would be greatful for any reference or comment. Best wishes, Alexander

4 3

preprint available
by Anders Kock 31 May '07

31 May '07

Dear all, This is to announce the availability of a preprint "Infinitesimal cubical structure, and higher connections" The preprint can be downloaded from http://arxiv.org/abs/0705.4406 or from my home page http://home.imf.au.dk/kock/ In the context of Synthetic Differential Geometry, we describe a notion of higher connection with values in a cubical groupoid. We do this by exploiting a certain structure of cubical complex derived from the first neighbourhood of the diagonal of a manifold. This cubical complex consists of infinitesimal parallelepipeda. Yours Anders

1 0

Re: hyperdoctrines and cylindric algebras (Correction)
by Bill Lawvere 30 May '07

30 May '07

Hyperdoctrines (in many variants) were introduced as an algebraic aspect of "proof theory" and as such are definitely not equivalent to cylindric algebras (or polyadic algebras or even various categorical formulations of logic). They involve fibered categories whose fibers are cartesian closed (and with adjoints between the fibers etc.). The poset reflection of these fibers are Heyting algebras. This reflection process was intuited already by Curry and was later called "the Curry-Howard isomorphism" even though this is a serious misnomer because it is very far from being an isomorphism. (See my paper Adjoints in and among bi-categories, Logic & Algebra, Lecture Notes in Pure and Applied Mathematics. 180:181-189. Ed. A. Ursini, P Agliano, Marcel Dekker, Inc. Basel, 1996, as well as the author's commentary on my paper Adjointness in Foundations, as reprinted in TAC. Recent papers of Matias Menni further clarify these developments, which were partly inspired by work of Hans Laeuchli.) Conceptually, the problem of presentation of a theory in algebraic logic by means of primitive predicates and axioms can be viewed as taking place in two steps: first the presentation of a hyperdoctrine with non-trivial fibers, and then the further collapse by imposing the condition that projection maps act as inverse to diagonal maps (within each fiber). This process can be localized. The problematic existential quantifier which is the core problem of proof theory: ("there exists a proof of ....") is thus split into several parts to be studied separately. I hope the above helps to clarify the relationship between two levels of categorical algebra. Bill ************************************************************ F. William Lawvere, Professor emeritus 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 ************************************************************ On Thu, 24 May 2007, Zinovy Diskin wrote: > On 5/23/07, Alexander Kurz <kurz(a)mcs.le.ac.uk> wrote: > > There clearly is a connection between hyperdoctrines and cylindric > > algebras. > > > > yes, of course. Roughly speaking, they are equivalent: hyperdoctrines > (HDs) are indexed category style algebraization of first order logic > while cylindric algebras (CAs) are an equivalent fibrational > formulation. To make it precise, we need to consider a few rather > straightforward yet technically bulky generalizations of both notions, > reproducing in HDs the classical context of CAs and vice versa. I'm > traveling and do not have references at hand, but below is an outline > of how it can be done (apologies for possible inaccuracies). > ...

2 1

LICS 2007 - Call for Participation
by Kreutzer + Schweikardt 23 May '07

23 May '07

LICS 2007 Call for Participation Reminder: Early registration deadline is approaching: May 31st, 2007 LICS 2007 will be held in the Institute of Computer Science, University of Wroclaw, Poland, 10th - 14th July 2007. It will be colocated with: - International Colloquium on Automata, Languages and Programming (ICALP 2007), 9th - 13th July 2007, and - ASL European Summer Meeting (Logic Colloquium 2007), 14th - 19th July 2007. The IEEE Symposium On Logic In Computer Science (LICS) is an annual international forum on theoretical and practical topics in computer science that relate to logic broadly construed. Detailed information can be found on the webpage: - http://www.informatik.hu-berlin.de/lics/lics07/ - http://july2007.ii.uni.wroc.pl/ Important dates: - May 31st 2007: Early registration discount expires. - 10th - 14th July 2007: Conference Invited Speakers: - Thomas Hales (University of Pittsburgh) - Martin Hyland (University of Cambridge) - Phokion Kolaitis (IBM Almaden Research Centre) - Gordon Plotkin (University of Edinburgh) - Michael Rabin (Harvard University and Hebrew University) - Colin Stirling (University of Edinburgh)

1 0

Book - Finite Model Theory and Its Applications
by MYV 19 May '07

19 May '07

Finite Model Theory and Its Applications by Erich Graedel, Phokion G. Kolaitis, Leonid Libkin, Maarten Marx, Joel Spencer, Moshe Y. Vardi, Yde Venema, and Scott Weinstein Springer, 2007, 437 pages, hardcover, ISBN: 978-3-540-00428-8. (Series: Texts in Theoretical Computer Science. An EATCS Series) >>From the back cover: This book gives a comprehensive overview of central topics in finite model theory - expressive power of logics, descriptive complexity, and zero-one laws - together with selected applications relating to database theory and artificial intelligence, especially constraint databases and constraint satisfaction problems. The final chapter provides a concise modern introduction to modal logic, emphasizing the interaction with finite model theory. The underlying theme of the book is the use of first-order, second-order, fixed-point, and infinitary logic, as well as various fragments of and hierarchies within these logics, to gain insight into phenomena and problems in complexity theory and combinatorics. The book emphasizes the use of combinatorial games, such as extensions and refinements of the Ehrenfeucht-Fraissi games, as a powerful way to analyze the expressive power of logics, and illustrates how sophisticated notions from model theory and combinatorics, such as o-minimality and treewidth, arise naturally in the applications of finite model theory to database theory and artificial intelligence. Students of logic and computer science will find here the tools necessary to embark on research into finite model theory, and all readers will experience the excitement of a vibrant area of the applications of logic to computer science. Table of contents: 1.Unifying Themes in Finite Model Theory 2.On the Expressive Power of Logics on Finite Models 3.Finite Model Theory and Descriptive Complexity 4.Logic and Random Structures 5.Embedded Finite Models and Constraint Databases 6.A Logical Approach to Constraint Satisfaction 7.Local Variations on a Loose Theme: Modal Logic and Decidability To order, see http://www.springer.com/978-3-540-00428-8

1 0

CALCO-07 - Call for Participation
by Michal Walicki 14 May '07

14 May '07

CALCO 2007 2nd Conference on Algebra and Coalgebra in Computer Science CALCO Tools Day August 20-24, 2007, Bergen, Norway May 16 Early Registration deadline July 1 Registration deadline ------------------------------------------------------------------ http://www.ii.uib.no/calco07/ ------------------------------------------------------------------ August 20 CALCO-jnr, CALCO-tools August 21-24 CALCO technical programme CALCO'07 takes place at the Grand Hotel Terminus in Bergen, one of many historic hotels in Norway. The conference starts Monday with two workshops followed by an official reception Monday evening. The main program runs Tuesday through Friday, each morning starting with an invited speaker. Additional events are excursion by boat in the Bergen archipelago (Wednesday afternoon) and conference dinner on one of the mountains surrounding the city centre (Thursday afternoon). Registration ------------ Registration fee is 3200 NOK (1200 NOK for students), with substantial discounts for early registration. The fee includes the full conference with all workshops, a copy of the proceedings, lunches and coffee breaks, internet access and the official reception Monday evening. Registration is via the calco07 web site: http://www.ii.uib.no/calco07/ Note that Bergen is very busy during the tourist season, so early booking of accommodation and transportation is recommended. Main CALCO'07 conference ------------------------ CALCO is a high-level, bi-annual conference. It 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. The accepted papers report 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. Some main key words are: * Abstract models and logics * Specialised models and calculi * Algebraic and coalgebraic semantics * System specification and verification The list of accepted papers is available at the web site. Invited speakers ---------------- Stephen L. Bloom, Stevens Institute of Technology, NJ, USA Prof. Bloom works on algebraic specification theories and was instrumental in developing iterative theories, an elaborate coalgebraic method - predating coalgebras. Luis Caires, New University of Lisbon, Portugal Prof. Caires has made important contributions to the field of distributed and mobile systems, and spatial logics for these. Barbara Knig, University of Duisburg-Essen, Germany Prof. Knig works on graph transformation systems, with applications to concurrent and mobile systems, software reliability and security. Glynn Winskel, University of Cambridge, United Kingdom Prof. Winskel is well-known for his fundamental work in semantics and theory of concurrency. CALCO-jnr (CALCO Young Researchers Workshop) -------------------------------------------- CALCO-jnr is dedicated to presentations by PhD students and by those who completed their doctoral studies within the past few years. This year 12 contributions within the theme of CALCO have been accepted. See the overview on the CALCO-jnr web page on the CALCO web site. -- http://www.ii.uib.no/calco07/

1 0

An obituary for Max
by Ross Street 14 May '07

14 May '07

See the latest issue of the Aust Math Soc Gazette <http://www.austms.org.au/Gazette> Ross

1 0

WoLLIC'2007 - Call for Participation
by ruy＠cin.ufpe.br 12 May '07

12 May '07

[** sincere apologies for duplicates **] Call for Participation 14th Workshop on Logic, Language, Information and Computation (WoLLIC'2007) Rio de Janeiro, Brazil July 2-5, 2007 (a satellite event to Brazilian Computer Society Conference - CSBC'07) WoLLIC is an annual international forum on inter-disciplinary research involving formal logic, computing and programming theory, and natural language and reasoning. Each meeting includes invited talks and tutorials as well as contributed papers. The Fourteenth WoLLIC will be held in Rio de Janeiro, Brazil, from July 2 to July 5, 2007, in conjunction with the 27th Brazilian Computer Society Conference. It is sponsored by the Association for Symbolic Logic (ASL), the Interest Group in Pure and Applied Logics (IGPL), the European Association for Logic, Language and Information (FoLLI), the European Association for Theoretical Computer Science (EATCS), the Sociedade Brasileira de Computacao (SBC), and the Sociedade Brasileira de Logica (SBL). PROCEEDINGS The proceedings of WoLLIC'2007, including both invited and contributed papers, will be published in advance of the meeting as a volume in Springer's Lecture Notes in Computer Science. In addition, abstracts will be published in the Conference Report section of the Logic Journal of the IGPL, and selected contributions will be published as a special post-conference WoLLIC'2007 special issue of the journal Information and Computation. INVITED SPEAKERS Alex Borgida (Rutgers) Alessandra Carbone (Paris) Martin Escardo (Birmingham) Philippa Gardner (Imperial Coll) Achim Jung (Birmingham) Louis Kauffman (U Illinois Chicago) Michael Moortgat (Utrecht) Paulo Oliva (London/QM) John Reif (Duke) Yde Venema (Amsterdam) TUTORIAL LECTURES Stone duality, by A. Jung Quantum topology and quantum computation, by L. Kauffman Biological computing, by J. Reif INVITED TALKS Description Logics: formal foundations and applications, by A. Borgida Group Theory and Classical Proofs, by A. Carbone Algorithmic Topology of Program Types, by M. Escardo Contex Logic and Tree Update, by Ph. Gardner On the interplay of logic and information: A topological analysis, by A. Jung Spin networks in quantum computation, by L. Kauffman Symmetries in natural language syntax and semantics: the Lambek-Grishin calculus, by M. Moortgat Computational Interpretations of Classical Linear Logic, by P. Oliva Autonomous programmable biomolecular devices using self-assembled DNA nanostructures specifying properties of data DNA Nanostructures, by J. Reif A modal distributive law, by Y. Venema BOOK EXHIBITION The following publishers are expected to be exhibiting various books from their catalogue, prospectuses, journal samples, etc., and there will be a chance to order items at promotional prices: The MIT Press Springer-Verlag A K Peters Cambridge Univ Press CSLI Publications (Stanford Univ) Oxford Univ Press World Scientific It is likely that a few other international publishers will also take part in the book exhibit. PROGRAM COMMITTEE Samson Abramsky (U Oxford) Michael Benedikt (Bell Labs) Lars Birkedal (ITU Copenhagen) Andreas Blass (U Michigan) Thierry Coquand (Chalmers U, Goteborg) Jan van Eijck (CWI, Amsterdam) Marcelo Finger (U Sao Paulo) Rob Goldblatt (Victoria U, Wellington) Yuri Gurevich (Microsoft Redmond) Hermann Haeusler (PUC Rio) Masami Hagiya (Tokyo U) Joseph Halpern (Cornell U) John Harrison (Intel UK) Wilfrid Hodges (U London/QM) Phokion Kolaitis (IBM Almaden Research Center) Marta Kwiatkowska (U Birmingham) Daniel Leivant (Indiana U) (Chair) Maurizio Lenzerini (U Rome) Jean-Yves Marion (LORIA Nancy) Dale Miller (Polytechnique Paris) John Mitchell (Stanford U) Lawrence Moss (Indiana U) Peter O'Hearn (U London/QM) Prakash Panangaden (McGill, Montreal) Christine Paulin-Mohring (Paris-Sud, Orsay) Alexander Razborov (Steklov, Moscow) Helmut Schwichtenberg (Munich U) Jouko Vaananen (U Helsinki) ORGANISING COMMITTEE Marcelo da Silva Correa (U Fed Fluminense) Renata P. de Freitas (U Fed Fluminense) Ana Teresa Martins (U Fed Ceara') Anjolina de Oliveira (U Fed Pernambuco) Ruy de Queiroz (U Fed Pernambuco, co-chair) Petrucio Viana (U Fed Fluminense, co-chair) WEB PAGE www.cin.ufpe.br/~wollic/wollic2007 ---

1 0

FMCS 2007 - Final Call for Participation
by Philip Mulry 12 May '07

12 May '07

**************************************************** Final Announcement - FMCS 2007 This is the final call for participation in FMCS 2007 *** The registration deadline is May 20. *** University accommodations can not be guaranteed after that date. The Department of Computer Science at Colgate University is hosting Foundational Methods in Computer Science 2007 on the Colgate University campus 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. Invited speakers this year include: a.. Steve Awodey(Carnegie Mellon) b.. Steve Bloom(Stevens) c.. Robin Cockett (Calgary) d.. Paul Hudak(Yale) e.. Ernie Manes (U Mass) f.. Robert Rosebrugh(Mount Allison) The remaining research talks are solicited from participants. Time slots are limited, so please register early if you would like to be considered for a talk. Graduate student participation is particularly encouraged at FMCS 2007. Students will pay a reduced registration fee. Conference Link: http://cs.colgate.edu/faculty/mulry/FMCS2007/FMCS2007.html Contacts The local organizer of FMCS 2007 is: Philip Mulry The secretary for FMCS 2007 is Char Jablonski

1 0