November 2007 - 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

positions in Louvain-la-Neuve
by Enrico Vitale 30 Nov '07

30 Nov '07

Dear Colleagues, Two full-time academic positions at the Department of Mathematics in Louvain-la-Neuve are available. One position is in algebra and the other one in analysis. The deadline for applications is January 18, 2008. For further information please see at http://www.uclouvain.be/97693.html (algebra) http://www.uclouvain.be/38444.html (analysis) or contact Michel Willem, dean of the department, at michel.willem(a)uclouvain.be Best regards, Enrico Vitale

1 0

Re: countable Heyting algebras (third try)
by Dana Scott 29 Nov '07

29 Nov '07

On Nov 26, 2007, at 10:09 AM, Dana Scott wrote, recall in an earlier posting: > Now, F can also be considered as the clopens of the Cantor space > 2^N. The cHa of all opens is fully non-atomic, but it is uncountable. > Call it C for Cantor. The not-not stable elements of C are the so- > called regular open sets. They form an uncountable cBa which is the > completion of F. But we want to ask if there are there interesting > countable subalgebras of C? We note that elements of C are determined > by the elements of F they contain. (In fact, the cHa C is isomorphic > to the lattice of ideals of F.) The phrase "fully non-atomic" was not well chosen. Let us use "atomless" to mean "no minimal non-zero elements", and let us say a Ha is "gapless" if we cannot have elements a < b with [a, b] = {a, b} (i.e. nothing strictly between). An atomless Ba is always gapless. Now the cHa C above, as I pointed out in the previous message, DOES have gaps, even though it is atomless. (The Ba F is atomless, and it generates C by taking unions of clopen sets to make opens. Thus, no open set could be an atom in C.) Take any point t in the Cantor set 2^N. Let b = 2^N and let a = 2^N \ {t}. Clearly, a is a dense open set and [a, b] is a gap. By removing one pont at a time, we can have a whole sequence of dense open sets a_0 < a_1 < ... < a_n with each [a_i, a_(i+1)] being a gap. Note that negation in C gives --a_i = b, since in topological lattices double negation is interior-of-closure. In general, in any Ha which F generates, if a < b and [a, b] is a gap, then b =< --a. Because if not, then b /\ -a is non-zero. By the generation, there must be a non-zero e in F with e =< b /\ -a. Thus, e /\ a = 0. Because F is atomless, we can write e = f \/ g, with two disjoint, non-zero elements of F. But then c = a \/ f is an element strictly between a and b. This comment shows that gaps, if they exist are somewhat limited. But, C has many gaps, and in general an interval [a, --a] might be quite large. Remember, assuming a = --a for all a makes the Ha Boolean. So, I have not really made much progress in answering how F might generate a countable, non-boolean Ha. I am guessing there are many non-isomorphic ways this can happen.

1 0

countable Heyting algebras
by Dana Scott 27 Nov '07

27 Nov '07

Thomas Streicher recently noted: > omega + 1 is an infinite countable Ha which nevertheless > is complete True. And the dual algebra {0} + omega* with the descending copy integers is also a complete Ha (cHa). But this second example, which is non-atomic, is not fully non-atomic; that is, there are minimal gaps in the ordering. Take Q = rationals in [0,1]. This is a countable, non-complete Ha, where between any two distinct elements there is a third. Note that all these Ha's are subalgebras of the unit interval [0,1] of all reals -- which is uncountable, of course. In linearly ordered Ha's, the implication b --> c == c if b > c, and is 1 otherwise. It follows that the not-not stable elements are just 0 and 1. As I remarked once before, it is an old theorem that all countable, non-atomic Boolean algebras are isomorphic. Call this Boolean algebra F for free, for short. This isomorphism theorem is far from true for Ha's, however. Take the algebra Q x Q. This is a fully non-atomic, but it has FOUR not-not stable elements = {0,1} x {0,1}. So this is not the algebra Q. Take any other finite power, Q x Q x ... x Q. They are all different by reference to the not-not stable elements. The Ba I called F has a recursive structure (as one sees from what we know about propositional calculus) in that all the operations are recursive in terms of a simple enumeration of the elements of F. The question I want to consider is what countable Ha extend F in such a way F equals the not-not stable elements. Now, F can also be considered as the clopens of the Cantor space 2^N. The cHa of all opens is fully non-atomic, but it is uncountable. Call it C for Cantor. The not-not stable elements of C are the so- called regular open sets. They form an uncountable cBa which is the completion of F. But we want to ask if there are there interesting countable subalgebras of C? We note that elements of C are determined by the elements of F they contain. (In fact, the cHa C is isomorphic to the lattice of ideals of F.) Here is one construction. Let A be the arithmetically definable elements of C. That is, take the elements of x of C where the set {a in F | a =< x } is (first-order) arithmetically definable (in terms of the enumeration of F). I claim that A is a Ha. Of course it contains F; and, if it is a subalgebra of C, then the not-not stable elements give us an extension of F. But it is countable and the extension of F, call it G, is non-atomic; hence, the stable elements of A form a Ba G isomorphic to F. To check the subalgebra part we note for x,y in C and a in F: a =< x /\ y <==> a =< x & a =< y; a =< x \/ y <==> (for some b,c in F)[ a = b \/ c & b =< x & c =< y ]. Hence, if x,y are in A, then so are x /\ y and x \/ y. At first I had thought the recursively enumerable opens would be enough, but there is trouble with negation. We have for x in C and a in F, and with -x notating negation in C: a =< -x <==> (for all b in F)[ b =< x ==> a /\ b = 0 ]. The universal quantifier seems needed, and so {a in F | a =< -x } does not seem to be r.e. in general. But, if x is in A, then so is -x. We need to generalize this remark to implication in C, so for a in F and x,y in C: a =< x --> y <==> (for all b in F)[ b =< x ==> a /\ b =< y ]. Hence, if x,y are in A, then so is x --> y. And A is a sub-Ha of C. Note that in A, if an element x is not 0, than the interval [0,x] in A is in itself a non-Boolean cHa (a homomorphic image of A). Consider next the algebra A x F. This algebra is a countable, fully non-atomic Ha. The not-not stable elements of A come out to be G x F, which is isomorphic to F (and G). But, the element x = (0,1) has the interval [0,x] in A x F isomorphic to F. And that is Boolean. So, A and A x F are NOT isomorphic. Note, however, that A x F and (A x F) x F ARE isomorphic. Also, as I forgot to mention, A and A x A are isomorphic. Anyway, we have at least two non-isomorphic, non-Boolean Ha's with an isomorph of F as the not-not stables. And they are fully non-atomic. Are there other, non-isomorphic extensions of F? At this moment I do not see a knock-down argument. One idea, is to call the above algebra A_1 (for first-order definable opens) and consider the algebras A_n of n-th order definable opens. I think we get the same conclusions about A_n and A_n x F not being isomorphic, BUT is every A_n somehow isomorphic to A_1 (with a highly non-recursive automorphism of F)? Is that possible, or have I missed an obvious point? If the A_n are all not isomorphic, then we can probably get an uncountable collection of mutually non-isomorphic extensions of F. And, how would these relate to Sub(1) Ha's of countable topoi? Or are these considerations a red herring?

1 1

HOCAT 2008
by Joachim Kock 27 Nov '07

27 Nov '07

This is the second announcement of the conference HOCAT 2008 Homotopy Structures in Geometry and Algebra; Derived Categories, Higher Categories June 30 to July 5, 2008 Centre de Recerca Matemàtica Bellaterra (Barcelona) an event within the CRM thematic year on Homotopy Theory and Higher Categories http://www.crm.cat/hocat/ The following have agreed to speak at the conference: John Baez (University of California at Riverside) Paul Balmer (University of California at Los Angeles) David Benson (University of Aberdeen) Julia Bergner (Kansas State University) Tom Bridgeland (University of Sheffield) Søren Galatius (Stanford University) Ezra Getzler (Northwestern University) Mikhail Kapranov (Yale University) (to be confirmed) Ralf Meyer (Georg-August Universität Göttingen) (to be confirmed) Charles Rezk (University of Illinois at Urbana) Bertrand Toën (Université Paul Sabatier, Toulouse) Michel Van den Bergh (Hasselt University) A limited number of slots are available for contributed talks. Prospective speakers should submit an abstract to any of the organisers before March 31 (and will be notified before April 15). For registration (deadline May 30) and further information about the conference, see http://www.crm.cat/HOCAT2008/ We look forward to seeing you in Barcelona. The organisers, Carles Casacuberta André Joyal Joachim Kock Amnon Neeman Frank Neumann

1 0

SCORE: Student COntest in SoftwaRe Engineering (ICSE 2009)
by events-admin＠fmeurope.org 24 Nov '07

24 Nov '07

(Apologies if you receive multiple copies) PRELIMINARY CALL FOR PARTICIPATION Student COntest in softwaRe Engineering SCORE 2009 http://score.elet.polimi.it an initiative of the 31st International Conference in Software Engineering (ICSE 2009) 16-24 May 2009, Vancouver, Canada ICSE 2009 in Vancouver, Canada will see the first finals of the SCORE Software Engineering Contest. Teams from all over the world will enter in a competition that is open to students from undergraduate to masters level. Each team will develop a system chosen from those proposed by SCORE committee members. Teams will produce a report as their first deliverable, followed by a prototype system for those chosen as semi-finalists. Evaluation will be based on the quality of the software engineering process followed, as well as the outcome. In order to accommodate all academic calendars, the 2009 SCORE Contest will run from December 2007 to January 2009 with with team sign-up starting in February 2008 and ending in November 2008. Up to 10 finalist teams will be announced in April 2009. At least one representative from each of the finalist teams will have expenses paid to attend ICSE in Vancouver, 16-24 May 2009, for final judging. The SCORE Contest is aimed at promoting and fostering software engineering in universities worldwide. The committee consists of members of industry and academia. Each participating team will benefit from the experience of working on member selected projects, and from being part of an exciting new venture. Program Chairs: Mehdi Jazayeri, University of Lugano, Switzerland Dino Mandrioli, Politecnico di Milano, Italy Upcoming Important Date: 15 December 2007: publication of the project topics on the SCORE website For all information, including a full Call for Participation, see the website: http://score.elet.polimi.it _______________________________________________ events mailing list events(a)fmeurope.org http://www.fmeurope.org/mailman/listinfo/events

1 0

address change
by Myles TIERNEY 22 Nov '07

22 Nov '07

Just want to announce that my UQAM email address has changed. >>From tierney(a)math.uqam.ca to tierney.myles(a)uqam.ca. The Rutgers address remains the same: tierney(a)math.rutgers.edu. Myles Tierney

1 0

when are Lindenbaum-Tarski algebras complete?
by Thomas Streicher 22 Nov '07

22 Nov '07

I also suspect that Sub(1) of the free topos with nno is not complete. But countability does not suffice for refuting completeness (the ordinal \omega + 1 is an infinite countable cHa which nevertheless is complete). >>From Goedel's Theorem for HAH (higher order intuit. arithmetic) it follows that Sub(1) of the free topos with nno is not atomic. But that also doesn't suffice for refuting completeness. On p.169 of Freyd, Friedman and Scedrov's paper "Lindenbaum algebras of intuitionistic theories and free categories" (APAL 35) they claim "Lindenbaum algebras are almost never complete" but don't give a proof. Thomas Streicher

2 1

Complete Heyting algebras
by Lutz Schroeder 21 Nov '07

21 Nov '07

Is the Heyting algebra of global elements of the classifier in an elementary topos always complete? (Of course, the classifier is complete internally; here, I mean externally complete.) I suspect not, but I can't presently think of a natural counterexample. Thanks, Lutz Schröder -- ------------------------------------------------------------------ PD Dr. Lutz Schröder office @ Universität Bremen: Senior Researcher Cartesium 2.051 Safe and Secure Cognitive Systems Enrique-Schmidt-Str. 5 DFKI-Lab Bremen FB3 Mathematik - Informatik Robert-Hooke-Str. 5 Universität Bremen D-28359 Bremen P.O. Box 330 440 D-28334 Bremen phone: (+49) 421-218-64216 Fax: (+49) 421-218-9864216 mail: Lutz.Schroeder@dfki,de www.dfki.de/sks/staff/lschrode ------------------------------------------------------------------ ------------------------------------------------------------- Deutsches Forschungszentrum für Künstliche Intelligenz GmbH Firmensitz: Trippstadter Strasse 122, D-67663 Kaiserslautern Geschäftsführung: Prof. Dr. Dr. h.c. mult. Wolfgang Wahlster (Vorsitzender) Dr. Walter Olthoff Vorsitzender des Aufsichtsrats: Prof. Dr. h.c. Hans A. Aukes Amtsgericht Kaiserslautern, HRB 2313 -------------------------------------------------------------

3 2

CiE08 - 2nd Call for Papers
by A.Beckmann＠swansea.ac.uk 19 Nov '07

19 Nov '07

[Apologies for multiple copies] ****************************************************************** SECOND CALL FOR PAPERS CiE 2008 http://www.cs.swan.ac.uk/cie08/ Computability in Europe 2008: Logic and Theory of Algorithms University of Athens Athens, June 15-20 2008 PAPER SUBMISSION is now OPEN: http://www.cs.swan.ac.uk/cie08/submission.php This is the fourth in a series of conferences organised by CiE (Computability in Europe), a European network of mathematicians, logicians, computer scientists, philosophers, physicists and others interested in new developments in computability and their underlying significance for the real world. Previous meetings took place in Amsterdam (2005), Swansea (2006) and Siena (2007). CiE 2008 aims at bridging the gap from the logical methods of mathematical and meta-mathematical flavour to the applied and industrial questions that are involved in devising and choosing the right algorithms and analysing their effectiveness and efficiency. IMPORTANT DATES: Submission of papers: January 4, 2008 Notification of authors: February 15, 2008 Final revisions: March 7, 2008 TUTORIALS will be given by: John V. Tucker (Swansea) Moshe Y. Vardi (Houston, TX) PLENARY SPEAKERS will include: Keith Devlin (Stanford, CA) Rosalie Iemhoff (Utrecht) Antonina Kolokolova (Vancouver, BC) Janos Makowsky (Haifa) Dag Normann (Oslo) Prakash Panangaden (Montreal, QC) Christos Papadimitriou (Berkeley, CA) Jan van Leeuwen (Utrecht) & Jiri Wiedermann (Prague) SPECIAL SESSIONS Algorithms in the history of mathematics (organized by J. Hoyrup, Roskilde, and K. Chemla, Paris) Formalising mathematics and extracting algorithms from proofs (organized by H. Barendregt, Nijmegen, and M. Seisenberger, Swansea) Higher type recursion theory and applications (organized by U. Berger, Swansea, and D. Normann, Oslo) Algorithmic game theory (organized by E. Koutsoupias, Athens, and B. von Stengel, London) Quantum algorithms and complexity (organized by V. Kendon, Leeds, and B. Coecke, Oxford) Biology and computation (organized by N. Jonoska, Tampa FL, and G. Mauri, Milano) CiE 2008 conference topics include, but not exclusively * Admissible sets * Analog computation * Artificial intelligence * Automata theory * Classical computability and degree structures * Complexity classes * Computability theoretic aspects of programs * Computable analysis and real computation * Computable structures and models * Computational and proof complexity * Computational learning and complexity * Concurrency and distributed computation * Constructive mathematics * Cryptographic complexity * Decidability of theories * Derandomization * DNA computing * Domain theory and computability * Dynamical systems and computational models * Effective descriptive set theory * Finite model theory * Formal aspects of program analysis * Formal methods * Foundations of computer science * Games * Generalized recursion theory * History of computation * Hybrid systems * Higher type computability * Hypercomputational models * Infinite time Turing machines * Kolmogorov complexity * Lambda and combinatory calculi * L-systems and membrane computation * Mathematical models of emergence * Molecular computation * Neural nets and connectionist models * Philosophy of science and computation * Physics and computability * Probabilistic systems * Process algebra * Programming language semantics * Proof mining * Proof theory and computability * Quantum computing and complexity * Randomness * Reducibilities and relative computation * Relativistic computation * Reverse mathematics * Swarm intelligence * Type systems and type theory * Uncertain reasoning * Weak systems of arithmetic and applications Contributed papers will be selected from submissions received by the PROGRAMME COMMITTEE consisting of: L. Aiello (Roma) T. Altenkirch (Nottingham) K. Ambos-Spies (Heidelberg) G. Ausiello (Roma) A. Beckmann (Swansea, co-chair) L. Beklemishev (Moscow) P. Bonizzoni (Milano) S. A. Cook (Toronto ON) B. Cooper (Leeds) C. Dimitracopoulos (Athens, co-chair) R. Downey (Wellington) E. Koutsoupias (Athens) O. Kupferman (Jerusalem) S. Laplante (Orsay) H. Leitgeb (Bristol) B. Loewe (Amsterdam) E. Mayordomo Camara (Zaragoza) F. Montagna (Siena) M. Mytilinaios (Athens) (+) M. Nielsen (Aarhus) I. Oitavem (Lisboa) C. Palamidessi (Palaiseau) T. Pheidas (Heraklion) Ramanujam (Chennai) A. Schalk (Manchester) U. Schoening (Ulm) H. Schwichtenberg (Muenchen) A. Selman (Buffalo NY) A. Sorbi (Siena) I. Soskov (Sofia) C. Timpson (Leeds) S. Zachos (New York NY) We cordially invite all researchers (European and non-European) in computability related areas to submit their papers (in PDF- format, max 10 pages) for presentation at CiE 2008. We particularly invite papers that build bridges between different parts of the research community. The CONFERENCE PROCEEDINGS will be published by LNCS, Springer-Verlag. There will also be journal special issues, collecting invited contributions related to the conference. So far we have secured special issues in the journals "Theory of Computing Systems" and "Archive for Mathematical Logic".

1 0