Theory and Applications of Categories, Vol. 14, No. 7, 2005, pp. 125–156.

A MONADIC APPROACH TO POLYCATEGORIES

JÜRGEN KOSLOWSKI

Abstract. In the quest for an elegant formulation of the notion of “polycategory” we develop a more symmetric counterpart to Burroni’s notion of “T-category”, where T is a cartesian monad on a category 𝒳 with pullbacks. Our approach involves two such monads, S and T, that are linked by a suitable generalization of a distributive law in the sense of Beck. This takes the form of a span T S [figure: ω] ST in the functor category [𝒳, 𝒳] and guarantees essential associativity for a canonical pullback-induced composition of S-T-spans over 𝒳, identifying them as the 1-cells of a bicategory, whose (internal) monoids then qualify as “ω-categories”. In case that S and T both are the free monoid monad on set , we construct an ω utilizing an apparently new classical distributive law linking the free semigroup monad with itself. Our construction then gives rise to socalled “planar polycategories”, which nowadays seem to be of more intrinsic interest than Szabo’s original polycategories. Weakly cartesian monads on 𝒳 may be accommodated as well by first quotienting the bicategory of 𝒳-spans.

0. Motivation and Outline

Lately multicategories have received renewed attention in the field of higher-dimensional category theory, cf., [Lei98] and [Her00], respectively. But in categorical logic, where they were introduced originally by Jim Lambek in the 1960’s [Lam69], without imposing further structure multicategories correspond to a rather simple logical system. Basically the comma separating objects in the domain list is interpreted as a conjunction. Cut-elimination holds for (in hindsight) fairly trivial reasons. On the other hand, polycategories, where lists of objects are allowed not just as domains but also as codomains of morphisms, at least in their planar variant are of much greater interest in categorical logic. It was shown by Robin Cockett and Robert Seely [CS92, CS97] that planar polycategories are closely related to linearly distributive categories. These in turn correspond precisely to the tensor-par fragment of linear logic. There the cut-elimination procedure is highly nontrivial, and has an interesting graph-theoretic representation in terms of proof nets.

While small multicategories have been characterized elegantly as monoids in a bicategory of set -spans with free set -monoids as domains, a special case of Albert Burroni’s notion of T-category [Bur71], no such description of small polycategories seems to have been available so far. To keep this paper self-contained, Section 1 reviews the basic set-up for multicategories before addressing Manfred E. Szabo’s original definition of polycat-

Received by the editors 2004-01-15 and, in revised form, 2005-01-09. Transmitted by Richard Blute. Published on 2005-05-08. 2000 Mathematics Subject Classification: 18C15; 18D05. Key words and phrases: cartesian monad, S-T-span, (cartesian) distributive law, multicategory,

(planar) polycategory, fc-polycategory, associative double semigroup.

\begin{matrix}c \\ ◯ \end{matrix} Jürgen Koslowski, 2005. Permission to copy for private use granted.

egories [Sza75]. The language of circuit diagrams turns out to be a valuable tool in this context. In Section 2 we recall a family of grph -based multicategories (nowadays known as “fc -multicategories”) 𝒞-spn _{□} that for suitable choices of 𝒞 provides a convenient environment for stating our problem and later for the solution.

We then investigate distributive laws in the sense of Jon Beck [Bec69] between cartesian monads S and T on a category 𝒳 with pullbacks in Section 3. If these are cartesian in a suitable sense, such distributive laws indeed allow the construction of new bicategories with the same objects as 𝒳 and “S-T-spans” as 1-cells, i.e., spans with domains of the form XS and codomains of the form Y T, cf., Theorem 3.2. Monoids in such bicategories can then be viewed as “S-T-categories”. For polycategories, however, where S and T coincide with the free monoid monad (_)^{∗} on set , there is no distributive law to get this construction off the ground.

Clearly, in this case a more symmetric substitute for distributive laws would be desirable. Utilizing the decomposition of (_)^{∗} into the free semigroup monad and the exception monad, in Section 4 we define a relation on (_)^{∗∗} by means of three cartesian distributive laws that still allows us to construct a bicategory of (_)^{∗}-(_)^{∗}-spans. Its monoids turn out to be precisely the small planar polycategories. Szabo’s original polycategories require a different construction and a span instead of a relation. However, as the language of circuit diagrams shows, only the notion of planar polycategory admits a 2-dimensional generalization, where objects are replaced by typed 1-cells. The resulting “fc -polycategories” have essentially the same characterization as planar polycategories, but over the base grph rather than set . In view of other shortcomings of Szabo’s original concept this suggests that planar polycategories may indeed be the “correct” generalization of multicategories.

One of the three distributive laws used in the construction above behaves like a “complementation” on the free semigroup monad and seems to be new. We identify its algebras as associative double semigroups. In fact, the free such structure on a set B can be extended from B^{++} to an associative double monoid structure on B^{∗∗}.

Section 5 addresses the fundamental question, which spans between T S and ST correctly generalize (cartesian) distributive laws and provide an essentially associative composition for S-T-spans over 𝒳 with canonical units. This contrasts with Elisabeth Burroni’s approach [Bur73], who weakened the notion of associativity for her notion of D-catégories in order to encompass the non-cartesian power-set monad. Our definition of cartesian generalized distributive law is best formulated in the fc -multicategory [𝒳, 𝒳]-spn _{□} of spans and morphisms in [𝒳, 𝒳]. This clarifies an apparent asymmetry in our notion of cartesian distributive law (Section 3), thus justifying the added generality.

Finally, in Section 6 we show how by first quotienting the bicategory 𝒳-spn the constructions outlined above can be used even for weakly cartesian monads. In particular this applies to the free commutative monoid monad, which fails to be cartesian. We than adapt the construction for planar polycategories to obtain symmetric polycategories in a similar fashion.

In preliminary form some of these results were presented at CTCS 2002 in Ottawa.

1. Polycategories informally

In 1969 Lambek introduced multicategories as a framework for his logic-inspired syntactic calculus [Lam69]. In terms of pasting diagrams or circuit diagrams [CKS00] (which we prefer here), the theory of multicategories concerns the compositional properties of “multi-2-cells” g_{0}, g_{1}, …, g_{n−1} [figure: β] h of the form

[figure: ...; g_{1}; •; •; g_{n−1}; •; g_{0}; h; β; •]  or  ^{g_{0}} ^{g_{1}} ^{...} ^{g_{n−1}}_{h}^{β}  (1-00)

The input or source is a finite, possibly empty, list of “1-cells”, while the output or target is a single 1-cell. These 1-cells may even be typed: the nodes (in the pasting version), respectively, the regions (in the circuit version) between the 1-cells then provide the corresponding “0-cells” or “objects” serving as sources (left), respectively, targets (right) for the 1-cells cf. Example 2.1.

We may compose two multi-2-cells vertically by substituting the first into the second at a specific matching 1-cell. (Since inputs may occur repeatedly, the exact position of the composition has to be specified.) This corresponds to the cut operation of logic for sequents with one conclusion. Besides associativity of binary substitution and the existence of “identity 2-cells” 1_{f} for each 1-cell f, Lambek also had to require “commutativity”: for any distinct i, j < n in Diagram (1-00) two multi-2-cells with codomains g_{i} and g_{j}, respectively, may be substituted into β “in parallel”, i.e., in this case the order of substitution does not matter.

The need for commutativity indicates a shortcoming of binary substitution as the principal operation in this context. Consider, instead, the operation of “multi-substitution” that combines a finite list of multi-2-cells and a single multi-2-cell such that the list of targets of the former and the source of the latter match, e.g.,

Φ_{0} Φ_{1}  ... Φ_{n−1} h α_{0} α_{1}  α_{n−1} β g_{0} g_{1}  g_{n−1}

We use double lines with capital Greek labels to indicate lists, possibly empty, of (typed) 1-cells. If precisely one α_{i} is not an identity 2-cell, we recover binary substitution. And if multi-substitution is associative, Lambek’s commutativity requirement is an easy consequence of the the existence of identity 2-cells. Also notice that composing the empty list of multi-2-cells with an input-free multi-2-cell β leaves β unchanged.

Already in 1971 this view of multicategories with multi-substitution as basic operation was subsumed by Albert Burroni’s notion of (internal) T-category (for a cartesian monad T on a category with pullbacks, cf. Section 2). Just as small categories are monads in the bicategory of set -spans, small multicategories arise as monads in a bicategory of T - spans C_{0}T [figure: s] C_{1} [figure: t] C_{0}, where T is the free monoid monad on set [Bur71, Proposition III.3.23].

Advances in higher-dimensional category theory led to renewed interest in T-catego-ries in the mid-1990’s, notably by Tom Leinster [Lei98] and by Claudio Hermida [Her00]. More recently, Maria Manuel Clementino and Walter Tholen have proposed starting from a bicategory of 𝒱-valued relations or matrices for symmetric monoidal closed 𝒱 instead of from a bicategory of spans [CT03]. This leads to a notion of “𝒱-enriched T-category”.

It is important to note that á priori there is no provision for horizontally composing multi-2-cells, not even 1-cells. Such an operation ⊗, called “tensor product” in the untyped case, only becomes available in the context of what Hermida called “representable multicategories”, cf. [Her00, Definition 8.3] and Definition 1.1 below.

Manfred E. Szabo in 1975 generalized multicategories to polycategories [Sza75] by also allowing finite lists of 1-cells as output of what we now call “poly-2-cells”. (Notice that in 1974 Ellen Redi, supervised by Jaak Hion, used the term “polycategories” for multicategories in the sense of Lambek [Red74].) Szabo considered a composition modeled on the binary cut operation in logic for sequents with multiple inputs and outputs, implicitly linked by conjunction (“and”) and disjunction (“or”), respectively. Such cuts can only be performed along single 1-cells: the implicit links between two 1-cells joining two poly-2-cells would differ at the input and the output side, cf. Remark 1.2(a) below. In terms of circuit diagrams,

the binary cut of  ^{Γ}_{Δ_{0}} _{x} _{Δ_{1}}^{α}  and ^{Γ_{0}} ^{x} ^{Γ_{1}}_{Δ}^{β}  along x results in ^{Γ_{0}}  ^{Γ} ^{Γ_{1}}_{Δ_{0}} _{Δ} _{Δ_{1}}^{α}^{β}^{x}  (1-01)

Besides the obvious requirements of associativity and the existence of identity 2-cells, Szabo also had to impose a commutativity condition: whenever

Γ_{1}_{Δ_{0}} _{x} _{Δ_{1}}^{α_{1}}  and  ^{Γ_{3}}_{Δ_{2}} _{y} _{Δ_{3}}^{α_{3}}  are to be composed with ^{Γ_{0}} ^{x} ^{Γ_{2}} ^{y} ^{Γ_{4}}_{Δ}^{β}  (1-02)

along x and y, respectively, the order of this composition does not matter, provided that one of Δ_{0} and Δ_{2} and one of Δ_{1} and Δ_{3} is empty. Vertical reflection yields a second such commutativity condition.

Even though locally the output of α and the input of β remain planar, the composed diagram in (1-01) may fail to be planar. This phenomenon does not occur for multicategories and presents an obstacle to considering typed 1-cells in this context. Restricting the admissible cuts by requiring one of Γ_{0} and Δ_{0} as well as one of Γ_{1} and Δ_{1} to be empty will avoid this problem and results in four planar “shapes” of binary cuts:

Γ_{0}  ^{Γ} ^{Γ_{1}}_{Δ}^{α}^{β}^{x}  ,  ^{Γ} ^{Γ_{1}}_{Δ_{0}} _{Δ}^{α} ^{β}^{x}  ,  ^{Γ}_{Δ_{0}} _{Δ} _{Δ_{1}}^{α}^{β}^{x}  ,  ^{Γ_{0}}  ^{Γ}_{Δ} _{Δ_{1}}^{α}^{β}^{x}  (1-03)

For planar polycategories only binary cuts of this form are allowed.

1.1. Definition. (Hermida [Her00, Definition 8.3], cf. [CKS03, Section 2.1]) A multi-2-cell Γ [figure: α] x is said to represent the list Γ of (typed) 1-cells as input, provided that in any context Γ_{0}, Γ_{1} cutting with α at x, as in the first instance of Diagram (1-03), induces bijections between poly-2-cells

{Γ_{0}, x, Γ_{1}  [figure] Δ \atop =}Γ_{0}, Γ, Γ_{1}  [figure] Δ

that are natural in Γ_{0}, Γ_{1} and Δ, in the sense that they commute with all binary cut operations on any of the 1-cells in Γ_{0}, Γ_{1} and Δ.

Dual notion: The comulti-2-cell x [figure: β] Δ as in the third instance of Diagram (1-03) represents Δ as output.

A (planar) polycategory is called representable, if every (typed) list of 1-cells can be represented both as input and as output.

1.2. Remarks.

(a) Clearly, it suffices to require the representability of (typed) binary lists x, y and nullary lists ε_{A}, where A ranges through the 0-cells that provide types for the 1cells. For a given choice of representing multi-2-cells, we denote their outputs by x ⊗ y and ⊤_{A}, respectively. Dually, the inputs of chosen representing comulti-2-cells will be denoted as x ⊕ y and ⊥_{A}.

In a representable polycategory two poly-2-cells can only be linked by a list Γ of 1-cells, if Γ can be represented both as input and as output by the same 1-cell. This trivially is the case for singleton lists, and also in compact-closed polycategories, where the so-called tensors ⊗ and ⊕ agree, but not in general.

(b) Multiplicative linear logic can be modeled by ∗-autonomous categories. Dropping the explicit negation led J. R. B. Cockett and R. A. G. Seely to introduce “weakly distributive categories” [CS92] and [CS97], later renamed to “linearly distributive categories”, that carry two monoidal structures with “tensors” ⊗ and ⊕ linked by so-called “linear distributions”

A ⊗ (B ⊕ C) [figure] (A ⊗ B) ⊕ C and (A ⊕ B) ⊗ C [figure] A ⊕ (B ⊗ C)  (1-04)

subject to certain coherence conditions. In view of (a) these are just representable planar polycategories. Tensors that need not be symmetric are most naturally realized as compositions of typed 1-cells, i.e., in a 2-dimensional setting. This led to the notion of linear bicategory in [CKS00].

(c) Planar polycategories support a notion of adjunction, cf. [CKS00] and [CKS03]. Such “linear adjunctions” may be used to simulate negation in categorical logic. The restriction to singleton outputs for multi-2-cells is a major obstacle to expressing such a concept in multicategories.

(d) Unfortunately, important intended examples for the original notion of polycategory turned out not to satisfy the commutativity requirement. If a category 𝒞 with finite products and coproducts is “distributive” in the sense that all canonical morphisms

A × B + A × C [figure: δ_{ℓ}] A × (B + C) and A × C + B × C [figure: δ_{r}] (A + B) × C

are isomorphisms, consider 𝒞-objects as untyped 1-cells and 𝒞-morphisms from the product of Γ to the coproduct of Δ as poly-2-cells. A composition as in (1-01) that is associative and has the expected identities can be realized via

\xymatrix{∏ Γ_{0} × ∏ Γ × ∏ Γ_{1} \ar[d]_{id ×α×id} \ar@{.>}[r] & ∑ Δ_{0} + ∑ Δ + ∑ Δ_{1} \\ ∏ Γ_{0} × (∑ Δ_{0} + X + ∑ Δ_{1}) × ∏ Γ_{1} \ar[r] & ∑ Δ_{0} + (∏ Γ_{0} × X × ∏ Γ_{1}) + ∑ Δ_{1} \ar[u]_{id +β+id}}

where X is a 𝒞-object and the second step first utilizes the inverses of δ_{ℓ} and δ_{r} and then appropriate projections in the outer summands.

Cockett and Seely showed [CS97, Proposition 3.1] that this composition satisfies Szabo’s commutativity requirement iff 𝒞 is a pre-order, i.e., a distributive lattice. This confirmed lingering doubts that distributive categories captured the proof theory for the ∧/∨-fragment of intuitionistic logic.

Concretely, commutativity may already fail in the following situation

1  1 1  0  1 id  id id 0 0

The two possible compositions result in the inclusions of 1 = 1 × 1 into 1 + 1, which differs from 1, unless 𝒞 is a poset.

(e) The intersecting 1-cells in the resulting diagram of (1-01) cannot be simulated in a planar fashion by special poly-2-cells that interchange a pair of 1-cells, since that would lead, e.g., to diagrams of the form

z  Γ y  Δ α γ β y x z

If one cuts α and γ along y first, the resulting poly-2-cell will be linked with β along two 1-cells, which in general is not allowed.

While in a representable polycategory with symmetric tensors ⊗ and ⊕ all wires can intersect, the restrictions imposed on intersecting wires in case of non-symmetric tensors are rather curious. In fact, we do not know any natural examples of this phenomenon. To properly express symmetry without reference to representability one should replace free monoids by free commutative monoids, i.e., sets of bags or multi-sets, cf., Section 6.

Planar or not, the binary cuts above ought to be special cases of composing suitably matching lists ⟨Γ_{i} [figure: α_{i}] Δ_{i}:i < n ⟩ and ⟨ Φ_{j} [figure: β_{j}] Ψ_{j}:j < m ⟩ of poly-2-cells simultaneously or in parallel, i.e., of “poly-substitution”. Which matching conditions does this impose on the list ⟨ Δ_{i} : i < n ⟩ of codomain lists, and the list ⟨ Φ_{j} : j < m ⟩ of domain lists, and how can they be expressed at the level of the free monoid monad? Clearly, in the planar case all possible parallel compositions can be expressed in terms of sequential binary compositions. However, non-planarity may lead to parallel composites not accounted for by Szabo’s notion of polycategory.

1.3. Example. [Planar compositions] It is easy to see that there are 2^{|n−1|} possible geometric configurations for a planar composition using n > 0 1-cells (cf. Example 4.1). Up to n ≤ 3 and modulo horizontal and vertical reflections these are

\begin{matrix}α_{0} \\ β_{0} \end{matrix} , ^{α_{0}} ^{α_{1}}_{β_{0}} , ^{α_{0}} ^{α_{1}} ^{α_{2}}_{β_{0}}  ^{α_{0}} ^{α_{1}}_{β_{0}} _{β_{1}}  (1-05)

(The inputs of the α_{i} and the outputs of the β_{j} are irrelevant and have been left off.)

1.4. Example. [Non-planar compositions] The smallest non-planar circuit diagrams have three 1-cells and four multi-2-cells. In case of four 1-cells we already have eighteen non-planar geometric configurations; modulo reflections:

(3)^{α_{0}} ^{α_{1}}_{β_{0}} _{β_{1}}^{1}^{2} ^{0} , _{(4.0)}^{α_{0}} ^{α_{1}} ^{α_{2}}_{β_{0}} _{β_{1}}^{3} ^{1}^{2} ^{0}  _{(4.1)}^{α_{0}} ^{α_{1}} ^{α_{2}}_{β_{0}} _{β_{1}}^{3}^{1} ^{0} ^{2}  _{(4.2)}^{α_{0}} ^{α_{1}} ^{α_{2}}_{β_{0}} _{β_{1}}^{1}^{2} ^{0}^{3}  _{(4.3)}^{α_{0}} ^{α_{1}} ^{α_{2}}_{β_{0}} _{β_{1}}^{3} ^{1}^{2}^{0}  _{(4.4)}^{α_{0}} ^{α_{1}} ^{α_{2}}_{β_{0}} _{β_{1}}^{1}^{2} ^{0} ^{3}  (1-06)

Configurations (4.0) – (4.2) derive from (3) by adding a new input to β_{0}, while in (4.3) and (4.4) β_{1} gets another input. No further non-planar configurations with four 1-cells arise from the last two configurations of Diagram (1-05), hence our list is exhaustive. The 1-cell labels indicate a possible order for sequential composition. While this need not be unique, in configurations (4.0) and (4.1) the order of occurrence is determined for the β_{i}. Notice that sequential composition according to (1-01) in (4.1) leads to 1-cell no. 3 intersecting all outputs of β_{0} rather than its inputs, as in this more compact presentation. A similar phenomenon occurs in (4.2) with 1-cell no. 3 and the outputs of β_{1} (and also in (4.4), if one starts composing with 1-cell no. 2 rather than no. 0). However, not all configurations are legitimate in Szabo’s sense:

(4)^{α_{0}} ^{α_{1}}_{β_{0}} _{β_{1}} ,  _{(5.0)}^{α_{0}} ^{α_{1}} ^{α_{2}} ^{α_{3}}_{β_{0}} _{β_{1}}^{f}  ,  _{(5.1)}^{α_{0}} ^{α_{1}} ^{α_{2}} ^{α_{3}}_{β_{0}} _{β_{1}} ^{g} ,  _{(6.0)}^{α_{0}} ^{α_{1}} ^{α_{2}} ^{α_{3}} ^{α_{4}}_{β_{0}} _{β_{1}}  ,  _{(6.1)}^{α_{0}} ^{α_{1}} ^{α_{2}} ^{α_{3}} ^{α_{4}}_{β_{0}} _{β_{1}}  (1-07)

In configuration (4) the result of any threefold sequential composition is linked along two 1-cells with the remaining poly-2-cell, which in general is not allowed. The same phenomenon occurs, whenever the undirected graph determined by the 1-cells between prospective domain and codomain contains a cycle and thus fails to be simply connected in the sense that removing any 1-cell increases the number of components.

The other configurations, even though simply connected, still cannot be sequentialized. Responsible are the interlocking “wedges” ⟨α_{0}, β_{0}, α_{2}⟩ and ⟨α_{1}, β_{1}, α_{3}⟩ in case of (5.0), respectively, ⟨α_{0}, β_{0}, α_{3}⟩ and ⟨α_{1}, β_{1}, α_{4}⟩ in case of (6.0). E.g., in configuration (5.0) early introduction of β_{0} effectively makes α_{1} inaccessible and thus prevents β_{1} from being introduced. Similarly, early introduction of β_{1} blocks off α_{2} and hence β_{0}. Analogous wedge arguments apply to configurations (5.1) and (6.1).

Notice, however, that replacing f in configuration (5.0) by a 1-cell between α_{1} and β_{0}, or between α_{2} and β_{1}, yields a sequentiazable configuration. Replacing g in (5.1) by a 1-cell between α_{1} and β_{1} or between α_{2} and β_{0} has a similar effect. Hence the criterion of interlocking wedges needs further refinement in as far as certain poly-2-cells then must not be connected by 1-cells.

1.5. Theorem. For non-empty lists ⟨Γ_{i} [figure: α_{i}] Δ_{i} : i < n ⟩ and ⟨ Φ_{j} [figure: β_{j}] Ψ_{j} : j < m ⟩ of poly-2-cells a legitimate sequentiaizable composition á la Szabo is specified by a permutation of the concatenated codomains Δ_{i}, i < n, realized by potentially intersecting 1-cells, that agrees with the concatenated domains Φ_{j}, j < m, such that

(S0) the induced undirected graph is simply connected;

(S1) each codomain Δ_{i} and each domain Φ_{j} remains locally planar;

(S2) whenever there is a sub-configuration of solid 1-cells of the form

α_{i} ^{α_{j}} ^{α_{k}} ^{α_{l}}_{β_{p}} _{β_{q}}  or _{β_{i}} _{β_{j}} _{β_{k}} _{β_{l}}^{α_{p}} ^{α_{q}}  or ^{α_{i}} ^{α_{j}} ^{α_{k}} ^{α_{l}}_{β_{p}} _{β_{q}}  or _{β_{i}} _{β_{j}} _{β_{k}} _{β_{l}}^{α_{p}} ^{α_{q}}

where the poly-2-cells in the domain, respectively codomain, need not be immediate neighbors, precisely one further 1-cell has to exist along the dotted lines.

Proof. What remains to be shown is that in case (S1) is satisfied, non-sequentiazability implies the existence of a cycle or one of the forbidden configurations.

For positions v, w < m of the poly-2-cells in the codomain we write v ⊏ w provided that in sequential composition, due to their respective inputs, β_{v} at position v has to precede β_{w} at position w. This irreflexive relation ⊏ decomposes as ⊏_{0} + ⊏_{1}, where the inputs of the poly-2-cells in the specified positions have either no (⊏_{0}), or at least one (⊏_{1}) common poly-2-cell in the domain. It is immediately clear that v ⊏_{0} w iff the non-empty input of β_{v} in position v is confined between two subsequent 1-cells in the input of β_{v} in position v, i.e.,

... ^{α_{i}} ^{α_{j}} ^{...} ^{α_{k}} ^{α_{l}} ^{...}_{β_{v}} _{β_{w}}  or ^{...} ^{α_{i}} ^{α_{j}} ^{...} ^{α_{k}} ^{α_{l}} ^{...}_{β_{w}} _{β_{v}}

Otherwise the order of sequential composition would not be determined, or the first forbidden sub-configuration would occur. In particular, ⊏_{0} is irreflexive and transitive, hence there can be no ⊏_{0}-cycles.

On the other hand, if u ⊏_{1} v, one of the following sub-configurations has to exist

α_{j} ^{α_{k}} ^{α_{l}}_{β_{u}} _{β_{v}}^{0} ^{2}^{1} ^{3} or ^{α_{j}} ^{α_{k}} ^{α_{l}}_{β_{u}} _{β_{v}}^{3}^{1} ^{0} ^{2} or ^{α_{j}} ^{α_{k}} ^{α_{l}}_{β_{v}} _{β_{u}}^{3} ^{1}^{2} ^{0} or ^{α_{j}} ^{α_{k}} ^{α_{l}}_{β_{v}} _{β_{u}}^{2} ^{0} ^{1}^{3}  (1-08)

cf., configurations (4.0) and (4.1) of Diagram (1-06). Obviously a cycle with respect to ⊏_{1} induces a cycle in the induced graph, thus violating (S0).

Thus in any ⊏-cycle an instance of u ⊏_{1} v ⊏_{0} w has to occur. Without loss of generality we may assume u < v. The first diagram in (1-08) then leads to three configurations

α_{i} ^{α_{j}} ^{α_{k}} ^{α_{l}} ^{α_{m}}_{β_{u}} _{β_{v}} _{β_{w}}  and ^{α_{i}} ^{α_{j}} ^{α_{k}} ^{α_{l}} ^{α_{m}}_{β_{u}} _{β_{w}} _{β_{v}}  and ^{α_{i}} ^{α_{j}} ^{α_{k}} ^{α_{l}} ^{α_{m}}_{β_{w}} _{β_{u}} _{β_{v}}

The forbidden sub-configurations for positions u and v, respectively, w imply that further inputs of β_{u} cannot originate right of α_{l}, respectively, left of α_{i}, which implies u ⊏_{0} w. A similar argument for the second diagram in (1-08) shows that in

α_{i} ^{α_{j}} ^{α_{k}} ^{α_{l}} ^{α_{m}}_{β_{u}} _{β_{v}} _{β_{w}}  and ^{α_{i}} ^{α_{j}} ^{α_{k}} ^{α_{l}} ^{α_{m}}_{β_{u}} _{β_{w}} _{β_{v}}  and ^{α_{i}} ^{α_{j}} ^{α_{k}} ^{α_{l}} ^{α_{m}}_{β_{w}} _{β_{u}} _{β_{v}}

further inputs of β_{u} must originate neither left of α_{j}, nor right of α_{m}, which again implies u ⊏_{0} w. Hence any ⊏-cycle reduces to a ⊏_{0}-cycle, which is impossible.

Condition (S0) not only prevents poly-2-cells α_{i} in the domain and β_{j} in the codomain from being linked by more than one 1-cell, and circuit diagrams from having more than one component (in particular, parallel 1-cells only make sense either as outputs or as inputs of a poly-2-cell). It also prevents poly-2-cells with empty codomains or domains from appearing among other poly-2-cells in Γ or Δ, respectively (cf. Remark 1.2(a)).

For planar polycategories there is no need to mention a permutation. Only (S0) has to be required, the other conditions are satisfied automatically.

In case of multicategories, “composability” is determined by a match between the first factor’s list of codomains and the domain of the second factor; it is a total and cototal relation on (_)^{∗}. Due to the problems with poly-2-cells having empty domain or codomain, for planar polycategories the composability relation on (_)^{∗∗} can be neither total nor cototal, but should be symmetric. Since different wires in circuit diagrams can carry the same label, configurations (4.0) and (4.1) in Diagram (1-06) show that in general polycategories two lists of poly-2-cells can be composed in more than one way. Consequently, instead of a composability relation on (_)^{∗∗} we need a span that specifies all possible compositions.

2. Spans and monads

Let 𝒳 be a cartesian category, i.e., every cospan A [figure: f] C [figure: g] B has a pullback. Choosing a pullback for each cospan yields the 1-cell composition for a bicategory 𝒳-spn with the same objects as 𝒳 and spans A [figure: k_{0}] K [figure: k_{1}] B as 1-cells A [figure: ⟨k_{0},K,k_{1}⟩] B. For brevity we will set k := ⟨k_{0}, K, k_{1}⟩, or refer to ⟨k_{0}, k_{1}⟩ when the span’s center is understood. Given another span A [figure: p] B with center P, a 2-cell k [figure: u] p is an 𝒳-morphism K [figure: u] P satisfying u; p_{i} = k_{i}, i < 2. The composition A [figure: l;k] C of spans A [figure: k] B [figure: l] C with centers K and L derives from the chosen pullback of K [figure: k_{1}] B [figure: l_{0}] L by extending its “legs” with k_{0} and l_{1}, respectively. Since the choice of pullbacks need not be canonical in any sense, the associativity of this composition and the properties of the evident identity 1-cells only hold up to coherent isomorphism. Hence in general we obtain a bicategory rather than a 2-category.

It may aid the intuition to think of endo-spans C_{0} [figure: ∂] C_{0} as “𝒳-graphs” with C_{0} as “object-of-nodes”. If equipped with a monad structure, i.e., 2-cells ∂; ∂ [figure: c] ∂, serving as associative binary “composition”, and C_{0} [figure: i] ∂, providing identities for this composition, we view them as “𝒳-categories”.

Functors and natural transformations are called cartesian, if they preserve pullbacks, respectively, have naturality squares that are pullbacks. Burroni [Bur71] realized that a cartesian monad S = ⟨S, μ, η⟩ (all components cartesian) could be used to “skew” the span-construction above by applying S to the spans’ sources (we are reserving the name T for the “target-monad”, cf. below). This results in a bicategory S-spn with the same objects as 𝒳, 𝒳-spans of the form AS [figure: k] B as 1-cells A[figure: k] B (called S-spans) and the evident 2-cells inherited from 𝒳-spn . The composition of A[figure: k] B with B [figure: l] C in S-spn results from the composition in 𝒳-spn

AS [figure: Aμ] ASS [figure: kS] BS [figure: l] C  (2-00)

where we interpret AS [figure: Aμ] ASS as trivial span with an 𝒳-identity as right component. Identity 1-cells in S-spn now have the form A = ⟨Aη, A, 1_{A}⟩. An alternative description of this composition is presented in Diagram (2-01) below.

Aurelio Carboni and Peter Johnstone [CJ95] have identified monads S = ⟨S, μ, η⟩ over set where μ and η are cartesian natural transformations and S preserves wide pullbacks with “strongly regular theories”; these employ finitary operators and equations with the same variables in the same order on both sides without repetition. In particular, every corresponding monad is cartesian. However, the theory of commutative monoids is not strongly regular and its monad is not cartesian, cf., e.g., [Lei98].

In view of Remark 1.2(e) this is bad news, since the free commutative monoid monad ought to produce symmetric polycategories. Hence in Section 6 we investigate a weaker conditions on a monad that still allows us to construct bicategories of modified spans.

For cartesian S, monoids in S-spn yield interesting generalizations of 𝒳-categories. We recall a specific example that will help us later.

2.1. Example. [fc -multicategories] On the category [(• [figure] •), set ] of directed graphs the free category monad, which we also denote by (_)^{∗}, is cartesian. Its (_)^{∗}-categories have been considered already by Burroni [Bur71] (who called them simply “multicategories”). More recently, they were popularized under the name “fc -multicategories” by Leinster [Lei99], [Lei02]. Given such a structure

(H [figure: s; t] O)^{∗} [figure: ⟨d_{00},d_{01}⟩] (M [figure: ∂_{0}; ∂_{1}] V) [figure: ⟨d_{10},d_{11}⟩] (H [figure: s; t] O)

the elements of M, or multi-2-cells, have “vertical 1-cells” in V as “horizontal domains and codomains”. Their “vertical domains and codomains” are typed paths of “horizontal 1cells” in H, respectively, single horizontal 1-cells, which in turn have sources and targets in a set O of objects or 0-cells. The horizontal/vertical terminology is geared towards pasting diagrams rather than generalized circuit diagrams, cf.,

[figure: A_{0}; l; g_{0}; A_{1}; g_{1}; ...; g_{n−1}; A_{n}; r; B_{0}; h; β; B_{1}] vs.  ^{g_{0}}  ^{g_{1}}  ^{...} ^{g_{n−1}}_{h}^{l}  ^{r}^{A_{0}} ^{A_{1}}  ^{A_{n}}^{B_{0}}  ^{B_{1}}^{β}

where we have distinguished the vertical 1-cells l and r.

Notice that the vertical composition defined in a (_)^{∗}-category automatically yields a category structure on the span O [figure: d_{01}] V [figure: d_{11}] O.

In case of V = 1 = O we recover Lambek’s original multicategories, while just requiring V = O yields typed multicategories, or “multi-bicategories”. In this case the only vertical 1-cells are identities and can be left off. On the other hand, replacing the free category monad by the identity monad yields double-categories, which hence may be viewed as “fc -monoidal categories”.

The spans in any category 𝒞 can be organized into an fc -multicategory: objects are those of 𝒞, horizontal 1-cells are the spans, while vertical 1-cells are 𝒞-morphisms. A multi-2-cell

[figure: A_{0}; l; G_{0}; g_{0,0}; g_{0,1}; A_{1}; G_{1}; g_{1,0}; g_{1,1}; ...; G_{n−1}; g_{n−1,0}; g_{n−1,1}; A_{n}; r; B_{0}; H; h_{0}; h_{1}; β; B_{1}]

is a functor from the category of cones for the dotted zig-zag above consisting of n − 1 cospans to the category of cones for the two solid cospans such that a cone and its image agree on the components at G_{0} and at G_{n−1}. If 𝒞 has pullbacks, up to isomorphism we can choose a composite of the spans on top, say, A_{0} [figure: g] A_{n} with center G. Then β uniquely corresponds to a 𝒞-morphism G [figure: b] H satisfying g_{0}; l = b; h_{0} and g_{1}; r = b; h_{1}. In this case the fc -multicategory of spans and 𝒞-morphisms is representable in the sense of Hermida and may be identified with the double-category 𝒞-spn _{□} with 𝒞-objects as objects, 𝒞spans as horizontal and 𝒞-morphisms as vertical 1-cells, and the 2-cells indicated above. The subtle relationship between multicategories and monoidal categories, at least over the base set , is analyzed in [Her00, Section 8].

Now we can interpret the composition (2-00) of 1-cells in S-spn as a multi-2-cell in 𝒳-spn _{□} whose underlying 𝒳-morphism is an isomorphism

[figure: ASS; Aμ; kS; BS; l; C; id; AS; k;l; ∼; C]  (2-01)

The construction of S-categories is biased in favor of sources. To achieve a balance we would like to apply either the same, or possibly a second cartesian monad T = ⟨T, ν, ψ⟩ on the target side. I.e., we wish to consider S-T-spans of the form AS [figure: k] BT as 1-cells A[figure: k]B. If the composition is to proceed along the same lines as in the multi-case (think of T as the identity monad), this raises the question of how to fill the gap in

[figure: ASS; Aμ; kS; BT S; ?; BST; lT; CT T; Cν; AS; k;l; ∼; CT]  (2-02)

Intuitively, we wish to compose “S-tuples” of “poly-2-cells” from A to B with “T -tuples” of “poly-2-cells” from B to C. This ought to require a span between “S-tuples” of “T -tuples” of codomains in B and “T -tuples” of “S-tuples” of domains in B, preferably natural in B, that specifies all admissible composites. But which spans between T S and ST in [𝒳, 𝒳] will yield an essentially associative composition of S-T-spans with canonical identities?

3. Distributive laws

Natural candidates for completing the diagram in (2-02) are of course the B-components of distributive laws T S [figure: λ] ST (or in the opposite direction) in the sense of Beck [Bec69], i.e., of natural transformations compatible with both S and T, in the sense that

\xymatrix{T SS \ar@{=>}[r]^{λS} \ar@{=>}[dd]_{T μ} & ST S \ar@{=>}[r]^{Sλ} & SST \ar@{=>}[dd]^{μT} &  & T \ar@{=>}[r]^{id} \ar@{=>}[dd]_{T η} & T \ar@{=>}[dd]^{ηT} \\  &  &  & and \\ T S \ar@{=>}[rr]_{λ} &  & ST &  & T S \ar@{=>}[r]_{λ} & ST}  (3-00)

\xymatrix{T T S \ar@{=>}[r]^{T λ} \ar@{=>}[dd]_{νS} & T ST \ar@{=>}[r]^{λT} & ST T \ar@{=>}[dd]^{Sν} &  & S \ar@{=>}[r]^{id} \ar@{=>}[dd]_{ψS} & S \ar@{=>}[dd]^{Sψ} \\  &  &  & and \\ T S \ar@{=>}[rr]_{λ} &  & ST &  & T S \ar@{=>}[r]_{λ} & ST}  (3-01)

While over 𝒳 = set distributive laws only realize functions, mapping the domain’s codomain 1-cells to the codomain’s domain 1-cells (or vice versa), we expect them to serve as building blocks for certain spans that specify the various ways in which the domain’s codomain 1-cells and the codomain’s domain 1-cells can be connected.

3.1. Definition. We call a distributive law T S [figure: λ] ST cartesian, if λ is a cartesian natural transformation and if in addition the squares in (3-00) are pullbacks.

The apparent asymmetry of the latter notion, which puts no extra requirements on the diagrams in (3-01), will be explained in Section 5.

3.2. Theorem. Given cartesian monads S = ⟨S, μ, η⟩ and T = ⟨T, ν, ψ⟩ on 𝒳, any cartesian distributive law T S [figure: λ] ST induces a bicategory λ-spn with the same objects as 𝒳, spans AS [figure: k] BT in 𝒳 as 1-cells A[figure: k]B and the evident 2-cells inherited from 𝒳-spn . The 1-cell composition A[figure: k]B [figure: l]C is realized as a 2-cell in 𝒳-spn _{□} whose center is an isomorphism

[figure: ASS; Aμ; kS; BT S; Bλ; BST; lT; CT T; Cν; AS; k;l; ∼; CT]

and the identity 1-cells are canonically given by the units η and ψ.

Proof. This will follow from Theorem 5.6, but a direct proof is quite easy.

3.3. Example. For T = Id _{𝒳} and λ = 1_{S} we recover S-multicategories.

3.4. Remark. Besides strongly regular theories, endo-functors of the form (_) + C for any set C (of nullary operations or constants), and of the form (_) × M for any monoid M (of unary operations) induce cartesian monads on set [CJ95]. Already Beck observed [Bec69] that canonical distributive laws

\xymatrix{XT + C \ar[r]^{id +Cφ} & XT + CT \ar[r]^{[ι_{X}T,ι_{C}T]} & (X + C)T}

respectively

\xymatrix{XT × M \ar[r]^{[ ⟨id ,m⟩:m∈M ]} & (X × M)T}

connect these types of monads with any other monad T = ⟨T, ν, φ⟩ on set . Here ⟨id , m⟩ is the embedding of X as the m-th slice of X × M and we regard XT × M as the M-fold coproduct of XT. Because set is extensive, for cartesian T the canonical transformation T^{2}+ [figure]+ T induced by the universal property of coproducts is cartesian. This renders both these distributive laws cartesian. Hence we may repeatedly apply various instances of the special monads above, which combine to a cartesian monad S, and obtain a canonical cartesian distributive law T S [figure] ST.

3.5. Example. The free monoid monad ⟨(_)^{∗}, μ, η⟩ on 𝒳 = set is of course the composite of the free semigroup monad H = ⟨(_)^{+}, μ_{+}, η_{+}⟩ and the exception monad E = ⟨(_) + 1, μ_{1}, η_{1}⟩, both cartesian. The cartesian distributive law EH [figure: ζ] HE underlying this composition eliminates the new symbol of BE = B + 1 from all strings in BEH = (B + 1)^{+}.

Unfortunately, even though ζ is a cartesian natural transformation, it is not a cartesian distributive law: the compatibility diagram with η_{+} in (3-00) fails to be a pullback. Hence Theorem 3.2 cannot be applied.

The construction of Remark 3.4 yields a cartesian distributive law HE [figure: ι] EH that includes B^{∗} into (B + 1)^{+} by mapping the empty word of B to the singleton word over B + 1 consisting of the new symbol, leaving all non-empty words unchanged.

With H = S and E = T the dual construction of Theorem 3.2 yields a bicategory of spans, in which monads are close relatives of multicategories: for a set B of 1-cells the poly-2-cells have non-empty inputs and at most one output. Binary composition is given by cut along single 1-cells. Poly-2-cells with no output only compose with the empty string of poly-2-cells. Alternatively, we can introduce a new 1-cell ε ∉ B and its identity-2-cell 1_{ε}, the only poly-2-cell with ε occurring in the input. For all other poly-2-cells the inut belongs to B^{+}, while the output belongs to B + {ε}.

4. Polycategories revisited, and some of their relatives

For planar polycategories strings of poly-2-cells admit at most one composition. The corresponding composability relation is symmetric but not total. A distributive law on the free monoid monad cannot capture this, we will need a proper relation between T S and ST. As the example of general polycategories shows, even spans T S [figure: ω_{0}] W [figure: ω_{1}] ST, or T S [figure: ω] ST for short, in the category [𝒳, 𝒳] of endo-functors and natural transformations may be necessary (cf., Theorem 1.5).

Before studying this in Section 5, let us see how some examples, in particular planar polycategories, fit into the proposed framework. After replacing T S [figure: λ] ST in Theorem 3.2 by T S [figure: ω] ST the proposed composition A[figure: k]B [figure: l]C depends on the pullbacks

[figure: Z; z_{0}; z_{1}; X; x_{0}; x_{1}; Y; y_{0}; y_{1}; KS; k_{1}S; BW; Bω_{0}; Bω_{1}; LT; l_{0}T; BT S; BST]  (4-00)

If the original monads S and T happen to be composites, as in case of our motivating example, we may try to build ω_{0} and ω_{1} from suitably well-behaved distributive laws.

4.1. Example. [Planar polycategories] Let both S and T be the free monoid monad over set , induced by the non-cartesian distributive law EH [figure: ζ] HE of Example 3.5.

To find candidates for W, we list further distributive laws involving H and E: Besides the the cartesian canonical inclusion HE [figure: ι] EH, cf. Example 3.5 and Remark 3.4, there is a second distributive law EH [figure: ξ] HE. It maps non-empty strings over B+1 containing the new symbol to the empty word in B^{∗}. However, ξ fails to be cartesian.

The involution EE [figure: ϑ] EE that interchanges the two new points of course is cartesian. But there also is an involution HH [figure: κ] HH: each set BHH = B^{++} carries a natural refinement ordering, as a disjoint union of atomic Boolean algebras, indexed by the nonempty words over B: for n ≥ 1 and Γ = ⟨b_{i}:i < n⟩ the corresponding Boolean algebra has top element ⟨Γ⟩ = Γ(B^{+}η_{+}), bottom element ⟨ ⟨b_{i}⟩:i < n ⟩ = Γ(Bη_{+})^{+} and as atoms those words over B^{+} of length n − 1 that contain singletons with the exception of precisely one doubleton ⟨b_{k}b_{k+1}⟩ for k < n − 1. Consequently, a complementation operation is available on B^{++}, which is the B-component of κ.

Jointly, ϑ and κ provide a complementation on W = H^{2}E^{2} = (_)^{++}+1+1 = (_)^{+∗}+1: think of BW as B^{++} extended with global complementary bottom and top elements that may be identified with the empty word ε_{B^{∗}} ∈ B^{∗∗} and with the B^{∗}η-image ⟨ε_{B}⟩ of the empty word ε_{B} ∈ B^{∗}. Let us interpret Diagram (4-00) when (HE)^{2} [figure: ω] (HE)^{2} is given by

(HE)^{2} [figure: HιE] H^{2}E^{2} [figure: H^{2}ϑ] W [figure: κE^{2}] H^{2}E^{2} [figure: HιE] (HE)^{2}  (4-01)

The set X consists of those lists of poly-2-cells, whose list of codomains (in B^{∗∗}) is either empty, or consists of one empty list, or only contains one or more non-empty lists. The same characterization applies to the list of domains of the lists of poly-2-cells in Y. The composable pairs in Z ⊆ X × Y have codomain- and domain-lists, respectively, that complement each other, like (f, g)(h)(k, l)(m) and (f)(g, h, k)(l, m) in case of

α_{0} α_{1} α_{2} α_{3} β_{0} β_{1} β_{2} f g h k l m

Non-singleton lists over B^{∗} containing the empty word do not have complements. Although no longer total, in the planar case the composability relation is still single-valued. Because of its symmetry, the inner endo-span on B^{∗∗} can be reversed without changing the composition. Moreover, since ϑ and κ are involutions, the same result will be achieved by using κϑ on one side of the span.

The reader may check the identities for this composition of modified spans and its associativity. It will also follow from Proposition 5.8 below. Clearly the monoids in this bicategory are precisely the planar polycategories of Section 1;

The following observation concerning κ was first made by Robin Cockett.

4.2. Proposition. The distributive law κ above has as algebras precisely the associative double semigroups, i.e., sets X with two associative binary operations ∘ and ⋆ that are associative with respect to the other, i.e.,

(a ∘ b) ⋆ c = a ∘ (b ⋆ c) and (a ⋆ b) ∘ c = a ⋆ (b ∘ c) for a, b, c ∈ X  (4-02)

Proof. Any set of the form B^{++} has the desired algebraic structure: take for ∘ the concatenation operation on B^{++}, and for ⋆ the “De Morgan dual” of ∘, i.e., Γ ⋆ Δ := (Γκ ∘ Δκ)κ for Γ, Δ ∈ B^{++}. The associativity of ⋆ and the axioms (4-02) follow immediately, once we observe

Γ ⋆ Δ = ⟨Γ_{i} : i < |Γ| − 1⟩ ∘ ⟨Γ_{|Γ|−1} · Δ_{0}⟩ ∘ ⟨Δ_{j} : 0 < j < |Δ|⟩  (4-03)

where · denotes the concatenation on B^{+}.

We wish to extend a function B [figure: f] D into an associative double semigroup ⟨D, ∘, ⋆⟩ to a homomorphism B^{++} [figure: f̄] D. Recall the partial ordering on B^{++} described in Example 4.1 and the complementation κ. Since in B^{++} we have ⟨(a)(b)⟩κ = ⟨(ab)⟩, we can extend f by mapping singleton words over B^{+}, i.e., essentially words over B, to the ⋆-product of the f-images of its letters. Non-singleton words over B^{+} are then mapped to the ∘- product of the ⋆-products of its constituent B^{+}-elements. This clearly is a homomorphism. If B^{++} [figure: h] D is a homomorphic extension of f, in particular we have ⟨(a)⟩h = ⟨(a)⟩f̄, a ∈ B. But ⟨(a)⟩ ∘ ⟨(b)⟩ = ⟨(a)(b)⟩ and ⟨(a)⟩ ⋆ ⟨(b)⟩ = ⟨(ab)⟩ in B^{++} force h to agree with f̄. This establishes (_)^{++} as left adjoint to the forgetful functor from the category ads of associative double semigroups and homomorphisms to set .

For an Eilenberg-Moore algebra ⟨B, β⟩ define associative binary operations ∘ and ⋆ on B by a ∘ b := ⟨(a)(b)⟩β and a ⋆ b := ⟨(ab)⟩β. These clearly obey axioms (4-02).

4.3. Remark. Axioms (4-02) closely resemble the structural morphisms for a linearly distributive category, cf. Diagram (1-04), except that the latter in general are not isomorphisms. The name “linearly distributive category” was evidently chosen to distinguish the linear logic approach to capturing the ∧∨-fragment of intuitionistic logic from Szabo’s attempt employing distributive categories. However, the axioms (4-02) clearly express a notion of associativity rather than distributivity, and the same applies to the structural morphisms (1-04).

4.4. Remark. Since the complementation canonically extended from B^{++} to B^{++} + 1 + 1, one might attempt to extend the concatenation ∘ on B^{++} and its “De Morgan dual” ⋆ in a similar fashion. Of course, ∘ is the restriction of the concatenation on B^{∗∗} with the empty word ε_{B^{∗}} ∈ B^{∗∗} as neutral element. On the other hand Formula (4-03) is meaningful on B^{∗+}, which hence becomes a monoid with neutral element ⟨ε_{B}⟩. Clearly, the axioms (4-02) extend to B^{∗+}. Extending the monoid ⟨B^{∗+}, ⋆, ⟨ε_{B}⟩⟩ by a new neutral element, namely ε_{B^{∗}}, somewhat surprisingly establishes B^{∗∗} as an “associative double monoid” with ε_{B^{∗}} serving double duty as neutral element. In fact, there are no other options. The requirement

ε_{B^{∗}} ⋆ Δ = ε_{B^{∗}} ⋆ (ε_{B^{∗}} ∘ Δ) = (ε_{B^{∗}} ⋆ ε_{B^{∗}}) ∘ Δ  (4-04)

for any Δ ∈ B^{∗+} prevents the ⋆-multiplication with ε_{B^{∗}} from shrinking any of its arguments in length. In particular, ⟨ε_{B}⟩ cannot be neutral for ⋆ on all of B^{∗∗}.

The assumption ε_{B^{∗}} ⋆ε_{B^{∗}} := ⟨ε_{B}⟩ by (4-04) implies ε_{B^{∗}} ⋆Δ = ⟨ε_{B}⟩∘Δ for all Δ ∈ B^{∗∗}. However, for Δ ≠ ε_{B^{∗}} we get Δ = ⟨ε_{B}⟩ ⋆ Δ = (ε_{B^{∗}} ⋆ ε_{B^{∗}}) ⋆ Δ, and ε_{B^{∗}} ⋆ (ε_{B^{∗}} ⋆ Δ) = ⟨ε_{B}, ε_{B}⟩ ∘ Δ, violating the associativity of ⋆.

4.5. Example. [Polycategories] The composition for general polycategories, as described in Section 1, cannot be captured by the complementation on H^{2}E^{2}, except for the global (and the local) top and bottom elements.

For non-empty lists ⟨Γ_{i} [figure: α_{i}] Δ_{i} : i < n ⟩ and ⟨ Φ_{j} [figure: β_{j}] Ψ_{j} : j < m ⟩ of poly-2-cells with non-empty outputs and inputs, respectively, the existence of a permutation from the concatenation of the Δ_{i} to the concatenation of the Φ_{j} subject to the conditions (S0)– (S2) defines a span H^{2} [figure: υ_{0}] U [figure: υ_{1}] H^{2}. Combining this with the complementation of the global top and bottom elements yields a span (HE)^{2} [figure: ω] (HE)^{2} with center W := UE^{2} via

(HE)^{2} [figure: HιE] H^{2}E^{2} [figure: Hϑ] UE^{2} [figure: υE^{2}]H^{2}E^{2} [figure: HιE] (HE)^{2}

While this clearly yields an associative composition with the desired units, we do not know, whether this span can be expressed in terms of distributive laws.

4.6. Example. [fc -polycategories] Generalizing Example 2.1, over the category grph of directed graphs we also may apply the free category monad to the codomain of spans. The free category (H [figure: s; t] O)^{∗} can again be constructed in two stages: first we form the set H^{+} of non-empty typed paths, and then we add empty paths ε_{H}^{A} for each object A ∈ O. Again, H^{++} is closed under complementation and can be extended by ⟨ε_{H}^{A}⟩ and by its complement ε_{H^{∗}}^{A}, A ∈ O. The rest of the construction proceeds as before.

Monads in this setting might be called “fc -polycategories” and will be studied elsewhere. Their composition “by triangulation” is indicated by

[figure: Γ_{0}; Γ_{1}; Γ_{2}; Δ_{0}; Δ_{1}; u_{0};v_{0}; u_{3};v_{2}; α_{0}; α_{1}; α_{2}; β_{0}; β_{1}; ;; ;; x_{0}; x_{1}; x_{2}; x_{3}; u_{0}; u_{1}; u_{2}; u_{3}; v_{0}; v_{1}; v_{2}]

The circled semi-colons indicate the vertical composition of vertical 1-cells. If V = O, all vertical 1-cells are identities, ι_{A}, and may be left off. We then obtain typed polycategories (these must be planar, as explained in Section 1), also known as “poly-bicategories”, cf. [CKS03]. Even if none of the α’s has an input and none of the β’s has an output, the vertical 1-cells serve to “anchor” the resulting poly-2-cell.

Two horizontal 1-cells A [figure: f] B and B [figure: g] A are adjoint, if poly-2-cells τ (the unit) and γ (the counit) exist such that

[figure: f; f; ι_{A}; ι_{B}; τ; 1_{f}; 1_{f}; γ; ;; ;; f; g; f; ι_{A}; ι_{A}; ι_{B}; ι_{A}; ι_{B}; ι_{B}] =  ^{f}_{f}^{ι_{A}}  ^{ι_{B}}^{1_{f}}

and the other composition of γ with τ results in the identity for g.

4.7. Example. [Ribbons] In (fc -) polycategories vertical wires (= horizontal 1-cells) could be replaced by “ribbons” that may be twisted, indicated by an integer “winding number”. Realizing this feature by restricting attention to (graphs with edge) sets of the form B × ZZ would equip the poly-2-cells with an integer component without natural interpretation. Instead, the free semigroup functor (_)^{+} should be replaced by the functor ((_) × ZZ)^{+}, with ZZ serving as a monoid of unary operations on the horizontal 1-cells, cf. Remark 3.4. The unit maps B into (B × {0})^{+}. Similarly, we freely equip the the graph’s edges with the monoid ZZ of unary operations before applying the free category functor.

4.8. Example. [Braidings] Non-empty words over a set may be paired with an element of the braid group of the word’s length. This generalization of the free semigroup functor yields a cartesian monad that may be composed with the exception monad E. Sequences of poly-2-cells with an outer braiding now can be composed, if the sequences of codomains and domains after application of the inner and outer braidings are complements. Notice that if braidings are replaced by permutations, one still does not recover Szabo’s original polycategories.

4.9. Example. [Virtual 1-cells] From Remark 3.4 recall the cartesian monad on set induced by (_)+2, where 2 = {0, 1}. Call this monad S. Its Eilenberg-Moore algebras are bi-pointed sets (with two distinguished constants), and the homomorphisms preserving these constants are bi-strict functions. The category set ^{S} clearly is cartesian.

Beck’s canonical cartesian distributive law from S to the free semigroup monad H (cf. Remark 3.4) induces an extension H′ of H to set ^{S} [Bec69]. The distinguished points of (X + 2)^{+} are the singleton words consisting of the distinguished elements of X + 2. In fact, H′ is again cartesian and admits a complementation κ′. Now Theorem 3.2 yields a bicategory of spans in set ^{S}.

Those spans (A + 2)^{+} [figure: k_{0}] K + 2 [figure: k_{1}] (B + 2)^{+}, where poly-2-cells in K only have inputs from A + {0} and outputs from B + {1}, form a sub-bicategory. Its monads are almost planar polycategories: The only compositions along the “virtual” 1-cells 0 and 1 involve an identity-2-cell in the other factor. The “virtual” 1-cells represent empty sublists at specific positions of the input or output, or “locally neutral” elements for partial tensor products ⊗ and ⊕. To obtain “globally neutral” elements we need to identify all poly-2-cells that only differ in their “virtual” inputs or outputs.

5. Replacing distributive laws by appropriate spans

We now return to our question at the end of Section 2: which spans T S [figure: ω] ST in [𝒳, 𝒳] allow defining an essentially associative composition on 𝒳-spans A[figure: k]B [figure: l]C via 2-cells in 𝒳-spn _{□} with an isomorphism in the center

[figure: ASS; Aμ; kS; BT S; Bω; BST; lT; CT T; Cν; AS; k;l; ∼; CT]  (5-00)

such that the units of S and T yield identity 1-cells?

The latter requirement implies that the units η and ψ occur as projections in the following wide pullback in [𝒳, 𝒳]

[figure: 𝒳; η; ψ; S̄; ω̄_{0}; ψ̄; T̄; η̄; ω̄_{1}; S; ψS; W; ω_{0}; ω_{1}; T; ηT; T S; ST]

For simplicity, and in view of the direct proof of Theorem 3.2, it seems reasonable to require

(I0) The pullbacks of ω_{0} along ψS and of ω_{1} along ηT are isomorphisms.

Intuitively, every “S-tuple” of “identity-2-cells” composes (from the top) with some “T - tuple” of “poly-2-cells”, and dually for “T -tuples” of “identity-2-cells”. Since under the assumption of (I0) the span S [figure: η] 𝒳 [figure: ψ] T of units arises as a pullback of the cospan S [figure: ψ̄] W [figure: η̄] T, an “S-tuple” of “identity-2-cells” and a “T -tuple” of “identity-2-cells” only compose, if both “tuples” are “singletons”. This internalizes the fact that for (planar) polycategories á priori there is no horizontal composition of identity-2-cells, or equivalently, 1-cells.

Since η is cartesian, T̄ = T implies that η̄; ω_{0} and T η have the same pullback along ψS. While this only forces η̄; ω_{0} to agree with T η on T-units, we wish to require more

(I1) η̄; ω_{0} = T η and ψ̄; ω_{1} = Sψ

This expresses the idea that the only “S-tuples” of “poly-2-cells” composable with “T - tuples” of “identity-2-cells” are “singleton S-tuples”, and its dual.

If ω is to be viewed as a generalized distributive law, it ought to satisfy appropriate generalizations of axioms (3-00) and (3-01). While replacing λ in those diagrams by the span ω does not produce well-formed diagrams in [𝒳, 𝒳], viewed in the double-category [𝒳, 𝒳]-spn _{□} of spans and morphisms in [𝒳, 𝒳], they could serve as carriers for 2-cells (cf. Example 2.1).

5.1. Definition. Given two monads S = ⟨S, μ, η⟩ and T = ⟨T, ν, ψ⟩ on a category 𝒳, a generalized distributive law ⟨ω, μ̄, ν̄, η̄, ψ̄⟩ between S and T consists of a span T S [figure: ω] ST in [𝒳, 𝒳] together with four 2-cells in the double-category [𝒳, 𝒳]-spn _{□}

[figure: T SS; T μ; ωS; ST S; Sω; SST; μT; T S; ω; μ̄; ST; ,; T T S; νS; T ω; T ST; ωT; ST T; Sν; T S; ω; ν̄; ST]  (5-01)

[figure: T; T η; T; T; ηT; T S; ω; η̄; ST; ,; S; ψS; S; S; Sψ; T S; ω; ψ̄; ST]  (5-02)

(Here the centers need not be isomorphisms.)

In our specific situation the 2-cells η̄ and ψ̄ amount to the existence of natural transformations T [figure: η̄] W and S [figure: ψ̄] W such that in [𝒳, 𝒳] we have

[figure: T; T η; T; id; id; η̄; T; ηT; T S; W; ω_{0}; ω_{1}; ST; and; S; ψS; S; id; id; ψ̄; S; Sψ; T S; W; ω_{0}; ω_{1}; ST]

The left, respectively right squares amount to condition (I1) above. Asking, in addition, for η̄ to be a pullback of ηT and for ψ̄ to be a pullback of ψS along ω_{1} and ω_{0}, respectively, we recover precisely condition (I0).

5.2. Definition. If 𝒞 is cartesian, we call a 2-cell in the double-category 𝒞-spn _{□} of spans and 𝒞-morphisms right-sided (left-sided), if its right (left) underlying 𝒞-square is a pullback.

5.3. Proposition. If T S [figure: ω] ST admits right- and left-sided 2-cells η̄ and ψ̄, respectively, as in Diagram (5-02), the composition defined by Diagram (4-00) has the canonical identities.

An analogous result for the associativity also requires ω to be cartesian in the sense that both components have this property.

5.4. Proposition. If T S [figure: ω] ST is cartesian and admits right- and left-sided 2-cells μ̄ and ν̄, respectively, as in Diagram (5-01), the composition defined by (4-00) is essentially associative.

Proof. Let W S [figure: φ] SW with center F and T W [figure: γ] W T with center G be the pointwise pullbacks of ⟨ω_{1}S, Sω_{0}⟩ and ⟨T ω_{1}, ω_{0}T ⟩, respectively.

Consider S-T-spans A[figure: k]B, B [figure: l]C and C [figure: m]D and denote the pullbacks occurring in the composition of l with m according to Diagram (4-00) by X′, Y′ and Z′, respectively. We now wish to compare the following limits of the dotted diagrams:

[figure: KS; k_{1}S; (0); X; x_{0}; x_{1}; R; r_{0}; r_{1}; Q; q_{0}; q_{1}; q; BT S; BW; Bω_{0}; Bω_{1}; BF; Bμ̄; Bφ_{1}; P; f; p_{1}; BSW; BSω_{1}; (2); (4); LW; Lω_{1}; l_{0}W; P′; p′_{0}; p′_{1}; (6); BST; BSST; BμT; LST; l_{0}ST; X′T; x′_{0}T; Z′T; z′_{0}T; Q′; q′_{0}; q′_{1}; q′; R′; u′_{0}; r′_{1}; Y′; y′_{0}; y′_{1}; MT; m_{0}T; (1); P′; p′_{0}; g; CG; Cγ_{0}; Cν̄; CW; Cω_{0}; Cω_{1}; CST; P; p_{0}; p_{1}; (7); LW; Lω_{0}; l_{1}W; CT W; CT ω_{0}; (5); (3); ZS; z_{1}S; Y S; y_{1}S; LT S; l_{1}T S; CT T S; CνS; CT S]  (5-03)

Composing k and l, respectively l and m according to Diagram (4-00) yield the pullbacks (0) and (1). Since μ̄ is right-sided and ν̄ is left-sided, (2) and (3) are pullbacks, while the cartesian transformations ω_{1} and ω_{0} are responsible for the pullbacks (4) and (5). To account for (7), consider the cube

[figure: BF; Bφ_{1}; Bφ_{0}; BSW; BSω_{0}; P; f; p_{1}; p_{0}; LW; l_{0}W; Lω_{0}; BW S; Bω_{1}S; BST S; Y S; y_{0}S; y_{1}S; LT S; l_{0}T S]

Since S is cartesian, in view of (4-00) the bottom is a pullback. The naturality of ω_{0} causes the right face to commute, while the rear face commutes by definition of F. This induces a unique morphism P [figure: p_{0}] Y S rendering the left face and the front commutative. Since the other faces are actually pullbacks, so is the front face. Hence the pullback at Q factors through (7). An analogous argument applies to (6) and the pullback at Q′.

Since μ and S are cartesian, the pullback of k_{1}S along f; B(μ̄; ω_{0}) coincides with the pullback of z_{1}S along p_{0}

[figure: KSS; k_{1}SS; Kμ; XS; x_{0}S; x_{1}S; ZS; z_{0}S; z_{1}S; KS; k_{1}S; BT SS; BT μ; BW S; Bω_{0}S; Y S; y_{0}S; R; r_{2}; r_{1}; BT S; BW; Bω_{0}; BF; Bφ_{0}; Bφ; P; p_{0}; f]

It is now easy to see that

Q [figure: q_{1}] Z′T [figure: z′_{1}T] Y′T [figure: y′_{1}T] MT T [figure: Mν] MT
Q [figure: q_{0}] R [figure: r_{2}] ZS
Q [figure: q] P′ [figure: g] CG [figure: Cν̄] CW

constitute a cone for the second diagram in (5-03). Similarly, we get a cone for the first diagram with vertex Q′, which implies that Q′ is isomorphic to Q.

5.5. Definition. We call a generalized distributive law ⟨ω, μ̄, ν̄, η̄, ψ̄⟩ between S and T cartesian, if μ̄ and η̄ are right-sided, and ν̄ and ψ̄ are left-sided.

5.6. Theorem. Given cartesian monads S and T on a category 𝒳 with pullbacks, any cartesian span T S [figure: ω] ST induces a bicategory ω-spn with the same objects as 𝒳, spans AS [figure: k] BT in 𝒳 as 1-cells A[figure: k]B, and the evident 2-cells. The identity-1-cells are given by the units of S and T, while the composition of 1-cells A[figure: k]B [figure: l]C is defined by means of 2-cells (5-00) in 𝒳-spn _{□} with an isomorphism in the center.

If we interpret a natural transformation T S [figure: λ] ST as a span with an identity as left component, the existence of 2-cells μ̄ and η̄ as well as ν̄ and ψ̄ is equivalent to λ being a distributive law. ν̄ and ψ̄ will be trivially left-sided, while the right-sidedness of μ̄ and η̄ corresponds to the squares in Diagram (3-00) being pullbacks. Hence the notion of being cartesian coincides for distributive laws and generalized distributive laws with trivial left component, and we obtain Theorem 3.2 as a direct corollary of Theorem 5.6.

We now analyze the case that ω_{0} and ω_{1} are built from cartesian distributive laws, as in our motivating example. We start with four cartesian monads S_{i} = ⟨S_{i}, μ_{i}, η_{i}⟩ and T_{i} = ⟨T_{i}, ν_{i}, φ_{i}⟩, i < 2, and two cartesian distributive laws S_{1}S_{0} [figure: σ] S_{0}S_{1} and T_{1}T_{0} [figure: τ] T_{0}T_{1}. These induce composite cartesian monads S and T in the usual fashion

S = ⟨S_{0}S_{1}, S_{0}σS_{1}; μ_{0}μ_{1}, η_{0}; S_{0}η_{1}⟩ and T = ⟨T_{0}T_{1}, T_{0}τT_{1}; ν_{0}ν_{1}, φ_{0}; T φ_{1}⟩

Candidates for the center W of ω are shuffles of S_{0}S_{1} and T_{0}T_{1}, depending on which cartesian distributive laws are available.

To account for Example 4.1, we consider four cartesian distributive laws:

\begin{matrix}T_{1}S_{1} [figure: ϑ] S_{1}T_{1} \\ T_{1}S_{0} [figure: α] S_{0}T_{1} \end{matrix} and \begin{matrix}T_{0}S_{0} [figure: κ] S_{0}T_{0} \\ T_{0}S_{1} [figure: β] S_{1}T_{0} \end{matrix}  (5-04)

With W := T_{0}ST_{1} these induce a span T S [figure: ω] ST by

T S [figure: T_{0}αS_{1}] T_{0}S_{0}T_{1}S_{1} [figure: T_{0}S_{0}ϑ] W [figure: κS_{1}T_{1}] S_{0}T_{0}S_{1}T_{1} [figure: S_{0}βT_{1}] ST  (5-05)

Notice that this construction is less symmetric than may have been suggested by Diagram (4-01) in Example 4.1. (With other distributive laws, e.g., the shuffle S_{0}T S_{1} could have been used for W instead.)

The units η and ψ are easy to handle. A simple diagram chase shows:

5.7. Lemma. If the compatibility diagrams for κ with η_{0} and for β with η_{1} are pullbacks, a right-sided 2-cell η̄ exists as in Diagram (5-02). If the compatibility diagrams if for both ϑ and α with ψ_{1} are pullbacks, then a left-sided 2-cell ψ̄ exists.

To establish associativity is somewhat more complicated. First observe that because of ω_{1}S = (κS_{1}; S_{0}β)T_{1}S and Sω_{0} = ST_{0}(S_{0}ϑ; αS_{1}) the pullback W S [figure: φ] SW with center F needed for the span-composition ωS; Sω is trivially given by the span

W S [figure: T_{0}S(S_{0}ϑ;αS_{1})] T_{0}S^{2}T_{1} [figure: (κS_{1};S_{0}β)ST_{1}]SW

We wish to establish the following [𝒳, 𝒳]-diagrams as the left and right components of the desired right-sided 2-cell μ̄ in [𝒳, 𝒳]-spn _{□}

[figure: T S^{2}; T S_{0}σS_{1}; T_{0}S_{0}T_{1}S_{1}S; T_{0}S_{0}T_{1}σS_{1}; T_{0}αS_{1}S; W S; T_{0}S_{0}ϑS; T_{0}SS_{0}T_{1}S_{1}; T_{0}S_{0}σT_{1}S_{1}; T_{0}SαS_{1}; (2); T_{0}S^{2}T_{1}; T_{0}S_{0}σS_{1}T_{1}; T_{0}SS_{0}ϑ; T S_{0}^{2}S_{1}^{2}; T μ_{0}μ_{1}; T_{0}S_{0}T_{1}SS_{1}; T_{0}αSS_{1}; T_{0}S_{0}^{2}T_{1}S_{1}^{2}; T_{0}μ_{0}T_{1}μ_{1}; T_{0}S_{0}αS_{1}^{2}; (1); T_{0}S_{0}ST_{1}S_{1}; T_{0}S_{0}^{2}ϑS_{1}; T_{0}S_{0}^{2}S_{1}^{2}T_{1}; T_{0}μ_{0}μ_{1}T_{1}; T_{0}S_{0}Sϑ; (0); T S; T_{0}S_{0}T_{1}S_{1}; T_{0}αS_{1}; T_{0}ST_{1}; T_{0}S_{0}ϑ; T_{0}S^{2}T_{1}; T_{0}S_{0}σS_{1}T_{1}; κS_{1}ST_{1}; S_{0}T_{0}S_{1}ST_{1}; S_{0}T_{0}σS_{1}T_{1}; S_{0}βST_{1}; (5); SW; SκS_{1}T_{1}; SS_{0}T_{0}S_{1}T_{1}; S_{0}σT_{0}S_{1}T_{1}; SS_{0}βT_{1}; S^{2}T; S_{0}σS_{1}T; T_{0}S_{0}^{2}S_{1}^{2}T_{1}; T_{0}μ_{0}μ_{1}T_{1}; κS_{0}S_{1}^{2}T_{1}; (3); S_{0}T_{0}SS_{1}T_{1}; S_{0}κS_{1}^{2}T_{1}; S_{0}^{2}T_{0}S_{1}^{2}T_{1}; μ_{0}T_{0}μ_{1}T_{1}; S_{0}^{2}βS_{1}T_{1}; (4); S_{0}ST_{0}S_{1}T_{1}; S_{0}SβS_{1}T_{1}; S_{0}^{2}S_{1}^{2}T; μ_{0}μ_{1}T; T_{0}ST_{1}; κS_{1}T_{1}; S_{0}T_{0}S_{1}T_{1}; S_{0}βT_{1}; ST]

The marked pullbacks trivially result from two non-interfering natural transformations. Parts (0) and (1) as well as (3) and (4) commute because of the axioms for distributive laws. The latter two can easily be shown to be pullbacks, provided the compatibility squares of κ and β with the multiplications μ_{0} and μ_{1}, respectively, are pullbacks. The remaining parts (2) and (5) can be addressed simultaneously by requiring (σ) T_{0}σT_{1} provides a right-sided 2-cell in [𝒳, 𝒳]-spn _{□}

[figure: T S_{1}S_{0}; T σ; T_{0}S_{1}S_{0}T_{1}; ⟨T_{0}(S_{1}α;ϑS_{0}),id ⟩; ⟨id ,(βS_{0};S_{1}κ)T_{1}⟩; S_{1}S_{0}T; σT; T S; ω; T_{0}σT_{1}; ST]

which in [𝒳, 𝒳] amounts to

[figure: T S_{1}S_{0}; T σ; T_{0}S_{1}T_{1}S_{0}; T_{0}ϑS_{0}; T_{0}S_{1}S_{0}T_{1}; T_{0}S_{1}α; T_{0}σT_{1}; βS_{0}T_{1}; S_{1}T_{0}S_{0}T_{1}; S_{1}κT_{1}; S_{1}S_{0}T; σT; T S; W; ω_{0}; ω_{1}; ST]  (5-06)

Unfortunately, the left-sided 2-cell ν̄ cannot be handled dually, because our set-up (5-05) lacks symmetry. Consider first

[figure: T^{2}S; T_{0}τT_{1}S; T T_{0}S_{0}T_{1}S_{1}; T T_{0}αS_{1}; T_{0}τS_{0}T_{1}S_{1}; T W; T T_{0}S_{0}ϑ; T_{0}^{2}T_{1}^{2}S; ν_{0}ν_{1}S; T_{0}T S_{0}T_{1}S_{1}; T_{0}^{2}T_{1}αS_{1}; T_{0}T ST_{1}; T_{0}τST_{1}; T_{0}^{2}αS_{1}T_{1}; T_{0}^{2}T_{1}S_{0}ϑ; T_{0}^{2}S_{0}T_{1}^{2}S_{1}; ν_{0}S_{0}ν_{1}S_{1}; T_{0}^{2}αT_{1}S_{1}; T_{0}^{2}S_{0}T_{1}ϑ; T_{0}^{2}S_{0}T_{1}S_{1}T_{1}; T_{0}W T_{1}; ν_{0}Sν_{1}; T_{0}^{2}S_{0}ϑT_{1}; (0); T S; T_{0}S_{0}T_{1}S_{1}; T_{0}αS_{1}; (1); W; T_{0}S_{0}ϑ; W T; κS_{1}T_{1}T; S_{0}T_{0}S_{1}T_{1}T; S_{0}T_{0}S_{1}τT_{1}; S_{0}βT_{1}T; ST^{2}; ST_{0}τT_{1}; T_{0}W T_{1}; ν_{0}Sν_{1}; T_{0}κS_{1}T_{1}^{2}; (2); T_{0}S_{0}T_{0}S_{1}T_{1}^{2}; T_{0}ST T_{1}; T_{0}SτT_{1}; T_{0}S_{0}βT_{1}^{2}; κS_{1}T_{0}S_{1}T_{1}; S_{0}T_{0}^{2}S_{1}T_{1}^{2}; S_{0}ν_{0}S_{1}ν_{1}; S_{0}T_{0}βT_{1}^{2}; κT_{0}S_{1}T_{1}^{2}; S_{0}T_{0}S_{1}T T_{1}; S_{0}βT T_{1}; ST_{0}^{2}T_{1}^{2}; Sν_{0}ν_{1}; W; κS_{1}T_{1}; S_{0}T_{0}S_{1}T_{1}; T_{0}βS_{1}; (3); ST]

Again we have marked the trivial pullbacks. If the compatibility diagrams of both ϑ and α with the multiplication ν_{1} are pullbacks, parts (0) and (1) can be shown to be pullbacks as well. The axioms for distributive laws imply that parts (2) and (3) commute. To obtain a left-sided 2-cell ν̄ we need to fill the obvious gap. This can be done by requiring (τ) in [𝒳, 𝒳]-spn _{□} there exists a left-sided 2-cell

[figure: T_{1}T_{0}S; τS; ⟨id ,T_{1}(κS_{1};S_{0}β)⟩; T_{1}ST_{0}; ⟨(S_{0}ϑ;αS_{1})T_{0},id ⟩; ST_{1}T_{0}; σT; T S; ω; τ̄; ST]

which in [𝒳, 𝒳] amounts to the existence of a natural transformation τ̄ from the pullback H to W such that

[figure: T_{1}ST_{0}; T_{1}T_{0}S; T_{1}(κS_{1};S_{0}β); τS; ST_{1}T_{0}; (S_{0}ϑ;αS_{1})T_{0}; Sτ; H; χ_{0}; τ̄; χ_{1}; T S; ST; W; ω_{0}; ω_{1}]  (5-07)

The two lower squares in (5-07), enclosed by T_{0} and T_{1}, fill the gap and ν̄ = T_{0}τ̄T_{1}; ν_{0}Sν_{1} yields the desired left-handed 2-cell.

Together with Lemma 5.7 and as a consequence of Theorem 5.6 we obtain

5.8. Proposition. If ϑ, α, κ and β as in (5-04) are cartesian distributive laws satisfying (σ) and (τ), the objects of 𝒳, spans of the form AS [figure: k] BT as 1-cells from A to B with the composition according to (5-00) and (5-05) and the evident 2-cells form a bicategory.

The hypotheses are easily verified for the relevant distributive laws on the free semigroup monad and the exception monad of Example 4.1. Hence that construction indeed yields a bicategory with planar polycategories as monads.

6. Weakly cartesian monads

Our construction above is based on the bicategory 𝒳-spn . Since certain interesting monads fail to be cartesian, foremost the free commutative monoid monad, we wish to suitably modify 𝒳-spn before performing the remaining steps of the construction. This is intended to force pullbacks wherever the monad-functors and their natural transformations as well as ω fail to produce them. In other words, we wish to invert the span-morphisms induced by the pullbacks for the cospans in certain commutative squares. This has the flavor of forming a “bicategory of fractions”, an operation where attention has to be paid to potential size problems. However, if the span-morphisms to be inverted happen to be retractions, such size problems can be avoided.

6.1. Definition. A span A [figure: k] B a category 𝒳 with pullbacks is called a weak pullback of a cospan A [figure: f]B, if the uniquely determined span-morphism from k into the pullback of f is a retraction.

The notions of cartesian functor/natural transformation/monad, of right/left-sided 2-cell in [𝒳, 𝒳]-spn _{□} and of cartesian span in [𝒳, 𝒳] may all be weakened by replacing pullbacks by weak pullbacks in the respective definitions.

Since functors preserve retractions, we see that cartesian functors/monads are weakly cartesian. An easy exercise establishes

6.2. Proposition. The free commutative monoid monad is weakly cartesian.

6.3. Definition. For a bicategory ℬ and a class R of 2-cells that are retractions, let ∼_{R} be the least congruence on the class of 2-cells with respect to the composition functors [X, Y] × [Y, Z] [figure] [X, Z] such that

• ∼_{R} contains all parallel pairs ⟨ρ; σ, 1⟩, where ρ ∈ R and σ; ρ = 1;

• on each hom-category [X, Y] of ℬ the relation ∼_{R} restricts to a congruence relation with respect to the composition of 2-cells.

The quotient bicategory ℬ/∼_{R} is obtained by quotienting all hom-categories [X, Y] by the appropriate restriction of ∼_{R}.

The objects and 1-cells of ℬ/∼_{R} coincide with those of ℬ, and the canonical morphism of bicategories from ℬ to ℬ/∼_{R} maps the 2-cells in R to isomorphisms.

6.4. Theorem. For weakly cartesian monads S = ⟨S, μ, η⟩ and T = ⟨T, ν, ψ⟩ on 𝒳, any weakly cartesian span T S [figure: ω] ST induces a bicategory, again denoted by ω-spn , with the same objects as 𝒳, spans AS [figure: k] BT in 𝒳 as 1-cells A[figure: k]B and the evident 2-cells inherited from 𝒳-span /∼_{R}, where R is the class of retractions determined by all

(0) S-images, respectively, T -images of pullbacks of the form

[figure: KS; k_{1}S; Z; BT S; BW; Bω_{0}; Y; y_{0}; and; Z′; LT; l_{0}T; X′; x′_{1}; BW; Bω_{1}; BST]

(1) naturality squares of the form

\xymatrix{BS \ar[dd]_{BSψ} & L \ar[l]_{l_{0}} \ar[dd]^{Lψ} &  & K \ar[dd]_{Kη} \ar[r]^{k_{1}} & BT \ar[dd]^{BT η} \\  &  & and \\ BST & LT \ar[l]^{l_{0}T} &  & KS \ar[r]_{k_{1}S} & BT S}

for the weakly cartesian natural transformations ψ and η; (2) naturality squares of the form

\xymatrix{BST T \ar[dd]_{BSν} & LT T \ar[l]_{l_{0}T T} \ar[dd]^{Lν} &  & KSS \ar[dd]_{Kμ} \ar[r]^{k_{1}SS} & BT SS \ar[dd]^{BT μ} \\  &  & and \\ BST & LT \ar[l]^{l_{0}T} &  & KS \ar[r]_{k_{1}S} & BT S}

for the weakly cartesian natural transformations ν and μ;

(3) naturality squares for the weakly cartesian natural transformations ω_{0}, ω_{1};

(4) weak pullbacks resulting from the weakly right-sided 2-cells η̄ and μ̄;

(5) weak pullbacks resulting from the weakly left-sided 2-cells ψ̄ and ν̄.

Composition of 1-cells A[figure: k]B [figure: l]C is defined by means of 2-cells of the form (5-00) in 𝒳-spn _{□}/∼_{R} with an isomorphism in the center, and the identity-1-cells are given by the units of S and T.

Consider the free commutative monoid functor on set . Since this happens to be part of a weakly cartesian monad, we expect to obtain “symmetric polycategories” as monoids in bicategory of the type described in Theorem 6.4, provided a weakly cartesian counterpart for the span ω of Example 4.1 can be found.

The free symmetric monoid over B consists of “unordered lists”, also known as “bags”, or “multi-sets”, or “subsets with finite repetition” and can be identified with functions B [figure: f] IN where IN \ {0} has a finite pre-image. Addition of bags operates by adding functions and has the constant zero function as neutral element.

Concerning the ways of composing two bags of poly-2-cells with bags of suitable sets as domains and codomains, the only condition to carry over from Section 1 ought to be simple connectedness. Hence drawing such compositions may involve arbitrarily intersecting 1cells. However, due to the nature of bags, these can also be disentangled: since the diagram is simply connected, there has to be at least one poly-2-cell linked by a single 1cell to the rest. Removing this yields another legitimate composition diagram (where one poly-2-cell has one input or output less than before). In this fashion we can successively remove all but two poly-2-cells and then re-attach them in the reversed order, but in planar fashion.

6.5. Theorem. Let U be the bag-monad, and let HE [figure: ψ] U be the natural transformation that turns words into bags by forgetting the order. Extending (HE)^{2} [figure: ω] (HE)^{2} of Example 4.1 by ψ^{2} on both sides produces a weakly cartesian span U^{2} [figure: ω′] U^{2} in [set , set ], such that symmetric polycategories are the monads in ω′-spn .

7. Concluding remarks

For weakly cartesian monads S and T, we managed to interpret all S-T-spans as 1-cells of a bicategory ω-spn , whenever a weakly cartesian generalized distributive law T S [figure: ω] ST exists. In such an environment several types of monoids may be studied. Endo-1-cells A[figure: k]A, or “S-T-graphs”, can be specialized to

[figure: ω-categories, if; AS; K; k_{0}; k_{1}; AT; is a monoid;; ω-orders, if; AS; K; k_{0}; k_{1}; AT; is a monoid and monosource;; ω-EM-bialgebras, if; AS; K; k_{0}; k_{1}; AT; is a monoid with k_{0} = id_{AS};; S-T-bialgebras, if; AS; K; k_{0}; k_{1}; AT; satisfies k_{0} = id_{AS}.] (7-00)

Of course, some such monoids may exist even if the bicategory ω-spn cannot be defined.

7.1. Example. If T = 𝒳 and ω = id_{S}, then for spans of the form AS [figure: ^{id^{AS}}] AS [figure: ξ] A the question, whether they carry a monoid structure, does not depend on S being cartesian. Due to the left leg of the span being an identity, the only possibly monoid structure must be given by Aμ and Aη. The conditions for the span’s right leg then are precisely the EM-algebra axioms for S. The unit and associativity requirements for the relevant span compositions directly boil down to the monad axioms.

Unless S is cartesian, we cannot build a bicategory of all 𝒳-S-spans (note the reversal of S and 𝒳). However, we may always build a bicategory of 𝒳-S-spans of the form A [figure: ^{id^{A}}] A [figure: f] BS: in fact this is just the Kleisli category for S equipped with 2-cells via commutative triangles. Since the left legs of these spans are identities, the notions of ω^{op}-EM-bialgebras and of 𝒳-S-bialgebras coincide; they are determined precisely by the monad units A [figure: Aη] AS.

We hope that our new description of polycategories, especially their planar and symmetric variants, in simple categorical terms will allow them to shed their somewhat tainted image and become the subject of further categorical investigation. Some open questions, partly arising from our analysis above, conclude this section.

- Which notions of morphisms suit the structures outlined (7-00), especially ω-cate-gories? Besides the obvious “ω-functors” and their “ω-transformations”, other possibilities should not be discounted. In particular, how do the “poly-functors” and “poly-modules” of [CKS03] fit into the picture?

- Ordinary distributive laws between S and T facilitate a composition of the monads, or equivalently, a lifting of T to 𝒳^{S}. What can be said about generalized distributive laws (Definition 5.1) in this regard?

- The diagrams in (5-06) raise a general question concerning distributive laws. Canceling T_{0} on the left, respectively T_{1} on the right, results in diagrams describing two different ways of reversing the order of three monads by applying three distributive laws. In general, AB [figure: α] BA, AC [figure: β] CA and BC [figure: γ] CB yield αC; Bβ; γA and Aγ; βB; Cα from ABC to CBA. Although there exists a composite monad with carrier CBA, neither of these reversals is used in constructing its multiplication. That results from BACB [figure: BβB] BCAB [figure: γα] CBBA. Hence it is not clear, whether or not αC; Bβ; γA and Aγ; βB; Cα always agree.

- Does it make sense to consider “composites” of A[figure: k]B and B [figure: l]C where the center of the 2-cell (5-00) need not be an isomorphism?

- In the quest for “categories without identities”, also called “taxonomies”, a weakening of the notion of monad was proposed in [Kos97]: an interpolad ⟨a, α⟩ on A is an endo-1-cell A [figure: a] A equipped with a multiplication aa [figure: α] a that is a coequalizer of aα and αa (and hence in particular associative).

For interpolads S and T a cartesian span T S [figure: ω] ST will still give rise to a composition of S-T-spans, but the lack of identities for S and T will in general prevent this multiplication from having identities. This raises the question, what a meaningful notion of “bicategory without identity 1-cells” or “bitaxonomy” could be, and what conditions on ω are necessary to produce such a structure. In a next step, one might even consider interpolads in a bitaxonomy.

Acknowledgment

The idea of characterizing planar polycategories in terms of monads grew out of joint research on poly-bicategories [CKS03] with J.R.B. Cockett of the University of Calgary and R.A.G. Seely of McGill University in Montreal. I am grateful for their encouragement to pursue this question and for their stimulating and helpful remarks. Two anonymous referees’ comments also led to substantial improvements of earlier versions of this paper. The diagrams were produced with XY-pic 3.7.

References

[Bec69] Jon M. Beck. Distributive laws. In B. Eckmann, editor, Seminar on Triples and Categorical Homology Theory, volume 80 of LNM, pages 119–140. Springer-Verlag, Berlin, Heidelberg and New York, 1969.

[Bur71] Albert Burroni. T-categories (catégories dans un triple). Cahiers Topologie Géom. Différentielle, 12(3):215–321, 1971.

[Bur73] Elisabeth Burroni. Algebres non deterministiques et D-categories. Cahiers Topologie Géom. Différentielle, 14(4):417–475, 1973?

[CJ95] Aurelio Carboni and Peter Johnstone. Connected limits, familial representability and Artin glueing. Math. Structures Comp. Sci., 5:441–459, 1995.

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

[CKS03] J. R. B. Cockett, J. Koslowski, and R. A. G. Seely. Morphisms and modules for poly-bicategories. Theory and Applications of Categories, 11(2):15–74, 2003.

[CS92] J. R. B. Cockett and R. A. G. Seely. Weakly distributive categories. In M. P. Fourman, P. T. Johnstone, and A. M. Pitts, editors, Applications of Categories to Computer Science (Durham, 1991), volume 177 of London Math. Soc. Lecture Note Ser., pages 45–65. Cambridge Univ. Press, Cambridge, 1992.

[CS97] J. R. B. Cockett and R. A. G. Seely. Weakly distributive categories (corrected

version at http://www.math.mcgill.ca/rags/linear/wdc.ps.gz ). J. Pure

Appl. Algebra, 114:133–173, 1997.

[CT03] Maria Manuel Clementino and Walter Tholen. Metric, topology and multicategory – a common approach. J. Pure Appl. Algebra, 179:13–47, 2003.

[Her00] Claudio Hermida. Representable multicategories. Adv. in Math., 151:164–225, 2000.

[Kos97] Jürgen Koslowski. Monads and interpolads in bicategories. Theory and Applications of Categories, 3(8):182–212, 1997.

[Lam69] Joachim Lambek. Deductive systems and categories. II. Standard constructions and closed categories. In Category Theory, Homology Theory and their Applications, I (Battelle Institute Conference, Seattle, Wash., 1968, Vol. One), volume 86 of LNM, pages 76–122. Springer-Verlag, Berlin, Heidelberg and New York, 1969.

[Lei98] Tom Leinster. General operads and multicategories. math.CT/9810053, 1998.

[Lei99] Tom Leinster. fc-multicategories. math.CT/9903004, 1999. Talk given at PSSL 70 in Cambridge, February 1999.

[Lei02] Tom Leinster. Generalized enrichment of categories. J. Pure Appl. Algebra, 168(2-3):391–406, 2002.

[Red74] Ellen Redi. Onesided ideals of symmetric polycategories. Tartu Riikl. Ül. Toimetised, (336):31–61, 1974.

[Sza75] M. E. Szabo. Polycategories. Comm. Algebra, 3:663–689, 1975.

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 anony-

mous ftp at ftp://ftp.tac.mta.ca/pub/tac/html/volumes/14/7/14-07.{dvi,ps}

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.

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@mathstat.uottawa.ca Lawrence Breen, Université de Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of North Wales: r.brown@bangor.ac.uk Jean-Luc Brylinski, Pennsylvania State University: jlb@math.psu.edu 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