Additive Operations on Cartesian Frames

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 . 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 (), 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: is the category whose objects are Cartesian frames over , whose morphisms from to are pairs of functions , such that for all and , and whose composition of morphisms is given by .

The composition of two morphisms and , then, sends the agent of to and sends the environment of to .

Claim: is a category.

Proof: It suffices to show that composition is well-defined and associative and there exist identity morphisms. For identity, is clearly an identity on , where is the identity map from to itself.

The composition of with is . To verify that this is a morphism, we just need that for all , and , where . 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.

1. What Do These Morphisms Represent?

1.1. Morphisms as Interfaces

A Cartesian frame is a first-person perspective. The agent finds itself in a certain situation or game, where it expects to encounter an environment . The morphisms in allow the agent of one Cartesian frame to play the game of another Cartesian frame.

We can think of the morphisms from to as ways of fitting the agent of into the environment of . Indeed, for every morphism , one can construct a Cartesian frame , whose agent matches ‘s agent, and whose environment matches ’s environment, with given by . (The morphism from to can actually be viewed as the composition of with .)

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 to interact with some other environment . However, we aren’t just randomly throwing and together. ’s interaction with factors through the function , so can in a sense still be thought of as using an interface where it interacts with . It just interacts with an that is of the form for some . But this is happening simultaneously with the dual view in which can be thought of as still interacting with !

Since a Cartesian frame is a first-person perspective, you can imagine having the internal experience of interacting with , while has the “experience” of interacting with . The morphism’s job is to be the translation interface that allows this and to interact with each other, while preserving their respective internal experiences in such a way that they feel like they’re interacting with and respectively. gets to play ’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 to as saying something like “‘s agent is at least as strong as ’s agent.”

This is easiest to see for a morphism where and are both injective. In this case, it is as though and , so ’s agent has more options to choose between and fewer environments it has to worry about.

Since some of the environments in might have been good for the agent, the agent isn’t necessarily strictly better off in ; but in a zero-sum game, the agent will indeed be strictly better off. I think this justifies saying that ’s agent is in some sense weaker than agent.

If or is not injective, we could duplicate elements of and to make it injective, so the interpretation “‘s agent is no stronger than ’s agent” is reasonable in that case as well. In particular, the existence of a morphism from to implies that (and thus ).

However, the existence of a morphism is stronger than just saying the set of ensurables is larger. The morphism from to can be thought of as telling ‘s agent how to strategy-steal from ‘s agent, and thus do anything that ’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 () or ignoring the test (). We will represent the student with a Cartesian frame over letter grades, where .

If the student doesn’t study, her final grade is always a C+, represented by the possible world . If she does study, she may oversleep and get a bad grade (represented by the environment selecting and putting her in ). If she studies and doesn’t oversleep, she is uncertain about whether her teacher is typical (, resulting in ) or unusually demanding (, resulting in ). We represent this with the frame

.

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

.

There is a morphism from the student’s frame today to her frame yesterday, representing the fact that can be plugged into ’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

.

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

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

While and are both stronger than , we have no morphisms between and ; 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 and are equivalent (in a sense to be defined), there will be a morphism going from to and another going from to . But not all pairs of Cartesian frames with morphisms going both ways are equivalent. Consider, for example,

.

In , the default outcome is , but the agent and environment can handshake to produce . In , there are no choices, and there’s only one possible world, .

It turns out that there is a morphism , where is the constant function and is the constant function ; and there is a second morphism where is the constant function and is the constant function . We can interpret these like so:

  • There is a morphism because is effectively plus a promise from the environment “I’ll choose .” The agent in 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 because ’s agent has strictly more options than agent: moving from to lets you retain the option to produce if you want, but it also lets you try for .

So we can view the smaller matrix as the larger matrix plus a promise from the environment “I’ll choose ,” or we can view it as the larger matrix plus a commitment from the agent “I’ll choose .”

This example demonstrates that my intuitive statement “wherever there’s a morphism from to , is at least as strong as ” 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 , the agent of 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 , the agent of is “stronger” in the sense that it has more options.

2. Self-Duality

A key property of is that it is self-dual.

Definition: Let be the functor given by , where , and .

The more standard notation for dual in linear logic would be , but this is horrible notation.1

Claim: is an isomorphism between and .

Proof: First, we show is a functor. The objects in are the same as in , the morphisms from to in are the morphisms from to in , and composition is the same, but with the order reversed. clearly preserves identity morphisms. To show that 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 for the functor from to given by , where , and . Clearly, we have and composing to the identity in both orders, so is an isomorphism.

Going back to our visualization of Cartesian frames as matrices, just takes the transpose of the matrix, swapping agent with environment. ” 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, 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 , .

Proof: Trivial.

3. Sums of Cartesian Frames

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

Definition: For Cartesian frames and over , is the Cartesian frame , where if , and if .

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 or from , 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 , or as the agent of .

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 if the agent chooses from , and selects an option from if the agent chooses from .

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 and be given by the matrices

.

Here, is given by

.

If we wish to interpret 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 be given by the Cartesian frame , where is the empty set, is any singleton set, and is trivial, since it has empty domain.

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

Proof: Trivial.

Returning to our interpretation of morphisms as differences in agents’ strength: The agent of can choose between being the agent from or the agent from , and so is stronger than either. Indeed, we can think of ‘s agent as the weakest agent that is stronger than both ‘s agent and ’s agent. Mathematically, this translates to being the categorical coproduct in .

Theorem: is the coproduct of and in , and is initial in .

Proof: First, we show that is initial. We want to show that there exists a unique morphism from to a given . Indeed, a morphism from to is a function from to along with a function from to , and there is always exactly one such pair of functions, regardless of what and are. It is also easy to see that this pair of functions is a morphism, since the condition for morphism is empty, since is empty. Thus is initial.

Let , and let . We want to show that there exist inclusion morphisms and such that for any Cartesian frame , and any pair of morphisms and we have that there exists a unique morphism such that and .

First, we need to specify . We let , where is just the the obvious inclusion of into , and is just the obvious projection. This is clearly a morphism.

Given and , we let , where is given by where is such that , and is given by . This is a morphism because for all and , we have

where is such that . It is clear from the definitions that .

Finally, we need to show the uniqueness of this . Let be a morphism such that for both . This means that when , so for all . Similarly, must project to and , so

for all . Thus .

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 and over , is the Cartesian frame , where if , and if .

means that the agent might have to be the agent of , and might have to be the agent of , but does not get to decide which one. Thus, it will have to choose a pair, , where says how to behave in a situation, and says how to behave in a situation. The environment will “choose” to either be ‘s environment or ’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. is equivalent to an interaction where the environment first chooses which Cartesian frame, or , to play; then the agent observes this choice, and the agent and environment simultaneously behave as though they were in the chosen frame, either or .

(In fact, if and are disjoint, we can see this interpretation in the formalism by noting that —that is, the agent can change its behavior on the basis of whether the environment selected from or from .)

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

,

then is given by

.

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

It turns out that the second example we provided in “Introduction to Cartesian Frames” §3.2 (Examples of Controllables) is exactly equal to the product of these two Cartesian frames,

.

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 be given by the Cartesian frame , where is a singleton, is the empty set, and is trivial, since it has empty domain.

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

Proof: Trivial.

is essentially just from the point of view of the environment. Thus, since swaps agent and environment, we can express using and .

Claim: , , , and .

Proof: Trivial.

In other words, and are De Morgan dual with respect to .

In the same way that we interpreted as having the weakest agent that is stronger than the agents of and , we can interpret ’s agent as the strongest agent that is weaker than the agents of and .

Theorem: is the product of and in , and is terminal in .

Proof: Since is the coproduct in , it is the product in . Since is an isomorphism between and , we can take a product in of and by sending them to via this isomorphism, taking a product, and sending them back. Thus is the product in of and .

Similarly, since is initial in , it is terminal in . Thus, is terminal in .

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 is bad notation for dual is that normally represents , where is your category’s internal hom functor. For Chu spaces, is . Since will be the name for an object in our category, one would reasonably expect to represent , but it doesn’t. Worse still, does happen to be equivalent to , and this will be an important fact to understand. To minimize confusion, we instead use the common notation for dual.