dependent sum


Category theory

Limits and colimits



The dependent sum is a universal construction in category theory. It generalizes the Cartesian product to the situation where one factor may depend on the other. It is the left adjoint to the base change functor between slice categories.

The dual notion is that of dependent product.


Let 𝒞\mathcal{C} be a category and f:AIf \colon A \to I a morphism in 𝒞\mathcal{C} such that pullbacks along ff exist in 𝒞\mathcal{C}. These then constitute a base change functor

f *:𝒞 /I𝒞 /A f^* \colon \mathcal{C}_{/I} \to \mathcal{C}_{/A}

between the corresponding slice categories.


The dependent sum or dependent coproduct along the morphism ff is the left adjoint f:𝒞 /A𝒞 /I\sum_f \colon \mathcal{C}_{/A} \to \mathcal{C}_{/I} of the base change functor

( ff *):𝒞 /Af * f𝒞 /I. (\sum_f \dashv f^* ) \colon \mathcal{C}_{/A} \stackrel{\overset{\sum_f}{\to}}{\underset{f^*}{\leftarrow}} \mathcal{C}_{/I} \qquad.

This is directly seen to be equivalent to the following.


The dependent sum along f:AIf \colon A \to I is the functor

ff():𝒞 /A𝒞 /I \sum_f \coloneqq f\circ (-) \colon \mathcal{C}_{/A} \to \mathcal{C}_{/I}

given by composition with ff.


Relation to the product

Assume that the category 𝒞\mathcal{C} has a terminal object *𝒞* \in \mathcal{C}. Let X𝒞X \in \mathcal{C} be any object and assume that the terminal morphism f:X*f \colon X \to * admits all pullbacks along it.

Notice that a pullback of some A*A \to * along X*X \to * is simply the product X×AX \times A, equipped with its projection morphism X×AXX \times A \to X. We may regard X×AXX \times A \to X as the image of the base change functor f *:𝒞 /*𝒞 /Xf^* \colon \mathcal{C}_{/*} \to \mathcal{C}_{/X}, but this is not quite just the product in 𝒞\mathcal{C}, which instead corresponds to the terminal morphisms X×A*X \times A \to *. But we have:


The product X×A𝒞X \times A \in \mathcal{C} is, if it exists, equivalently the dependent sum of the base change of A*A \to * along X*X \to *:

XX *AX×A𝒞. \sum_{X} X^* A \simeq X \times A \in \mathcal{C} \quad .

Here we write “XX” also for the morphism X*X \to *.

Relation to type theory

Under the relation between category theory and type theory the dependent sum is the categorical semantics of dependent sum types .

Notice that under the identification of propositions as types, dependent sum types (or rather their bracket types) correspond to existential quantification x:X,Px\exists x\colon X, P x.

The following table shows how the natural deduction rules for dependent sum types correspond to their categorical semantics given by the dependent sum universal construction.

type theorycategory theory
natural deductionuniversal construction
dependent sum typedependent sum
type formationX:Typex:XA(x):Type( x:XA(x)):Type\frac{\vdash\: X \colon Type \;\;\;\;\; x \colon X \;\vdash\; A(x)\colon Type}{\vdash \; \left(\sum_{x \colon X} A\left(x\right)\right) \colon Type}(A p 1 X𝒞)(A𝒞)\left( \array{ A \\ \downarrow^{\mathrlap{p_1}} \\ X} \; \in \mathcal{C}\right) \Rightarrow \left( A \in \mathcal{C}\right)
term introductionx:Xa:A(x)(x,a): x:XA(x)\frac{x \colon X \;\vdash\; a \colon A(x)}{\vdash (x,a) \colon \sum_{x' \colon X} A\left(x'\right) }Q a A x X\array{ Q &\stackrel{a}{\to}& A \\ & {}_{\mathllap{x}}\searrow & \\ && X }
term eliminationt:( x:XA(x))p 1(t):Xp 2(t):A(p 1(t))\frac{\vdash\; t \colon \left(\sum_{x \colon X} A\left(x\right)\right)}{\vdash\; p_1(t) \colon X\;\;\;\;\; \vdash\; p_2(t) \colon A(p_1(t))}Q (x,a) A p 1 X\array{ Q &\stackrel{(x,a)}{\to}& A \\ & & \downarrow^{\mathrlap{p_1}} \\ && X }
computation rulep 1(x,a)=xp 2(x,a)=ap_1(x,a) = x\;\;\;\; p_2(x,a) = aQ (x,a) A x p 1 X\array{ Q &\stackrel{(x,a)}{\to}& A \\ & {}_{\mathllap{x}}\searrow & \downarrow^{\mathrlap{p_1}} \\ && X }

Relation to some limits


For 𝒞\mathcal{C} a category with finite limits and X𝒞X \in \mathcal{C} an object, then dependent sum

X:𝒞 /X𝒞 \underset{X}{\sum}: \mathcal{C}_{/X} \longrightarrow \mathcal{C}

preserves and reflects fiber products.


By this proposition limits over a cospan diagram in the slice category are computed as limits over the cocone diagram under the cospan in the base category. By this proposition this inclusion is a final functor, hence preserves limits. Since the dependent sum of the diagram is the restriction along this final functor, the result follows.


For 𝒞\mathcal{C} a category with finite limits and X𝒞X\in \mathcal{C} any object, the naturality square of the unit of the (XX *)(\underset{X}{\sum} \dashv X^\ast)-adjunction on any morphism (f:AB)(f \colon A \to B) in 𝒞 /X\mathcal{C}_{/X}

A X *XA f X *Xf B X *XB \array{ A &\longrightarrow& X^\ast \underset{X}{\sum} A \\ \downarrow^{\mathrlap{f}} && \downarrow^{\mathrlap{X^\ast \underset{X}{\sum} f}} \\ B &\longrightarrow& X^\ast \underset{X}{\sum} B }

is a pullback.


By prop. 2 it suffices to see that the diagram is a pullback in 𝒞\mathcal{C} under X\underset{X}{\sum}, where, by Frobenius reciprocity, it becomes

XA (A,id) X×XA Xf (id,Xf) XB (B,id) X×XB. \array{ \underset{X}{\sum} A &\stackrel{(A,id)}{\longrightarrow}& X \times \underset{X}{\sum} A \\ \downarrow^{\mathrlap{\underset{X}{\sum}f}} && \downarrow^{\mathrlap{(id, \underset{X}{\sum} f)}} \\ \underset{X}{\sum} B &\stackrel{(B,id)}{\longrightarrow}& X \times \underset{X}{\sum} B } \qquad .

For 𝒞\mathcal{C} a category with finite limits and X𝒞X\in \mathcal{C} any object, the naturality square of the counit of the (XX *)(\underset{X}{\sum} \dashv X^\ast)-adjunction on any morphism (f:AB)(f \colon A \to B) in 𝒞\mathcal{C}

XX *A A XX *f f XX *B B \array{ \underset{X}{\sum} X^\ast A &\longrightarrow& A \\ \downarrow^{\mathrlap{\underset{X}{\sum}X^\ast f}} && \downarrow^{\mathrlap{f}} \\ \underset{X}{\sum} X^\ast B &\longrightarrow& B }

is a pullback.


By Frobenius reciprocity the diagram is equivalent to

X×A A (id,f) f X×B B. \array{ X\times A & \longrightarrow& A \\ \downarrow^{\mathrlap{(id,f)}} && \downarrow^{\mathrlap{f}} \\ X \times B &\longrightarrow& B } \qquad.


Standard textbook accounts include section A1.5.3 of

and section IV of

Revised on June 11, 2017 11:14:59 by Peter Heinig (