Scott's Sunday talk, covering content from this post and the Intro post: https://www.youtube.com/watch?v=H1tJdaCvcck
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.
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 (⊗), 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: Chu(W) is the category whose objects are Cartesian frames over W, whose morphisms from C=(A,E,⋅) to D=(B,F,⋆) are pairs of functions (g:A→B,h:F→E), such that a⋅h(f)=g(a)⋆f for all a∈A and f∈F, and whose composition of morphisms is given by (g1,h1)∘(g0,h0)=(g1∘g0,h0∘h1).
The composition of two morphisms C0→C1 and C1→C2, then, sends the agent of C0 to C2 and sends the environment of C2 to C0.
Claim: Chu(W) is a category.
Proof: It suffices to show that composition is well-defined and associative and there exist identity morphisms. For identity, (idA,idE) is clearly an identity on C=(A,E,⋅), where idX is the identity map from X to itself.
The composition (g1,h1)∘(g0,h0) of (g0,h0):C0→C1 with (g1,h1):C1→C2 is (g1∘g0,h0∘h1):C0→C2. To verify that this is a morphism, we just need that a0⋅0h0(h1(e2))=g1(g0(a0))⋅2e2 for all a0∈Agent(C0), and e2∈Env(C2), where ⋅i=Eval(Ci). Indeed,
a0⋅0h0(h1(e2))=g0(a0)⋅1h1(e2)=g1(g0(a0))⋅2e2,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 A finds itself in a certain situation or game, where it expects to encounter an environment E. The morphisms in Chu(W) 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,⋅) to D=(B,F,⋆) as ways of fitting the agent of C into the environment of D. Indeed, for every morphism (g,h):C→D, one can construct a Cartesian frame (A,F,⋄), whose agent matches C's agent, and whose environment matches D's environment, with ⋄ given by a⋄f=a⋅h(f)=g(a)⋆f. (The morphism from C to D can actually be viewed as the composition of (idA,h):C→(A,F,⋄) with (g,idF):(A,F,⋄)→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→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∈E that is of the form h(f) for some f∈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,⋅) to D=(B,F,⋆) 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→D where g and h are both injective. In this case, it is as though A⊆B and F⊆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∖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'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 Ensure(C)⊆Ensure(D) (and thus Ctrl(C)⊆Ctrl(D)).
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 (as) or ignoring the test (ai). We will represent the student with a Cartesian frame over letter grades, where W={A+,A,A-,B+,B,B-,C+,C,C-,D+,D,D-,F}.
If the student doesn't study, her final grade is always a C+, represented by the possible world C+. If she does study, she may oversleep and get a bad grade (represented by the environment selecting eo and putting her in D-). If she studies and doesn't oversleep, she is uncertain about whether her teacher is typical (et, resulting in A-) or unusually demanding (ed, resulting in B+). We represent this with the frame
CT=et ed eoasai(A-B+D-C+C+C+).
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
CY=ft fd fobsbibc⎛⎜⎝A-B+D-C+C+C+A+A+A+⎞⎟⎠.
There is a morphism from the student's frame today to her frame yesterday, representing the fact that Agent(CT) can be plugged into Agent(CY)'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
CT′=e′d e′oa′sa′i(B+D-C+C+).
Here, we have a morphism from the student today (CT) to her perspective if she had an additional promise from the environment (CT′). This represents the fact that CT′ can strategy-steal from a version of herself who knows strictly less.
Given two Cartesian frames C0 and C1, I am not aware of an efficient universal method for determining whether there exists a morphism from C0 to C1. Indeed, I conjecture that this problem might be NP-complete. In the above cases, however, we can see that there exist morphisms from CT to the other two frames by observing that CT is effectively CY with a row deleted, or CT′ with a column added.
While Agent(CY) and Agent(CT′) are both stronger than Agent(CT), we have no morphisms between CY and CT′; 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,
C1=e0e1a0a1(w0w0w0w1) and D1=f0b0(w0).
In C1=(A,E,⋅), the default outcome is w0, but the agent and environment can handshake to produce w1. In D1=(B,F,⋆), there are no choices, and there's only one possible world, w0.
It turns out that there is a morphism (g,h):C1→D1, where g is the constant function b0 and h is the constant function e0; and there is a second morphism (g′,h′):D1→C1, where g′ is the constant function a0 and h′ is the constant function f0. We can interpret these like so:
So we can view the smaller matrix as the larger matrix plus a promise from the environment "I'll choose e0," or we can view it as the larger matrix plus a commitment from the agent "I'll choose a0."
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 CT′, the agent of D1 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 CY, the agent of C1 is "stronger" in the sense that it has more options.
2. Self-Duality
A key property of Chu(W) is that it is self-dual.
Definition: Let −∗:Chu(W)→Chu(W)op be the functor given by (A,E,⋅)∗=(E,A,⋆), where e⋆a=a⋅e, and (g,h)∗=(h,g).
The more standard notation for dual in linear logic would be −⊥, but this is horrible notation.1
Claim: −∗ is an isomorphism between Chu(W) and Chu(W)op.
Proof: First, we show −∗ is a functor. The objects in Chu(W)op are the same as in Chu(W), the morphisms from D to C in Chu(W)op are the morphisms from C to D in Chu(W), and composition is the same, but with the order reversed. −∗ clearly preserves identity morphisms. To show that −∗ preserves composition, we have
(g0,h0)∗∘op(g1,h1)∗=(h1,g1)∘(h0,g0)=(h1∘h0,g0∘g1)=((g0,h0)∘(g1,h1))∗.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 Chu(W)op to Chu(W) given by (E,A,⋆)∗=(A,E,⋅), where a⋅e=e⋆a, and (h,g)∗=(g,h). Clearly, we have −∗:Chu(W)→Chu(W)op and −∗:Chu(W)op→Chu(W) 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. "Chu(W) 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 C, (C∗)∗=C.
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 C=(A,E,⋅) and D=(B,F,⋆) over W, C⊕D is the Cartesian frame (A⊔B,E×F,⋄), where a⋄(e,f)=a⋅e if a∈A, and a⋄(e,f)=a⋆f if a∈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 C2=(A,E,⋅) and D2=(B,F,⋆) be given by the matrices
C2=e0e1a0a1(w0w1w2w3) and D2=f0 f1 f2b0b1b2⎛⎜⎝w4w5w6w7w8w9w10w11w12⎞⎟⎠.
Here, C2⊕D2 is given by
C2⊕D2=e0f0 e0f1 e0f2 e1f0 e1f1 e1f2a0a1b0b1b2⎛⎜ ⎜ ⎜ ⎜ ⎜ ⎜⎝ w0 w0 w0 w1 w1 w1 w2 w2 w2 w3 w3 w3 w4 w5 w6 w4 w5 w6 w7 w8 w9 w7 w8 w9 w10 w11 w12 w10 w11 w12 ⎞⎟ ⎟ ⎟ ⎟ ⎟ ⎟⎠.
If we wish to interpret C2⊕D2 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=({},{e},⋅), where Agent(0) is the empty set, Env(0)={e} is any singleton set, and Eval(0) is trivial, since it has empty domain.
Claim: ⊕ is commutative and associative, and 0 is the identity of ⊕ (up to isomorphism).
Proof: Trivial. □
Returning to our interpretation of morphisms as differences in agents' strength: The agent of C⊕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⊕D's agent as the weakest agent that is stronger than both C's agent and D's agent. Mathematically, this translates to ⊕ being the categorical coproduct in Chu(W).
Theorem: C0⊕C1 is the coproduct of C0 and C1 in Chu(W), and 0 is initial in Chu(W).
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,⋅) is a function from {} to A along with a function from E to {e}, 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 Agent(0) is empty. Thus 0 is initial.
Let Ci=(Ai,Ei,⋅i), and let C0⊕C1=(A0⊔A1,E0×E1,⋄). We want to show that there exist inclusion morphisms ι0:C0→C0⊕C1 and ι1:C1→C0⊕C1 such that for any Cartesian frame D=(B,F,⋆), and any pair of morphisms ϕ0:C0→D and ϕ1:C1→D, we have that there exists a unique morphism ϕ:C0⊕C1→D such that ϕ∘ι0=ϕ0 and ϕ∘ι1=ϕ1.
First, we need to specify ιi:(Ai,Ei,⋅i)→(A0⊔A1,E0×E1,⋄). We let ιi=(ji,ki), where ji:Ai→A0⊔A1 is just the the obvious inclusion of Ai into A0⊔A1, and ki:E0×E1→Ei is just the obvious projection. This is clearly a morphism.
Given ϕ0=(g0,h0):C0→D and ϕ1=(g1,h1):C1→D, we let ϕ=(g,h), where g:A0⊔A1→B is given by g(a)=gi(a) where i is such that a∈Ai, and h:F→E0×E1 is given by h(f)=(h0(f),h1(f)). This is a morphism because for all a∈A0⊔A1 and f∈F, we have
a⋄h(f)=a⋅ihi(f)=gi(a)⋆f=g(a)⋆f,where i is such that a∈Ai. It is clear from the definitions that ϕ∘ιi=ϕi.
Finally, we need to show the uniqueness of this ϕ. Let ϕ′=(g′,h′):C0⊕C1→D be a morphism such that ϕ′∘ιi=ϕi for both i=1,2. This means that g′(a)=gi(a) when a∈Ai, so g′(a)=g(a) for all a∈A0⊔A1. Similarly, h′(f) must project to h0(f) and h1(f), so
h′(f)=(h0(f),h1(f))=h(f)for all f∈F. 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 C=(A,E,⋅) and D=(B,F,⋆) over W, C&D is the Cartesian frame (A×B,E⊔F,⋄), where (a,b)⋄e=a⋅e if e∈E, and (a,b)⋄e=b⋆e if e∈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 Image(C) and Image(D) are disjoint, we can see this interpretation in the formalism by noting that Image(C)∈Obs(C&D)—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 C2 and D2 be as the example in §3,
C2=e0e1a0a1(w0w1w2w3) and D2=f0 f1 f2b0b1b2⎛⎜⎝w4w5w6w7w8w9w10w11w12⎞⎟⎠,
then C2&D2 is given by
C2&D2= e0 e1 f0 f1 f2 a0b0a0b1a0b2a1b0a1b1a1b2⎛⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜⎝w0w1w4w5w6w0w1w7w8w9w0w1w10w11w12w2w3w4w5w6w2w3w7w8w9w2w3w10w11w12⎞⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟⎠.
A second example: Suppose that we have two Cartesian frames, C3 and D3. C3 is a frame in which it's raining, and the agent chooses whether to carry an umbrella. D3 is a frame in which it's sunny, and the agent chooses whether to carry an umbrella.
C3=run(urnr) and D3=sun(usns)
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,
rsuu=unn=nun=u↔rnu=u↔s⎛⎜ ⎜ ⎜⎝urusnrnsurnsnrus⎞⎟ ⎟ ⎟⎠.
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 ⊤=({a},{},⋅), where Agent(⊤) is a singleton, Env(⊤) is the empty set, and Eval(⊤) 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: C&D=(C∗⊕D∗)∗, ⊤=0∗, C⊕D=(C∗&D∗)∗, and 0=⊤∗.
Proof: Trivial. □
In other words, ⊕ and & are De Morgan dual with respect to −∗.
In the same way that we interpreted C⊕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: C0&C1 is the product of C and D in Chu(W), and ⊤ is terminal in Chu(W).
Proof: Since ⊕ is the coproduct in Chu(W), it is the product in Chu(W)op. Since −∗ is an isomorphism between Chu(W) and Chu(W)op, we can take a product in Chu(W) of C0 and C1 by sending them to Chu(W)op via this isomorphism, taking a product, and sending them back. Thus (C∗0⊕C∗1)∗=C0&C1 is the product in Chu(W) of C0 and C1.
Similarly, since 0 is initial in Chu(W), it is terminal in Chu(W)op. Thus, 0∗=⊤ is terminal in Chu(W). □
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 AB normally represents B→A, 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 C⊥ to represent ⊥⊸C, but it doesn't. Worse still, C∗ does happen to be equivalent to C⊸⊥, and this will be an important fact to understand. To minimize confusion, we instead use the common notation −∗ for dual. ↩