Reference Introduction to extensive and distributive categories [carboni-lack-walters-extensive]

Abstract

  • February 3, 1993
  • Aurelio Carboni, Stephen Lack, R. F. C. Walters

In recent years, there has been considerable discussion as to the appropriate definition of distributive categories. Three definitions which have had some support are: (1) A category with finite sums and products such that the canonical map δ:A×B+ A×C→A×(B+C) is an isomorphism (Walters). (2) A category with finite sums and products such that the canonical functor +:A/A× A/B→A/(A+B) is an equivalence (Monro). (3) A category with finite sums and finite limits such that the canonical functor + of (2) is an equivalence (Lawvere and Schanuel). There has been some confusion as to which of these was the natural notion to consider. This resulted from the fact that there are actually two elementary notions being combined in the above three definitions. The first, to which we give the name distributivity, is exactly that of (1). The second notion, which we shall call extensivity, is that of a category with finite sums for which the canonical functor + of definitions (2) and (3) is an equivalence. Extensivity, although it implies the existence of certain pullbacks, is essentially a property of having well-behaved sums. It is the existence of these pullbacks which has caused the confusion. The connections between definition (1) and definitions (2) and (3) are that any extensive category with products is distributive in the first sense, and that any category satisfying (3) satisfies (1) locally. The purpose of this paper is to present some basic facts about extensive and distributive categories, and to discuss the relationships between the two notions. 

 @article
{carboni-lack-walters-extensive, title={Introduction to extensive and distributive categories}, volume={84}, ISSN={0022-4049}, DOI={10.1016/0022-4049(93)90035-R}, number={2}, journal={Journal of Pure and Applied Algebra}, author={Carboni, Aurelio and Lack, Stephen and Walters, R. F. C.}, year={1993}, month={Feb}, pages={145–158} }

Backlinks

The Universal Property of Measure-Theoretic Probability › Distributive and extensive Markov Categories [efr-MGSE]

We will need to impose a few different categorical properties on our Markov categories. These are analogues of preexisting properties of ordinary categories, but will typically need to be modified somewhat to suit Markov categories. The usual pattern is to demand that \mathcal {C}_\mathrm {det} has some property, and that this is preserved by the inclusion into \mathcal {C}. In this section we will describe these conditions.

For background on extensive and distributive categories, see Reference [carboni-lack-walters-extensive]. For background on Boolean categories, see Reference [johnstone-elephant-vol1], section A1.4. Reference [chen-universal-stdborel-2019] also contains a review of these terms and the relations between them that suffices for this paper.

The list of hypotheses we will chiefly be interested in is the following:

  1. \mathcal {C}_\mathrm {det} is Boolean, countably complete and (countably) extensive (so that it receives a unique functor from \mathsf {Borel} by Chen's theorem).
  2. The inclusion \mathcal {C}_\mathrm {det} \hookrightarrow \mathcal {C} preserves the countable coproducts, the pullbacks along coproduct inclusions (hence all monomorphisms), and carries the countable products to Kolmogorov products.

There are various ways we can break this up into sub-assumptions. For example, if \mathcal {C} admits Kolmogorov products of a given cardinality, \mathcal {C}_\mathrm {det} admits products of that cardinality. So if \mathcal {C} has countable Kolmogorov products and \mathcal {C}_\mathrm {det} has pullbacks along monomorphisms, \mathcal {C}_\mathrm {det} has all limits.

Remark

  1. In the Cartesian case, if \mathcal {C} is Boolean, countably complete and extensive, then it is also countably extensive (Reference [chen-universal-stdborel-2019], Lemma 2.5). However, the proof of this relies on identifying morphisms X \to Y with their graphs (subobjects of X \times Y), and applying our knowledge about the subobject lattice. In the Markov context, we can not necessarily identify a morphism with a deterministic subobject of X, hence this argument does not work—to be precise, \mathcal {C}_\mathrm {det} will have all countable coproducts but the inclusion will not necessarily preserve them. If \mathcal {C} is representable, the inclusion preserves all colimits and this limitation disappears.
  2. Let \mathcal {C}, \mathcal {D} be Markov categories with countable Kolmogorov products, so that \mathcal {C}_\mathrm {det}, \mathcal {D}_\mathrm {det} is countably extensive and Boolean, and the inclusions preserve the countable coproducts, and let F: \mathcal {C} \to \mathcal {D} be a strong Markov functor. Suppose F_\mathrm {det} : \mathcal {C}_\mathrm {det} \to \mathcal {D}_\mathrm {det} preserves countable limits and finite coproducts. Then it automatically preserves countable coproducts as well (again, by Chen's argument). Since these are also countable coproducts in \mathcal {C}, \mathcal {D}, it follows that F preserves countable coproducts as well.

Definition [efr-T0AU]

A Markov category is distributive (\kappa -distributive) if \mathcal {C}_\mathrm {det} admits finite (\kappa -small) coproducts, these are preserved by the inclusion \mathcal {C}_\mathrm {det} \hookrightarrow \mathcal {C}, and by the tensors A \otimes -.

In a distributive monoidal category, if A,B are each comonoids, then A+B acquires an induced comonoid structure given by A + B \to A \otimes A + B \otimes B \hookrightarrow (A+B)\otimes (A+B) If \mathcal {C} is a Markov category, each of these objects has furthermore a canonical given comonoid structure. \mathcal {C} is distributive as a Markov category if and only if the coproducts can be chosen so that the canonical comonoid structure coincides with the induced one.

This parametrization in a regular cardinal \kappa will recur a few times in this paper. We are chiefly interested in the cases \kappa = \omega , corresponding to finite coproducts, and \kappa = \omega _1, corresponding to countable coproducts (this case requires a weak form of the axiom of choice).

Definition Extensive Markov Category [efr-B2P7]

A Markov category is said to be an extensive Markov category if it admits finite coproducts, whose injections are deterministic, and which satisfy the following equivalent conditions:

  1. If we let \mathcal {C}_{/a}^\mathrm {det} refer to the full subcategory of the slice spanned by the deterministic morphism x \to a, we have an equivalence of categories \mathcal {C}_{/a}^\mathrm {det} \times \mathcal {C}_{/b}^\mathrm {det} \cong \mathcal {C}_{/a + b}^\mathrm {det}, given by taking coproducts
  2. \mathcal {C}_\mathrm {det} is an extensive category in the usual sense and the inclusion \mathcal {C}_\mathrm {det} \to \mathcal {C} preserves pullbacks along coproduct inclusions.

More generally, for an infinite regular cardinal \kappa , we say that \mathcal {C} is \kappa -extensive if \mathcal {C}_\mathrm {det} is a \kappa -extensive category in the ordinary sense and both coproduct inclusions and pullbacks along them are preserved by the functor \mathcal {C}_\mathrm {det} \to \mathcal {C}.

Note that any extensive Markov category is automatically distributive (for the same \kappa ). Note also that if \mathcal {C} is extensive Markov, then \mathcal {C}_\mathrm {det} automatically admits all finite limits, since it has finite products just by virtue of being a Markov category.

Recall that a coherent category is called Boolean if every subobject lattice is a Boolean algebra. Also note that an extensive category is Boolean (and coherent) as soon as it satisfies the condition that every monomorphism V \hookrightarrow X is a coproduct inclusion (the object V' so that A = V + V' is then the complement subobject of V). We will not need to study any other case than this, and so we simply make the following definition.

Definition Boolean Markov category [efr-7JNJ]

An extensive Markov category \mathcal {C} is Boolean (as a Markov category) if \mathcal {C}_\mathrm {det} is Boolean, i.e if every monomorphism in \mathcal {C}_\mathrm {det} is a coproduct inclusion.

In the common case that \mathcal {C} is the Kleisli category of a monad on \mathcal {C}_\mathrm {det}, the inclusion \mathcal {C}_\mathrm {det} \hookrightarrow \mathcal {C} automatically preserves all colimits, which makes many of the above things automatic.

Lemma [efr-198L]

Let \mathcal {C} be a representable Markov category, and let P be the associated distribution monad. Then

  1. If \mathcal {C}_\mathrm {det} is \kappa -extensive and P: \mathcal {C}_\mathrm {det} \to \mathcal {C}_\mathrm {det} preserves pullbacks along coproduct inclusions, then \mathcal {C} is \kappa -extensive.
  2. If \mathcal {C}_\mathrm {det} is Boolean, then \mathcal {C} is Boolean.
  3. If \mathcal {C}_\mathrm {det} is (finitely) extensive, Boolean, and \kappa -complete, and P: \mathcal {C}_\mathrm {det} \to \mathcal {C}_\mathrm {det} preserves the cofiltered limits \prod _{i \in J} A_i = \lim _{F \subseteq J \mathrm { finite}} \prod _{i \in F} A_i for |J| < \kappa , then \mathcal {C} is \kappa -extensive (and Boolean and admits \kappa -small Kolmogorov products).

Remark [efr-GZCD]

We will characterize \mathsf {BorelStoch} as the initial Markov category which is countably extensive, Boolean, admits countable Kolmogorov products, and a coinflip. Let us say a few words justifying these axioms as natural. Extensivity is a property of most categories of "spaces", and the requirement that \mathcal {C}_\mathrm {det} \hookrightarrow \mathcal {C} preserves coproducts and pullbacks along monomorphisms holds in essentially every Markov category of interest.

However, Boolean categories are a bit more uncommon. In the presence of extensivity, Boolean-ness is equivalent to I + I being a subobject classifier - the obstruction to this typically being that "the" indicator of many subobjects are discontinuous.

A common assumption about Markov categories is the presence of conditionals (Reference [fritz-synthetic-markov-cats] 11.5). If V \hookrightarrow X is a subobject, and I \to I + I, I \to V, I \to X are distributions of full support, then a Bayesian inverse of their pairing I + I \to X is forced to have a discontinuity at the boundary of V.

While this does not rise to the level of a formal argument that conditionals imply Boolean (it seems very hard to imagine such an argument, since conditionals are only defined up to almost sure equality, and measures with full support don't always exist, for example, in \mathsf {BorelStoch}), it does demonstrate the difficulties involved in admitting conditionals without being Boolean.

Proposition [efr-GY4W]

\mathsf {BorelStoch} is countably extensive and Boolean.

Proof

Note first that \mathsf {Borel} is countably extensive and Boolean, by Reference [chen-universal-stdborel-2019] theorem 1.1. Hence it suffices to observe that the Giry monad preserves pullbacks along coproduct inclusions. Consider X \to A + B. The claim is that the square

is a pullback, where X_A is the preimage of A inside X. But this is clear: a probability measure on A is exactly a probability measure on A + B which happens to be concentrated on A, and a probability measure on X has an image in G(A + B) of this form if and only if it is concentrated on X_A (and is such equivalent to a measure on X_A).