nLab limit

This entry is about the notion of “limit” in category theory. For the notion of the same name in analysis and topology see at limit of a sequence.

category theory

Applications

Limits and colimits

limits and colimits

Contents

Idea

In category theory a limit of a diagram $F:D\to C$ in a category $C$ is an object $\mathrm{lim}F$ of $C$ equipped with morphisms to the objects $F\left(d\right)$ for all $d\in D$, such that everything in sight commutes. Moreover, the limit $\mathrm{lim}F$ is the universal object with this property, i.e. the “most optimized solution” to the problem of finding such an object.

The limit construction has a wealth of applications throughout category theory and mathematics in general. In practice, it is possibly best thought of in the context of representable functors as a classifying space for maps into a diagram. So in some sense the limit object $\mathrm{lim}F$ “subsumes” the entire diagram $F\left(D\right)$ into a single object, as far as morphisms into it are concerned. The corresponding universal object for morphisms out of the diagram is the colimit.

An intuitive general idea is that a limit of a diagram is the locus or solution set of a bunch of equations, where each of the coordinates is parametrized by one of the objects of the diagram, and where the equations are prescribed by the morphisms of the diagram. This idea is explained more formally here.

Often, the general theory of limits (but not colimits!) works better if the source of $F$ is taken to be the opposite category ${D}^{\mathrm{op}}$ (or equivalently, if $F$ is taken to be a contravariant functor). This is what we do below. In any given situation, of course, you use whatever categories and functors you're interested in.

In some cases the category-theoretic notion of limit does reproduce notions of limit as known from analysis. See the examples below.

Global versus local

In correspondence to the local definition of adjoint functors (as discussed there), there is a local definition of limits (in terms of cones), that defines a limit (if it exists) for each individual diagram, and there is a global definition, which defines the limit for all diagrams (in terms of an adjoint).

If all limits over the given shape of diagrams exist in a category, then both definitions are equivalent.

See also the analogous discussion at homotopy limit.

Terminology and notation

A limit is taken over a functor $F:{D}^{\mathrm{op}}\to C$ and since the functor comes equipped with the information about what its domain is, one can just write $\mathrm{lim}F$ for its limit. But often it is helpful to indicate how the functor is evaluated on objects, in which case the limit is written ${\mathrm{lim}}_{d\in D}F\left(d\right)$; this is used particularly when $F$ is given by a formula (as with other notation with bound variables.)

In some schools of mathematics, limits are called projective limits, while colimits are called inductive limits. Also seen are (respectively) inverse limits and direct limits. Both these systems of terminology are alternatives to using ‘co-’ when distinguishing limits and colimits. The first system also appears in pro-object and ind-object.

Correspondingly, the symbols $\underset{←}{\mathrm{lim}}$ and $\underset{\to }{\mathrm{lim}}$ are used instead of $\mathrm{lim}$ and $colim$.

Confusingly, many authors restrict the meanings of these alternative terms to (co)limits whose sources are directed sets; see directed limit. In fact, this is the original meaning; projective and inductive limits in this sense were studied in algebra before the general category-theoretic notion of (co)limit.

Definition

Local definition in terms of representable functors

There is a general abstract definition of limits in terms of representable functors, which we describe now. This reproduces the more concrete and maybe more familiar description in terms of universal cones, which is described further below.

Let in the following $D$ be a small category and Set the category of sets (possibly realized as the category $U\mathrm{Set}$ of $U$-small sets with respect to a given Grothendieck universe.)

Limit of a Set-valued functor

The limit of a Set-valued functor $F:{D}^{\mathrm{op}}\to \mathrm{Set}$ is the hom-set

$\mathrm{lim}F:={\mathrm{Hom}}_{\left[{D}^{\mathrm{op}},\mathrm{Set}\right]}\left(\mathrm{pt},F\right)\in \mathrm{Set}$lim F := Hom_{[D^{op}, Set]}(pt, F) \in Set

in the functor category $\left[{D}^{\mathrm{op}},\mathrm{Set}\right]$ (the presheaf category), where

$\mathrm{pt}:{D}^{\mathrm{op}}\to \mathrm{Set}$pt : D^{op} \to Set
$\mathrm{pt}:d↦\left\{*\right\}$pt : d \mapsto \{*\}

is the functor constant on the point, i.e. the terminal diagram.

The set $\mathrm{lim}F$ is equivalently called

• the set of global sections of $F$;

• the set of generalized elements of $F$.

The set $\mathrm{lim}F$ can be equivalently expressed as an equalizer of a product, explicitly:

$\mathrm{lim}F\simeq \left\{\left({x}_{d}{\right)}_{d\in D}\in \prod _{d\in D}F\left(d\right)\mid \forall \left({d}_{i}\stackrel{\alpha }{\to }{d}_{j}\right)\in D:F\left(\alpha \right)\left({x}_{{d}_{j}}\right)={x}_{{d}_{i}}\right\}$lim F \simeq \left\lbrace (x_d)_{d \in D} \in \prod_{d \in D} F(d) | \forall (d_i \stackrel{\alpha}{\to} d_j) \in D : F(\alpha)(x_{d_j}) = x_{d_i} \right\rbrace

In particular, the limit of a set-valued functor always exists.

Notice the important triviality that the covariant hom-functor commutes with set-valued limits: for every set $S$ we have a bijection of sets

${\mathrm{Hom}}_{\mathrm{Set}}\left(S,\mathrm{lim}F\right)\simeq \mathrm{lim}{\mathrm{Hom}}_{\mathrm{Set}}\left(S,F\left(-\right)\right)\phantom{\rule{thinmathspace}{0ex}},$Hom_{Set}(S, lim F) \simeq \lim Hom_{Set}(S, F(-)) \,,

where $\mathrm{Hom}\left(S,F\left(-\right)\right):{D}^{\mathrm{op}}\to \mathrm{Set}$.

Limit of a functor with values in an arbitrary category

The above formula generalizes straightforwardly to a notion of limit for functors $F:{D}^{\mathrm{op}}\to C$ for $C$ an arbitrary category if we construct a certain presheaf on $C$ which we will call $\stackrel{^}{\mathrm{lim}}F$. The actual limit $\mathrm{lim}F$ is then, if it exists, the object of $C$ representing this presheaf.

More precisely, using the the Yoneda embedding $Y:C\to \left[{C}^{\mathrm{op}},\mathrm{Set}\right]$ define for $F:{D}^{\mathrm{op}}\to C$ the presheaf $\stackrel{^}{\mathrm{lim}}F\in \left[{C}^{\mathrm{op}},\mathrm{Set}\right]$ by the analog of the above formula

$\left(\stackrel{^}{\mathrm{lim}}F\right)\left(c\right)\simeq {\mathrm{Hom}}_{\left[{C}^{\mathrm{op}},\mathrm{Set}\right]}\left(Y\left(c\right),\stackrel{^}{\mathrm{lim}}F\right):=\mathrm{lim}{\mathrm{Hom}}_{C}\left(c,F\left(-\right)\right)$(\hat \lim F)(c) \simeq Hom_{[C^{op}, Set]}(Y(c), \hat \lim F) := \lim Hom_C(c, F(-))

for all $c\in C$.

Here the $\mathrm{lim}$ on the right is again that of Set-valued functors defined before.

By the above this can also be written as

$\left(\stackrel{^}{\mathrm{lim}}F\right)\left(c\right)={\mathrm{Hom}}_{\left[{D}^{\mathrm{op}},\mathrm{Set}\right]}\left(\mathrm{pt},{\mathrm{Hom}}_{C}\left(c,F\left(-\right)\right)$(\hat \lim F)(c) = Hom_{[D^{op}, Set]}(pt , Hom_C(c,F(-))

or, suppressing the subscripts for readability:

$\left(\stackrel{^}{\mathrm{lim}}F\right)\left(c\right)=\mathrm{Hom}\left(\mathrm{pt},\mathrm{Hom}\left(c,F\left(-\right)\right)\phantom{\rule{thinmathspace}{0ex}}.$(\hat lim F)(c) = Hom(pt , Hom(c,F(-)) \,.

So also the presheaf-valued limit always exists. Iff this presheaf is representable by an object $\mathrm{lim}F$ of $F$, then this is the limit of $F$:

$\mathrm{Hom}\left(c,\mathrm{lim}F\right)\simeq \mathrm{Hom}\left(\mathrm{pt},\mathrm{Hom}\left(c,F\left(-\right)\right)\right)\phantom{\rule{thinmathspace}{0ex}}.$Hom(c, \lim F) \simeq Hom(pt, Hom(c,F(-))) \,.

Generalization to weighted limits

In the above formulation, there is an evident generalization to weighted limits:

replace in the above the constant terminal functor $\mathrm{pt}:{D}^{\mathrm{op}}\to \mathrm{Set}$ with any functor $W:{D}^{\mathrm{op}}\to \mathrm{Set}$ – then called the weight –, then the $W$-weighted limit of $F$

$\underset{W}{\mathrm{lim}}F$\lim_W F

often written

$\left\{W,F\right\}$\{W,F\}

is, if it exists, the object representing the presheaf

$c↦{\mathrm{Hom}}_{\left[{D}^{\mathrm{op}},\mathrm{Set}\right]}\left(W,{\mathrm{Hom}}_{C}\left(c,F\left(-\right)\right)\right)\phantom{\rule{thinmathspace}{0ex}},$c \mapsto Hom_{[D^{op}, Set]}(W , Hom_C(c,F(-))) \,,

i.e. such that

$\mathrm{Hom}\left(c,\underset{W}{\mathrm{lim}}F\right)\simeq \mathrm{Hom}\left(W,\mathrm{Hom}\left(c,F\left(-\right)\right)\right)\phantom{\rule{thinmathspace}{0ex}}$Hom(c, \lim_W F) \simeq Hom(W, Hom(c,F(-))) \,

naturally in $c\in C$.

Relation to continuous functors

The very definition of limit as above asserts that the covariant hom-functor $\mathrm{Hom}\left(c,-\right):C\to \mathrm{Set}$ commutes with forming limits. Indeed, the definition is equivalent to saying that the hom-functor is a continuous functor.

Definition in terms of universal cones

Unwrapping the above abstract definition of limits yields the following more hands-on description in terms of universal cones.

Unwrapping

Let $F:{D}^{\mathrm{op}}\to C$ be a functor.

Notice that for every object $c\in C$ an element

$*\to \mathrm{Hom}\left(\mathrm{pt},\mathrm{Hom}\left(c,F\left(-\right)\right)\right)$* \to Hom(pt, Hom(c, F(-)))

is to be identified with a collection of morphisms

$c\to F\left(d\right)$c \to F(d)

for all $d\in D$, such that all triangles

$\begin{array}{ccc}& & c\\ & ↙& & ↘\\ F\left({d}_{i}\right)& & \stackrel{F\left(f\right)}{\to }& & F\left({d}_{j}\right)\end{array}$\array{ && c \\ & \swarrow && \searrow \\ F(d_i) && \stackrel{F(f)}{\to} && F(d_j) }

commute. Such a collection of morphisms is called a cone over $F$, for the obvious reason.

If the limit $\mathrm{lim}F\in C$ of $F$ exist, then it singles out a special cone given by the composite morphism

$*\stackrel{*↦{\mathrm{Id}}_{\mathrm{lim}F}}{\to }{\mathrm{Hom}}_{C}\left(\mathrm{lim}F,\mathrm{lim}F\right)\stackrel{\simeq }{\to }\mathrm{Hom}\left(\mathrm{pt},\mathrm{Hom}\left(\mathrm{lim}F,F\left(-\right)\right)\right)\phantom{\rule{thinmathspace}{0ex}},$* \stackrel{* \mapsto Id_{\lim F}}{\to} Hom_C(\lim F, \lim F) \stackrel{\simeq}{\to} Hom(pt, Hom(\lim F, F(-))) \,,

where the first morphism picks the identity morphism on $\mathrm{lim}F$ and the second one is the defining bijection of a limit as above.

The cone

$\begin{array}{ccc}& & \mathrm{lim}F\\ & ↙& & ↘\\ F\left({d}_{i}\right)& & \stackrel{F\left(f\right)}{\to }& & F\left({d}_{j}\right)\end{array}$\array{ && \lim F \\ & \swarrow && \searrow \\ F(d_i) && \stackrel{F(f)}{\to} && F(d_j) }

is called the universal cone over $F$, because, again by the defining property of limit as above, every other cone $\left\{c\to F\left(d\right){\right\}}_{d\in D}$ as above is bijectively related to a morphism $c\to \mathrm{lim}F$

$*\stackrel{\left\{c\to F\left(d\right){\right\}}_{d\in D}}{\to }\mathrm{Hom}\left(\mathrm{pt},\mathrm{Hom}\left(c,F\left(-\right)\right)\right)\stackrel{\simeq }{\to }\mathrm{Hom}\left(c,\mathrm{lim}F\right)\phantom{\rule{thinmathspace}{0ex}}.$* \stackrel{\{c \to F(d)\}_{d \in D}}{\to} Hom(pt, Hom(c, F(-))) \stackrel{\simeq}{\to} Hom(c, \lim F) \,.

By inspection one finds that, indeed, the morphism $c\to \mathrm{lim}F$ is the morphism which exhibits the factorization of the cone $\left\{c\to F\left(d\right){\right\}}_{d\in D}$ through the universal limit cone

$\begin{array}{ccc}& & c\\ & ↙& & ↘\\ F\left({d}_{i}\right)& & \stackrel{F\left(f\right)}{\to }& & F\left({d}_{j}\right)\end{array}=\begin{array}{ccc}& & c\\ & & ↓\\ & & \mathrm{lim}F\\ & ↙& & ↘\\ F\left({d}_{i}\right)& & \stackrel{F\left(f\right)}{\to }& & F\left({d}_{j}\right)\end{array}\phantom{\rule{thinmathspace}{0ex}}.$\array{ && c \\ & \swarrow && \searrow \\ F(d_i) && \stackrel{F(f)}{\to} && F(d_j) } = \array{ && c \\ && \downarrow \\ && \lim F \\ & \swarrow && \searrow \\ F(d_i) && \stackrel{F(f)}{\to} && F(d_j) } \,.

An illustrative example is the following: a limit of the identity functor ${\mathrm{Id}}_{c}:C\to C$ is, if it exists, an initial object of $C$.

Global Definition in terms of adjoint of the constant diagram functor

Given categories $D$ and $C$, limits over functors ${D}^{\mathrm{op}}\to C$ may exist for some functors, but not for all. If it does exist for all functors, then the above local definition of limits is equivalent to the following global definition.

For $D$ a small category and $C$ any category, the functor category $\left[{D}^{\mathrm{op}},C\right]$ is the category of $D$-diagrams in $C$. Pullback along the functor ${D}^{\mathrm{op}}\to \mathrm{pt}$ to the terminal category $\mathrm{pt}=\left\{•\right\}$ induces a functor

$\mathrm{const}:C\to \left[{D}^{\mathrm{op}},C\right]$const : C \to [D^{op},C]

which sends every object of $C$ to the diagram functor constant on this object.

${\mathrm{colim}}_{D}:\left[{D}^{\mathrm{op}},C\right]\to C$colim_D : [D^{op},C] \to C

of this functor is, if it exists, the functor which sends every diagram to its colimit and the right adjoint is, if it exists, the functor

${\mathrm{lim}}_{D}:\left[{D}^{\mathrm{op}},C\right]\to C$lim_D : [D^{op},C] \to C

which sends every diagram to its limit. The Hom-isomorphisms of these adjunctions state precisely the universal property of limit and colimit given above.

Concretely this means that for all $c\in C$ we have a bijection

${\mathrm{Hom}}_{C}\left(c,\mathrm{lim}F\right)\simeq {\mathrm{Hom}}_{\left[{D}^{\mathrm{op}},C\right]}\left({\mathrm{const}}_{X},F\right)\phantom{\rule{thinmathspace}{0ex}}.$Hom_C(c, \lim F) \simeq Hom_{[D^{op},C]}(const_X, F) \,.

From this perspective, a limit is a special case of a Kan extension, as described there, namely a Kan extension to the point.

Generalizations

The notion of limit, being fundamental to category theory, generalizes to many other situations. Examples include the following.

Examples

The central point about examples of limits is:

Categorical limits are ubiquitous.

To a fair extent, category theory is all about limits and the other universal constructions: Kan extensions, adjoint functors, representable functors, which are all special cases of limits – and limits are special cases of these.

Listing examples of limits in category theory is much like listing examples of integrals in analysis: one can and does fill books with these. (In fact, that analogy has more to it than meets the casual eye: see coend for more).

Keeping that in mind, we do list some special cases and special classes of examples that are useful to know. But any list is necessarily wildly incomplete.

General

Here are some important examples of limits, classified by the shape of the diagram:

Properties

Existence: construction from products and equalizers

Frequently some limits can be computed in terms of other limits. This makes things easier since we only have to assume that categories have, or functors preserve, some easier-to-verify class of limits in order to obtain results about a larger one.

The most common example of this is the computation of limits in terms of products and equalizers. Specifically, if the limit of $F:{D}^{\mathrm{op}}\to C$ and the products ${\prod }_{d\in \mathrm{Obj}\left(D\right)}F\left(d\right)$ and ${\prod }_{f\in \mathrm{Mor}d}F\left(s\left(f\right)\right)$ all exist, then $\mathrm{lim}F$ is a subobject of ${\prod }_{d\in \mathrm{Obj}\left(D\right)}F\left(d\right)$, namely the equalizer of

$\prod _{d\in \mathrm{Obj}\left(D\right)}F\left(d\right)\stackrel{\prod _{f\in \mathrm{Mor}\left(d\right)}\left(F\left(f\right)\circ {p}_{t\left(f\right)}\right)}{\to }\prod _{f\in \mathrm{Mor}\left(D\right)}F\left(s\left(f\right)\right)$\prod_{d \in Obj(D)} F(d) \stackrel{\prod_{f \in Mor(d)} (F(f) \circ p_{t(f)}) }{\to} \prod_{f \in Mor(D)} F(s(f))

and

$\prod _{d\in \mathrm{Obj}\left(D\right)}F\left(d\right)\stackrel{\prod _{f\in \mathrm{Mor}\left(d\right)}\left({p}_{s\left(f\right)}\right)}{\to }\prod _{f\in \mathrm{Mor}\left(D\right)}F\left(s\left(f\right)\right)\phantom{\rule{thinmathspace}{0ex}}.$\prod_{d \in Obj(D)} F(d) \stackrel{\prod_{f \in Mor(d)} (p_{s(f)}) }{\to} \prod_{f \in Mor(D)} F(s(f)) \,.

Conversely, if both of these products exist and so does the equalizer of this pair of maps, then that equalizer is a limit of $F$. In particular, therefore, a category has all limits as soon as it has all products and equalizers, and a functor defined on such a category preserves all limits as soon as it preserves products and equalizers.

Another example is that all finite limits can be computed in terms of pullbacks and a terminal object.

Interaction with $\mathrm{Hom}$-functor

Covariant Hom commutes with limits

For $C$ a locally small category, for $F:{D}^{\mathrm{op}}\to C$ a functor and writing $C\left(c,F\left(-\right)\right):{\mathrm{CD}}^{\mathrm{op}}\to \mathrm{Set}$, we have

$C\left(c,\mathrm{lim}F\right)\simeq \mathrm{lim}C\left(c,F\left(-\right)\right)\phantom{\rule{thinmathspace}{0ex}}.$C(c, lim F) \simeq lim C(c, F(-)) \,.

Depending on how one introduces limits this holds by definition or is an easy consequence.

In $\mathrm{Set}$

Limits in Set are hom-sets

For $F:{D}^{\mathrm{op}}\to \mathrm{Set}$ any functor and ${\mathrm{const}}_{*}:{D}^{\mathrm{op}}\to \mathrm{Set}$ the functor constant on the point, the limit of $F$ is the hom-set

$\mathrm{lim}F\simeq \left[{D}^{\mathrm{op}},\mathrm{Set}\right]\left({\mathrm{const}}_{*},F\right)$lim F \simeq [D^{op}, Set](const_{*}, F)

in the functor category, i.e. the set of natural transformations from the constant functor into $F$.

In functor categories

Proposition – limits in functor categories are computed pointwise

Let $D$ be a small category and let $D\prime$ be any category. Let $C$ be a category which admits limits of shape $D$. Write $\left[D\prime ,C\right]$ for the functor category. Then

• $\left[D\prime ,C\right]$ admits $D$-shaped limits;
• these limits are computed objectwise (“pointwise”) in $C$: for $F:{D}^{\mathrm{op}}\to \left[D\prime ,C\right]$ a functor we have for all $d\prime \in D\prime$ that $\left(\mathrm{lim}F\right)\left(d\prime \right)\simeq \mathrm{lim}\left(F\left(-\right)\left(d\prime \right)\right)$. Here the limit on the right is in $C$.

Proposition – right adjoints commute with limits

Let $R:C\to C\prime$ be a functor that is right adjoint to some functor $L:C\prime \to C$. Let $D$ be a small category such that $C$ admits limits of shape $D$. Then $R$ commutes with $D$-shaped limits in $C$ in that

for $F:{D}^{\mathrm{op}}\to C$ some diagram, we have

$R\left(\mathrm{lim}F\right)\simeq \mathrm{lim}\left(R\circ F\right)\phantom{\rule{thinmathspace}{0ex}}.$R(lim F) \simeq lim (R \circ F) \,.
Proof

Using the adjunction isomorphism and the above fact that Hom commutes with limits, one obtains for every $c\prime \in C\prime$

$\begin{array}{rl}C\prime \left(c\prime ,R\left(\mathrm{lim}F\right)\right)& \simeq C\left(L\left(c\prime \right),\mathrm{lim}F\right)\\ & \simeq \mathrm{lim}C\left(L\left(c\prime \right),F\right)\\ & \simeq \mathrm{lim}C\prime \left(c\prime ,R\circ F\right)\\ & \simeq C\prime \left(c\prime ,\mathrm{lim}\left(R\circ F\right)\right)\phantom{\rule{thinmathspace}{0ex}}.\end{array}\phantom{\rule{thinmathspace}{0ex}}.$\begin{aligned} C'(c', R (lim F)) & \simeq C(L(c'), lim F) \\ & \simeq lim C(L(c'), F) \\ & \simeq lim C'(c', R\circ F) \\ & \simeq C'(c', lim (R \circ F)) \,. \end{aligned} \,.

Since this holds naturally for every $c\prime$, the Yoneda lemma, corollary II on uniqueness of representing objects implies that $R\left(\mathrm{lim}F\right)\simeq \mathrm{lim}\left(G\circ F\right)$.

Commutativity with limits and colimits

Proposition – small limits commute with small limits

Let $D$ and $D\prime$ be small catgeories and let $C$ be a category which admits limits of shape $D$ as well as limits of shape $D\prime$. Then these limits commute with each other, in that

for $F:{D}^{\mathrm{op}}×{D\prime }^{\mathrm{op}}\to C$ a functor , with corresponding induced functors ${F}_{D}:{D\prime }^{\mathrm{op}}\to \left[{D}^{\mathrm{op}},C\right]$ and ${F}_{D\prime }:{D}^{\mathrm{op}}\to \left[{D\prime }^{\mathrm{op}},C\right]$, then

$\mathrm{lim}F\simeq {\mathrm{lim}}_{D}\left({\mathrm{lim}}_{D\prime }{F}_{D}\right)\simeq {\mathrm{lim}}_{D\prime }\left({\mathrm{lim}}_{D}{F}_{D\prime }\right)\phantom{\rule{thinmathspace}{0ex}}.$lim F \simeq lim_{D} (lim_{D'} F_D ) \simeq lim_{D'} (lim_{D} F_{D'} ) \,.
Proof

This follows from the above proposition and the characterization of the limit as right adjoint to the functor $\mathrm{const}$ defined above in the section on adjoints.

See limits and colimits by example for what this formula says for instance for the special case $C=$ Set.

In general limits do not commute with colimits. But under a number of special conditions of interest they do. More on that at commutativity of limits and colimits.

Revised on June 11, 2013 18:38:24 by Manuel Baerenz (128.243.253.113)