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(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(a)(b.c) one must first form b.(a@c) and (a(a)b).c using 1D
composition . before pasting them with 2D composition :, as in a(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(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.
