Biextensional Equivalence

[Scott Garrabrant]

This is the third post in the Cartesian frames sequence. Read the first post here.

This post will introduce the standard equivalence relations we’ll be using for Cartesian frames. Our primary interest will be in homotopy equivalence, which will allow us to classify frames according to their agents’ and environments’ effect on possible worlds.

1. Isomorphism

Before defining homotopy equivalence, I want to define isomorphism between Cartesian frames.

Definition: A morphism $(g,h):C\to D$ is an isomorphism if both $g$ and $h$ are bijective. If there is an isomorphism between $C$ and $D$, we say $C\cong D$.

Claim: $\cong$ is an equivalence relation.

Proof: Reflexivity is trivial because the identity is an isomorphism. For symmetry, we have that if $(g,h)$ is an isomorphism from $C$ to $D$, then $(g^{-1},h^{-1})$ is an isomorphism from $D$ to $C$. Transitivity follows from the fact that bijection is transitive. $\square$

Claim: $C\cong D$ if and only if there is a pair of morphisms $\varphi :C\to D$ and $\psi :D\to C$ that compose to the identity morphism in both orders.

Proof: If $C\cong D$, we have $(g,h):C\to D$ with both $g$ and $h$ bijective, and we can take $\varphi =(g,h)$ and $\psi =(g^{-1},h^{-1})$.

Conversely, if $(g_1,h_1)\circ (g_0,h_0)$ is the identity morphism on $C=(A,E,\cdot )$, then $g_1\circ g_0$ is the identity on $A$, so $g_0$ must be injective. Similarly, $h_0\circ h_1$ is the identity on $E$, so $h_0$ must be surjective. Surjectivity of $g_0$ and injectivity of $h_0$ follow similarly from the fact that $(g_0,h_0)\circ (g_1,h_1)$ is the identity on $D$. $\square$

Isomorphism is pretty intuitive. It is basically saying that it doesn’t matter what the possible agents and possible environments are, other than how they interact with the evaluation function.

We will basically always be working up to at least isomorphism. For example, in the last post (“Additive Operations on Cartesian Frames”), we noted that $\oplus$ and $\&$ are commutative and associative up to isomorphism.

2. Homotopy Equivalence

2.1. Homotopic Morphisms

Our initial definition of homotopy equivalence will be devoid of interpretation, but the meaning will become clear later.

We say that two morphisms from $C$ to $D$ are homotopic if you can take the first function from the first morphism and the second function from the second morphism, and the resulting object is still a morphism.

Definition: Two morphisms $(g_0,h_0),(g_1,h_1):C\to D$ with the same source and target are called homotopic if $(g_0,h_1)$ is also a morphism.

Note that the mere existence of two morphisms from $C$ to $D$ doesn’t entail that those morphisms are homotopic. Consider the frame $C_0=(A,E,\cdot )$ given by

$C_0=\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}_1& w_0\\ w_0& w_1\end{array}\right)\end{array}$.

There are two morphisms from $C_0$ to itself: the identity morphism $({\text{id}}_A,{\text{id}}_E):C_0\to C_0$, and a morphism $(g,h):C_0\to C_0$ that flips $C_0$’s rows and columns, sending $a_0$ to $a_1$, $a_1$ to $a_0$, $e_0$ to $e_1$, and $e_1$ to $e_0$. These two morphisms are not homotopic, because neither $({\text{id}}_A,h)$ nor $(g,{\text{id}}_E)$ is a morphism.

Being homotopic is an equivalence relation on morphisms. (As such, in the above example it would have been superfluous to demonstrate that both $({\text{id}}_A,h)$ and $(g,{\text{id}}_E)$ aren’t morphisms.)

Claim: Homotopic is an equivalence relation.

Proof: Let $(g_i,h_i):(A,E,\cdot )\to (B,F,\star )$.

Reflexivity is trivial. For symmetry, we want to show that if $(g_0,h_0)$, $(g_1,h_1)$, and $(g_0,h_1)$ are all morphisms, then so is $(g_1,h_0)$. Indeed, for all $a\in A$ and $f\in F$,

$$\begin{array}{cc}{g}_1\left(a\right)\star f& =a\cdot h_1\left(f\right)\\ & =g_0\left(a\right)\star f\\ & =a\cdot h_0\left(f\right).\end{array}$$

For transitivity, we want to show that if $(g_0,h_0)$, $(g_0,h_1)$, $(g_1,h_1)$, $(g_1,h_2)$, and $(g_2,h_2)$ are all morphisms, then so is $(g_0,h_2)$. Indeed, for all $a\in A$ and $f\in F$,

$$\begin{array}{cc}{g}_0\left(a\right)\star f& =a\cdot h_1\left(f\right)\\ & =g_1\left(a\right)\star f\\ & =a\cdot h_2\left(f\right).\end{array}$$

$\square$

Being homotopic is also respected by composition.

Claim: If ${\varphi }_0:C_0\to C_1$ is homotopic to ${\varphi }_1:C_0\to C_1$, and ${\psi }_0:C_1\to C_2$ is homotopic to ${\psi }_0:C_1\to C_2$, then ${\psi }_0\circ {\varphi }_0$ is homotopic to ${\psi }_1\circ {\varphi }_1$.

Proof: Let $C_i=(A_i,E_i,{\cdot }_i)$, let ${\varphi }_i=(g_i,h_i)$, and let ${\psi }_i=(j_i,k_i)$. We want to show that $(j_0\circ g_0,h_1\circ k_1)$ is a morphism. Indeed, since $(g_0,h_1)$ and $(j_0,k_1)$ are morphisms,

$$\begin{array}{cc}{j}_0\left(g_0\right(a\left)\right){\cdot }_{2}f& =g_0\left(a\right){\cdot }_1{k}_1\left(f\right)\\ & =a{\cdot }_0{h}_1\left(k_1\right(f\left)\right).\end{array}$$

$\square$

Next, we define when two Cartesian frames are homotopy equivalent in the standard way.

2.2. Homotopy Equivalence

Homotopy equivalence relies on the existence of morphisms between $C$ and $D$ that we can compose in either order and end up with something that is homotopic to the identity morphism.

Definition: $C$ is homotopy equivalent to $D$, written $C\simeq D$, if there exists a pair of morphisms $\varphi :C\to D$ and $\psi :D\to C$ such that $\psi \circ \varphi$ is homotopic to the identity on $C$ and $\varphi \circ \psi$ is homotopic to the identity on $D$.

Claim: $\simeq$ is an equivalence relation.

Proof: Reflexivity is trivial, by taking $\psi =\varphi$ to be the identity. Symmetry is also trivial by swapping $\varphi$ and $\psi$.

For transitivity, assume that for $i=0,1$, we have ${\varphi }_i:C_i\to C_{i+1}$ and ${\psi }_i:C_{i+1}\to C_i$ such that ${\varphi }_i\circ {\psi }_i$ and ${\psi }_i\circ {\varphi }_i$ are homotopic to the identity. It suffices to show that ${\varphi }_0\circ {\varphi }_1\circ {\psi }_1\circ {\psi }_0$ and ${\psi }_1\circ {\psi }_0\circ {\varphi }_0\circ {\varphi }_1$ are both homotopic to the identity. In both cases, since composition respects what is homotopic, we have that the inner pair of morphisms cancels, and then the outer pair of morphisms cancels. $\square$

Note that homotopy equivalence is weaker than isomorphism.

Claim: If $C\cong D$, then $C\simeq D$.

Proof: Trivial. $\square$

We now have the homotopy equivalence relation on Cartesian frames, but no real philosophical interpretation. To understand the meaning of $\simeq$, we will first need to define biextensional collapse.

3. Biextensional Equivalence

3.1. Biextensionality

Definition: A Cartesian frame $C=(A,E,\cdot )$ is called biextensional if whenever $a_0,a_1\in A$ are such that $a_0\cdot e=a_1\cdot e$, for all $e\in E$, we have $a_0=a_1$, and whenever $e_0,e_1\in E$ are such that $a\cdot e_0=a\cdot e_1$, for all $a\in A$, we have $e_0=e_1$.

This is basically saying that a Cartesian frame is biextensional if all of its possible agents and possible environments are distinct when viewed as functions from environment to world and functions from agent to world respectively. The agent doesn’t have two options that invariably produce the same outcomes as each other, nor does the environment.

Viewed as a matrix, $C$ is biextensional if all of its rows and columns are distinct.

We have the following lemma that hints at the relationship between biextensionality and homotopy equivalence.

Lemma: Let $C$ and $D$ be biextensional Cartesian frames. Then, $C\simeq D$ if and only if $C\cong D$.

Proof: The “if” direction is trivial. For the “only if” direction, let $C=(A,E,\cdot )$ and $D=(B,F,\star )$ be two biextensional Cartesian frames, and let $C\simeq D$. Thus, there is a pair of morphisms $(g,h):C\to D$ and $(j,k):D\to C$ such that $(j\circ g,h\circ k)$ is homotopic to the identity on $C$, and $(g\circ j,k\circ h)$ is homotopic to the identity on $D$. Thus $(j\circ g,{\text{id}}_E)$ and $(g\circ j,{\text{id}}_F)$ are both morphisms, where ${\text{id}}_S$ is the identity on the set $S$. This means that $j\left(g\right(a\left)\right)\cdot e=a\cdot e$ for all $a$ and $e$, which since $C$ is biextensional implies that $j\circ g$ is the identity on $A$. Similarly, since $(g\circ j,{\text{id}}_F)$ is a morphism, we have that $g\circ j$ is the identity on $B$. Thus $g:A\to B$ is a bijection.

By the symmetry of homotopic, we also have that $({\text{id}}_A,k\circ h)$ and $({\text{id}}_B,h\circ k)$, which similarly gives us that $k\circ h$ is the identity on $E$ and $h\circ k$ is the identity of $F$, so $h:F\to E$ is a bijection. Thus, $C\cong D$. $\square$

Thus, we now understand how to interpret homotopy equivalence for biextensional Cartesian frames: it is equivalent to isomorphism.

To understand homotopy equivalence in general, we will first show how to collapse any Cartesian frame into a biextensional one.

3.2. Biextensional Collapse

Given a Cartesian frame $C=(A,E,\cdot )$, we can define an equivalence relation on $A$ that says two possible agents are equivalent if they implement the same function from $E$ to $W$; and we can similarly say that two elements of $E$ are equivalent if they implement the same function from $A$ to $W$.

Definition: Given a Cartesian frame $C=(A,E,\cdot )$, for $a_0,a_1\in A$, we say $a_0\sim a_1$ if $a_0\cdot e=a_1\cdot e$ for all $e\in E$. For $e_0,e_1\in E$, we say that $e_0\sim e_1$ if $a\cdot e_0=a\cdot e_1$ for all $a\in A$.

Claim: $\sim$ is an equivalence relation on $A$ and on $E$ .

Proof: Trivial. $\square$

Definition: Given a Cartesian frame $C=(A,E,\cdot )$, for $a\in A$, let $\hat{a}$ denote the equivalence class of $a$ up to $\sim$. Let $\hat{A}$ denote the set of equivalence classes of $\sim$ in $A$. Similarly, for $e\in E$, let $\hat{e}$ denote the equivalence class of $e$ up to $\sim$, and let $\hat{E}$ denote the set of equivalence classes of $\sim$ in $E$.

Definition: Given a Cartesian frame $C=(A,E,\cdot )$, the biextensional collapse of $C$, denoted $\hat{C}$, is the Cartesian frame $(\hat{A},\hat{E},\hat{\cdot })$, where $\hat{a}\hat{\cdot }\hat{e}=a\cdot e$.

Claim: $\hat{C}$ is well-defined.

Proof: We need to show that $\hat{\cdot }$ is well defined, meaning we need to show that for all $a_0\sim a_1$ and $e_0\sim e_1$, we have that $a_0\cdot e_0=a_1\cdot e_1$. This is immediate from the definition of $\sim$. $\square$

Viewed as a matrix, $\hat{C}$ is basically formed from $C$ by deleting any duplicate rows and any duplicate columns. It doesn’t matter whether you delete duplicate rows or duplicate columns first. After doing both, you will end up with a matrix with no duplicates.

Claim: $\hat{C}$ is biextensional for all Cartesian frames $C$.

Proof: Let $C=(A,E,\cdot )$. We want to show that for all $\widehat{a_0}\ne \widehat{a_1}\in \hat{A}$, there exists an $\hat{e}\in \hat{E}$ such that $\widehat{a_0}\hat{\cdot }\hat{e}\ne \widehat{a_1}\hat{\cdot }\hat{e}$. Indeed, since $\widehat{a_0}\ne \widehat{a_1}$, we have that $a_0\nsim a_1$, so there exists an $e\in E$ such that $a_0\cdot e\ne a_1\cdot e$, which gives us that $\widehat{a_0}\hat{\cdot }\hat{e}\ne \widehat{a_1}\hat{\cdot }\hat{e}$. Similarly, for all $\widehat{e_0}\ne \widehat{e_1}\in \hat{E}$, there exists an $\hat{e}\in \hat{E}$ such that $\hat{a}\hat{\cdot }\widehat{e_0}\ne \hat{a}\hat{\cdot }\widehat{e_1}$. $\square$

Claim: $C$ is biextensional if and only if $C\cong \hat{C}$.

Proof: If $C$ is biextensional, then all equivalence classes up to $\sim$ on both $A$ and $E$ are singletons. Thus, the morphism $(g,h):C\to \hat{C}$ given by $g\left(a\right)=\hat{a}$ and $h\left(\hat{e}\right)=e$ is well-defined, and both $g$ and $h$ are bijective, so $C\cong \hat{C}$.

Conversely, if $C\cong \hat{C}$$,$ then $C$ is isomorphic to a biextensional Cartesian frame, and since biextensionality is clearly preserved by isomorphism, $C$ is also biextensional. $\square$

3.3. Biextensional Equivalence

We can now (finally) use biextensional collapse to give an intuitive meaning to homotopy equivalence.

Claim: $C\simeq D$ if and only if $\hat{C}\cong \hat{D}$.

Proof: It suffices to show that $C\simeq \hat{C}$ for all Cartesian frames $C$. Then, we will have that if $C\simeq D$, then $\hat{C}\simeq C\simeq D\simeq \hat{D}$. Since homotopy equivalence is the same as isomorphism on biextensional Cartesian frames, this gives $\hat{C}\cong \hat{D}$. And conversely, if $\hat{C}\cong \hat{D}$ then $C\simeq \hat{C}\cong \hat{D}\simeq D$, so $C\simeq D$.

Let $C=(A,E,\cdot )$. We want to show that $C\simeq \hat{C}$. We do this by constructing a pair of morphisms $(g,h):C\to \hat{C}$, and $(j,k):\hat{C}\to C$. We will define $g:A\to \hat{A}$ by $a\mapsto \hat{a}$, and $k:E\to \hat{E}$ by $e\mapsto \hat{e}$. For $h:\hat{E}\to E$, and $j:\hat{A}\to A$, we can send each equivalence class to any one member of that class. The choice does not matter.

Now, we want to show that $(g\circ j,k\circ h)$ is homotopic to the identity on $\hat{C}$, and that $(j\circ g,h\circ k)$ is homotopic to the identity on $C$. The first case is trivial, since $g\circ j$ and $k\circ h$ are the identity on $\hat{A}$ and $\hat{E}$ respectively.$j\circ g$ and $h\circ k$ need not be the identity on $A$ and $E$, but $j\left(g\right(a\left)\right)\sim a$ and $h\left(k\right(e\left)\right)\sim e$ for all $a\in A$ and $e\in E$. To show that $(j\circ g,h\circ k)$ is homotopic to the identity on $C$, we just need to show that $(j\circ g,{\text{id}}_E)$ is a morphism, where ${\text{id}}_E$ is the identity on $E$. However, this just means that $j\left(g\right(a\left)\right)\cdot e=a\cdot e$ for all $a\in A$ and $e\in E$, which follows from the fact that $j\left(g\right(a\left)\right)\sim a$. $\square$

We now have that two Cartesian frames are homotopy equivalent if and only if their biextensional collapses are isomorphic. Thus, when $C$ and $D$ are homotopy equivalent, we will also call them biextensionally equivalent.

Definition: We say $C$ and $D$ are biextensionally equivalent if $C\simeq D$.

When working up to biextensional equivalence, we are basically saying that we are ignoring any multiplicity in the space of possible worlds and possible environments.

Claim: Each biextensional equivalence class contains a unique biextensional Cartesian frame.

Proof: Each biextensional equivalence class has at least one element, $C$, and $\hat{C}$ is in the same equivalence class as $C$ and is biextensional, so there must be at least one biextensional Cartesian frame in the class. If there were two biextensional Cartesian frames, they would have to be isomorphic, because isomorphic is equivalent to biextensional equivalence on biextensional Cartesian frames. $\square$

From my perspective, the value of this equivalence relation is that it lets us be less realist about possible agents and possible environments, and instead just care about differences between possible worlds.

This fits well with our general approach in this sequence. Cartesian frames are particular ways of looking at the world and mentally carving it up into an agent component and an environment component, but we allow many different carvings, and we do not give any one carving privileged status as the “true” carving. Thus, we put less weight on our conception of the agent and environment, and more weight on the worlds themselves.

Giving less realism to possible agents/​environments also fits with the fact that “worlds” may include details about the agent and environment, “possible agents” may specify features of the agent beyond its “actions,” and so on.

Imagine an agent with two unrelated choices: which color to think about (green $\text{G}$, or red $\text{R}$) and whether to go for a walk or stay home ($\text{W}$ or $\text{H}$). This yields the possible agents $A=\{\text{GH},\text{GW},\text{RH},\text{RW}\}$. The environment either is safe or has bears: $E=\{\text{S},\text{B}\}$. If we represent this scenario with the Cartesian frame

$C_0=\begin{array}{cc}& \begin{array}{cc}\text{S}& \text{B}\end{array}\\ \begin{array}{c}\text{GH}\\ \text{GW}\\ \text{RH}\\ \text{RW}\end{array}& \left(\begin{array}{cc}{w}_0& w_1\\ w_2& w_3\\ w_4& w_5\\ w_6& w_7\end{array}\right)\end{array}$,

then the possible worlds $w_0$ and $w_4$ differ only in which thought the agent is thinking; likewise $w_1$ and $w_5$, etc.

We could have instead described a frame

$C_1=\begin{array}{cc}& \begin{array}{cc}\text{S}& \text{B}\end{array}\\ \begin{array}{c}\text{GH}\\ \text{GW}\\ \text{RH}\\ \text{RW}\end{array}& \left(\begin{array}{cc}{w}_8& w_9\\ w_{10}& w_{11}\\ w_8& w_9\\ w_{10}& w_{11}\end{array}\right)\end{array}$,

in which case we would not be treating the agent’s thoughts as a relevant difference between possible worlds.¹ But we have the option of fully representing “agent-internal” properties using possible worlds, just the same as “environment-internal” properties. As such, we don’t need to separately reify possible agents or possible environments.

3.4. Example

One reason there are two definitions here is because the homotopy definition is easier to work with categorically, while the biextensionality definition is easier to work with directly with matrices.

Let $C_0$ and $C_1$ be the Cartesian frames given by:

$C_0\cong \left(\begin{array}{ccc}{w}_0& w_1& w_1\\ w_2& w_3& w_3\\ w_0& w_1& w_1\end{array}\right)$ and $C_1\cong \left(\begin{array}{ccc}{w}_2& w_3& w_2\\ w_0& w_1& w_0\\ w_2& w_3& w_2\end{array}\right)$.

Note that when working up to isomorphism, there is no need to label the rows or columns.

We can then see that $C_0\simeq C_1$ because

${\hat{C}}_0\cong {\hat{C}}_1\cong \left(\begin{array}{cc}{w}_0& w_1\\ w_2& w_3\end{array}\right)$.

To verify the equivalence using the the homotopy definition would be far more tedious.

3.5. Relationship to Additive Operations

Since we will often want to work with Cartesian frames up to biextensional equivalence, it will be helpful to know that all of our additive operations respect biextensional equivalence.

Claim: If $C_0\simeq C_1$ and $D_0\simeq D_1$, then $C_0^{\ast }\simeq C_1^{\ast }$, $C_0\oplus D_0\simeq C_1\oplus D_1$, and $C_0\&D_0\simeq C_1\&D_1$.

Proof: It is clear from the definition of biextensional collapse that $\widehat{-}$ commutes with ${-}^{\ast }$. Thus since $\widehat{C_0}\cong \widehat{C_1}$, we have $\widehat{C_0^{\ast }}\cong \widehat{C_1^{\ast }}$, so $C_0^{\ast }\simeq C_1^{\ast }$.

For the rest, it suffices to show that if $C_0\simeq C_1$, then $C_0\oplus D\simeq C_1\oplus D$. Then, since $\oplus$ is symmetric up to isomorphism, we have

$$\begin{array}{cc}{C}_0\oplus D_0& \simeq C_1\oplus D_0\\ & \cong D_0\oplus C_1\\ & \simeq D_1\oplus C_1\\ & \cong C_1\oplus D_1,\end{array}$$

and using the fact that $\oplus$ and $\&$ are De Morgan dual, we have

$$\begin{array}{cc}{C}_0\&D_0& \cong (C_0^{\ast }\oplus D_0^{\ast }{)}^{\ast }\\ & \simeq (C_1^{\ast }\oplus D_1^{\ast }{)}^{\ast }\\ & \cong C_1\&D_1.\end{array}$$

We will use the homotopy equivalence definition. Let $C_i=(A_i,E_i,{\cdot }_i)$ and let $D=(B,F,\star )$. Let $(g_0,h_0):C_0\to C_1$ and $(g_1,h_1):C_1\to C_0$ compose to something homotopic to the identity in both orders. We want to construct a $(g_0^{\prime },h_0^{\prime }):C_0\oplus D\to C_1\oplus D$ and $(g_1^{\prime },h_1^{\prime }):C_1\oplus D\to C_0\oplus D$, that similarly compose to something homotopic to the identity in both orders. We will take $g_i^{\prime }:A_i\bigsqcup B\to A_{1-i}\bigsqcup B$ to be given by $g_i^{\prime }\left(a\right)=g_i\left(a\right)$ if $a\in A_i$, and $g_i^{\prime }\left(a\right)=a$ if $a\in B$. Similarly, we will take $h_i^{\prime }:E_{1-i}\times F\to E_i\times F$ to be given by $h_i^{\prime }(e,f)=\left(h_i\right(e),f)$.

Without loss of generality, it suffices to show that $(g_0^{\prime },h_0^{\prime })$ is a morphism and that $(g_1^{\prime },h_1^{\prime })\circ (g_0^{\prime },h_0^{\prime })$ is homotopic to the identity on $C_0\oplus D$. The fact that $(g_1^{\prime },h_1^{\prime })$ is a morphism and $(g_0^{\prime },h_0^{\prime })\circ (g_1^{\prime },h_1^{\prime })$ is homotopic to the identity will follow symmetrically. Let ${\diamond }_i=\text{Eval}(C_i\oplus D)$.

To show that $(g_0^{\prime },h_0^{\prime })$ is a morphism, observe that for all $a\in A_0$ and $(e,f)\in E_1\times F$, we have

$$\begin{array}{cc}{g}_0^{\prime }\left(a\right){\diamond }_1(e,f)& =g_0\left(a\right){\cdot }_{1}e\\ & =a{\cdot }_0{h}_0\left(e\right)\\ & =a{\diamond }_0\left(h_0\right(e),f)\\ & =a{\diamond }_0{h}_0^{\prime }(e,f).\end{array}$$

Similarly, for all $a\in B$ and $(e,f)\in E_1\times F$, we have

$$\begin{array}{cc}{g}_0^{\prime }\left(a\right){\diamond }_1(e,f)& =a\star f\\ & =a{\diamond }_0\left(h_0\right(e),f)\\ & =a{\diamond }_0{h}_0^{\prime }(e,f).\end{array}$$

To show that $(g_1^{\prime },h_1^{\prime })\circ (g_0^{\prime },h_0^{\prime })$ is homotopic to the identity on $C_0\oplus D$, we just need that for all $a\in A_0\bigsqcup B$ and all $(e,f)\in E_0\times F$, we have $a{\diamond }_0(e,f)=g_1^{\prime }\left(g_0^{\prime }\right(a\left)\right){\diamond }_0(e,f)$. Indeed, if $a\in B$, then $a=g_1^{\prime }\left(g_0^{\prime }\right(a\left)\right)$, and if $a\in A_0$, then

$$\begin{array}{cc}a{\diamond }_0(e,f)& =a{\cdot }_{0}e\\ & =g_1\left(g_0\right(a\left)\right){\cdot }_{0}e\\ & =g_1^{\prime }\left(g_0^{\prime }\right(a\left)\right){\diamond }_0(e,f).\end{array}$$

$\square$

Image is also clearly preserved by biextensional equivalence.

Claim: If $C\simeq D$, then $\text{Image}\left(C\right)=\text{Image}\left(D\right)$.

Proof: Trivial from the biextensional collapse definition. $\square$

4. Some Small Cartesian Frames

We will now classify all biextensional Cartesian frames (and thus biextensional equivalence classes of Cartesian frames) in which the agent’s size is at most one and/​or the environment’s size is at most one.

Definition: $\text{null}$ is the Cartesian frame $\left(\right\{\},\{\},\cdot )$ with empty agent, empty environment, and empty evaluation function.

If you have an empty Cartesian frame—one with no image, no elements of $W$—then it must be biextensionally equivalent to either $\text{null}$, $0$, or $\top$.

Claim: If $|\text{Agent}\left(C\right)|=0$ and $|\text{Env}\left(C\right)|\ne 0$, then $C\simeq 0$. If $|\text{Env}\left(C\right)|=0$ and $|\text{Agent}\left(C\right)|\ne 0$, then $C\simeq \top$. If $|\text{Agent}\left(C\right)|=|\text{Env}\left(C\right)|=0$, then $C\simeq \text{null}$.

Proof: If $|\text{Agent}\left(C\right)|=0$ and $|\text{Env}\left(C\right)|\ne 0$, then all environments are equivalent up to $\sim ,$ so $\hat{C}$ has one possible environment and no possible agents, so $\hat{C}\cong 0$, so $C\simeq 0$. Similarly, if $|\text{Env}\left(C\right)|=0$ and $|\text{Agent}\left(C\right)|\ne 0$, all agents are equivalent up to $\sim$, so $\hat{C}\cong \top$ and $C\simeq \top$. If $|\text{Agent}\left(C\right)|=|\text{Env}\left(C\right)|=0$, then $C$ is already equal to $\text{null}$. $\square$

Claim: The only three biextensional Cartesian frames $C$ with $\text{Image}\left(C\right)=\left\{\right\}$ are $0$, $\top$, and $\text{null}$.

Proof: A Cartesian frame has empty image if and only if it has empty agent or empty environment. All three of 0, $\top$, and $\text{null}$ are clearly biextensional, and any other Cartesian frame with empty image is biextensionally equivalent to one of them, and so cannot be biextensional. $\square$

We now understand all biextensional Cartesian frames with empty agent or empty environment. Let’s look at the case where either the agent or environment is a singleton.

$1_S$ is the biextensional Cartesian frame you get when the agent has only one option, and the frame’s image is some set of possible worlds $S$. Since $\text{Env}\left(1_S\right)$ will be in bijective correspondence with $S=\text{Image}\left(1_S\right)$ and the labels on $\text{Env}\left(1_S\right)$ don’t matter, we will identify $\text{Env}\left(1_S\right)$ with $S$.

Definition: Given $S\subseteq W$, $1_S$ is the Cartesian frame $1_S=\left(\right\{a\},S,\star )$, where $a\star s=s$ for all $s\in S$. $1$ is the Cartesian frame $1_W$.

We can think of $1_S$ as the perspective of a bystander who has no control, and is just observing which world the environment brings about.

${\perp }_S$ is the transpose of $1_S$, where the environment has only one option and the agent’s options are $S$. You can think of ${\perp }_S$ as a powerful agent facing no obstacles, beyond being constrained to $S$: it gets to choose exactly what world we’re in.

Definition: Given $S\subseteq W$, ${\perp }_S$ is the Cartesian frame ${\perp }_S=(S,\{e\},\star )$, where $s\star e=s$ for all $s\in S$. $\perp$ is the Cartesian frame ${\perp }_W$.

The names $1$ and $\perp$ will make more sense later, when we define multiplicative operations on Cartesian frames.²

We can think of $1$ as a powerless, all-knowing agent, and $1_S$ as $1$ with a promise from the environment that the world will be in $S$. Similarly, we can think of $\perp$ as an all-powerful agent, and ${\perp }_S$ as $\perp$ with a commitment to do $S$.

The class of frames where the agent has only one option, $1_S$, contains $1$ at one extreme (where $S=W$) and $\top$ at the other extreme (where $S=\left\{\right\}$). Meanwhile, the class of frames where the environment has only one option, ${\perp }_S$, contains $\perp$ at one extreme (where $S=W$) and $0$ at the other (where $S=\left\{\right\}$).

Claim: $1^{\ast }=\perp$, ${\perp }^{\ast }=1$, $1_S^{\ast }={\perp }_S$, ${\perp }_S^{\ast }=1_S,$ $1_{\left\{\right\}}=\top$, ${\perp }_{\left\{\right\}}=0$.

Proof: Trivial. $\square$

Claim: If $|\text{Agent}\left(C\right)|=1$, then $C\simeq 1_S$, where $S=\text{Image}\left(C\right)$. If $|\text{Env}\left(C\right)|=1$, then $C\simeq {\perp }_S$, where $S=\text{Image}\left(C\right)$.

Proof: If $\text{Agent}\left(C\right)=\left\{a\right\}$, then equivalence classes of environments are given by where they send $a$. There will be one such equivalence class for each $s\in \text{Image}\left(C\right)$, and it will send $a$ to $s$. Thus $\hat{C}=1_S$, so $C\simeq 1_S$. The $|\text{Env}\left(C\right)|=1$ case is the same with agent and environment swapped. $\square$

Now that we have built up language for talking about Cartesian frames categorically, we are ready to revisit controllables and observables and interpret them through the lens of category theory. This will be the focus of our next post.

Footnotes

1. Similarly, we could have decided that we don’t care about certain things about the environment. For example, if we only care whether there are bears in possible worlds where the agent went for a walk and might therefore encounter them, then we could construct a frame

$C_2=\begin{array}{cc}& \begin{array}{cc}\text{S}& \text{B}\end{array}\\ \begin{array}{c}\text{GH}\\ \text{GW}\\ \text{RH}\\ \text{RW}\end{array}& \left(\begin{array}{cc}{w}_{12}& w_{12}\\ w_{13}& w_{14}\\ w_{15}& w_{15}\\ w_{16}& w_{17}\end{array}\right)\end{array}$.

↩

2. Indeed, this section on small Cartesian frames would make more sense as part of our discussion of multiplicative operations on Cartesian frames; our motivation for discussing these objects will be provided there. I’m introducing these objects early because they will be useful in a few contexts before we get to multiplicative operations. ↩

[ESRogs]

Are the two frames labeled $C_0$ and $C_1$ in section 3.3 (with an agent that thinks about either red or green and walks or stays home, and an environment that’s safe or has bears) equivalent? (I would guess so, given the section that example was in, but didn’t see it stated explicitly.)

[Rob Bensinger]

They’re not equivalent. If two frames are ‘homotopy equivalent’ /​ ‘biextensionally equivalent’ (two names for the same thing, in Cartesian frames), it means that you can change one frame into the other (ignoring the labels of possible agents and environments, i.e., just looking at the possible worlds) by doing some combination of ‘make a copy of a row’, ‘make a copy of a column’, ‘delete a row that’s a copy of another row’, and/​or ‘delete a column that’s a copy of another column’.

The entries of $C_0$ and $C_1$ are totally different ($\text{Image}\left(C_0\right)=\{w_0,w_1,w_2,w_3,w_4,w_5,w_6,w_7\}$, while $\text{Image}\left(C_1\right)=\{w_8,w_9,w_{10},w_{11}\}$, before we even get into asking how those entries are organized in the matrices), so they can’t be biextensionally equivalent.

There is an important relationship between $C_0$ and $C_1$, which Scott will discuss later in the sequence. But the reason they’re brought up in this post is to make a more high-level point “here’s a reason we want to reify agents and environments less than worlds, which is part of why we’re interested in biextensional equivalence,” not to provide an example of biextensional equivalence.

[Rob Bensinger]

An example of frames that are biextensionally equivalent to $C_1$:

$\begin{array}{cc}& \left(\begin{array}{cc}{w}_8& w_9\\ w_{10}& w_{11}\\ w_8& w_9\\ w_{10}& w_{11}\end{array}\right)\end{array}\simeq \begin{array}{cc}& \left(\begin{array}{cc}{w}_8& w_9\\ w_{10}& w_{11}\\ w_8& w_9\end{array}\right)\end{array}\simeq \begin{array}{cc}& \left(\begin{array}{cc}{w}_8& w_9\\ w_{10}& w_{11}\\ w_{10}& w_{11}\end{array}\right)\end{array}\simeq \begin{array}{cc}& \left(\begin{array}{cc}{w}_8& w_9\\ w_{10}& w_{11}\end{array}\right)\end{array}$

… or any frame that enlarges one of those four frames by adding extra copies of any of the rows and/​or columns.

[ESRogs]

This is helpful. Thanks!

[Rob Bensinger]

Scott’s post explaining the relationship between $C_0$ and $C_1$ exists as of now: Functors and Coarse Worlds.

[Edouard Harris]

Really interesting!

I think there might be a minor typo in Section 2.2:

For transitivity, assume that for $i=1,2$

I think this should be $i=0,1$ based on the indexing in the rest of the paragraph.

[Scott Garrabrant]

Fixed. Thanks.

[MikkW]

$\cong$ in as equivalence relation

I presume this is supposed to be “is an”?

[Rob Bensinger]

Yep!

[Eigil Rischel]

Does the biextensional collapse satisfy a universal property? There doesn’t seem to be an obvious map either $C\to \hat{C}$ or $\hat{C}\to C$ (in each case one of the arrows is going the wrong way), but maybe there’s some other way to make it universal?

[Scott Garrabrant]

I think the right way to think about biextensional collapse categorically is as a reflector.

[Eigil Rischel]

But then shouldn’t there be a natural biextensional equivalence $C\to \hat{C}$? Suppose $C=(A,E,\star )$, and denote $\hat{C}=(\hat{A},\hat{E},\star )$. Then the map $A\to \hat{A}$ is clear enough, it’s simply the quotient map. But there’s not a unique map $\hat{E}\to E$ - any section of the quotient map will do, and it doesn’t seem we can make this choice naturally.

I think maybe the subcategory of just “agent-extensional” frames is reflective, and then the subcategory of “environment-extensional” frames is coreflective. And there’s a canonical (i.e natural) zig-zag $C\to (\hat{A},E,\star )\leftarrow \hat{C}$

[Scott Garrabrant]

You might be right, I am not sure.

It looks to me like it satisfies the definition on wikipedia, which does not require that the morphism $r_B$ is unique, only that it exists.