Previous: Background Up: Chu Spaces from the Next: Transformation

# Representation

A Chu space resembles a formal language, in that it may be understood intuitively as a set of words'' over an alphabet . An ordinary word w of length n can be defined as a function , 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 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 , 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 .

This intuition is formalized as follows. A Chu space over is a triple consisting of sets A and X and a function . We call A and X respectively the carrier and cocarrier of , their elements respectively points and states, and r the interaction matrix.

Words and dual words. The interaction matrix has left and right transposes and satisfying = r(a,x) = , which we may interpret as representations of A and X respectively. For each point , represents a as a function from X to , i.e. of type , namely a word over an alphabet of length X in the above sense. Dually represents state x as a function from A to , similarly constituting a word of length A over the same alphabet , which we shall refer to as a dual word of .

The Chu space whose words are the dual words of is where , called the dual of and denoted .

When two points a,b are represented by the same word, i.e. when , we call them equivalent, written , Dually, equivalent states, those satisfying , are likewise indicated by .

When no two distinct points are equivalent, i.e. is injective, we call a faithful representation of A, and say that is separable. Dually when is injective we call it a faithful representation of X, and say that 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 itself forms a language consisting of all words of length 1 over alphabet . This makes it a Chu space, which we denote where and is projection on the first coordinate, satisfying for all . Its dual, , consists of a single word containing one occurrence of every symbol in . Its role is as the discrete singleton, denoted by 1.

The discrete empty language, denoted 0, is . The inconsistent empty language, , plays no important role and needs no name.

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