Chu space

Last updated March 06, 2023

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.

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 matrix 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 conditions(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⁻¹, 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.

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 with dualizing object (K, λ, {*}) where λ : K × {*} → K is defined by λ(k, *) = k (Barr 1979). As such it is a model of Jean-Yves Girard's linear logic (Girard 1987).

Variants

The more general enriched category Chu(V, k) originally appeared in an appendix to Barr (1979). 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 spaces, due to de Paiva (1989) 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 representationF((X, T)) = (X, ∈, T) as noted above. This representation is moreover a realization in the sense of Pultr and Trnková (1980), 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 (1991) point out that Chu spaces over 2 realize both topological spaces and coherent spaces (introduced by J.-Y. Girard (1987) to model linear logic), 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 (1995) to the realization of k-ary relational structures by Chu spaces over 2^k. 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 .

Applications

Automata

Chu spaces can serve as a model of concurrent computation in automata theory 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.^[2]

Related Research Articles

In mathematics and computer science, currying is the technique of translating the evaluation of a function that takes multiple arguments into evaluating a sequence of functions, each with a single argument. For example, currying a function $that takes three arguments creates a nested unary function, so that the code$

In mathematics, specifically category theory, a functor is a mapping between categories. Functors were first considered in algebraic topology, where algebraic objects are associated to topological spaces, and maps between these algebraic objects are associated to continuous maps between spaces. Nowadays, functors are used throughout modern mathematics to relate various categories. Thus, functors are important in all areas within mathematics to which category theory is applied.

In topology and related branches of mathematics, a Hausdorff space ( HOWS-dorf, HOWZ-dorf), separated space or T₂ space is a topological space where, for any two distinct points, there exist neighbourhoods of each which are disjoint from each other. Of the many separation axioms that can be imposed on a topological space, the "Hausdorff condition" (T₂) is the most frequently used and discussed. It implies the uniqueness of limits of sequences, nets, and filters.

<span class="mw-page-title-main">Homeomorphism</span> Mapping which preserves all topological properties of a given space

In the mathematical field of topology, a homeomorphism, topological isomorphism, or bicontinuous function is a bijective and continuous function between topological spaces that has a continuous inverse function. Homeomorphisms are the isomorphisms in the category of topological spaces—that is, they are the mappings that preserve all the topological properties of a given space. Two spaces with a homeomorphism between them are called homeomorphic, and from a topological viewpoint they are the same.

This is a glossary of some terms used in the branch of mathematics known as topology. Although there is no absolute distinction between different areas of topology, the focus here is on general topology. The following definitions are also fundamental to algebraic topology, differential topology and geometric topology.

In mathematics, general topology is the branch of topology that deals with the basic set-theoretic definitions and constructions used in topology. It is the foundation of most other branches of topology, including differential topology, geometric topology, and algebraic topology. Another name for general topology is point-set topology.

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 that their internal language is the simply typed lambda calculus. They are generalized by closed monoidal categories, whose internal language, linear type systems, are suitable for both quantum and classical computation.

In mathematics, a sheaf is a tool for systematically tracking data attached to the open sets of a topological space and defined locally with regard to them. For example, for each open set, the data could be the ring of continuous functions defined on that open set. Such data is well behaved in that it can be restricted to smaller open sets, and also the data assigned to an open set is equivalent to all collections of compatible data assigned to collections of smaller open sets covering the original open set.

In mathematics, a function space is a set of functions between two fixed sets. Often, the domain and/or codomain will have additional structure which is inherited by the function space. For example, the set of functions from any set X into a vector space has a natural vector space structure given by pointwise addition and scalar multiplication. In other scenarios, the function space might inherit a topological or metric structure, hence the name function space.

In mathematics, there is an ample supply of categorical dualities between certain categories of topological spaces and categories of partially ordered sets. Today, these dualities are usually collected under the label Stone duality, since they form a natural generalization of Stone's representation theorem for Boolean algebras. These concepts are named in honor of Marshall Stone. Stone-type dualities also provide the foundation for pointless topology and are exploited in theoretical computer science for the study of formal semantics.

In mathematics, equivariance is a form of symmetry for functions from one space with symmetry to another. A function is said to be an equivariant map when its domain and codomain are acted on by the same symmetry group, and when the function commutes with the action of the group. That is, applying a symmetry transformation and then computing the function produces the same result as computing the function and then applying the transformation.

In mathematics, a closure operator on a set S is a function $:{\mathcal {P}}(S)\rightarrow {\mathcal {P}}(S)}$ from the power set of S to itself that satisfies the following conditions for all sets

In mathematics, a Radon measure, named after Johann Radon, is a measure on the σ-algebra of Borel sets of a Hausdorff topological space X that is finite on all compact sets, outer regular on all Borel sets, and inner regular on open sets. These conditions guarantee that the measure is "compatible" with the topology of the space, and most measures used in mathematical analysis and in number theory are indeed Radon measures.

In topology, an Alexandrov topology is a topology in which the intersection of any family of open sets is open. It is an axiom of topology that the intersection of any finite family of open sets is open; in Alexandrov topologies the finite restriction is dropped.

In mathematics, a duality translates concepts, theorems or mathematical structures into other concepts, theorems or structures, in a one-to-one fashion, often by means of an involution operation: if the dual of $A$ is $B$ , then the dual of $B$ is $A$ . Such involutions sometimes have fixed points, so that the dual of $A$ is $A$ itself. For example, Desargues' theorem is self-dual in this sense under the standard duality in projective geometry.

In mathematics, especially in order theory, a complete Heyting algebra is a Heyting algebra that is complete as a lattice. Complete Heyting algebras are the objects of three different categories; the category CHey, the category Loc of locales, and its opposite, the category Frm of frames. Although these three categories contain the same objects, they differ in their morphisms, and thus get distinct names. Only the morphisms of CHey are homomorphisms of complete Heyting algebras.

In mathematics, the compact-open topology is a topology defined on the set of continuous maps between two topological spaces. The compact-open topology is one of the commonly used topologies on function spaces, and is applied in homotopy theory and functional analysis. It was introduced by Ralph Fox in 1945.

In mathematics, the restriction of a function $is a new function, denoted or obtained by choosing a smaller domain for the original function The function is then said to extend$

In mathematics, a pullback is either of two different, but related processes: precomposition and fiber-product. Its dual is a pushforward.

In mathematics, a topos is a category that behaves like the category of sheaves of sets on a topological space. Topoi behave much like the category of sets and possess a notion of localization; they are a direct generalization of point-set topology. The Grothendieck topoi find applications in algebraic geometry; the more general elementary topoi are used in logic.

References

↑ The Chu Construction: History of an Idea, Michael Barr McGill University
↑ Pratt, V.R. (1994). "Chu spaces: Automata with quantum aspects". Proceedings Workshop on Physics and Computation. Phys Comp '94. pp. 186–195. doi:10.1109/PHYCMP.1994.363682. ISBN 978-0-8186-6715-2.

External links

Guide to Papers on Chu Spaces, Web page.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] The Chu Construction: History of an Idea, Michael Barr McGill University

[2] Pratt, V.R. (1994). "Chu spaces: Automata with quantum aspects". Proceedings Workshop on Physics and Computation. Phys Comp '94. pp. 186–195. doi:10.1109/PHYCMP.1994.363682. ISBN 978-0-8186-6715-2.

[1]

[2]