Theory and Applications of Categories, Vol. 22, No. 5, 2009, pp. 97–135.

CATEGORIES WITH SLICING

THORSTEN PALM

Abstract. Prior work towards the subject of higher-dimensional categories gives rise to several examples of a category over Cat to which the slice-category construction can be lifted universally. The present paper starts by supplying this last clause with a precise meaning. It goes on to establish for any such category a certain embedding in a presheaf category, to describe the image, and hence to derive conditions collectively sufficient for that functor to be an equivalence. These conditions are met in the foremost of the examples: the category of dendrotopic sets.

Introduction

One of the fundamental concepts of category theory is the category-of-elements construction. For a fixed category 𝔰 it associates with each presheaf (= contravariant set-valued functor) X on 𝔰 a category 𝔰↓X, thus giving rise to a functor 𝔰↓^{( )} from Set^{𝔰^{op}} to Cat (provided 𝔰 is small). This functor is faithful and conservative, and so it is not surprising that it allows for many presheaf concepts to be discussed at the level of categories. Here are some paradigmatic facts. A presheaf is representable if and only if its image has a terminal object. The presheaf morphism constructed in (the proof of) the Yoneda lemma is mapped to the slice-category projection.

In this paper we examine a more general situation. Let 𝔄 be a category, and let ∂ be a conservative functor from 𝔄 to Cat. Suppose that the following two conditions are satisfied.

(i) For any object A of 𝔄 and any object a of A∂, the slice-category projection A∂↓a [figure] A∂ has a cartesian lifting A↓a [figure] A. This morphism is to be called the slice-object projection associated with A and a.

(ii) For any small category 𝔞 and any 𝔞-shaped diagram P_{( )} in 𝔄 mapped by ∂ to the slice-category diagram 𝔞↓^{( )}, the cocone 𝔞↓^{( )} [figure]𝔞 of slice-category projections has a cocartesian lifting P_{( )} [figure]A (or, equivalently, P_{( )} has a colimit that is respected by ∂).

We then call 𝔄 together with ∂ a conservative category with slicing. The reader may want to check at this point that Set^{𝔰^{op}} together with 𝔰↓^{( )} is an example indeed.

This work was compiled while the author was a Scott Russell Johnson Fellow at Macquarie University, Australia.

Received by the editors 2006-10-18 and, in revised form, 2009-04-12.

Transmitted by Walter Tholen. Published on 2009-04-23.

2000 Mathematics Subject Classification: 18D99.

Key words and phrases: slice categories, presheaf category, polytopic sets.

\begin{matrix}c \\ ◯ \end{matrix} Thorsten Palm, 2009. Permission to copy for private use granted.

Following the presheaf example we call an object A ∈ 𝔄 represented iff it comes equipped with a distinguished terminal object of A∂. We form the category 𝔄̌ of represented objects and all their morphisms in 𝔄. A rather direct consequence of the axioms is that the projection 𝔄̌ [figure] 𝔄 is dense. We can accordingly view 𝔄 as a full subcategory of Set𝔄̌^{op} (provided 𝔄 has small hom-sets).

The main theorem of this paper goes on to characterize the objects of 𝔄 among the presheaves on 𝔄̌. The statement involves the restriction X [figure] X_{⊤} of a presheaf X on 𝔄̌ to the all-object subcategory 𝔄̌_{⊤} whose morphisms are mapped by ∂ to functors respecting the distinguished terminal objects “on the nose”: X belongs to 𝔄 if and only if X_{⊤} is a small sum of representable presheaves on 𝔄̌_{⊤} whose universal elements are respected by the slice-object projections of 𝔄̌.

My first version of this theorem dealt with a single instance. In [5] I had introduced the notions of ‘polytopic set’ and of ‘dendrotopic set’, the former as a basis for the latter, and the latter as a replacement for the notion of ‘multitopic set’, which is central to M. Makkai’s approach to the subject of weak higher-dimensional categories. A replacement, that is, in the best possible sense: [5] and [2] together yield an equivalence between the two categories in question. The paper [3], which had introduced multitopic sets, had also shown that they form a presheaf category. Thus it was clear that dendrotopic sets form a presheaf category. I now wanted to capture the extent to which polytopic sets, in spite of all analogies, fall short of this ideal.

The proof I was pencilling down turned out to rely entirely on just a few properties. Thus an axiomatic approach suggested itself (ultimately leading to the present account). Once carried out, it brought the immediate boon that the result could easily be transferred to the many variants of polytopic sets, some of which appear more or less implicitly in [5], and the salient one of which is dendrotopic sets.

If 𝔄 = Poly Set, the category of polytopic sets, with ∂ understood to assign to each object its “face lattice”, then 𝔄̌ = Poly, the full subcategory of polytopes, and 𝔄̌_{⊤} = ∑_{n∈N} Poly_{n}, where Poly_{n} is the full subcategory of n-dimensional polytopes. An elementary combinatorial argument shows Poly_{n} to be essentially small, and so the size issue raised by the theorem in its general form can be disregarded here. The analogous statements hold true for 𝔄 = Dend Set, the category of dendrotopic sets. But a morphism between two dendrotopes of the same dimension is unique and invertible. Thus the conditions characterizing dendrotopic sets among the presheaves on the full subcategory of dendrotopes are automatically met. Along these lines we obtain what is probably the most direct proof of the fact that Dend Set is a presheaf category.

In the meantime Makkai wrote the paper [4], in one section of which he explores a theme similar to ours. The main difference is that his underlying concrete objects are not categories but mere sets.

The theorem applies even to situations where ∂ is not conservative. The precise requirements are more complicated: roughly, we add the new condition that the cocones arising by virtue of either one of the two old conditions arise for the other one as well. We then simply speak of a category with slicing. The primary non-conservative example was the category of all (small) category presentations. It includes many interesting conservative ones, such as Poly Set or the category of (upward) forests.

In view of the theorem we can recover the category 𝔄, as such, from the category 𝔄̌ and its subcategory 𝔄̌_{⊤}. Can we also recover its structure as a category with slicing? Yes, if we retain a structure on 𝔄̌ analogous to the one in question. This structure comes in the form of a functor to Čat, the category of small categories with designated terminal object and all functors between them. In order for an arbitrary category with a functor to Čat to occur as 𝔄̌ in this way, it is necessary and sufficient that it satisfy a single condition, namely (i) above. We call such a category a slicing site. A more abstract form of this answer will be presented as a subordinate theorem.

This paper is divided into five sections. The odd-numbered ones properly contain the bare logical necessities with regard to its central result: section 1 presents the axioms on a category with slicing, section 3 the main theorem and section 5 its proof. Section 2 and the first half of section 4 are devoted to examples of categories with slicing, and the remainder of section 4 treats slicing sites.

Before we start, a few conventions. We shall be dealing with two fairly distinct kinds of categories. On the one hand, categories as ordinary mathematical objects. They are small and of interest up to isomorphism; they are the objects of the large 1-category Cat. On the other hand, categories as metamathematical objects. They are large (that is, in general not small) and of interest up to equivalence; they are the objects of the “extra large” 2-category CAT. It seems desirable to keep the two apart notationally: we use lowercase letters for the first kind and upper-case letters for the second kind. This rule does not only apply to the categories themselves, but also to the functors between them and to the objects and morphisms they contain. Categories and functors take Fraktur type, objects and morphisms take the usual italic type. Inconsistencies may be feared when functors from a small category 𝔞 to a large category 𝔄 are concerned. In these situations, however, we speak of 𝔞-shaped diagrams in 𝔄 and use family notation (inasmuch as the letters denoting diagrams in 𝔄 are the same as the ones denoting objects in 𝔄, while the arguments appear as subscripts). By a morphism between diagrams we of course mean a natural transformation. Most of these rules will be proved by their exceptions, which will therefore not have to be pointed out.

1. The Axioms

Let 𝔞 be a category. Given an object a of 𝔞, we denote by 𝔞↓a the slice category of objects over a and by Δ_{a}^{𝔞} the associated projection 𝔞↓a [figure] 𝔞. The slice category has a terminal object (a, 1_{a}), which the projection maps to a. It moreover is universal with respect to these data: for any category 𝔟 with a terminal object b and any functor 𝔣 : 𝔟 [figure] 𝔞 with b · 𝔣 = a, there is a unique functor 𝔣^{⊤} : 𝔟 [figure] 𝔞↓a with b · 𝔣^{⊤} = (a, 1_{a}) and 𝔣^{⊤} · Δ_{a}^{𝔞} = 𝔣

[figure: ( 𝔟; 𝔞↓a; 𝔞; b; (a, 1_{a}); a ).; 𝔣^{⊤}; 𝔣; Δ_{a}^{𝔞}]

Thus, in the large category 1↓Cat of categories with base object, the full subcategory of categories with terminal base object is coreflective.

Any morphism α : a′ [figure]a of 𝔞 induces a functor 𝔞↓α : 𝔞↓a′ [figure]𝔞↓a, and we have 𝔞↓α · Δ_{a}^{𝔞} = Δ_{a′}^{𝔞}

[figure: ^{( 𝔞↓a′}; 𝔞↓a; 𝔞 ).; 𝔞↓α; Δ_{a′}^{𝔞}; Δ_{a}^{𝔞}]

If 𝔞 is small, we thus obtain an 𝔞-shaped diagram 𝔞↓^{( )} and a cocone Δ𝔞_{( )} : 𝔞↓^{( )} [figure]𝔞 in Cat. This cocone is in fact a universal one, that is: a colimit.

Now let 𝔣 : 𝔟 [figure]𝔞 be a functor. It induces for each object b of 𝔟 the slice functor 𝔟↓b [figure]𝔞↓(b · 𝔣), which we shall (not entirely satisfactorily) denote by 𝔣↓b, and we have 𝔣↓b · Δ_{b·𝔣}^{𝔞} = Δ_{b}^{𝔟} · 𝔣

[figure: ^{( 𝔟↓b}; 𝔞↓(b · 𝔣); 𝔟; 𝔞 ).; 𝔣↓b; Δ_{b·𝔣}^{𝔞}; Δ_{b}^{𝔟}; 𝔣]

In fact, using the universality of (𝔞↓(b · 𝔣), Δ_{b·𝔣}^{𝔞}) we can express this functor as 𝔣↓b = (Δ_{b}^{𝔟}·𝔣)^{⊤}, where the designated terminal object of 𝔟↓b is of course (b, 1_{b}). Also the equations 𝔣↓b′ · 𝔞↓(β · 𝔣) = 𝔟↓β · 𝔣↓b hold

[figure: ^{( 𝔟↓b′}; 𝔞↓(b′ · 𝔣); 𝔟↓b; 𝔞↓(b · 𝔣) ),; 𝔣↓b′; 𝔞↓(β·𝔣); 𝔟↓β; 𝔣↓b]

wherefore the 𝔣↓b form a morphism 𝔟↓^{( )} [figure] 𝔞↓(^{( )} · 𝔣) of 𝔟-shaped diagrams in Cat.

We now turn to categories over Cat to which the slice-category construction, along with its two universal properties, can be lifted. Thus we let 𝔄 be a category that comes equipped with a functor 𝔄 [figure] Cat, called the structural one and denoted by ∂, and we require that four conditions are satisfied. The first two in all their explicitness are as follows.

(Sl 1) Let A ∈ 𝔄 and 𝔞 ∈ Cat be two objects with (an isomorphism) 𝔲 : 𝔞 [figure: ≃] A∂. For any object a ∈ 𝔞, there are an object P_{a} ∈ 𝔄 with 𝔳_{a} : 𝔞↓a [figure: ≃] P_{a}∂ and a cartesian morphism D_{a} : P_{a} [figure] A with D_{a}∂ = 𝔳_{a}^{−1} · Δ_{a}^{𝔞} · 𝔲

[figure: ( 𝔄 ∋; ∈ Cat ).; •; 𝔞; •; A∂; •; 𝔞↓a; ∘; P_{a}∂; •; A; ∘; P_{a}; ≃; 𝔲; ≃; 𝔳_{a}; Δ_{a}^{𝔞}; D_{a}∂; D_{a}]

Cartesianness of D_{a} means that for any object Q ∈ 𝔄 and any two morphisms F : Q [figure]A and 𝔤 : Q∂ [figure]P_{a}∂ with 𝔤 · D_{a}∂ = F ∂, there is a unique morphism G : Q [figure] P_{a} with G · D_{a} = F and G∂ = 𝔤

[figure: ( 𝔄 ∋; ∈ Cat ).; •; A∂; •; Q∂; •; P_{a}∂; •; A; •; Q; •; P_{a}; 𝔤; D_{a}∂; F ∂; G; D_{a}; F]

(Sl 2) Let 𝔞 be a small category, and let P_{( )} be an 𝔞-shaped diagram in 𝔄 with 𝔳_{( )} : 𝔞↓^{( )} [figure: ≃]P_{( )}∂ and each P_{α} : P_{a′} [figure]P_{a} (α : a′ [figure]a ∈ 𝔞) cartesian. There are an object A in 𝔄 with 𝔲 : 𝔞 [figure: ≃]A∂ and a cocartesian cocone

D_{( )} : P_{( )} [figure] A with D_{( )}∂ = 𝔳−1_{( )} · Δ𝔞_{( )} · 𝔲

[figure: ( 𝔄 ∋; ∈ Cat ).; •; 𝔞; ∘; A∂; •; 𝔞↓^{( )}; •; P_{( )}∂; ∘; A; •; P_{( )}; ≃; 𝔲; ≃; 𝔳_{( )}; Δ_{( )}^{𝔞}; D_{( )}∂; D_{( )}]

Cocartesianness of D_{( )} means that for any object B ∈ 𝔄, any cocone F_{( )} : P_{( )} [figure]B and any morphism 𝔤 : A∂ [figure]B∂ with D_{( )}∂ · 𝔤 = F_{( )}, there is a unique morphism G : A [figure] B with D_{( )} · G = F_{( )} and G∂ = 𝔤

[figure: ( 𝔄 ∋; ∈ Cat ).; •; A∂; •; B∂; •; P_{( )}∂; •; A; •; B; •; P_{( )}; 𝔤; F_{( )}∂; D_{( )}∂; G; F_{( )}; D_{( )}]

We can bring these statements into a more digestible form by introducing the following conventions. Here, as on certain other occasions, we let 𝔄 live over an arbitrary base category ℑ, while we maintain the notation for our standard case ℑ = Cat. By a diagram A_{( )} in 𝔄 above a diagram 𝔞_{( )} in ℑ of the same shape let us mean one that comes equipped with an isomorphism 𝔞_{( )} ≃ A_{( )}∂. The definition specializes to the case of objects (shape 1), morphisms (shape 2) and so on. Now if, say, an object A above 𝔞 is already under consideration, where 𝔲 : 𝔞 [figure: ≃]A∂ is the implicit isomorphism, then a morphism F :

B [figure]A above 𝔣 : 𝔟 [figure]𝔞 is understood to have this very 𝔲 as the second constituent of its own implicit isomorphism.

Our two conditions can now be restated as follows. (Sl 1) For any small category 𝔞, any object A in 𝔄 above 𝔞 and an object a ∈ 𝔞,

there is a cartesian morphism to A above Δ_{a}^{𝔞} : 𝔞↓a [figure] 𝔞. (Sl 2) For any small category 𝔞 and any 𝔞-shaped diagram P_{( )} in 𝔄 above 𝔞↓^{( )},

there is a cocartesian cocone from P_{( )} above Δ𝔞_{( )} : 𝔞↓^{( )} [figure] 𝔞.

In a sense we can do better than just hide the obtrusive isomorphisms behind a word. Call a category 𝔄 over ℑ replete iff it “treats the objects of the base category as abstract”. By this we mean that for two objects A ∈ 𝔄 and 𝔟 ∈ ℑ and an isomorphism 𝔲 : 𝔟 [figure: ≃] A∂, there are always an object B ∈ 𝔄 with B∂ = 𝔟 and an isomorphism U : B [figure: ≃]A with U∂ = 𝔲. This lifting condition on isomorphisms of objects implies an analogous one on isomorphisms of diagrams. We conclude that a category replete over Cat satisfies (Sl 1) or (Sl 2) if and only if it satisfies the corresponding ‘strict’ condition, obtained by replacing ‘≃’ with ‘=’.

Any category over ℑ is equivalent as such to a replete one, for instance the “iso-comma” category of the structural functor and the identity of ℑ, while properties (Sl 1) and (Sl 2), as well as all further properties we give prominence to, are passed along equivalences over Cat. We can therefore assume all our abstract categories over Cat to be replete without losing generality; in fact we shall often do so tacitly.

A special kind of category over ℑ is a subcategory 𝔄 ⊆ ℑ, the structural functor being the inclusion. Here ‘replete’ has its standard meaning: if 𝔞 belongs to 𝔄, then so does every isomorphism 𝔟 [figure: ≃] 𝔞 of ℑ. We may occasionally want to replace an arbitrary category 𝔄 over ℑ with a replete subcategory equivalent over ℑ. This is possible if and only if the structural functor is faithful as well as full on isomorphisms, the latter statement meaning that for any two objects A and B of 𝔄, any isomorphism 𝔲 : B∂ [figure: ≃] A∂ in ℑ is the image U∂ of an isomorphism U : B [figure: ≃] A in 𝔄. (In fact, with the faithfulness condition in place there is no need to demand explicitly that U be invertible.)

A few comments on the notions of a cartesian morphism and, more so, a cartesian cone (of which the notion of a cocartesian cocone arises by dualization) may be due. The former is standard, being essential in the definition of ‘fibration’. The latter is a generalization (morphisms can be viewed as cones for 1-shaped diagrams) which suggests itself; not surprisingly it has already appeared elsewhere ([7]). There is no room here to praise their utility in full. What is relevant to us are the following facts.

• Cartesian morphisms are closed under composition and right division(^{1}).

• A cone above a universal one is cartesian if and only if it is universal itself. The second statement is immediately, up to dualization, related to axiom (Sl 2): we could have just as well required that D_{( )} be a colimit (except that this alternative formulation would be less “symmetric”). The 1-shaped case is the well-known fact that a morphism above an invertible one is cartesian if and only if it is invertible itself.

1When we say that a class of morphisms is closed under right division, we mean that with F and H ·F it also contains H.

The idea of lifting the two universal properties enjoyed by the slice-category construction would be implemented more accurately if we imposed the condition defining cartesianness in (Sl 1) only on situations in which Q∂ has a terminal object and F ∂ maps it to a (we are tacitly assuming repleteness), so that 𝔤 = F ∂^{⊤}. In fact, in this work the relevant part of axiom (Sl 1) will only ever be applied to these situations. I have forgone the modification thus suggested since on the one hand the added generality is spurious, as will follow from the previous sentence and the second proposition below, while on the other hand I have as yet been unable to find an instance for which the restricted cartesianness is any easier to verify than full cartesianness.

Axiom (Sl 1) invites us to put the following conventions into place. The object P_{a} and the cartesian morphism D_{a} : P_{a} [figure] A (which together are unique up to isomorphism) will be called, respectively, the slice object of objects over a and the associated projection. (While we are assuming that (Sl 1) holds as a whole, this definition may be applied whenever D_{a} and P_{a} exist for individual (A, a).) The notations P_{a} = A↓a and D_{a} = Δ_{a}^{A} suggest themselves. For any morphism α : a′ [figure]a of A∂, cartesianness of Δ_{a}^{A}, existence part, yields a morphism A↓α : A↓a′ [figure] A↓a above A∂↓α with A↓α · Δ_{a}^{A} = Δ_{a′}^{A}

[figure: ( 𝔄 ∋; ∈ Cat ).; •; A∂↓a′; •; A∂↓a; •; A∂; •; A↓a′; •; A↓a; •; A; A∂↓α; Δ_{a′}^{A∂}; Δ_{a}^{A∂}; A↓α; Δ_{a′}^{A}; Δ_{a}^{A}]

Since Δ_{a′}^{A} is cartesian as well, closedness under right division ensures that A↓α is. The uniqueness part of cartesianness guarantees that A↓^{( )} is an A∂-shaped diagram, so that ΔA_{( )} is a cocone A↓^{( )} [figure] A. Thus, applying (Sl 1) to all objects of 𝔞 establishes the premiss of (Sl 2).

Now let F : B [figure]A be a morphism of 𝔄. For any object b of B∂, cartesianness (existence part) of Δ_{b·F ∂}^{A} yields a morphism F ↓b : B↓b [figure]A↓(b · F ∂) above F ∂↓b with F ↓b · Δ_{b·F ∂}^{A} = Δ_{b}^{B} · F

[figure: ( 𝔄 ∋; ∈ Cat ).; •; B∂↓b; •; B∂; •; A∂↓(b·F ∂); •; A∂; •; B↓b; •; B; •; A↓(b·F ∂); •; A; F ∂↓b; Δ_{b·F ∂}^{A∂}; Δ_{b}^{B∂}; F ∂; F ↓b; Δ_{b·F ∂}^{A}; Δ_{b}^{B}; F]

Further, for any morphism β : b′ [figure]b of B∂, cartesianness (uniqueness part) of Δ_{b·F ∂}^{A} gives B↓β · F ↓b = F ↓b′ · A↓(β · F ∂).

Given an object A of 𝔄 as in (Sl 1), we can apply axiom (Sl 2) to the 𝔞-shaped diagram P_{( )} = A↓^{( )} of slice objects. Conversely, given an 𝔞-shaped diagram P_{( )} as in (Sl 2), we can apply (Sl 1) to the colimit object A. In both instances we are already presented with candidates for the required liftings; only the correct kind of universality may be lacking. Our final two axioms say that it must not. (Sl 3) In the situation of (Sl 2), each cocone constituent D_{a} : P_{a} [figure] A is cartesian. (Sl 4) In the situation of (Sl 1), the induced cocone D_{( )} : P_{( )} [figure] A from the slice-

object diagram P_{( )} = A↓^{( )} is cocartesian. A category 𝔄 over Cat satisfying (Sl 1), (Sl 2), (Sl 3) and (Sl 4) will be said to have slicing.

The cartesian morphisms and cocartesian cocones whose existence is required by (Sl 1) and (Sl 2) turn out to be essentially the same as those for which merely the respective property is required in (Sl 3) and (Sl 4). This insight allows us to streamline the verification of these axioms. Suppose that 𝔄 is a category over Cat satisfying (Sl 1) (so that a slice object is always available) and (Sl 4). For convenience suppose also that 𝔄 is replete. In order for 𝔄 to have slicing, it suffices (and is of course necessary) that for any small category 𝔞 and any 𝔞-shaped diagram P_{( )} in 𝔄 with each P_{α} cartesian and P_{( )}∂ = 𝔞↓^{( )}, there are an object A in 𝔄 with A∂ = 𝔞 and an isomorphism U_{( )} : P_{( )} [figure: ≃] A↓^{( )} of 𝔞-shaped diagrams with U_{( )}∂ = 1_{𝔞↓^{( )}}. Without the repleteness assumption, three more isomorphisms would enter this statement (replacing the equations P_{( )}∂ = 𝔞↓^{( )}, (A↓^{( )})∂ = A∂↓^{( )} and A∂ = 𝔞) and together occur in the final equation (replacing U_{( )}∂ = 1_{𝔞↓^{( )}}). The “dual” statement, having (Sl 2) and (Sl 3) as its suppositions, is also valid, but seems to be less useful.

My original intention was to work with the following two additional axioms (instead of (Sl 3) and (Sl 4)). (Sl 3′) Under the premiss of (Sl 1), all morphisms to A above each of the Δ_{a}^{𝔞} are

cartesian. (Sl 4′) Under the premiss of (Sl 2), all cocones from P_{( )} above Δ𝔞_{( )} are cocartesian. Their advantage is that they are meaningful irrespective of whether (Sl 1) and (Sl 2) are satisfied. Of course (Sl 3′) implies (Sl 3) and (Sl 4′) implies (Sl 4).

Let us call a category over an arbitrary base category conservative iff its structural functor is. As a consequence of the following proposition, a category 𝔄 over Cat satisfies (Sl 1), (Sl 2), (Sl 3′) and (Sl 4′) if and only if it has slicing and is conservative.

Proposition. For a category 𝔄 over Cat satisfying (Sl 1) and (Sl 2) the following three conditions are equivalent.

(a) 𝔄 is conservative.

(b) 𝔄 satisfies (Sl 4′).

(c) 𝔄 satisfies (Sl 3′) and (Sl 4).

Proof. Clearly if 𝔄 is conservative, then cartesianness or cocartesianness of one instance of D_{a} above Δ_{a}^{𝔞} as in (Sl 1) or D_{( )} above Δ𝔞_{( )} as in (Sl 2) carries over to all instances; thus (a) implies (b) and (since (Sl 4′) entails (Sl 4)) also (c). We are now going to show that under the assumption of either (b) or (c), 𝔄 is conservative. So let F : B [figure]A be a morphism in 𝔄 for which the functor F ∂ is invertible; we have to show that F itself is invertible.

First consider (b). Apply (Sl 1) to A to obtain a cocone ΔA_{( )} : A↓^{( )} [figure]A. Now by (Sl 4′) both the cocones ΔA_{( )} and ΔA_{( )} · F are cocartesian. It follows that the induced morphism F is invertible.

Now consider (c). We proceed in two steps.

First consider the case that A∂ has a terminal object a. Then Δ_{a}^{A∂} is an invertible functor, and hence so is 𝔳_{a} = Δ_{a}^{A∂} · F ∂^{−1}

[figure: ( 𝔄 ∋; ∈ Cat ).; •; A∂↓a; •; B∂; •; A∂; •; A∂; •; B; •; A; ≃; 𝔳_{a}; F ∂; Δ_{a}^{A∂}; =; F]

By (Sl 3′) F is cartesian. But a cartesian morphism above an isomorphism is itself an isomorphism.

We now turn to the general case. For each object b of B∂, the slice functor F ∂↓b : B∂↓b [figure] A∂↓(b · F ∂) is invertible, whence according to the previous paragraph so is the morphism F ↓b. Thus we have an invertible morphism F ↓^{( )} : B↓^{( )} [figure]A↓(^{( )} · F ∂) of A∂-shaped diagrams. By (Sl 4) the cocones ΔB_{( )} and, since F ∂ is invertible, Δ_{^{( )}·F ∂}^{A} are universal. We conclude that F is a colimit morphism of F ↓^{( )} and is hence invertible too.

Even for a conservative category with slicing the structural functor may fail to be faithful: see example 7 in the following section.

We now turn to another familiar notion that is important for this work. Recall that a functor 𝔣 : 𝔟 [figure]𝔞 is an (ordinary) discrete fibration if and only if all the slice functors 𝔣↓b : 𝔟↓b [figure] 𝔞↓(b · 𝔣) are invertible. We may take this statement as a definition.

Let 𝔄 be a category over Cat. We define a discrete fibration in 𝔄 to be a morphism that is cartesian above an ordinary discrete fibration. The following three facts regarding 𝔄 can easily be derived from the familiar corresponding facts regarding Cat.

• Discrete fibrations are closed under composition and right division.

• If B∂ has a terminal object, then a morphism F : B [figure] A is invertible if and only if it is a discrete fibration and F ∂ preserves terminality.

• Slice-object projections (where they exist) are discrete fibrations.

Many more facts on discrete fibrations carry over from Cat to categories with slicing. Two of them will be shown from scratch in example 3 of section 2 and the lemma of section 5. For now we deal with our characterization above.

Proposition. A morphism F : B [figure] A in a category with slicing is a discrete fibration if and only if all its slice morphisms F ↓b : B↓b [figure] A↓(b · F ∂) are invertible.

Proof. First let F be a discrete fibration. For each b ∈ B∂ we have F ↓b·Δ_{b·F ∂}^{A} = Δ_{b}^{B} ·F, and since F and the slice-object projections are discrete fibrations, so is the left factor F ↓b. Since (F ↓b)∂ also preserves terminality, F ↓b is invertible indeed.

Conversely let F have all its slice morphisms invertible; we are going to show that F is a discrete fibration. Since (F ↓b)∂ = F ∂↓b is invertible, the functor F ∂ is a discrete fibration. The major part of the proof will establish that F is cartesian.

Let C be an object, G : C [figure]A a morphism and 𝔥 : C∂ [figure]B∂ a functor with 𝔥 · F ∂ = G∂. We wish to show that there is a unique morphism H : C [figure] B above 𝔥 with H · F = G

[figure: ( 𝔄 ∋; ∈ Cat ).; •; A∂; •; B∂; •; C∂; •; A; •; B; •; C; 𝔥; F ∂; G∂; H; F; G]

Since F is a discrete fibration, the morphism F ↓(^{( )} · 𝔥) : B↓(^{( )} · 𝔥) [figure]A↓(^{( )} · G∂) of C∂-shaped diagrams is invertible. Now consider the cocone G↓^{( )} · (F ↓(^{( )} · 𝔥))^{−1} · Δ_{^{( )}·𝔥}^{B} : C↓^{( )} [figure] B, which lies above

G∂↓^{( )} · (F ∂↓(^{( )} · 𝔥))^{−1} · Δ_{^{( )}·𝔥}^{B∂} = 𝔥↓^{( )} · Δ_{^{( )}·𝔥}^{B∂} = ΔC∂_{( )} · 𝔥.

By (Sl 4) there is a unique morphism H : C [figure] B above 𝔥 with G↓^{( )}·(F ↓(^{( )}·𝔥))^{−1} ·Δ_{^{( )}·𝔥}^{B} =

ΔC_{( )} · H

[figure: ( 𝔄 ∋; ∈ Cat ).; •; C∂↓^{( )}; •; •; A∂↓(^{( )}·G∂); •; C∂; •; B∂; •; C↓^{( )}; •; B↓(^{( )}·𝔥); •; A↓(^{( )}·G∂); •; C; •; B; 𝔥↓^{( )}; F ∂↓(^{( )}·𝔥); ≃; G∂↓^{( )}; Δ_{( )}^{C∂}; 𝔥; Δ_{( )·𝔥}^{B∂}; F ↓(^{( )}·𝔥); ≃; G↓^{( )}; Δ_{( )}^{C}; H; Δ_{( )·𝔥}^{B}]

Thus ΔC_{( )} · H · F = G↓^{( )} · (F ↓(^{( )} · 𝔥))^{−1} · Δ_{^{( )}·𝔥}^{B} · F = G↓^{( )} · Δ_{^{( )}·G∂}^{A} = ΔC_{( )} · G, whence by

(Sl 4) again it follows that indeed H · F = G. Conversely, given a morphism H′ : C [figure] B

above 𝔥 with H′·F = G, we have H′↓^{( )}·F ↓(^{( )}·𝔥) = G↓^{( )} and thus ΔC_{( )}·H′ = H′↓^{( )}·Δ_{^{( )}·𝔥}^{B} =

G↓^{( )} · (F ↓(^{( )} · 𝔥))^{−1} · Δ_{^{( )}·𝔥}^{B}, whence by uniqueness of H we get H′ = H.

Suppose now that 𝔄 is a conservative category with slicing. The proposition makes clear that a morphism in 𝔄 is a discrete fibration if and only if its underlying functor is; in other words, a morphism above a discrete fibration is automatically cartesian. The converse of this statement is false: see example 10.

2. Examples

The following list of examples (some of them being general constructions) should convince the reader that categories with slicing abound. The foremost example mentioned in the introduction appears at the end of this section. The list will be continued in section 4, where there is also further discussion of some of the items presented here.

Example 1. Cat, together with the identity functor, is a conservative category with slicing.

Example 2. If 𝔄 is a category with slicing, its all-object subcategory 𝔄_{cart} of cartesian morphisms is a conservative category with slicing.

Proof. Since cartesian morphisms are closed under right division, all morphisms in 𝔄_{cart} remain cartesian there. As an immediate consequence, 𝔄_{cart} is conservative. Since the slice-object projections are in 𝔄_{cart}, we also have (Sl 1) right away. In order to see that (Sl 2) carries over in the same fashion, we start by noting that by (Sl 3) the constituents of the cocone in question do indeed belong to 𝔄_{cart}. What is left to be proved is that a morphism F : B [figure] A in 𝔄 with each Δ_{b}^{B} · F : B↓b [figure] A cartesian is so itself.

So let C ∈ 𝔄, G : C [figure] A and 𝔥 : C∂ [figure] B∂ with 𝔥 · F ∂ = G∂; we wish to show that there is a unique H : C [figure]B above 𝔥 with H · F = G. For each c ∈ C∂, the functor 𝔥↓c : C∂↓c [figure] B∂↓(c · 𝔥) satisfies 𝔥↓c · (Δ_{c·𝔥}^{B} · F)∂ = (Δ_{c}^{C} · G)∂ and can hence uniquely be lifted to S_{c} : C↓c [figure] B↓(c · 𝔥) with S_{c} · Δ_{c·𝔥}^{B} · F = Δ_{c}^{C} · G

[figure: ( 𝔄 ∋; ∈ Cat ).; •; C∂↓c; •; C∂; •; B∂↓(c·𝔥); •; B∂; •; A∂; •; C↓c; •; C; •; B↓(c·𝔥); •; B; •; A; 𝔥; Δ_{c}^{C∂}; G∂; 𝔥↓c; Δ_{c·𝔥}^{B∂}; F ∂; Δ_{c}^{C}; G; S_{c}; Δ_{c·𝔥}^{B}; F; ∈𝔄_{cart}]

Clearly S_{( )} · Δ_{^{( )}·𝔥}^{B} is a cocone and therefore induces H : C [figure] B above 𝔥 with ΔC_{( )} · H =

S_{( )} ·Δ_{^{( )}·𝔥}^{B}. Now ΔC_{( )} ·H ·F = S_{( )} ·Δ_{^{( )}·𝔥}^{B}·F = ΔC_{( )} ·G, from which we can conclude H ·F = G.

Thus we have shown existence of an H as required; uniqueness is established by following the argument backwards.

Example 3. If 𝔄 is a category with slicing, its all-object subcategory 𝔄_{difi} of discrete fibrations is a conservative category with slicing.

Proof. We can copy the first paragraph from the previous proof, replacing ‘cartesian morphism’, modulo grammatical variations, with ‘discrete fibration’. What remains to be shown is that a morphism F : B [figure] A for which all the Δ_{b}^{B} · F are discrete fibrations is one itself. Now Δ_{b}^{B} · F = F ↓b · Δ_{b·F ∂}^{A}, so the left factor F ↓b is a discrete fibration. As it preserves terminality as well, it is invertible as required.

Example 4. Let 𝔄 be a category with slicing, and let T be an object of 𝔄. The slice category 𝔄↓T, together with the functor Δ_{T}^{𝔄}∂, has slicing. If 𝔄 is conservative, so is 𝔄↓T.

Proof. The slice-category projection Δ_{T}^{𝔄} is conservative, hence the second statement. It creates (in the obvious sense) cartesian morphisms and cocartesian cocones, hence the first statement.

Example 5. Fix a set X. By an X-colouring of a category 𝔞 we mean a map assigning to each object of 𝔞 an element (“colour”) of X. The category of X-coloured categories and colour-preserving functors, together with the “decolourization” functor, is conservative and has slicing.

Proof. View X as a category by giving it the chaotic preorder; then the category in question is isomorphic over Cat to Cat↓X. Now apply examples 1 and 4.

We mention this example explicitly since it will be referred to in the following section. It by the bye illustrates our treatment of small categories as objects of a one-dimensional category, ignoring their natural transformations.

Example 6. Let 𝔨 be a small category. The category Set^{𝔨^{op}} of left 𝔨-sets X, together with the category-of-elements functor X [figure] 𝔨↓X, is conservative and has slicing.

Proof. It is well known that we have an equivalence Set^{𝔨^{op}} [figure: ≈]Cat_{difi}↓𝔨 over Cat, mapping a left 𝔨-set X to the category of elements 𝔨↓X, along with the associated projection. Now apply examples 1, 3 and 4.

This example can be made work without the smallness assumption on 𝔨. To this end we have to replace Set^{𝔨^{op}} with the full subcategory of those left 𝔨-sets that have small categories of elements. Of course the proof will have to be adjusted.

Example 7. Let 𝔎 be a category. We denote by 𝔎⟶ Fam the category of (small) families in 𝔎. An object of 𝔎⟶ Fam consists of a small set X and an X-indexed family ( K_{x} |x ∈ X) = K of objects K_{x} ∈ 𝔎. A morphism (X, K) [figure](Y, L) of 𝔎⟶ Fam consists of a map φ : X [figure] Y and an X-indexed family ( U_{x} | x ∈ X) = U of morphisms U_{x} : K_{x} [figure] L_{x·φ}. We have an embedding 𝔎 [figure] 𝔎⟶ Fam, K [figure] ({∗}, K), where on the right-hand side K ∈ 𝔎 is viewed as the singleton-indexed family with itself as the only member, and we have a projection 𝔎⟶ Fam [figure]Set, (X, K) [figure]X. The composite of the projection and the discrete-category embedding Set [figure] Cat makes 𝔎⟶ Fam a category over Cat. The category 𝔎⟶ Fam, together with this composite, has slicing. It is conservative if and only if 𝔎 is a groupoid.

Proof. It is easy to check that a morphism (ψ, W) : (Y, L) [figure](Z, M) is cartesian if and only if each W_{y} : L_{y} [figure]M_{y·ψ} is invertible in 𝔎. So if 𝔎 is a groupoid, then every morphism of 𝔎⟶ Fam is cartesian, and hence 𝔎⟶ Fam is conservative. Conversely, a non-invertible morphism U : K [figure]L in 𝔎 gives rise to a non-invertible morphism (1_{{∗}}, U) : ({∗}, K) [figure] ({∗}, L) above 1_{{∗}}.

Now let (X, K) ∈ 𝔎⟶ Fam. Since (X, K)∂ = X is discrete, each slice category (X, K)∂↓x is a singleton, while the associated projection Δ_{x}^{(X,K)∂} is the element x, interpreted as a map. Taking (X, K)↓x = ({∗}, K_{x}) and Δ_{x}^{(X,K)} = (x, 1_{K_{x}}), we verify (Sl 1). As for (Sl 4), we should have to confirm that these Δ_{x}^{(X,K)} exhibit (X, K) as a sum ∑_{x∈X}({∗}, K_{x}) in 𝔎⟶ Fam. But that they do is a well-known property of the ⟶ Fam-construction. Finally, let 𝔞 be a small category, and let (X^{( )}, K^{( )}) be an 𝔞-shaped diagram in 𝔎⟶ Fam with X^{( )} = (X^{( )}, K^{( )})∂ isomorphic to 𝔞↓^{( )}. Since each category 𝔞↓a ≃ X^{a} is discrete, so must be 𝔞. On the other hand, the set X^{a} ≃ 𝔞↓a must be a singleton: X^{a} = {∗} and K^{a} ∈ 𝔎. Starting the process described before with the object (𝔞, ( K^{a} | a ∈ 𝔞)) of 𝔎⟶ Fam, we clearly obtain a slice-object diagram isomorphic to (X^{( )}, K^{( )}). This shows (Sl 2) and (Sl 3).

If we take 𝔎 to have a hom-set with more than one element, the functor ∂ : 𝔎⟶ Fam [figure] Cat will not be faithful. If we take 𝔎 to have a non-small hom-set, the category 𝔎⟶ Fam will have one as well. All the while 𝔎 can be a groupoid. Thus neither faithfulness of the structural functor nor even smallness of hom-sets is necessary for a conservative category over Cat to have slicing.

Example 8. Let 𝔎 be a category. We consider 𝔎⟵ Dg^{op}, the opposite of the “projective diagram category” of 𝔎. An object of 𝔎⟵ Dg^{op} consists of a small category 𝔞 and an 𝔞shaped diagram K_{( )} = K in 𝔎. A morphism (𝔟, L) [figure](𝔞, K) of 𝔎⟵ Dg^{op} consists of a functor 𝔣 : 𝔟 [figure] 𝔞 and a morphism U_{( )} = U : K_{𝔣} [figure] L of 𝔟-shaped diagrams in 𝔎; these data are summarized in the picture

[figure: 𝔟; 𝔞; 𝔎.; 𝔣; K; L; U]

All the fixed-shape diagram categories 𝔎^{𝔞} are included contravariantly in 𝔎⟵ Dg^{op}, while we have a covariant projection to Cat. The category 𝔎⟵ Dg^{op}, together with this projection, has slicing. It is conservative if and only if 𝔎 is a groupoid.

Proof. Clearly a morphism (𝔣, U) is cartesian if and only if (each constituent of) U is invertible. The validity of the second statement follows.

Let (𝔞, K) be an object of 𝔎⟵ Dg^{op}, and let a be an object of (𝔞, K)∂ = 𝔞. Above Δ_{a}^{𝔞} : 𝔞↓a [figure]𝔞 we have a cartesian morphism (Δ_{a}^{𝔞}, 1_{K_{Δ^{𝔞}_{a}}}) : (𝔞↓a, K_{Δ_{a}^{𝔞}}) [figure](𝔞, K). This settles (Sl 1). We now wish to show that the collection of these morphisms constitutes a cocartesian cocone. So let 𝔣^{∗} : 𝔞 [figure] 𝔟 be a functor, and let (𝔣^{( )}, U^{( )}) : (𝔞↓^{( )}, K_{Δ_{( )}^{𝔞}}) [figure] (𝔟, L) be a cocone above 𝔣^{( )} = Δ𝔞_{( )} · 𝔣^{∗}. Each morphism

[figure: 𝔞↓a; 𝔞; 𝔟; 𝔎; Δ_{a}^{𝔞}; K; 𝔣^{a}; L; U^{a}]

of (𝔞↓a)-shaped diagrams in 𝔎 amounts to an (𝔞↓a)-shaped diagram U^{a} : 𝔞↓a [figure]𝔎^{2} in the morphism category of 𝔎, and as such they together form a cocone U^{( )} : 𝔞↓^{( )} [figure]𝔎^{2} in CAT. Since Δ𝔞_{( )} is universal, there is a unique diagram U^{∗} : 𝔞 [figure] 𝔎^{2} with U_{Δ_{( )}^{𝔞}}^{∗} = U^{( )}, which in turn amounts to a diagram morphism

[figure: 𝔞; 𝔟; 𝔎.; 𝔣^{∗}; L; K; U^{∗}]

with (Δ𝔞_{( )}, 1_{K_{Δ{𝔞 \atop ( )}}}) · (𝔣^{∗}, U^{∗}) = (𝔣^{( )}, U^{( )}). This settles (Sl 4).

In settling (Sl 2) and (Sl 3) we use the repleteness of 𝔎⟵ Dg^{op} for convenience. Thus let (𝔞↓^{( )}, K^{( )}) be a diagram strictly above 𝔞↓^{( )}, with each (𝔞↓f, K^{f}) : (𝔞↓b, K^{b}) [figure] (𝔞↓a, K^{a}) cartesian, that is, with K_{(c,h)}^{f} : K_{(c,g)}^{a} [figure]K_{(c,h)}^{b} invertible for each commutative triangle

[figure: c; b; a; h; g; f] in 𝔞. Now put K_{a}^{∗} = K_{(a,1_{a})}^{a} and K_{f}^{∗} = (K_{(b,1_{b})}^{f})^{−1} · K_{f}^{a}, the latter being visualized

by the picture

[figure: K_{(b,1_{b})}^{b} = K_{b}^{∗}; K_{(b,f)}^{a}; K_{a}^{∗} = K_{(a,1_{a})}^{a}.; K_{(b,1_{b})}^{f}; ≃; K_{f}^{a}]

Clearly K_{1_{a}}^{∗} = 1_{K_{a}^{∗}} and, taking into account the commutativity of

[figure: K_{(c,h)}^{b}; K_{(c,g)}^{a}; K_{(b,f)}^{a}; K_{(b,1_{b})}^{b},; K_{(c,h)}^{f}; K_{h}^{b}; K_{h}^{a}; K_{(b,1_{b})}^{f}]

K_{h}^{∗}·K_{f}^{∗} = K_{h∘f=g}^{∗}. Thus we have obtained an 𝔞-shaped diagram K^{∗} in 𝔎, which amounts to an object (𝔞, K^{∗}) strictly above 𝔞 in 𝔎⟵ Dg^{op}. For each a ∈ 𝔞 the slice object (𝔞, K^{∗})↓a = (𝔞↓a, K_{Δ_{a}^{𝔞}}^{∗}) is isomorphic to (𝔞↓a, K^{a}) strictly above the identity of 𝔞↓a via (b, f) [figure]

K_{(b,1_{b})}^{f} : K_{(b,f)}^{a} [figure: ≃]K_{(b,1_{b})}^{b} = K_{(b,f)·Δ_{a}^{𝔞}}^{∗}, and the family of these isomorphisms is clearly natural in a ∈ 𝔞.

This proof can be reassembled in a more conceptual manner. The last part of what we have done here establishes en passant the rather well known fact that Δ𝔞_{( )} : 𝔞↓^{( )} [figure] 𝔞, in addition to being a colimiting cocone in Cat, is also a bicolimiting cocone in CAT. We shall revisit this idea in section 4.

If we take 𝔨 or 𝔎 in any of the previous three examples to be empty, we obtain a trivial category with slicing: a category equivalent to 1 with a structural functor that is constant with value 0. At this point it should be mentioned that by (Sl 2) a category with slicing must have an initial object O with O∂ = 0, while by (Sl 4) every object O with O∂ = 0 must be initial. From these two facts it follows that a category with slicing whose structural functor is constant is automatically trivial.

We are now starting to close in on our motivating example. To aid the reader’s comprehension we develop in parallel one that is to some extent similar, but more familiar.

Example 9. The category Grph of (directed) graphs, together with the ‘paths’ functor Grph [figure] Cat (left adjoint to the forgetful one), is conservative and has slicing.

Proof. The ‘paths’ functor is faithful and full on isomorphisms. Indeed, the structure of a graph A can be recovered from the structure of its category A∂ of vertices and paths: the arrows of A are the indecomposable morphisms of A∂. In this manner the structure of A∂ also determines the length function of A. Functors corresponding to morphisms in Grph are those that preserve indecomposability and hence also length.

For A a graph and a ∈ A∂ (that is, a a vertex in A), we can take A↓a to be the evident graph whose vertices are paths in A ending in a, and Δ_{a}^{A} to be the evident graph morphism assigning to each such path its origin. The Δ_{a}^{A} are cartesian, as in fact are all morphisms of Grph: length preservation is closed under right division. Thus we have (Sl 1). As Grph is small cocomplete and ∂ is small cocontinuous, we also have (Sl 2).

Example 10. A graph is called reflexive iff it comes equipped with a map associating with each vertex a loop about it. These loops, along with the paths in which they occur, will be called degenerate. A morphism between reflexive graphs is demanded to preserve degeneracy. The category Refl Grph of reflexive graphs, together with the ‘non-degenerate paths’ functor Refl Grph [figure]Cat (left adjoint to the forgetful one), is conservative and has slicing.

Proof. We can argue as in the previous proof, with one important difference. In the present case the functors B∂ [figure] A∂ corresponding to morphisms B [figure] A are those that do not increase (but not necessarily preserve) length. But Δ_{a}^{A} still preserves length, and this property is sufficient for cartesianness: if 𝔣 preserves length and 𝔥 · 𝔣 does not increase length, then neither does 𝔥.

This example shows that it is not necessary for a conservative category with slicing to have all its morphisms be cartesian. In Refl Grph a morphism is cartesian if and only if it maps none of two consecutive non-degenerate arrows (or, put positively, only degenerate arrows and arrows from a “source” to a “sink”) to a degenerate one. (The honestly degeneracy-reflecting morphisms, corresponding to the length-preserving functors, form an all-object subcategory of Refl Grph_{cart} equivalent to Grph over Cat.)

Example 11. We take an undirected graph to be an ordinary (directed!) graph together with a direction-reversing involution fixing each vertex but no arrow. Thus, each arrow u : a′ [figure]a has an inverse u^{∗} : a [figure]a′ with u^{∗} ≠ u (if a = a′) and u^{∗∗} = u. An arrow from a′ to a and its inverse, no matter in which order, together form an edge with extremities a and a′. Given a (directed) path in an undirected graph, we call two successive occurrences of an arrow and its inverse a degeneracy. Non-degenerate paths are composed by first concatenating them as usual and then “cancelling out” the degeneracies that have arisen about the joint. In this way vertices and non-degenerate paths form a category (in fact, a free groupoid). Moreover, the assignment of this category to an undirected graph is functorial. The category Undir Grph of undirected graphs, together with the ‘non-degenerate paths’ functor Undir Grph [figure] Cat, is conservative and has slicing.

While forgoing the actual proof, we mention the complications it bears in comparison to the previous two. Firstly, the structural functor is not full on isomorphisms (free groupoids in general have many “bases”), and therefore Undir Grph is not equivalent over Cat to a replete subcategory. (The functor is, however, conservative, faithful and injective on isomorphism classes.) Secondly, the category Undir Grph is not small cocomplete, so that the verification of (Sl 2) requires a closer inspection of the diagrams in question.

The second complication would disappear if we dropped the condition u^{∗} ≠ u in the definition of an undirected graph. A loop u with u^{∗} = u would be considered degenerate and having a single extremity (rather than the same extremity twice). The resulting category over Cat has slicing as well. As a mere category it is small cocomplete (in fact, it is the small-cocompletion of Undir Grph), while its structural functor is left adjoint.

Example 12. The concept of a category presentation should be familiar, at least as a practical tool, but maybe less so as the subject of theoretical studies. In making it the latter, we first have to say what exactly the term is to mean.

The definition most authoritative for category theorists takes a category presentation to be a “computad” in Street’s original sense (that is, 2-dimensional). However, to accommodate a certain purpose we shall instead consider computads carrying an additional structure making the hom-graphs undirected in the sense of example 11 (that is, we want the relators to be symmetric). We henceforth use the term ‘category presentation’, or ‘presentation’ for short, for the latter notion. The reader will find that the undirectedness has little bearing on this example itself. In fact, practically any reasonable notion of ‘category presentation’ will analogously give rise to a category with slicing.

Let us state our definition more explicitly. A presentation A consists of objects forming a set A_{0}; generators that are the arrows of a graph A_{01} whose vertices are the objects; and relators that are the edges of an undirected graph A_{12} = ∑_{a,b∈A_{0}} A(b, a), where the vertices of A(b, a) are the paths from b to a in A_{01}. The relators should be thought of as equations to be enforced; its extremities are therefore called its sides. A relator can be pictured

[figure: •; •; •; •; ||·; •; •; •; •],

where in this case both sides have length 2. Presentations and their morphisms form a large category Cat Pres.

To a presentation A we assign another presentation Ã as follows. The object–generator graph of Ã is the same as for A, while a relator (for generator paths) from b to a in Ã consists of two objects b′ and a′, two generator paths, one from b to b′, one from a′ to a, and a relator from b′ to a′. From the perspective of A this may look as follows:

[figure: •; •; •; •; ||·; •; •; •; •; •; •; •; •; •; •; •; b; b′; a; a′] .

Note that Ã naturally becomes a category enriched in (Undir Grph, ⊗), where ⊗ is geometric multiplication. Applying the strongly monoidal ‘components’ functor π_{0} : (Undir Grph, ⊗) [figure](Set, ×) to the hom-objects of Ã, an ordinary category Aτ_{1} arises. (Its objects are those of A, while the morphisms from b to a are the components of the undirected graph Ã(b, a).) This category is of course the one presented by A. The assignment A [figure] Aτ_{1} can be naturally extended to become a functor τ_{1} : Cat Pres [figure] Cat. The category Cat Pres, together with the functor τ_{1} (which is far from being conservative), has slicing.

Sketch of proof. The key step is to characterize the discrete fibrations of Cat Pres. They turn out to be precisely those morphisms F : B [figure] A satisfying the following two conditions.

• For each object b of B and each generator u : a′ [figure]b · F in A, there is a unique generator v : b′ [figure] b in B with v · F = u.

• For each two generator paths \underline{v}, \underline{v}′ : b′ [figure] b in B and each relator r : \underline{v}′ · F =^{!} \underline{v} · F

in A, there is a unique relator s : \underline{v}′ =^{!} \underline{v} in B with s · F = r. The remaining task is routine. Given a presentation A and an object a of A, the slice presentation A↓a has objects those of the slice category Aτ_{1}↓a, while the generators and relators from (c, g) to (b, f) in A↓a are those generators and relators from c to b in A representing morphisms h : c [figure]b with h ∘ f = g. Given a category 𝔞 and an 𝔞-shaped diagram P_{( )} in Cat Pres with P_{( )}τ_{1} ≃ 𝔞↓^{( )}, we obtain an associated presentation of 𝔞 by using as generators and relators to a ∈ 𝔞 those to the object corresponding to (a, 1_{a}) ∈ 𝔞↓a in P_{a}.

Example 13. A propolytopic set(^{2}) is a category presentation with the following two properties.

• Each path occurring as a side of a relator has length 2.

• Each path of length 2 occurs as a side of a relator precisely once. Put more concisely, the ‘side’ relation is a two-to-one correspondence between length-2 paths of generators on the one hand and relators on the other hand. A propolytopic map is a presentation morphism between propolytopic sets. The category Propoly Set of propolytopic sets and maps, together with the functor _{Propoly Set} ↿ τ_{1}, is conservative and has slicing.

Sketch of proof. This is another example that has many relevant features in common with number 9 (in fact, more than number 10). First one notices that by considering indecomposable morphisms one can recover a propolytopic set from the abstract category it presents. From here one deduces that the functor _{Propoly Set} ↿ τ_{1} is faithful, full on isomorphisms and, therefore, conservative. It remains to show that the category Propoly Set over Cat has slicing. As it is a full subcategory of Cat Pres over Cat, which we know to have slicing, we only have to check that its object class is closed with respect to the operations given by (Sl 1) and (Sl 2). This is easily done: focus on the generator paths and relators terminating in a given object.

2In [5] I introduced a slightly different notion under this name. There, all propolytopic sets are “graded” and “finitary”. The reader, especially after skimming through the relevant part of section 4, will find no difficulties in showing that the propolytopic sets with any given selection of these two attributes form a category with slicing.

Example 14. Let 𝔄 be a conservative category with slicing. Let Θ be an object of 𝔄 for which Θ∂ is a singleton category and which has no non-trivial automorphisms (and hence, by conservativeness, no non-trivial endomorphisms altogether). We consider the following subcategory 𝔄_{Θ} of 𝔄. Objects are those A for which A∂ has an initial object ⊥_{A} with A↓⊥_{A} isomorphic to Θ. Then ⊥_{A} is the only object of A∂ to which there is no non-trivial morphism; the uniqueness is expressed in the notation. Morphisms B [figure]A are those F for which F ∂ maps ⊥_{B} to ⊥_{A} and all other objects of B∂ to other objects of A∂ (so that the fibre over ⊥_{A} is the singleton category consisting of ⊥_{B}). This can be expressed differently by saying that F ∂ creates initiality. Note that Θ is an initial object in 𝔄_{Θ}.

Taking 𝔄 = Cat (example 1) and Θ = 1, we obtain a subcategory Cat_{1} of Cat. As a mere category, Cat_{1} is equivalent to Cat: the functor Cat [figure]Cat_{1}, 𝔞 [figure]𝔞^{+}, which to each object of Cat freely adjoins an initial object ⊥_{𝔞^{+}}, has as an up-to-isomorphism inverse the functor Cat_{1} [figure] Cat, 𝔟 [figure] 𝔟^{−}, which from each object of Cat_{1} extracts the full subcategory of non-initial objects. Moreover, both these functors commute in an obvious manner with the slice-category construction.

Now back to the general situation. The functor ∂ : 𝔄 [figure] Cat maps the subcategory 𝔄_{Θ} into the subcategory Cat_{1}, so that we can form the composite ∂^{−} : 𝔄_{Θ} [figure] Cat_{1} [figure] Cat. The category 𝔄_{Θ}, together with the functor ∂^{−}, is conservative and has slicing.

Proof. Conservativeness of ∂ : 𝔄 [figure]Cat carries over to ∂ : 𝔄_{Θ} [figure]Cat_{1}, and ^{( )}^{−} : Cat_{1} [figure] Cat is an equivalence. Thus (𝔄_{Θ}, ∂^{−}) is conservative.

Let A be an object of 𝔄_{Θ}, and let a be an object of A∂^{−}. The slice object A↓a in 𝔄 belongs to 𝔄_{Θ}, namely with ⊥_{A↓a} = (⊥_{A}, a · ¡_{A}), where a · ¡_{A} is the unique morphism ⊥_{A} [figure]a in A∂. Also the associated projection Δ_{a}^{A} belongs to 𝔄_{Θ}. Functors creating initiality are closed under right division, whence all morphisms of 𝔄_{Θ} cartesian in 𝔄 are also cartesian in 𝔄_{Θ}; and in particular so is Δ_{a}^{A}. This settles (Sl 1).

Now let 𝔞 be a small category, and let P_{( )} be an 𝔞-shaped diagram in 𝔄_{Θ} with P_{( )}∂^{−} ≃ 𝔞↓^{( )}. Since Θ is initial in 𝔄_{Θ}, there is a unique extension of P_{( )} to an 𝔞^{+}-shaped diagram P̂_{( )} with P̂_{⊥_{𝔞^{+}}} = Θ. By commutation of ^{( )}^{+} with the slice-category construction we have P̂_{( )}∂ ≃ 𝔞^{+}↓^{( )}, and by conservativeness of (𝔄, ∂) all the morphisms P̂_{α} : P̂_{a′} [figure] P̂_{a}

(α : a′  [figure]a ∈ 𝔞^{+}) are cartesian there. So in 𝔄 there is a colimit D̂_{( )} : P̂_{( )}  [figure]A
with D̂_{( )}∂ ≃ Δ𝔞^{+}_{( )} : 𝔞^{+}↓^{( )}  [figure]𝔞^{+}. Its restriction D_{( )} : P_{( )}  [figure]A is a cocone in 𝔄_{Θ}

with D_{( )}∂^{−} ≃ Δ𝔞_{( )}. All that remains to be shown is that D_{( )} is a colimit in 𝔄_{Θ}. So consider an arbitrary 𝔞-shaped cocone F_{( )} : P_{( )} [figure]B in 𝔄_{Θ}. It has a unique extension to an 𝔞^{+}-shaped cocone F̂_{( )} : P̂_{( )} [figure]B. Clearly a morphism G : A [figure]B in 𝔄_{Θ} that satisfies D_{( )} · G = F_{( )} also satisfies D̂_{( )} · G = F̂_{( )}. Conversely, a morphism G : A [figure]B in 𝔄 that satisfies D̂_{( )} · G = F̂_{( )} belongs to 𝔄_{Θ}: since F̂_{a} belongs to 𝔄_{Θ}, the object a · G∂ = (a, 1_{a}) · D̂_{a}∂ · G∂ = (a, 1_{a}) · F̂_{a}∂ of B∂ is ⊥_{B} if a = ⊥_{A}, otherwise ≠ ⊥_{B}. From here it is obvious that (Sl 2) holds.

Example 15. An (upward) forest is a graph with a distinguished set of vertices, called its roots, having the property that for each vertex a there is precisely one path from a root to a. Note that the set of roots is determined by the mere graph as the set of “sources”: vertices without incoming arrows. A tree is a forest with precisely one root. A morphism between forests (or trees) is a graph morphism respecting roots. We thus have a category Frst of forests and a category Tree of trees. It turns out that the two are equivalent: the functor Frst [figure] Tree adjoining to each forest a new vertex, along with one arrow to each (then former) root, and the functor Tree [figure] Frst removing from each tree the root, along with all its outgoing arrows, are up-to-isomorphism inverses of each other. The category Frst of forests, together with the restricted ‘paths’ functor Frst [figure]Cat, is conservative and has slicing.

Proof. Use examples 9 and 14: take Θ to be the graph with one vertex and no arrow; then Grph_{Θ} = Tree as subcategories of Grph, and via the said equivalence Grph_{Θ} ≈ Frst over Cat.

Note that we did not require explicitly that a tree morphism map non-roots to nonroots: it does so automatically. The situation is different when we develop the analogous notions in the presence of degeneracies, as we (partially) do in the next example.

Example 16. A reflexive (upward) forest is a reflexive graph with a distinguished set of vertices, called its roots, such that each vertex can be reached via a unique non-degenerate path starting at a root. A morphism of reflexive forests is a morphism of reflexive graphs respecting roots. The category Refl Frst of reflexive forests, together with the restricted ‘non-degenerate paths’ functor Refl Frst [figure] Cat, is conservative and has slicing.

Proof. Use examples 10 and 14, taking Θ to be the graph with one vertex and only the associated degenerate arrow.

We have finally arrived at the motivating example itself.

Example 17. An augmented polytopic set is a propolytopic set with an object ⊥ initial in the presented category.(^{3}) An augmented polytopic map is a propolytopic map between augmented polytopic sets respecting ⊥. A plain polytopic set is obtained from an augmented polytopic set by removal of ⊥ along with the generators and relators originating there. A plain polytopic map is obtained from an augmented one by restricting domain and range accordingly. From the structure of a plain polytopic set one can recover the structure of the augmented polytopic set that has given rise to it, namely by adding the following: one object ⊥; one generator from ⊥ to each vertex, that is, object that was not the target of any generator; relators in the only possible way, which makes one from ⊥ to each edge. We have thus constructed up-to-isomorphism inverses between the category Aug Poly Set of augmented polytopic sets and maps and the category Pln Poly Set of plain polytopic sets and maps. The category Pln Poly Set, together with the functor Pln Poly Set ↿ τ_{1}, is conservative and has slicing.

3A more practical characterization of augmented polytopic sets has as its crucial condition the connectedness of all dual graphs except the one for the initial object itself. See [5] for a treatment of the graded case. (A grading is often naturally present, and the presence of an initial object implies the presence of a grading.)

Proof. Apply examples 13 and 14: take Θ to be the propolytopic set with one object and no generator (and therefore no relator); then Propoly Set_{Θ} = Aug Poly Set as mere categories, while the said equivalence gives Propoly Set_{Θ} ≈ Pln Poly Set over Cat.

3. The Main Theorem

Let 𝔄 be a category with slicing. Following example 6 we may call an object A ∈ 𝔄 representable iff A∂ has a terminal object, which itself we may call a universal element or a representation of A. We consider the category 𝔄̌ described as follows. An object P of 𝔄̌ is an object P 𝔍 of 𝔄 together with a terminal object ⊤_{P} of P 𝔍∂, which we refer to as the representation of P. A morphism F : Q [figure] P is merely a morphism F 𝔍 : Q𝔍 [figure] P 𝔍. Thus we have also described a full and faithful functor 𝔍 : 𝔄̌ [figure] 𝔄.

Evidently 𝔄̌ is equivalent over 𝔄 to the full subcategory of representable objects. But, because of the concrete nature of the situation, “simplifying” the definition of 𝔄̌ accordingly would only shift our dealing with a not-quite-subcategory to a less convenient place. (Admittedly in our best examples — 9, 10, 13, 15, 16 and 17 —, 𝔄̌ is canonically isomorphic to said subcategory, because the terminal objects in question are unique. In this sense we may as well elevate this uniqueness property to the rank of an axiom. But after the initial kinks have been straightened out, the generality of our treatment will cease to pose an extra burden.)

Henceforth we shall take the practical approach of writing P rather than P 𝔍 (somewhat in spite of what was said in the previous paragraph) whenever the context makes clear that the object we are referring to is one of 𝔄. In a similar vein we shall often take a slice object A↓a of 𝔄 to be an object of 𝔄̌, with ⊤_{A↓a} understood to be the “canonical” representation (a, 1_{a}) of A↓a.

The morphisms that one would have classically associated with the objects of 𝔄̌ are those whose underlying functors respect the distinguished terminal objects “on the nose”. They play an important role for us too and therefore deserve a designation. It suggests itself to say that they preserve representation. Examples are the slice morphisms F ↓b : B↓b [figure] A↓(b · F ∂).

We shall be discussing two all-object subcategories of 𝔄̌: in 𝔄̌_{difi} the morphisms are the discrete fibrations, and in 𝔄̌_{⊤} the morphisms are the representation-preserving ones. Note that a representation-preserving discrete fibration is automatically an isomorphism, whose inverse of course preserves representation as well; in other words, 𝔄̌_{difi} ∩ 𝔄̌_{⊤} is a groupoid. Note also that two objects isomorphic in 𝔄̌ are not necessarily isomorphic in 𝔄̌_{⊤}, even if 𝔄 is conservative, as example 5 (coloured categories) demonstrates. But if 𝔄̌ has small-many isomorphism classes, then so has 𝔄̌_{⊤}: for a small representative system { P_{i} = (A_{i}, ⊤_{P_{i}}) | i ∈ I } of isomorphism classes of 𝔄̌, the small set

{ (A_{i}, a) | i ∈ I; a terminal in A_{i}∂ }

includes a representative system of isomorphism classes of 𝔄̌_{⊤}.

We may view 𝔄̌_{⊤} as a full subcategory of 1↓∂, the category of 𝔄-objects above categories equipped with a base object and 𝔄-morphisms above functors respecting base objects. As such it is, as a consequence of (Sl 1) and the corresponding fact for 𝔄 = Cat, coreflective. Explicitly, for a morphism F : P [figure]A ∈ 𝔄 with P ∈ 𝔄̌, there is a unique representation-preserving morphism F^{⊤} : P [figure] A↓(⊤_{P} · F ∂) with F^{⊤} · Δ_{⊤_{P} ·F ∂}^{A} = F ∂. We shall call

[figure: P; A↓(⊤_{P} · F ∂); A; F^{⊤}; Δ_{⊤_{P} ·F ∂}^{A}]

the slice-object factorization of F; it will be crucial in the last section of this work. For P ∈ 𝔄̌, postcomposing with the respective morphism Δ_{a}^{A} yields a bijection

∑_{a∈A∂} 𝔄̌_{⊤}(P, A↓a) [figure: ≃] 𝔄(P, A)

(with inverse F [figure] F^{⊤}). For B ∈ 𝔄, precomposing with the cocone ΔB_{( )} yields a bijection

𝔄(B, A) [figure: ≃] ⟵ lim_{b∈B∂} 𝔄(B↓b, A)

(since it is universal). We hence see that if any one of the categories 𝔄, 𝔄̌ and 𝔄̌_{⊤} has small hom-sets, so have the other two.

Denote by YON^{𝔍} the covariant functor represented by 𝔍, that is,

YON^{𝔍} : 𝔄 [figure] SET𝔄̌^{op}, A [figure] 𝔄(^{( )}𝔍, A).

Here SET is the “extra large” category of large sets. If 𝔄 (or 𝔄̌, or 𝔄̌_{⊤}) has small hom-sets, we can adjust the range of YON^{𝔍} to obtain a functor Yon^{𝔍} : 𝔄 [figure]Set𝔄̌^{op}. Given a left 𝔄̌-set X, denote by X_{⊤} the left 𝔄̌_{⊤}-set obtained by restriction.

Having introduced all the players, we can now state our main result. The decisive terms may still warrant an explanation, which we shall deliver afterwards.

Theorem. Let 𝔄 be a category with slicing, and use the notations just introduced. The functor YON^{𝔍} is full and faithful, and a left 𝔄̌-set X is within an isomorphism of its image if and only if the following three conditions are satisfied.

(i) X_{⊤} is small generated. (ii) X_{⊤} is free. (iii) Local universality in X_{⊤} is preserved by discrete fibrations.

Let 𝔎 be a category. We view the objects X of SET^{𝔎^{op}} as families of sets X_{P}, indexed by the objects P of 𝔎 and acted upon by the morphisms F : Q [figure] P of 𝔎. The contravariance is expressed by writing the morphisms to the left of the elements: the image of x ∈ X_{P} under X_{F} : X_{P} [figure]X_{Q} is written F · x. Thus the X are left 𝔎-sets. The morphisms of SET^{𝔎^{op}} are treated accordingly and will be called left 𝔎-maps.

Category actions are essentially the same as many-sorted algebras with unary operations, so the terminology of Universal Algebra can be applied. Thus it should be clear what it means for a 𝔎-set to be “small generated” or “free”. Nevertheless we are going to be explicit. Let Y be a subset of (the set of elements of) X. Associated with it is the 𝔎-map ε : ∑_{P ∈𝔎_{0}} Y_{P} × 𝔎(^{( )}, P) [figure]X given by the assignment (y, F) [figure]F · y. The subset Y is said to generate the image of ε, which is a 𝔎-subset of X; it is generating iff (each constituent of) ε is surjective, and it is freely generating iff (each constituent of) ε is bijective (whence ε is an isomorphism). The 𝔎-set X itself is small generated iff some small subset generates it, and it is free iff some subset freely generates it. (One easily sees that if X is small generated and free, then there is a subset that is small and freely generating at once.)

We call a left 𝔎-set representable iff it is so as a set-valued functor, that is, iff it is isomorphic to 𝔎(^{( )}, P) for some P ∈ 𝔎 or, still equivalently, iff it has a freely generating singleton. The member of such a singleton is known as a universal element. A morphism F : Q [figure]P of 𝔎 is universal when viewed as an element of 𝔎(^{( )}, P) if and only if it is invertible.

On a more geometric note we have the notion of connectedness, which we now briefly recall. A 𝔎-set X is connected iff in any sum decomposition X ≃ ∑_{i} X^{(i)} precisely one summand X^{(i)} is non-empty (has some non-empty constituent). One can give an equivalent definition requiring the existence of an element and the existence of a zigzag between each two elements, where the zigzags referred to here are those of the category of elements. The representable 𝔎-sets are connected. Every 𝔎-set has a unique sum decomposition into connected ones, called its components.

Now in order for a 𝔎-set X to be free it is not only necessary but also sufficient to be a sum of representable 𝔎-sets (an apparent triviality resting on the Yoneda lemma). But since representable 𝔎-sets are connected, they are components wherever they appear as summands. Thus X is free if and only if each component of X is representable. Or, equivalently, if and only if each component X′ of X contains an element that is universal within X′. To express more concisely the relationship of such an element to the whole of X, we need an abbreviation for the phrase ‘within its component’. I have taken the liberty of choosing the term ‘locally’ (or ‘local’, depending on grammatical requirements).(^{4}^{,∗}) Thus, using this newly designated piece of language, X is free if and only if each component of X contains a locally universal element. But a locally universal element generates its entire component. Thus another, and final, condition equivalent to the freedom of X is for the set of locally universal elements to be generating. Spelt out this means that for each element y ∈ X_{Q} there is a locally universal element x ∈ X_{P} and a (then necessarily unique) morphism F : Q [figure] P with F · x = y.

The term ‘local’ could be applied directly to the names of special kinds of universal elements. Thus a local limit of a diagram P_{( )} in 𝔎 would be a locally universal element of the functor sending each object Q to the set of cones Q [figure] P_{( )}. In particular a locally terminal object in 𝔎 is one that is terminal within its (category) component. (For instance, in the category of fields the prime fields are locally initial.)

4While the term ‘local’ is already being used in too many other senses, the present definition does not appear to give rise to new inconsistencies. As for alternative names, [4] has ‘partial initial object’ for what we shall call a locally initial object, and [1] has ‘familial limit’ for what we shall call a local limit.

*After writing this I learnt that the very terminology initiated here had also been used, and in fact developed further, in Y. Diers: ‘Catégories localisables’, Université des sciences et techniques de Lille I

A slightly more hands-on characterization of local terminality and local universality is provided by the following result.

Lemma. An object P of a category 𝔎 is locally terminal if and only if for each situation

[figure: ∈ 𝔎; R; Q; P; H; G]

there is a unique morphism F : Q [figure]P. An element x ∈ X_{P} of a left 𝔎-set X is locally universal if and only if for each element y ∈ X_{Q} and each situation as before with H · y = G · x there is a unique morphism F : Q [figure] P with F · x = y.

The identity H · F = G is not explicitly required; it can be derived by applying the uniqueness requirement to the situation with H = 1_{R}. Making it subject to the uniqueness part would alter the condition so as to render both implications false.

Proof. The second statement just recounts what the first statement means when applied to the category of elements of X. So we only have to prove the latter. The necessity of the condition is clear. As for sufficiency consider an arbitrary object Q in the component of P. There is a zigzag of morphisms

[figure: Q = Q_{0}; R_{0}; Q_{1}; ⋯; Q_{n−1}; R_{n−1}; Q_{n} = P; H_{0}; G_{0}; Gn−1]

in 𝔎. To show that there is a unique morphism Q [figure]P we can proceed by induction on the number n of “zigs” or “zags”. If n = 0 we use the condition with G = 1_{P} and H = 1_{P}. If n ≥ 1 we use the condition with G = G_{n−1} and H = H_{n−1} and in the case n ≥ 2 further replace G_{n−2} with G_{n−2} · F and then use the induction hypothesis.

By now all clauses of the theorem should be comprehensible, except perhaps (iii). Here we mean that for any discrete fibration F : Q [figure] P, if an element x ∈ X_{P} is locally universal in X_{⊤}, then so is the element F · x ∈ X_{Q}.

This raises an interesting question. Does an isomorphism of 𝔄̌ necessarily preserve local universality in X_{⊤}? The representation-preserving ones surely do. For simplicity let us assume that X_{⊤} is free (condition (ii) of the theorem). Still, if 𝔄̌_{⊤} were just any old all-object subcategory, there would be no reason why the answer should be ‘yes’. Yet the special nature of 𝔄̌_{⊤} forces it to be just this, as we are about to witness.

Proposition. Let X be a left 𝔄̌-set for which X_{⊤} is free. Local universality in X_{⊤} is preserved by all isomorphisms of 𝔄̌.

Proof. For utter clarity, let us denote a typical object of 𝔄̌ by (A, a) (A ∈ 𝔄; a ∈ A∂ terminal) and a typical morphism (B, b) [figure] (A, a) of 𝔄̌ by (F, b, a) (F : B [figure] A ∈ 𝔄).

Without loss of generality we can consider only those isomorphisms of 𝔄̌ that are identities of 𝔄 relating objects differing only by their base objects; thus (1_{A}, a′, a) : (A, a′) [figure](A, a). Let x ∈ X_{(A,a)} be locally universal in X_{⊤}; we have to show that so is x′ = (1_{A}, a′, a) · x ∈ X_{(A,a′)}.

Since X_{⊤} is free, there are an element y′ ∈ X_{(B,b′)} locally universal in X_{⊤} and a representation-preserving morphism (G, a′, b′) : (A, a′) [figure] (B, b′) with (G, a′, b′) · y′ = x′. Putting b = a · G∂ we obtain another representation-preserving morphism (G, a, b) : (A, a) [figure](B, b). Now consider the element y = (1_{B}, b, b′) · y′ ∈ X_{(B,b)}. It shares its X_{⊤}-component with (G, a, b) · y = (1_{A}, a, a′) · (G, a′, b′) · (1_{B}, b′, b) · y = x, by whose local universality there hence is a representation-preserving morphism (F, b, a) : (B, b) [figure] (A, a) with (F, a, b) · x = y. Since (G · F, a, a) · x = (G, a, b) · (F, b, a) · x = x, the morphism G · F is the identity of A. It follows that b′ · F ∂ = a′ · G∂ · F ∂ = a′, so the morphism (F, b′, a′) : (B, b′) [figure] (A, a′) also preserves representation. Now

(F · G, b′, b′) · y′ = (1_{B}, b′, b) · (F, b, a) · (1_{A}, a, a′) · (G, a′, b′) · y′ = y′,

so by local universality of y′ the morphism F · G is the identity of B. Thus (G, a′, b′) is a representation-preserving isomorphism. We conclude that with y′ also the element x′ = (G, a′, b′) · y′ is locally universal in X_{⊤}.

In many important cases the description of the full subcategory of the theorem can take a simpler form.

Special case 1. 𝔄̌ is essentially small, or, equivalently (we have considered number of isomorphism classes and size of hom-sets separately), 𝔄̌_{⊤} is essentially small. In this situation, firstly, since 𝔄 has small hom-sets, YON^{𝔍} : 𝔄 [figure]SET𝔄̌^{op} can be replaced with Yon^{𝔍} : 𝔄 [figure] Set𝔄̌^{op} in the statement of the theorem. Secondly, since 𝔄̌_{⊤} has small-many isomorphism classes, every pointwise small 𝔄̌_{⊤}-set (= object of Set𝔄̌_{⊤}^{op}) is small generated; thus condition (i) can then be omitted.

Special case 2. All discrete fibrations in 𝔄̌ are invertible. Since in particular the sliceobject projections are discrete fibrations, the following two conditions are equivalent to the first: if A is representable, all objects of A∂ are terminal (and hence A∂ is a chaotically preordered set); every underlying category A∂ is an equivalenced set(^{5}). The preceding proposition grants us that in this (admittedly rather degenerate) situation condition (iii) can be omitted.

5An equivalenced set is evidently meant to be a preordered set for which the preorder relation is an equivalence relation (that is, symmetric). The phrase ‘essentially discrete category’ expresses an equivalent notion (at least to us believers in the axiom of choice), but has the drawback of referring to more complicated concepts.

Special case 3. All representation-preserving morphisms are invertible. Since the inverses preserve representation as well, equivalently 𝔄̌_{⊤} is a groupoid. Two further clearly equivalent conditions are: all representation-preserving morphisms of 𝔄̌ are discrete fibrations; all morphisms of 𝔄 are discrete fibrations. (Since all discrete fibrations are cartesian, the latter condition implies that 𝔄 is conservative.) In this situation an 𝔄̌_{⊤}-set is representable if and only if all its elements are universal, and hence an 𝔄̌_{⊤}-set is free if and only if all its elements are locally universal. Thus condition (iii) can be omitted.

Special case 4. All representation-preserving morphisms are invertible and moreover all representation-preserving automorphisms are trivial. Equivalently, 𝔄̌_{⊤} is essentially discrete. In this situation every 𝔄̌_{⊤}-set is free. Thus condition (ii) (along with condition (iii)) can be omitted.

Thus, if we are in special cases 1, 3 and 4 at a time, the functor Yon^{𝔍} exists and maps essentially onto Set𝔄̌^{op}. This result is worth being stated officially.

Corollary. Let 𝔄 be a category with slicing, and use the notations introduced at the beginning of this section. If 𝔄̌ is essentially small and 𝔄̌_{⊤} is essentially discrete, then Yon^{𝔍} : 𝔄 [figure] Set𝔄̌^{op} exists and is an equivalence of categories.

4. Miscellaneous

We start this section by relating the theorem to some of the examples of section 2. To avoid size issues, I shall only in passing mention examples not falling under special case 1.

Example 6, continued. Put Set^{𝔨^{op}} = 𝔄. Here 𝔄̌ is the category of those (small) 𝔨-sets that are represented in the usual sense and all their 𝔨-maps. Particular objects are the “prototypical” represented 𝔨-sets 𝔨(^{( )}, k), with the distinguished universal elements taken to be the respective identities. Now if P and Q are two represented 𝔨-sets, the distinguished elements being ⊤_{P} ∈ P_{k} and ⊤_{Q} ∈ Q_{l}, then a representation-preserving morphism Q [figure]P exists if and only if the “sorts” k and l agree, and such a morphism then is unique (and hence invertible). As a consequence the isomorphism classes of 𝔄̌_{⊤} are in a one-to-one correspondence with the objects of 𝔨. In summary, we are in special cases 1 and 4, and so the corollary applies: Yon^{𝔍} (exists and) is an equivalence Set^{𝔨^{op}} [figure: ≈] Set𝔄̌^{op}. Of course there is little surprise here (and in fact quite the contrary is intended): already the functor 𝔨 [figure]𝔄̌ sending k to 𝔨(^{( )}, k) is an equivalence, which, when followed by 𝔍 : 𝔄̌ [figure]𝔄, yields the Yoneda embedding 𝔨 [figure]Set^{𝔨^{op}}; by the Yoneda lemma it hence induces an up-to-isomorphism inverse for Yon^{𝔍}.

Example 7, continued. Put 𝔎⟶ Fam = 𝔄. Since all underlying categories (X, K)∂ = X are discrete, we are in special case 2. The ones with terminal objects are precisely the singleton sets. Thus the issue of distinguishing a particular terminal object does not arise: we can identify 𝔄̌ with a full subcategory of 𝔄. We have a projection 𝔄̌ [figure]𝔎, ({x}, K) [figure]K_{x}, which clearly is an equivalence. Thus we are in special case 1 if and only if 𝔎 is essentially small. So let us suppose 𝔎 has this property. Now the theorem tells us that the functor Yon^{𝔍} : 𝔎⟶ Fam [figure]Set𝔄̌^{op} is full and faithful, and that its image essentially consists of those left 𝔄̌-sets that are free. Again we should not be surprised. Suppose for the sake of this argument that 𝔎 is genuinely small. In this case 𝔎⟶ Fam can easily be seen to be the Kleisli category for the monad on Set^{𝔎_{0}} (where 𝔎_{0} is the set of objects of 𝔎) whose Eilenberg–Moore algebras are left 𝔎-sets. The Kleisli category is by design isomorphic to the full category of free Eilenberg–Moore algebras, and the property of freedom is invariant under equivalences of the operating categories. Our functor Yon^{𝔍} turns out to be isomorphic to the composite of the embedding 𝔎⟶ Fam [figure] Set^{𝔎^{op}} and the functor induced by the equivalence 𝔄̌ [figure: ≈] 𝔎.

Examples 9 and 15, continued. First consider 𝔄 = Grph. Here 𝔄̌ is the category of downward trees and all graph morphisms. By graph duality, 𝔄̌_{⊤} is equivalent as a category to Tree. Neither of the two is essentially small, for which reason we immediately move on to 𝔄 = Frst. Here the size aspect of the situation is fundamentally different. A graph that is both an upward forest and a downward tree is just a single finite “branch” or path, and the isomorphism classes of paths correspond via the length function to the natural numbers. As the roots for the upward forest are respected by the morphisms of 𝔄 = Frst, the category 𝔄̌ is clearly equivalent to N as an ordered set. The morphisms of 𝔄̌_{⊤} respect the roots for the downward trees as well and therefore are invertible; the corresponding all-object subcategory of N is the discrete one. Thus we are in special cases 1 and 4, and the corollary tells us that Yon^{𝔍} is an equivalence Frst [figure: ≈] Set𝔄̌^{op}. Since Frst ≈ Tree and 𝔄̌ ≈ N we also have Tree ≈ Set^{N^{op}}. Yet once more category theorists cannot be surprised; many define the category of trees as suggested by the last equivalence.

Examples 10 and 16, continued. First consider 𝔄 = Refl Grph. The objects of 𝔄̌ are reflexive downward trees (which are defined in the evident way); certainly 𝔄̌ is not essentially small. Thus consider 𝔄 = Refl Frst instead. Here the objects of 𝔄̌ are such reflexive graphs as are reflexive upward forests and reflexive downward trees at a time. As in the previous paragraph, the isomorphism classes correspond to natural numbers. The morphisms, however, from a length-m reflexive path to a length-n reflexive path correspond to functions φ : {0, …, m} [figure] {0, …, n} with (0)φ = 0 and (i)φ ≤ (i+1)φ ≤ (i)φ + 1. The discrete fibrations correspond to the inclusions, and the representationpreserving morphisms correspond to the surjective (order-preserving) functions (which coincide with the degeneracy maps in the topologist’s simplex category). From here the reader can work out how according to the theorem Refl Frst can be viewed as a full category of set-valued functors.

Examples 13 and 17, continued. This example pair agrees with the previous two in that each object can have at most one representation. First consider 𝔄 = Propoly Set. We call the objects of 𝔄̌ propolytopes. By “propolytopic duality” they correspond to augmented polytopic sets. There are more than small-many isomorphism classes of them, and so we instead consider 𝔄 = Pln Poly Set (≈ Aug Poly Set). Here we call the objects of 𝔄̌ plain polytopes. Contrary to the branches of example 15, a plain polytope P can have many maximal generator paths; yet all their lengths agree. We call this number the dimension of P.

It may be illustrative to mention the polytopes (the term is now used in the ‘up to isomorphism’ sense) of the first three dimensions. There is one of dimension 0, called the point; its representation is a vertex. There is one of dimension 1, called the line segment; it has precisely two vertices; its representation is an edge. And for each m ∈ {1, 2, 3, …; ∞} there is one of dimension 2 with precisely m vertices, called the m-gon (with any explicit value of m to be expressed in Greek: monogon, digon, trigon, …; apeirogon); it has also precisely m edges. Here are the key ones pictured:

[figure: ∘; •] point, [figure: ∘; •; •; •; ^{\binom{!}{=}}]

line segment,

[figure: ∘; •; •; •; •; •; •; •; •; •; ⋯; ⋯; ^{\binom{!}{=}}; ^{\binom{!}{=}}; ^{\binom{!}{=}}; =^{!}; =^{!}; =^{!}]

apeirogon.

(Items indicated lightly belong to the augmented but not the plain version.)

It is not difficult to show that all polytopes are countable (in the obvious sense) and that hence there are at most continuum-many of them. Thus we are in special case 1. The representation-preserving morphisms of 𝔄̌ are the polytopic maps between polytopes of the same dimension.(^{6}) The discrete fibrations of 𝔄 = Pln Poly Set can be described roughly as those polytopic maps that “maintain the shape” of individual “cells”. (A morphism from the m′-gon to the m-gon — there are 2m of them whenever m divides m′ — is a discrete fibration if and only if m = m′.) The theorem ensures that the better we understand polytopes and their polytopic maps, the better we understand polytopic sets and maps at large.

We now take a second look at our system of axioms of section 1, with the aim of convincing ourselves that the most tempting omissions would change the notion at hand.

With axioms (Sl 1) and (Sl 2) in place, axioms (Sl 3) and (Sl 4) (unlike (Sl 3′) and (Sl 4′)) are independent of each other. This is shown by the following two (parametrized) counterexamples. Let 𝔄 be a category with slicing. We consider its cartesian product 𝔄 × 2 with the ordered set 2 = {0, 1}, taken over Cat in the canonical way (that is, by putting (A, i)∂ = A∂). We easily see that 𝔄 × 2 satisfies (Sl 1) and (Sl 2). But 𝔄 × 2 fails to satisfy (Sl 4) — consider an object (A, 1) with A initial in 𝔄 — and, unless 𝔄 is trivial, also (Sl 3) — for two (possibly the same) non-initial objects A_{0}, A_{1} of 𝔄, consider the (A_{0}∂ + A_{1}∂)-shaped diagram which on the summand indexed by i takes the form (A_{i}↓^{( )}, i). The actual counterexamples I have in mind arise as full subcategories of 𝔄 × 2.

6The category of n-dimensional polytopes is equivalent to the full category of transitive C_{n}-sets having certain properties. Here C_{n} is the Coxeter group whose Dynkin diagram is the n-vertex path with all edges labelled ∞. (Examining the details of this assessment would lead us too far afield.) A certain category resembling P̌oly Set_{⊤} is being examined by Robin Cockett ([1]).

The result of discarding all objects (A, 1) with A initial satisfies (Sl 4), but, unless 𝔄 is trivial, not (Sl 3). The result of instead discarding all objects (A, 0) for which there is a morphism in 𝔄 from A to a representable object satisfies (Sl 3), but, unless all A have the stated property, not (Sl 4). For conservative 𝔄 the latter full subcategory even satisfies (Sl 3′), whence we see that the first proposition of section 1 cannot be improved. Here I owe an example of an object in a (preferably non-trivial) conservative category 𝔄 with slicing from which there is indeed no morphism to a representable one. A such would be the terminal object in Set^{𝔨^{op}}, provided (say) for each k ∈ 𝔨 there is l ∈ 𝔨 with 𝔨(l, k) = ∅.

We also set our sight on the phrase ‘with each P_{α} cartesian’ in (Sl 2). One may wonder what would happen if we left it out. We may do so in two ways, retaining either the wording or the meaning of (Sl 3) (that is, letting the latter axiom refer to either the changed or the original version of the former). In the first case closedness under right division leads to the conclusion that in fact all diagrams above 𝔞↓^{( )} are in 𝔄_{cart} from the outset. This condition is rather strange; it holds true in conservative categories with slicing, but I know of no other example. The second case is more interesting. The strengthened axiom (Sl 2) is satisfied by Cat Pres, to name an example that is not conservative. Yet it is not satisfied by all categories with slicing. Indeed, consider (𝔪↓∗)⟵ Dg^{op}, the opposite of the projective diagram category of the “Cayley category” of a small commutative monoid 𝔪, viewed as a category with a single object ∗. If 𝔪 contains a non-invertible element, then there is no cocartesian lifting of Δ𝔪_{( )} to the 𝔪-shaped diagram above 𝔪↓^{( )} whose object is the identity functor on 𝔪↓∗. (Exercise.)

We are now going to give further examples of categories with slicing, working our way towards the remaining one mentioned prominently in the preface. At this point it is useful to bring some “2-abstract nonsense” into the picture.

Let 𝔄 and 𝔅 be two categories over an arbitrary base category ℑ. By a functor 𝔉 : 𝔅 [figure] 𝔄 over ℑ we mean one that comes equipped with a (natural) isomorphism

[figure: 𝔅; 𝔄; ℑ.; 𝔉; ∂; ∂; ≃]

By a natural transformation over ℑ between two such functors we mean one rendering the evident cone-shaped figure commutative.

We are working with a universe of “small” sets and a universe of “large” sets, the latter containing the former as an element.(^{7}) We have an “extra large” 2-category CAT of large categories, functors and natural transformations. The corresponding data over ℑ form the pseudo-slice 2-category CAT⇓ℑ. We further have a projection CAT⇓ℑ [figure]CAT, which is biconservative: a functor over ℑ which is an equivalence as a plain functor (that is, in CAT) is automatically an equivalence over ℑ (that is, in CAT⇓ℑ).(^{8})

7Elsewhere we follow the custom of using the term ‘small’ in the sense of ‘small up to isomorphism’ as well and concealing the process of overcoming the difference of the two meanings.

8Notwithstanding my adapted use of the term ‘above’, I am trying to follow standard 2-categorical terminology.

Now let 𝔄 and 𝔅 be two categories with slicing. We say that a functor 𝔉 : 𝔅 [figure]𝔄 over Cat preserves slicing iff it preserves cartesianness of the morphisms of (Sl 1) and cocartesianness of the cocones of (Sl 2). This property of course comes for free if 𝔉 is an equivalence. It is also implied in the case that 𝔄 is conservative. We have virtually encountered some slicing-preserving functors already: the inclusions 𝔄_{difi} [figure]𝔄_{cart} [figure]𝔄 (examples 2 and 3) and Pln Poly Set [figure]Propoly Set [figure]Cat Pres (examples 13 and 17; also Grph, Refl Grph and Undir Grph can be viewed as subcategories-with-slicing of Cat Pres) as well as the projection Δ_{T}^{𝔄} : 𝔄↓T [figure] 𝔄 (example 4). Categories with slicing, slicing-preserving functors and natural transformations form a sub-2-category SLCAT of CAT⇓Cat.

It is known that CAT is (strictly) large complete and hence bicategorically large complete. For instance, bipulling back

[figure: 𝔅; 𝔛; 𝔄; 𝔊; 𝔉]

yields the iso-comma category (the full subcategory of 𝔊↓𝔉 having objects (B, U, A) with U : B𝔊 [figure]A𝔉 invertible), up to equivalence. (This representative is not a pseudopullback!) It is also known that the property of bicategorical completeness is inherited by pseudo-slice 2-categories, the connected bilimits (such as bipullbacks) being created by the projection. Thus in particular CAT⇓Cat is bicategorically large complete. Further it can be shown that SLCAT is closed in CAT⇓Cat with respect to bilimits.

Example 18. Let 𝔉 : 𝔅 [figure]𝔄 be a slicing-preserving functor, and let T be an object of 𝔄. The comma category 𝔉↓T has slicing.

Proof. The category in question comes about via a bipullback square

[figure: 𝔄; 𝔅; 𝔄↓T; 𝔉↓T; 𝔉; Δ_{T}^{𝔄}]

(which happens to be a pullback square as well) in SLCAT.

Let us apply this example to the situation where 𝔉 is the inclusion Propoly Set [figure] Cat Pres and T is the presentation T_{or} with one object, two generators − and + and four relators

[figure: •; •; •; •; ||·; •; •; •; •; +; −; +; +], [figure: •; •; •; •; ||·; •; •; •; •; +; +; +; −], [figure: •; •; •; •; ||·; •; •; •; •; −; −; −; +], [figure: •; •; •; •; ||·; •; •; •; •; −; +; −; −].

(T_{or} is not a propolytopic set: each of the four length-2 paths occurs as a side of two relators.) The structure on a propolytopic or augmented polytopic set conveyed by a presentation morphism to T_{or} is an orientation. (For plain polytopic sets there is an additional condition.) Thus our result is that the category Or Propoly Set of oriented propolytopic sets has slicing. Applying example 14 next we further infer that so has the category Or Propoly Set_{Θ} = Or Aug Poly Set of oriented augmented polytopic sets, where we understand that the structural functor drops the initial objects. (This modification is the reason why we cannot arrive at the same conclusion by applying example 18 again: the inclusion Aug Poly Set [figure] Cat Pres does not live over Cat, while the functor Aug Poly Set [figure]Cat Pres dropping initial objects would give rise to a different comma category.)

Our last official example has as its instances arbitrary full and replete subcategories inheriting slicing.

Example 19. Let 𝔄 be a category with slicing. Any full and replete subcategory of 𝔄 that contains an object A if and only if it contains all the associated slice objects A↓a (a ∈ A∂) has itself slicing.

We have already used this fact, namely in our proof for example 13. We could have advantageously used it in our proof for example 7 too: clearly 𝔎⟶ Fam is equivalent over Cat to a full subcategory of 𝔎^{op}⟵ Dg^{op}, namely of those diagrams whose shapes are discrete or, equivalently, whose slice diagrams all have shape (isomorphic to) 1.

An (augmented) dendrotopic set is an oriented augmented polytopic set in which • each object except the initial one has finitely many negative and precisely one

positive incoming generators,

• each 3-codimensional morphism (that is, morphism represented by generator paths of length 3) is represented in precisely one way by a configuration

[figure: •; •; •; •; ||·; •; •; •; •; •; +].

It is fairly clear that an object of the category Or Aug Poly Set has these properties if and only if all of its slice objects have. From the example we infer that the full subcategory Dend Set of dendrotopic sets has slicing. Moreover, Dend Set falls into special cases 1 and 4 of the previous section. I mentioned the reasons in [6]; I will supply more details in a future paper. All said, we arrive at the conclusion that dendrotopic sets form a presheaf category.

In example 19, the subcategory 𝔅 of 𝔄 is determined, as such, by the subcategory 𝔅̌ of 𝔄̌. This insight leads to a much further reaching idea: What if instead of 𝔅̌ we were given an abstract category 𝔓 with suitable extra structure? Explicitly, we are seeking a construction assigning to 𝔓 a category with slicing from which 𝔓 can be recovered, up to equivalence, as the full category of represented objects. Moreover, if 𝔓 = 𝔄̌ for a given category 𝔄 with slicing, we should like our construction to produce a category equivalent to 𝔄 over Cat. (The theorem of the previous section points in this direction, but leaves the issue of structural functors aside.)

We first have to determine what extra structure we need on 𝔓. If 𝔓 = 𝔄̌, then we have an induced functor P [figure] P ∂ into Čat, the category of small categories with distinguished terminal object and all functors between them. As a category over Čat, 𝔓 will satisfy an appropriately modified version of (Sl 1), namely:

(Šl 1) Let P ∈ 𝔓 and 𝔭 ∈ Čat be two objects with 𝔲 : 𝔭 [figure: ≃] P ∂ ∈ Čat_{⊤}. For any object a ∈ 𝔭, there are an object Q ∈ 𝔓 with 𝔳 : 𝔭↓a [figure: ≃] Q∂ ∈ Čat_{⊤} and a

cartesian morphism F : Q [figure] P with F ∂ = 𝔳^{−1} · Δ_{a}^{𝔭} · 𝔲.

(We continue to take automatically the distinguished terminal object of a slice category to be the identity morphism.) Let us call an arbitrary category 𝔓 over Čat satisfying (Šl 1) a slicing site.

It should have become clear what we mean by the phrase ‘appropriately modified’: all the small categories mentioned have to be represented (= equipped with a distinguished terminal object); all their invertible functors mentioned have to respect representations. The latter modification is particularly noteworthy. It leads us to limit accordingly the meaning of the preposition ‘above’ in relation to a category over Čat. (There is a case here for studying categories over a base category ℑ with a distinguished all-object subgroupoid of “true isomorphisms”.)

Note that any category over Čat trivially satisfies the appropriately modified versions of the other three axioms on a category with slicing. (This is because a diagram whose shape has a terminal object carries along its own colimit.) As a consequence, the main results of section 1 on categories with slicing, appropriately modified, hold for slicing sites as well. In particular, we can talk about discrete fibrations, which are those morphisms F : Q [figure]P for which all slice morphisms F ↓b : Q↓b [figure]P ↓(b · F ∂) are invertible or, equivalently, the cartesian morphisms above discrete fibrations in Čat.

Given a slicing site 𝔓, we construct a category 𝔓̂ replete over Cat as follows. An object strictly above 𝔞 consists of an 𝔞-shaped diagram P_{( )} = P in 𝔓 for which each P_{α} : P_{a′} [figure]P_{a} is cartesian, and an isomorphism 𝔲_{( )} = 𝔲 : 𝔞↓^{( )} [figure: ≃]P ∂ for which each 𝔲_{a} : 𝔞↓a [figure: ≃]P_{a}∂ respects representations. A morphism (𝔟, Q, 𝔳) [figure](𝔞, P, 𝔲) strictly above 𝔣 : 𝔟 [figure]𝔞 is a morphism Φ_{( )} = Φ : Q [figure]P_{𝔣} of 𝔟-shaped diagrams such that Φ∂ = 𝔳^{−1} · 𝔣↓^{( )} · 𝔲_{𝔣}

[figure: ( 𝔞; 𝔟; 𝔓; Čat; 𝔣; P; ∂; 𝔟↓^{( )}; Q; Φ; 𝔳; ≃; 𝔞; 𝔟; 𝔓; _{Čat ).}; 𝔣; P; ∂; 𝔟↓^{( )}; 𝔞↓^{( )}; 𝔣↓^{( )}; 𝔲; ≃; =]

This last condition implies that each Φ_{b} : Q_{b} [figure] P_{b·𝔣} respects representations. Composition in 𝔓̂ is carried out in the obvious way.

We are now going to show that 𝔓̂ has slicing. We start by noting that a morphism (𝔤, Φ) of 𝔓̂ is a discrete fibration if and only if the diagram morphism Φ is invertible. Let (𝔞, P, 𝔲) be an object of 𝔓̂. Any discrete fibration 𝔤 : 𝔠 [figure]𝔞 has a cartesian lifting (𝔤, 1_{P_{𝔤}}) : (𝔠, P_{𝔤}, 𝔤↓^{( )} · 𝔲_{𝔤}) [figure] (𝔞, P, 𝔲); in particular, so have the slice-category projections. Next, consider a functor 𝔣^{∗} : 𝔞 [figure] 𝔟 and let (𝔣^{a}, Φ^{a}) : (𝔞↓a, P_{Δ_{a}^{𝔞}}, Δ_{a}^{𝔞}↓^{( )} · 𝔲_{Δ_{a}^{𝔞}}) [figure] (𝔟, Q, 𝔳)

[figure: 𝔞↓a; ( 𝔟; 𝔓; Čat; 𝔣^{a}; Q; ∂; (𝔞↓a)↓^{( )}; 𝔞; Δ_{a}^{𝔞}; P; 𝔞↓^{( )}; Φ^{a}; 𝔲; ≃; ≃; 𝔞↓a; 𝔟; 𝔓; _{Čat )}; 𝔣^{a}; Q; ∂; (𝔞↓a)↓^{( )}; 𝔟↓^{( )}; _{𝔣^{a}↓_{( )}}; 𝔳; ≃; =]

form a cocone on the slice-object diagram, with 𝔣^{a} = Δ_{a}^{𝔞} · 𝔣^{∗}. The diagram morphisms Φ^{a} : P_{Δ_{a}^{𝔞}} [figure] Q_{𝔣^{a}} now form a modification between two (strict) cocones in CAT. Since Δ𝔞_{( )} is a bicolimit, there is a unique diagram morphism Φ^{∗} : P [figure] Q_{𝔣^{∗}} with Φ_{Δ_{a}^{𝔞}}^{∗} = Φ^{a}. Now

(𝔲 · Φ^{∗}∂)_{Δ_{a}^{𝔞}} = 𝔲_{Δ_{a}^{𝔞}} · Φ^{a}∂ = (Δ_{a}^{𝔞}↓^{( )})^{−1} · 𝔣^{a}↓^{( )} · 𝔳_{𝔣^{a}} = 𝔣^{∗}↓(^{( )} · Δ_{a}^{𝔞}) · 𝔳_{𝔣^{a}} = (𝔣^{∗}↓^{( )} · 𝔳_{𝔣^{∗}})_{Δ_{a}^{𝔞}}
[figure: 𝔞↓a; ( 𝔟; 𝔞; 𝔓; Čat; Δ_{a}^{𝔞}; Q; ∂; 𝔞↓^{( )}; 𝔣^{∗}; P; Φ^{∗}; 𝔲; ≃; 𝔞↓a; 𝔟; 𝔞; 𝔓; _{Čat ),}; Δ_{a}^{𝔞}; Q; ∂; 𝔞↓^{( )}; 𝔣^{∗}; 𝔟↓^{( )}; 𝔳; ≃; =]

whence also Φ^{∗}∂ = 𝔲^{−1} · 𝔣^{∗}↓^{( )} · 𝔳_{𝔣^{∗}}. Thus indeed there is a unique morphism (𝔣^{∗}, Φ^{∗}) : (𝔞, P, 𝔲) [figure] (𝔟, Q, 𝔳) with (Δ_{a}^{𝔞}, 1_{P_{Δ^{𝔞}_{a}}}) · (𝔣^{∗}, Φ^{∗}) = (𝔣^{a}, Φ^{a}).

Now suppose that (𝔞↓^{( )}, P^{( )}, 𝔲^{( )}) is an arbitrary diagram strictly above 𝔞↓^{( )}, with each

(𝔞↓f, P^{f}) : (𝔞↓b, P^{b}, 𝔲^{b}) [figure] (𝔞↓a, P^{a}, 𝔲^{a})

cartesian, that is, each P^{f} : P^{b} [figure]P_{𝔞↓f}^{a} invertible. Then the P^{a} form a pseudo-cocone 𝔞↓^{( )} [figure] 𝔓 in CAT. Since Δ^{𝔞} : 𝔞↓^{( )} [figure] 𝔞 is a bicolimit, there are an 𝔞-shaped diagram P^{∗} and diagram isomorphisms Φ^{a} : P^{a} [figure: ≃]P_{Δ_{a}^{𝔞}}^{∗} amounting to a modification of pseudo-

cocones, so that we have P^{f} · Φ_{𝔞↓f}^{a} = Φ^{b}. Now note that the Δ_{a}^{𝔞}↓^{( )} : (𝔞↓a)↓^{( )} [figure: ≃] 𝔞↓(^{( )} · Δ_{a}^{𝔞}) as well as the 𝔲^{a} : (𝔞↓a)↓^{( )} [figure: ≃] P^{a}∂ amount to a modification of pseudo-cocones 𝔞↓^{( )} [figure] Čat. It follows that so do the (Δ_{a}^{𝔞}↓^{( )})^{−1} · 𝔲^{a} · Φ^{a}∂ : (𝔞↓^{( )})_{Δ_{a}^{𝔞}} [figure] P_{Δ_{a}^{𝔞}}^{∗}∂ (both these nominal pseudo-cocones are in fact strict). They therefore equal 𝔲_{Δ_{a}^{𝔞}}^{∗} for a unique diagram morphism 𝔲^{∗} : 𝔞↓^{( )} [figure] P^{∗}∂, which inherits invertibility and representation preservation

[figure: 𝔞↓a; ( 𝔞; 𝔓; Čat; Δ_{a}^{𝔞}; ∂; P^{∗}; (𝔞↓a)↓^{( )}; 𝔞↓^{( )}; ≃; 𝔲^{∗}; ≃; 𝔞↓a; 𝔞; 𝔓; _{Čat ).}; Δ_{a}^{𝔞}; ∂; P^{∗}; (𝔞↓a)↓^{( )}; P^{a}; 𝔲^{a}; ≃; Φ^{a}; ≃; =]

We have thus constructed an object (𝔞, P^{∗}, 𝔲^{∗}) of 𝔓̂ and an isomorphism (1_{𝔞↓^{( )}}, Φ^{( )}) : (𝔞, P^{∗}, 𝔲^{∗})↓^{( )} [figure: ≃](𝔞↓^{( )}, P^{( )}, 𝔲^{( )}) of 𝔞-shaped diagrams in 𝔓̂ strictly above the identity of 𝔞↓^{( )}. This completes our proof.

If 𝔓 = 𝔄̌ for a category 𝔄 with slicing, then 𝔓̂ ≈ 𝔄 over Cat. A functor from 𝔄 to 𝔓̂ is obtained using (Sl 1); its object assignment is A [figure] (A∂, A↓^{( )}, 1_{A↓^{( )}}). A functor in the opposite direction is obtained using (Sl 2); its object assignment is (𝔞, P, 𝔲) [figure] A, where A denotes a colimit object of the diagram P. By (Sl 3) and (Sl 4) these two functors are indeed pseudo-inverses of each other.

We also have ˇ 𝔓̂ ≈ 𝔓 over Čat, in the sense indicated above that the isomorphisms involved preserve representation. Here the two pseudo-inverses have object assignments P [figure](P ∂, P ↓^{( )}, 1_{P ↓^{( )}}) and (𝔞, P, 𝔲) [figure]P⊤_{𝔞}. The verification of the details is left to the reader.

To put these results into a concise form, we introduce the 2-category SLSITE of slicing sites. The objects are the ones suggested by the name. The 1-cells are the slicingpreserving functors, that is, functors 𝔉 : 𝔔 [figure] 𝔓 preserving cartesianness as required by (Šl 1) and coming equipped with a representation-preserving isomorphism 𝔉∂ [figure: ≃] ∂. The 2-cells are those natural transformations satisfying the evident commutativity condition (and hence preserving representation themselves). Of course SLSITE is a sub-2-category of CAT⇓Čat, the pseudo-slice 2-category of categories over Čat.

The assignments 𝔄 [figure] 𝔄̌ and 𝔓 [figure] 𝔓̂ can be extended in a straight-forward manner to become 2-functors SLCAT [figure]SLSITE and SLSITE [figure]SLCAT. The equivalences 𝔄 ≈ ˆ 𝔄̌ and 𝔓 ≈ ˇ 𝔓̂ described above similarly become the constituents of pseudo-natural transformations. Again I leave the verification of the details to the reader.

We can now summarize.

Theorem. The 2-categories SLCAT and SLSITE are biequivalent via the 2-functors

𝔄 [figure] 𝔄̌ and 𝔓 [figure] 𝔓̂.

5. The Proof

The main theorem consists of three parts, whose separate proofs are arranged here with increasing difficulty and length. A theme common to the last two parts is treated in a lemma.

We write 𝔓 for 𝔄̌ throughout.

(First part). YON^{𝔍} is full and faithful.

Proof. Let A, B ∈ 𝔄 and consider a 𝔓-map

φ : 𝔄(^{( )}𝔍, B) [figure] 𝔄(^{( )}𝔍, A).

Applying φ_{B↓b} to the slice-object projection Δ_{b}^{B} ∈ 𝔄(B↓b, B) we obtain a morphism F′_{b} = (Δ_{b}^{B})φ_{B↓b} ∈ 𝔄(B↓b, A). By naturality of φ these morphisms are the constituents of a B∂-shaped cocone F ′_{( )} : B↓^{( )} [figure]A. Since ΔB_{( )} is a universal cocone, there is precisely one morphism F : B [figure]A such that ΔB_{( )} · F = F ′_{( )}. All we need to show is that this equation is equivalent to 𝔄(^{( )}𝔍, F) = φ. But if the latter equation holds, the former is just the definition of F ′_{( )}. So what remains to be shown is that the former implies the latter.

So suppose ΔB_{( )} · F = (ΔB_{( )})φ_{B↓^{( )}}, and let P ∈ 𝔓 and H ∈ 𝔄(P, B). Using the sliceobject factorization of H we find that

H · F = H^{⊤} · Δ_{⊤_{P} ·H}^{B} · F = H^{⊤} · (Δ_{⊤_{P} ·H}^{B})φ_{B↓(⊤_{P} ·H)} = (H^{⊤} · Δ_{⊤_{P} ·H}^{B})φ_{P} = (H)φ_{P} .

Lemma. Consider the situation

[figure: P; B; A; G; F; ∈ 𝔄]

with F a discrete fibration and P ∈ 𝔓. For any b ∈ B∂ with b · F ∂ = ⊤_{P} · G∂ there is precisely one morphism H : P [figure] B with ⊤_{P} · H∂ = b and H · F = G.

Proof. Glancing at the diagram

[figure: P; B; A,; P ↓⊤_{P}; B↓b; A↓a; G; F; G↓⊤_{P}; F ↓b; ≃; ΔP ; {⊤ \atop P}; ≃; Δ_{a}^{A}; Δ_{b}^{B}; H; H↓⊤_{P}]

we see that H = (ΔP ; ⊤_{P})^{−1} · G↓⊤_{P} · (F ↓b)^{−1} · Δ_{b}^{B} meets the requirements. Conversely, if H meets the requirements, then H = (ΔP ; ⊤_{P})^{−1} · H↓⊤_{P} · Δ_{b}^{B} and H↓⊤_{P} = G↓⊤_{P} · (F ↓b)^{−1}.

(Second part). Each X = 𝔄(^{( )}𝔍, A) satisfies conditions (i), (ii) and (iii).

Proof. We first show that an element x ∈ X_{P} is locally universal in X_{⊤} if and only if the morphism x : P [figure] A is a discrete fibration.

As for the ‘if’ part, we apply the lemma on local universality (section 3). Thus we have to consider a commutative square

[figure: R; Q; P; A; H; y; G; x]

with x a discrete fibration and G and H preserving representation. Now since ⊤_{P} · x∂ = ⊤_{R} · G∂ · x∂ = ⊤_{R} · H∂ · y∂ = ⊤_{Q} · y∂, the preceding lemma applies: there is precisely one representation-preserving morphism F : Q [figure] P with F · x = y. And this is what we have had to show.

As for the ‘only if’ part, it suffices to show that in the slice-object factorization

P [figure: x^{⊤}] A↓a [figure: Δ_{a}^{A}] A,  (1)

x^{⊤} is an isomorphism. To this end, first note that since x^{⊤} preserves representation, we can apply the local universality of x in X_{⊤} to the commutative square

[figure: P; A↓a; P; A; x^{⊤}; Δ_{a}^{A}; =; x; U]

to obtain a representation-preserving morphism U as shown, making the lower right and, as we know, also the upper left triangle commute. Thus x^{⊤} · U = 1_{P}. Then consider the situation

[figure: A↓a; A↓a; A.; Δ_{a}^{A}; Δ_{a}^{A}]

Since Δ_{a}^{A} is a discrete fibration, the preceding lemma tells us that there is only one representation-preserving morphism rendering the triangle commutative. Now U·x^{⊤}·Δ_{a}^{A} = U · x = Δ_{a}^{A}, so that U · x^{⊤} = 1_{A↓a}. In summary, U is an inverse for x^{⊤}.

Now the assertions on X can easily be verified. Property (iii) is obvious since discrete fibrations are closed under composition. As for properties (i) and (ii), the possibility of a decomposition (1) makes clear that the elements Δ_{a}^{A} ∈ X_{A↓a} generate X_{⊤}. They are small many since A∂ ∈ Cat, and they are locally universal in X_{⊤} since they are discrete fibrations.

(Third part). A left 𝔓-set X satisfying conditions (i), (ii) and (iii) is isomorphic to one of the form 𝔄(^{( )}𝔍, A).

Proof. We start by laying out the essential constructions. Write 𝔍_{difi} for the projection 𝔓_{difi} [figure] 𝔄_{difi}. For each A ∈ 𝔄 we have three functors

[figure: 𝔍↓A; A∂.; 𝔍_{difi}↓A; τ_{A}; σ_{A}; ρ_{A}; ?]  (2)

Namely, ρ_{A} is the inclusion, σ_{A} is the assignment a [figure](A↓a, Δ_{a}^{A}), and τ_{A} is defined as follows. For P ∈ 𝔓 and F : P [figure] A ∈ 𝔄 put

(P, F)τ_{A} = ⊤_{P} · F ∂,

and for H : Q [figure] P ∈ 𝔓 with H · F = G put

(H : (Q, G) [figure] (P, F))τ_{A} = ⊤_{Q} · H∂ ·!_{P} · F ∂,

where p · !_{P} denotes the unique morphism p [figure]⊤_{P}. The process giving rise to the morphism Hτ_{A} is visualized by the diagram

[figure: Q; P; A; H; G; F; ⊤_{Q}·H∂; ⊤_{P}; ⊤_{Q}; ⊤_{Q}·G∂; ⊤_{P} ·F ∂; .]

The three categories displayed in (2) are the object values at A of three evident functors of 𝔄_{difi}. Thus we can discuss naturality with respect to discrete fibrations for the accompanying three families of functors: ρ self-evidently is natural, and τ can easily be checked to be; from these two facts and the result of the following paragraph one can infer that σ is pseudo-natural.

Let us compare the three ternary composites of (2) with the corresponding identities. Firstly, we have a natural transformation

1_{𝔍↓A}  [figure] τ_{A}σ_{A}ρ_{A}  (3)

mapping (P, F) ∈ 𝔍↓A to the representation-preserving morphism

F^{⊤} : (P, F) [figure] (A↓(⊤_{P} · F ∂), Δ_{⊤_{P} ·F ∂}^{A})

occurring in the slice-object factorization of F : P [figure] A. If F is a discrete fibration, then so is F^{⊤} by closedness under right division; thus we can restrict domain and range of (3) simultaneously to 𝔍_{difi}↓A to obtain a natural transformation 1_{𝔍_{difi}↓A} [figure]ρ_{A}τ_{A}σ_{A}. But a representation-preserving discrete fibration is an isomorphism, and so we have, secondly,

1_{𝔍_{difi}↓A} ≃ ρ_{A}τ_{A}σ_{A}.

The third and remaining composite is easily checked to be the identity:

1_{A∂} = σ_{A}ρ_{A}τ_{A}.  (4)

All said, the functor ρ_{A}τ_{A} has σ_{A} as both a (strict) section and a pseudo-inverse; it is therefore a surjective equivalence.

We need to understand fully the “one-dimensional behaviour” of ρ_{A}τ_{A}. To achieve this end we are going to prove the following statement: The functor ρ_{A}τ_{A} sends a morphism H : (Q, G) [figure](P, F) of 𝔍_{difi}↓A to an identity in A∂ if and only if H : Q [figure]P preserves representation. It is clear that if H preserves representation, Hρ_{A}τ_{A} is an identity. Conversely, suppose that Hρ_{A}τ_{A} is the identity of an object a. For both ⊤_{Q} · H∂ ·!_{P} : ⊤_{Q} · H∂ [figure] ⊤_{P} and 1⊤_{P} : ⊤_{P} [figure] ⊤_{P} the image under F ∂ is 1_{a}. Since F ∂ is a discrete fibration, we get ⊤_{Q} · H∂ = ⊤_{P}, or in other words: H preserves representation.

After these preliminaries we now turn to the proof itself. Let X be a 𝔓-set satisfying conditions (i), (ii) and (iii). Denote by X_{⊤} and X_{difi} the respective structures obtained by restricting X to 𝔓_{⊤} and 𝔓_{difi}. The well-known “absorption” of the element-category construction (of which the slice-category construction can be viewed as a special case via the Yoneda embedding) associates with each element x ∈ X_{P} an isomorphism

(𝔓_{difi}↓X_{difi})↓(P, x) [figure: ≃] 𝔓_{difi}↓P,  (5)

whose inverse maps (Q, F) to ((Q, F · x), F). The family of these isomorphisms, for (P, x) varying in 𝔓_{difi}↓X_{difi}, is natural.

Form the full subcategory 𝔖 of 𝔓_{difi}↓X_{difi} whose objects are those elements of X_{difi} that are locally universal in X_{⊤}. Since X satisfies (iii), 𝔖 is in fact a sieve in 𝔓_{difi}↓X_{difi}, so that we have 𝔖↓(P, x) = (𝔓_{difi}↓X_{difi})↓(P, x) for all (P, x) ∈ 𝔖. Putting this equation together with the functors (5) and ρ_{P} τ_{P} we obtain a surjective equivalence

𝔖↓(P, x) [figure: ≈] P ∂  (6)

sending precisely the representation-preserving morphisms to identities.

Now choose a representative system for representation-preserving isomorphism in 𝔖 and form the corresponding full subcategory 𝔞. Since X satisfies (i), there are only small-many such classes, whence we may without loss of generality assume that 𝔞 ∈ Cat (justifying our use of a lower-case letter). For each (P, x) ∈ 𝔞 we consider the composite 𝔲_{(P,x)} of the inclusion 𝔞↓(P, x) [figure] 𝔖↓(P, x) and (6). We claim that it is an isomorphism of categories. It clearly is full and faithful, and in the next two paragraphs we show that it is bijective on objects as well.

Surjectivity. Each a ∈ P ∂ is the image under (6) of some ((Q, y), F) ∈ 𝔖↓(P, x). By choice of 𝔞 there are (Q′, y′) ∈ 𝔞 and a representation-preserving G : (Q′, y′) [figure: ≃] (Q, y) ∈ 𝔖. Put F′ = G · F. Then ((Q′, y′), F′) ∈ 𝔞↓(P, x) and G : ((Q′, y′), F′) [figure: ≃] ((Q, y), F) ∈ 𝔖↓(P, x), so that ((Q′, y′), F′) is mapped to a as well.

Injectivity. Suppose two objects ((Q_{i}, y_{i}), F_{i}) ∈ 𝔞 (i ∈ {0, 1}) are mapped to the same object of P ∂. Then some representation-preserving isomorphism G : ((Q_{0}, y_{0}), F_{0}) [figure: ≃] ((Q_{1}, y_{1}), F_{1}) is mapped to the associated identity. By choice of 𝔞 we have (Q_{0}, y_{0}) = (Q_{1}, y_{1}); so let us omit the subscripts here. Now G · y = y, so since y is locally universal in X_{⊤} (the only subtlety), we have G = 1_{Q} and further F_{0} = G · F_{1} = F_{1}.

The family of isomorphism

𝔲_{(P,x)} : 𝔞↓(P, x) [figure: ≃] P ∂

inherits the naturality of its defining factors. It thus determines a situation to which — a flourish! — axioms (Sl 2) and (Sl 3) apply. There are hence an object A with A∂ = 𝔞 (assuming repleteness) and a family of isomorphisms

U_{(P,x)} : A↓(P, x) [figure: ≃] P

with U_{(P,x)}∂ = 𝔲_{(P,x)}, natural for (P, x) varying in 𝔞. Inspecting the process from the start we find that in fact each U_{(P,x)} preserves representation and therefore is an isomorphism in 𝔓_{⊤}.

We wish to construct an invertible 𝔓-map ε : 𝔄(^{( )}𝔍, A) [figure: ≃]X. So let P ∈ 𝔓 and F : P [figure] A ∈ 𝔄. Consider the slice-object factorization

[figure: P; A↓(P′, x′); A; F^{⊤}; Δ_{(P′,x′)}^{A}]

of F and put (F)ε_{P} = F^{⊤} · U_{(P′,x′)} · x′. For H : Q [figure] P ∈ 𝔓 and H · F = G we have a commutative diagram

[figure: Q; A↓(Q′, y′); Q′; P; A↓(P′, x′); P′,; G^{⊤}; U_{(Q′,y′)}; F^{⊤}; U_{(P′,x′)}; H; A↓H′; H′]

where it is the functor τ_{A} : 𝔍↓A [figure] A∂ = 𝔞 that brings about the assignment

(H : (Q, G) [figure] (P, F)) [figure] (H′ : (Q′, y′) [figure] (P′, x′)).

From this it is clear that ε is 𝔓-natural. It remains to show that each ε_{P} is bijective.

We first show that ε_{P} is injective. Suppose (F_{0})ε_{P} = (F_{1})ε_{P}. That is, with the evident notational convention, F_{0}^{⊤} · U_{(P′_{0},x′_{0})} · x′_{0} = F_{1}^{⊤} · U_{(P′_{1},x′_{1})} · x′_{1}. Since both x′_{0} and x′_{1} are locally universal in X_{⊤}, they are isomorphic in 𝔓_{⊤}↓X_{⊤}. Since they also belong to the representative system chosen to obtain 𝔞, they in fact agree, say (P′_{i}, x′_{i}) = (P′, x′). Still by local universality of x′ we have F_{0}^{⊤} · U_{(P′,x′)} = F_{1}^{⊤} · U_{(P′,x′)}, whence F_{0}^{⊤} = F_{1}^{⊤} because U_{(P′,x′)} is invertible. But F_{i} = F_{i}^{⊤} · Δ_{(P′,x′)}^{A}, so we are done.

Finally we show that each ε_{P} is surjective. Since X satisfies (ii), it suffices to prove that every element locally universal in X_{⊤} is in the image of ε. By choice of the subcategory 𝔞 it even suffices to consider such elements as can be found there. Now if x ∈ X_{P} is such an element, we can put F = U_{(P,x)}^{−1} · Δ_{(P,x)}^{A}; then clearly F^{⊤} = U_{(P,x)}^{−1} and so (F)ε_{P} = x.

References

[1] Robin Cockett: ‘Notes on Polytopes’

[2] V. Harnik, M. Makkai, M. Zawadowski: ‘Multitopic sets are the same as many-to-

     one computads’, www.math.mcgill.ca/makkai

[3] C. Hermida, M. Makkai, A. J. Power: ‘On weak higher dimensional categories’, Journal of Pure and Applied Algebra; part 1: 154 (2000), 221–246; part 2: 157 (2001), 247–277; part 3: 166 (2002), 83–104

[4] M. Makkai: ‘The word problem for computads’, www.math.mcgill.ca/makkai [5] Thorsten Palm: ‘Dendrotopic Sets’, Galois Theory, Hopf Algebras, and Semiabelian

Categories, Fields Institute Communications, vol. 43 (American Mathematical Society, Providence, 2004), 393–443

[6] Thorsten Palm: ‘Dendrotopic Sets for Weak ∞-Categories’, Ph. D. dissertation, York University, Toronto (2003)

[7] D. Schumacher, R. Street: ‘Some parametrized categorical concepts’, Communications in Algebra 16 (1988), 2313–2347

[8] Ross Street: ‘Fibrations in bicategories’, Cahiers de topologie et géométrie différentielle 21 (1980), 111–160

Institut für Theoretische Informatik Technische Universität Braunschweig 38023 Braunschweig Germany

Email: palm@iti.cs.tu-bs.de

This article may be accessed at http://www.tac.mta.ca/tac/ or by anonymous ftp at

ftp://ftp.tac.mta.ca/pub/tac/html/volumes/22/5/22-05.{dvi,ps,pdf}

THEORY AND APPLICATIONS OF CATEGORIES (ISSN 1201-561X) will disseminate articles that significantly advance the study of categorical algebra or methods, or that make significant new contributions to mathematical science using categorical methods. The scope of the journal includes: all areas of pure category theory, including higher dimensional categories; applications of category theory to algebra, geometry and topology and other areas of mathematics; applications of category theory to computer science, physics and other mathematical sciences; contributions to scientific knowledge that make use of categorical methods. Articles appearing in the journal have been carefully and critically refereed under the responsibility of members of the Editorial Board. Only papers judged to be both significant and excellent are accepted for publication. 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, McGill University: gavin_seal@fastmail.fm

Transmitting editors.

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