Medici Money

One of my humanist friends, L., worries about the growing power of computer "technicians" in society. The public services in Italy are rapidly being computerized, and access to them requires following the plans and fantasies of the technicians.
However he has a sneaking admiration for mathematicians - they are more philosophers than scientists or technologists.

I tried to point out to him that numbers, since Pacioli (Summa de arithmetica, geometria, proportioni et proportionalita,Venice 1494) (and long before), have ruled us much more tightly.

When I came to Italy, trying to manage my own numbers, I wrote (with Katis and Sabadini) a categorical analysis of partita doppia (double-entry bookkeeping) (which had always puzzled me since a child). It involved the compact closed structure on Span(Graph), and in fact lead to another very abstract paper (P. Katis, R.F.C. Walters, The compact closed bicategory of left adjoints, Math. Proc. Camb. Phil. Soc., 130, 77-87, 2001).

These thoughts came back to me recently when I tried to read a book by Tim Parks (Medici Money, Profile Books, 2005). I say 'tried to' because I found the book quite indigestible despite my interest in the subject matter. It is a book without concentrated form or idea. I am surprised because I found Tim Parks' book, Italian Neighbours, on a foreigner coming to live and work in Italy well-organized and very pleasant. That book I feel I should have read before moving to Italy myself - almost every experience in it I have lived myself.

For a book on money I much prefer Frozen Desire, by James Buchan (Picador 1997), a book I return to, even if money remains to me still a mystery.

Perhaps if I read more carefully Sean Carmody's recent posts on Stubborn Mule I might be further enlightened. Or perhaps he should use some of the category theory he knows to formalize and make more precise his annecdotal explanations.

Teaching category theory to undergraduates

Recently in the Categories mailing list there has been some discussion about whether it is yet time to teach category theory to undergraduates. Some, for example John Baez, expressed the idea that it was still too early - we must wait until there are sufficient teachers who understand category theory etc, etc.

I have been teaching category theory to undergraduates now for twenty years. The first time was in 1989 when I taught a course on categories and computer science to third year undergraduates of mathematics and computer science, a course which lead to my book Categories and Computer Science (Carslaw Publications 1991, Cambridge University Press 1992).

There are many others who have taught category theory at an undergraduate level, some mentioned on the list. One in particular was Gordon Preston who taught a course in Melbourne in the early seventies (reported by Kirill Mackenzie). Another famous course was that taught by Bill Lawvere and Steve Schanuel, which resulted in the book Conceptual Mathematics: A First Introduction to Categories (with Stephen H. Schanuel), Cambridge Uni. Press, 1997 ISBN 0-521-47817-0.

Rather than premature the undergraduate teaching of category theory is overdue.

Update: Mike Shulman has written to me saying that perhaps I have misrepresented John Baez. What John Baez wrote was:

I think it's premature to introduce category theory in the undergrad curriculum. Why? Merely because there aren't enough professors who'd see how to teach the subject at that level.

I suppose I have always hoped that professors at university level were not so governed by such things as curricula.

Algebra of automata versus Process algebra

The work I have been pursuing for some years with Nicoletta Sabadini and collaborators (Piergiulio Katis, Luisa de Francesco Albasini) has been the study of distributed and concurrent systems using algebras of automata, with the main operations being sequential and communicating-parallel composition.

This is in contrast with the mainstream of concurrency which studies process algebras.

Why our contrary attitude? I would like to explain the point of view.

In a nutshell our view is that semantics should come before syntax. Process algebra takes the opposite point of view, syntax before sematics.

Let's take an analogous development in mathematics, the study of numbers.
Numbers come first. Then, after a long time, operations on numbers. Then a language for talking about numbers and their operations - polynomials. Finally, equations between polynomials.

We believe the same sequence should occur in the theory of systems. Discrete systems have states and transitions, that is, are graphs. They have interfaces and sequential and (communicating) parallel operations (including feedbacks). The languages for describing systems are the free algebras. Finally equations in the algebra (recursion) may be used to specify systems.

Process algebras take the opposite point of view. Beginning with a vague intuition about systems, processes are defined to be solutions of equations of a free algebra. The danger of this sudden jump to the language before a careful mathematical analysis of systems and their operations is that the wrong algebra with the wrong operations may be taken. Milner's CCS does not have a sequential composite of systems (only that a process may be preceded by a transition). Union is used instead of disjoint union in the other sequential operation. The communicating parallel operation is based on a vague broadcast idea.

Of course, in the end of a development as proposed by us, free algebras and recursion arise, but only when the correct operations have been identified. At this stage also other semantics may be identified (in the example of numbers, real numbers, complex numbers, rings of functions, ...). If the algebra of systems has been developed correctly, at least a part should have continuous systems as models, thus allowing the confrontation between discrete and continuous.

Some years ago we produced a process algebra based on our idea of parallel. Recently Pawel Sobocinski is developing a process algebra based on our idea of communicating parallel (but not our view of sequential).

The discovery of adjoint functors

Bill Lawvere, in his lectures in Como, 10 January 2008, discusses Kan's discovery of adjoint functors.


Here's a photograph of Daniel Marinus Kan:

The parallel composition of processes

We have been arguing for some years (really since the appearance of our paper on Span(Graph) in AMAST 97) that the usual operation in process algebras called parallel is a wrong direction, not describing explicitly the media of communication. I talked about this in Calais at CT 2008, saying on the first slide that our work "hasn’t as yet been used by the concurrency community but it should be".

Well it seems that at last someone from that community is listening.

After the talk Pawel Sobocinski came up to me saying he had an idea of a process algebra like Span(Graph). We had actually produced such a thing, but rather half-heartedly, to try to communicate with process algebra people. But Pawel is now developing a full-blown process algebra with communication like Span(Graph).

It is interesting that Pawel, in his second year at University in Sydney, did a vacation project with me on Span(Graph) and attended the 1997 AMAST meeting.

His process algebra does not incorporate the full sequential operations of Cospan which we introduced in the paper "P. Katis, N. Sabadini, R.F.C. Walters, A formalisation of the IWIM Model. in: Proc. COORDINATION 2000,(Eds.) Porto A., Roman G.-C., LNCS 1906:267-283, Springer Verlag, 2000".

We became involved in thinking about Coordination through visits to Como by Farhad Arbab. Our paper showed how to give an abstraction of his IWIM model in CospanSpan(Graph) which had however the advantage of a compositional theory of connectors, not a feature of Manifold. We criticized Manifold for this defect to Farhad and I think this had an influence on his new coordination language Reo.

Gavin Wraith's web pages

I particularly like Gavin's web pages. I find them particularly evocative, with their concentrated careful use of language, a style I cannot emulate. I think Gavin has the makings of a novelist. He might abstract from his family history and write a novel placed in Byzantium, between the east and the west. Probably he would prefer to write fantasy but this would interest me less.

Looking back at my posts I notice that many have a decidedly negative tone. Gavin has separated equivalent writing under the category "rants". I will introduce today two new categories of posts, optimistic and pessimistic. Choose which mood you would like to see.

Snippet of Bill Lawvere's lectures in Como, 10 January 2008

Well worth viewing despite the fact that Bill's face is obscured for the first few seconds of the snippet. I will put up a few more pieces in later posts. This video is also at my old department pages where there are more details of the meeting.

New paper with Steve Lack and Richard Wood - bicategories of spans

We have just put a new paper on arxiv called "Bicategories of spans as cartesian bicategories", where we characterize such bicategories as follows: a bicategory is biequivalent to Span(E) for E a category with finite limits iff it is cartesian, each comonad has an Eilenberg-Moore object, and every map is comonadic.

There is quite a bit of further stuff in the paper, but one extra point I would like to mention as it is relevant to our paper on spans and cospans.

The extra result is that Span(E) for E finitely complete has direct sums iff E is extensive. This is related to work of Heindel and Sobocinski (T. Heindel and P. Sobocinski. Van Kampen colimits as bicolimits in Span. In Calco '09, LNCS, Springer, 2009).

To bring this result down to earth lets look at Span(Sets) and see why it has direct sums. Consider a span R from X to Y. Suppose X=U1+U2+..Um, and Y=V1+...Vn. Then clearly R breaks up into a family of sets Rij, the elements which go from Ui to Vj. So the span R becomes a matrix Rij of spans. A special case of this is when R is an endomorphism of X, that is, R is a graph. If the vertices of the graph break up as a sum U1+...Um, the graph may be expressed as a square matrix of spans Ui->Uj (i,j=1,2,...,m). (A span in sets is a kind of bipartite graph.)

On cospans and spans II

A little explanation of the paper http://arxiv.org/abs/0909.4136.

The aim of the paper is to describe discrete systems which communicate in parallel (that is, they are distributed in space) and evolve sequentially (the physical form of the system may change). This is an aim shared with so many (prior) authors it is invidious to begin a list but I must do so - Milner, Hoare, Petri, Zielonka, Nivat, ...

The basic model we take for a system is a graph of states and transitions.

To be capable of being combined with others a system must have borders, boudaries, or interfaces. Two types of interfaces are necessary. The first are sequential interfaces, drawing inspiration from the sequential operations of Kleene. A system must have (generalized) initial and terminal states. We commence more generally with two graph morphisms into the system.

A system with sequential interfaces is a cospan
\[\usepackage[all]{xy}\xymatrix{
A\ar[r]^{\gamma_{0}}& G&B \ar[l]_{\gamma_1}
}\]
of graphs. The graph $G$ is the graph of the system; $A$, and $B$ are the graphs of the interfaces. Systems compose sequentially by pushout.

For the parallel interfaces we take inspiration from the model of circuits. Circuits have transitions which are reflected on the boundaries. We take here as our definition two graph morphisms out of the system

A system with parallel interfaces is a span
\[\usepackage[all]{xy}\xymatrix{
X& G\ar[l]_{\partial_{0}}\ar[r]^{\partial_{1}}&Y
}\]
of graphs. The graph $G$ is the graph of the system; $X$, and $Y$ are the graphs of the interfaces. Parallel composition of systems is by pullback.

A system with sequential and parallel interfaces consists of a
commutative diagram of graphs and graph morphisms
\[\usepackage[all]{xy}
\xymatrix{
G_0\ar[d]_{\gamma_0} & X \ar[l]_{\partial_0}\ar[d]_{\gamma_0}\ar[r]^{\partial
_1}&G_1\ar[d]_{\gamma_0}\\
A & G\ar[l]_{\partial_0} \ar[r]^{\partial_1}&B\\
G_2\ar[u] ^{\gamma_1}& Y\ar[l]_{\partial_0}\ar[u]^{\gamma_1}\ar[r]^{\partial
_1}&G_3\ar[u]^{\gamma_1}}%
\]

We denote such a system very briefly as $G_{Y;A,B}^{X}$, or even $G_{Y}^{X}$
or $G_{A,B}$ or even just $G$, depending on the context.

A blog worth visiting - The Stubborn Mule

The Stubborn Mule's Perspective is a blog of Sean Carmody, whom I knew as a student in Sydney. In fact his fourth year thesis was the extension of the Todd-Coxeter procedure to categories and functors. The blog involves also other students I knew in Sydney.

One of the main activities of the blog is the display of economic and other measurements pulled out of the net.

I always liked the subject of display of data since I read (?) the book by Edward Tufte, The Visual Display of Quantitative Information. In particular I liked the famous representation by Charles Joseph Minard of the Russian campaign of Napoleon. (Actually, now that I think about it, another amazing work of graphical represntation is Gray's Anatomy,)

On the Stubborn Mule you will see the advances in representation of data produced by computer technology.

I am hoping we will also see more conclusions, concentration of information, and identification of underlying causes.

Life in Italy

I am beginning a new series of posts about life in Italy which would not be perhaps appropriate on the department web site, even if many may refer to University matters.

The first one: Assisi

We just spent the weekend in Assisi (at a conference of Computer Professionals). Assisi is an astonishingly beautiful city. I used to travel the world when I lived in Australia, but now I feel Italy is enough.