previous up next
Previous: Background Up: Chu Spaces from the Next: Transformation


A Chu space resembles a formal language, in that it may be understood intuitively as a set of ``words'' over an alphabet $\Sigma$. An ordinary word w of length n can be defined as a function $w:\{1,2,\ldots,n\}\to\Sigma$, having for its i-th symbol w(i) or wi.

Chu spaces modify this in two ways. First, a word is taken to be a function $w:X\to\Sigma$ where X is an arbitrary set, not necessarily an initial segment of the positive integers. We may then speak of X as the ``length'' of w. (Note that the number of words of ``length'' a five-element set is the same as the number of ordinary words of ordinary length 5.)

Second, the words of a given Chu space are all of the same length, i.e. all have a given set X as their common domain. No restrictions are placed on either X or $\Sigma$, which may be empty, or initial segments of the positive integers, or sets of reals, or any other set. Likewise no restrictions are placed on the words, which may be any function from X to $\Sigma$.

This intuition is formalized as follows. A Chu space over $\Sigma$ is a triple ${\cal A}=(A,r,X)$ consisting of sets A and X and a function $r:A\times X\to \Sigma$. We call A and X respectively the carrier and cocarrier of ${\cal A}$, their elements respectively points and states, and r the interaction matrix.

Words and dual words. The interaction matrix has left and right transposes $\kern.25em\lower.2em\hbox{$\mathaccent''7B5E{\vphantom~}$ }\kern-.55emr:A\to \Sigma^X$ and $\kern.25em\lower.2em\hbox{$\mathaccent''7B14{\vphantom~}$ }\kern-.55emr:X\to \Sigma^A$ satisfying $\kern.25em\lower.2em\hbox{$\mathaccent''7B5E{\vphantom~}$ }\kern-.55emr(a)(x)$ = r(a,x) = $\kern.25em\lower.2em\hbox{$\mathaccent''7B14{\vphantom~}$ }\kern-.55emr(x)(a)$, which we may interpret as representations of A and X respectively. For each point $a\in A$, $\kern.25em\lower.2em\hbox{$\mathaccent''7B5E{\vphantom~}$ }\kern-.55emr(a)$ represents a as a function from X to $\Sigma$, i.e. of type $\Sigma^X$, namely a word over an alphabet $\Sigma$ of length X in the above sense. Dually $\kern.25em\lower.2em\hbox{$\mathaccent''7B14{\vphantom~}$ }\kern-.55emr(x)$ represents state x as a function from A to $\Sigma$, similarly constituting a word of length A over the same alphabet $\Sigma$, which we shall refer to as a dual word of ${\cal A}$.

The Chu space whose words are the dual words of ${\cal A}=(A,r,X)$ is $(X,r\breve{~},A)$ where $r\breve{~}(x,a)=r(a,x)$, called the dual of ${\cal A}$ and denoted ${\cal A}^\bot$.

When two points a,b are represented by the same word, i.e. when $\kern.25em\lower.2em\hbox{$\mathaccent''7B5E{\vphantom~}$ }\kern-.55emr(a)=\kern.25em\lower.2em\hbox{$\mathaccent''7B5E{\vphantom~}$ }\kern-.55emr(b)$, we call them equivalent, written $a\equiv b$, Dually, equivalent states, those satisfying $\kern.25em\lower.2em\hbox{$\mathaccent''7B14{\vphantom~}$ }\kern-.55emr(x)=\kern.25em\lower.2em\hbox{$\mathaccent''7B14{\vphantom~}$ }\kern-.55emr(y)$, are likewise indicated by $x\equiv y$.

When no two distinct points are equivalent, i.e. $\kern.25em\lower.2em\hbox{$\mathaccent''7B5E{\vphantom~}$ }\kern-.55emr:A\to \Sigma^X$ is injective, we call $\kern.25em\lower.2em\hbox{$\mathaccent''7B5E{\vphantom~}$ }\kern-.55emr$ a faithful representation of A, and say that ${\cal A}$ is separable. Dually when $\kern.25em\lower.2em\hbox{$\mathaccent''7B14{\vphantom~}$ }\kern-.55emr:Y\to \Sigma^A$ is injective we call it a faithful representation of X, and say that ${\cal A}$ is extensional. A Chu space that is both separate and extensional is called biextensional.

The usual notion of a formal language as a set of words all distinct corresponds to the property of separability. Nonseparable Chu spaces may be understood as multisets of words, allowing the same word to occur more than once in the language. For our purposes the identity of points and states is determined by their representations, and for this reason the biextensional Chu spaces will be the ones we shall be mainly concerned with.

The alphabet $\Sigma$ itself forms a language consisting of all words of length 1 over alphabet $\Sigma$. This makes it a Chu space, which we denote $\bot=(\Sigma,\pi_1,1)$ where $1=\{0\}$ and $\pi_1:\Sigma\times1\to\Sigma$ is projection on the first coordinate, satisfying $\pi_1(i,0)=i$ for all $i\in\Sigma$. Its dual, $\bot^\bot$, consists of a single word containing one occurrence of every symbol in $\Sigma$. Its role is as the discrete singleton, denoted by 1.

The discrete empty language, denoted 0, is $(\emptyset,!,1)$. The inconsistent empty language, $(\emptyset,!,\emptyset)$, plays no important role and needs no name.

previous up next
Previous: Background Up: Chu Spaces from the Next: Transformation
Vaughan Pratt