Additive Operations on Cartesian Frames

by Scott Garrabrant11 min read26th Oct 20204 comments

22

Embedded AgencyCategory TheoryAI
Frontpage

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.

 


Note: I'll be holding online office hours 2-4pm the next three Sundays, for discussing Cartesian frames and answering questions. This Sunday at 2, I'll also be giving a talk on Cartesian frames on Gather.Town, with this post and "Introduction to Cartesian Frames" as prerequisites. See Ben's post for details on the talk and office hours.

 

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.

22

4 comments, sorted by Highlighting new comments since Today at 8:23 AM
New Comment

Scott's Sunday talk, covering content from this post and the Intro post: https://www.youtube.com/watch?v=H1tJdaCvcck 

Typo in the definition of product: b cdot e should be b star e.

Yep. Fixed. Thanks.

The main intuition this sparks in me is that it gives us concrete data structures to look for when talking broadly about the brain doing 'compression' by rotating a high dimensional object and carving off recognized chunks (simple distributions) in order to make the messy inputs more modular, composable, accessible, error correctable, etc. Sort of the way that predictive coding gives us a target to hunt for in looking for structures that look like they might be doing something like the atomic predictive coding unit.