Math. Struct. in Comp. Science (1991), vol. 1, pp. 1–20

Introduction to Distributive Categories

J.R.B. Cockett

Department of Computer Science University of Calgary

Received 9 September 1992

Distributive category theory is the study of categories with two monoidal structures one of which “distributes” over the other in some manner. When these are the product and coproduct this distribution is taken to be the law:

(A × B) + (A × C) ≃ A × (B + C)

which asserts that the obvious canonical map has an inverse. A distributive category is here taken to mean a category with finite products and binary coproducts such that this law is satisfied. In any distributive category the coproduct of the final object with itself, 1 + 1, forms a boolean algebra. Thus, maps into 1 + 1 provide a boolean logic: if each such map recognizes a unique subobject then category is a recognizable distributive category. If, furthermore, the category is such that these recognizers classify detachable subobjects (coproduct embeddings) then it is an extensive distributive category. Extensive distributive categories can be approached in various ways. For example recognizable distributive categories, in which coproducts are disjoint or all preinitials are isomorphic, are extensive. Also a category, X, having finite products and binary coproducts, satisfying the slice equation X × X ≃ X/1 + 1 (due to Schanuel and Lawvere) is extensive. The paper describes a series of embedding theorems. Any distributive category has a full faithful embedding into a recognizable distributive category. Any recognizable distributive category can be “solidified” faithfully to obtain an extensive distributive category. Any extensive distributive category can be embedded into a topos. A peculiar source of extensive distributive categories is those which arise as coproduct completions of categories with familial finite products. In particular, this includes the coproduct completion of cartesian categories, which is serendipitously therefore also the distributive completion. Familial distributive categories can be characterized as distributive categories for which every object has a finite decomposition into indecomposables.

CONTENTS

1 Introduction 2 Basic Definitions and Overview 3 Distributive Categories

3.1 Basic results

3.2 Decomposition to preinitials and solid objects 3.3 Disjointness 3.4 Solidification

4 Embedding Theorems 4.1 Local properties 4.2 Recognition properties 4.3 Characterizations of recognition 4.4 Extensive categories 4.5 Recognizable completion 4.6 Topos embedding

5 Familial distributive categories 5.1 Indecomposable objects 5.2 The family construction 5.3 Object decidability 5.4 The Burnside rig

6 Acknowledgements References

1. Introduction

The purpose of this paper is to give an overview of the results obtained during the first three months of 1990 in distributive category theory at the Sydney Category Seminar (SCS) and the Categories in Computer Science Seminar (CICS) held at the University of Sydney and Macquarie University. The nomenclature evolved since those original discussions and I have taken the liberty of bringing the exposition up to date in that respect. Although many proofs have been omitted, it has been the intent to leave sufficient detail so that proofs can be reconstructed when the results are not obvious from the development.

Distributive categories occur (it seems) all over mathematics. However, a primary motivation for this development was the potential computer science applications. It had been realized for some time that distributive categories are the correct formal setting for studying acyclic programs. In particular, the control aspects of programs, which have proved to be difficult to model equationally, are modeled precisely by the coproduct (sum or disjoint union) of distributive categories. Furthermore, distributive categories (and their analogues in finite sum sketches) provide a powerful language for abstract data structure specification. The coproduct is fundamental to almost all complex data structures and yet has often been absent in alternative specification methodologies.

The concept of initial algebra has tended to dominate the understanding of data structures in the computer science community. The negative results on the existence of initial algebras for distributive (or finite sum) theories, had a correspondingly negative effect on their acceptance as a viable tool. This is unfortunate as there is a perfectly good substitute for the initial algebra in the generic model. While this model does not live in Sets as it is a term model, it is a prefectly good model. Furthermore, as the use of term models is, by necessity, becoming an increasingly important conceptual tool in computer science, the generic model is in step these trends. Category theorists might go further to comment that it is the correct formal tool anyway: even for the equational theories which have initial algebras.

It is tempting to think that category theory simply provides nice theoretical models of computational settings. However, there is growing realization that category theory is also an important medium for computation. Thus, a constructive categorical setting can be implemented in much the same way that the λ-calculus can be implemented. Category theory then becomes a basis for specification and verification.

Distributive categories stand at a crossroads where such a program can become a reality as on the one hand they can have a direct computational reality and on the other they can embody many of the elementary geometric intuitions which underlie mathematical thought. The relationship between geometric intuition and computation can be used to enrich, facilitate, and elucidate software implementation.

2. Basic Definitions and Overview

There are two basic types of categories which are central to (cartesian) distributive category theory: Distributive categories: terminal object, binary products (i.e. finite products) and

binary coproducts where the binary products “distribute” over coproducts:

(A × B) + (A × C) ≡ A × (B + C).

This isomorphism is obtained by requiring that the canonical map

⟨i × b_{0}|i × b_{1}⟩ : (A × B) + (A × C)

be an isomorphism. This is the distributive property. Extensive (distributive) categories: Categories with finite products, binary coprod-

ucts, and pullbacks along coprojections such that

[figure: X; x; Z; y; Y; f; (1); h; (2); g; A; b_{0}; A + B; b_{1}; B]

(1) and (2) are pullbacks if and only if the top row, (Z, x, y), is a coproduct. This is the extensive property. It is, of course, the case that every extensive (distributive) category satisfies the dis-

tributive property.

Between these extremes lie a number of different variations obtained by demanding specific “local” properties. For example I shall discuss an intermediate concept, recognizable distributive categories, where the slice over 1 + 1 is required to be distributive. This implies that every slice over a sum of final objects (e.g. n = 1+1+...+1) is distributive and, thus, gives a fibration over finite sets.

I do not demand that distributive categories have an initial object (as does Bob Walters). An initial object, however, is sometimes useful and can always be demanded in addition. The gain in dropping the requirement is that some fairly natural examples, which definitely lack initial objects, are then covered.

Demanding that the extensive property holds does significantly affect the structure of the category. The extensive property in the form of a slice condition was introduced by Steve Schanuel at the Sydney category seminar in 1988. Extensive distributive categories have pullbacks over detachable subobjects (essentially coprojections), an initial object, and disjoint coproducts; unlike distributive categories they always have a full faithful embedding into a topos.

As for distributive categories one can demand that extensive categories have further local properties. An extensive distributive category would be locally extensive when every slice is extensive but this reduces to the additional demand of finitely completeness. These finitely complete categories were the categories investigated by Steve Schanuel and Bill Lawvere and they called them distributive categories: consequently they are often referred to as Schanuel/Lawvere distributive categories. These categories seem to crop up again and again in various disparate fields of mathematics.

The following diagram relates the 2-categories involved. Each arrow represents a psuedo 2-adjunction. The horizontal arrows have their units full and faithful functors while the vertical arrow have only faithful units. The process of passing from the distributive to the extensive property is called solidification. The process in some sense represents the passage from computational settings to geometric settings.

[figure: A × (B + C) ≃ (A × B) + (A × C); Dist; Dist_{rec}; Dist_{loc}; solidification; EDist; LEDist; T op; X/(A + B) ≃ X/A × X/B]

Dist is the 2-category of distributive categories with distributive functors, that is functors which preserve finite products and binary coproducts. Dist_{rec} is the 2-category of recognizable distributive categories with functors which are not only distributive but preserve recognition. Dist_{loc} is the 2-category of locally distributive categories with maps distributive functors which preserve recognition. EDist is the 2-category of extensive distributive categories with distributive functors. LEDist is the 2-category of Schanuel/Lawvere distributive categories with distributive functors. Finally Top is the 2-category of topoi with distributive functors.

Of particular interest is the problem of generating free distributive categories from various starting points. Bob Walters, with Shu-Hao Sun, studied this problem starting from:

•an arbitrary category,

•a category with products, •a distributive graph or sketch.

Steve Schanuel also studied the first of these problems and gave a “one step” construction as opposed to the two step construction (first freely add products then freely add coproducts) advocated by Bob Walters and Shu-Hao Sun. It turns out that using the “family” construction to freely add coproducts to a cartesian category automatically produces a distributive category (observed by Shu-Hao Sun). Indeed it is the free distributive category on the cartesian category. Rather different is the construction from a distributive graph: it is necessary to use essentially algebraic techniques to generate the initial free distributive category on the given data. One is assured from general principles that such exists because initial models for all finite limit sketches exist (designated products, coproducts, terminal, and initial are implied in these constructions and some extra argumentation is needed to remove such assumptions).

Free distributive categories in this sense have also been approached from the point of view of their term logic [Coc-89]. This gives yet another perspective. In particular, there are techniques for reducing the terms of this logic which process corresponds to optimizing the corresponding acyclic code.

A familial distributive category is a distributive category for which every object has a finite (possibly empty) decomposition as a finite coproduct of indecomposables. These categories are equivalent to the coproduct completion of the full subcategory of their indecomposables. The full subcategories, A, which are determined by the indecomposables of familial distributive categories, are precisely categories which have familial products. The coproduct completion, of course, is given by the “family” construction, which I write as S//A following Ross Street. The category A has familial products if and only if S//A has products. As this category embeds in the distributive category Sets^{A^{op}} preserving limits and colimits it must itself be distributive. Thus, a distributive category is a familial distributive category precisely if it is equivalent to S//A for some A: whence the name.

Familial distributive categories are always extensive. They provide a good source of both examples and counter-examples. G-Set_{f} provides a classic example of a familial distributive category. In fact, G-Set_{f} has in addition each object decidable. That is each object has a decomposition of its product as a diagonal and an off-diagonal. Extensive distributive categories with this property are finitely complete and so Schanuel/Lawvere distributive. In fact, familial distributive categories with decidable objects begin to look very like G-Set_{f} and have a number of interesting properties.

The distributive completion of a cartesian category is also an example of a familial distributive category. In fact the familial distributive category which results from the coproduct completion of a cartesian category can be characterized in various ways: as having indecomposables whose products are indecomposable or as having the component counting functor (which gives the familial fibration) distributive.

Familial distributive categories have (relatively) simple Burnside rigs (rings in which additive inverses are not assumed) which can always be faithfully extended to Burnside rings. This is another reason why they are of interest. In particular, the various rigs (and of course their ring counterparts) of G-Set_{f} have been extensively studied.

3. Distributive Categories

A distributive category is a category with finite products (including a final object) with binary coproducts such that the product distributes over the coproduct. Explicitly this means that the map

⟨b_{0} × i_{A}|b_{1} × i_{A}⟩ : B_{1} × A + B_{2} × A ⟶ (B_{1} + B_{2}) × A

is an isomorphism whose inverse is denoted

d_{0} : (B_{1} + B_{2}) × A ⟶ B_{1} × A + B_{2} × A.

It follows that

⟨i_{A} × b_{0}|i_{A} × b_{1}⟩ : A × B_{1} + A × B_{2} ⟶ A × (B_{1} + B_{2})

is invertible with inverse denoted by

d_{1} : A × (B_{1} + B_{2}) ⟶ A × B_{1} + A × B_{2}.

Note that a distributive category need not have an initial object. An interesting way in which a distributive category can arise is as the idempotent completion (otherwise known as the Cauchy or Karoubi completion) of a cartesian category. In particular, the idempotent completions of Bool, the theory of Boolean algebras, and Prim the formal theory of primitive recursive functions are distributive (and lack initial objects). The general conditions which cause the idempotent completion of a cartesian category to be distributive are discussed in [Coc-91].

3.1. Basic results

A fundamental observation concerning the coproduct in any distributive category is:

Lemma 3.1. In any distributive category coproduct coprojections are monic.

Proof. Suppose b_{0} : A ⟶ A + B and f, g : C ⟶ A with f.b_{0} = g.b_{0} then certainly

⟨p_{0}.f.b_{0}, i⟩ = ⟨p_{0}.g.b_{0}, i⟩ : C × A ⟶ (A + B) × (C × A)

but then

⟨p_{0}.f.b_{0}, i⟩.d_{0} = ⟨p_{0}.g.b_{0}, i⟩.d_{0} : C × A ⟶ A × (C × A) + B × (C × A)

where

⟨p_{0}.f, i⟩.b_{0} = ⟨p_{0}.f.b_{0}, i⟩.d_{0} = ⟨p_{0}.g.b_{0}, i⟩.d_{0} = ⟨p_{0}.g, i⟩.b_{0}

However the embedding

b_{0} : A × (C × A) ⟶ A × (C × A) + B × (C × A)

is certainly monic as it is a section of

⟨i|p_{1}.⟨p_{1}, i⟩⟩ : A × (C × A) + B × (C × A) ⟶ A × (C × A).

This means that ⟨p_{0}.f, i⟩ = ⟨p_{0}.g, i⟩ so that p_{0}.f = p_{0}.g and as this projection is a retract (with section ⟨i, f⟩) it follows f = g. Thus, the original b_{0} was monic.

This legitimizes the term embedding for coprojection.†

A distributive category does not require an initial object to be present nor must distributive functors preserve such an object. Despite this objects which are nearly initial play a key role.

A preinitial object is an object which has at most one map to each given object. A preinitial is strict if every object with a map to it is a preinitial object.

A preinitial may not be an initial object as it may not have a map to every object in the category. If the category has an initial object the preinitial objects are “epimorphs” of it and so might be regarded as “cotruth” values. Notice that an initial object is strict precisely when every map to it is an isomorphism. Also notice that a strict preinitial is a subobject of every object to which it has a map. Lemma 3.2. In a category with coproducts the following are equivalent:

(i) P is preinitial,

(ii) whenever there is a map p : P ⟶ X the embedding b_{0} : X ⟶ X + P is an isomorphism, (iii) b_{0} : P ⟶ P + P is an isomorphism, (iv) the codiagonal map ⟨i|i⟩ : P + P ⟶ P is an isomorphism,

(v) b_{0} = b_{1} : P ⟶ P + P.

The proof of these equivalences is straightforward. In a distributive category even more is true: Proposition 3.3. In any distributive category the following are equivalent:

(i) P is preinitial,

(ii) there is an object X such that b_{0} : X ⟶ X + P is an isomorphism,

: † This fact has often been overlooked: for example the definition of “universal disjoint coproducts,” occurring everywhere but probably originating from [SGA4], leads one to assume the requirement that the embeddings be monic is an independent requirement: this is not the case. In fact, as shall be seen, even the requirement of disjointness is not totally independent as universal coproducts are nearly disjoint.

(iii) !.b_{0} =!.b_{1} : P ⟶ 1 + 1.

Proof.

(i) ⇒ (ii) b_{0} : P ⟶ P + P is an isomorphism. (ii) ⇒ (iii) The square

[figure: P + X; ! + i; 1 + X; ! + i; =; b_{0} + i; 1 + X; b_{1} + i; (1 + 1) + X]

commutes as preceding the maps by b_{1} reduces them to the identity. But

!.b_{0}.b_{0} = b_{0}.⟨! + i⟩.⟨b_{0} + i⟩ = b_{0}.⟨! + i⟩.⟨b_{1} + i⟩ =!.b_{1}.b_{0}

now, using the fact that b_{0} is monic (notice that it is not necessary to use the result above for this as it is a section of ⟨i|!.b_{0}⟩) gives !.b_{0} =!.b_{1}.

(iii) ⇒ (i) If !.b_{0} =!.b_{1} : P ⟶ 1 + 1 then

[figure: P × P; i×!; P × 1; i×!; =; p_{0}.b_{0}; P × 1; p_{0}.b_{1}; P + P]

commutes. Notice that distribution over 1 + 1 has been used to obtain this diagram. This means p_{0}.b_{0} = p_{0}.b_{1} : P × P ⟶ P + P. However, this p_{0} is split by the diagonal and so is a retract. This shows that the embeddings are equal and that b_{0} = b_{1} : P ⟶ P + P, which shows that P is preinitial. The proof of the last equivalence (iii) ⇒ (i) is due to Mike Johnson, and was a signif-

icant improvement of the non-elementary proof of these facts that I gave. In particular notice that only this step requires distributivity and in fact only the distributivity of the product over 1 + 1. These various equivalent descriptions of preinitial allow the following observations: Corollary 3.4. In a distributive category

(i) preinitials are strict,

(ii) if an initial object exists, it is necessarily a strict initial object,‡

: ‡ Bob Walters originally gave the definition of a distributive category as having finite products and coproducts such that not only was the distributive law satisfied but also the law X × 0 ≃ 0. In retrospect, this is already implied.

(iii) if P is a preinitial and X is any object then P × X is preinitial,

(iv) if any preinitial exists, every object has a preinitial subobject,

(v) if the square

[figure: P; q_{0}; A; q_{1}; =; b_{0}; B; b_{1}; A + B]

commutes then P is preinitial.

3.2. Decomposition to preinitials and solid objects

A prelattice is a preorder with products and coproducts. A prelattice is unbounded if it lack a top and bottom.

Lemma 3.5. The full subcategory Pr(X) of preinitials of a distributive category is a, possibly unbounded, distributive prelattice.

A final preinitial is a preinitial object 0 such that every preinitial has a (necessarily unique) map to it. A distributive category is quasi-solid in case it has a final preinitial, and solid when this final preinitial is initial.

Observe that if a final preinitial is initial then every preinitial is isomorphic to it. As every object X in a quasi-solid distributive category contains a preinitial, namely p_{0} : X × 0 ⟶ X, a quasi-solid category in which all preinitials are isomorphic must be solid.

A solid object is one which has a (necessarily unique) map from the final preinitial 0 or, equivalently, has X + 0 ≡ X. If there is a final preinitial there is an obvious distributive functor, S, which reflects X faithfully into the full subcategory Solid(X) of solid objects. The category Solid(X) is isomorphic to the coslice category 0/X which is clearly solid. Similarly, Pr(X) is isomorphic to the slice category X/0 and so has a coreflection P.

Proposition 3.6. If X is a distributive category with a final preinitial, 0, then:

(i) P = − × 0 : X ⟶ Pr(X) is a distributive coreflection,

(ii) S = − + 0 : X ⟶ Solid(X) is a faithful distributive reflection to a solid full subcategory, (iii) ⟨P, S⟩ : X ⟶ Pr(X) × Solid(X) is a fully faithful distributive subdirect decomposition. The fact that the slicing and coslicing give rise to distributive functors relies heavily

on the fact that X is distributive. To prove that the decomposition is full, given h : X + 0 \overline{}Y + 0 and that P (X) ≤ P (Y), the following diagram is useful:

[figure: X + 0; h; Y + 0; p_{1}; =; p_{1}; b_{1}; =; X × (X + 0); i × h; X × (Y + 0); =; i + p_{1}; ⟨i, b_{0}⟩; d_{1}; ≅; X; =_{defn}; (X × Y) + (X × 0); p_{1} + i; Y + (X × 0); b_{0}; ≅; X; h′; Y]

Its purpose is to give the definition of a map h′ : X \overline{}Y such that h = h′ + i. To this end note that Y ≡ Y + X × 0 as P (X) ≤ P (Y), this means that the lowest polygon can be used to define h′.

The functor −+0 is the solidification functor. We shall return shortly to the problem of performing a solidification when no final preinitial is present.

Distributive categories can be viewed as full subcategories of the product of a solid distributive category and a prelattice. In fact, we will show that a distributive category is always a full subcategory of the product of a topos and a prelattice.

3.3. Disjointness

Coproducts are disjoint (respectively quasi-disjoint) in case all pullbacks of the form

[figure: b_{0} ∧ b_{1}; p_{0}^{b_{0}∧b_{1}}; A; p_{1}^{b_{0}∧b_{1}}; pb; b_{0}; B; b_{1}; A + B]

exist and b_{0} ∧ b_{1} is initial (respectively preinitial).

Observe that if

[figure: X; x_{0}; A; x_{1}; =; b_{0}; B; b_{1}; A + B]

commutes then certainly X is preinitial. Thus, if there is a largest preinitial with a map to both A and B that will be the pullback. When the category is quasi-solid this largest preinitial exists and is P (A)×P (B). This means that coproducts are quasi-disjoint. The converse is also true as the final preinitial is necessarily the pullback of the coproduct embeddings of 1 + 1. Proposition 3.7. A distributive category is (quasi-)solid if and only it has (quasi-)disjoint coproducts.

3.4. Solidification

To adjoin an initial object to a distributive category is trivial: one simply adds a new object ∅ together with a unique map to each object (the composition is then forced). However, adding a final preinitial is considerably more delicate. I shall now describe how this can be done using the general version of solidification.

Suppose that X is an arbitrary distributive category and F : X ⟶ Y a distributive functor to Y a quasi-solid distributive category. As Y can be subdirectly decomposed we have:

[figure: X; F; Pr(Y); P; Y; S; Solid(Y)]

If F l(X) is the reflection of X to prelattices and Solid(X) is the reflection to solid distributive categories then we can factorize F ∘ P and F ∘ S, respectively, through these categories:

[figure: F l(X); F l; X; S; Solid(X); ≃; F; ≃; Pr(Y); P; Y; S; Solid(Y)]

The quasi-solid completion of X can be constructed as the smallest full distributive subcategory of F l(X) × Solid(X) containing all objects of the form ⟨P_{X}(X), S_{X}(X)⟩, for X ∈ X, and the final preinitial ⟨P_{X}(1), 0⟩.

Notice that this shows that the preinitial lattice of the quasi-solid completion of X is equivalent to the flattening of X by reflection to preorders. This indicates the information the preinitial prelattice of a distributive category may contain.

It remains to construct Solid(X). This construction has two stages. First, an initial object, ∅, is adjoined (as discussed above). Second, all maps of the form b_{0} : X ⟶ X +P where P is preinitial, called thin detachments, are formally inverted to obtain a calculus of left fractions.

Let Σ now denote the class of thin detachments of a distributive category X, which has an initial object. It is easily checked that: Proposition 3.8. In any distributive category Σ admits a calculus of left fractions.

It follows that S_{X} : X ⟶ X(Σ^{−1}) preserves and creates finite colimits. In particular, as each b_{0} : ∅ ⟶ ∅ + P is inverted, it is clear that X(Σ^{−1}) has a strict final preinitial object and so is solid.

In general the category of fractions construction can turn a locally small category into one which is not locally small. This does not happen in this case as: Lemma 3.9. If f : X ⟶ X + P and g : X ⟶ Y + P′ and P and P′ are preinitial, then there is a g′ : X ⟶ X + P such that in X(Σ^{−1}) g.b_{0}^{−1} = g′.b_{0}^{−1}.

Proof. Define g′ by g′ = ⟨f, g⟩.γ.⟨p_{1} +p_{0}⟩, where γ : (Y +P)×(Y +P′) ⟶ (Y ×Y)+ (P × P′) is the evident isomorphism. It is easy to check that g′ has the desired property.

S_{X} : X ⟶ X(Σ^{−1}) is faithful as all inverted maps are bijections. Furthermore, X(Σ^{−1}) is the “solidification” of X as clearly any such process must at least invert the maps of Σ. This gives: Theorem 3.10. S_{X} : X ⟶ X(Σ^{−1}) ≡ Solid(X) is a faithful distributive functor to a solid distributive category and is such that given any distributive functor

F : X ⟶ Y

where Y is a solid distributive category there is a unique functor F^{∗} : Solid(X) ⟶ Y with S_{X} ∘ F^{∗} = F.

If X already has a final preinitial object, 0, then Solid(X) is equivalent to the full subcategory of strict objects as b_{0} : X ⟶ X +0 is in Σ and any b_{0} : X +0 ⟶ (X +0)+P is already an isomorphism.

Corollary 3.11. If X has a final preinitial Solid(X) ≡ X(Σ^{−1}) ≡ 0/X.

If F : X ⟶ Y is a faithful distributive functor and f.b_{0}^{−1}, g.b_{0}^{−1} : A ⟶ B in Solid(X) then using the lemma above we may alter g to a g′ having the same codomain as f in X. If f.b_{0}^{−1} ≠ g.b_{0}^{−1} then f.b_{0}^{−1} ≠ g′.b_{0}^{−1} but now S_{Y} (F (f)) ≠ S_{Y} (F (g′)) so that certainly Solid(F)(f.b_{0}^{−1}) ≠ Solid(F)(g.b_{0}^{−1}) showing that Solid(F) is faithful whenever F is.

Corollary 3.12. If F : X ⟶ Y is a faithful distributive functor between distributive categories then Solid(F) : Solid(X) ⟶ Solid(Y) is faithful.

These result shows that “solidification” is given by a “Koch-Zöberlien doctrine” in the terminology of [St-80] on the 2-category of distributive categories.

In case one is tempted to believe that solid distributive categories have a simple structure consider the following example, which provides a solid distributive category which cannot be embedded in a topos. Example: D[g] cannot be embeded in a topos

Consider the free distributive category, D[g], generated by the condition that g : X ⟶ Y + 1 equalizes i + b_{0}, i + b_{1} : Y + 1 ⟶ Y + (1 + 1) (that is g.⟨i + b_{0}⟩ = g.⟨i + b_{1}⟩). This category is non-trivial and has no preinitial objects. This can be seen as there is a model in Sets_{f}^{∗} × 2 (where 2 is ! : 0 ⟶ 1) given by (b_{0},!) : (1, 1) ⟶ (1, 0) + (1, 1). Notice that there is no map from (1, 1) to (1, 0) and the distributive category Sets_{f}^{∗} × 2 has no preinitials.

As D[g] has no preinitials we may adjoin an initial object, ∅, this category is now solid. However, in any topos it is easy to see that such a g must factor through the embedding b_{0}. Therefore, D[g] cannot be distributively embedded into a topos.

4. Embedding Theorems

In general when one has an elementary condition, such as the distributive law it is traditional to consider the effect of requiring it not only in the category itself but also in its slice categories. One then says that the category locally satisfies the condition. A variant of this is to ask that the condition be satisfied in some specified slices.

The object 1 + 1 in distributive categories forms a boolean algebra and is a natural candidate from which to build a internal boolean logic. The subobjects which can be described in this logic should be thought of as the “recursive” subobjects of the setting. More precisely they are subobjects for which there is a recognizer, where a subobject, a : A ⟶ X, has a recognizer χ_{a} : X ⟶ 1 + 1 whenever

[figure: A; a; X; !; pb; χ_{a}; 1; ⊤; 1 + 1]

is a pullback. Here ⊤ = b_{0}, ⊥ = b_{1} : 1 ⟶ 1+1. The recognizer of a subobject is distinct from the characteristic map. The latter is a map to a subobject classifier which may always exist: recognizers, of course, will not always exist. As 1 + 1 is a subobject of any (more general) subobject classifier, this internal logic will always be a restriction of any more general logic.

This “recognition” logic will only give information about the subobject structure of the category if subobjects corresponding to recognizers actually exist. We may guarantee this by requiring that the distributive category is local at 1+1, that is X/1+1 is distributive. Such a category has the necessary subobject structure to carry this logic and is called a recognizable distributive category.

4.1. Local properties

A map, f : X ⟶ Y, is quarrable if one can pullback along it. If, in addition, this pulling back preserves coproducts, that is f^{∗} : X/Y ⟶ X/X preserves coproducts, then f is said to be a locally coproductive. Pullbacks and compositions of locally coproductive maps are also locally coproductive.

An object, X, is said to be locally distributive if slicing at that object gives a distributive category, X/X. An object is locally distributive if and only if every map into that object is locally coproductive. Subobjects of locally distributive objects are locally distributive.

In any distributive category, the final object 1, is always locally distributive. To secure the correspondence between recognizers and subobjects it suffices we require that 1 + 1 be locally distributive. We shall interpret this as a requirement on that coproduct.

A coproduct (A + B, b_{0}, b_{1}) is quasi-extensive in case the embeddings are quarrable and given any

[figure: X; x; Z; y; Y; f; (1); h; (2); g; A; b_{0}; A + B; b_{1}; B]

where (1) and (2) are pullbacks the the top row, (Z, x, y), is a coproduct. It is said to be a extensive if, in addition, whenever (Z, x, y) is a coproduct (1) and (2) must be pullbacks.

If every coproduct is extensive then the category is extensive: this will be discussed in the next sections.

Notice that if (A + B, b_{0}, b_{1}) is a quasi-extensive coproduct then certainly the top row of the diagram will also be a quasi-extensive coproduct. I shall refer to (Z, x, y) as the coproduct induced by h over (A + B, b_{0}, b_{1}).

Lemma 4.1. A + B is locally distributive if and only if (A + B, b_{0}, b_{1}) is quasi-extensive, b_{0} and b_{1} are locally coproductive, and A and B are locally distributive.

If A + B is locally distributive then certainly A and B will be as they are subobjects. The maps b_{0} and b_{1} are locally coproductive as any map to a locally distributive object is. Finally, pulling back b_{0} and b_{1} along any map to A + B shows that (A + B, b_{0}, b_{1}) is quasi-extensive.

To obtain the reverse implication it is necessary to show that any map into A + B is coproductive. To show this for a map we form the coproduct induced the map into A+B and work with the components. In each component the map is locally coproductive, and the quasi-extensive property together with the coproductivity of the embeddings allows (by a tricky but straightforward pullback argument) the coproductivity of the components to be reconstituted into the coproductivity of the whole.

We note that pulling back f + g along b_{0} does not quite recapture the first component and this is the essential subtlety which we are being careful to capture:

Lemma 4.2. If the embedding b_{0} : A ⟶ A + B is locally coproductive and f + g : X + Y ⟶ A + B then b_{0} ∧ ⟨f + g⟩ ≡ X + P where P is a preinitial.

4.2. Recognition properties

A recognizable distributive category has a final preinitial given by the pullback ⊤ ∧ ⊥. Thus, the category has quasi-disjoint coproducts.

A subobject a : A ⟶ X is detachable if there is another subobject b : B ⟶ X with ⟨a|b⟩ : A + B ⟶ X an isomorphism. It is complemented if it is detachable and (preinitial) saturated, that is any preinitial P with P ⟶ X has P ⟶ A. As there is a final preinitial, a : A ⟶ X is saturated if and only if P (A) ≃ P (X). Furthermore, a subobject of X can always be saturated by adding P (X).

Lemma 4.3. In a recognizable distributive category if a : A ⟶ X is detachable there is a unique (to isomorphism) complemented subobject, ¬a : ¬A ⟶ X, such that ⟨a|¬a⟩ : A + ¬A ⟶ X is an isomorphism.

If ⟨a|b⟩ : A + B ⟶ X is an isomorphism then we may form

[figure: ¬A; ¬a; A + B; !; pb; !+!; 1; ⊥; 1 + 1]

by pullback. (¬A, ¬a) is both saturated and detachable (the latter because A+¬A ≡ A+ (B + P) ≡ X). Furthermore, ¬a : ¬A ⟶ X is independent of the choice of b : B ⟶ X, so any b : B ⟶ X with A + B ≡ X factors uniquely through ¬a : ¬A ⟶ X. In fact, as ¬A ≡ B + P for any such B, we have ¬A ≡ B when B is saturated.

This shows that the lattice of complemented subobjects of X, sub_{c}(X), is a boolean algebra. In fact, we have all but shown:

Proposition 4.4. In a recognizable distributive category X, 1 + 1 is a boolean algebra and ⊤^{∗} : X(X, 1 + 1) ⟶ Sub_{c}(X) is an isomorphism of boolean algebras.

This means complemented subobjects are represented by unique recognizers, recognizers are represented by unique (to isomorphism) complemented subobjects, and these representations are mutually inverse. The logic based on recognizers makes subobject sense when this happy coincidence reigns.

4.3. Characterizations of recognition

A coproduct (A + B, b_{0}, b_{1}) is saturated in case each of its components is. Every such coproduct occurs as a splitting of !+! over (1 + 1, ⊤, ⊥) this immediately means:

Lemma 4.5. In a recognizable distributive category all saturated coproducts have locally coproductive embeddings and are quasi-extensive.

Notice now that all components of a coproduct which contain an element (map from 1) are necessarily saturated. Thus in a recognizable distributive category any coproduct of final objects is locally distributive by the following structural induction: 1 is locally distributive and (1+...+1)+(1+..+1) is locally distributive if and only if its components are locally distributive (inductive assumption), its embeddings are locally coproductive, and the coproduct is quasi-extensive. The latter two properties are given by the previous lemma and the remark which started this paragraph. This leads to:

Proposition 4.6. If X is distributive, the following are equivalent

(i) X is recognizable,

(ii) (1 + 1, ⊤, ⊥) is quasi-extensive with each embedding locally coproductive, (iii) every saturated coproduct is splitting with each embedding locally coproductive, (iv) X/1 + ... + 1 distributive for all non-empty coproducts of the terminal object.

A coproduct is quasi-extensive if and only if

[figure: X/A + B; X/A + B; ⟨b_{0}^{∗}, b_{1}^{∗}⟩; ≃; +; X/A × X/B]

commutes to equivalence. When this is the case, ⟨b_{0}^{∗}, b_{1}^{∗}⟩ includes X/A + B into X/A × X/B as the full reflexive subcategory with objects saturated pairs (X, Y), that is having P (X) ≡ P (Y). This gives:

Proposition 4.7. If X is distributive, the following are equivalent:

(i) X is recognizable distributive,

(ii) ⟨⊤^{∗}, ⊥^{∗}⟩ : X/1+1 ⟶ X ×X is a coproductive inclusion of a reflexive subcategory, (iii) for every saturated coproduct ⟨b_{0}^{∗}, b_{1}^{∗}⟩ : X/A+B ⟶ X/A×X/B is a coproductive inclusion of a reflexive subcategory,

4.4. Extensive categories

A recognizable distributive category still does not necessarily have every detachable map complemented as not every detachable map need be saturated. This defect can be remedied by passing to the solid full subcategory. A solid recognizable distributive category is an extensive distributive category, however, this is not the preferred definition:§

An extensive distributive category is a cartesian category with binary coproducts such that for any A and B

+ : X/A × X/B \overline{}^{≅} X/A + B.

This can be simplified to the equivalent requirement that

+ : X × X \overline{}^{≅} X/1 + 1.

These conditions can be reexpressed as (A+B, b_{0}, b_{1}) is an extensive coproduct for any A and B and (1+1, ⊤, ⊥) is an extensive coproduct, respectively. For proving things about extensive distributive categories the former condition is most useful while for proving that something is an extensive distributive category the latter condition is the more useful.

Diagrammatically the former condition says:

: § In 1988 at the Sydney Category Seminar [SCS-88] Gordon Monro, following the work of Schanuel, explicitly studied the properties of distributive categories satisfying the extensive property without the assumption of finite completeness. He realized that they had very attractive properties especially from the point of view of studying recursive properties (particularly because detachable and complemented coincide). In 1990 I talked at Sydney Category Seminar about the recognizable completion and Gordon, realizing the connection, made available his notes. The current treatment is greatly influenced by those notes.

[figure: X; x; Z; y; Y; f; (1); h; (2); g; A; b_{0}; A + B; b_{1}; B]

(1) and (2) are pullbacks if and only if the top row, (Z, x, y), is a coproduct. This condition was, for example, used explicitly in the development of Mackey functors by Dress [Dress-73] and Lintner [Lint-76]. However, they also assumed that the category was finitely complete (which makes it a Schanuel/Lawvere distributive category).

If X is a solid distributive category then, whenever A + B is locally distributive, (A + B, b_{0}, b_{1}) will be extensive. If 1 + 1 is locally distributive then as every coproduct is obtained as the coproduct induced by !+! : A + B ⟶ 1 + 1 over (1 + 1, ⊤, ⊥) every coproduct will be extensive. Thus, a solid recognizable distributive category is an extensive distributive category.

Proposition 4.8. When X has finite products and binary coproducts, the following are equivalent:

(i) X is extensive,

(ii) X is solid recognizable distributive,

(iii) X is solid and has every coproduct quasi-extensive,

(iv) every coproduct is extensive,

(v) (1 + 1, ⊤, ⊥) is extensive.

One should not forget that the following are always pullbacks:

[figure: C × A; i × b_{0}; C × (A + B); p_{0}; C; p_{1}; pb; p_{1}; pb; !; A; b_{0}; A + B; !; 1]

The left square can be used to show that when coproducts are quasi-extensive the category is automatically distributive. Also observe that if every coproduct is extensive then pullbacks will preserve and be created by coproducts. More precisely:

Lemma 4.9. In an extensive distributive category the pullbacks

[figure: Z_{0}; x_{0}; X; Z_{1}; x_{1}; X; y_{0}; pb; f; y_{1}; pb; f; A_{0}; a_{0}; Y; A_{1}; a_{1}; Y]

exist if and only if the pullback

[figure: Z; x; X; y; pb; f; A_{0} + A_{1}; ⟨a_{0}|a_{1}⟩; Y]

exists, where

[figure: Z_{0}; x′_{0}; Z; x′_{1}; Z_{1}; y_{0}; pb; y; pb; y_{1}; A_{0}; b_{0}; A_{0} + A_{1}; b_{1}; A_{1}]

with x′_{0}.x = x_{0} and x′_{1}.x = x_{1}.

The proof of this is straightforward and simply uses the fact that any map to A_{0} + A_{1} results in the domain being split into a coproduct.

A coproduct is a extensive if and only if the two functors ⟨b_{0}^{∗}, b_{1}^{∗}⟩ and + are adjoint equivalences. In this case ⟨b_{0}^{∗}, b_{1}^{∗}⟩ is forced to be coproductive and this allows the results to be stated in terms of this functor. Proposition 4.10. When X has finite products and binary coproducts, the following are equivalent:

(i) X is a solid recognizable distributive category, (ii) X/A × X/B ≃ X/A + B for every A and B by + , (iii) X × X ≃ X/1 + 1 by + . These are the forms of the extensive property introduced by Steve Schanuel.¶

: ¶ In fact, both Schanuel and Monro demanded that there be an initial object and X/0 ≃ 1 (which is the requirement that 0 is a strict initial object). Both requirements are redundant: the initial object is ⊤ ∧ ⊥ and it is necessarily strict.

In an extensive distributive category a coproduct can be characterized as a regular epic family of mutually disjoint monic maps. Furthermore, monic maps from coproducts are given by mutually disjoint monic families: Proposition 4.11. The map ⟨a_{0}|a_{1}⟩ : A_{0} + A_{1} ⟶ X is monic if and only if a_{0} and a_{1} are monic and disjoint.

Notice that we are not guaranteed that the pullback a_{0} ∧ a_{1} exist in an extensive distributive category. The fact that it does is a component of the lemma. This makes the result a little more delicate than at first sight it may seem.

If ⟨a_{0}|a_{1}⟩ is monic then certainly a_{0} and a_{1} must be monic and disjoint. For the converse, we should consider the pullback of ⟨a_{0}|a_{1}⟩ over itself. This exists only as the pullbacks over each component does and

(a_{0} ∧ a_{0}) + (a_{0} ∧ a_{1}) + (a_{1} ∧ a_{0}) + (a_{1} ∧ a_{1}) = A_{0} + 0 + 0 + A_{1} = A_{0} + A_{1}

from which the result is immediate.

If an extensive distributive category has all diagonal maps detachable, then it is finitely complete, as equalizers are pullbacks over diagonals, and a distributive category in the sense of Schanuel and Lawvere. Proposition 4.12. An extensive distributive category with all objects decidable is finitely complete.

A functor of extensive categories should preserve the ingredients of the extensive property. In particular, a functor must preserve pullbacks along detachments. It is a nice observation that: Lemma 4.13. A distributive functor between extensive distributive categories preserves pullbacks over detachable subobjects.

Thus, we take the appropriate 2-category to be extensive distributive categories with distributive functors.

4.5. Recognizable completion

The purpose of this section is to describe the construction of the free recognizable distributive category from a distributive category. The construction has a number of important ramifications. Its purpose in this discussion is that it provides the crucial link between distributive and extensive categories.

Let X be a distributive category then denote by Rc(X) the following category: Objects: The objects are maps x : X ⟶ 1 + 1 of X, Maps: The maps are “almost commuting” triangles

[figure: X; g; Y; x; ⇒; y; 1 + 1]

where ⟨x, g.y⟩. ⇒= ⊤ where ⇒ is Boolean implication.

Define rc_{x}(g) := ⟨x, g⟩.d_{0}.⟨p_{1}+!⟩ then two maps g_{1}, g_{2} : f ⟶ h are equivalent if and only if rc_{x}(g_{1}) = rc_{x}(g_{2}).

Notice that the equivalence is to ensure that two maps are identified when their behaviors over the characterized parts are the same.

Theorem 4.14. For any distributive category, X, the recognizable completion Rc(X) is a recognizable distributive category which includes X distributively, fully, and faithfully by

R_{X} : X ⟶ Rc(X); X ⟶!_{X}.⊤.

Furthermore, given any distributive functor F from X to a recognizable distributive category Y, there is a unique to unique equivalence recognizable distributive functor

F̃ : Rc(X) ⟶ X

such that R ∘ F̃ ≃ F.

The construction is actually a limited equalizer completion and there are various reasons for considering this restriction. The main reasons derive from the economical nature of the construction.

If X is a category whose map equality predicate is decidable (externally) then Rc(X) also has a decidable map equality predicate. This can be seen directly from the construction: two maps g_{1}, g_{2} : x ⟶ y are equal precisely if rc_{x}(g_{1}) = rc_{x}(g_{2}) in X. This gives:

Corollary 4.15. If X has a decidable map equality predicate if and only if Rc(X) has its map equality predicate decidable.

The “only if” is due to the fact that X can be fully and faithfully embedded in Rc(X). This direction is particularly useful in proving the undecidability of X as one can often obtain such a proof more easily using the recognizable completion. The positive direction is also useful as the constructive decidability of X will often be easier to obtain than for the completion.

The proof of the main theorem may be accomplished in two stages. First by forming the category X/B, where B is the boolean algebra on 1 + 1 regarded as an internal cartesian category. This is certainly a distributive category. Next one quotients this category by the relation g_{1} ∼_{rc} g_{2} : x ⟶ y if and only if rc_{x}(g_{1}) = rc_{x}(g_{2}). Checking that this results in a category of the desired form is lengthy but straightforward. To obtain the desired universal property one uses X//B to obtain a functor and note that this functor factors uniquely through (X//B)/ ∼_{rc}.

In fact a good deal more can be taken through this construction: for example if X has list-arithmetic then Rc(X) will have list arithmetic. This will be reported in detail in a later paper and is beyond the scope of this introduction.

A useful observation which is needed in the construction of X//B is that the functor from the initial distributive category, Set_{f}^{∗}, preserves all the finite colimits and limits which exist. The latter fact is the more surprising and useful as this assures us that B is indeed an internal cartesian category. Furthermore, it is a consequence of a quite general result: Proposition 4.16. If Y is a distributive category which (has a faithful distributive embedding into an extensive distributive category, and) has all regular monics coretractions and all objects decidable, then any product preserving functor from Y preserves all limits.

As already has been mentioned, an object is decidable in a distributive category if its diagonal map is detachable. A distributive category with every regular monic either an isomorphism or detachable will have every regular monic a coretraction when every object is inhabited (has an element). Clearly Set_{f}^{∗} is such a category. Also distributive categories formed as a full subcategories generated by inhabited subsets of a natural number object have this property.

To prove this result we shall use the following technical lemma: Lemma 4.17. Suppose e′.x = x.e, where x is monic and e′ and e are idempotent then

[figure: e′ = i; p^{e′=i}; X; pb; x; e = i; p^{e=i}; Y]

is a pullback.

Proof. Let (X, (f, g)) be such that f.x = g.p^{e=i} then f.x.e = f.x so that f.e′.x = f.x giving f.e′ = f as x is monic. Thus, f factors through p^{e′=i} uniquely showing that this is a pullback.

The point of the lemma is that equalizers of idempotents with identities are always preserved by any functor (they are absolute limits). So provided the fact that x is monic is preserved by a functor then this pullback will necessarily be preserved: Corollary 4.18. If in the above x is a section then the above square is an absolute pullback.

This can now be used to obtain the proof of the proposition.

Proof. (of 4.16) As finite products are preserved it suffices to show that equalizers are also preserved. The equalizer of f and g can be expressed by requiring

[figure: f = g; p^{f=g}; X; ⟨p^{f=g}.f, p^{f=g}⟩; pb; ⟨f, g, i⟩; Y × X; ⟨p_{0}, p_{0}, p_{1}⟩; Y × Y × X]

to be a pullback.

Notice that both ⟨f, g, i⟩ and ⟨p_{0}, p_{0}, p_{1}⟩ are sections. p^{f=g} is certainly regular monic as it is the equalizer of f and g, so by assumption we have a retraction of p^{f=g} and an associated idempotent on e′ : X ⟶ X. Define e : Y × Y × X ⟶ Y × Y × X by

[figure: Y × X; ⟨p_{0}, p_{0}, p_{1}⟩; ⟨p_{0}, p_{0}, p_{1}⟩; Y × Y × X; e; Y × Y × X; ⟨c × i⟩; ⟨p_{0}, p_{0}, p_{1}⟩; C × X; p_{1}.⟨e′.f, e′⟩; Y × X]

where (Y × Y, ⟨i, i⟩, c) is the coproduct giving the detachment of the diagonal. Clearly e splits through ⟨p_{0}, p_{0}, p_{1}⟩.

I claim ⟨f, g, i⟩.e = e′.⟨f, g, i⟩ so that the lemma above can be applied. To see this embed the category faithfully into an extensive distributive category and follow through the maps on f = g and ¬f = g.

Amusingly, as Set_{f}^{∗} has a full faithful distributive embedding in Set_{f} we obtain that B is an internal cartesian category whence we can prove that every distributive has a faithful embedding in a extensive distributive category: implying that this condition can be removed from the proposition. The argument is as follows: the completion procedure allows us to pass fully and faithfully to a recognizable distributive category and whence, by solidification, faithfully to the full subcategory of strict objects. This full subcategory is extensive distributive and we obtain the faithful passage from distributive to extensive distributive.∥

: ∥ This faithful passage can be used to obtain many less than obvious results on distributive categories. A personal favorite is as follows: “No non-trivial distributive category has enough fixed points.” A map g : X ⟶ Y has a fixed point if there is an element fix(g) : 1 ⟶ X with fix(g) = fix(g).g. Consider ¬ : 1 + 1 ⟶ 1 + 1 suppose that fix(¬) : 1 ⟶ 1 + 1 exists. Embed into an extensive distributive category and form:

[figure: \frac{1}{2}; !; 1; !; pb; b_{0}; 1; fix(¬); 1 + 1]

It is worth noting that the recognizable completion of Set_{f}^{∗} is Set_{f}. The recognizable completion of Set_{f}, however, adds a new final preinitial object. This means that the procedure is nowhere idempotent (except on the degenerate category).

4.6. Topos embedding

If X is an extensive distributive category it forms a site with covers given by finite coproduct decompositions. These covers contain the identity, are stable and composable (in the terminology of [BW-85]) therefore they form a Grothendiek topology.∗∗ This topology is called the decomposition topology on X and is denoted d. The fact that coproducts are disjoint make it immediate that the representable functors are sheaves; that is, d is subcanonical.

The embedding Y : X ⟶ Set_{d}^{X^{op}} is certainly full and faithful and preserves any limits which happen to be present in X. Coproducts are also preserved as, being covers, they become jointly epimorphic families of subobjects which are mutually disjoint (the empty set is a cover of the initial object). Furthermore, in order for the embedding to preserve coproducts these families must certainly provide covers in the saturated topology.

Clearly, any topology stronger than d will result in Y being a distributive functor. In particular, the canonical topology will have this property. This gives: Proposition 4.19. If X is extensive distributive the Yoneda functor

Y : Set ⟶ Set_{j}^{X^{op}}

is a distributive functor if and only if j is stronger than d. Furthermore, d is a subcanonical topology.

This result shows that extensive distributive categories can be embedded in a topos and furthermore shows that the unit of the 2-adjunction to topoi is full and faithful.

Now every distributive category can be embedded fully and faithfully into a recognizable distributive category which in turn can be decomposed as a subdirect product of an extensive distributive category and prelattice (with possibly no lower bound). Finally an extensive distributive category can be embedded into a topos so we have: Corollary 4.20. Any distributive category has a full faithful distributive embedding into a product of a topos and a prelattice.

5. Familial distributive categories

An important problem for computer science applications is that of generating free distributive categories. One aspect of this problem concerns freely generating distributive

Now \frac{1}{2} + \frac{1}{2} ≃ 1 yet !.b_{0} =!. fix(¬) =!. fix(¬).¬ =!.b_{0}.¬ =!.b_{1} which means that \frac{1}{2} is preinitial. However, this means 1 is preinitial which means that the distributive category is trivial (in the sense of every object being preinitial). The result is of some classical importance as it has often been assumed that “sensible computer science” settings should have enough fixed points. Yet forcing fixed points to be present implies one cannot have sensible coproducts: I am not alone in believing this is shear stupidity!

: ∗∗ This a pretopology in the terminology of [John-77].

categories from cartesian categories, which correspond to equational theories. Surprisingly, the construction is simply the free coproduct completion, ignoring the cartesian structure (Shu-Hao Sun and Bob Walters [SCS-90]).

The generalization of this, which follows the ideas in Yves Diers thesis, is to consider categories which have familial products and equalizers. The coproduct completions of these more general categories are also distributive categories. They are characterized by each object having a finite coproduct decomposition into indecomposables and are called familial distributive categories. Surprisingly every familial distributive category is already extensive.

The fibration functor, which counts components, always preserves coproducts. However, it is not necessarily distributive as it may not preserve products. Indeed, it preserves coproducts only if products of indecomposables are indecomposable. In other words, the category is the coproduct completion of a cartesian category.

The category of G-Set_{f} is a good example of a familial distributive category. The product of two indecomposable G-sets is not indecomposable. Indeed, it is well-known that the Burnside rig, which describes the behavior of isomorphism classes of G-sets under the multiplication given by the product, provides useful information concerning the structure of the group.

5.1. Indecomposable objects

An object, A is indecomposable in a category if, whenever (Z, x, y) is a coproduct, any f : A ⟶ Z factors through either x or y but not both. If the category has coproducts this means, in particular, that indecomposables are not preinitial. In general we have the following characterization:

Proposition 5.1. A is indecomposable if and only if X(A, −) : X ⟶ Set preserves coproducts.

If the category is extensive there are a number of other characterizations of indecomposables. The following result is well-known (see [Dier-85] for example):

Proposition 5.2. In an extensive distributive category the following are equivalent:

(i) A is indecomposable,

(ii) Sub_{c}(A) = 2,

(iii) any map f : A ⟶ 1 + 1 factors through ⊤ or ⊥ but not both, (iv) whenever A ≃ X + Y either X or Y is 0 but not both,

(v) X(A, −) : X ⟶ Set is a distributive functor.

The following analogue of the Krull-Schmidt lemma for modules of a ring is true:

Lemma 5.3. In a redistributive category, if A is indecomposable and ⟨c_{0}|c_{1}⟩ : A +

C \overline{}^{≅} A + B then B ≃ C.

This can be obtained by examining the following diagram:

[figure: b_{0} ∧ c_{0}; A; b_{1} ∧ c; pb; c_{0}; pb; A; b_{0}; A + B; b_{1}; B; pb; c_{1}; pb; c_{1} ∧ b_{0}; C; c_{1} ∧ b_{1}]

Each row and column is a coproduct. Either b_{0} ∧ c_{0} ≃ A or c_{1} ∧ b_{0} ≃ b_{1} ∧ c_{0} ≃ A in either case B ≃ C.

An indecomposable (coproduct) decomposition of an object X is given by a pair ([A_{1}, ..., A_{n}], α), consisting of a list of indecomposable objects together with an isomorphism α : A_{1} + ... + A_{n} ⟶ X given by the detachments α_{i} : A_{i} ⟶ X. As is the case for modules we can now prove:

Corollary 5.4. In an extensive distributive category if ([A_{1}, ..., A_{n}], α) and ([B_{1}, ..., B_{m}], β) are indecompsable decompositions of X then n = m and there is a permutation σ and isomorphisms ρ_{i} : A_{i} ⟶ B_{σ(i)} such that α_{i} = ρ_{i}.β_{σ(i)}.

Thus, any two decompositions to indecomposables in an extensive distributive category are equivalent.

If X is a distributive category with an initial object in which every object has a finite indecomposable decomposition (including the empty decomposition) then we shall call it a familial distributive category. In particular note that the decomposition of 0 is ([], 0_{0}) and there can be no other preinitials non-isomorphic 0 as they would have the same decomposition and so would be isomorphic. Thus, a familial distributive category is certainly solid.

Proposition 5.5. Familial distributive categories are extensive.

To prove this it suffices to prove that (1 + 1, ⊤, ⊥) is splitting. However, any f : X ⟶ 1 + 1 can be decomposed as ⟨f_{1}|...|f_{n}⟩ : X_{1} + ... + X_{n} ⟶ 1 + 1 where each X_{i} is indecomposable. This means that each f_{i} : X_{i} ⟶ 1 + 1 factors through either ⊤ or ⊥. Suppose X_{1}, ..., X_{r} factors through ⊤ and X_{r+1}, ..., X_{n} factor through ⊥ then I claim:

[figure: X_{1} + ... + X_{r}; X; X_{r+1} + ... + X_{n}; !; pb; f; pb; !; 1; ⊤; 1 + 1; ⊥; 1]

Certainly each square commutes. Considering any map h : Z ⟶ X it is determined by the maps from its the indecomposables in its decomposition h_{i} : Z ⟶ X. However, each such map must factor through one indecomposable component of X. If h.f =!.⊤ then each component must factor through one of X_{1}, ..., X_{r} and thus the left square is a pullback. Similarly, the right square is a pullback.

5.2. The family construction

Let S : D_{0} ⟶ Set denote the initial functor of distributive categories with an initial object to Set. Thus, S gives an equivalence to Set_{f}. We may take D_{0} as also being initial in the category of elementary distributive categories with functors which preserves designated coproducts so that the objects of D_{0} are coproduct “shapes” of the form (1 + 1) + (1 + (1 + 1)).

Given any category X then the internal categories of X form a 2-category cat(X). In particular the objects of X form discrete categories so that given any internal category C one may form the category whose objects are functors from discrete categories to C and whose maps are pairs (t, α) : f ⟶ g, where t is a functor between the discrete categories (i.e. a map between the objects) and α : f ⇒ t.g is a natural transformation. This category is denoted X//C, and is called the double slice category over C. It is an example of a “super comma category” [MacL-71] and is discussed in [Schu-88] as it gives rise to a fibration over X.

We may further refine this by considering any functor F : Y ⟶ X then by F//C is meant the category whose discrete objects are in Y but whose natural transformations are given in the obvious manner in X.

If A is a small category it is an internal category in Set, so we may form S//A. Explicitly, the objects of this category are maps x : S(X) ⟶ A_{0}, while the maps are given by pairs (f_{0}, f_{1}) where f_{0} : X ⟶ Y and f_{1} : X ⟶ A_{1} such that:

[figure: S(X); f_{0}; S(Y); f_{1}; x; A_{1}; y; δ_{0}; δ_{1}; A_{0}]

x = f_{1}.δ_{0} and S(f_{0}).y = f_{1}.δ_{1}.

This category is also sometimes denoted F am(A) and is called the category of families of A. Notice that each object of S//A may be regarded as consisting of a shape together with a labeling of the leaves of that shape by the objects of A. As such there is a natural extension of any functor of A into a category with designated coproducts which takes these labeled shapes to the designated coproducts and the maps to the obvious coproduct comparison maps. This gives: Proposition 5.6. S//A is the free (designated) coproduct completion of A.

A category, A, is said to have familial finite products if for every A_{1}, ..., A_{n} the category of discrete cones A/(A_{1}, ..., A_{n}) has finitely many connected components and a final object in each component. Each such final object I shall call a familial product of A_{1}, ..., A_{n} in A. In particular, the components of A/() are the components of A each of which must have a final object, each of which I shall call a familial final object of A.

A has familial finite products if and only if S//A has actual finite products. It can be seen that this product distributes over the coproduct in two ways. First, the coproduct completion is a full faithful subcategory of Set^{A^{op}} and the products are preserved in this embedding so they certainly distribute over the coproduct. Second, notice that the familial products of A give a functor − × − : A × A ⟶ S//A which can be extended “bilinearly” to the coproduct completion in each coordinate. This functor (− × −)^{∗} : S//A × S//A ⟶ S//A gives the products in S//A and, by construction, it preserves coproducts in each coordinate showing that S//A is distributive. Proposition 5.7. S//A is an distributive category if and only if A has familial finite products.

There is an obvious coproduct preserving functor δ : S//A ⟶ S which simply forgets the structure given by A. This allows one to regard the situation as a fibration [Schu-88]. In particular, the category A can be recaptured as the fibre over 1. This also allows the observation that each object of A becomes indecomposable in S//A as 1 is indecomposable in D_{0} and Ind(S//A), the full subcategory of indecomposables in S//A, is simply A. Furthermore, each object in S//A has, by definition, a finite indecomposable decomposition, which shows: Corollary 5.8. If A has familial products then S//A is extensive distributive .

If A is cartesian, so that it has finite products, then certainly it has familial products. Furthermore, any functor H : A ⟶ X of A to a distributive category X having an initial object which preserves products has its extension H^{+} : S//A ⟶ X a functor which preserves coproducts. This gives: Corollary 5.9. If A is cartesian the free distributive completion is S//A^{∗}.

Furthermore, observe that in this case products of indecomposables are indecomposable, so that: Corollary 5.10. If A is cartesian if and only if

(i) products of indecomposables are indecomposable in S//A, (ii) δ : S//A ⟶ S is distributive. While δ is distributive for cartesian A it will not in general preserve all finite limits. For

example, we may take A to be an algebraic theory with two distinct elements 1 [figure: 1]^{0} A (e.g. the theory of rings). In S//A the map ⟨0|1⟩ : 1 + 1 ⟶ A is monic. It is easily seen that δ does not preserve this monic by counting components. This should be a sharp reminder that distributive functors between extensive categories need not behave well on arbitrary limits.

So far we have seen that every S//A, where A has familial finite products, is familial distributive. In fact, the converse is also true, to equivalence: Theorem 5.11. X is familial distributive if and only if X ≃ S//A where A has familial finite products. Furthermore, A ≃ Ind(X).

Clearly as each object has an indecomposable decomposition it can be regarded as a family of indecomposable objects. Furthermore, the maps between objects can also be represented familially and this shows S// Ind(X) ≃ X. Any equivalence of categories will carry indecomposables onto indecomposables, so that the A of the theorem is always equivalent to Ind(X).

This means in discussing familial distributive categories one can equivalently deal with categories with familial finite products. This alternate view of familial distributive categories is sometimes fruitful.

5.3. Object decidability

S//A has finite limits, and so is distributive in the sense of Schanuel and Lawvere, if and only if A has familial finite limits. It is obvious that X is a finitely complete familial distributive category if and only if Ind(X) has familial finite limits. Furthermore, every slice X/X is a finitely complete familial distributive category. From which one can deduce that a category is has familial finite limits if and only if each slice has familial products.

We have noted that one way in which a Schanuel and Lawvere distributive category arises naturally from an extensive distributive category is when every object is decidable.

Familial distributive categories in which every object is decidable have a number of interesting properties.

Notice that equalizers are detachable when every object is decidable. This means that maps to indecomposables must either be epic or initial. Similarly, considering the equalizer of two maps from an indecomposable: either they are equal everywhere or nowhere. A rather striking observation is that graphs of maps are detachable giving:

Lemma 5.12. In an internally decidable familial distributive category there are only finitely many maps between any two objects.

In particular, considering an endomorphism, f : A ⟶ A of an indecomposable object A, because there are only finitely many endomorphisms, it follows that f^{n} = f^{m} for some n ≠m. Using the fact that f is epic we obtain f^{n−m} = i, so that f is an isomorphism. This provides an anologue of Schur’s lemma:

Proposition 5.13. In internally decidable familial categories all endomorphisms of indecomposables are isomorphisms.

This has the following rather surprising consequence:

Corollary 5.14. A category A with familial products has all objects S//A decidable if and only if A has no non-trivial idempotents.

If S//A is internally decidable then every idempotent of an indecomposable must be an isomorphism, whence the identity. Conversely, consider the component of the product into which the diagonal map embeds: the composition of a projection and the diagonal map provide an idempotent on that component. If it is trivial then this component must be the diagonal, giving decidability of the object.

5.4. The Burnside rig

The isomorphism classes of objects of any elementary distributive category under the sum and product form a (commutative) rig which is called the Burside rig.†† A rig is a quintuple, R = (R_{0}, 0, 1, +, ×), where R_{0} is the underlying object, 0 and 1 are constants and identities for + and × which are associative binary operations with + commutative and × distributing over +. A rig is commutative if × is commutative and cancellative if x+z = y+z ⇒ x = y. Notice that in a cancellative rig a×0 = 0 as 0+a×0 = a×0+a×0.

There is a reflection of rigs into rings which uses the following construction:

Let R be a rig then define the following rig structure on R(R) = R × R/ ∼:

(x, y) + (x′, y′) = (x + x′, y + y′)
(x, y) × (x′, y′) = (x × x′ + y × y′, x × y′ + y × x′)

with equivalence relation given by:

(x, y) ∼ (x_{1}, y_{1}) ⇔ x + y_{1} + z = y + x_{1} + z.

: †† This name is due to Steve Schanuel and Bill Lawvere and is a ring without negatives.

for some z. Clearly R(R) is a ring and gives the reflection of rigs to rings. It is immediate from this construction that cancellative rigs can be embedded faithfully into their enveloping ring.

It is of some interest to uncover conditions under which the Burnside rig of a distributive category is cancellative. Clearly we must have X + A ≃ Y + A ⇒ X ≃ Y. However, notice that this is a version of the Krull-Schmidt lemma and is clearly satisfied by any A which is a finite coproduct of indecomposables. An immediate observation is:

Proposition 5.15. The Burnside rig of a familial distributive category is cancellative and so embeds faithfully into the Burnside ring.

The Burnside rig of a familial distributive category is the free additive semi-group generated by indecomposables with multiplication given by equations of the form:

a × a′ = a_{1} + ... + a_{n}

derived directly from the familial products.

6. Acknowledgements

The original form of this document was written while I was a research fellow at Macquarie University being supported by the Australian Research Council. Contributions to this work were made by the participants of the various Sydney category theory seminars which included: Mike Johnson, Max Kelly, Gordon Monro, Ross Street, Michel Thiebaud, and Bob Walters. I particularly wish to acknowledge the influence and encouragement of Ross Street throughout my stay in Sydney.

REFERENCES

BW-85 M. Barr and C. Wells, Toposes, triples and theories, Grundlehren der mathematischen

Wissenschaften 278, Springer-Verlag, Berlin, Heidelberg, New York(1985). Coc-89 Cockett, J.R.B. Distributive logic. University of Tennessee, Department of Computer

Science, Technical Report. CS-89-01 (1989). Coc-91 Cockett, J.R.B. Conditional control is not quite categorical control, in Graham Birtwistle

(Ed.) IV Higher Order Workshop, Banff 1990 Workshops in Computing, Springer-Verlag (1991) 190-217.

Dier-85 Y. Diers Categories of boolean sheaves of simple algebras, Lecture Notes in Mathematics

1187, Springer-Verlag, Berlin, Heidelberg, New York(1985). Dress-73 A. W. M. Dress Contributions to the theory of induced representations, in “Algebraic

K-Theory II”, Lecture Notes in Mathematics 342, Springer-Verlag, Berlin, Heidelberg, New York183-240 (1973).

GZ-67 P. Gabriel, M. Zisman Calculus of fractions and homotopy theory. Ergebnisse der Mathematik und Ihre Grenzgebiete, New Series, Vol. 35, Springer-Verlag, Berlin, Heidelberg, New York(1967).

SGA4 A. Grothendiek and J.L. Verdier, Théorie des topos, (SGA 4, exposé I-IV). Second edition, Lecture Notes in Mathematics 269-270, Springer-Verlag, Berlin, Heidelberg, New York(1972).

Robin Cockett 32

John-77 P.T. Johnstone, Topos theory, Academic Press, London, New York, San Francisco

(1977). Lint-76 H. Lintner A remark on Mackey-functors, manuscripta math. 18,275-278 (1976). MacL-71 S. Mac Lane Categories for the working mathematician, Springer-Verlag, Berlin, Hei-

delberg, New York(1971). St-80 R. H. Street Fibrations in bicategories, Cahiers de Topologie et Géométrie Différentielle,

21 (1980), 111-160. Schu-88 D. Schumacher, R. H. Street Some Parameterized Categorical Concepts, Communica-

tions in Algebra, 16(11), 2313-2347 (1988). SCS-88 Sydney category seminar abstracts (1988). SCS-90 Sydney category seminar abstracts (1990).