Bob Walters

Categories and automata

2012-01-16T01:14:00.000-08:00

I have just finished a course here in Como on categories and automata, a fair part of which was about what I called "Reticular Categories" - symmetric strict monoidal categories, each object of which has a commutative frobenius algebra structure, the structures being compatible with the tensor.
(Braided reticular categories were the subject of our recent Arxiv article called Tangled Circuits.)

I believe reticular categories can be appreciated at an undergraduate level - which is where I taught the course. They will be part of a book we are writing to follow-up Categories and Computer Science.

Quality

2011-12-31T06:14:00.000-08:00

It was recently said at a university that, in deciding where funds should go, it was impossible to evaluate the quality of researchers, so that they must be judged by the quantity of their research production.

Number Theory book

2011-12-31T06:11:00.000-08:00

A Japanese translation of my book "Number Theory: an Introduction, Carslaw Publications, 1987" has been published in September 2011 by Iwanami Shoten, Publishers, 2-5-5 Hitotsubashi, Chiyoda-ku Tokyo 101-8002 Japan.

What do I believe of Physics?

2011-12-06T03:59:00.000-08:00

I wrote a post with this name in 2009 but the matter has come to mind again. The point is whether I actually believe the new results of physics in the same way that I believe facts about the moon (for example that the distance from the centre of the earth to the moon is between 350,000 and 450,000 km).

I am now in the Department of Science and High Technology, Como, the fourth department of which I have been a member since joining the University of Insubria. I have been successively in (i) the Department of the Sciences of Mathematics, Physics and Chemistry, Como, then (ii) the Department of the Sciences of Culture, Politics and Information, Como, then (iii) the Department of Informatics and Communication, Varese, and finally (iv) the present department.

As a member of (iv) I thought I should attend some interdisciplinary seminars - in fact I have mentioned elsewhere how I miss seminars - and so I attended one about the most recent Nobel prizes in physics. It was a very good lecture with a brief introduction to the mathematics and physics of cosmological models, and a description of measurements which lead to the idea that the expansion of the universe is accelerating. When I was a student in Canberra I remember hearing about the work of Allan Sandage surveying Cepheid variable stars to estimate Hubble's constant (his colleage Olin J. Eggen was at Stromlo observatory). I thought at the time that the measurements were discutibile, they were not far fetched but I certainly did not believe the results in the sense mentioned above.

The newer Nobel prize work involves the extension of the measurements using supernovae. I am even more cautious about this.

The last part of the lecture was a beautiful graphic of the history of the universe from the big bang, through inflation etc, to the current accelerating stage with 75% of the universe being dark (matter or energy). This seems to me to be completely speculative.

The first question from the audience was from a physicist who asked "do you believe this?". It seemed to me from the involved response (in rapid Italian, and for that I am unsure) that the speaker himself found the matter speculative. Certainly from the question at least one physicist present did.

I do not touch here on the works of Deutsch and of Tegmark which to me are beyond speculation.

Update I was talking to a physicist today about my doubts. He said "Well, you don't have the competence to judge!".

Peter Robb

2011-11-21T05:05:00.000-08:00

I am reading at the moment (on my Kindle) a book by Peter Robb - Street fight in Naples: A city's unseen history. I know very little about Peter Robb other than what he reveals explicitly or otherwise in his book. He is an Australian who has spent many years in Italy, and in particular in Naples.
I have also read his books Midnight in Sicily and M (about Caravaggio or Merisi).

His style is to intermingle his personal experiences with the many layers of Italian history. The result comes very close to expressing what I love about Italy, why I enjoy living here.

I am surprised to see now from wikipedia that he lived in Italy for only fourteen years. I've been 13, and I'm not ready yet to write my Italian opus. Maybe next year.

Old fashioned names

2011-11-11T02:25:00.000-08:00

I have a certain nostalgia for names.They carry history with them.
I notice now that some physicists think Eilenberg and Mac Lane's name "category" is not optimal and suggest instead "semigroupoid".
An even bolder proposal is to change the old fashioned name "mathematics" to "homotopy type theory pseudocode".

One of the arguments against the old fashioned terms is ambiguity, so "set of points" is in danger (try googling that), but I think the same people have already solved that by the introduction of "setoid". How should physics be renamed to avoid the ambiguity of "un bel fisico"?

Personally I prefer to retain the word "mathematics" with its connotations of learning, and suggest renaming HoTT pseudocode as "pseudomathematics".

One of the rigidities of Italian life is that it is very difficult to change your name - you more or less have to have the permission of the president.

MathSciNet

2011-11-11T02:19:00.000-08:00

I rarely look at MathSciNet these days, but I noticed yesterday that most of my recent papers are not mentioned there, and probably never will be. To me the papers have considerable mathematical interest. It's the problem of being a mathematician working in computer science - or maybe I am no longer a mathematician.

Double entry bookkeeping again

2011-10-22T02:09:00.000-07:00

I have had some interesting correspondence with Professor David Ellerman about our arxiv paper on double entry bookkeeping (a version of which was also included in the published paper
P. Katis, N. Sabadini, R.F.C. Walters, On the algebra of systems with feedback & boundary, Rendiconti del Circolo Matematico di Palermo Serie II, Suppl. 63 (2000), 123-156,
also available here).

Professor Ellerman has written extensively (prior to our work) on the mathematical treatment of double-entry bookkeeping. For his views one should consult his papers and blog, but his main slogan seems to me to be that double-entry bookkeeping is an elementary application of the group of differences construction (that is, the construction of the additive group of integers from the abelian monoid of natural numbers).

Our view was that there is another context in which to study the subject, namely the algebra of concurrent distributed processes. There accounting amounts to measuring such processes, not simply in an abelian group but in a kind of distributed abelian group.

However, from the discussions with Professor Ellerman I see that in the section where we give an example of traditional accounting we have omitted an important aspect.

It was difficult to write the section because an accounting system is a complicated thing with a lot of structure and there is debate about just what is the minimum to constitute a double-entry accounting system. This debate has bedevilled the historical research into the origins of partita doppia.

Before describing the main matter there is a minor thing I might like to change, namely that we used negative and positive numbers instead of credits and debits. That unfortunately suggests to a mathematician that we are using the ring of integers rather than the abelian group. The distributive law destroys the duality between positive and negative, between debits and credits. Professor Ellerman calls the group of debits and credits the Pacioli group in honour of Luca Pacioli who wrote at a time (1494) when there was no ring of integers.

We believe that the principal aspects of partita doppia is that a system of accounts is closed, and that in any transaction a pair (or more) of accounts is involved, a debit being made to one account whereas a credit is made to another, and further that the total is invariant. These are the key properties of a system of accounts in our algebra. To me these are the properties which characterize double-entry accounting, and the origin of the name.

However there is another crucial feature of partita doppia in practice, namely that the state of an account is held as a pair of numbers, a debit and a credit total, and not just as the (debit or credit) balance. (In the history of transactions in an account the debits are written to the left and credits to the right.) Further the accounts in a conventional system are divided into accounts which are normally credit accounts and those which are normally debit accounts, which helps, via the "golden rules of accounting", to keep track of which account should be credited and which debited.

When I get time I will add some new material in the example in the arxiv paper in which the state of a conventional T-account will be a pair of natural numbers, debit and credit, rather than an integer.

International Review of Mathematical Sciences December 2010

2011-10-22T00:32:00.000-07:00

I just noticed this report of the mathematical sciences in the United Kingdom.

There is no mention of Category Theory.

I am always interested to know the people responsible.
The committee making the report was
Professor Margaret Wright (Chair) New York University, USA
Professor Anthony Davison École Polytechnique Fédérale, Switzerland
Professor Stephen Fienberg Carnegie Mellon University, USA
Professor Andrew Granville University of Montreal, Canada
Professor Peter Hall University of Melbourne, Australia
Professor Gary Horowitz University of California, Santa Barbara, USA
Professor Patrick Huerre Le Laboratoire d’Hydrodynamique de l’École Polytechnique
(LadHyX), France
Professor Willi Jäger University of Heidelberg, Germany
Professor Zhi-Ming Ma Institute of Applied Mathematics, Beijing, China
Professor Robert MacPherson Institute of Advanced Study, USA
Professor Dusa McDuff Columbia University, USA
Professor Stefan Müller University of Bonn, Germany
Professor Cheryl Praeger University of Western Australia, Australia
Professor David Ryan University of Auckland, New Zealand
Professor Andreas Schuppert RWTH Aachen University, Germany
Professor Ruth Williams University of California, San Diego, USA

Tangled circuit diagrams III

2011-10-04T23:13:00.000-07:00

I promised an introduction to a paper on tangled circuit diagrams some time ago, but other work caught up with me. At least the paper has now appeared in arxiv at arXiv:1110.0715v1 [math.CT].

Term has just started here, with the usual confusion, and we have visitors from Australia, so the promised exposition will have to wait a bit more.

Tangled circuit diagrams II

2011-09-16T02:01:00.000-07:00

Instead of proceeding linearly with the exposition I decided today to point out an open problem.

We are able to distinguish using representations (invariants) the circuits mentioned in Tangled circuit diagrams I, but other very simple examples escape our methods (or perhaps the expressions we are trying to distinguish are actually the same and we can't see the proof).

For example, we can prove that the rotation through 720 degrees in the diagram:

is equal to no rotation (Dirac's belt trick).

However we suspect that rotation through 360 degrees is not equivalent to no rotation, but we cannot decide. Our invariants don't distinguish but we don't see a proof of equality.

Just to make something precise about the definition of tangled circuit diagrams - the commutative property of commutative Frobenius algebras is commutativity with respect to the braid twist.

I will be putting up an arxiv version of the paper in the next week.

Tangled circuit diagrams I

2011-09-14T05:34:00.000-07:00

I haven't blogged for some time, but I want to start a series of posts about a paper we (Rosebrugh, Sabadini and I) have written on tangled circuit diagrams (we are just cleaning up final details now). I have given hints in earlier posts but now I would like to give an exposition in blog-post form.

The aim is to describe an algebra with the property that expressions in the algebra may be pictured as circuit diagrams, but circuits in which the tangling of the wires is taken into account.

For example, the following two circuits should be expressions in the algebra, but distinct:

Another example of two distinct circuits:

Another:

Both a trefoil and an unknot should be examples of circuits (with wires only, and no components) and they should be distinct.

But it should be possible to do Dirac's belt trick and prove in the algebra that the following two circuits are equal:

The point of the paper is to define such an algebra, and to prove statements such as those above, using representations of the algebra in more concrete algebras of the same type. A special case will be the use of knot colouring, and knot groups in the study of knots. Some of the more concrete algebras have been used by us previously in modelling various kinds of circuits with state, and systems of parallel processes etc.

Let me begin in this post by at least making the definition of the algebra of tangled cicuits. I will simplify slightly by considering circuits with only one type of wire.
In fact it is not just one algebra; first one must choose a "multigraph" M of components. The edges (components) in a multigraph have not just a source and a target but a number of sources (the input wires) and a number of targets (the output wires).

Definition Given a multigraph M the algebra of tangled circuit diagrams formed from M, denoted TCircD, is the free braided strict monoidal category on M such that the single generating object has a commutative Frobenius algebra structure.

I will stop there for today, but will explain this definition in the next post. I should recount the history of the ideas, and the other research on which they depend but will leave that to a later post - that's one of the things we are cleaning up in the paper now.

Bill Lawvere's lectures 10 January 2008, Como, Italy

2011-07-22T05:33:00.000-07:00

I put on YouTube a first piece of Bill's lectures. I will gradually be putting most of his lectures there.

Peter Cameron on the purpose of a university

2011-07-22T02:22:00.000-07:00

I have quoted an earlier post of Peter Cameron:
"The purpose of a university used to be teaching and research; now it is making money and scoring well in league tables".

He has just amplified this posting and I must endorse most of what he says.

I have a couple of extra comments to make:

Peter says that now teaching quality is judged by student evaluations. But in fact in Sydney at least the situation is much more complicated - new staff members are advised to begin developing a teaching dossier which includes research in teaching etc. He rightly says that research is evaluated by grant-attracting ability.

The accademic community is not blameless in this change.

The teaching and learning policies were introduced by academics.

When I began my career in 1970 there were no such things as grants for mathematicians. Later we happily accepted them and asked for more. We gradually spent more of our time writing grant applications.

I have no objection to politicians deciding priorities for public resources. I find many claims by scientists (see Brian Cox) for a greater share of public funds ridiculous.

However decisions of quality in teaching and research must be done by academics. If they do it badly universities will be damaged. Using so-called objective measures is an abdication of responsibility.

The situation is particularly clear in Italy. Nobody trusts anyone (perhaps with reason), and as a result the wily Italians have built up an incredibly intricate net of controls to keep people honest. When people are dishonest the controls don't work. For honest people the controls are an impediment. Nevertheless good work gets done.

It is hard however to recommend this new academia as a career to young people.

France

2011-07-21T08:56:00.000-07:00

I didn't go to the annual category theory meeting, currently occurring in Vancouver - I am beginning to lose enthusiasm for intercontinental travel. I don't know how many times I have flown from Australia to Europe or America - too many times. And the internet has changed the need for so much travel. I do hope the organizers put up slides of the talks, and I would of course liked to have met old friends.

Instead I made a car trip to France, a holiday, with my wife and daughter. We left Italy by Gottardo Tunnel, going to Beaune, Chartres, Paris for a few days, then Brittany for a few days - including Carnac, returning through the Loira Valley, Bourges, Bourge-en-Bresse and the Monte Bianco Pass.

In terms of art and architecture the late 20th century comes out very badly in comparison with Egypt, the middle ages,
and renaissance Italy.

Ugo Montanari's talk 22 June 2011

2011-06-24T10:51:00.000-07:00

on the occasion of a celebration in Milan in honour of Gianni Degli Antoni.

Ugo spoke about his latest work about a compositional calculus for Petri nets using the wire calculus of Sobocinski.

I was disappointed that he didn't mention our work on connectors, which we have spoken about for years, including in joint projects, and which goes back to 1997 or even 1987.

In particular because the work of Sobocinski derives from ours. It arose in discussions with me (he even agreed that it was a joint project at the time), and lectures given by me, one at CT 2008 in Calais, where I emphasized the important difference between the parallel communication in Span(Graph) and that in conventional process algebras such as CSP and CCS. The slides are available at the CT site.
Sobocinski actually carried out a student project with me in 1997 at the University of Sydney on Span(Graph) and was present at our talks at AMAST 1997 in Sydney, one of which was on representing Petri nets in Span(Graph). He refers to both our AMAST papers in his article in CONCUR 2010, including the following quote:
"The operations of the calculus presented in this paper are fundamentally different to those utilised in the aforementioned literature. Indeed, they are closer in nature to those of tile logic [13] and Span(Graph) [18] than to the operations of CCS. More recently, similar operations have been used by Reo [2], glue for component-based systems [8] and the wire calculus [30]. Indeed, in [17] Span(Graph) is used to capture the state space of P/T nets; this work is close in spirit to the translation from nets to terms given in this paper."

I might say that even Arbab was influenced by us. He visited us in Como in 2000 and was talking about Manifold. I told him his connectors were not compositional. I believe his subsequent work on Reo was influenced by our discussions. Our paper in COORDINATION 2000, prior to Reo, used compositional connectors in modelling IWIM in CospanSpan(Graph).

The point of this post is not casual.
The main contention in all our work is that concurrency theory has taken a wrong direction for thirty years, because of the choice of the wrong basic operations. We have said this in many forums including IFIP WG1.3 without apparently any reaction. For some more detailed comments see this post.

Kindle

2011-06-15T03:47:00.000-07:00

I mentioned in an earlier post that I had bought an Amazon Kindle reader. At that point I had had the Kindle for a week or so and it seemed to me a revolutionary device (more so for me than an Ipad).
I started putting all my document (in pdf) on the Kindle, as well as buying some books (which arrived instantaneously). I found it really easy to read books with the paper-like screen. (I have never been able to have the kind of interaction with a computer screen that I have always had with books, in which one is not conscious of the medium.)
We have a big problem with the volume and weight of our books. When I moved to Italy I brought 70 boxes of books, leaving many behind. I really needed books in English, and I still prefer to read books in English. It seemed that I did not need to add to that volume in future.
Then I had a surprise. I had been treating my Kindle like a book, but certainly not worse than a computer or a mobile phone. But one day the screen froze.
I wrote to Amazon who were extremely cooperative and offered to replace the Kindle. I had some doubts because it seemed to me that the device is more fragile than I hoped.
My confidence has returned. The new Kindle has a cover which I strongly recommend. I still believe it is a revolutionary device.
The family now has now have two Kindles and is considering a third.

Tangled Circuits

2011-06-14T14:33:00.000-07:00

The work Nicoletta and I did with Bob Rosebrugh during his visit concerned tangled circuits; that is, adding to our model of circuits the possibility that the tangling of the wires might be recorded. This is related to the previous post here.
In that post I described, or better hinted at, a new category in which tangles might be represented, which I will now call TRel. Let me describe that category here.

Take a group G. The objects of the category are (formal) powers of G. An arrow from G^m to G^n is a relation R from G^m to G^n satisfying two properties:
1) (x_1, ..., x_m)R(y_1, ... ,y_n) implies that for all g in G
(g^(-1)x_1g, .... , g^(-1)x_mg)R( g^(-1)y_1g, .... , g^(-1)y_mg)
2) (x_1 , .... , x_m)R( y_1 , .... , y_m ) implies x_1...x_m(y1...yn)^(-1) is in Z(G) (the center of G).

I will give some more details later, but this category is a braided monoidal category, and the object G has the structure of a commutative Frobenius algebra. This means that G has a fortiori the structure that the generator of the category of tangles has. Hence there is a monoidal functor Tangles -> TRel. There is a similar category TSpan based on spans instead of relations, and the functor Tangles -> TSpan yields the colouring of knots in the group G.
Bob Rosebrugh has just been speaking about this at FMCS. in Calgary.

Cospan Span (Graph)

2011-06-14T14:04:00.000-07:00

We (Nicoletta and I) have been lecturing at the University of Milan at Bicocca this fortnight on our work on an algebra of automata for application to concurrent, distributed, hierarchical systems partly described in this post.
One thought occurred to me before the lecture today which I do not usually emphasize in lectures to computer scientists: the algebra we describe is really standard categorical algebra invented for completely different reasons.
For example the (bi)category of spans (and hence also cospans) was invented in 1967 (if I remember correctly) by Jean Benabou. Followers of the n-category cafe will see its use in other fields. The structure we use on Span(Graph) was introduced by Carboni and me in studying relations but its roots goes back to Frobenius (google Frobenius algebras).
The structure which includes both spans and cospans seems new though quite in line with other developments. The computer science interpretation is due to us and collaborators.

I mention all this because similar models introduced by Computer Scientists, such as Asynchronous automata, automata of Arnold and Nivat, Team automata etc seem to me to be ad hoc constructions with little connection with other parts of science.

Of course using standard mathematics might be a way of forcing mathematics on an application. We don't believe that is so in this case.

A visit from Bob Rosebrugh

2011-05-26T00:17:00.000-07:00

Nicoletta and I have Bob Rosebrugh visiting for two weeks. We are getting some nice work done (I will report later) in which the Yang-Baxter equations play a part.

We went on Tuesday to a physics lecture by Professor David Sherrington (Oxford, Center for Non-Linear Studies LANL, Santa Fe Institute) on the theme of complexity in physics which seemed to be a review of rather old material with a relation to the original work of Baxter. The slogan of the work is that "complexity is not complication". By complexity, which they think of a good thing, the subject in which they make progress, the physicists in this field mean the types of complicated behaviours which may arise from a regular net of very simple components. A complicated (uninteresting) system instead is a complicated net of (possibly) complicated components. It is the same kind of view held by another type of physicist regarding cellular automata.
OK. Complex systems in this sense are worth studying, but to pretend as they do that this explains economic systems, the brain etc seems to me to totally ignore the ideas of organization, structure, hierarchy etc. Computers, for example, are not designed as cellular automata.
It seems to me that the slogan is designed to promote physics as central, a suspicion that was confirmed a little by the speaker who said that "people think that physicists are arrogant" and who presented a slide with a star-shaped diagram (or should I say a pre-Copernican diagram) with physics at the centre and connections between the centre and many other subjects (economics, biology, mathematics, informatics,...) but no connections between these other subjects.

The richness of Italy

2011-05-06T09:53:00.000-07:00

I first came to Italy in 1980 (not quite true: I had been to Naples briefly as a boy, sailing to England from Australia on the Orient Line ship Otranto). I bought a Guide Michelin dated 1974. I have just been looking at it because we made a car trip to Salento, the heel of Italy.

The guide contains nothing south of Lecce - it is a blank about the whole region. Amazing. There is no Otranto in the guide for example. Where would the gothic novel be without Otranto (I read Bram Stoker on my new Kindle on the trip)?
The most remarkable thing about Otranto is the Tree of Life mosaic, created by Pantaleone (in four years from 1163) on the floor of the cathedral. You can find out more about it at this site. It is beautiful and astonishing.
On the way down to Salento we visited the other astonishing, much better known, mosaics in Ravenna. Have a look at the Mausoleum of Galla Placidia here.

Como Category Seminar: What does "observable" mean? Hidden Markov models

2011-04-13T08:34:00.000-07:00

In various applications, for example in language recognition, there is a variation of the notion of Markov chain called the Hidden Markov model. The word "hidden" refers to the fact that the states are regarded as hidden or unobservable. Roughly the idea is this: the states are syntactical classes, and there is a given probability of passing from one class to another. Further, in a certain class there is a probability associated with each element of the class, the probability that this element is output, or visible.

The question of what is visible or not is just declared by the formal definition, but I would like to suggest that visible has a wider meaning. A state or a transition of an open system is observable or visible if it is the projection of a state or transition of the system on its boundary. What does boundary mean? The boundary is the part of the open system which may be glued to the boundary of another open system. In other words composition of open systems determines what observable means. What is observable is what can be joined to an observer. The extreme case is that closed systems have no visible features.

Let me give an equivalent but alternative definition of hidden markov model in which these ideas are explicit. Consider the following open markov chain G in which the states are visible (as transitions on the boundary):

Now compose this system with one V with only one state, and a transition for each element of each syntactic class (the same element may occur in different syntactic classes with different probabilities), for example:

The composed system is:

in which the states of the system G are hidden. Of course inferences may be made about them: one may ask, for example, given an observed string what is the probability that a certain path in the system G was used to generate it - a probabilistic parsing.
This system is pictured in the hidden markov model as:

In practice there are many fewer syntactic rules than words in the vocabulary, and it the separation of syntax from vocabulary which is presented as the advantage of the hidden markov model, a separation which is particularly clear in the compositional description.

Italian enterprise

2011-04-07T00:42:00.000-07:00

Italian academics have discovered Spin-offs (the english word is used, though in a sense particularly Italian). The small set of offices where I work in Como now contains three Spin-offs. One, called Light in Light occupies the meeting room where we used to hold seminars, meetings of department, televised lectures (transmitted to Varese), discussion with graduate students etc. The second called Opensoftengineering occupies the office which used to be occupied by graduate students, visitors etc. The last, which is perhaps not technically a Spin-off, but is certainly a centre, is called the Centro di Ricerca in Knowledge and Service Management for Business Applications, and occupies what was formerly a staff office.

The Varese pole of the university has been even more enterprising with a Foundation called Mind the Bridge. (To my Australian ears this name is a little unfortunate with echoes of "mind your step!" or "mind your head!").

Teaching and learning, and research management

2011-04-05T03:26:00.000-07:00

I have been a teacher for more than 40 years. I have taught thousands of students (including 9 PhD's). I have written textbooks. I have always found it hard work.
Towards the end of my career in Sydney (1998) I discovered the astonishing fact that in order to prove that one was an excellent teacher (which I was not) to the satisfaction of university committees one needed to have published research in education. At the same time the university started using the word learning rather than teaching.

This process of formalizing what it means to be a good teacher has progressed enormously in Sydney. There are the very interesting centres The Institue for Teaching and Learning, and Learning Solutions which will give you courses on how to prove you are an excellent teacher, and how to manage your career.
Learning Solutions is "responsible for developing and training staff across the University, in support of the University's strategic objectives. Learning Advisors work closely with Faculties and Units to build the capabilities of their staff. Programs focus on leadership and change, community engagement (media), and research", so they also give courses on research.
So, for example, there is a programme for "mid-career researchers who are new to the role of CI (recently won grants) or who are currently working towards being in a CI role (ie. who have already been involved in successful grants and have submitted grant applications with themselves as a lead CI). The program develops the skills required by those responsible for the management of research grants and projects. The focus of the program is on those who will be managing research projects, teams or budgets".

I have doubts that such programmes identify good teachers, or improve teaching or research. They certainly increase the amount of nonsense, and business language in universities. I don't believe research is the same thing as managing research grants.

I can only repeat Peter Cameron's phrase:
"the purpose of a university used to be teaching and research; now it is making money and scoring well in league tables".

Cherries

2011-04-05T00:38:00.000-07:00

This is the moment when the hills around our house are daubed with the white of flowering cherry trees

(at least up to 700 metres above sea level). At our house in the Bergamo valleys which is above 1000 metres the cherries are still to bloom. In the distance the Orobie Alps remain snow covered.

Como category seminar: Open Markov chains

2011-03-21T02:37:00.000-07:00

Today (16th March 2011) was the defence of the doctoral thesis of our student Luisa de Francesco Albasini. I will describe one aspect of her work. Traditional markov chains are an extremely useful tool in diverse applications. Just to give one example Google uses a markov chain to rank web pages creating some order in the internet.
A markov chain is a system whose dynamics is encoded in a square matrix of non-negative reals whose row sums are all 1. The rows (and columns) may be thought of as states of a system and the i,j th element of the matrix as the probability of a transition from state i to state j. The k th power of the matrix gives the probabilities of paths of length k.
A markov chain is easily represented also as a labelled graph or automaton:

Systems modelled in this way are closed systems. An essential aspect of compositionality of systems
is that one needs to consider open systems.

Luisa gives an answer as to what is an open markov chain and the algebra of such. Aspects of this idea occur in other studies but the combination is new; in particular the constants of the algebra. More details may be found in the two papers [1],[2] below.

So what is an open markov chain? It consists of a family of matrices of non-negative nxn matrices rather than just one. Each matrix in the family describes the probability of transitions between states in the presence of given input/output, or better with a given interaction with the external. The sum of all the matrices in the family is a markov matrix though each individual matrix is not.
An open markov chain may also be represented as an automaton, but now labelled not only by probabilities but also input/output symbols:

The corresponding automaton:

Notice that in the automaton the interaction with the external is pictured as wires with possible signals on the wires, and there may be several such wires. For the algebra they are organized as wires on the left and wires on the right - but one should not really think in terms of input on the left and output on the right. The wires are not input/output wires but channels to the environment.

What we have described so far fits into the classical notion of weighted transducer, though that notion is usually thought of as translating input to output.

What are important now are the binary operations and constants. The main binary operation is the circuit-like operation of joining the right-hand wires of one automaton R to the left-hand wires of another S, which composite we denote as RS.

The formula for this operation is analogous to the formula for composition of relations, or of matrices:

Actually I need to make a correction: this formula does not necessarily result in an open markov chain because the condition about the row sums may be violated. In doing this composition the transitions are restricted to those which are possible in the combined system. This means that the matrices of RS need to be normalized (and an extra condition is needed to assure that zero row sums do not occur in the total matrix of RS).

This operation exists in the work of Shutzenberger and Eilenberg on transducers.
In addition to this operation (and a similar one analogous to the parallel composition of circuits) we introduce the following important constants:
the identity, the diagonal, the twist, the opposite diagonal, the turn and the opposite turn. These are wire operations and have the following pictorial representations:

These constant automata are all one state automata, in which there is a transition for every combination of signals (I/O), and all transitions have the same probability. Using the constants and the binary operations we can form "circuits" of open markov chains. If the circuits are closed we get a traditional markov chain as a result.

This structure of the markov chain may be highly significant in the applications. The open "components" of a closed markov chain may be the entities of interest. What you can prove about a markov chain may come from the intuition about its open components rather than just from the global states and transition probabilities (just as a building may be modelled by a huge system of differential equations, or by considering how it is built from components).

If you want to see some examples, or some precise definitions look at the papers below.
This has been an experiment in using graphics in this blog - it hasn't proved to be too difficult.

[1] L. de Francesco Albasini, N. Sabadini, R.F.C. Walters: The compositional construction of Markov processes, Applied Categorical Structure, Springer Netherlands, 2010 (preliminary version arXiv:0901.2434, 16.01.2009), and
[2] L. de Francesco Albasini, N. Sabadini, R.F.C. Walters: The compositional construction of Markov processes II, to appear in RAIRO-Theoretical Informatics and applications, EDP Sciences (preliminary version arXiv:1005.0949v1, 6.05.2010).

Update: Here is a link to Luisa's thesis. Notice that what I called open Markov chains are called instead Markov automata in the thesis.

Como Category Seminar

2011-03-15T07:00:00.000-07:00

I have said that the original motivation for this blog was to rant about problems with university reform in Italy. However I realize now that another reason for the blog is that I miss having a scientific seminar in Como. My scientific life in Sydney was always bound up with the Sydney Category Seminar. Here in Como, despite some attempts, I have never been able to create a regular seminar, so I am going to use part of this blog to take the place of a seminar. If I can get others to contribute all the better, but in any case I will record here the kind of lectures I used to give in Sydney; that is, work in progress, comments on other research etc.

The purpose of a university

2011-03-10T03:33:00.000-08:00

From Peter Cameron's blog:
"The purpose of a university used to be teaching and research; now it is making money and scoring well in league tables".

Duality

2011-02-22T10:30:00.000-08:00

The Frobenius equations mentioned for example in the last post were introduced in my paper with Carboni in 1987 to express the fact that an object V of a symmetric monoidal category might be self dual - that is, that V is adjoint to V - in a strong sense. Each object of the category of sets and relations is self-dual in the strong sense that it has a Frobenius algebra structure (given by the diagonal map; that is, arising from equality). Even the Frobenius structure of wires in electrical circuits mentioned in the last post has an idea of equality associated, in that case the wires are equipotential regions.

However categories are not self-dual objects in the category of categories and bimodules (=profunctors); the natural dual of a category, the opposite category, is not isomorphic to the category. Here I describe a generalization of the notion of Frobenius algebra which implies that an object has a dual, but is not necessarily self-dual, and which applies to the category of categories and bimodules.
(A simpler example you may like to consider is the category of posets with arrows being bi-ideals (a bi-ideal from V to W is a subset of VxW with the property that if (v,w) is in the subset and v'<=v, w<=w' then also (v',w') is in the subset).)

Definition A generalized Frobenius algebra in a symmetric monoidal category (tensor written x) consists of two objects V and W and six arrows (for my ease I have used the same name for last two)
delta:V -> VxV, nabla: WxW->W,
d:W->WxV, n:VxW->V,
!:I->W, !:V->I
satisfying the following equations (writing composition in diagrammatic order):
(i) nabla and ! make W a monoid; delta and ! make V a comonoid,
(ii) (Vxd) (nxV) = n delta = (delta x W)(Vxn) : VxW -> VxV,
(iii) (dxW)(Wxn) = nabla d = (Wxd)(nabla xV) ; WxW -> WxV,
(iv) (Vx!)n = 1 : V->V,
(v) d (Wx!) = 1: W->W.

Example A Frobenius algebra is a special case taking V=W, d=delta, n=nabla.

Example In the category of categories and bimodules consider a category V and its opposite W. Then
delta: V->VxV is the profunctor corresponding to the diagonal functor of V. That is,
delta(v1,(v2,v3))=Hom(v1,v2)xHom(v1,v3).
In this and the following Hom always means Hom in V. Then nabla:WxW->W is defined by
nabla((v1,v2),v3)=Hom(v3,v1)xHom(v3,v2),
n;VxW->V by
n((v1,v2),v3)=Hom(v1,v2)xHom(v1,v3),
d;W->WxV by
d(v1,(v2,v3))=Hom(v2,v1)xHom(v2,v3).
Finally !(*,v)={*} and !(v,*)={*}.

It is straightforward to check the equations, using the Yoneda lemma.

I want to prove the simple result, that V is the right adjoint of W. Then since in a symmetric monoidal category this implies that V is also the left adjoint of W, if we call W the dual of V, then the dual of the dual of V is V.

V is the right adjoint of W. Define eta to be (! d): I -> WxV and
epsilon to be (n !) : VxW -> I. We need to check the two triangular identities for adjunction.
The first: (Vx eta)(epsilon xV) = (Vx!)(Vxd)(nxV)(!xV)
= (Vx!)n delta (!xV)
= 1 1 =1 as requried.
The second triangular equation (eta x W)(W x epsilon) = (!xW)(dxW)(Wxn)(Wx!)
=(!xW)(nabla d)(Wx!) =1 1 =1.

Remark Just as there is graphical language for Frobenius algebras, there is a useful graphical language here. The difference is that the connectors between components have orientation.

Knots, groups, cospans and spans III

2011-02-17T00:04:00.000-08:00

This post is the third of a series, the first being In praise of composition: knot groups and cospans and the second Knots, groups, cospans and spans.

I want to give some details, and a slight extension to the remarks of the second post. In brief I will show how the Frobenius equations characterize the existence of inverses, and how the tensor product of Frobenius objects gives a semi-direct product of groups.

The starting point is a group in a category with finite limits, but let's just think of the category of sets and functions, so that we are just talking about a usual group G.

In the previous posts I considered spans, but these are just generalized relations. To simplify I will consider here just relations, the composition of relations, the product of relations and so on. We will write a relation R from X to Y as R : X -|-> Y, the composition with S : Y -|-> Z as RS : X -|-> Z, the product of R with T : U -|-> V as RxT : XxU -|-> YxV, the opposite of R as R^ : Y-|-> X, a function f : X->Y considered as a relation as f : X-|-> Y, the identity relation as 1 : X-|-> X.

Turning back to the group G, the operations of multiplication m and identity e give rise to four relations (I a one point set)
m: GxG-|->G, e: I-|->G, m^:G-|->GxG, and e^:G-|->I which clearly satisfy the associative law (mx1)m=(1xm)m:GxGxG-|->G, the coassociative law G-|->GxGxG and identity and coidentity laws. But they also satisfy the laws introduced by Carboni and Walters in 1987 exactly studying relations, now called the Frobenius equations, namely
(1xm^)(mx1) = mm^ = (m^x1)(1xm): GxG -|-> GxG.

I did not mention so far the operation of inverse in the group. So all the definitions of the last paragraph could be made just for a monoid. However the Frobenius equations are then satisfied if and only if the monoid is a group.

Let's see why that is true. Call the three relations equated above R, S, and T respectively. Then
(x,y)R(z,w) if there exists a u in G such that x=zu (ie x=m(z,u)) and uy=w. If the monoid is a group this is equivalent to equations inverse(z) x=w inverse(y), that is, xy=zw. But this is exactly the second relation. So a group satisfies the Frobenius equations.

For the converse, suppose only that G is a monoid and that the Frobenius equations are satisfied. Then R=S means that there exists a u such that x=zu and uy=w if and only if xy=zw. Put x=e=w the identity of the monoid and y=z. Clearly xy=zw(= y=z). Hence there exists a u in G such that zu=1=uz.

Next we want to discuss commutativity. The group G was not assumed commutative but in a certain twisted sense in the category of relations the Frobenius operations of a group are commutative. To say an operation m is commutative we usually say that m composed with the twist operation (x,y) |-> (y,x) is the same as m (that is m(y,x)=m(x,y)). But there is an unusual twist operation GxG -|-> GxG, namely the function twist: ((x,y) |-> (xy inverse(x) , x). One sees immediately that
m(twist(x,y))=m(xy inverse(x)x)=m(x,y). So in this twisted sense G is commutative and also cocommutative. (It was exactly this twist that was used by Artin to represent braids.) This "braid-twist" satisfies the equations satisfied by the transposition permutation except that it is not its own inverse.

Now it is a general fact that the (tensor) product of two Frobenius algebras in the presence of such a braid-twist has also the structure of a Frobenius algebra. So GxG has an induced Frobenius operations (written, I hope without confusion, also as m and m^) defined as follows:
m=(1x twist x 1)(m x m): (GxG)x(GxG)-|->GxG.
In more elementary terms this is:
m((x,y), (z,w))=(xyz inverse(y),yw), the multiplication of a semidirect product of G with G.

Kirchhoff's law I have mentioned in the second post an example involving invariants of knots. I hinted in the first post at connections with electric circuit theory, discussed in P. Katis, N. Sabadini, R.F.C. Walters, On the algebra of systems with feedback & boundary, Rendiconti del Circolo Matematico di Palermo Serie II, Suppl. 63 (2000), 123-156. Notice that taking the group G to be the real numbers the component m^ : G -|-> GxG is the fanning out of a wire into two, satisfying the Kirchhoff law for currents, and m is the corresponding joining of two wires. Repeated use of m and m^ can describe any Kirkhoff connector. Since the reals are commutative the braid-twist is the usual twist.

Mathematical economics - double-entry bookkeeping

2011-02-16T07:34:00.000-08:00

I want to talk a little about a mathematical description of accounting rather than economics in general. When I was making the move from Australia to Italy, which I finally did in 1998, I had some particular trouble understanding my financial resources. I thought about the method of keeping accounts introduced in Italy, and first described by Luca Pacioli in 1494, called double-entry bookkeeping or partita doppia.

It seemed very closely related to the work we had been doing on compositional concurrent systems using the compact closed bicategory of spans of graphs, so in 1997 I spoke at New Trends in Semantics in Bologna, and in 1998 we wrote a paper about partita doppia which was accepted by TAC subject to revisions which we never carried out. Much later (2008) I did make this paper available on arxiv, but in the mean time we had written about accounts in the published paper P. Katis, N. Sabadini, R.F.C. Walters, On the algebra of systems with feedback & boundary, Rendiconti del Circolo Matematico di Palermo Serie II, Suppl. 63 (2000), 123-156. We had also published a paper giving some details of the mathematical structure involved, namely P. Katis, R.F.C. Walters, The compact closed bicategory of left adjoints, Math. Proc. Camb. Phil. Soc., 130, 77-87, 2001.
This all came back to mind since I happened by chance on a blog by John Baez on Mathematical Economics dated January 8, 2011. He mentions that a student of his, Miguel Carrión Álvarez, had moved to economics after his PhD in physics, and he quotes Álvarez as follows:
"I believe the proper way to look at macroeconomics is as a flow network and as such ideas from category theory may be useful at least to organize one’s thinking. The economy is a network whose nodes are “agents” and links are “economic relations”. Economic relations are flows, of goods and services in one direction and of money in the other direction (opposite categories via arrow reversal?).
Each node also has a balance sheet: assets and liabilities, andit’s the liabilities that are the key here, because they are mostly monetary." You can find the rest here.
In the comments that followed this post our paper in arxiv was mentioned rather critically - the fact that the title was "On partita doppia" was clearly viewed as an affectation. Perhaps so. I was trying to emphasize the historical origins. Our introduction begins:
In 1494 Fra Luca Pacioli published in Venice one of the first printed mathematical books. One section, Computis e Scripturis, is the first published description of partita doppia or double-entry bookkeeping, the foundation of accounting. Double-entry bookkeeping had been developed over a period of years by Italian merchants and bankers. The aim of accounting is the measurement of a distributed concurrent system, and it is our contention that it is one of the earliest and most successful mathematical theories of concurrency.
The other criticism by Baez was the lack of some higher categorical definitions. His criticism is partially justified - the abstract formal notions and their applications were developed slowly by a handful of mathematicians - but in any case he seems to be unaware of Cambridge Philosophical Society paper mentioned above.
I finish this post by recommending to Álvarez these old papers. I think they make some progress in the direction he also is considering. (I should not omit mentioning that in concurrency theory the use of (compact closed) monoidal categories is well-known beginning with David Benson in the 70's, then Montanari and Meseguer 1990, and later Samson Abramsky among others, and of course our work.)

Knots, groups, cospans and spans

2011-02-11T02:50:00.000-08:00

In the last few days I have clarified the ideas described in the last post (partially responding to objections by Aurelio Carboni), introducing further structure which John Armstrong does not seem to have noticed.

The clarification which I will describe makes evident that the two invariants described by John Armstrong (i) the fundamental group of (the complement of) a knot, and (ii) the number of colourings of a knot, are both examples of a single phenomenon, and both can be extended beyond tangles.

The abstract context is this: consider a group object G in a category C with finite limits. In case (i) the group is the free group on one generator which has a group structure in the dual of the category of (finitely presented) groups. In case (ii) the group object is any group in Sets.
Then consider the full subcategory Sp(C,G) of Span(C) whose objects are the powers of G.

This category Sp(C,G) has the obvious monoidal structure arising from products, but a subcategory has a braiding different from the usual symmetry arising from conjugation in the group G. The braiding is GxG <- GxG->GxG, where the first arrow is the identity and the second (x,y) |-> (y, inverse(y)xy). (9/3/2011: Notice that in the original post I claimed that this was a braiding for the whole of Sp(C,G) but the braiding is natural only for a subcategory: the error was pointed out by Aurelio Carboni.)

In addition the object G has a Frobenius algebra structure which is braided commutative (both multiplication and comultiplication).

The mutiplication of G in Sp(C,G) is GxG <- GxG -> G, the first arrow being the identity, and the second is multiplication of G in C. The identity of G in Sp(C,G) is I <- I -> G the second arrow being the identity of G in C. The comultiplication and coidentity in Sp(C,G) are just the transposes of the multiplication and identity in Sp(C,G).
The equations for a Frobenius algebra, first introduced by Carboni and Walters in 1987, are easily checked - note they require that G be a group. The operations are braided-symmetric. (Notice that Span(C) has also quite different Frobenius algebra structures on the objects arising from the diagonal map and projection, which was the structure studied 1987 on relations.)

As a consequence the subcategory of Sp(C,G) is self-dual compact closed and braided, and the braiding goes well with the compact closed structure, so tangles may be represented there.

The calculation of the fundamental group of the (complement of the) trefoil correspond to the case in which G is the free group on one generator in the dual of groups. If instead the letters in the diagrams had been elements of a group in Sets the limit of the diagram (the subset of a power of the group satisfying the equations) is the number of colourings of the trefoil. The limit may also be calculated by the expression in Span.

In praise of composition: knot groups and cospans

2011-01-27T08:09:00.000-08:00

I have been thinking about knots recently. The context is our work (with Sabadini, Katis, Rosebrugh etc) since 1997 ([1]) in using the tensor and composition in categories of spans and cospans to describe "evolving nets of automata" - the most recent paper being [4]. After these thoughts I noticed that the main idea of this post, seen somewhat differently, has already been discovered by John Armstrong (see below). It could easily be also in other works, for example Yetter's book on Functorial Knot Theory (I don't have a copy).

The idea is to see a knot as a system composed from parts. Let's look at the trefoil:

The components which we wish to use to build knots are the following:

I am going to call these components C, Z, S and D respectively (chosen for a vague resemblance with the geometry). If I draw these as boxes rather than wires I get a picture for the trefoil that looks like a circuit diagram:

Now to calculate the knot group of the trefoil we label all the edges of the circuit with distinct letters, and the components with equations which relate the letters on the adjacent wires with the following result:

By looking at particular C,D,Z,and S components in this picture one can see the rule for assigning equations.
Finally, the knot group is the free group on all the letters quotiented by the equations.
In the case of the trefoil, if we express all the letters in terms of "a" and "e" the equations reduce to one equation, namely "aea=eae", so the knot group is ‹ a,e; aea=eae› .

Notice the resemblance to, for example, analogue circuit diagrams where we associate voltages and currents to the wires and differential equations to the components (see [3,4])

So what are we doing here? The letters on the wires entering (or leaving a component) may be thought of as the generators of a free group. The equation in the middle of a component may be thought of a the quotient of the coproduct of the input and output free groups defined by the relations. So a component is a cospan of groups between free groups. The whole diagram is a tensor diagram in Groups (the tensor being +) and the knot group is its tensor colimit as described in [2]. As described in [2] this colimit may be calculated by evaluating an expression in the monoidal category of cospans of groups.

For the trefoil, the expression is (C+C)*(1+S+1)*(1+1+Z)*(1+S+1)*(D+D) (+ means coproduct, * means composition).
Notice that a cospan of groups is assigned to any meaningful expression, that is to any tangle, not just to closed knots. The cospan corresponding to a braid is Artin's representation of a braid as an automorphism of a free group.

One of the motives for these thoughts were the remarks I made in an earlier post that graphical languages should be studied not only at the syntactical level, or the topological level but in terms of semantic categories like cospan(multigraphs/G) (see [2]). I wanted to be able to model the hardware in my office with the tangle of wires connecting.

A technical matter I did not mention is that the category whose objects are finite sets, and whose arrows are cospans of groups between the free groups on these sets, has a subcategory with a braided monoidal structure, with a self dual structure on the objects, which I more or less described, but is quite different from the usual one we use on cospan(C) for C a category with finite colimits. (9/3/2011: Notice that in the original posting I claimed erroneously that the whole of the category was braided monoidal - the error was pointed out to me by Aurelio Carboni).

I almost forgot to explain the title. The advantage of the algebraic expression in cospan(groups) is that it is an open expression which may be evaluated and composed repeatedly. To deal only with knots or the closure of braids is like writing an operating system as a straight line program with a loop only at the end. It could be done (a theorem of Kleene) but it would be a crazy exercize. Programs are written by nested loops.

Coming back to John Armstrong. By googling cospans and knots I found two papers: one, The Extension of Knot Groups to Tangles [6], in which he defines topologically a cospan of groups to a tangle (he seems to have re-invented cospans himself for the purpose); the other [7] in which he describes algebraically a cospan of quandles to a tangle. (I don't feel so bad about not knowing John's work since he doesn't know about ours - a google search of cospans finds our papers on the second page. I guess we never figure in the n category cafe!)

I must admit that I haven't followed the enormous literature on the connection between geometry and monoidal categories even though I made some small contributions (i) with Carboni and Lawvere in 1983 - a lecture to the Sydney Category Seminar suggesting that symmetric monoidal categories should be thought of a categories with two monoidal structures analogously to the Eckmann-Hilton argument (Ross Street corrected this idea discovering braided monoidal categories with Andre Joyal) and (ii) the discovery with Carboni of the Frobenius equations in 1987.

[1] P. Katis, N. Sabadini, R.F.C. Walters, Span(Graph): an algebra of transition systems, Proceedings AMAST '97, SLNCS 1349, 322-336, 1997
[2] R. Rosebrugh, N. Sabadini, R.F.C. Walters, Calculating colimits compositionally, Montanari Festschrift, LNCS 5065, pp. 581–592, 2008.(also arXiv:0712.2525)
[3] L. de Francesco Albasini, N. Sabadini, R.F.C. Walters, Systems with discrete geometry, ART 2008, Analysing Reduction systems using Transition systems, 122--131, Forum, Udine, 2008.
[4] P. Katis, N. Sabadini, R.F.C. Walters, On the algebra of systems with feedback & boundary, Rendiconti del Circolo Matematico di Palermo Serie II, Suppl. 63 (2000), 123-156
[5] L. de Francesco Albasini, N. Sabadini, R.F.C. Walters, Cospans and spans of graphs: a categorical algebra for the sequential and parallel composition of discrete systems, arXiv:0909.4136
[6] John Armstrong, The Extension of Knot Groups to Tangles,http://arxiv.org/pdf/math/0509665
[7] John Armstrong, Categorifying Coloring Numbers, http://arxiv.org/pdf/0803.1642

Hard sciences

2011-01-27T03:06:00.000-08:00

Here in Como the hard sciences are said to be physics, chemistry and mathematics, but not computer science.

I have just been given a program by a student and I would like to know that it is correct. This is more difficult than writing a new program myself.

In mathematics instead it is usually much easier to be convinced of a proof than to construct a proof. Part of the reason is that mathematicians usually don't check a proof completely but try to find clues from the description and construct a proof themselves.

Reading a program and a proof are both difficult exercises. Proofs are usually deeper than programs, but verifying correctness, which is necessary with a program, is hard.

Added 2 February 2011 I have just seen this comment by William Thurston in an article (ON PROOF AND PROGRESS IN MATHEMATICS, BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY Volume 30, Number 2, April 1994, Pages 161-177)
"I have spent a fair amount of effort during periods of my career exploring mathematical questions by computer. In view of that experience, I was astonished to see the statement of Jaffe and Quinn that mathematics is extremely slow and arduous, and that it is arguably the most disciplined of all human activities. The standard of correctness and completeness necessary to get a computer program to work at all is a couple of orders of magnitude higher than the mathematical community’s standard of valid proofs. Nonetheless, large computer programs, even when they have been very carefully written and very carefully tested, always seem to have bugs."

Cultural differences

2011-01-27T02:58:00.000-08:00

Italian children are brought up with the saying "the end justifies the means". I was brought up in Australia with the opposite exhortation.

University news

2011-01-21T03:20:00.000-08:00

Reform The grand university reform of Mariastella Gelmini has passed into law by a whisker - immediately after a no-confidence motion passed by three votes. We are now waiting to see what effect this will have. Already many courses have closed including ours. The position of researcher has a significantly changed status and many are working to rule, putting courses in difficulty.

The fractal nature of politics I don't really mean fractal. I am referring to the fact that behaviour at a high level is reflected at a lower level.
I have rather studiously avoided talking about Italian politics even if it is one of the topics most discussed here. However the premier himself often refers to the fact that he is under siege, with the opposition including former allies.

At the University level, a president of a faculty, who pressured a previous president to resign, has publically asked the rector to resign. Now I hear rumours that he himself is under siege, with the opposition including former allies.

The good old days

2011-01-14T14:51:00.000-08:00

This phrase (or something like it) occurred in some discussions on the Categories List, in connection with a paper I wrote with Ross Street in 1978 (Yoneda structures). The comprehensive factorization of 1973 was also mentioned recently. I have also been asked if I have an electronic version of my PhD thesis of 1970. I had already decided to scan my unpublished MSc (1967) and PhD theses and put them on line.
Today I finished scanning the master's thesis and it is available at this address. It was written at the University of Queensland in the good old days, before anyone had completed a doctorate there, and research publication by staff members was a special event.

20 January 2011: I have now finished scanning my PhD thesis, and it is available here.

What is functional programming?

2010-11-26T04:07:00.000-08:00

In the early days of my interest in Computer Science (in the late 1980's), flushed with enthusiasm for the connections between Category Theory and Computer Science, I wrote a paper with that title. It was accepted for the first volume of a new journal, Mathematical Structures in Computer Science, and was promised even in the advertisements for the new journal. But then the editors had a change of heart and withdrew their acceptance. (I must find in my papers the letters.)
I accepted this rejection without a whimper because my ex student Mike Johnson was against the paper (or at least its title) and even I came to believe that I had been rather presumptuous (as I tend to be when I enter a new subject - see recently probability theory). I received further criticism later for my impudence from Phil Wadler when he visited us in Sydney. However I did include some hints about the idea in my book "Categories and Computer Science" in sections 5.5 and 6.2, under the modest title "The specification of functions".

I am persuaded to write more about the topic by the fact that, judging by exchanges on the categories mailing list, the average category theorist doesn't have any idea what functional programming is. The matter has not been well explained. Those who do know functional programming speak what seems to be a foreign language when they refer to it. In addition a functional programmer is likely to talk about the most advanced aspects, whereas it is possible to begin with very simple ideas. One of the striking advantages of category theory is that one can begin simply, already seeing part of the idea, and then add structure revealing more richness.
Don't be put off by the simplicity of my first remarks.

The very simplest version - Categories As one might imagine from the name functional programming regards the computation of functions. Consider the category Sets of sets and functions. We notice that there is an object I, a one point set, and an object N, the natural numbers, together with two functions o:I → N (zero) and s:N → N (the successor). We are interested to calculate the function f(x)=2x.
There are some equations this function satisfies namely fo=o and fs=ssf.
The graph of these two objects with the arrows o,s and f, together with the equations, form the generators and relations defining an abstract (syntactical) category which naturally has an induced functor to Sets taking s to successor, o to 0, the symbol f to the concrete doubling function f.
We can calculate in this syntactical category as follows:
fssso=ssfsso=ssssfso=ssssssfo=sssssso, which sequence of deductions is a calculation of the fact that f(2)=6.

So the program consists of the graph with objects I,N and arrows o,s,f ; the execution is the deduction fssso=ssfsso=ssssfso=ssssssfo=sssssso.

Let's make clearer what the programming language is, and what an execution is for this primitive language.

A program is a graph, and a finite number of equations u=v between paths in the graph. An execution of the program on a path is a sequence of deductions from the equations.

To be practical, we might modify the definitions slightly. Instead of equations take ordered equations (or rewrites) thus distinguishing between u=v and v=u (but possibly including both). Further an execution may only use the rewrites in the order u=>v given, and termination consists when the deduced path is irreducible.

With care a programmer can now organize that there are unique executions from paths in a desired set of paths, thus computing a function. If the programmer has in mind some actual functions which satisfy the equations then the correctness of the computation is clear. The more difficult things to manage are uniqueness of the result, the termination and the efficiency.

Remark What we have described is just traditional algebra, but applied to an algebra of functions. Suppose you want to calculate with numbers rather than functions. You notice they form a ring. You can talk about elements in a concrete ring by using symbols to describe some elements, forming the free ring to talk about other elements, and state equational properties. Then a calculation is a sequence of equational deductions. Example; (1+1)(1+1)=1(1+1)+1(1+1)=(1+1+1+1). The deductions may be made more efficient by ordering the equations.

The programming language above is very easy to implement; one just needs to program rewriting of words. There is a question as to how useful (as distinct from powerful) it is. Maybe with this amount of structure not much, but with a little more categorical structure we can really program. The resulting programs will resemble programs in Lisp.

Categories with products The category of Sets has finite products, and we would like to write programs to calculate such functions as addition :NxN → N, mutiplication, factorial and so on. More generally we would like to program functions on lists, and even program term rewriting itself, but for that see later.

I will tell you immediately what the programming language and its execution are. a program is a finite multigraph (in the sense of my book - that is, a set of objects, and a set of arrows each of which has as codomain an object but whose domain may be a finite product of objects) together with a finite number of (ordered) equations between terms (arrows in the free category with products on the multigraph). An execution starting with a term is a sequence of rewrites of the terms until arriving at an irreducible term.

I repeat: to write a program one should have in mind the particular functions in Sets one is describing and equations which involve them. It is all to easy to forget the semantics and end up in mindless symbol pushing. .

To see the strength of the language we will first write a program to calculate HCF : NxN → N starting with nothing. It will be clear from this example that such constructions as "while", "if then else", "sequence" can be programmed.

The objects in the multigraph are I and N as above. I will gradually be introducing new arrows into the multigraph, but the initial ones will be o : I → N, s : N → N and add : NxN → N (symbol for addition).

The first equations which will sufficient to calculate addition are:

add(s(x),y)=add(x,s(y))
add(o,y)=y.

An execution:
add(s(s(o)),s(o))=add(s(o),s(s(o)))=add(o,s(s(s(o))))=s(s(s(o))).

We don't need multiplication for calculating the GCD of two numbers but I will describe a program for it as an illustration (see also my post on tail recursion).

Adjoin to the multigraph two arrows mult : NxN → N and auxmult : NxNxN → N. For auxmult the function we have in mind is (m,n,p) → mn+p.

The further program equations which allow the computation of multiplication are:

auxmult(s(m),n,p)=auxmult(m,n,add(n,p))
auxmult(o,n,p)=p.
mult(m,n)=auxmult(m,n,o).

Now the algorithm I have in mind for GCD will require a Boolean test function, namely geq(m,n) – “greater than or equal”, and a partial function on NxN, namely minus. To deal with these it is convenient to introduce a new object M in the multigraph, to represent the set N+{true, false}. We will need an arrow i:N → M, j:M → N and two arrows true:I → M, false:I → M. The functions we have in mind are i(n)=n, and j(n)=n, j(true)=1, j(false)=0.

We adjoin an equation to relate the arrows into M with those in N:

j(i(n))=n
j(true)=s(o)
j(false)=o.

Now the function minus from NxN to M takes (m,n) to m-n if m is greater than or equal to n, otherwise minus(m,n)= false. We adjoin minus ; NxN → M to the multigraph. Its program is:

minus(m,o)=i(m)
minus(o,s(n))=false
minus(s(m),s(n))=minus(m,n).

We adjoin geq:MxN → M to the multigraph and the program:

geq(i(m),o)=true
geq(i(o),s(n))=false
geq(i(s(m)),s(n))=geq(i(m),n)
geq(false,n)=false
geq(true,n)=false.

Finally, the HCF of two natural numbers is defined using two new arrows in the multigraph, auxHCF: MxMxN → M, HCF : NxN → N. The function I have in mind for auxHCF takes (true,m,n) to HCF(m,n) if m ≥ n; takes (false, m,n) to HCF(m,n) if m < n; and is false for all other values.

auxHCF(true, i(m),s(n))=auxHCF(geq(minus(m,s(n)),s(n)),minus(m,s(n)),s(n))
auxHCF(false,i(m),n)=auxHCF(true,i(n),m)
auxHCF(true,i(m),o)=i(m).

HCF(m,n)=j(auxHCF(geq(i(m),n),i(m),n)).

Let's look at an execution, assuming that minus and geq execute correctly, and writing k for s^k(o).

HCF(6,9)=j(auxHCF(false,6,9))=j(auxHCF(true,9,6))=j(auxHCF(false,3,6))
=j(auxHCF(true,6,3))=j(auxHCF(true,3,3))=j(auxHCF(false,0,3))
=j(auxHCF(true,3,0))=j(i(3))=3.

Notice that I have not written down enough equations to calculate auxHCF(u,m,n) for all values of u,m,n, but enough to calculate HCF. I didn't say, but the value for HCF of (0,0) I have in mind is 0.

Remark It is obvious that adding more structure to the category (distributive, cartesian closed, ...) adds more linguistic mechanisms (if then else, higher order, ...) for writing programs. However the idea is already present here.
Notice another thing: programs can be written which may apply to different sets. For example, a sort algorithm may apply to many types of data. It can be written with unspecified objects and arrows, and later these may be identified with objects an arrows in another graph. I am saying that pushouts of graphs may be used to combine programs.
The same idea might be applied also to quite different semantic categories.

Remark Functional programming is sometimes promoted by saying that it is easier to check the correctness of such programs. That may be so if the programmer has in mind clearly all the functions involved. However if functional programming involves translating while loops into tail recursion it cannot be easier to check than the imperative program. Knowing the functions involved is like knowing invariants of imperative programs.

Lisp and stack overflow

2010-11-23T03:32:00.000-08:00

This semester I am teaching a course which over the years has had many names (Computational algebra, Symbolic computation, Categories and automata, etc, etc) but which is really my thoughts about relations between algebra and computer science. For some years I used Maple as an illustrative programming language, but it is expensive, and the faculty in Como has withdrawn support, closing the laboratory which had Maple installed a couple of years ago. So this year at the last moment I thought of using Common Lisp (Clisp). To be honest I am not a programmer though I have written programs in a large number of different languages but not in Lisp.
Perhaps strangely for a category theorist I have always been rather negative towards functional style programming.
As a first example, I wrote the following informally described programs (in which o is just a symbol):

add(successor(x),y)=successor(add(x,y))
add(o, y)=y;

multiply(successor(x),y)=add(multiply(x,y),y)
multiply(o,y)= o;

factorial(successor(x))=multiply(successor(x),factorial(x))
factorial(o)=successor(o).

I was surprised that with these programs I could calculate at most factorial(7) without stack overflow (by 7 I mean of course successor(successor(...o)))))))). I would have thought that a language based on recursion would support recursion to the limit of the memory of the machine. (My first effort with a language or a machine is to try to break it, but this was too easy.)

Reading further about Lisp I realised that you are supposed to write not general recusion but "tail recursion".
Tail recursion is really just "while". I would like to give an explanation of tail recursion in terms of the Elgot automata we introduced in the paper P. Katis, N. Sabadini, R.F.C. Walters, Bicategories of processes. Journal of Pure and Appled Algebra, 115:141-178, 1997.

An Elgot automaton is a function g : X + U → U + Y (where + means disjoint union). The partial function fun(g) : X → Y computed by g is defined as follows: given x in X apply g repeatedly until the result lies in Y. The result, if it exists is then fun(g)(x).
Notice that g can be broken into two parts: g1 : X → U + Y and g2 : U →U + Y; g1 is an initialization step and g2 is an iteration step.

Let us look at an example, namely calculating factorial given multiplication.
Take X=N the natural numbers. Take U=NxN, and take Y=N.
The initialization step g1: n → (n,1) in NxN.
The iteration step g2 : NxN → NxN + N is defined by (n,p) → (n-1, p*n) if n>0, else (0.p) → p.
Clearly the function fun(g) calculated by the Elgot automaton g is factorial; this is a usual imperative program for factorial.

Going back to the general Elgot automata, notice that g2 defines a partial function also, from U to Y, namely the result of iterating g2 on the whole of U. Calling this "auxiliary" partial function auxfun(g) it is clear that fun(g) = (auxfun(g) | 1Y) • g1. But also the auxiliary function satisfies a fixed point equation, namely that
auxfun(g)(u)=auxfun(g)(g2(u))
since in a computation of auxfun(g)(u) (iterating g2) all the values passed through arrive (if they arrive at all) in the same value auxfun(g)(u).

In the example above of the program for factorial the auxiliary function is easily seen (by iterating g2) to be
(n,p) → (0, factorial(n)*p).

This equation auxfun(g)(u)=auxfun(g)(g2(u)) may be taken to be a recursive program for auxfun, and then fun(g) is a composite. A recursive evaluation consists in the steps
auxfun(g)(u)=auxfun(g)(g2(u))=auxfun(g)(g2(g2(u))=auxfun(g)(g2(g2(g2(u)))= ... until a value which would land in Y arrives. This is tail recursion - it involves only one application of auxfun.

The idea then is this: to do tail recursion think of a calculation using iteration. This involves introducing new state (U), initializing (g1) and also an auxiliary function (g2). The function you wish to calculate then is a composition of the initialization and the tail recursion of the auxiliary function.

Let us write tail recursive programs for addition, multiplication and factorial.

Addition
For addition there is no need to introduce new state. The internal state is NxN, the same as the domain of addition. The iterative step is (m,n) → (m-1,n+1) with exit when the first variable is 0.
Hence the recursive definition of and is:

Add(o,y)=y
Add(successor(x),y)=Add(x,successor(y)).

Multiplication
For multiplication the iterative program introduces a new variable p.
The initialization is (x,y) → (x,y,o).
The iterative step is (x,y,p) → (x-1,y, p+y).
Exit is (o,y,p) → p.

The auxiliary function auxMultiply is (x,y,p) → x*y+p.

The recursive program for auxMuliply is:

auxMultiply(o,y,p)=p
auxMultiply(s(x),y,p)=auxMultiply(x,y,Add(p,y))

Then
Multiply(x,y)=auxMultiply(x,y,o).

Factorial
For calculating factorial(x) by iteration one introduces a new variable p.
The initialization is x → (x,1).
The iterative step is (x,p) → (x-1,x*p).
The exit is (o,p) → p.

The auxiliary function auxFactorial is (x,p) → (factorial(x)*p).
The recursive program for auxFactorial is:

auxFactorial(o,p)=p
auxFactorial(s(x),p)=auxFactorial(x,s(x)*p).

Then
Factorial(x)=auxFactorial(x,1).

Remark The Elgot automata form the arrows of a symmetric monoidal category with feedback with delay. In fact they are a case of a general construction for universally adding such feedback with delay to a symmetric monoidal category (see P. Katis, N. Sabadini, R.F.C. Walters, Feedback, trace and fixed-point semantics , Theoret. Informatics Appl. 36:181-194 (2002)). The product monoidal structure on Sets gives Mealy automata, variations of which are being studied for application to circuits by Miklos Bartha. There are close relations with the work of Joyal, Street and Verity on traced monoidal categories.

Remark The idea of McCarthy to form a language with a data type (s-expressions) so that programs become data, plus the idea that programs should be equational (recursive) definition of functions makes a very interesting language. However I remain convinced that the object of programming is not just to describe functions but instead systems and their composition.

Banditismo e prepotenza

2010-11-23T02:55:00.000-08:00

The parish journal of the village where I live has, in addition to the usual announcements of baptisms and communions, a section written by some local historians called "Banditismo e prepotenza" on the banks of the Adda. It has stories about arguments and murders in the 16th century and the efforts of Carlo Borromeo to create order. There is a statue of San Carlo in the centre of the village which last Christmas was adorned with a Santa Claus hat.
Despite San Carlo's efforts banditismo and prepotenza are alive and well at all levels of Italian life. Certain colleagues have taught me about it at university level and the newspapers write about it at much higher levels.
There is so much I could mention that in fact I have writer's block.
I have decided I have said enough about such negative matters, so from now on I will write about mathematics and computer science, and enjoy the pleasures of Italian life, which are many.

Strumentalizzazione

2010-10-26T03:03:00.000-07:00

One may learn about Italy by studying the words in Italian which don't quite correspond to their English alternatives. Sistemare is an example, which I may discuss on another occasion. If I ever grasp the meaning of word intendere I will write about it. Today's word however is strumentalizzare.
What it means is to make someone or something a tool to be used for another purpose.

I don't know an English word that means exactly this.

The word is used quite frequently in such phrases as "I see that I have been strumentalizzato", or "this matter should not be strumentalizzata".

I see constant use of the concept. For example, the following is quite common. Group A is complaining about a problem without understanding the cause. Group B, who secretly were responsible for the problem, use the distress of Group A to further disadvantage Group A. It is not even necessary that Group B hide their actions; it is sufficient to lie about them.

Any Italian reading this will immediately recognize examples, but actually the matter comes to mind in thinking about posts to this blog. I am concerned that in making criticisms I may be misquoted or misread.

For example, some time ago I made the assertion in this blog that we were creating too many mathematicians. I would not like my comments to be strumentalizzati against mathematics.

I was not criticizing mathematics or mathematicians in general, just making a comment about the prospects for employment doing research in mathematics. Many students do PhD degrees with that in mind. Supervisors are happy to have graduate students. The reality is that the most common paid employment of mathematicians is in teaching. It is what I have been paid to do all my life. Even university mathematics departments justify their existence by their service teaching role.

The problem is that in Italy at the moment there are very few positions for teaching mathematics in the schools. Many students who do PhD's do not want to teach in the schools. There are also very few positions in the universities. There may be particular Italian aspects of this problem but judging from Peter Woit's blog the situation in the United States in the universities is similar.

The odd thing about the Science faculty in Como is that it was created without a service teaching role. It is difficult to justify the employment of 80 staff with a new enrolment of more or less 80 students. The faculty must be justified as a research institute which principally exists for the staff, not for the students.

I guess this whole post might be construed as a criticism of Italy. It is not.

Stephen L. Bloom

2010-10-13T04:01:00.000-07:00

It has been a great sadness to us to learn that our good friend and collaborator Steve Bloom died on 11th October. He had been sick for some time. We would like to express our sympathy to his wife Cynthia Graae, daughters Valeria and Paula Bloom and his brother Peter Bloom.

We will always remember his intelligence and humour and the good times we had with him in Sydney and Italy. We will plant a tree at our mountain house in Roncola in his memory.

Bob and Nicoletta

Old post: Why are we concerned? F.W. Lawvere

2010-10-06T01:21:00.000-07:00

This is an old post of Friday, March 31, 2006 taken from the Categories mailing list.

F.W. Lawvere: WHY ARE WE CONCERNED? I
Categories Mailing List
Sun, 26 Mar 2006 16:43:31 -0500 (EST)

WHY ARE WE CONCERNED? I
When Saunders Mac Lane penned his hard-hitting 1997 Synthese article, he was defending mathematics from an attack many of us hoped would just go away. But Saunders was aware of the seriousness of the threat, which indeed is still here with greater determination. Although the title of that article was "Despite physicists, proof is essential in mathematics", he was not opposing physics, nor even that immediate handful who, assuming the mantle of "mathematical physicists", gave themselves license to insult generations of scrupulously serious physicists and to demand that mathematics adopt a culture that considers conjecture as nearly-established truth. In essence it was an attack on science itself, as the highest form of knowing, that Saunders was opposing.
The increased determination of that attack is expressed in two ways. To equip and organize the attack, finance capital has set up several institutions, some of which rather openly proclaim their goal of submitting science to the service of medieval obscurantism. Others say that they support mathematical research, but encourage a barrage of "popular" writings to shock and awe the public into continuing in the belief that they will never understand mathematics and hence never be able to actively participate in science.
The contempt for Mac Lane's fight, recently expressed in articles supposedly memorializing him, takes the form of the claim that category theory itself is a "cool" instrument for deepening obscurantism. Not only Harvard's "When is one thing equal to another thing?" and the Cambridge "morality" muddle, but also a 2003 article aimed at teachers of undergraduates, quite explicitly support that claim. In the MAA Monthly, a Clay Fellow states as fact that category theory "is mathematics with the substance removed". Mastering the technique of disinformation whereby the readers are first told that now finally they will be informed, the article suggests that some raising of the level of understanding of the relationship between space and intensively variable quantity is going to be achieved. Then the author short-circuits any such understanding via the simplifying assumption that omits the distinction between covariant and contravariant functors as "unwieldy". As final display of the mastery of expositional technique, the categorical object which has, for nearly twenty pages, been heralded as simple, is revealed in the final pages in
the most complicated and unexplained form possible. (Totally passed over is the issue that had led Grothendieck to the considerations allegedly being treated: not only the category of affine schemes, but also the category of all its presheaves, where the author implicitly wants us to work, fails to have the geometrically correct colimits needed to define projective space.)
Another level of attack was launched when Cornell University was given very large sums of money to develop methods of teaching geometry without mentioning any geometrical concepts. No proof of the desirability of such a draconian excising of content needed to be given, beyond some phrases from the Dalai Lama.
"Dumbing down" is an attack not only on school children and on undergraduates, but also one taking measured aim at colleagues in adjacent fields and at the general public. The general public is thirsty for genuinely informational articles to replace the science fiction gruel served constantly by journals like the Scientific American and the New York Times "Science" section. Those journals have never published anything resembling a mathematical proof and hence have rarely actually explained any scientific subject in a usable way. Nor have they even undertaken any program to raise the level of knowledge of calculus or linear algebra among their readers in a way which would make such explanations feasible. Instead, they provide games and amusements to divert the mathematically-interested public.
In January of 2005 the Notices of the AMS announced that they had for a full ten years been strictly following a certain editorial policy. There had been a widespread demand for expository articles. To that demand, the response was a new definition of "expository": all precise definitions of mathematical concepts must be eliminated. Authors of expository articles were forced to compromise their presentation, or to withdraw their paper. Mathematicians, who were for several years becoming aware that these new expository articles are absolutely useless for developing a mathematical thought, were shocked to learn that a conscious policy had forced that situation.
A peculiar sort of anti-authoritarianism seems to be the only justification offered for degrading the role of definition, theorem, and proof; certainly, serious expositors have never considered that the use of those three pillars of geometrical enlightenment excludes explanations and examples. Others have urged, however, that those instruments be eliminated even from lectures at meetings and from professional papers.
That threat is part of the background for the concern expressed in the many messages to the categories list over the past weeks. Deeply concerned mathematicians ask me "How can we know?". Indeed, how can we know whether it is worthwhile to attend a certain meeting or a certain talk, and how can a scientific committee know whether a proposed talk is scientifically viable? If the "you don't want to know" culture of no proofs, no definitions, is accepted, we will truly have no way of knowing, and will be pressured to fall back on unsupported faith.

************************************************************
F. William Lawvere
Mathematics Department, State University of New York
244 Mathematics Building, Buffalo, N.Y. 14260-2900 USA
Tel. 716-645-6284
HOMEPAGE: http://www.acsu.buffalo.edu/~wlawvere
************************************************************

F. William Lawvere: WHY ARE WE CONCERNED? II
Categories Mailing List
Tue, 28 Mar 2006 21:30:59 -0500 (EST)

WHY ARE WE CONCERNED? II

Misconceptions

The question is not whether mathematics should be applied. Most of us agree that it should. The concern is rather that our subject is sometimes being used as a mystifying smoke screen to protect pseudo-applications against the scrutiny of the general public and of the scientific colleagues in adjacent disciplines. We need to ensure that applications themselves be maximally effective, not clouded by misunderstanding.

Some of the most important applications of our unifying efforts as categorists have been to the
teaching of algebraic topology
teaching of algebraic geometry
teaching of logic and set theory
teaching of differential geometry
These subjects all arose from the efforts to clarify and apply calculus; thus some of us have applied category theory to the teaching of calculus.

But it seems that we have not taught category theory itself well enough. Several recent writings reveal that basic misunderstandings about category theory are still prevalent, even among people who use it. Some of these concern the myth that category theory is the "insubstantial part" of mathematics and that it heralds an era when precise axioms are no longer needed. (Other myths revolve around the false belief that there are "size problems" if one tries to do category theory in a way harmonious with the standard practice of professional set theorists; see next posting.) The first of these misunderstandings is connected with taking seriously the
jest "sets without elements". The traditions of algebraic geometry and of category theory are completely compatible about elements, as I now show.

Contrary to Fregean rigidity, in mathematics we never use "properties" that are defined on the universe of "everything". There is the "universe of discourse" principle which is very important: for example, any given group, (or any given topological space, etc.) acts as a universe of discourse. As these examples suggest, a universe of discourse typically carries a structure which permits interesting properties and constructions on it. As the examples also show, there are typically many objects of a given mathematical category and also many categories, so transformation is an essential part of the content. As quantity includes zero, so structure includes the case of no structure, which Cantor considered one of his most profound and exciting discoveries. (His conjecture that the continuum hypothesis holds in that realm is probably true. [Bulletin of Symbolic Logic 9 (2003) 213-223].) Dedekind, Hausdorff, and most of 20th century mathematics followed the paradigm whereby structures have two aspects, a theory and an interpretation of it in such a featureless background. Because the background thus contributes minimal
distortion to the assumptions of the theory, the completeness theorems of first-order logic, the Nullstellensatz, and related results are available. The more geometric background categories which receive models are also viewed as structures (of an opposite kind) in abstract sets, for example the classifying topos for local rings as a background for algebraic groups. Such is "set theory" in the practice of mathematics; it is part of the essence from which organization emerges.

By contrast, the "set theory" studied by 20th century set theorists has a different aim and architecture. The aim is "justification" of mathematics, and the architecture is that of the cumulative hierarchy. The alleged need for justification arose in connection with the re-naming of Cantor's theorem as "Russell's paradox"; Cantor's theorem had shown that the system proposed by Frege was inconsistent, but there were those who dreamed nonetheless of restoring that rigidity. There was a bitter controversy between Cantor and Frege, and Zermelo swore allegiance to
Frege [Cantor G.: Abhandlungen mathematischen und philosophischen Inhalts, 1966, page 441, remarks of Zermelo on Cantor's 1884 review of Frege]. Von Neumann based himself on Zermelo and made explicit the cumulative hierarchy, which Bernays and Goedel used and which many subsequent set theorists presumed was the only architecture to be studied. The justificational aspect stems from the supposed construction of the hierarchy by a bizarre parody of ordinary iteration, parameterized by infinite ordinal numbers (Cantor's third discovery), entities which from the point of view of ordinary mathematics are even more in need of
justification than the analysis that supposedly needed it. (Indeed, in attempting to describe what these alleged infinite ordinals are and do, people often resort to stories about gods and demons.) Little or no progress has been made on this "justification" problem in a century, but work with the hierarchy has produced some knowledge about the possibilities for categories of sets. By adopting a standard definition of map and discarding the mock iteration (with its concomitant complicated structure), each model of the cumulative hierarchy yields a category of
abstract nearly featureless sets; most of the usual set-theoretical issues depend only on the mere category: measurable cardinals, Goedel-constructibility, the continuum hypothesis, etc.

Having thus briefly understood the two visions which are called set theory

(1) a category of Cantorian featureless sets which serves as the background recipient for the structures of algebra, geometry and analysis;

(2) the cumulative hierarchy with its rigid Fregean structure aiming to justify mathematics,

it is not surprising that the precise nature of the elementhood relations appropriate to each are quite different. While the Fregean image involves rigid inclusion and elementhood relations imagined to be given once and for all for mathematics as a whole, the usual mathematical practice instead considers inclusion and membership relations for subsets of a given universe of discourse (such as R^3). Thanks to Grothendieck's Tohoku observation, these mathematical local belonging relations are well globalized within the notion of category, whose primitives are domain, codomain, identity, and composition.

[The notion of category is a simple first-order theory of a semi-algebraic kind. It has myriads of interpretations, some in "classes", some "locally small" etc., but such undefined restrictions on interpretations have nothing to do with the notion of category per se. Many properties are best expressed within the first-order theory itself.]

Composition is a kind of non-commutative multiplication, hence there are two kinds of division problems. In any category, given any two morphisms a and b we can ask whether there exists a morphism p such that a = bp; if so, we may say that a belongs to b. This forces a and b to have as codomain the same object, which serves as their common universe of discourse. (The dual relation, f determines g, defined by "there exists m with mf = g", is probably equally important in mathematics.) There are two special cases of this belonging relation which are of special interest. First we say that b is a part (or subset in the case of a category of sets) of its codomain, if for all a belonging to b, the proof p of that belonging is unique; this is immediately seen to be equivalent to the usual notion of monomorphism. Then, if a and b are parts of the same object, we say a included in b iff a belongs to b. Any arbitrary morphism x with codomain X may be considered an element of X in the sense of Volterra (also known as a figure in X); we say that x is a member of b iff x belongs to b. Then clearly

a is included in b iff for all x, if x is a member of a, then x is a member of b.

The usual relationship between these two relations is thus maintained. Because in category theory the domain relation is as important as the codomain relation, we can be more precise about elements: very often it is appropriate to consider a special property of objects, and restrict the term element (or figure) to elements whose domain has that property, that is, to figures whose shape has the property. For example, in algebraic geometry the connected separable objects are appropriate domains for the figures known as "points"; in the algebraically closed case it suffices to consider elements with domain a terminal object 1 as points. On the other
hand, frequently it is of interest to choose a small class of figure shapes which generates in the sense of Grothendieck, i.e. so that the above equivalence between inclusion and universal implication of memberships holds even when the figures x are restricted to those of the prescribed shapes. A basic property of categories of Cantorian sets is that this holds with x restricted to those with terminal domain 1. In algebraic geometry, the figures whose domains have trivial cohomology are adequate. Note that if f is a morphism from A to B and if x is an element of A, then fx is an element of B of the same shape (of course in general figures are singular in that they distort their shape, for example, fx may be more singular than the figure x). Properties of x in A may be quite different from the properies of fx in B.

The mysterious distinction between x and singleton(x) in the hierarchical Frege architecture takes quite a different form in the categorical architecture where there is a natural transformation from the identity functor to the covariant power set functor; this natural transformation can be called singleton: singleton(x) is simply x considered as a special element of PX, rather than of the original X.

Professors may not consider the possibility of learning from undergraduate text books, and some may feel bored that I have once again repeated the above basic definitions and observations. But if these basics were widely understood among algebraic geometers, perhaps misconceptions like "category theory is the insubstantial part of mathematics" would not have arisen. (As we know from experience, all of the substance of mathematics can be fully expressed in categories.) Perhaps the general term "A-points" for arbitrary rings A was confusing. "Spec(A)-shaped figures" is a more accurate rendering of Volterra's "elements"; that could be abbreviated to "A-figures", but points are in some sense special among figures. On the other hand, we often vary the background category, so that alternative terminology might involve passing from a category E to
E/spec(A), and restricting the notion of "point" in any category to mean figure of terminal shape; then the A-figures become, on pulling back to the new category, literally "moving points".

Whatever the particular chosen terminology, the important conclusion is to actively eliminate the mythology that spaces in categories have no elements, because as we see, this mythology obscures the simplicity of certain matters and thus provides a bogus basis for insulating one field of mathematics from another.

[The belonging relation is just the poset collapse of the categories E/X, whose actual maps serve as incidence relations, especially between figures in X. Thus every category E supports a certain geometrical imagery wherein all maps are geometrically continuous, in that they map figures to figures without tearing the incidence relations. Precise axioms about E are a key to further progress because they explicitly sum up and guide our experience with the objects and maps in E.]

************************************************************
F. William Lawvere
Mathematics Department, State University of New York
244 Mathematics Building, Buffalo, N.Y. 14260-2900 USA
Tel. 716-645-6284
HOMEPAGE: http://www.acsu.buffalo.edu/~wlawvere
************************************************************

F. William Lawvere: WHY ARE WE CONCERNED? III
Categories Mailing List
Date: Fri, 31 Mar 2006 09:15:28 -0500 (EST)

The second main misconception about category theory

Part of the perception that category theory is "foundations" (in the pejorative sense of being remote from applications and development) is due to a preoccupation with huge size. Since such perceptions hold back the learning of category theory, and hence facilitate its misuse as a mystifying shield, they are among our concerns. We need to deal with the size preoccupation head on.

Experience has shown that we cannot build up or construct mathematical concepts from nothing. On the contrary, centuries of experience become concentrated in concepts such as "there must be a group of all rotations" and we then place ourselves conceptually within that creation; we state succinctly the properties which that creation as a structure seems to have, and then develop rigorously the consequences of those properties taken as axioms. The notion of category arose in that way, and in turn serves as a powerful instrument for guiding further such developments. Placing ourselves conceptually within the metacategory of categories, we routinely make use of the leap which idealizes the category of all finite sets as an object. The question is, what more? Of course we make use of the experience of those who have labored to justify mathematics, and it is fortunate that ultimately our results are compatible with theirs. (Mac Lane's use of the term metacategory is not
mysterious; it simply refers to the universe of discourse of any model, in the special context where the elements of such a model are themselves called categories and functors. In the spirit of algebra, we do not concentrate on the cumulative hierarchy which might have been used to present the metacategory, but rather on the mathematical category itself.)

The supposed size problems of category theory are often concentrated in functor category formation. For any two categories that are objects of the metacategory, the category of functors from one to the other exists in the sense that it also is an object in the metacategory (it is unique by exponential adjointness). That existence statement is compatible with standard set theory, although it is often presumed to be
incompatible.

In the original 1945 exposition of category theory, it was the Goedel-Bernays account of the cumulative hierarchy (see posting II) that was cited as probably relevant (in case the problem of justifying category theory should come up). As a result, category theorists have been worried about supposed "illegitimacies" that might arise from violating the Goedel-Bernays rules (which in essence stemmed from von Neumann). These rules expressed an expediency which was a very effective trick at the time, identifying two kinds of membership relation and truncating the
content at a plausible level. The Goedel-Bernays theory is well known to have the same logical strength as the Zermelo-Fraenkel system. An important advantage is that the greater expressive power of Goedel-Bernays permits it to be finitely axiomatizable, whereas Zermelo-Fraenkel is not; the greater expressive power concerns an element V of any model in which all small sets of the model can be embedded (just as another smaller element captures all finite sets). But the greater expressive power still allows mutual relative consistency: To every model of Goedel-Bernays, a model of Zermelo-Fraenkel can be constructed in a fairly straightforward
manner: just take the small elements; in the converse direction there are two procedures (left and right adjoint?): given a model of Zermelo-Fraenkel, one can take all definable subsets of it, or just all subsets, and in either case a model of Goedel-Bernays apparently results. Because these mutual interpretations are hypothetical, relatively weak assumptions are required on the background category of sets taken as the recipient of models. In fact, with only slightly stronger assumptions on the background category one can construct, for any model of Zermelo-Fraenkel, a model of what set theorists use daily as BG+, which contains as elements not only V but W = V^V, V^W etc.

Our practice is consistent with the minimal assumptions of professional set theorists: For any model of BG+ the presented metacategory of categories is both cartesian closed (in the usual elementary sense) and also has an object S of small sets. (Those facts strongly augment well-known properties, such as the existence of the first four finite ordinals and their adequacy in the metacategory relative to
the sub-metacategory of discrete categories; of course these same ordinals also co-represent one of the "2-category" structures on the metacategory).

The category S is itself cartesian closed, and the categories of structures of geometry and analysis are enriched in it. Of course functor categories may no longer enjoy the same enrichment, just as functor categories starting from finite sets may not have finite hom-sets; but that is no reason to avoid considering them, and functionals on them, etc. when such considerations serve mathematics.

It is of special interest to note that the restrictive "law" (under which categorists have been chafing) was already repealed forty years ago by Goedel and Bernays themselves. In their correspondence of 1963, it appears that they had been informed that a student of Eilenberg was working on a project to base set theory and mathematics on category theory; their immediate response was that mathematics will have to consider finite types over the class of small sets. (The relative consistency was presumably obvious to them.)

Even though most set-theorists have themselves maintained clarity on the distinction, the identification of two kinds of membership in a formalized theory may have fostered in the minds of others a confusion between smallness (of a class or set) and existence as an element of the (meta)universe. Certainly, the specific meaning of smallness needs to be clarified (although for some purposes it can be taken as a parameter). There is a way of specifying smallness that is directly related to fundamental space/quantity dualities (rather than to imagined "building up" by stronger and stronger closure properties).

Just as Dedekind finite sets X are characterized by the condition that a natural map X --->Hom(Q^X, Q) is an isomorphism, so indications from the study of rings of continuous functions and other branches of analysis strongly suggest that all small sets X should satisfy the same sort of isomorphism, with the truth-value space Q being replaced by the real line (in both cases, Hom refers to the binary algebraic operations on the object Q). There is the possibility to assume that conversely all sets X satisfying that isomorphism are small i.e. that, like the Dedekind-finite sets, they belong to a single uniquely-determined category S. That possibility in itself would imply no commitment concerning the existence or non-existence of super-huge objects in the metacategory "beyond" S, S^S, etc. Such an axiom would be somewhat stronger than ZF, but much weaker than the standard discussions of contemporary set theorists.

************************************************************
F. William Lawvere
Mathematics Department, State University of New York
244 Mathematics Building, Buffalo, N.Y. 14260-2900 USA
Tel. 716-645-6284
HOMEPAGE: http://www.acsu.buffalo.edu/~wlawvere
************************************************************

Names

2010-09-14T15:31:00.000-07:00

I believe I have written a post earlier about names in Science. I am prompted to write again by a particularly irritating phenomenon in Category Theory. It seems that names are being introduced for vague concepts and used as ideological weapons.
Three examples annoy me in particular: "evil" and "categorification" and "(infinity,n)-categories".

None of these notions has a precise meaning. All have strong and as yet unjustified associations. The second has certainly already occurred in the formal literature and probably also the third. They are used continually in blogs and the categories mailing list. I am unable to join a discussion in which these words are used.

I forgot to mention another word: "morally".

All these words might be used casually in conversation but have no place in the serious literature.

The act of making names does not mean that the names have meaning but it does allow one to produce books with titles such as
"Towards Higher Categories"
or articles such as
"A Prehistory of n-Categorical Physics".

In the news again

2010-09-14T15:01:00.000-07:00

In the past few days all the members of the University have received emails from a president of a faculty here in Como suggesting that the Rector and the Rector Vicario resign. Other emails have been received from another president, and an ex president in Varese.
I report on this publicly because the matter has been taken up by the Como newspapers (and I think also in a national newspaper) with one headline being:
Tre presidi contro il rettore
Insubria: "E' il collasso".

Another article is headed "Salvare la dignità e rispettare Como".

These are difficult times in the University system in Italy but I remain firmly of the opinion that the main problem of the University in Como is the lack of students of the Faculty of Science in Como. The number of new students this year may well exceed by very little the number of lecturing staff, even though this year new first year students of Mathematics, Physics and Chemistry were relieved of the necessity to pay fees.

Added: In this whole affair there is an internet effect. The ease and rapidity of sending a message from any staff member to all staff, in some cases without even correcting spelling and grammatical errors, has the result that the discussion is extremely dramatic and heated. It also leaks into the local press and becomes even more inflamed. An investigation into the leaks would be interesting.

I must say that I do not write to mailing lists for this reason. I prefer to write to this blog which nobody is forced to read. I also do not like very much the comment section of blogs unless they are strictly moderated.

The Grand Design

2010-09-10T02:17:00.000-07:00

Some links about the Grand Design.

1. From here:
In The Grand Design we explain why, according to quantum theory, the cosmos does not have just a single existence, or history, but rather that every possible history of the universe exists simultaneously. We question the conventional concept of reality, posing instead a "model-dependent" theory of reality. We discuss how the laws of our particular universe are extraordinarily finely tuned so as to allow for our existence, and show why quantum theory predicts the multiverse--the idea that ours is just one of many universes that appeared spontaneously out of nothing, each with different laws of nature. And we assess M-Theory, an explanation of the laws governing the multiverse, and the only viable candidate for a complete "theory of everything." As we promise in our opening chapter, unlike the answer to the Ultimate Question of Life given in the Hitchhiker’s Guide to the Galaxy, the answer we provide in The Grand Design is not, simply, "42."

2. From here:
That brings me to another bit of news making the headlines in the UK – huge and looming cuts in science funding.
The cuts will be implemented by Vince Cable who is the UK’s secretary of state for business, innovation and skills.
He was interviewed in a third piece on Today and made the remarkable claim that “45% of research grants [in the UK] go to research that is not of an excellent standard”.
Ouch…and to save money, the government will soon be “rationing funds by quality”.
So what does this have to do with Stephen Hawking and M-theory?
Physicists need the backing of the British public to ensure that the funding cuts don’t hit them disproportionately. This could be very difficult if the public think that most physicists spend their time arguing about what unproven theories say about the existence of God.

The challenge, of course, is how to make the public aware of all the fantastic work done by other British physicists.

3. From here:
Fortunately, everyone, most of all God, knows that no one ever listens to anything physicists have to say unless it proves a minor point of reference in Star Trek. So, physicists can tell us that Warp drives will be possible in forty years, and we go, "Yay!" When they start babbling about everything being held up by Superstrings, we know that they are one grant application away from serving burgers for a living.

Update: There are interesting reviews in Peter Woit's blog and the Economist of Monday September 13th 2010.

A formula

2010-09-03T08:57:00.001-07:00

If
\[A=\left( \begin{array}{ccc}
25 & 15 & 30 \\
104 & 80 & 120 \\
30 & 30 & 30 \end{array} \right)
\]
and
\[
B_k=
\left( \begin{array}{ccc}
-2k^2+k+4 & 2k^2+7k+6 & 0 \\
2k^2+7k+2 & 0 & 2k^2+7k+6\\
2k^2-k & 0 & 0 \end{array} \right)
}
\]
then the (scaled) columns of
\[ A\prod_{k=2}^{n}B_k\]
tend towards
\[
\left(
\begin{array}{c}
log(2)\\
\pi \\
1
\end{array}
\right)
\]
as \[n\to\infty.\]

The Category Seminar in Sydney

2010-08-20T03:47:00.000-07:00

There has been a continuous series of category theory seminars in Sydney since 1970, and the 40th birthday is coming up. It was a crucial seminar in my scientific career, though I haven't been a part of it since around 1998. I owe much, in particular, to Max Kelly and Ross Street, and to the many visitors we had to Sydney.

I have not been able to determine the exact date of the first seminar, held at Macquarie University, but it was probably 23rd September 1970. The first date for which I have notes of a lecture in 7th October 1970:

Mathematics and computer science

2010-08-19T00:36:00.000-07:00

I haven't written much lately since we have been travelling. Now I am working on a paper and I am faced once more with the difficulties of working between two fields with different cultures, mathematics and computer science. As I have mentioned elsewhere I worked as a mathematician for 20+ years and then as a computer scientist for 20 years. Perhaps it would be more accurate to say as a mathematician working on computer science for the last 20 years, since the first years have a more profound effect. However my direction really changed around 1990 and I see mathematics differently now.

I want to make a series of observations about this experience as they occur to me, not in any particular order. I will collect them all in this post even though I write them over time.

1. The debate over Tuesdays child which as far as I am concerned was never resolved (even in Peter Cameron's blog) illustrates one hugely important fact about mathematics. It seems to be the only subject where arguments can be clearly decided and resolved. Its is also the limitation of mathematics - we do want to understand the world and that is outside such certainty.

2. Computer scientists, even theoreticians, are very rough in creating models. At least to my taste. They are influenced by engineers for whom what works, as soon as possible, in OK. But this to me is no way to create theories. I believe from my mathematical experience that there is usually a correct way to do things, which needs to be distilled from experience.

3. Let's look at the success of Google. A mathematician looking at this imagines that the important thing was the algorithm for rating web pages, and take credit for the fact that this comes from the theory of Markov chains (just as physicists take credit for the world wide web because it was developed at CERN; one would hope something useful came out of all that expense). The algorithm is clearly important but if you look at the first paper by Brin and Page (which I see now was presented in Brisbane!) it is much more about the architecture of Google and the problem of implementing search as rapidly as possible using a large number of machines. The algorithm is a very small part of the achievement.

4. To be continued.

Clive Selwyn Davis, 15 April 1916 – 29 October 2009

2010-08-11T06:01:00.000-07:00

I am rather out of touch with Australian mathematics and so I have just found out by chance that my MSc supervisor Clive Davis died in October last year. There is an obituary in the Australian Mathematical Society Gazette.
I learnt number theory from him, and remember well "the clarity, vigour and high standard of his lectures. His handwriting on the board was immaculate, and his brief
dictated final summary of each lecture was much appreciated." (quote from the obituary)
I wrote a Master's thesis on continued fractions in 1966 with him, and eventually even wrote a small book on number theory.
At that time, if I remember correctly, the first PhD in mathematics at the University of Queensland had yet to be awarded, so I went to Bernard Neumann's department at the ANU in Canberra, and changed direction, with Hanna Neumann as my supervisor. I had considered continuing number theory with Kurl Mahler, but my impression was that he was not very keen on having students.

Professor in Italy

2010-07-19T11:52:00.001-07:00

Recently I became a full professor of Computer Science in Italy. I had been a mathematician at the University of Sydney in Australia, and when I moved to Italy I had no plans for an academic career here, but the opportunity arose.

However just as I reached this pinnacle it seems that the Italian university sytem is falling into deep crisis. I will quote two sentences from a report in Nature.
"Science teaching in Italian universities could be crippled if tens of thousands of junior staff make good on threats to strike later this year. The 'ricercatori' (researchers) are protesting harsh university budget cuts and a looming reform bill, which threaten their futures."
"If these changes don't happen, and the ricercatori carry out their threat to strike, universities may find themselves unable to open for teaching in September."

If you read the comments to the article you will see that the situation is very complicated.

Italy has all the advantages and disadvantages of being a very interesting place to live.

Rants

2010-07-06T02:54:00.000-07:00

It is now more than a year since I began regularly posting to this blog. I see that I actually started the blog in 2005 with some irregular posting and I had done blog-like posts before when I was in Sydney. The motivation, I have to admit, has been principally objections to things, though I have tried not to seem too negative.

The posts in 2005 were about what seemed to me to be an error in Andy Tannenbaum's book on operating systems. I wrote to him several times over several years but couldn't get an answer from him, so I wrote a post. I still haven't managed to get anyone to agree or disagree with my comment (not just to the post but in conversation, in lectures etc) so that post didn't resolve anything.

Another series of posts, from which however I learnt a great deal, were a result of my dissatisfaction with process algebras.

However the main energy behind this blog has been the struggles at the University of Insubria, including the closure of our course in Informatica at Como. I was so distressed by the misinformation occurring in some local newspapers that I needed an outlet.

I have tried always to be diplomatic in the blog, not saying saying anything too explicitly to avoid upsetting anyone. This seems to have worked, although I did overstep the bounds once it seems.

Although the energy has come from rants, I feel now that there is some kind of conversation going on, with few people maybe, but also with other blogs, and I enjoy it.

Bits and pieces

2010-06-29T08:05:00.000-07:00

1. A recent paper on topos theory claims "one can generate a huge number of new results in any mathematical field without any creative effort".

This does not seem to me plausible, at least if interesting new results are intended. I await the evidence as it develops.

2. Research activity hinders the application for research funds: During the week of 13-19 June I was hosting two international visitors and organized a miniconference in Como on 15-16 June. On the Sunday I went to Genova for the annual international meeting (CT2010) in my subject with more than 120 attendees from more than 25 countries. (I was on the Organizing and Scientific committees as well as being a speaker.) After the conference a third international scientist visited me in Como.

As a result of this activity I was unable to apply for postdoctoral positions at the University of Insubria next year. I received details on how to apply Thursday 17th June, which applications had to be presented by 9am Monday 21 June.

The usual complaint is that making grant applications hinders research.

Categories and Computer Science Workshop

2010-06-07T12:34:00.000-07:00

CATEGORIES and COMPUTER SCIENCE Workshop Tuesday 15th & Wednesday 16th June 2010
Sala Riunione, via Carloni 78, Como

TUESDAY 15th June 2010
3pm Matias Menni (La Plata, Argentina)
Title: "The morning characterization of EB monads"
4:30pm Aurelio Carboni (Insubria)
Title: "Slices of monoidal closed categories"
5pm Robert Rosebrugh (Mt Allison, Canada)
Title: "Fibrations, partial lenses and universal updates"

WEDNESDAY 16th June 2010
3pm Matias Menni (La Plata, Argentina)
Title: "Reflective subcategories of decidable objects"
4:30pm RFC Walters (Insubria)
Title: "Weighted automata and CospanSpan".

Dipartimento di Informatica e Comunicazione
Università degli Studi dell'Insubria

Robbie Gates on seven trees in one

2010-06-04T06:56:00.001-07:00

I am recuperating some old posts made while I was in Sydney, this one by my then student Robbie Gates.

On Bijections between Data Types

Copyright Robbie Gates, 8th May 1996

This is a short note detailing the content of a lecture given to the third year "Categories and Computer Science" course in pure mathematics at Sydney University by Robbie Gates in which the results of the papers [Gat] and [Bla] were discussed.

Introduction

As previously discussed, the constructing arrows in a distributive category from a collection of basic arrows using composition and the properties of sums and products corresponds to writing straightline programs using given primitive operations. These composites can also be represented by drawing circuit diagrams, where the circuit elements represent arrows in the composite, and wires represent the objects.
To construct programs that use looping constructs (such as for or while loops), or circuits involving feedback requires more sophisticated notions, see [KSW] for the theory developing these ideas.

Types as objects of a Distributive Category

Types may be described as objects of a distributive category satisfying certain equations in the distributive category.
For example, the type "binary trees of X" may be described as an object T together with a given isomorphism T≅ TXT + 1 which consists of a pair of arrows break : T -> TXT + 1 breaks a binary tree into (left subtree, node, right subtree) or returns * for the empty tree, and make : TXT + 1 -> T which constructs a tree from its subtrees and node, or constructs the empty tree from *. Straight line programs utilising this data type are then arrows constructible from this isomorphism and the operations of a distributive category. For example, the arrow which interchanges the left and right subtrees of a given tree can be described as
make . (prj3,prj2,prj1) + 1 . break
or drawn as the following circuit,

where the wires are labelled by the object of the distributive category they represent.
We shall be mainly concerned here with a simpler example, namely trees of 1, that is to say, an object with a bijection T≅T^2 + 1.
The primary example we shall have in mind is indeed when T is the set of binary trees with unlabelled nodes in the distributive category Sets. Isomorphisms constructed between powers of T will then corresponding to bijections between the sets of tuples of binary trees. Note that this has the form P(T)≅T for the polynomial P(x) = x^2 + 1, where P is consider to be a polynomial with natural number coefficients. By considering polynomials with coefficients in an arbitrary distributive category, more interesting examples can be obtained (for example the paramatrized types such as trees of X as described above).

The Generic Solution

Of particular interest is the "free" solution to the problem of finding a distributive category containing an object T and isomorphism P(T) ≅ T. By free here, we mean 2-initial in a suitable 2-category of distributive categories with designated object T and isomorphism P(T)≅T. The object T in this category is the generic solution to the equation, and the arrows represent generic operations on the data type, that is to say, operations that are constructed from the isomorphism using distributive operations, or alternatively, the straight line programs on the data type.
The main result of [Gat] is to described the burnside rig (the rig of isomorphism classes of objects) of the category containing the generic solution for a large class of polynomials, including the example P(x) = x^2 + 1 (first studied by[Bla]). This is done by giving a particularly tractable explicit construction of the category containing the generic object, as a category of fractions on the category of families of a particular Lawvere theory obtained from the polynomial.
In fact, the burnside rig turns out to be simply the free rig containing a solution to the equation. This is referred to by the slogan "Combinatorial equivalence is the same as Algebraic equivalence" (after a theorem from [Bla]). By way of explanation, we note Combinatorial equivalence refers to an isomorphism between objects of the category - it is an explicit construction using the operations of the data type, where Algebraic equivalence refers to an equational deduction using rig operations.

An Interesting Bijection

Let us return again to the example P(T) = T^2 + 1. Here, there is an equational deduction of the fact T^7 = T from the equation
T^2 + 1 = T using rig operations. Extremely informally, a suggestion of why this occurs can be obtained by solving the given quadratic over the complex numbers, and observing its roots indeed satisfy T^7 = T. Of course, this uses non-rig theoretic reasoning (although as we shall see, this is almost irrelevant !), an honest derivation can be given as follows:

This derivation can easily be converted to a circuit (in fact, the circuit may be easily constructed simply by thinking circuit theoretically). Such a circuit is given in the follow diagram, note that we have labelled the wires simply by the exponent of T occurring, and all vertical juxtapositions are +. Further, labels on the circuit elements have been omitted, right-pointing triangles are instances of break multiplied by an appropriate power of T, whereas left-pointing triangles are instances of make multiplied by an appropriate power of T.

Proving Bijections don't Exist

As noted above, the circuit can indeed be constructed after some fiddling. From one point of view, the important part of the theorem is the negative part - one can show the nonexistence of straight-line programs exhibiting certain bijections. In particular, there is no bijection between the set of pairs of binary trees and the set of binary trees constructible from make and break using distributive operations. To see this, it suffices to show there is no equational deduction of T^2 = T from T^2 + 1 = T. This can be seen by exhibiting an element of any rig which satisfies the latter equation but not the former. Either root of x^2 + 1 = x in the complexes suffices.
Suppose you are given a isomorphism U^2 + U + 1 ≅U in a distributive category. Can you necessarily construct an isomorphism between U^7 and U^6 ? The answer is no, the complex number i satisfies x^2 + x + 1 = x but not x^7 = x^6.

Utilising the terminology of [Sch], it is shown in [Bla] that Euler characteristic and Dimension are sufficient to characterise the elements of the free rig with a solution to x^2 +1 = x. Without going into details, the net effect of this is that to determine whether or not two elements are equal, it suffices to check them at one root of the quadratic (the Euler characteristic), and to check that they either both contain an x or neither contain an x (the Dimension). This allows the existence of isomorphisms to be guaranteed merely by checking simple algebraic properties.

Further Work

The author of [Gat] is continuing investigations in this area, with particular interest in parametrized data types (for example, the template construct in C++)and applying the Euler characteristic and Dimension arguments to more general examples. A strong theory of data types and their behaviour in relation to straight-line programs is emerging from this work, and this connection is being vigorously explored.

Bibliography

[Bla] A. Blass, "Seven Trees in one", Journal of Pure and Applied Algebra, 103:1-22,1995.
[Gat] R. Gates, "On the generic solution to P(X)≅X in Distributive Categories", Journal of Pure and Applied Algebra (to appear).
[KSW] P. Katis, N. Sabadini, R. F. C. Walters, "Bicategories of Processes", Journal of Pure and Applied Algebra (to appear).
[Sch] S.H. Schanuel, "Negative sets have Euler characteristic and dimension", Category Theory, Proceedings, Como 379-385, 1990.

Good news for Category Theory in Sydney

2010-06-02T03:05:00.000-07:00

I hear from Ross Street that Steve Lack has accepted an appointment at Macquarie University. This augurs well for the continuation of a strong group at Macquarie.

Probability 2 - Boy or Girl paradox

2010-05-23T23:43:00.000-07:00

I continue to be amazed by the fact that apparently simple probability problems are often so difficult to resolve. It is particularly surprizing in view of the fact that so much science seems to depend on probability these days: the particle physicists' results are small probabilistic anomalies in incredibly expensive experiments, quantum physicists say that nature is inherently probabilistic, the medicine we take is determined by 'random' trials, evolution apparently occurs by 'random' mutation, etc, etc. (I don't necessarily concur with all this, by the way.)

I have been thinking more about this fact since the blog post of Peter Cameron, which derived from another post by Alex Bellos. The particular problem they consider is this: if someone tells you that they have two children at least one of whom is a boy born on Tuesday, what is the probability that the second child is a boy?

Actually, the simpler version of this problem in which there is no mention of the day of birth (possibly introduced by Martin Gardner who died 22nd May), has been discussed and disputed in short and in long, in circles high and low, under the name "The Boy or Girl Paradox".

In short, my view is that the answer to this question is 1/2 (under the simplifying assumptions clearly intended; that is, that the birth rates of boys and girls are equal, etc).
However a closely related problem which I will explain would yield the answer 1/3, the answer preferred by mathematicians.

I think this simple problem benefits from the distinction between states and actions, the states being the quality of being a girl or a boy, and the actions being the declarations made. In the real world problem you need to consider the probability of the action as well as the probability of being in a state.

Let's now consider the problem in detail: the simplifying assumptions mentioned above mean that given a family with two children the following four cases are equally likely: BoyBoy, BoyGirl, GirlBoy, GirlGirl. In the case BoyBoy the likelihood of a declaration that there is a boy is 1, in the case of GirlGirl the likelihood of a declaration that there is a girl is 1, but in the other two cases there is a half chance that the declaration is 'boy', and a half chance that the declaration is 'girl'. Now let's look at the total weight of a declaration 'boy': it is 1+1/2+1/2. The weight which corresponds to the case BoyBoy is 1. Hence the proportion of 'boy' answers which correspond to the state two boys is
1/(1+1/2+1/2)=1/2.

Now a slightly different problem: suppose I interview people with two children, and ask if they have a boy in the family; if they answer yes, what is the probability that the second child is a boy?
Again the simplifying assumptions mentioned above mean that given a family with two children the following four cases are equally likely: BoyBoy, BoyGirl, GirlBoy, GirlGirl. In the case BoyBoy the likelihood that they respond 'yes' is 1, in the case of GirlGirl the likelihood that they respond 'yes' is 0; in both the other two cases the likelihood of 'yes' is 1, not 1/2. Now let's look at the total weight of a response 'yes': it is 1+1+1. The weight which corresponds to the case BoyBoy is 1. Hence the proportion of 'yes' answers which correspond to the state two boys is
1/(1+1+1)=1/3.

If there is also mention of the day of birth there are at least three interpretions:
1) a person declares that they have two children at least one a boy born on Tuesday;
2) when asked if they have a boy, the response is 'yes, and born on Tuesday';
3) when asked if they have a boy born on Tuesday, the response is 'yes'.

The probability of the second child being a boy in the first case is 1/2, in the second
1/3 and in the third 13/27.

In this post I have tried (exaggeratedly) to argue in as simple language as possible, because a simple problem should only require the appropriate distinctions, not a big machinery. However I have earlier proposed (with Sabadini and de Francesco Albasini) a mathematical context, in which many of the perplexities are seen to arise from considering (normalized) probabilities, rather than weights of actions. The precise mathematical point is that normalization does not behave well with respect to sequential operations (which include abstraction). Another simple perplexing example where abstraction does not work well with normalization is Simpson's paradox, the mathematical origin of which is the fact that not always a/b+c/d=(a+c)/(b+d).

An extreme example of Simpson's paradox is the following:
Consider treatments A,B and diseases X,Y.
Treatment A with disease X on one person cures the person (100% cure rate - best possible)
Treatment B with disease X on 99 people cures 98 (worse than 100%).
So A has a better success rate than B with disease X.

Treatment A with disease Y on 99 people cures 1 person (this is better than 0% cure rate)
Treatment B with disease Y on one person fails to cure (0% cure rate - worst possible).
So A is better than B with disease Y.

In both diseases X and Y the treatment A is better than B.

However treatment A saves 2 people in 100, B saves 98 in a hundred.
B is worse than A???

Como and Varese

2010-05-21T07:02:00.000-07:00

For those who followed the disputes I reported about the computer science course in Como, I have some news. Next year there will be no first year course in Informatica at the University of Insubria in Como.
Since the 7th of May 2010 the computer science staff previously part of the Faculty of Science in Como, have been transferred to the Science Faculty in Varese. We are also now members of the Department of Informatica and Communication in Varese.

The established "hard" sciences Mathematics, Physics and Chemistry have won. All that remains is for them to find some students.

Synthetic DNA

2010-05-21T05:16:00.000-07:00

I must admit to being alarmed by the reported creation by J Craig Venter's research institute of a reproducing cell with synthesized DNA.

Coprifuoco

2010-05-19T12:08:00.000-07:00

There are severe disadvantages living in a country where the language is not your mother tongue. However there are also advantages. I am constantly learning things about English from my exposure to Italian.

One example today: the newspapers are talking about a coprifuoco (cover fire) in the battle in Bangkok. At first I couldn't imagine what that meant. Then I guessed the meaning without being able to recall the English word (this happens too frequently these days). Finally I realized that coprifuoco was curfew, with an instant insight into the origin of English word.

From the Online Etymological Dictionary:
curfew early 14c., from Anglo-Fr. coeverfu (late 13c.), from O.Fr. covrefeu, lit. "cover fire," from couvre, imper. of couvrir "to cover" + feu "fire." The medieval practice of ringing a bell at fixed time in the evening as an order to bank the hearths and prepare for sleep. The original purpose was to prevent conflagrations from untended fires. The modern extended sense of "periodic restriction of movement" had evolved by 1800s.

Hypotheses

2010-05-17T23:54:00.000-07:00

I notice that John Baez has realized a danger of the new scientific order of blog posts, blog comments, labs, mailing lists, expository-style papers, preprints in arxiv, and traditional scientific journal articles.

From a comment on the May 15, 2010 post of n-category cafe (my italics)
"This Week’s Finds and my seminar notes are packed with hunches of varying caliber. Sometimes you need to read between the lines a bit to see them — for example, if I say something ‘should’ be true, it means I believe it’s true but haven’t proved it. And sometimes, I’ve said something is true even though I haven’t proved it. By now I realize this is a bad habit… thanks to the following story.
Once I went to a talk where somebody said that for any ring R there’s a one-object tricategory Alg(R) consisting of R-algebras, bimodules and bimodule morphisms. I said “Really? Do you know if anyone has ever written that up?” And the speaker said “Sure! It’s in This Week’s Finds!” Which galled me, because while I knew it was true, I’d never seen a proof written up — and I realized then that by claiming it was true in This Week’s Finds, I’d reduced the chances of ever seeing a proof."
Another remark:
"The last page of my slides was supposed to summarize only the ideas that will surprise and thrill the audience, so I get a standing ovation."

I find the current state of n-category theory a confusing mixture of conjecture, unfinished definitions, unfinished proofs, buts lots of exposition.

I am old-fashioned and believe that to maintain integrity we must insist that the science exists in the scientific journal articles. Credit should be assigned on the basis of published scientific articles.
I don't know what it means to have expository articles of an vaguely developed field.

Perhaps we will end with Bogdanovs.

Probability

2010-05-06T08:49:00.000-07:00

I made the suggestion recently that the Kolmogorov presentation of probability was too abstract, and that this was the cause of elementary confusions like those common in the Monty Hall problem.

I must admit to being quite unsure of the foundations of probability theory. The fact that simply stated problems are easy to make errors about hints to me that the gap between theory and practice is too wide. I make some tentative remarks below, which are made more formal in a small paper we have just written.

1. First, I think probability should be about explicitly described systems. (Peter Cameron in his blog post describes two possible systems ("protocols") which might be behind a particular problem, yielding different results.) This would imply that one needs a notion of system. In this context probabilities are weightings of actions in a particular state of a system. Such a weighting represents information about the cause of actions. It is a kind of primitive dynamical information.

2. The Kolmogorov view is that independence is defined in terms of the probabilities of events. This is the attitude that we are observing behaviours, rather than considering systems. For systems there is a clear operation of composition in parallel. Actions may be appear to be independent behaviourally without being actually parallel.

3. The fact that the sum of all probabilities must be 1 is another evidence of a behavioural view. A system may have big reasons for making a choice, or small reasons, in both cases, say, with a half and half probability. This doesn't affect observed behaviours. However in composing systems large reasons in one system may overwhelm small reasons in another.

To make this more concrete: suppose I am in a situation where I am deciding to eat an apple or a pear (with equal interest), and suddenly I perceive that a car is driving straight towards me, and that with equal choice I must decide whether to run to the left or right to avoid an accident. This is a state in a composition of two systems. It is clear that the weight behind choosing an apple or a pear is overwhelmed by the choice between jumping left or right.

At a system level weight is more fundamental than probability, which arises as a normalization of weight.

Update: I see now that Peter Cameron has come to a conclusion (which I quote in full, but with my italics; it refers to a particular calculation which you can see at his blog):
"Mathematically the conditional probability that someone has two boys, given that one of their two children is a boy born on Tuesday, is 13/27. If we started defining the probability of some event in terms of the algorithm that led to the statement being made, all our textbooks would need to be rewritten from the ground up. I think the best way to proceed is to say, we do know how to calculate probability (and how to interpret it), but this requires careful thought, and sometimes our intuition lets us down."

Update: I made a too brief comment on Peter Cameron's blog, namely that
"I agree with John Faben [another commenter] that the calculation of probability requires information about the algorithm involved."

It is somewhat difficult in blogs to follow which comments are later referred to, but it seems that Peter replied to my comment with the following:
"Sorry to have to disagree…

Any calculation in probability can be done unambiguously by the rules (based on Kolmogorov’s axioms) provided we specify carefully what is the “sample space” and what is the probability measure on the sample space. If you start bringing in other factors like the algorithm used to generate a statement then all you are doing is changing the measure. That is why I said in my example that I am a covert Bayesian. I happen to think that the probability measure that applies in a given situation depends on everything I know about the situation (which may include information about the algorithm used to generate some statement)."

He wrote more which I do not reproduce here.

I have been trying to understand why is it difficult to apply the existing theory (Kolmogorov) to apparently simple real world problems, a fact admitted by Peter. (There is a rumour that even Erdos had difficulty with Monty Hall.)

My suggested answer to this is that there is too great a gap between real world problems and the theory, and perhaps there could be a more detailed theory in between reducing the gap.

The more detailed theory would be prior to the construction of the probability space.
It would consist in making more precise the real world problem, by describing a mathematically formal system (algorithm, or protocol). This is not beyond the capacity of mathematics to do.

Peter seems to agree when he says "everything I know about the situation", which is another way of saying the precise system under consideration.

There is a sleight of hand in the statement "If you start bringing in other factors like the algorithm used to generate a statement then all you are doing is changing the measure". The algorithm is needed to determine the measure; different algorithms determine different measures.

The fragility of computer programs

2010-05-04T01:37:00.000-07:00

For some time I have used mainly the Opera browser, which has about 2 percent of users on the web. I used it with a Gmail as a POP server. About a month ago the mail server stopped working. I couldn't do anything with Gmail on Opera, so I started using Chrome more frequently, and had almost decided to dump completely Opera.
I did try to fix Opera in this period, searching for similar experiences on the web. Just today I found that a single flag in preferences:advanced:security:security_protocols, namely the lack of enabling of TLS1.1, was causing the problem.

I have returned to using Opera as my main browser.

Bits and pieces

2010-05-03T11:08:00.001-07:00

I have been quiet for a while as we have just had a month long visit from one of my sons and a granddaughter. Very enjoyable, interesting and distracting from normal activities. I want to make some brief comments which maybe I will enlarge upon later.

1. Why is probability so unintuitive? Peter Cameron has an interesting post about probability. I am particularly amused by his admission that after five years of teaching probability (something I have never done) he had a recurring nightmare that a student might ask him "What is probability?" and that he would be unable to answer.
He implicitly raises the question I began with, by describing a very simple problem the usual solution to which he finds unconvincing. Recently a whole book has been written about a famous simple question, the Monty Hall Problem.
I have always had similar difficulties about the meaning of probability theory, but recently in our work on algebras of processes I have come to the conclusion that one of the main reasons for the difficulty is that probability theory, and in particular the set theoretical formulation of Kolmogorov, is too abstract. Probabilities should not be associated with events, but instead to transitions or processes. Conditional probability then arises from communication between processes. (Peter starts to describe protocols. In fact, he shows that different protocols for his problem yield different results.) I think the mathematical model needs to be richer. The lack of intuition is related to the fact that problems are presented in too abstract a context: ask an Italian about Monty Hall and he will imagine any kind of imbroglio. We wrote a little paper in this direction, and are currently writing another.

2. How can people write programs without having a precise semantics for the language? I have been working for some years on the theory of programming languages. I have the view that the design of a programming language should involve first having an idea of an algebra of systems, and that the language should arise from the notion of free algebra. This doesn't seem to be an idea shared by many. (As a crude example of the idea, the integers form a ring, and elements of a free ring Z[x,y,..] are programs for making calculations with numbers.)
It seems however that programmers don't need to know mathematics and can write programs that are more or less correct without knowing really what the language means. (Also I write programs like that.) How is it possible?
To make a comparison, students have the greatest difficulty making proofs. Very few succeed.

3. Absurdities. I think there are some mad ideas being presented in science these days. Just two examples: multiverses, and Max Tegmark's classification of these; the aggresive insistence of David Deutsch on the Everett interpretation of quantum theory. More worrying is that both of these are being supported at the highest level of the scientific establishment. The Edge also seems to me to be full of dubious ideas.
I read in an article by Deutsch that people like me who express doubts about many worlds are like those who doubted the motion of the earth, on common sense grounds, at the time of Galileo. Looks like I am in bad company.

Heat on the net

2010-04-01T10:02:00.000-07:00

Communication can become very heated on the net. I remember my first experience of it years ago when a round of emails between me, Max Kelly and Ross Street spiralled, in the course of a couple of hours, in aggression. The only way out of it was to stop writing, and start again later. (We successfully maintained a seminar, with others, which began in 1970, was still active when I left Sydney in 1998, and remains today one of the principal seminars in category theory.)

I was reminded of this while thinking of the 20 year success of the Categories List. One needs to be conscious of the new mode of communication in order to produce a stable and productive group communication. I receive other lists which contain nothing but announcements of conferences and of jobs, whereas the categories list has managed to sustain mathematical discussion.

I found an interesting page about moderated academic lists. I quote one paragraph:
"One lesson I learned along the way is that the ecology of an active online community is surprisingly fragile. It can go wildly out of whack, and even self-destruct, in a very short time. I’ve seen any number of lists decline and die over the years. Some merely waste away through attrition and neglect until no one posts
to them anymore; others become mere notice boards for calls for papers and the like, without any real interaction among subscribers. A few flame out spectacularly, bursting with so many nasty, off-topic messages that all the “lurkers” unsubscribe, leaving the
disputants to fight among themselves until even they grow weary of it. Charting a middle course means achieving a high “signal-to-noise” ratio, in which the list’s content is useful enough to make it worth people’s time to stay involved."

Another thing I learnt looking around is the meaning of "internet troll". From wikipedia a quote:
"Forum trolls are users that repeatedly and deliberately breach the netiquette of an established online community, posting inflammatory, extraneous, or off-topic messages to bait or excite users into responding or to test the forum rules and policies, and with that the patience of the forum staff. Their provocative behavior may potentially start flame wars or other disturbances. Responding to a troll's provocations is commonly known as 'feeding the troll' and is generally discouraged, as it can encourage their disruptive behavior."

Categories list - 20 years old!

2010-03-25T07:27:00.000-07:00

I notice that the Categories List, started and maintained by Bob Rosebrugh, is now 20 years old. The advertisement (see below) for the list was first sent out on 11th March 1990. My email address then was munnari!maths.su.oz.au!walters_b@uunet.uu.net.

We category theorists owe a great deal to Bob Rosebrugh for this initiative, and for his other creation the on-line journal Theory and Applications of Categories.
Among other things he has dealt very calmly and competently with the little crises which tend to occur on such lists.

Thank you, Bob.

(I think I played a small (very small) part in the creation. Some years prior I spoke at every categories conference about the importance of email and the internet. I will have to look up the date, I think it was around 1983/1985.)

------------------------------------------------------------------------
March 11,1990

Dear Colleague:

This letter is to announce the availability of a Bulletin Board for Category
Theory on BITNET. The address is CATEGORIES@MTA.BITNET.

The intention is to operate in a manner similar to the Types Bulletin Board.
To join the mailing list, simply send a message to:

categories-request@mta.bitnet.

After confirmation of two-way transmission your name will be added to the list.
Please provide a very complete return address. To distinguish messages for
forwarding from others of an administrative nature, please mail to Categories
ONLY messages which are intended to be forwarded. All other messages should be
sent to categories-request@mta.bitnet, or to me ( rrosebrugh@mta.bitnet )

Anyone may submit (electronically only) any material about Category Theory (and
only about Category Theory) for distribution - abstracts, announcements of
results or meetings, queries, or full papers. Material will be forwarded as
received unless there is evidence that the message received is garbled. The
initial committment is that turn-around times will not exceed a couple of days.

TeX files are welcome in any flavour - plain, AmSTeX or LaTeX. They should
include a Character Code Reference which is available on request.
Unfortunately, until we see how well this works, there can be no committment to
either authors or subscribers regarding accuracy of TeX files transmitted. TeX
preprints will be archived separately, and a catalogue of them will be
published irregularly. Macro packages are the responsibility of the author,
however an attempt will be made to archive versions of diagram macro packages.

I gratefully acknowledge assistance from David Jones at Types who suggested
some of the procedures to be used. Electronic addresses to which this is being
sent are taken from lists provided by Mike Barr and Max Kelly, and I thank
them (and Mike Johnson who transmitted Max's list.)

Those seem to be the main points. Looking forward to a useful exchange,

Regards,

Bob Rosebrugh
/TO categories@mta.bitnet
/BC Mike Barr ,
Francis Borceux ,
Aurelio Carboni ,
Peter Freyd ,
Mike Johnson ,
Paul Johnson ,
Stefano Kasangian ,
Fred Linton ,
Phil Mulry ,
Susan Niefield ,
Bob Pare ,
Andy Pitts ,
Pino Rosolini ,
Dietmar Schumacher ,
Phil Scott ,
Robert Seely ,
Ross Street ,
Paul Taylor ,
Bob Walters ,
Charles Wells ,
Richard Wood
/TX

The following message has been sent out to about 100 addresses from
Mike's and Max's address lists. On the assumption that anyone I have heard
from wishes to be included on the subscriber list, I have included you already.
Let's see how it goes.

Bob

Impossibility proofs

2010-03-24T03:04:00.000-07:00

Proofs that something is impossible (the solution of quintic equations in radicals, squaring the circle, etc) have been crucial in mathematics since they require a very precise understanding. This has also been true in computer science: the impossibility of calculating the halting function requires a precise formulation of computability.

I have been thinking about the impossibility of more particular constructions in practical programming languages. One I have in mind is the following: in C is it possible to write a function which given two pointers to functions returns a pointer to the composite function? I don't think so. People (for example, Yuri Gurevich) have claimed to give a precise meaning to C and hence an impossibility proof is conceivable. I would like to see such a proof (or an example program refuting my conjecture).

Applied Algebra

2010-03-01T08:54:00.000-08:00

By algebra I don't mean the usual groups, rings, fields, vector spaces etc of a mathematics course. Algebra is much more general, and involves considering the operations on things, and of course equations between these operations.

In applying algebraic ideas to a new field the first problem is to decide what are the basic operations. You don't see this problem in a classical algebra course because the operations of symmetries (groups), quantities (rings, and fields) have long since been clarified. In a new field the choice is very difficult and a bad choice leads to endless complication and confusion.

I have written about this in earlier posts: the parallel operation on processes seems to me to be misguided; the operations on relations in the algebra called "allegories" also seems to me to be misguided. I have suggested alternatives.

Here is another example from the book by Ferenc Gecseg on Products of Automata (Monographs in Theoretical Computer Science, An EATCS Series). A sequential machine has a set of states A, an input alphabet X and an output alphabet Y. It has also a transition function AxX->A and an output function AxX->Y. Now Gecseg defines a "product of sequential machines" as follows:
Click here for the definition.

The definition looks complicated, but even more complicated is the graphical representation:

This graphical representation suggests that there are much simpler operations, with the property that Gecseg's operation is a derived operation. The real entities are the boxes with wires on the boundaries. The real operations are the series and parallel operations, together with certain wire constants. Gecseg's operation is a derived operation in the algebra Span(Graph).

Oral examinations

2010-02-25T14:20:00.000-08:00

In Sydney we had only written examinations, so it has been an interesting experience to conduct oral exams. One gets to know the students better. It is possible to follow a line of questioning. Perhaps the results are not so objective: it is very difficult to have a marking scheme and give an evaluation to three decimal places. Usually however after 5 minutes one has a very good idea of the ability and preparation of the student.

Two comments after this month's exams.

One good student came prepared to tell me one of my theorems was mistaken. He had checked in two different ways. It took 15 minutes to follow his calculations and find that he had made a trivial copying error which vitiated both calculation. He got a very good result.

I asked the mathematics students what careers they wanted: the females had in mind to be high school teachers, and the males geniuses.

"A remarkable book"

2010-02-25T01:55:00.000-08:00

That is a quote from John Nash about a book I looked at recently - Prime Obsession by John Derbyshire.

On page (ix) he states the Riemann hypothesis, that the non-trivial zeros of the zeta function have real part one half.

It is not till page 146 that he describes how to calculate any value of zeta(z) with real part of z less than 1.

But the most remarkable thing about the book is that I don't see (in my superficial reading) a description of how one would calculate even one non-trivial zero of the zeta function.

I must be mistaken, and am happy to be corrected.

Absurdities

2010-02-23T23:44:00.000-08:00

A collection of small absurdities.

Private theft: Yesterday while I was walking back from lunch I noticed a youth unscrewing the antenna from a car in a somewhat furtive fashion. I enquired if he was stealing the antenna, and he claimed he actually knew the owner of the car (thus verifying that it was not his). There were also some young people across the road laughing (probably the whole thing was harmless), however I pretended to photograph the situation with my mobile phone. The immediate Italian reaction was that I was violating their privacy.

Cheating: There is a fair bit of cheating in Italian universities. A student just submitted to me a program of which, he insisted, he had written every symbol. He was unable to explain the program. Worse, the problem was to modify a program which I had written so that 95% of the code was written by me. A colleague received a program from an Italian student in which the comments were in Turkish.

Great thinkers:
L’edizione 2010 di Abitatori del tempo si compone di 10 appuntamenti, dal 15 gennaio al 26 marzo 2010, in 9 Comuni della Brianza, tutti dedicati alla riflessione sul senso della vita e la complessità della condizione umana nelle riflessioni e nei problemi posti da filosofia, teologia, arte e scienze.
Protagonisti degli incontri i maggiori pensatori ed esponenti del pensiero filosofico contemporaneo: Emanuele Severino, Giuseppe Rizzardi, Massimo Marassi, Vincenzo Vitiello, Giulio Giorello, Salvatore Natoli, Stefano Serra Capizzano, Carlo Sini, Elio Franzini.

Honorary degrees

2010-02-23T05:20:00.000-08:00

The universities in Italy have started awarding honorary laureas to people for their celebrity rather than academic merit. Valentino Rossi, the motor cyclist, received a laurea (una laurea magistrale honoris causa in Comunicazione e Pubblicità) from Urbino.

The danger of this is that academics don't really know the people they are honouring.

Recently I saw a letter recommending a celebrity for an honorary laurea degree for his/her "riconosciute doti scientifiche e morali". The same day, by coincidence, the papers were full of stories regarding legal investigations into this person's behaviour - the scandal of the month.

Scandals in Italy, however, are so frequent that are quickly forgotten.

Update: I hesistated between writing the phrase "scandal of the month" or "scandal of the week". I chose wrongly: today the newspapers speak of something new: "la più colossale frode di sempre".

Integrity

2010-02-06T00:34:00.000-08:00

I wrote recently about the tyranny of numbers when writing about double-entry accounting and the book Medici Money.

I was reminded of the subject reading an article by Peter Cameron called "Publishing and assessing mathematics". I also looked around his blog which is certainly worth visiting. Of particular interest to me is that he has begun an autobiography which describes life in Queensland at more or less the same time I was growing up there.

In the article, he writes about, and laments, the changes that have occurred in the assessment and publication of mathematics during his (and my) lifetime. His particular concern is how one might maintain the integrity of mathematical science in the context of an enormous increase in mathematical publication, and the use of numbers to evaluate scientific worth.

I agree with many of the things he says. However in my opinion he misses the main point.

My generation was seduced by the promise of grant money into accepting the numerical evaluation of research. Such evaluation, instead of being an incentive to improve the quality of research, has damaged mathematics. The result is that too many papers are published, many of which are now quite inadequately refereed even in journals.
We have produced too many mathematicians, a large proportion of whom will not find the employment they seek, but will scramble to publish as much as possible in the attempt. (The article reports that Peter has had 33 doctoral students; I had nine.)

This inflation is breaking the mechanisms for ensuring the integrity of mathematics.

Bits and pieces

2010-02-04T22:52:00.000-08:00

I haven't written for a few weeks. I don't know why. In January I was finishing courses. I have a couple of bits and pieces to report.

1) The University of Insubria. The Faculty of Science in Como, after essentially declaring war (the word guerra appeared in the papers) on the rest of the university in November and December, seems to decided against that strategy, at least temporarily. In December the rump of the faculty held a secret survey which, when released to the press, revealed that most members of the faculty wished to leave the university. But now the local newspapers have stopped talking about us, in favour of a local scandal in which one of the local bene shot an associate and tried to destroy the evidence by putting the offending head in a pizza oven. The faculty and the union decided to drop legal action against our request to transfer to the faculty in Varese.

2) Since we are moving faculty I have been looking at undergraduate Computer Science syllabuses. Computer science seems to have real difficulty deciding what to teach. The new course we are joining has (in proposal at least) several core mathematics courses but no core courses on automata, logic, complexity theory, recursive function theory, grammars, graph theory. The problem with mathematicians teaching informatica is that they have a very limited view of mathematics. The problem with computer scientists is that they have not decided if they want to describe a sequence of tricks, or if they really want a science.

3) I wrote recently about Tim Park's book "Medici Money". Afterwards I looked for reviews on the net, and it seems that I am completely outvoted. The reviews are uniformly glowing.

4) I wrote about John Baez's change of direction. I notice now that he has written "I’ve decided to change my research direction — so I don’t even want to give talks about topological quantum field theory, n-categories and that kind of stuff. I’d rather think about new things". In my post I said that he might consider politics like D. B*** but I don't think he would find that fun.

His announced talk at QPL2010 does not seem to be original work, apart from some extensions to n-category theory, and is about categories where the morphisms are matrices taking values in a rig, to categories of profunctors and spans, to the way star-autonomous categories act like commutative Frobenius algebras in the world of profunctors, the last being a report on work of Ross Street.

5) Another mistake in Andy Tanenbaum (I already wrote about one in 2005). Tanenbaum provides, as extra material to his book Modern Operating Systems, 2nd Edition a translation of the examples in Java. In particular he provides a semaphore class, which I have used without examination (not being a Java programmer). Up to this year it has always functioned as I expected. However this year in student's solution to a problem there arose a situation in which the semaphore class does not act as a semaphore! I am embarassed that I did not check earlier. I will write a post with details when I get a chance.

Category Theory 2010, Genoa, 20 - 26 June 2010

2010-01-17T11:59:00.000-08:00

The web site of CT2010 is now available.

The invited speakers are:
Olivia Caramello, Cambridge-Pisa,
Denis-Charles Cisinski, Paris,
George Janelidze, Cape Town,
André Joyal, Montreal,
Matias Menni, La Plata,
Mark Weber, Paris.

John Baez is changing course

2010-01-17T01:01:00.000-08:00

John Baez has announced that he is going to Singapore for a year, and at the same time is changing his research direction. He would like to try his hand "at some slightly more ‘practical’ endeavors", and has a "growing urge to help save the planet".

He is going to the Centre for Quantum Technologies, a research institute whose mission is to conduct interdisciplinary theoretical and experimental research into the fundamental limits to information processing, and is directed by Artur Ekert, who is a professor of quantum physics at the Mathematical Institute, Oxford University. (Bob Coecke, who uses category theory to study quantum information is also at Oxford but at the Computing laboratory.)

There John is likely to meet one of our Como physicists, Giulio Casati, actually the founder of the Como Science Faculty, winner of the Enrico Fermi prize (2008), Somaini prize (1991), and associate editor of Chaos, Solitons & Fractals. John may have more success than I in interesting Giulio in category theory.

The work John is developing on n-category cafe in a sequence of posts regards graphical reasoning in biological and physical systems. He might be interested in a paper of mine with Katis and Sabadini, "On the algebra of feedback and systems with boundary" (Rendiconti del Circolo Matematico di Palermo Serie II, Suppl. 63 (2000), 123-156), in which section 4.2 is called "Towards an algebraic foundation for electrical circuit theory". A version of the paper is available called here. Another paper which might be of interest is called "Systems with discrete geometry" and is available here.

Given his desire to save the world I have the sneaking suspicion that one day John will end up in politics like another young mathematician with name B***, who also wrote an article seeking to popularize category theory. (I regret to say that I found the article of B*** particularly unconvincing).

Medici Money

2010-01-07T09:31:00.000-08:00

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

2009-12-30T12:24:00.000-08:00

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

2009-12-19T08:21:00.000-08:00

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).

Honesty in Science

2009-12-11T06:42:00.000-08:00

Andre Joyal just sent a mail to the Category Theory list with a reference to an article of Richard Feynman linked here. The main point is that in science, as opposed to advertising, one should try one's hardest to expose the weakness of one's position, as well as its strengths.

I must keep that in mind when I write my next paper.

Snow

2009-12-01T14:30:00.000-08:00

We went to Colmar for the weekend driving via the San Gottardo tunnel. We had a delightful time there staying in Turckheim and visiting villages near Colmar, as well as visiting the city itself.

Unfortunately, on our return to Italy we were caught in a snow storm before the San Gottardo tunnel, and spent 7 hours blocked on the highway. We eventually managed, with the help of Italians also blocked, to get off the highway, follow a parallel road to a later entry point and arrive home after a trip of 12 hours. Usual time for the trip is 5 hours. Others who did not manage to exit from the highway (A2) spent 12 hours unable to move.

A new experience for me. Born in Brisbane I was 20 before I saw snow.

Como newspapers

2009-11-20T13:53:00.000-08:00

Como newspapers are up in arms about the problems of the Como seat of the University of Insubria.
We got front page coverage on the Corriere di Como, and strident articles also in the Provincia di Como.

They do not make clear that the Science Faculty of Como itself decided to close Informatica in Como months ago. An informatica course was not even presented to the Senate for consideration. The choice of the Science Faculty was instead to present Scienze Ambientale.

As a consequence informatica staff requested and were permitted to transfer to Varese (same university) to support the remaining informatica course of the University of Insubria - which lacked sufficient staff to continue otherwise. One ambientalist has been transferred from Varese to Como, and a further six from Varese will count towards the Ambientale course in Como.

Today there is a funny article in the Provincia (La Provincia di Como, 20 November 2009: Facoltà di Scienze a rischio Gli studenti corrono in aiuto) in which the reporter quotes a facebook page. The article's title translates as "Science faculty at risk: students run to the aid of the faculty". Unfortunately the reporter misread the Facebook site, the last post being in April, not November. Many of the students attached to that page were students of informatica, and Prof. Sabadini discussed fully with them at the time the actual situation. The meeting with the president mentioned in the article as occurring next week actually occurred in April.

The Provincia instead claims that the only response was from the president of the faculty who said: "... sono un calabrese coriaceo e stia tranquillo che farò di tutto perché questa facoltà, che è per qualità scientifica 'il pezzo pregiato' dell'Ateneo, non solo non sia ridimensionata ma ne esca rafforzata. ...".

The dangers of being a reporter in this electronic age! Reporters have the duty to double-check their sources. There were however such gross mistakes in the past - the present one joins classic errors like "Dewey defeats Truman".

Pietro Berra of the Provincia di Como

27th November 2009:Update I have decided not to write further on this issue except perhaps to report the final outcome. In my view the Science Faculty of Como has made serious mistakes of policy over the years, and is now in difficulty as a result. The main problem is that the faculty has not attracted sufficient students. On the closure of the informatics course the informatics staff have requested to transfer to Varese. It is the right of any staff memember to ask for a transfer from one seat to another. All the rest consists of decisions of the organs of the university and discussion which is now at the level of politicians. Basta.

The discovery of adjoint functors

2009-11-20T01:53:00.000-08:00

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

2009-11-18T03:24:00.000-08:00

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.

Informatica at the university in Como

2009-11-18T03:14:00.001-08:00

I have mentioned in an earlier post that, as a result of university reform, the faculty of science in Como decided to close the informatica course in Como. As a result we informatici asked to transfer to the seat in Varese (smae university - Insubria) to support the informatica course there (which has need of staff).

This caused tremendous excitement in Como, with many newspaper articles and television commentary (which I didn't see). The latest thing is that there has been a question in parliament in Rome.

We have the feeling of being a capro espiatorio (scape goat) for all the problems of the university in Como. Today there is a university senate meeting which may/will discuss the matter.

Yesterday there was a surprising development. It seems that after years of neglect of the Como informatica course we are in fact pregiati. Como, or some section of the Como establishment, wants our course to continue.

I don't think it will happen - it would require closing some course dear to the hearts of the Science faculty.

Update: Como science faculty presented to the senate the proposal to discontinue the Como infomatica course. The senate accepted this and decided to accept our transferral to Varese.
I assume that our Como degree will continue at least till current students complete, that is for two more years. I would like to record in a later post some facts about our laurea course. I think it was an excellent course and we worked hard to support it. In particular Nicoletta Sabadini made a huge effort towards its success.

Gavin Wraith's web pages

2009-11-10T22:19:00.000-08:00

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

2009-11-10T13:45:00.000-08:00

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.

Greek laptop

2009-11-04T01:47:00.001-08:00

This picture from a Greek vase was the logo of our department "Dipartimento di Scienze della Cultura, Politiche e dell'Informazione", a short-lived attempt at an interaction between Informatica and the humanities. The department closed recently (31 September 2009) as a result of the endless intrigues of Italian academic life.

If I remember correctly the department was formed in 2005.

Categorical algebras of relations

2009-10-30T02:02:00.000-07:00

I would like to discuss two different algebras of relations:
(i) the notion of allegory of Peter Freyd and Andre Scedrov;
(ii) the notion of bicategory of relations of Aurelio Carboni and myself.

These two notions begin with the idea that relations form the arrows of a category Rel, and more that the order between relations induces a 2-category structure on Rel.

That is, given relations $R:X\to Y$, $S:Y\to Z$ (i.e. $R$ a subset of $X\times Y$, $S$ a subset of $Y\times Z$) denote the composite as $R\circ S$; then composition is associative and has an identity. Further $R\subset T:X\to Y$, $S\subset U:Y\to Z$ implies that $R\circ S\subset T\circ U$.

After this common beginning the two notions diverge. The definitions take different operations and constants, and as a result the axioms are quite different. I don't want to go into all the details but concentrate on one particular aspect.

Allegories take as operations a) the intersection of relations $R\cap T:X\to Y$, and b) the opposite $R^{o}$ of a relation $R$. Then the main axiom is the modular law, namely that
\[(RS\cap T\subset (R\cap TS^{o})S.\]

Bicategories of relations instead take as operations $R\times S:X\times Y\to Z\times W$, and
$\Delta :X \to X \times X$, and $\nabla :X \times X\to X$
($\Delta$ is the diagonal relation whereas $\nabla$ is the opposite of the diagonal.)

Among the axioms are the requirement that $\Delta_X$ and $\nabla_X$ are the commutative comultiplication and multiplication of comonoid and monoid structures on $X$ and that $\Delta_X$ and $\nabla_X$ are lax natural; that is, $R\Delta\subset \Delta(R\times R)$ and $\nabla R\subset (R\times R)\nabla$.
But the main axioms are the so-called Frobenius equations:
\[(1\times \Delta)(\nabla\times 1)=\nabla\Delta,\]
\[(\Delta\times 1)(1\times\nabla)=\nabla\Delta,\]
and the separable axiom
\[\Delta\nabla =1.\]
(which first occur in our work).
It is immediately clear that there is a difference between the notions - allegories have no operations on objects and hence are likely to be more common. However our claim is that bicategories of relations are more natural. This is supported by the fact that subsets of our axioms are satisfied by many other naturally occuring examples, like 2D topological field theories, etc etc. The Frobenius axiom seems to be turning up all over the place. It is essentially an axiom of equality. We think the modular axiom is a trifle bizarre.

What I would like to do in this post is to explain why our axioms imply the modular law, exhibiting at the same time the graphical language of bicategories of relations.

Peter Johnstone missed an opportunity in the chapter on allegories in his book "Sketches of an elephant", Oxford University Press, 2002..

Some people however like the bizarre in mathematics. I think the modular law is an example of "formiche mentali".

Jobs for mathematics graduates

2009-10-29T22:35:00.000-07:00

Recently I have spoken to several Italian high-school teachers. Their advice to students proceeding to university is that the important thing is to do something you like. This seems to me to be dangerous advice. It is important not to do something you don't like, if possible. However, a student must consider future job prospects in making a decision. It is no good training for non-existing positions and then demanding that the positions be created afterwards. It is not reasonable to imagine that it is trivial to change after spending three or more years learning skills in one area - this is to discount the value of education. One should realize also that educators in an area have an interest in attracting students independent of job opportunities.

Contrast the following two documents: one is the advice of the Mathematics Department, New York University; the other is a blog by a mathematics graduate:

Mathematics Department, New York University
"Career Opportunities
The study of mathematics can lead to a variety of exciting professional careers. Basic research, engineering, finance, business, and government service are among the opportunities open to those with mathematical training. Moreover, with the increasing importance of basic science and information technology, prospects for careers in the mathematical sciences are very good. Mathematical analysis and computational modeling are important for solving some of the most pressing problems of our time - new energy resources, climate change, risk management, epidemiology, to name a few. We must strive to maintain our technological edge; mathematical skills will be crucial to this effort.
Some more specific business positions include portfolio analysis, design studies, statistical analysis, computer simulation, software design and testing, and other areas of operations research. There are extensive opportunities for mathematics in finance, the actuarial fields, and economic forecasting.
Many laboratories, both government and private, maintain independent research staffs that include mathematicians. Their work often deals with the development of new technology, including research in basic physics and software development, as well as applied mathematics. Numerical simulation, such as weather and climate forecasting, depends heavily on the use of supercomputers.
Practical considerations aside, there is the pleasure of learning, applying, and creating mathematics. Real world issues pose problems that can be studied by formulating and analyzing mathematical models. In some cases applications may lead to new mathematics, and a new branch of the science is born. In other cases abstract theory finds unexpected practical purpose. Working on research problems is exciting; solving difficult problems successfully is, for many, satisfaction enough."

John Armstrong's blog
"All the evidence I see is that mathematics, in and of itself, is worthless in the current job market. It seems to have value solely as training in addition to some other primary field of study. I would love to be proven wrong, but every rejection (most without comment) that passes reinforces this hypothesis."

Update The comment by Sean Carmody that follows is interesting. When a new area which needs mathematical expertize opens there may be opportunities for people with only mathematical degrees but for a limited time. Unfortunately the advice given to new students doesn't mention the limited time, just the successes. I had a similar experience: when I finished a masters degree in mathematics in 1966 (?) I looked at job opportunities. Programming was open to anyone. Now a mathematics student without programming experience has to compete with people with years of experience for such positions.

Trouble at n-category cafe

2009-10-29T00:40:00.000-07:00

One of the blogs I look at rather regularly is n-category cafe. A recent post Math: Folk Wisdom in an Electronic Age raises questions about the future of mathematical discussion on the web.

There seems to have developed contrasting opinions among the presenters of the blog. In brief, one group holds that blogs should be entertaining as well as informative. The other group has more serious intentions.

I think there is a place for entertaining blogs which at the same time inform. However there should be a clear separation between this level of discussion and precise scientific papers.

The danger from the entertainers' direction is that papers try to be entertaining and lose precision.

The danger from the serious bloggers is that serious-sounding blogs take the place of papers, while being pretentious but not precise.

A paper or a book is a concentrated form of knowledge which cannot be replaced by conversations. A paper or a book can be helped by the addition of informal discussion.

University reform in Italy

2009-10-28T02:29:00.000-07:00

I have written several times, always as a foreigner trying to understand the Italian mind, about university reform. I think however I have not emphasized an important (perhaps the most important) aspect. What follows is my imperfect understanding.

Money comes the the universities for two reasons - from research applications, and from the student enrolment.

Research money is fickle and allows one to employ temporary staff. (Research staff and graduate students are of course almost essential for certain areas of research.)

Student money is hard, and allows one to employ permanent staff. The desire to employ permanent staff in ones area seems to be a main driving force for Italian (maybe all) academics.

So what did Italian academics do in recent years? Create courses to attract students. Insubria university in Como created in Science an Informatica course and a Bene Culturale course. In Giurisprudenza the university created Scienze di Turismo and Mediazione Linguistica. These courses did attract students.

However the resulting money coming to the university from student numbers was used, not for permanent staff in the new areas, but for staff in the old areas.

With the contraction of the reform these new courses may/must close for lack of staff, with a resulting loss of a large proportion of the student numbers.

Megatrends

2009-10-22T07:03:00.000-07:00

I learnt the word megatrend listening to a talk of Federico Faggin in Milano a few years ago. Federico Faggin has his initials on the first microprocessor ever produced (Intel 4004). He also founded Zilog with Ungermann, and designed the Z80. And other things. So perhaps he has the right to talk of megatrends.

I think one of the megatrends of the 20th and perhaps 21st century is the use of computers in almost every phase of life, in particular for communication. It is perhaps comparable to the industrial revolution, and is changing the work people do in a similarly dramatic fashion.

Universities however seem to be rather bad at adjusting to megatrends. A professional academic is happy at new and exciting developments in his/her field, but new areas are invisible.

The University of Insubria seems to be just in the process of closing a Laurea in Informatica in Como. With the reform it seems to be the only possibility acceptable to the physicists, mathematicians, chemists and ambientalists, in particular as a result of the lack of investment of the Como Faculty of Science in Informatica over a period of some years. Fortunately it is likely there will be a laurea in informatica in Varese, but with a small investment in Informatica over the years, instead of losing the course in Como, the University could have had courses in both Como and Varese.

I think the lack of investment in Informatica has been a megamistake for Como.

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

2009-10-16T00:57:00.000-07:00

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 names

2009-10-14T09:13:00.000-07:00

Recently I have been thinking about the importance of standardizing definitions and names in Science.

I was looking at the notion of regular category, which is the correct setting for defining relations. Unfortunately this important concept has not settled completely. A regular category in the first place is finitely complete. But then some papers assume the existence of all coequalisers, but most (correctly) prove the existence of coequalisers of kernel pairs from a factorization system into extremal epis and monos, plus the fact that extremal epis are preserved by pullback (Joyal).

Unfortunately what I just called extremal epis are sometimes called strong epis or even special epis. Peter Johnstone in his Elephant book (which has a rather good treatment of regular categories) introduces another concept namely covers.

My point is that such a basic and important concept should not have a confusion of names or definitions.

However I really wanted to talk about a much more difficult problem, the naming of concepts in computer science.
The problem arises from two sources. One is that different forms of a concept have arisen in many different fields, and hence there are many existing names, usually with resticted sense, and hence difficult to use in an extended sense, with out upsetting the existing use. The second problem is confusion - the concepts have not been sufficiently analysed or a single name is used for several different concepts.

I could give a long list of examples. Let's take a few names and try to untangle them. The names I have in mind are "concurrent", "process", "system", "processor", "machine", "agent", "automaton".

Concurrent: the word appears to signify entities or behaviours of entities (two different things already) which run together, at the same time. In fact, the word has come to refer to, not entities, but behaviours which do not run together, but interleave.

Process: it is not clear in the literature whether process refers to an entity, or an entity in a state, or the behaviour of an entity. These are such fundamentally different things that they can't be confused.

System: the word system is so vague that it is difficult to use - but in the end we have resorted to using it in a recent paper. At least it is clear that a system is an entity.

Processor: is clearly an entity but seems to refer to a hardware component, so is insufficiently abstract.

Machine: similarly.

Agent: seems to be an entity but is used by many (Milner) to mean a process in a certain state (and what is a process?).

Automaton: seems like a good word for an entity, but a difficulty is that the word either is used in a very limited meaning (by finite state automata theorists) or there are too many uses for the word.

One more word, rather different. The word "series" has long been used in electrical circuit theory to denote a system physically constructed by a sequence of components. It does not mean that the behaviour is sequential although if the circuit contains pulses it may be. We used in at least one paper the word series composition to mean "communicating parallel composition" as it does in such circuits. I think we were mistaken to do so because series certainly suggests "sequential", which we definitely did not intend.

The nerve of n-category - with Michael Johnson 1987

2009-10-09T01:19:00.000-07:00

I see a recent post on n-category cafe explaining higher dimensional associativities. There is no reference to Ross Street's orientals (Ross Street, The algebra of oriented simplexes , J. Pure Appl. Algebra 49 (1987) 283-335; MR89a:18019) of twenty odd years ago. An old paper of mine with Michael Johnson might also be of some interest.

One of the effects of blogging is a certain loss of history, which is also a loss of content. Formal papers have always made some attempt at recording the history of ideas. I think blogging might well benefit from some increased formalism, since it seems inevitably to be taking over dissemination of research.

On cospans and spans II

2009-10-09T00:30:00.000-07:00

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.

Aesop on the importance of having decisive leadership

2009-10-03T00:46:00.000-07:00

Living in Italy, in particular working in Italian academia, makes one think frequently of the problem of good government. There are famous frescoes of Lorenzetti in the Comune di Siena called "ALLEGORIA DEL BUONO E CATTIVO GOVERNO".

We are now at a critical point in the University of Insubria in the discussion of University reform. It looks as if we may finally have to implement the 25% reduction in courses proposed by the minister (for universities which until now had the minimum number of teachers) - though Italians tell me that I am naive to imagine such a definite result. Some of us believe that decisive leadership is crucial at this time. I would prefer wise leadership. Maybe even benevolent leadership.

I suppose that is also naive. Consider the following story.

THE FROGS WHO WISHED FOR A KING

The Frogs were tired of governing themselves. They had so much freedom that it had spoiled them, and they did nothing but sit around croaking in a bored manner and wishing for a government that could entertain them with the pomp and display of royalty, and rule them in a way to make them know they were being ruled. No milk and water government for them, they declared. So they sent a petition to Jupiter asking for a king.

Jupiter saw what simple and foolish creatures they were, but to keep them quiet and make them think they had a king he threw down a huge log, which fell into the water with a great splash. The Frogs hid themselves among the reeds and grasses, thinking the new king to be some fearful giant. But they soon discovered how tame and peaceable King Log was. In a short time the younger Frogs were using him for a diving platform, while the older Frogs made him a meeting place, where they complained loudly to Jupiter about the government.

To teach the Frogs a lesson the ruler of the gods now sent a Crane to be king of Frogland. The Crane proved to be a very different sort of king from old King Log. He gobbled up the poor Frogs right and left and they soon saw what fools they had been. In mournful croaks they begged Jupiter to take away the cruel tyrant before they should all be destroyed.

"How now!" cried Jupiter "Are you not yet content? You have what you asked for and so you have only yourselves to blame for your misfortunes."

Steve Lack wins the Australian Mathematical Society Medal.

2009-10-01T08:26:00.000-07:00

I am very pleased to hear the news that Steve Lack has won an Australian Mathematical Society Medal this year.

He did his fourth year essay in Sydney with me on extensive categories (my interest arose from the use of distributive and extensive categories in Computer Science). I think however he learnt much more about the way of doing mathematics from Max Kelly. He seems to have Max Kelly's great style of clarifying and solving problems. He went on to do his PhD with Peter Johnstone in Cambridge. As I commented in a post I enjoyed his talk perhaps the most in Capetown this year.

One interesting aspect of the award was that Category Theory seems almost to have joined the main stream. I remember some years ago when Gus Lehrer prophesied that there would not be any more posts for category theorists at the University of Sydney - and after I left Sydney, and until now, this prediction seems to have been fulfilled. We can hope that maybe in the future category theory might return to the University of Sydney where it flourished for so many years, and gave such credit to the university.

Conferences: Category Theory 2010 (CT2010)

2009-09-30T02:58:00.000-07:00

Next years International Category Theory meeting will take place in Genoa, Italy.
Dates: Sunday, 20 June, to Saturday, 26 June 2010.

The Organizing Committe is:
Marco Grandis, Sandra Mantovani, Eugenio Moggi, Giuseppe Rosolini, Robert Walters.

Further details will be posted here, and naturally elsewhere, when available.