Chu spaces and linear logic [chu-spaces-and-linear-logic]
Chu spaces and linear logic [chu-spaces-and-linear-logic]
A _Chu space over S_ consists of a pair of sets (X,U), and a function e: X \times U \to S. A map of chu spaces (X,U,e) \to (Y,V,e') is a pair of maps X \to Y, V \to U so that the diagram
commutes. This defines a category of Chu spaces, called Chu(Set,S) You can think of a Chu space as a normal-form game. X is the set of choices available to one player, and U is the set of choices available to the other. The outcome, given the choices x and u, is e(x,u).
You can think of a map of Chu spaces as a way of transforming strategies between the two games. If you would play x \in X in the original game, you instead play f(x) \in Y. The map in the opposite direction ensures that, no matter what your opponent chooses in the target game, the same outcome could have happened in the domain game - hence your strategy is no worse, in some vague sense (but note that there is no ordering on S, so this does not literally make sense).
The cool thing is that Chu spaces are also a model of linear logic, in a way that sort of reflects "Game semantics for linear logic", but with some important differences (which we will see).