Previous: Transformation Up: Chu Spaces from the Next: Abstract Structure

# Inherited Structure

From now on we shall treat only biextensional Chu spaces. Most of what we say here could be applied to general Chu spaces provided we substitute a'' for the'' and (same representation) for =. However this complicates the story without any real gain. It would be like studying preordered sets instead of partially ordered sets, where the notion of the least upper bound of a subset must be generalized to that of a clique of least upper bounds, with no essential advantage to the elementary theory.

Up to this point we have dealt with A, X, and as unstructured sets, but with the promise that by representing the elements of A as words we would somehow impose structure on A.

In the next section we shall define a general but extremely austere notion of structure. The austerity takes some getting used to, so by way of motivation we first consider in this section a less general but more familiar notion of structure which we shall show is preserved by continuous functions. We illustrate this with three examples, pointed sets, posets, and semilattices.

The class of all relational structures of a given signature is closed under both arbitrary product and substructure. Hence if we equip the unstructured set with a relational structure, chosen completely arbitrarily, then this structure is inherited by , and thence by any subset thereof.

For example if we order the set so that , then this order is inherited by every Chu space over in the usual way: just when for all , . This is just the ordinary inclusion order on 2X when understood as the power set of X.

What we shall show is that continuous functions preserve the structure inherited from . What is remarkable about this is that the notion of continuity was defined without reference to that structure, regardless of how rich or combinatorially complex that structure might be.

Let us begin with the simple case of declaring one element of , say 0, to be a constant (definable as a unary relation holding just at 0), making a pointed set. Pointed sets transform like ordinary sets except for the requirement that the constant in the source be mapped to the constant in the target. Now consider for any set X. The induced constant in is the constant word . This is as in universal algebra, where the n-th direct power of an algebra with a constant contains that constant as a constant n-tuple.

Now suppose appears in , call it . Then every projection of onto sends to 0. Let be continuous. Then every projection of to must send to 0, or we would have a projection of whose composition with f fails to be a projection of . Hence must itself be the constantly zero word.

But this behavior of f must hold even if we do not equip with any structure, because the definition of continuous function is independent of any structure we might assign to . That is, constant words must be preserved by continuous functions: not only must always be mapped to (of the appropriate length) but must be mapped to and so on.

We now pass from as a structure with one or more constants to the above example ordered by . Any Chu space (A,r,X) over this alphabet, viewed as a subset of the power set of X, becomes a set of subsets of X, with the inherited order being the ordinary inclusion order.

Proposition 2   All continuous functions between two Chu spaces over 2 are monotone with respect to the inclusion order.

Proof:   Suppose to the contrary that in but the continuous function is such that . Hence for some projection , but . But must be a projection of , whose just-observed behavior contradicts .

For our third and last example, furnish with the usual join or disjunction operation . This induces a partial join operation on defined as the join (bitwise OR) of words of . If for any two words a,b of that join is itself a word of , call it , then we say that is defined at (a,b).

Proposition 3   Whenever is defined in and is continuous, then is defined in and equals .

Proof:   Suppose not. Then there must exist a projection with . But as before, must be a projection of , giving us a position (element ) at which the alleged fails to be the join of a and b after all.

Common to these proofs is the existence of a refuting state of , which is turned into a refuting state of by composing it with f. This technique generalizes in the now obvious way to any relational structure we might impose on .

Now one might deduce from all this that in order to preserve every possible relational structure we can think of for , continuous functions must be terribly constrained. In some situations this is indeed the case: for example if contains a constant word and does not contain the same constant, there is no continuous function from to .

But in some situations every function from to can be continuous. This happens in particular when is the dual of the Chu space consisting of all words of length X. In this case a projection from to is just a word of , of length X. But contains every possible word of length X. Hence the test as to whether is a projection of must always succeed, whence every function from to any Chu space whatsoever will be continuous. Such an therefore behaves like a pure set, an object devoid of structure, which we call a discrete Chu space. This is the Chu counterpart of a discrete topological space.

This way of constructing discrete spaces ensures that no matter what relational structure we equip with, and hence , all of this structure may be eliminated by shrinking enough, namely to size double-logarithmic (with base ) in the size of (since is discrete when X is ).

So just how much relational structure can we equip with? The answer is that it suffices to take all possible relations of all possible arities on , including infinite arities. For arity X (as a set of variables in preference to just a number) these form the set of all X-ary relations on . One set X of each cardinality suffices. Most of these relations will be obtainable by composition from a very small basis. When , X-ary relations on 2 for finite X are just X-ary Boolean operations, for which a sufficient basis is implication and the constant 0. More generally, with still 2, the maximal structure with which we may equip is that of a complete atomic Boolean algebra. If we ignore questions of concreteness, this remains true for larger [Pra95].

Previous: Transformation Up: Chu Spaces from the Next: Abstract Structure
Vaughan Pratt
1998-03-14