nLab free coproduct completion

Contents

Contents

Idea

Given a category π’ž\mathcal{C}, its free coproduct completion (or free sum completion) is the category PSh βŠ”(π’ž)PSh_{\sqcup}(\mathcal{C}) (often denoted Fam(π’ž)Fam(\mathcal{C}), for families in π’ž\mathcal{C}) obtained by freely adjoining coproducts of all objects of π’ž\mathcal{C}.

Definitions

Here are a few concrete realizations of free coproduct completions.

Via indexed sets of objects

The following explicit description of the coproduct completion is pretty immediate and seems to be part of category theory folklore (for instance the way it is referred to in Carboni, Lack & Walters (1993), Proof of Prop. 2.4). Early references include BΓ©nabou (1985), Β§3, see also Hu & Tholen (1995), p. 281, 286.

An explicit description of the free coproduct completion PSh βŠ”(π’ž)PSh_{\sqcup}(\mathcal{C}) of a category π’ž\mathcal{C} is:

  • Its objects are dependent pairs consisting of

    1. an index set I∈I \in Set

    2. an II-indexed set (X iβˆˆπ’ž) i∈I\big( X_i \in \mathcal{C} \big)_{i \in I} of objects of π’ž\mathcal{C}.

  • Its morphisms (X i) i∈Iβ†’(Ο• i) i∈I(Y j) j∈J\big( X_i \big)_{i \in I} \xrightarrow{ \; ( \phi_i )_{i \in I} \; } \big( Y_j \big)_{j \in J} pairs consisting of

    • a function of index sets f:Iβ†’Jf \,\colon\, I \to J.

    • an II-indexed set of morphisms Ο• i:X iβ†’Y f(j)\phi_i \,\colon\, X_i \xrightarrow{\;} Y_{f(j)} in π’ž\mathcal{C}.

  • The composition-law and identity morphisms are the evident ones.

As a Grothendieck construction

The following is also pretty immediate and essentially discussed in BΓ©nabou (1985), Β§3 (though without mentioning of the term β€œGrothendieck construction”).

The free coproduct completion of a category π’ž\mathcal{C} is equivalently the Grothendieck construction

PSh βŠ”(π’ž)β‰ƒβˆ«S∈Set∏s∈Sπ’ž PSh_{\sqcup}(\mathcal{C}) \;\; \simeq \;\; \underset { S \,\in\, Set } { \textstyle{\int} } \; \underset{s \in S}{\textstyle{\prod}} \mathcal{C}

on the contravariant pseudofunctor on Set which sends a set SS to the SS-indexed product category of π’ž\mathcal{C} with itself (equivalently: to the functor category into π’ž\mathcal{C} out of the discrete category on SS):

Set op ⟢ Cat S ↦ Func(S,π’ž) β‰ƒβˆs∈Sπ’ž ↓ f ↑ f * T ↦ Func(T,π’ž) β‰ƒβˆt∈Tπ’ž, \array{ Set^{op} &\longrightarrow& Cat \\ S &\mapsto& Func(S,\mathcal{C}) & \simeq \;\underset{s \in S}{\prod} \mathcal{C} \\ \Big\downarrow\mathrlap{{}^{f}} && \Big\uparrow\mathrlap{{}^{f^\ast}} \\ T &\mapsto& Func(T,\mathcal{C}) & \simeq \;\underset{t \in T}{\prod} \mathcal{C} \mathrlap{\,,} }

where the base change-functors f *f^\ast are given (on functor categories by precomposition with ff, hence) by:

(1)f:S⟢T⊒∏t∈Tπ’ž β†’f ∏s∈Sπ’ž (X t) t∈T ↦ (X f(s)) s∈S. f \,\colon\, S \longrightarrow T \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \vdash \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \array{ \underset{t \in T}{\prod} \mathcal{C} &\xrightarrow{\;\; f \;\;}& \underset{s \in S}{\prod} \mathcal{C} \\ \big( X_t \big)_{t \in T} &\mapsto& \big( X_{f(s)} \big)_{s \in S} \,. }

Namely, by definition of the Grothendieck construction

  1. its objects are dependent pairs of the form

    X S≑(S∈Set,(X sβˆˆπ’ž) s∈S) X_S \;\equiv\; \big( S \in Set ,\, (X_s \in \mathcal{C})_{s \in S} \big)
  2. its morphisms

    Ο• f:X S⟢Y T \phi_f \;\colon\; X_S \longrightarrow Y_T

    are dependent pairs consisting of a map

    f:S⟢T f \,\colon\, S \longrightarrow T

    and a morphism in ∏s∈Sπ’ž\underset{s \in S}{\prod} \mathcal{C} of the form

    Ο•:X S⟢f *Y T. \phi \,\colon\, X_S \longrightarrow f^\ast Y_T \,.

    where, by definition (1) of f *f^\ast and the nature of product categories, the latter is an SS-indexed set (Ο• s) s∈S(\phi_s)_{s \in S} of morphisms in π’ž\mathcal{C} of the form

    Ο• s:X s⟢Y f(s). \phi_s \,\colon\, X_s \longrightarrow Y_{f(s)} \,.

But this is manifestly the same as the explicit description of PSh βŠ”(π’ž)PSh_{\sqcup}(\mathcal{C}) above.

Via coproducts of presheaves

The free coproduct completion of π’ž\mathcal{C} is equivalently the full subcategory

PSh βŠ”(π’ž)β†ͺPSh(π’ž) PSh_{\sqcup}(\mathcal{C}) \xhookrightarrow{\;} PSh(\mathcal{C})

of the category of presheaves over π’ž\mathcal{C} on those which are coproducts of representables. The latter is the free cocompletion of π’ž\mathcal{C} under all small colimits.

The Yoneda embedding hence factors through the free coproduct completion

y:π’žβ†ͺPSh βŠ”(π’ž)β†ͺPSh(π’ž) y \;\colon\; \mathcal{C} \xhookrightarrow{\;} PSh_{\sqcup}(\mathcal{C}) \xhookrightarrow{\;} PSh(\mathcal{C})

Notice that the first inclusion here does not preserve coproducts (coproducts are freely adjoined irrespective of whether π’ž\mathcal{C} already had some coproducts), but the second does. Both inclusions preserve those limits that exist.

Properties

Fairly immediate from the explicit definition above is:

Proposition

A category ℬ\mathcal{B} with small-indexed coproducts is equivalent to a free coproduct completion PSh βŠ”(π’ž)PSh_{\sqcup}(\mathcal{C}) for a small category π’ž\mathcal{C} if

  1. π’žβ†ͺℬ\mathcal{C} \xhookrightarrow{\;} \mathcal{B} is a full subcategory of connected objects,

    i.e. Xβˆˆπ’žβ†ͺℬX \,\in\, \mathcal{C} \hookrightarrow \mathcal{B} means that the hom-functor ℬ(X,βˆ’):ℬ→Set\mathcal{B}(X,-) \,\colon\, \mathcal{B} \to Set preserves coproducts

    (which when π’ž\mathcal{C} is extensive means equivalently that if XX is a coproduct, then one of the summands is initial, by this Prop.);

  2. each object of ℬ\mathcal{B} is a coproduct of objects in π’žβ†ͺℬ\mathcal{C} \hookrightarrow \mathcal{B}.

(Carboni & Vitale 1998, Lem. 42)
Proof

Since, by assumption, the objects of ℬ\mathcal{B} are already presented by indexed sets (X s) s∈S\big(X_s\big)_{s \in S} of objects in π’ž\mathcal{C}, it is sufficient to see that under this presentation the morphisms

Ο•:(∐s∈SX s)⟢(∐t∈TY t) \phi \,\colon\, \big(\underset{s \in S}{\coprod} X_s\big) \longrightarrow \big(\underset{t \in T}{\coprod} Y_t\big)

in ℬ\mathcal{B} correspond bijectively to indexed sets of morphisms in π’ž\mathcal{C} according to the explicit description of the free coproduct completion above. Indeed, using

  1. the general fact that hom-functors take coproducts in the first argument to products

  2. the defining property that the resulting hom-functors out of connected objects take coproducts in the second argument to coproducts,

we obtain the following sequence of natural bijections

Hom π’ž(∐ sX s,∐ tY t) β‰ƒβˆ sHom π’ž(X s,∐ tY t) β‰ƒβˆs∈S∐t s∈THom π’ž(X s,Y t s) β‰ƒβˆf:Sβ†’T∏s∈SHom π’ž(X s,Y f(s)). \begin{array}{ll} Hom_{\mathcal{C}}\big( \coprod_s X_s ,\, \coprod_t Y_t \big) \\ \;\simeq\; \prod_s Hom_{\mathcal{C}}\big( X_s ,\, \coprod_t Y_t \big) \\ \;\simeq\; \underset{s \in S}{\prod} \underset{t_s \in T}{\coprod} Hom_{\mathcal{C}}\big( X_s ,\, Y_{t_s} \big) \\ \;\simeq\; \underset{f \colon S \to T}{\coprod} \underset{s \in S}{\prod} Hom_{\mathcal{C}}\big( X_s ,\, Y_{f(s)} \big) \,. \end{array}

Proposition

The free coproduct completion of an accessible category is itself accessible.

(Makkai & ParΓ© (1989), Cor. 5.3.6)

Proposition

Any free coproduct completion is an extensive category.

(e.g. Carboni, Lack & Walters 1993)

Proposition

For π’ž\mathcal{C} a category with all Cartesian products, its free coproduct completion PSh βŠ”(π’ž)PSh_{\sqcup}(\mathcal{C}) also has products and they distribute over the coproducts.

Proof

This is readily seen by component inspection, but it may be instructive to see it from more abstract reasoning:

Namely, with the free cocompletion understood as a Grothendieck construction, PSh βŠ”(π’ž)β‰ƒβˆ« S∈Setπ’ž SPSh_{\sqcup}(\mathcal{C}) \,\simeq\, \int_{S \in Set} \mathcal{C}^S discussed above, its cartesian produducts are computed by the general formula for limits in Grothendieck constructions (here) as the β€œexternal cartesian product” (here, we now show binary products only, just for ease notation):

X S,Y T∈∫ S∈Setπ’žβŠ’X SΓ—Y T≃(((pr S) *X)Γ— SΓ—T((pr T) *Y)) SΓ—T. X_S,\, Y_T \,\in\, \textstyle{\int}_{S \in Set} \mathcal{C} \;\;\;\;\;\;\;\;\; \vdash \;\;\;\;\;\;\;\;\; X_S \times Y_T \;\simeq\; \Big( \big( (pr_S)^\ast X \big) \times_{S \times T} \big( (pr_T)^\ast Y \big) \Big)_{S \times T} \,.

Of course this comes down to the expected component formula

(X SΓ—Y T) s,t ≃(((pr S) *X)Γ— SΓ—T((pr T) *Y)) s,t by the above ≃{(s,t)} *(((pr S) *X)Γ— SΓ—T((pr T) *Y)) by definition ≃(({(s,t)} *(pr S) *X)Γ— {(s,t)}({(s,t)} *(pr T) *Y)) pullback is right adjoint ≃({s} *X)Γ— {(s,t)}({t} *Y) by commuting diagram below ≃X sΓ—Y t by definition \begin{array}{ll} \big( X_S \times Y_T \big)_{s,t} \\ \;\simeq\; \Big( \big( (pr_S)^\ast X \big) \times_{S \times T} \big( (pr_T)^\ast Y \big) \Big)_{s,t} & \text{by the above} \\ \;\simeq\; \{(s,t)\}^\ast \Big( \big( (pr_S)^\ast X \big) \times_{S \times T} \big( (pr_T)^\ast Y \big) \Big) & \text{by definition} \\ \;\simeq\; \Big( \big( \{(s,t)\}^\ast (pr_S)^\ast X \big) \times_{\{(s,t)\}} \big( \{(s,t)\}^\ast (pr_T)^\ast Y \big) \Big) & \text{pullback is right adjoint} \\ \;\simeq\; \big( \{s\}^\ast X \big) \times_{\{(s,t)\}} \big( \{t\}^\ast Y \big) & \text{by commuting diagram below} \\ \;\simeq\; X_s \times Y_t & \text{by definition} \end{array}
{s} ≃ {(s,t)} ≃ {t} ↓ ↓ ↓ S ⟡pr S SΓ—T ⟢pr T T \array{ \{s\} &\simeq& \{(s,t)\} &\simeq& \{t\} \\ \Big\downarrow && \Big\downarrow && \Big\downarrow \\ S &\underset{pr_S}{\longleftarrow}& S \times T &\underset{pr_T}{\longrightarrow}& T }

Similarly, the component formula for the free coproduct is

(Y Tβ¨ΏYβ€² Tβ€²) τ≃{Y Ο„ | Ο„βˆˆT Yβ€² Ο„ | Ο„βˆˆTβ€². \big( Y_T \amalg Y'_{T'} \big)_{\tau} \;\simeq\; \left\{ \begin{array}{lll} Y_\tau &\vert& \tau \in T \\ Y'_{\tau} &\vert& \tau \in T' \end{array} \right. \,.

Using all this, distributivity is verified as follows:

(X SΓ—(Y TβŠ”Y Tβ€²)) s,Ο„ ≃X sΓ—(Y TβŠ”Y Tβ€²) Ο„ ≃{X sΓ—Y Ο„ | Ο„βˆˆT X sΓ—Yβ€² Ο„ | Ο„βˆˆTβ€² ≃{(X SΓ—Y T) s,Ο„ | Ο„βˆˆT (X SΓ—Yβ€² Tβ€²) s,Ο„ | Ο„βˆˆTβ€² ≃((X SΓ—Y T)βŠ”(X SΓ—Yβ€² Tβ€²)) s,Ο„. \begin{array}{ll} \Big( X_S \times \big( Y_T \sqcup Y_{T'} \big) \Big)_{s, \tau} \\ \;\simeq\; X_s \times \big( Y_T \sqcup Y_{T'} \big)_\tau \\ \;\simeq\; \left\{ \begin{array}{lll} X_s \times Y_\tau &\vert& \tau \in T \\ X_s \times Y'_{\tau} &\vert& \tau \in T' \end{array} \right. \\ \;\simeq\; \left\{ \begin{array}{lll} (X_S \times Y_T)_{s, \tau} &\vert& \tau \in T \\ (X_S \times Y'_{T'})_{s, \tau} &\vert& \tau \in T' \end{array} \right. \\ \;\simeq\; \Big( \big( X_S \times Y_T \big) \sqcup \big( X_S \times Y'_{T'} \big) \Big)_{s,\tau} \,. \end{array}

Remark

It seems plausible, that, more abstractly, Prop. follows because the 2-monad for free product completion would distribute over the 2-monad for free coproduct cocompletion; the composite 2-monad would exhibit the free distributive category-construction. We don’t currently have a proof or reference for these statements, though.

Examples

Coproduct completion of connected objects

The following examples follow as special cases of Prop. :

Example

The category Set is the free coproduct completion of the terminal category.

Example

(skeletal groupoids form the free coproduct completion of groups)
The 1-category of skeletal groupoids among that of all strict groupoids is the free coproduct completion of the category of 1-object delooping groupoids which (as 1-categories) is equivalently the category of groups:

PSh βŠ”(Grp)≃PSh βŠ”(Grpd (Obj=*))≃Grpd skl. PSh_{\sqcup}\big( Grp \big) \;\; \simeq \;\; PSh_{\sqcup}\big( Grpd_{(Obj = \ast)} \big) \;\; \simeq \;\; Grpd_{skl} \,.

Example

( G G -sets are the free coproduct completion of G G -orbits)
Let G∈Grp(Set)G \,\in\, Grp(Set) be a discrete group. Write

Since every G-set XX decomposes as a disjoint union of transitive actions, namely of orbits of elements of XX, this inclusion exhibits GSetG Set as the free coproduct completion of G Orbt.

Coproduct compeletion of extensive categories

Example

(coproduct completion of extensive categories)
While Prop. says that every free coproduct completion is extensive, if a category π’ž\mathcal{C} is already extensive to start with then its free coproduct completion may equivalently be described as the category of π’ž\mathcal{C}-bundles over sets, the latter regarded as objects of π’ž\mathcal{C} via the unique coproduct-preserving functor ΞΉ Set:SetβŸΆπ’ž\iota_{Set} \,\colon\, Set \longrightarrow \mathcal{C}, hence as the comma category π’ž Set≔(id π’ž,ΞΉ Set)\mathcal{C}_{Set} \,\coloneqq\, \big(id_{\mathcal{C}}, \iota_{Set}\big):

(2)𝒳extensive⊒PSh βŠ”(π’ž)β‰ƒπ’ž Set={∐s∈SX s βŸΆΟ• ∐t∈TY t ↓ ↓ S ⟢f T,} \mathcal{X}\;\text{extensive} \;\;\;\;\;\;\;\;\;\; \vdash \;\;\;\;\;\;\;\;\;\; PSh_{\sqcup}(\mathcal{C}) \;\; \simeq \;\; \mathcal{C}_{Set} \;\; = \;\; \left\{ \array{ \underset{s \in S}{\coprod} X_s &\overset{\phi}{\longrightarrow}& \underset{t \in T}{\coprod} Y_t \\ \Big\downarrow && \Big\downarrow \\ S &\underset{f}{\longrightarrow}& T \,, } \right\}

where on the right we are indicating a generic morphism of such bundles.

Namely, since every set is the coproduct of singleton sets indexed by its elements, and due to the defining property of an extensive category that the coproduct functors are equivalences between (products of) slice categories

π’ž /ΞΉ(S)β‰ƒβˆs∈Sπ’ž /ΞΉ(s) \mathcal{C}_{/ \iota(S)} \;\; \simeq \;\; \underset{s \in S}{\prod} \mathcal{C}_{/\iota(s)}

it follows that:

  1. every object X SX_S of π’ž ΞΉ(S)\mathcal{C}_{\iota(S)} is of the form shown in (2) hence determined by a family (X s) s∈S(X_s)_{s \in S},

  2. morphisms as shown in (2) are equivalently (by the universal property of the pullback) morphisms of the form

    ∐s∈SX s βŸΆΟ• ∐s∈SY f(s) ↓ ↓ S ⟢id S S, \array{ \underset{s \in S}{\coprod} X_s &\overset{\phi}{\longrightarrow}& \underset{s \in S}{\coprod} Y_{f(s)} \\ \Big\downarrow && \Big\downarrow \\ S &\underset{\;\;\; id_S \;\;\;}{\longrightarrow}& S \,, }

    (where we used pullback stability of coproducts in an extensive category, see there, to deduce that f *Y Sβ‰ƒβˆs∈Sf *(Y S) sβ‰ƒβˆs∈SY f(s)f^\ast Y_S \,\simeq\, \underset{s \in S}{\coprod} f^\ast(Y_S)_s \,\simeq\, \underset{s \in S}{\coprod} Y_{f(s)})

    which by extensitivity are equivalently SS-indexed families Ο• s:X s⟢Y f(s)\phi_s\,\colon\, X_s \longrightarrow Y_{f(s)}.

This is again manifestly the explicit description of the free coproduct completion from above.

Conversely this gives a sense that if a category π’ž\mathcal{C} is not extensive, so that the notion of bundles with total spaces and fibers in π’ž\mathcal{C} does not make sense, its free coproduct completion may be understood as the closest stand-in for that category of π’ž\mathcal{C}-bundles over sets.

References

Early discussion of the concept:

  • Jean BΓ©nabou, Β§3.3 in: Fibered Categories and the Foundations of Naive Category Theory, The Journal of Symbolic Logic, Vol. 50 1 (1985) 10-37 [doi:10.2307/2273784]

On accessibility of free coproduct completions:

On limits in free coproduct completions:

In the context of regular and exact completions:

In the general context of extensive categories:

As categorical semantics for dependent linear type theories (in the context of quantum programming languages with β€œdynamic lifting”, such as proto-Quipper), the free coproduct completion of symmetric closed monoidal categories is considered in

and its followups.

Last revised on August 19, 2023 at 11:03:28. See the history of this page for a list of all contributions to it.