Talk:Chu space
From Wikipedia, the free encyclopedia
Chu spaces generalize the notion of topological space by dropping the requirements that the set of open sets be closed under union and finite intersection, that the open sets be extensional, and that the membership predicate be two-valued. The definition of continuous function remains unchanged other than being worded carefully to make sense for these more general spaces.
Understood statically, a Chu space (A,r,X) over a set K consists of a set A of points, a set X of states, and a function r:A×X→K. This makes it an A×X matrix with entries drawn from K, or equivalently a K-valued binary relation between A and X.
Understood dynamically, Chu spaces transform in the manner of topological spaces, with A as the set of points, X as the set of open sets, and r as the membership relation between them, where K is the set of all possible degrees of membership of a point in an open set. The counterpart of a continuous function from (A,r,X) to (B,s,Y) is a pair (f,g) of functions f:A→B, g:Y→X satisfying s(f(a),y) = r(a,g(y)) for all aεA and yεY. That is, f maps points forwards at the same time as g maps states backwards, with g playing the role of the inverse image function associated to f (the content of the above equation), and with the requirement that the inverse image of open sets be open met by the requirement that g(y) ε X.
A topological space (X,T) where X is the set of points and T the set of open sets, can be understood as a Chu space (X,ε,T) over {0,1}. That is, the points of the topological space become those of the Chu space while the open sets become states and the membership relation ε between points and open sets is made explicit in the Chu space. There is furthermore the requirement that the set of open sets be closed under finite (including empty) union and arbitrary (including empty) intersection.
The category of Chu spaces over K and their maps is denoted by Chu(Set,K). As is clear from the symmetry of the definitions, it is a self-dual category, meaning that it is equivalent (indeed isomorphic) to its opposite (the category obtained by reversing all the maps). It is furthermore a *-autonomous category [1] with dualizing object (K,λ,{*}) where λ:K×{*}→K is defined by λ(k,*)=k, and as such a model of Girard's linear logic [3].
The more general enriched category Chu(V,k) is defined in an appendix to Barr's book contributed by his master's student Po-Hsiang Chu, after whom they are named, see also [2]. Ordinary Chu spaces arise as the case V=Set, that is, when the monoidal category V is specialized to the cartesian closed category Set of sets and their functions.
The category Top of topological spaces and their continuous functions embeds in Chu(Set,2) in the sense that there exists a full and faithful functor F:Top → Chu(Set,2) providing for each topological space (X,T) its representation F((X,T)) = (X,ε,T) as noted above. This representation is moreover a realization in the sense of Pultr and Trnková [7], namely that the representing Chu space has the same set of points as the represented topological space and transforms in the same way via the same functions.
Chu spaces are remarkable for the wide variety of familiar structures they realize. Lafont and Streicher [3] point out that Chu spaces over 2 realize both topological spaces and coherent spaces (introduced in 1987 by J.-Y. Girard to model linear logic [3]), while Chu spaces over K realize any category of vector spaces over a field whose cardinality is at most that of K. This was extended by V. Pratt [6] to the realization of k-ary relational structures by Chu spaces over 2k; for example the category Grp of groups and their homomorphisms is realized by Chu(Set,8). Chu(Set,2) realizes a wide range of ``logical`` structures such as semilattices, distributive lattices, complete and completely distributive lattices, Boolean algebras, complete atomic Boolean algebras, etc. Further information on this and other aspects of Chu spaces, including their application to the modeling of concurrent behavior, may be found at http://chu.stanford.edu/ .
References
[1] M. Barr, *-Autonomous categories, Springer-Verlag Lecture Notes in Mathematics 752, 1979.
[2] M. Barr, The Chu construction, Theory and Applications of Categories, 2:2, 17-35 (1996).
[3] J.-Y. Girard, Linear logic, Theoretical Computer Science, 50:1–102, 1987.
[4] Y. Lafont and T. Streicher. Games semantics for linear logic. Proc. 6th Annual IEEE Symp. on Logic in Computer Science, 43–49, Amsterdam, July 1991.
[5] V. de Paiva. A dialectica-like model of linear logic. In Proc. Conf. on Category Theory and Computer Science, Springer-Verlag Lecture Notes in Computer Science 389, pp. 341–356, Manchester, September 1989.
[6] V.R. Pratt. The Stone gamut: A coordinatization of mathematics. In Logic in Computer Science, pages 444–454. IEEE Computer Society, June 1995.
[7] A. Pultr and V. Trnková. Combinatorial, Algebraic and Topological Representations of Groups, Semigroups, and Categories. North-Holland, 1980.
[edit] Oops
- JA: Sorry, didn't know you were still working on it, will hold off formatting till tomorrow or Monday. Jon Awbrey 05:32, 12 March 2006 (UTC)
[edit] On 2
- JA: It might help to bold the "2" when it's used as the name of a domain. Jon Awbrey 17:34, 12 March 2006 (UTC)
