April 2003 - Categories - categories.org.au

More Topos questions ala "Conceptual Mathematics"
by Galchin Vasili 11 Jun '03

11 Jun '03

Hello, 1) In the very last chapter (Session 33 "2: Toposes and logic" of "Conceptual Mathematics" where the authors cover topoi, they define '=>' for the internal Heyting algebra of Omega: "Another logical operation is 'implication', which is denoted '=>'. This is also a map Omega x Omega->Omega, defined as the classifying map of the subobject S 'hook' Omega x Omega determined by the all those <alpha, beta> in Omega x Omega such that alpha "subset of" beta." Starting from "subobject S 'hook" ......" I got totally lost. I am frustrated because I know this is crucial to understanding why Omega is an internal Heyting algebra, so any help would be appreciated. (I am assuming that alpha and beta are subojects of Omega???). 2) In the same Session 33 on pg 350 is a set "rules of logic". These are exactly the axioms for a Heyting algebra, yes? Regards, Bill Halchin

2 2

2nd CFP: Workshop on Categorical Methods for Concurrency, Interaction, and Mobility
by Thomas Hildebrandt 01 May '03

01 May '03

2nd Call for Papers: [ Apologies for multiple copies ] Workshop on CATEGORICAL METHODS FOR CONCURRENCY, INTERACTION, AND MOBILITY Marseille, France, 6 September, 2003 affiliated with CONCUR 2003 and held together with GETCO 2003 (See also: http://www.mcs.le.ac.uk/events/cmcim03) Aims and Scope: The aim of the workshop is to bring together researchers applying category theory to concurrency, interaction, or mobility. Topics of interest include, but are not limited to: categorical algebras of processes categorical methods in game semantics and geometry of interaction categorical models of term/graph rewriting or rewriting logic Chu spaces coalgebras, bialgebras, coinduction comparing models of concurrency enriched categories of processes interaction categories presheaf models GETCO'03: Due to the close relation between geometric and topological methods on the one hand and categorical methods on the other hand, CMCIM'03 will be held jointly with the workshop on Geometric and Toplogical Methods in Concurrency Theory (GETCO'03). Both workshops will be on the same day with their talks not overlapping. Invited Lecture: Glynn Winskel Programme Committee: Marcelo Fiore (Cambridge) Eric Goubault (Paris) Thomas Hildebrandt (Copenhagen) Alexander Kurz (Leicester) Ugo Montanari (Pisa) John Power (Edinburgh) Jan Rutten (Amsterdam) Peter Selinger (Ottawa) Glynn Winskel (Cambridge) Important dates: Deadline for submission: June 1 Notification of acceptance: July 7 Final version due: July 27 Workshop dates: September 6 Location: The workshop will be held in Marseille. It is a satellite workshop of CONCUR 2003. For venue and registration see the CONCUR web page at http://concur03.univ-mrs.fr Submissions: It is planned to publish the proceedings of the meeting as a volume in Elsevier's ENTCS series. Papers must contain original contributions. Papers should be submitted as PostScript files by email to cmcim03(a)mcs.le.ac.uk , containing `CMCIM-submission' in the subject. A separate message should also be sent (subject: CMCIM-abstract), containing authors, title, and a text-only abstract. Workshop organizers: Thomas T. Hildebrandt Theory Department, IT University of Copenhagen Glentevej 67, 2400 Copenhagen NV, Denmark Alexander Kurz Department of Mathematics and Computer Science, University of Leicester, University Road, Leicester, LE1 7RH. Email: cmcim03(a)mcs.le.ac.uk Further information at http://www.mcs.le.ac.uk/events/cmcim03

1 0

Hacking through topos theory ... internal language
by Galchin Vasili 30 Apr '03

30 Apr '03

Hello, I have started reading the stuff on internal language in McLarty's book and also in the Lambek/Scott book. I am trying to short circuit my learning a little (in a vast and humbling subject!) What are the models for topos logic? The class of Heyting algebras? Regards, Bill

1 0

a question about equational classes
by James J. Madden 29 Apr '03

29 Apr '03

There are many examples of functors between equational classes F:V -> W that are defined by letting F(A) be the free W-algebra on the elements of A modulo an equivalence generated by certain expressions of the form: w(v(a)) = w'(v'(a)). Here, w, w' are tuples of W-words, v(a) and v'(a) are tuples of V-words that we fill in in all possible ways with elements of A. A nice example is Joyal's definition of the "spectrum" functor from commutative rings to distributive lattices. Here, F(A) is the free distributive lattice on the underlying set of A, modulo the relations: 1 = top, 0 = bottom, a*b = a inf b, a+b sup a sup b = a sup b. (Under strong enough set-theoretic assumptions, F(A) is the distributive lattice of compact opens in the spectrum of A, and if we let 'a' stand for the element of F(A) corresponding to an element a from A, then 'a' may be identified the "cozero" set of a.) Several similar examples of spectrum functors defined by generators and relations appear in Johnstone's book on Stone spaces. There are many other examples, e.g., free group over a monoid, group rings, booleanization of a lattice. There are also examples from K-theory (the Steinberg group, I believe---but now I'm recalling very old stuff so don't pin me down). Less well-known, there a kind of universal valuation that I've been interested in, which is a functor from commutative rings to lattice-ordered monoids defined by letting F(A) be the free commutative, totally distributive lattice-ordered-monoid with infinity on A modulo: 1_A = 0_F(A), 0_A = infinity, a *_A b = a +_F(A) b, a +_A b geq a sup_F(A) b. (These, of course, are equational versions of the usual conditions for a valuation.) My question is, has there ever been an attempt to make a general theory about functors of this kind? Any relevant references that anyone knows about? -- James J. Madden Department of Mathematics Louisiana State University Baton Rouge LA 70803-4918

1 0

correction
by Peter Freyd 29 Apr '03

29 Apr '03

Vaughan has noticed that I hadn't broken the commutative habit. So let me start again. He asked if one can determine a minimal equational theory with the theory of distributive lattices as its unique maximal consistent extension. Yes, here's an example: x meet 1 = x, x meet 0 = 0, 1 join 1 = 1, 1 join 0 = 1, 0 join 1 = 1, 0 join 0 = 0. (I was missing the penultimate equation.) There is a Klein-group's worth of variations. One operation simultaneously interchanges meet and join, 0 and 1. Another operation simultaneously interchanges the arguments of the operators. I'll hazard that the resulting four theories are the only ones that do the trick.

1 0

equivalent varieties
by Peter Freyd 28 Apr '03

28 Apr '03

Varieties of algebras when viewed as categories can be unexpectedly equivalent. For a reason explained at the end, I was looking at varieties of unital rings satisfying the equations p = 0 and x^p = x, one such variety for each prime integer p. The equivalence type of these categories is independent of p. The easiest way of establishing that is to show that each is equivalent to the category of Boolean algebras (a well-known fact when p = 2) and all the equivalences can by established by just one functor. Given a unital ring, R, define B(R) to be the boolean algebra of its central idempotents where the meet of a and b is ab and the join is a + b - ab. Then the restriction of B to the p'th variety described above is always an equivalence of categories. The fastidious will note (one would certainly hope) that B is not a functor in general (homomorphisms don't preserve centrality). But in a ring "without nilpotents" (that is, in which x^2 = 0 implies x = 0) all idempotents are central. The equations x^p = x, of course, imply the absence of nilpotents. (Given p the inverse functor to B can be described as follows: for a Boolean algebra C consider the set of "p-labeled partitions of unity", that is, the set of functions f:Z_p -> C whose values are pairwise disjoint and have unity as their join. Given two such, f and g, define their sum by setting (f+g)i to be the join of the set { fj ^ gk | j+k = i } and their product by setting (fg)i to be the join of { fj ^ gk | jk = i }.) I was looking for examples of equational theories with unique maximal consistent equational extensions. The best known example is the theory of lattices: every equation consistent with the theory of lattices is a consequence of distributivity. (Inconsistent in the equational setting means that all equations can be proved, or equivalently, the one equation x = y can be proved.) That is, the unique maximal consistent extension of the theory of lattices is the theory of distributive lattices (fortunately this is independent of your choice of whether top and/or bottom are considered to be part of the theory of lattices). A less-well-known example is the theory of Heyting algebras: every equation consistent with the theory of Heyting algebras is a consequence of the law of double-negation: (x -> 0) -> 0 = x. That is, the unique maximal consistent extension of the theory of Heyting algebras is the theory of Boolean algebras. This search for examples was sparked by what I consider a great example -- not to be described here -- in "algebraic real analysis". The only other examples I've found are the theories of unital rings of characteristic p, one such example for each prime p. To shift to the traditional language here, any polynomial identity consistent with characteristic p is a consequence of characteristic p and the identity x^p = x. A lot of examples. But, then again, maybe just one example.

6 7

unique maximal consistent extensions
by Peter Freyd 27 Apr '03

27 Apr '03

When looking for the examples I mentioned in my last post, I had in mind examples where the unique maximal consistent extension, of an equational theory is finitely axiomatizable If one drops that condition there are many more examples, and one of particular interest: the theory of lattice-ordered unital rings. This theory does have a unique maximal consistent extension but it is very much not finitely axiomatizable. For any integer polynomial, P, the non-existence of a root for P is equivalent with the equation 1 = (1 meet P^2). (Conversely, whether any equation holds -- indeed, whether any universally quantified sentence in this theory holds -- is equivalent to a Diophantine problem,) Vaughan has asked if one can determine a minimal theory whose unique maximal consistent extension is the theory of distributive lattices. To my surprise the answer is yes. Indeed, there are exactly two such theories (minimality not defined by number of equations but by their deductive strength). One is the set of five equations: x meet 1 = x, x meet 0 = 0, 1 join 1 = 1, 1 join 0 = 1, 0 join 0 = 0. The other, of course, is obtained my interchanging meet and join, 0 and 1.

1 0

Categories on vacation
by Bob Rosebrugh 27 Apr '03

27 Apr '03

Your Categories moderator will be out of email contact April 29-May 6, 2003. Postings submitted to Categories during that period will be distributed when I return. (If you were thinking of posting something and want it distributed sooner, you've got till Monday afternoon...) Best wishes, Bob

1 0

Kripke semantics and Alexandrov topology
by Galchin Vasili 25 Apr '03

25 Apr '03

Hello, I have been re-reading the chapter on intuitionism in Goldblatt's book, specifically the section on Kripke semantics. Am I wrong to say that Kripke semantics is based on the Alexandrov topology generated by the underlying poset? Regards, Bill

3 2

WAIT 2003: Deadline approaching
by WAIT 2003 25 Apr '03

25 Apr '03

---------------------------------------------------------------------- CALL FOR PAPERS 32 JAIIO - WAIT 2003 Argentinian Workshop on Theoretical Computer Science Buenos Aires - Argentina September 1-5, 2003 Deadline for reception of papers: May 4 ---------------------------------------------------------------------- The Argentinian Workshop on Theoretical Computer Science (WAIT) has become an important Latin American forum for the exchange of ideas and the presentation of research in theoretical computer science and its applications. The workshop aims are to build a bridge between academic and applied research and to stimulate the exchange of ideas and experience between theory and practise in computer science. The meeting includes contributed and invited talks, and tutorials. Further, we are very pleased to announce that there will be a special issue of ENTCS (http://www.elsevier.nl/locate/entcs) dedicated to WAIT 2003 publishing a selection of outstanding contributions. WAIT 2003 (http://wait2003.famaf.unc.edu.ar) the 7-th workshop in the series, will be held in Buenos Aires during September 1-5 (2003) as part of the 32-nd Argentinian Conference on Informatics and Operations Research (32 JAIIO, http://www.jaiio2003.uade.edu.ar) Buenos Aires (http://www.buenosaires.gov.ar/areas/turismo/en/) is a cosmopolitan and modern urban centre easily accessible by plane from most mayor cities in the world. The city is characterised by the multiplicity of its artistic expressions, ranging from the great assortment of sculptures and monuments to streets and corners that surprise with their allegorical reliefs and murals. The climate of Buenos Aires ---oceanic and warm--- is mild all year round, allowing visitors to discover the city on foot in any season. The city offers all categories of accommodation, and food ---which is something of a cult--- is of high quality. TOPICS Submissions are welcome in all fields of Theoretical Computer Science. Specific topics of WAIT 2003 include (but are not limited to): * Logical and algebraic foundations of computer science (logics for computation, category theory, relation algebras, type theory); * Formal methods (formal specification of sequential and concurrent programs, analysis, verification and transformation of programs, model checking); * Algorithms and data structures (sequential, parallel, distributed and on-line computing, probabilistic algorithms); * Automata theory and computational complexity; * Symbolic and algebraic computation; * Quantum Computing; * Bioinformatics. Submissions are expected to contain original research and will be refereed by international experts. Research papers must contain previously unpublished results. They will be judged on the base of originality and importance of their contributions and clarity of presentation. Papers should not exceed 12 pages, including figures and references. PROGRAM COMMITTEE: Martin Abadi (University of California at Santa Cruz) Gilles Barthe (INRIA Sophia-Antipolis) Gabriel Baum (Universidad de La Plata) Veronica Becher (Universidad de Buenos Aires) Vincent Danos (CNRS, Paris VII) Peter Dybjer (University of Gothenburg) Roberto Di Cosmo (PPS, Paris VII) Esteban Feuerstein (Universidad de Buenos Aires) Marcelo Fiore (Cambridge University) (co-chair) Daniel Fridlender (Universidad de Cordoba) (co-chair) Joos Heintz (Universidad de Buenos Aires) Gonzalo Navarro (Universidad de Chile) Peter O'Hearn (QMW, University of London) Alfredo Viola (Universidad de la Republica) IMPORTANT DATES: Deadline for reception of papers.................................May 4 Notification of acceptance.....................................June 27 Deadline for reception of the final version....................July 18 INSTRUCTIONS FOR AUTHORS: To facilitate the dissemination of papers and results, authors are invited to submit their papers in English. However, papers in Spanish or Portuguese are also welcome. Accepted contributions will be published in the Proceedings of the 32 JAIIO. Further, a selection of outstanding contributions will be invited to be published (in English) in a special issue of ENTCS dedicated to WAIT 2003. Papers should respond to ENTCS format (obtainable from http://math.tulane.edu/~entcs/) or similar, and must be submitted electronically in PostScript format (ghostview-readable) or PDF to the following e-mail address: wait2003(a)famaf.unc.edu.ar. Authors should communicate in a separate e-mail (in ASCII format) the title of the paper together with a short abstract, name and affiliation of all co-authors and their e-mail addresses, phone and FAX numbers. The message should also contain a list of keywords describing the area of the paper. ----------------------------------------------------------------------

1 0