Theory and Applications of Categories, Vol. 13, No. 14, 2004, pp. 191–234.

GENERIC MORPHISMS, PARAMETRIC REPRESENTATIONS AND WEAKLY CARTESIAN MONADS

Dedicated to Aurelio Carboni on the occasion of his sixtieth birthday

MARK WEBER

Abstract. Two notions, generic morphisms and parametric representations, useful for the analysis of endofunctors arising in enumerative combinatorics, higher dimensional category theory, and logic, are defined and examined. Applications to the Batanin approach to higher category theory, Joyal species and operads are provided.

1. Introduction

Combinatorial species and analytic functors were introduced by André Joyal as a unifying conceptual notion for enumerative combinatorics. In characterising the analytic endofunctors of Set in [Joy86], Joyal was led to the technical notion of generic element of an endofunctor T of Set. Viewing the elements of T as functions 1→T X, the property of genericness does not rely on the domain of these functions being the singleton, or on the category of sets. In this way, one arrives at the notion of a generic morphism f : A→T X for an endofunctor T of an arbitrary category. A stricter notion of generic morphism arose in the PhD thesis of Lamarche [Lam88], which itself builds on the work of Girard [Gir86] on qualitative domains. Qualitative domains give a semantics for variable types, and generic morphisms arise in two ways in this semantics. Namely, to express the normal form characterisation for stable maps of qualitative domains, and moreover, to express the normal form theorem for variable types (which arise as endofunctors of the category of qualitative domains). The paper [Gir86] inspired the development of a subject in logic called stable domain theory^{1}. Applications to the study of stable domains and variable types, and their connections to higher category theory, are the subject of on-going research, but will not be discussed any further in this paper.

In his PhD thesis [Die77], Diers considered functors into Set with a family of representing objects, and in [CJ95] the theory of these familially representable functors was developed further. However, in higher dimensional category theory, there arise endofunctors of presheaf categories that are of a similar form. All of the formidable combinatorics in the operadic approaches comes packaged as such endofunctors. So it seems that overcoming these complications will require further techniques and concepts for the manipulation and investigation of such endofunctors. The inadequacy of our present state of knowledge of such endofunctors and monads is expressed most forcefully in appendix C of [Lei03]. Generic morphisms and related notions enable us to generalise the theory of familially representable functors, so as to include familially representable endofunctors of presheaf categories.

I am indebted to Michael Batanin, Steve Lack, Michael Makkai, Phil Scott and Ross Street for illuminating discussions on the substance of this paper.

Received by the editors 2003-10-26 and, in revised form, 2004-02-19.

Published on 2004-12-05.

2000 Mathematics Subject Classification: 18D50, 55P48.

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

1A survey of this area can be found in [Tay90].

Abstract clubs and cartesian monads, together with operads over them, provide an excellent improvement and generalisation of the usual notion of non-symmetric operad. However, the corresponding notion for symmetric operads is yet to be identified. Generic morphisms can be used to recognise cartesian and weakly cartesian transformations, and so we are able to generalise cartesian monads thereby providing a candidate notion. It is then demonstrated that symmetric operads in Set are indeed captured by this generalisation.

The background required to understand the examples is presented in sections (2)– (4). Generics, parametric representations, related concepts, and associated results are presented in sections (5)–(7), which constitute the technical heart of the paper.

In section (5), T -generic morphisms are defined for an endofunctor T of an arbitrary category A. We also consider the T for which any map f : A→T B factors appropriately through a generic (such functors are said to “admit generic factorisations”), and natural transformations that preserve and reflect generics in the appropriate fashion. One of the main technical themes of this paper is that these generic properties of endofunctors and natural transformations, correspond to pullback-preservation for endofunctors and cartesianness for natural transformations. One has (as we shall see) the more convenient “generic properties” of endofunctors and natural transformations on the one hand, versus the more commonly-used “cartesian properties” of endofunctors and natural transformations on the other. Just as one has pullbacks and weak pullbacks, there are strict and non-strict generic morphisms, and so the full correspondence alluded to here goes as follows:

• endofunctors that admit strict generic factorisations correspond to endofunctors that preserve wide pullbacks.

• endofunctors that admit generic factorisations correspond to endofunctors that preserve weak wide pullbacks.

• natural transformations that preserve and reflect strict generic morphisms correspond to cartesian natural transformations.

• natural transformations that preserve and reflect generic morphisms correspond to weakly cartesian natural transformations.

Most of section (5) is devoted to spelling out the parts of this correspondence that are valid in general, as well as exploring the interplay between the generic properties for

GENERIC MORPHISMS, PARAMETRIC REPRESENTATIONS AND WEAKLY CARTESIAN MONADS 193

endofunctors and those for natural transformations. The remainder of this section explains the relationship of these notions with the parametric right adjoints of [Str00], and their compatibility with the composition of endofunctors.

Section (6) provides two results which require some further hypotheses on A and T. In the previous section, it is shown that the generic properties of endofunctors imply the corresponding cartesian properties in general. The first result, Theorem(6.6), is the converse result that the preservation of wide pullbacks by an endofunctor implies that it admits strict generic factorisations. This result is not new – versions of it appear in [Die77], [Lam88], and [Tay88], although I know of no published proof. The second result, Theorem(6.8), is new, generalising André Joyal’s observation that analytic endofunctors of Set preserve cofiltered limits.

The strict generic notions have an alternative 2-categorical description, in terms of the concept of a parametric representation described in section (7). Although this paper is concerned with endofunctors, many of the notions, and parametric representations in particular, make sense for functors with different domain and codomain. Seen in this light, parametric representability is a very general notion of representability – including the familially representable functors of [CJ95] – but which on the face of it appears to have very little to do with the category Set. Instead such functors are between categories which have a small dense subcategory and satisfy a cocompleteness condition with respect to this subcategory. One sees the objects of this small dense subcategory as “element parametrizers”, and these categories as being “accessible with respect to their elements”. Such categories arise already in section (6) as part of the additional hypotheses required there. The remainder of section (7) relates parametric representability to strict generics and related notions, and generalises the characterisation of familial representability in [CJ95].

The applications are presented in sections (8)–(11). Section (8) characterises connected limit preserving endofunctors of presheaf categories with rank, and section (9) applies this to the description of some of the more fundamental combinatorial objects in the Batanin approach to higher category theory. Section (10) uses generics to characterise analytic endofunctors of Set, and section (11) describes our generalised notion of cartesian monad and operad over it.

2. Abstract Clubs

Throughout this paper we shall refer to a monad whose underlying endofunctor is T, unit is η and multiplication is μ by (T, η, μ) or just by T when the context is clear. We shall always use the letter η for the unit of a monad or an adjunction, the letter μ for the multiplication of a monad, and the letter ε for the counit of an adjunction. For a category A we write End(A) for the category of endofunctors of A and natural transformations between them. Recognising the strict monoidal structure on End(A) whose tensor product is composition of endofunctors, we write Mnd(A) for the category of monoids in End(A). The objects of this category are of course monads, and we shall refer to its arrows as monad morphisms. While there are other important notions of monad morphism, see [Str72] for example, they will not be discussed here.

2.1. Definition. Let A be a category with finite limits, and T ∈ End(A). T -Coll is the full subcategory of End(A)↓T consisting of the cartesian transformations into T. Write

\xymatrix{T -Coll \ar[r]^{π_{T}} & End(A)}

for the faithful “projection”, whose object map takes the domain of a cartesian transformation. When the context is clear, the T subscript for π will be dropped.

By the elementary properties of pullbacks, to give an object S⇒T of T -Coll, it suffices to provide f, and for each A ∈ A, the projections of

\xymatrix{SA \ar[rr] \ar[dd] &  & T A \ar[dd]^{T!} \\  & pb \\ S1 \ar[rr]_{f} &  & T 1}

More formally, the functor obtained by evaluating at the terminal object

\xymatrix{T -Coll \ar[r]^{ev_{1}} & A↓T 1}

is an equivalence of categories.

Given a monoid M in any monoidal category V, the slice category V↓M inherits a monoidal structure. The unit for V↓M is the unit i : I→M for the monoid, and the tensor product of two objects f and g of V↓M is the composite

\xymatrix{A ⊗ B \ar[r]^{f⊗g} & M ⊗ M \ar[r]^{m} & M}

where m is the monoid multiplication. The projection

\xymatrix{V↓M \ar[r] & V}

is a strict monoidal faithful functor. A monoid structure on q : N→M in V↓M, is a monoid structure on N in V, for which q is a morphism of monoids. In particular when T is a monad on A then End(A)↓T is a strict monoidal category, since composition of endofunctors makes End(A) strict monoidal. A subcategory W of a monoidal category V is said to be a monoidal subcategory of V when W is a monoidal category and the inclusion of W in V is a strict monoidal functor.

2.2. Definition. [Kelly [Kel92]] A club on A is a T ∈ Mnd(A) such that T -Coll is a monoidal subcategory of End(A)↓T.

We say that T preserves cartesian transformations when ϕ : S⇒S′ in End(A) is a cartesian transformation implies T ϕ is cartesian also. A more explicit description of clubs is given by

GENERIC MORPHISMS, PARAMETRIC REPRESENTATIONS AND WEAKLY CARTESIAN MONADS 195

2.3. Proposition. [Kelly [Kel92]] A monad T is a club iff η and μ are cartesian, and T preserves cartesian transformations ϕ : S⇒T (that is, T ϕ is cartesian for cartesian transformations ϕ whose codomain is T).

It is worth describing the monoidal structure on T -Coll from the point of view of A↓T 1. The unit is simply the terminal component of the unit of T. Given f, g ∈ A↓T 1, their tensor product is the dotted composite in

\xymatrix{ & . \ar@{.>}[dr] \ar[dl] \\ A \ar[dr]_{f} & pb & T B \ar[dl]^{T!} \ar@{.>}[dr]^{T g} \\  & T 1 &  & T^{2}1 \ar@{.>}[dr]^{μ_{1}} \\  &  &  &  & T 1}

2.4. Definition. Let T be a club. The category T -Op of T -operads is the category of monoids in T -Coll. Explicitly, a T -operad is a cartesian monad morphism into T, and a morphism ϕ→ϕ′ in T -Op is a commutative triangle

\xymatrix{S \ar[rr]^{ψ} \ar[dr]_{ϕ} &  & S′ \ar[dl]^{ϕ′} \\  & T}

in Mnd(A). By the elementary properties of pullbacks, ψ here is automatically a cartesian monad morphism.

A cartesian monad is a club whose functor part preserves pullbacks. That is, a monad T on a finitely complete category A for which T preserves pullbacks and μ and η are cartesian. A T -operad in our sense, is precisely a T -multicategory in the sense of Burroni [Bur71], Hermida [Her00b] and Leinster [Lei00], whose underlying object is the terminal object of A.

2.5. Definition. The category of algebras for an operad ϕ : S⇒T is the category of Eilenberg-Moore algebras for the monad S.

2.6. Proposition. [Kelly [Kel92]] Let T be a club and ϕ : S⇒T be an operad. Then S is a club.

2.7. Examples.

1. Recall the monad M on Set whose algebras are monoids. Let X be a set. Then MX, often denoted as X^{∗}, is the set of finite sequences from X. We shall denote a typical element of MX as a function n→X where n ∈ ℕ is also being regarded as the set {0, ..., n − 1}. The component of the unit of M at a set X takes x∈X to the function x : 1→X which picks out the element x. An element of MMX is a finite sequence of finite sequences from X which is more conveniently regarded as

\xymatrix{k & n \ar[l]_{f} \ar[r]^{x} & X}

where f is in Δ (the category of finite ordinals and order-preserving functions), and x is just a function. So, as far as f is concerned, the set n is being regarded as an ordinal in the usual way, whereas from the point of view of x, n is just a set. The monad multiplication applied to this element forgets f. M preserves connected limits, and its unit and multiplication are cartesian^{2}. An M-operad is a non-symmetric operad in Set.

2. The tree monad T on Glob (the category of globular sets) described in section (9) is cartesian and, as pointed out in [Lei00], a T -operad is an operad in the monoidal globular category Span(Set) in the sense of [Bat98]. Among these operads is one whose algebras are weak ω-categories in the sense of Michael Batanin.

3. In [Web01] a cartesian monad F on Glob is described whose algebras are strict monoidal strict ω-categories. There is an F-operad whose algebras are monoidal weak ω-categories. These are one-object Batanin weak ω-categories whose n-cells for n > 0 are being regarded as (n − 1)-cells.

4. Recall the monad S on Cat whose algebras are symmetric strict monoidal categories. The category SX has the following description

• objects: functors n→X where n is being regarded as a discrete category.

• arrows: an arrow from x to y consists of a pair (f, ϕ) as in

[figure: n; ϕ; x; n; y; X; f]

where ϕ ∈ Sym_{n} and f is a natural transformation as shown.

This monad is also cartesian, and S-operads are the clubs originally considered by Max Kelly in [Kel72b] and [Kel72a]. Monoidal categories, strict monoidal categories, braided monoidal categories, braided strict monoidal categories, symmetric monoidal categories, and symmetric strict monoidal categories are examples of categorical structures that arise as algebras of S-clubs.

2In fact it is shown in [Bén91] that this is true far more generally, that is, when Set is replaced by an elementary topos with a natural numbers object.

GENERIC MORPHISMS, PARAMETRIC REPRESENTATIONS AND WEAKLY CARTESIAN MONADS 197

5. Recall the monad C on Set whose algebras are commutative monoids. An element of CX, the free commutative monoid on the set X, is an unordered sequence from X. This amounts to an equivalence class of elements of M(X) in which x and x′ are considered equivalent iff there is a ρ ∈ Sym_{n} (the nth symmetric group) making

\xymatrix{n \ar[rr]^{ρ} \ar[dr]_{x} &  & n \ar[dl]^{x′} \\  & X}

commute. We shall use square brackets to denote the taking of such equivalence classes, so such an element will be denoted by [x] and x is called a representative of this element of C(X). Similarly an element of CCX is represented by an element of MMX, regarded as in (2.7)(1) modulo the identification of the rows of

[figure: k; ρ_{1}; n; ρ_{0}; X; k; n; X]

given the existence of permutations ρ_{i} for i ∈ 2, making the above diagram commute. The rest of this monad is specified as in (2.7)(1), that is, on representatives. That is, the taking of equivalence classes is a monad morphism c : M⇒C. C is not cartesian, because it does not preserve the pullback

\xymatrix{2 × 2 \ar[r] \ar[d] & 2 \ar[d] \\ 2 \ar[r] & 1}

and because the naturality square of μ for 2→1 is not cartesian. However, in section (11) the current notion of club and operad for it will be generalised to include C. Given this definition, C-operads coincide with symmetric operads in Set.

Many more examples are presented in [Lei03].

3. Analytic endofunctors of Set I

We shall denote by G the composite

[figure: Set/ℕ; ^{ev′^{1}}; M-Coll; π_{M}; End(Set)]

where ev′_{1} is a pseudo-inverse of ev_{1}. Upon identifying Set/ℕ as [ℕ, Set], G can also be regarded as the process of taking left extensions along the functor E_{M} : ℕ→Set, which regards n ∈ ℕ as in (1). Clearly E_{M} factors through Set_{f}, and so G(α : A→ℕ) is finitary.

An element of G(α)(X) is a pair of functions (1→A_{n}, n→X) where A_{n} is the fibre of α over n. A morphism f : X_{1}→X_{2} in X is said to be essentially in the image of a functor F : A→X when there is an g : A_{1}→A_{2} in A and isomorphisms ρ_{i} : F A_{i}→X_{i} such that ρ_{2}F g = fρ_{1}. An object X in X is essentially in the image of F when 1_{X} is essentially in the image of F.

3.1. Definition. The functors and natural transformations essentially in the image of G are said to be strongly analytic.

Define ℙ to be the category with natural numbers as objects, hom-sets given by

ℙ(n, m) = \{ \begin{matrix}Sym_{n} & if n = m \\ ∅ & otherwise \end{matrix}

and composition given by multiplication in the groups Sym_{n}^{3}. A species is a functor ℙ→Set. Recall the adjunction

[figure: End(Set); r; [ℙ, Set]; E; ⊥]

which corresponds to left extension and restriction along the E_{C} : ℙ→Set that regards permutations as bijective functions. Clearly E_{C} factors through Set_{f}, and so EX is finitary for any species X. Given a set Z, an element of E(X)(Z) is represented by a pair (x : 1→X_{n}, h : n→Z) modulo the identification of (x, h) with (x′, h′) whenever there is a ρ ∈ Sym_{n} such that the triangles

[figure: 1; x; x′; X_{n}; X_{ρ}; X_{n}; n; ρ; h; n; h′; Z]

commute. Denote by [x, h] the element of E(X)(Z) represented by (x, h). Using this notation, the arrow map of E(X) is simply

\xymatrix{[x, h] \ar@{|->}[r]^{E(X)(f)} & [x, fh]}

3.2. Definition. The functors and natural transformations essentially in the image of E are said to be analytic.

In [Joy86] the following theorem was obtained.

3More conceptually, ℙ ≅ S1.

GENERIC MORPHISMS, PARAMETRIC REPRESENTATIONS AND WEAKLY CARTESIAN

3.3. Theorem. [Joyal]

1. An endofunctor of Set is analytic iff it preserves weak pullbacks, filtered colimits and cofiltered limits.

2. A natural transformation between analytic endofunctors of Set is analytic iff it’s naturality squares are weak pullbacks.

It was close inspection of Joyal’s proof of this result that lead to much of the theory described in this paper. One immediate consequence of this result is that analytic functors compose, a fact that this not obvious from the definition.

The unit η and counit ε of E ⊣ r will now be specified.

• For X ∈ [ℙ, Set] and x∈X_{n}, η_{X,n}(x) = [x, 1_{n}].

• For T ∈ End(Set) and Z ∈ Set, ε_{T,Z}[a : 1→T (n), h : n→Z] = T h(a).

Identifying Set/ℕ as [ℕ, Set], the adjunction F ⊣ R arises by left kan extension and restriction along the identity on objects functor ℕ→ℙ, and we have

[figure: Set/ℕ; G; F; End(Set); [ℙ, Set]; E; R; ⊢]

with EF = G. Let X be a species and write ε for the counit of the above adjunction, then for Z ∈ Set, (Eε_{X})_{Z}(x, h) = [x, h]. For T analytic, denote the corresponding natural transformation as

\xymatrix{\overline{T} \ar[r]^{c_{T}} & T}

That is, for T = EX, c_{T} = Eε_{X}. Observe that \overline{T} is strongly analytic by definition, and that from the explicit description of c_{T}, its components are clearly surjective.

3.4. Example. For T = C, c_{T} is (the underlying natural transformation of) the monad morphism c described in (5).

4. Globular cardinals

Define the category 𝔾 to have natural numbers as objects, and a generating subgraph

\xymatrix{0 \ar[r]^{σ_{0}} \ar[r]_{τ_{0}} & 1 \ar[r]^{σ_{1}} \ar[r]_{τ_{1}} & 2 \ar[r]^{σ_{2}} \ar[r]_{τ_{2}} & 3 \ar[r]^{σ_{3}} \ar[r]_{τ_{3}} & …}

subject to the “cosource/cotarget” equations σ_{n+1}σ_{n} = τ_{n+1}σ_{n} and τ_{n+1}τ_{n} = σ_{n+1}τ_{n}, for every n ∈ ℕ. More generally, an arrow \xymatrix{n \ar[r] & m} in 𝔾 is a string of σ’s and τ’s of length m−n, and so by the cosource/cotarget equations, is determined by the first (ie right-most) character. So when n < m we can write

\xymatrix{n \ar[r]^{σ} \ar[r]_{τ} & m}

to describe the hom-set 𝔾(n, m). The category Glob of globular sets is defined as Glob := [𝔾op, Set]. Thus, a globular set Z consists of a diagram of sets and functions

\xymatrix{Z_{0} & Z_{1} \ar[l]_{s_{0}} \ar[l]^{t_{0}} & Z_{2} \ar[l]_{s_{1}} \ar[l]^{t_{1}} & Z_{3} \ar[l]_{s_{2}} \ar[l]^{t_{2}} & … \ar[l]_{s_{3}} \ar[l]^{t_{3}}}

so that s_{n}s_{n+1} = s_{n}t_{n+1} and t_{n}t_{n+1} = t_{n}s_{n+1} for every n ∈ ℕ. The elements of Z_{n} are called the n-cells of Z, and the functions s_{n} and t_{n} are called source and target functions. In this way an (n + 1)-cell z is regarded as a directed edge \xymatrix{s(z) \ar[r]^{z} & t(z)} between n-cells. The source/target equations tell us how to regard an (n + 2)-cell z as an edge between edges between n-cells. Clearly, every n-cell has a unique k-source and a unique k-target, where 0≤k < n.

We shall now describe globular pasting schemes. Let Z be a globular set. Recall from [Str91] the solid triangle order ◀ on the elements (of all dimensions) of Z. Define first the relation x ≺ y for x ∈ Z_{n} iff x = s_{n}(y) or t_{n−1}(x) = y. Then take ◀ to be the reflexive-transitive closure of ≺. Write Sol(Z) for the preordered set so obtained. Observe that Sol is the object map of a functor

\xymatrix{Glob & Sol \ar[r] & PreOrd}

where PreOrd is the category of preordered sets and order-preserving functions.

4.1. Definition. A globular cardinal is a globular set Z such that Sol(Z) is a non-empty finite linear order.

We begin understanding morphisms between globular cardinals by noticing that the square

[figure: Glob; res; Sol; PreOrd; U; _{Set_{ℕ}}; colim; Set]

is commutative up to isomorphism in Cat, where U is the forgetful functor and res is restriction along the inclusion of objects ℕ→𝔾. Since U creates all limits and colimits, res preserves all limits and colimits, and coproducts in Set commute with colimits and connected limits, Sol preserves colimits and connected limits. Furthermore, observe that Sol preserves and reflects monics and epics since U, res and colim do. We summarise these observations in

GENERIC MORPHISMS, PARAMETRIC REPRESENTATIONS AND WEAKLY CARTESIAN MONADS 201

4.2. Proposition. The functor Sol preserves colimits and connected limits, and reflects monos and epis.

4.3. Corollary.

1. Let \xymatrix{X \ar[r]^{f} & Z} ∈ Glob and X, Z be globular cardinals. Then f is monic.

2. Let \xymatrix{X \ar[r]^{r} & Z} be a retraction and X be a globular cardinal. Then r is an isomorphism.

Proof. (1): Consecutive elements x, y ∈ Sol(X) come from different dimensions, so that Sol(f)(x) ≠ Sol(f)(y). Thus Sol(f) is an order-preserving function between finite linear orders that does not identify consecutive elements, and so must be monic. By (4.2) f must be monic. (2): A retract of a finite linear order in PreOrd is a finite linear order. Thus Z is a globular cardinal and the result follows from (1).

It is a result of Street [Str00] that globular cardinals are the globular pasting schemes of [Bat98]. We shall describe that connection now for the convenience of the reader. A tree^{4} T of height n is a diagram

\xymatrix{T_{0} & … \ar[l]_{∂_{0}} & T_{n} \ar[l]_{∂_{n−1}}}

in Δ such that T_{0} = 1. A leaf of height k (0 ≤ k < n) is an element of T_{k} which is not in the image of ∂_{k}. All elements of T_{n} are leaves (of height n). For example

[figure: .; .; .; .; .; .; .; .; .; .]

is a tree T of height 3, for which T_{1}, T_{2} and T_{3} each have 3 elements. It has 2 leaves of height 2 and 1 leaf of height 1. For r ∈ ℕ, define an r-zig-zag sequence to be a finite sequence of natural numbers

(n_{i} : i ∈ (2r − 1))

such that n_{2j} > n_{2j+1} < n_{2j+2} for j ∈ (r − 1). Given a tree T with r leaves, we construct an r-zig-zag sequence, called the zig-zag sequence of T,

zz(T) := (n_{T,i} : i ∈ (2r − 1))

4Usually a tree is defined to be a finite undirected loop-free graph. The trees described here are rooted trees, that is, trees together with a distinguished vertex (the root which is the element of T_{0}).

by ordering the leaves in the obvious way (from left to right in the above example), taking n_{T,2j} to be the height of the j-th leaf (where j ∈ r), and taking n_{T,2j+1} to be the maximum height at which the j-th and (j + 1)-st leaves are joined (where j ∈ (r − 1)). By induction on r, this construction specifies a bijection between trees with r leaves, and r-zig-zag sequences. A smooth zig-zag sequence is a finite sequence

(n_{i} : i ∈ r)

of natural numbers, satisfying

1. n_{0} = 0 = n_{r−1}.

2. For i ∈ (r − 1), |n_{i+1} − n_{i}| = 1.

A peak of a smooth zig-zag sequence is an n_{i}, where 0 < i < (r − 1), such that n_{i−1} < n_{i} > n_{i+1}. A trough of a smooth zig-zag sequence is an n_{i}, where 0 < i < (r − 1), such that n_{i−1} > n_{i} < n_{i+1}. Reading off the peaks and troughs of smooth zig-zag sequences as they arise, provides a bijection between smooth zig-zag sequences and zig-zag sequences, and thus with trees. For any tree T, define szz(T), the smooth zig zag sequence of T, to be the smooth zig-zag sequence corresponding to T by these bijections. In the above example

zz(T) = (2, 1, 3, 2, 3, 2, 3, 0, 1, 0, 2)

and

szz(T) = (0, 1, 2, 1, 2, 3, 2, 3, 2, 3, 2, 1, 0, 1, 0, 1, 2, 1, 0)

To obtain the tree T corresponding to a globular cardinal Z, write down the dimensions of the elements of Z as they appear in Sol(Z). The result is a smooth zig-zag sequence, and the corresponding tree is T. Conversely, given a tree T, we regard its zig-zag sequence as a diagram of representables in Glob

\xymatrix{n_{T,0} & n_{T,1} \ar[l]_{τ} \ar[r]^{σ} & … \ar[r]^{σ} & n_{T,2r}}

identifying 𝔾 as a full subcategory of Glob in the usual way. Then, the globular set associated to T is the colimit of this diagram. This construction of globular sets from trees was named the *-construction in [Bat98].

Identifying Δ as a subcategory of Set as usual, the full subcategory tr of Glob consisting of the globular cardinals, is clearly isomorphic to the subcategory of Δ↓ℕ consisting of

• objects: smooth zig-zag sequences. Here a sequence of natural numbers of length r is being regarded as a function \xymatrix{r \ar[r] & ℕ}.

• arrows: injections which preserve sources and targets. Recall that the source(target) of an instance of n in a smooth zig-zag sequence, is the preceding(succeeding) instance of (n − 1).

GENERIC MORPHISMS, PARAMETRIC REPRESENTATIONS AND WEAKLY CARTESIAN MONADS 203

Trees form a globular set Tr. The set of n-cells consists of trees of height ≤ n. Let T be a tree of height n and 0 ≤ m < n. Then the truncation at height m of T, notated by ∂_{m}(T), is obtained by ignoring the vertices of T above height m. Sources and targets for Tr are given by s_{m} = ∂_{m} = t_{m}. There is a morphism u : 1→Tr in Glob which in each dimension n, picks out the tree U_{n}, which has one leaf at height n. That is, U_{n} is the tree whose corresponding globular set is the representable 𝔾(−, n).

Truncation admits a natural description via smooth zig-zag sequences and the above description of tr. Let X = (n_{i} : i ∈ r) be a smooth zig-zag sequence. An m-region of X is a subsequence Y such that

1. Y is consecutive, that is, if 0 ≤ i < j < k < r, and n_{i}, n_{k} ∈ Y, then n_{j} ∈ Y.

2. the first and last terms of Y are instances of m.

3. for any n_{i} ∈ Y, n_{i} ≥ m.

4. Y is a maximal subsequence of X for which conditions (1)-(3) hold.

Let T be a tree of height n and m ∈ ℕ. Then one obtains szz(∂_{m}(T)) by collapsing each of the m-regions of szz(T) to a single instance of m. There is a morphism σ : ∂_{m}(T)→T in Glob, which identifies the n_{i} < m, and takes each instance of m ∈ szz(∂_{m}(T)) to the first term in the corresponding m-region of szz(T). Similarly there is a morphism σ : ∂_{m}(T)→T in Glob, which identifies the n_{i} < m, and takes each instance of m ∈ szz(∂_{m}(T)) to the last term in the corresponding m-region of szz(T). Notice in particular when n ≤ m, that σ and τ are identities. The following proposition is immediate.

4.4. Proposition. Let T ∈ Tr_{n}, 0 ≤ r < m < n and consider

\xymatrix{∂_{r}(T) \ar[r]^{σ} \ar[r]_{τ} & ∂_{m}(T) \ar[r]^{σ} \ar[r]_{τ} & T}

Then σσ = σ = τσ and ττ = τ = στ.

For example, restricting to the trees with one leaf, whose corresponding globular sets are the representables, one recaptures the cosource-cotarget relations. Proposition(4.4) enables one to write the *-construction as a functor in the following definition.

4.5. Definition. The functor E_{T} : y↓Tr→Glob, where y is the yoneda embedding, is defined to have the arrow map

[figure: (∂_{m}(T), m); σ; τ; (T, n); ∂_{m}(T); σ; τ; T]

where m ≤ n.

Suppose that S and T are trees, and m ∈ ℕ, such that ∂_{m}(S) = ∂_{m}(T). We shall construct a new tree S⊗_{m}T so that ∂_{m}(S⊗_{m}T) = ∂_{m}(S) = ∂_{m}(T). Notice that this condition ensures that S, T and S⊗_{m}T must have the same number of m-regions. It suffices to specify the m-regions of S⊗_{m}T. The i-th m-region of S⊗_{m}T is obtained by concatenating the i-th m-region S_{i}, of S, with the i-th m-region T_{i} of T, and identifying the last term of S_{i} with the first term of T_{i} (which are both instances of m).

4.6. Example. Let szz(S) be

(0, 1, 2, 1, 0, 1, 2, 3, 2, 1, 2, 3, 2, 3, 2, 1, 0)

and szz(T) be

(0, 1, 2, 3, 4, 3, 2, 1, 0, 1, 2, 3, 2, 1, 2, 1, 0)

then szz(∂_{2}(S)) = szz(∂_{2}(T)) is

(0, 1, 2, 1, 0, 1, 2, 1, 2, 1, 0)

The three 2-regions of S as they arise are (2), (2, 3, 2) and (2, 3, 2, 3, 2). The corresponding three 2-regions of T are (2, 3, 4, 3, 2), (2, 3, 2) and (2) respectively. Thus, the corresponding three 2-regions of S⊗_{2}T are (2, 3, 4, 3, 2), (2, 3, 2, 3, 2) and (2, 3, 2, 3, 2) respectively. Thus, szz(S⊗_{2}T) is

(0, 1, 2, 3, 4, 3, 2, 1, 0, 1, 2, 3, 2, 3, 2, 1, 2, 3, 2, 3, 2, 1, 0)

It is instructive to picture this example in terms of trees.

Writing

\xymatrix{S \ar[r]^{c_{S}} & S⊗_{m}T & T \ar[l]_{c_{T}}}

for the obvious inclusions, it is straightforward to observe that

[figure: ∂_{m}(S); σ; τ; T; c_{T}; S; c_{S}; S⊗_{m}T; po]  (1)

is a pushout in Glob. Let n ∈ ℕ. When n > m, n-regions are contained within mregions, so that n-truncation and ⊗_{m} “commute”. That is, ∂_{n}(S⊗_{m}T) = ∂_{n}(S)⊗_{m}∂_{n}(T). Conversely, when n ≤ m, ∂_{n}∂_{m} = ∂_{n}, and ∂_{n}(S) and ∂_{n}(T) have no m-regions, so that ∂_{n}(S⊗_{m}T) = ∂_{n}(S)⊗_{m}∂_{n}(T) holds in this case also. It is also straightforward to see that truncation commutes with cosources and cotargets of globular cardinals.

Let A be a globular cardinal whose corresponding zig-zag sequence is (n_{A,i} : i ∈ (2r − 1)). A morphism of globular sets f : A→Tr amounts to a sequence (T_{i} : i ∈ r) of trees, where T_{i} is of height ≤ n_{A,2i}, and for i ∈ (r − 1), ∂_{n_{T,2i+1}}(T_{i}) = ∂_{n_{T,2i+1}}(T_{i+1}). The comments relating to ⊗_{m} generalise to

GENERIC MORPHISMS, PARAMETRIC REPRESENTATIONS AND WEAKLY CARTESIAN

4.7. Proposition. Let A be a globular cardinal, f : A→Tr, and

[figure: y↓A; f∘−; 1; B; y↓Tr; E_{T}; Glob; g]

exhibits B as a left extension. That is, g is the universal cocone that exhibits B as colim(E_{T} (f ∘ −)). Then B is a globular cardinal. Moreover, such colimits commute with cosources and cotargets of globular cardinals.

Proof. B is the colimit of the diagram

\xymatrix{T_{0} & ∂_{n_{T,1}}(T_{0}) \ar[l]_{τ} \ar[r]^{σ} & … \ar[r]^{σ} & T_{r−1}}

where (T_{i} : i ∈ r) is the sequence of trees corresponding to f, and these trees are being regarded as globular cardinals. This colimit can be obtained by successively taking pushouts of the form (1). As argued above, such pushouts give rise to globular cardinals, and commute with cosources and cotargets.

Let A and B be trees of height n. A morphism f : B→A of trees is a commutative diagram

\xymatrix{B_{0} \ar[d]_{f_{0}} & B_{1} \ar[d]_{f_{1}} \ar[l]_{∂_{0}} & ... \ar[l]_{∂_{1}} & B_{n} \ar[d]_{f_{n}} \ar[l]_{∂_{n−1}} \\ A_{0} & A_{1} \ar[l]^{∂_{0}} & ... \ar[l]^{∂_{1}} & A_{n} \ar[l]^{∂_{n−1}}}

in Set such that for i∈n, f_{i+1} preserves the linear order on each fibre of ∂_{i}. Let A have r leaves. Regard j-th leaf of A (ie j∈r), say of height h(j), as being picked out by a morphism of trees l(j) : U_{h(j)}→A. Pulling back the l(j)_{i} along the f_{i} in Set distinguishes a subtree f^{−1}(j) of B. Doing this for each leaf of A produces f̂: A→Tr in Glob (where A here is regarded as a globular cardinal). That is, f̂ corresponds to the sequence of trees (f^{−1}(j) : j ∈ r). Moreover colim(E_{T} (f̂ ∘ −))≅A and the universal cocone is uniquely determined. We have proved

4.8. Proposition. The above construction sets up a bijective correspondence between morphisms of plane trees f : B→A, and f̂: A→Tr and

[figure: y↓A; f̂∘−; 1; B; y↓Tr; E_{T}; Glob; g]

exhibiting B as a left extension.

We write Ω for the category whose objects are globular cardinals and morphisms are morphisms between the corresponding trees^{5}.

5. Generic morphisms

Throughout this section, take A to be a category, S and T to be endofunctors of A, and ϕ : S⇒T to be a natural transformation from S to T.

5.1. Definition.

1. Let I be a non-empty set. A diagram in A consisting of the family of arrows

((π_{i} : W →B_{i}, f_{i} : B_{i}→C) : i ∈ I)

such that f_{i}π_{i} = f_{j}π_{j} for every i, j ∈ I is called a wide commutative square. It will be convenient to denote its common diagonal f_{i}π_{i} by π, to drop the adjective “commutative” when the context is clear, and to drop the adjective “wide” when the cardinality of I is 2. Such a wide square is said to be weakly cartesian relative to A ∈ A if for any other wide commutative square

((a_{i} : A→B_{i}, f_{i} : B_{i}→C) : i ∈ I)

there is a z : A→W such that a_{i} = π_{i}z for every i ∈ I. When these commutative fillers (ie the z’s) exist uniquely, the original wide square is said to be cartesian relative to A. This wide square is said to be weakly cartesian (also a wide weak pullback), respectively cartesian or a wide pullback, when it is weakly cartesian, respectively cartesian, relative to all A ∈ A.

2. ϕ is (weakly) cartesian (relative to A) when its naturality squares are (weakly) cartesian (relative to A).

5.2. Definition. A morphism f : A→T B is T -generic when for any α, β, and γ making the outside of

[figure: A; α; f; T (X); T (γ); T (B); T (β); T (δ); T (Y)]

commute, there is a δ for which γ ∘ δ = β and T (δ) ∘ f = α. We call such a δ a T -fill for this square. We say that f is a strict T -generic, when there is a unique T -fill for any α, β, and γ as above.

5Another important viewpoint described in [BS00] and [Her00a] is to regard Ω as a monoidal globular category which plays the role of a globular monoid classifier.

GENERIC MORPHISMS, PARAMETRIC REPRESENTATIONS AND WEAKLY CARTESIAN MONADS 207

5.3. Example. Let T be an endofunctor of Set. A generic element of T in the sense of [Joy86] is a generic morphism 1→T B in our sense.

5.4. Definition. T admits (strict) generic factorisations relative to A ∈ A when any A→T Z factors as

\xymatrix{A \ar[r]^{g} & T (H) \ar[r]^{T (h)} & T (Z)}

where g is (strict) T -generic. We say that T admits (strict) generic factorisations when it admits (strict) generic factorisations relative to all A ∈ A.

5.5. Example. Recall the monoid monad on Set from (2.7)(1). A function f : A→MB amounts to functions \overline{f}_{a} : n_{a}→B where n_{a} ∈ ℕ and a ∈ A. That is, f amounts to a discrete A-indexed cocone with vertex B. One can verify directly that f is M-generic iff \overline{f} is a universal (that is, a coproduct) cocone, and that M admits strict generic factorisations, or see this as a consequence of (7.3) below. Moreover f : A→MB is generic and A is finite ⇒ B is finite.

5.6. Definition.

1. ϕ preserves (strict) generics relative to A ∈ A when for all B and f (strict) Sgeneric, the composite

\xymatrix{A \ar[r]^{f} & S(B) \ar[r]^{ϕ_{B}} & T (B)}

is a (strict) T -generic. ϕ preserves (strict) generics when it preserves (strict) generics relative to all A ∈ A.

2. ϕ reflects (strict) generics relative to A ∈ A when for all B and f, the composite

\xymatrix{A \ar[r]^{f} & S(B) \ar[r]^{ϕ_{B}} & T (B)}

is (strict) T -generic implies that f is (strict) S-generic. ϕ reflects (strict) generics when it reflects (strict) generics relative to all A ∈ A.

We shall now describe the basic general facts concerning generic morphisms, endofunctors that admit generic factorisations and natural transformations that are (weakly) cartesian.

5.7. Lemma. Let

\xymatrix{A \ar[r]^{g} \ar[d]_{f} & T (C) \ar[d]^{T (k)} \\ T (B) \ar[r]_{T (h)} & T (D)}

commute where f and g are T -generic. Then any T -fill \xymatrix{B \ar[r] & C} for this square is an isomorphism.

Proof. Use the genericness of f to induce δ_{1} and that of g to induce δ_{2}.

[figure: A; g; f; T (C); T (k); T (B); T (h); T (δ_{1}); T (D); A; f; g; T (B); T (δ_{1}); T (C); 1; T (δ_{2}); T (C)]

Thus δ_{2} is a section of δ_{1}. By the same argument δ_{2} is also a retraction, and so is the inverse of δ_{1}.

5.8. Corollary. T admits strict generic factorisations relative to A ⇒ all generics f : A→T (B) are strict.

Let A have a terminal object 1 and denote by T̂ : A→A↓T 1 the functor which sends A to T (!) : T A→T 1. In [Str00] T is said to be a parametric right adjoint when T̂ has a left adjoint.

5.9. Proposition. Let A have a terminal object. T admits strict generic factorisations iff T is a parametric right adjoint.

Proof. (⇒): Choose a strict generic factorisation

\xymatrix{A \ar[r]^{g_{f}} & T A_{f} \ar[r]^{T!} & T 1}

for every morphism f : A→T 1. Then E(f) = A_{f} describes the object map of a left adjoint to T̂ (and g_{f} is the corresponding component of the unit of this adjunction). (⇐): Let E be a left adjoint to T̂. We must give a strict generic factorisation for any f : A→T B, but it suffices to consider the case B = 1, because if T!g is a strict generic factorisation of T!f, then (T δ)g is a strict generic factorisation of f, where δ is the unique T -fill indicated in

[figure: A; f; g; T B; T!; T C; T!; T δ; T 1]

Observe that for f : A→T 1, the component of the unit at f of the given adjunction is

\xymatrix{A \ar[rr]^{η_{f}} \ar[dr]_{f} &  & T Ef \ar[dl]^{T!} \\  & T 1}

and the strict genericness of η_{f} amounts to the universal property of η as the unit of an adjunction.

GENERIC MORPHISMS, PARAMETRIC REPRESENTATIONS AND WEAKLY CARTESIAN MONADS 209

5.10. Proposition.

1. ϕ is weakly cartesian relative to A ⇒ ϕ preserves generics relative to A.

2. ϕ is cartesian relative to A ⇒ ϕ preserves strict generics relative to A.

3. S admits generic factorisations relative to A and ϕ preserves generics relative to A ⇒ ϕ is weakly cartesian relative to A.

4. S admits strict generic factorisations relative to A and ϕ preserves strict generics relative to A ⇒ ϕ is cartesian relative to A.

5. S and T admit strict generic factorisations relative to A and ϕ preserves generics relative to A ⇒ ϕ is cartesian relative to A.

Proof. (1): Given a S-generic f, and α, β, and γ so that the outside of

\xymatrix{A \ar[rrrr]^{α} \ar@{.>}[ddrr]_{δ} \ar[dddd]_{f} &  &  &  & T (X) \ar[dddddd]^{T (γ)} \\  &  & I \\  &  & S(X) \ar[ddd]_{S(γ)} \ar[uurr]_{ϕ} \\  & II \\ S(B) \ar[drr]_{S(β)} \ar[dd]_{ϕ} &  &  & III \\  &  & S(Y) \ar[drr]_{ϕ} \\ T (B) \ar[rrrr]_{T (β)} &  &  &  & T (Y)}

commutes, the arrow δ is induced so that (I) and (II) commute, since (III) is weakly cartesian relative to A. Since f is S-generic, there is a S-fill ε for (II). By the naturality of ϕ, ε must also be a T -fill for the outer square as required. (2): Assuming now that f is a strict S-generic and that ϕ is cartesian, it suffices to show that ε obtained above is a unique T -fill. Let ε′ be another T -fill. Then since (III) is a pullback, ε′ is also a S-fill, and so by the strictness of f, ε′ = ε. (3): Given α, β and γ making

\xymatrix{A \ar[ddr]_{α} \ar[drr]^{β} \ar@{.>}[dr] \\  & S(X) \ar[r]^{ϕ} \ar[d]_{S(γ)} & T (X) \ar[d]^{T (γ)} \\  & S(Y) \ar[r]_{ϕ} & T (Y)}

commute, we must provide a commutative fill (dotted arrow). Since S admits generic factorisations relative to A, we can factor α as S(h) ∘ g where g is S-generic, to obtain

\xymatrix{A \ar[d]_{g} \ar[drr]^{β} \\ S(H) \ar@{.>}[r]^{S(δ)} \ar[dd]_{ϕ} \ar[dr]_{S(h)} & S(X) \ar[r]^{ϕ} \ar[d]^{S(γ)} & T (X) \ar[d]^{T (γ)} \\  & S(Y) \ar[r]_{ϕ} & T (Y) \\ T (H) \ar[urr]_{T (h)}}

Since ϕ preserves generics relative to A, the composite ϕ_{H} ∘ g is T -generic, and so this diagram has a T -fill δ. The desired commutative fill is S(δ) ∘ g. (4): Arguing as in (3) and assuming that g is a strict generic, we must see that the commutative fill \xymatrix{A \ar[r] & S(X)} is unique. Let ε be such a commutative fill, induce the δ′ in

[figure: A; ε; g; S(X); S(γ); S(H); S(h); S(δ′); S(Y)]

and so it suffices to show δ = δ′. This follows since δ′ is also a T -fill for the outside of the second diagram of (3), and since ϕ preserves strict generics. (5): If T admits strict generic factorisations relative to A then all generics A→T B are strict, so ϕ in fact preserves strict generics relative to A, and the result follows from (4).

5.11. Proposition. ϕ is cartesian ⇒ ϕ reflects generics and strict generics.

Proof. Consider f as above so that ϕ_{B} ∘ f is (strict) T -generic, and α, β and γ so that the top-left square of

\xymatrix{A \ar[r]^{α} \ar[d]_{f} & S(X) \ar[d]^{S(γ)} \ar[r]^{ϕ} & T (X) \ar[dd]^{T (γ)} \\ S(B) \ar[r]^{S(β)} \ar[d]_{ϕ} & S(Y) \ar[dr]^{ϕ} \\ T (B) \ar[rr]_{T (β)} &  & T (Y)}

commutes. Then the cartesianness of ϕ guarantees that a (unique) T -fill for the whole square is a (unique) S-fill for the top-left square.

GENERIC MORPHISMS, PARAMETRIC REPRESENTATIONS AND WEAKLY CARTESIAN MONADS 211

5.12. Lemma. ϕ preserves generics and generics for T are strict ⇒ generics for S are strict.

Proof. Consider the diagram of the previous proposition this time with ϕ genericpreserving and f generic. An S-fill for the top-left square is a T -fill for the large square, which is unique since ϕ ∘ f is strict generic.

5.13. Proposition. Let ϕ be weakly cartesian relative to A.

1. S admits generic factorisations relative to A ⇒ ϕ reflects generics relative to A.

2. T admits generic factorisations relative to A and ϕ reflects generics relative to A ⇒ S admits generic factorisations relative to A.

3. T admits strict generic factorisations relative to A and ϕ reflects generics relative to A ⇒ S admits strict generic factorisations relative to A and ϕ is cartesian relative to A.

Proof. (1): Suppose that the composite

\xymatrix{A \ar[r]^{f} & S(X) \ar[r]^{ϕ_{X}} & T (X)}

is T generic. Factor f as S(h) ∘ g

\xymatrix{A \ar[r]^{f} \ar[dr]_{g} & S(X) \ar[r]^{ϕ_{X}} & T (X) \\  & S(H) \ar[r]_{ϕ_{H}} \ar[u]_{S(h)} & T (H) \ar[u]_{T (h)}}

where g is S-generic, so that ϕ_{H} ∘ g is T -generic by lemma(5.10). Thus, by lemma(5.7), h is an isomorphism, so that f is S-generic. (2): Given f : A→SZ, factorise ϕ_{Z} ∘ f to obtain

\xymatrix{A \ar[r]^{f} \ar[dr]^{g′} \ar[ddr]_{g} & S(Z) \ar[r]^{ϕ_{Z}} & T (Z) \\  & S(H) \ar[u]_{S(h)} \ar[d]^{ϕ_{H}} \\  & T (H) \ar[uur]_{T (h)}}

where g is T -generic. We induce g′ from the weak cartesianness of ϕ relative to A, and g′ is S-generic since ϕ reflects generics relative to A. (3): Immediate from (2), lemma (5.12) and proposition (5.10)(5).

5.14. Lemma. Let f : A→SB be (strict) S-generic and g : B→T C be (strict) T -generic. Then the composite

\xymatrix{A \ar[r]^{f} & S(B) \ar[r]^{S(g)} & ST (C)}

is (strict) ST -generic.

Proof. Suppose first that f and g are generics. An ST -fill for

\xymatrix{A \ar[r]^{α} \ar[d]_{f} & ST (X) \ar[dd]^{T (γ)} \\ S(B) \ar[d]_{S(g)} \\ ST (C) \ar[r]_{ST (β)} & ST (Y)}

is obtained as a T -fill for the left square

\xymatrix{B \ar[r]^{δ} \ar[d]_{g} & T (X) \ar[d]^{T (γ)} & A \ar[r]^{α} \ar[d]_{f} & ST (X) \ar[d]^{S(T (γ))} \\ T (C) \ar[r]_{T (β)} & T (Y) & S(B) \ar[r]_{S(T (β)∘g)} & ST (Y)}

where δ is an S-fill for right square. Now suppose that f and g are strict generics. Given an ST -fill ε, S(ε) ∘ g is an S-fill for the right square, thus S(ε) ∘ g = δ since f is strict generic, and so ε is the unique T -fill for the left square since g is strict generic, whence ε is the unique ST -fill.

5.15. Corollary. If S admits generic factorisations relative to A and T admit generic factorisations, then ST admits generic factorisations relative to A.

5.16. Proposition.

1. T admits generic factorisations relative to A ⇒ T takes wide weak pullbacks to wide squares that are weakly cartesian relative to A.

2. T admits strict generic factorisations relative to A ⇒ T takes wide pullbacks to wide squares that are cartesian relative to A.

Proof. (1): Let

((π_{i} : W →B_{i}, f_{i} : B_{i}→C) : i ∈ I)

be a weak wide pullback, and

((a_{i} : A→T B_{i}, T f_{i} : T B_{i}→T C) : i ∈ I)

GENERIC MORPHISMS, PARAMETRIC REPRESENTATIONS AND WEAKLY CARTESIAN

be a wide commutative square. Choose i ∈ I and factor a_{i} as

\xymatrix{A \ar[r]^{g} & T (Y) \ar[r]^{T (h_{i})} & T (B_{i})}

where g is T -generic. Then for j ∈ I where j ≠ i, induce h_{j} as a T -fill of

\xymatrix{A \ar[r]^{a_{j}} \ar[d]_{g} & T (B_{j}) \ar[d]^{T (f_{j})} \\ T (Y) \ar[r]_{T (f_{i}h_{i})} & T (C)}

and so we have a wide commutative square

((h_{j} : Y →B_{j}, f_{j} : B_{j}→C) : j ∈ I)

and since the original wide square is a weak wide pullback, we have y : Y →W so that π_{j}y = h_{j} for j ∈ I. Thus T (y)g provides the desired fill exhibiting

(( \xymatrix{T (W) \ar[r]^{T (π_{j})} & T (B_{j})} , \xymatrix{T (B_{j}) \ar[r]^{T (f_{j})} & T (C)} ) : j ∈ I)

as weakly cartesian relative to A. (2): Suppose that the original wide square described above is cartesian. Let b : A→T W be a filler, that is, T (π_{j})b = a_{j} for j ∈ I. We must show that b = T (y)g. Let δ_{j} be the T -fill of

\xymatrix{A \ar[r]^{b} \ar[d]_{g} & T (W) \ar[d]^{T (f_{j})} \\ T (Y) \ar[r]_{T (h_{j})} & T (B_{j})}

but composing this square with f_{j}, δ_{j} is also the T -fill of

\xymatrix{A \ar[r]^{b} \ar[d]_{g} & T (W) \ar[d]^{T (f)} \\ T (Y) \ar[r]_{T (h)} & T (C)}

and so is independent of j (that is δ_{j} = δ_{k} for j, k ∈ I) since T -generics are strict. We denote this common fill by δ. Since δ satisfies π_{j}δ = h_{j} for j ∈ I, δ = y by the uniqueness of y, and so b = T (y)g as required.

An immediate consequence of this last result is

5.17. Corollary.

1. T admits generic factorisations ⇒ T preserves weak wide pullbacks.

2. T admits strict generic factorisations ⇒ T preserves wide pullbacks.

6. Further exactness results

Our purpose in this section is to understand two results which are true given additional hypotheses on A and T. These results are

1. Theorem(6.6) – which is a converse to (5.17)(2).

2. Theorem(6.8) – by which the admission of (not necessarily strict) generic factorisations implies the preservation of certain special connected limits. Namely, the preservation of cofiltered limits.

The additional hypotheses alluded to above will be drawn from

6.1. Definition. Let I : S→A be the inclusion of a small full subcategory S. For A ∈ A, denote by

[figure: S↓A; π_{A}; 1; A; S; I; A; α]

the usual comma square. That is, an object of S↓A is an arrow f : S→A where S ∈ S, and α_{f} = f. We shall refer to α as “A’s canonical diagram”. A is accessible from S when

1. For A ∈ A and F : S↓A→A, the colimit of F exists.

2. For A ∈ A, A’s canonical diagram is a left extension (that is, a universal cocone).

An object B ∈ A is S-small when for f : B→C and

[figure: S↓A; u; F; 1; C; A; ψ]

exhibiting C as a left extension of F along u, there is g : S→A so that f factors as

\xymatrix{B \ar[r] & F (g) \ar[r] & C}

We say that S is retract-closed when a retract of any object in S is isomorphic to an object in S. T is said to be S-ranked when it preserves colimits of all F : S↓A→A.

GENERIC MORPHISMS, PARAMETRIC REPRESENTATIONS AND WEAKLY CARTESIAN

6.2. Remarks.

1. Condition(2) says that the inclusion is a dense functor in the usual sense, and so the condition that A is accessible from S amounts to S being a dense subcategory together with a cocompleteness condition on A. It is instructive to unpack the density condition. It says that to specify a morphism A→B in A, one must assign to each a : S→A an arrow fa : S→B in such a way that a′g = a ⇒ (fa′)g = fa. That is, maps out of S ∈ S play the role of generalised elements.

2. A sufficient condition for B to be S-small is for A(B, −) to preserve the colimits of all F : S↓A→A.

6.3. Examples.

1. Fix a regular cardinal λ and denote by A_{λ} the full subcategory of A consisting of the λ-presentable objects. If A is λ-accessible in the usual sense then A_{λ} is essentially small (that is, equivalent to a small category) and A is accessible from A_{λ}. λ-presentable objects are A_{λ}-small by 6.2(2). If T preserves λ-filtered colimits then it is A_{λ}-ranked.

2. Let C be a small category. [Cop, Set] is C-accessible via the yoneda embedding. Representable functors are C-small by 6.2(2) since homming out of C(−, C) is evaluating at C, which has left and right adjoints, and so in particular preserves all colimits.

6.4. Definition. Given f : A→T (B), the category Fact(f) is defined as follows:

• objects: pairs (g : A→T (C), h : C→B) such that f = T (h)g.

• arrows: an arrow (g, h)→(g′, h′) in Fact(f) is a morphism δ as in

[figure: A; g′; g; T (C′); T (h′); T (C); T (h); T (δ); T (Y)]

such that δT (g) = T (g′) and h′δ = h.

Clearly to demand that T admits generic factorisations is to ask that Fact(f) has a weak initial object for every such f. Similarly, T admits strict generic factorisations if and only if Fact(f) has an initial object for every such f.

6.5. Lemma. If A has wide pullbacks and T preserves them, then for any f : A→T (B), Fact(f) is complete.

Proof. It suffices to show that Fact(f) has (arbitrary) products and pullbacks, and these are easily constructed directly using the hypotheses of this lemma.

Recall from [Mac71], that a solution set for a category A is a set X of objects of A that is jointly weakly initial, in the sense that for any A ∈ A, there is an S ∈ X and a morphism S→A. Recall also that the initial object theorem constructs an initial object for any category that is locally small, complete, and possesses a solution set. Clearly such an initial object will be a retract of some S ∈ X.

6.6. Theorem. Let A be accessible from S, S be retract closed, all S ∈ S be Ssmall, and T be S-ranked. If T preserves wide pullbacks, then it admits strict generic factorisations.

Proof. For any f : A→T B we must construct an initial object for Fact(f). By the initial object theorem it suffices by (6.5) to verify that Fact(f) has a solution set. We shall show that there is a set X of objects of A, depending only on A, such that any f as above factors as

\xymatrix{A \ar[r]^{g} & T (S) \ar[r]^{T (h)} & T (B)}

where S∈X A solution set for Fact(f) will be obtained as consisting of pairs

( \xymatrix{A \ar[r] & T (S)} , \xymatrix{S \ar[r] & B} )

where S ∈ X. Since X is a set and A is locally small, this is indeed a set. Consider first the case where A is in S. Noting that T (B) is the colimit of T applied to B’s canonical diagram, since T is S-ranked, the S-smallness of A guarantees that f factors through a component of this colimiting cocone for T (B). Thus we can take the elements of X to be the objects of S. An initial object of Fact(f), which is a generic factorisation of f, is a retract of a factorisation of f in our solution set, which amounts to saying that f factors as

\xymatrix{A \ar[r]^{g} & T (S) \ar[r]^{T (h)} & T (B)}

where g is generic, and S is the retract of an object S, and thus can be taken to be in S since S is retract closed. In the general case, for any S ∈ S and σ ∈ A(S, A), using the S-smallness of S and the rank of T, we obtain S_{σ} ∈ S, g_{σ} and h_{σ} making

\xymatrix{S \ar[r]^{σ} \ar[d]_{g_{σ}} & A \ar[d]^{f} \\ T (S_{σ}) \ar[r]_{T (h_{σ})} & T (B)}

commute. Moreover, we may assume that the g_{σ} are generic by the above analysis of the case where A ∈ S (applied to A = S). Given an arrow

\xymatrix{S_{1} \ar[rr]^{ψ} \ar[dr]_{σ_{1}} &  & S_{2} \ar[dl]^{σ_{2}} \\  & A}

GENERIC MORPHISMS, PARAMETRIC REPRESENTATIONS AND WEAKLY CARTESIAN

in S↓A, notice that there is a unique T -fill S_{ψ} in

[figure: S_{1}; ψ; g_{σ_{1}}; S_{2}; g_{σ_{2}}; T (S_{σ_{2}}); T (h_{σ_{2}}); T (S_{σ_{1}}); T (h_{σ_{1}}); T (S_{ψ}); T (B)]

as g_{σ_{1}} is generic. Since these T -fills are induced uniquely, they provide the arrow mappings of a functor S_{(−)}, and the g_{σ}’s and the h_{σ}’s are the components of natural transformations g and h, so that

[figure: S↓A; π; S_{(−)}; 1; B; S; I; A; T; S; I; A; h; g; S↓A; π; 1; B; A; A; T; S; I; A; k_{A}; f]

Upon taking colimits, and denoting by \overline{S} the colimit of IS_{(−)}, this last equality provides a factorisation of f as

\xymatrix{A \ar[r]^{\overline{g}} & T (\overline{S}) \ar[r]^{T (\overline{h})} & T (B)}

So we can take X to be objects in the image of

[figure: [S↓A, S]; I∘−; [S↓A, A]; colim; A]

which is small because the functor category [S↓A, S] is small, since S↓A and S are small.

In the previous proof it was necessary to understand generic factorisations of morphisms out of objects of S first, before proceeding to the general case. This made evident the following useful fact.

6.7. Scholium. Let A be accessible from S, S be retract-closed, all S ∈ S be S-small and T be S-ranked. If A ∈ S and g : A→T B is generic, then B is isomorphic to an object of S.

Proof. T applied to B’s canonical diagram gives T B as a colimit of T S’s where S ∈ S, and A is S-small, and so g factors through a component of this universal cocone. This exhibits B as a retract of some S ∈ S.

Recall that a category is cofiltered when its dual is filtered, and a functor F is cofinitary when it preserves cofiltered limits, or equivalently, when F op is finitary.

6.8. Theorem. Let A be accessible from S, S be retract-closed, all S ∈ S be S-small and T be S-ranked. Suppose also that the automorphism groups of the S ∈ S are finite. If T admits generic factorisations relative to the objects of S then T is cofinitary.

Proof. By the dual of theorem(1.5) and corollary(1.7) of [AR94], it suffices to show that T preserves limits of diagrams of the form

\xymatrix{… \ar[r]^{∂_{2}} & X_{2} \ar[r]^{∂_{1}} & X_{1} \ar[r]^{∂_{0}} & X_{0}}

Let c_{n} : X→X_{n} be the components of a universal cone. We must show that the cone for the diagram

\xymatrix{… \ar[r]^{T (∂_{2})} & T (X_{2}) \ar[r]^{T (∂_{1})} & T (X_{1}) \ar[r]^{T (∂_{0})} & T (X_{0})}

whose components are T (c_{n}), is universal. Let x_{n} : A→T X_{n} be the components of some other cone for this diagram. We must show that there is a unique x : A→T X such that T (c_{n}) ∘ x = x_{n}. By 6.2(1) it suffices to consider the case where A ∈ S. Factor x_{0} as

\xymatrix{A \ar[r]^{g} & T (B) \ar[r]^{T (h_{0})} & T (X_{0})}

where g is T -generic and B∈S by (6.7). By induction on n ∈ ℕ, assume that we have factored x_{n} as

\xymatrix{A \ar[r]^{g} & T (B) \ar[r]^{T (h_{n})} & T (X_{n})}

so that we have

\xymatrix{A \ar[r]^{x_{n+1}} \ar[d]_{g} & T (X_{n+1}) \ar[d]^{T (∂_{n})} \\ T (B) \ar[r]_{T (h_{n})} & T (X_{n})}

commutative. A T -fill h_{n+1} for this diagram provides the analogous factorisation of x_{n+1}, and satisfies ∂_{n} ∘h_{n+1} = h_{n}. Thus the h_{n} provide the components of a cone for the original diagram, and so there is a unique h for which c_{n} ∘ h = h_{n}. We can take x to be T (h) ∘ g. To see that this x is unique, consider x′ so that T (c_{n}) ∘ x′ = x_{n}. Factor x′ as

\xymatrix{A \ar[r]^{g′} & T (B′) \ar[r]^{T (h′)} & T (X)}

where g′ is T -generic and B′∈S, and observe that for each n ∈ ℕ,

\xymatrix{A \ar[r]^{g′} \ar[d]_{g} & T (B′) \ar[d]^{T (c_{n}∘h′)} \\ T (B) \ar[r]_{T (h_{n})} & T (X_{n})}

GENERIC MORPHISMS, PARAMETRIC REPRESENTATIONS AND WEAKLY CARTESIAN MONADS 219

is commutative. Since g is T -generic, each of these squares must have a T -fill. Observe that if δ∈A(B, B′) is a T -fill for the n-th square, then it is a T -fill for the m-th square when m < n. Thus either δ is a T -fill for every such square, or there is a maximum n for which it T -fills the n-th square. Since B and B′ ∈ S, the set of isomorphisms in A(B, B′) is finite. Since there are infinitely many squares each of which are T -filled by some δ∈A(B, B′), there must exist a δ which T -fills every square. For this particular δ, T (δ) ∘ g = g′ and for n ∈ ℕ, c_{n} ∘ h′ ∘ δ = h_{n} = c_{n} ∘ h. Since the c_{n} form a universal cone, they are jointly monic, so that h′ ∘ δ = h, and so x′ = T (h′) ∘ g′ = T (h) ∘ g = x.

7. Parametric representability

We shall now explain the sense in which endofunctors T that admit strict generic factorisations have a family of representing objects. In doing so, we obtain 2-categorical descriptions of those concepts related to strict generic morphisms.

7.1. Definition. Let A be accessible from S. A parametric representation for T from S is a 2-cell

[figure: E_{T}; E_{T}; π_{T}; A; T; S; I; A; g_{T}]

that satisfies the following universal property: given any 2-cell ϕ as shown below, there is ϕ̃ and \overline{ϕ} unique so that F = π_{T} ϕ̃ and

[figure: C; G; F; B; H; A; T; S; I; A; ϕ; C; G; ϕ̃; B; H; E_{T}; E_{T}; π_{T}; A; T; S; I; A; \overline{ϕ}; g_{T}]  (2)

The functor E_{T} is called the exponent of the parametric representation. A functor T is said to be parametrically representable from S when there is such a parametric representation for it. It is straightforward to verify that the above universal property determines π_{T}, E_{T} and E_{T} up to isomorphism.

7.2. Example. For n ∈ ℕ, let g_{n} : 1→Mn pick out 1_{n} ∈ Mn. Then this defines a parametric representation

[figure: ℕ; E_{M}; Set; M; 1; 1; Set; g]

of M from 1.

Given a parametric representation for T another description of f : A→T B becomes available. By the definition of parametric representability, there is f̃ and \overline{f} unique so that π_{T} f̃ = π_{A} and

[figure: S↓A; π_{A}; 1; A; T B; S; I; A; α; f; S↓A; f̃; 1; B; E_{T}; E_{T}; π_{T}; A; T; S; I; A; \overline{f}; g_{T}]  (3)

and since α is a left extension, f̃ and \overline{f} determine f uniquely as well.

7.3. Proposition. Let A be accessible from S and T be parametrically representable from S. Then \overline{f} is a left extension iff f is strict T -generic. Moreover, T admits strict generic factorisations.

Proof. To say that

\xymatrix{A \ar[d]_{f} \ar[r]^{ϕ} & T X \ar[d]^{T γ} \\ T B \ar[r]_{T β} & T Y}

commutes is to say that

[figure: S↓A; f̃; 1; B; Y; E_{T}; E_{T}; A; \overline{f}; β; S↓A; f̃; 1; X; Y; E_{T}; E_{T}; A; \overline{ϕ}; γ]

so a T -fill for the original square is induced uniquely when \overline{f} is a left extension. Since A is accessible from S, any such \overline{f} will factor as

[figure: S↓A; f̃; 1; C; B; E_{T}; E_{T}; A; \overline{g}; h]

where \overline{g} is a left extension, and so f = T (h)g with \overline{g} a left extension. Thus T admits strict generic factorisations. Taking f to be generic, h is an isomorphism by (5.7), whence \overline{f} is a left extension.

GENERIC MORPHISMS, PARAMETRIC REPRESENTATIONS AND WEAKLY CARTESIAN

7.4. Examples.

1. Take A to be Set and S to consist of the one-element set 1. If T is parametrically representable with E_{T} = 1 then T is representable in the usual sense, with the exponent E_{T} picking out the representing object of T.

2. For S and A as in (1), T is parametrically representable iff T is a coproduct of representable functors, and E_{T} must always be a set, with E_{T} picking out the representing objects of these representable functors.

7.5. Theorem. Let A be accessible from S and have a terminal object 1. If T admits strict generic factorisations relative to the objects of S then it is parametrically representable from S. Moreover, the resulting parametric representation exhibits T as a pointwise left extension of Iπ_{T} along E_{T}, and π_{T} is a discrete fibration.

Proof. For S ∈ S and x : S→T 1, choose a strict generic factorisation

\xymatrix{S \ar[r]^{g_{x}} & T \overline{x} \ar[r]^{T (!)} & T 1}

of x. Given

\xymatrix{S_{1} \ar[dr]^{x} \ar[dd]_{f} \\  & T 1 \\ S_{2} \ar@{-->}[ur]_{y}}

an arrow of S↓T 1, the strict genericness of g_{x} induces a unique \overline{f_{xy}} : \overline{x}→\overline{y} making

\xymatrix{S_{1} \ar[d]_{g_{x}} \ar[r]^{f} & S_{2} \ar[d]^{g_{y}} \\ T \overline{x} \ar[r]_{T \overline{f_{xy}}} & T \overline{y}}

commute. So we define that E_{T} : S↓T 1→A takes the above arrow of S↓T 1 to \overline{f_{xy}}, and the component of

[figure: S↓T 1; E_{T}; π_{T 1}; A; T; S; I; A; g]

at x as g_{x}. It now remains to verify that g is a parametric representation for T and that it exhibits T as a pointwise left extension of Iπ_{T 1} along E_{T}. To see that G is a parametric representation, consider ϕ as in (2). For C∈C take ϕ̃(C) = T!ϕ_{C} and \overline{ϕ}_{C} to be the unique T -fill of

\xymatrix{IF C \ar[r]^{ϕ_{C}} \ar[d]_{g_{x}} & T HGC \ar[d]^{T!} \\ T \overline{x} \ar[r]_{T!} & T 1}

where x = ϕ̃(C). For f : C_{1}→C_{2} in C, take ϕ̃(f) = IF f. Notice that F = π_{T 1}ϕ̃ and (2) hold by definition. The functoriality of ϕ̃, the naturality of \overline{ϕ} and their required uniqueness follows easily since all the g_{x}’s are strict generics. To see that g is a pointwise left extension we verify directly that given ψ and X

[figure: E_{T} ↓X; B; U; S↓T 1; π_{T 1}; S; I; A; ψ; E_{T} ↓X; B; X; U; S↓T 1; E_{T}; π_{T 1}; A; T; S; I; A; λ; g; ψ̂]  (4)

there is a unique ψ̂ satisfying (4). Here λ is the usual comma object, that is, the natural transformation whose component at (x : S→T 1, y : E_{T} (x)→XB, B) is y. For B ∈ B, in view of (6.2)(1), we specify ψ̂_{B} : T XB→UB by assigning to each f : S→T XB with S ∈ S, the morphism ψ_{(}x, f̂, B) : S→UB, where x = T!(f) and f̂ is the unique T -fill for

\xymatrix{S \ar[r]^{f} \ar[d]_{g_{x}} & T XB \ar[d]^{T!} \\ T \overline{x} \ar[r]_{T!} & T 1}

The well-definedness of the ψ̂_{B}, their naturality, equation(4), and the required uniqueness of ψ̂ are all straightforward to verify.

When A is accessible from S, and T and U are parametrically representable from S, another description of 2-cells ϕ : T ⇒U becomes available. That is, there is ϕ̃ and \overline{ϕ} unique so that π_{U} ϕ̃ = π_{T} and

[figure: E_{T}; E_{T}; π_{T}; A; T; U; S; I; A; g_{T}; ϕ; E_{T}; ϕ̃; E_{T}; E_{U}; E_{U}; π_{U}; A; U; S; I; A; \overline{ϕ}; g_{U}]  (5)

GENERIC MORPHISMS, PARAMETRIC REPRESENTATIONS AND WEAKLY CARTESIAN

and when g_{T} is a left extension, as is the case when A has a terminal object, ϕ̃ and \overline{ϕ} determine ϕ uniquely as well.

7.6. Theorem. Let A be accessible from S and ϕ : T ⇒U with T and U parametrically representable from S.

1. \overline{ϕ} is an isomorphism ⇒ ϕ is cartesian.

2. A has a terminal object and ϕ is cartesian ⇒ \overline{ϕ} is an isomorphism.

Proof. (1): By (5.10)(5) and (7.3) it suffices to prove that ϕ preserves generics. Let f : A→T B be generic. Then by equations (3) and (5), \overline{ϕ_{B}f} is the composite

[figure: S↓A; !; f̃; 1; B; E_{T}; ϕ̃; E_{T}; E_{U}; E_{U}; A; \overline{f}; \overline{ϕ}]  (6)

Since f is generic, \overline{f} exhibits B as a left extension of E_{T} f̃ along !, and since \overline{ϕ} is an isomorphism, (6) exhibits B as a left extension of E_{U} ϕ̃f̃ along !. Thus by (7.3) ϕ_{B}f is generic. (2): Since A has a terminal object, the explicit descriptions of the parametric representations of T and U in terms of generics, used in the proof of (7.5), become available. Take ϕ̃ to be ϕ_{1}∘− : S↓T 1→S↓U1, and for x : S→T 1, take \overline{ϕ}_{x} to be the unique U-fill of

\xymatrix{S \ar[d]_{g_{ϕ_{1}x}} \ar[r]^{g_{x}} & T \overline{x} \ar[r]^{ϕ\overline{x}} & U\overline{x} \ar[d]^{U!} \\ U\overline{ϕ_{1}x} \ar[rr]_{U!} &  & U1}

It is straightforward to verify that this defines ϕ̃ and \overline{ϕ} satisfying equation(5). Since ϕ preserves generics, \overline{ϕ}_{x} must be an isomorphism for all x by (5.7).

8. Parametrically representable endofunctors of presheaf categories

Let λ be a regular cardinal. Recall that T is said to have rank λ when it preserves λ-filtered colimits. We shall now use the above analysis to understand parametric representability for endofunctors of [Cop, Set].

224  MARK WEBER

8.1. Theorem. For an endofunctor T of [Cop, Set] with rank λ, the following statements are equivalent.

1. T is parametrically representable from C (via the yoneda embedding).

2. T admits strict generic factorisations.

3. T preserves wide pullbacks. Moreover when T satisfies these hypotheses, f : A→T B is generic and A is a λ-presentable object ⇒ B is a λ-presentable object. Proof. (1) ⇒ (2) by (7.3), (2) ⇒ (1) by (7.5), and (2) ⇒ (3) by (5.17)(2). For (3) ⇒ (2) apply (6.6) this time where S = [Cop, Set]_{λ}. The final statement of the theorem follows from (6.7).

Applying (7.6) in this case enables one to understand cartesian transformations between such endofunctors of [Cop, Set].

9. The tree monad and Ω

Two of the most fundamental mathematical objects that arise in the higher category theory of Michael Batanin in [Bat98], [Bat02b], [Bat02a] and [Bat03] are

1. The monad T on Glob whose algebras are strict ω-categories. It was denoted as D_{s} in [Bat98], and we shall refer to it as the tree monad.

2. The category Ω of plane trees described in (4). We shall describe these objects in terms of generic morphisms.

The underlying endofunctor of T is obtained as a left extension

[figure: y↓Tr; E_{T}; π_{T}; Glob; T; 𝔾; y; Glob; g_{T}]

which in turn is a parametric representation of T . The following proposition is an immediate consequence of this description of T , (4.7) and (7.3). 9.1. Proposition.

1. T admits strict generic factorisations.

2. f : A→T B is generic and A is a globular cardinal ⇒ B is a globular cardinal.

GENERIC MORPHISMS, PARAMETRIC REPRESENTATIONS AND WEAKLY CARTESIAN MONADS 225

We shall now describe the monad structure purely in terms of generics. This description hinges on the fact that for a globular cardinal A (whose corresponding tree is) of height ≤ n, there is a unique x : 𝔾(−, n)→Tr so that E_{T} (x)≅A. By (7.3) it follows that this amounts to saying that f : A→X uniquely determines f̂ so that

\xymatrix{𝔾(−, n) \ar[rr]^{f̂} \ar[dr]_{g} &  & T X \\  & T A \ar[ur]_{T f}}

commutes where g is T -generic. Conversely, by generically factorising f̂ one determines f and A, and this describes the isomorphism of sets

Glob(𝔾(−, n), T X) ≅ ∑_{T ∈Tr_{n}} Glob(E_{T} (n, T), X)

which corresponds to the original description of T in [Bat98]. The description of T ’s monad structure proceeds as follows:

1. Fix a parametric representation for T from tr. In terms of generics this amounts to a choice of generic factorisation of every A→T X where A is a globular cardinal.

2. In view of (6.2)(1) we specify η_{X} : X→T X for X in Glob by assigning x̂ to x : 𝔾(−, n)→X.

3. In view of (6.2)(1) we specify μ_{X} : T T X→T X for X in Glob by assigning x̂′ to x : 𝔾(−, n)→T T X, where the T T -generic factorisation

\xymatrix{𝔾(−, n) \ar[rr]^{x} \ar[dr]_{g} &  & T T X \\  & T T A \ar[ur]_{T T x′}}

of x is specified by (1) and (5.14), and so by (9.1) A is a globular cardinal.

The well-definedness of the components of η and μ, their cartesian naturality and the monad axioms are all easily verified. That T -algebras are strict-ω-categories is immediate from the definition, if one takes strict-ω-category structures to be defined as a choice of unique composites of globular pasting diagrams. The proof that this corresponds with strict-ω-categories defined by successive enrichment can be found in [Lei00]. The following characterisation of Ω, originally due to Clemens Berger [Ber02], follows from (4.8), (7.3) and the above generic description of the tree monad.

9.2. Proposition. Ω is isomorphic to the dual of the following subcategory of the Kleisli category of T :

• objects are globular cardinals.

• an arrow A→B is a T -generic morphism A→T B

10. Analytic endofunctors of Set II

In this subsection we continue the discussion of section (3), and characterise the images of G and E in terms of generics.

10.1. Theorem. For a finitary endofunctor T of Set the following statements are equivalent.

1. T is strongly analytic.

2. T admits strict generic factorisations.

3. T preserves wide pullbacks.

Moreover when T satisfies these hypotheses, f : A→T B is generic and A is a finite set ⇒ B is finite.

Proof. Suppose that T is strongly analytic. Then by definition, T comes equipped with a cartesian transformation τ : T ⇒M. Thus (1)⇒(2) since M admits strict generic factorisations by (5.5) and τ preserves and reflects generics since it is cartesian. Now suppose that T is parametrically representable from 1. Then for a given parametric representation, E_{T} must factor through Set_{f} since T is finitary. Defining ϕ̃ : T 1→ℕ by ϕ̃x = |E_{T} x| and choosing a bijection \overline{ϕ}_{x} : E_{M}(|E_{T} x|)→E_{T} x produces

[figure: T 1; ϕ̃; E_{T}; ℕ; E_{M}; Set; \overline{ϕ}]

which corresponds by (7.6) and the parametric representation for M given in (7.2), to a cartesian transformation ϕ : T ⇒M. The result now follows from (8.1).

10.2. Theorem. For ϕ : S⇒T, a natural transformation between strongly analytic functors, the following statements are equivalent:

1. ϕ is strongly analytic.

2. ϕ preserves and reflects generics.

3. ϕ is cartesian.

Proof. To say that ϕ is strongly analytic is to say that there are cartesian transformations σ and τ making

\xymatrix{S \ar[rr]^{ϕ} \ar[dr]_{σ} &  & T \ar[dl]^{τ} \\  & M}

commute. Thus (1)⇒(2). Conversely, if ϕ is cartesian and T is strongly analytic, we have τ : T ⇒M cartesian and σ = τϕ exhibits S and ϕ as strongly analytic. Since S admits strict generic factorisations (2)⇔(3) by (5.10) and (5.11).

GENERIC MORPHISMS, PARAMETRIC REPRESENTATIONS AND WEAKLY CARTESIAN MONADS 227

This completes the characterisation of the image of G. We begin with that of E by observing

10.3. Lemma. Let ϕ : X→Y ∈ [ℙ, Set]. Then Eϕ is weakly cartesian.

Proof. Let f : A→B ∈ Set. We must show that

\xymatrix{E(X)(A) \ar[r]^{E(X)(f)} \ar[d]_{E(ϕ)_{A}} & E(X)(B) \ar[d]^{E(ϕ)_{B}} \\ E(Y)(A) \ar[r]_{E(Y)(f)} & E(Y)(B)}

is weakly cartesian. Consider [y ∈ Y (m), g ∈ A^{m}] ∈ E(Y)(A) and [x ∈ X(n), h ∈ B^{n}] ∈ E(X)(B) so that [y, fg] = [ϕ(x), h]. This says that m = n, and that there is ρ ∈ Sym_{n} so that Y (ρ)(y) = ϕ(x) and fgρ = h. Since [y, g] = [Y (ρ)(y), gρ] by definition, we can assume without loss of generality that y and g were chosen so that y = ϕ(x) and fg = h. Thus [x, g] ∈ E(X)(A) satisfies E(ϕ)_{A}[x, g] = [y, g] and E(X)(f)[x, g] = [x, h].

10.4. Corollary. For T analytic, c_{T} as defined in (3) is weakly cartesian.

We denote by WcEnd(Set) the subcategory of End(Set) consisting of all endofunctors of Set and weakly cartesian transformations between them, and write I for the inclusion. Lemma(10.3) demonstrates that E is a composite

\xymatrix{[ℙ, Set] \ar[r]^{E^{∘}} & WcEnd(Set) \ar[r]^{I} & End(Set)}

For T ∈ End(Set) and n ∈ ℕ, denote by r^{∘}(T)(n) the set of T -generic morphisms f : 1→T (n). Lemma(5.10) guarantees that for weakly cartesian α : T ⇒T′,

\xymatrix{f \ar@{|->}[r] & α_{n} ∘ f}

are well-defined arrow mappings for the functor

\xymatrix{WcEnd(Set) \ar[r]^{r^{∘}} & [ℙ, Set]}

Recall r : End(Set)→[ℙ, Set] from section (3), the functor that corresponds to restriction along E_{C} : ℙ→Set which regards permutations as bijective functions. Since r(T)(n) may be viewed as the set of all morphisms 1→T (n), there are natural inclusions which assemble together to provide a monomorphism ψ : r^{∘}⇒rI.

10.5. Lemma. Let X be a species. Then an element of rE(X)(n) is in the image of η_{X,n} iff it is E(X)-generic as an arrow 1→E(X)(n).

Proof. (⇒): Recalling the definition of E(X), the commutativity of

\xymatrix{1 \ar[r]^{[x′,f]} \ar[d]_{[x,1_{n}]} & E(X)(A) \ar[d]^{E(X)(γ)} \\ E(X)(n) \ar[r]_{E(X)(β)} & E(X)(B)}

where x ∈ X(n), x′ ∈ X(m), and f ∈ A^{m}, means that [x, β] = [x′, γf]. That is, m = n and there is ρ ∈ Sym_{n}, so that x = X(ρ)(x′) and β = γfρ. However [x′, f] = [X(ρ)(x′), fρ] by definition, so that without loss of generality we may assume that x′ and f were chosen so that x = x′ and β = γf. Thus f is a E(X)-fill for this square. (⇐): Let [x, f] : 1→E(X)(n) where f : m→n, be E(X)-generic. Since [x, f] factors as

\xymatrix{1 \ar[r]^{[x,1]} & E(X)(m) \ar[r]^{E(X)(f)} & E(X)(n)}

and [x, 1] is E(X)-generic also, m = n and f is an automorphism of n by lemma(5.7), so that [x, f] = [X(f^{−1})(x), 1].

A conceptual restatement of this lemma is

10.6. Corollary. η factors as

[figure: [ℙ, Set]; 1; E^{∘}; [ℙ, Set]; WcEnd(Set); I; End(Set); r; η; [ℙ, Set]; 1; E^{∘}; [ℙ, Set]; WcEnd(Set); I; r^{∘}; End(Set); r; η^{∘}; ψ; =]  (7)

where η^{∘} is an isomorphism.

Noting that for T ∈ End(Set) and Z ∈ Set, E^{∘}r^{∘}(T)(Z) is the subset of Er(T)(Z) consisting of those [f, g] such that f : 1→T n is T -generic, and we define ε^{∘} : E^{∘}r^{∘}⇒1 by ε^{∘}[f, g] = T (g)∘f which by definition satisfies

[figure: WcEnd(Set); r^{∘}; I; [ℙ, Set]; E^{∘}; End(Set); 1; r; WcEnd(Set); I; End(Set); ψ; ε; WcEnd(Set); r^{∘}; I; 1; [ℙ, Set]; E^{∘}; End(Set); 1; WcEnd(Set); I; End(Set); ε^{∘}; =; =]  (8)

10.7. Lemma. ε^{∘} is monic.

GENERIC MORPHISMS, PARAMETRIC REPRESENTATIONS AND WEAKLY CARTESIAN MONADS 229

Proof. Let f : 1→T (n) be T -generic, g : n→Z, f′ : 1→T (m) be T -generic, and g′ : m→Z, with ε^{∘}[f, g] = ε^{∘}[f′, g′]. Then

\xymatrix{1 \ar[r]^{f′} \ar[d]_{f} & T (m) \ar[d]^{T (g′)} \\ T (n) \ar[r]_{T (g)} & T (Z)}

commutes, and so has a T -fill that is an isomorphism. That is m = n, and there is ρ ∈ Sym_{n} so that T (ρ)(f) = f′ and g′ρ = g. Thus, [f, g] = [T (ρ^{−1})(f′), g′ρ] = [f′, g′].

Recall that an arrow f in a 2-category K is representably faithful when for any K ∈ K, the functor K(K, f) is faithful.

10.8. Lemma. Consider an adjunction η, ε: IE^{∘} ⊣ r, 2-cells η^{∘} : 1⇒r^{∘}E^{∘} and ε^{∘} : E^{∘}r^{∘}⇒1, and, a monomorphism ψ : r^{∘}⇒rI, in a 2-category, where I is representably faithful, and suppose that this data satisfies (7) and (8). Then η^{∘}, ε^{∘}: E^{∘} ⊣ r^{∘}.

Proof. The triangular identities for η^{∘} and ε^{∘} follow immediately from those for η and ε, and the hypotheses of this lemma.

Applying (10.8) to the present situation produces

[figure: WcEnd(Set); r^{∘}; [ℙ, Set]; E^{∘}; ⊥]

with unit η^{∘} an isomorphism and counit ε^{∘} a monomorphism. Thus we obtain an elementary characterisation of the image of E in terms of generics and weakly cartesian transformations.

10.9. Proposition.

1. T ∈ End(Set) is analytic iff every 1→T Z factors as

\xymatrix{1 \ar[r]^{g} & T n \ar[r]^{T (h)} & T Z}

where g is T -generic and n ∈ ℕ.

2. EX⇒EY is analytic iff it is weakly cartesian.

Proof. (1): T ∈ End(Set) is analytic iff ε_{T}^{∘} is epic, which amounts to the condition that every 1→T Z factors as above. (2): E^{∘} is fully-faithful since η^{∘} is an isomorphism.

This result appears as propositions 2 and 3 of the appendix of [Joy86].

10.10. Theorem. For a finitary endofunctor T of Set the following statements are equivalent.

1. T is analytic.

2. T admits generic factorisations.

3. There is a unique ϕ : T ⇒C which preserves and reflects generics.

Moreover when T satisfies these hypotheses, f : A→T B is generic and A is a finite set ⇒ B is finite.

Proof. (1)⇒(2): Consider f as in (2) we factor it by choosing \overline{f} so that f = c_{T,Z} ∘ \overline{f} (using the surjectivity of c_{T,Z}), and factoring \overline{f} using (10.1)

\xymatrix{A \ar[rr]^{f} \ar[dr]^{\overline{f}} \ar[ddr]_{g} &  & T (Z) \\  & \overline{T} (Z) \ar[ur]^{c_{T,Z}} \\  & \overline{T} (H) \ar[u]_{\overline{T} (h)} \ar[r]_{c_{T,H}} & T (H) \ar[uu]_{T (h)}}

so that g is \overline{T} -generic. By (5.10) and (10.4), c_{T,H} ∘ g is T -generic. Moreover, if A is finite and f is generic then B is finite by (10.1). (1)⇒(3): By (1) there is a species X and a natural isomorphism ι : T ⇒E(X). Composing with ι gives a bijection WcEnd(Set)(T, C)≅WcEnd(Set)(E(X), C). Since E(1) = C, WcEnd(Set)(E(X), C)≅1 by (10.9)(2). That is, there is a unique weakly cartesian ϕ : T ⇒C, and so it suffices to show that ϕ reflects generics. By (1)⇒(2) T admits generic factorisations, and so by (5.13)(1), ϕ reflects generics. (3)⇒(2): Since C admits generic factorisations the result follows from (5.13)(2). (2)⇒(1): Immediate from (10.9)(1).

10.11. Theorem. For ϕ : S⇒T, a natural transformation between analytic functors, the following statements are equivalent:

1. ϕ is analytic.

2. ϕ preserves and reflects generics.

3. ϕ is weakly cartesian.

Proof. (1)⇔(3) by (10.9). Since S admits generic factorisations by (10.10), (3)⇔(2) by (5.10) and (5.13).

GENERIC MORPHISMS, PARAMETRIC REPRESENTATIONS AND WEAKLY CARTESIAN MONADS 231

By comparing (10.11) and (10.2) the following observation of Batanin in [Bat02a] is immediate.

10.12. Corollary. Let S and T be strongly analytic and ϕ : S⇒T. Then ϕ is weakly cartesian ⇒ ϕ is cartesian.

It is shown in the appendix of [Joy86] that T ∈ End(Set) is analytic iff it is finitary, cofinitary and weak pullback preserving. Given the above characterisation of analytic functors one direction of Joyal’s result is now immediate. Namely, from (10.10), (5.17) and (6.8) analytic functors possess these properties.

11. Weakly cartesian monads and their operads

We now exhibit the generalised notion of cartesian monad and operad over it as promised in (2.7)(5). First we require a notion of collection.

11.1. Definition. Let T ∈ End(A). The category T -Coll of T -collections is defined as the full subcategory of End(A)↓T consisting of the σ : S⇒T such that S admits generic factorisations and σ is weakly cartesian.

In general, T -Coll here is different to the definition of T -Coll given in section(2). However by proposition(5.13)(3) the definitions coincide when T admits strict generic factorisations.

11.2. Definition. A monad (T, η, μ) on A is weakly cartesian when it satisfies the following axioms:

1. T admits generic factorisations.

2. η and μ are weakly cartesian.

11.3. Remark. By (5.10), (5.13) and (5.15), “weakly cartesian” in (11.2) and (11.1) can be replaced by “preserves and reflects generics”.

An immediate consequence of (5.15) and (5.16) is

11.4. Proposition. Let T be a weakly cartesian monad on A. Then T -Coll is a monoidal subcategory of End(A)↓T.

11.5. Definition. Let T be a weakly cartesian monad on A.

1. A T -operad is a monoid in T -Coll. Thus, a T -operad consists of a weakly cartesian monad morphism S⇒T.

2. An algebra of a T -operad S⇒T is an algebra of the monad S.

11.6. Examples.

1. Cartesian monads are weakly cartesian monads whose generics are strict. The collections and operads defined here coincide with those defined in section(2).

2. C (the commutative monoid monad on Set) is a weakly cartesian monad. A symmetric operad in Set is usually defined to be a monoid in [ℙ, Set] for substitution of species. The functor E is strong monoidal with respect to substitution of species and composition of endofunctors. Moreover, it is easy to verify directly that E is faithful, and so by definition, provides a monoidal equivalence between [ℙ, Set] and the category of analytic functors and analytic natural transformations. Thus a symmetric operad amounts to a monad T on Set whose functor part, unit and multiplication are all analytic. That is, by the results of the previous section symmetric operads in Set are precisely C-operads.

References

[AR94] J. Adamek and J. Rosicky, Locally presentable and accessible categories, London Math Soc. Lecture Notes, no. 189, Cambridge University Press, 1994.

[Bat98] M. Batanin, Monoidal globular categories as a natural environment for the theory of weak n-categories, Advances in Mathematics 136 (1998), 39–103.

[Bat02a] , Computads and slices of operads, preprint, 2002.

[Bat02b] , The Eckmann-Hilton argument, higher operads and E_{n}-spaces, preprint, 2002.

[Bat03] , The combinatorics of iterated loop spaces, preprint, 2003.

[Bén91] J. Bénabou, Some remarks on free monoids in a topos, Lecture Notes in Math. 1488 (1991), 20–29.

[Ber02] C. Berger, A cellular nerve for higher categories, Advances in Mathematics 169 (2002), 118–175.

[BS00] M. Batanin and R. Street, The universal property of the multitude of trees, JPAA 154 (2000), 3–13.

[Bur71] A. Burroni, T-categories (catégories dans un triple), Cahiers Topologie Gom. Differentielle Catégoriques 12 (1971), 215–321.

[CJ95] A. Carboni and P.T. Johnstone, Connected limits, familial representability and Artin glueing, Mathematical Structures in Computer Science 5 (1995), 441–459.

[Die77] Y. Diers, Catégories localisables, Ph.D. thesis, Université de Paris VI, 1977.

GENERIC MORPHISMS, PARAMETRIC REPRESENTATIONS AND WEAKLY CARTESIAN

MONADS 233

[Gir86] J.-Y. Girard, The system F of variable types, fifteen years later, Theoret. Comput. Sci 45 (1986), 159–192.

[Her00a] C. Hermida, From coherent structures to universal properties, J. Pure Appl. Algebra 165 (2000), 7–61.

[Her00b] , Representable multicategories, Advances in Mathematics 151 (2000), 164–225.

[Joy86] A. Joyal, Foncteurs analytiques et espèces de structures, Lecture Notes in Math. 1234 (1986), 126–159.

[Kel72a] G.M. Kelly, An abstract approach to coherence, Lecture Notes in Math. 281 (1972), 106–147.

[Kel72b] , Many-variable functorial calculus I, Lecture Notes in Math. 281 (1972), 66–105.

[Kel92] , On clubs and data-type constructors, Applications of categories to computer science, Cambridge University Press, 1992, pp. 163–190.

[Lam88] F. Lamarche, Modelling polymorphism with categories, Ph.D. thesis, McGill, 1988.

[Lei00] T. Leinster, Operads in higher-dimensional category theory, Ph.D. thesis, University of Cambridge, 2000.

[Lei03] , Higher operads, higher categories, lecture note series, London Mathematical Society, 2003.

[Mac71] S. Mac Lane, Categories for the working mathematician, Graduate Texts in Mathematics, vol. 5, Springer-Verlag, 1971.

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

[Str91] , Parity complexes, Cahiers Topologie Géom. Différentielle Catégoriques 32 (1991), 315–343.

[Str00] , The petit topos of globular sets, J. Pure Appl. Algebra 154 (2000), 299– 315.

[Tay88] P. Taylor, The trace factorisation of stable functors, preprint, 1988.

[Tay90] , An algebraic approach to stable domains, JPAA 64 (1990), 171–203.

[Web01] M. Weber, Symmetric operads for globular sets, Ph.D. thesis, Macquarie University, 2001.

Department of Mathematics and Statistics, University of Ottawa

Email: Mark.Weber@science.uottawa.ca

This article may be accessed via WWW at http://www.tac.mta.ca/tac/ or by anony-

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

THEORY AND APPLICATIONS OF CATEGORIES (ISSN 1201-561X) will disseminate articles that significantly advance the study of categorical algebra or methods, or that make significant new contributions to mathematical science using categorical methods. The scope of the journal includes: all areas of pure category theory, including higher dimensional categories; applications of category theory to algebra, geometry and topology and other areas of mathematics; applications of category theory to computer science, physics and other mathematical sciences; contributions to scientific knowledge that make use of categorical methods.

Articles appearing in the journal have been carefully and critically refereed under the responsibility of members of the Editorial Board. Only papers judged to be both significant and excellent are accepted for publication.

The method of distribution of the journal is via the Internet tools WWW/ftp. The journal is archived electronically and in printed paper format.

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

rrosebrugh@mta.ca.

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

Editorial board.

Michael Barr, McGill University: barr@barrs.org, Associate Managing Editor Lawrence Breen, Université Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of Wales Bangor: r.brown@bangor.ac.uk Jean-Luc Brylinski, Pennsylvania State University: jlb@math.psu.edu Aurelio Carboni, Università dell Insubria: aurelio.carboni@uninsubria.it Valeria de Paiva, Palo Alto Research Center: paiva@parc.xerox.com Martin Hyland, University of Cambridge: M.Hyland@dpmms.cam.ac.uk P. T. Johnstone, University of Cambridge: ptj@dpmms.cam.ac.uk G. Max Kelly, University of Sydney: maxk@maths.usyd.edu.au Anders Kock, University of Aarhus: kock@imf.au.dk Stephen Lack, University of Western Sydney: s.lack@uws.edu.au F. William Lawvere, State University of New York at Buffalo: wlawvere@buffalo.edu Jean-Louis Loday, Université de Strasbourg: loday@math.u-strasbg.fr Ieke Moerdijk, University of Utrecht: moerdijk@math.uu.nl Susan Niefield, Union College: niefiels@union.edu Robert Paré, Dalhousie University: pare@mathstat.dal.ca Robert Rosebrugh, Mount Allison University: rrosebrugh@mta.ca, Managing Editor Jiri Rosicky, Masaryk University: rosicky@math.muni.cz James Stasheff, University of North Carolina: jds@math.unc.edu Ross Street, Macquarie University: street@math.mq.edu.au Walter Tholen, York University: tholen@mathstat.yorku.ca Myles Tierney, Rutgers University: tierney@math.rutgers.edu Robert F. C. Walters, University of Insubria: robert.walters@uninsubria.it R. J. Wood, Dalhousie University: rjwood@mathstat.dal.ca