Dialectica Categories as Matrices

 

The Topos Institute officially opened on the 4th January 2021. On the 4th February David Spivak gave the first  Topos Institute Colloquium on the category POLY. I have not decided, yet, what I want to talk about in the Colloquium: too many ideas.  But when Brendan Fong suggested that we had internal talks where we explain to our colleagues what we do, I was very pleased to do it. The idea was a short talk, with few or no slides and lots of discussion. Great, right?

I talked on Friday and the slides are already in slideshare. And the conversation was great, but we couldn't get to half of the material. Oh well, the discussion was that good. So I decided that writing a few blog posts about the various Dialectica categories and some of the work that ensued is a good thing. This is the first post. 

 

The Dialectica construction starts from a cartesian closed base category (with coproducts -- think of Sets!) and builds structure on top of that. 

So we have a new category Dial whose objects are triples (U, X, alpha), where U and X are sets and alpha is a relation. Now you can think of a relation alpha either as a subset of a product (alpha is contained in the product UxX) or as a map, from the product UxX to 2, taking a pair of elements (u,x) to alpha(u,x) which either holds (alpha(u,x)=1) or doesn't hold (alpha(u,x)=0). Here we will concentrate on the view of relations as maps to 2, instead of subsets. (OK, I do need to find a way of inserting LaTeX here, will do it soon!)

Now recently I became aware of a series of blog posts by Scott Garrabrant that describe how Chu spaces can be given an intuitive explanation in terms of a collection of agents interacting with an environment. Since Chu spaces and dialectica categories have (almost) the same objects, this same explanation works for dialectica categories too. So you can think of U as your (undercover) agents, and of  X as your unknown environments and alpha relates some agents to some unknown conditions in the environment.

One of the differences between Chu spaces and dialectica objects is that for Chu the set in which we evaluate the relation W does not have any structure: it's simply a set with elements {w, v, t,...}.  For dialectica we need an order on the elements of W to even construct the category.

Here's Scott's concrete example: Consider the case where there are two possible environments, $r$ for rain, and $s$ for sun. The agent independently chooses between two options, $u$ for umbrella, and $n$ for no umbrella, r for rain and s for sunny, $U=\{u,n\}$ and $X=\{r,s\}$. There are four possible worlds in $W=\{ur,us,nr,ns\}$. We interpret $ur$ as the world where the agent has an umbrella and it is raining, and similarly for the other worlds. The Chu  C space looks like a matrix 2x2, but nothing stops me from thinking of this as a dialectica object:

$C_{}=\begin{array}{cc}& \begin{array}{cc}r& s\end{array}\\ \begin{array}{c}u\\ n\end{array}& \left(\begin{array}{cc}ur& us\\ nr& ns\end{array}\right)\end{array}$

Vaughan Pratt has been trying to convince me that these matrices are lovely since before 2000, when we organized together a Workshop on Chu and Dialectica Spaces in Santa Barbara, that eventually became the TAC Special Volume. But while Vaughan has tried to tell me that the matrices are a good model of Linear Logic, Scott tells me that are a useful way of formalizing a community of agents.

I have been wanting to have a model of reasoning agents for a while. Dealing with multiagent systems (MAS) is what my friends Natasha and Brian do and I have always wanted to try to work more with them. So this is not it, yet, but I hope this thinking of dialectica categories as multiagent systems might turn out to be the bridge I need to work with Natasha again.