Representing general structures with Chu spaces

A natural question to ask is, how general are the ideas of the preceding section? We have given two answers to this question elsewhere, one measuring the generality of Chu spaces in terms of arbitrary relational structures and their homomorphisms, of which the foregoing are examples, the other in terms of arbitrary small categories, for which a forgetful functor may or may not be given.

For all these situations we have shown [Pra93,Pra96], that the objects in question can be represented by Chu spaces in such a way that the continuous functions between the representing Chu spaces are exactly the homomorphisms of the corresponding represented objects. More precisely, in each case the category of interest embeds fully and concretely in the category of Chu spaces over an appropriate alphabet.

Proposition 5   The relational structures (A,R) of arity n embed fully and concretely in ${\bf chu}_{2^n}$.

Proof:   (Outline) We first give the representation of (A,R) in the case when R consists of exactly one n-tuple $t\in A^n$. Take (A,r,X) to be the Chu space such that $X\subseteq (2^A)^n$ consists of those n-tuples $(x1,\ldots,x_n)$ of subsets $x_i\subseteq A$ such that there exists $i\le n$ for which $t_i\in x_i$, and $r(a,x)=\{i\vert a\in x_i\}$.

We then generalize this representation to arbitrary R by intersecting the X's that arise as above for each n-tuple in R, and restricting r to A times that intersection. One can then show that a function from (A,R) to (B,S) is a homomorphism if and only if it is a continuous function between the respective representing Chu spaces [Pra93]. $\rule{2mm}{3mm}$

The construction generalizes to multiple relations by combining them into one super-relation with arity the sum of its constituent arities. It further generalizes to multiple sorts by combining them into one sort with disjoint union and indicating the sorts with one unary relation per sort.

Structures so representable include groups, transforming standardly by group homomorphisms ( $\vert\Sigma\vert=8$ because the group multiplication relation ab=c is ternary), directed graphs (or binary relations) transforming by graph homomorphisms ( $\vert\Sigma\vert=4$), small categories transforming by functors ( $\vert\Sigma\vert=16$ because we need a ternary relation for composition and also a unary relation to mark the identities), and so on.

The corresponding theorem for categories is as follows.

Proposition 6   Every small category C embeds fully and concretely in the category of Chu spaces over the set ar(C) of arrows of C.

(In the absence of an explicitly given forgetful functor $U:C\to{\bf Set}$ we take that given by the Yoneda embedding. On the one hand this is the standard way to make any small category concrete, on the other it is not a very economical way so the result is not as useful as the theorem following this.)

Proof:   Represent each object b of C as the Chu space F(b) whose points are the morphisms $f:a\to b$ from any object a of C, whose states are the morphisms $h:b\to c$ to any object c of C, and for which r(f,h) is defined as the composite f;h (= $h\circ f$). Represent each morphism $g:b\to b'$ of C as the continuous function F(g) = $\lambda f.f;g$ (which maps points of F(b) to points of F(b')), with adjoint $\lambda h.g;h$ (which maps states of F(b') to states of F(b).

That this is indeed the adjoint follows immediately from (f;g);h=f;(g;h), associativity of composition. That F is full and faithful is a nice exercise (or see [Pra96]). That F is concrete (commutes with the forgetful functor to ${\bf Set}$) holds when we take as the forgetful functor for small categories the functor that sends each object to the set of all morphisms to that object, which is just the covariant half of our Chu representation. $\rule{2mm}{3mm}$

A category admitting a full embedding of any small category is called universal [PT80,Trn66,HL69]. Unlike all previous universal categories however, Chu is concretely universal in the sense that the embedding preserves the carrier. This is the case both for this representation of objects of an arbitrary small category and for the preceding representation of relational structures (which normally form large categories).

A variant of this categorical embedding holds for small concrete categories (C,U) where $U:C\to{\bf Set}$ is a given faithful functor. The advantage of this theorem over the preceding one is that it is concrete with respect to the given forgetful functor, not with respect to one we make up for the occasion. For it to go through we require one minor additional condition on (C,U), namely that if $U(a)=\emptyset$ then for all objects b, there must exist a morphism $a\to b$, necessarily just one since U is faithful.

Denote by Elt(C,U) the disjoint union of the U(a)'s over all objects a of C, itself a set since C is small. This is the set of all occurrences of elements in the underlying sets of the objects of C.

Proposition 7   Every small honest concrete category (C,U) embeds fully, faithfully, and concretely in ${\bf chu}_{Elt(C,U)}$.

Proof:   (Outline) Represent object a of C by the Chu space (U(a),r,X) where X is the set of all morphisms $x:a\to b$ of C with domain a, and for each element u of U(a), r(u,x) = U(x)(u), the image of element u under the representation of x. It is then straightforward to show that this representation is faithful, full, and concrete. $\rule{2mm}{3mm}$