Chu space
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 (of points in open sets) be two-valued. The definition of continuous function
remains unchanged other than having to be worded carefully to continue to make sense after these generalizations.
with entries drawn from K, or equivalently a K-valued binary relation
between A and X (ordinary binary relations being 2-valued).
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 the adjointness condition 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. The adjointness condition makes g the inverse image function f–1, while the choice of X for the codomain
of g corresponds to the requirement for continuous functions that the inverse image of open sets be open. Such a pair is called a Chu transform or morphism of Chu spaces.
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. The condition that the set of open sets be closed under arbitrary (including empty) union and finite (including empty) intersection becomes the corresponding condition on the columns of the matrix. A continuous function f: X → X between two topological spaces becomes an adjoint pair (f,g) in which f is now paired with a realization of the continuity condition constructed as an explicit witness function g exhibiting the requisite open sets in the domain of f.
[1] with dualizing object (K, λ, {*}) where λ : K × {*} → K is defined by λ(k, *) = k, and as such a model of Jean-Yves Girard
's linear logic
[3].
Chu(V, k) originally appeared in an appendix to [1]. The Chu space concept originated with Michael Barr
and the details were developed by his student Po-Hsiang Chu, whose master's thesis formed the appendix. 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, but were not studied in their own right until more than a decade after the appearance of the more general enriched notion. A variant of Chu spaces, called dialectica space
s, due to de Paiva [5] replaces the map condition (1) with the map condition (2):
Chu spaces are remarkable for the wide variety of familiar structures they realize. Lafont and Streicher [4] point out that Chu spaces over 2 realize both topological spaces and coherent space
s (introduced 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 Vaughan 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) since the group multiplication can be organized as a ternary relation
. 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 Chu Spaces.
to express branching time and true concurrency
. Chu spaces exhibit the quantum mechanical phenomena of complementarity and uncertainty. The complementarity arises as the duality of information and time, automata and schedules, and states and events. Uncertainty arises when a measurement is defined to be a morphism
such that increasing structure in the observed object reduces the clarity of observation. This uncertainty can be calculated numerically from its form factor to yield the usual Heisenberg uncertainty relation. Chu spaces correspond to wavefunctions as vectors of Hilbert space
.
Topological space
Topological spaces are mathematical structures that allow the formal definition of concepts such as convergence, connectedness, and continuity. They appear in virtually every branch of modern mathematics and are a central unifying notion...
by dropping the requirements that the set of open sets be closed under union
Union (set theory)
In set theory, the union of a collection of sets is the set of all distinct elements in the collection. The union of a collection of sets S_1, S_2, S_3, \dots , S_n\,\! gives a set S_1 \cup S_2 \cup S_3 \cup \dots \cup S_n.- Definition :...
and finite intersection
Intersection (set theory)
In mathematics, the intersection of two sets A and B is the set that contains all elements of A that also belong to B , but no other elements....
, that the open sets be extensional, and that the membership predicate (of points in open sets) be two-valued. The definition of continuous function
Continuous function
In mathematics, a continuous function is a function for which, intuitively, "small" changes in the input result in "small" changes in the output. Otherwise, a function is said to be "discontinuous". A continuous function with a continuous inverse function is called "bicontinuous".Continuity of...
remains unchanged other than having to be worded carefully to continue to make sense after these generalizations.
Definition
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 matrixMatrix (mathematics)
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...
with entries drawn from K, or equivalently a K-valued binary relation
Binary relation
In mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = . More generally, a binary relation between two sets A and B is a subset of...
between A and X (ordinary binary relations being 2-valued).
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 the adjointness condition 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. The adjointness condition makes g the inverse image function f–1, while the choice of X for the codomain
Codomain
In mathematics, the codomain or target set of a function is the set into which all of the output of the function is constrained to fall. It is the set in the notation...
of g corresponds to the requirement for continuous functions that the inverse image of open sets be open. Such a pair is called a Chu transform or morphism of Chu spaces.
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. The condition that the set of open sets be closed under arbitrary (including empty) union and finite (including empty) intersection becomes the corresponding condition on the columns of the matrix. A continuous function f: X → X between two topological spaces becomes an adjoint pair (f,g) in which f is now paired with a realization of the continuity condition constructed as an explicit witness function g exhibiting the requisite open sets in the domain of f.
Categorical structure
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: it is equivalent (in fact isomorphic) to its dual, the category obtained by reversing all the maps. It is furthermore a *-autonomous category*-autonomous category
In mathematics, a *-autonomous category C is a symmetric monoidal closed category equipped with a dualizing object \bot.-Definition:Let C be a symmetric monoidal closed category...
[1] with dualizing object (K, λ, {*}) where λ : K × {*} → K is defined by λ(k, *) = k, and as such a model of Jean-Yves Girard
Jean-Yves Girard
Jean-Yves Girard is a French logician working in proof theory. His contributions include a proof of strong normalization in a system of second-order logic called system F; the invention of linear logic; the geometry of interaction; and ludics...
's linear logic
Linear logic
Linear logic is a substructural logic proposed by Jean-Yves Girard as a refinement of classical and intuitionistic logic, joining the dualities of the former with many of the constructive properties of the latter...
[3].
Variants
The more general enriched categoryEnriched category
In category theory and its applications to mathematics, enriched category is a generalization of category that abstracts the set of morphisms associated with every pair of objects to an opaque object in some fixed monoidal category of "hom-objects" and then defines composition and identity solely...
Chu(V, k) originally appeared in an appendix to [1]. The Chu space concept originated with Michael Barr
Michael Barr (mathematician)
Michael Barr is Peter Redpath Emeritus Professor of Pure Mathematics at McGill University. Although his earlier work was in homological algebra, his principal research area for a number of years has been category theory...
and the details were developed by his student Po-Hsiang Chu, whose master's thesis formed the appendix. Ordinary Chu spaces arise as the case V = Set, that is, when the monoidal category
Monoidal category
In mathematics, a monoidal category is a category C equipped with a bifunctorwhich is associative, up to a natural isomorphism, and an object I which is both a left and right identity for ⊗, again up to a natural isomorphism...
V is specialized to the cartesian closed category
Cartesian closed category
In category theory, a category is cartesian closed if, roughly speaking, any morphism defined on a product of two objects can be naturally identified with a morphism defined on one of the factors. These categories are particularly important in mathematical logic and the theory of programming, in...
Set of sets and their functions, but were not studied in their own right until more than a decade after the appearance of the more general enriched notion. A variant of Chu spaces, called dialectica space
Dialectica space
Dialectica spaces are a categorical way of constructing models of linear logic.They were introduced by Valeria de Paiva, Martin Hyland's student, in her doctoral thesis, as a way of modeling both linear logic and Gödel's dialectica interpretation—hence the name.Given a category C and a...
s, due to de Paiva [5] replaces the map condition (1) with the map condition (2):
- s(f(a), y) = r(a, g(y)).
- s(f(a), y) ≤ r(a, g(y)).
Universality
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 [4] point out that Chu spaces over 2 realize both topological spaces and coherent space
Coherent space
In proof theory, a coherent space is a concept introduced in the semantic study of linear logic.Let a set C be given. Two subsets S,T ⊆ C are said to be orthogonal, written S ⊥ T, if S ∩ T is ∅ or a singleton...
s (introduced 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 Vaughan 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) since the group multiplication can be organized as a ternary relation
Triadic relation
In mathematics, a ternary relation or triadic relation is a finitary relation in which the number of places in the relation is three. Ternary relations may also be referred to as 3-adic, 3-ary, 3-dimensional, or 3-place....
. 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 Chu Spaces.
Automata
Chu spaces can serve as a model of concurrent computation in automata theoryAutomata theory
In theoretical computer science, automata theory is the study of abstract machines and the computational problems that can be solved using these machines. These abstract machines are called automata...
to express branching time and true concurrency
Concurrency (computer science)
In computer science, concurrency is a property of systems in which several computations are executing simultaneously, and potentially interacting with each other...
. Chu spaces exhibit the quantum mechanical phenomena of complementarity and uncertainty. The complementarity arises as the duality of information and time, automata and schedules, and states and events. Uncertainty arises when a measurement is defined to be a morphism
Morphism
In mathematics, a morphism is an abstraction derived from structure-preserving mappings between two mathematical structures. The notion of morphism recurs in much of contemporary mathematics...
such that increasing structure in the observed object reduces the clarity of observation. This uncertainty can be calculated numerically from its form factor to yield the usual Heisenberg uncertainty relation. Chu spaces correspond to wavefunctions as vectors of Hilbert space
Hilbert space
The mathematical concept of a Hilbert space, named after David Hilbert, generalizes the notion of Euclidean space. It extends the methods of vector algebra and calculus from the two-dimensional Euclidean plane and three-dimensional space to spaces with any finite or infinite number of dimensions...
.
External links
- Guide to Papers on Chu Spaces, Web page.