The mathematical object (but not the philosophical interpretation) of a Cartesian Frame is studied under the name "Chu space."

(In category theory, Chu spaces are usually studied in the special case of $W=2$. To learn more about Chu spaces, see Vaughan Pratt's guide to papers and nLab's page on the Chu construction.)

In this post and the next one, I'll mostly be discussing standard facts about Chu spaces. I'll also discuss how to interpret the standard definitions as statements about agency.

Chu spaces form a category as a special case of the Chu construction. You may notice a strong similarity between operations on Cartesian frames and operations in linear logic, coming from the fact that the Chu construction is also intimately related to linear logic, and is used in the semantics for linear logic.

Linear logic has a large number of operations—additive conjunction ($\&$), multiplicative conjunction ($\otimes$), and so on—and many of those symbols will turn out to have interpretations for Cartesian frames, and they're actually going to be meaningful interpretations in this setting. For that reason, we'll be stealing much of our notation from linear logic, though this sequence won't assume familiarity with linear logic.

Definition: $\text{Chu}\left(W\right)$ is the category whose objects are Cartesian frames over $W$, whose morphisms from $C=(A,E,\cdot )$ to $D=(B,F,\star )$ are pairs of functions $(g:A\to B,h:F\to E)$, such that $a\cdot h\left(f\right)=g\left(a\right)\star f$ for all $a\in A$ and $f\in F$, and whose composition of morphisms is given by $(g_1,h_1)\circ (g_0,h_0)=(g_1\circ g_0,h_0\circ h_1)$.

The composition of two morphisms $C_0\to C_1$ and $C_1\to C_2$, then, sends the agent of $C_0$ to $C_2$ and sends the environment of $C_2$ to $C_0$.

Claim: $\text{Chu}\left(W\right)$ is a category.

Proof: It suffices to show that composition is well-defined and associative and there exist identity morphisms. For identity, $({\text{id}}_A,{\text{id}}_E)$ is clearly an identity on $C=(A,E,\cdot )$, where ${\text{id}}_X$ is the identity map from $X$ to itself.

The composition $(g_1,h_1)\circ (g_0,h_0)$ of $(g_0,h_0):C_0\to C_1$ with $(g_1,h_1):C_1\to C_2$ is $(g_1\circ g_0,h_0\circ h_1):C_0\to C_2$. To verify that this is a morphism, we just need that $a_0{\cdot }_0{h}_0\left(h_1\right(e_2\left)\right)=g_1\left(g_0\right(a_0\left)\right){\cdot }_2{e}_2$ for all $a_0\in \text{Agent}\left(C_0\right)$, and $e_2\in \text{Env}\left(C_2\right)$, where ${\cdot }_i=\text{Eval}\left(C_i\right)$. Indeed, 

since each component is a morphism.

Associativity of the composition follows from the fact that it is just a pair of compositions of functions on sets, and composition is associative for sets. $\square$

1. What Do These Morphisms Represent?

1.1. Morphisms as Interfaces

A Cartesian frame is a first-person perspective. The agent $A$ finds itself in a certain situation or game, where it expects to encounter an environment $E$. The morphisms in $\text{Chu}\left(W\right)$ allow the agent of one Cartesian frame to play the game of another Cartesian frame.

We can think of the morphisms from $C=(A,E,\cdot )$ to $D=(B,F,\star )$ as ways of fitting the agent of $C$ into the environment of $D$. Indeed, for every morphism $(g,h):C\to D$, one can construct a Cartesian frame $(A,F,\diamond )$, whose agent matches $C$'s agent, and whose environment matches $D$'s environment, with $\diamond$ given by $a\diamond f=a\cdot h\left(f\right)=g\left(a\right)\star f$. (The morphism from $C$ to $D$ can actually be viewed as the composition of $({\text{id}}_A,h):C\to (A,F,\diamond )$ with $(g,{\text{id}}_F):(A,F,\diamond )\to D$.)

Two random large Cartesian frames will typically have no morphisms between them. When there is a morphism, the morphism functions as an interface that allows the agent $A$ to interact with some other environment $F$. However, we aren't just randomly throwing $A$ and $F$ together. $A$'s interaction with $F$ factors through the function $h:F\to E$, so $A$ can in a sense still be thought of as using an interface where it interacts with $E$. It just interacts with an $e\in E$ that is of the form $h\left(f\right)$ for some $f\in F$. But this is happening simultaneously with the dual view in which $F$ can be thought of as still interacting with $B$!

Since a Cartesian frame is a first-person perspective, you can imagine $A$ having the internal experience of interacting with $E$, while $F$ has the "experience" of interacting with $B$. The morphism's job is to be the translation interface that allows this $A$ and $F$ to interact with each other, while preserving their respective internal experiences in such a way that they feel like they're interacting with $E$ and $B$ respectively. $A$ gets to play $B$'s game, while still thinking that it is playing its own game.

1.2. Morphisms as Differences in Agents' Strength

We can also interpret the existence of a morphism from $C=(A,E,\cdot )$ to $D=(B,F,\star )$ as saying something like "$D$'s agent is at least as strong as $C$'s agent."

This is easiest to see for a morphism $(g,h):C\to D$ where $g$ and $h$ are both injective. In this case, it is as though $A\subseteq B$ and $F\subseteq E$, so $D$'s agent has more options to choose between and fewer environments it has to worry about.

Since some of the environments in $E\setminus F$ might have been good for the agent, the agent isn't necessarily strictly better off in $D$; but in a zero-sum game, the agent will indeed be strictly better off. I think this justifies saying that $C$'s agent is in some sense weaker than $D\text{'s}$ agent.

If $g$ or $h$ is not injective, we could duplicate elements of $B$ and $E$ to make it injective, so the interpretation "$C$'s agent is no stronger than $D$'s agent" is reasonable in that case as well. In particular, the existence of a morphism from $C$ to $D$ implies that $\text{Ensure}\left(C\right)\subseteq \text{Ensure}\left(D\right)$ (and thus $\text{Ctrl}\left(C\right)\subseteq \text{Ctrl}\left(D\right)$).

However, the existence of a morphism is stronger than just saying the set of ensurables is larger. The morphism from $C$ to $D$ can be thought of as telling $D$'s agent how to strategy-steal from $C$'s agent, and thus do anything that $C$'s agent can do.

We now provide a few examples to illustrate morphisms between Cartesian frames. (If you're ready to forge ahead, skip to §2 instead.)

1.3. Simple Examples of Morphisms

Imagine a student who is deciding between staying up late studying for a test ($a_s$) or ignoring the test ($a_i$). We will represent the student with a Cartesian frame over letter grades, where $W=\{\text{A+},\text{A},\text{A-},\text{B+},\text{B},\text{B-},\text{C+},\text{C},\text{C-},\text{D+},\text{D},\text{D-},\text{F}\}$.

If the student doesn't study, her final grade is always a C+, represented by the possible world $\text{C+}$. If she does study, she may oversleep and get a bad grade (represented by the environment selecting $e_o$ and putting her in $\text{D-}$). If she studies and doesn't oversleep, she is uncertain about whether her teacher is typical ($e_t$, resulting in $\text{A-}$) or unusually demanding ($e_d$, resulting in $\text{B+}$). We represent this with the frame

$C_T=\begin{array}{cc}& \begin{array}{ccc}{e}_t& e_d& e_o\end{array}\\ \begin{array}{c}{a}_s\\ a_i\end{array}& \left(\begin{array}{ccc}\text{A-}& \text{B+}& \text{D-}\\ \text{C+}& \text{C+}& \text{C+}\end{array}\right)\end{array}$.

Let us also suppose that yesterday, the student had the extra option of copying another student's answers on test day to get a sure A+. However, she decided not to cheat. We represent the student's options yesterday, prior to precommitting, with the frame

$C_Y=\begin{array}{cc}& \begin{array}{ccc}{f}_t& f_d& f_o\end{array}\\ \begin{array}{c}{b}_s\\ b_i\\ b_c\end{array}& \left(\begin{array}{ccc}\text{A-}& \text{B+}& \text{D-}\\ \text{C+}& \text{C+}& \text{C+}\\ \text{A+}& \text{A+}& \text{A+}\end{array}\right)\end{array}$.

There is a morphism from the student's frame today to her frame yesterday, representing the fact that $\text{Agent}\left(C_T\right)$ can be plugged into $\text{Agent}\left(C_Y\right)$'s game, or that the student was "stronger" yesterday than she is today.

Let us also suppose that the student's teacher is in fact demanding. If the student today knew this fact, we would instead represent her perspective with the frame

$C_{T^{\prime }}=\begin{array}{cc}& \begin{array}{cc}{e}_d^{\prime }& e_o^{\prime }\end{array}\\ \begin{array}{c}{a}_s^{\prime }\\ a_i^{\prime }\end{array}& \left(\begin{array}{cc}\text{B+}& \text{D-}\\ \text{C+}& \text{C+}\end{array}\right)\end{array}$.

Here, we have a morphism from the student today ($C_T$) to her perspective if she had an additional promise from the environment ($C_{T^{\prime }}$). This represents the fact that $C_{T^{\prime }}$ can strategy-steal from a version of herself who knows strictly less.

Given two Cartesian frames $C_0$ and $C_1$, I am not aware of an efficient universal method for determining whether there exists a morphism from $C_0$ to $C_1$. Indeed, I conjecture that this problem might be NP-complete. In the above cases, however, we can see that there exist morphisms from $C_T$ to the other two frames by observing that $C_T$ is effectively $C_Y$ with a row deleted, or $C_{T^{\prime }}$ with a column added.

While $\text{Agent}\left(C_Y\right)$ and $\text{Agent}\left(C_{T^{\prime }}\right)$ are both stronger than $\text{Agent}\left(C_T\right)$, we have no morphisms between $C_Y$ and $C_{T^{\prime }}$; their options are different enough that we can't compare their strength directly.

1.4. Examples of Morphisms Going Both Ways

Every Cartesian frame has an identity morphism pointing to itself; and as we'll discuss in the next post, whenever two Cartesian frames $C$ and $D$ are equivalent (in a sense to be defined), there will be a morphism going from $C$ to $D$ and another going from $D$ to $C$. But not all pairs of Cartesian frames with morphisms going both ways are equivalent. Consider, for example,

$C_1=\begin{array}{cc}& \begin{array}{cc}{e}_0& e_1\end{array}\\ \begin{array}{c}{a}_0\\ a_1\end{array}& \left(\begin{array}{cc}{w}_0& w_0\\ w_0& w_1\end{array}\right)\end{array}\text{and}{D}_1=\begin{array}{cc}& \begin{array}{c}{f}_0\end{array}\\ \begin{array}{c}{b}_0\end{array}& \left(\begin{array}{c}{w}_0\end{array}\right)\end{array}$.

In $C_1=(A,E,\cdot )$, the default outcome is $w_0$, but the agent and environment can handshake to produce $w_1$. In $D_1=(B,F,\star )$, there are no choices, and there's only one possible world, $w_0$.

It turns out that there is a morphism $(g,h):C_1\to D_1$, where $g$ is the constant function $b_0$ and $h$ is the constant function $e_0$; and there is a second morphism $(g^{\prime },h^{\prime }):D_1\to C_1,$ where $g^{\prime }$ is the constant function $a_0$ and $h^{\prime }$ is the constant function $f_0$. We can interpret these like so:

• There is a morphism $C_1\to D_1$ because $D_1$ is effectively $C_1$ plus a promise from the environment "I'll choose $e_0$." The agent in $D_1$ is "stronger" in the sense that it has fewer possible environments to worry about. There is less the environment can do to interfere with the agent's choices.
• There is a morphism $D_1\to C_1$ because $C_1$'s agent has strictly more options than $D_1\text{'s}$ agent: moving from $D_1$ to $C_1$ lets you retain the option to produce $w_0$ if you want, but it also lets you try for $w_1$.

So we can view the smaller matrix as the larger matrix plus a promise from the environment "I'll choose $e_0$," or we can view it as the larger matrix plus a commitment from the agent "I'll choose $a_0$."

This example demonstrates that my intuitive statement "wherever there's a morphism from $C$ to $D$, $D$ is at least as strong as $C$" conflates two different notions of "stronger." These notions often go together, but come apart in situations such as the handshake example. Like the hypothetical student in $C_{T^{\prime }}$, the agent of $D_1$ is "stronger" in the sense that the environment can't do as much to get in the way. But like the not-yet-precommitted student in $C_Y$, the agent of $C_1$ is "stronger" in the sense that it has more options.

2. Self-Duality

A key property of $\text{Chu}\left(W\right)$ is that it is self-dual.

Definition: Let ${-}^{\ast }:\text{Chu}\left(W\right)\to \text{Chu}(W{)}^{\text{op}}$ be the functor given by $(A,E,\cdot {)}^{\ast }=(E,A,\star )$, where $e\star a=a\cdot e$, and $(g,h{)}^{\ast }=(h,g)$.

The more standard notation for dual in linear logic would be ${-}^{\perp }$, but this is horrible notation.¹

Claim: ${-}^{\ast }$ is an isomorphism between $\text{Chu}\left(W\right)$ and $\text{Chu}(W{)}^{\text{op}}$.

Proof: First, we show ${-}^{\ast }$ is a functor. The objects in $\text{Chu}(W{)}^{\text{op}}$ are the same as in $\text{Chu}\left(W\right)$, the morphisms from $D$ to $C$ in $\text{Chu}(W{)}^{\text{op}}$ are the morphisms from $C$ to $D$ in $\text{Chu}\left(W\right)$, and composition is the same, but with the order reversed. ${-}^{\ast }$ clearly preserves identity morphisms. To show that ${-}^{\ast }$ preserves composition, we have

To see that it is an isomorphism, we need a left and right inverse. We will abuse notation and also write ${-}^{\ast }$ for the functor from $\text{Chu}(W{)}^{\text{op}}$ to $\text{Chu}\left(W\right)$ given by $(E,A,\star {)}^{\ast }=(A,E,\cdot )$, where $a\cdot e=e\star a$, and $(h,g{)}^{\ast }=(g,h)$. Clearly, we have ${-}^{\ast }:\text{Chu}\left(W\right)\to \text{Chu}(W{)}^{\text{op}}$ and ${-}^{\ast }:\text{Chu}(W{)}^{\text{op}}\to \text{Chu}(W)$ composing to the identity in both orders, so ${-}^{\ast }$ is an isomorphism. $\square$

Going back to our visualization of Cartesian frames as matrices, ${-}^{\ast }$ just takes the transpose of the matrix, swapping agent with environment. "$\text{Chu}\left(W\right)$ is self-dual" is another way of saying that transposing a Cartesian frame always gives you another Cartesian frame.

Philosophically, depending on our interpretation, this may be doing something weird. We talk about possible agents and possible environments, but we may mean something different by "possible" in those two cases.

Since we are imagining events from the point of view of the agents, "possible agents" is referring to all of the ways the agent can choose to be by exercising its "free will." We could think of "possible environments" similarly, or we could think of possible environments as representing the agent's uncertainty.

Under the view where possible environments represent uncertainty, ${-}^{\ast }$ is pointing to an interesting duality that swaps choices with uncertainty, swaps the "could" of "I could do X" with the "could" of "The world could have property Y," and (if we add probability to the mix) swaps mixed strategies with probabilistic uncertainty. "What will I do?" becomes "What game am I playing?", or "What is the world-as-a-function-of-my-action like?"

I will introduce many operations on Cartesian frames, so it will help to highlight even the basic properties as I go. Here, I'll note:

Claim: For any Cartesian