March 2005 - Categories - categories.org.au

replacemnt
by Thomas Streicher 17 Mar '05

17 Mar '05

As the topic of Replacement versus topos logic (i.e. higher order intuitionistic arithmetic) has come up (again) it might be appropriate to point at a paper of mine (which has been accepted for the proceedings of "From Sets and Types to Topology and Analysis: Towards Practicable Foundations for Constructive Mathematics" (L.~Crosilla, P.~Schuster, eds.), Oxford University Press, forthcoming) and can be found at www.mathematik.tu-darmstadt.de/~streicher/NOTES/UniTop.ps.gz In this paper I discuss how to extend the notion of toposes in order to capture the relevant part of the set-theoretic Replacement Axiom. I suggest to add so called universes to toposes which allow one to quantify over small sets (the elements of the universe). This notion of universe has been developed (in a predicative setting) by Martin-Loef in the early 70ies and in the 2nd half of the eighties there was quite some activity to give semantics to such universes using categorical notions. Actually, the categorical notion of universe was introduced already in J. B'enabou "Problemes dans les topos" (Louvain-la-Neuve Report, 1973) My conclusion is that most of the uses of replacement are to define (by recursion) families of sets indexed by some index set (e.g. P^n(X) for n \in N) which is impossible in toposes. Alas, in my note it is not settled whether this notion of universe allows one to build models for IZF as in Joyal and Moerdijk's "Algebraic Set Theory" where they use a slightly different notion of universe (see dicussion on p.12 of my note for more details). Of course, I agree that for most mathematics higher order arithmetic suffices (and actually subsystems of 2nd order arithmetic suffice!). In classical mathematics theorems requiring Replacement are typically from Descriptive Set Theory as e.g. Borel Determinacy (BD). The situation is that ZF proves BD but Z (i.e. ZF without replacement) does not. However, for IZF (intuit. set theory) such examples are not known (Set validates BD but the realizability model for IZF does not!). However, there is a very nice example from Computer Science due to Alex Simpson in "Computational Adequacy for Recursive Types in Models of Intuitionistic Set Theory" In Annals of Pure and Applied Logic, 130:207-275, 2004 where he shows that relative to the axioms of SDT (Synthetic Domain Theory) IZF proves the existence of solutions of recursive domain equations whereas higher order arithmetic doesn't. (The reason is that for solutions of such recursive domain equations one has to construct by recursion families of domains which are not a priori contained in an already given domain). But for this pleasant example the existence of a universe (hosting all domains) would already be sufficient. But existence of solutions of domain equations cannot be formulated in the language of higher order arithmetic itself. Thus, from this point of view it is still open whether there exist (purely "mathematical") statements expressible in the language of higher order arithmetic (like e.g. Borel determinacy) which can be proved in IZF but not in intuit.(!) higher order arithmetic. I would be most grateful if anyone could tell me such an example! Thomas 23-Mar-2005 21:52:32 -0400,973;000000000000-00000000

1 0

PhD studentships
by Paul B Levy 17 Mar '05

17 Mar '05

Dear all, Funding is available for PhD studentships in theory/semantics at the University of Birmingham. We have a vibrant group of researchers across the spectrum from programming languages to mathematical foundations. Our work includes game, domain, effect, pointer and categorical semantics, logic, topology and much else besides; and the funding is not tied to particular projects. As our current students will confirm, we have a lively and friendly atmosphere. The group is burgeoning right now, and includes - Martin Escardo (domain theory, topology, semantics and more) - Dan Ghica (interaction models of computation and applications to software analysis) - Achim Jung (domain theory, semantics, topology) - Paul Blain Levy (denotational semantics and its problems) - Uday Reddy (programming logic and formal methods, object-oriented programming) - Eike Ritter (type theory, computational logic, automatic verification) - Hayo Thielecke (types and logics for effects in programming languages) - Steve Vickers (relating topology, computer science and logic, especially using toposes and locales) This year, we're hosting both Midlands Graduate School and Mathematical Foundations of Progamming Semantics. It's all happening here - come and be part of it! Please don't hesitate to send us any queries, whether about research, money or anything else. Application information is at http://www.cs.bham.ac.uk/study/postgraduate-research/research_applications.… regards Paul -- Paul Blain Levy email: pbl(a)cs.bham.ac.uk School of Computer Science, University of Birmingham Birmingham B15 2TT, U.K. tel: +44 121-414-4792 http://www.cs.bham.ac.uk/~pbl 17-Mar-2005 17:13:39 -0400,3995;000000000000-00000000

1 0

Categories as a "foundation" for math
by Topos8＠aol.com 17 Mar '05

17 Mar '05

In the 1966 La Jolla conference volume appeared Lawvere's paper "The category of categories as a foundation for mathematics". Is it known just how much mathematics can be done using Lawvere's axiom scheme? My confusion on this point arises partly from a remark by Gray in his paper "The categorical comprehension scheme" in which he asserted that Lawvere's axioms couldn't do all that was claimed for them. Of course all of this predates the recognition that an elementary topos (with nn object) can be treated as a "universe of sets". I know that there has been some work (e.g. Joyal and Moerdijk) on constructing models of ZF set theory within categories with special properties. Can such categories be constructed using Lawvere's axioms? I hope this question makes sense but my skills in set theory and logic are pretty limited. Carl Futia 11-Mar-2005 13:01:41 -0400,22182;000000000001-00000000

7 6

Structures and Deduction Workshop 2nd cfp - ICALP'05 Satellite
by Paola Bruscoli 16 Mar '05

16 Mar '05

(ICALP Workshop-Lisbon July 16-17, 2005) STRUCTURES AND DEDUCTION The quest for the essence of proofs http://www.prooftheory.org/sd05 Submissions page is now open! http://www.easychair.org/SD05/submit/ This meeting is about new algebraic and geometric methods in proof theory, with the aim of expanding our ability to manipulate proofs, eliminate bureaucracy from deductive systems, and ultimately provide: 1) a satisfying answer to the problem of identity of proofs and 2) tools for improving our ability to implement logics. Stimulated by computer science, proof theory is progressing at fast pace. However, it is becoming very technical, and runs the risk of splitting into esoteric specialties. The history of science tells us that this has happened several times before, and that these centrifugal tendencies are very often countered by conceptual reunifications, which occur when one is looking at a field after having taken a few steps back. Some emerging ideas are showing their unifying potential. Deep inference's atomization of deductions simplifies and unifies the design of deduction systems; it provides unprecedented plasticity to proofs and has injected new impetus into the theory of proof nets. New proof nets, and new associated semantics, are giving surprising insight about the very subtle relationship between categories and proofs, for example in the formerly intractable case of classical logic. The field of deduction modulo, which turns out to be very much in the spirit of deep inference, decreases our dependency on the syntactic presentation of functional objects, and brings us closer to their intrinsic nature, even from the computational point of view. After studying all those trees for years we at last have the impression of looking at the forest. The core topics are organised along the axis: algebraic semantics deduction of proofs deep inference modulo game semantics operads and specification <--> structads <--> proof nets proof search calculus of deductive structures implementations proof nets This workshop aims at being a meeting point for all those who are interested in decreasing the dependency of logic from low-level syntax. The list of topics above is not exhaustive: if you feel you can contribute to the discussion along the broad lines outlined above, please submit your contribution. SUBMISSION, IMPORTANT DATES AND PUBLICATION Contributions such as work in progress, programmatic/position papers, tutorials, as well as regular papers are more than welcome. We will favor the former over regular papers that seem to us to be minor contributions, although we will definitely not reject major contributions! Submissions should be formatted with the LNCS LaTeX style, and should take between two and fifteen pages, to allow the committee to assess their merits with reasonable effort. This limit can be relaxed for the versions that will be presented at the workshop, depending on the total bulk of the accepted contributions. We want to make clear that contributions from members of the PC are allowed. Contributions should be submitted electronically at the following site (powered by EasyChair, thanks to Andrei Voronkov): http://www.easychair.org/SD05/submit/ submission: 15.4.2005 notification: 22.5.2005 final version: 10.6.2005 The volume of proceedings will be made available elctronically, allowing authors to keep their copyrights. The issue of printed proceedings is still under discussion. INVITED SPEAKERS Martin Hyland (Cambridge) Claude or Helene Kirchner (LORIA & INRIA Lorraine, Nancy) Dale Miller (INRIA Futurs and LIX, Paris) David Pym (Bath and HP Labs) PROGRAM COMMITTEE Paola Bruscoli (Dresden) Pietro Di Gianantonio (Udine) Gilles Dowek (LIX & Ecole Polytechnique, Paris) Roy Dyckhoff (St Andrews) Rajeev Gore' (NICTA and ANU, Canberra) Francois Lamarche (LORIA & INRIA Lorraine, Nancy) -- Chair Luke Ong (Oxford) Prakash Panangaden (McGill) Michel Parigot (CNRS, Paris) Charles Stewart (Dresden) Thomas Streicher (Darmstadt) LOCATION Lisbon, July 16-17, 2005; the workshop is a satellite of the ICALP 2005 conference. HOW TO REGISTER A registration fee for attending the workshop will be paid to the ICALP Workshop general chair; no fee for participating in the main conference should be necessary, while participation in both conference and workshop should entitle to special discounts. Please visit the ICALP web site for up-to-date, precise information: <http://icalp05.di.fct.unl.pt> ORGANISERS Paola Bruscoli (Dresden) Francois Lamarche (LORIA & INRIA Lorraine, Nancy) -- Chair Charles Stewart (Dresden) 16-Mar-2005 11:16:08 -0400,1933;000000000000-00000000

1 0

TAC: New Editors
by Bob Rosebrugh 15 Mar '05

15 Mar '05

The editors of Theory and Applications of Categories are pleased to announce that Professors Richard Blute of the University ot Ottawa, Ezra Getzler of Northwestern University and Brooke Shipley of the University of Illinois at Chicago have joined the Editorial Board. Articles for consideration by TAC may be submitted to any member of the Editorial Board. Professor John Baez has resigned from the Editorial Board, and the editors thank him for his service over the past ten years. best wishes, Bob Rosebrugh =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= Robert Rosebrugh, Professor Department of Mathematics and Computer Science Mount Allison University 67 York Street Sackville, NB E4L 1E6 Canada rrosebrugh(a)mta.ca www.mta.ca/~rrosebru +1-506-364-2530 fax: -364-2583 14-Mar-2005 20:16:35 -0400,1965;000000000001-00000000

1 0

Re: Categories as a "foundation" for math
by Vaughan Pratt 13 Mar '05

13 Mar '05

Besides Carl Futia's question as to the expressiveness of categories (if I understood its drift) there is also the less judgmental question of what it feels like to use category theoretic methods at any given level of sophistication, from the viewpoint of a classically trained mathematician, scientist, engineer, or technologist. Bill Lawvere's early pre-topos (in the nontechnical sense) work on the categorical axiomatization of sets creates something of a straw to grasp at for non-category theorists looking for insights into this question. But while it is natural to view topos theory as a maturation of this program, there is a bifurcation in the maturation process that should be kept in mind. Toys are the natural playthings of the institution of childhood. Maturation can shift the focus of that energy either to more sophisticated toys (and I lump preoccupation with fast cars together with love of good engineering or architectural design here) or to the support of institutions -- teaching, management, etc. This is not purely bimodal but is something of a spectrum, with entrepreneurs, technology visionaries, research university professors, and project team leaders occupying intermediate positions along it. Taking ordinary sets as the toys of late 19th century foundations, it seems to me that set theory and algebra stand in an analogous relationship. Set theory continues the early preoccupation with sets at a far more mature and technically demanding level. I'm not suggesting that set theory's motto should be "he who dies with the largest cardinal wins," but rather that its success has created a certain technically focused inertia that has sustained set theory for over a century in close to its original form as conceived by its founders. Algebra is more institutional in its outlook. Whereas set theory sits patiently inside the same house it was born in, algebra can view that house from outside if it wishes. In this regard I lump category theory together with algebra, with category theory strongly supporting the inside-out perspective via the Duality Principle as generalized from posets to categories (reverse the arrows -- the Duality Principle is like glass, so transparent as to make its substance invisible). This is actually easier for algebra as it was not born in that house, predating set theory by half a century. The symmetric group of finite order n is more easily seen to have an underlying set than say a Lie algebra, and one might even take the view that Lie algebras have been unjustly dragged into the house and taken hostage by set theory, with pointset topology intervening to prevent their torture. Isbell's example of the intersection of the rationals and the irrationals as a nonvacuous locale makes the point that a faithful functor to Set^op, as a house on the other side of the street, might offer a more hospitable home than the Set house for some denizens of mathematics. The fact that many algebraists still have a strongly set-theoretic view of their world is more inertial than intrinsic, as evidenced by an increasing willingness of the mainstream algebra community to accept categorical perspectives as a legitimate point of view. This is not to say a set theoretic outlook on algebra is bad, rather that it puts traditional algebraists in a middle position not unlike that of technology visionaries or team leaders. But without recognition of the Duality Principle, a geometer such as Bill Thurston, who as then-director of MSRI kicked off the 1989 UACT meeting with the insightful confession that he felt ill contemplating Set^op, is missing a major part of the big picture, just as is the visionary entrepreneur who fails to see the need for marketing expertise. It should be a rite of passage to category theory that the initiate be told that a topos is not intended as a universe of sets so much as of institutions (again in a non-technical sense) of a particular character. Even those who insist that a graph is a set (on the ground that everything is a set) will surely allow that it is a set with structure. And in fact they would not object to calling a graph a pair of sets V and E of vertices and edges as long as you humored them by allowing that it was therefore the set {{V,E},{V}}, as the von Neumann encoding of the pair (V,E) as a single set. But if you could put this encoding in perspective for them as being less central (in whatever sense impresses them: pedagogical, natural, etc.) to the graph concept than the basic sets V and E themselves, you are off to a good start explaining what toposes are about. If this post had been directed to non-category theorists it would be necessary to make it somewhat longer. The present audience should need nothing beyond the distinction between sets per se such as V and E vs. presheaves of sets to continue it to its intended conclusion (though it's a nice question how many conclusions might result). Those with experience of hostile appointment and promotion committees may already have had some practice with that. Simplicial complex theory as an extension of reflexive graph theory (both as petits toposes) is a nice next step avoiding the implication that graphs constitute the core paradigm here. The same needs to be pointed out concerning the role of reflexive graphs as the algebraic stepping stone from sets to categories, which is only the beginning of that story when one looks ahead to n-categories. While I'm still unclear as to the optimal order of things for training the working mathematician in category theory, a short introduction to category theory for the benefit of the other kind of mathematician might profitably organize itself around a manageable part of the background material presumed by the above point of view, with the goal being insight into why presheaves are not sets and how toposes abstract them. Unless of course you're one of those rugged left-field individualists who believe that linearly distributive categories are more important than toposes. ;) Vaughan Pratt 14-Mar-2005 11:01:08 -0400,3248;000000000000-00000000

1 0

Bott periodicity and an octagon of functors
by John Baez 11 Mar '05

11 Mar '05

Dear Categorists - Though it's not really news, I only recently realized that Bott periodicity is all about an octagonal diagram with functors circling around clockwise, all with ambidextrous adjoints circling around the other way. Maybe some of you will be interested.... Best, jb ......................................................................... Also available at http://math.ucr.edu/home/baez/week211.html March 6, 2005 This Week's Finds in Mathematical Physics - Week 211 John Baez The last time I wrote an issue of this column, the Huyghens probe was bringing back cool photos of Titan. Now the European "Mars Express" probe is bringing back cool photos of Mars! 1) Mars Express website, http://www.esa.int/SPECIALS/Mars_Express/index.html There are some tantalizing pictures of what might be a "frozen sea" - water ice covered with dust - near the equator in the Elysium Planitia region: 2) Mars Express sees signs of a "frozen sea", http://www.esa.int/SPECIALS/Mars_Express/SEMCHPYEM4E_0.html Ice has already been found at the Martian poles - it's easily visible there, and Mars Express is getting some amazing closeups of it now - here's a here's a view of some ice on sand at the north pole: 3) Glacial, volcanic and fluvial activity on Mars: latest images, http://www.esa.int/SPECIALS/Mars_Express/SEMLF6D3M5E_1.html What's new is the possibility of large amounts of water in warmer parts of the planet. Now for some math. It's always great when two subjects you're interested in turn out to be bits of the same big picture. That's why I've been really excited lately about Bott periodicity and the "super-Brauer group". I wrote about Bott periodicity in "week105", and about the Brauer group in "week209", but I should remind you about them before putting them together. Bott periodicity is all about how math and physics in n+8-dimensional space resemble math and physics in n-dimensional space. It's a weird and wonderful pattern that you'd never guess without doing some calculations. It shows up in many guises, which turn out to all be related. The simplest one to verify is the pattern of Clifford algebras. You're probably used to the complex numbers, where you throw in just *one* square root of -1, called i. And maybe you've heard of the quaternions, where you throw in *two* square roots of -1, called i and j, and demand that they anticommute: ij = -ji This implies that k = ij is another square root of -1. Try it and see! In the late 1800s, Clifford realized there's no need to stop here. He invented what we now call the "Clifford algebras" by starting with the real numbers and throwing in n square roots of -1, all of which anticommute with each other. The result is closely related to rotations in n+1 dimensions, as I explained in "week82". I'm not sure who first worked out all the Clifford algebras - perhaps it was Cartan - but the interesting fact is that they follow a periodic pattern. If we use C_n to stand for the Clifford algebra generated by n anticommuting square roots of -1, they go like this: C_0 R C_1 C C_2 H C_3 H + H C_4 H(2) C_5 C(4) C_6 R(8) C_7 R(8) + R(8) where R(n) means n x n real matrices, C(n) means n x n complex matrices, and H(n) means n x n quaternionic matrices. All these become algebras with the usual addition and multiplication of matrices. Finally, if A is an algebra, A + A consists of pairs of guys in A, with pairwise addition and multiplication. What happens next? Well, from then on things sort of "repeat" with period 8: C_{n+8} consists of 16 x 16 matrices whose entries lie in C_n! So, you can remember all the Clifford algebras with the help of this eight-hour clock: 0 R 7 1 R+R C 6 R H 2 C H+H 5 3 H 4 To use this clock, you have to remember to use matrices of the right size to get C_n to have dimension 2^n. So, when I write "R + R" next to the "7" on the clock, I don't mean C_7 is really R + R. To get C_7, you have to take R + R and beef it up until it becomes an algebra of dimension 2^7 = 128. You do this by taking R(8) + R(8), since this has dimension 8 x 8 + 8 x 8 = 128. Similarly, to get C_{10}, you note that 10 is 2 modulo 8, so you look at "2" on the clock and see "H" next to it, meaning the quaternions. But to get C_{10}, you have to take H and beef it up until it becomes an algebra of dimension 2^{10} = 1024. You do this by taking H(16), since this has dimension 4 x 16 x 16 = 1024. This "beefing up" process is actually quite interesting. For any associative algebra A, the algebra A(n) consisting of n x n matrices with entries in A is a lot like A itself. The reason is that they have equivalent categories of representations! To see what I mean by this, remember that a "representation" of an algebra is a way for its elements to act as linear transformations of some vector space. For example, R(n) acts as linear transformations of R^n by matrix multiplication, so we say R(n) has a representation on R^n. More generally, for any algebra A, the algebra A(n) has a representation on A^n. More generally still, if we have any representation of A on a vector space V, we get a representation of A(n) on V^n. It's less obvious, but true, that *every* representation of A(n) comes from a representation of A this way. In short, just as n x n matrices with entries in A form an algebra A(n) that's a beefed-up version of A itself, every representation of A(n) is a beefed-up version of some representation of A. Even better, the same sort of thing is true for maps between representations of A(n). This is what we mean by saying that A(n) and A have equivalent categories of representations. If you just look at the categories of representations of these two algebras as abstract categories, there's no way to tell them apart! We say two algebras are "Morita equivalent" when this happens. It's fun to study Morita equivalence classes of algebras - say algebras over the real numbers, for example. The tensor product of algebras gives us a way to multiply these classes. If we just consider the invertible classes, we get a *group*. This is called the "Brauer group" of the real numbers. The Brauer group of the real numbers is just Z/2, consisting of the classes [R] and [H]. These correspond to the top and bottom of the Clifford clock! Part of the reason is that H tensor H = R(4) so when we take Morita equivalence classes we get [H] x [H] = [R] But, you may wonder where the complex numbers went! Alas, the Morita equivalence class [C] isn't invertible, so it doesn't live in the Brauer group. In fact, we have this little multiplication table for tensor prod algebras: tensor R C H ---------------------- R | R C H | C | C C+C C(2) | H | H C(2) R(4) Anyone with an algebraic bone in their body should spend an afternoon figuring out how this works! But I won't explain it now. Instead, I'll just note that the complex numbers are very aggressive and infectious - tensor anything with a C in it and you get more C's. That's because they're a field in their own right - and that's why they don't live in the Brauer group of the real numbers. They do, however, live in the *super-Brauer* group of the real numbers, which is Z/8 - the Clifford clock itself! But before I explain that, I want to show you what the categories of representations of the Clifford algebras look like: 0 real vector spaces 7 1 split real vector spaces complex vector spaces 6 real vector spaces quaternionic vector spaces 2 complex vector spaces split quaternionic vector spaces 5 3 quaternionic vector spaces 4 You can read this information off the 8-hour Clifford clock I showed you before, at least if you know some stuff: A real vector space is just something like R^n A complex vector space is just something like C^n A quaternionic vector space is just something like H^n and a "split" vector space is a vector space that's been written as the direct sum of two subspaces. Take C_4, for example - the Clifford algebra generated by 4 anticommuting square roots of -1. The Clifford clock tells us this is H + H. And if you think about it, a representation of this is just a pair of representations of H. So, it's two quaternionic vector spaces - or if you prefer, a "split" quaternionic vector space. Or take C_7. The Clifford clock says this is R + R... or at least Morita equivalent to R + R: it's actually R(8) + R(8), but that's just a beefed-up version of R + R, with an equivalent category of representations. So, the category of representations of C_7 is *equivalent* to the category of split real vector spaces. And so on. Note that when we loop all the way around the clock, our Clifford algebra becomes 16 x 16 matrices of what it was before, but this is Morita equivalent to what it was. So, we have a truly period-8 clock of categories! But here's the really cool part: there are also arrows going clockwise and counterclockwise around this clock! Arrows between categories are called "functors". Each Clifford algebra is contained in the next one, since they're built by throwing in more and more square roots of -1. So, if we have a representation of C_n, it gives us a representation of C_{n-1}. Ditto for maps between representations. So, we get a functor from the category of representations of C_n to the category of representations of C_{n-1}. This is called a "forgetful functor", since it "forgets" that we have representations of C_n and just thinks of them as representations of C_{n-1}. So, we have forgetful functors cycling around counterclockwise! Even better, all these forgetful functors have "left adjoints" going back the other way. I talked about left adjoints in "week77", so I won't say much about them now. I'll just give an example. Here's a forgetful functor: forget complex structure complex vector spaces ---------------------------> real vector spaces which is one of the counterclockwise arrows on the Clifford clock. This functor takes a complex vector space and forgets your ability to multiply vectors by i, thus getting a real vector space. When you do this to C^n, you get R^{2n}. This functor has a left adjoint: complexify complex vector spaces <-------------------------- real vector spaces where you take a real vector space and "complexify" it by tensoring it with the complex numbers. When you do this to R^n, you get C^n. So, we get a beautiful version of the Clifford clock with forgetful functors cycling around counterclockwise and their left adjoints cycling around clockwise! When I realized this, I drew a big picture of it in my math notebook - I always carry around a notebook for precisely this sort of thing. Unfortunately, it's a bit hard to draw this chart in ASCII, so I won't include it here. Instead, I'll draw something easier. For this, note the following mystical fact. The Clifford clock is symmetrical under reflection around the 3-o'clock/7-o'clock axis: 0 real vector spaces 7 1 split real vector spaces complex vector spaces \ \ \ \ 6 real vector spaces \ quaternionic vector spaces 2 \ \ \ \ complex vector spaces split quaternionic vector spaces 5 3 quaternionic vector spaces 4 It seems bizarre at first that it's symmetrical along *this* axis instead of the more obvious 0-o'clock/4-o'clock axis. But there's a good reason, which I already mentioned: the Clifford algebra C_n is related to rotations in n+1 dimensions. I would be very happy if you had enough patience to listen to a full explanation of this fact, along with everything else I want to say. But I bet you don't... so I'll hasten on to the really cool stuff. First of all, using this symmetry we can fold the Clifford clock in half... and the forgetful functors on one side perfectly match their left adjoints on the other side! So, we can save space by drawing this "folded" Clifford clock: split real vector spaces | ^ forget splitting | | double v | real vector spaces | ^ complexify | | forget complex structure v | complex vector spaces | ^ quaternionify | | forget quaternionic structure v | quaternionic vector spaces | ^ double | | forget splitting v | split quaternionic vector spaces The forgetful functors march downwards on the right, and their left adjoints march back up on the left! The arrows going between 7 o'clock and 0 o'clock look a bit weird: split real vector spaces | ^ forget splitting | | double V | real vector spaces Why is "forget splitting" on the left, where the left adjoints belong, when it's obviously an example of a forgetful functor? One answer is that this is just how it works. Another answer is that it happens when we wrap all the way around the clock - it's like how going from midnight to 1 am counts as going forwards in time even though the number is getting smaller. A third answer is that the whole situation is so symmetrical that the functors I've been calling "left adjoints" are also "right adjoints" of their partners! So, we can change our mind about which one is "forgetful", without getting in trouble. But enough of that: I really want to explain how this stuff is related to the super-Brauer group, and then tie it all in to the *topology* of Bott periodicity. We'll see how far I get before giving up in exhaustion.... What's a super-Brauer group? It's just like a Brauer group, but where we use superalgebras instead of algebras! A "superalgebra" is just physics jargon for a Z/2-graded algebra - that is, an algebra A that's a direct sum of an "even" or "bosonic" part A_0 and an "odd" or "fermionic" part A_1: A = A_0 + A_1 such that multiplying a guy in A_i and a guy in A_j gives a guy in A_{i+j}, where we add the subscripts mod 2. The tensor product of superalgebras is defined differently than for algebras. If A and B are ordinary algebras, when we form their tensor product, we decree that everybody in A commutes with everyone in B. For superalgebras we decree that everybody in A "supercommutes" with everyone in B - meaning that ab = ba if either a or b are even (bosonic) while ab = -ba if a and b are both odd (fermionic). Apart from these modifications, the super-Brauer group works almost like the Brauer group. We start with superalgebras over our favorite field - here let's use the real numbers. We say two superalgebras are "Morita equivalent" if they have equivalent categories of representations. We can multiply these Morita equivalence classes by taking tensor products, and if we just keep the invertible classes we get a group: the super-Brauer group. As I've hinted already, the super-Brauer group of the real numbers is Z/8 - just the Clifford algebra clock in disguise! Here's why: The Clifford algebras all become superalgebras if we decree that all the square roots of -1 that we throw in are "odd" elements. And if we do this, we get something great: C_n tensor C_m = C_{n + m} The point is that all the square roots of -1 we threw in to get C_n *anticommute* with those we threw in to get C_m. Taking Morita equivalence classes, this mean [C_n] [C_m] = [C_{n+m}] but we already know that [C_{n+8}] = [C_n] so we get the group Z/8. It's not obvious that this is *all* the super-Brauer group, but it actually is - that's the hard part. Now let's think about what we've got. We've got the super-Brauer group, Z/8, which looks like an 8-hour clock. But before that, we had the categories of representations of Clifford algebras, which formed an 8-hour clock with functors cycling around in both directions. In fact these are two sides of the same coin - or clock, actually. The super-Brauer group consists of Morita equivalence classes of Clifford algebras, where Morita equivalence means "having equivalent categories of representations". But, our previous clock just shows their categories of representations! This suggests that the functors cycling around in both directions are secretly an aspect of the super-Brauer group. And indeed they are! The functors going clockwise are just "tensoring with C_1", since you can tensor a representation of C_n with C_1 and get a representation of C_{n+1}. And the functors going counterclockwise are "tensoring with C_{-1}"... or C_7 if you insist, since C_{-1} doesn't strictly make sense, but 7 equals -1 mod 8, so it does the same job. Hmm, I think I'm tired out. I didn't even get to the topology yet! Maybe that'll be good as a separate little story someday. If you can't wait, just read this: 4) John Milnor, Morse Theory, Princeton U. Press, Princeton, New Jersey, 1963. You'll see here that a representation of C_n is just the same as a vector space with n different anticommuting ways to "rotate vector by 90 degrees", and that this is the same as a real inner product space equipped with a map from the n-sphere into its rotation group, with the property that the north pole of the n-sphere gets mapped to the identity, and each great circle through the north pole gives some action of the circle as rotations. Using this, and stuff about Clifford algebras, and some Morse theory, Milnor gives a beautiful proof that Omega^8(SO(infinity)) ~ SO(infinity) or in English: the 8-fold loop space of the infinite-dimensional rotation group is homotopy equivalent to the infinite-dimensional rotation group! The thing I really like, though, is that Milnor relates the forgetful functors I was talking about to the process of "looping" the rotation group. That's what these maps from spheres into the rotation group are all about... but I want to really explain it all someday! I learned about the super-Brauer group here: 5) V. S. Varadarajan, Supersymmetry for Mathematicians: An Introduction, American Mathematical Society, Providence, Rhode Island, 2004. though the material here on this topic is actually a summary of some lectures by Deligne in another book I own: 6) P. Deligne, P. Etingof, D.S. Freed, L. Jeffrey, D. Kazhdan, J. Morgan, D.R. Morrison and E. Witten, Quantum Fields and Strings: A Course For Mathematicians 2 vols., American Mathematical Society, Providence, 1999. Notes also available at http://www.math.ias.edu/QFT/ Varadarajan's book doesn't go as far, but it's much easier to read, so I recommend it as a way to get started on "super" stuff. ----------------------------------------------------------------------- Previous issues of "This Week's Finds" and other expository articles on mathematics and physics, as well as some of my research papers, can be obtained at http://math.ucr.edu/home/baez/ For a table of contents of all the issues of This Week's Finds, try http://math.ucr.edu/home/baez/twf.html A simple jumping-off point to the old issues is available at http://math.ucr.edu/home/baez/twfshort.html If you just want the latest issue, go to http://math.ucr.edu/home/baez/this.week.html 12-Mar-2005 15:39:41 -0400,2197;000000000000-00000000

1 0

LICS 2005: Call for Short Presentations
by Alex Simpson 09 Mar '05

09 Mar '05

Twentieth Annual IEEE Symposium on LOGIC IN COMPUTER SCIENCE (LICS 2005) June 26th-29th, 2005, Chicago, Illinois http://www.lfcs.informatics.ed.ac.uk/lics/ CALL FOR SHORT PRESENTATIONS The LICS Symposium is an annual international forum on theoretical and practical topics in computer science that relate to logic broadly construed. LICS 2005 will have a session of short (5-10 minutes) presentations. This session is intended for descriptions of work in progress, student projects, and relevant research being published elsewhere; other brief communications may be acceptable. Submissions for these presentations, in the form of short abstracts (1 or 2 pages long), should be entered at the LICS 2005 submission site between 19th March and 25th March 2005. Authors will be notified of acceptance or rejection by 1st April 2005. 11-Mar-2005 13:01:40 -0400,1466;000000000000-00000000

1 0

lax transformations of 2-functors
by Marco Grandis 04 Mar '05

04 Mar '05

Dear categorists, Is there a good terminology for "relaxed transformations" between 2-functors and the "relaxed adjunctions" where they appear as unit/counit? Generally, I find the Kelly-Street terminology (LNM 420, 1974) for 2-dimensional category theory very convenient: clear, elegant and as simple as possible. However, I have problems in the cases recalled above. 1. Let us agree, with Kelly-Street, that a LAX functor F (between 2-categories, to simplify things) has comparison cells F(g).F(f) --> F(gf), while an OP-LAX one has comparison cells the other way round. (It is quite reasonable to take the first notion as the leading one, since it is related with LIMITS and MONADS, while the opposite is related with COLIMITS and COMONADS). 2. Now, let us say for the moment that an "XXX-transformation" phi: F --> G has comparison cells (corresponding to maps a: A --> B in the domain) phi(a): phi(B).Fa --> Ga.phi(A), while an "op-XXX-transformation" has reversed comparison cells. Let us also speak of an "XXX-adjunction" (between strict 2-functors, to simplify things) to mean that its unit and counit are XXX-transformations; similarly for op-XXX-adjunctions (examples below, point 4). Such notions (and precise definitions) were introduced in the 70's. An XXX-transformation is called: - a "quasi-natural transformation" in Bunge LNM 195 (1971) and Trans. AMS (1974); - a "quasi_d natural transformation" in Gray LNM 391 (1974) ("d" for down); - an "op-lax natural transformation" in Kelly, On clubs and doctrines, LNM 420 (1974). An XXX-adjunction is called a "formal lax adjunction" in Bunge, Trans. AMS. An op-XXX-adjunction is called a "weak quasi-adjunction" in Gray. 3. Here, I find the term "lax" or "op-lax" misleading, since LAX functors can have both XXX- and op-XXX-transformations. Moreover, "lax adjunction" would seem to point to the functors rather than to unit & counit. 4. A few simple examples of XXX- and op-XXX-adjunctions can be of help in clarifying things. Take the strict 2-functors p: RelAb --> 1, i: 1 --> RelAb, sending the one object to the null group 0. We have: (a) an XXX-adjunction p -| i, with XXX unit 1 --> ip, sending an object A to the greatest relation A --> 0 (and trivial counit pi = 1); (b) an op-XXX-adjunction p -| i, with op-XXX unit 1 --> ip, sending an object A to the least relation A --> 0; (c) an XXX-adjunction i -| p, with XXX counit ip --> 1, sending an object A to the least relation 0 --> A; (d) an op-XXX-adjunction i -| p, with XXX unit ip --> 1, sending an object A to the greatest relation 0 --> A. These examples also show (perhaps) some motivation for taking the XXX notion as the leading one: - (a) shows the null group as an XXX-terminal object via the TERMINAL relation to it, - (c) shows the null group as an XXX-initial object via the INITIAL relation from it. 5. Now we are left with finding a good term for "XXX". (a) I would avoid "lax", as already motivated. (b) "weak" should probably be avoided as well, as is often used in the same sense of "pseudo", i.e. with reference to invertible comparisons; moreover, "weak terminal" means a different thing in 1-category theory. (c) "quasi" might be acceptable? It would give "quasi transformation" (or quasi natural transformation") , "op-quasi transformation", "quasi adjunction", "op-quasi adjunction", "quasi terminal",... _________ I would appreciate comments, criticism and suggestions. Best regards to all Marco Grandis Dipartimento di Matematica Universita` di Genova via Dodecaneso 35 16146 GENOVA, Italy e-mail: grandis(a)dima.unige.it tel: +39.010.353 6805 fax: +39.010.353 6752 http://www.dima.unige.it/~grandis/

1 0

TLCA 2005 Call for Participation
by Hasegawa Masahito 03 Mar '05

03 Mar '05

======================================================================= TLCA 2005 Seventh International Conference on Typed Lambda Calculi and Applications 21-23 April 2005, Nara, Japan http://www.kurims.kyoto-u.ac.jp/rdp05/tlca/ CALL FOR PARTICIPATION ** Early Registration Deadline: 31 March 2005 ** ======================================================================= The TLCA series of conferences serves as a forum for presenting original research results that are broadly relevant to the theory and applications of typed lambda calculi and related systems. This 7th TLCA Conference will consist of 3 invited talks and 27 refereed talks (see the programme below). TLCA'05 will be held as part of the Federated Conference on Rewriting, Deduction and Programming (RDP'05), jointly with the 16th International Conference on Rewriting Techniques and Applications (RTA'05) and several workshops. Now the registration and hotel booking procedures for RDP'05 are open; please follow the link to the registration page from the RDP'05 top page http://www.kurims.kyoto-u.ac.jp/rdp05/ to complete your registration. There also are links to web pages providing some travel and local information. Please remember that the number of hotel rooms is limited. Requests will be processed on a first come first served basis and will be subject to availability. RDP'05 will take place at the Nara-Ken New Public Hall which is located in the centre of the beautiful Nara National Park, within 20 minutes walk from the Kintestu Nara Station. CONTACT Enquiries regarding the registration and hotel booking should be sent to the RDP'05 organizers <rdp05(a)m.aist.go.jp>. Enquiries regarding the TLCA conference should be sent to the TLCA'05 organizers <tlca05org(a)kurims.kyoto-u.ac.jp>. FURTHER INFORMATION RDP'05 website: http://www.kurims.kyoto-u.ac.jp/rdp05/ TLCA'05 website: http://www.kurims.kyoto-u.ac.jp/rdp05/tlca/ ======================================================================= PROGRAMME of TLCA 2005 Thursday, 21st April 08:30-09:00 Registration 09:00-10:00 Amy Felty (invited speaker, joint with RTA) A Tutorial Example of the Semantic Approach to Foundational Proof-Carrying Code 10:00-10:30 Tea Break 10:30-11:00 Olivier Hermant Semantic Cut Elimination in the Intuitionistic Sequent Calculus 11:00-11:30 Rene David and Karim Nour Arithmetical Proofs of Strong Normalization Results for the Symmetric Lambda-mu-calculus 11:30-12:00 Francois Lamarche and Lutz Strassburger Naming Proofs in Classical Propositional Logic 12:00-12:30 Francois-Regis Sinot Call-by-Name and Call-by-Value as Token-Passing Interaction Nets 12:30-14:00 Lunch 14:00-14:30 Andreas Abel and Thierry Coquand Untyped Algorithmic Equality for Martin-Lof's Logical Framework with Surjective Pairs 14:30-15:00 Hugo Herbelin On the Degeneracy of Sigma-types in Presence of Computational Classical Logic 15:00-15:30 Ken-etsu Fujita Galois Embedding from Polymorphic Types into Existential Types 15:30-17:00 Social Event (Guided City Walk) 17:30-22:30 Drink, Entertainments, Conference Dinner Friday, 22nd April 09:00-10:00 Susumu Hayashi (invited speaker) Can Proofs be Animated by Games? 10:00-10:30 Tea Break 10:30-11:00 Carsten Schurmann, Adam Poswolsky, Jeffrey Sarnat The $\nabla$-Calculus. Functional Programming with Higher-order Encodings 11:00-11:30 Christian Urban and James Cheney Avoiding Equivariance in Alpha-Prolog 11:30-12:00 Peter Selinger and Benoit Valiron A Lambda-calculus for Quantum Computation with Classical Control 12:00-12:30 Greg Morrisett, Amal Ahmed, Matthew Fluet L^3: A Linear Language with Locations 12:30-14:00 Lunch 14:00-14:30 John Power and Miki Tanaka Binding Signatures for Generic Contexts 14:30-15:00 Sam Lindley and Ian Stark Reducibility and TT-lifting for Computation Types 15:00-15:30 Nick Benton and Benjamin Leperchey Relational Reasoning in a Nominal Semantics for Storage 15:30-16:00 Coffee Break 16:00-16:30 Paolo Coppola, Ugo Dal Lago and Simona Ronchi Della Rocca Elementary Linear Logics and the Call-by-value Lambda Calculus 16:30-17:00 Patrick Baillot and Kazushige Terui A Feasible Algorithm for Typing in Elementary Affine Logic 17:00-17:30 Ferruccio Damiani Rank-2 Intersection and Polymorphic Recursion 17:30-18:30 Business Meeting Saturday, 23rd April 09:00-10:00 Thierry Coquand (invited speaker) Completeness Theorems and $\lambda$-calculus 10:00-10:30 Tea Break 10:30-11:00 Yves Bertot Filters on Co-Inductive Streams: An Application to Eratosthenes' Sieve 11:00-11:30 Virgile Prevosto and Sylvain Boulme Proof Contexts with Late Binding 11:30-12:00 Stan Matwin, Amy Felty, Istvan Hernadvolgyi, and Venanzio Capretta Privacy in Data Mining Using Formal Methods 12:00-12:30 Damiano Zanardini Higher-Order Abstract Non-Interference 12:30-14:00 Lunch 14:00-14:30 Klaus Aehlig, Jolie G de Miranda, Luke Ong The Monadic Second Order Theory of Trees Given by Arbitrary Level Two Recursion Schemes Is Decidable 14:30-15:00 Paula Severi and Fer-Jan de Vries Continuity and Discontinuity in Lambda Calculus 15:00-15:30 Jim Laird The Elimination of Nesting in SPCF 15:30-16:00 Coffee Break 16:00-16:30 Ana Bove and Venanzio Capretta Recursive Functions with Higher Order Domains 16:30-17:00 Gilles Barthe, Benjamin Gregoire, Fernando Pastawski Practical Inference for Typed-based Termination in a Polymorphic Setting 17:00-17:30 Roberto Di Cosmo, Francois Pottier, Didier Remy Subtyping Recursive Types Modulo Associative Commutative Products =======================================================================

1 0