May 2004 - Categories - categories.org.au

book: Mal'cev, Protomodular, Homological and Semi-Abelian Categories
by bourn 12 May '04

12 May '04

This is to announce the publication of the following book Truly yours Francis Borceux and Dominique Bourn Mal'cev, Protomodular, Homological and Semi-Abelian Categories -------------------------------------------------------------- by Francis Borceux and Dominique Bourn Mathematics and its Applications, volume 566, 2004 Kluwer Academic Publishers, Dordrecht, Boston, London ISBN 1-4020-1961-0 The purpose of the book is to take stock of the situation concerning Algebra via Category Theory in the last fifteen years, where the new and synthetic notions of Mal'cev, protomodular, homological and semi-abelian categories emerged. These notions force attention on the fibration of points and allow a unified treatment of the main algebraic: homological lemmas, Noether isomorphisms, commutator theory. The book gives full importance to examples and makes strong connections with Universal Algebra. One of its aims is to allow appreciating how productive the essential categorical constraint is: knowing an object, not from inside via its elements, but from outside via its relations with its environment. The book is intended to be a powerful tool in the hands of researchers in category theory, homology theory and universal algebra, as well as a textbook for graduate courses on these topics. The table of contents is the following: Preface Metatheorems ------------ 0.1 The Yoneda embedding 0.2 Pointed categories 1. Intrinsic centrality ----------------------- 1.1 Spans and relations 1.2 Unital categories 1.3 Cooperating and central morphisms 1.4 Commutative objects 1.5 Symmetrizable morphisms 1.6 Regular unital categories 1.7 Associated abelian object 1.8 Strongly unital categories 1.9 Gregarious objects 1.10 Linear and additive categories 1.11 Antilinear and antiadditive categories 1.12 Complemented subobjects 2. Mal'cev categories --------------------- 2.1 Slices, coslices and points 2.2 Mal'cev categories 2.3 Abelian objects in Mal'cev categories 2.4 Naturally Mal'cev categories 2.5 Regular Mal'cev categories 2.6 Connectors in Mal'cev categories 2.7 Connector and cooperator 2.8 Associated abelian object and commutator 2.9 Protoarithmetical categories 2.10 Antilinear Mal'cev categories 2.11 Abelian groupoids 3. Protomodular categories -------------------------- 3.1 Definition and examples 3.2 Normal subobjects 3.3 Couniversal property of the product 3.4 Groupoids, protomodularity and normality 4. Homological categories ------------------------- 4.1 The short five lemma 4.2 The nine lemma 4.3 The Noether isomorphism theorems 4.4 The snake lemma 4.5 The long exact homology sequence 4.6 Examples of homological categories 5. Semi-abelian categories -------------------------- 5.1 Definition and examples 5.2 Semi-direct products 5.3 Semi-associative Mal'cev varieties 6. Strongly protomodular categories ----------------------------------- 6.1 Centrality and normality 6.2 Normal subobjects in the fibres 6.3 Normal functors 6.4 Strongly protomodular categories 6.5 A counterexample 6.6 Connector and cooperator 7. Essentially affine categories -------------------------------- 7.1 The fibration of points 7.2 Essentially affine categories 7.3 Abelian extensions Appendix -------- A.1 Algebraic theories A.2 Internal relations A.3 Internal groupoids A.4 Variations on epimorphisms A.5 Regular and exact categories A.6 Monads A.7 Fibrations Classification table of the fibration of points

1 0

Naive question: game semantics vs game theory
by Galchin Vasili 10 May '04

10 May '04

Hello, What relation if any is there between game semantics and game theory a la von Neumann/Nash? Also what is relationship between game theory in model theory and von Neumann/Nash game theory? Kind regards, Bill Halchin

4 3

jobs: 4 LECTURERS IN COMPUTER SCIENCE
by Susan Bates 06 May '04

06 May '04

UNIVERSITY OF DURHAM DEPARTMENT OF COMPUTER SCIENCE 4 Lecturer Posts Up to 4 appointments will be made at the level of Lecturer. It is expected that applicants will range from young researchers who have just completed their PhDs through to established academics with internationally-leading research profiles. Common to all appointments will be a high quality research portfolio or demonstrable potential of such. All positions are tenable from 1st September 2004 or from a mutually acceptable date thereafter. Further particulars can be obtained from the University's jobs pages at: https://jobs.dur.ac.uk/home.asp The Department of Computer Science has recently appointed 8 new members of academic staff, 7 of whom are due to arrive in Durham in summer 2004 and 1 at a later date (see http://www.durham.ac.uk/computer.science for more details). This second phase of our recruitment will take the number of full-time permanent academic staff up to 20, with the intention being to increase this number to 25 by 2006. The appointments will be split across the 2 research groups, which are Theoretical Computer Science, and Software Engineering and Distributed Systems. 2 Lectureships will support the new Professor of Computer Science, Professor Hajo Broersma, and 2 Lectureships will support the Software Engineering and Distributed Systems research group. As regards the 2 Lectureships in Theoretical Computer Science, applications are welcomed from candidates with research interests ranging across the subject, but applications are particularly encouraged from candidates with research interests in: algorithmic graph theory; computational complexity; graph theory and combinatorics; communications networks; and probabilistic and randomised algorithms. As regards the 2 Lectureships in Software Engineering and Distributed Computing, applications are welcomed from candidates whose research interests lie within the broad area covered by these subjects. However, applicants with research interests in visualisation and distributed architectures as they relate to e-Science or in inter-disciplinary applications are particular welcome. Applicants unsure as to whether their research expertise falls under that described above are encouraged to informally contact Professor Iain Stewart who can provide advice and guidance. As mentioned earlier, the first phase of our reorganisation commenced with the advertisement of positions in October 2003. Given that about 7 months have elapsed since then and previous applicants personal details may have changed considerably in that time, previous applicants for the positions advertised in October 2003 are encouraged to re-apply if they feel that their situation merits it. Again, any previous applicants who are undecided should contact Professor Iain Stewart for advice and guidance. Further details on the University of Durham can be found via the web-pages at http://www.durham.ac.uk, and on the Department of Computer Science via the web-pages at http://www.durham.ac.uk/computer.science. Informal enquiries about any of the positions may be made to Professor Iain Stewart: telephone +44 (0)191 3341720; e-mail i.a.stewart(a)durham.ac.uk.

1 0

Arithmetic Universes and Abstract Stone Duality
by Paul Taylor 04 May '04

04 May '04

Arithmetic Universes and Abstract Stone Duality -- Paul Taylor www.cs.man.ac.uk/~pt/ASD (a) Inside every model of Abstract Stone Duality lies an Arithmetic Universe (b) Every Arithmetic Universe is embedded in a model of Abstract Stone Duality. The first is the title of a new draft paper, available from the web page above, on which your comments are invited. I haven't written up the second, but the essence of the argument follows below. The "embedding" in question is (up to equivalence) as exactly the full subcategory of overt discrete objects. ABSTRACT of (a): The first paper published on Abstract Stone Duality showed that the overt discrete objects (those admitting exists and equality internally) form a pretopos, ie admit finite limits, stable disjoint coproducts and stable effective quotients of equivalence relations. Using an N-indexed least fixed point axiom, here we show that this full subcategory is an arithmetic universe, having a free semilattice (KX, "collection of Kuratowski-finite subsets") and a free monoid (List X, "collection of lists") on any overt discrete object. Each finite subset is represented by its pair ([], <>) of modal operators (although a tight correspondence with these depends on a stronger Scott-continuity axiom). Topologically, such subsets are both compact and open and also involve proper open maps. In applications of ASD this can eliminate lists in favour of a continuation-passing interpretation. The three aspects of the paper to which I would like to draw your attention are: The use of modal operators is related to the three powerdomains (in particular to the Plotkin or convex one) in domain theory. The construction itself is a domain-theoretic one, as the object KX is constructed by means of an idempotent that is the solution of a fixed point equation. A novel induction principle is needed to prove the modal laws from the fixed point equation. The final section shows how KX is a "finite powerset" in that it classifies Kuratowski-finite subsets or compact open subspaces of X. More generally, maps Gamma->KX correspond to open relations U subset Gamma x X for which U->Gamma is proper. As this paper is the first serious use of internal induction and recursion in ASD, it forced me to reconsider the definition of the natural numbers object in this category without arbitrary equalisers (cf my message to "categories" on 4 November). Proof-theoretically, this means that the judgements in the ASD lambda-calculus must allow equations as well as assignments of types to variables as hypotheses. Topologically, this may provide a way of extending ASD from locally compact locales to all locales (but as several previous attempts to do this have failed, I'm making no promises here). THE CONVERSE (b) - embedding a given AU in a model of ASD. There are numerous constructions and characterisations of categories of domains using "bases", "information systems", "approximable relations" etc., most notably that in Dana Scott's 1982 "Domains for Denotational Semantics" that defined what have since become known as Scott domains. In these, each domain is encoded as a set of tokens, possibly with other structure such as a closure condition, and each continuous function is encoded as a relation between tokens. Although these constructions were almost invariably presented in very concrete language with "set" meaning "set", the categorically astute observer will notice that they need far less than full set theory in the metalanguage. In fact they require - cartesian products (products) - sets of solutions of equations (equalisers) - disjoint unions (extensivity - stable disjoint coproducts) - relations considered as a notion of function (regularity - stable image factorisation) - relations considered as a notion of equality (exactness - stable effective quotients of equivalence relations) - definition by description and - recursion over lists (free monoids), where the formal categorical names are given in brackets for the various notions that are to be found in a first year "Discrete Math" course. All but the last define a PRETOPOS, and including the last we have an ARITHMETIC UNIVERSE (AU). One way to construct a model of ASD around an AU would be as the category of "abstract bases" and "abstract matrices" defined in my paper "Computably based locally compact spaces". (My abstract bases are similar to the "strong proximity lattices" used by Achim Jung and others to characterise stably locally compact spaces.) However, such a construction would be rather difficult - and unnecessarily so, as "Subspaces in ASD" already provides a general way of adding the monadic property to a given category that has powers of an object Sigma. All we need, therefore, is a category in which the given AU embeds as a full subcategory, in which there are powers of an object Sigma. In classical terms, a suitable such category would be that of disjoint unions of algebraic lattices, with Scott-continuous maps. For convenience, we call such a disjoint union a "predomain". An "information system" construction would encode a predomain as a family of sets of tokens, each set being equipped with a finitary closure relation. The members of the family correspond to the components of the disjoint union. A "family of sets" can be encoded in an AU as a single morphism, and a relation as a subobject. The morphisms are "approximable relations", which are also encoded as subobjects. This category has finite products and stable disjoint coproducts, and the given AU is embedded as a full subcategory: an object N of the AU becomes the predomain encoded as the N-indexed family of empty sets (the morphism 0->N). Sigma is encoded as the family consisting of a single singleton (the morphism 1->1). The exponential Sigma^X exists for any predomain X, encoded as the family whose one member is the set of finite sets of tokens of X - this is where the free semilattice comes in. One striking but actually very simple property of this category of predomains is that Sigma classifies subobjects in the AU: U ----> 1 v | | |--- | top | | v v N ----> Sigma That is, Sigma has exactly the defining property of a subobject classifier (Omega), as if the AU were an elementary topos - except that the object Sigma belongs to the larger category of predomains, not to the given AU. This property is achieved by the same sleight of hand that often makes category theory so powerful - we may encode objects and morphisms of a category as we please, in this case as subobjects (it would be better to say monomorphisms) of a given category. Besides having powers of Sigma and embedding the AU exactly as its full subcategory of overt discrete objects, the category of predomains obeys the Phoa principle, its morphisms are all Scott continuous and its objects are Sigma-split subspaces of Sigma^N. Its "monadic completion" (using "Subspaces in ASD") is therefore exactly the kind of category that is discussed in "Computably based locally compact spaces". In particular, no new overt discrete objects are added by these constructions: the given AU is embedded (up to equivalence) as exactly the full subcategory of overt discrete objects. It seems to me that the "equivalence" between AUs and ASD that is established by these two results should be very significant. Andre' Joyal originally introduced AUs because they are the minimal natural categorical structure in which one can form the free internal thing of the same kind. Since any AU can be embedded in a model of ASD, we can use domain theoretic methods (of which my new paper is a clumsy simple example) to construct free internal algebras (including free categories) and cofree internal coalgebras. The semantics of WHILE programs given in "first order" terms using coequalisers in Section 6.4 of "Practical Foundations" is really the same thing as the better known "higher order" domain-theoretic fixed point semantics. On the other hand, we may construct the free internal AU as a subcategory of the free internal model of ASD. Paul Taylor www.cs.man.ac.uk/~pt pt(a)cs.man.ac.uk University of Manchester ("East London Campus")

1 0

ICCL Summer School 2004 - Final Call
by Int. Center for Computational Logic 04 May '04

04 May '04

ICCL Summer School 2004 Proof Theory and Automated Theorem Proving ------------------------------------------ PCC Workshop 2004 ------------------------------- Technische Universitaet Dresden June 14-25, 2004 <http://www.iccl.tu-dresden.de/events/SA-2004> Call for Participation ---------------------- This two-week meeting consists of two integrated parts, a summer school and a workshop, aimed at graduate students and researchers. The themes for the summer school are proof theory and automated theorem proving, the workshop is about proof, computation and complexity. As in the summer schools at TU Dresden in 2002 and 2003 and in the previous editions of the PCC workshop, people from distinct but communicating communities will gather in an informal and friendly atmosphere. We ask for a participation fee of 200 EUR. We request registration before May 10, 2004; please send an email to <mailto:PTEvent@ICCL.TU-Dresden.DE>, making sure you include a very brief bio (5-10 lines) stating your experience, interests, home page (if available), etc. It will be possible for some students to present their work: please indicate in your application if you would like to do so and give us some information about your proposed talk. We will select applicants in case of excessive demand. A limited number of grants covering all expenses is available, please indicate in your application if the only possibility for you to participate is via a grant. Applications for grants must include an estimate of travel costs and they should be sent together with the registration. We will provide assistance in finding an accommodation in Dresden. Week 1, June 14-17: courses on Term Rewriting Systems Franz Baader (TU Dresden) Deep Inference and the Calculus of Structures Alessio Guglielmi (TU Dresden) Game Semantics and Its Applications C.-H. L. Ong (Oxford) On June 14 Prof Wolfgang Bibel will give an invited lecture June 17-19: workshop For more details, please consult the workshop web page <http://www1.informatik.unibw-muenchen.de/Birgit/pcc04.html> Week 2, June 21-25: courses on Deduction Modulo Claude Kirchner (Loria & INRIA, Nancy) Logic Considered as a Branch of Geometry Francois Lamarche (Loria & INRIA, Nancy) Proofs as Programs Michel Parigot (CNRS - Universite' Paris 7) Automated Reasoning for Substructural Logics John Slaney (NICTA, Canberra and Australian National University) Automated Theorem Proving for Classical Logics Andrei Voronkov (Manchester) Venue ----- Dresden, on the river Elbe, is one of the most important art cities of Germany. You can find world-class museums and wonderful architecture and surroundings. We will organize trips and social events. Organization ------------ This event is organized by the International Center for Computational Logic (ICCL), Paola Bruscoli, Birgit Elbl, Sylvia Epp, Bertram Fronhoefer, Axel Grossmann, Alessio Guglielmi, Steffen Hoelldobler, Reinhard Kahle and Mariana Stantcheva; it is sponsored by Deutscher Akademischer Austausch Dienst (DAAD), under the program `Deutsche Sommer-Akademie', and CoLogNet. Please distribute this message broadly.

1 0