IFIP WG2.2 40th Anniversary Meeting (3): Utility of categories

This comment arises from a question: at one of the coffee breaks a participant asked Furio Honsell what results can be proved more easily using categories.

I think it is a question category theorists should be able to respond to with easily understood examples.

I make an analogy with ring theory. Perhaps the first useful thing about rings is Gauss's observation that there is a homomorphism from Z to Z mod m. Of course you don't need to mention rings in talking of this homomorphism but only by avoiding the word, not the concept. This homomorphism (reducing modulo m) immediately gives results.

Example 0: x*x-3*y*y = 19 has no solutions in integers (an infinite problem).
Proof: consider modulo 4. The left had side can be 0,1 or 2 modulo 4 but never 3.
The right hand side is 3 mod 4. Contradiction.

There should be results almost as simple for categories. I intend to make a list.

Example 1: (but too complicated for what I would like) The fundamental group pi_1 is a functor from (pointed) Top to Groups. Futher pi_1(circle)=Z, pi_1(disk)=0, so there cannot be a continuous map Disk->Circle such that
Circle->Disk->Circle = identity, because there are no functions Z->0->Z which compose to be the identity.

Example 2: (discussion with Aurelio Carboni) Consider the category D of open intervals of R, and differentiable functions, and the category L whose objects are of the form RxU (U an open interval) and whose arrows from RxU to RxV are pairs s:RxU->R, f:U->V where s(-,u) is linear, and f:U->V is differentiable; composition is usual composition of functions. Then differentiation is a functor from D to L. This is just the chain rule.

Application: The extrema of exp(cos(x*x)) occur at the points sqrt(n*pi) and their negatives. Proof: differentiate using the chain rule, and look for zeros.
Everyone knows this from a first course in calculus, but just as modular arithmetic uses rings, these calculations use composition of functions and the functoriality of differentiation.

(Comment by Aurelio: I would phrase the content as follows:
The graphs D and L are categories such that the obvious graphs morphism is a functor iff differentiable maps compose, iff chain rule holds. Obviously D and L can be applied to any choosen class of composable differentiable maps.)

Perhaps a simpler version of this example would be to take D to have objects R^n (n=0,1,2,3,..) and L could even be the same as D. Then diff takes R^n to R^(2n), and
f:R^n->R^m to a polynomial g:R^(2n)->R^(2m) such that if u, v are in R^n then
g(u,v)=(f'(v)(u),f(v)), where f'(v) is the linear function approximating f at v.
The fact that diff is a functor is the chain rule for polynomial functions of
several variables.


Example 3: (Burnside Lemma) Consider a finite groupoid H. It is obvious that in a connected component C of H the homs between any pair of objects have the same number of elements, k_C say. So the number e_C of endomorphisms in the component C = k_C x number of objects in C. But the number n_C of arrows out of an object in C is also k_C x number of objects in C. Hence e_C=n_C.

Hence e_H, the total number of endomorphisms in H, = sum over the components C of n_C.

Application: (from Wikipedia - counting the number of distict cubes painted with 3 colours) Consider the rotation group of the cube - it has 24 elements. Consider the groupoid whose objects are the 3^6 cubes coloured with three colours, and whose arrows are the rotations transforming one coloured cube into another.
The connected components of this groupoid are the distinct 3-coloured cubes.
The number of arrows out of any object is always 24.
Hence the total number of endomorphisms in the groupoid = 24 x number of components.
That is,
number of distinct 3-coloured cubes = 1/24 x number of 3-coloured cubes fixed under rotations.
There are 3^6 cubes fixed uner the identity.
There are 6 x 3^3 cubes fixed under the six 90-degree face rotations.
There are 3 x 3^4 cubes fixed under the three 180-degree face rotations.
There are 8 x 3^2 cubes fixed under the eight 120-degree vertex rotations.
There are 6 x 3^3 cubes fixed under the six 180-degree edge rotations.

Hence the number of distict 3-coloured cubes is
1/24 x (3^6+6x3^3+3x3^4+8x3^2+6x3^3) = 57.
---
This is usually considered an application of group theory (and hence of categories). But in my view, as above, there is a groupoid involved.

Example 4. to develop In close analogy to the example above regarding congruences, facts about systems may be deduced using instead various compositional simulations.

Example 5. to develop The free strict symmetric monoidal category on one object is the category P with objects natural numbers and arrows permutations. The category S with objects natural numbers and for each object n two arrows + and - from n to n, is a strict symmetric monoidal category with symmetry -:1+1->1+1. The induced functor sign:P->S is very useful in proving that various games have impossible reachable states - ex Rubik's cube etc.

Example 6. to develop Metric spaces and enriched categories

Example 7. to develop Kleene theorem and enriched categories

IFIP WG2.2 40th Anniversary Meeting (2): State Machines

Lamport and Boerger in their talks emphasized State machines.
I have a problem with the name.

Systems have two aspects: perhaps the simplest model of a system is a graph; that is, it consists of states (vertices, points, being) and transitions (actions, processes, edges, motions, becoming).

To concentrate on one of these is a mistake. It is somehow related to the classical view that mathematics is about sets (ZF), rather than the idea that sets *and* functions are primitive (Lawvere).

Of course functions may be thought of particular sets, just as memory allows actions to be stored as states, but not to regard functions and actions as primary is to distort the theory.

In principle, systems interact sequentially through states, and in parallel through actions.

I don't know why the name *automaton* has been abandoned - seems to be historical, and neutral with respect to states and actions. It should be rescued from the overstrict use by classical language theorists.

Further thoughts (16 October 2006) The usual meaning of a program to a programmer is that statements of a program are commands, i.e. actions or processes, and between the commands are states, often not represented explicitly. This point of view means that a program is a composition (in an approprate algebra) of basic programs; i.e. the program text is an expression, in an algebra of programs.

On the other hand, functional programming, and process algebras, take the program text to be state.

It is clearly correct to consider programs which have as part of their state text, plans, programs, specifications etc. For example the DNA in a human cell is a plan for the development of the cell. In fact one would expect most programs to have an internal model of themselves as state.

However it seems to me of fundamental importance to separate program as state from program as a composition (expression) of processes.

IFIP WG2.2 40th Anniversary Meeting (1)

From 11th to 13th September 2006 I attended a meeting of IFIP WG2.2 in Udine.
I am still thinking about issues that arose at the meeting. There was a considerable clash of views - in particular between those presented by Leslie Lamport and those of Gordon Plotkin.
I am hoping that the video produced at the conference becomes publically available so that I can check the correctness of my impressions.

Lamport made some extremely negative comments about Process algebras, Petri nets etc. He claimed that all you needed to understand concurrency was "mathematics", by which he intended set theory and first order logic.

He claimed that Process algebras had produced no results (undertanding?) about concurrency, illustrating his remarks by a challenge: is it possible to obtain mutual exclusion between processes (at a high level)without already *assuming* mutual exclusion with respect to access to the memory?

Part of the problem of answering this question is what physical assumptions you make on reading and writing to memory.

My opinion:------------------------------------------------
It is fundamental to make the assumption that it is possible to read and write to the same memory in the same discrete time interval; i.e. reading and writing may be made simultaneously.

This is not to say that for all mechanisms for reading and writing this is possible. In addition we are looking at the world at the level of discrete behaviour - that is, a continuous implementation involves arbiters.

Argument (N. Sabadini): If it is impossible to read and write at the same time, then it is impossible to listen to someone speaking.

Argument (mathematical): the identity process I, which outputs exactly the signal input, has the property that reading occurs simultaneously with writing. If you require that reading occurs after writing then this process does not act as an identity under composition with other processes - I*P is not P but P with added delay. The identity process is as important for an algebra of processes as zero is for an algebra of quantities.
------------------------------------------------------------------------

Under this assumption about reading and writing Lamport showed in 1974 that mutual exclusion with respect to the memory is not necessary for higher level mutex [A New Solution of Dijkstra's Concurrent Programming Problem, Communications of the ACM 17, 8 (August 1974), 453-455].