February 2009 - Categories - categories.org.au

Research positions
by Maria Manuel Clementino 26 Feb '14

26 Feb '14

5-YEAR RESEARCH POSITIONS The Centre for Mathematics of the University of Coimbra (CMUC) invites applications for five 5-year research positions in all areas of Mathematics. Applicants should have a PhD in Mathematics and at least three years of post-doctoral experience, with an international-level publication record and demonstrated ability to perform independent research. Preference will be given to candidates working in one of the areas in which the members of CMUC are currently active. A very good command of English is required. The appointments will be made for three years, renewable for two more. Successful applicants are expected to develop research within the areas of interest of CMUC. They should also contribute to graduate studies, supervising students from the Department of Mathematics. The basic salary is equivalent to the index 195 of the Portuguese research career (in the order of 42 500 euros a year), in accordance with the Ciência 2008 guidelines http://alfa.fct.mctes.pt/apoios/contratacaodoutorados/edital2008 Benefits include private health insurance and social security. Applicants should send • cover sheet (available from www.mat.uc.pt/cmuc/coversheet.pdf) including names and contact information of three persons who can provide a letter of recommendation • curriculum vitae (publication list included) • a 5-year research proposal (2 pages max), emphasizing their own research goals as pdf files to cmuc(a)mat.uc.pt. The subject of the e-mail message must include the job reference C2008 FCTUC CMUC v15-v19. The deadline for applications is *September 10, 2008.* ------------------------------ More information can be found at www.mat.uc.pt

1 1

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

More arrow decorations
by Michael Barr 01 Mar '09

01 Mar '09

By playing with Micah's discovery (which is actually documented on page 39, third line from the bottom of Fig. 13), I have come up with the following potentially useful decorations: $$\bfig \morphism/@{>}|-@{|}/<500,500>[A`B;f] \efig$$ $$\bfig \morphism/@{>}|-@{x}/<500,500>[A`B;f] \efig$$ $$\bfig \morphism/@{>}|-@{o}/<500,500>[A`B;f] \efig$$ $$\bfig \morphism/@{>}|-@{*}/<500,500>[A`B;f] \efig$$ $$\bfig \morphism/@{>}|-@{||}/<500,500>[A`B;f] \efig$$ $$\bfig \morphism/@{>}|-@{)}/<500,500>[A`B;f] \efig$$ $$\bfig \morphism/@{>}|-@{(}/<500,500>[A`B;f] \efig$$ The same ideas also work in native xy-pic and, for all I know, in the matrix version as well. Michael

1 0

ticked arrowheads in xy-pic and diagxy
by Michael Barr 26 Feb '09

26 Feb '09

A month or two ago, Micah McCurdy wrote to ask me if it was possible to make an arrow with a tick in the middle (that is ----+---->) and I said I didn't know how to do that and suggested he ask Ross Moore. Ross told him that xy-pic didn't have that capacity. Well, Micah discovered that it did. Here are some samples, using diagxy, but that is just a front end to xy-pic. $$\bfig \node a(0,0)[A] \node b(300,400)[B] \arrow/@{>}|-*@{>}/[a`b;f] \efig$$ $$\bfig \ptriangle/>`>`@{>}|-@{|}/[A`B`C;f`g`h] \efig$$ $$\bfig \morphism/@{>}|-@{+}/<700,0>[ABCDE`F;h] \efig$$ $$\bfig \morphism/@{>}|-*@{|}/<700,0>[ABCDE`F;h] \efig$$ As far as I can tell, the * between the - and the @ has no effect. The one limitation is that what goes inside the -@{ } must be a \dir. This is a limitation for me, since I cannot figure out the syntax of \newdir. For this to work, it clearly has to be something that tex can rotate. Michael

1 0

E. W. Beth Dissertation Prize: 2009 call for submissions
by Carlos Areces 26 Feb '09

26 Feb '09

E. W. Beth Dissertation Prize: 2009 call for submissions Since 2002, FoLLI (the European Association for Logic, Language, and Information, www.folli.org) awards the E. W. Beth Dissertation Prize to outstanding dissertations in the fields of Logic, Language, and Information. We invite submissions for the best dissertation which resulted in a Ph.D. degree in the year 2008. The dissertations will be judged on technical depth and strength, originality, and impact made in at least two of the three fields of Logic, Language, and Computation. Inter-disciplinarity is an important feature of the theses competing for the E. W. Beth Dissertation Prize. Who qualifies. ~~~~~~~~~~~~~~ Nominations of candidates are admitted who were awarded a Ph.D. degree in the areas of Logic, Language, or Information between January 1st, 2008 and December 31st, 2008. There is no restriction on the nationality of the candidate or the university where the Ph.D. was granted. After a careful consideration, FoLLI has decided to accept only dissertations written in English. Dissertations produced in 2008 but not written in English or not translated will be allowed for submission, after translation, also with the call next year (for 2009). Respectively, nominations of full English translations of theses originally written in other language than English and defended in 2007 and 2008 will be accepted for consideration this year, too. Prize. ~~~~~~ The prize consists of: * a certificate * a donation of 2500 euros provided by the E. W. Beth Foundation. * an invitation to submit the thesis (or a revised version of it) to the new series of books in Logic, Language and Information to be published by Springer-Verlag as part of LNCS or LNCS/LNAI. (Further information on this series is available on the FoLLI site) How to submit. ~~~~~~~~~~~~~~ Only electronic submissions are accepted. The following documents are required: 1. the thesis in pdf or ps format (doc/rtf not accepted); 2. a ten page abstract of the dissertation in ascii or pdf format; 3. a letter of nomination from the thesis supervisor. Self-nominations are not admitted: each nomination must be sponsored by the thesis supervisor. The letter of nomination should concisely describe the scope and significance of the dissertation and state when the degree was officially awarded; 4. two additional letters of support, including at least one letter from a referee not affiliated with the academic institution that awarded the Ph.D. degree. All documents must be submitted electronically to bethaward2008(a)gmail.com. Hard copy submissions are not admitted. In case of any problems with the email submission or a lack of notification within three working days after submission, nominators should write to goranko(a)maths.wits.ac.za or policriti(a)dimi.uniud.it, with a cc to bethaward2008(a)gmail.com. Important dates: Deadline for Submissions: March 16, 2009. Notification of Decision: July 1, 2009. Committee : * Anne Abeill=C3=A9 (Universit=C3=A9 Paris 7) * Natasha Alechina (University of Nottingham) * Wojciech Buszkowski (Adam Mickiewicz University, Poznan) * Didier Caucal (IGM-CNRS) * Nissim Francez (The Technion, Haifa) * Valentin Goranko (chair) (University of the Witwatersrand, Johannesburg= ) * Alexander Koller (Saarland University) * Alessandro Lenci (University of Pisa) * Gerald Penn (University of Toronto) * Alberto Policriti (Universit=C3=A0 di Udine) * Rob van der Sandt (University of Nijmegen) * Colin Stirling (University of Edinburgh)

1 0

Question on E-coreflective subcategories
by Serge P. Kovalyov 26 Feb '09

26 Feb '09

Dear Category Theory gurus, In my reserach I have encountered the following problem. Let A be a full isomorphism-closed coreflective subcategory of a category C, G : C -> A be a coreflection. Let (E, M) be a factorization system for C-morphisms, such that class G(E) contains class of all A-isomorphisms and is contained in class of all A-retractions. Is any of the following statements correct: 1. If functor G preserves M, then it preserves E. 2. If any M-morphism is mono, then an M-morphism belongs to Mor(A) provided that its codomain belongs to Ob(A). Examples known to me satisfy both statements, but I fail to prove any. Thanks, Serge.

1 1

Dedekind versus Cauchy reals
by Thomas Streicher 23 Feb '09

23 Feb '09

Paul has asked why most constructivists have a preference for Cauchy numerals. Well, most constructivists haven't since under the widely accepted AC_N they coincide. This, of course, doesn't deny the fact that in many sheaf toposes AC_n fails. But from point of view of the BHK interpretation AC_N is most natural. But I think the reason for prefering Cauchy over Dedekind has a quite pragmatic reason. What you are interested in is a Cauchy sequence of reals with a fixed rate of convergence (ensuring e.g. that the n-th item has distance < 2^{-n} to the limit). AC_N of course allows you to magically find a modulus of convergence for every Cauchy sequence. But like Church's Thesis or Brouwer's Theorem this is sort of a Deus ex machina (actually those are 2 contradictory dei ex machina!) and thus of moderate help for exact computation on the reals. If you base your reals on Dedekind's idea you may certainly compute with them but the result isn't very telling because a computable Dedkind real is a semidecision procedure telling you whether a given rational interval contains the (ideal) real under consideration. This doesn't help you at all to compute the real up to a given precision because you have to first guess the right interval. Of course, you may consider a partition of some area of guesses and apply the semidecision procedure to all those intervals in parallel. But that's very inefficient and can't be implemented within usual sequential programming languages. Thomas

8 11

Fixing the constructive continued-fraction definition of the reals: proofs and refutations
by Vaughan Pratt 23 Feb '09

23 Feb '09

Prof. Peter Johnstone wrote: > On Wed, 11 Feb 2009, Vaughan Pratt wrote: > >> Prof. Peter Johnstone wrote: >>> Whoa! This simply can't work. Whatever the final coalgebra for N x (-) >>> looks like, it must (thanks to Lambek) be isomorphic to N x itself, >>> and therefore (since equality for N is decidable) must have lots of >>> complemented subobjects {0} x itself, {1} x itself, ... The point of >>> the continuity theorem for functions R --> R is that there are toposes >>> in which R has *no* nontrivial complemented subobjects [...] >>> The only way to get round it (apart from using glue) >>> is to replace N by some "nonstandard natural number object" having no >>> nontrivial complemented subobjects -- but where you get that from, I >>> don't know. >> >> You're assuming product distributes over sums, which would be true for >> ordinary product but I specified lexicographic product, with the left >> argument as the "high order digit" (converse of the usual convention for >> ordinal product in ordinal arithmetic). > > For goodness' sake, Vaughan! How many times do I have to tell you that > I'm talking about *the underlying object* of the final coalgebra, and > not its order structure or its topology? If the underlying object of > the lexicographic product is the ordinary (cartesian) product -- and > if it's not, then I don't know what it is -- then it distributes over > sums because that's what products do in a topos. Peter, if you don't mind my answering a question with a question, did either of us mention underlying objects before? (I could have overlooked an earlier message.) When you speak out of the blue about "the underlying object of the final coalgebra," what exactly is underlying what? I feel like I've abruptly stepped through a mirror into some strange part of topos theory that will be covered in Volume 3 of the Elephant. One notion of underlying object that makes sense for me in the context so far is the set E(1,X) of elements of an object X in a topos E. With this notion I have a prayer of making sense of your claim in the context of the following four objects of a topos E with NNO N (and whatever else if anything is needed to ensure that objects 2-4 exist in E). 1. N^2. 2. The initial object among all objects X with an element 0: 1 --> X and maps s,t: X --> X satisfying st = ts. 3. As for 2 with ts = t in place of st = ts. 4. As for 3 with st = s in place of ts = t. If I've grasped this slippery topos concept, all four objects X of E have, as their underlying set E(1,X), the set of all pairs (m,n) of natural numbers (up to isomorphism of course). In 2 the elements take the form of terms (s^m||t^n)(0) meaning m s's and n t's applied in any order to 0. In 3 the elements take the form of maps s^m(t^n(0)) meaning n applications of t (coarse tuning) followed by m applications of s (fine tuning), while in 4 they take the form of maps t^m(s^n(0)) (3 with s and t interchanged). I could well imagine 1 and 2 turning out to be isomorphic, but I feel I would get a lot from seeing the proof of whichever way that goes. I presume that 3 and 4 are isomorphic on the ground that s and t can be mapped to any two endomorphisms whence there must exist an isomorphism exchanging s and t. I imagine I would get less out of a rigorous proof of that unless there's a bug in the previous sentence. If there's no bug then this would seem to constitute a subtle difference from algebra, where the signature labels the operations in a way that prevents such an interchange and puts 3 and 4 in distinct albeit equivalent varieties. Whether or not 1 and 2 are isomorphic, they are in some sense both representations of the ordinary product of N with itself. Where I have greater difficulty is imagining an isomorphism between 2 and 3 merely on the ground that they have the same underlying object. I'm really not following your logic here. 2 implements product concurrently whereas 3 and 4 implement it sequentially. How could they be isomorphic in every topos? (I can see that they'd have to be isomorphic in Set, and presumably certain other toposes which however I have no idea how to characterize.) I regard 3 and 4 as equivalent definitions of the ordinal w^2 (w = \omega) in a topos. What are the necessary subobjects of 3, and which of those are necessarily complemented? I can think of the singletons {(m,n)}, the set of successor elements (since s: X --> X is a monic), and the *uniform* tails s^m: X --> X of the successor elements, but not the set of limit ordinals in w^2 since t: X --> X is not a monic, and hence not anything involving t. Are there other subobjects of 3, and can you characterize them all in some neat way? If as you seem to be implying, 1-4 are isomorphic, then I would have to agree with your "for goodness' sake" (yes it was really stupid of me not to see that) and resign myself to the absence (thus far) of any alternative to apartness for representing the reals. If however you agree with me that they can't be isomorphic (via something more reliable than my proof by agitated gesticulation born of summary dismissal) then we can move on with the rest of my envisaged program to define the continuum [0,x) in a topos without appealing to apartness. This too may or may not have bugs, whence the "proofs and refutations" qualification in the new subject line. (If this were darts there'd be a sequential scoreboard, concurrently with beer.) Vaughan

2 4

Categorical development of algebra?
by Jacques Carette 23 Feb '09

23 Feb '09

Has anyone ever redone the classical development of algebra (magma, monoid, semigroup, quasigroup, group, ring, modules, etc) as appropriate diagrams in the Kleisli category of signatures and translations? Jacques

1 0

MFPS Call for Participation
by MFPS 22 Feb '09

22 Feb '09

Dear Colleagues, Registration is now open for MFPS 25, which will take place at Oxford from April 3 through April 7. A list of accepted papers and an outline program are also available. Participants will be housed either in University College or in Linton Lodge, a hotel located not far from the Computer Laboratory where the meetings will take place. We offer reduced registration fees for students and for faculty who attend only the last two days of the program. To register for the meeting, please point your browser at http://www.math.tulane.edu/~mfps/mfps25 Accommodations are being held only until March 24, so please register before then to reserve a room. Thanks, and best regards, Mike Mislove Mathematical Foundations of Programming Semantics http://www.math.tulane.edu/~mfps

2 1