Chu Spaces Live


Google site search

ContentsIntroductionBasicIntermediateAdvancedFuturePolicyInfrastructure

Chu Spaces Live

LOAD CALCULATOR

This page originally authored by Vaughn Pratt of Stanford for the java version,
revised by Paul Nash of webscool for the Tcl version.

1   Orientation        

Welcome to Chu Spaces Live, and the Tcl chu calculator which can be downloaded directly from here.

Chu spaces provide a simple, universal, and well-structured representation for a broadly applicable range of objects. They are simple by virtue of being merely a rectangular array whose rows represent points and whose columns represent dual points or states. They are universal in that all conventionally transformable objects of mathematics are representable by Chu spaces within a single typeless framework. And the exercises below will acquaint you with the structure conferred by their operations.

The calculator provides hands-on experience with "live" Chu spaces. They are viewed through three windows each of which can be "positioned over" an existing space by selecting it from the menu above the window. More than one window may be set to the same space, and any changes to that space will take immediate effect in all those windows.

The initial environment provides the following spaces.

o 0 is the empty set, having no points and 1 state.
o T is the inconsistent space, having 1 point and no states.
o 1 is the singleton set, having 1 point and 2 states (when K=2).
o _|_ is the 2-element Boolean algebra, dual to (transpose of) 1.
o Pt2 is the pointed doubleton, self-dual with 1 constant and 1 variable point.
o Sp2 is the spinor, self-dual with 2 states whimsically called up and down.
o GF2^2 is the two-dimensional vector space over GF(2).

This small starting set can be expanded in two basic ways. First, new spaces can be built from old using the operations of process algebra and linear logic. The unary operations are to the left of the first or left-operand window, while the binary operations are between the two operand windows. The result of any operation then appears in the right-hand or result window. A re-executable script of the operations you perform is maintained below the three windows.

Second, new spaces can be built by editing existing spaces, using an editor that overlays the script (nondestructively) when you select it with the Edit button to the left of the script. Editing is performed by selecting a space, editing it, and parsing and saving the result.

2   Exercise 1: Sum        

For our first experiment, add 1 and 1 to make 2. Select 1 in both operand menus, select p in the result menu, and click on the + button at the top of the list of binary operations. This sets p to the discrete doubleton 2. This is a set with 2 elements, a Chu space consisting of 2 points and all possible states, namely 4.

Now perform p = p + 1 repeatedly as follows. Make p the left operand by selecting it from the menu of the first window. Now repeatedly click on + to add the right operand, 1, to p. Observe that with each click the number of points increases by 1 while the number of states doubles. With enough patience and a large enough computer every finite nonempty set can be built in this way. This instructional version of the calculator, running under a Tcl plugin interpreter rather, will however only let you get up to a maximum of 600 rows or columns so as not to impact on your local system.

The sum operation does double duty as an operation of both process algebra and linear logic. For process algebra it denotes noninteracting parallel composition. For linear logic, sum A+B is coproduct, one of the two additive connectives, A&B being the other.

3   Exercise 2: Creating new variables        

We will find it useful to be able to create new variables. The result menu lists four variables p,q,u,v plus the NEW entrybox. The NEW entrybox provides the means to create new variables. We shall use it here to create a variable called 2 in which we shall store the discrete doubleton, as follows.
  1. Type 2 into the NEW entrybox and press return.
  2. Set both operands to 1 and click +. This sets 2 to the result of 1+1.
  3. Select p again from the result window menu. This moves the result window away from 2 to protect it from being overwritten.
Although our choice of name "2" suggests that it is constant, 2 is treated as a variable just like p. To keep it constant never select it again in the result window. In case you forget and overwrite a space, a useful trick for reconstructing the lost space is to select the commands in the Script window below that produced that space and re-execute them by clicking on "Execute selected text".

4   Exercise 3: Product        

Having created 2 as in the previous exercise, select 2 in both operand windows. Multiply them together by clicking on * (the button below +) to set p = 2*2. This is a 4-point set, discrete like everything else we have built so far.

If we now make the left operand p we can repeatedly press * as we did with +, but this time each click doubles the number of points and squares the number of states. (We could get the same effect by setting both operands to p and pressing + repeatedly.) Pressing * with p initially 2 can only be done once, the second press would set p to a 16 point space having 65,536 states which is more than the calculator will handle.

Like sum A+B, product A*B works much as in arithmetic, and indeed satisfies such laws as A*B ~ B*A and A*(B+C) ~ A*B+A*C, where ~ means "is isomorphic to". Technically speaking A*B is tensor product of Chu spaces, the direct or categorical product A&B is less important in this context and is relegated to Exercise 7.

More about sets

5   Exercise 4: Concatenation        

So far we have only encountered sets. We now use the semicolon operation, as a variant of + called sequential composition or concatenation, to create ordered structures.

With both operands 1 and result p, click on ; to create a 2-point space having only 3 states. Note that the column 10 is missing. The significance of this is that the two points now form a chain, that is, they are linearly ordered, with the lower row 001 understood as being less than the upper, 011.

In the 00 state both points are 0. We pass to the 10 state by making the first point 1, and thence to the 11 state by making the second point 1. Thinking of points as events, for an event to have value 1 in a state means that it has happened. In this space the first event is constrained to happen before the second.

Notice that the first state is all 0's (no events have happened yet) while the last is all 1's (all events have happened). On the other hand the first event is 011, meaning that the second and third states are possible futures of the first event, while the second is 001, meaning that it has only the third state as a possible future. As far as changing 0's to 1's goes, events progress oppositely to states. This makes sense when you think about it; it is our first encounter with the duality of points and states, which live in mirror worlds.

Again we can repeatedly perform p = p;1 to form any nonempty finite chain. In this case p = 1;p produces the same chains, albeit by putting the 1 at the beginning (top) instead of the end.

Chains are very different from sets, having no exponential explosion of states: the number of states is only one more than the number of points. You could therefore press ; hundreds of times before the calculator started to slow down. On the other hand, starting from p = 1, you only have to perform p = p;p about 8 times to slow it down.

Now go back to p = 1;1 and form q = p*p, a 4-point space with 6 states. The chain p is a special case of a partially ordered set or poset, and the product of posets is another poset. The top and bottom points are the top (greatest) and bottom (least) elements of the poset, while the two points in the middle are independent of each other, the whole being in the shape of a diamond.

In terms of events, picture the first 1;1 as a sequence of two trains, and the second as a sequence of two stations. Then their product is what we have called the orthocurrence of two processes, denoting the train-station pairs, as arrival of each train at each station, in their proper order. The top event corresponds to the arrival of train 1 at station 1. The next two are for train 1 at station 2, independently of train 2 at station 1. Last, at the bottom, comes train 2 at station 2. Looking at the states, the first and last of these are respectively bottom and top, while the other four form a square. This is a distributive lattice having 6 elements, in the shape of a kite with a spike above and below.

For a different shape concatenate 1 and 2 by selecting them for the operands and clicking on ;. The row 01111 is the single point of 1, while the other two rows are the points of 2. Notice that the first row precedes the other two, which remain independent with respect to each other. This may be understood as a process in which the first event happens, after which the remaining two events happen without further constraint.

Repeating this in the other order, 2;1, yields a process in which the top two events happen independently, after which the third happens. Now try 2;2, which gives four events made up of two independent events followed (when both of them are done) by another two independent events.

6   Exercise 5: Choice        

The other basic behavioral connective besides concatenation is choice, traditionally written U. As with concatenation, 1U1 has two events and three states. However the missing state is 11, indicating that these two events are in conflict: either one can happen but never both.

Now try 2U2. Here we have 7 = 1+3+3 states: the initial state, followed by three more states depending on which of the two 2's are chosen.

Now perform C=1;1 by setting both operands to 1, creating C (for chain) as a new variable, and clicking ; (don't forget to move the result window away from C to avoid clobbering it). Now form CUC. Here we have four events and five states: the initial state followed by two more states on each arm of the branch taken depending on which copy of C we chose to perform.

7   Exercise 6: The Editor        

The editor lets you custom-build those spaces that you can't see how to build from existing spaces using the available operations. Editing can be done manually one entry at a time, or whole spaces can be entered from other windows by copying and pasting. These can be spaces saved from a previous calculator session by copying and pasting, or generated independently by some other program, or received as email, etc.

The editing process proceeds in three phases: select a named space to edit, edit it using the arrow keys to move around, select a destination for the space and press Parse>> to edit and store. If your parse indicates problems, re-edit and parse again.

To illustrate the use of the editor we shall turn the partial order 1;2 into a semilattice by deleting its second column. Create a new variable S and set it to 1;2. Now click Edit (near the bottom left) and select S from the editor's object menu beside (left of) the editor's leftmost window. This places an editable text version of S in that window. This places an editable text version of S in that window. Using the arrow keys to move around and backspace to delete, delete the second column of S, namely 100. Select the target space S by clicking on S in the middle edit listbox. Click on the Parse>> button, which if all went well turns the editable text into a "live" Chu space in the rightmost window stored in S.

What makes S a semilattice is that its three points are closed under bitwise OR. Before we deleted the second state this was not true: the OR of points 2 and 3 was the row 00111, which was not a point of the old S.

You can also select a contiguous top-left subspace of the space in the left edit window by adjusting the numbers in the points and states entry boxes. By setting them both to 2 and pressing Parse>> you can select the first two points/states of the space. This can be useful when working with spaces of different sizes that may have a similar structure, such as chains. You dont have to delete and then retype again to try a larger space.

The Tcl plugin does not have cut and paste functionality. To do this and following sections enclosed in tables that use cut and paste, you need to save the calculator and run it under Tcl Wish interpretor which you can download from here. Alternatively, you may prefer to type the space into the left edit window.

The editor is also the place to import Chu spaces from the outside world. Here is a space we will find useful later on.

1011
0101
0010
0001

Enter this into the calculator by starting out to edit a space named R (use NEW again for this). When you get to the point where you would type the space in, instead select the above space with your mouse and paste it into the edit window. Now parse and save the space under the name R.

You may notice that R has only 3 points. This is because the 3 is left over from the previous exercise. Change the points in the lefthand edit window to 4 to get the whole space and press Parse>> again.

8   Exercise 7: Linear Logic        

Besides modeling concurrent and sequential processes, Chu spaces model J-Y. Girard's linear logic soundly (and quite possibly completely judging by recent progress). The two operations common to both frameworks are sum A+B and product A*B. Concatenation A;B and choice AUB are not linear logic operations, being purely process algebraic. On the other hand with A&B and par A#B are purely linear logic operations, along with linear implication A-oB, intuitionist implication A=>B, perp A_|_, and the exponentials !A and ?A.

The perp operation, A_|_, is very important: it denotes the dual of A, defined as transpose. Perp is a unary operation (the unary operations are on the left of the left operand) which transposes the left operand and puts the result in the result window.

A&B and A#B are simply the De Morgan duals of A+B and A*B respectively. A&B is direct or categorical product, characterized by the law C-o(A&B) ~ C-oA & C-oB. A&B can be obtained as (A_|_ + B_|_)_|_. A#B is (A_|_ * B_|_)_|_, and distributes over &, that is, A#(B&C) ~ A#B & A#C. These are of interest primarily when one happens to be viewing the action of addition or multiplication from the dual side. All the exercises for sum and product can be repeated for with and par when all matrices are replaced by their duals.

More interesting is linear implication A-oB, definable either as (A * B_|_)_|_ or as as A_|_ # B. A-oB consists of the legal or continuous functions from A to B, while its states are pairs (a,y) where a is a point of A and y is a state of B.

In preparation for experimenting with A-oB, click on the Unique button to make it Multi. This is to make it easier to read each row of A-oB as a function. When Unique is on, every row of any given Chu space is unique (no repeated rows), and likewise every column. Changing Unique to Multi permits multiple occurrences of the same row or column, generalizing a well-known distinction between preordered sets and partially ordered sets. Sometimes A-oB naturally produces multiple columns (but not multiple rows unless B has multiple rows), whose elimination makes rows harder to parse.

For our first example of A-oB take both A and B to be 2. Click on -o and observe that the result has 4 points and 8 states. Each point of A-oB represents a continuous function f:A->B mapping each point a of A to a point f(a) of B. So the calculator claims there are four continuous functions from 2 to 2. This is as it should be, because A is in this case a set and all functions whose source A is a set are automatically continuous, no matter how many or few states the target B has.

Each function can be read as a list of values of f(a) as a ranges over the points of A, with each value being represented as the f(a)-th row of B. For example the first row of 2-o2 is 00110011, which we parse as 0011,0011, meaning that both elements of A are mapped to row 0011 of B, which is its first row. Thus this is a constant function. The second row of 2-o2 is read similarly as 0011,0101 denoting the identity function on 2. The third row is the function exchanging the two elements of 2, while the last is the other constant function.

For an example where the source is not discrete, consider Pt2 -o 2. This contains no functions because Pt2 contains a constant row 00, which must be mapped to a row of all 0's in the target, but 2 contains no such row. On the other hand GF2^2 has a row of 0's, namely the origin of the vector space it represents, and there are four functions in Pt2 -o GF2^2 because the independent (second) point of Pt2 is free to be mapped to any element of GF2^2. In fact there is a simple rule for determining the number of functions in Pt2 -o B: if B contains a constantly 0 row then there are |B| functions (writing |B| for the number of points of B), and otherwise zero.

When done with -o, click on Multi to return to Unique.

As our next linear logic connective we consider the unary operation !A. For finite Chu spaces over K = 2, !A yields the underlying partial order of A. This has the same points as A, which are taken to be ordered in such a way that a <= b just when it this is true in every column. Thus we have 001 <= 101 but not 010 <= 101.

The states of !A, still for K = 2, turn out to be definable as the closure under union and intersection of the states of A, together with the constantly 0 and constantly 1 states. An equivalent characterization of these states is that they are all those states that are consistent with the above partial order on A: any additional state would contradict some a <= b.

The importance of !A, for any K, is as follows. There are two very useful functions, a destroyer and a duplicator of points. The destroyer is the unique function 0:A->1 (thinking of 1 as {0}), while the duplicator is the function d:A->A*A defined by d(a) = (a,a). In general these functions need not be continuous: A may be too "brittle" to allow its points to be annihilated and cloned. However they become continuous when A is furnished with the extra states that turn it into !A. Thus the role of ! is to make A more laid back about these actions, a sort of alcoholic beverage for Chu spaces.

We could of course get this effect by declaring !A to be simply a set, furnished with all possible states. Our less draconian choice of states for !A is just those states sufficient to make annihilation and duplication continuous.

As an immediate application for 0:A->1 and d:A->A*A, we can define projection p:A*B->A, namely p(a,b) = a, as A*0:A*B->A*1 (where A:A->A is how we refer to the identity function on A, always continuous) satisfying (A*0)(a,b) = (a,0), which we then compose with g:A*1->A defined as g(a,0) = a, also continuous. Projection so defined is continuous provided 0:B->1 is continuous, since f*g:A*B->A'*B', defined by (f*g)(a,b) = (f(a),g(b), is continuous when f:A->A' and g:B->B' are. (This depends on definitions and theorems about continuous functions that we shall not pursue further here.)

The operation ?A is the De Morgan dual of !A, defined by ?A = (!(A_|_))_|_. Just as !A weakens A to a poset (when K=2), ?A dually strengthens A to a distributive lattice, the dual notion to a poset.

Applying ? to 2 yields the 6-element distributive lattice consisting of a diamond with a spike above and below. Try ? on other objects.

9   Exercise 8: Higher Dimensional Automata        

K larger than 2 is possible. The current limit is 10, ensuring that entries in the displayed Chu spaces will be a single digit from 0 to 9. Here we shall use K=3 to realize higher dimensional automata.

Whereas for K = 2 we took 0 to mean "not happened" for events and 1 "happened", for K = 3 we shall take 0 to mean "not started", 1 to mean "ongoing", and 2 "finished". We shall think of (0,1,2) as the lifetime of an event, regarding 1 as a primitive transition and 0 and 2 as its endpoints. Thus 1 is a 1-dimensional edge while 0 and 2 are 0-dimensional. We take the dimension of a state to be the number of 1's in that column. With K=2 the two states of an event were both 0-dimensional, whence all states had dimension 0 and there was no possibility of higher-dimensional automata.

Change K by going to the text box to the right of K, in the top right corner, and typing 3 then carriage return. The immediate effect is to change the appearance of 1 and _|_, which now have 3 states and 3 points respectively. All other Chu spaces, even those previously made by copying 1 and _|_ when K was 2, remain unchanged.

Repeat the exercises for sum, product, concatenation, and choice. Here n-point sets now have 3n states. Consider 2 = 1+1, which has 2 events and now 9 states instead of 4. Four of those nine have dimension 0, four have dimension 1 (4 1's in those states), and one, the state 11, has dimension 2 representing the overlapping activity of both events. These nine states correspond respectively to the corners, edges, and interior of a square automaton representing the independent execution of two events. This differs from a conventional automaton in that its interior is filled in with the state 11.

Using the editor, delete the state 11 from 2 and save the result under the name Mutex. This is the primitive mutual-exclusion process, which permits its two one-event constituents to happen in either order just so long as they do not happen at the same time. Mutex cannot be sensibly defined for a 2-event Chu space over K = 2, there being only 4 possible states, no subset of which corresponds sensibly to mutual exclusion.

The concatenation 1;1 still has 2 events, but it now has 5 states. Three of these have dimension 0 and are the ordinary states of a sequential two-transition automaton, while the remaining two have dimension 1 and constitute the transitions of that automaton.

The choice 1U1 also has 2 events and 5 states, which are the 3 ordinary states and 2 transitions of a V-shaped branching automaton.

Recall the train-station example of Exercise 4, namely the product or orthocurrence of 1;1 with itself to give all four train-station arrivals, in their proper order. Repeating this computation with K=3 yields 4 points as before, but now we have 13 states. These can be understood as the original 6 0-dimensional states, plus 6 edges and 1 square surface, i.e. the kite and two spikes viewed as solid.

These 13 states correspond to the 13 ways two intervals can be aligned. One can precede the other, or the start of one can be aligned with the end of the other, or they can overlap in various ways, a structure that attracted some attention in artificial intelligence circles a while ago. We can read off exactly which is which from the states. Thus 0000 is one interval entirely before the other, before the first train has pulled into the first station. 0001 is when the start of one is aligned with the end of the other, when train 1 is at station 1. 0002 is the state in which train 1 has left station 1 but no other arrivals have happened. We then have 2010 and 2100 as respectively train 1 at station 2 and train 2 at station 1, and 2020 and 2200 as their respective departures. But we also have 2110 as the case when those two arrivals are simultaneous, the one 2-dimensional state out of all 13. And so on.

10   Exercise 9: Abelian Groups        

Here we make more liberal use of K. For any given choice of K we shall normalize the values 0 to K-1 to the interval [0,1) by dividing them by K. Thus when K=5, the values 0,1,2,3,4 are to be understood as 0,1/5,2/5,3/5,4/5. The Chu calculator does not care whether 3 denotes the number 3 or the fraction 3/5, to it they are merely K distinct values. What we really want is K = [0,1), but finiteness considerations force us to settle for a representative set of rationals, any fixed choice permitting only finitely many abelian groups to be represented faithfully.

A group is normally defined as a set equipped with an invertible associative binary operation, such as the group of integers under addition or the group of nonzero reals under multiplication. A group is abelian when it adds the requirement that the binary operation be commutative.

In place of that representation we represent the finite abelian group A as the Chu space A having the same points, and having as its states all group homorphisms to the group [0,1) of reals under addition mod 1. In this group 2/3 + 2/3 = 1/3. It turns out that these homomorphisms, called group characters, are in 1-1 correspondence with the group elements. Thus this way of representing abelian groups as Chu spaces yields square Chu spaces. The entry at point a and state x is x(a), the value of the homomorphism x at the group element a.

Set K=6. This is enough to represent the abelian groups of order 2, 3, and 6, of which there is one of each, along with one of the two groups of order 4, the Klein 4-group V4, but not the other, Z4, as 4 does not divide 6 and so no element of order 4 can be a point of a Chu space over 6. Copy the following spaces into the editor, set K to 6 for each (just above the edit window---this step should be redundant but is necessitated temporarily by a bug), and parse and store them as Z2, Z3, Z6, and V4 respectively, remembering to set the points and states where necessary.

00
03

000
024
042

000000
012345
024024
030303
042042
054321

0000
0033
0303
0330

Experiment with G-oH for various choices of G and H from among Z2, Z3, Z6, and V4. Observe that the number of maps between Zm and Zn in either direction is gcd(m,n). For example Z3 -o Z6 has 3 maps, Z2 -o Z6 has 2 maps, and Z2 -o Z3 has only 1 map. On the other hand there are 16 maps from V4 to itself (corresponding exactly to the 16 linear transformations of GF(2)2 to itself), and 4 maps between V4 and Z6.

Problems (i) Experiment to find an empirical rule for the number of maps between V4 and Zm. (ii) Prove the correctness of your rule.

11   Exercise 10: Scripts        

Clicking on Script at the bottom left will bring up the script, a running record of all operations performed since the beginning.

Selecting any sequence of previously performed operations from the script and pressing the "Execute selected text" button will perform those operations again on the current state of the calculator.

It is easy to get carried away with scripts and ask the calculator to produce objects exponentially larger than your computer and that take a lifetime to compute. It is easy to get carried away with scripts and ask the calculator to produce objects exponentially larger than your computer and that take a lifetime to compute. If the status window at the top says "Executing" and nothing much seems to be happening, the current computation can be aborted by pressing CANCEL. This should work, but if not you may have no choice but to restart your browser. The calculator checks that a compuation is not going to exceed reasonably small bounds and gobble up computer memory. Because of the exponential nature of these computations, if they do not return an answer within a minute or so, then they are quite likely to take months or years to compute, so there is no point in waiting "just another minute" for the operation to complete.

Like the editing window the script is editable. While this does let you change old entries this is not the intended purpose. Rather it lets you append new commands that you wish to execute. You can type these in anywhere in the script, then select what you typed and click "Execute selected text". Use the existing script as a guide to what you can say. The main thing to note is that a space is required to separate each token in the script including the comma seperating commands.

Here is a script that will set K to 3, set p to 1;1, and set q to p*p.

3 , p = 1 ; 1 , q = p * p ,

Select it, paste it into to the script window, select what you just pasted, and click Execute. You should get the 4 point 13 state Chu space at the end of Exercise 7.

As with Chu spaces, scripts can be saved to files and retrieved, or sent in email to other users of the calculator.

12   Exercise 11: Rigidity        

Sets are the least rigid of all mathematical objects. They are like pure sand, with not even a trace of glue to stick their elements together or even vaguely correlate their movements, which are completely independent. All other objects are more rigid than sets.

In this exercise we explore how rigid things can get. We will do this by considering A-oA for various spaces A, whose rows are all ways of transforming A into itself, called the self-maps or endomorphisms of A. A-oA is never empty because there is always at least the identity map. The automorphisms are those endomorphisms that are bijections; while these are of great interest the calculator is regrettably not set up to single these out conveniently.

Once again we should switch from Unique to Multi, the better to read off the functions as rows of A-oA.

We have already seen that there are 4 endomorphisms of the set 2. This is true regardless of K, try it for a few larger values of K, remembering that 10 is the limit.

Although 1;1 has the same number of points as 2, it has only three endomorphisms, lacking the automorphism that exchanges the two points. Loss of endomorphisms is the typical symptom of increasing rigidity. 1;1 is a poset (partially ordered set) and hence its endomorphisms are monotone functions. Reversing order violates monotonicity.

Now set U to 1U1 (with Unique on) and consider U-oU (with Multi on), that is, perform

Unique , U = 1 U 1 , Multi , p = U -o U ,

Now we have only two functions. Whereas 1;1 lost exchange, 1U1 lost the two constant functions, making it even more rigid than 1;1. This behavior is the same as for Sp2, which also only allows identity and exchange. 1U1 is Sp2 with an extra state of all 0's, which however does not change the endomorphisms of Sp2.

Now try Mutex, the result of deleting the 11 state from 1+1 when K=3. Whereas 2 had four endomorphisms, Mutex only has two, again identity and exchange just like Sp2 and 1U1. All three disallow both events happening simultaneously, which would be contradicted by a function that identified the two events by mapping them to the same event.

Can Chu spaces get even more rigid than this? Any space with only one point or one state is rigid, but that's only to be expected. For K=2, it turns out there are no 2x2 or 3x3 rigid Chu spaces. There are however several rigid 4x4 spaces, in particular the following.

1011
0101
0010
0001

0100
1010
1101
1110

1011
0101
0010
1001

0100
1010
1101
0110

Enter these as R, NR, S, and NS respectively (N for Not). Now try A-oB for A, B set to any two of these. Notice that when A and B are set to the same space there is only one endomorphism, the identity, and when they are set to any two distinct spaces there are no maps between the two spaces at all. Not only are these spaces rigid with respect to themselves, they are noncommunicative among each other, the ultimate in rigidity.

13   Universality of Chu spaces        

We have by now seen a great variety of computational and mathematical objects represented as Chu spaces. We have seen concurrent and sequential processes, sets and Boolean algebras, posets and distributive lattices, groups and vector spaces, and yet all this has merely scratched the surface. The matrix structure, a mere table of numbers, is deceptively simple, hiding a rich tapestry of structure.

What are the limits of Chu spaces? There are some obvious limitations, such as the exponential state explosion that makes sets far bulkier than chains, the counterintuitive encoding of structure lurking in an ostensibly unstructured homogeneous matrix, and the inevitable mismatch between general structure and the myriad detailed requirements of domain-specific modeling.

One can nevertheless reasonably ask where the vein of rich mathematical structures starts to peter out. The answer is that, in at least two technical senses, Chu spaces are a universal Theory of Everything.

The first sense is that every category of n-ary relational structures, with or without topological structure, embeds fully and concretely in the category of Chu spaces over 2n, or 2n+1 when there is nondiscrete topology. That is, every such structure A can be represented as a Chu space having the same points (concrete embedding) whose matrix entries can be viewed as bit vectors of length n or n+1, such that the continuous functions between the representing Chu spaces are all and only the homomorphisms between the represented structures (full embedding). The original proof of this appears in [Pr93], for a smoother recent account see [Pr97].

The second sense is that every small concrete category C, no matter how randomly organized, embeds fully and concretely in the category of Chu spaces over the set of arrows of that category. That is, each object c of C with underlying set U(c) can be represented as a Chu space having U(c) for its set of points such that the continuous functions between any two representing Chu spaces are exactly the functions (morphisms f:c->c' made concrete as U(f):U(c)->U(c')) between the represented objects c and c'.

As a structurally attractive variant of this embedding, a symmetric "bi-Yoneda" embedding is possible for the special case where the concreteness of the embedded category is derived from its arrows by taking the elements of an object to be the set of arrows to that object.

One caveat about any universal category is that the embeddings of particular categories in various corners of the general category cannot be expected to preserve limits and colimits. In particular sum or product in a subcategory of C will not in general be sum or product in C.

This phenomenon is not peculiar to categories, it is already encountered with lattices, where the sups and infs (joins and meets) of a sublattice L' of a lattice L need not be those of L, i.e. sup F(X) = F(sup X) need not hold where F:L'->L is the embedding of L' in L. In particular when L' is sparsely distributed in L, the least upper bound in L' of a subset X of L' may be a lot further away from X than when computed in L, since L may contain upper bounds on X that are smaller than all those in L'. The best one can say in general is that sup F(X) <= F(sup X).

The analogous observation holds for objects such as processes, groups, and vector spaces represented as Chu spaces. Given an embedding (faithful functor) say F:Vct->Chu, we cannot rely on F(A+B) being isomorphic to the sum (coproduct) F(A)+F(B), the best we can do in general is to promise a canonical map F(A)+F(B) -> F(A+B). For (categorical) product A&B the map goes the other way: F(A&B) -> F(A&B). Appearances notwithstanding, tensor product A*B is actually a colimit and the canonical map, called a tensorial strength, is therefore as for sum, F(A)*F(B) -> F(A*B).

As an example of such a tensorial strength, take A = GF(2)2 as the 2-dimensional vector space over the two-element Galois field GF(2), and compare F(A)*F(A) with F(A*A) where A*A is tensor product of vector spaces. F(A) = GF2^2 in the menu. Writing each of the 16 linear transformations from A*A = GF(2)4 to GF(2) as a column, we obtain the Chu space F(A*A) =


0000000000000000
0101010101010101
0011001100110011
0110011001100110
0000111100001111
0101101001011010
0011110000111100
0110100101101001
0000000011111111
0101010110101010
0011001111001100
0110011010011001
0000111111110000
0101101010100101
0011110011000011
0110100110010110

To see how close F(A)*F(A) gets to this, select GF2^2 for both operands and click on *. The result has the appropriate 16 states but only 10 points. In fact F(A)*F(A) is a subspace of F(A*A), with the embedding (which turns out to be continuous) constituting the tensorial strength F(A)*F(A) -> F(A*A). Writing p = 0101010101010101, q = 0011001100110011, r = 0000111100001111, s = 0000000011111111, the 10 points of F(A)*F(A) are 0, p, q, r, s, p+q, r+s, p+r, q+s, and p+q+r+s, missing are p+s, q+r, p+q+r, p+q+s, p+r+s, and q+r+s. Problem: Explain why.

14   Credits        

The calculator was written and documented by Larry Yogman in Java. Earlier versions were written by Vineet Gupta in C and by Russ Allbery in C++. The Tcl version of the calculator was written by Paul Nash of WEBSCOOL.

The general categorical notion of a Chu space originated with Michael Barr based on an idea in George Mackey's 1945 thesis and was studied by Barr's student Peter Chu, whose master's thesis appears as an appendix to Barr's 1979 book "*-autonomous Categories." The more concrete set-based notion of Chu space was first studied by Yves Lafont and Thomas Streicher in LICS'91, who called them games.

Vaughn Pratt wishes to acknowledge his student Vineet Gupta who collaborated in the development of Chu spaces as a model of concurrent processes [Gup94]. Mike Barr for the original idea and some excellent suggestions of directions to pursue, to the participants in my courses and tutorials on Chu spaces since 1993, to my students Anna Patterson and Harish Devarajan who have taught me much about Chu spaces, and especially to Gordon Plotkin for several fruitful summer collaborations on Chu spaces.

Vaughan Pratt
pratt@cs.stanford.edu.

©2000 - 2006 WEBSCOOL This page last updated 31 May 2006. All rights reserved - including copying or distribution of any portion of this document in any form or on any medium without authorisation. For more regarding the copyright.