Additive Operations on Cartesian Frames

post by Scott Garrabrant · 2020-10-26T15:12:14.556Z · LW · GW · 6 comments

Contents

  1. What Do These Morphisms Represent?
    1.1. Morphisms as Interfaces
    1.2. Morphisms as Differences in Agents' Strength
    1.3. Simple Examples of Morphisms
    1.4. Examples of Morphisms Going Both Ways
  2. Self-Duality
  3. Sums of Cartesian Frames
  4. Products of Cartesian Frames
  Footnotes
None
6 comments

The mathematical object (but not the philosophical interpretation) of a Cartesian Frame [LW · GW] 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, 

$$\begin{array}{cc}{a}_0{\cdot }_0{h}_0\left(h_1\right(e_2\left)\right)& =g_0\left(a_0\right){\cdot }_1{h}_1\left(e_2\right)\\ & =g_1\left(g_0\right(a_0\left)\right){\cdot }_2{e}_2,\end{array}$$

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 [LW · GW] 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.¹ [LW(p) · GW(p)]

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

$$\begin{array}{cc}(g_0,h_0{)}^{\ast }{\circ }^{\text{op}}(g_1,h_1{)}^{\ast }& =(h_1,g_1)\circ (h_0,g_0)\\ & =(h_1\circ h_0,g_0\circ g_1)\\ & =\left(\right(g_0,h_0)\circ (g_1,h_1){)}^{\ast }.\end{array}$$

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 frame $C$, $(C^{\ast }{)}^{\ast }=C$.

Proof: Trivial. $\square$

 

3. Sums of Cartesian Frames

The first binary operation on Cartesian frames I want to introduce is the sum, $\oplus$.

Definition: For Cartesian frames $C=(A,E,\cdot )$ and $D=(B,F,\star )$ over $W$, $C\oplus D$ is the Cartesian frame $(A\bigsqcup B,E\times F,\diamond )$, where $a\diamond (e,f)=a\cdot e$ if $a\in A$, and $a\diamond (e,f)=a\star f$ if $a\in B$.

The sum takes the disjoint union of the agents and the Cartesian product of the environments, and does the obvious thing with the evaluation function. The agent can choose any strategy from $A$ or from $B$, and the environment has to respond to that strategy. We can interpret this as an agent that can choose between two different first-person perspectives: it can decide to interact with the environment as the agent of $C$, or as the agent of $D$.

Maybe "Rebecca the chess player" is considering which chess opening to employ, whereas "Rebecca the food-eater" is considering putting her plate down on the chess board and having lunch instead. "Rebecca the agent that can choose between playing chess and having lunch" is the sum of the other two Rebeccas.

If Rebecca tunnel-visions on the chess game, she may not consider her other options. Likewise if she tunnel-visions on lunch. If she inhabits the perspective of the third Rebecca, she can instead decide between chess moves and decide whether she wants to be playing chess at all.

Meanwhile, the environment must use a policy that selects an option from $E$ if the agent chooses from $A$, and selects an option from $F$ if the agent chooses from $B$.

In the chess example: The environment must be able to respond to different chess moves, but it must also be able to respond to Rebecca deciding to play a different game.

To give a formal example, let $C_2=(A,E,\cdot )$ and $D_2=(B,F,\star )$ be given by the matrices

$C_2=\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_1\\ w_2& w_3\end{array}\right)\end{array}\text{and}{D}_2=\begin{array}{cc}& \begin{array}{ccc}{f}_0& f_1& f_2\end{array}\\ \begin{array}{c}{b}_0\\ b_1\\ b_2\end{array}& \left(\begin{array}{ccc}{w}_4& w_5& w_6\\ w_7& w_8& w_9\\ w_{10}& w_{11}& w_{12}\end{array}\right)\end{array}$.

Here, $C_2\oplus D_2$ is given by

$C_2\oplus D_2=\begin{array}{cc}& \begin{array}{cccccc}{e}_0{f}_0& e_0{f}_1& e_0{f}_2& e_1{f}_0& e_1{f}_1& e_1{f}_2\end{array}\\ \begin{array}{c}{a}_0\\ a_1\\ b_0\\ b_1\\ b_2\end{array}& \left(\begin{array}{cccccc}{w}_0& w_0& w_0& w_1& w_1& w_1\\ w_2& w_2& w_2& w_3& w_3& w_3\\ w_4& w_5& w_6& w_4& w_5& w_6\\ w_7& w_8& w_9& w_7& w_8& w_9\\ w_{10}& w_{11}& w_{12}& w_{10}& w_{11}& w_{12}\end{array}\right)\end{array}$.

If we wish to interpret $C_2\oplus D_2$ temporally, we can say: The agent first chooses what game to play. The environment then, as a function of which game was chosen, "chooses" what it does; and the agent simultaneously chooses its own move within the game it picked.

Definition: Let $0$ be given by the Cartesian frame $0=\left(\right\{\},\{e\},\cdot )$, where $\text{Agent}\left(0\right)$ is the empty set, $\text{Env}\left(0\right)=\left\{e\right\}$ is any singleton set, and $\text{Eval}\left(0\right)$ is trivial, since it has empty domain.

Claim: $\oplus$ is commutative and associative, and $0$ is the identity of $\oplus$ (up to isomorphism).

Proof: Trivial. $\square$

Returning to our interpretation of morphisms as differences in agents' strength: The agent of $C\oplus D$ can choose between being the agent from $C$ or the agent from $D$, and so is stronger than either. Indeed, we can think of $C\oplus D$'s agent as the weakest agent that is stronger than both $C$'s agent and $D$'s agent. Mathematically, this translates to $\oplus$ being the categorical coproduct in $\text{Chu}\left(W\right)$.

Theorem: $C_0\oplus C_1$ is the coproduct of $C_0$ and $C_1$ in $\text{Chu}\left(W\right)$, and $0$ is initial in $\text{Chu}\left(W\right)$.

Proof: First, we show that $0$ is initial. We want to show that there exists a unique morphism from $0$ to a given $C$. Indeed, a morphism from $0$ to $C=(A,E,\cdot )$ is a function from $\left\{\right\}$ to $A$ along with a function from $E$ to $\left\{e\right\}$, and there is always exactly one such pair of functions, regardless of what $A$ and $E$ are. It is also easy to see that this pair of functions is a morphism, since the condition for morphism is empty, since $\text{Agent}\left(0\right)$ is empty. Thus $0$ is initial.

Let $C_i=(A_i,E_i,{\cdot }_i)$, and let $C_0\oplus C_1=(A_0\bigsqcup A_1,E_0\times E_1,\diamond )$. We want to show that there exist inclusion morphisms ${\iota }_0:C_0\to C_0\oplus C_1$ and ${\iota }_1:C_1\to C_0\oplus C_1$ such that for any Cartesian frame $D=(B,F,\star )$, and any pair of morphisms ${\varphi }_0:C_0\to D$ and ${\varphi }_1:C_1\to D,$ we have that there exists a unique morphism $\varphi :C_0\oplus C_1\to D$ such that $\varphi \circ {\iota }_0={\varphi }_0$ and $\varphi \circ {\iota }_1={\varphi }_1$.

First, we need to specify ${\iota }_i:(A_i,E_i,{\cdot }_i)\to (A_0\bigsqcup A_1,E_0\times E_1,\diamond )$. We let ${\iota }_i=(j_i,k_i)$, where $j_i:A_i\to A_0\bigsqcup A_1$ is just the the obvious inclusion of $A_i$ into $A_0\bigsqcup A_1$, and $k_i:E_0\times E_1\to E_i$ is just the obvious projection. This is clearly a morphism.

Given ${\varphi }_0=(g_0,h_0):C_0\to D$ and ${\varphi }_1=(g_1,h_1):C_1\to D$, we let $\varphi =(g,h)$, where $g:A_0\bigsqcup A_1\to B$ is given by $g\left(a\right)=g_i\left(a\right)$ where $i$ is such that $a\in A_i$, and $h:F\to E_0\times E_1$ is given by $h\left(f\right)=\left(h_0\right(f),h_1(f\left)\right)$. This is a morphism because for all $a\in A_0\bigsqcup A_1$ and $f\in F$, we have

$$\begin{array}{cc}a\diamond h\left(f\right)& =a{\cdot }_i{h}_i\left(f\right)\\ & =g_i\left(a\right)\star f\\ & =g\left(a\right)\star f,\end{array}$$

where $i$ is such that $a\in A_i$. It is clear from the definitions that $\varphi \circ {\iota }_i={\varphi }_i$.

Finally, we need to show the uniqueness of this $\varphi$. Let ${\varphi }^{\prime }=(g^{\prime },h^{\prime }):C_0\oplus C_1\to D$ be a morphism such that ${\varphi }^{\prime }\circ {\iota }_i={\varphi }_i$ for both $i=1,2$. This means that $g^{\prime }\left(a\right)=g_i\left(a\right)$ when $a\in A_i$, so $g^{\prime }\left(a\right)=g\left(a\right)$ for all $a\in A_0\bigsqcup A_1$. Similarly, $h^{\prime }\left(f\right)$ must project to $h_0\left(f\right)$ and $h_1\left(f\right)$, so

$$\begin{array}{cc}{h}^{\prime }\left(f\right)& =\left(h_0\right(f),h_1(f\left)\right)\\ & =h\left(f\right)\end{array}$$

for all $f\in F$. Thus ${\varphi }^{\prime }=\varphi$. $\square$

 

4. Products of Cartesian Frames

Dual to sum, we have the product operation, $\&$. This operation is a product. It is also in the section on additive operations. There are many counterintuitive things about the notation of Chu spaces and linear logic.

Definition: For Cartesian frames $C=(A,E,\cdot )$ and $D=(B,F,\star )$ over $W$, $C\&D$ is the Cartesian frame $(A\times B,E\bigsqcup F,\diamond )$, where $(a,b)\diamond e=a\cdot e$ if $e\in E$, and $(a,b)\diamond e=b\star e$ if $e\in F$.

$C\&D$ means that the agent might have to be the agent of $C$, and might have to be the agent of $D$, but does not get to decide which one. Thus, it will have to choose a pair, $(a,b)$, where $a$ says how to behave in a $C$ situation, and $b$ says how to behave in a $D$ situation. The environment will "choose" to either be $C$'s environment or $D$'s environment. When the agent and environment interact, the agent uses the component of its pair that matches the environment's choice.

Instead of thinking of the agent as choosing a pair, we could again think about the situation temporally. $C\&D$ is equivalent to an interaction where the environment first chooses which Cartesian frame, $C$ or $D$, to play; then the agent observes this choice, and the agent and environment simultaneously behave as though they were in the chosen frame, either $C$ or $D$.

(In fact, if $\text{Image}\left(C\right)$ and $\text{Image}\left(D\right)$ are disjoint, we can see this interpretation in the formalism by noting that $\text{Image}\left(C\right)\in \text{Obs}\left(C\&D\right)$—that is, the agent can change its behavior on the basis of whether the environment selected from $C$ or from $D$.)

For example, if we let $C_2$ and $D_2$ be as the example in §3,

$C_2=\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_1\\ w_2& w_3\end{array}\right)\end{array}\text{and}{D}_2=\begin{array}{cc}& \begin{array}{ccc}{f}_0& f_1& f_2\end{array}\\ \begin{array}{c}{b}_0\\ b_1\\ b_2\end{array}& \left(\begin{array}{ccc}{w}_4& w_5& w_6\\ w_7& w_8& w_9\\ w_{10}& w_{11}& w_{12}\end{array}\right)\end{array}$,

then $C_2\&D_2$ is given by

$C_2\&D_2=\begin{array}{cc}& \begin{array}{ccccc}{e}_0& e_1& f_0& f_1& f_2\end{array}\\ \begin{array}{c}{a}_0{b}_0\\ a_0{b}_1\\ a_0{b}_2\\ a_1{b}_0\\ a_1{b}_1\\ a_1{b}_2\end{array}& \left(\begin{array}{ccccc}{w}_0& w_1& w_4& w_5& w_6\\ w_0& w_1& w_7& w_8& w_9\\ w_0& w_1& w_{10}& w_{11}& w_{12}\\ w_2& w_3& w_4& w_5& w_6\\ w_2& w_3& w_7& w_8& w_9\\ w_2& w_3& w_{10}& w_{11}& w_{12}\end{array}\right)\end{array}$.

A second example: Suppose that we have two Cartesian frames, $C_3$ and $D_3$.  $C_3$ is a frame in which it's raining, and the agent chooses whether to carry an umbrella. $D_3$ is a frame in which it's sunny, and the agent chooses whether to carry an umbrella.

$C_3=\begin{array}{cc}& \begin{array}{c}r\end{array}\\ \begin{array}{c}u\\ n\end{array}& \left(\begin{array}{c}ur\\ nr\end{array}\right)\end{array}\text{and}{D}_3=\begin{array}{cc}& \begin{array}{c}s\end{array}\\ \begin{array}{c}u\\ n\end{array}& \left(\begin{array}{c}us\\ ns\end{array}\right)\end{array}$

It turns out that the second example we provided in "Introduction to Cartesian Frames" §3.2 (Examples of Controllables [LW · GW]) is exactly equal to the product of these two Cartesian frames, 

$\begin{array}{cc}& \begin{array}{cc}r& s\end{array}\\ \begin{array}{c}uu=u\\ nn=n\\ un=u\leftrightarrow r\\ nu=u\leftrightarrow s\end{array}& \left(\begin{array}{cc}ur& us\\ nr& ns\\ ur& ns\\ nr& us\end{array}\right)\end{array}$.

The environment is the disjoint union of the rain and sun environments, and the policies of the agent can be viewed as "I get to choose what to do as a function of what game we're playing," where "what game we're playing" is "what the weather is."

Definition: Let $\top$ be given by the Cartesian frame $\top =\left(\right\{a\},\{\},\cdot )$, where $\text{Agent}\left(\top \right)$ is a singleton, $\text{Env}\left(\top \right)$ is the empty set, and $\text{Eval}\left(\top \right)$ is trivial, since it has empty domain.

Claim: $\&$ is commutative and associative, and $\top$ is the identity of $\&$ (up to isomorphism).

Proof: Trivial. $\square$

$\&$ is essentially just $\oplus$ from the point of view of the environment. Thus, since ${-}^{\ast }$ swaps agent and environment, we can express $\&$ using $\oplus$ and ${-}^{\ast }$.

Claim: $C\&D=(C^{\ast }\oplus D^{\ast }{)}^{\ast }$, $\top =0^{\ast }$, $C\oplus D=(C^{\ast }\&D^{\ast }{)}^{\ast }$, and $0={\top }^{\ast }$.

Proof: Trivial. $\square$

In other words, $\oplus$ and $\&$ are De Morgan dual with respect to ${-}^{\ast }$.

In the same way that we interpreted $C\oplus D$ as having the weakest agent that is stronger than the agents of $C$ and $D$, we can interpret $C\&D$'s agent as the strongest agent that is weaker than the agents of $C$ and $D$.

Theorem: $C_0\&C_1$ is the product of $C$ and $D$ in $\text{Chu}\left(W\right)$, and $\top$ is terminal in $\text{Chu}\left(W\right)$.

Proof: Since $\oplus$ is the coproduct in $\text{Chu}\left(W\right)$, it is the product in $\text{Chu}(W{)}^{\text{op}}$. Since ${-}^{\ast }$ is an isomorphism between $\text{Chu}\left(W\right)$ and $\text{Chu}(W{)}^{\text{op}}$, we can take a product in $\text{Chu}\left(W\right)$ of $C_0$ and $C_1$ by sending them to $\text{Chu}(W{)}^{\text{op}}$ via this isomorphism, taking a product, and sending them back. Thus $(C_0^{\ast }\oplus C_1^{\ast }{)}^{\ast }=C_0\&C_1$ is the product in $\text{Chu}\left(W\right)$ of $C_0$ and $C_1$.

Similarly, since $0$ is initial in $\text{Chu}\left(W\right)$, it is terminal in $\text{Chu}(W{)}^{\text{op}}$. Thus, $0^{\ast }=\top$ is terminal in $\text{Chu}\left(W\right)$. $\square$

 

Our next post will discuss equivalence relations between Cartesian frames. We will introduce a homotopy equivalence on Cartesian frames, and employ these relations to classify small Cartesian frames up to homotopy.

 

---

Footnotes

1. One important reason ${-}^{\perp }$ is bad notation for dual is that $A^B$ normally represents $B\to A$, where $\to$ is your category's internal hom functor. For Chu spaces, $\to$ is $⊸$. Since $\perp$ will be the name for an object in our category, one would reasonably expect $C^{\perp }$ to represent $\perp ⊸C$, but it doesn't. Worse still, $C^{\ast }$ does happen to be equivalent to $C⊸\perp$, and this will be an important fact to understand. To minimize confusion, we instead use the common notation ${-}^{\ast }$ for dual. ↩ [LW · GW]

6 comments

Comments sorted by top scores.