May 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

General notions of equivalence and exactness
by Sam Staton 06 Jun '08

06 Jun '08

Hello. In a category with pullbacks, say that a binary relation X <- R -> Y is "z-closed" if it satisfies the following axiom (interpreted as usual): If x R y and x' R y and x' R y' then x R y'. (The "z" in "z-closed" refers to the pattern of variables in the premise.) Z-closedness seems to be a sensible generalization of "equivalence" to relations between two different objects. (e.g. In computer science, it is common to relate the state spaces of two different systems.) Note that an endorelation is an equivalence relation if and only if it is z-closed and reflexive. Also note that, in an abelian category, every relation is z-closed. The [z-closed v. equivalence] connection seems to extend to [pullbacks v. kernel pairs]. Every span that arises from a pullback is a z-closed relation. Say that a category is "z-effective" if every z-closed relation arises as a pullback. - every abelian category is straightforwardly z-effective; - in a topos, every z-closed relation arises as a pullback span. Indeed, an extensive regular category has effective equivalence relations if and only if it is z-effective. These notions and ideas seem quite elementary, even fundamental, and I would be surprised if no-one had thought of them before. I borrowed the terminology "z-closed" from a paper by Erik de Vink and Jan Rutten (Theoret Comput Sci, 221:271-293, 1999) but I couldn't find any other references. Have I missed something? I'd be grateful for any observations or suggestions. Sam PS. I'd like to take the opportunity to acknowledge the helpful replies (public and private) to my question about W-types, a few months ago.

4 3

Mal'cev allegories
by Peter Freyd 31 May '08

31 May '08

Sam Staton asks about relations with the property: If x R y and x' R y and x' R y' then x R y'. Given an equational theory all relations in its category of models satisfy this property iff there's a Mal'cev operator,(a favorite topic among "universal algebraists"). Years ago I used the phrase Mal'cev property (MP) to mean that all relations in an allegory satisfy the condition. Some easy lemmas: MP implies all reflexive relations are symmetric (RIS). RIS implies equivalence relations commute (ERC). MP implies all reflexive relations are transitive (RIT). RIT implies ERC. ERC implies that the smallest equivalence relation containing a given pair of equivalence relations is their composition and that easily implies that the lattice of equivalence relations on any object is a modular lattice. ERC does not imply MP (there are simple examples for RIS not implying RIT and RIT not implying RIS). But in an allegory in which every relation is spanned by a pair of maps (in particular, in the calculus of relations arising from any regular category) it's easy to see that ERC does implies MP. For the record: txyz is defined to be a Mal'cev operator if it satisfies the two equations txxz = z txzz = x. In any theory that includes the theory of groups xy^{-1}z is such. For Heyting algebras take txyz = ((x -> y) -> z) ^ ((z -> y) -> z). That generalizes to a one-object division allegory: tPQR = (R/(1 ^ (R\Q))) ^ (R/(1 ^ (P\Q))). The provably simplest Mal'cev theory has one binary operation x*y and one equation x*(y*x) = y (e.g. in the presence of a group structure x*y = x^{-1}y^{-1}). Take txyz = (x*x)*(z*(x*y)). There are another 23 Mal'cev terms of the same size. If one weakens the theory of groups to the theory of quasigroups: that is, three binary relations and four equations (x/y)y = x x(x\y) = y (xy)/y = x x\(xy) = y then txyz = (x/x)\((x/y)z) is a Mal'cev operator. If we stick to terms of the same size there are 72 versions. Heavenly. But this one uses only the first and fourth equation (and, consequently, its mirror image uses only the second and third equations). The fact that the existence of a Mal'cev operator implies that congruence lattices are modular was well known by universal algebraists.

1 0

Re: General notions of equivalence and exactness (fwd)
by rjwood＠mathstat.dal.ca 29 May '08

29 May '08

Dear Sam I believe that you'll find `Frobenius objects in cartesian bicategories' by Bob Walters and me, #3 in volume 20 of TAC, interesting. It is precisely this closing of Z-configurations to give an X-configuration that translates the Frobenius condition in the cartesian bicategory of profunctors. It has been known for a long time, but I think unpublished until our paper appeared, that the Frobenius objects in profunctors are groupoids. The paper by Bob W and me shows that this admits considerable generalization. Best regards Richard Wood Hello. In a category with pullbacks, say that a binary relation X <- R -> Y is "z-closed" if it satisfies the following axiom (interpreted as usual): If x R y and x' R y and x' R y' then x R y'. (The "z" in "z-closed" refers to the pattern of variables in the premise.) Z-closedness seems to be a sensible generalization of "equivalence" to relations between two different objects. (e.g. In computer science, it is common to relate the state spaces of two different systems.) Note that an endorelation is an equivalence relation if and only if it is z-closed and reflexive. Also note that, in an abelian category, every relation is z-closed. The [z-closed v. equivalence] connection seems to extend to [pullbacks v. kernel pairs]. Every span that arises from a pullback is a z-closed relation. Say that a category is "z-effective" if every z-closed relation arises as a pullback. - every abelian category is straightforwardly z-effective; - in a topos, every z-closed relation arises as a pullback span. Indeed, an extensive regular category has effective equivalence relations if and only if it is z-effective. These notions and ideas seem quite elementary, even fundamental, and I would be surprised if no-one had thought of them before. I borrowed the terminology "z-closed" from a paper by Erik de Vink and Jan Rutten (Theoret Comput Sci, 221:271-293, 1999) but I couldn't find any other references. Have I missed something? I'd be grateful for any observations or suggestions. Sam PS. I'd like to take the opportunity to acknowledge the helpful replies (public and private) to my question about W-types, a few months ago.

1 0

Funded PhD Student (GTA) positions
by rlc3＠mcs.le.ac.uk 29 May '08

29 May '08

Dear Colleagues, The Department of Computer Science in the University of Leicester, UK, is offering two new Graduate Teaching Assistant (GTA) positions. The deadline for applications is June 16th. The application forms and further details are here: http://www.le.ac.uk/personnel/supportjobs/s3759a.html A GTA is a funded PhD student who is expected to undertake teaching duties during the ten week teaching periods of each of our two annual semesters (roughly, subsets of October to December and January to March). These positions should be of special interest to readers of the Categories and Types mailing lists, with both of these research areas being very active within the Department. Roy Crole.

1 0

Post doc grants
by Maria Manuel Clementino 28 May '08

28 May '08

Our national Foundation for Sciences and Technology (http://alfa.fct.mctes.pt/ ) accepts applications for post doc grants. The Regulations can be found at http://alfa.fct.mctes.pt/apoios/bolsas/regulamento2008 [in Portuguese]. In order to apply the candidate needs the support of a supervisor, working in a Portuguese university. For further information, please send a message. Regards, Maria Manuel Clementino

1 0

Post doc position
by Patrik Eklund 27 May '08

27 May '08

A postdoc position (2 years) in AI will be announced now very soon at Umea University, Department of Computing Science. We look forward also to applications from logicians with a strong categorical background. Applications are developed e.g. within health care. For further information, please send a message. Best regards, Patrik

1 0

ICLP'08 CALL FOR PAPERS
by ICLP 08 27 May '08

27 May '08

CALL FOR PAPERS ICLP'08 24th International Conference on Logic Programming Udine, Italy, December 9th-13th, 2008 http://iclp08.dimi.uniud.it CONFERENCE SCOPE ---------------- Since the first conference held in Marseilles in 1982, ICLP has been the premier international conference for presenting research in logic programming. Contributions (papers, position papers, and posters) are sought in all areas of logic programming including but not restricted to: * Theory: Semantic Foundations, Formalisms, Nonmonotonic Reasoning, Knowledge Representation. * Implementation: Compilation, Memory Management, Virtual Machines, Parallelism. * Environments: Program Analysis, Program Transformation, Validation and Verification, Debugging, Profiling, Integration. * Language Issues: Extensions, Integration with Other Paradigms, Concurrency, Modularity, Objects, Coordination, Mobility, Higher Order, Types, Modes, Programming Techniques. * Related Paradigms: Abductive Logic Programming, Inductive Logic Programming, Constraint Logic Programming, Answer-Set Programming. * Applications: Databases, Data Integration and Federation, Software Engineering, Natural Language Processing, Web and Semantic Web, Agents, Artificial Intelligence, Bioinformatics The three broad categories for submissions are: (1) Technical papers, providing novel research contributions, innovative perspectives on the field, and/or novel integrations across different areas; (2) Application papers, describing innovative uses of logic programming technology in real-world application domains; (3) Posters, ideal for presenting and discussing current work, not yet ready for publication, for PhD thesis summaries and research project overviews. A separate session dedicated to the celebration of the 20th anniversary of stable model semantics will also be part of the program. Accepted papers and posters will be allocated time for presentation during the conference. At least one author of each accepted submission is expected to register and participate in the event. In addition to papers and posters, the technical program will include invited talks, advanced tutorials, specialized sessions, workshops, and a Doctoral Student Consortium. Details, as they become available will be posted at: http://iclp08.dimi.uniud.it PAPERS AND POSTERS ------------------ Papers and posters must describe original, previously unpublished research, and must not be simultaneously submitted for publication elsewhere. Emphasis will be placed on the novelty and innovative nature of the results (even if not completely polished and refined). All submissions will be peer-reviewed by an international panel. Submissions MUST contain substantial original, unpublished material. All submissions must be written in English. Technical papers and application papers must not exceed 15 pages in the Springer LNCS format (see http://www.springeronline.com/lncs/) The limit for posters is 5 pages in the same format. The primary means of submission will be electronic, through the Easychair submission system. The submission page is available at http://www.easychair.org/conferences/?conf=ICLP08 PUBLICATION ----------- The proceedings of the conference will be published by Springer-Verlag in the LNCS series. All accepted papers and posters will be included in the proceedings. WORKSHOPS --------- The ICLP'08 program will include several workshops. They are perhaps the best place for the presentation of preliminary work, novel ideas, and new open problems to a more focused and specialized audience. Workshops also provide a venue for presenting specialised topics and opportunities for intensive discussions and project collaboration in any areas related to logic programming, including cross-disciplinary areas. DOCTORAL CONSORTIUM ------------------- The Doctoral Consortium (DC) on Logic Programming is the 4th Doctoral consortium to provide doctoral students with the opportunity to present and discuss their research directions, and to obtain feedback from both peers and word-renown experts in the field. The DC will also offer invited speakers and panel discussions. Accepted participants will receive partial financial support to attend the event and the main conference. The best paper and presentation from the DC will be given the opportunity to present in special session of the main ICLP conference. CELEBRATING 20th YEARS OF STABLE MODEL SEMANTICS ------------------------------------------------ The year 2008 marks the 20th anniversary of the publication that introduced the stable model semantics for logic programs with negation. The paper titled "The stable semantics for logic programs" by Michael Gelfond and Vladimir Lifschitz was presented at ICLP-1988. It was a momentous event that gave rise to a vibrant subfield of logic programming known now as the answer-set programming. Its distinguishing aspects are close connections to the fields of knowledge representation, satisfiability and constraint satisfaction, ever faster computational tools, and a growing list of successful applications. To celebrate the stable-model semantics, there will be a special session at ICLP 2008 dedicated to answer-set programming. The session will feature talks by Michael Gelfond and Vladimir Lifschitz. as well as by other major contributions to the field, presenting personal perspectives on the stable-model semantics, its impact and its future. There will be a panel discussion, and regular accepted ICLP papers falling into the answer-set programming area will complete the program. CONFERENCE VENUE ---------------- The conference will be held in the city of Udine, the capital of the historical region of Friuli, Italy. Located between the Adriatic sea and the Alps, close to Venice, Austria and Slovenia, Udine is a city of Roman origins, funded by Emperor Otto in 983. Rich of historical sites, Udine is also famous for its commercial and shopping opportunities and its outstanding wine and culinary traditions. SUPPORT SPONSORING AND AWARDS ----------------------------- The conference is sponsored by the Association for Logic Programming (ALP). The ALP has funds to assist financially disadvantaged participants. The ALP is planning to sponsor two awards for ICLP 2008: for the best technical paper and for the best student paper. IMPORTANT DATES --------------- Papers Posters Abstract submission deadline June 2nd n/a Submission deadline June 9th August 15th Notification of authors August 1st September 1st Camera-ready copy due September 15th September 15th 20 Years of Stable Models TBA Doctoral Consortium TBA Workshop Proposals June 2nd Early-bird Registration TBA Conference December 9-13, 2008 ICLP'2008 ORGANIZATION ---------------------- General Chair: Agostino Dovier (University of Udine) Program Co-Chairs: Maria Garcia de la Banda (Monash University) Enrico Pontelli (New Mexico State University) Workshop Chair: Tran Cao Son (New Mexico State University) Doctoral Student Consortium: David Warren (SUNY Stony Brook) Tom Schrijvers (K.U.Leuven) Publicity Co-Chairs: Marcello Balduccini (Kodak Research Labs) Alessandro Dal Palu' (University of Parma) Programming Competition Chair: Bart Demoen (K.U.Leuven) 20 Years of Stable Models: Mirek Truszczynski (University of Kentucky) Andrea Formisano (University of Perugia) Program Committee: Salvador Abreu Sergio Antoy Pedro Barahona Chitta Baral Gerhard Brewka Manuel Carro Michael Codish Alessandro Dal Palu' Bart Demoen Agostino Dovier John Gallagher Michael Gelfond Carmen Gervet Gopal Gupta Manuel Hermenegildo Andy King Michael Maher Juan Moreno Navarro Alberto Pettorossi Brigitte Pientka Gianfranco Rossi Fariba Sadri Vitor Santos Costa Tran Cao Son Paolo Torroni Frank Valencia Mark Wallace Web Master: Raffaele Cipriano Local Arrangements Committee: Alberto Casagrande Elisabetta De Maria Luca Di Gaspero Carla Piazza ---------------------------------------------------- For further information: iclp08(a)cs.nmsu.edu http://iclp08.dimi.uniud.it

1 1

Workshop on Deep Inference, Nancy
by lamarche＠loria.fr 26 May '08

26 May '08

(a reminder for many, an announcement for others, and perhaps something verging on spam for some, with apologies) The workshop Deep Inference, its Algebra, Geometry and Syntax Will be held in Nancy, France on June 18 2008. As the title implies the main theme of the workshop is deep inference, but talks on related subjects like the the improvement and abstract theory of proof formalisms are most welcome. The workshop will be held at the Loria computer science lab on Wednesday June 18 2008, starting at 10:30, so as to ensure an easy commute from Paris (there is a Paris-Nancy TGV that leaves Gare de l'Est at 8:12 and the last return train leaves Nancy at 20:15). The webpage http://www.loria.fr/~lamarche/deepinf.html contains a few more details, including suggestions for accomodation. Please contact me if you intend to attend and/or give a talk. François Lamarche

1 0

Re: A small cartesian closed concrete category
by PETER EASTHOPE 26 May '08

26 May '08

Folk, At Thu, 14 Feb 2008 22:46:44 -0500 Fred E.J. Linton wrote, "... skeletal version of the full category of "sets of cardinality < 2" having as only objects the ordinal numbers 0 and 1." There is a better diagram on carnot now. http://carnot.pathology.ubc.ca/FLcategory.jpg If anyone can point out an error, that will help. There are several ways to specify this in TeX. The _Companion_ mentions LaTeX and two or three packages. Can anyone tell me how to go from TeX to SVG? I've yet to work with SVG. Seems that another approach is to write a macro package for diagrams in SVG and then to code a diagram directly using the macros. Thanks, ... Peter E. -- http://carnot.yi.org/ http://members.shaw.ca/peasthope/

3 3