Sub-Sums and Sub-Tensors

This is the eighth post in the Cartesian frames sequence. Here, we define new versions of the sum and tensor of Cartesian frames that can delete spurious possible environments from the frame.

1. Motivating Examples

The sum of $C$ and $D$ is supposed to represent an agent that can do anything either $C$ or $D$ can do, while the tensor, $C \otimes D$ , is supposed to represent an agent that can do anything $C$ and $D$ can do working freely together on a team. However, sometimes these operations produce Cartesian frames with more environments than we would expect.

Consider two players, Alice and Bob, in a prisoner's dilemma. We will let $W = {0, 1, 2, 3}$ be the space of utilities for Alice. The Cartesian frame for Alice looks like

$C_{0} = (\begin{matrix} 2 & 0 3 & 1 \end{matrix})$ ,

where the top row represents Alice cooperating, and the left column represents Bob cooperating.

Let $C_{1} = (\begin{matrix} 2 & 0 \end{matrix})$ represent Alice committed to cooperating, and let $C_{2} = (\begin{matrix} 3 & 1 \end{matrix})$ represent Alice committed to defecting. Since the real Alice can either cooperate or defect, one might expect that Alice ( $C_{0}$ ) would equal the sum ( $C_{1} \oplus C_{2}$ ) of Alice cooperating with Alice defecting. However,

$C_{1} \oplus C_{2} = (\begin{matrix} 2 & 0 & 2 & 0 3 & 1 & 1 & 3 \end{matrix})$ .

The last two columns are spurious environments that represent Bob copying Alice's move, and Bob doing the opposite of Alice's move. However, since Bob cannot see Alice's move, Bob should not be able to implement these policies: Bob can only choose to cooperate or defect.

Next, consider a unilateralist's curse game where two players each have access to a button that destroys the Earth. If either player pushes the button, the Earth is destroyed. Otherwise, the Earth is not destroyed. $W = {0, 1}$ , where $0$ represents the world being destroyed and $1$ represents the world not being destroyed.

Here, both players have the Cartesian frame

$D_{1} = (\begin{matrix} 0 & 0 0 & 1 \end{matrix})$ ,

where the first row represents pressing the button, and the first column represents the other player pressing the button.

The two players together can be expressed with the Cartesian frame

$D_{2} = ⎛ ⎜ ⎜ ⎜ ⎝ \begin{matrix} 0001 \end{matrix} ⎞ ⎟ ⎟ ⎟ ⎠$ ,

where the rows in order represent: both players pressing the button; the first player pressing the button; the second player pressing the button; and neither player pressing the button.

One might expect that $D_{1} \otimes D_{1}$ would be $D_{2}$ , but in fact,

$D_{1} \otimes D_{1} = ⎛ ⎜ ⎜ ⎜ ⎝ \begin{matrix} 0 & 0 0 & 0 0 & 0 1 & 0 \end{matrix} ⎞ ⎟ ⎟ ⎟ ⎠$ .

The second possible environment, in which the earth is just destroyed regardless of what the players do, is spurious.

In both of the above examples, the spurious environments are only spurious because of our interpretation. In the prisoner's dilemma case, $C_{1} \oplus C_{2}$ would be correct if Alice and Bob were playing a modified dilemma where Bob can see Alice's choice. In the unilateralist's curse example, $D_{1} \otimes D_{1}$ would be correct if there were three people playing the game. The problem is that the $\oplus$ and $\otimes$ operations do not see our interpretation, and so include all possible environments.

2. Deleting Spurious Environments

We introduce two new concepts, called sub-sum and sub-tensor, which represents sum and tensor with some (but not too many) spurious environments removed.

Definition: Let $C = (A, E, \cdot)$ , and let $D = (B, F, ⋆)$ . A sub-sum of C and D is a Cartesian frame of the form $(A ⊔ B, X, ⋄)$ , where $X \subseteq Env (C \oplus D)$ and $⋄$ is $Eval (C \oplus D)$ restricted to $(A ⊔ B) \times X$ , such that $C ≃ (A, X, ⋄_{C})$ and $D ≃ (B, X, ⋄_{D})$ , where $⋄_{C}$ is $⋄$ restricted to $A \times X$ and $⋄_{D}$ is $⋄$ restricted to $B \times X$ . Let $C ⊞ D$ denote the set of all sub-sums of $C$ and $D$ .

Definition: Let $C = (A, E, \cdot)$ , and let $D = (B, F, ⋆)$ . A sub-tensor of $C$ and $D$ is a Cartesian frame of the form $(A \times B, X, ∙)$ , where $X \subseteq Env (C \otimes D)$ and $∙$ is $Eval (C \otimes D)$ restricted to $(A \times B) \times X$ , such that $C ≃ (A, B \times X, ∙_{C})$ and $D ≃ (B, A \times X, ∙_{D})$ , where $∙_{C}$ and $∙_{D}$ are given by $a ∙_{C} (b, x) = (a, b) ∙ x$ and $b ∙_{D} (a, x) = (a, b) ∙ x$ . Let $C ⊠ D$ denote the set of all sub-tensors of $C$ and $D$ .

Thus, we define $C ⊞ D$ and $C ⊠ D$ to be sets of Cartesian frames that can be obtained by deleting columns from from $C \oplus D$ and $C \otimes D$ , respectively, but we have an extra restriction to ensure that we do not delete too many columns.

We will discuss later how to interpret the extra restriction, but first let us go back to our above examples.

If $C_{1} = (\begin{matrix} 2 & 0 \end{matrix})$ and $C_{2} = (\begin{matrix} 3 & 1 \end{matrix})$ , then $C_{1} ⊞ C_{2}$ has 7 elements:

$(\begin{matrix} 2 & 0 & 2 & 0 3 & 1 & 1 & 3 \end{matrix}), (\begin{matrix} 2 & 0 & 2 3 & 1 & 1 \end{matrix}), (\begin{matrix} 2 & 0 & 0 3 & 1 & 3 \end{matrix}), (\begin{matrix} 2 & 2 & 0 3 & 1 & 3 \end{matrix}), (\begin{matrix} 0 & 2 & 0 1 & 1 & 3 \end{matrix}), (\begin{matrix} 2 & 0 3 & 1 \end{matrix}), (\begin{matrix} 2 & 0 1 & 3 \end{matrix})$

The 9 Cartesian frames that can be obtained by deleting columns from $C \oplus D$ that are not in $C_{1} ⊞ C_{2}$ are:

$(\begin{matrix} 2 & 2 3 & 1 \end{matrix}), (\begin{matrix} 2 & 0 3 & 3 \end{matrix}), (\begin{matrix} 0 & 2 1 & 1 \end{matrix}), (\begin{matrix} 0 & 0 1 & 3 \end{matrix}), (\begin{matrix} 23 \end{matrix}), (\begin{matrix} 01 \end{matrix}), (\begin{matrix} 21 \end{matrix}), (\begin{matrix} 03 \end{matrix}), (\begin{matrix} \end{matrix})$ .

The Cartesian frames above in $C_{1} ⊞ C_{2}$ are exactly those with all four entries, $0$ , $1$ , $2$ , and $3$ . This is because the extra restriction to be in $C_{1} ⊞ C_{2}$ is exactly that if you delete the bottom row, you get an object biextensionally equivalent to $(\begin{matrix} 2 & 0 \end{matrix})$ , and if you delete the top row, you get an object biextensionally equivalent to $(\begin{matrix} 3 & 1 \end{matrix})$ .

Similarly, from the unilateralist's curse example,

$D_{1} ⊠ D_{1} = ⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ ⎛ ⎜ ⎜ ⎜ ⎝ \begin{matrix} 0001 \end{matrix} ⎞ ⎟ ⎟ ⎟ ⎠, ⎛ ⎜ ⎜ ⎜ ⎝ \begin{matrix} 0 & 0 0 & 0 0 & 0 1 & 0 \end{matrix} ⎞ ⎟ ⎟ ⎟ ⎠ ⎫ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎭$ .

It is easy to see that there are no other Cartesian frames in $D_{1} ⊠ D_{1}$ , since there are only four subsets of the two element environment of $D_{1} \otimes D_{1}$ , and the Cartesian frames corresponding to the other two subsets do not have 1 in their image, so we cannot build anything biextensionally equivalent to $D_{1}$ out of them.

Conversely, let $C = (A, E, \cdot)$ and $D = (B, F, ⋆)$ both be $D_{1}$ , and notice that if

$(A \times B, X, ∙) = ⎛ ⎜ ⎜ ⎜ ⎝ \begin{matrix} 0001 \end{matrix} ⎞ ⎟ ⎟ ⎟ ⎠$ ,

then $(A, B \times X, ∙_{C})$ and $(B, A \times X, ∙_{D})$ are both two-by-two matrices with a single $1$ entry and three $0$ entries, and so must be isomorphic to $D_{1}$ . Similarly, if

$(A \times B, X, ∙) = ⎛ ⎜ ⎜ ⎜ ⎝ \begin{matrix} 0 & 0 0 & 0 0 & 0 1 & 0 \end{matrix} ⎞ ⎟ ⎟ ⎟ ⎠$ ,

then $(A, B \times X, ∙_{C})$ and $(B, A \times X, ∙_{D})$ are both two-by-four matrices with a single $1$ entry and seven $0$ entries, and so must by biextensionally equivalent to $D_{1}$ .

3. Properties of Sub-Sums and Sub-Tensors

3.1. Sub-Sums and Sub-Tensors Are Commutative

Claim: For any Cartesian frames $C_{0}$ and $C_{1}$ , there is a bijection between $C_{0} ⊞ C_{1}$ and $C_{1} ⊞ C_{0}$ that preserves Cartesian frames up to isomorphism. Similarly, there is a bijection between $C_{0} ⊠ C_{1}$ and $C_{1} ⊠ C_{0}$ that preserves Cartesian frames up to isomorphism.

Proof: Trivial. $□$

3.2. Tensors Need Not Be Sub-Tensors

For any Cartesian frames $C$ and $D$ with nonempty environments, we have that $C \oplus D \in C ⊞ D$ . However, sometimes $C \otimes D \notin C ⊠ D$ . Indeed, sometimes $C ⊠ D = {}$ .

For example, if $C$ and $D$ both have nonempty image, but there are no morphisms from $C$ to $D^{*}$ , then $C \otimes D$ has no environments, and it is easy to see that $C ⊠ D$ must be empty.

3.3. Sub-Sums and Sub-Tensors Are Superagents

Claim: For any Cartesian frames $C_{0}$ and $C_{1}$ , and for any $D_{0} \in C_{0} ⊞ C_{1}$ , we have $C_{0} ◃ D_{0}$ and $C_{1} ◃ D_{0}$ . Similarly, for any $D_{1} \in C_{0} ⊠ C_{1}$ , we have $C_{0} ◃ D_{1}$ and $C_{1} ◃ D_{1}$ .

Proof: Let $C_{i} = (A_{i}, E_{i}, \cdot_{i})$ and $D_{i} = (B_{i}, F_{i}, ⋆_{i})$ . First, we show $C_{0} ◃ D_{0}$ using the currying definition of subagent. Observe $B_{0} = A_{0} ⊔ A_{1}$ . Consider the Cartesian frame $(A_{0}, {e}, ⋄)$ over $B_{0}$ , where $⋄$ is given by $a ⋄ e = a$ . Observe that the definition of sub-sum says that $C_{0} ≃ D_{0}^{\circ} (A_{0}, {e}, ⋄)$ , so $C_{0} ◃ D_{0}$ . Therefore, $C_{0} ◃ D_{0}$ , and by commutativity, we also have $C_{1} ◃ D_{0}$ .

Similarly, we show $C_{0} ◃ D_{1}$ using the currying definition of subagent. Observe that $B_{1} = A_{0} \times A_{1}$ . Consider the Cartesian frame $(A_{0}, A_{1}, ∙)$ over $B_{1}$ , where $∙$ is given by $a_{0} ∙ a_{1} = (a_{0}, a_{1})$ . Observe that the definition of sub-tensor says that $C_{0} ≃ D_{1}^{\circ} (A_{0}, A_{1}, ∙)$ . Therefore, $C_{0} ◃ D_{1}$ , and by commutativity, we also have $C_{1} ◃ D_{1}$ . $□$

Observe that in the above proof, the Cartesian frame over $B_{0}$ we constructed to show that sub-sums are superagents had a singleton environment, and the Cartesian frame over $B_{1}$ we constructed to show that sub-tensors are superagents had a surjective evaluation function. The relevance of this observation will become clear later.

3.4. Biextensional Equivalence

As we do with most of our definitions, we will now show that sub-sums and sub-tensors are well-defined up to biextensional equivalence.

Claim: Given two Cartesian frames over $W$ , $C_{0}$ and $C_{1}$ , and given any $D \in C_{0} ⊞ C_{1}$ , we have that for all $C_{0}^{'} ≃ C_{0}$ and $C_{1}^{'} ≃ C_{1}$ , there exists a $D^{'} ≃ D$ , with $D^{'} \in C_{0}^{'} ⊞ C_{1}^{'}$ .

Proof: Let $C_{0} = (A_{0}, E_{0}, \cdot_{0})$ , let $C_{1} = (A_{1}, E_{1}, \cdot_{1})$ , and let $D = (A_{0} ⊔ A_{1}, X, ⋆)$ be an element of $C_{0} ⊞ C_{1}$ , so $X \subseteq E_{0} \times E_{1}$ , and $a ⋆ (e_{0}, e_{1}) = a \cdot_{0} e_{0}$ if $a \in A_{0}$ , and $a ⋆ (e_{0}, e_{1}) = a \cdot_{1} e_{1}$ if $a \in A_{1}$ .

The fact that $D \in C_{0} ⊞ C_{1}$ tells us that for $i \in {0, 1}$ , $D_{i} ≃ C_{i}$ , where $D_{i} = (A_{i}, X, ⋆_{i})$ with $⋆_{i}$ given by $a ⋆_{0} (e_{0}, e_{1}) = a \cdot_{0} e_{0}$ and $a ⋆_{1} (e_{0}, e_{1}) = a \cdot_{0} e_{1}$ .

For $i \in {0, 1}$ , let $C_{i}^{'} = (A_{i}^{'}, E_{i}^{'}, \cdot_{i}^{'})$ satisfy $C_{i}^{'} ≃ C_{i}$ . Thus, there exist morphisms $(g_{i}, h_{i}) : C_{i} \to C_{i}^{'}$ , and $(g_{i}^{'}, h_{i}^{'}) : C_{i}^{'} \to C_{i}$ , such that $(g_{0}, h_{0}) \circ (g_{0}^{'}, h_{0}^{'})$ , $(g_{0}^{'}, h_{0}^{'}) \circ (g_{0}, h_{0})$ , $(g_{1}, h_{1}) \circ (g_{1}^{'}, h_{1}^{'})$ , and $(g_{1}^{'}, h_{1}^{'}) \circ (g_{1}, h_{1})$ are all homotopic to the identity.

We define a function $f : E_{0} \times E_{1} \to E_{0}^{'} \times E_{1}^{'}$ by $f (e_{0}, e_{1}) = (h_{0}^{'} (e_{0}), h_{1}^{'} (e_{1}))$ . Then, we define $X^{'} \subseteq E_{0}^{'} \times E_{1}^{'}$ by $X^{'} = {f (x) | x \in X}$ , and let $D^{'} = (A_{0}^{'} ⊔ A_{1}^{'}, X^{'}, ⋆^{'})$ , where $a ⋆^{'} (e_{0}, e_{1}) = a \cdot_{0}^{'} e_{0}$ if $a \in A_{0}^{'}$ , and $a ⋆^{'} (e_{0}, e_{1}) = a \cdot_{1}^{'} e_{1}$ if $a \in A_{1}^{'}$ . We need to show $D^{'} \in C_{0}^{'} ⊞ C_{1}^{'}$ , and that $D^{'} ≃ D$ .

To show that $D^{'} ≃ D$ , we will construct a pair of morphisms $(j, k) : D \to D^{'}$ and $(j^{'}, k^{'}) : D^{'} \to D$ that compose to something homotopic to the identity in both orders. We define $j : A_{0} ⊔ A_{1} \to A_{0}^{'} ⊔ A_{1}^{'}$ by $j (a) = g_{0} (a)$ if $a \in A_{0}$ , and $j (a) = g_{1} (a)$ if $a \in A_{1}$ . We similarly define $j^{'} : A_{0}^{'} ⊔ A_{1}^{'} \to A_{0} ⊔ A_{1}$ by $j^{'} (a) = g_{0}^{'} (a)$ if $a \in A_{0}^{'}$ , and $j^{'} (a) = g_{1}^{'} (a)$ if $a \in A_{1}^{'}$ . We define $k^{'} : X \to X^{'}$ by $k^{'} (x) = f (x)$ , which is clearly a function into $X^{'}$ , by the definition of $X^{'}$ . Further, $k^{'}$ is surjective, and thus has a right inverse. We choose $k : X^{'} \to X$ to be any right inverse to $k^{'}$ , so $f (k (x)) = x$ for all $x \in X^{'}$ .

To see that $(j^{'}, k^{'})$ is a morphism, observe that for $a \in A_{0}^{'} ⊔ A_{1}^{'}$ , and $(e_{0}, e_{1}) \in X$ , if $a \in A_{i}^{'},$ then

\begin{matrix} j^{'} (a) ⋆ (e_{0}, e_{1}) & = g_{i}^{'} (a) \cdot_{i} e_{i} = a \cdot_{i}^{'} h_{i}^{'} (e_{i}) = a ⋆^{'} (h_{0}^{'} (e_{0}), h_{1}^{'} (e_{1})) = a ⋆^{'} k^{'} (e_{0}, e_{1})) . \end{matrix}

To see that $(j, k)$ is a morphism, consider an arbitrary $a \in A_{0} ⊔ A_{1}$ and $(e_{0}^{'}, e_{1}^{'}) \in X^{'}$ , and let $(e_{0}, e_{1}) = k (e_{0}^{'}, e_{1}^{'})$ . Then, if $a \in A_{i}$ , we have

\begin{matrix} j (a) ⋆^{'} (e_{0}^{'}, e_{1}^{'}) & = j (a) ⋆^{'} f (e_{0}, e_{1}) = j (a) ⋆^{'} (h_{0}^{'} (e_{0}), h_{1}^{'} (e_{1})) = g_{i} (a) \cdot_{i}^{'} h_{i}^{'} (e_{i}) = g_{i}^{'} (g_{i} (a)) \cdot_{i} e_{i} = a \cdot_{i} e_{i} = a ⋆ (e_{0}, e_{1}) = a ⋆ k (e_{0}^{'}, e_{1}^{'}) . \end{matrix}

To see that $(j^{'}, k^{'}) \circ (j, k)$ is homotopic to the identity on $D$ , observe that for all $a \in A_{0} ⊔ A_{1}$ and $(e_{0}, e_{1}) \in X$ , we have that if $a \in A_{i}$ ,

\begin{matrix} j^{'} (j (a)) ⋆ (e_{0}, e_{1}) & = g_{i}^{'} (g_{i} (a)) \cdot_{i} e_{i} = a \cdot_{i} e_{i} = a ⋆ (e_{0}, e_{1}) . \end{matrix}

Similarly, to see that $(j, k) \circ (j^{'}, k^{'})$ is homotopic to the identity on $D^{'}$ , observe that for all $a \in A_{0}^{'} ⊔ A_{1}^{'}$ and $(e_{0}, e_{1}) \in X^{'}$ , we have that if $a \in A_{i}^{'}$ ,

\begin{matrix} j (j^{'} (a)) ⋆^{'} (e_{0}, e_{1}) & = g_{i} (g_{i}^{'} (a)) \cdot_{i}^{'} e_{i} = a \cdot_{i}^{'} e_{i} = a ⋆^{'} (e_{0}, e_{1}) . \end{matrix}

Thus, $D^{'} ≃ D$ .

To see $D^{'} \in C_{0}^{'} ⊞ C_{1}^{'}$ , we need to show that $D_{i}^{'} ≃ C_{i}^{'}$ , where $D_{i}^{'} = (A_{i}^{'}, X^{'}, ⋆_{i}^{'})$ with $⋆_{i}^{'}$ given by $a ⋆_{0}^{'} (e_{0}, e_{1}) = a \cdot_{0}^{'} e_{0}$ and $a ⋆_{1}^{'} (e_{0}, e_{1}) = a \cdot_{1}^{'} e_{1}$ . It suffices to show that $D_{i}^{'} ≃ D_{i}$ , since $D_{i} ≃ C_{i} ≃ C_{i}^{'}$ .

For $i \in {0, 1}$ , we construct morphisms $(j_{i}, k_{i}) : D_{i} \to D_{i}^{'}$ , and $(j_{i}^{'}, k_{i}^{'}) : D_{i}^{'} \to D_{i}$ . We define $j_{i} = g_{i}$ , $j_{i}^{'} = g_{i}^{'}$ , $k_{i} = k$ , and $k_{i}^{'} = k^{'}$ .

To see that $(j_{i}, k_{i})$ is a morphism, observe that for all $a \in A_{i}$ and $x \in X^{'}$ , we have

\begin{matrix} j_{i} (a) ⋆_{i}^{'} x & = g_{i} (a) ⋆_{i}^{'} x = j (a) ⋆^{'} x = a ⋆ k (x) = a ⋆_{i} k_{i} (x), \end{matrix}

and to see that $(j_{i}^{'}, k_{i}^{'})$ is a morphism, observe that for all $a \in A_{i}^{'}$ , and $x \in X$ , we have

\begin{matrix} j_{i}^{'} (a) ⋆_{i} x & = g_{i}^{'} (a) ⋆_{i} x = j^{'} (a) ⋆ x = a ⋆^{'} k^{'} (x) = a ⋆_{i}^{'} k_{i}^{'} (x) . \end{matrix}

To see $(j_{i}^{'}, k_{i}^{'}) \circ (j_{i}, k_{i})$ is homotopic to the identity on $D_{i}$ , observe that for all $a \in A_{i}$ and $x \in X$ , we have

\begin{matrix} j_{i}^{'} (j_{i} (a)) ⋆_{i} x & = g_{i}^{'} (g_{i} (a)) ⋆_{i} x = j^{'} (j (a)) ⋆ x = a ⋆ x = a ⋆_{i} x, \end{matrix}

and similarly, to show that $(j_{i}, k_{i}) \circ (j_{i}^{'}, k_{i}^{'})$ is homotopic to the identity on $D_{i}^{'}$ , observe that for all $a \in A_{i}^{'}$ and $x \in X^{'}$ , we have

\begin{matrix} j_{i} (j_{i}^{'} (a)) ⋆_{i}^{'} x & = g_{i} (g_{i}^{'} (a)) ⋆_{i}^{'} x = j (j^{'} (a)) ⋆^{'} x = a ⋆^{'} x = a ⋆_{i}^{'} x . \end{matrix}

Thus, we have that $D_{i}^{'} ≃ D_{i}$ , completing the proof. $□$

We have a similar result for sub-tensors, whose proof directly mirrors the proof for sub-sums:

Claim: Given two Cartesian frames over $W$ , $C_{0}$ and $C_{1}$ , and any $D \in C_{0} ⊠ C_{1}$ , we have that for all $C_{0}^{'} ≃ C_{0}$ and $C_{1}^{'} ≃ C_{1}$ , there exists a $D^{'} ≃ D$ , with $D^{'} \in C_{0}^{'} ⊠ C_{1}^{'}$ .

Proof: Let $C_{0} = (A_{0}, E_{0}, \cdot_{0})$ , let $C_{1} = (A_{1}, E_{1}, \cdot_{1})$ , and let $D = (A_{0} \times A_{1}, X, ⋆)$ be an element of $C_{0} ⊠ C_{1}$ , so $X \subseteq hom (C_{0}, C_{1}^{*})$ , and

\begin{matrix} (a, b) ⋆ (g, h) & = a \cdot_{0} h (b) = b \cdot_{1} g (a) . \end{matrix}

The fact that $D \in C_{0} ⊠ C_{1}$ tells us that for $i \in {0, 1}$ , $D_{i} ≃ C_{i}$ , where $D_{i} = (A_{i}, A_{1 - i} \times X, ⋆_{i})$ with $⋆_{i}$ given by

\begin{matrix} a ⋆_{0} (b, (g, h)) & = b ⋆_{1} (a, (g, h)) = (a, b) ⋆ (g, h) . \end{matrix}

We define a function $f : hom (C_{0}, {C_{1}}^{*}) \to hom (C_{0}^{'}, {C_{1}^{'}}^{*})$ by $f (g, h) = (h_{1}^{'}, g_{1}^{'}) \circ (g, h) \circ (g_{0}^{'}, h_{0}^{'})$ . This function is well-defined, since $(h_{1}^{'}, g_{1}^{'}) = (g_{1}^{'}, h_{1}^{'})^{*} \in hom (C_{1}^{*}, {C_{1}^{'}}^{*})$ and $(h_{0}^{'}, g_{0}^{'}) \in hom (C_{0}^{'}, C_{0})$ .

Then, we define $X^{'} \subseteq hom (C_{0}^{'}, {C_{1}^{'}}^{*})$ by $X^{'} = {f (g, h) | (g, h) \in X}$ , and let $D^{'} = (A_{0}^{'} \times A_{1}^{'}, X^{'}, ⋆^{'})$ , where

\begin{matrix} (a, b) ⋆^{'} (g, h) & = a \cdot_{0}^{'} h (b) = b \cdot_{1}^{'} g (a) . \end{matrix}

We need to show that $D^{'} \in C_{0}^{'} ⊠ C_{1}^{'}$ , and that $D^{'} ≃ D$ .

To show that $D^{'} ≃ D$ , we will construct a pair of morphisms $(j, k) : D \to D^{'}$ and $(j^{'}, k^{'}) : D^{'} \to D$ that compose to something homotopic to the identity in both orders. We define $j : A_{0} \times A_{1} \to A_{0}^{'} \times A_{1}^{'}$ by $j (a, b) = (g_{0} (a), g_{1} (b))$ , and we similarly define $j^{'} : A_{0}^{'} \times A_{1}^{'} \to A_{0} \times A_{1}$ by $j^{'} (a, b) = (g_{0}^{'} (a), g_{1}^{'} (b))$ . We define $k^{'} : X \to X^{'}$ by $k^{'} (x) = f (x)$ , which is clearly a function into $X^{'}$ , by the definition of $X^{'}$ . Further, $k^{'}$ is surjective, and thus has a right inverse. We choose $k : X^{'} \to X$ to be any right inverse to $k^{'}$ , so $f (k (x)) = x$ for all $x \in X^{'}$ .

To see $(j^{'}, k^{'})$ is a morphism, observe that for $(a, b) \in A_{0}^{'} \times A_{1}^{'}$ , and $(g, h) \in X$ , we have

\begin{matrix} j^{'} (a, b) ⋆ (g, h) & = (g_{0}^{'} (a), g_{1}^{'} (b)) ⋆ (g, h) = g_{1}^{'} (b) \cdot_{1} g (g_{0}^{'} (a)) = b \cdot_{1}^{'} h_{1}^{'} (g (g_{0}^{'} (a))) = (a, b) ⋆^{'} (h_{1}^{'} \circ g \circ g_{0}^{'}, h_{0}^{'} \circ h \circ g_{1}^{'}) = (a, b) ⋆^{'} k^{'} (g, h) . \end{matrix}

To see that $(j, k)$ is a morphism, consider an arbitrary $(a, b) \in A_{0} \times A_{1}$ and $(g^{'}, h^{'}) \in X^{'}$ , and let $(g, h) = k (g^{'}, h^{'})$ . Then, we have:

\begin{matrix} j (a, b) ⋆^{'} (g^{'}, h^{'}) & = (g_{0} (a), g_{1} (b)) ⋆^{'} f (g, h) = (g_{0} (a), g_{1} (b)) ⋆^{'} (h_{1}^{'}, h_{1}^{'}) \circ (g, h) \circ (g_{0}^{'}, h_{0}^{'}) = g_{1} (b) \cdot_{1}^{'} h_{1}^{'} (g (g_{0}^{'} (g_{0} (a)))) = g_{1}^{'} (g_{1} (b)) \cdot_{1} g (g_{0}^{'} (g_{0} (a))) = b \cdot_{1} g (g_{0}^{'} (g_{0} (a))) = g_{0}^{'} (g_{0} (a)) \cdot_{0} h (b) = a \cdot_{0} h (b) = (a, b) ⋆ (g, h) = (a, b) ⋆ k (g^{'}, h^{'}) . \end{matrix}

To see that $(j^{'}, k^{'}) \circ (j, k)$ is homotopic to the identity on $D$ , observe that for all $(a, b) \in A_{0} \times A_{1}$ and $(g, h) \in X$ , we have:

\begin{matrix} j^{'} (j (a, b)) ⋆ (g, h) & = (g_{0}^{'} (g_{0} (a)), g_{1}^{'} (g_{1} (b))) ⋆ (g, h) = g_{1}^{'} (g_{1} (b)) \cdot_{1} g (g_{0}^{'} (g_{0} (a))) = b \cdot_{1} g (g_{0}^{'} (g_{0} (a))) = g_{0}^{'} (g_{0} (a)) \cdot_{0} h (b) = a \cdot_{0} h (b) = (a, b) ⋆ (g, h) . \end{matrix}

Similarly, to see that $(j, k) \circ (j^{'}, k^{'})$ is homotopic to the identity on $D^{'}$ , observe that for all $(a, b) \in A_{0}^{'} \times A_{1}^{'}$ and $(g, h) \in X$ , we have:

\begin{matrix} j (j^{'} (a, b)) ⋆^{'} (g, h) & = (g_{0} (g_{0}^{'} (a)), g_{1} (g_{1}^{'} (b))) ⋆^{'} (g, h) = g_{1} (g_{1}^{'} (b)) \cdot_{1}^{'} g (g_{0} (g_{0}^{'} (a))) = b \cdot_{1}^{'} g (g_{0} (g_{0}^{'} (a))) = g_{0} (g_{0}^{'} (a)) \cdot_{0}^{'} h (b) = a \cdot_{0}^{'} h (b) = (a, b) ⋆^{'} (g, h) . \end{matrix}

Thus, $D^{'} ≃ D$ .

To see $D^{'} \in C_{0}^{'} ⊠ C_{1}^{'}$ , we need to show that $D_{i}^{'} ≃ C_{i}^{'}$ , where $D_{i}^{'} = (A_{i}^{'}, A_{1 - i}^{'} \times X^{'}, ⋆_{i}^{'})$ with $⋆_{i}^{'}$ given by

\begin{matrix} a ⋆_{0}^{'} (b, (g, h)) & = b ⋆_{1}^{'} (a, (g, h)) = (a, b) ⋆^{'} (g, h) . \end{matrix}

It suffices to show that $D_{i}^{'} ≃ D_{i}$ , since $D_{i} ≃ C_{i} ≃ C_{i}^{'}$ .

For $i \in {0, 1}$ , we construct morphisms $(j_{i}, k_{i}) : D_{i} \to D_{i}^{'}$ , and $(j_{i}^{'}, k_{i}^{'}) : D_{i}^{'} \to D_{i}$ . We define $j_{i} = g_{i}$ and $j_{i}^{'} = g_{i}^{'}$ . We define $k_{i} : (A_{1 - i}^{'} \times X^{'}) \to (A_{1 - i} \times X)$ by $k_{i} (a, x) = (g_{1 - i}^{'} (a), k (x))$ , and similarly define $k_{i}^{'} : (A_{1 - i} \times X) \to (A_{1 - i}^{'} \times X^{'})$ by $k_{i}^{'} (a, x) = (g_{1 - i} (a), k^{'} (x))$ .

To see that $(j_{0}, k_{0})$ is a morphism, observe that for all $a \in A_{0}$ and $(a_{1}, (g, h)) \in A_{1}^{'} \times X^{'}$ , we have:

\begin{matrix} a ⋆_{0} k_{0} (b, (g, h)) & = a ⋆_{0} (g_{1}^{'} (b), k (g, h)) = (a, g_{1}^{'} (b)) ⋆ k (g, h) = j (a, g_{1}^{'} (b)) ⋆^{'} (g, h) = (g_{0} (a), g_{1} (g_{1}^{'} (b))) ⋆^{'} (g, h) = g_{1} (g_{1}^{'} (b)) \cdot_{1}^{'} g (g_{0} (a)) = b \cdot_{1}^{'} g (g_{0} (a)) = (g_{0} (a), b) ⋆^{'} (g, h) = j_{0} (a) ⋆_{0}^{'} (b, (g, h)) . \end{matrix}

To see that $(j_{1}, k_{1})$ , $(j_{0}^{'}, k_{0}^{'})$ , and $(j_{1}^{'}, k_{1}^{'})$ are morphisms is similar.

To see $(j_{0}^{'}, k_{0}^{'}) \circ (j_{0}, k_{0})$ is homotopic to the identity on $D_{0}$ , observe that for all $a \in A_{0}$ and $(b, (g, h)) \in A_{1} \times X$ , we have

\begin{matrix} j_{i}^{'} (j_{i} (a)) ⋆_{i} x & = (g_{i}^{'} (g_{i} (a)), b) ⋆ (g, h) = g_{i}^{'} (g_{i} (a)) \cdot_{0} h (b) = a \cdot_{0} h (b) = (a, b) ⋆ (g, h) = a ⋆_{0} (b, (g, h)), \end{matrix}

and seeing that $(j_{1}^{'}, k_{1}^{'}) \circ (j_{1}, k_{1})$ , $(j_{0}, k_{0}) \circ (j_{0}^{'}, k_{0}^{'})$ , and $(j_{1}, k_{1}) \circ (j_{1}^{'}, k_{1}^{'})$ are homotopic to the identity is similar.