Previous: Inherited Structure Up: Chu Spaces from the Next: Representing general structures with

# Abstract Structure

In this section we shall identify the states of any extensional Chu space (A,r,X) with the dual words representing them. Thus instead of an extensional Chu space being (A,r,X) with being injective, we have just (A,X) with r(a,x) being defined implicitly as x(a) (application of to ).

Define a property of a Chu space (A,X) to be any superset of X that is a subset of . The discrete Chu space has only the one property, namely itself, which we identify with the vacuous property . In general the properties of form the set , namely all ways of adding new columns to .

Given two sets A and B, a function induces a map of properties sending the property to the property . This is true independently of the choice of making A into a Chu space (A,X). When F sends every property of to a property of , i.e. when implies , we call f a homomorphism of Chu spaces. The following is easily seen.

Proposition 4   A function is a homomorphism of Chu spaces if and only if it is continuous.

Proof:   If f is a homomorphism from (A,X) to (B,Y) then it sends the property X to a superset of Y. But this is equivalent to saying that for every column , is in X, whence f is continuous.

Conversely, suppose f is continuous. Let be a property of . We wish to show that is a superset of Y. But this is just the requirement that every satisfies . Since f is continuous we have the stronger property that .

This notion of property is quite abstract, and it will therefore be helpful to develop some intuition about it to demonstrate its relationship to more conventional notions of property.

To begin with, its generality notwithstanding, this notion of property is internal to the Chu space being described, since it is defined in terms of a fixed carrier A and alphabet . We cannot use it to express properties that refer to other Chu spaces, such as the property of being the smallest Chu space meeting some condition.

Some intuition for the scope of this concept of property can be built up as follows. We call a property atomic when it excludes exactly one state. The intersection of two atomic properties excludes both their respective states and thus corresponds to conjunction, yielding a compound (non-atomic) property. By allowing arbitrary conjunction we can express any property of a Chu space as a conjunction of its atomic properties; in particular itself can be expressed as the conjunction of all its atomic properties, namely those states absent from .

When , a natural presentation of an atomic property is as where is a list of the points projected by the property to 1 and lists the remaining points, those projected to 0. If we interpret points as propositions that may be either true (1) or false (0), and take to be the conjunction of its members and the disjunction, then is the logical expression of this atomic property, since it is false in the state excluded by that property and true in all other states.

This language generalizes to larger alphabets by providing a region for each letter. With three letters one could write something like , where every letter appears in exactly one , and describes the state in which each letter in has value i.

Every property of a Chu space can be expressed as a conjunction of atomic properties of , which therefore can serve as the constants of a description language for . But if we insist on atomicity for the constants of our language, it may be unnecessarily rich.

Consider a Chu space having atomic properties whose excluded states differ from each other only at one element a, which is assigned a different letter of in each state. Instead of listing all of these properties, we could simply take one of them and drop a from it, which would say the same thing. More generally if the space had atomic properties which collectively were independent of n points in the same way, we could again simply take one of those properties and drop any mention of all n of those points.

These considerations lead to the notion of an axiomatization as a set of properties, not necessarily atomic, whose conjunction is the property X of being the Chu space (A,X).

We can take this notion a step further by defining a language for a set A to consist of a set of possible properties of A. Each such property is some subset of . The purpose of such a language is to specify Chu spaces in a more conventional way than simply by giving the whole matrix, namely as the conjunction of the available properties.

For example, take and regard states as subsets of A. We can specify those Chu spaces representing a partial ordering of the set A by taking the language to consist of one property for each pair (a,b) in A2. The property associated with (a,b) would exclude all states containing a but not b, and hence express the relationship . A partial order can now be defined on A by forming the conjunction of those properties sufficient to express that order.

The advantage of this particular language is that each property can be named by naming just a and b, which for large A requires many fewer bits of information than needed to identify even one state let alone the many needed to identify the whole partial order.

For another example, still with , take the language to consist of one property for each triple (a,b,c), namely the property whose states are all those satisfying . With this language we can equip A with the structure of a join-semilattice by listing one such property for each pair a,b in A, choosing c to be whatever the join of a and b happens to be in that semilattice.

If we list only a subset of those properties then we will have specified a partial join-semilattice, one for which the join operation is defined only for some pairs. Continuous functions from such a structure will preserve only those joins that exist. In particular we can specify an arbitrary partial order by listing only those triples (a,b,c) such that a and b are comparable in that order, in which case c will always be the larger of a and b, being their improper join. Continuous functions from such a structure will then preserve only the partial order, that is, they will simply be monotone functions. Even if two incomparable elements happen to have a least upper bound in that partial order, continuous functions need not preserve that least upper bound, i.e. they will not recognize least upper bounds as being part of the signature.''

Previous: Inherited Structure Up: Chu Spaces from the Next: Representing general structures with
Vaughan Pratt
1998-03-14