February 2008 - 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

A small cartesian closed concrete category
by PETER EASTHOPE 04 Mar '08

04 Mar '08

Is there a cartesian closed concrete category which is small enough to write out explicitly? It would be helpful in learning about map objects, exponentiation, distributivity and etc. Can such a category be made with binary numbers for instance? Thanks, ... Peter E. http://carnot.yi.org/

10 9

Backup TeX editor
by Michael Barr 01 Mar '08

01 Mar '08

[Note from moderator: Please cc: any expressions of interest to tac(a)mta.ca] TAC has been in existence now for 13 years. For about the first half of its existence, Bob did everything to get papers ready for publication. He did consult with me if he had particular tex problems. About when I retired, I took on the task of preparing papers (most of them) for publication. However I am uncomfortable with being the only one who really understands what is going on with tac.cls. I would like to find a volunteer to back me up, with a view to eventually taking over when the times comes, as it must, that I can no longer do the job. The job is not onerous. We get about 20 papers a year. On average, a paper takes a couple hours of preparation. Sometimes it is more, but often there is essentially no prep time since the author has used tac.cls and made no formatting errors. I am not planning on stopping this any time soon, but I think it is past time to prepare for the future. Michael

2 1

preprints available
by Ronnie 29 Feb '08

29 Feb '08

The following are available from my preprint page, by me unless stated otherwise: http://www.bangor.ac.uk/~mas010/brownpr.html 1) 08.04 Exact sequences of fibrations of crossed complexes, homotopy classification of maps, and nonabelian extensions of groups ABSTRACT: The classifying space of a crossed complex generalises the construction of Eilenberg-Mac Lane spaces. We show how the theory of fibrations of crossed complexes allows the analysis of homotopy classes of maps from a free crossed complex to such a classifying space. This gives results on the homotopy classification of maps from a CW-complex to the classifying space of a crossed module and also, more generally, of a crossed complex whose homotopy groups vanish in dimensions between 1 and n. The results are analogous to those for the obstruction to an abstract kernel in group extension theory. 2) 06.04 R. Brown, I. Morris, J. Shrimpton and C.D. Wensley Graphs of morphisms of graphs ABSTRACT: This is an account for the combinatorially minded reader of various categories of directed and undirected graphs, and their analogies with the category of sets. As an application, the endomorphisms of a graph are in this context not only composable, giving a monoid structure, but also have a notion of adjacency, so that the set of endomorphisms is both a monoid and a graph. We extend Shrimpton's (unpublished) investigations on the morphism digraphs of reflexive digraphs to the undirected case by using an equivalence between a category of reflexive, undirected graphs and the category of reflexive, directed graphs with reversal. In so doing, we emphasise a picture of the elements of an undirected graph, as involving two types of edges with a single vertex, namely `bands' and `loops'. Such edges are distinguished by the behaviour of morphisms with respect to these elements. 3) Possible connections between whiskered categories and groupoids, many object Lie algebras, automorphism structures and local-to-global questions ABSTRACT: We define the notion of whiskered categories and groupoids and discuss potential applications and extensions, for example to a many object Lie theory, and to resolutions of monoids. This paper is more an outline of a possible programme or programmes than giving conclusive results. 4) A new higher homotopy groupoid: the fundamental globular $\omega$-groupoid of a filtered space MSC Classification:18D10, 18G30, 18G50, 20L05, 55N10, 55N25. KEY WORDS: filtered space, higher homotopy van Kampen theorem, cubical singular complex, free globular groupoid ABSTRACT: We show that the graded set of filter homotopy classes rel vertices of maps from the $n$-globe to a filtered space may be given the structure of globular $\omega$--groupoid. The proofs use an analogous fundamental cubical $\omega$--groupoid due to the author and Philip Higgins. This method also relates the construction to the fundamental crossed complex of a filtered space, and this relation allows the proof that the crossed complex associated to the free globular $\omega$-groupoid on one element of dimension $n$ is the fundamental crossed complex of the $n$-globe. Ronnie

1 0

Mismatch in lcc pretoposes with W-types?
by Sam Staton 29 Feb '08

29 Feb '08

Various people (including Moerdijk & Palmgren, Hyland & Gambino, Abbott & Altenkirch & Ghani) have considered locally cartesian closed pretoposes with W-types, ie initial algebras for generalized polynomial functors, aka 'containers'. (These W-types are an appropriate analysis of the fixed points of intensional constructions and so these categories have been motivated as "constructive toposes", as models of a particular version of Martin-Lof's type theory). Lcc pretoposes are Heyting pretoposes. For any object X, consider those monotone endofunctions on the class Sub(X) that can be constructed from the pullback functors and their left and right adjoints. By my calculations, in a topos, these monotone endofunctions have least and greatest fixed points (by internalizing them and then using Tarski's fixed point theorem). It seems that, in general, these monotone endofunctions will not have least or greatest fixed points in lcc pretoposes with W-types. (I haven't proved this, though, and perhaps I have missed a neat trick.) If I'm not mistaken, this is a mismatch. Lcc pretoposes let you work both intensionally and extensionally, yet when it comes to W-types, we only consider the intensional constructions. Is there a reason for this?-- are these fixed points "non-constructive" or "impredicative" in some sense? Has anybody thought about these things before? Have I missed something? All the best, Sam [My example is bisimilarity for transition systems, as studied in concurrency theory. This is conventionally calculated as a maximum fixed point for a monotone endofunction on the lattice of binary relations. I can define a 'constructive' version of bisimilarity using W-types, and then take the image. This differs from the usual notion, unless choice is assumed.]

3 2

CMCS 08: final call for short contributions
by Clemens Kupke 27 Feb '08

27 Feb '08

---------------------------------------------------------------------- CMCS 08 : FINAL CALL FOR SHORT CONTRIBUTIONS 9th International Workshop on Coalgebraic Methods in Computer Science http://www.cwi.nl/projects/cmcs08/ Budapest, Hungary April 4-6, 2008 Key Note Speaker: Dexter Kozen Invited Speakers: Stefan Milius and Dirk Pattinson The workshop will be held in conjunction with the 11th European Joint Conferences on Theory and Practice of Software ETAPS 2008 March 29 - April 6, 2008 Following the tradition of preceding workshops we invite short contributions that will be collected in a technical report of the Technical University of Braunschweig. They should be no more than two pages and may describe work in progress, summarise work submitted to a conference or workshop elsewhere, or in some other way appeal to the CMCS audience. They should be submitted in postscript or pdf form as attachments to an email to cmcs08(a)cwi.nl. Deadline for submission of short contributions: March 10, 2008. Notification of acceptance of short contributions: March 17, 2008. Jiri Adamek and Clemens Kupke PC co-chairs

1 0

GALOP@ETAPS'08: Call for participation
by Russ Harmer 26 Feb '08

26 Feb '08

This is a Call for Participation to the 3rd International Workshop on Games for Logic and Programming Languages (GALOP3) to be held at ETAPS, on 5--6 April 2008, in Budapest. Invited speakers are: # Gabriel Sandu (University of Helsinki): Independence between quantifiers # Merlijn Sevenster (Universiteit van Amsterdam): Independence between modal operators # Paul-André Melliès (PPS, CNRS & Paris-Diderot): Game semantics as string diagrams More details about the workshop, including a list of accepted contributions, can be found at: http://www.cs.bham.ac.uk/~drg/galop.html To register for the workshop, please use the following link: http://etaps08.mit.bme.hu/

1 0

Language of an internal category?
by Nath Rao 26 Feb '08

26 Feb '08

Is there a version of Mitchell-Benabou language for internal categories in toposes (with natural number objects)? What I have in mind is something that will allow automatic translations of definitions and proofs to internal categories that gives the expected results for established notions. [I have glanced through "Relative set theories", and the relevant chapters of Jacobs, "Categorical logic and type theory"; they do not seem to what I am looking for, in the sense that the primary focus is not on the properties of the internal category.] Thanks in advance Nath Rao

1 0

Postdoctoral Fellowhships
by Matthew Hennessy 26 Feb '08

26 Feb '08

Apologies for Multiple Postings --------------------------------------------------- The Foundations of Global Computing - Trinity College Dublin Two postdoctoral Research Fellowships Applications are invited for TWO post-doctoral positions to undertake research into the foundations of Global Computing. The posts are within the Software Systems Lab of the Department of Computer Science at Trinity College Dublin as part of a new SFI-funded research project, under the direction of Matthew Hennessy, which seeks to establish a firm mathematical and logical basis for the next generation of widely distributed computing computing environments. Applicants should have a PhD in Computer Science, or a closely related discipline. Candidates with expertise in following areas are particularly welcome: - operational semantics - concurrency theory - model checking - verification techniques - type theory - program logics These posts are tenable from April 2008 at a salary commensurate with the successful candidates' qualifications and experience. Appointments will be made initially for a 24 month period, although there will be scope for extension. Further particulars of the posts may be obtained from the address below, and informal enquiries are also welcomed. Applications should include - detailed curriculum vitae, in pdf format - copies of relevant publications, or url-pointers to them - the names of two referees - a statement outlining the applicant's suitability to the project. Applications should be sent to: Matthew Hennessy Department of Computer Science The O'Reilly Institute Trinity College Dublin 2 Ireland email: matthew.hennessy(a)cs.tcd.ie tel: +353 (01) 8962634 Trinity College is an equal opportunities employer.

1 0

REACHABILITY PROBLEMS (RP'08) Liverpool, 15-17 September 2008
by Potapov, Igor 24 Feb '08

24 Feb '08

2nd WORKSHOP ON REACHABILITY PROBLEMS, RP'08 (September 15-17, 2008, Liverpool, UK) Deadline for submissions: 19 May, 2008 http://www.csc.liv.ac.uk/~rp2008/ The Workshop on Reachability Problems will take place at the University of Liverpool, Liverpool, UK on September 15-17, 2008. Papers presenting original contributions related to reachability problems in different computational models and systems are being sought. The Reachability Workshop is specifically aimed at gathering together scholars from diverse disciplines and backgrounds interested in reachability problems that appear in - Algebraic structures - Computational models - Hybrid systems - Verification Invited Speakers: ================ - Ahmed Bouajjani, Paris, France - Juhani Karhumaki, Turku, Finland - Colin Stirling, Edinburgh, UK - Wolfgang Thomas, Aachen, Germany Submissions: ============ Papers presenting original contributions related to reachability problems in different computational models and systems are being sought. Topics of interest include (but are not limited to): Reachability probelms in infinite state systems, rewriting systems, dynamical and hybrid systems; reachability problems in logic and verification; reachability analysis in different computational models, counter/ timed/ cellular/ communicating automata; Petri-Nets; computational aspects of algebraic structures (semigroups, groups and rings); predictability in iterative maps and new computational paradigms. Authors are invited to submit a draft of a full paper with at most 12 pages (in standard LaTeX article style 11pt A4 paper) via the conference web page http://www.csc.liv.ac.uk/~rp2008/ . Proofs omitted due to space constraints must be put into an appendix to be read by the program committee members at their discretion. Submissions deviating from these guidelines risk rejection. Electronic submissions should be formatted in postscript or pdf. Simultaneous submission to other conferences or workshops with published proceedings is not allowed. Important dates: ================ Submission deadline : May 19, 2008 Notification to authors: June 30, 2008 Final version: July 15, 2008 Workshop: September 15-17, 2008 The proceedings of the workshop will appear in Electronic Notes in Theoretical Computer Science (ENTCS). ENTCS is published electronically on Science Direct, Elsevier's main platform for electronic publication to provide rapid publication and broad dissemination of the volumes in the series. Selected papers will appear in a special issue of a high quality journal. Program Committee: ================ - Parosh Aziz Abdulla , Uppsala - Eugene Asarin , Paris - Vincent Blondel, Louvain - Olivier Bournez, Nancy - Cristian S. Calude , Auckland - Javier Esparza , Munchen - Vesa Halava , Turku - Oscar Ibarra , Santa Barbara - Juhani Karhumaki, Turku - Igor Potapov , Liverpool - Colin Stirling, Edinburgh - Wolfgang Thomas , Aachen - Hsu-Chun Yen , Taipei Organizing Committee: ================ - Igor Potapov, Liverpool - Vesa Halava, Turku Contact: ================ RP'08, Department of Computer Science, University of Liverpool, Ashton Building, Ashton Street, Liverpool, L69 3BX E-mail: rp2008 [at] csc.liv.ac.uk Web: http://www.csc.liv.ac.uk/~rp2008/

1 0