May 1997 - Categories - categories.org.au

CT97
by John MacDonald 10 Jun '97

10 Jun '97

LAST CALL FOR PREREGISTRATION INTERNATIONAL CATEGORY THEORY MEETING (CT97) July 13-19, 1997 University of British Columbia Vancouver, Canada The conference arrival day is Sunday July 13 with a reception 6-9pm in the Fireplace Lounge of Walter Gage Towers on the UBC campus. The scientific program will begin Monday morning July 14 at 9am in Angus 104 and will finish on Saturday July 19 at the end of the morning session (12:30pm). On Wednesday afternoon July 16 there will be a Vancouver city tour followed by a dinner cruise with Harbour Ferries. Pickup time will be 2:30pm in front of Gage Towers. On Friday evening there will be a banquet starting at 7:30PM. PREREGISTRATION If you plan to attend the conference and have not preregistered, or if you would like more information to enable you to decide whether to attend, then please preregister as soon as possible. To preregister, and thus receive future announcements as well as a registration form and a housing form please send e-mail to johnm(a)math.ubc.ca with subject `preregistration'. Please provide your name and a postal address in the body of the message. HOUSING DEADLINE Accomodation is available on the U.B.C. campus in a block of rooms being held for CT97 until June 13, one month before the starting date of the conference. On June 13 all rooms from our block which have not been individually reserved will be released to the public for reservation. After this time one can still request space on an individual basis, but the outcome is less certain, especially since a major music festival begins in Vancouver on July 18. If you think that you may attend but are not sure yet, then you may find it advisable to reserve a room since this can be done by email on the housing form and for the single rooms with shared washroom it does not require a deposit. If you have preregistered but have misplaced your room reservation form, then please send email to johnm(a)math.ubc.ca with the subject Housing and a room reservation form will be sent to you. TALK DEADLINE If you wish to give a talk and have not yet informed the organizers, then please let us know of your intention by May 31 by sending email to johnm(a)math.ubc.ca including a title, if possible. Abstracts should be sent to stone(a)math.ubc.ca by June 10. There may be parallel sessions on some afternoons. The total number of speakers may have to be limited as well. PREREGISTRANT LIST For your information a list of those who have preregistered as of May 16 is attached. This list is presented roughly in the order in which preregistrations were received. If your name is not on the list and you would like it added, then please follow the procedure listed under PREREGISTRATION above. CT97 PREREGISTRATION LIST (5/16/97) P.J. Johnstone, C.J. Mulvey, M. Hebert, M. Grandis, R.J. Wood B. Jay, S. Niefeld, J. Isbell, D. Novick, F. Gago I. Moerdijk, J. Funk, F. Zalamea, H. Lord, H. Hu J. Duskin, Y. Katsov, H. Marcum, J.R. Otto, M. Johnson R. Pare, P. McCrudden, H.E. Porst, R. Seely, R. Gates V. Pratt, R. Kieboom, J. Rosicky, G. Rosolini, S. Crans R. Street, S. Lack, U. Montanari, F. Piessens, W. Hunsaker F.W. Lawvere, H. Kleisli, J.W. Pelletier, L.S. Barbosa, P.C. Carrasco W. Tholen, A. Madanshekaf, J. Picado, F. Marmolejo, S. Fusco Y.P. Velinov, R. Rosebrugh, A. Schauerte, W. Boshuck, D. Bourn S. Mac Lane, J. MacDonald, A.Stone, L. Roman, S. Mantovani G.M. Kelly, L. Mauri, C. Pedicchio, J. Thiessen, M. Thiebaud M. Barr, G. Richter, F.G. Lastaria, D. Hofmann, J. Walters-Wayland L. Sousa, M.J.Healy, P. Mulry, R. Dawson, Z. Omiadze J. Koslowski, F. Linton, D. Pronk, A. Kock, H. Miyoshi C. Hermida, D. Schumacher

1 1

CTCS'97 - Call for Participation
by Eugenio Moggi 31 May '97

31 May '97

[Please look at the conference URL for more detailed information] CATEGORY THEORY AND COMPUTER SCIENCE (CTCS'97) 4-6 SEPTEMBER 1997, S. MARGHERITA LIGURE (GENOA), ITALY CONFERENCE URL: "http://www.disi.unige.it/conferences/ctcs97/" PRELIMINARY PROGRAMME and CALL FOR PARTICIPATION CTCS'97 is the 7th conference on Category Theory and Computer Science. The purpose of the conference series is the advancement of the foundations of computing using the tools of category theory, algebra, geometry and logic. While the emphasis is upon applications of category theory, it is recognized that the area is highly interdisciplinary. The proceedings will be published by Springer in the LNCS series. The conference is sponsored by GNIM (Gruppo Nazionale Informatica Matematica) of CNR and Universita' di Genova. LOCATION The conference will take place at Hotel Regina Elena, a 4 stars hotel with private beach, located in S. Margherita Ligure. S. Margherita is a beautiful sea resort in Liguria very close to Portofino promontory and about 30 km east of Genova. INVITED SPEAKERS - J. Baez, Univ. of California at Riverside (USA) - R. Bird, Oxford Univ. (UK) - B. Jay, Univ. of Technology Sydney (Australia) - G. Plotkin, Univ. of Edinburgh (UK) ************************ IMPORTANT DEADLINES ************************ **** 15 JULY 1997 early registration **** **** 31 JULY 1997 "guaranteed" hotel reservation **** ********************************************************************* REGISTRATION. See the CONFERENCE URL for details on how to register. | before 15 July | after 15 July | -----------------------------------------------| Regular rate | 260000 It.Lire | 400000 It.Lire | -----------------------------------------------| Student rate | 220000 It.Lire | 400000 It.Lire | ------------------------------------------------ The fee includes the welcome reception, coffee breaks, lunches, a copy of the proceedings. HOTEL RESERVATION. Hotel reservations are handled by DAVOR VIAGGI (see the CONFERENCE URL for details). Participants will be hosted in 3 and 4 stars hotels (among them the conference hotel). All hotels are within walking distance from the conference hotel and have rooms with private bathrooms. The price range of a room per day inclusive of breakfast and taxes are | single room | double/twin room | --------------------------------------------------------| 4 stars | 113000-138000 It.Lire | 178000-242000 It.Lire | --------------------------------------------------------| 3 stars | 75000-115000 It.Lire | 120000-155000 It.Lire | --------------------------------------------------------- Requests are handled on a first-come-first-served basis, therefore it is advisable to send the hotel registration form well before the deadline. After JULY 31 DAVOR VIAGGI will accept reservations, but can no longer guarantee that they can be satisfied. CONTACT INFORMATION - Conference email: ctcs97(a)disi.unige.it fax: +39 (10) 3536699 - Address: E. Moggi (CTCS'97), DISI, v. Dodecaneso 35, 16146 Genova, Italy - Organizers: E. Moggi, moggi(a)disi.unige.it, +39 (10) 353 6629 G. Rosolini, rosolini(a)disi.unige.it, +39 (10) 353 6630 PROGRAMME COMMITTEE S. Abramsky (UK) P.-L. Curien (France), P. Dybjer (Sweden), P. Johnstone (UK), G. Longo (France), G. Mints (USA), J. Mitchell (USA), E. Moggi (Italy), A. Pitts (UK), A. Poigne (Germany), G. Rosolini (Italy), D. Rydeheard (UK), F-J. de Vries (Japan). RELATED EVENTS Express'97 workshop, 8-12 Sep 1997, S. Margherita Ligure, Italy. ----------------------------------------------------------------------------- PRELIMINARY PROGRAMME HOTEL REGINA ELENA Lungomare Milite Ignoto 44, 16038 S. Margherita Ligure, Italy phone: +39 (185) 287003, fax: +39 (185) 284473 WEDNESDAY, 3 September 18.00 Welcome Reception and Registration THURSDAY, 4 September 09.00 Invited Talk: Richard Bird 10.15 Coffee Break 10.40 Proof Principles for Datatypes with Iterated Recursion by Ulrich Hensel, Bart Jacobs 11.20 A Calculus for Collections and Aggregates by Kazem Lellahi, Val Tannen 12.00 When do datatypes commute? by Paul Hoogendijk, Roland Backhouse 12.40 Lunch 14.45 Invited Talk: John Baez 16.00 Coffee Break 16.30 A factorisation theorem for external derivations by Paul-Andre Mellies 17.10 Monads and Modular Term Rewriting by Christoph Lueth, Neil Ghani 17.50 A 2-Categorical Presentation of Term Graph Rewriting by Andrea Corradini, Fabio Gadducci FRIDAY, 5 September 09.00 Invited Talk: Barry Jay 10.15 Coffee Break 10.40 Presheaf Models for the pi-Calculus by Gian Luca Cattani, Ian Stark, Glynn Winskel 11.20 Categorical Modelling of Structural Operational Rules: case studies by Daniele Turi 12.00 Specifying Interaction Categories by Dusko Pavlovic, Samson Abramsky 12.40 Lunch 14.45 Invited Talk: Gordon Plotkin 16.00 Coffee Break 16.30 Lifting by A. Bucalo, G. Rosolini 17.10 General Synthetic Domain Theory -- A Logical Approach by Bernhard Reus, Thomas Streicher 17.50 Discussion on CTCS 20.00 Conference Dinner SATURDAY, 6 September 09.00 Shedding New Light in the World of Logical Systems by Uwe Wolter, Alfio Martini 09.40 Combining and Representing Logical Systems by Till Mossakowski, Andrzej Tarlecki, Wieslaw Pawlowski 10.20 Coffee Break 10.50 A decision algorithm for linear isomorphism of types O(nlog^2n) by Alexander Andreev, Sergei Soloviev 11.30 Effectiveness of the Global Modulus of Continuity on Metric Spaces by Klaus Weihrauch, Xizhong Zheng 12.30 Lunch Free Afternoon -----------------------------------------------------------------------------

1 0

ANNOUNCING: Xy-pic version 3.5 released!
by Kristoffer Hogsbro Rose 30 May '97

30 May '97

Dear Category Theorists, Please find enclosed a copy of the TRAILER for a new version of Xy-pic - I am sorry for announcing a new version so soon after the previous release but a serious bug needed fixing. I hope you will find this version useful. Sincerely, Kristoffer H. Rose PS. Notice that DIKU has discontinued my ftp directory, so the European home of Xy-pic is now at brics.dk; as usual the mirror at CTAN should be current in a few days. ======================================================================= ANNOUNCING the Xy-pic version 3.5 DIAGRAM TYPESETTING PACKAGE ======================================================================= This is to announce a release of my diagram typesetting package Xy-pic. version 3.5 is a bug fix release where a single serious bug of the previous major release of Xy-pic 3 has been eliminated. ----------------------------------------------------------------------- GENERAL ----------------------------------------------------------------------- Xy-pic is a package for typesetting a variety of graphs and diagrams with TeX. Xy-pic works with most formats (including LaTeX, AMS-LaTeX, AMS-TeX, and plain TeX), in particular Xy-pic is provided as a LaTeX2e `supported package' (following the `CTAN LaTeX2e bundle' standard). Further specifics of the package are in the distribution README file. ----------------------------------------------------------------------- NEWS ----------------------------------------------------------------------- Xy-pic version 3 was a thorough rewrite of the prior major version, version 2 (last version 2 release was release 2.6; several beta-test releases of version 3, numbered 2.7-2.12, were made available to users). However, full backwards compatibility is maintained (except for the unavoidable but fully documented obscure cases). Release 3.5 fixes the following problem of release 3.4: * Breaks (in arrows) were ignored more often than not! Furthermore version 3.5 adds an installation script for TDS-compliant un*x Xy-pic installations. Thanks to Uffe Engberg, Juan Carlos Soliveres, and John Landamore for your bug reports! ----------------------------------------------------------------------- AVAILABILITY ----------------------------------------------------------------------- Xy-pic can be retrieved through the World Wide Web Xy-pic `home pages': URL: http://www.brics.dk/~krisrose/Xy-pic.html URL: http://www.mpce.mq.edu.au/~ross/Xy-pic.html as well as by anonymous ftp from CTAN: macros/generic/diagrams/xypic and from the private archives of the authors: ftp.brics.dk : /Staff/krisrose/TeX/ ftp.mpce.mq.edu.au : /pub/maths/TeX/ Check the README file in each location for specifics, in particular check that you have reached a version 3.5 copy (some archives take a while to mirror the latest files)! ----------------------------------------------------------------------- HISTORY & CREDITS ----------------------------------------------------------------------- The first public release (version 1.40) of Xy-pic was created by Kristoffer H. Rose, DIKU, U of Copenhagen (now BRICS, U of Aarhus) and distributed via Usenet on December 19, 1991. (Version 3.3 was released on December 19, 1996 because this was the fifth anniversary of Xy-pic.) This quickly became Version 2 of which version 2.6 was the most stable. The rewrite that became version 3 is a continued collaboration with Ross Moore, Macquarie U, Sydney, initiated through a visit to Macquarie (Jan-May 1994 supported by the Australian Research Council, Macquarie University, and using donated DEC equipment). Xy-pic is Copyright (c) 1991-1997 by Kristoffer H. Rose and 1994-1997 by Ross Moore under GNU COPYLEFT which means that you can use the package for any purpose but if you provide the macros or any code derived from them to a third party then you are obliged to include the entire Xy-pic package (full details in the file COPYING). ----------------------------------------------------------------------- This is the end of the announcement. Enjoy Xy-pic! ----------------------------------------------------------------------- PS. Don't miss TUG'97 with the latest in advanced TeX/LaTeX web & math typesetting developments! See <URL: http://tug.cs.umb.edu/tug97/> -- Kristoffer Hxgsbro ROSE, Ph.D. <krisrose(a)brics.dk> BRICS International Ph.D. School <URL: http://www.brics.dk/~krisrose> Department of Computer Science +45 89423193, 20900180, fax 89423255 University of Aarhus, Ny Munkegade, bld. 540, DK-8000 Erhus C, DENMARK

1 0

injectivity
by Marek Golasinski 28 May '97

28 May '97

Dear Colleagues, Let $Vect_k$ be the category of vector spaces over a field $k$ and $I$ a small category. Consider the category $I-Vect_k$ of all covariant functors from $I$ to $Vect_k$. For two object $F,F'$ of the category $I-Vect_k$ consider their tensor product $F\otimes F'$ such that $(F\otimes F')(i)=F(i)\otimes F'(i)$ for all $i\in I$ and in the obvious way on the morphisms of $I$. 1) Is it true that this tensor product $F\otimes F'$ is injective provided that $F$ and $F'$ are injective? I am really intersted in its particular case. Namely, let $G$ be a finite group and $O(G)$ the finite associated category of canonical orbits. Objects of $O(G)$ are given by the finite $G$-sets $G/H$ for all subgroups $H\subsetq G$ and morphisms by eqivariant maps. 2) What about preserving the injectivity by the above defined tensor product in the functor category $O(G)-Vect_k$? If that is not true for $I=O(G)$ then I would greatly appreciate getting a counterexample. Many thanks in advance for your kind attention on the problem above. With my best regards, Marek Golasinski

3 2

equilogical spaces
by Jiri Rosicky 28 May '97

28 May '97

With J.Adamek, we have proved that the category of topological spaces is weakly cartesian closed. Hence its exact completion is cartesian closed (following the result I announced on May 15).

1 0

BarrFest Schedule
by Robert A. G. Seely 24 May '97

24 May '97

Here is the (reasonably final) schedule of talks for the BarrFest meeting in Montreal May 29 - 31. Details of the meeting (as well as a PS file of the schedule) are available from the Categories (Montreal) group's WWW site <ftp://triples.math.mcgill.ca/ctrc.html> - Robert Seely ------------------- Barrfest Schedule May 29-31, 1997 THURSDAY 9:00- 9:55 Murray Gerstenhaber Developments from Barr's thesis 10:00-10:25 George Janelidze On Barr's results on Galois theory in topoi, and further developments from topoi to general categories 11:00-11:55 Fred E J Linton HomB ( B B ) and all that 12:00-12:25 Noson Yanofsky Obstructions to Coherence - Lunch 1:30- 2:25 Jack Duskin Higher Dimensional Non-Abelian Cohomology via Cotriples 2:30- 3:25 Donovan VanOsdol Barr, Cobar, and Koszul 4:00- 4:25 Marta Bunge Admissible KZ-doctrines: overview and examples 4:30- 4:55 Jonathon Funk A bicomma object condition for KZ-doctrines 5:05- 6:00 Jim Lambek Diagram chasing in ordered categories with involution FRIDAY 9:00- 9:55 Saunders MacLane Triples versus Universal Algebra 10:00-10:25 Hongde Hu Coherence completions, free bicompletion and Chu construction 11:00-11:25 Vaughan Pratt Chu Spaces as Universal Algebras 11:30-12:25 Peter Chu Torsion theory in Rings with several objects - Lunch 1:30- 2:25 John Power Sketches 2:30- 3:25 John Kennison Solution manifolds for differential equations 4:00- 4:25 Ieke Moerdijk Barr's covering theorem and coherent Hausdorff topoi 4:30- 4:55 Walter Tholen Functorial factorization, well-pointedness and separability 5:05- 6:00 Myles Tierney 2-torsors, 2-descent, etc 6:45- ? Dinner Thompson House SATURDAY 9:00- 9:55 Charles Wells Graph Based Logic and Equational Logic 10:00-10:25 Dorette Pronk Simplicial Cohomology of Orbifolds 11:00-11:55 James Otto Presenting LCC categories by answering queries 12:00-12:25 Francois Lamarche Chu spaces and denotational semantics - Lunch 1:30- 2:25 Michael Makkai A somewhat personal overview of regular categories 2:30- 2:55 Robin Cockett Montreal summers need not be listless 3:00- 3:25 Robert Seely Linearly distributive functors 4:00- 4:25 Richard Blute Nuclear Ideals in Tensored *-categories 4:30- 4:55 Bernhard Banaschewski A uniform view of real compactness 5:05- 6:00 Peter Freyd Cartesian Logic, Alternation Logic

1 0

PhD-Studentships in Theoretical Computer Science
by Eike Ritter 22 May '97

22 May '97

THE UNIVERSITY OF BIRMINGHAM SCHOOL OF COMPUTER SCIENCE RESEARCH OPPORTUNITIES IN THEORETICAL COMPUTER SCIENCE The School of Computer Science, broadly grouped into areas of Theory of Computation, Artificial Intelligence, and Software Engineering, offers a number of PhD studentships each year. The Theory of Computation group concentrates on the development of logics and semantics for programming languages. The overall aim is to provide intuitive conceptual tools for the everyday practice of programming. Within this framework, the activities range from abstract mathematics to issues of implementation and software development. Current research projects include probabilistic computation and model checking, semantics for concurrent systems, observation logics, exact real number computation, semantics for databases, (linear) functional programming, type systems for optimization of programs, and automated deduction. Current members of the Theory group are: Dr Valeria de Paiva, Professor Achim Jung, Dr Marta Kwiatkowska, Dr Eike Ritter and Dr Mark Ryan. There are also two Research Fellows (Dr Natasha Alechina and Dr Neil Ghani) and 9 PhD students associated with the group, of the total of 30 in the School. Possible topics for research include, but are not restricted to: Probabilistic and stochastic systems Software verification Semantics for concurrency Extensions to the relational database model (theory and implementation) Semantics of object-oriented languages Linear abstract machines Type systems for imperative and OO programming Machine-assisted reasoning Categorical models of rewriting Applicants should possess a good honours degree (equivalent to an upper second class degree in a UK university) in Mathematics or Computer Science, or a closely related title. Applicants willing to undertake building software systems as part of their research are particularly encouraged. Informal enquiries can be directed to any member of the group: Valeria de Paiva +44 121 414 4766 Achim Jung +44 121 414 4776 Marta Kwiatkowska +44 121 414 7264 Eike Ritter +44 121 414 4772 Mark Ryan +44 121 414 7361 email {vdp,axj,mzk,exr,mdr}(a)cs.bham.ac.uk Additional information about the School of Computer Science and the University of Birmingham is accessible via WWW from URL: http://www.cs.bham.ac.uk

1 0

Last Call
by ruy＠di.ufpe.br 22 May '97

22 May '97

4th Workshop on Logic, Language, Information and Computation (WoLLIC'97) August 20-22 1997 Fortaleza (Ceara'), Brazil LAST CALL FOR CONTRIBUTIONS DEADLINE: 1st of June! http://www.di.ufpe.br/~wollic97 (Sincere apologies apply if you receive multiple copies of this message.)

1 0

ANNOUNCING: Xy-pic version 3.4 released!
by Kristoffer Hogsbro Rose 21 May '97

21 May '97

Dear Category Theorists, Please find enclosed a copy of the TRAILER for a new version of Xy-pic. I hope you will find it useful. Notice that DIKU has discontinued my ftp directory, so the principal home of Xy-pic is now at brics.dk. Sincerely, Kristoffer H. Rose ======================================================================= ANNOUNCING the Xy-pic version 3.4 DIAGRAM TYPESETTING PACKAGE ======================================================================= This is to announce a RELEASE of the DIAGRAM TYPESETTING PACKAGE: Xy-pic 3.4 This is a maintenance release where a few more bugs of the previous major release of Xy-pic 3 have been eliminated and a few things have been added... ----------------------------------------------------------------------- GENERAL ----------------------------------------------------------------------- Xy-pic is a package for typesetting a variety of graphs and diagrams with TeX. Xy-pic works with most formats (including LaTeX, AMS-LaTeX, AMS-TeX, and plain TeX), in particular Xy-pic is provided as a LaTeX2e `supported package' (following the `CTAN LaTeX2e bundle' standard). Further specifics of the package are in the distribution README file. ----------------------------------------------------------------------- NEWS ----------------------------------------------------------------------- Xy-pic version 3 was a thorough rewrite of the prior major version, version 2 (last version 2 release was release 2.6; several beta-test releases of version 3, numbered 2.7-2.12, were made available to users). However, full backwards compatibility is maintained (except for the unavoidable but fully documented obscure cases). Release 3.4 fixes the following problems remaining in release 3.3: * \txt and v2 arrow commands now work again, even first in matrix entries! * Tiling patterns are functional again! * PostScript frames have the right shape again! * The [F**] `enhance' modifier is now useful, even without PostScript! * Using Xy-constructions with & inside other table constructs possible! * Improved non-PostScript curved dashing! * `Illegal parameter number in definition of \lastprentry@@' bug fixed! as well as the usual collection of minor fixes in code & documentation (all described in the ChangeLog file of the source distribution). Thanks to J|rgen Koslowski, Clemens Beckstein, G. Allen Morris III, Chris L. Skeels, and Peter Selinger, for your bug reports (and to David Carlisle for reminding us of LaTeX2e's \AtBeginDvi mechanism, and last but not least to Karl Berry for releasing web2c-7.0 so we won't have to get `out of memory' errors any more and gee are we proud of being the only macro package mentioned in texmf.cnf :) ----------------------------------------------------------------------- AVAILABILITY ----------------------------------------------------------------------- Xy-pic can be retrieved through the World Wide Web Xy-pic `home pages': URL: http://www.brics.dk/~krisrose/Xy-pic.html URL: http://www.mpce.mq.edu.au/~ross/Xy-pic.html as well as by anonymous ftp from CTAN: macros/generic/diagrams/xypic and from the private archives of the authors: ftp.brics.dk : /Staff/krisrose/TeX/ ftp.mpce.mq.edu.au : /pub/maths/TeX/ Check the README file in each location for specifics. ----------------------------------------------------------------------- HISTORY & CREDITS ----------------------------------------------------------------------- The first public release (version 1.40) of Xy-pic was created by Kristoffer H. Rose, DIKU, U of Copenhagen (now BRICS, U of Aarhus) and distributed via Usenet on December 19, 1991. (Version 3.3 was released on December 19, 1996 because this was the fifth anniversary of Xy-pic.) This quickly became Version 2 of which version 2.6 was the most stable. The rewrite that became version 3 is a continued collaboration with Ross Moore, Macquarie U, Sydney, initiated through a visit to Macquarie (Jan-May 1994 supported by the Australian Research Council, Macquarie University, and using donated DEC equipment). Xy-pic is Copyright (c) 1991-1997 by Kristoffer H. Rose and 1994-1997 by Ross Moore under GNU COPYLEFT which means that you can use the package for any purpose but if you provide the macros or any code derived from them to a third party then you are obliged to include the entire Xy-pic package (full details in the file COPYING). ----------------------------------------------------------------------- This is the end of the announcement. Enjoy Xy-pic! ----------------------------------------------------------------------- PS. Don't miss TUG'97 with the latest in advanced TeX/LaTeX web & math typesetting developments! See <URL: http://tug.cs.umb.edu/tug97/> -- Kristoffer Hxgsbro ROSE, Ph.D. <krisrose(a)brics.dk> BRICS International Ph.D. School <URL: http://www.brics.dk/~krisrose> Department of Computer Science +45 89423193, 20900180, fax 89423255 University of Aarhus, Ny Munkegade, bld. 540, DK-8000 Erhus C, DENMARK

1 0

Scott is Phoa, locally
by Thomas Streicher 19 May '97

19 May '97

In a paper circulated since end of last year Dana Scott has proposed a category PEQU of algebraic lattices with partial equivalence relations as objects and equivariant Scott continuous maps as morphisms. One nice thing about PEQU is that Scott has shown it to be equivalent to the category EQU of T_0 spaces with (total) equivalence relations and equivariant continuous maps. It has been shown (by students of Scott) that PEQU is not even well-powered despite being regular and locally cartesian closed (in particular, it is a logos and thus a model for FOL). If one considers $\omega$-PEQU, the category of $\omega$-algebraic lattices with partial equivalence relations as objects and equivariant Scott continuous maps as morphisms, then it can be shown easily to be equivalent to PER(P $\omega$), the category of pers over the good old P $\omega$ model of lambda calculus, which embeds into Ass(P $\omega$), the category of assemblies over P $\omega$ and finally into RT(P $\omega$), the realisability topos over P $\omega$. All these full inclusions are reflective. This realisability model has been studied by Wesley Phoa in his Thesis (1990) and in his paper "Building Domains from Graph Models" (MSCS, 1992). The reason for the equivalence of $\omega$-PEQU and PER(P $\omega$) is that any $\omega$-algebraic lattice L is contained in P $\omega$ via an inflationary retract e : L -> P $\omega$ , p : P $\omega$ -> L. Now if R is a per on L then P $\omega$ may be endowed with the per e[R] := { (e(x),e(y)) | x R y } and the pair e,p of equivariant Scott continuous maps establishes an isomorphism between (L,R) and (P $\omega$ , e[R]). This observation does not hinge on countable cardinality. For any cardinal $\kappa$ we may consider $\kappa$-PEQU (where the bases of the algebraic lattices are required to have cardinality less or equal $\kappa$) and show it to be equivalent to PER(P $\kappa$) by the same argument as above. The reason why this is possible is that any infinite set M contains List(M) x M as a retract and therefore can be endowed with a graph model structure -- as emphasised by Scott. The benefits of this (simple) observation are the following (1) $\kappa$-PEQU does not admit a generic (regular) mono (= weak s.o. classifier) as for any partial combinatory algebra A the category PER(A) does not admit such (as each homset has cardinality less or equal |A| and there are 2^{|A|} (regular) subobjects of (A, \Delta(A))) but, never mind, the required weak / strong classifiers live in Ass(A) / RT(A) , respectively (2) Phoa already has started to investigate SDT in PER(P $\omega$), one may take as a dominance (S , \Delta(S)) where S is Sierpinski space together with [t] : ({*} , \Delta({*})) -> (S , \Delta(S)) where t(*) = \top. The same may be taken as a dominance for PEQU without any size restrictions. Anyway, PEQU appears as an amalgamation of ALL realisability models over graph models of all size. Assuming a Grothendieck universe U we may consider (the fairly big) graph model P U appearing most naturally so as we have List(U) x U \subseteq U. Thus PER(P U) contains PEQU, i.e. EQU, when one restricts the underlying algebraic lattices / T_0 spaces of PEQU / EQU to live in universe U. But notice that (P U , \Delta(P U)) lives outside this PEQU. Anyway, PER(P U), Ass(P U), RT(P U) appear as the appropriate models of logic in which to study Scott's recently proposed categories. >>From the point of view of mathematical practice, however, the restriction to cardinality $\omega$ does not seem to be too restrictive as most spaces in "real" mathematics have a countable base (e.g. separable metric spaces). Thomas Streicher

1 0