Theory and Applications of Categories, Vol. 17, No. 6, 2006, pp. 103–126.

AN EXTENDED VIEW OF THE CHU-CONSTRUCTION

JÜRGEN KOSLOWSKI

Abstract. The cyclic Chu-construction for closed bicategories with pullbacks, which generalizes the original Chu-construction for symmetric monoidal closed categories, turns out to have a non-cyclic counterpart. Both use so-called Chu-spans as new 1-cells between 1-cells of the underlying bicategory, which form the new objects. Chu-spans may be seen as a natural generalization of 2-cell-spans in the base bicategory that no longer are confined to a single hom-category. This view helps to clarify the composition of Chu-spans.

We consider various approaches of linking the underlying bicategory with the newly constructed ones, for example, by means of two-dimensional generalizations of bifibrations. In the quest for a better connection, we investigate, whether Chu-spans form a double category. While this turns out not to be the case, we are led to considering a generalization of the construction to paths of 1-cells in the base, leading to two hierarchies of closed bicategories, one for linear paths and one for loops. The possibility of moving beyond paths, respectively, loops of the same length is indicated.

Finally, Chu-spans in rel are identified as bipartite state transition systems. Even though their composition may fail here due to the lack of pullbacks in rel, basic game-theoretic constructions can be performed on cyclic Chu-spans. These are available in all symmetric monoidal closed categories with finite products. If pullbacks exist as well, the bicategory of cyclic Chuspans inherits a monoidal structure that on objects coincides with the categorical product.

1. Introduction

The Chu-construction’s original purpose was to build ∗-autonomous categories out of autonomous (= symmetric monoidal closed) categories. But although successful at that, it has long been regarded as a slightly obscure technical trick. Here we wish step back and analyze the real core of the construction at the level of closed bicategories. A wider scope of the construction then becomes discernible and the connection with ∗-autonomy turns out to hinge on the restriction to cyclic chains of what we call Chu-spans.

In his late-1970s Master’s Thesis [Chu79], supervised by Michael Barr, Po-Hsiang Chu constructed a new category 𝒜_{a} = chu ⟨𝒱, a⟩from an autonomous category 𝒱 and a 𝒱-object a. Besides being autonomous, 𝒜_{a} contained a so-called dualizing object ⊥ (depending on a) that by means of its internal hom-functor [−, ⊥] induced an equivalence between 𝒜_{a}^{op} and 𝒜_{a}. While ∗-autonomous categories had been discovered by Barr in the realm of functional analysis [Bar79], they also turned out to provide nice models for certain fragments of linear logic [See87]. Hence interest for such categories grew among computer scientists and logicians

Received by the editors 2004-02-09 and, in revised form, 2005-03-09. Published on 2006-12-18 in the volume Chu spaces: theory and applications. 2000 Mathematics Subject Classification: 18D99, 91A99. Key words and phrases: closed bicategory, Chu-spans, games, bipartite state transition systems. \begin{matrix}c \\ ◯ \end{matrix} Jürgen Koslowski, 2005. Permission to copy for private use granted.

during the 1980s. One open question concerned models for non-symmetric linear logic.

The early 1990s saw an extension of the categorical ideas to the non-symmetric but closed setting: Dualizing objects with examples were discussed in Street’s lecture notes [Str91]. Independently, Barr [Bar95] defined ∗-autonomy and described a Chu-construction in that setting, provided the base category 𝒱 has finite limits. In [Bar96] he restructured his original approach by first considering the Chu-construction for the terminal object t. Certain monads in chu ⟨𝒱, t⟩, which may be identified with 𝒱×𝒱^{op} , then generate the (generalized) ∗-autonomous categories chu ⟨𝒱, a⟩, a ∈ ob(𝒱), as categories of endo-modules.

Recall that a monoidal category may be viewed as a bicategory with one object, the tensor corresponding to the composition of 1-cells. Barr’s revised approach together with the well-known construction of the bicategory of monads from a bicategory with local coequalizers prompted the author to consider the Chu-construction in closed bicategories ℬ with local pullbacks [Kos01]. In particular, this raised the question of formulating a 2-dimensional generalization of ∗-autonomy, which tied in with research by Robin Cockett and Robert Seely on linearly distributive categories (loosely speaking “ ∗-autonomous categories without dualizing objects”), ultimately resulting in the notion of a linear bicategory [CKS00]. In the inherently non-symmetric setting of a bicategory’s 1-cell composition one should in fact expect to have two negations, that is, two ways of reversing 1-cells. These may agree, however, and in the presence of “dualizing 1-cells” this leads to the notion of cyclic ∗-autonomous bicategory.

The present paper concerns the other important lesson of [Kos01], not exploited at the time: to view the Chu-construction as a genuinely bicategorical construction, independent from the construction of the bicategory of monads. In fact, and perhaps surprisingly, the construction per se is not even concerned with ∗-autonomy. Initially, it uses all 1-cells of a closed bicategory ℬ with local pullbacks as objects for a new closed bicategory Chu_{1} (ℬ) . This contains a non-full cyclic ∗-autonomous sub-bicategory cChu_{1} (ℬ) with the endo-1-cells as objects.

Both the cyclic and the non-cyclic variant of the construction employ the same type of new 1-cells between the objects, which we call (cyclic) Chu-spans, compare Section 2. If ℬ is (the suspension of) a symmetric monoidal closed category 𝒱, for a ∈ 𝒱 the classical Chu-category 𝒜_{a} = chu ⟨𝒱, a⟩appears as full subcategory of the hom-category of cChu_{1} (𝒱) at a, compare [Kos01]. In general, endo-Chu-spans on a need not be constrained by symmetry (as required in the classical case), and there also will be Chu-spans between different objects of 𝒱.

The composition of Chu-spans (Section 3) utilizes the closedness of ℬ and the existence of local pullbacks. Modulo exponential transposition it can actually be viewed as the composition of genuine spans (hence the terminology), which eliminates the technical obscurity often associated with the classical Chu-construction.

In order to ascertain the actual scope of the construction, in Section 4 we first consider two canonical (strict) functors cChu_{1} (ℬ) [figure] ℬ and Chu_{1} (ℬ) [figure] ℬ × ℬ connecting the new bicategories with the base ℬ. While both may be viewed as two-dimensional generalizations of the notion of bifibration, the resulting possibilities of embedding either ℬ×ℬ into Chu_{1} (ℬ) or ℬ into cChu_{1} (ℬ) come across as somewhat artificial. Clearly, a better way of relating ℬ to the Chu-bicategories is called for.

To this end, we then explore the question, whether Chu-spans admit second mode of composition, orthogonal to the one discussed in Section 3, possibly giving rise to a double category. This turns out not to be the case, but short of composing Chu spans in this fashion, we may still “chain” them together.

This opens up the possibility of considering other domains and codomains for Chu-spans besides single 1-cells of ℬ, which we explore in Section 5. In particular, 1-cell paths in ℬ of fixed length n ∈ in ℬ straightforwardly induce a closed bicategory Chu_{n} (ℬ) . In addition, infinite paths indexed either by or by may be considered as objects of still further closed bicategories based on ℬ. This suggests using finite 1-cell loops in ℬ of length n > 0 as objects of a cyclic ∗-autonomous bicategory cChu_{n} (ℬ) . But the existence of non-trivial automorphisms of such loops has to be taken into account. A similar construction produces cChu_{}(ℬ) , into which the other cyclic ∗-autonomous bicategories cChu_{n} (ℬ) , n > 0 may be embedded, albeit not fully.

Finally, the notion of Chu-span may even be useful in cases where composition is not always possible. Section 6 shows that Chu-spans in the category rel (with trivial 2-cells) can be viewed as “bipartite” labeled transition systems (LTSs) that serve as a basis for strictly alternating two-party interactions and games. Three important operations on games have direct interpretations in terms of Chu-operations. Unfortunately, rel does not have pullbacks. But the game operations carry over to any symmetric monoidal closed category with finite products. If pullbacks exist as well, cyclic Chu-span morphisms into R S provide arrows R [figure] S for a ∗-autonomous category.

Some of these results were presented at the Workshop on Chu Spaces at the University of California, Santa Barbara, 2000-06-25.

2. Chu-spans and Chu-morphisms, the basic building blocks

In case of a symmetric monoidal closed category 𝒱 = ⟨𝒱, ⊗, ⊤⟩ with pullbacks the Chu-category chu ⟨𝒱, a⟩has 𝒱-morphisms of the form f_{1} ⊗ f_{0} [figure: φ] a as objects.

The monoidal category chu ⟨𝒱, a⟩can be viewed as a bicategory in the sense of Bénabou [Ben67], compare also [Bor94], with just one 0-cell, which may be identified with the 𝒱-object a. Then ⟨f_{0}, φ, f_{1}⟩ specifies an endo-1-cell on a. This suggests considering all 𝒱-objects simultaneously as 0-cells of a new bicategory, which raises the question, how to generalize the endo-1-cells above to 1-cells between possibly different 0-cells. We can even try to use the 1-cells of an arbitrary bicategory ℬ = ⟨ℬ, ⊗, ⊤⟩ as 0-cells of a new structure (here ⊤ maps objects to identity 1-cells).

2.1. Definition. A Chu-span φ = ⟨f_{0}, φ_{0}, f_{1}, φ_{1}, f_{2}⟩ from A_{0} [figure: a] A_{2}to B_{0} [figure: b] B_{2} in ℬ consists of two independent 2-cells

[figure: B_{0}; B_{2}; A_{0}; A_{2}; φ_{0}; φ_{1}; b; a; f_{0}; f_{1}; f_{2}]  (2-01)

We call φ simple, if a and b are terminal in their hom-categories, trivial, if f_{0} and f_{2} are isomorphisms, and cyclic, if f_{0} = f_{2} . In this case the opposite Chu-span from b to a is given by φ^{∗} = ⟨f_{1}, φ_{1}, f_{0} = f_{2}, φ_{0}, f_{1}⟩.

The new terminology (in [Kos01] we called these gadgets “Chu-cells”) was inspired by the observation that a trivial Chu-span is just an ordinary span in the hom-category B⟨A_{0}, A_{2}⟩. Hence Chu-spans may be viewed as generalizations of spans with domains and codomains in possibly different hom-categories of ℬ.

In a symmetric monoidal category 𝒱 any f_{1} ⊗ f_{0} [figure: φ] a specifies half of a Chu-span

[figure: •; •; •; •; φ; φ̂; a; a; f_{0}; f_{1}; f_{0}]

where the other half is induced by symmetry. If 𝒱 is not symmetric, f_{1} ⊗ f_{0} [figure: φ] a need not have a canonical counterpart unless some additional structure is present (for example, a shift operation in case that 𝒱 consists of graded objects). Our approach sidesteps the issue of canonical counterpart by pairing f_{1} ⊗ f_{0} [figure: φ] a with every 2-cell f_{0} ⊗ f_{1} [figure: ψ] a.

If 𝒱 is also closed, classically a morphism from f_{1} ⊗ f_{0} [figure: φ] a to f′_{1}⊗ f′_{0} [figure: φ′] a in chu ⟨𝒱, a⟩ consists of 𝒱-morphisms f_{0} [figure: ρ_{0}] f′_{0}and f′_{1} [figure: ρ_{1}] f_{1} such that

[figure: f_{0}; φ̃; ρ_{0}; [f_{1}, a]; [ρ_{1},a]; f′_{0}; φ̃′; [f′_{1}, a]; or equivalently; f′_{1}⊗ f_{0}; ρ_{1}⊗f_{0}; f′_{1}⊗ρ_{0}; f_{1} ⊗ f_{0}; φ′; f′_{1}⊗ f′_{0}; φ; a]  (2-02)

Here [−, −] denotes the closed structure of 𝒱 and ˜ indicates exponential transposes. While the first presentation superficially resembles a coalgebra homomorphism, the second one identifies ρ_{0} and ρ_{1} as “formal adjoints” with respect to φ and φ′, denoted by ρ_{0} ⊣_{φ′}^{φ} ρ_{1} (think of 𝒱 = set , where ⊗ is cartesian product).

Even though morphisms between Chu-spans can be defined in any bicategory ℬ, closedness of ℬ (with respect to 1-cell composition) allows for a more concise formulation and will shortly be needed to define the composition of Chu-spans.

2.2. Assumption. We require ℬ to be right-closed in the sense of [SW78]: every 1-cell A [figure: t] C admits a right extension ⟨ev, r ▷t⟩ along any A [figure: r] B, and a right lifting through any B [figure: s] C

[figure: A; B; C; and; A; B; C; ev; ve; t; r; r▷t; t; t◁s; s]

in the sense that for the 2-cells pasting at r ▷t, respectively, at t ◁s is bijective. The transition from s ⊗ r [figure: χ] t to s [figure: χ^{▷}] r ▷t or to r [figure: χ^{◁}] t ◁s is known as “(exponential) transposition” or, alternatively, as “currying”.

2.3. Definition. Given Chu-spans a [figure: φ] b and a [figure: φ′] b, a Chu-morphism φ [figure: ρ] φ′ consists of 2-cells ⟨f_{0} [figure: ρ_{0}] f′_{0}, f_{1} [figure: ρ_{1}] f′_{1}, f_{2} [figure: ρ_{2}] f′_{2}⟩ subject to

[figure: f_{0} ▷a; f_{1}; φ_{0}^{▷}; φ_{1}^{◁}; b ◁f_{2}; f′_{0}▷a; ρ_{0}▷a; f′_{1}; φ′_{0}^{▷}; φ′_{1}^{◁}; ρ_{1}; b ◁f′_{2}; b◁ρ_{2}] or, alternatively, ρ_{0} ⊣_{φ′_{0}}^{φ_{0}} ρ_{1} ⊣_{φ_{1}}^{φ′_{1}} ρ_{2}

We call ρ cyclic, if ρ_{0} = ρ_{2} . In this case the opposite Chu-morphism (φ′)^{∗} [figure: ρ^{∗}] φ^{∗} is given by ⟨ρ_{1}, ρ_{0} = ρ_{2}, ρ_{1}⟩.

Compared to the left presentation in Diagram (2-02) we have curried twice in order to display the Chu-spans as genuine spans with centers f_{1} and f′_{1}, respectively. Compared to span morphisms Chu-morphisms point in the opposite direction. This is necessary to obtain closed rather than coclosed Chu-bicategories and will later enable us to recover ℬ rather than ℬ^{co} inside those.

2.4. Example. The category set of sets and functions is symmetric monoidal with respect to the cartesian product ×. Recall that a span a [figure: φ_{0}] f_{1} [figure: φ_{1}] b in set may be thought of as a directed bi-partite (multi-)graph with node-set a + b, edge-set f_{1} , and domains and codomains given by φ_{0} and φ_{1} , respectively.

Now we can interpret a Chu-span φ = ⟨f_{0}, φ_{0}, f_{1}, φ_{1}, f_{2}⟩ from a to b in set as a family of bipartite graphs with fixed node-set a + b and edge-set f_{1} , where the domain- and codomain functions are parameterized by sets f_{0} and f_{2} , respectively. In case of a cyclic Chu-span, the parameter sets coincide and we think of these functions as being jointly parameterized by f_{0} rather than being separately parameterized by f_{0} × f_{0} .

For simple Chu-spans the graphs have just two nodes, hence are completely determined by the set of edges. The parameterization now only determines the size of the family, all members have the same trivial “shape”.

For a endo-Chu-spans the sets a and b coincide. Instead of bipartite graphs with node set a+a we may therefore consider graphs just on a, where paths of length 1 become available. In particular, this applies to classical Chu-spans, which by default are cyclic. Symmetry relating the domain and codomain functions forces every edge in the corresponding graph to be a loop.

Dualization of cyclic Chu-spans interchanges the roles of parameter set and edge set in the graph, besides reversing the arrows.

In Section 6 we will consider a different graph-theoretical interpretation of Chu-spans over set in the larger context of Chu-spans over the monoidal closed category ⟨rel, ×, 1⟩.

3. The composition of Chu-spans

In order to use Chu-spans as 1-cells in a new bicategory with the 1-cells of ℬ as objects, we need to be able to compose them. Simplicity suggests composing the outer 1-cells (with even index) of matching Chu-spans just like 1-cells in ℬ:

\binom{φ}{γ} = [figure: C_{0}; C_{2}; B_{0}; B_{2}; A_{0}; A_{2}; φ_{0}; φ_{1}; γ_{0}; γ_{1}; c; b; a; f_{0}; f_{1}; f_{2}; g_{0}; g_{1}; g_{2}] ↦ [figure: C_{0}; C_{2}; A_{0}; A_{2}; ϵ_{0}; ϵ_{1}; c; a; e_{0}=g_{0}⊗f_{0}; e_{1}; e_{2}=g_{2}⊗f_{2}] =: γ ⊙ φ  (3-03)

If φ and γ are trivial, the construction of e_{1} reduces to the composition of ordinary spans in B⟨B_{0}, B_{2}⟩by means of a pullback of φ_{1} and γ_{0} , leading to

3.1. Assumption. ℬ locally has pullbacks.

In the general case we still need to derive a 1-cell C_{0} [figure] A_{2} from a pullback B_{0} [figure: p] B_{2} of φ_{1} and γ_{0} . Let us utilize the closedness of ℬ (compare Assumption 2.2) to solve this problem. Recall that (g_{0} ▷p) ◁f_{2} and g_{0} ▷(p ◁f_{2}) have the same universal property, hence we may drop the parentheses. Since g_{0} ▷− and − ◁f_{2} are right-adjoint to − ⊗ g_{0} and f_{2} ⊗ −, respectively, we obtain the pullback g_{0} ▷p ◁f_{2} as a first candidate for e_{1} . The difficulty with this approach is to extract a Chu-span from a to c from this pullback. This would seem to require 2-cells (f_{2} ⊗ f_{1}) ◁f_{2} [figure] f_{1} and g_{0} ▷(g_{1} ⊗ g_{0}) [figure] g_{1}, for which there are no canonical candidates.

Instead, we could first curry and then obtain e_{1} ∈ B⟨C_{0}, A_{2}⟩as a pullback:

[figure: e_{1}; ν_{1}; μ_{1}; g_{1} ◁f_{2}; γ_{0}^{▷}◁f_{2}; γ_{1}^{◁}◁f_{2}; (c ◁g_{2}) ◁f_{2}; g_{0} ▷f_{1}; g_{0}▷φ_{1}^{◁}; g_{0}▷φ_{0}^{▷}; g_{0} ▷b ◁f_{2}; g_{0} ▷(f_{0} ▷a)]  (3-04)

This construction links the non-matching transposes of the original Chu-spans φ and γ

[figure: f_{1}; φ_{1}^{◁}; φ_{0}^{▷}; b ◁f_{2}; f_{0} ▷a; and; g_{1}; γ_{1}^{◁}; γ_{0}^{▷}; c ◁g_{2}; g_{0} ▷b]

Now g_{0} ▷(f_{0} ▷a) (g_{0} ⊗ f_{0}) ▷a and (c ◁g_{2}) ◁f_{2} c ◁(g_{2} ⊗ f_{2}) allow us to extract a Chu-span from a to c from Diagram (3-04). Conceptually, e_{1} may be thought of as the “object of formal adjunctions” with respect to φ_{1} and γ_{0} .

3.2. Definition. Given Chu-spans φ = ⟨f_{0}, φ_{0}, f_{1}, φ_{1}, f_{2}⟩ and γ = ⟨g_{0}, γ_{0}, g_{1}, γ_{1}, g_{2}⟩ from A_{0} [figure: a] A_{2}to B_{0} [figure: b] B_{2} to C_{0} [figure: c] C_{2}, define their composite γ ⊙ φ from a to c by

[figure: B_{0}; B_{2}; A_{0}; A_{2}; C_{0}; C_{2}; φ_{0}; γ_{1}; ν_{1}; μ_{1}; ev; ve; c; a; f_{0}; g_{0}; f_{1}; g_{0}▷f_{1}; e_{1}; g_{1}◁f_{2}; g_{1}; f_{2}; g_{2}]  (3-05)

3.3. Theorem. 1-cells of ℬ as objects, Chu-spans as 1-cells and Chu morphisms as 2-cells form a closed bicategory Chu_{1} (ℬ) .

Proof. The identity Chu-span 1_{a} on A_{0} [figure: a] A_{2} is given by the structural unit isomorphisms

[figure: A_{0}; A_{2}; A_{0}; A_{2}; u_{l}; u_{r}; a; a; ^{⊤^{A_{0}}}; a; ^{⊤^{A_{2}}}]  (3-06)

The essential associativity and the functoriality of the Chu-span composition follow, since the central 1-cell of both (η ⊗ γ) ⊗ φ and η ⊗ (γ ⊗ φ) with η = ⟨h_{0}, η_{0}, h_{1}, η_{1}, h_{2}⟩ from c to D_{0} [figure: d_{1}] D_{2} derives from a limit (for example, via three pullbacks) of the diagram

\xymatrix{h_{0} ▷(g_{0} ▷f_{1}) \ar@{=>}[dr]_{h_{0}▷(g_{0}▷φ_{1}^{◁})} &  & h_{0} ▷g_{1} ◁f_{2} \ar@{=>}[dr]^{h_{0}▷γ_{1}^{◁}◁f_{2}} \ar@{=>}[dl]_{h_{0}▷γ_{0}^{▷}◁f_{2}} &  & (h_{1} ◁g_{2}) ◁f_{2} \ar@{=>}[dl]^{(η_{0}^{▷}◁g_{3})◁f_{2}} \\  & h_{0} ▷(g_{0} ▷b) ◁f_{2} &  & h_{0} ▷(c ▷g_{2}) ◁f_{2}}

Note that the different variance in the even and odd components of a Chu-morphism is necessary for the functoriality of this composition.

Given φ and a Chu-span κ = ⟨k_{0}, κ_{0}, k_{1}, κ_{1}, k_{2}⟩ from a to c, define γ := φ ▷κ by

[figure: A_{2}; B_{0}; B_{2}; C_{0}; C_{2}; φ_{1}; κ_{1}; ω_{0}; ev; ve; c; b; k_{1}; f_{2}; g_{0}; f_{1}◁k_{1}; f_{1}; k_{2}; f_{2}▷k_{2}; where; g_{0}; ω_{0}; λ_{0}; f_{1} ◁k_{1}; φ_{0}^{▷}◁k_{1}; f_{0} ▷k_{0}; f_{0}▷κ_{0}^{◁}; f_{0} ▷a ◁k_{1}]  (3-07)

To show that this induces a right extension of κ along φ, we need to construct an “evaluation” E := γ ⊙ φ [figure: Ev] κ. For the outer components we use

g_{0} ⊗ f_{0} [figure: λ_{0}⊗f_{0}] (f_{0} ▷k_{0}) ⊗ f_{0} [figure: ev] k_{0}  and  (k_{2} ⊗ f_{2}) ⊗ f_{2} [figure: ev] k_{2} .

Exponentially transposing g_{1} ⊗ g_{0} = f_{2} ⊗ k_{1} ⊗ g_{0} [figure: γ_{0}] b above in different ways yields

\xymatrix{k_{1} \ar@{=>}[r]^{ev^{▷}} \ar@{=>}[d]_{1_{f_{2}⊗k_{1}}^{◁}} & (f_{1} ◁k_{1}) ▷f_{1} \ar@{=>}[r]^{ω_{0}▷f_{1}} & g_{0} ▷f_{1} \ar@{=>}[d]^{g_{0}▷φ_{1}^{◁}} \\ (f_{2} ⊗ k_{1}) ◁f_{2} \ar@{=>}[rr]_{γ_{0}^{▷}◁f_{2}} &  & g_{0} ▷b ◁f_{2}}

This induces Ev_{1} from k_{1} into the pullback e_{1} of γ_{0}^{▷} ◁f_{2} and g_{0} ▷φ_{1}^{◁}.

Now consider a Chu-span b [figure: γ′] c and a Chu-morphism E′:= γ′⊙ F [figure: σ] κ. To find a unique Chu-morphism γ′ [figure: σ^{▷}] γ = φ ▷κ that satisfies Ev∘σ^{▷} ⊙ φ = σ, we set (σ^{▷})_{2} = σ_{2}^{▷}. Exponentially transposing the property κ_{0}∘k_{1} ⊗ σ_{0} = ϵ′_{0}∘σ_{1} ⊗ e′_{0} of σ results in

\xymatrix{g′_{0} \ar@{=>}[r]^{ev^{◁}} \ar@{=>}[d]_{σ_{0}^{▷}} & f_{1} ◁(g′_{0} ▷f_{1}) \ar@{=>}[r]^{f_{1}◁σ_{1}} & f_{1} ◁k_{1} \ar@{=>}[d]^{φ_{0}^{▷}◁k_{1}} \\ f_{0} ▷k_{0} \ar@{=>}[rr]_{f_{0}▷κ_{0}^{◁}} &  & f_{0} ▷a ◁k_{1}}

The pullback g_{0} of f_{0} ▷ κ_{0}^{◁} and φ_{0}^{▷} ◁ k_{1} provides us with g′_{0} [figure: (σ^{▷})_{0}] g_{0}. Finally, transposing k_{1} [figure: σ_{1}] e′_{1} [figure: ν′_{1}] g′_{1} ◁ f_{2} exponentially yields the central component g_{1} = f_{2} ⊗ k_{1} [figure: (σ^{▷})_{1}] g′_{1}. A straightforward computation establishes the desired property of σ^{▷}.

The construction of right liftings is analogous.

3.4. Remarks.

(0) The construction of a right extension in Diagram (3-07) shows that the bicategories spn(B⟨A_{0}, A_{2}⟩) will in general not be left-closed with respect to span-composition: in the trivial case, for isomorphisms f_{0} and f_{2} as well as k_{0} and k_{2} , the 2-cell g_{0} [figure: ω_{0}] f_{0}▷k_{0} 1_{a} need not be an isomorphism. In other words, left extensions (and liftings) of ordinary spans will in general be proper Chu-spans.

(1) In case of two parallel Chu-spans φ, φ′ from a to b, the right extension γ := φ ▷φ′ and the right lifting η := φ′◁φ may jointly be used to encode Chu-morphisms from φ to φ′: combine 2-cells B_{0} [figure: β] g_{0} and A_{2} [figure: α] e_{2} with the corresponding pullback projections and uncurry to obtain f_{0} [figure: ρ_{0}] f′_{0}, f′_{1} [figure: ρ_{1},σ_{1}] f_{1} and f_{2} [figure: σ_{2}] f′_{2}with

[figure: f′_{1}⊗ f_{0}; ρ_{1}⊗f_{0}; f′_{1}⊗ρ_{0}; f_{1} ⊗ f_{0}; φ′; f′_{1}⊗ f′_{0}; φ; a; respectively; f′_{2}⊗ f_{1}; σ_{2}⊗f_{1}; f′_{2}⊗σ_{1}; f_{2} ⊗ f_{1}; φ′; f′_{2}⊗ f′_{1}; φ; b]  (3-08)

compare Diagram (2-02). ⟨β, α⟩ specifies a Chu-morphism iff ρ_{1} = σ_{1} 3.5. Examples.

(0) Since set is cartesian closed, Chu-spans as in Example 2.4 can be composed as indicated above. The composition of ordinary spans may be visualized as the composition of bipartite graphs. This does carry over to the composition of Chu-spans: given φ = ⟨f_{0}, φ_{0}, f_{1}, φ_{1}, f_{2}⟩ and γ = ⟨g_{0}, γ_{0}, g_{1}, γ_{1}, g_{2}⟩ from a to b to c, the arrows of the composite Chu-span from a to c are pairs of functions ⟨g_{0} [figure: λ] f_{1}, f_{2} [figure: ρ] g_{1}⟩ such that for all ⟨i, j⟩ ∈ g_{0} × f_{2} we have φ_{1}⟨λ(i), j⟩= γ_{0}⟨i, ρ(j)⟩, that is, λ and ρ are “formal adjoints” λ ⊣_{γ_{0}}^{φ_{1}} ρ. In case of g_{0} = 1 = f_{2} this reduces to the familiar notion of “matching” or “composable” arrows.

Similarly, if κ = ⟨k_{0}, κ_{0}, k_{1}, κ_{1}, k_{2}⟩ is another Chu-span from a to c, the arrow-set of the right-extension φ ▷κ consists of the formal adjoints α ⊣_{κ_{0}}^{φ_{0}} β.

(1) The bicategory rel with sets as objects, relations as 1-cells and inclusions as 2-cells is well-known to be closed with respect to 1-cell composition. Its hom-categories are power-sets and hence complete lattices. If we consider diagram (3-04) or (3-05) in rel, the central relation C_{0} [figure: e_{1}]A_{2} is simply the intersection of the sets

\begin{aligned}g_{0} ▷f_{1} & = \{ ⟨z, x⟩ ∈ C_{0} × A_{2} : ∀y ∈ B_{0}. ⟨y, z⟩ ∈ g_{0} =⇒ ⟨y, x⟩ ∈ f_{1} \} \\ g_{1} ◁f_{2} & = \{ ⟨z, x⟩ ∈ C_{0} × A_{2} : ∀v ∈ B_{2}. ⟨z, v⟩ ∈ g_{1} ⟸ ⟨x, v⟩ ∈ f_{2} \} \end{aligned}

Once we restrict attention to cyclic and hence reversible Chu-spans, we would expect the resulting closed bicategory to be “ ∗-autonomous” in a suitable sense. The following definition was introduced in [Kos01]. It minimizes coherence issues and implies closedness of the bicategory and the existence of “dualizing 1-cells” on every object.

3.6. Definition. A cyclic ∗-autonomous bicategory ℬ is equipped with

(0) a “self-dual” family of equivalences

B⟨A, B⟩ [figure: (−)^{∗}] B^{coop}⟨A, B⟩= (B⟨B, A⟩)^{op}

for ℬ_{0}-objects A, B, that is,

(B⟨A, B⟩ [figure: (−)^{∗}] B^{coop}⟨A, B⟩) ⊣ (B⟨B, A⟩ [figure: (−)^{∗}] B^{coop}⟨B, A⟩)^{op}

(1) a natural family of 2-cells r^{∗} ⊗ r [figure: ^{ev^{r}}] (⊤_{A})^{∗}, A [figure: r] B a 1-cell in ℬ, such that ⟨ev_{r}, r^{∗}⟩ is a right extension of (⊤_{A})^{∗} along r.

It is easy to see that ⟨r, ev_{r}⟩ is a right lifting of (⊤_{A})^{∗} through r^{∗}. Hence the “dualizing 1-cells” are given by the images of the identity 1-cells under (−)^{∗}.

3.7. Remark. In a cyclic ∗-autonomous bicategory we may define a second tensor composition ⊕ (“par”) by de Morgan duality, that is, g ⊕ f := (f^{∗} ⊗ g^{∗})^{∗}. This is essentially associative and has units of the form ⊥_{A} := (⊤_{A})^{∗}. In fact, we obtain a second bicategory structure on the objects, 1-cells and 2-cells of ℬ, which is linked with the original one via so-called “linear distributions” (C ⊕ B) ⊗ A [figure: δ_{L}] C ⊕ (B ⊗ A) and C ⊗ (B ⊕ A) [figure: δ_{R}] (C ⊗ B) ⊕ A subject to certain coherence requirements. “Linear bicategories” were introduced [CKS00] to study such related bicategory structures that do not necessarily arise via de Morgan duality.

3.8. Theorem. Endo-1-cells of ℬ as objects, cyclic Chu-spans as 1-cells and cyclic Chu-mor-phisms as 2-cells form a cyclic ∗-autonomous bicategory cChu_{1} (ℬ) .

Proof. The dualization operation (−)^{∗} on cyclic Chu-spans and cyclic Chu-span morphisms provides the required family of equivalences.

If φ is cyclic from A [figure: a] A to B [figure: b] B, the central component of φ^{∗} ⊙ φ is given by a pullback e_{1} of the cospan f_{1} ▷f_{1} [figure: f_{1}▷φ_{1}^{◁}] f_{1} ▷b ◁f_{0} [figure: φ_{1}^{▷}◁f_{0}] f_{0} ◁ f_{0}. Exponential transposes of the identities on f_{0} and f_{1} now yield the central component ⊤_{A} [figure] e_{1} of a Chu-morphism φ^{∗} ⊙ φ [figure: ^{ev^{φ}}] (1_{a})^{∗} with outer component φ_{0} . The right extension property and the naturality of the right extensions are routine verifications.

3.9. Remark. While the tensor-compositions in cChu_{1} (ℬ) and Chu_{1} (ℬ) coincide, right extensions in Chu_{1} (ℬ) of cyclic Chu-spans a [figure: φ] b and a [figure: κ] c will in general not be cyclic. Instead, in cChu_{1} (ℬ) the right extension of κ along φ is given by

[figure: A_{0}; B_{0}; B_{0}; C_{0}; C_{0}; φ_{1}; κ_{1}; ω_{0}; ev; ve; λ_{0}; b; c; k_{1}; f_{0}; g_{0}; f_{1}◁k_{1}; f_{1}; k_{0}; g_{0}; f_{0}▷k_{0}; where; g_{0}; ω_{0}; λ_{0}; f_{1} ◁k_{1}; φ_{0}^{▷}◁k_{1}; f_{0} ▷k_{0}; f_{0}▷κ_{0}^{◁}; f_{0} ▷a ◁k_{1}]  (3-09)

Just as in ordinary ∗-autonomous categories, this may be expressed in terms of ⊗ and (−)^{∗} as (φ ⊗ κ^{∗})^{∗}. Right liftings behave dually.

Recall that for a monoidal closed category 𝒱 with finite limits the Chu-category chu ⟨𝒱, t⟩ coincides with 𝒱^{op} × 𝒱. Hence the following result for Chu-bicategories, which extends the one for Chu-categories, is not surprising.

3.10. Proposition. If ℬ locally has 𝒥-limits and 𝒥-colimits, so do Chu_{1} (ℬ) and cChu_{1} (ℬ) .

Proof. For a functor 𝒥 [figure: P] (Chu_{1} (ℬ))⟨a, b⟩we obtain induced functors P_{i}, i < 3 , from 𝒟 into B⟨A_{0}, B_{0}⟩, B⟨B_{0}, A_{2}⟩and B⟨A_{2}, B_{2}⟩, respectively. Consider limits ⟨ℓ_{0}, λ_{0}⟩ and ⟨ℓ_{2}, λ_{2}⟩ of P_{0} and P_{2} , respectively, and a colimit ⟨μ_{1}, m_{1}⟩ of P_{1} . For j ∈ 𝒥 transposes of the 2-cell-components P_{1}(j) ⊗ P_{0}(j) [figure] a and P_{2}(j) ⊗ P_{1}(j) [figure] b of P(j) induce cocones

P_{1}(j) [figure] P_{0}(j) ▷a [figure: λ_{0}_{j}▷a] ℓ_{0} ▷a and P_{1}(j) [figure] b ◁P_{2}(j) [figure: b◁λ_{2}_{j}] b ◁ℓ_{2}

that both factor through μ_{1}_{j} . Combination with the appropriate right extension ev and right lifting ve then yields a Chu-span

[figure: B_{0}; B_{2}; A_{0}; A_{2}; ξ_{0}; ξ_{1}; b; a; ℓ_{0}; m_{1}; ℓ_{2}]

with projections ⟨λ_{0}_{d}, μ_{1}_{d}, λ_{2}_{d}⟩ into P(d) that clearly form a limit of P. To obtain a colimit, start with a limit of P_{1} and proceed dually, utilizing colimits of P_{0} and P_{2} .

3.11. Remark. Since Chu_{1} (ℬ) encompasses all bicategories (spn(B⟨A_{0}, A_{2}⟩))^{co} , all their maps (= right-adjoint spans) are preserved. In particular, every 2-cell b [figure: ξ] a in B⟨X, Y⟩induces a pair of adjoint Chu-spans

ξ^{+} = [figure: X; Y; X; Y; u_{l}; ξ; u_{r}; a; b; a; b; ^{⊤^{X}}; ^{⊤^{Y}}]  ⊣  ξ_{+} = [figure: X; Y; X; Y; u_{l}; ξ; u_{r}; b; a; b; a; ^{⊤^{X}}; ^{⊤^{Y}}]  (3-10)

These admit particularly simple compositions with other Chu-spans that have domain, respectively, codomain b: just compose the appropriate 2-cell component with ξ.

4. Relating ℬ directly with the Chu-bicategories

In order to analyze how a closed bicategory ℬ is related to Chu_{1} (ℬ) and cChu_{1} (ℬ) , we first investigate, whether the latter form extensions of ℬ.

Then each object A of ℬ ought to be mapped to a 1-cell of ℬ. The only canonical ones would seem to be ⊤_{A}, and perhaps the terminal 1-cell t_{A}, provided finite limits exist locally. In both cases cChu_{1} (ℬ) appears to be a more natural candidate for an embedding of ℬ.

Chu(ℬ) , on the other hand, may be better suited as an extension of ℬ × ℬ. Again the question arises, which canonical 1-cell A_{0} [figure] A_{2} to choose. Unless the hom-categories of ℬ have terminal objects, it is not clear which other suitable candidates to choose.

Turning the problem around, the (strict) domain/codomain functors cChu_{1} (ℬ) [figure] ℬ and Chu_{1} (ℬ) [figure] ℬ×ℬ map a Chu-span φ = ⟨f_{0}, φ_{0}, f_{1}, φ_{1}, f_{2}⟩ to f_{0} and ⟨f_{0}, f_{2}⟩, respectively. For closed ℬ with local pullbacks, we suspect that diagrams of the form

[figure: C_{0}; C_{2}; B_{0}; B_{2}; c; g_{0}; g_{2}; and; B_{0}; B_{2}; A_{0}; A_{2}; a; f_{0}; f_{2}]

can be completed to Chu-spans into c, respectively, from a in some optimal fashion, where in the cyclic case we require g_{0} = g_{2} , respectively f_{0} = f_{2} . Technically this means that the above functors should be either lax or oplax counterparts of bifibrations, that is, admit the appropriately weakened form of “initial” and “terminal” lifts.

4.1. Definition. Given a lax functor 𝒳 [figure: ⟨L,λ⟩] 𝒴 and a 1-cell B [figure: g] L(W) in 𝒴, we call a 1-cell V [figure: ḡ] W in 𝒳 a lax initial lift of g, provided that

• L(ḡ) = g, and

• for any 2-cell g ⊗ f [figure: α] L(k) in 𝒴, there exists a 2-cell ḡ⊗ f̄ [figure: ᾱ] k in 𝒳 such that

- L(f̄) = f ;

- α = (L(ᾱ)) ∘λ_{f̄,ḡ};

- any other 2-cell ḡ⊗ f̂ [figure: α̂] k in 𝒳 with L(f̂) = f and α = (L(α̂)) ∘λ_{f̂,ḡ} factors through ᾱ by means of a unique 2-cell f̂ [figure: ξ] f̄in 𝒳.

In form of pasting diagrams (starting in a zig-zag pattern at the lower left):

[figure: B; L(W); L(U); B; L(W); L(U); B; L(W); L(U); V; W; U; V; W; U; V; W; U; =; =; =; ∀; ∃; ∀; ∃!; α; λ_{f̄,ḡ}; λ_{f̂,ḡ}; ᾱ; α̂; ᾱ; ξ; L(ᾱ); L(α̂); g; f; L(k); g; L(ḡ⊗f̄); L(f̄)=f; L(k); g; L(ḡ⊗f̂); L(f̂)=f; L(k); ḡ; f̄; k; ḡ; f̂; k; ḡ; f̂; f̄; k; L; L]

⟨L, λ⟩ is a lax fibration, if each B [figure: g] L(W) in 𝒴 has a lax initial lift. Lax terminal lifts and lax opfibrations are defined dually. A lax bifibration is both a lax fibration and a lax opfibration.

4.2. Theorem. If ℬ is closed and has local pullbacks, both functors cChu_{1} (ℬ) [figure] ℬ and Chu_{1} (ℬ) [figure] ℬ × ℬ are lax bifibrations.

Proof. In case of Chu_{1} (ℬ) [figure] ℬ × ℬ we need to construct a lax initial lift of C_{0} [figure: c] C_{2} along ⟨B_{0} [figure: g_{0}] C_{0}, B_{2} [figure: g_{2}] C_{2}⟩. Define a Chu-span into c by

[figure: b; c; C_{0}; C_{2}; B_{0}; B_{2}; γ_{0}; ve; c; b:=(c⊗g_{0})◁g_{2}; g_{0}; g_{1}:=c◁g_{2}; g_{2}; γ; :=]

where γ_{0} is a transpose of ve ⊗ g_{0} . For any Chu-span κ = ⟨k_{0}, κ_{0}, k_{1}, κ_{1}, k_{2}⟩ from A_{0} [figure: a] A_{2} to c, and all 2-cells g_{i} ⊗ f_{i} [figure: α_{i}] k_{i}, i ∈ {0, 2}, in ℬ, we need to find an essentially unique Chumorphism γ ⊙ φ [figure: α] κ with outer components α_{0} and α_{2} such that every other Chu-morphism γ ⊙ φ̂ [figure: α′] κ with the same outer components factors as α′ = α ∘(γ ⊙ ξ) by means of a unique Chu-morphism φ̂ [figure: ξ] φ. Concretely, with β := (κ_{1}∘(α_{2} ⊗ k_{1}))^{◁} we set

[figure: a; b; B_{0}; B_{2}; C_{0}; A_{0}; A_{2}; κ_{0}; α_{0}; β; γ_{0}; (c⊗g_{0})◁g_{2}; a; f_{0}; g_{0}; k_{0}; c◁g_{2}; k_{1}; f_{2}; φ; :=]

For φ_{1} = γ_{0} ∘(β ⊗ g_{0}) we then compute (φ_{1}^{▷})^{◁} = (φ_{1}^{◁})^{▷} from k_{1} to g_{0} ▷b ◁f_{2} :

[figure: k_{1}; β^{◁}; 1_{k_{1}⊗g_{0}}^{▷}; g_{1} ◁f_{2} c ◁(g_{2} ⊗ f_{2}); γ_{0}^{▷}◁f_{2} 1_{c⊗g_{0}}^{▷} ◁(g_{2}⊗f_{2}); g_{0} ▷(k_{1} ⊗ g_{0}); g_{0}▷φ_{1}^{◁}; g_{0} ▷b ◁f_{2} g_{0} ▷(c ⊗ g_{0}) ◁(g_{2} ⊗ f_{2})]

Here we utilized (x ◁g_{2}) ◁f_{2} x ◁(g_{2} ⊗ f_{2}) for x = c and for x = c ⊗ g_{0} . The central 1-cell e_{1} of ϵ := γ ⊙ φ being a pullback of the lower cospan induces the required 2-cell k_{1} [figure: α_{1}] e_{1}. A straightforward calculation establishes α = ⟨α_{0}, α_{1}, α_{2}⟩ as a Chu-morphism from γ ⊙ φ to κ.

Notice that the transpose φ [figure: α^{▷}] κ ▷γ has the identity on k_{1} ⊗ g_{0} as central 1-cell. Hence if γ ⊙ φ̂ [figure: α̂] κ also has the outer components α_{0} and α_{2} , the central 1-cell of its transpose φ̂ [figure: α̂^{▷}] κ ▷γ provides us with a candidate for the central 1-cell of the desired φ [figure: ξ] φ, the outer 1-cells being fixed as identities. A simple calculation then shows α̂ = α ∘(γ ⊙ ξ) .

If f_{0} = f_{2} , the Chu-span γ is cyclic, hence the same construction applies.

“Lax terminal lifts” for both Chu_{1} (ℬ) [figure] ℬ × ℬ and cChu_{1} (ℬ) [figure] ℬ are computed dually with the help of right extensions.

In order to embed ℬ into cChu_{1} (ℬ) we need to choose endo-1-cells for each ℬ-object and Chu-spans for each 1-cell of ℬ. With identities and terminals, respectively, we can build Chu-spans that are closed under composition:

[figure: B; B; A; A; π_{0} ⊗ f_{0}; ev; f_{0} ⊗ π_{1}; ve; _{⊤_{B}}; ^{⊤^{A}}; f_{0}; f_{0}▷⊤_{A}×⊤_{B}◁f_{0}; f_{0}; respectively; B; B; A; A; !; !; t_{B}; t_{A}; f_{0}; t_{B,A}; f_{0}] (4-11)

In fact, t_{B,A} = f_{0} ▷ t_{a} × t_{B} ◁ f_{0} , so both constructions follow the pattern of forming limits in cChu_{1} (ℬ) , see Proposition 3.10. However, the second choice is both “lax initial” and “lax terminal”, while the first one has neither of these properties. This partially explains the usefulness of simple Chu-spans in [Bar96]. The second type of Chu-span also generalizes to the non-cyclic case. This yields an embedding of ℬ × ℬ into Chu_{1} (ℬ) , provided local terminals exist.

However, the cyclic Chu-spans of Diagram (4-11) are not closed under dualization (−)^{∗}. So in case that ℬ happens to be cyclic ∗-autonomous in the sense of Definition 3.6, these embeddings are not very useful. As Example 5.2 below will show, additional structure on ℬ provides other possibilities for embeddings.

In view of these shortcomings a more conceptual comparison of ℬ with the Chu-categories is needed.

A right-closed bicategory ℬ may be specified by its hom-categories B⟨X, Y⟩(where 2-cells are composed “vertically”), the composition functors B⟨X, Y⟩× B⟨Y, Z⟩ [figure: ⊗] B⟨X, Z⟩(responsible for the “horizontal” composition of 1- and 2-cells), and the adjunctions − ⊗ r ⊣ r ▷ −, respectively, s ⊗ − ⊣ − ◁s between appropriate hom-categories (expressing closedness).

Provided ℬ locally has pullbacks, we replacing its hom-categories by their bicategories of spans (with 2-cells reversed) yields a 3-dimensional structure. Since 1-cell composition in ℬ is left rather than right adjoint, local limits need not be preserved. Hence the composition functors of ℬ only extend to normal lax functors, and instead of an interchange law for vertical and horizontal span compositions, we only have a 3-cell in one direction.

Generalizing from ordinary spans to Chu-spans further reduces the possibilities of meaningful horizontal composition, but instead provides us with an extended vertical composition that even admits right extensions and right liftings – which could be seen as a trade-off. This justifies drawing Chu-spans vertically rather than horizontally: the composition of Chu-spans generalizes the vertical composition of ℬ, not the horizontal one. Schematically we have

[figure: A_{0}; A_{2}; A_{4}; ℬ :; A_{0}; A_{2}; A_{4}; ℬ_{spn} :; C_{0}; C_{2}; C_{4}; B_{0}; B_{2}; B_{4}; A_{0}; A_{2}; A_{4}; Chu_{1} (ℬ) :] (4-12)

To see concretely, why horizontal composition of Chu-spans is unlikely to work, consider

⟨φ_{1}, φ_{3}⟩ = [figure: B_{0}; B_{2}; B_{4}; A_{0}; A_{2}; A_{4}; φ_{0}; φ_{1}; φ_{2}; φ_{3}; a_{1}; a_{3}; b_{1}; b_{3}; f_{0}; f_{1}; f_{2}; f_{3}; f_{4}]↦[figure: B_{0}; B_{4}; A_{0}; A_{4}; φ_{2}⊗φ_{0}; φ_{3}⊗φ_{1}; b_{3}⊗b_{1}; a_{3}⊗a_{1}; f_{0}; f_{3}⊗f_{2}⊗f_{1}; f_{4}]= φ_{3} ⊗ φ_{1}  (4-13)

While for another pair of Chu-spans ⟨b_{1}, b_{3}⟩ [figure: ⟨γ_{1},γ_{3}⟩] ⟨c_{1}, c_{3}⟩ we can always construct a Chumorphism (γ_{3} ⊙ φ_{3}) ⊗ (γ_{1} ⊙ φ_{1}) [figure] (γ_{3} ⊗ γ_{1}) ⊙ (φ_{3} ⊗ φ_{1}) with trivial outer components, there are serious problems with this approach.

• In general, there are no identities for this operation. In fact, f_{2} admits a horizontal right or left identity iff f_{2} is an isomorphism.

• This proposed horizontal composition of Chu-spans does not extend to Chu-morphisms; the different variance in the even and odd 1-cell components prevents us from finding a 2-cell from f′_{3} ⊗ f′_{2} ⊗ f′_{1} to f_{3} ⊗ f_{2} ⊗ f_{1} , as required. In fact, it appears impossible to combine f_{1} , f_{2} and f_{3} into a 1-cell B_{0} [figure] A_{4} that avoids this problem.

5. Bicategories of Chu-chains

While the idea of composing Chu-spans horizontally seems to hold little promise, the left side of Diagram (4-13) indicates the possibility of extending the notion of Chu-span to link typed paths of 1-cells in ℬ by chaining matching Chu-spans together horizontally.

Since paths of length 0 are just objects, we expect to find ℬ at the bottom of a hierarchy of right-closed bicategories Chu_{n} (ℬ) , n ∈ . Moreover, infinite paths can be considered as well.

Our indexing scheme for the 1-cell-paths is intended to avoid the need for index-tuples or double indices, which would clutter up the notation even further.

5.1. Theorem. Let ℬ be right-closed with local pullbacks, and n ∈ . Typed 1-cell-paths a = ⟨A_{2i} [figure: a_{2i+1}] A_{2i+2} : i < n⟩ of length n as objects, typed Chu-span paths as 1-cells and the evident (2n + 1)-sequences of 2-cells in ℬ of alternating variance as new 2-cells form a right-closed bicategory Chu_{n} (ℬ) .

Similarly we obtain closed bicategories Chu_{}(ℬ), Chu_{}(ℬ) and Chu_{\} (ℬ), where the 1-cells A_{2i} [figure: a_{2i+1}] A_{2i+2} in the objects are indexed by , and \ , respectively.

Proof. For n ∈ {0, 1} we recover ℬ and Chu_{1} (ℬ) , respectively. For n > 1 the operations in Chu_{n} (ℬ) work component-wise, except the formation of right extensions and right liftings. These take the neighboring component into account, and only the rightmost component of a right extension has the shape of Diagram (3-07), while the other components have the shape of Diagram (3-09). For example, ⟨a_{1}, a_{3}⟩ [figure: ⟨φ_{1},φ_{3}⟩] ⟨b_{1}, b_{3}⟩ and ⟨a_{1}, a_{3}⟩ [figure: ⟨κ_{1},κ_{3}⟩] ⟨c_{1}, c_{3}⟩ have a right extension ⟨φ_{1}, φ_{3}⟩ ▷⟨κ_{1}, κ_{3}⟩ given by

[figure: A_{2}; A_{4}; B_{0}; B_{2}; B_{4}; C_{0}; C_{2}; C_{4}; φ_{1}; κ_{1}; ω_{0}; ev; ve; φ_{3}; κ_{3}; ω_{2}; λ_{2}; ev; ve; b_{1}; b_{3}; c_{1}; c_{3}; k_{1}; f_{2}; k_{3}; f_{4}; g_{0}; f_{1}◁k_{1}; f_{1}; k_{2}; g_{2}; f_{3}◁k_{3}; f_{2}▷k_{2}; f_{1}; k_{4}; f_{4}▷k_{4}]  (5-14)

The same phenomenon occurs for \ -indexed paths. For left extensions, the leftmost component of finite or -indexed paths for lack of a left neighbor will display an exceptional shape, whereas in the -indexed case no exceptional shapes occur.

5.2. Example. We call a linear bicategory ℬ in the sense of Remark 3.7 right-closed, if any A [figure: f] B has so-called left and right “linear adjoints” f^{⋄} := f ▷⊥_{A} and ^{⋄}f =: ⊥_{B}◁f , where ⊥ picks out the units for the second tensor ⊕. With A_{i} = A and B_{i} = B for all i ∈ 2 we may consider a -path of left and right “linear adjoints” of f

[figure: B; B_{0}; B; A; A_{0}; A; ve; ve; ev; ev; ⊥_{A}; ⊥_{A}; ⊥_{A}; ⊥_{B}; ⊥_{B}; ⊥_{B}; ^{⋄⋄}f; ^{⋄}f; f; f^{⋄}; f^{⋄⋄}; ...; ...]

The 2-cell f^{⋄} ⊗ f [figure: ev] ⊥_{A} should be viewed as the counit of the linear adjunction f^{⋄} ⊣ f ; its unit is given by (f^{⋄⋄} ⊗ f^{⋄} [figure: ev] ⊥_{B})^{⋄} = (⊤_{B} [figure: ev^{⋄}] f ⊕ f^{⋄}).

If ℬ happens to be cyclic ∗-autonomous (compare Definition 3.6), ^{⋄}f and f^{⋄} are coherently isomorphic to f^{∗}. Then -paths may be “curled up” into cyclic paths of lengths 1 . Thus we obtain a (−)^{∗}-preserving embedding of ℬ into cChu_{1} (ℬ) .

Let us now turn to the general cyclic case. What is cChu_{n} (ℬ) supposed to be for n 1 ? Recall that the cyclic ∗-autonomous bicategory cChu_{1} (ℬ) sits inside Chu_{1} (ℬ) as a non-1-full sub-bicategory containing all cyclic and hence reversible 1-cells. For n > 1 one can consider the corresponding sub-bicategory of Chu_{n} (ℬ) . However, cyclicity of Chu-span-paths in general will no longer insure unique reversibility as for n = 1 .

5.3. Example. For n = 2 a cyclic pair of Chu-spans ⟨a_{1}, a_{3}⟩ [figure: ⟨φ_{1},φ_{3}⟩] ⟨b_{1}, b_{3}⟩ has two different possibilities for reversal

[figure: A_{0}; A_{2}; A_{0}; B_{2}; B_{0}; B_{2}; φ_{3}; φ_{0}; φ_{1}; φ_{2}; b_{3}; b_{1}; a_{1}; a_{3}; f_{3}; f_{0}; f_{1}; f_{2}; f_{3}; B_{0}; B_{2}; B_{0}; A_{0}; A_{2}; A_{0}; φ_{0}; φ_{1}; φ_{2}; φ_{3}; a_{1}; a_{3}; b_{1}; b_{3}; f_{0}; f_{1}; f_{2}; f_{3}; f_{0}; A_{2}; A_{0}; A_{2}; B_{0}; B_{2}; B_{0}; φ_{1}; φ_{2}; φ_{3}; φ_{0}; b_{1}; b_{3}; a_{3}; a_{1}; f_{1}; f_{2}; f_{3}; f_{4}; f_{1}]

which might be denoted by ^{⋄}⟨φ_{1}, φ_{3}⟩ and ⟨φ_{1}, φ_{3}⟩^{⋄}, respectively. The operations ^{⋄}(−) and (−)^{⋄} are clearly inverses, cyclically shifting the rightmost, respectively, leftmost 2-cell to the other side, which after four iterations reproduces ⟨φ_{1}, φ_{3}⟩. In general, ^{⋄⋄}⟨φ_{1}, φ_{3}⟩ = ⟨φ_{3}, φ_{1}⟩ = ⟨φ_{1}, φ_{3}⟩^{⋄⋄} differs from ⟨φ_{1}, φ_{3}⟩.

We now obtain an analogon of a linear adjunction, compare Example 5.2: The same computation we utilized in the proof of Theorem 3.8 generates canonical 2-cells

⟨φ_{1}, φ_{3}⟩ ⊗^{⋄}⟨φ_{1}, φ_{3}⟩ [figure]^{⋄}⟨1_{b_{1}}, 1_{b_{3}}⟩ and ⟨φ_{1}, φ_{3}⟩^{⋄} ⊗ ⟨φ_{1}, φ_{3}⟩ [figure] ⟨1_{a_{1}}, 1_{a_{3}}⟩^{⋄}

However, for n > 1 it does not seem possible to combine ⊗, ^{⋄}(−) and (−)^{⋄} into a sensible ⊕-operation, and thus to obtain a linear structure, on the sub-bicategory of Chu_{n} (ℬ) generated by the cyclic Chu-spans.

Turning to infinite paths, every 1-cell a [figure: φ] b of Chu_{}(ℬ) is cyclic, but unless φ is periodic, all the 1-cells ^{⋄^{2n}}φ and φ^{⋄^{2n}}, n ∈ , will be distinct. Again, we obtain the counterpart to a linear adjunction, namely canonical 2-cells φ ⊗^{⋄}φ [figure]^{⋄}(1_{b}) and φ^{⋄} ⊗ φ [figure] (1_{a})^{⋄}, but no ⊕-operation.

Finally, even though none of the 1-cells in Chu_{}(ℬ) is cyclic, we can still define an operation (−)^{⋄} on all 1-cells a [figure: φ] b, which simply removes the leftmost 2-cell f_{1} ⊗ f_{0} [figure: φ_{0}] a_{1}. Now there is only one canonical 2-cell φ^{⋄} ⊗ φ [figure] (1_{a})^{⋄} without a counterpart: the absence of rightmost 2-cells in -indexed Chu-span paths prevents us from defining a ^{⋄}(−)-operation.

While the sub-bicategories of Chu_{n} (ℬ) , n > 1 , described in the preceding example may be of some independent interest, they, as well as Chu_{}(ℬ) , fail to be cyclic ∗-autonomous, apparently due to a shortage of 1-cells. To fix this, we propose a slight shift in perspective.

5.4. Definition. We write n_{−} and n_{∘} for the graphs with node-set n + 1 = { i ∈ : i ≤ n } and the successor relation, respectively, node-set n and the successor relation modulo n. Similarly, the graphs _{−} and _{∘} have node-sets , respectively, and the successor relation.

For simplicity, we will refer to graph morphisms from n_{∘} or from _{∘} into ℬ as ℬ-loops and to 1-cells between these as Chu-loops.

An object a of Chu_{n} (ℬ) can be viewed as a graph morphism from n_{−} into ℬ, mapping i to A_{2i} and ⟨i, i + 1⟩ to a_{i+1} . If the endpoints A_{0} and A_{2n} accidentally coincide, a may be used as domain or codomain for cyclic Chu-span paths as well as non-cyclic ones. In Example 5.3 the paths

A_{0} [figure: a_{1}] A_{2} [figure: a_{3}] A_{0} and A_{2} [figure: a_{3}] A_{0} [figure: a_{1}] A_{2}

are different images of the graph 2_{−} = (0 [figure] 1 [figure] 2), whereas they can be viewed as different presentations of a single image of 2_{∘} = (0 [figure] 1). Clearly, it is preferable to consider graphmorphisms from n_{∘} as objects, when we are interested just in cyclic ℬ-loops. Then Chu-loops take the shape of “triangulated cylinders”, which can readily be turned upside down. This operation ought to be an involution.

Observe that the graphs n_{∘} and _{∘} admit non-trivial endomorphisms, which are in fact automorphisms, in contrast to the “rigid” graphs n_{−} and _{−} . While any linear Chu-span path a [figure: φ] b has to start with a 1-cell A_{0} [figure: f_{0}] B_{0}, in case of a Chu-loop we can relax this requirement of matching base points and allow the codomain of the 1-cell originating at A_{0} , say f_{0} , to be B_{2k} for some k ∈ ; in case of loops of length n all subscripts are to be understood modulo 2n. The value k identifies an automorphism to be performed on the target ℬ-loop before building a Chu-loop. The latter will also contain 1-cells A_{−2k} [figure] B_{0} and B_{0} [figure] A_{2−2k}. By making k part of the 1-cells, we obtain ⟨k: φ⟩^{∗} = ⟨1 − k: φ^{∗}⟩.

5.5. Definition. For n > 0 the bicategory cChu_{n} (ℬ) has graph-morphisms n_{∘} [figure] ℬ as objects. Its 1-cells a [figure: ⟨k:φ⟩] b consist of an automorphism n_{∘} [figure: k] n_{∘} and a Chu-loop a [figure: φ] b ∘k, while 2-cells ⟨k: φ⟩ [figure: ρ] ⟨k′: φ′⟩ only exist for k = k′ and consist of 2-cells f_{2i} [figure: ρ_{i}] f′_{2i} and f′_{2i+1} [figure: ρ_{2i+1}] f_{2i+1}, i < n, subject to the evident axioms. cChu_{}(ℬ) is defined analogously.

5.6. Proposition. The bicategories cChu_{n} (ℬ) , n > 0 , and cChu_{}(ℬ) are cyclic ∗-auto-nomous, and the canonical functors into the subcategories of graphs with single object n_{∘}, respectively, _{∘} are bifibrations.

Proof. Cyclic ∗-autonomy is an immediate consequence of our considerations above. For example, the right extension of a [figure: ⟨p:κ⟩] c along a [figure: ⟨i:φ⟩] b is given by b [figure: ⟨p−i:φ▷κ⟩] c. All morphisms in the base being automorphisms, the existence of initial and terminal lifts is trivial.

Each of these rather simple bifibrations has a single fibre corresponding to the subcategory of Chu_{n} (ℬ) described in Example 5.3, respectively, Chu_{}(ℬ) .

For n > 0 the bicategories cChu_{n} (ℬ) clearly can be recovered within cChu_{}(ℬ) as non-1-full sub-bicategories of n-periodic ℬ-loops and n-periodic Chu-loops; this embedding preserves right extensions and right liftings. Thus in a sense cChu_{}(ℬ) addresses most aspects of cyclic ∗-autonomy related to ℬ. Of course, this rather satisfactory situation does not carry over to non-cyclic paths.

Our observations in the cyclic case so far raise at least two issues beyond the scope of the current paper: what is cChu_{0} (ℬ) supposed to be, and how can we combine all these single fibers into a more meaningful bifibration over some subcategory of grph, such that the total bicategory remains cyclic ∗-autonomous?

Clearly, the objects of a hypothetical bicategory cChu_{0} (ℬ) ought to be just ℬ-objects, respectively identity 1-cells. In order to guarantee uniquely reversible 1-cells, we may either consider isomorphisms, which yields a non-1-full sub-bicategory of Chu_{0} (ℬ) = ℬ, or adjoint equivalences, which yields a non-1-full sub-bicategory of cChu_{1} (ℬ) . We tend to prefer the second choice, but both allow us to at least partially address the second question.

Recall the geometric interpretation of 1-cells in the Chu-bicategories between ℬ-loops of the same size as triangulated cylinders. Those triangles, which carry an identity 2-cell, or at least the counit of an adjoint equivalence, should essentially be collapsible. In other words, if we extend two ℬ-loops a and b of potentially different size by inserting identity 1-cells until the resulting ℬ-loops a′ and b′ have the same length, then any Chu-loop a′ [figure: φ] b′∘k whose 2cell components into the newly inserted 1-cells are identities, or counits of adjoint equivalences, ought to qualify as a Chu-loop from a to b. This suggests some form of bisimulation between graphs as a candidate for the morphisms in the base of our hypothetical bifibration.

Of course, this also works for non-cyclic ℬ-paths, hence the bicategories Chu_{n} (ℬ) , n ∈ , should form the fibers of a larger entity as well.

Taking the speculation a bit further, we might even hope to mimic some form of cobordism in this context. For example, two disjoint ℬ-loops a and b could be linked to a single ℬ-loop c in the following fashion

[figure: Q; B_{0}; A_{0}; B_{4}; A_{2}; B_{2}; A_{4}; C_{0}; C_{6}; C_{10}; C_{2}; C_{8}; C_{4}; a_{1}; a_{3}; a_{5}; b_{1}; b_{3}; b_{5}; c_{1}; c_{3}; c_{5}; c_{7}; c_{9}; c_{11}]

Here the 1-cells A_{0}  [figure] C_{0}, A_{0}  [figure] C_{6} as well as B_{0}  [figure] C_{0} and B_{0}  [figure] C_{6} factor through a com-

mon object Q. The underlying grph-morphisms form a cospan

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •]

6. Symmetry and the game product

Interactions and games have lately been studied to find models for certain fragments of linear logic. They have mostly been represented in terms of trees (compare for example, [Bla92] [Abr97], [AJ94], [HO93], and [Hyl97]), but here we wish to use labeled transition systems (LTSs) instead. These can be viewed as graph morphisms from a small graph into rel, or even into spn, if one wants to allow repetition of labels along parallel arrows.

In order to model interaction, we wish to use bipartite graphs with two nodes, 0 and 1 , for Opponent and Player, respectively. If the interaction is to be strictly alternating, the homsets [0, 0] and [1, 1] will be empty, that is, there are no internal transitions. Call the other hom-sets a := [0, 1] and b := [1, 0] . A graph morphism into rel now specifies state sets f_{0} (for Opponent) and f_{1} (for Player) together with a function a [figure] rel⟨f_{0}, f_{1}⟩ = 𝒫(f_{0} × f_{1} ) assigning to each element x ∈ a the set of x-labeled moves from states in f_{0} to states in f_{1} , and a similar function b [figure] rel⟨f_{1}, f_{0}⟩ = 𝒫(f_{1} × f_{0} ). Of course, these functions are equivalent to relations f_{0} × f_{1} [figure: φ_{0}]a and f_{1} × f_{0} [figure: φ_{1}]b.

Observe that rel is monoidal closed with respect to the cartesian product ×: exponentiation is also given by ×, but now interpreted as a functor rel^{op} × rel [figure] rel. Consequently, the evaluation relations a × (a × b) [figure: ev]b and (a × b) × b [figure: ve]a as transposes of the diagonal on a × b satisfy ⟨w, ⟨x, y⟩, z⟩ ∈ ev, respectively, ⟨⟨x, y⟩, z, w⟩ ∈ ve iff x = w and y = z. Hence a bipartite LST may be identified with a cyclic Chu-span in the symmetric monoidal closed category ⟨rel, ×, 1⟩, compare Diagram (2-01).

Similarly, non-cyclic Chu-spans may be thought of as “tripartite” LTSs. If in the cyclic case a set f_{0}^{0} ⊆ f_{0} of initial states for Opponent is specified, we can define the subsets f_{1}^{2k+1} ⊆ f_{1} and f_{0}^{2k+2} ⊆ f_{0} reachable after 2k + 1 and 2k + 2 steps, respectively. The corresponding finite or -indexed path of Chu-spans can be thought of as the unfolding or trellis of the interaction.

If γ = ⟨g_{0}, γ_{0}, g_{1}, γ_{1}, g_{0}⟩ is another bipartite LTS with move sets c for Opponent and d for Player, a standard game-theoretic operation is to interleave γ with φ. Of particular interest are those cases, where only one participant is allowed to switch games. We distinguish ω := φ γ (only Opponent can switch) and π := φ γ (only Player can switch). The moves keep one state-component fixed, as indicated in the following schematic state transition diagram with x ∈ a, y ∈ b, z ∈ c and t ∈ d:

[figure: g_{0}; g_{1}; f_{0}; f_{1}; a + c; φ γ; b + d; f_{0}; f_{1}; g_{0}; g_{1}; c + b; φ γ; a + d; x; y; z; t; t; z; x; y]  \begin{aligned}w_{0} & = g_{0} × f_{0} \\ w_{1} & = g_{0} × f_{1} + g_{1} × f_{0} \\ p_{0} & = f_{0} × g_{0} + f_{1} × g_{1} \\ p_{1} & = f_{0} × g_{1} \end{aligned}

Switching between games is indicated by a change of the transition’s direction. In case of unrestricted interleaving, Opponent’s state set is f_{0} × g_{0} + f_{1} × g_{1} , while Player’s state set is g_{0} × f_{1} + g_{1} × f_{0} . Hence allowing only Opponent or Player to switch games effectively renders parts of their state sets unreachable.

Clearly, the operation is symmetric and we have

φ γ = (φ γ^{∗})^{∗} and (γ φ) δ = γ (φ δ)

We emphasize again that the domains and codomains of the cyclic Chu-spans do not need to match for these operations to make sense.

Recall that disjoint union + in rel provides the categorical product, in particular ∅ is the terminal object. Since the constructions above do not use 2-cells of rel, they must be available in any symmetric monoidal closed category 𝒱 with finite products. We denote the identity for ⊗ by ⊤, the terminal object by t, and write τ for the terminal projections. While two arbitrary cyclic Chu-spans

φ = [figure: •; •; •; •; φ_{0}; φ_{1}; a; b; f_{0}; f_{1}; f_{0}] and γ = [figure: •; •; •; •; γ_{0}; γ_{1}; c; d; g_{0}; g_{1}; g_{0}]

in general cannot be composed, we can compose appropriate partial “simplifications”:

[figure: •; •; •; •; •; •; φ_{0}; φ_{1}; γ_{0}; γ_{1}; d; b; t; c; a; f_{0}; f_{1}; f_{0}; g_{0}; g_{1}; g_{0}] ↦ γ^{t} ⊙ φ_{t} and [figure: •; •; •; •; •; •; γ_{0}; γ_{1}; φ_{0}; φ_{1}; b; d; t; a; c; g_{0}; g_{1}; g_{0}; f_{0}; f_{1}; f_{0}] ↦ φ^{t} ⊙ γ_{t}

where φ_{t} := τ_{+} ⊙ φ and φ^{t} := φ ⊙ τ^{+} , compare Remark 3.11. By the symmetry of ⊗, not only do the outer 1-cells z_{0} := g_{0} ⊗ f_{0} and f_{0} ⊗ g_{0} agree, but also both central pullbacks coincide, which because of the terminal t reduce to products:

z_{1} := g_{0} ▷f_{1} × g_{1} ◁f_{0} f_{0} ▷g_{1} × f_{1} ◁g_{0}

6.1. Definition. If γ^{t} ⊙ φ_{t} = ⟨z_{0}, ζ^{a}, z_{1}, ζ_{d}, z_{0}⟩ and φ_{t} ⊙ γ_{t} = ⟨z_{0}, ζ^{c}, z_{1}, ζ_{b}, z_{0}⟩, combining both composites yields

γ φ := [figure: •; •; •; •; ⟨ζ^{a},ζ^{c}⟩; ⟨ζ_{d},ζ_{b}⟩; a×c; d×b; z_{0}; z_{1}; z_{0}]

Even though the motivating example ⟨rel, ×, 1⟩ fails to have all pullbacks and hence does not allow the formation of a Chu-bicategory, let us collect the results above.

6.2. Proposition. For any symmetric monoidal closed category ⟨𝒱, ⊗, ⊤⟩ with finite products, up to natural isomorphism the operation on cyclic Chu-spans is symmetric, associative and has the identity Chu-span 1_{t} as a unit. Moreover, it extends to cyclic Chu-morphisms. Defining φ γ := (γ^{∗} φ)^{∗} from b × c to d × a yields an operation that satisfies

(γ φ) δ = (γ φ δ^{∗})^{∗} = γ (φ δ^{∗})^{∗} = γ (φ δ)

and extends to cyclic Chu-morphisms as well.

In the presence of pullbacks in 𝒱 we obtain

6.3. Theorem. If ⟨𝒱, ⊗, ⊤⟩ is symmetric monoidal closed and has finite limits, then the cyclic ∗- autonomous bicategory cChu_{1} (𝒱) is symmetric monoidal with respect to , which on objects coincides with ×.

6.4. Remark. Even though the operation of cChu_{1} (𝒱) coincides with the categorical product on objects, which thus trivially carry a cocommutative comonoid structure, in general cChu_{1} (𝒱) will not be a cartesian bicategory in the sense of Carboni and Walters [CW87]. They in addition required every 1-cell to be a lax comonoid homomorphism. In our context for a Chu-span a [figure: φ] b this amounts to requiring Chu-morphisms between (ι(b))^{+}⊙φ and (ι(a))^{+} , respectively, between (δ(b))^{+} ⊙ φ and (φ φ) ⊙ (δ(a))^{+} , subject to certain axioms (where a [figure: ι(a)] ⊤and a [figure: δ(a)] a × a constitute the product-induced comonoid structure on a in 𝒱). But without canonical 𝒱-morphisms between ⊤ and f , respectively, f ⊗ f and f for every 𝒱-object f , such Chu-morphisms need not exist.

Now the obvious question arises, how to interpret cyclic Chu-spans in 𝒱 as objects of a symmetric ∗-autonomous category with as tensor, (−)^{∗} as dualization and as internal hom. First we formulate the copy-cat strategy in terms of a Chu-morphism.

6.5. Definition. Given a cyclic Chu-span c [figure: γ] d, let η^{d} and η_{d} be the 2-cell components of γ^{t} ⊙ γ_{t}^{∗}, and let η^{c} and η_{c} be the 2-cell components of (γ^{∗})^{t} ⊙ γ_{t}. Setting (χ_{γ})_{0} = ⟨id_{g_{0}}^{▷}, id_{g_{1}}^{◁}⟩ and (χ_{γ})_{1} = ⟨γ_{0}, γ_{1}⟩ specifies a cyclic Chu-morphism

1_{d×c} = [figure: •; •; •; •; u_{l}; u_{r}; d×c; d×c; ⊤; d×c; ⊤] [figure: χ_{γ}] γ γ = [figure: •; •; •; •; ⟨η_{d},η_{c}⟩; ⟨η^{d},η^{c}⟩; d×c; d×c; g_{0}▷g_{0}×g_{1}◁g_{1}; g_{1}⊗g_{0}; g_{0}▷g_{0}×g_{1}◁g_{1}]

This suggests the possibility of encoding arrows (that is, strategies for games) from a [figure: φ] b to c [figure: γ] d by means of cyclic Chu-morphisms into φ γ. Hence given another cyclic Chuspan e [figure: δ] f, we wish to combine cyclic Chu-morphisms

[figure: b × c; ξ; φ γ; ρ; a × d; and; d × e; ϑ; γ δ; σ; c × f]  (6-15)

in such a way that allows us to obtain a Chu-span morphism into b × e [figure: φ δ] a × f . But rather than simply forming

[figure: d × e × b × c; ϑ ξ; (δ γ) (φ δ); σ ρ; c × f × a × d]

and projecting out the required domain and codomain, we wish to take the partial matches between the domains and codomains into account, in other words, we wish to form a trace. So far the existence of finite products was sufficient to perform the Chu-span compositions we needed. However, we now will be concerned with non-trivial composites, which depend on the existence of pullbacks. Although rel in general lacks pullbacks, the following construction is of course inspired by the idea of hiding appropriate pairs of moves as indicated above.

6.6. Definition. In the spirit of Definition 6.1 we compose cyclic Chu-spans

ξ = [figure: •; •; •; •; ξ_{0}; ξ_{1}; b×c; a×d; x_{0}; x_{1}; x_{0}] and υ = [figure: •; •; •; •; υ_{0}; υ_{1}; d×e; c×f; y_{0}; y_{1}; y_{0}] to υ _{d×c} ξ = [figure: •; •; •; •; ζ_{0}; ζ_{1}; b×e; a×f; y_{0}⊗x_{0}; z_{1}; y_{0}⊗x_{0}]

by combining

[figure: •; •; •; •; •; •; ξ_{0}; ξ_{1}; γ_{0}; γ_{1}; b; f; c×f; a×d; d; d×e; b×c; x_{0}; x_{1}; x_{0}; y_{0}; y_{1}; y_{0}] ↦ υ_{f}^{d} ⊙ ξ_{d}^{b}  and  [figure: •; •; •; •; •; •; γ_{0}; γ_{1}; ξ_{0}; ξ_{1}; a×d; a; c×f; c; b×c; d×e; e; y_{0}; y_{1}; y_{0}; x_{0}; x_{1}; x_{0}] ↦ ξ_{a}^{c} ⊙ υ_{c}^{e}

where the unlabeled 2-cells denote projections compare Proposition 3.11. In this case z_{1} is obtained by pulling back a transpose y_{o} ▷x_{1} [figure] y_{0} ▷(c × d) ◁x_{0} [figure] y_{1}◁x_{0} of the induced cospan

[figure: x_{1} ⊗ x_{0}; ⟨ξ_{0};π_{c},ξ_{1};π_{d}⟩; c × d; ⟨υ_{1};π_{c},υ_{0};π_{d}⟩; y_{0} ⊗ y_{1}]

6.7. Theorem. For every symmetric monoidal closed category 𝒱, cyclic Chu-spans as objects and cyclic Chu-span morphisms into φ γ as morphisms from φ to γ form a symmetric ∗-autonomous category [cChu_{1} (ℬ)]^{}with tensor .

Proof. Setting λ := φ γ and μ := γ δ and, we only need to construct a Chu-span morphism from ω := λ _{d×c} μ to ν := φ δ.

Although ⊗ need not preserve products, we certainly obtain 2-cells from

w_{0} = m_{0} ⊗ ℓ_{0} = (g_{0} ▷d_{0} × g_{1} ◁d_{1}) ⊗ (f_{0} ▷g_{0} × f_{1} ◁g_{1})

into (f_{0} ▷g_{0} ⊗ g_{0} ▷d_{0}) × (f_{1} ◁g_{1} ⊗ g_{1} ◁d_{1}) and from there into (f_{0} ▷d_{0}) × (f_{1} ◁d_{1}) = n_{0} . On the other hand, transposing

f_{0} ⊗ d_{1} ⊗ (g_{1} ◁d_{1}) [figure: id⊗ve] f_{0} ⊗ g_{1}  and  (f_{0} ▷g_{0}) ⊗ f_{0} ⊗ d_{1} [figure: ev⊗id] g_{0} ⊗ d_{1}

induces 2-cells from n_{1} = f_{0} ⊗ d_{1} to (g_{1} ◁d_{1})▷(g_{1} ⊗ f_{0}) and to (d_{1} ⊗ g_{0}) ◁(f_{0} ▷g_{0}) , and from there via symmetry and projections in the exponent to m_{0} ▷ ℓ_{1} and m_{1} ◁ ℓ_{0} . The universal property of the pullback w_{1} now yields the desired 2-cell n_{1} [figure] w_{1}.

The functoriality of _{d×c} is obvious. Given cyclic Chu-span morphisms as in Diagram (6-15), we define the composition of σ _{d×c} ρ with the Chu-span morphism constructed above to be the composite arrow σ ∘ρ from φ to δ. The remaining verifications of the associativity and of the fact that the copy-cat Chu-spans are units for this composition are lengthy but straightforward.

Acknowledgment

I am grateful to my colleagues at the TU Braunschweig for inspiring discussions, and to three anonymous referees for helpful comments that lead to substantial improvements of this paper. The diagrams were produced with XY-pic 3.7.

References

[Abr97] Samson Abramsky. Semantics of interaction: an introduction to game semantics. In Andrew M. Pitts and Peter Dybjer, editors, Semantics and Logics of Computation, Publications of the Newton Institute, chapter 1, pages 1–31. Cambridge University Press, Cambridge, 1997.

[AJ94] S. Abramsky and R. Jagadeesan. Games and full completeness for multiplicative linear logic. Journal of Symbolic Logic, 59:543–574, 1994.

[Bar79] Michael Barr. ∗-Autonomous categories, volume 752 of LNM. Springer-Verlag, Berlin, Heidelberg and New York, 1979.

[Bar95] Michael Barr. Non-symmetric ∗-autonomous categories. Theor. Comp. Sci., 139:115–130, 1995.

[Bar96] Michael Barr. The Chu construction. Theory Appl. Categ., 2(2):17–35, 1996.

[Ben67] Jean Bénabou. Introduction to bicategories. In Reports of the Midwest Category Seminar. I, volume 47 of LNM, pages 1–77. Springer-Verlag, Berlin, Heidelberg and New York, 1967.

[Bla92] Andreas Blass. A game semantics for linear logic. Ann. Pure Appl. Logic, 56:183– 220, 1992.

[Bor94] Francis Borceux. Handbook of Categorical Algebra 1, Basic Category Theory, volume 50 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 1994.

[Chu79] P.-H. Chu. Constructing ∗-autonomous categories, volume 752 of LNM, pages 103– 137. Springer-Verlag, Berlin, Heidelberg and New York, 1979.

[CKS00] J. R. B. Cockett, J. Koslowski, and R. A. G. Seely. Introduction to linear bicategories. Math. Structures Comput. Sci., 10:165–203, 2000.

[CW87] A. Carboni and R. F. C. Walters. Cartesian bicategories I. J. Pure Appl. Algebra, 49:11–32, 1987.

[HO93] J. M. E. Hyland and C.-H. L. Ong. Fair games and full completeness for multiplicative linear logic without the mix-rule. Working Draft, July 1993.

[Hyl97] Martin Hyland. Game semantics. In Andrew M. Pitts and Peter Dybjer, editors, Semantics and Logics of Computation, Publications of the Newton Institute, chapter 4, pages 131–184. Cambridge University Press, Cambridge, 1997.

[Kos01] Jürgen Koslowski. Beyond the Chu construction. Appl. Categ. Structures, 9(2):153– 171, 2001.

[Pav97] Duško Pavlović. Chu I: cofree equivalences, dualities and ∗-autonomous categories. Math. Struct. in Comp. Sci., 7:49–73, 1997.

[See87] R. A. G. Seely. Linear logic, ∗ -autonomous categories, and cofree coalgebras. In John W. Gray and Andre Scedrov, editors, Categories in Computer Science and Logic, volume 92 of Contemorary Mathematics, pages 371–382, Boulder, CO, June 1987. American Mathematical Society, Providence, RI, 1989.

[Str91] Ross Street. Quantum Groups: an entrée to modern algebra. Macquarie University, ftp://ftp.mpce.mq.edu.au/pub/maths/TeX/Quantum, 1991.

[SW78] Ross Street and R. F. C. Walters. Yoneda structures on 2-categories. Journal of Algebra, 50:350–379, 1978.

Institut für Theoretische Informatik TU Braunschweig, Mühlenpfordstr. 23 38106 Braunschweig, Germany Email: koslowj@iti.cs.tu-bs.de

This article may be accessed via WWW at http://www.tac.mta.ca/tac/ or by anonymous ftp at ftp://ftp.tac.mta.ca/pub/tac/html/volumes/17/6/17-06.{dvi,ps,pdf}

THEORY AND APPLICATIONS OF CATEGORIES (ISSN 1201-561X) will disseminate articles that significantly advance the study of categorical algebra or methods, or that make significant new contributions to mathematical science using categorical methods. The scope of the journal includes: all areas of pure category theory, including higher dimensional categories; applications of category theory to algebra, geometry and topology and other areas of mathematics; applications of category theory to computer science, physics and other mathematical sciences; contributions to scientific knowledge that make use of categorical methods. Articles appearing in the journal have been carefully and critically refereed under the responsibility of members of the Editorial Board. Only papers judged to be both significant and excellent are accepted for publication. The method of distribution of the journal is via the Internet tools WWW/ftp. The journal is archived electronically and in printed paper format.

Subscription information. Individual subscribers receive (by e-mail) abstracts of articles as they are published. Full text of published articles is available in .dvi, Postscript and PDF. Details will be e-mailed to new subscribers. To subscribe, send e-mail to tac@mta.ca including a full name and postal address. For institutional subscription, send enquiries to the Managing Editor, Robert Rosebrugh, rrosebrugh@mta.ca.

Information for authors. The typesetting language of the journal is TEX, and L^{A}TEX2e is the preferred flavour. TEX source of articles for publication should be submitted by e-mail directly to an appropriate Editor. They are listed below. Please obtain detailed information on submission format and style files from the journal’s WWW server at http://www.tac.mta.ca/tac/. You may also write to tac@mta.ca to receive details by e-mail.

Managing editor. Robert Rosebrugh, Mount Allison University: rrosebrugh@mta.ca

TEXnical editor. Michael Barr, McGill University: mbarr@barrs.org

Transmitting editors.

Richard Blute, Université d’ Ottawa: rblute@uottawa.ca Lawrence Breen, Université de Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of North Wales: r.brown@bangor.ac.uk Aurelio Carboni, Università dell Insubria: aurelio.carboni@uninsubria.it Valeria de Paiva, Xerox Palo Alto Research Center: paiva@parc.xerox.com Ezra Getzler, Northwestern University: getzler(at)math(dot)northwestern(dot)edu Martin Hyland, University of Cambridge: M.Hyland@dpmms.cam.ac.uk P. T. Johnstone, University of Cambridge: ptj@dpmms.cam.ac.uk G. Max Kelly, University of Sydney: maxk@maths.usyd.edu.au Anders Kock, University of Aarhus: kock@imf.au.dk Stephen Lack, University of Western Sydney: s.lack@uws.edu.au F. William Lawvere, State University of New York at Buffalo: wlawvere@acsu.buffalo.edu Jean-Louis Loday, Université de Strasbourg: loday@math.u-strasbg.fr Ieke Moerdijk, University of Utrecht: moerdijk@math.uu.nl Susan Niefield, Union College: niefiels@union.edu Robert Paré, Dalhousie University: pare@mathstat.dal.ca Jiri Rosicky, Masaryk University: rosicky@math.muni.cz Brooke Shipley, University of Illinois at Chicago: bshipley@math.uic.edu James Stasheff, University of North Carolina: jds@math.unc.edu Ross Street, Macquarie University: street@math.mq.edu.au Walter Tholen, York University: tholen@mathstat.yorku.ca Myles Tierney, Rutgers University: tierney@math.rutgers.edu Robert F. C. Walters, University of Insubria: robert.walters@uninsubria.it R. J. Wood, Dalhousie University: rjwood@mathstat.dal.ca