April 2004 - Categories - categories.org.au

Extensions of Z+Z by Z
by Colin McLarty 01 May '04

01 May '04

After calculating the group extensions of Z+Z by Z, with constant action, I am curious whether the groups have any more natural form than I found. I mean extension of Z+Z by Z in this sense, as a sequence of groups where E need not be commutative: 0 --> Z --> E --> Z+Z --> 0 and the kernel is in the center of E. The form I found is parametrized by the integers this way: For any integer c, the group E_c has triples of integers (i,,j,k) as elements and the multiplication rule is coordinate-wise addition plus an extra bit in the first coordinate. (i,,j,k).(q,r,s) = ( (i+j+c.(kr)), j+r, k+s) When c=0 this is commutative and is just the coproduct Z+Z+Z. In any group E_c, the element (c,0,0) is the commutator of (0,0,1) and (0,1,0). The Baer sum of extensions corresponds to addition of the parameters c as integers. So I understand the group of extensions. Of course I understood it before I calculated it, since it is the second cohomology group of the torus. That is why I tried the algebraic calculation. But is there a natural way to think about each group E_c, for non-zero values of c? Do these groups appear in any other natural way? thanks, colin

3 2

A situation in search of terminology
by Vaughan Pratt 30 Apr '04

30 Apr '04

I'm looking for language advice on dealing with the following "St. Ives" problem, as a 2-categorical down-sizing of the 4-categorical original. I have a 2-category CAT^{\pm} (arising from a 2-monad C\pm1 analogous to the monad X+1) that is disconnected in the sense that it is representable as a sum of connected 2-categories. Each summand has homcats that are similarly disconnected, being representable as a sum of connected homcats. If I take a summand 2-category, and from each of its homcats coherently take a summand 1-category, I end up with a 2-category with an initial and a final category serving as respectively the syntax and the semantics of a certain 2-theory (of linearly distributive but not self-dual categories of dually typed objects, but that's another story I'm hoping Myles Tierney will like better than the Chu story). I don't think it's caused by my doing anything wrong--the situation appears to have arisen naturally and I've found no way of making it go away. Has this situation arisen before? If so, what is the proposed terminology for this kind of finality and its associated uniqueness? If not, I'm happy to make up my own conventions, but I don't want to reinvent the wheel here. Vaughan Pratt

1 0

Re: Modeling infinitesimals with 2x2 matrices
by Vaughan Pratt 29 Apr '04

29 Apr '04

From: Steve Vickers <s.j.vickers(a)cs.bham.ac.uk> >I thought that was the whole reason for contemplating infinitesimals in >the first place - 0/0 cannot be meaningful, but d/d is 1, ed/d is e etc. Well, you're not alone in thinking that way. This was the basis for Robinson's invention of nonstandard analysis: the belief that a/b has to be defined for all nonzero b in order to make infinitesimals nonparadoxical. Instead of formulating division a/b as an operation, go back to its motivating formulation as a system in search of a solution, in this case the system consisting of the one linear equation a = bx in one unknown. Had the system been one of ordinary or partial differential equations, there would be no argument that the solution space could turn out quite oddly shaped. Now when a and b are reals the solution space is a rectangle: only the column indexed by b=0 is undefined. This remains true when a and b are extended to the complex numbers, or even to the quaternions. But if you extend the domain to the algebra R(2) of 2x2 real matrices, the columns indexed by singular matrices now lose some of their entries. But not all, and so the solution space ceases to be rectangular. Robinson believed that the way to make infinitesimals safe for analysis was to make the solution space for a = bx rectangular. Today's logicians are magicians with logic: if logic indicates the impossibility of a rectangular solution space, no need to abandon that goal, just bend logic until the solution space does become rectangular. The students will bend with you, at least those who've approached nonstandard analysis with the proper upbeat spirit about how much simpler analysis becomes when infinitesimals can be objectified. Power tools are wonderful. To answer your question (or comment), in the system of refined numbers I described, if b is infinitesimal and nonzero, a = bx is solvable if and only if a is infinitesimal. The division table is no longer rectangular. So what? One might grumble that a = bx can't have an infinitesimal part when a and b are both infinitesimals, but in the simple cases that's a plus. In more complicated cases, 2x2 matrices aren't enough, you need nxn matrices, with distance of nonzero entries from the diagonal measuring the degree of their infinitesimality (if that's a word). In this case d^n = 0 only for higher n's. After thinking along those lines for a bit more the other day, I decided that even though I liked this approach better than throwing ultrafilters at it, it still wasn't as good as doing analysis in Boole's finite difference calculus with h remaining unbound throughout, the approach I'd used since the early 1970's. That approach has the great advantage of being able to use the same analysis in classical and quantum physics by setting h=0 to interpret a result classically and setting it to Planck's constant to interpret the same result quantumly. As a case in point, the same integration formulas can deliver areas under smooth curves and discrete summations of e.g. n^3, the latter with h=1. (I already wrote a bit about that two or three messages ago.) The right power tools are even more wonderful. Vaughan Pratt

2 2

Re: Extensions of Z+Z
by John Baez 29 Apr '04

29 Apr '04

Ronnie Brown writes: > Colin McLarty wrote: > > After calculating the group extensions of Z+Z by Z, with constant action, > > I am curious whether the groups have any more natural form than I found. > > I mean extension of Z+Z by Z in this sense, as a sequence of groups where > > E need not be commutative: > > > > 0 --> Z --> E --> Z+Z --> 0 > > > > and the kernel is in the center of E. > > > > The form I found is parametrized by the integers this way: For any > > integer c, the group E_c has triples of integers (i,j,k) as elements and > > the multiplication rule is coordinate-wise addition plus an extra bit > > in the first coordinate. > Try the Heisenberg group of upper triangular matrices with 1's on the > diagonal and the integers i,j,k in the upper non diagonal entries. > > 1 k i > 0 1 j > 0 0 1 > > This should give the case c=1 [...] The name "Heisenberg" hints that anyone with a physics bone in their body can't resist thinking about this sort of extension in terms of quantum mechanics. In this context, the constant that parametrizes the central extension, which Colin and Ronnie are calling "c", is called "Planck's constant", or "hbar" for short. The original Heisenberg groups were the central extensions of R^2 by U(1) (the unit complex numbers). To get these, we represent any element (a,b) in R^2 as a unitary operator on L^2(R): U(a,b) = exp(iaq + ibp) where q and p are the self-adjoint "position" and "momentum" operators on L^2(R): q = multiplication by x p = -i hbar d/dx These unitary operators U(a,b) fail to commute because [p,q] = - i hbar so the group they generate is not R^2, except in the "classical" case where hbar = 0. Instead, they generate a group of operators that is a central extension of R^2 by U(1). We get all the central extensions of R^2 by U(1) this way. Central extensions of R^2 by R work similarly; you get one for each real number hbar. Apparently central extensions of Z^2 by Z also work similarly! Best, jb

1 0

CoLoPS04: Call for Papers
by Frank D. Valencia 29 Apr '04

29 Apr '04

[[ -- Apologies for multiple copies of this message -- ]] =================================================================== CoLoPS 2004 International Workshop on COnstraint & LOgic Programming in Security December 5-11th, 2004 - Saint-Malo, France Satellite Workshop to ICLP 2004 ==================================================================== Scope of the workshop: Due to its practical relevance and complexity, the study of security has become a serious challenge involving several disciplines of computer science. A noteworthy aspect is that in several instances this study has used directly or indirectly tools and techniques from (Concurrent) Constraint Programming and (Linear) Logic Programming. For example, constraint solving has successfully been used for verifying security protocols, and several process algebras for modelling cryptographic protocols (e.g., recent variants of the spi calculus, SPL) have remarkable similarities with Concurrent Constraint Programming. Also (Linear) Logic Programming has been used as a framework for security protocols, and one of its central notions, unification, has been used for the symbolic execution of cryptographic calculi. CoLoPS aims at getting a broader perspective on the role of Constraint and Logic Programming in the study of security. Topics of interest include (but are not restricted to) frameworks for security using algorithms, verification techniques, process algebras or programming languages, with a Constraint or Logic Programming flavor. Submission and publication: Paper submissions should not exceed 15 pages. Submissions should be sent as a PDF or Postscript le via email to Frank D. Valencia (frankv(a)it.uu.se) The email should have: 1. "COLOPS Submission" as subject, 2. submission title and authors' relevant information as body, and 3. submission le as an attachment. The accepted papers will be included in the workshop proceedings as a research report of Uppsala University. Accepted papers will be published in an ENTCS (Electronic Notes in Theoretical Computer Science) volume dedicated to ICLP 2004 workshops. Papers describing ongoing work or already published are also welcome but will not be part of the proceedings. Please mark your paper accordingly. Program Committee: Elvira Albert (UC Madrid, Spain) Maria Alpulente (UP Valencia, Spain) Stefano Bistarelli (ITT-CNR, Italy) Martin Leucker (TU Munich, Germany) Sebastian Moedersheim (ETH Zurich, Switzerland) Ugo Montanari (Universita di Pisa, Italy) Catuscia Palamidessi (INRIA, France) Justin Pearson (Uppsala University, Sweden) Fred Spiessens (Universit e catholique de Louvain, Belgium) Frank D. Valencia (Uppsala University, Sweden) Pascal Van Hentenryck (Brown University, USA) Vijay Saraswat (IBM, USA) Bjorn Victor (Uppsala University, Sweden) Alicia Villanueva (UP Valencia, Spain) Organizing Committee: Martin Leucker (TU Munich, Germany), Justin Pearson (Uppsala University, Sweden), Fred Spiessens (Universit e catholique de Louvain, Belgium), Frank D. Valencia (Uppsala University, Sweden) Important dates: Submission deadline: June 27, 2004 Notification of acceptance: July 18, 2004 Final version: August 15, 2004 Workshop: September 5th or 11th, 2004 (Dependent on ICLP organizers) For more and up-to-date information see the www page http://www.info.ucl.ac.be/people/fsp/colops2004/

1 0

AMAST 04: Call for Participation
by Carron Shankland 29 Apr '04

29 Apr '04

******** AMAST 2004 ******** ** Call for participation ** **************************** 10th International Conference on Algebraic Methodology and Software Technology July 12th - 16th 2004 Stirling, Scotland, UK http://www.cs.stir.ac.uk/events/amast2004/ ********************************************************************* 20 EPSRC supported places for UK based students first come, first served - apply now and avoid disappointment! ********************************************************************* Keynote Speakers: * Roland Backhouse (Nottingham) * Don Batory (Texas) * Michel Bidoit (CNRS) * Muffy Calder (Glasgow) * Bart Jacobs (Nijmegen) * JJ Meyer (Utrecht) ********************************************************************* AMAST promotes research that may lead to the setting of software technology on a firm, mathematical basis. This goal is achieved by a large international cooperation with contributions from both academia and industry. AMAST 2004 will include keynote talks by leaders in the fields of software/system correctness, software development, including extensible and adaptive software, and evolutionary systems. The main programme consists of presentations of refereed technical papers on leading-edge research. AMAST 2004 is co-located with MPC 2004 (Mathematics of Program Construction) ARTS 2004 (AMAST Real Time Workshop). Participants for AMAST will be able to attend talks of both these events for free (and vice versa). AMAST 2004 is being held in Stirling, a historic city located in the heart of Scotland. The conference venue and accommodation are all based on the University campus, which is convenient for visiting the ancient castle and Wallace monument, or for going further afield and exploring the beautiful countryside. Social events include a civic reception, an afternoon excursion to Loch Lomond, and dinner in a quaint Scottish village. ********************************************************************** Book early for cheaper registration and guaranteed accommodation Deadline: 29th May 2004 http://www.cs.stir.ac.uk/events/amast2004/ ********************************************************************** -- The University of Stirling is a university established in Scotland by charter at Stirling, FK9 4LA. Privileged/Confidential Information may be contained in this message. If you are not the addressee indicated in this message (or responsible for delivery of the message to such person), you may not disclose, copy or deliver this message to anyone and any action taken or omitted to be taken in reliance on it, is prohibited and may be unlawful. In such case, you should destroy this message and kindly notify the sender by reply email. Please advise immediately if you or your employer do not consent to Internet email for messages of this kind.

1 0

The proposition O=H
by Vaughan Pratt 28 Apr '04

28 Apr '04

Anyone who's subscribed to this list long enough knows that I've been sufficiently bothered by the disjunction "Sets or categories" as to pester the list with my botherment periodically. I bothered the FOM mailing list with the same question for some years, with rather less civilized responses on occasion -- that was quite a wild list for a while, but Martin Davis seems to have done a good job of stabilizing it, too late unfortunately for those of us who found the repartee counterproductive and moved on before his administration. My pestering is not so much to make a nuisance of myself as to get a satisfactory answer. So far the answers, on either side, have struck me as entailing a certain acceptance of the local lore and wisdom bordering on religion. I would like to propose a middle ground on which set theorists and category theorists can meet amicably. The middle ground is expressed by the proposition O=H, that objects and homobjects are of the same type. One of "mathematics" or "short" is defined by the proposition that all short definitions have been made, all short questions asked already, and all short theorems either previously proved or now famous open problems. Before pursuing this line of thought any further I'd like to ask whether O=H is short in the above sense. Has it been brought up before, and if so what are the prevailing views on it? Vaughan Pratt

1 0

Getting rid of cardinality as an issue
by Vaughan Pratt 25 Apr '04

25 Apr '04

Encouraged by the lack of objections to my previous message about why Russell's Paradox should not be a big deal, I had a shot at shrinking the position I spelled out there down to one paragraph, as follows. ------------ We shall axiomatize certain 1-categories using 2-categories. We avoid Russell's paradox by treating any aggregation of $n$-categories as an $(n+1)$-category, and allowing for the possibility that the $(n+1)$-category $n$-$\CAT$ of all $n$-categories might be exponentially larger than any of its members. We impose no other size constraints besides the obvious one of keeping things small enough to remain consistent. Sets are defined as usual as 0-categories and categories as 1-categories. ------------ While I'm happy to field objections like "too flippant", I'm more concerned as to whether there are any technical flaws, and to a lesser extent philosophical or religious concerns. (I would not want to be held responsible for guns being brought to the next UACT meeting if ever there is one.) Makkai and Pare address the same issue in AMS CM 104 (Accessible Categories) with a hierarchy of Grothendieck universes (three, since they like me stop at 2-categories for the application at hand). Now the Grothendieck hierarchy is stepped through via ZF rather than Z, with Fraenkel's Replacement axiom doing the heavy hitting. This creates gaps mind-bogglingly larger than my teensy exponential gaps above. The general idea seems to be that these gaps ought to be large enough to take care of Russell while still not running headlong into inconsistency. However gaps this large do entail a certain amount of finger-crossing, and one might question the logic of hitting Russell with a nuclear weapon that might send some fallout your way when a harmless little tack-hammer will take him out. One objection I can readily imagine to the above is that I've conflated the n-category hierarchy with Russell's proposal for a ramified types hierarchy. I would disagree with that. All I have done is to insist on two things that seem to me to be independent. 1. I have proposed to call aggregations of n-categories (n+1)-categories. Now morphisms between n-categories are n-functors, and where there are n-functors there are n-natural transformations, so this is hardly a bold proposal. 2. *Some* gap is needed between n-CAT and (n+1)-CAT, starting with the requirement that Set be bigger than any set. Russell's paradox is no respecter of n, applying just as effectively to an (n+1)-category of n-categories as it does to a 1-category of sets. Certainly I have juxtaposed 1 and 2, but that is not the same thing as conflating them. Their mere juxtaposition provides sufficient armor against both Russell's paradox and the Icarus risk of flying too close to an inconsistently large cardinal. The "prior art" for dealing with these issues has given rise to the adjectives "small", "large," "superlarge", etc. and the nouns "set" and "class." A good test for any revolution is the amount of blood it needs to shed. The following definitions are aimed at minimal upheaval through maximum compatibility with the status quo. * An object is n-small when it belongs to an n-category. * Small = 1-small, large = 2-small, superlarge = 3-small, etc. * A set is a discrete 1-category. * A class is a discrete n-category for unspecified n. Hopefully Sol Feferman will give an even simpler solution in his talk tomorrow. Vaughan Pratt

6 5

Modeling infinitesimals with 2x2 matrices
by Vaughan Pratt 25 Apr '04

25 Apr '04

At some point I'll try to collect my thoughts on Sol Feferman's Thursday lecture on his alternative to Grothendieck universes, which he objected to as entailing an infinity of inaccessible cardinals. (What was Grothendieck's view of inaccessible cardinals vis a vis his universes?) During the lecture it struck me that his approach was quite like Robinson's approach to infinitesimals, in that it constructed lots of models of what was needed, took the common theory, then constructed a single model from the many, using techniques of Vaught and others to avoid losing too much of the common spirit of the many guided by the common theory (not sure if that captures the idea completely faithfully, but it's something like that). Thus distracted, I found myself wondering yet again why the d^2 = 0 property was so difficult for an infinitesimal d. Having been mulling over the quaternions lately, it seemed to me there was something of an analogy there, some property so built into our very psyche that we can't let go of it. Hamilton finally dropped commutativity, along with any reservations he might have harbored about vandalizing stone bridges in his own town. For the quaternions, d^2 = 0 implies d = 0, so this doesn't help. However the quaternions have a sibling algebra, just as noncommutative, and of exactly the same vector space dimension (in fact the only Clifford such, i.e. the only other real 4D vector space for which ij+ji=0 for all orthogonal vectors i,j having no real component), that is even better known than the quaternions (imagine that). Namely the Clifford algebra of 2x2 real matrices, as a 4D real vector space, made an algebra with matrix multiplication. Why not model d as the matrix 0 1 0 0? This is a perfectly good quantity, adding and scaling just like any real, e.g. 2d = 0 2 0 0. And obviously d^2 = 0. Standard reals x would have the form x 0 0 x 1+d would therefore be 1 1 0 1 (1+d)^2 then becomes 1 2 0 1 as common sense would indicate. The determinant of d being 0, one can't divide by it. But who in their right mind would want to divide by a quantity infinitesimally close to zero? Obviously that's going to produce an infinitely large quantity; if you want to do that, why not just go ahead and divide by zero itself? As Douglas Adams pointed out, you may think the store down the road is a fair way away, but other galaxies are even further away. To a nematode they're all far away. On the other hand 1 2 0 1 has a perfectly good reciprocal, namely 1 -2 0 1 again as suggested by common sense. So the proposal is to base calculus on a field-like object that is a field in the large, but zero divide errors set in when one gets infinitesimally close to zero. Basically what happens with IEEE floating point arithmetic, but modeled with 2x2 real matrices rather than 64-bit numbers. Oh, but what about the noncommutativity of 2x2 matrices, might that mess something up? Actually no, this two-dimensional algebra consisting of matrices of the form a b 0 a is commutative. So only the zero divisors really close to 0 constitute any departure at all from the field axioms. The diagonal element a is the standard real part and the off-diagonal element b in the upper right gives the infinitesimal displacement. So we have a real commutative associative algebra of refined numbers, having a real part and an infinitesimal part, whose only zero divisors are the infinitesimals. We don't *have* to think of them as matrices because we can just write its elements as x+yd by analogy with x+iy, where d is the above matrix representing the prototypical infinitesimal. The square of i is -1, and the square of d is 0. Moreover x and y in x+yd can be complex. We then have numbers x+iy+ud+ivd, which can parsed as either refined complex numbers, namely complex numbers with refined coefficients x+ud+i(y+vd), or complex refined numbers, namely refined numbers with complex coefficients x+iy+(u+iv)d. This is still a real associative algebra, which through force of habit people will no doubt want to call a complex commutative associative algebra, but it could just as legitimately be called a refined associative algebra. Ok, what about commutative? Well, the complex numbers are commutative and the refined numbers are commutative, so how could refining complex numbers make any difference? Well, the reason I wrote x+yd rather than x+dy is that, even though the *natural* thing to do is to make i commute with d, if instead we make id+di=0, the defining condition for Clifford algebras, then we can fit the whole thing into 2x2 *real* matrices! Here I'm using the following 2x2 real matrices for i and d respectively: (0 -1) (0 1) (1 0) (0 0) But now notice that the matrices for 1,i,d,id form a basis for all the 2x2 matrices. In fact *any* 2x2 matrix [[a,b],[c,d]] can be decomposed as (d -c) + (a-d b+c) (c d) ( 0 0 ) (I'd appreciate feedback from anyone for whom the above doesn't typeset readably.) So to read an arbitary 2x2 real matrix as a refined complex number, take the bottom row reversed as the complex part and the departure of the top row from the usual matrix representation of complex numbers as the infinitesimal part, taking care to get both signs right. How did I notice this? Simple. I knew (i) that id+di=0 would make it a Clifford algebra, (ii) there are only two 4D Clifford algebras, and (iii) d^2 = 0 -> d = 0 in the quaternions. This narrows things down to the 2x2 real matrices, there are no other associative algebras with these properties. Getting the above decomposition was then just a matter of solving some trivial linear equations. This is so simple, and the infinitesimals have been worried at for so long, that this *has* to be known already. But then it would really bug me to have been the last to learn about it -- why wasn't I told, as they say? Vaughan Pratt

2 2

MFPS Program Now Available - Deadline for Reduced Hotel Rates
by Michael Mislove 25 Apr '04

25 Apr '04

Dear Colleagues, With apologies for multiple copies, the program for MFPS 20 is available at http://www.math.tulane.edu/~mfps/mfps20prog.html It also can be accessed from the MFPS 20 home page http://www.math.tulane.edu/~mfps/mfps20.htm Registration for the meeting can be done online at http://www.math.tulane.edu/~mfps/regform20.html Those interested in attending the meeting should note that the conference hotel will hold a block of rooms at the conference rate ONLY UNTIL MAY 1. After that date, the conference rate will no longer be available. Best regards, Mike Mislove =============================================== Professor Michael Mislove Phone: +1 504 862-3441 Department of Mathematics FAX: +1 504 865-5063 Tulane University URL: http://www.math.tulane.edu/~mwm New Orleans, LA 70118 USA ===============================================

1 0