December 1995 - Categories - categories.org.au

associativity and commutativity of addition
by BOERGER 04 Jan '96

04 Jan '96

It is well-known that a category in which finite products exist and coincide with finite coproducts (i.e. a zero object exists and the binary product functor is naturally equivalent to the binary coproduct functor) is semi- additive, i.e. enriched over the monoidal closed category of commutative monoids. Conversely, in a semi- additive category, every (existing) finite product is automatically a finite coroduct in the canonical way (an vice versa). Now my student Claus Kirschner observed that the proof of the latter fact does not use associativity and commutativity of the addition. Strange enough, together with the first fact this means: If a category with finite products has an operation called "addition" with neutral element 0 on each hom-set satisfying f0=0f=0 and the distributive laws, then the addition is automatically associative and commutative. Has anyone ever seen this before? Of course, finite products (or coproducts) are essential; otherwise one can easily construct single-object counterexamples. On the other hand, Hilbert observes something similar but different in an appendix to his book "Grundlagen der Geometrie": For unital rings, the commutativity of addition follows from the other axioms; one can even relax the exisence of the additive inverse to cancellation conditions. The argument is as follows: x+x+y+y=(1+1)x+(1+1)y=(1+1)(x+y)=1(x+y)+1(x+y)=x+y+x+y Cancelling x on the left and y on the right, we get x+y=y+x. Does anybody know more about similar implications? Greetings Reinhard

3 2

Query about citations
by David B. Benson 29 Dec '95

29 Dec '95

One defines the category of Diagrams on category A, Diag(A), as in Makkai & Pare's "Accessible Categories". One similarly defines the category of cones on diagrams on A and the category of cocones on diagrams on A. Limits and colimits exist when certain adjunctions hold between these derived categories. I am sure I have seen one or more papers or monographs giving the details for the above. I simply cannot recall where this (these) workout(s) appeared. I would like to (re)read the paper(s), so I would greatly appreciate receiving reminders about where to look for these results. Thank you in advance. With the warmest of season's greetings, David

2 1

3rd WoLLIC'96 - 2nd Call
by Ruy de Queiroz 22 Dec '95

22 Dec '95

Second Call for Contributions 3rd Workshop on Logic, Language, Information and Computation (WoLLIC'96) May 8-10, 1996 Salvador (Bahia), Brazil The `3rd Workshop on Logic, Language, Information and Computation' (WoLLIC'96) will be held in Salvador, Bahia (Brazil), from the 8th to the 10th May 1996. Contributions are invited in the form of two-page (600 words) abstract in all areas related to logic, language, information and computation, including: pure logical systems, proof theory, model theory, type theory, category theory, constructive mathematics, lambda and combinatorial calculi, program logic and program semantics, nonclassical logics, nonmonotonic logic, logic and language, discourse representation, logic and artificial intelligence, automated deduction, foundations of logic programming, logic and computation, and logic engineering. There will be a number of guest speakers, including: Andreas Blass (Ann Arbor), Nachum Dershowitz (Urbana-Champaign), Keith Devlin (St. Mary's), J. Michael Dunn (Indiana), Peter G"ardenfors (Lund), Jeroen Groenendijk (Amsterdam), Wilfrid Hodges (London), Roger Maddux (Ames, Iowa), Andrew Pitts (Cambridge), Amir Pnueli (Rehovot), Michael Smyth (London). WoLLIC'96 is part of a larger biennial event in computer science being held in the campus of the Federal University of Bahia from the 6th to the 10th of May 1996: the `6th SEMINFO' (6th Informatics Week). The 6th SEMINFO will involve parallel sessions, tutorials, mini-courses, as well as the XI Brazilian Conference on Mathematical Logic (EBL'96), and a Workshop on Distributed Systems (WoSiD'96). Submission: Two-page abstracts, preferably by e-mail to *** wollic96(a)di.ufpe.br *** must be RECEIVED by MARCH 8th, 1996 by the Chair of the Organising Committee. Authors will be notified of acceptance by April 8th, 1996. The 3rd WoLLIC'96 is under the official auspices of the Interest Group in Pure and Applied Logics (IGPL) and The European Association for Logic, Language and Information (FoLLI). Abstracts will be published in the Journal of the IGPL (ISSN 0945-9103) as part of the meeting report. Selected contributed papers will be invited for submission (in full version) to a special issue of the Journal. The location: Salvador, Capital of the Bahia state, the first European settlement of Portuguese America and the first Capital of Brazil, is where all the most important colonial buildings were constructed: churches, convents, palaces, forts and many other monuments. Part of the city historical center has been safekept by UNESCO since 1985. Five hundred years of blending Native American, Portuguese, and African influences have left a rich culture to its people, which can be felt on its music, food, and mysticism. Salvador is located on the northeastern coast of Brazil and the sun shines year round with the average temperature of 25 degrees Celsius. It is surrounded by palm trees and beaches with warm water. City population is around 2.5 million and life style is quite relaxed. Programme Committee: W. A. Carnielli (UNICAMP, Campinas), M. Costa (EMBRAPA, Brasilia), V. de Paiva (Cambridge Univ., UK), R. de Queiroz (UFPE, Recife), A. Haeberer (PUC, Rio), T. Pequeno (UFC, Fortaleza), L. C. Pereira (PUC, Rio), K. Segerberg (Uppsala Univ., Sweden), A. M. Sette (UNICAMP, Campinas), P. Veloso (PUC, Rio). Organising Committee: H. Benatti (UFPE), L. S. Baptista (UFPE), A. Duran (UFBA), T. Monteiro (UFPE), A. G. de Oliveira (UFBA), N. Riccio (UFBA). For further information, contact the Chair of Organising Committee: R. de Queiroz, Departamento de Informatica, Universidade Federal de Pernambuco (UFPE) em Recife, Caixa Postal 7851, Recife, PE 50732-970, Brazil, e-mail: ruy(a)di.ufpe.br, tel.: +55 81 271 8430, fax: +55 81 271 8438. (Co-Chair: T. Pequeno, LIA, UFC, tarcisio(a)lia.ufc.br, fax +55 85 288 9845) Web homepage: http://www.di.ufpe.br/simposios/wollic.html ----- \documentstyle[a4]{article} \renewcommand{\thepage}{} \begin{document} \begin{center} {\large\bf 3rd Workshop on Logic, Language, Information and Computation (WoLLIC'96)}\\[1.0ex] {\large May 8--10, 1996}\\[.8ex] {\large Salvador (Bahia), Brazil}\\[1.0ex] \end{center} \bigskip \noindent The {\bf 3rd Workshop on Logic, Language, Information and Computation} ({\bf WoLLIC'96}) will be held in Salvador, Bahia (Brazil), from the 8th to the 10th May 1996. Contributions are invited in the form of two-page (600 words) abstract in all areas related to logic, language, information and computation, including: pure logical systems, proof theory, model theory, type theory, category theory, constructive mathematics, lambda and combinatorial calculi, program logic and program semantics, nonclassical logics, nonmonotonic logic, logic and language, discourse representation, logic and artificial intelligence, automated deduction, foundations of logic programming, logic and computation, and logic engineering.\\ There will be a number of guest speakers, including:\\ Andreas Blass (Ann Arbor), Nachum Dershowitz (Urbana-Champaign), Keith Devlin (St.\ Mary's), J.\ Michael Dunn (Indiana), Peter G\"ardenfors (Lund), Jeroen Groenendijk (Amsterdam), Wilfrid Hodges (London), Roger Maddux (Ames, Iowa), Andrew Pitts (Cambridge), Amir Pnueli (Rehovot), Michael Smyth (London)\\ {\bf WoLLIC'96} is part of a larger biennial event in computer science being held in the campus of the Federal University of Bahia from the 6th to the 10th of May 1996: the {\bf 6th SEMINFO} (6th Informatics Week). The {\bf 6th SEMINFO} will involve parallel sessions, tutorials, mini-courses, as well as the {\bf XI Brazilian Conference on Mathematical Logic} ({\bf EBL'96}), and a {\bf Workshop on Distributed Systems} ({\bf WoSiD'96}).\\ {\bf Submission}: Two-page abstracts, preferably by e-mail to ***~wollic96(a)di.ufpe.br~*** must be RECEIVED by MARCH 8th, 1996 by the Chair of the Organising Committee. Authors will be notified of acceptance by April 8th, 1996. The {\bf 3rd WoLLIC'96} is officially sponsored by the Interest Group in Pure and Applied Logics (IGPL) and The European Association for Logic, Language and Information (FoLLI). The {\bf EBL'96} is the annual meeting of Brazilian Logic Society. Abstracts will be published in the Journal of the IGPL (ISSN 0945-9103) as part of the meeting report. Selected contributed papers will be invited for submission (in full version) to a special issue of the Journal.\\ {\bf The location}: Salvador, Capital of the Bahia state, the first European settlement of Portuguese America and the first Capital of Brazil, is where all the most important colonial buildings were constructed: churches, convents, palaces, forts and many other monuments. Part of the city historical center has been safekept by UNESCO since 1985. Five hundred years of blending Native American, Portuguese, and African influences have left a rich culture to its people, which can be felt on its music, food, and mysticism. Salvador is located on the northeastern coast of Brazil and the sun shines year round with the average temperature of 25 degrees Celsius. It is surrounded by palm trees and beaches with warm water. City population is around 2.5 million and life style is quite relaxed.\\ {\bf Programme Committee}: W.\ A.\ Carnielli (UNICAMP, Campinas), M.\ Costa (EMBRAPA, Brasilia), V.\ de Paiva (Cambridge Univ., UK), R.\ de Queiroz (UFPE, Recife), A.\ Haeberer (PUC, Rio), T.\ Pequeno (UFC, Fortaleza), L.\ C.\ Pereira (PUC, Rio), K.\ Segerberg (Uppsala Univ., Sweden), A.\ M.\ Sette (UNICAMP, Campinas), P.\ Veloso (PUC, Rio).\\ {\bf Organising Committee}: H.\ Benatti (UFPE), L.\ S.\ Baptista (UFPE), A.\ Duran (UFBA), T.\ Monteiro (UFPE), A.\ G.\ de Oliveira (UFBA), N.\ Riccio (UFBA).\\ For further information, contact the Chair of Organising Committee: R.\ de Queiroz, Departamento de Inform\'atica, Universidade Federal de Pernambuco (UFPE) em Recife, Caixa Postal 7851, Recife, PE 50732-970, Brazil, e-mail: ruy(a)di.ufpe.br, tel: +55~81~271~8430, fax +55~81~271~8438. (Co-Chair: T.\ Pequeno, LIA, UFC, tarcisio(a)lia1.ufc.br, fax +55~85~288~9845)\\ Web homepage: http://www.di.ufpe.br/simposios/wollic.html \end{document}

1 0

(Fwd) Re: Abstracts "Descent Theory", Oberwolfach '95
by Walter Tholen 21 Dec '95

21 Dec '95

Dear Colleagues, a link has been appended to my WWW home page to obtain the notes of Ross Street's lectures on Descent Theory at the Oberwolfach Conference in September. These files may accessed also directly; the address is ftp://ftp.mpce.mq.edu.au/pub/maths/Categories/Oberwolfach/ The files themselves are: -rw-r--r-- 1 ross ftpmaths 1329104 Dec 13 16:34 Oberwolfach_1.ps -rw-r--r-- 1 ross ftpmaths 707855 Dec 13 16:33 Oberwolfach_1.ps.Z -rw-r--r-- 1 ross ftpmaths 1196252 Dec 13 16:34 Oberwolfach_2.ps -rw-r--r-- 1 ross ftpmaths 605741 Dec 13 16:34 Oberwolfach_2.ps.Z -rw-r--r-- 1 ross ftpmaths 1018897 Dec 13 16:37 Oberwolfach_3.ps -rw-r--r-- 1 ross ftpmaths 549743 Dec 13 16:37 Oberwolfach_3.ps.Z ... giving a PostScript file (txt) and a compressed (binary) version of each. A good Web browser can get them using the above as a URL. It may even automatically uncompress and render the PostScript file. Best wishes for the Holiday Season and a Happy New Year! Walter. -- Walter Tholen Department of Mathematics and Statistics York University, North York, Ont., Canada M3J 1P3 tel. (416) 736 5250 or 736 2100, ext. 33918 fax. (416) 736 5757 http://www.math.yorku.ca/Who/Faculty/Tholen/menu.html

1 0

MSc course
by Edmund Robinson 20 Dec '95

20 Dec '95

Dear Colleagues, Next year we shall be mounting a (heavily) revised version of our MSc course, an advert for which follows. Please pass the advert on to anyone you think might be interested. Please encourage all your best students to apply to us. And of course, please have a wonderful Christmas! all best wishes Edmund Robinson PS Perhaps I should also take this opportunity to tell those of you who haven't heard, that we are proud to announce the appointment of Peter O'Hearn to a readership in the department. Peter continues a departmental tradition of people called Peter with interests in programming languages. He replaces Peter Landin, who has retired from formal duties. --------------------------------------------------- Queen Mary and Westfield College University of London Department of Computer Science ------------------------------------------------------ | Advanced MSc in Logic and Foundations of Programming | ------------------------------------------------------ Applications for entry in Autumn 1996 are invited from candidates who have or expect to obtain a good honours degree in mathematics or a subject with substantial mathematical content. This newly designed MSc programme aims to allow mathematically able students to acquire a thorough grounding in the logical foundations of computer science and the theory and practice of programming. ---------- | Syllabus | ---------- Students take four courses: * Programming Programming in imperative, logic and functional languages; specification and verification applied to imperative programs; the use of equational specification; program transformation; logical foundations of Prolog; partial evaluation. * Deduction Formal logical systems; structural proof theory including proof search constructive logic and its semantics; type theory, lambda calculi and structural operational semantics. * Semantics Universal algebra; category theory; categorical model theory; classical denotational semantics; topics in modern denotational semantics. * Concurrency Game theory and its applications in logic and to the theory of processes; process algebra; equivalences between processes; equational reasoning; use of process calculus in specification and verification. All four courses will be taught by active researchers who are experts in these fields. Courses are taught over the first two semesters, with the remainder of the year being devoted to the project. --------- | Funding | --------- We expect that a small number of EPSRC studentships will be available for suitably qualified candidates. --------------------- | Further information | --------------------- Prof E.P. Robinson (edmundr(a)dcs.qmw.ac.uk) or Dr D.J. Pym (pym(a)dcs.qmw.ac.uk) Department of Computer Science, Tel: +44 (0)171 975 5555 Queen Mary and Westfield College, Fax: +44 (0)181 980 6533 University of London, URL: http://www.dcs.qmw.ac.uk/ Mile End Road, London E1 4NS, England, U.K.

1 0

addresses for Max and Imogen Kelly
by Max Kelly 15 Dec '95

15 Dec '95

>>From 17 Dec 1995 to 3 Feb 1996: 58 Crescent Road Kingston-on-Thames Surrey KT2 7RF ENGLAND Tel. +44-181-546-6383 email as usual kelly_m(a)maths.su.oz.au >>From 4 Feb to 29 Feb 1996: C/o Prof. Aurelio Carboni, Dipartimento di Matematica, Universita' di Genova, via Dodecaneso 35 16146 GENOVA, ITALY. (Phone Home 02-342935 Work 010-353-6804 Fax 010-353-6752 (Milan FAX: 39-2-70630346) email for Kelly still as above. Best wishes to all for the coming holiday season - Max and Imogen.

1 0

position in Dunkerque
by Enrico Vitale 14 Dec '95

14 Dec '95

Dear categorists, a position of Maitre de Conferences (assistan-researcher) will be available at the Universite du Littoral (Dunkerque-Calais, France) starting from the next academic year. We are particularly interested in applications of people working in category theory and related areas. A basic knowledge of French language and a Ph.D. degree are requested. People interested in such a position should contact us as soon as possible for more informations. Best regards Dominique Bourn Enrico Vitale Enrico Vitale Laboratoire LANGAL - Faculte de Sciences Universite du Littoral 1 quai Freycinet - B.P. 5526 59379 Dunkerque - FRANCE tel. 0033 - 28237161 fax 0033 - 28237039 e-mail vitale(a)lma.univ-littoral.fr

1 0

Dinatural exercise solved: addendum
by Peter Freyd 12 Dec '95

12 Dec '95

Whoops. I lifted the proof I posted yesterday out of a longer ms I'm writing. It occured to me (you know how it goes -- around 3 a.m.) that it assumed the reader already knew the dinatural transformation 1 -> (A,A). Its source is the terminal set-valued bifunctor: the constant bifunctor whose constant value is a one-element set. Its target is the "hom" bifunctor. The dinatural transformation is the one with identity maps as values. See: the reader did already know it (because, of course, it's the only dinatural from 1 to (A,A) that can be defined uniformly for all categories).

1 0

Dinatural exercise solved
by Peter Freyd 11 Dec '95

11 Dec '95

I had asked if the following is new: Let *A* be a locally small category. Let *D* be the category whose objects are set-valued bifunctors on *A* (contravariant on the first variable, covariant on the second) and whose maps are the dinatural transformations. Then *A* is a groupoid. Meaning, of course, that dinaturals are closed under composition iff *A* is a groupoid. Well, all I've received are requests for the proof. So: given *A* let P denote the covariant power-set functor on the category of sets. Fix an object C. Consider the bifunctor that sends A to P(C,A) and consider the dinatural transformation (A,A) -> P(C,A) that sends an endomorphism e in (A,A) to the set of solutions o the equation: x x e C -> A = C -> A -> A. The composition 1 -> (A,A) -> P(C,A) has as its unique value the _entire_ subset of maps from C to A. If it is dinatural then for any f:A -> C: P(C,A) / 1 | P(1,f) \ P(C,C). g f Every endomorphism of C is thus of the form C -> A -> C. In particular, the identity map is of that form, that is, f is left invertible, hence, every map targeted at C is left-invertible. If this remains true for every C then every map in *A* is left invertible, thus invertible. I also asked for a reference for: If *A* is a groupoid then *D* is equivalent to the category of presheaves on *A*. Nobody's asked for it, but let *A* be a groupoid anyway. For any target category and any dinatural S -> T one may easily prove that the hexagon used for defining dinaturals expands to a commutative diagram (from which the computability of dinaturals easily follows): SAA ------------------> TAA SfA / \ SAf TfA / \ TAf SBA SAB --> TBA TAB SBf \ / SfB TBf \ / TfB SBB -------------------> TBB. If *A* is a groupoid then the category composed of dinaturals between bifunctors from *A* to *B* is equivalent to the category composed of natural transformations between covariant functors from *A* to *B*. Show that for any bifunctor, S, there is an isomorphism (in the category composed of dinaturals) to a bifunctor, T, with the special property that TAB = TAA and TAx = TA1. Given S define T to be the bifunctor such that TAB = SAA and Tfg = Sff' (where f' is the inverse of f). The collection of identity functions from SAA to TAA forms a dinatural transformation as does the collection of identity functions from TAA back to SAA. The full subcategory of such functors is easily seen to be isomorphic to the category of contravariant functors from *A* to *B*.

1 0

Discrete opfibrations of graphs
by Sebastiano Vigna 11 Dec '95

11 Dec '95

Suppose you have coloured graphs G,H (with multiple edges, etc. i.e., we are in the topos of coloured graphs). A morphism G->H induces a functor between the free categories generated by G and H. I am interested in those morphisms which induce discrete opfibrations. Has anyone studied this notion? Essentially, any arc f(x)->y of H can be lifted uniquely to an arc (with the same label) x->x', for some x' such that f(x')=y. Sebastiano Vigna

1 0