I'd written most of the following (including the references to Street's and Aitchison's papers) before getting Ross's reply. However I think most of what I have to say below remains relevant. His reply does however prompt me to formulate my question, hopefully more sharply, as "give an elementary description of tensor product of n-categories." Such a description should be inferrable from Ross's parity complexes paper, but thus far I don't have a clear picture of these products, and was hoping maybe someone else had a more elementary description. ===== I think Michael's first two comments can be answered with the remarks that I didn't specify a category, and that cartesian product XxY and intersection X&Y of sets X and Y are each categorical products, albeit not in the same category. Third, the analogy with the story breaks down. To be analogous, you should be looking at the tensor product of two stories to have 6 parts, not nine. You would have to identify <begin, end>, <middle, middle> and <end, begin> Let's call these BE, MM, EB, and call the stories a and b. BE denotes the situation where b has ended while a has yet to begin, while EB is this situation with a and b interchanged. MM is the situation in which both stories are ongoing. I don't see where the identification BE=MM=EE comes from or what it would be used for. The picture, with MM cast (admittedly oddly, but nevertheless the effect I'm after) as a 2-cell, is: b ----> BM BB-------->BE ! ! ! ! __ ! a! MB! //!MM !ME ! ! // ! V V V EB-------->EE EM What seems likelier is that the tensor product of two categories is a two dimensional category. Ah, good. This is exactly what happens at this point in the "obvious" scenario, in which MM is a square having MB and BM as "orthogonal sources" and ME and EM as "orthogonal targets". Here MM is "just a square", whereas the above picture makes MM a 2-cell from MB.EM to BM.ME. And this is the nub of my question. Two (and higher) dimensional categories emerge naturally at this point. The difficulty I have with them, and perhaps I should have spent more time on this point, is that n-dimensional categories have "too many" compositions. Yes, they have only n compositions, just like an n-category, but these compositions are indexed by axis rather than by dimension. (Since "dimension" is in some contexts used to mean "axis" I should emphasize that I am here using it in its basis-independent sense, as in "n-dimensional", referring to an attribute of space, as in area vs. volume, rather than a direction, as in north-south vs. east-west.) Thus in the story analogy, if story a is to be read concurrently with the consecutive readings of stories b and c, namely a@(b.c), then using 2-dimensional categories we have a$(b.c) = a$b{a}a$c. (I'll write a$b for this product to distinguish it from the more topological (homological) product a@b I'm asking about.) Here the composition {a} denotes composition of squares "orthogonal to" the a-axis. b c --------> ---------> ! ! ! these squares are composed ! ! ! via {a} (composition orthogonal a! a! a! to a) ! ! ! ! b ! b ! --------> ---------> But now if we have the consecutive readings of a and b concurrently with the reading of c, we have (a.b)$c = a$c{c}b$c. c --------> ! ! ! ! a! a! these squares are composed ! ! via {c} (composition orthogonal ! c ! to c) --------> ! ! ! ! b! b! ! ! ! c ! --------> Well, so n-dimensional categories have n compositions. But what's so bad about that? So do n-categories. Moreover the intuition behind n-dimensional compositions is quite a bit clearer, and their algebra more straightforward, than that of n-category composition. So why would anyone want to use these complicated n-category compositions for geometrical applications? (Luckily Bob Rosebrugh sent my message back to me to repair some carets and vertical bars that a mailer ate again, giving me a chance to try to express my intuition about this important issue a bit more clearly. The next paragraph hopefully does the trick.) What n-categories offer geometry is more versatility for the same number of compositions. Expressions built up with the n compositions of an n-dimensional category are translatable (albeit clumsily) into those of an n-category but not conversely. A basic example of the latter is that of horizontal composition in a two-category, for which two-dimensional categories offer no equivalent. For a very down-to-earth example, read stories a and b concurrently, then c and d concurrently. This is conveniently expressible in a 2-category as (a@b).(c@d), but ****************************************************** it has no equivalent 2-dimensional category expression. ****************************************************** A drawback (slight or serious depending on your point of view) is the clumsiness of the translation from n-dimensional category expressions to n-category expressions. In actually doing either of the above-illustrated pastings of squares, one must first extend the squares using horizontal (= 1D) composition so that they match up. Thus for a@(b.c) one must first form b.(a@c) and (a@b).c using 1D composition . before pasting them with 2D composition :, as in a@(b.c) = ((a@b).c):(b.(a@c)). b c -----------> ---------> ---------> ! ! ! b ! ! __ ! ! __ ! !a //! !a a! //! a! ! // ! ! // ! V c V V V ---------> ---------> -----------> b c For (a.b)@c we have the (easily visualized) transpose of this figure, (a.b)@c = (a.(b@c)):((a@c).b). Actually this clumsiness in translation resides in the result of distributing @ over ., not in the short and clear expression a@(b.c) itself. Distributivity in logic is the archenemy of efficiency in decision methods (the word problem for lattices is decidable but not for distributive lattices, etc. etc.). The present distributivity rule looks even worse than that for logic, but it could well turn out that from a computational complexity point of view, logical distributivity (of conjunction over disjunction) adds about the same to algorithmic complexity as the present one. This is a question for a complexity theorist rather than a basis for allegations of clumsiness. Note that both these pastings use the same composition, namely the vertical composition :, as their top-level operation. This has to be the case for the pasting of any two 2-cells sharing a nonzero length boundary. In this sense n-categories have fewer compositions than n-dimensional categories: only one operation for pasting n-cells along a nondegenerate (n-1)-cell instead of n. (This was the essence of my previous defence of 2-categories in geometry. Although I still see some merit to that defence, the above translatability issue yields what seems to me a more knock-down argument.) ============ The relevant background for much of this is contained in an eminently readable and very striking paper by Ross Street, entitled "The algebra of oriented simplexes", which appeared in the Journal of Pure and Applied Algebra for 1987 on pages 283-335. As the title suggests, the paper concentrates on simplexes (triangles, tetrahedra, ..., as opposed to cubes and other shapes), which paste together to form simplicial sets, namely objects of Delta"=>Set (writing " for op). A manuscript by Street's former postdoc Iain Aitchison treats "The Geometry of Oriented Cubes". Here simplexes are replaced by cubes, a good step towards understanding dimension-increasing product. This transition reflects a small movement in geometry within the last five years or so, led by Grothendieck, towards generalizing Delta"=>Set (the functor category of graded sets and boundary, coboundary, etc. morphisms) to Pos"=>Set, via the obvious embedding of the category Delta of finite chains into the category Pos of all posets, see also an older paper by Metropolis and Rota, "Combinatorial Structure of the Faces of the n-cube" in Siam J. Appl. Math. 35:4, 689-694 (1978). Just as the simplexes form the category Delta, so do the cubes constitute the finite objects of w=>Lambda (w=omega) where Lambda is the poset M Lambda = / \ / \ B E (with B,M,E denoting Beginning, Middle, End as before). (For purposes of comparison, writing 2 for that ordinal, the two-element chain, Delta can be taken to be the finite objects of w=>2 = the ordinal w+1, the chain of all order ideals of the chain w, the finite objects of which cutely reconstitute themselves as the ordinal w. I have also recently been looking at the closed category w=>3' , where 3' is the unique closed category whose underlying category is a chain of 3 objects and whose tensor is strict, idempotent, symmetric, but not cartesian, described along with its cartesian closed sibling 3 in more detail in CTCS-89 (Manchester), LNCS 389, p.33. Like w=>Lambda, w=>3' admits interpretation as a category of cubes, but spiced up with a closed monoidal structure that promises to be very useful, my apologies for not going into more detail here on this.) Here Delta shows up not so much as a subcategory of w=>Lambda but rather as tetrahedral corners of cubes; indeed an n-cube can be described as n! n-tetrahedra pasted together, one per 1-dimensional path from the beginning BB..BB to the end EE..EE of the n-cube. A significant advantage of Aitchison's paper is the considerable intuition it provides for Street's subsequent paper on "parity complexes," which is relatively bare of either intuition or examples. I'd like to think that parity complexes formed a yet larger fragment of Pos"=>Set, but I haven't yet seen how to match it up to that description. Instead it seems to be an ingenious, and quite possibly the definitive, combinatorial solution to the problem that Street had in 1976 introduced "computads" for, namely to give a graph-theoretic account of 2-category pasting given that the source or target of an 2-cell might be a composite of 1-cells, the forgetting of which renders the underlying graph of a 2-category not very useful. (A 1-category diagram in C is just a graph morphism into U(C), but try explaining diagrams of 2-cells in those terms.) Street defines the tensor product a@b of two parity complexes (two sets of cells) as their cartesian product. The key to making this product a sensible cell complex is the definition of the faces of this cartesian product; Street's definition mimics the usual boundary property of tensor products of cell complexes, see e.g. equation (9.2) of MacLane's "Homology." This seems exactly right. However I don't as yet have the slightest intuition as to what this very clean and nice definition of product translates into in terms of n-categories viewed as cell complexes, and Ross's paper doesn't offer much in the way of hints here. A hopefully less vague formulation of my question this is as follows. Give an elementary description of the product of n-categories. Here for example is one way one might try to do this for a@b. For each composite u.v of two m-cells in a and x:y of two n-cells in b (where . and : denote m- and n-dimensional composition in a and b respectively), form the following square, whose vertices are 0-cells, whose edges are (m+n-1)-cells, and whose ==>'s are (m+n)-cells. x y --------> ---------> ! ! ! ! __ ! __ ! u! //! u! //! u! ! // ! // ! V x V y V --------> ---------> ! ! ! ! __ ! __ ! v! //! v! //! v! ! // ! // ! V x V y V --------> ---------> Sum this over all such pairs (u.v,x:y), then make the "appropriate" identifications to arrive at a@b. (For example identify the common u@x square for all pairs of pairs (u.v,x:y) and (u.v',x:y').) But how are the edges of say the square u@x related to u and x? And what should be their composition as (m+n-1)-cells of a@b? Is there some way of completing this definition, or one at the same elementary level, that is equivalent to Ross's definition? The above-mentioned boundary equation (MacLane (9.2)) almost surely provides the key here, and perhaps I should be figuring this out for myself instead of bothering this list with questions arising out of only half-understood ideas. Such an elementary description of this tensor product would help the more visually oriented of us to see it. In particular those like myself working on models of concurrent computation might benefit from such notions, provided they are made sufficiently accessible. The analogy of stories being read concurrently should hint at this application. Vaughan Pratt PS. As a minor syntactic detail, I just noticed that the (purely arbitrary) convention I'm using for direction of n-cells for n>1 in these products is the opposite of the one Iain Aitchison uses. I should have checked before jumping to the conclusion that the permutation ab->ba was the natural order of things, rather than ba->ab. I haven't yet worked out which way round Ross does it in "Parity Complexes" because it is hard to keep reliable track of parity during the 15 pages of concepts leading up to his definition of product, and the paper doesn't contain an example of a product.
participants (1)
-
pratt@cs.stanford.edu