Chu Spaces

Origin. Po-Hsiang Chu, "Constructing *-autonomous categories", the appendix (103–138) to Michael Barr, *-Autonomous Categories (Lecture Notes in Mathematics 752, Springer 1979), written up from Chu's master's thesis under Barr; Barr returned to the construction as a semantics for linear logic (1991). Lafont and Streicher, "Games semantics for linear logic" (LICS 1991, 43–50), treated the case over Set, reading the spaces as games. Vaughan Pratt made them a program: "Chu spaces: automata with quantum aspects" (PhysComp '94, IEEE 1994, 186–195), "The Stone gamut: a coordinatization of mathematics" (LICS 1995, 444–454), "Chu spaces from the representational viewpoint" (Annals of Pure and Applied Logic 96, 1999, 319–333). Barwise and Seligman, Information Flow: The Logic of Distributed Systems (Cambridge Tracts in Theoretical Computer Science 44, Cambridge University Press 1997), built the logic of distributed systems on the same objects under the name classifications.

Models. A Chu space over an alphabet K is a matrix: rows are points, columns are states, and the entry at (x, a) says how the point x answers the state a. The object is two-sided — it holds a structure and its dual in one piece, with transposition an involution exchanging them — and the entry's subject is the three readings that this one object supports. Read as Barr and Chu built it, the construction completes a symmetric monoidal closed category to a *-autonomous one, so Chu(Set, K) is a model of classical linear logic, with the involutive negation that the Dialectica construction lacks. Read as Pratt proposed, it is a coordinatization of mathematics: relational structures, topological spaces, and ordered sets all realize concretely inside Chu(Set, 2ᵏ), and the classical dualities, Stone's first among them, become matrix transposition. Read as Barwise and Seligman use it, the matrix is a classification of instances by types, and its transforms are the infomorphisms along which information flows between parts of a distributed system. The constructions differ from the sibling Dialectica Categories at one point: the transform condition here is an equation where Dialectica's is an implication, and that equation is where the classical duality comes from.

Formalism.

Chu space: 𝒜 = (X, r, A): a set X of points, a set A of states, a matrix r : X × A → K. Extensional: no two columns equal. Separable: no two rows equal. Biextensional: both.

Chu transform: (f, g) : (X, r, A) → (Y, s, B), with f : X → Y forward on points and g : B → A backward on states, such that s(f(x), b) = r(x, g(b)) for all x ∈ X, b ∈ B — the adjointness condition.

Duality: 𝒜^⊥ = (A, r̆, X), r̆(a, x) = r(x, a): transpose the matrix. (f, g)^⊥ = (g, f). 𝒜^⊥⊥ = 𝒜, on the nose.

Linear connectives in Chu(Set, K): 1 = ({∗}, r, K) with r(∗, k) = k. 𝒜 ⊗ ℬ: points X × Y; states the Chu transforms 𝒜 → ℬ^⊥. 𝒜 ⊸ ℬ = (𝒜 ⊗ ℬ^⊥)^⊥; 𝒜 ⅋ ℬ = (𝒜^⊥ ⊗ ℬ^⊥)^⊥ — tensor and par are De Morgan duals. The category is bicomplete; products and coproducts interpret the additives.

The construction in general: V symmetric monoidal closed with pullbacks, k an object of V: Chu(V, k) is *-autonomous (Chu 1979). Chu(Set, K) is the case V = Set, and the one the readings above use.

Realization (Pratt): The category of n-ary relational structures and homomorphisms is a concretely full subcategory of Chu(Set, 2ⁿ). Any category of relational structures of total arity k realizes in Chu(Set, 2ᵏ): a full and faithful functor commuting with the underlying-set functors. Topological spaces: the extensional Chu spaces over 2 whose columns are closed under arbitrary union and finite intersection; the Chu transforms between them are exactly the continuous functions. Preorders and posets realize over 2 as well; topological groups in Chu(Set, 16).

Classification (Barwise–Seligman): Classification: instances, types, and a satisfaction relation between them — a Chu space over 2. Infomorphism: types forward, instances backward, satisfaction invariant under the pair — a Chu transform. Channel: a system of infomorphisms from component classifications into a common core. Local logic: a classification with a set of constraints among its types and a set of normal instances satisfying them.

Symbols.

Metatheory. Chu's appendix proves that Chu(V, k) is *-autonomous for any symmetric monoidal closed V with pullbacks and any object k. Chu(Set, K) is, in Pratt's formulation, "a concrete self-dual bicomplete closed category and hence a constructive model of linear logic", with negation involutive on the nose rather than up to isomorphism; Devarajan, Hughes, Plotkin and Pratt, "Full completeness of the multiplicative linear logic of Chu spaces" (LICS 1999, 234–243), established full completeness for the multiplicative fragment. Lafont and Streicher connected the Set case to von Neumann–Morgenstern games, observing that vector spaces, topological spaces and coherence spaces realize as games. Pratt's realization theorems make the universality precise: structures of total arity k embed fully, faithfully and concretely in Chu(Set, 2ᵏ), and the Stone gamut paper embeds the categories of Johnstone's Stone duality as full concrete duality-preserving subcategories of Chu(Set, 2), where "the notoriously difficult notion of Stone duality reduces simply to matrix transposition" (see Stone Duality). The identification of Barwise and Seligman's apparatus with Chu spaces is standard in print — classifications were "independently studied and introduced under names such as Chu spaces (Pratt 1995) or Formal Contexts (Ganter and Wille 1999)", as the Stanford Encyclopedia's survey of the information-flow literature puts it — and van Benthem, "Information transfer across Chu spaces" (Logic Journal of the IGPL 8(6), 2000, 719–731), works the two traditions against each other. The infomorphism condition itself — types translated forward, instances backward, satisfaction invariant under the pair — is the satisfaction condition of Institutions stated for a single pair of signatures rather than axiomatized across a category of them (see Institutions).

Applies to. Semantics of classical linear logic (see Linear Logic). Concurrency, through Pratt's reading of Chu spaces as automata and concurrent objects ("Chu spaces and their interpretation as concurrent objects", LNCS 1000, 1995, 392–405). Information flow in distributed systems, through Barwise–Seligman channels and local logics. Formal concept analysis, whose formal contexts are the same matrices over 2. Game semantics, through Lafont–Streicher. The single-setting representation of mathematical structures — Pratt's coordinatization.

Limitations. The construction supplies the multiplicatives and the additives but not the exponentials: Chu(Set, K) is a model of MALL outright, and of full linear logic only once an exponential is chosen, since ! is not determined by the *-autonomous structure (see Linear Logic and Intuitionistic Linear Logic on the non-canonicity of the exponentials). The classical duality is obtained by the equational transform condition, and what the equation removes is Dialectica's interaction reading — a morphism no longer says that answered challenges transfer, only that the matrices agree — so Chu and Dialectica model classical and intuitionistic linear logic respectively (see Dialectica Categories). Realization is coordinatization: the alphabet must grow with the arity, 2ᵏ for total arity k, and which matrices lie in the image — which columns form a topology, which rows a group — is stated as a side condition on columns, outside the categorical language. A classification fixes only a two-valued satisfaction matrix: consequence among types and the selection of normal instances are added by the local-logic apparatus rather than derived from the space.

© 2026 Lingenic LLC