Thursday, February 16, 2006

My interest in monoidal bicategories

An old article first posted in 1997

My interest in monoidal bicategories.
RFC Walters 7th April 1997

1966-70 In my PhD thesis (ANU) about category theory and universal algebra I used the 2-category structure of Cat to define things and hence became interested in pasting cells.
1970 I visited Mac Lane (Chicago) as research associate and discovered that the category PA of presheaves on a small category is 'total' which lead to a collaboration with Ross Street beginning in 1970 of the 2-categorical properties of yoneda yA:A->PA. We were trying to characterize Sets in Cat but in analogy to studying 2 in Sets by looking at arrows A->PB (here PB means subsets of B) we studied functors A->PB.
1974 I spoke on his work at a conference at UNSW organized when Peter Freyd was here by Max Kelly. The paper appeared much later in "Yoneda structures". The beginning of the study of Mod and Rel was already there.
1980 I visited Milan and discovered that the sheaf condition can be expressed in terms of Cauchy completeness of categories enriched over a bicategory of 'relations' - this work appeared in Cahiers. A group of us studied categories enriched over bicategories, and bimodules between them. We looked at properties which lifted from the base bicategory to the bicategory of bimodules.
1982 Lifting the tensor product lead to my idea with Lawvere and Carboni that the classical treatment of this in terms of symmetry could be explained in terms of a tensored one-object bicategory and a Eckman-Hilton argument - I gave a lecture on this on 26th January 1983 which inspired Ross to discover braided monoidal categories with Joyal (whose motivation was different).
1983 I began the study with Carboni of Rel as a monoidal bicategory in Milan December 1983. It was completed in January 1985. Aurelio had previously done work in the direction of Freyd on relations regarding Rel as a category and using the mysterious 'modular law'.
1985 I believe I lectured on Rel at Sussex. The paper had been submitted some time before and Scedrov had written a report recommending rejection, but it was eventually accepted. A third strand was that Mike Johnson and I had begun work (ask Mike when he began as my student) on an alternative version of the n-category generated by an n-simplex - the higher associative laws. (I had suggested to him originally a different problem: describing cech cocyles as categories enriched over an n-category.)
1985 Mike and I presented this at Bangor. At around that point I began to be interested in computer science. I gave a couple of lectures in the Sydney Category Seminar. I occasionally tried to get divert Mike's attention in this direction. That took me off into distributive, extensive categories, only to return to monoidal bicategories (now with feedback) in 1994.
1992 I began the study of concurrency with Nicoletta Sabadini.
1994 After a visit of Bloom, seeing his work on iteration theories I gave a lecture at the Sydney Half-hour Seminar on machines as arrows (29th April). Since then Giulio Katis, Nicoletta Sabadini and I have worked extensively on this idea, one result being the 1997 paper "Bicategories of Processes". An earlier version of the paper was written presented at CATS '94. The work with Henry Weld on circuits, and the earlier work with Wafaa Khalil on 'functional processes' have been very influential - in fact there is an exercise in the 1992 Cambridge version on my book which appropriately interpreted is about the monoidal bicategory of Elgot automata.


Wednesday, February 15, 2006

History of an equation - (1 tensor delta)(nabla tensor 1)=(nabla)(delta)

This is a personal history of the equation
(1 tensor delta)(nabla tensor 1)=(nabla)(delta)
now called the Frobenius equation, or by computer scientists S=X.

1983 Milano Worked with Aurelio Carboni in Milano, and later in Sydney, on characterizing the category of relations.
1985 Sydney We submitted to JPAA on 12th February the paper eventually published as
A. Carboni, R.F.C. Walters, Cartesian bicategories I, Journal of Pure and Applied Algebra 49 (1987), pp. 11-32.
The main equation was the Frobenius law, called by us discreteness or (D) (page 15).
1985 Isle of Thorns, Sussex: Lectured on work with Carboni concentrating on importance of this new equation - replacing Freyd's "modular law". Present in the audience were Joyal, Anders Kock, Lawvere, Mac Lane, Pitts, Scedrov, Street. I asked the audience to state the modular law, Joyal responded with the classical modular law, Pitts finally wrote the law on the board, but mistakenly. Scedrov said "So what?" to the new equation and "After all, the new law is equivalent to the modular law". Nobody ventured to have seen the equation before.
(I asked Freyd in Gummersbach in 1981 where he had found the modular law, and he replied that he found it by looking at all the small laws on relations involving intersection, composition and opposite, until he found the shortest one that generated the rest. We believe that this law actually occurs also in Tarski,
A. Tarski, On the Calculus of Relations, J. of Symbolic Logic 6(3), pp. 73-89 (1941)
but certainly in the book "Set theory without variables" by Tarski and Givant, though not in the central role that Freyd emphasised.)
At this Sussex meeting Ross Street reported on his discovery with Andre Joyal of braided monoidal categories (in the birth of which we also played a part - lecture by RFC Walters, Sydney Category Seminar, On a conversation with Aurelio Carboni and Bill Lawvere: the Eckmann-Hilton argument one-dimension up, 26th January 1983). This disovery was a major impulse towards the study of geometry and higher dimensional categories.
1987 Louvain-la-Neuve Conference I lectured on well-supported compact closed categories - every object has a structure satisfying the equation S=X, plus diamond=1. Aurelio spoke about his discovery that adding the axiom diamond=1 to the commutative and Frobenius equations characterizes commutative separable algebras, later reported in
A. Carboni, Matrices, relations, and group representations, J. Alg. 136:497–529,1991
(submitted in 1988).
After Aurelio's lecture Andre Joyal stood up and declared that "these equations will never be forgotten". At this, Sammy Eilenberg rather ostentatiously rose and left the lecture - perhaps the equation occurs already in Cartan-Eilenberg?
Andre pointed out to us the geometry of the equation - drawing lots of 2-cobordisms.
During the conference in a discussion in a bar with Joyal, Bill Lawvere and others, Bill recalled that he had written equations for Frobenius algebras in his work
F.W. Lawvere, Ordinal Sums and Equational Doctrines, Springer Lecture Notes in Mathematics No. 80, Springer-Verlag (1969), 141-155.
The equations did not incude S=X, diamond=1, or symmetry, but the equation S=X is easily deducible (see Carboni, "Matrices, ...", section 2). Bill's interest, as ours, was to discover a general notion of self-dual object. In Freyd's work there is instead the rather non-categorical assumption of an involution satisfying X^opp=X.
2004 Joachim Kock's book I jump to this because it enables me to discuss quickly later developments. The fronticepiece of the book
Joachim Kock, Frobenius algebras and 2D topological quantum field theories, Cambridge University Press 2004
is a picture of our equation S=X in the geometric form pointed out to us by Andre Joyal in 1987, the form which suggests the name S=X (maybe Z=X might be more suggestive but I prefer S=X). Kock discusses Lawvere's work on page 121, but, unaware of our introduction of the equation in 1985, he states that
"The first explicit mention of the Frobenius relation, and a proof of 2.3.4, were given in 1991 by Quinn" in
Frank Quinn, Lectures on axiomatic topoogical quantum field theory, in Geometry and quantum field theory, American Mathematical Society, 1995.
Kock's very pleasant book is a readable account of the relation between the algebra and the geometry of the Frobenius equation. It does not describe the physical intuition behind topological field theory, a concept introduced by Witten in 1988 in
Edward Witten, Topological quantum field theory, Communications in mathematical physics, 117, 353-38, 1988.

For another account of the history of category theory from an Australian point of view see the article
Ross Street, An Australian conspectus of higher categories, Institute for Mathematics and Applications Summer Program: n-categories: Foundations and Applications, June 2004.
Curiously, this article does not mention our discovery of the Frobenius equation.


Thursday, February 09, 2006

6. Sleeping Barber - continued

I would like to continue this thread, but am busy at the moment. I just want to point out the provably false statement in Tanenbaum. Consider page 130:

page 130. "Our solution uses three semaphores: customers, which counts waiting customers (excluding the customer who is in the barber chair, who is not waiting) , barbers, the number of barbers (0 or 1) who are idle, waiting for customers, and mutex, which is used for mutual exclusion. We need also a variable, waiting, which also counts the waiting customers."

The fact is that the barbers semaphore is _not_ restricted to having values 0 or 1 as Tanenbaum states, and as is suggested by his meaning given to the semaphore. The semaphore may take arbitrarily large values.