Theory and Applications of Categories, Vol. 30, No. 16, 2015, pp. 533–598.

POLYNOMIALS IN CATEGORIES WITH PULLBACKS

MARK WEBER

Abstract. The theory developed by Gambino and Kock, of polynomials over a locally cartesian closed category E, is generalised for E just having pullbacks. The 2-categorical analogue of the theory of polynomials and polynomial functors is given, and its relationship with Street’s theory of fibrations within 2-categories is explored. Johnstone’s notion of “bagdomain data” is adapted to the present framework to make it easier to completely exhibit examples of polynomial monads.

1. Introduction

Thanks to unpublished work of André Joyal dating back to the 1980’s, polynomials admit a beautiful categorical interpretation. Given a multivariable polynomial function p with natural number coefficients, like say

p(w, x, y, z) = (x^{3}y + 2, 3x^{2}z + y)  (1)

one may break down its formation as follows. There is a set In = {w, x, y, z} of “input variables” and a two element set Out of “output variables”. Rewriting p(w, x, y, z) = (x^{3}y + 1 + 1, x^{2}z + x^{2}z + x^{2}z + y), there is a set

MSum = {x^{3}y, (1)_{1}, (1)_{2}, (x^{2}z)_{1}, (x^{2}z)_{2}, (x^{2}z)_{3}, y}

of “monomial summands”, and a set

UVar = {x_{1}, x_{2}, x_{3}, y_{1}, x_{4}, x_{5}, z_{1}, x_{6}, x_{7}, z_{2}, x_{8}, x_{9}, z_{3}, y_{2}}

of “usages of variables”, informally consisting of no w’s, nine x’s, two y’s and three z’s. The task of forming the polynomial p can then be done in three steps. First one takes the input variables and duplicates or ignores them according to how often each variable is used. The book-keeping of this step is by means of the evident function p_{1} : UVar → In, which in our example forgets the subscripts of elements of UVar. In the second step one performs all the multiplications, and this is book-kept by taking products over the fibres of the function p_{2} : UVar → MSum which sends each usage to the monomial summand in which it occurs, that is

\begin{matrix}x_{1}, x_{2}, x_{3}, y_{1} ↦ x^{3}y & x_{4}, x_{5}, z_{1} ↦ (x^{2}z)_{1} & x_{6}, x_{7}, z_{2} ↦ (x^{2}z)_{2} \\ x_{8}, x_{9}, z_{3} ↦ (x^{2}z)_{3} & y_{2} ↦ y. \end{matrix}

Received by the editors 2014-08-11 and, in revised form, 2015-04-30.

Transmitted by Stephen Lack. Published on 2015-05-02.

2010 Mathematics Subject Classification: 18A05; 18D20; 18D50.

Key words and phrases: polynomial functors, 2-monads.

\begin{matrix}c \\ ◯ \end{matrix} Mark Weber, 2015. Permission to copy for private use granted.

Finally one adds up the summands, and this is book-kept by summing over the fibres of the evident function p_{3} : MSum → Out. Thus the polynomial p “is” the diagram

[figure: In; UVar; MSum; Out; p_{1}; p_{2}; p_{3}]  (2)

in the category Set. A categorical interpretation of the formula (1) from the diagram (2) begins by regarding an n-tuple of variables as (the fibres of) a function into a given set of cardinality n. Duplication of variables is then interpretted by the functor Δ_{p_{1}} : Set/In → Set/UVar given by pulling back along p_{1}, taking products by the functor Π_{p_{2}} : Set/UVar → Set/MSum and taking sums by applying the functor Σ_{p_{3}} : Set/MSum → Set/Out given by composing with p_{3}. Composing these functors gives

P(p) : Set/In → Set/Out

the polynomial functor corresponding to the polynomial p.

Functors of the form Δ_{p_{1}}, Π_{p_{2}} and Σ_{p_{3}} are part of the bread and butter of category theory. For any map p_{3} in any category, one may define Σ_{p_{3}} between the appropriate slices, and one requires only pullbacks in the ambient category to interpret Δ_{p_{1}} more generally. The functor Π_{p_{2}} is by definition the right adjoint of Δ_{p_{2}}, and its existence is a condition on the map p_{2}, called exponentiability. Locally cartesian closed categories are by definition categories with finite limits in which all maps are exponentiable. Consequently a reasonable general categorical definition of polynomial is as a diagram

[figure: X; A; B; Y; p_{1}; p_{2}; p_{3}]  (3)

in some locally cartesian closed category E. The theory polynomials and polynomial functors was developed at this generality in the beautiful paper [11] of Gambino and Kock. There the question of what structures polynomials in a locally cartesian closed E form was considered, and it was established in particular that polynomials can be seen as the arrows of certain canonical bicategories, with the process of forming the associated polynomial functor giving homomorphisms of bicategories.

In this paper we shall focus on the bicategory Poly_{E} of polynomials and cartesian maps between them in the sense of [11]. Our desire to generalise the above setting comes from the existence of canonical polynomials and polynomial functors for the case E = Cat and the wish that they sit properly within an established framework. While local cartesian closedness is a very natural condition of great importance to categorical logic, enjoyed for example by any elementary topos, it is not satisfied by Cat. Avoiding the assumption of local cartesian closure may be useful also for applications in categorical logic. For example, the categories of classes considered in Algebraic Set Theory [14] are typically not assumed to be locally cartesian closed, but the small maps are assumed to be exponentiable.

The natural remedy of this defect is to define a polynomial p between X and Y in a category E with pullbacks to be a diagram as in (3) such that p_{2} is an exponentiable map. Since exponentiable maps are pullback stable and closed under composition, one obtains the bicategory Poly_{E} together with the “associated-polynomial-functor homomorphism”, as before. We describe this in Section 3.

The main technical innovation of Sections 2 and 3 is to remove any reliance on type theory in the proofs, giving a completely categorical account of the theory. In establishing the bicategory structure on Poly_{E} in Section 2 of [11], the internal language of E is used in an essential way, especially in the proof of Proposition 2.9. Our development makes no use of the internal language. Instead we isolate the concept of a distributivity pullback in Section 2.2 and prove some elementary facts about them. Armed with this technology we then proceed to give an elementary account of the bicategory of polynomials, and the homomorphism which encodes the formation of associated polynomial functors. Our treatment requires only pullbacks in E.

Our second extension to the categorical theory of polynomials is motivated by the fact that Cat is a 2-category. Thus in Section 4.1 we develop the theory of polynomials within a 2-category K with pullbacks, and the polynomial 2-functors that they determine. In this context the structure formed by polynomials is a degenerate kind of tricategory, called a 2-bicategory, which roughly speaking is a bicategory whose homs are 2-categories instead of categories. However except for this change, the theory works in the same way as for categories. In fact our treatment of the 1-categorical version of the theory in Section 3 was tailored in order to make the previous sentence true (in addition to giving the desired generalisation).

A first source of examples of 2-categorical polynomials come from the 2-monads considered first by Street [27] whose algebras are fibrations. In Proposition 4.2.3 these 2-monads are exhibited as being polynomial in general. Fibrations in a 2-category play another role in this work, because it is often the case that the maps participating in a polynomial may themselves be fibrations or opfibrations in the sense of Street. This has implications for the properties that the resulting polynomial 2-functor inherits. To this end, the general types of 2-functor that are compatible with fibrations are recalled from [34] in Section 4.3, and the polynomials that give rise to them are identified in Theorem 4.4.5.

As explained in [7, 23] certain 2-categorical colimits called codescent objects are important in 2-dimensional monad theory. Theorem 4.4.5 has useful consequences in [32], in which certain codescent objects which arise naturally from a morphism of 2-monads are considered. When these codescent objects arise from a situation conforming appropriately to the hypotheses of Theorem 4.4.5, they acquire extra structure which facilitates their computation. Also of relevance to the computation of associated codescent objects, we have in Theorem 4.5.1 identified sufficient conditions on polynomials in Cat so that their induced polynomial 2-functors preserve all sifted colimits.

While the bicategorical composition of polynomials has been established in [11], and more generally in Sections 3 and 4 of this paper, actually exhibiting explicitly a polynomial monad requires some effort due to the complicated nature of this composition. However one can often avoid the need to check monad axioms by using an alternative approach, based on Johnstone’s notion of “bagdomain data” [13]. The essence of this approach is described in Theorem 5.3.3 and its 2-categorical analogue Theorem 5.4.1. These methods are then illustrated in Section 5.4, where various fundamental examples of polynomial 2-monads on Cat are exhibited. In particular the 2-monads on Cat for symmetric and for braided monoidal categories are polynomial 2-monads.

Polynomial functors over some locally cartesian closed category E arise in diverse mathematical contexts as explained in [11]. They arise in computer science under the name of containers [1]. Tambara in [30] studied polynomials over categories of finite G-sets motivated by representation theory and group cohomology. Very interesting applications of Tambara’s work were found by Brun in [8] to Witt vectors, and in [9] also to equivariant stable homotopy theory and cobordism. Moreover in [22] one finds applications of polynomial functors to higher category theory.

Having generalised to the consideration of non-locally cartesian closed categories we have expanded the possible scope of applications. In this article we have described some basic examples of polynomial monads over Cat. Further examples for Cat of relevance to operads are provided in [3, 32, 33]. The results of Section 3 apply also to polynomials over Top which were a part of the basic setting of the work of Joyal and Bisson [4] on Dyer-Lashof operations.

Notations. We denote by [n] the ordinal {0 < ... < n} regarded as a category. The category of functors A → B and natural transformations between them is usually denoted as [A, B], though in some cases we also use exponential notation B^{A}. For instance E^{[1]} is the arrow category of a category E, and E^{[2]} is a category whose objects are composable pairs of arrows of E. A 2-monad is a Cat-enriched monad, and given a 2-monad T on a 2-category K, we denote by T -Alg_{s} the 2-category of strict T -algebras and strict maps, T -Alg the 2-category of strict algebras and strong maps^{1} and Ps-T -Alg for the 2-category of pseudo-T -algebras and strong maps, following the usual notations of 2-dimensional monad theory [5, 23].

2. Elementary notions

In this section we describe the elementary notions which underpin our categorical treatment of the bicategory of polynomials in Section 3. In Section 2.1 we recall basic facts and terminology regarding exponentiable morphisms. In Section 2.2 we introduce distributivity pullbacks, and prove various general facts about them.

2.1. Exponentiable morphisms. Given a morphism f : X → Y in a category E, we denote by Σ_{f} : E/X → E/Y the functor given by composition with f. When E has pullbacks Σ_{f} has a right adjoint denoted as Δ_{f}, given by pulling back maps along f. When Δ_{f} has a right adjoint, denoted as Π_{f}, f is said to be exponentiable. A commutative square in E as on the left

1Which are T -algebra morphisms up to coherent isomorphism

[figure: A; B; D; C; f; k; g; h; E/A; E/B; E/D; E/C; Σ_{f}; Δ_{k}; Σ_{g}; Δ_{h}; α; E/A; E/B; E/D; E/C; Δ_{f}; Π_{k}; Δ_{g}; Π_{h}; β]

determines a natural transformation α as in the middle, as the mate of the identity Σ_{k}Σ_{f} = Σ_{g}Σ_{h} via the adjunctions Σ_{h} ⊣ Δ_{h} and Σ_{k} ⊣ Δ_{k}. We call α a left Beck-Chevalley cell for the original square. There is another left Beck-Chevalley cell for this square, namely Σ_{h}Δ_{f} → Δ_{g}Σ_{k}, obtained by mating the identity Σ_{k}Σ_{f} = Σ_{g}Σ_{h} with the adjunctions Σ_{f} ⊣ Δ_{f} and Σ_{g} ⊣ Δ_{g}. If in addition h and k are exponentiable maps, then taking right adjoints produces the natural transformation β from α, and we call this a right Beck-Chevalley cell for the original square. There is another right Beck-Chevalley cell Δ_{k}Π_{g} → Π_{f}Δ_{h} when f and g are exponentiable. It is well-known that the original square is a pullback if and only if either associated left Beck-Chevalley cell is invertible, and when h and k are exponentiable, these conditions are also equivalent to the right Beck-Chevalley cell β being an isomorphism. Under these circumstances we shall speak of the left or right Beck-Chevalley isomorphisms.

Clearly exponentiable maps are closed under composition and any isomorphism is exponentiable. Moreover, exponentiable maps are pullback stable. For given a pullback square as above in which g is exponentiable, one has Σ_{h}Δ_{f} ≅ Δ_{g}Σ_{k}, and since Σ_{h} is comonadic, Δ_{g} has a right adjoint by the Dubuc adjoint triangle theorem [10].

When E has a terminal object 1 and f is the unique map X → 1, we denote by Σ_{X}, Δ_{X} and Π_{X} the functors Σ_{f}, Δ_{f} and Π_{f} (when it exists) respectively. In fact since Σ_{X} : E/X → E takes the domain of a given arrow into X, it makes sense to speak of it even when E doesn’t have a terminal object. An object X of a finitely complete category E is exponentiable when the unique map X → 1 is exponentiable in the above sense (ie when Π_{X} exists). A finitely complete category E is cartesian closed when all its objects are exponentiable, and locally cartesian closed when all its morphisms are exponentiable.

Note that as right adjoints the functors Δ_{f} and Π_{f} preserve terminal objects. An object h : A → X of the slice category E/X is terminal if and only if h is an isomorphism in E, but there is also a canonical choice of terminal object for E/X – the identity 1_{X}. So for the sake of convenience we shall often assume below that Δ_{f} and Π_{f} are chosen so that Δ_{f}(1_{Y}) = 1_{X} and Π_{f}(1_{X}) = 1_{Y}.

2.2. Distributivity pullbacks. For f : A → B in E a category with pullbacks, Δ_{f} : E/B → E/A expresses the process of pulling back along f as a functor. One may then ask: what basic categorical process is expressed by the functor Π_{f} : E/A → E/B, when f is an exponentiable map?

Let us denote by ε_{f}^{(1)} the counit of Σ_{f} ⊣ Δ_{f}, and when f is exponentiable, by ε_{f}^{(2)} the counit of Δ_{f} ⊣ Π_{f}. The components of these counits fit into the following pullbacks:

[figure: Y; X; B; A; ε_{f,b}^{(1)}; b; f; Δ_{f} b; pb; Q; P; A; B; R; ε_{f,a}^{(2)}; a; f; Π_{f} a; ε_{f,Π_{f} a}^{(1)}; pb]  (4)

Now the universal property of ε_{f}^{(1)}, as the counit of the adjunction Σ_{f} ⊣ Δ_{f}, is equivalent to the square on the left being a pullback as indicated. An answer to the above question is obtained by identifying what is special about the diagram on the right in (4), that corresponds to the universal property of ε_{f}^{(2)} as the counit of Δ_{f} ⊣ Π_{f}. To this end we make

2.2.1. Definition. Let g : Z → A and f : A → B be a composable pair of morphisms in a category E. Then a pullback around (f, g) is a diagram

[figure: X; Z; A; B; Y; p; g; f; r; q; pb]

in which the square with boundary (gp, f, r, q) is, as indicated, a pullback. A morphism (p, q, r) → (p′, q′, r′) of pullbacks around (f, g) consists of s : X → X′ and t : Y → Y′ such that p′s = p, qs = tq′ and r = r′s. The category of pullbacks around (f, g) is denoted PB(f, g).

For example the pullback on the right in (4) exhibits (ε_{f,a}^{(2)}, ε_{f,Π_{f} a}^{(1)}, Π_{f}a) as a pullback

around (f, a). One may easily observe directly that the universal property of ε_{f,a}^{(2)} is equivalent to (ε_{f,a}^{(2)}, ε_{f,Π_{f} a}^{(1)}, Π_{f}a) being a terminal object of PB(f, a). Thus we make

2.2.2. Definition. Let g : Z → A and f : A → B be a composable pair of morphisms in a category E. Then a distributivity pullback around (f, g) is a terminal object of PB(f, g). When (p, q, r) is a distributivity pullback, we denote this diagramatically as follows:

[figure: X; Z; A; B; Y; p; g; f; r; q; dpb]

and we say that this diagram exhibits r as a distributivity pullback of g along f.

Thus the answer to the question posed at the beginning of this section is: when f : A → B is an exponentiable map in E a category with pullbacks, the functor Π_{f} : E/A → E/B encodes the process of taking distributivity pullbacks along f.

For any (p, q, r) ∈ PB(f, g) one has a Beck-Chevalley isomorphism as on the left

Π_{q}Δ_{p}Δ_{g} ≅ Δ_{r}Π_{f}  δ_{p,q,r} : Σ_{r}Π_{q}Δ_{p} → Π_{f}Σ_{g}

which when you mate it by Σ_{r} ⊣ Δ_{r} and Σ_{g} ⊣ Δ_{g}, gives a natural transformation δ_{p,q,r} as on the right in the previous display. When this is an isomorphism, it expresses a type of distributivity of “sums” over “products”, and so the following proposition explains why we use the terminology distributivity pullback.

2.2.3. Proposition. Let f be an exponentiable map in a category E with pullbacks. Then (p, q, r) is a distributivity pullback around (f, g) if and only if δ_{p,q,r} is an isomorphism.

Proof. Since (ε_{f,g}^{(2)}, ε_{f,Π_{f} g}^{(1)}, Π_{f}g) is terminal in PB(f, g), one has unique morphisms d and e fitting into a commutative diagram

[figure: Z; X; Y; B; E; D; p; q; r; ε_{f,g}^{(2)}; ε_{f,Π_{f} g}^{(1)}; Π_{f} g; d; e; pb]

in which the middle square is a pullback by the elementary properties of pullbacks. Thus (p, q, r) is a distributivity pullback if and only if e is an isomorphism. Since the adjunctions Σ_{r} ⊣ Δ_{r} and Σ_{g} ⊣ Δ_{g} are cartesian, δ_{p,q,r} is cartesian, and so it is an isomorphism if and only if its component at 1_{Z} ∈ E/Z is an isomorphism. Since Δ_{p}(1_{Z}) = 1_{X} and Π_{q}(1_{X}) = 1_{Y} one may easily witness directly that (δ_{p,q,r})_{1_{X}} = e.

When manipulating pullbacks in a general category, one uses the “elementary fact” that given a commutative diagram of the form

[figure: A; B; C; F; E; D; pb]

then the front square is a pullback if and only if the composite square is. In the remainder of this section we identify three elementary facts about distributivity pullbacks.

2.2.4. Lemma. (Composition/cancellation) Given a diagram of the form

[figure: B_{6}; B_{2}; B; X; Y; B_{3}; B_{4}; B_{5}; Z; h_{9}; h_{6}; h_{7}; g; f; h; h_{2}; h_{8}; h_{3}; h_{5}; h_{4}; pb; dpb; pb]

in any category with pullbacks, then the right-most pullback is a distributivity pullback around (g, h_{4}) if and only if the composite diagram is a distributivity pullback around (gf, h).

Proof. Let us suppose that right-most pullback is a distributivity pullback, and that C_{1}, C_{2}, k_{1}, k_{2} and k_{3} as in

[figure: B_{6}; B_{2}; B; X; Y; B_{3}; B_{4}; B_{5}; Z; C_{1}; C_{2}; C_{3}; h_{9}; h_{6}; h_{7}; g; f; h; h_{2}; h_{8}; h_{3}; h_{5}; h_{4}; k_{1}; k_{2}; k_{3}; k_{4}; k_{5}; k_{6}; k_{7}; k_{8}; k_{9}; k_{10}; k_{11}; pb; dpb; dpb]

are given such that the square with boundary (hk_{1}, gf, k_{3}, k_{2}) is a pullback. Then we must exhibit r : C_{1} → B_{6} and s : C_{2} → B_{5} unique such that h_{2}h_{8}r = k_{1}, h_{6}h_{9}r = sk_{2} and h_{7}s = k_{3}. Form C_{3}, k_{4} and k_{5} by taking the pullback of k_{3} along g, and then k_{6} is unique such that k_{5}k_{6} = k_{2} and k_{4}k_{6} = fhk_{1}. Clearly the square with boundary (hk_{1}, f, k_{4}, k_{6}) is a pullback around (f, h). From the universal property of the left-most distributivity pullback, one has k_{7} and k_{8} as shown unique such that k_{1} = h_{2}k_{7}, h_{3}k_{7} = k_{8}k_{6} and h_{4}k_{8} = k_{4}. From the universal property of the right-most distributivity pullback, one has k_{9} and k_{10} as shown unique such that k_{8} = h_{5}k_{9}, h_{6}k_{9} = k_{10}k_{5} and h_{7}k_{10} = k_{3}. Clearly h_{5}k_{9}k_{6} = h_{3}k_{7} and so by the universal property of the top-left pullback square one has k_{11} as shown unique such that h_{8}k_{11} = k_{7} and h_{9}k_{11} = k_{9}k_{6}. Clearly h_{2}h_{8}k_{11} = k_{1}, h_{6}h_{9}k_{11} = k_{10}k_{2} and h_{7}k_{10} = k_{3} and so we have established the existence of maps r and s with the required properties.

As for uniqueness, let us suppose now that r : C_{1} → B_{6} and s : C_{2} → B_{5} are given such that h_{2}h_{8}r = k_{1}, h_{6}h_{9}r = sk_{2} and h_{7}s = k_{3}. We must verify that r = k_{11} and s = k_{10}. Since the right-most distributivity pullback is in particular a pullback, one has k′_{9} : C_{3} → B_{4} unique such that h_{4}h_{5}k′_{9} = k_{4} and h_{6}k′_{9} = sk_{5}. Since (h_{4}h_{5}, h_{6}) are jointly monic, and clearly h_{4}h_{5}h_{9}r = h_{4}h_{5}k′_{9}k_{6} and h_{6}h_{9}r = h_{6}k′_{9}k_{6}, we have h_{9}r = k′_{9}k_{6}. By the universal property of the left-most distributivity pullback, it follows that h_{5}k′_{9} = k_{8} and h_{8}r = k_{7}. Thus by the universal property of the left-most distributivity pullback, it follows that k_{9} = k′_{9} and k_{10} = s. Since (h_{8}, h_{9}) are jointly monic, h_{8}k_{11} = k_{7} = h_{8}r and h_{9}k_{11} = k_{9}k_{6} = h_{9}r, we have r = k_{11}.

Conversely, suppose that the composite diagram is a distributivity pullback around (gf, h), and that C_{1}, C_{2}, k_{1}, k_{2} and k_{3} as in

[figure: B_{6}; B_{2}; B; X; Y; B_{3}; B_{4}; B_{5}; Z; C_{3}; C_{2}; C_{1}; h_{9}; h_{6}; h_{7}; g; f; h; h_{2}; h_{8}; h_{3}; h_{5}; h_{4}; k_{3}; k_{2}; k_{5}; k_{4}; k_{1}; k_{8}; k_{7}; k_{6}; pb; dpb; pb]

are given such that the square with boundary (h_{4}k_{1}, g, k_{3}, k_{2}) is a pullback. We must give r : C_{1} → B_{4} and s : C_{2} → B_{5} unique such that k_{1} = h_{5}r, h_{6}r = sk_{2} and h_{7}s = k_{3}. Pullback k_{1} along h_{3} to produce C_{3}, k_{4} and k_{5}. This makes the square with boundary (hh_{2}k_{4}, gf, k_{3}, k_{2}k_{5}) a pullback around (gf, h). Thus one has k_{6} and k_{7} as shown unique such that h_{8}k_{6} = k_{4}, h_{6}h_{9}k_{6} = k_{7}k_{2}k_{1} and k_{7}h_{7} = k_{3}. By universal property of the right pullback and since gh_{4}k_{1} = h_{7}k_{7}k_{2}, one has k_{8} as shown unique such that h_{5}k_{8} = k_{1} and h_{6}k_{8} = k_{7}k_{2}. By the uniqueness part of the universal property of the left distributivity pullback, it follows that h_{5}k_{8} = k_{1}, and so we have established the existence of maps r and s with the required properties.

As for uniqueness let us suppose that we are given r : C_{1} → B_{4} and s : C_{2} → B_{5} such that k_{1} = h_{5}r, h_{6}r = sk_{2} and h_{7}s = k_{3}. We must verify that r = k_{8} and s = k_{7}. By the universal property of the top-left pullback one has k′_{6} unique such that h_{8}k′_{6} = k_{4} and h_{9}k′_{6} = rk_{5}. By the uniqueness part of the universal property of the left distributivity pullback, it follows that h_{8}k_{6} = h_{8}k′_{6} and h_{5}k_{8} = h_{5}r. Thus by the uniqueness part of the universal property of the composite distributivity pullback, it follows that k_{6} = k′_{6} and s = k_{7}. Since (h_{4}h_{5}, h_{6}) are jointly monic, it follows that r = k_{8}.

2.2.5. Lemma. (The cube lemma). Given a diagram of the form

[figure: A_{2}; A_{3}; A_{1}; B_{2}; B_{1}; D_{2}; D_{1}; C_{2}; C_{3}; C_{1}; f_{1}; k_{1}; g_{1}; h_{1}; f_{2}; k_{2}; g_{2}; h_{2}; h_{3}; d_{1}; d_{2}; d_{3}; d_{4}; d_{5}; d_{6}; pb; pb; (1); (2); (3); dpb]

in any category with pullbacks, in which regions (1) and (2) commute, region (3) is a pullback around (f_{2}, d_{2}), the square with boundary (f_{1}, k_{1}, g_{1}, h_{1}) is a pullback and the bottom distributivity pullback is around (g_{2}, d_{4}). Then regions (1) and (2) are pullbacks if and only if region (3) is a distributivity pullback around (f_{2}, d_{2}).

Proof. Let us suppose that (1) and (2) are pullbacks and p, q and r are given as in

[figure: A_{2}; A_{3}; A_{1}; B_{2}; B_{1}; D_{2}; D_{1}; C_{2}; C_{3}; C_{1}; f_{1}; k_{1}; g_{1}; h_{1}; f_{2}; k_{2}; g_{2}; h_{2}; h_{3}; d_{1}; d_{2}; d_{3}; d_{4}; d_{5}; d_{6}; pb; pb; pb; pb; pb; dpb; X; Y; p; q; r; s_{2}; t_{2}; s; t]

such that the square with boundary (q, r, f_{2}, d_{2}p) is a pullback. Then one can use the bottom distributivity pullback to induce s_{2} and t_{2} as shown, and then the pullbacks (1) and (2) to induce s and t, and these clearly satisfy d_{1}s = p, f_{1}s = tq and r = d_{5}t. On the other hand given s′ : X → A_{1} and t′ : Y → B_{1} satisfying these equations, define s′_{2} = h_{1}s′ and t′_{2} = k_{1}t′. But then by the uniqueness part of the universal property of the bottom distributivity pullback it follows that s′_{2} = s_{2} and t′_{2} = t_{2}, and from the uniqueness parts of the universal properties of the pullbacks (1) and (2), it follows that s = s′ and t = t′, thereby verifying that s and t are unique satisfying the aforementioned equations.

For the converse suppose that (3) is a distributivity pullback. Note that (2) being a pullback implies that (1) is by elementary properties of pullbacks, so we must show that (2) is a pullback. To that end consider s and t as in

[figure: A_{2}; A_{3}; A_{1}; B_{2}; B_{1}; D_{2}; D_{1}; C_{2}; C_{3}; C_{1}; f_{1}; k_{1}; g_{1}; h_{1}; f_{2}; k_{2}; g_{2}; h_{2}; h_{3}; d_{1}; d_{2}; d_{3}; d_{4}; d_{5}; d_{6}; pb; pb; =; =; dpb; dpb; P; Z; s; t; u; v; w; x; y; z]

such that k_{2}s = d_{6}t, and then pullback s and f_{2} to produce P, u and v. Using the fact that the bottom distributivity pullback is a mere pullback, one has w unique such that d_{4}d_{3}w = h_{2}u and g_{1}w = tv. Using the inner left pullback, one has x unique such that h_{3}x = d_{3}w and d_{2}x = u. Using the distributivity pullback (3), one has y and z unique such that d_{1}y = x, f_{1}y = zv and s = d_{5}z. By the uniqueness part of the universal property of the bottom distributivity pullback, it follows that t = k_{1}z. Thus we have constructed z satisfying s = d_{5}z and t = k_{1}z. On the other hand given z′ : Z → B_{1} such that s = d_{5}z′ and t = k_{1}z′, one has y′ : P → A_{1} unique such that d_{2}d_{1}y = u and f_{1}y = zv, using the fact that the top distributivity pullback is a mere pullback. Then from the uniqueness part of the universal property of that distributivity pullback, it follows that y = y′ and z = z′. Thus as required z is unique satisfying s = d_{5}z and t = k_{1}z.

2.2.6. Lemma. (Sections of distributivity pullbacks). Let

[figure: D; A; B; C; E; p; g; f; r; q; dpb]

be a distributivity pullback around (f, g) in any category with pullbacks. Three maps

s_{1} : B → A s_{2} : B → D s_{3} : C → E

which are sections of g, gp and r respectively, and are natural in the sense that s_{1} = ps_{2} and qs_{2} = s_{3}f, are determined uniquely by the either of the following: (1) the section s_{1}; or (2) the section s_{3}.

Proof. Given s_{1} a section of g, induce s_{2} and s_{3} uniquely as shown:

[figure: D; A; B; C; E; p; g; f; r; q; dpb; B; C; s_{1}; f; 1; s_{2}; s_{3}]

using the universal property of the distributivity pullback. On the other hand given the section s_{3}, one induces s_{2} using the fact that the distributivity pullback is a mere pullback, and then put s_{1} = ps_{2}.

We often assume that in a given category E with pullbacks, some choice of all pullbacks, and of all existing distributivity pullbacks, has been fixed. Moreover we make the following harmless assumptions, for the sake of convenience, on these choices once they have been made. First we assume that the chosen pullback of an identity along any map is an identity. This ensures that Δ_{1_{X}} = 1_{E/X} and that Δ_{f}(1_{B}) = 1_{A} for any f : A → B. Similarly we assume that all diagrams of the form

[figure: •; •; •; •; •; 1; 1; f; 1; f; dpb; •; •; •; •; •; 1; g; 1; g; 1; dpb]

are among our chosen distributivity pullbacks. This has the effect of ensuring that Π_{f}(1_{A}) = 1_{B} for any exponentiable f : A → B, and that Π_{1_{X}} = 1_{E/X}.

3. Polynomials in categories

This section contains our general theory of polynomials and polynomial functors. In Section 3.1 we give an elementary account of the composition of polynomials, culminating in Theorem 3.1.10, in which polynomials in a category E with pullbacks are exhibited as the 1-cells of the bicategory Poly_{E}. Then in Section 3.2, we study the process of forming the associated polynomial functor, exhibiting this as the effect on 1-cells of the homomorphism P_{E} : Poly_{E} → CAT in Theorem 3.2.6. At this generality, the homs of the bicategory Poly_{E} have pullbacks, and the hom functors of P_{E} preserve them. This gives the sense in which the theory of polynomial functors could be iterated, and this is described in Section 3.3. The organisation of this section has been chosen to facilitate its generalisation to the theory of polynomials in 2-categories, in Section 4.1.

3.1. Bicategories of polynomials. Let E be a category with pullbacks. In this section we give a direct description of a bicategory Poly_{E}, whose objects are those of E, and whose one cells are polynomials in E in the following sense. For X, Y in E, a polynomial p from X to Y in E consists of three maps

[figure: X; A; B; Y; p_{1}; p_{2}; p_{3}]

such that p_{2} is exponentiable. Let p and q be polynomials in E from X to Y. A cartesian morphism f : p → q is a pair of maps (f_{0}, f_{1}) fitting into a commutative diagram

[figure: X; A; B; Y; B′; A′; p_{1}; p_{2}; p_{3}; q_{1}; q_{2}; q_{3}; f_{0}; f_{1}; pb]

We call f_{0} the 0-component of f, and f_{1} the 1-component of f. With composition inherited in the evident way from E, one has a category Poly_{E}(X, Y) of polynomials from X to Y and cartesian morphisms between them. These are the homs of our bicategory Poly_{E}.

In order to describe the bicategorical composition of polynomials, we introduce the concept of a subdivided composite of a given composable sequence of polynomials. This enables us to give a direct description of n-ary composition for Poly_{E}, and then to describe the sense in which coherence for this bicategory “follows from universal properties”.

Consider a composable sequence of polynomials in E of length n, that is to say, polynomials

[figure: X_{i−1}; A_{i}; B_{i}; X_{i}; p_{i1}; p_{i2}; p_{i3}]

in E, where 0 < i ≤ n. We denote such a sequence as (p_{i})_{1≤i≤n}, or more briefly as (p_{i})_{i}.

3.1.1. Definition. Let (p_{i})_{1≤i≤n} be a composable sequence of polynomials of length n. A subdivided composite over (p_{i})_{i} consists of objects (Y_{0}, ..., Y_{n}), morphisms

q_{1} : Y_{0} → X_{0} q_{2,i} : Y_{i−1} → Y_{i} q_{3} : Y_{n} → X_{n}

for 0 < i ≤ n, and morphisms

r_{i} : Y_{i−1} → A_{i}  s_{i} : Y_{i} → B_{i}

for 0 < i ≤ n, such that p_{11}r_{1} = q_{1}, p_{n3}s_{n} = q_{3} and

[figure: Y_{i}; A_{i+1}; X_{i}; B_{i}; r_{i+1}; p_{i+1,1}; p_{i3}; s_{i}; =; Y_{i−1}; Y_{i}; B_{i}; A_{i}; q_{2i}; s_{i}; p_{i2}; r_{i}; pb]

For example a subdivided composite over (p_{1}, p_{2}, p_{3}), that is when n = 3, assembles into a commutative diagram like this:

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; p_{11}; p_{12}; p_{13}; p_{21}; p_{22}; p_{23}; p_{31}; p_{32}; p_{33}; q_{21}; q_{22}; q_{23}; r_{1}; s_{1}; r_{2}; s_{2}; r_{3}; s_{3}; q_{1}; q_{3}; pb; pb; pb]

We denote a general subdivided composite over (p_{i})_{i} simply as (Y, q, r, s).

3.1.2. Definition. Let (p_{i})_{1≤i≤n} be a composable sequence of polynomials of length n. A morphism (Y, q, r, s) → (Y′, q′, r′, s′) of subdivided composites consists of morphisms t_{i} : Y_{i} → Y′_{i} for 0 ≤ i ≤ n, such that q_{1} = q′_{1}t_{0}, q′_{2i}t_{i−1} = t_{i}q_{2i}, q_{3} = q′_{3}t_{n}, r_{i} = r′_{i}t_{i−1} and s_{i} = s′_{i}t_{i}. With compositions inherited from E, one has a category SdC(p_{i})_{i} of subdivided composites over (p_{i})_{i} and morphisms between them.

Given a subdivided composite (Y, q, r, s) over (p_{i})_{i}, note that the morphisms q_{2i} are exponentiable since exponentiable maps are pullback stable, and that the composite q_{2} : Y_{0} → Y_{n} defined as q_{2} = q_{2n}...q_{21} is also exponentiable, since exponentiable maps are closed under composition. Thus we make

3.1.3. Definition. The associated polynomial of a given subdivided composite (Y, q, r, s) over (p_{i})_{i} is defined to be

[figure: X_{0}; Y_{0}; Y_{n}; X_{n}; q_{1}; q_{2}; q_{3}]

The process of taking associated polynomials is the object map of a functor

ass : SdC(p_{i})_{i} ⟶ Poly_{E}(X_{0}, X_{n}).

Having made the necessary definitions, we now describe the canonical operations on subdivided composites which give rise to the bicategorical composition of polynomials.

Let n > 0 and (p_{i})_{1≤i≤n} be a composable sequence of polynomials in E. One has evident forgetful functors res_{0} and res_{n} as in

[figure: SdC(p_{i})_{1<i≤n}; SdC(p_{i})_{1≤i≤n}; SdC(p_{i})_{1≤i<n}; ^{res^{0}}; ^{res^{n}}; (−)·p_{1}; p_{n}·(−); ⊥; ⊥]

and we now give a description of the right adjoints of these forgetful functors.

For (Y, q, r, s) a subdivided composite over (p_{i})_{1≤i<n}, we construct the subdivided composite

p_{n} · (Y, q, r, s) := (p_{n} · Y, p_{n} · q, p_{n} · r, p_{n} · s)

over (p_{i})_{1≤i≤n} as follows. First we form the diagram on the left

[figure: X_{n−1}; A_{n}; B_{n}; X_{n}; Y_{n−1}; C; (p_{n} · Y)_{n−1}; (p_{n} · Y)_{n}; p_{n1}; p_{n2}; p_{n3}; q_{3}; (p_{n}·q)_{2,n}; (p_{n}·q)_{3}; ε_{n−1}; dpb; pb; =; =; (p_{n} · Y)_{n−k−1}; (p_{n} · Y)_{n−k}; Y_{n−k}; Y_{n−k−1}; (p_{n}·q)_{2,n−k}; ε_{n−k}; q_{2,n−k}; ε_{n−k−1}; pb]

and then for 1 ≤ k < n we form pullbacks as on the right in the previous display. Finally we define

(p_{n} · q)_{1} = q_{1}ε_{0} (p_{n} · r)_{i} = r_{i}ε_{i−1} (p_{n} · s)_{i} = s_{i}ε_{i}.

The ε_{i} are the components of a morphism

ε_{(Y,q,r,s)} : res_{n}(p_{n} · (Y, q, r, s)) ⟶ (Y, q, r, s)

of subdivided composites. The n = 4 case of this construction is depicted in the diagram:

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; p_{11}; p_{12}; p_{13}; p_{21}; p_{22}; p_{23}; p_{31}; p_{32}; p_{33}; p_{41}; p_{42}; p_{43}; q_{21}; q_{22}; q_{23}; •; •; •; r_{1}; s_{1}; r_{2}; s_{2}; r_{3}; s_{3}; q_{1}; q_{3}; (p_{4}·q)_{24}; (p_{4}·q)_{3}; ε_{0}; ε_{1}; ε_{2}; (p_{4}·q)_{21}; (p_{4}·q)_{22}; (p_{4}·q)_{23}; pb; pb; pb; pb; pb; pb; pb; dpb]

3.1.4. Lemma. The morphisms ε_{(Y,q,r,s)} just described are the components of the counit of an adjunction res_{n} ⊣ p_{n} · (−).

Proof. Let (Y′, q′, r′, s′) be a subdivided composite over (p_{i})_{1≤i≤n}, then for t as in

[figure: res_{n}(p_{n} · (Y, q, r, s)); (Y, q, r, s); res_{n}(Y′, q′, r′, s′); ε_{(Y,q,r,s)}; t; res_{n}(t′)]

we must give t′ unique so that the above triangle commutes. The following commutative diagram assembles this given data in the case n = 4.

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; p_{11}; p_{12}; p_{13}; p_{21}; p_{22}; p_{23}; p_{31}; p_{32}; p_{33}; p_{41}; p_{42}; p_{43}; q_{21}; q_{22}; q_{23}; •; •; •; r_{1}; s_{1}; r_{2}; s_{2}; r_{3}; s_{3}; q_{1}; q_{3}; (p_{4}·q)_{24}; (p_{4}·q)_{3}; ε_{0}; ε_{1}; ε_{2}; (p_{4}·q)_{21}; (p_{4}·q)_{22}; (p_{4}·q)_{23}; pb; pb; pb; pb; pb; pb; pb; dpb; •; •; •; •; •; q′_{21}; q′_{22}; q′_{23}; q′_{24}; t_{0}; t_{1}; t_{2}; t_{3}; q′_{3}; r′_{4}; s′_{4}]

Since q_{n−1}t_{n−1} = p_{n1}r′_{n} one induces u : Y′_{n−1} → C using the defining pullback of C, and then one induces t′_{n−1} : Y′_{n−1} → Y_{n−1} and t′_{n} : Y′_{n} → Y_{n} from the maps u and s′_{n} using the distributivity pullback. The rest of the t′_{i} are induced inductively as follows. For 0 < i < n given t′_{i} : Y′_{i} → Y_{i}, one induces t′_{i−1} using the maps t_{i−1} and t′_{i} and the pullback which defines (p_{n} · Y)_{i−1}. By construction the t′_{i} are the components of the required unique map t′.

For (Y, q, r, s) a subdivided composite over (p_{i})_{1<i≤n}, we construct the subdivided composite

(Y, q, r, s) · p_{1} := (Y · p_{1}, q · p_{1}, r · p_{1}, s · p_{1})

over (p_{i})_{1≤i≤n} as follows. First one takes the pullback on the left, then for 0 < i < n the distributivity pullbacks as in the middle,

[figure: C_{02}; Y_{0}; X_{1}; B_{1}; f_{0}; q_{1}; p_{13}; g_{0}; pb; C_{i1}; C_{i2}; Y_{i}; Y_{i−1}; C_{i−1,2}; q′_{2,i}; f_{i}; q_{2,i}; f_{i−1}; g_{i}; dpb; (Y · p_{1})_{n−i−1}; (Y · p_{1})_{n−i}; C_{n−i−1,2}; C_{n−i−1,1}; (q·p_{1})_{2,n−i}; g′′_{i}; q′_{2,n−i−1}; g′_{i+1}; pb]

and then for 0 < i < n one takes the pullbacks as on the right in the previous display, setting (q · p_{1})_{2,n} = q′_{2,n−1}, g′′_{1} = g_{n−1}, g′′_{i+1} = g_{n−i+1}g′_{i+1} for i + 1 < n, g′′_{n−1} = g_{0}g_{1}g′_{n−1} and q′_{02} = p_{12}. Finally one defines

(q · p_{1})_{1} = p_{11}g′_{n}  (q · p_{1})_{3} = q_{3}f_{n−1}.

In the case n = 4 one obtains a diagram like this:

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; p_{11}; p_{12}; p_{13}; p_{21}; p_{22}; p_{23}; p_{31}; p_{32}; p_{33}; p_{41}; p_{42}; p_{43}; q_{21}; q_{22}; q_{23}; r_{1}; s_{1}; r_{2}; s_{2}; r_{3}; s_{3}; q_{1}; q_{3}; pb; pb; pb; •; •; •; •; •; •; •; •; •; •; g′_{4}; g′_{3}; g_{1}; f_{0}; g′_{2}; g_{2}; f_{1}; g_{3}=g′′_{1}; f_{2}; f_{3}; (q·p_{1})_{21}; (q·p_{1})_{22}; (q·p_{1})_{23}; (q·p_{1})_{24}; q′_{22}; q′_{21}; g_{0}; (q·p_{1})_{1}; (q·p_{1})_{3}; pb; pb; dpb; dpb; dpb; pb; pb]

The equations ε′_{0} = f_{0}g_{1}g′_{3}, ε′_{n−1} = f_{n−1} and ε′_{i} = f_{i}g′′_{n−i−1} for 0 < i < n − 1, define the components of the morphism

ε′_{Y,q,r,s} : res_{0}((Y, q, r, s) · p_{1}) ⟶ (Y, q, r, s).

3.1.5. Lemma. The morphisms ε′_{Y,q,r,s} just described are the components of the counit of an adjunction res_{0} ⊣ (−) · p_{1}.

Proof. Given (Y, q, r, s) in SdC(p_{i})_{1≤i≤n} and t as in

[figure: res_{0}((Y, q, r, s) · p_{1}); (Y, q, r, s); res_{0}(Y′, q′, r′, s′); ε′_{Y,q,r,s}; t; res_{0}(t′)]

we must exhibit t′ as shown unique so that the above diagram commutes. In the case n = 4 the data (Y′, q′, r′, s′) and t fit into the following diagram:

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; p_{11}; p_{12}; p_{13}; p_{21}; p_{22}; p_{23}; p_{31}; p_{32}; p_{33}; p_{41}; p_{42}; p_{43}; q_{21}; q_{22}; q_{23}; r_{1}; s_{1}; r_{2}; s_{2}; r_{3}; s_{3}; q_{1}; q_{3}; pb; pb; pb; •; •; •; •; •; •; •; •; •; •; (q·p_{1})_{21}; (q·p_{1})_{22}; (q·p_{1})_{23}; (q·p_{1})_{24}; pb; pb; dpb; dpb; dpb; pb; pb; •; •; •; •; •; q′_{1}; q′_{21}; q′_{22}; q′_{23}; q′_{24}; q′_{3}; t_{1}; t_{2}; t_{3}; t_{4}; r′_{1}; s′_{1}]

Using the pullback that defines C_{02} and the maps s′_{1} and t_{1}, one induces Y′_{1} → C_{02}. Using the distributivity pullbacks one induces successively the morphisms Y′_{i} → C_{i1} and Y′_{i+1} → C_{i2} for 0 < i < n. In the case i = n − 1 we denote these maps as t′_{n−1} and t′_{n} respectively. The components t′_{i} for 0 ≤ i < n − 1 are then induced from this data and the pullbacks that define the objects (Y · p_{1})_{i}. By construction the t′_{i} are the components of the required unique map t′.

3.1.6. Proposition. For any composable sequence (p_{i})_{1≤i≤n} of polynomials in a category E with pullbacks, the category SdC(p_{i})_{i} has a terminal object.

Proof. We proceed by induction on n. In the case n = 0, observe that a subdivided composite consists just of the data Y_{0}, q_{1} : Y_{0} → X_{0} and q_{3} : Y_{0} → X_{0}, and that SdC() is the category Span_{E}(X_{0}, X_{0}) of endospans of X_{0}. The identity endospan is terminal. For the inductive step apply either of the functors p_{n} · (−) or (−) · p_{1} which as right adjoints, preserve terminal objects.

3.1.7. Definition. Let E be a category with pullbacks. A composite of a composable sequence (p_{i})_{1≤i≤n} of polynomials in E, is defined to be the associated polynomial of a terminal object in the category SdC(p_{i})_{i}. When such a composite has been chosen, it is denoted as p_{n} ∘ ... ∘ p_{1}.

Let us consider now some degenerate cases of Definition 3.1.7.

• n = 0: Choosing identity spans as terminal nullary subdivided composites (see the proof of Proposition 3.1.6), nullary composition of polynomials gives polynomials whose constituent maps are all identities. That is,

[figure: X; X; X; X; 1_{X}; 1_{X}; 1_{X}]

is the “identity polynomial on X” as one would hope.

• n = 1: One may identify SdC(p) as the slice Poly_{E}(X_{0}, X_{1})/p, and thus choose 1_{p} as the terminal unary subdivided composite over (p). Thus the unary composite of a given polynomial p is just p.

• n = 2: applying p_{2} ·(−) to p_{1}, or (−)·p_{1} to p_{2}, gives the same subdivided composite, namely

[figure: •; •; •; •; •; •; •; •; •; •; •; p_{11}; p_{12}; p_{13}; p_{21}; p_{22}; p_{23}; pb; dpb; pb]

which is terminal by the case n = 1 and since the functors p_{2} · (−) and (−) · p_{1}, as right adjoints, preserve terminal objects. Thus the associated composite of the above is the binary composite p_{2} ∘ p_{1}, and this agrees with the binary composition of polynomials given in [11].

3.1.8. Lemma. Let n > 0 and (p_{i})_{1≤i≤n} be a composable sequence of polynomials in a category E with pullbacks. Then one has canonical isomorphisms

[figure: SdC(p_{i})_{1≤i<n}; Poly^{E}(X_{0}, X_{n−1}); Poly_{E}(X_{0}, X_{n}); SdC(p_{i})_{1≤i≤n}; ass; p_{n}∘(−); ass; p_{n}·(−); ≅; SdC(p_{i})_{1<i≤n}; Poly^{E}(X_{1}, X_{n}); Poly_{E}(X_{0}, X_{n}); SdC(p_{i})_{1≤i≤n}; ass; (−)∘p_{1}; ass; (−)·p_{1}; ≅]

Proof. The canonical isomorphism on the left follows from the definitions and the elementary properties of pullbacks. The canonical isomorphism on the right follows from the definitions, and iterated application of Lemma 2.2.4.

In order to make explicit the horizontal composition of 2-cells in Poly_{E} we consider a horizontally composable sequence of morphisms of polynomials of length n, that is to say diagrams

[figure: X_{i−1}; A_{i}; B_{i}; X_{i}; B′_{i}; A′_{i}; p_{i1}; p_{i2}; p_{i3}; q_{i3}; q_{i2}; q_{i1}; f_{0i}; f_{1i}; pb]

in E, for 0 < i ≤ n. We denote such a sequence as (f_{0i}, f_{1i})_{i} : (p_{i})_{i} → (q_{i})_{i} since it is a morphism of the category ∏_{i=1}^{n} Poly_{E}(X_{i−1}, X_{i}). The process of vertically stacking subdivided composites and their morphisms on top of (f_{0i}, f_{1i})_{i} gives a functor

SdC(f_{0i}, f_{1i})_{i} : SdC(p_{i})_{i} ⟶ SdC(q_{i})_{i}.

The assignation (f_{0i}, f_{1i})_{i} ↦ SdC(f_{0i}, f_{1i})_{i} is functorial, and natural in the evident sense with respect to the restriction and associated polynomial functors defined above. For any choice t_{1} and t_{2} of terminal object of SdC(p_{i})_{i} and SdC(q_{i})_{i} respectively, one has composites

p_{n} ∘ ... ∘ p_{1} = ass(t_{1})  q_{n} ∘ ... ∘ q_{1} = ass(t_{2})

by Definition 3.1.7, and a unique morphism u_{t_{1},t_{2}} : SdC(f_{0i}, f_{1i})_{i}(t_{1}) → t_{2}.

3.1.9. Definition. Let E be a category with pullbacks and (f_{0i}, f_{1i})_{i} : (p_{i})_{i} → (q_{i})_{i} be a horizontally composable sequence of polynomial morphisms of length n. Then in the context just described, the 2-cell

f_{n} ∘ ... ∘ f_{1} : p_{n} ∘ ... ∘ p_{1} ⟶ q_{n} ∘ ... ∘ q_{1}

is defined to be ass(u_{t_{1},t_{2}}).

In the case n = 2 the original data and the chosen terminal subdivided composites comprise the solid parts of the diagram,

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; f_{01}; f_{11}; f_{02}; f_{12}; pb; pb; •; •; •; •; pb; pb; dpb; •; •; •; •; pb; pb; dpb; ϕ_{1}; ϕ_{2}; ϕ_{3}; ϕ_{4}]

and one then induces ϕ_{1} using the pullback defining its codomain, ϕ_{2} and ϕ_{3} are then induced by the universal property of the bottom distributivity pullback, and finally ϕ_{4} is induced by the bottom pullback. One verifies easily that (ϕ_{4}, ϕ_{2}, ϕ_{3}) a morphism of subdivided composites, thus it is u_{t_{1},t_{2}}, and so by Definition 3.1.9 the composite f_{2} ∘ f_{1} is given by (ϕ_{4}, ϕ_{3}).

3.1.10. Theorem. Let E be a category with pullbacks. One has a bicategory Poly_{E}, whose objects are those of E, whose hom from X to Y is Poly_{E}(X, Y), horizontal composition of 1-cells is given by Definition 3.1.7, and horizontal composition of 2-cells is given by Definition 3.1.9.

Proof. By induction on n, using the fact that the functors p_{n} · (−) and (−) · p_{1} preserve terminal objects, and Lemma 3.1.8, it follows that any iterated binary composite of polynomials of length n, is a composite in the sense of Definition 3.1.7. That is, such an iterated composite is the associated polynomial of a terminal subdivided polynomial, which arises from the composable sequence of polynomials that participates in the given iterated binary composite. Hence between any two alternative brackettings of a given composite, there is a unique isomorphism of their underlying subdivided composites, giving rise to a “coherence” isomorphism of the composites themselves upon application of “ass”. Any diagram of such coherence isomorphisms must commute, since it is the image by the appropriate “ass” functor, of a diagram whose vertices are all terminal subdivided composites. Thanks to our conventions regarding chosen pullbacks and chosen distributivity pullbacks of identities described in Section 2.2, the unit coherence isomorphisms here turn out to be identities.

The functoriality of horizontal composition comes from the functoriality of (f_{0i}, f_{1i})_{i} ↦ SdC(f_{0i}, f_{1i})_{i} and the naturality of SdC(f_{0i}, f_{1i})_{i} with respect to the “ass” functors. It remains to verify the naturality of the coherence isomorphisms identified in the previous paragraph. To this end we suppose that a horizontally composable sequence (f_{0i}, f_{1i})_{i} : (p_{i})_{i} → (q_{i})_{i} of morphisms of polynomials of length n, and binary brackettings β_{1} and β_{2} of n things is given. Let us denote by t_{β_{1}}(p_{i})_{i}, t_{β_{2}}(p_{i})_{i}, t_{β_{1}}(q_{i})_{i} and t_{β_{2}}(q_{i})_{i} the terminal subdivided composites witnessing the iterated binary composites of (p_{i})_{i} and (q_{i})_{i} via the given brackettings. In SdC(q_{i})_{i} one has the diagram

[figure: SdC(f_{0i}, f_{1i})_{i}(t_{β_{1}}(p_{i})_{i}); SdC(f_{0i}, f_{1i})_{i}(t_{β_{2}}(p_{i})_{i}); t_{β_{2}}(q_{i})_{i}; t_{β_{1}}(q_{i})_{i}]

in which the top horizontal arrows are the effect of applying SdC(f_{0i}, f_{1i})_{i} to the unique morphisms, and the other morphisms are determined uniquely and both squares commute because t_{β_{1}}(q_{i})_{i} and t_{β_{2}}(q_{i})_{i} are terminal. Applying ass : SdC(q_{i})_{i} → Poly_{E}(X_{0}, X_{n}) to this diagram gives the squares witnessing the naturality of the coherence morphisms.

A span in E as on the left

[figure: X; Z; Y; s; t; X; Z; Z; Y; s; 1_{Z}; t]

may be identified as a polynomial in which the middle map is an identity as on the right. Polynomial composition of spans coincides exactly with span composition, giving us a strict inclusion

Span_{E} ↪ Poly_{E}

of bicategories which is the identity on objects and locally fully faithful. For a given map f : X → Y in E, we denote by f^{•} : X → Y and f_{•} : Y → X the polynomials

[figure: X; X; X; Y; 1; 1; f; Y; X; X; X; f; 1; 1]

respectively. These are spans, it is well known that one has f^{•} ⊣ f_{•} and that this is part of the basic data of the proarrow equipment (E, Span_{E}) [36, 37]. By the above strict inclusion, this extends to another proarrow equipment (E, Poly_{E}), and all this at the generality of a category E with pullbacks. It is worth noting that polynomial composites of the form f^{•} ∘ p and q ∘ g_{•} are particularly easy, these being

[figure: •; •; •; •; p_{1}; p_{2}; fp_{3}; •; •; •; •; gq_{1}; q_{2}; q_{3}]

respectively.

The homs of Poly_{E} interact well with the slices of E. For all X and Y one has obvious forgetful functors

[figure: E/X; Poly_{E}(X, Y); E/Y; l_{X,Y}; r_{X,Y}]

and we refer to these as the left and right projections of the homs of Poly_{E}. From the above descriptions of composites of the form f^{•} ∘ p and q ∘ g_{•}, one obtains immediately the sense in which these forgetful functors are natural.

3.1.11. Lemma. For all f : Y → Z and g : X → W one has

\begin{aligned}Σ_{g}l_{X,Y} & = & l_{W,Y} ((−) ∘ g_{•}) & Σ_{f}r_{X,Y} & = & r_{X,Z}(f^{•} ∘ (−)) \\ l_{X,Y} & = & l_{X,Z}(f^{•} ∘ (−)) & r_{X,Y} & = & r_{W,Y} ((−) ∘ g_{•}) \end{aligned}

3.2. Polynomial functors. Let E be a category with pullbacks. In this section we define a homomorphism of bicategories

P_{E} : Poly_{E} ⟶ CAT  X ↦ E/X

with object map as indicated, in Theorem 3.2.6. Given a polynomial p : X → Y in E, the functor P_{E}(p) : E/X → E/Y is defined to be the composite Σ_{p_{3}}Π_{p_{2}}Δ_{p_{1}}, which for the sake of brevity, will also be denoted as p(−) : E/X → E/Y. In more elementary terms the effect of p(−) on an object x : C → X of E/X is described by the following commutative diagram:

[figure: X; A; B; Y; C; C_{2}; C_{3}; C_{4}; p_{1}; p_{2}; p_{3}; x; p(x); dpb; pb]

Similarly one may, by exploiting the universal property of the pullback and distributivity pullback in this description, induce the maps which provide the arrow map of p(−). These explicit descriptions together with Lemma 3.1.11 enables us to catalogue all the ways one can use the composition of Poly_{E} to describe the functor p(−), and we record this in

3.2.1. Lemma. Let p : X → Y be a polynomial in E.

1. Given x : C → X in E/X, one has

p(x) = r_{Z,Y} (p ∘ x^{•} ∘ g_{•})

for all Z and g : C → Z.

2. Given x_{1} : C_{1} → X, x_{2} : C_{2} → X and h : C_{1} → C_{2} over X, one has

p(h) = r_{Z,Y} (p ∘ h′ ∘ g_{•})

for all Z and g : C_{2} → Z, where h′ : x_{2}^{•} → x_{1}^{•}h_{•} is the mate of the identity x_{2}^{•}h^{•} = x_{1}^{•} via h^{•} ⊣ h_{•}.

To prove Theorem 3.2.6 we exhibit an analogous result, Lemma 3.2.5, giving all the ways of expressing P_{E}’s 2-cell map in terms of composition in Poly_{E}. Preliminary to this result we reconcile two ways of describing P_{E}’s 2-cell map – that given in [11] versus a direct description in terms of morphisms of induced from pullbacks and distributivity pullbacks, in Lemma 3.2.4. Lemmas 3.2.2 and 3.2.3 are preliminary to Lemma 3.2.4. The reader not interested in such technical details is encouraged to skip ahead to the statement of Theorem 3.2.6 below.

The description of P_{E}’s 2-cell map given in [11], is to associate to a given cartesian morphism f : p → q between polynomials from X to Y, the following natural transformation

[figure: E/X; E/A; E/B; E/Y; E/B′; E/A′; Δ_{p_{1}}; Π_{p_{2}}; Σ_{p_{3}}; Δ_{q_{1}}; Π_{q_{2}}; Σ_{q_{3}}; Δ_{f_{0}}; Δ_{f_{1}}; ≅; ≅]  (5)

in which the isomorphism in the middle is a Beck-Chevalley isomorphism, and Σ_{p_{3}}Δ_{f_{1}} → Σ_{q_{3}} is the mate of the identity via Σ_{f_{1}} ⊣ Δ_{f_{1}}. The advantage of this description is that the functoriality of the resulting hom functor

(P_{E})_{X,Y} : Poly_{E}(X, Y) ⟶ CAT(E/X, E/Y)

is evident. We will show that the component at x : C → X of (P_{E})_{X,Y} (f) is given by the map f_{4,x}, constructed in

[figure: X; A; B; Y; A′; B′; C; C_{2}; C_{3}; C_{4}; C′_{2}; C′_{3}; C′_{4}; p_{1}; p_{2}; p_{3}; q_{1}; q_{2}; q_{3}; p(x); q(x); x; f_{0}; f_{1}; f_{2,x}; f_{3,x}; f_{4,x}; pb; pb; dpb; dpb; pb]  (6)

To construct this diagram one induces f_{2,x} using f_{0} and the bottom pullback, and then it follows that the square (C_{2}, A, A′, C′_{2}) is a pullback. One can then induce f_{3,x} and f_{4,x} using the bottom distributivity pullback. Lemma 2.2.5 ensures that (C_{4}, B, B′, C′_{4}) is a pullback, and elementary properties of pullbacks ensure that (C_{2}, C_{3}, C′_{3}, C′_{2}) and (C_{3}, C_{4}, C′_{4}, C′_{3}) are also pullbacks.

Our next task is to explain why (6) really does describe the components of (5). This verification begins by unpacking, for a given commuting square as shown on the right

[figure: A; B; D; C; f; k; g; h; E/A; E/B; E/D; E/C; Σ_{f}; Δ_{k}; Σ_{g}; Δ_{h}; α; E/A; E/B; E/D; E/C; Δ_{f}; Π_{k}; Δ_{g}; Π_{h}; β]

the left Beck-Chevalley cell α, and when h and k are exponentiable, the right Beck-Chevalley cell β, in elementary terms. Since α is obtained by taking the mate of the identity Σ_{g}Σ_{h} = Σ_{k}Σ_{f} via the adjunctions Σ_{h} ⊣ Δ_{h} and Σ_{k} ⊣ Δ_{k}, it follows that α is uniquely determined by the equation Σ_{k}ε_{f}^{(1)} = (ε_{g}^{(1)}Σ_{k})(Σ_{g}α). On the other hand one has the commutative diagram

[figure: A_{3}; A_{2}; A; B; D; C; C_{2}; Δ_{h}x; f; k; g; x; ε_{h,x}^{(1)}; α_{x}; Δ_{k}(gx); ε_{k,gx}^{(1)}; h; pb]  (7)

and the above equation, for the component x, is witnessed by the commutativity of the bottom triangle. Thus

3.2.2. Lemma. The components of α are induced as in (7).

Moreover we can see directly from (7) that if the original square is a pullback, then α is invertible, and the converse follows by considering the case x = 1_{C}. The right Beck-Chevalley cell β may be obtained by taking the mate of Δ_{f}Δ_{k} ≅ Δ_{h}Δ_{g} via Δ_{h} ⊣ Π_{h} and Δ_{k} ⊣ Π_{k}. Thus it is uniquely determined by the commutativity of

[figure: Δ_{h}Δ_{g}Π_{k}; Δ_{h}Π_{h}Δ_{f}; Δ_{f}; Δ_{f}Δ_{k}Π_{k}; Δ_{h}β; ε_{h}^{(2)}Δ_{f}; Δ_{f} ε_{k}^{(2)}; coh.Π_{k}]  (8)

whereas inside E for all B_{2} and x : B_{2} → B we have

[figure: A; B; D; C; C_{3}; A_{3}; A_{2}; B_{2}; B_{3}; D_{2}; C_{2}; A_{4}; f; k; g; h; x; β_{x}; pb; pb; pb; dpb; dpb]  (9)

constructed as follows. Take the distributivity pullback of x along k and then pullback the result along g. Pullback x along f and then take the distributivity pullback of the result along h. Then form the top pullback and induce the morphism A_{4} → C_{2}. By the elementary properties of pullbacks, it follows that the squares (A_{4}, B_{3}, D_{2}, C_{2}) and (A_{4}, A, C, C_{2}) are pullbacks. From this last we induce the dotted arrows using the left distributivity pullback.

3.2.3. Lemma. The components of β are induced as in (9).

Proof. Note that the square (A_{4}, A_{3}, C_{3}, C_{2}) is also a pullback, and so one can identify the commuting triangle (A_{4}, A_{3}, A_{2}) with (8), once one has understood that A_{4} → A_{2} is the (appropriate component of) the lower composite in (8).

From this construction and Lemma 2.2.5 one may witness directly that if the original square is a pullback, then β is invertible, and the converse is easily witnessed by considering the case x = 1_{B}. With these details sorted out we can now proceed to the proof of

3.2.4. Lemma. The component at x : C → X of the natural transformation described in (5) is the morphism f_{4,x} described in (6).

Proof. The proof consists of unpacking the definition of (P_{E})_{X,Y} (f)_{x} with reference to the diagram (6), keeping track of the canonical isomorphisms that participate in the definition. All of this may be witnessed in

[figure: X; A; B; Y; A′; B′; C; C_{2}; C_{3}; C_{4}; C′_{2}; C′_{3}; C′_{4}; f_{3,x}; f_{4,x}; D_{1}; D_{2}; D_{3}; ϕ; D_{4}; α; D_{5}; γ; β]

in which the solid arrows appeared already in (6), and the dotted arrows are constructed as follows. Form D_{1} by pulling back f_{0} and C′_{2} → A′, then D_{1} → C is the composite for the triangle (D_{1}, C′_{2}, C). The form D_{2}, D_{3} and D_{4} by taking the distributivity pullback of D_{1} → A along p_{2}. Form D_{4} by pulling back f_{1} and C′_{4} → B′. The construction of the rest of the data proceeds in the same way as for (9) as shown in

[figure: A; A′; B′; B; D_{3}; D_{2}; D_{1}; C′_{2}; C′_{3}; C′_{4}; D_{4}; D_{5}; γ; β; pb; pb; pb; dpb; dpb]

Thus the arrow labelled as β is by Lemma 9 the right Beck-Chevalley isomorphism, and γ is also invertible. Clearly ϕ is an isomorphism witnessing the pseudo-functoriality of Δ_{(−)}, and considering (7) for the square

[figure: B; Y; Y; B′; p_{3}; 1_{Y}; q_{3}; f_{0}]

the arrow labelled α is evidently the appropriate component of the left Beck-Chevalley cell by Lemma 3.2.2. Thus (P_{E})_{X,Y} (f)_{x} is by definition the composite

[figure: C_{4}; D_{3}; D_{4}; C′_{4}; β^{−1}; α]

and to finish the proof we must show that this composite is f_{4,x}. Provisionally let us denote by ξ this composite, and by ζ the composite

[figure: C_{3}; D_{2}; D_{5}; C′_{3}.; γ^{−1}]

Observe that the squares

[figure: C_{2}; C_{3}; C′_{3}; C′_{2}; ζ; C_{3}; C_{4}; C′_{4}; C′_{3}; ξ; ζ; C_{4}; B; B′; C′_{4}; f_{1}; ξ]

are commutative, and so by the uniqueness aspect of the universal property of the bottom distributivity pullback, it follows that ζ = f_{3,x} and ξ = f_{4,x}.

The importance of this alternative description is that it can, in various ways, be written in terms of composition in the bicategory Poly_{E} whose composition and coherence we understand. These ways are described in the following result, which follows immediately from Lemma 3.1.11 and Lemma 3.2.4.

3.2.5. Lemma. Let p and q : X → Y be polynomials in E and f : p → q be a cartesian morphism between them. Then given x : C → X in E/X, one has

P_{E}(f)_{x} = f_{4,x} = r_{Z,Y} (p ∘ x^{•} ∘ g_{•})

for all Z and g : C → Z.

The fact that the one and 2-cell maps of P_{E} have, by Lemmas 3.2.1 and 3.2.5, been described in terms of the bicategory structure of Poly_{E}, is the reason why they give a homomorphism of bicategories. We expand on this further in the proof of

3.2.6. Theorem. Let E be a category with pullbacks. With the object map X ↦ E/X, arrow map p ↦ Σ_{p_{3}}Π_{p_{2}}Δ_{p_{1}}, and 2-cell map depicted in (5), one has a homomorphism

P_{E} : Poly_{E} ⟶ CAT

of bicategories.

Proof. It remains to exhibit the coherence isomorphisms and verify the coherence axioms. We assume a canonical choice of all pullbacks and existing distributivity pullbacks as explained at the end of Section 2.2. In particular this implies that identities in Poly_{E} are strict, making P_{E}(1_{X}) = 1_{E/X} for all X ∈ E by Lemma 3.2.1. Let p : X → Y and q : Y → Z be polynomials. For x : C → X in E/X one has the associativity isomorphism

α_{q,p,x^{•}}^{−1} : q ∘ (p ∘ x^{•}) ≅ (q ∘ p) ∘ x^{•}

and so the component of the coherence isomorphism

π_{q,p,x} : P_{E}(q)P_{E}(p)(x) ≅ P_{E}(q ∘ p)(x)

is defined to be l_{C,Z}(α_{q,p,x^{•}}^{−1}). Naturality in q, p and x is clear by definition. Note that by Lemma 3.1.11 there are many other descriptions of this same component, namely

π_{q,p,x} = r_{D,Z}(α_{q,p,x^{•}}^{−1} ∘ g_{•})

for any D and g : C → D. Using this and Lemmas 3.2.1 and 3.2.5, one can exhibit any component of any bicategorical homomorphism coherence diagram, as the image of a diagram of coherence isomorphisms in Poly_{E}, by a right projection of one of Poly_{E}’s homs. By Theorem 3.1.10 all such diagrams commute.

3.2.7. Definition. A polynomial functor over E is a functor which is isomorphic to a composite of functors of the form Σ_{f}, Δ_{g} and Π_{h}, where f and g can be arbitrary morphisms of E, and h can be an exponentiable morphism of E.

It follows from Theorem 3.2.6 that a functor between slices of E is polynomial if and only if it is in the essential image of P_{E}.

3.2.8. Definition. Let X ∈ E. A monad T on E/X is a polynomial monad if it is isomorphic to a monad of the form P_{E}(p), where p is a monad on X in Poly_{E}. A morphism ϕ : S → T of monads on E/X is a polynomial monad morphism if ϕ factors as

[figure: S; P^{E}(q); P^{E}(p); T; ι_{1}; P^{E}(ϕ′); ι_{2}]

where ι_{1} and ι_{2} are isomorphisms of monads, and ϕ′ : q → p is a morphism of monads on X in Poly_{E}.

We conclude this section by observing that the hom functors of P_{E} are faithful and conservative.

3.2.9. Proposition. For any category E with pullbacks and objects X, Y ∈ E, the hom functor (P_{E})_{X,Y} is faithful and conservative.

Proof. Considering the instance of (6) in which x = 1_{X}, it is clear that f_{4,1_{X}} = f_{1}, and so by Lemma 3.2.4 (P_{E})_{X,Y} (f) uniquely determines f_{1}. Let us now consider the case x = q_{1}. In that case C = A′ and the morphisms C′_{2} → C and C′_{2} → A′, namely the projections of the pullback defining C′_{2}, have a common section s_{1} : A′ → C′_{2}. Applying Lemma 2.2.6 to the bottom distributivity pullback, one obtains the sections s_{2} : A′ → C′_{3} and s_{3} : B′ → C′_{4} satisfying the naturality conditions of that lemma. Since the square (C_{4}, B, B′, C′_{4}) is a pullback, one induces unique s_{4} : B → C_{4} which is a section of the given map C_{4} → B and satisfies f_{4,x}s_{4} = s_{3}f_{1}. Applying Lemma 2.2.6, this time to the top distributivity pullback, one induces the natural sections s_{5} : A → C_{3} and s_{6} : A → C_{2}. From the naturality conditions of the sections so constructed and the commutativities in the original general diagram (6), it follows easily that f_{0} is equal to the composite

[figure: A; C_{2}; C = A′,; s_{6}]

which by construction and Lemma 3.2.4, is determined uniquely by (P_{E})_{X,Y} (f), and so (P_{E})_{X,Y} is faithful. If (P_{E})_{X,Y} (f) is invertible, then f_{1}, which we saw is the component at 1_{X} of this natural transformation, must also be invertible. Since f_{0} is a pullback along q_{2} of f_{1}, f_{0} is also invertible, and so (P_{E})_{X,Y} is conservative.

Example 2.10 of [11] shows that (P_{E})_{X,Y} is not full in general, and this is discussed further in Remark 3.3.4.

3.3. Enrichment over CAT_{pb}. Recall from [6] that the category CAT_{pb} of categories with pullbacks and pullback preserving functors is cartesian closed. The product in CAT_{pb} is as in CAT, and the internal hom [X, Y] is the category of pullback preserving functors X → Y and cartesian transformations between them. A CAT_{pb}-bicategory is a bicategory B whose homs have pullbacks and whose compositions

comp_{X,Y,Z} : B(Y, Z) × B(X, Y) → B(X, Z)

preserve them. The basic example is CAT_{pb} itself. A homomorphism F : B → C of CAT_{pb}-bicategories is a homomorphism of their underlying bicategories whose hom functors preserve pullbacks. The point of this section is to show that for any category E with pullbacks, the homomorphism P_{E} is in fact a homomorphism of CAT_{pb}-bicategories.

For all f : A → B in a category E with pullbacks, it is easy to witness directly that the adjunction Σ_{f} ⊣ Δ_{f} lives in CAT_{pb}. So polynomial functors preserve pullbacks, and the diagram (5) may be regarded as living in CAT_{pb}. In other words, P_{E} sends 2-cells in Poly_{E} to cartesian transformations. Thus the hom maps of P_{E} may be regarded as landing in the homs of CAT_{pb}, that is, one can write

(P_{E})_{X,Y} : Poly_{E}(X, Y) → CAT_{pb}(E/X, E/Y).

In fact these functors themselves live in CAT_{pb}. To see this we first we note that

3.3.1. Lemma. For any category E with pullbacks and objects X, Y ∈ E, the category Poly_{E}(X, Y) has pullbacks, and a commutative square in Poly_{E}(X, Y) is a pullback if and only if its 1-component is a pullback in E.

Proof. One has a canonical inclusion

Poly_{E}(X, Y) ⟶ E^{←→→}

of Poly_{E}(X, Y) into the functor category. In general, given a category ℂ, an arrow α in ℂ, and a square

[figure: P; B; C; A; q; g; f; p]

in [ℂ, E], then if the naturality squares of f and g at α are pullbacks, then so are those for p and q, by the elementary properties of pullback squares. Since exponentiable maps are pullback stable, and one may choose pullbacks in E so that identity arrows are pullback stable, it follows that pullbacks in Poly_{E}(X, Y) exist and are formed as in E^{←→→}. Thus it follows in particular that a commutative square in Poly_{E}(X, Y) as in the statement is a pullback if and only if its 0 and 1-components are pullbacks in E. But from the elementary properties of pullbacks, if the 1-component square is a pullback then so is the 0-component.

and so one has

3.3.2. Proposition. For any category E with pullbacks and objects X, Y ∈ E, the functor (P_{E})_{X,Y} preserves and reflects pullbacks.

Proof. Since by Proposition 3.2.9 (P_{E})_{X,Y} is conservative, it suffices to show that it preserves pullbacks. But by the elementary properties of pullbacks, a square in CAT_{pb}(E/X, E/Y) is a pullback if and only if its component at 1_{X} is a pullback. Since by Lemma 3.2.4 the component at 1_{X} of (P_{E})_{X,Y} (f) is just f_{1}, the result follows from Lemma 3.3.1.

3.3.3. Theorem. Let E be a category with pullbacks. Then Poly_{E} is a CAT_{pb}-bicategory and

P_{E} : Poly_{E} ⟶ CAT_{pb}

is a homomorphism of CAT_{pb}-bicategories.

Proof. By Proposition 3.3.2 it suffices to show that the composition functors of Poly_{E} preserve pullbacks. One has for each X, Y, Z ∈ E, an isomorphism

[figure: Poly^{E}(Y, Z) × Poly_{E}(X, Y); Poly^{E}(X, Z); CAT_{pb}(E/X, E/Z); CAT_{pb}(E/Y, E/Z) × CAT_{pb}(E/X, E/Y); ∘; (P_{E})_{X,Z}; ∘; (P_{E})_{Y,Z}×(P_{E})_{X,Y}; ≅]

The vertical functors preserve and reflect pullbacks by Proposition 3.3.2, the bottom one preserves pullbacks since CAT_{pb} is a CAT_{pb}-bicategory by cartesian closedness, and so the composition functor for Poly_{E} preserves pullbacks as required.

3.3.4. Remark. In the case where E is locally cartesian closed, the work of Gambino and Kock [11] tells us more. In that case E is in particular a monoidal category via its cartesian product, and it acts as a monoidal category on its slices. Moreover polynomial functors over such E acquire a canonical strength. Then by Proposition 2.9 of [11], the image of P_{E} consists of the slices of E, polynomial functors over E and strong cartesian transformations between them.

3.3.5. Remark. Since for any category E with pullbacks the homs of Poly_{E} also have pullbacks, the above result can be applied to any of those homs in place of E, giving a sense in which the theory of polynomials may be iterated. Such iteration is implicit in unpublished work of Martin Hyland on fibrations, type theory and the Dialectica interpretation. Building on this, the thesis [31] of von Glehn provides polynomial models of type theory, and shows the possibility of a more sophisticated kind of iteration.

We conclude this section by describing the sense in which the hom functors of P_{E} are fibrations. First we require some preliminary definitions. Given a functor F : A → B, a morphism f : X → Y of A is F -cartesian when for all g : Z → X and h : F Z → F X such that F (g)h = F f, there exists a unique k : Z → X such that F k = h and fk = g. When F is a fibration in the bicategorical sense of Street [29], we say that it is a bi-fibration. This property on F can be formulated in elementary terms as follows: every f : B → F A factors as

[figure: B; F C; F B; g; F h]

where h is F -cartesian and g is an isomorphism.

3.3.6. Proposition. Suppose that E is a category with finite limits, and let X and Y ∈ E. Then

(P_{E})_{X,Y} : Poly_{E}(X, Y) ⟶ CAT_{pb}(E/X, E/Y)

is a bi-fibration, and every morphism of Poly_{E}(X, Y) is (P_{E})_{X,Y} -cartesian.

Proof. We begin by verifying that (ϕ_{0}, ϕ_{1}) : (p_{1}, p_{2}, p_{3}) → (q_{1}, q_{2}, q_{3}) as in

[figure: X; E_{1}; B_{1}; Y; B_{2}; E_{2}; p_{1}; p_{2}; p_{3}; q_{3}; q_{2}; q_{1}; ϕ_{0}; ϕ_{1}; pb]

is (P_{E})_{X,Y} -cartesian. Denoting by 1 the terminal object of E, note that P_{(}ϕ_{0}, ϕ_{1}) = ϕ_{1}. Given (ψ_{0}, ψ_{1}) : (r_{1}, r_{2}, r_{3}) → (q_{1}, q_{2}, q_{3}), and a cartesian natural transformation α : P_{E}(r_{1}, r_{2}, r_{3}) → P_{E}(q_{1}, q_{2}, q_{3}) such that P_{E}(ϕ_{0}, ϕ_{1})α = P_{E}(ψ_{0}, ψ_{1}), we must exhibit (β_{0}, β_{1}) : (r_{1}, r_{2}, r_{3}) → (p_{1}, p_{2}, p_{3}) unique such that P_{E}(β_{0}, β_{1}) = α and (ϕ_{0}, ϕ_{1})(β_{0}, β_{1}) = (ψ_{0}, ψ_{1}) in Poly_{E}. But the first of these equations forces β_{1} = α_{1}, and the second equation forces β_{0} to be induced as in

[figure: X; E_{1}; B_{1}; Y; B_{2}; E_{2}; q_{3}; q_{2}; q_{1}; ϕ_{0}; ϕ_{1}; pb; E_{3}; B_{3}; r_{3}; r_{2}; r_{3}; β_{0}; ψ_{0}; α_{1}; ψ_{1}]

The statement that (P_{E})_{X,Y} is a bi-fibration is a reformulation of the fact that if P : E/X → E/Y is a polynomial functor and ϕ : Q → P is a cartesian transformation, then Q is also polynomial. This appeared as Lemma 2.10 of [11], and the proof given there works at the present generality.

3.3.7. Corollary. Let E be a category with finite limits, X ∈ E, P and Q be monads on E/X, and ϕ : Q → P be a monad morphism. If P is a polynomial monad and ϕ is a cartesian monad morphism, then Q is a polynomial monad and ϕ is a polynomial monad morphism.

Proof. It suffices to show that if p is a monad on X in Poly_{E} and ϕ : QtoP_{E}(p) is a cartesian monad morphism, then ϕ factors as

[figure: Q; P_{E}(q); P_{E}(p); ι; P^{E}(ψ)]

where ι is an isomorphism of monads on E/X and ψ : q → p is a morphism of monads on X in Poly_{E}. At the level of endomorphisms this follows from Proposition 3.3.6, so it suffices to exhibit a monad structure on q making ι and ψ into monad morphisms. The unit η^{q} : 1 → q is defined to be the unique 2-cell such that ψη = η^{p} and P_{E}(η^{q}) = η^{P^{E}(q)} = ιη^{Q}, by the (P_{E})_{X,X}-cartesianness of ψ. The multiplication μ^{q} : q ∘ q → q is defined similarly as the unique 2-cell such that ψμ^{q} = μ^{p}(ψ ∘ ψ) and P_{E}(μ^{q}) = ιμ^{Q}(ι ∘ ι)^{−1}. The monad axioms for (q, η^{q}, μ^{q}) are deduced from those of p and the uniqueness aspects of ψ’s (P_{E})_{X,X}-cartesianness, and with respect to this structure, ι and ψ are monad morphisms essentially by definition.

4. Polynomials in 2-categories

We now develop the 2-categorical aspects of the theory of polynomials. In Section 4.1 we directly generalise Section 3 to the setting of 2-categories. One sense in which the study of polynomial 2-functors is richer than its 1-dimensional counterpart, is that one can consider whether such 2-functors are compatible with the theory of fibrations internal to the 2-category in which the corresponding polynomial lives. We review briefly the theory of fibrations in a 2-category in Section 4.2, and in Section 4.3 recall from [34] the general theory of familial 2-functors, which are those 2-functors (not necessarily polynomial) which are compatible with the 2-categorical theory of fibrations. Then in Section 4.4 we give conditions on polynomials and morphisms thereof, so that the resulting polynomial 2-functors and morphisms thereof are familial. Since 2-dimensional monad theory [5] is most usefully applied to sifted colimit preserving 2-monads as explained at the beginning of Section 4.5, we give conditions on a polynomial in Cat so that ensure that its corresponding polynomial 2-functor preserves sifted colimits in Theorem 4.5.1.

4.1. Polynomial 2-functors. In this section we extend the developments of Section 3 to the setting of 2-categories. Let K be a 2-category with pullbacks. Recall that when one speaks of pullbacks, or more generally any weighted limit in a 2-category, the universal property has a 2-dimensional aspect. That is, a square S in K is by definition a pullback in K if and only if for all X ∈ K, the square K(X, S) in CAT is a pullback in CAT. On objects this is the usual universal property of a pullback as in ordinary category theory, and on arrows this is the “2-dimensional aspect”. Recall also [17] that if K admits tensors with [1], then the usual universal property implies this 2-dimensional aspect, but in the absence of tensors, one must verify the 2-dimensional aspect separately.

Similarly when we speak of distributivity pullbacks in K we will also demand that these satisfy a 2-dimensional universal property. Let g : Z → A and f : A → B be in K. We describe first the 2-category PB(f, g) of pullbacks around (f, g). The underlying category of PB(f, g) is described as in Definition 2.2.1. Let (s, t) and (s′, t′) : (p, q, r) → (p′, q′, r′) be morphisms in PB(f, g). Then a 2-cell between them consists of 2-cells σ : s → s′ and τ : t → t′ of K, such that p′σ = 1_{p}, qσ = τq′ and 1_{r} = r′σ. Compositions for PB(f, g) are inherited from K. One thus defines a distributivity pullback around (f, g) in K to be a terminal object of the 2-category PB(f, g).

The meaning of distributivity pullbacks in this 2-categorical environment is the same as in the discussion of Section 2.2. First note that Σ_{f} : K/A → K/B is a 2-functor, and that by virtue of the 2-dimensional universal property of pullbacks in K, Δ_{f} : K/B → K/A is a 2-functor and Σ_{f} ⊣ Δ_{f} is a 2-adjunction. To say that all distributivity pullbacks along f exist in K is to say that Δ_{f} has a right 2-adjoint, denoted Π_{f} as before, and this right adjoint encodes the process of taking distributivity pullbacks along f. Such morphisms f in K are said to be exponentiable, and as in the 1-dimensional case, exponentiable maps are closed under composition and are stable by pullback along arbitrary maps. Moreover Lemmas 2.2.4, 2.2.5 and 2.2.6 remain valid in our 2-categorical environment. The verification of this is just a matter of using the 2-dimensional aspects of pullbacks and distributivity pullbacks to induce the necessary 2-cells, in exact imitation of how one induced the arrows during these proofs in Section 2.2.

Polynomials in K and cartesian morphisms between them are defined as in Section 3.1. Given polynomials p and q : X → Y, and cartesian morphisms f and g : p → q, a 2-cell ϕ : p → q consists of 2-cells ϕ_{0} : f → g_{0} and ϕ_{1} : f_{1} → g_{1} such that p_{1} = q_{1}ϕ_{0}, q_{2}ϕ_{0} = ϕ_{1}p_{2} and q_{3}ϕ_{1} = p_{3}. With compositions inherited from K one has a 2-category Poly_{K}(X, Y) together with left and right projections

[figure: K/X; Poly_{K}(X, Y); K/Y.; l_{X,Y}; r_{X,Y}]

For a composable sequence (p_{i})_{i} of polynomials as in

[figure: X_{i−1}; A_{i}; B_{i}; X_{i}; p_{i1}; p_{i2}; p_{i3}]

one defines the 2-category SdC(p_{i})_{i} of subdivided composites over (p_{i})_{i} as follows. The objects and arrows are defined as in Definitions 3.1.1 and 3.1.2. Given morphisms t and t′ : (Y, q, r, s) → (Y′, q′, r′, s′) of subdivided composites, a 2-cell τ : t → t′ consists of 2cells τ_{i} : t_{i} → t′_{i} in K for 0 ≤ i ≤ n, such that q_{1} = q′_{1}τ_{0}, q′_{2i}τ_{i1} = τ_{i}q_{2i}, q_{3} = q′_{3}τ_{n}, r_{i} = r′_{i}τ_{i1} and s_{i} = s′_{i}τ_{i}. Compositions in SdC(p_{i})_{i} are inherited from K. The process of taking the associated polynomial of a subdivided composite, as described in Definition 3.1.3, is 2functorial. The forgetful functors res_{n} and res_{0} become 2-functors. The fact that Lemmas 3.1.4 and 3.1.5 remain valid in our 2-categorical environment, is once again a matter of using the 2-dimensional aspects of pullbacks and distributivity pullbacks to induce the necessary 2-cells in the same way that the arrows during these proofs were induced in the 1-dimensional case. Thus these 2-categories of subdivided composites admit terminal objects, and so one may define the composition of polynomials as in Definition 3.1.7. Moreover composition is 2-functorial.

Lemma 3.2.4 gives a direct description of the arrow map of the hom functors of P_{E} as being induced by the universal properties of pullbacks and distributivity pullbacks. Thus in our 2-categorical setting, with the 2-dimensional aspects of these universal properties available, we can do the same one dimension higher and induce directly the components of the modification induced by a 2-cell between maps of polynomials. Thus we have 2-functors

(P_{K})_{X,Y} : Poly_{K}(X, Y) → 2-CAT(K/X, K/Y)

for all objects X and Y of a 2-category K with pullbacks. We now describe the structure that polynomials in a 2-category form.

4.1.1. Definition. A 2-bicategory consists of a bicategory B whose hom categories are endowed with 2-cells making them 2-categories and the composition functors

comp_{X,Y,Z} : B(Y, Z) × B(X, Y) → B(X, Z)

are endowed with 2-cell maps making them into 2-functors. In addition we ask that the coherence isomorphisms of B be natural with respect to the 3-cells.

Since a 2-bicategory B is a degenerate sort of tricategory, we shall call the 2-cells in its homs 3-cells of B.

4.1.2. Examples.

1. Given a 2-category K with pullbacks, the bicategory Span_{K} has the additional structure of a 2-bicategory in which a 3-cell f → g consists of a 2-cell ϕ as in

[figure: X; A; Y; B; s_{1}; t_{1}; t_{2}; s_{2}; f; g; ϕ]

such that s_{2}ϕ = id and t_{2}ϕ = id.

2. Dually one has a 2-bicategory Cospan_{K} of cospans in any 2-category K with pushouts.

3. Any strict 3-category such as 2-CAT is a 2-bicategory.

4.1.3. Definition. A homomorphism F : B → C of 2-bicategories is a homomorphism of their underlying bicategories whose hom functors are endowed with 2-cell maps making them into 2-functors, and whose coherence data is natural with respect to 3-cells.

4.1.4. Theorem. Let K be a 2-category with pullbacks. One has a 2-bicategory Poly_{K} whose objects are those of K, whose hom between X and Y ∈ K is Poly_{K}(X, Y), and whose compositions are defined as above. Moreover with object, arrow and 2-cell maps defined as in the categorical case, and 3-cell map as defined above, one has a homomorphism

P_{K} : Poly_{K} ⟶ 2-CAT

of 2-bicategories.

Proof. By the way that things have been set up, Lemma 3.1.8 and Theorem 3.1.10 lift to our 2-categorical setting, with the extra naturality of the coherences coming from the 2-dimensional aspect of all the universal properties being used. Thus Poly_{K} is a 2-bicategory. Since in the proof of Theorem 3.2.6 the coherences of P_{E} were obtained from associativity coherences in Poly_{E}, the extra naturality enjoyed by the associativities in Poly_{K} gives the extra naturality required for the coherences of P_{K}. Thus P_{K} is a homomorphism of 2-bicategories.

The notions polynomial 2-functor, polynomial 2-monad and morphism of polynomial 2-monads are defined as in Definitions 3.2.7 and 3.2.8. Similarly one may speak of polynomial pseudo monads when the coherences are themselves also in the essential image of P_{K}.

4.1.5. Example. Suppose that a morphism U : E → B in a 2-category K with finite limits is both exponentiable and a classifying discrete opfibration in the sense of [35]. One can then define a discrete opfibration in K to be U-small when it arises by pulling back U. By definition U-small discrete opfibrations are pullback stable in K. Often they are also closed under composition, and when this is the case, one can consider the full sub-2-bicategory S_{U} of Poly_{K} consisting of those polynomials

[figure: I; A; C; J; s; p; t]

such that p is a U-small discrete opfibration. The condition of being a classifying discrete opfibration then implies that the polynomial

[figure: 1; E; B; 1; U]  (10)

is a biterminal object in S_{U}(1, 1). As such it admits a canonical pseudo-monad structure. When K = Cat and U is the forgetful functor Set_{f,•} → Set_{f} from the category of finite pointed sets to that of finite sets, a U-small discrete opfibration is one with finite fibres, and these are evidently closed under composition. By the finitary analogue of [34] Corollary 5.12, the endofunctor associated to (10) is the finite “Fam” construction, which associates to a category its finite coproduct completion. Replacing U by U^{op} gives a polynomial pseudo monad on Cat whose underlying endofunctor gives the finite product completion of a category. To summarise, the finite coproduct and finite product completion pseudo monads on Cat are polynomial pseudo monads.

The 2-categorical analogues of Proposition 3.3.6 and Corollary 3.3.7 are also valid, with proofs adapted from the 1-dimensional case in the same way as above. We record these results as follows.

4.1.6. Proposition. Let K be a 2-category with finite limits and let X and Y ∈ K. Let P be a polynomial 2-functor K/X → K/Y, and T be a polynomial 2-monad on K/X. Let ϕ : Q → P be a 2-natural transformation, and ψ : S → T be a morphism of 2-monads.

1. If ϕ is cartesian then Q is a polynomial 2-functor.

2. If ψ is cartesian then S is a polynomial 2-monad and ψ is a morphism of polynomial 2-monads.

4.2. Fibrations 2-monads. The 2-monads whose algebras are fibrations and opfibrations to be recalled here, play two roles in this work: (1) as part of the background to the discussion of familial 2-functors below in Section 4.3, and (2) as examples of polynomial 2-monads in Proposition 4.2.3. Fibrations internal to a 2-category were introduced by Street in [27].

Elementary descriptions of fibrations were given in Section 2 of [35] in terms of cartesian 2-cells. A similar 2-categorical reformulation of split fibrations, in which cleavages were expressed 2-categorically via the notion of chosen cartesian 2-cell, was given in Section 3 of [34]. Thus for any 2-category K, one can define fibrations and split fibrations in K. Moreover, given fibrations f : A → B and g : C → D in K, a morphism of fibrations (u, v) : f → g is a commutative square

[figure: A; C; D; B; u; g; v; f]

such that post-composition with u sends f-cartesian 2-cells to g-cartesian 2-cells. When f and g are split fibrations, (u, v) is a strict morphism when post-composing with u preserves chosen cartesian 2-cells.

Thus one has 2-categories Fib(K) and SFib(K) of fibrations, morphisms thereof and 2-cells; and of split fibrations and strict morphisms respectively, coming with forgetful 2-functors into K^{[1]}. Dually an opfibration in a general 2-category K is a fibration in the 2-category K^{co} obtained by reversing 2-cells. We freely use the associated dual notions, such as (chosen) f-opcartesian 2-cells below, and we define

OpFib(K) = Fib(K^{co})^{co}  SOpFib(K) = SFib(K^{co})^{co}.

When K has comma objects, Street [27] observed that fibrations can be regarded as pseudo algebras for certain easy to define 2-monads. The comma squares

[figure: 1_{B} ↓ f; A; B; B; q_{f}; f; 1_{B}; Φ_{K}(f); λ_{f}; f ↓ 1_{B}; B; B; A; Ψ_{K}(f); 1_{B}; f; p_{f}; λ′_{f}]

describe the effect on objects of the underlying endofunctors of 2-monads Φ_{K} and Ψ_{K} on K^{[1]}. For f : A → B the component of the unit of Φ_{K} is of the form (η_{f}, 1_{B}) where η_{f} is unique such that

Φ_{K}(f)η_{f} = f q_{f}η_{f} = 1_{A} λ_{f}η_{f} = id

and the f-component of the multiplication is of the form (μ_{f}, 1_{B}) where μ_{f} is unique such that

Φ_{K}(f)μ_{f} = Φ_{K}^{2}(f) q_{f}μ_{f} = q_{f}q_{Φ_{K}(f)} λ_{f}μ_{f} = (λ_{f}q_{Φ_{K}(f)})λ_{Φ_{K}(f)}.

The unit and multiplication of Ψ_{K} are described dually.

We follow the established notation of 2-dimensional monad theory by denoting, for a 2-monad T on a 2-category K, T -Alg_{s}, Ps-T -Alg and Kl(T) the 2-categories of strict T - algebras and strict maps, pseudo T -algebras and strong^{2} maps and the Kleisli 2-category of T respectively. Moreover one has

U^{T} : T -Alg_{s} ⟶ K  F_{T} : K ⟶ Kl(T)

the right adjoint part of the Eilenberg-Moore adjunction for T, and the left adjoint part of the Kleisli adjunction for T respectively. We proceed now to exhibit explicit descriptions of these for the 2-monads Φ_{K} and Ψ_{K}.

Denote by K_{colax}^{[1]} the 2-category of functors [1] → K, colax natural transformations between them, and modifications; and by K_{lax}^{[1]} the 2-category of functors [1] → K, lax natural transformations between them, and modifications. Thus a morphism f → g of K_{colax}^{[1]} is the unlabelled data in

[figure: A; C; D; B; g; f]

and for K_{lax}^{[1]} the 2-cell is in the opposite direction. Since strict natural transformations are degenerate instances of lax and colax ones, one has canonical inclusions K^{[1]} ↪ K_{colax}^{[1]} and K^{[1]} ↪ K_{lax}^{[1]}. The following result is known, though perhaps formulated slightly more globally than usual.

4.2.1. Proposition. [20, 27] Let K be a 2-category with comma objects.

1. One has isomorphisms

Ps-Φ_{K}-Alg ≅ Fib(K)  Φ_{K}-Alg_{s} ≅ SFib(K)
Ps-Ψ_{K}-Alg ≅ OpFib(K)  Ψ_{K}-Alg_{s} ≅ SOpFib(K)

commuting with the evident 2-functors into K^{[1]}.

2. One has isomorphisms

Kl(Φ_{K}) ≅ K_{colax}^{[1]}  Kl(Ψ_{K}) ≅ K_{lax}^{[1]}

commuting with the evident 2-functors out of K^{[1]}.

Proof. In the case K = Cat of (1) is completely standard. See [20] for a recent discussion. The result for general K follows by a representable argument since the 2-monads Φ_{K} and Ψ_{K} are described in terms of limits, and the notions of cartesian and opcartesian 2-cell are representable. The isomorphisms (2) are easily exhibited by using the universal property of comma objects and the definition of Kl(Φ_{K}) and Kl(Ψ_{K}).

2Meaning that the coherence data consists of invertible 2-cells

The fibre of the codomain 2-functor K^{[1]} → K over B ∈ K is exactly the slice 2category K/B, and these 2-monads restrict to the 2-monads Φ_{K,B} and Ψ_{K,B} on K/B defined originally by Street in [27]. Using Proposition 4.2.1 one then has an explicit description of the algebras of Φ_{K,B} (resp. Ψ_{K,B}) as fibrations (resp. opfibrations) with codomain B. Similarly 1-cells x → y of Kl(Φ_{K,B}) (resp. Kl(Ψ_{K,B})) may be identified with lax triangles

[figure: X; Y; B; y; x; X; Y; B.; y; x]

For any nice symmetric monoidal category V over which one may wish to enrich, one has a notion of monoidal V-category, and so in particular taking V = Cat (with the cartesian tensor product), one has a canonical notion of monoidal 2-category^{3}. In this sense, for any 2-bicategory B and object B therein, the hom B(B, B) is a monoidal 2category. Following [18, 21] we define a pseudo monoid in a monoidal 2-category K, with unit and multiplication denoted u : I → M and m : M ⊗ M → M, to be colax idempotent (resp. lax idempotent) when u ⊗ M ⊣ m ⊣ M ⊗ u (resp. M ⊗ u ⊣ m ⊣ u ⊗ M).

4.2.2. Definition. Let B be a 2-bicategory and B ∈ B. Then a pseudo monad (resp. 2-monad) on B in B is a pseudo monoid (resp. monoid) in the monoidal 2-category B(B, B). A pseudo monad on B in B is colax idempotent (resp. lax idempotent) when its corresponding pseudo monoid in B(B, B) is so.

Writing [n] for the ordinal {0 < ... < n} one has a cospan in Cat as on the left

[figure: [0]; [1]; [0]; δ_{1}; δ_{0}; B; B^{[1]}; B; d_{1}; d_{0}; B^{[1]}; B; B; B; d_{0}; 1_{B}; 1_{B}; d_{1}]

and cotensoring this with B gives the span in K in the middle, where Z^{A} denotes the cotensor of Z ∈ K with the category A. This span fits into comma square as depicted on the right in the previous display. To some extent the following result is implicit in the work of Street [27, 28, 29], and all that we have done is to observe that Street’s approach to the fibrations 2-monads exhibits them as polynomial 2-monads. In fact, since the underlying endofunctors come from spans, they are examples of “linear” polynomial 2-functors.

4.2.3. Proposition. Let K be a 2-category with comma objects and pullbacks and let B ∈ K.

3Monoidal bicategories in the most general sense whose underlying bicategory is a 2-category are weaker than this.

1. Φ_{K,B} is the result of applying P_{K} to a colax idempotent 2-monad in Poly_{K} whose underlying endomorphism is

[figure: B; B^{[1]}; B^{[1]}; B.; d_{0}; 1; d_{1}]

2. Ψ_{K,B} is the result of applying P_{K} to a lax idempotent 2-monad in Poly_{K} whose underlying endomorphism is

[figure: B; B^{[1]}; B^{[1]}; B.; d_{1}; 1; d_{0}]

Proof. The two statements are dual, so we consider just the monad Φ_{K,B}. By the elementary properties of comma squares and pullbacks, one can factor the defining comma square of Φ_{K,B}(f) = Φ_{K}(f) as

[figure: 1_{K,B} ↓ f; B^{[1]}; B; B; B; A; d_{1}; 1_{K,B}; 1_{K,B}; f; d_{0}; Φ_{K,B}(f); pb]

and so one has Φ_{K,B}(f) = Σ_{d_{1}}Δ_{d_{0}}(f). This expresses on objects that Φ_{K,B} is the result of applying P_{K} to the endopolynomial of the statement.

Recall that the inclusion Δ ↪ Cat is a cocategory object, and as described in [24, 29], the standard presentation of (topologists’) Δ as a subcategory of Cat has the 2-categorical feature that the successive generating coface and codegeneracy maps are adjoint. Thus the diagram

[figure: [0]; [1]; [2]; [3]; ......; [0]; [0]; σ_{0}; σ_{1}; σ_{0}; ⊥; ⊥; σ_{2}; σ_{0}; ⊥; ⊥; ⊥; ⊥; t; δ_{0}=t; t; t; ...; b; δ_{1}=b; b; b; ...]  (11)

in which each functor labelled as “t” picks out the top element of its codomain, and each functor labelled as “b” picks out a bottom element, is a colax idempotent 2-monad in Cospan_{Cat}. Cotensoring it with an object B in any finitely complete 2-category K, gives a colax idempotent 2-monad in Span_{K} and by means of the inclusion Span_{K} ↪ Poly_{K}, one has a polynomial colax idempotent 2-monad on B. The observation that associated 2-monad on K/B, obtained via application of P_{K}, is the 2-monad Φ_{K,B} is easily verified, and was implicit in Section 2 of [29].

4.2.4. Remark. In general d_{1} is a split fibration and d_{0} is a split opfibration. In 2categories K, such as the case K = Cat, in which fibrations and opfibrations are exponentiable, it follows that Φ_{K,B} and Ψ_{K,B} are themselves left adjoints. For such situations fibrations and opfibrations are thus also coalgebras for 2-comonads (ie those obtained from Φ_{K,B} and Ψ_{K,B} by taking right adjoints), and the forgetful 2-functors U^{Φ_{K,B}} and U^{Ψ_{K,B}} create all colimits.

4.3. Familial 2-functors. We now recall, and to some extent update, the theory of familial 2-functors from [34]. Intuitively, a familial 2-functor is one that is compatible in an appropriate sense with the theory of fibrations recalled in the previous section. In Section 4.4 we will identify conditions on polynomials in a 2-category which ensure that the corresponding 2-functor is familial.

The compatibility of familial 2-functors with the theory of fibrations is expressed formally by the formal theory of monads [26], in which monads in a 2-category A were organised in various useful ways into 2-categories. Since this material is used so extensively in this section, we recall it briefly now.

We denote a monad in a 2-category A as a pair (A, t) where A ∈ A, t is the underlying one-cell of the monad on A in A, and we denote the unit and multiplication 2-cells as η^{t} and μ^{t} respectively. A lax morphism f : (A, t) → (B, s) in A consists of an arrow f : A → B in A, and a “coherence” 2-cell f^{l} : sf → ft which satisfies f^{l}(η^{s}f) = fη^{t} and f^{l}(μ^{s}f) = (fμ^{t})(f^{l}t)(sf^{l}). A colax morphism f : (A, t) → (B, s) in A consists of an arrow f : A → B in A, and f^{c} : ft → sf satisfying f^{c}(fη^{t}) = η^{s}f and f^{c}(fμ^{t}) = (μ^{s}f)(sf^{c})(f^{c}t). Lax and colax morphisms of monads were called “monad functors” and “monad opfunctors” in [26] respectively.

Given a monad (A, t) in A one may have an associated Eilenberg-Moore object, which is a type of 2-categorical limit, whose universal 0 and 1-cell data is denoted as A^{t} and u^{t} : A^{t} → A respectively. The corresponding colimit notion is that of a Kleisli object, the universal 0 and 1-cell data of which is denoted A_{t} and f_{t} : A → A_{t} respectively. See [26] for the precise definitions. When A = Cat, A^{t} is the category of algebras and A_{t} is the Kleisli category, and in the general situation u^{t} has a left adjoint and f_{t} has a right adjoint. When A is the 2-category of 2-categories, a monad in A is a 2-monad (K, T), and the 0 and 1-cell data of the Eilenberg-Moore and Kleisli objects are denoted as

U^{T} : T -Alg_{s} ⟶ K  F_{T} : K ⟶ Kl(T)

respectively.

In general, when the 2-category A admits Eilenberg-Moore objects, given monads (A, t) and (B, s) in A, and an arrow f : A → B, then 2-cells f^{l} : sf → ft providing coherence data of a lax monad morphism are in bijection with liftings \overline{f} to the level of algebras as on the left in

[figure: A^{t}; B^{s}; B; A; \overline{f}; u^{s}; f; u^{t}; =; A_{s}; B_{s}; B; A; \underline{f}; f_{s}; f; f_{t}; =]

and dually, when A admits Kleisli objects, colax coherence data f^{c} : ft → sf is in bijection with extensions of f to \underline{f} as on the right in the previous display.

4.3.1. Remark. Let K be a 2-category with comma objects and pullbacks and f : A → B be a morphism therein. The 2-functor Σ_{f} : K/A → K/B clearly extends to lax triangles, and so one has \underline{Σ}_{f} : Kl(Φ_{K,A}) → Kl(Φ_{K,B}) such that \underline{Σ}_{f}F_{Φ_{K,A}} = F_{Φ_{K,B}}Σ_{f}. Such an extension is equivalent to the data of a 2-natural transformation σ_{f} providing the coherence datum for a colax morphism of 2-monads

(Σ_{f}, σ_{f}) : (K/A, Φ_{K,A}) ⟶ (K/B, Φ_{K,B})

and so by taking mates [19] with respect to Σ_{f} ⊣ Δ_{f}, also to the coherence datum δ_{f} for a lax morphism of 2-monads

(Δ_{f}, δ_{f}) : (K/B, Φ_{K,B}) ⟶ (K/A, Φ_{K,A}).

This last is in turn equivalent to lifting Δ_{f} to the level of split fibrations, that is to say, to giving a 2-functor \overline{Δ}_{f} : Φ_{K,B}-Alg_{s} → Φ_{K,A}-Alg_{s} such that U^{Φ_{A}} \overline{Δ}_{f} = Δ_{f}U^{Φ_{B}}. The 2-functor \overline{Δ}_{f} witnesses the pullback stability of split fibrations.

We recall now the familial 2-functors of [34]. For a 2-functor T : K → L and an object X ∈ K, we denote by T_{X} : K/X → L/T X the 2-functor given on objects by applying T to morphisms into X. A local right adjoint K → L is a 2-functor T : K → L equipped with a left adjoint to T_{X} for all X ∈ K. Given an adjunction as on the left

[figure: A; B; R; L; ⊥; A/X; B/RX; R_{X}; ⊥]

and X ∈ A, one always has an adjunction as on the right in the previous display. Thus when K has a terminal object 1, to exhibit T as a local right adjoint, it suffices to give a left adjoint to T_{1}.

4.3.2. Definition. Let K and L be 2-categories with comma objects, and suppose that K has a terminal object 1. Then a familial 2-functor K → L consists of local right adjoint T : K → L together with \overline{T}_{1} : K → Φ_{T 1}-Alg_{s} such that U^{Φ_{T 1}} \overline{T}_{1} = T_{1}.

Familial 2-functors are exactly those 2-functors which are compatible with fibrations because of 4.3.3. Proposition. Let K and L be 2-categories with comma objects, suppose that K has a terminal object 1 and let T be a 2-functor. To give T the structure of a familial 2-functor is to give the coherence data ϕ^{T} for a lax morphism

(T^{[1]}, ϕ^{T}) : (K^{[1]}, Φ_{K}) ⟶ (L^{[1]}, Φ_{L})

of 2-monads.

Proof. It is straight forward to adapt Theorem 6.6 of [34] to provide, given \overline{T}_{1}, the lifting of T^{[1]} to a 2-functor Φ_{K}-Alg_{s} → Φ_{L}-Alg_{s}. Conversely, given such a lifting one recovers \overline{T}_{1} by restricting to split fibrations in K into 1.

Implicit in Definition 5.2 of [34] is the idea that morphisms of familial 2-functors are simply cartesian 2-natural transformations. In this work we wish to adopt a more specialised notion which is compatible with Propostion 4.3.3.

4.3.4. Definition. Let S and T be familial 2-functors K → L. Then a 2-natural transformation α : S → T is familial when it is cartesian and for all X ∈ K, α’s naturality square with respect to the unique map t_{X} : X → 1 is a morphism of split fibrations (α_{X}, α_{1}) : St_{X} → T t_{X}.

4.3.5. Lemma. Let α : S → T be a familial natural transformation between familial 2-functors K → L, and f : A → B be a split fibration in K. Then the naturality square

[figure: SA; T A; T B; SB; α_{A}; T f; α_{B}; Sf]

is a morphism (α_{A}, α_{B}) : Sf → T f of split fibrations in L.

Proof. Recall from Lemma 6.3 of [34] that a 2-cell ψ as indicated on the left in

[figure: X; SA; x; y; ψ; X; SD; SA; SC; g_{2}; Sh_{2}; Sh_{1}; g_{1}; Sδ; ψ_{1}; Sψ_{2}]

is chosen Sf-cartesian if and only if ψ_{2} is chosen f-cartesian, where x = S(h_{1})g_{1} and y = S(h_{2})g_{2} are S-generic factorisations in the sense of [34], and ψ_{1} and ψ_{2} are unique such that the composite on the right in the previous display equal to ψ and ψ_{1} is chosen St_{D}-cartesian. We must show that if ψ is chosen Sf-cartesian, then α_{A}ψ is chosen T fcartesian. In

[figure: X; SD; SA; SC; g_{2}; Sh_{2}; Sh_{1}; g_{1}; Sδ; ψ_{1}; Sψ_{2}; T D; T A; T C; T h_{2}; T h_{1}; T δ; T ψ_{2}; α_{D}; α_{C}]

α_{D}ψ_{1} is chosen T t_{D}-cartesian since (α_{D}, α_{1}) is a morphism of split fibrations St_{D} → T t_{D}, and so the result follows by Lemma 6.3 of [34] applied to T.

When T : K → L is familial we denote by \overline{T} : Φ_{K}-Alg_{s} → Φ_{L}-Alg_{s} the lifting of T^{[1]} corresponding to ϕ^{T}. Then one obtains the following result immediately from Lemma 4.3.5.

4.3.6. Proposition. Let S and T be familial 2-functors and α : S → T be a cartesian natural transformation between them. Then α is familial if and only if it lifts to a 2-natural transformation \overline{α} : \overline{S} → \overline{T}.

We freely use and apply the dual notions and results, an opfamilial 2-functor being one which is compatible in the same way with opfibrations. A familial (resp. opfamilial) 2monad is one whose underlying endo-2-functor, unit and multiplication are familial (resp. familial).

4.3.7. Remark. All the examples familial and opfamilial 2-monads exhibited in [34] turn out to be familial and opfamilial 2-monads in the more restricted sense of this article. For those that arise from polynomials, we shall establish this from general results below.

4.4. Familial 2-functors from polynomials. In this section we identify conditions on polynomials in a 2-category and their morphisms, ensuring that the associated 2functors and 2-natural transformations are familial. The central result to this effect appears in this section as Theorem 4.4.5. The task of proving this result breaks up into that of identifying conditions ensuring that 2-functors of the form Δ_{f} and Π_{f}, and the “Beck-Chevalley 2-cells” lift to the level of split fibrations. These conditions are presented in turn in Lemmas 4.4.1-4.4.4 below.

4.4.1. Lemma. [12] Let f : A → B be a split opfibration in a 2-category K with pullbacks and comma objects.

1. One has \underline{Δ}_{f} : Kl(Φ_{K,B}) → Kl(Φ_{K,A}) such that \underline{Δ}_{f}F_{Φ_{K,B}} = F_{Φ_{K,A}}Δ_{f}.

2. If f is a discrete opfibration then \underline{Σ}_{f} ⊣ \underline{Δ}_{f}.

Proof. (1): Given (k, γ) : x → y in Kl(Φ_{K,B}), we pullback to obtain X_{2} and Y_{2} in

[figure: X_{2}; Y_{2}; A; X; Y; B; q_{1}; x; f; Δ_{f} x; h_{2}; q_{2}; y; Δ_{f} y; k; k_{2}; γ; γ_{2}]

γ_{2} is the chosen f-opcartesian lift of γq_{1}, and then k_{2} is unique such that Δ_{f}(y)k_{2} = h_{2} and q_{2}k_{2} = kq_{1}. One defines \underline{Δ}_{f}(k, γ) = (k_{2}, γ_{2}). Given a 2-cell κ : (k, γ) → (k′, γ′), then by the opcartesianness of γ_{2} one has κ_{2} : Δ_{f}(y)k_{2} → Δ_{f}(y)k′_{2} unique such that κ_{2}γ_{2} = γ′_{2} and fκ_{2} = yκq_{1}. By the 2-dimensional universal property of the pullback defining Y_{2}, one has κ_{3} : k_{2} → k′_{2} unique such that Δ_{f}(y)κ_{3} = κ_{2} and q_{2}κ_{3} = κq_{1}. We then define \underline{Δ}_{f}(κ) = κ_{3}. The 2-functoriality of these assignations follows easily from the uniqueness of the various lifts in these constructions and the 2-dimensional universal property of pullbacks in K.

(2): Note that in the above diagram q_{1} and q_{2} are the components of the counit of Σ_{f} ⊣ Δ_{f} at x and y respectively. Thus the commutativity of the diagram ensures that the counit is natural with respect to lax triangles, and 2-naturality follows similarly. It remains to verify the 2-naturality of the unit of Σ_{f} ⊣ Δ_{f} with respect to lax triangles when f is a discrete opfibration. Denoting the defining pullback of Δ_{f}Σ_{f}x as on the left in

[figure: X_{2}; X; B; A; q_{x}; fx; f; Δ_{f} Σ_{f} x; pb; X; Y; A; k; y; x; γ]

η_{x} : X → X_{2} is unique such that Δ_{f}Σ_{f}(x)η_{x} = x and q_{x}η_{x} = 1_{X}. Naturality with respect to (k, γ) amounts to checking that η_{y}k = k_{2}η_{x} and γ = γ_{2}η_{x} in

[figure: X; Y; A; k; y; x; γ; B; f; A; f; X_{2}; q_{x}; Y_{2}; q_{y}; k_{2}; Δ_{f} Σ_{f} y; γ_{2}; X; η_{x}; Y; η_{y}; k; x; γ]

in which γ_{2} is unique such that fγ_{2} = fγq_{x}. Thus fγ_{2}η_{x} = fγ and so since f is a discrete opfibration, the uniqueness of lifts implies γ_{2}η_{x} = γ and Δ_{f}Σ_{f}(y)k_{2}η_{x} = ky. From this last one obtains the first equation of

Δ_{f}Σ_{f}(y)η_{y}k = Δ_{f}Σ_{f}(y)k_{2}η_{x}  q_{y}k_{2}η_{x} = q_{y}η_{y}k

and the second equation is also easily verified, so that by the joint monicness of (Δ_{f}Σ_{f}(y), q_{y}), one has η_{y}k = k_{2}η_{x}. The verification of the 2-dimensional part of naturality proceeds straight forwardly along similar lines, and so is left to the reader.

4.4.2. Lemma. [12] Let f : A → B be an exponentiable split opfibration in a 2-category K with pullbacks and comma objects.

1. One has \overline{Π}_{f} : Φ_{K,A}-Alg_{s} → Φ_{K,B}-Alg_{s} such that U^{Φ_{K,B}} \overline{Π}_{f} = Π_{f}U^{Φ_{K,A}}.

2. If f is a discrete opfibration then \overline{Δ}_{f} ⊣ \overline{Π}_{f}.

Proof. (1): By the formal theory of monads the data of the extension \underline{Δ}_{f} of Lemma 4.4.1(1) is equivalent to that of a 2-natural transformation ∂_{f} providing the coherence datum for an oplax morphism

(Δ_{f}, ∂_{f}) : (K/B, Φ_{K,B}) ⟶ (K/A, Φ_{K,A}).

Since f is exponentiable, this is in turn equivalent, by taking mates with respect to the adjunction Δ_{f} ⊣ Π_{f}, to the data of a 2-natural transformation π_{f} providing the coherence datum of a lax morphism

(Π_{f}, π_{f}) : (K/A, Φ_{K,A}) ⟶ (K/B, Φ_{K,B}).

This last is in turn equivalent to the lifting \overline{Π}_{f} of Π_{f} to the level of split fibrations.

(2): The data of the adjunction \underline{Σ}_{f} ⊣ \underline{Δ}_{f} established in Lemma 4.4.1(2) corresponds by the formal theory of monads to the data of an adjunction of oplax morphisms of 2monads whose underlying 2-adjunction is Σ_{f} ⊣ Δ_{f}. This means that in addition to having the oplax coherence data σ_{f} and ∂_{f} described above, one has the compatibility of the unit η_{f} and counit ε_{f} of the adjunction Σ_{f} ⊣ Δ_{f} with respect to these coherences, which in explicit terms is the commutativity of

[figure: Φ_{K,A}; Δ_{f}Σ_{f}Φ_{K,A}; Δ_{f}Φ_{K,B}Σ_{f}; Φ_{K,A}Δ_{f}Σ_{f}; η_{f} Φ_{K,A}; Δ_{f} σ_{f}; ∂_{f} Σ_{f}; Φ_{K,A}η_{f}; Σ_{f}Δ_{f}Φ_{K,B}; Σ_{f}Φ_{K,A}Δ_{f}; Φ_{K,B}Σ_{f}Δ_{f}.; Φ_{K,B}; Σ_{f} ∂_{f}; σ_{f} Δ_{f}; Φ_{K,B}ε_{f}; ε_{f} Φ_{K,B}]

In terms of string diagrams (which go from top to bottom) in the 2-category of 2-categories (see [15]), the above commutative diagrams are expressed as

[figure: η_{f}; σ_{f}; ∂_{f}; Φ_{K,A}; Σ_{f}; Φ_{K,A}; Δ_{f}; =; η_{f}; Δ_{f}; Σ_{f}; Φ_{K,A}; Φ_{K,A}; ε_{f}; σ_{f}; ∂_{f}; Φ_{K,B}; Σ_{f}; Φ_{K,B}; Δ_{f}; =; ε_{f}; Δ_{f}; Σ_{f}; Φ_{K,B}; Φ_{K,B}]  (12)

It suffices now to verify that the lax coherence data δ_{f} and π_{f} are compatible with the unit η′_{f} and counit ε′_{f} of Δ_{f} ⊣ Σ_{f} in the same way, which is to say that

[figure: η′_{f}; π_{f}; δ_{f}; =; η′_{f}; ε′_{f}; π_{f}; δ_{f}; =; ε′_{f}]  (13)

because then by the formal theory of monads this corresponds to giving the rest of the data of the required adjunction \overline{Δ}_{f} ⊣ \overline{Π}_{f}. The definition of δ_{f} and π_{f} as mates of σ_{f} and ∂_{f} in explicit terms says that

[figure: η_{f}; σ_{f}; ε_{f}; =; δ_{f}; η′_{f}; ∂_{f}; ε′_{f}; =; π_{f}]  (14)

and so the left equation of (13) is established by the calculation

[figure: η′; π; δ; =; η′; ∂; ε′; η′; η; σ; ε; =; η′; ∂; η; σ; ε; =; η′; η; ε; =; η′]

which uses (12), (14) and the adjunction triangle equations. The right equation in (13) follows from a similar calculation.

Recall that given a commutative square in K as on the left

[figure: A; C; D; B; h; g; k; f; K/A; K/C; K/D; K/B; Σ_{h}; Δ_{g}; Σ_{k}; Δ_{f}; α; K/A; K/C; K/D; K/B; Δ_{h}; Π_{g}; Δ_{k}; Π_{f}; β]  (15)

one has a canonical 2-natural transformation α is obtained from Σ_{k}Σ_{f} = Σ_{g}Σ_{h} and the adjunctions Σ_{f} ⊣ Δ_{f} and Σ_{g} ⊣ Δ_{g}. If f and g are exponentiable, then by taking right adjoints one has a canonical 2-natural transformation β as on the right.

4.4.3. Lemma. If in a 2-category K with comma objects and pullbacks, the left-most square in (15) underlies a morphism of split opfibrations f → g, then α extends to a 2-natural transformation \underline{α} as on the left

[figure: Kl(Φ_{K,A}); Kl(Φ_{K,C}); Kl(Φ_{K,D}); Kl(Φ_{K,B}); ^{\underline{Σ}^{h}}; \underline{Δ}_{g}; _{\underline{Σ}_{k}}; \underline{Δ}_{f}; \underline{α}; ^{Φ_{K,A}-Alg^{s}}; ^{Φ_{K,C}-Alg^{s}}; _{Φ_{K,D}-Alg_{s}}; _{Φ_{K,B}-Alg_{s}}; ^{\overline{Δ}^{h}}; \overline{Π}_{g}; _{\overline{Δ}_{k}}; \overline{Π}_{f}; \overline{β}]

and if f and g are exponentiable, then β lifts to a 2-natural transformation \overline{β} as on the right.

Proof. By the formal theory of monads α extends to \underline{α} if and only if α underlies a monad 2-cell, that is to say, satisfies axioms of compatibility with the colax monad morphism structures on Σ_{h}Δ_{f} and Δ_{g}Σ_{k}. When f and g are exponentiable this in turn is equivalent, by the calculus of mates, to asking that β satisfy compatibility with respect to the lax monad morphism structures on Π_{f}Δ_{h} and Δ_{k}Π_{g}, which is moreover equivalent to the existence of the lifting \overline{β}. Thus it suffices to exhibit \underline{α}, in other words, that α is 2-natural with respect to lax triangles.

For the 1-dimensional part of this naturality note that the component of α at x : X → B is as shown on the right

[figure: X_{2}; X; B; D.; C; A; x_{3}; x; k; g; h; x_{2}; f; pb; X_{2}; X; B; D; C; A; X_{3}; x_{3}; x; k; g; h; x_{2}; α_{x}; x_{5}; x_{4}; pb]

Denoting by (k_{2}, ψ_{2}) the result of pulling back (k, ψ) along f

[figure: X_{2}; Y_{2}; A; X; Y; B; x; f; x_{2}; y; y_{2}; k; k_{2}; ψ; ψ_{2}]

as in Lemma 4.4.1, the desired naturality comes down to the commutativity of the prism (X_{2}, Y_{2}, Y_{3}, X_{3}, C, A) in

[figure: X_{3}; Y_{3}; C; X; Y; D; x_{5}; kx; g; x_{4}; y_{5}; ky; y_{4}; k; k_{3}; kψ; ψ_{3}; A; X_{2}; Y_{2}; k_{2}; α_{x}; α_{y}; h; ψ_{2}]

in which (k_{3}, ψ_{3}) is the result of pulling back (k, kψ) along g. Since gψ_{3}α_{x} = ghψ_{2}, and both ψ_{3}α_{x} and hψ_{2} are chosen g-opcartesian, it follows that ψ_{3}α_{x} = hψ_{2}. Taking codomains of this gives y_{4}k_{3}α_{x} = y_{4}α_{y}k_{2}, and y_{5}k_{3}α_{x} = y_{5}β_{y}k_{2}, so k_{3}α_{x} = α_{y}k_{2}. The uniqueness part of opcartesianness can be used to verify 2-naturality.

Given a commutative triangle as on the left

[figure: A; B; C; h; g; f; K/A; K/B; K/C; Δ_{h}; Σ_{g}; Σ_{f}; κ]  (16)

one has a canonical 2-natural transformation as on the right obtained from Σ_{g}Σ_{h} = Σ_{f} and Σ_{h} ⊣ Δ_{h}. When moreover f and g are split fibrations, since split fibrations compose, the 2-functors Σ_{f} and Σ_{g} lift to 2-functors

\overline{Σ}_{f} : Φ_{K,A}-Alg_{s} ⟶ Φ_{K,C}-Alg_{s}  \overline{Σ}_{g} : Φ_{K,B}-Alg_{s} ⟶ Φ_{K,C}-Alg_{s}

respectively.

4.4.4. Lemma. The 2-natural transformation (16) lifts to a 2-natural transformation

[figure: ^{Φ_{K,A}-Alg^{s}}; ^{Φ_{K,B}-Alg^{s}}; Φ_{K,C}-Alg_{s}; ^{\overline{Δ}^{h}}; ^{\overline{Σ}^{g}}; ^{\overline{Σ}^{f}}; \overline{κ}]

when f and g each have the structure of a split fibration.

Proof. Let p : E → B be a split fibration. We have to show that the component κ_{p} is a morphism of split fibrations, that is to say, that post-composition with κ_{p} preserves chosen cartesian 2-cells. So we consider a chosen fp_{2}-cartesian 2-cell ψ as in

[figure: X; E_{2}; E; B; C; A; x_{1}; h; x_{2}; κ_{p}; p; g; f; p_{2}; ψ; pb]

and we must show that κ_{p}ψ is chosen gp-cartesian. By the way in which one describes the cleavage for a composite of split fibrations, to say that κ_{p}ψ is chosen gp-cartesian is to say that κ_{p}ψ is chosen p-cartesian and pκ_{p}ψ is chosen g-cartesian; and to say that ψ is chosen fp_{2}-cartesian is to say that ψ is chosen p_{2}-cartesian and p_{2}ψ is chosen f-cartesian. By the way in which one describes the cleavage of a morphism resulting from pulling back a split fibration, to say that ψ is chosen p_{2}-cartesian is to say that κ_{p}ψ is chosen p-cartesian. Since h is a morphism of split fibrations and p_{2}ψ is chosen f-cartesian, hp_{2}ψ is chosen g-cartesian, and so the result follows.

4.4.5. Theorem. Let K be a 2-category with pullbacks and comma objects. Denote by P : K/I → K/J the polynomial 2-functor associated to the polynomial on the left

[figure: I; E; B; J; s; p; t; I; E_{1}; B_{1}; J; B_{2}; E_{2}; s_{1}; p_{1}; t_{1}; t_{2}; p_{2}; s_{2}; f_{2}; f_{1}; pb; =; =]

and by ϕ : P → Q the 2-natural transformation associated to the morphism of polynomials indicated on the right in the previous display. Then

1. If p has the structure of a split opfibration and t has the structure of a split fibration, then P lifts to a 2-functor \overline{P} : Φ_{K,I}-Alg_{s} → Φ_{K,J}-Alg_{s} such that U^{Φ_{K,J}} \overline{P} = P U^{Φ_{K,I}}.

2. If in the context of (1) I is discrete, then P is a familial 2-functor.

3. If (f_{2}, f_{1}) : p_{1} → p_{2} is a morphism of split opfibrations and (f_{1}, 1_{J}) : t_{1} → t_{2} is a morphism of split fibrations, then ϕ lifts to a 2-natural transformation \overline{ϕ} : \overline{P} → \overline{Q} such that U^{Φ_{K,J}} \overline{ϕ} = ϕU^{Φ_{K,I}}.

4. If in the context of (3) I is discrete, then ϕ is a familial 2-natural transformation.

Proof. When I is discrete Φ_{K,I} is the identity 2-monad, and so (2) follows from (1) by the definition of familial 2-functor, and (4) follows from (3) by the definition of familial 2-natural transformation. To obtain (1), define \overline{P} = \overline{Σ}_{t}\overline{Π}_{p}\overline{Δ}_{p}, where \overline{Π}_{p} exists by Lemma 4.4.1 and the remarks immediately following that result, and \overline{Σ}_{t} exists by the composability of split fibrations. To obtain (3), note that ϕ may be obtained as the composite

[figure: K/I; K/E_{1}; K/B_{1}; K/J.; K/B_{2}; K/E_{2}; Δ_{s_{1}}; Π_{p_{1}}; Σ_{t_{1}}; Σ_{t_{2}}; Π_{p_{2}}; Δ_{s_{2}}; Δ_{f_{2}}; Δ_{f_{1}}; ≅; β; κ]

The unnamed isomorphism is obtained by adjunction from the identity Σ_{f_{2}}Σ_{s_{1}} = Σ_{s_{2}} which clearly extends to the level of lax slices, and so this isomorphism lifts to the level of split fibrations by the same argument as that given in the first paragraph of the proof of Lemma 4.4.3. By Lemma 4.4.3 β also lifts to the level of split fibrations, and by Lemma 4.4.4 κ does too, and so (3) follows.

4.4.6. Remark. In subsequent work we shall also use the dual of the above result, in which K is replaced by K^{co}. For instance the dual version of (2) says that if I is discrete, p has the structure of a split fibration and t has the structure of a split opfibration, then P is opfamilial. Note also that when J is discrete, t, t_{1} and t_{2} are automatically split (op)fibrations in a unique way and f_{1} is a morphism thereof.

4.5. Preservation of sifted colimits. Two dimensional monad theory becomes a particularly powerful framework when applied to codescent object preserving 2-monads. For instance, as explained in [7, 23], a codescent object preserving 2-monad T on a 2category of the form Cat(E) automatically satisfies the conditions of Power’s general coherence theorem [23, 25]. Thus knowing T preserves codescent objects implies a coherence theorem for T -algebras in this case. In particular one recovers the usual coherence theorems for monoidal, braided monoidal and symmetric monoidal categories in this way, without any combinatorial analysis. Moreover as discussed in [32], knowing that a 2monad preserves codescent objects is one desirable condition leading to the ability to compute internal algebra classifiers involving T.

Codescent objects are particular instances of a class of 2-categorical colimits called sifted colimits, which include also reflexive coequalisers and filtered colimits. Recall that any weight J : C^{op} → Cat (with C a small 2-category) determines, by virtue of the cocompleteness of Cat as a 2-category, a functor

J ∗ − : [C, Cat] ⟶ Cat

given on objects by taking colimits in Cat weighted by J, and J is a sifted weight when J ∗ − preserves finite products. A sifted colimit is a weighted colimit whose weight is sifted. In other words, sifted colimits are exactly those colimits which in Cat commute with finite products. Sufficient conditions on a polynomial in Cat so that its corresponding polynomial 2-functor preserves sifted colimits is provided by

4.5.1. Theorem. The polynomial 2-functor associated to a polynomial

[figure: I; A; B; J; s; p; t]

in Cat such that I is discrete and p is a discrete fibration or a discrete opfibration with finite fibres, preserves sifted colimits.

Proof. It suffices to show that Π_{p}Δ_{s} preserves sifted colimits since Σ_{t} as a left adjoint preserves all colimits. We consider the case where p is a discrete fibration; the proof for the case where p is a discrete opfibration is similar. By Theorem 4.4.5(1) applied in the case K = Cat^{co}, one has the commutative diagram

[figure: Cat/I; ^{Ψ_{K,E}-Alg^{s}}; ^{Ψ_{K,B}-Alg^{s}}; Cat/B.; Cat/E; ^{\overline{Δ}^{s}}; ^{\overline{Π}^{p}}; U^{Ψ_{K,B}}; Π_{p}; Δ_{s}; U^{Ψ_{K,E}}]

By Remark 4.2.4 U^{Ψ_{K,E}} and U^{Ψ_{K,B}} create all colimits, and so it suffices to show that \overline{Π}_{p} preserves sifted colimits.

Since Ψ_{K,E}-Alg_{s} and Ψ_{K,B}-Alg_{s} are 2-equivalent to the functor 2-categories [E, Cat] and [B, Cat], and in these terms \overline{Δ}_{p} corresponds to the process of precomposition with p, by Lemma 4.4.2(2) one may identify \overline{Π}_{p} with the process of right Kan extension along p. But since p is a discrete fibration, such right Kan extensions are computed simply by taking products over the fibres of p. Since these products are finite, and limits and colimits in [B, Cat] are componentwise, the result follows by the definition of “sifted colimit”.

4.5.2. Examples. By Theorem 4.5.1 the finite product completion and finite coproduct completion endofunctors of Cat described in Example 4.1.5 preserve sifted colimits.

4.5.3. Examples. In part 3 of [2] Batanin and Berger exhibit various flavours of “operad” as algebras of polynomial monads over Set. The underlying endo-polynomial in all of their examples is of the form

[figure: I; E; B; I; s; p; t]  (17)

where p is a function with finite fibres. The algebras of the associated monad on Set/I are the particular flavour of operad under consideration in Set, however for the homotopical aspects of that work, it is also important to regard (17) as a componentwise discrete polynomial in Cat. The corresponding 2-monad on Cat/I is familial and opfamilial by Theorem 4.4.5 and preserves sifted colimits by Theorem 4.5.1.

5. Examples of polynomial 2-monads on Cat

In this section we exhibit the 2-monads

1. M for monoidal categories,

2. S for symmetric monoidal categories,

3. B for braided monoidal categories,

4. C_{fin} for categories with finite coproducts, and

5. P_{fin} for categories with finite products

on Cat, as polynomial 2-monads. These are all well-known cartesian 2-monads which were, for instance, basic examples for Kelly and his collaborators [5, 16, 18], in the establishment of 2-dimensional monad theory. We recall them as such in Section 5.1, and then in Section 5.2 exhibit their underlying endofunctors as polynomial. In Section 5.3 we reexpress Johnstone’s idea of bagdomain data, as a way of indirectly exhibiting the unit and multiplication of a polynomial monad. We apply this method in Section 5.4 to our examples. Many other examples are exhibited in [33].

5.1. The examples as cartesian 2-monads. Let X be a category. Then the objects of M(X), S(X), B(X), C_{fin}(X) and P_{fin}(X) are the same, namely they are finite sequences (x_{1}, ..., x_{n}) of objects of X. Denoting \underline{n} as the discrete category \{1, ..., n\} with n objects, we regard a sequence (x_{1}, ..., x_{n}) as a functor x : \underline{n} → X.

A morphism x → y in C_{fin}(X) consists of a function ϕ and a natural transformation \overline{ϕ} as on the left in

[figure: \underline{m}; \underline{n}; X; ϕ; y; x; \overline{ϕ}; x_{1}; x_{2}; x_{3}; x_{4}; y_{1}; y_{2}; y_{3}; ^{\overline{ϕ}^{1}}; ^{\overline{ϕ}^{2}}; _{\overline{ϕ}_{3}}; _{\overline{ϕ}_{4}}]

An alternative point of view is that such a morphism is a function (ϕ) decorated by the morphisms of X (the components of \overline{ϕ}) as indicated in the example on the right. Since it is useful to be able to reason precisely from this latter point of view, we make a brief notational digression.

We denote by 𝕊 the category whose objects are natural numbers, and whose morphisms m → n are functions \underline{m} → \underline{n}. The category 𝕊 is a skeleton of the category of finite sets and functions. We denote a sequence (x_{1}, ..., x_{n}) of objects of X alternatively as (x_{k})_{1≤k≤n}, or as (x_{k})_{k}, as convenience dictates. The result of concatenating a sequence of sequences ((x_{k,l})_{1≤l≤n_{k}})_{1≤k≤m}, is denoted (x_{k,l})_{k,l}. Implicit in this notation is the identification

{(k, l) : 1 ≤ k ≤ m, 1 ≤ l ≤ n_{k}} = {1, ..., n_{1} + ... + n_{m}}

via the lexicographic ordering of the former. Given morphisms ϕ : m_{1} → m_{2} and ϕ_{k} : n_{1,k} → n_{2,ϕ(k)} in 𝕊 for 1 ≤ k ≤ m_{1}, we denote by ϕ(ϕ_{k})_{k} the morphism Σ_{k}n_{1,k} → Σ_{k}n_{2,k} given by (ϕ(ϕ_{k})_{k})(k, l) = (ϕ(k), ϕ_{k}(l)). In these terms a general morphism of C_{fin}(X), is of the form

(ϕ, (\overline{ϕ}_{k})_{1≤k≤m}) : (x_{k})_{1≤k≤m} ⟶ (y_{k})_{1≤k≤n}

where ϕ : m → n is in 𝕊, and \overline{ϕ}_{k} : x_{k} → y_{ϕk} is in X for 1 ≤ k ≤ m. We refer to the datum ϕ of such a morphism as the indexing function.

The unit for C_{fin} is given by the full inclusion of sequences of length 1. On objects the components μ_{X} : C_{fin}^{2}(X) → C_{fin}(X) are given by concatenation of sequences, and on morphisms by

μ_{X}(ϕ, (ϕ_{k}, (\overline{ϕ}_{k,l})_{l})_{k}) = (ϕ(ϕ_{k})_{k}, (\overline{ϕ}_{k,l})_{k,l}),

which in intuitive terms, is just substitution of decorated functions. With the notation provided it is straight forward to verify that (C_{fin}, η, μ) is a cartesian 2-monad on Cat.

We have already considered a version of this 2-monad in Example 4.1.5. The difference is that here, we have taken a skeleton of the category of finite sets to index our families, and have more carefully book-kept the combinatorics. It is straight forward to check that C_{fin} is lax idempotent^{4} and thus to exhibit the pseudo algebras of either version as being the same, namely, categories with finite coproducts. The virtue of the more pain-staking approach taken here, is that C_{fin} is a 2-monad rather than just a pseudo monad.

One defines the 2-monad P_{fin} as P_{fin}(X) = C_{fin}(X^{op})^{op}. In direct terms, a morphism of P_{fin}(X) is of the form

(ϕ, (\overline{ϕ}_{k})_{1≤k≤m}) : (x_{k})_{1≤k≤m} ⟶ (y_{k})_{1≤k≤n}

where ϕ : n → m is in 𝕊, and \overline{ϕ}_{k} : x_{ϕk} → y_{k} is in X for 1 ≤ k ≤ n. This is a colax idempotent cartesian 2-monad, and its pseudo algebras are categories with finite products.

The morphisms of the category S(X) are defined to be those of C_{fin}(X) (or equally well, of P_{fin}(X)) whose underlying indexing functions are bijections. It is clear that S is a sub-2-monad of C_{fin}, and that the inclusion ι_{C}^{S} : S ↪ C_{fin} is a cartesian monad morphism. It follows that S is also a cartesian 2-monad. It is straight forward to verify directly that pseudo S-algebras are exactly unbiased^{5} symmetric monoidal categories, and strict algebras are exactly symmetric strict monoidal categories. Moreover the various notions of S-morphism – lax, colax, pseudo and strict – correspond to symmetric lax, colax, strong and strict monoidal functors respectively. Similarly one defines the cartesian 2-monad M for monoidal categories, by defining the morphisms of M(X) as those of C_{fin}(X) whose indexing functions are identities.

4Or in older language, C_{fin} is a Kock-Zöberlein 2-monad of colimit like variance.

As explained in [15] the 2-monad B for braided monoidal categories, there denoted 𝔹 ≀ (−), is given similarly as for S, except that the indexing bijections are replaced by indexing braids, in the definition of the morphisms of B(X). The process of taking the underlying permutation of a braid, gives a cartesian monad morphism π : B → S, and so B is also a cartesian 2-monad. Once again the different types of algebras and algebra morphisms of B reconcile in the expected way with braided (strict) monoidal categories and braided (lax, colax, strong or strict) monoidal functors. One also has a cartesian monad morphism ι_{B}^{M} : M → B, whose components can be regarded as the identity on objects inclusion which regards morphisms of M(X) as identity braids whose strings are decorated by the morphisms of X. The composite πι_{B}^{M} is denoted ι_{S}^{M}, and its components regards morphisms of M(X) as identity permutations whose strings are decorated by the morphisms of X.

To summarise, one has a diagram of cartesian 2-monads and cartesian monad morphisms as on the left

[figure: M; B; S; ^{C^{fin}}; _{P_{fin}}; ι_{B}^{M}; π; ι_{C}^{S}; ι_{P}^{S}; ι_{S}^{M}; ℕ; 𝔹; ℙ; 𝕊; 𝕊^{op}]  (18)

and the result of evaluating at 1 is denoted as on the right. Each monad morphism here is componentwise an identity on objects, and so in particular each functor on the right is the identity on objects. On the right one has M(1) = ℕ the natural numbers, B(1) = 𝔹 the braid category, S(1) = ℙ the permutation category, and so on. Recall, the non-empty hom-sets of ℙ are ℙ(n, n) = Σ_{n}, where Σ_{n} is the group of permutations of n elements, and similarly, 𝔹(n, n) is Br_{n}, the n-th braid group. In this section we shall establish that the left diagram of (18) is a diagram of polynomial 2-monads and morphisms thereof.

5.2. Underlying endofunctors as polynomial functors. We denote by 𝕊_{∗} the coslice 1/𝕊, whose objects may be regarded as pairs (i, n) where n ∈ ℕ and 1 ≤ i ≤ n, with i regarded as a “chosen basepoint”. A morphism (i, m) → (j, n) of 𝕊_{∗} is thus a function f : \underline{m} → \underline{n} such that fi = j. By definition, 𝕊_{∗} comes with a forgetful functor U^{𝕊} : 𝕊_{∗} → 𝕊, and U^{𝕊} is a discrete opfibration with finite fibres. The fibre over n ∈ 𝕊 may be identified with the set \underline{n} = \{1, ..., n\}. Since U^{𝕊} is a discrete opfibration, and (U^{𝕊})^{op} is a discrete fibration, U^{𝕊} and (U^{𝕊})^{op} are exponentiable functors.

5This means that an n-ary tensor product is defined for all n, and invertible coherence maps are given. The coherence theorems one has available enable one to identify these with symmetric monoidal categories defined in the usual biased way, with a unit and binary product, and so we regard pseudo S-algebras as symmetric monoidal categories, disregarding the biased/unbiased distinction.

5.2.1. Lemma. The underlying endofunctors of C_{fin} and P_{fin} are the result of applying P_{Cat} to

[figure: 1; 𝕊_{∗}; 𝕊; 1; U^{𝕊}; 1; 𝕊_{∗}^{op}; 𝕊^{op}; 1; (U^{𝕊})^{op}]

respectively.

Proof. We give the proof for C_{fin}, the case of P_{fin} follows similarly. Provisionally we write P for the 2-functor corresponding to the polynomial on the left in the above display. By definition one has

[figure: 1; 𝕊_{∗}; 𝕊; 1; X; X × 𝕊_{∗}; P_{∗}X; P X; U^{𝕊}; p_{X}; q_{X}; dpb; pb]  (19)

and we now proceed to identify P X with C_{fin}(X). An object of P X may be regarded as a functor h : [0] → P X, and thus also as a pair n : [0] → 𝕊 together with h : [0] → P X such that qh = n. By Δ_{U^{𝕊}} ⊣ Π_{U^{𝕊}} and since q_{X} = Π_{U^{𝕊}}(p_{X}), such an h is in bijection with k : (U^{𝕊})^{−1}{n} → X × 𝕊_{∗} over 𝕊_{∗}, but this in turn is just an n-tuple (x_{1}, ..., x_{n}) of objects of X. Thus an object of P X is a pair (n, x) where n ∈ ℕ and x : \underline{n} → X. Similarly regarding arrows of P X as functors [1] → P X and using the adjointness Δ_{U^{𝕊}} ⊣ Π_{U^{𝕊}} in the same way, one finds that a morphism (m, x) → (n, y) of P X consists of ϕ : \underline{m} → \underline{n} in 𝕊 together with \overline{ϕ} as in

[figure: \underline{m}; \underline{n}; X; ϕ; y; x; \overline{ϕ}]

and so P and C_{fin} agree on objects. Note that P_{∗}X also has an easy explicit description. Namely, an object is a triple (i, n, x) where (n, x) ∈ P X and 1 ≤ i ≤ n, and a morphism (i, m, x) → (j, n, y) consists of ϕ and \overline{ϕ} as above making (ϕ, \overline{ϕ}) : (m, x) → (n, y) a morphism of P X, such that ϕi = j. Moreover, all the functors participating in (19) also admit straight forward direct descriptions in these terms.

We must now verify that P f = C_{fin}(f) for f : X → Y. Note that P f is induced from f by the pullbacks and distributivity pullbacks that go into defining P X and P Y, whereas C_{fin}(f) is the functor described by composing with f, that is on objects one has C_{fin}(f)(n, x) = (n, fx). Let us define C_{fin}_{∗}(f) : P_{∗}X → P_{∗}Y to be the functor given on objects by (i, n, x) ↦ (i, n, fy). By the uniqueness aspects of the universal properties of the pullbacks and distributivity pullbacks involved in defining P Y, it suffices to show that

[figure: X × 𝕊_{∗}; P_{∗}X; P X; 𝕊; P Y; P_{∗}Y; Y × 𝕊_{∗}; q_{X}; q_{Y}; f×1_{𝕊∗}; C_{fin}_{∗}(f); C_{fin}(f)]

commutes. Given that everything in this diagram has been made so explicit, this is a straight forward calculation.

The functor (ι_{C}^{S})_{1} : ℙ → 𝕊 is the inclusion of the maximal subgroupoid of 𝕊, and similarly (ι_{P}^{S})_{1} is also a maximal subgroupoid inclusion. We define ℙ_{∗} as the maximal subgroupoid of 𝕊_{∗}. It comes with a forgetful functor U^{ℙ} : ℙ_{∗} → ℙ. Equivalently, ℙ_{∗} = 1/ℙ. The functor U^{ℙ} fits into pullback squares in

[figure: ℙ_{∗}; ℙ; 𝕊; 𝕊_{∗}; U^{ℙ}; (ι_{C}^{S})_{1}; U^{𝕊}; pb; 1; 1; ℙ_{∗}; ℙ; 𝕊^{op}; 𝕊_{∗}^{op}; U^{ℙ}; (ι_{P}^{S})_{1}; (U^{𝕊})^{op}; pb; 1; 1]

By Propositions 3.3.6 and 4.1.6 the underlying endofunctor of S is a polynomial 2-functor, and one may regard these morphisms of polynomials as corresponding to the 2-natural transformations ι_{C}^{S} and ι_{P}^{S}. Similarly by pulling back along π_{1} and (ι_{S}^{M})_{1}, one defines U^{𝔹} : 𝔹_{∗} → 𝔹 and U^{ℕ} : ℕ_{∗} → ℕ, exhibits B and M as polynomial 2-functors, and π, ι_{S}^{M} and ι_{B}^{M} as arising from morphisms of polynomials. To summarise, we have

5.2.2. Corollary. At the level of the underlying endofunctors, the left diagram of (18) is in the essential image of P_{Cat}.

To establish that (18) is a diagram of polynomial 2-monads and morphisms thereof, one way to proceed would be to write down the polynomial monad structures for C_{fin} and P_{fin} explicitly, and then use Proposition 4.1.6. To avoid computations involving composites of such polynomials, for instance when verifying monad axioms, we use an alternative approach. This approach is described in general in the next section, and applied to our examples in Section 5.4.

5.3. Bagdomain data as polynomial monad structures. The construction of the finite coproduct and finite product completion were seen to underlie polynomial pseudo monads in Cat in Example 4.1.5. However as explained in Section 5.1 these constructions underlie 2-monads, and a framework for these is described in this section. It is little more than an explicit encoding of some of the developments of Section 2 of [13], in the language of polynomials.

Recall that when a category E has pullbacks the codomain functor cod : E^{[1]} → E is a fibration, and that a morphism of E^{[1]} is cod-cartesian if and only if its underlying square in E is a pullback square.

5.3.1. Definition. Let E be a category with pullbacks and p : E → B be a morphism therein. Then a p-fibration is a cod-cartesian arrow into p, and a morphism of p-fibrations is a morphism in E^{[1]} ↓ p between p-fibrations.

As such a p-fibration consists of an arrow f : X → Y of E together with (u, v) fitting into a pullback square

[figure: X; Y; B; E; f; v; p; u; pb; X_{1}; Y_{1}; Y_{2}; X_{2}; f_{1}; v_{3}; f_{2}; u_{3}; pb]

as on the left. In this context we say that (u, v) is a p-fibration structure on f. For a morphism of p-fibrations (f_{1}, u_{1}, v_{1}) → (f_{2}, u_{2}, v_{2}) one has morphisms u_{3} and v_{3} as on the right in the previous display such that u_{3}u_{2} = u_{1} and v_{3}v_{2} = v_{1}. Clearly, u_{3} is uniquely determined by v_{3} and the universal property of the pullback containing (f_{2}, u_{2}, v_{2}), and so in minimalistic terms, (u_{3}, v_{3}) amounts to v_{3} : Y_{1} → Y_{2} over B.

5.3.2. Example. Let E = Set and regard U^{ℕ} : ℕ_{∗} → ℕ ∈ Set. Explicitly, ℕ_{∗} = {(i, j) : i ∈ ℕ, 1 ≤ j ≤ i} and U^{ℕ}(i, j) = i. Observe that for n ∈ ℕ, |(U^{ℕ})^{−1}{n}| = n. To give a function f : X → Y the structure of a U^{ℕ}-fibration is by definition to give functions u and v fitting into a pullback square

[figure: X; Y; ℕ; ℕ_{∗}; f; v; U^{ℕ}; v; pb]

and so f must have finite fibres since U^{ℕ} does. Moreover for y ∈ Y such that f^{−1}{y} = n, u restricts to a bijection u_{y} between f^{−1}{y} and (U^{ℕ})^{−1}{n}, and so amounts to a linear order on f^{−1}{y}. Conversely given a function f : X → Y with finite fibres and a linear order on each fibre, one determines v by the formula vy = |f^{−1}{y}|, and then u by taking ux = (n, i), where n = |f^{−1}{fx}| and i is x’s position in the linear order on f^{−1}{fx}. Thus a U^{ℕ}-fibration is a function with finite fibres together with a linear order on each fibre.

Recall that a double category (resp. double functor) is a category (resp. functor) internal to CAT. Given a category E we denote by D(E) the double category as on the left

[figure: E^{[2]}; E^{[1]}; E; id_{E}; ^{dom^{E}}; _{cod_{E}}; comp^{E}; X_{1}; X_{0}; d_{1}; d_{0}]

whose objects are those of E, vertical arrows and horizontal arrows are morphisms of E, and squares are commutative squares in E. Any double category X has, by forgetting horizontal identities and compositions, an underlying graph internal to CAT, consisting of the source and target functors as on the right in the previous display. Our conventions are that X_{0} is the category of objects and vertical arrows, and X_{1} is the category of horizontal arrows and squares between them.

In the context of Definition 5.3.1 we define

U_{p} : D(p) ⟶ D(E)

a graph morphism internal to CAT, as follows. The category D(p)_{0} of objects and vertical arrows of D(p) is E, and (U_{p})_{0} = 1_{E}. The category D(p)_{1} of horizontal arrows and squares of D(p), is the category of p-fibrations and their morphisms. Every p-fibration has an underlying arrow of E, and every morphism of p-fibrations has an underlying square, the assignations of which provide (U_{p})_{1}.

5.3.3. Theorem. Let E be a category with finite limits and p : E → B an exponentiable morphism therein. There is a bijection between the following types of data:

1. Unit and multiplication 2-cells in Poly_{E} making

[figure: 1; E; B; 1; p]

the underlying endoarrow of a monad in Poly_{E}.

2. Double category structures on D(p) making U_{p} a double functor.

Proof. We denote by P : 1 → 1 the endoarrow of (1). To give the data of a 2-cell u : 1_{1} → P in Poly_{E} is to give (u_{1}, u_{2}) fitting into a pullback square

[figure: 1; 1; B; E; u_{1}; p; u_{2}; pb; X; X; 1; 1; 1_{X}; pb; X; X; Y; Y; 1_{X}; f; 1_{Y}; f; pb]

as on the left. Given this data any identity arrow 1_{X} : X → X acquires the structure of a p-fibration, namely that which makes the square on the middle in the previous display a morphism 1_{X} → 1_{1} of p-fibrations. Given a morphism f : X → Y of E, with respect to these p-fibration structures on identity arrows, the square on the right in the previous display is clearly a morphism of p-fibrations. Thus one has a functor id_{p} : E → D(p)_{1} such that (U_{p})_{1}id_{p} = id_{E}. Conversely, such a functor amounts to assigning a p-fibration structure to each identity map in such a way that for all f : X → Y the right square above is a morphism of p-fibrations. Thus in particular there is a p-fibration structure on 1_{1}, which amounts to (u_{1}, u_{2}) as on the left in the previous display. The processes just described are easily verified to exhibit a bijection between 2-cells u : 1_{1} → P of Poly_{E} and functors id_{p} as above.

To give a functor comp_{p} : D(p)_{1}×_{E}D(p)_{1} → D(p)_{1} such that (U_{p})_{1}comp_{p} = comp_{E}(U_{p})_{2}, where (U_{p})_{2} is induced in the evident way using (U_{p})_{1}, is to give, for each composable pair f : X → Y, g : Y → Z in E together with p-fibration structures on f and g, a p-fibration structure on the composite gf, and that this assignation be functorial. This functoriality means that given morphisms of p-fibrations (u, v) : f → f′ and (v, w) : g → g′ as in

[figure: X; Y; Z; Z′; Y′; X′; f; g; w; g′; f′; u; v]

the composite square underlies a p-fibration morphism (u, w) : gf → g′f′.

Suppose that a 2-cell m : P ∘ P → P in Poly_{E} is given. Then given also a composable pair f : X → Y, g : Y → Z in E together with p-fibration structures on f and g, one has

[figure: 1; E; B; 1; E; B; 1; B × E; F; B^{(2)}; E^{(2)}; X; Y; Z; p; p; π_{E}; f; g; pb; dpb; pb; pb; pb]

in which the lower pullback squares witness the p-fibration structures on f and g. By the universal property of B × E one induces the unique arrow Y → B × E commuting with the morphisms into B and E. Thus the bottom right pullback is around (p, π_{E}), and so by the distributivity pullback one induces the morphisms Y → F and Z → B^{(2)}. Finally using the top right pullback one induces X → E^{(2)}. The squares (X, Y, F, E^{(2)}) and (Y, Z, B^{(2)}, F) so arising are pullbacks, and so the composite pullback

[figure: X; Y; Z; B^{(2)}; F; E^{(2)}; f; g; pb; pb; E; B; m_{1}; p; m_{2}; pb]

exhibits a p-fibration structure on gf, and so we have described the object map of the functor comp_{p}.

The composite p^{(2)} : E^{(2)} → B^{(2)} is the middle map of the composite polynomial P ∘P. When f and g are the morphisms E^{(2)} → F and F → B^{(2)} respectively, the top row of vertical arrows in the previous display are identities, and so one has a p-fibration structure on p^{(2)}. Moreover for general f and g, the composite of the top pullbacks of the previous display exhibits a morphism gf → p^{(2)} of p-fibrations. From

[figure: 1; E; B; 1; E; B; 1; B × E; F; B^{(2)}; E^{(2)}; X′; Y′; Z′; p; p; π_{E}; f′; g′; pb; dpb; pb; pb; pb; X; Y; Z; f; g; w; v; u; pb; pb]

in which (u, v) and (v, w) are morphisms of p-fibrations, (u, w) is a morphism gf → g′f′ of p-fibrations, thus giving the arrow map for comp_{p}. In this way from a 2-cell m : P ∘P → P in Poly_{E}, one obtains the functor comp_{p} such that (U_{p})_{1}comp_{p} = comp_{E}(U_{p})_{2}.

Conversely given comp_{p}, the pullbacks appearing in the formation of P ∘ P exhibit p-fibration structures on E^{(2)} → F and F → B^{(2)}, and applying comp_{p} to this composable pair gives a p-fibration structure to p^{(2)}, which amounts to the components (m_{1}, m_{2}) of a 2-cell m : P ∘ P → P. It is straight forward to verify that the processes described here exhibit a bijection between such 2-cells and such functors comp_{p}. The straight forward verification that the unit and associative laws for u and m correspond with the unit and associative laws for horizontal composition in the double category D(p) is left to the reader.

It was the data of Theorem 5.3.3(1) that Johnstone named bagdomain data in Definition 2.1 of [13].

5.3.4. Remark. In the context of Theorem 5.3.3, one can consider polynomials as on the left

[figure: I; X; Y; J; s; f; t; I; X_{1}; Y_{1}; J; Y_{2}; X_{2}; s_{1}; f_{1}; t_{1}; t_{2}; f_{2}; s_{2}; u; v; pb; =; =]

in which the middle map f has the structure of a p-fibration, morphisms thereof as on the right in which the middle pullback square is a morphism of p-fibrations. We call such a polynomial a p-structured polynomial from I to J. By definition the process of pulling back in E carries along p-fibration structures, and by Theorem 5.3.3 one has a composition of pfibrations. Thus composition in Poly_{E} can be extended to a composition of p-structured polynomials. In this way one has a bicategory Poly_{p}, whose 1-cells are p-structured polynomials, together with a strict homomorphism of bicategories Poly_{p} → Poly_{E}, and the polynomial

[figure: 1; E; B; 1; p]

is by definition terminal in the hom category Poly_{p}(1, 1). The monad structure it acquires is by definition that of Theorem 5.3.3. Thus for any category E with finite limits, any monad in Poly_{E} on 1 arises in a manner analogous to the process described in Example 4.1.5.

5.3.5. Example. By concatenating linear orders on fibres, U^{ℕ}-fibrations as characterised in Example 5.3.2 can be composed, and this composition is functorial with respect to morphisms of U^{ℕ}-fibrations. The polynomial monad one gets by Theorem 5.3.3 is the monoid monad on Set. Regarding U^{ℕ} as a functor between discrete categories and arguing the same way, one recovers the monad M on Cat.

5.4. Exhibiting the examples. The foregoing discussion is adapted to the 2-categorical context in the following way. For an exponentiable morphism p : E → B in a 2-category K with pullbacks, we define p-fibrations and morphisms thereof as in Definition 5.3.1. Given p-fibrations (f_{1}, u_{1}, v_{1}) and (f_{2}, u_{2}, v_{2}) and morphisms thereof as in

[figure: X_{1}; Y_{1}; B; E; f_{1}; v_{1}; p; u_{1}; pb; X_{2}; Y_{2}; B; E; f_{2}; v_{2}; p; u_{2}; pb; X_{1}; Y_{1}; Y_{2}; X_{2}; f_{1}; v_{3}; f_{2}; u_{3}; pb; X_{1}; Y_{1}; Y_{2}; X_{2}; f_{1}; v_{4}; f_{2}; u_{4}; pb; X_{1}; Y_{1}; Y_{2}; X_{2}; f_{1}; v_{4}; f_{2}; u_{4}; v_{3}; u_{3}; α; β]

a 2-cell (u_{3}, v_{3}) → (u_{4}, v_{4}) is a pair (α, β) such that the cylinder on the right commutes, and u_{2}α = id and v_{2}β = id. In minimalistic terms using the 2-dimensional universal property of pullbacks, (α, β) is determined by the 2-cell β over B.

We call a category (resp. functor) internal to 2-CAT a double 2-category (resp. double 2-functor). For any 2-category K one has the double 2-category D(K)

[figure: K^{[2]}; K^{[1]}; K.; ^{id^{K}}; ^{dom^{K}}; ^{cod^{K}}; ^{comp^{K}}]

In the situation where K has pullbacks and p is as above, the graph morphism U_{p} : D(p) → D(K) internal to 2-CAT is defined analogously to the definition given above with D(p)_{0} = K, (U_{p})_{0} = 1_{K}, D(p) is the 2-category of p-fibrations as just defined and (U_{p})_{1} is the evident forgetful 2-functor. The following result is proved in the same way as Theorem 5.3.3 with the 2-dimensional universal properties one now has providing the additional required information.

5.4.1. Theorem. Let K be a 2-category with finite limits and p : E → B be an exponentiable morphism therein. There is a bijection between the following types of data:

1. Unit and multiplication 2-cells in Poly_{K} making

[figure: 1; E; B; 1; p]

the underlying endoarrow of a 2-monad in Poly_{K}.

2. Double 2-category structures on D(p) making U_{p} a double 2-functor.

There is also a version of this result useful for exhibiting morphisms of polynomial 2-monads. Given a pullback square

[figure: E_{1}; B_{1}; B_{2}; E_{2}; p_{1}; v; p_{2}; u; pb]

in K in which p_{1} and p_{2} are exponentiable, composing with this pullback square is the effect on objects of a 2-functor D(u, v)_{1} : D(p_{1}) → D(p_{2}). Defining D(u, v)_{0} : K → K to be the identity, one has a graph morphism D(u, v) : D(p_{1}) → D(p_{2}) internal to 2-CAT over D(K). It is straight forward to extend the proof of Theorem 5.4.1 to a proof of

5.4.2. Theorem. In the context just described, there is a bijection between the following types of data:

1. Unit and multiplication 2-cells on in Poly_{K} making

[figure: 1; E_{1}; B_{1}; 1; E_{2}; B_{2}; p_{1}; p_{2}; u; v; pb]

the underlying endoarrow of a morphism of 2-monads in Poly_{K}.

2. Double 2-category structures on D(p_{1}) and D(p_{2}) making U_{p_{1}}, U_{p_{2}} and D(u, v) double 2-functors.

We now have sufficiently many tools to enable us to witness the diagram (18) as being a diagram of polynomial 2-monads. First we shall understand some of the relevant double 2-categories of p-fibrations for appropriate p. Recall from the definition of U^{ℙ} : ℙ_{∗} → ℙ given in Section 5.2, that ℙ is the permutation category, and that ℙ_{∗} has objects those of ℕ_{∗} as described explicitly in Example 5.3.2. An arrow (m, i) → (n, j) of ℙ_{∗} can only exist when m = n, in which case it is a permutation ρ ∈ Σ_{n} such that ρi = j. The forgetful functor U^{ℙ} is a discrete fibration of groupoids with finite fibres.

5.4.3. Lemma.

1. To give a U^{ℙ}-fibration is to give a functor f : X → Y which is a discrete fibration and a discrete opfibration with finite fibres, together with a linear order on each fibre.

2. Given U^{ℙ}-fibrations f_{1} : X_{1} → Y_{1} and f_{2} : X_{2} → Y_{2}, a to give a morphism f_{1} → f_{2} of U^{ℙ}-fibrations is to give a pair (h, k) of functors fitting into a pullback square as on the left

[figure: X_{1}; Y_{1}; Y_{2}; X_{2}; f_{1}; k; f_{2}; h; pb; X_{1}; Y_{1}; Y_{2}.; X_{2}; f_{1}; k_{2}; f_{2}; h_{2}; k_{1}; h_{1}; α; β]

such that for all y ∈ Y_{1}, h|_{f_{1}^{−1}{y}} : f_{1}^{−1}{y} → f_{2}^{−1}{ky} is order preserving.

3. Given f_{1} and f_{2} as in (2), and morphisms (h_{1}, k_{1}) and (h_{2}, k_{2}) of U^{ℙ}-fibrations, to give a 2-cell (h_{1}, k_{1}) → (h_{2}, k_{2}) in D(U^{ℙ})_{1} is to give a pair (α, β) fitting into a commutative cylinder as on the right in the previous display.

Proof. In each case we shall explain how to go from U^{ℙ}-fibrations, morphisms or 2-cells thereof to the data described in the statement, and how to go back, leaving to the reader the straight forward task of showing that these processes give the required bijections.

(1): To give a functor f : X → Y the structure of a U^{ℙ}-fibration is by definition to give functors u and v fitting into a pullback square

[figure: X; Y; ℙ.; ℙ_{∗}; f; v; U^{ℙ}; u; pb]  (20)

Thus f is a discrete fibration and a discrete opfibration with finite fibres since U^{ℙ} is, and these properties on a functor are pullback stable. For y ∈ Y, writing n = vy, because of the pullback (20) on objects, u restricts to a bijection between f^{−1}{y} and (U^{ℙ})^{−1}{n}, this latter set being {(n, 1), ..., (n, n)} in explicit terms. But to give such a bijection is to give a linear order on f^{−1}{y}, by taking the i-th element of f^{−1}{y} to be the element sent to (n, i) by the bijection.

Conversely suppose one has a functor f : X → Y which is a discrete fibration and a discrete opfibration with finite fibres, together with a linear order on each fibre. For y ∈ Y one can define vy = |f^{−1}{y}|. Putting n = vy and denoting the linearly ordered set f^{−1}{y} as {x_{1} < ... < x_{n}}, for 1 ≤ i ≤ n we define ux_{i} = (n, i). For β : y → y′ in Y, the unique lifting property f enjoys by being a discrete opfibration provides a function f^{−1}{y} → f^{−1}{y′}, the unique lifting property f enjoys by being a discrete fibration provides a function f^{−1}{y′} → f^{−1}{y}, and the uniqueness of these lifting properties ensures that these functions are mutually inverse. Let n = vy = vy′ and denote by {x_{1} < ... < x_{n}} and {x′_{1} < ... < x′_{n}} the linearly ordered sets f^{−1}{y} and f^{−1}{y′} respectively. The lifting properties just described give us, for 1 ≤ i ≤ n, a morphism α_{i} : x_{i} → x′_{ρi} of X, and the above bijection f^{−1}{y} → f^{−1}{y′} is given by x_{i} ↦ x′_{ρi}. Thus ρ ∈ Σ_{n}, and we define vβ = ρ and uα_{i} to be ρ : (n, i) → (n, ρi).

(2): We write (u_{1}, v_{1}) and (u_{2}, v_{2}) for the morphisms which exhibit the U^{ℙ}-fibration structures of f_{1} and f_{2} respectively. By definition a morphism f_{1} → f_{2} of U^{ℙ}-fibrations determines (h, k) fitting into a pullback square as in the statement, and the equation u_{2}h = u_{1} restricted to f^{−1}{y}, implies that h|_{f_{1}^{−1}{y}} is order preserving.

Conversely suppose that one has (h, k) as in the statement. We must verify that u_{2}h = u_{1} and v_{2}k = v_{1}. For y ∈ Y_{1} one has

v_{1}y = |f_{1}^{−1}{y}| = |f_{2}^{−1}{ky}| = v_{2}ky

in which the first and third equalities follow from the definitions of v_{1} and v_{2}, and the second equality follows by the pullback of the statement on objects. Writing x_{1,i} (resp. x_{2,i}) for the i-th element of f_{1}^{−1}{y} (resp. f_{2}^{−1}{y}), one has

u_{1}x_{1,i} = (n, i) = u_{2}x_{2,i} = u_{2}hx_{i}

where n = v_{1}y = v_{2}ky and x_{2,i} is the i-th element of f_{2}^{−1}{ky}, in which the first and second equalities follow by the definition of u_{1} and u_{2}, and the third equality follows since f_{2}h = kf_{1} and h is order preserving on the fibres of f_{1}.

For β : y → y′ in Y_{1}, we denote by x_{1,i}, x_{2,i}, x′_{1,i} and x′_{2,i} the i-th element of f_{1}^{−1}{y}, f_{2}^{−1}{ky}, f_{1}^{−1}{y′} and f_{2}^{−1}{ky′} respectively. As in (1) we have α_{1,i} : x_{1,i} → x′_{1,ρ_{1}i} such that f_{1}α_{1,i} = β, and α_{2,i} : x_{2,i} → x′_{2,ρ_{2}i} such that f_{2}α_{2,i} = kβ, where n = v_{1}y = v_{1}y′ and ρ_{1}, ρ_{2} ∈ Σ_{n}. We must show that v_{2}kβ = v_{1}β, that is that ρ_{1} = ρ_{2}, and that u_{2}hα_{1,i} = u_{1}α_{1,i} for all 1 ≤ i ≤ n. But since hα_{1,i} : hx_{1,i} → hx′_{1,ρ_{1}i}, hx_{1,i} = x_{2,i}, hx′_{1,ρ_{1}i} = x′_{2,ρ_{1}i}, and f_{2}hα_{1,i} = kβ, these equations follow from the uniqueness of lifts for f_{2}.

(3): By definition a 2-cell (h_{1}, k_{1}) → (h_{2}, k_{2}) of D(U^{ℙ})_{1} consists of (α, β) of the statement making the cylinder commute, and moreover verifying u_{2}α = id and v_{2}β = id. It suffices to show that these last two equations are automatic.

Let y ∈ Y_{1} and denote by {x_{1} < ... < x_{n}} the linearly ordered fibre f_{1}^{−1}{y}. We have β_{y} : k_{1}y → k_{2}y in Y_{2}, and for 1 ≤ i ≤ n, we have α_{x_{i}} : h_{1}x_{i} → h_{2}x_{i} in X_{2}. By the commutativity of the cylinder f_{2}α_{x_{i}} = β_{y}. By the definition of v_{2} on arrows, one has v_{2}β_{y} = id, and so by the definition of u_{2} on arrows, one has u_{2}α_{x_{i}} = id as required.

Thanks to Lemma 5.4.3 we have an explicit description of graph D(U^{ℙ}) internal to 2-CAT and of the internal graph morphism U_{U^{ℙ}}, which involves forgetting the U^{ℙ}- fibration structures. Similarly one can understand

U_{U^{𝕊}} : D(U^{𝕊}) ⟶ D(Cat)  U_{U^{𝕊^{op}}} : D(U^{𝕊^{op}}) ⟶ D(Cat)

by analysing what U^{𝕊}-fibrations (resp. U^{𝕊^{op}}-fibrations) and their morphisms amount to. To give a functor f : X → Y a U^{𝕊}-fibration (resp. U^{𝕊^{op}}-fibration) structure, is to exhibit it as a discrete opfibration (resp. discrete fibration) with finite fibres, and to give a linear order on each fibre. Via the pullback squares relating U^{ℙ}, U^{𝕊} and U^{𝕊^{op}}, one has internal graph morphisms D(ι_{C}^{S}) : D(U^{ℙ}) → D(U^{𝕊}) and D(ι_{P}^{S}) : D(U^{ℙ}) → D(U^{𝕊^{op}}) over D(Cat).

5.4.4. Theorem. The diagram

[figure: M; B; S; ^{C^{fin}}; P_{fin}; ι_{B}^{M}; π; ι_{C}^{S}; ι_{P}^{S}; ι_{S}^{M}]

described in (18) Section 5.1, is a diagram of polynomial 2-monads and morphisms thereof.

Proof. Any identity functor has a unique U^{ℙ}-fibration structure. Given U^{ℙ}-fibrations f : X → Y and g : Y → Z, the composite gf is a discrete fibration and discrete opfibration whose fibres are finite. For any z ∈ Z, an element of the fibre (gf)^{−1}{z} may be identified as a pair (x, y), where y ∈ g^{−1}{z} and x ∈ f^{−1}{y}. Defining (x_{1}, y_{1}) ≤ (x_{2}, y_{2}) if and only if y_{1} < y_{2} or y_{1} = y_{2} and x_{1} ≤ x_{2}, provides (gf)^{−1}{z} with a linear order. Thus there is an evident composition of U^{ℙ}-fibrations. Thus D(U^{ℙ}) acquires a double 2-category structure making U_{U^{ℙ}} : D(U^{ℙ}) → D(K) a double 2-functor. Moreover U_{U^{𝕊}}, U_{U^{𝕊^{op}}}, D(ι_{C}^{S}) and D(ι_{P}^{S}) are easily witnessed as double 2-functors, thanks to our explicit understanding of U^{ℙ}-fibrations, U^{𝕊}-fibrations and U^{𝕊^{op}}-fibrations. Thus C_{fin}, P_{fin} and S are polynomial 2-monads and ι_{C}^{S} and ι_{P}^{S} are morphisms thereof, by Theorems 5.4.1 and 5.4.2. To exhibit B, M, π and ι_{B}^{M} as polynomial, we appeal to Proposition 4.1.6 and Corollary 5.2.2, using the fact that S is a polynomial 2-monad.

Having exhibited these examples as polynomial, Theorems 4.4.5 and 4.5.1 enable us to read off some of their categorical properties.

5.4.5. Corollary.

1. All the 2-monads of Theorem 5.4.4 are sifted colimit preserving.

2. [34] M, B and S are familial and opfamilial, C_{fin} is familial, and P_{fin} is opfamilial.

3. ι_{C}^{S} is a familial 2-monad morphism, ι_{P}^{S} is an opfamilial 2-monad morphism, and all the other morphisms of Theorem 5.4.4 are both familial and opfamilial.

Acknowledgements

The author would like to acknowledge Michael Batanin, Richard Garner, Martin Hyland, Joachim Kock and Ross Street for interesting discussions on the subject of this paper. The author would also like to acknowledge the financial support of the Australian Research Council grant No. DP130101172.

References

[1] M. Abbott, T. Altenkrich, and N. Ghani. Categories of containers. In Foundations of Software Science and Computation Structures, volume 2620 of Lecture Notes in Computer Science, pages 23–38. Springer, 2003.

[2] M. Batanin and C. Berger. Homotopy theory of algebras of polynomial monads. ArXiv:1305.0086.

[3] M. Batanin and M. Weber. Algebraic Kan extensions from morphisms of 2-monads. In preparation.

[4] T. Bisson and A. Joyal. The Dyer-Lashof algebra in bordism. C.R. Math. Rep. Acad. Sci. Can., 17:135–140, 1995.

[5] R. Blackwell, G. M. Kelly, and A. J. Power. Two-dimensional monad theory. J. Pure Appl. Algebra, 59:1–41, 1989.

[6] J. Bourke. The category of categories with pullbacks is cartesian closed. arXiv:0904.2486, 2009.

[7] J. Bourke. Codesent objects in 2-dimensional universal algebra. PhD thesis, University of Sydney, 2010.

[8] M. Brun. Witt vectors and Tambara functors. Advances in Mathematics, 193:233– 256, 2005.

[9] M. Brun. Witt vectors and equivariant ring spectra applied to cobordism. Proc. London Math. Soc., 94:351–385, 2007.

[10] E. Dubuc. Kan extensions in enriched category theory. Number 145 in SLNM. Springer Verlag, 1970.

[11] N. Gambino and J. Kock. Polynomial functors and polynomial monads. Mathematical Proceedings Cambridge Philosophical Society, 154:153–192, 2013.

[12] P.T. Johnstone. Fibrations and partial products in a 2-category. Applied Categorical Structures, 1:141–179, 1993.

[13] P.T. Johnstone. Variations on the bagdomain theme. Theoretical Computer Science, 136:3–20, 1994.

[14] A. Joyal and I. Moerdijk. Algebraic Set Theory. Cambridge University Press, 1995.

[15] A. Joyal and R. Street. The geometry of tensor calculus I. Advances in Mathematics, 88:55–112, 1991.

[16] G.M. Kelly. On clubs and doctrines. Lecture Notes in Math., 420:181–256, 1974.

[17] G.M. Kelly. Basic concepts of enriched category theory, LMS lecture note series, volume 64. Cambridge University Press, 1982. Available online as TAC reprint no.

POLYNOMIALS IN CATEGORIES WITH PULLBACKS  597

[18] G.M. Kelly and S. Lack. On property-like structures. Theory and applications of categories, 3:213–250, 1997.

[19] G.M. Kelly and R. Street. Review of the elements of 2-categories. Lecture Notes in Math., 420:75–103, 1974.

[20] A. Kock. Fibrations as Eilenberg-Moore algebras. ArXiv:1312.1608.

[21] A. Kock. Monads for which structure are adjoint to units. J. Pure Appl. Algebra, 104:41–59, 1995.

[22] Joachim Kock, André Joyal, Michael Batanin, and Jean-François Mascari. Polynomial functors and opetopes. Adv. Math., 224(6):2690–2737, 2010.

[23] S. Lack. Codescent objects and coherence. J. Pure Appl. Algebra, 175:223–241, 2002.

[24] F. W. Lawvere. Ordinal sums and equational doctrines. Lecture Notes in Math., 80:141–155, 1969.

[25] A. J. Power. A general coherence result. J. Pure Appl. Algebra, 57:165–173, 1989.

[26] R. Street. The formal theory of monads. J. Pure Appl. Algebra, 2:149–168, 1972.

[27] R. Street. Fibrations and Yoneda’s lemma in a 2-category. Lecture Notes in Math., 420:104–133, 1974.

[28] R. Street. Cosmoi of internal categories. Trans. Amer. Math. Soc., 258:271–318, 1980.

[29] R. Street. Fibrations in bicategories. Cahiers Topologie Géom. Differentielle, 21:111– 160, 1980.

[30] D. Tambara. On multiplicative transfer. Comm. Alg., 21:1393–1420, 1993.

[31] T. von Glehn. Polynomials and models of type theory. PhD thesis, University of Cambridge, 2015.

[32] M. Weber. Internal algebra classifiers as codescent objects of crossed internal categories. ArXiv:1503.07585.

[33] M. Weber. Operads as polynomial 2-monads. ArXiv:1412.7599.

[34] M. Weber. Familial 2-functors and parametric right adjoints. Theory and applications of categories, 18:665–732, 2007.

[35] M. Weber. Yoneda structures from 2-toposes. Applied Categorical Structures, 15:259– 323, 2007.

[36] R. J. Wood. Abstract pro arrows I. Cahiers Topologie Géom. Différentielle Catégoriques, 23(3):279–290, 1982.

[37] R. J. Wood. Abstract pro arrows II. Cahiers Topologie Géom. Différentielle Catégoriques, 26(2):135–168, 1985.

Department of Mathematics, Macquarie University

Email: mark.weber.math@gmail.com
This article may be accessed at http://www.tac.mta.ca/tac/

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. Full text of the journal is freely available in .dvi, Postscript and PDF from the journal’s server at http://www.tac.mta.ca/tac/ and by ftp. It is archived electronically and in printed paper format.

Subscription information Individual subscribers receive abstracts of articles by e-mail as they are published. 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 strongly encouraged. Articles should be submitted by e-mail directly to a Transmitting Editor. Please obtain detailed information on submission format and style files at http://www.tac.mta.ca/tac/.

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

TEXnical editor. Michael Barr, McGill University: barr@math.mcgill.ca

Assistant TEX editor. Gavin Seal, Ecole Polytechnique Fédérale de Lausanne:

gavin seal@fastmail.fm

Transmitting editors.

Clemens Berger, Université de Nice-Sophia Antipolis: cberger@math.unice.fr 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: ronnie.profbrown(at)btinternet.com

Valeria de Paiva: valeria.depaiva@gmail.com

Ezra Getzler, Northwestern University: getzler(at)northwestern(dot)edu Kathryn Hess, Ecole Polytechnique Fédérale de Lausanne: kathryn.hess@epfl.ch Martin Hyland, University of Cambridge: M.Hyland@dpmms.cam.ac.uk Anders Kock, University of Aarhus: kock@imf.au.dk Stephen Lack, Macquarie University: steve.lack@mq.edu.au F. William Lawvere, State University of New York at Buffalo: wlawvere@buffalo.edu Tom Leinster, University of Edinburgh: Tom.Leinster@ed.ac.uk Ieke Moerdijk, Radboud University Nijmegen: i.moerdijk@math.ru.nl Susan Niefield, Union College: niefiels@union.edu Robert Paré, Dalhousie University: pare@mathstat.dal.ca Jiri Rosicky, Masaryk University: rosicky@math.muni.cz Giuseppe Rosolini, Università di Genova: rosolini@disi.unige.it Alex Simpson, University of Edinburgh: Alex.Simpson@ed.ac.uk James Stasheff, University of North Carolina: jds@math.upenn.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 R. J. Wood, Dalhousie University: rjwood@mathstat.dal.ca