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 $\equiv$ (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 $\Sigma$ 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 $\Sigma$ with a relational structure, chosen completely arbitrarily, then this structure is inherited by $\Sigma^X$, and thence by any subset ${\cal A}$ thereof.

For example if we order the set $2=\{0,1\}$ so that $0\le1$, then this order is inherited by every Chu space over ${\cal A}$ in the usual way: $a\le b$ just when for all $x\in X$, $r_a(x)\le r_b(x)$. This is just the ordinary inclusion order on 2^X when understood as the power set of X.

What we shall show is that continuous functions preserve the structure inherited from $\Sigma$. 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 $\Sigma$, say 0, to be a constant (definable as a unary relation holding just at 0), making $\Sigma$ 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 $\Sigma^X$ for any set X. The induced constant in $\Sigma^X$ is the constant word $00\ldots0$. 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 $00\ldots0$ appears in ${\cal A}$, call it ${\bf0}$. Then every projection of ${\cal A}$ onto $\Sigma$ sends ${\bf0}$ to 0. Let $f:{\cal A}\to{\cal B}$ be continuous. Then every projection of ${\cal B}$ to $\Sigma$ must send $f({\bf 0})$ to 0, or we would have a projection of ${\cal B}$ whose composition with f fails to be a projection of ${\cal A}$. Hence $f({\bf0})$ must itself be the constantly zero word.

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

We now pass from $\Sigma$ as a structure with one or more constants to the above example $\Sigma=2$ ordered by $0\le1$. Any Chu space (A,r,X) over this alphabet, viewed as a subset $A\subseteq2^X$ 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 $a\le b$ in ${\cal A}$ but the continuous function $f:{\cal A}\to{\cal B}$ is such that $f(a)\not\le f(b)$. Hence for some projection $\pi:{\cal B}\to\Sigma$, $\pi(f(a))=1$ but $\pi(f(b))=0$. But $\pi\circ f$ must be a projection of ${\cal A}$, whose just-observed behavior contradicts $a\le b$. $\rule{2mm}{3mm}$

For our third and last example, furnish $\Sigma=2$ with the usual join or disjunction operation $\vee:2^2\to2$. This induces a partial join operation on ${\cal A}\subseteq\Sigma^X$ defined as the join (bitwise OR) of words of ${\cal A}$. If for any two words a,b of ${\cal A}$ that join is itself a word of ${\cal A}$, call it $a\vee b$, then we say that $\vee$ is defined at (a,b).

Proposition 3   Whenever $a\vee b$ is defined in ${\cal A}$ and $f:{\cal A}\to{\cal B}$ is continuous, then $f(a)\vee f(b)$ is defined in ${\cal B}$ and equals $f(a\vee b)$.

Proof:   Suppose not. Then there must exist a projection $\pi:{\cal B}\to\Sigma$ with $\pi(f(a\vee b))\not=\pi(f(a))\vee\pi(f(b))$. But as before, $\pi\circ f$ must be a projection of ${\cal A}$, giving us a position (element $x\in X$) at which the alleged $a\vee b$ fails to be the join of a and b after all. $\rule{2mm}{3mm}$

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

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

But in some situations every function from ${\cal A}$ to ${\cal B}$ can be continuous. This happens in particular when ${\cal A}$ is the dual of the Chu space $\Sigma^X$ consisting of all words of length X. In this case a projection from ${\cal A}$ to $\Sigma$ is just a word of $\Sigma^X$, of length X. But $\Sigma^X$ contains every possible word of length X. Hence the test as to whether $\pi\circ f$ is a projection of ${\cal A}$ must always succeed, whence every function from ${\cal A}$ to any Chu space whatsoever will be continuous. Such an ${\cal A}$ 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 $\Sigma$ with, and hence $\Sigma^X$, all of this structure may be eliminated by shrinking $A\subset\Sigma^X$ enough, namely to size double-logarithmic (with base $\vert\Sigma\vert$) in the size of $\Sigma^X$ (since ${\cal A}$ is discrete when X is $\Sigma^A$).

So just how much relational structure can we equip $\Sigma$ with? The answer is that it suffices to take all possible relations of all possible arities on $\Sigma$, including infinite arities. For arity X (as a set of variables in preference to just a number) these form the set $2^{\Sigma^X}$ of all X-ary relations on $\Sigma$. One set X of each cardinality suffices. Most of these relations will be obtainable by composition from a very small basis. When $\Sigma=2$, 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 $\Sigma$ still 2, the maximal structure with which we may equip $\Sigma^X$ is that of a complete atomic Boolean algebra. If we ignore questions of concreteness, this remains true for larger $\Sigma$ [Pra95].