April 2000 - Categories - categories.org.au

Osius' set theory
by Wilkins E B 11 May '00

11 May '00

Hello, In his 1974 paper Osius showed that there are enough transitive objects in the initial topos to define a naive set theory. He then goes on the assume his topoi are well-pointedness and produces a characterisation of the category of sets in terms familiar to set theorists. I'm wondering whether anyone has produced an axiomatic set theory from Osius' naive set theory which characterises the initial topos. -- Dr Elwood Wilkins e-mail: elwood(a)essex.ac.uk Senior Research Officer tel: (+44) (0)1206 872336 Department of Computer Science fax: (+44) (0)1206 872788 University of Essex, Colchester, Essex, UK

7 7

devissage
by Todd H. Trimble 30 Apr '00

30 Apr '00

In section 5 of his Esquisse d'un Programme, in connection with tame topology, Grothendieck says he was able to convince himself that a formalism of devissage had some meaning in the context of topoi, via a suitable notion of "canonical tubular neighborhood of a subtopos" in an ambient topos. Has anyone besides Grothendieck pursued this idea? Thanks, Todd

1 0

Associate Professorship in Logic in Computer Science, Aarhus, DK
by karen Kjær Møller 26 Apr '00

26 Apr '00

UNIVERSITY OF AARHUS DEPARTMENT OF COMPUTER SCIENCE A tenured position as associate professor in the area of Logic in Computer Science, i.e. computational logic in a broad sense, is available at the Department of Computer Science, starting August 1, 2000. Ideally we seek applicants who as well as exhibiting a broad and impressive knowledge of Logic applicable in Computer Science, are able to support and encourage Logic on a broad front within the department. As a minimum requirement, applicants must have documented scientific qualifications within the area (equivalent to a PhD plus at least 2-3 years additional research and teaching). The Department conducts research and teaching in theoretical as well as experimental computer science. The staff is close to 200 people, including 25 full or associate professors, and 50 PhD students. The number of M.Sc. students is approximately 500. The position is intended to strengthen the Department's existing research group in Theoretical Computer Science, and will be associated with Research Centre BRICS (http:www.brics.dk/). Applicants must submit a curriculum vitae, a description of scientific accomplishments, future research plans and participation in research programmes, a description of teaching experience, a list of publications (all in 4 copies), and 3 copies of publications to be considered in the evaluation. The Faculty refers to the Ministerial Order No. 650 of 31.8.1998 on the appointment of teaching and research staff at the universities under the Ministry of Research and Information Technology. Applications should be addressed to The Faculty of Science, University of Aarhus, Ny Munkegade, Building 520, DK-8000 Aarhus C, Denmark, and marked 212/5-189 The deadline for receipt of all applications is May 10, 2000, at 12,00. For more information, please contact the head of the department Kurt Jensen (e-mail: kjensen(a)daimi.au.dk. Phone: +45 8942 5612) or consult the Web pages: http://www.daimi.au.dk/

1 0

From finite sets to Feynman diagrams
by John Baez 26 Apr '00

26 Apr '00

Here's a paper that might be of interest to some category theorists, although it's actually aimed at a general audience, and secretly tries to get them interested in categories. Later we'll write a more technical paper about Feynman diagrams and `stuff operators'. >>From Finite Sets to Feynman Diagrams John C. Baez and James Dolan To appear in "Mathematics Unlimited - 2001 and Beyond", eds. Bjorn Engquist and Wilfried Schmid, Springer Verlag. Abstract: `Categorification' is the process of replacing equations by isomorphisms. We describe some of the ways a thoroughgoing emphasis on categorification can simplify and unify mathematics. We begin with elementary arithmetic, where the category of finite sets serves as a categorified version of the set of natural numbers, with disjoint union and Cartesian product playing the role of addition and multiplication. We sketch how categorifying the integers leads naturally to the infinite loop space Omega^infinity S^infinity, and how categorifying the positive rationals leads naturally to a notion of the `homotopy cardinality' of a tame space. Then we show how categorifying formal power series leads to Joyal's `especes des structures', or `structure types'. We also describe a useful generalization of structure types called `stuff types'. There is an inner product of stuff types that makes the category of stuff types into a categorified version of the Hilbert space of the quantized harmonic oscillator. We conclude by sketching how this idea gives a nice explanation of the combinatorics of Feynman diagrams. Available at: http://arXiv.org/abs/math.QA/0004133

1 0

Lectureships in Computer Science at Birmingham
by Marta Z Kwiatkowska 20 Apr '00

20 Apr '00

THE UNIVERSITY OF BIRMINGHAM SCHOOL OF COMPUTER SCIENCE Lectureship in Computer Science (3 posts) *** Closing date: 16th May 2000 *** Applications are invited for THREE Lectureships in Computer Science at the University of Birmingham. All areas will be considered, but preference will be given to candidates who are research active in areas listed below: Vision Computational Linguistics Commonsense Reasoning Robotics Agents Advanced Interaction Technology & Software Systems Verification Bioinformatics Evolutionary and Natural Computation For more information see http://www.bham.ac.uk/personnel/s35434.htm Informal enquiries to Prof Achim Jung (Head of School), Email A.Jung(a)cs.bham.ac.uk, tel +44 121 414 4776.

1 0

CT 2000: Registration and Accomodation
by RFC Walters 20 Apr '00

20 Apr '00

CATEGORY THEORY 2000 (CT 2000) July 16-22, 2000 Centro di Cultura Scientifica "Alessandro Volta" di Villa Olmo Como, Italy REGISTRATION and booking of ACCOMODATION for CT 2000 is now possible through the web page for the conference http://www.disi.unige.it/conferences/ct2000/ Accomodation in Como may be booked through the Centro di Cultura Scientifica "A. Volta", Villa Olmo, at the web page http://www.disi.unige.it/conferences/ct2000/accomodation_form.html The deadline for such a booking is 12th June 2000. Organizing Committee A. Carboni (Insubria) G. Rosolini (Genova) R.F.C. Walters (Insubria) 20th April 2000

1 0

LICS Workshop on Chu Spaces and Applications 25th June 2000,
by Valeria Correa Vaz de Paiva 14 Apr '00

14 Apr '00

Final CALL FOR PAPERS LICS'2000 Workshop on Chu Spaces: Theory and Applications Sunday, June 25, 2000, Santa Barbara, California http://www.cs.bham.ac.uk/~vdp/chu.html ****Submission deadline: April,25, 2000**** A Chu space is a related pair of complementary objects. Besides having intrinsic interest in their own right, Chu spaces have found applications to concurrent processes, information flow, linear logic, proof theory, and universal categories. The workshop is concerned with the theory and applications of Chu spaces, as well as related structures such as the Dialectica construction and double glueing. The workshop will bring together computer scientists, mathematicians, logicians, philosophers, and other interested parties to discuss the development of the subject with regard to its foundations, applications, prospects, and directions for future work. Work in the subject is currently fragmented across several areas: category theory, traditional model theory, concurrency, and the semantics of programming languages, and such a workshop can contribute to the coordination and possibly even some unification of these efforts. Suggested topics for presentation and discussion include but are by no means limited to new results about Chu spaces and related structures; their applications to various areas such as concurrency, games, proof theory, etc.; and their implications for foundations and philosophy of computation, mathematics, physics, and other disciplines. The workshop will be held on Sunday, June 25, 2000 at Santa Barbara, California, as an adjunct to the International Conference on Logic in Computer Science (LICS'2000), June 26-29 at the same location as per http://www.cs.bell-labs.com/who/libkin/lics/index.html. Papers within the scope of the workshop are solicited, and may be either work in progress or more mature work. Submission should be in the form of an extended abstract of at most 10 pages, in postscript format, mailed electronically to paiva(a)parc.xerox.com. Submissions will be evaluated by a committee selected by the organizers, and the full version of accepted papers will be printed in a proceedings available at the start of the workshop. Important dates: Extended abstract: April 25, 2000 Notification of acceptance: May 15, 2000 Proceedings version: June 9, 2000 The workshop will be one full day and is open to all interested researchers. Valeria de Paiva paiva(a)parc.xerox.com Vaughan Pratt pratt(a)cs.stanford.edu http://www.cs.bham.ac.uk/~vdp/chu.html

1 0

preprints available
by jvoosten＠math.uu.nl 14 Apr '00

14 Apr '00

The following preprints are available from the WWW: Jaap van Oosten Realizability: A Historical Essay http://www.math.uu.nl/publications/preprints/1131.ps.gz Abstract: historical survey on Realizability. Focuses on notions of realizability used in the study of metamathematics of arithmetical theories, and topos-theoretic developments. Bibliography contains 96 items.24 pages Lars Birkedal and Jaap van Oosten Relative and Modified Relative Realizability http://www.math.uu.nl/publications/preprints/1146.ps.gz Abstract: We approach `relative realizability' from an abstract point of view, studying internal partial combinatory algebras in an arbitrary topos E. Let RT(E,A) denote the standard realizability topos over E w.r.t. A. We define the notion of `elementary subobject' in a topos; if, for two internal pca's A and B in E, there is an embedding which maps A as elementary subobject into B, there is a local geometric morphism from RT(E,B) to RT(E,A). Next we study the situation where an internal topology j is given; we have a tripos over E using only the j-closed subobjects of A, giving a topos RTj(E,A). RTj(E,A) is a subtopos of RT(E,A) and we have a pullback diagram of toposes: Sh_j(E)--->RTj(E,A) | | | | V V E ----> RT(E,A) If A--> B is an embedding with A elementary subobject of B, the local geometric morphism restricts to a local geometric morphism: RTj(E,B)-->RTj(E,A) Moreover if A --> B is a j-dense embedding, there is a logical functor (a filter-quotient situation): RTj(E,A) --> RTj(E,B). If j is an open topology, the inclusion RTj(E,A)-->RT(E,A) is open too, and it makes sense to consider its closed complement; we call this the modified relative realizability topos Mj(E,A) w.r.t. A and j. We have an automatic pullback diagram Sh_k(E)---->Mj(E,A) | | | | V V E ----> RT(E,A) where k denotes the closed complement of j. In a section `Examples' we show that our treatment generalizes former definitions of relative realizability (in Awodey, Birkedal, Scott) and modified realizability. 16 pages.

1 0

LPAR'2000: call for papers
by parigot＠logique.jussieu.fr 14 Apr '00

14 Apr '00

[Apologies for receiving multiple copies] LPAR'2000 7th International Conference on LOGIC for PROGRAMMING and AUTOMATED REASONING Reunion Island, November 6-10, 2000 CALL FOR PAPERS Location: LPAR'2000 will be held November 6-10, 2000, on Reunion Island, a small french island in the Indian Ocean, to the east of Madagascar. It will be followed by a "Workshop on Implementations of Logic", November 11-12. Topics: * automated reasoning * lambda and combinatory calculi * interactive theorem proving * constructive logic and type theory * implementations of logic * computional interpretations of logic * design of logical frameworks * logical foundations of programming * program & system verification * logical aspects of concurrency * model checking * program extraction from proofs * rewriting * linear logic * logic programming * modal and temporal logics * constraints programming * knowledge representation & reasoning * logic and databases * reasoning about actions * logic & computational complexity * description logics * specification using logics * nonmonotonic reasoning Both "theoretical" papers and "experimental" papers are welcome. The first category is intended to contain new theoretical results, the second one to describe implementations of systems, to report experiments with implemented systems, or to compare implemented systems. Programme Committee: * Stefano Berardi, Torino * Patrick Lincoln, SRI * Manfred Broy, Munich * David McAllester, AT&T Labs * Maurice Bruynooghe, Leuven * Robert Nieuwenhuis, Barcelona * Gilles Dowek, INRIA * Mitsuhiro Okada, Tokyo * Harald Ganzinger, MPI * Catuscia Palamidessi, Penn State * Mike Gordon, Cambridge * Leszek Pacholski, Wroclaw * Yuri Gurevich, Microsoft Res. * Michel Parigot, Paris (co-chair) * Neil Jones, Copenhagen * Frank Pfenning, Pittsburgh * Teodor Knapik, Reunion * Helmut Schwichtenberg, Munich * Yves Lafont, Marseille * Jan Smith, Goteborg * Daniel Leivant, Bloomington * Wolfgang Thomas, Aachen * Giorgio Levi, Pisa * Pascal van Hentenryck, Providence * Leonid Libkin, Bell Labs * Andrei Voronkov, Manchester (co-chair) Organizing Committee: * Teodor Knapik, University of Reunion * Pascal Manoury, University of Paris VI * Andrei Voronkov, University of Manchester Submission of papers: Submitted papers must be original and not submitted concurrently for publication to a journal or to another conference. Submission by members of the Program Committee is not allowed. The proceedings of LPAR'2000 will be published by Springer-Verlag in the LNAI series and available at the conference. Submitted "theoretical" papers should not be longer than 15 proceedings pages. Submitted "experimental" papers should not be longer than 10 proceedings pages. Instructions for submission will be on the conference web page: http://www.cs.man.ac.uk/~voronkov/LPAR/2000/general.html Important dates: Submission: June 1 Notification: July 15 Final version: August 10 Conference: November 6-10 Worskhop: November 11-12 More information: http://www.cs.man.ac.uk/~voronkov/LPAR/2000/general.html

1 0

AB4.5
by Michael Barr 11 Apr '00

11 Apr '00

A day after I sent my previous note, I realized the (or an) answer. In fact, I seem to have discovered a new infinite exactness condition that is between AB4 and AB5 and, inevitably, I call AB4.5. So far I know only that it is implied by AB5, implies AB4 and, since module categories satisfy both AB5 and AB4.5*, it is definitely weaker than AB5. I do not, at this time, know that it is stronger than AB4. Here is how it works. Call a poset superdirected if it is directed and all down segments are finite. The natural numbers is one example and the set of finite subsets of any set is another. If I is superdirected, A an abelian category and F,G: I --> A are two diagrams, say that a natural transformation alpha: F --> G is supernatural (OK, suggestions for better names welcome) if for any i in I, the following: Look at the diagram consisting of all the Fj for j =< i and all the Gj for j < i. The arrows in the diagram are all the alpha j, for j =< i, as well as all the arrows from the restrictions of F and G. The diagram has a cocone to Gi and that cocone is monic (meaning the natural map from the colimit to Gi is monic) for each i in I, call alpha supernatural. Now the condition is that whenever alpha is supernatural, the induced colim F --> colim G is monic. To see that this implies AB4, suppose for all x in X, A_x >--> B_x. Let I consist of all the finite subsets of X. For i in I, let Fi be the direct sum of all the A_x, x in i and Gi be the direct sum of the correspnding B_x. The supernaturality is satisfied and hence the sum of the A_x maps monically to the sum of the B_x. The application to my question comes as follows. To recall, I am supposing that del del ... -----> (C_n,d) -----> (C_{n-1},d) ---> ... ---> (C_0,d) --> 0 is a chain complex of differential abelian groups, except that we assume d.del = -del.d. Suppose (C_n,d) is exact for each n. Let C be the direct sum of the C_n with boundary given by the matrix ( d 0 0 ... ) ( del d 0 ... ) ( 0 del d ... ) ( . . . . ) ( . . . . ) ( . . . . ) The finite truncations F^n = C_0 +...+ C_n are readily shown to be exact: F^0 = C_0 is by hypothesis and there is an exact sequence 0 --> F^{n-1} --> F^n --> C_n --> 0. Thus each F^n is exact. Now let Z^n and B^n be the kernel and image, resp. of the boundary operator on F^n. Then the rows of 0 ----> Z^n -------> F^n -------> B^n ----> 0 | | | | | | | | | v v v 0 --> Z^{n+1} ---> F^{n+1} ---> B^{n+1} --> 0 Since the right hand vertical arrow is monic, it follows that the left hand square is a pullback, which in turn implies that the induced map F^n +_{Z^n} Z^{n+1} ---> F^{n+1} is monic. Taking colimits, and using this Ab4.5 condition together with the right exactness of colimits implies that 0 --> colim Z^n --> C --> B --> 0 is exact, so that Z = colim Z^n and then B^n = Z^n for all n implies B = Z. As for AB4.5* on module categories (for which it is sufficient to prove it for Ab), it is a bit complicated notationally for this medium, but not hard. The point is that when you try to construct an element in the inverse limit, the crucial thing is that you can do it one index at a time and no choice you make at an earlier stage ever has to be changed at a later one, so you can just continue. Of course, AC is involved. This might a way to find a category that satisfies AB4*, but not AB4.5*; the trouble is that AC is also used to show AB4*. Michael

1 1