Skip to content
The Lumenary
Advanced undergraduateUndergraduate 120 min

Limits and colimits

Carving out and gluing together — equalisers, pullbacks, inverse limits and their mirror images as one universal construction, from solution sets to the pp-adic integers.

Formally verified · 14 LeanComputationally tested · 2 PythonAI-drafted · awaiting human reviewMathematically reviewed: Awaiting human review
MotivationH

Solving, intersecting, gluing, approximating

Here are some constructions from across mathematics.

  • The solution set {x∈X:f(x)=g(x)}\{x \in X : f(x) = g(x)\} of an equation between two maps.
  • The kernel of a homomorphism, and the intersection of two subgroups or subspaces.
  • The preimage f−1(B′)f^{-1}(B') of a subset, and the fibre product {(a,b):f(a)=g(b)}\{(a, b) : f(a) = g(b)\}.
  • The pp-adic integers, built from the rings Z/pZ←Z/p2Z←Z/p3Z←⋯\Z/p\Z \leftarrow \Z/p^2\Z \leftarrow \Z/p^3\Z \leftarrow \cdots by taking all compatible sequences of residues.
  • Quotients Y/∼Y/{\sim}, the sphere obtained by gluing two discs along their boundary circles, the rationals as a union of the groups 1nZ\frac{1}{n}\Z.

The first four "carve out" a piece of a product by equations; the last group "glues" pieces of a disjoint union together. Category theory shows that each of them is a limit or a colimit — one universal property, applied to diagrams of different shapes. The payoff is threefold: one proof of uniqueness for all of them; one theorem constructing all of them from two basic ones (products and equalisers); and a precise way to say which constructions a functor respects. That last point already decides questions such as whether a functor can have an adjoint, the subject of the next lesson.

IntuitionH

Cones: compatible families, everywhere at once

A diagram is a picture of objects and arrows in a category — a cospan A→C←BA \to C \leftarrow B, a parallel pair X⇉YX \rightrightarrows Y, a tower ⋯→D3→D2→D1\cdots \to D_3 \to D_2 \to D_1. A cone over the diagram is an object XX with one arrow to each object of the diagram, compatible with all the arrows of the diagram: whichever path you follow from XX to an object, you get the same arrow. The limit is the best cone: every other cone factors through it in exactly one way.

In Set\cat{Set}, take X={∗}X = \{\ast\}. A cone from the one-point set is just a choice of one element in each object of the diagram, compatible with all the arrows — a compatible family. So the limit of a diagram of sets is the set of compatible families. For the cospan A→fC←gBA \xrightarrow{f} C \xleftarrow{g} B, a compatible family is (a,b,c)(a, b, c) with f(a)=c=g(b)f(a) = c = g(b): the fibre product. For the tower of rings Z/pnZ\Z/p^n\Z, it is a sequence of residues, each reducing to the previous one: a pp-adic integer.

Colimits reverse every arrow. A cocone is an object receiving an arrow from every object of the diagram, compatibly, and the colimit is the best cocone. In Set\cat{Set} it is the disjoint union of all the objects, with xx glued to D(u)(x)D(u)(x) for every arrow uu of the diagram.

Limits carve out, colimits glue together.

DefinitionsH

Definitions

Throughout, C\mathcal{C} is a category and J\mathcal{J} a small category, the shape. Composition is written g∘fg \circ f.

Definition— diagram

A diagram of shape J\mathcal{J} in C\mathcal{C} is a functor D:J→CD : \mathcal{J} \to \mathcal{C}. For an object XX of C\mathcal{C}, the constant diagram ΔX:J→C\Delta X : \mathcal{J} \to \mathcal{C} sends every object to XX and every arrow to idX\mathrm{id}_X.

Definition— cone and limit

A cone over DD with apex XX is a natural transformation λ:ΔX⇒D\lambda : \Delta X \Rightarrow D. Concretely: arrows λj:X→D(j)\lambda_j : X \to D(j), one for each object jj of J\mathcal{J}, with D(u)∘λi=λjD(u) \circ \lambda_i = \lambda_j for every arrow u:i→ju : i \to j of J\mathcal{J}. A morphism of cones (X,λ)→(X′,λ′)(X, \lambda) \to (X', \lambda') is an arrow h:X→X′h : X \to X' with λj′∘h=λj\lambda'_j \circ h = \lambda_j for all jj. A limit of DD is a terminal object (lim⁡D,π)(\lim D, \pi) of the category of cones: for every cone (X,λ)(X, \lambda) there is a unique h:X→lim⁡Dh : X \to \lim D with πj∘h=λj\pi_j \circ h = \lambda_j for all jj.

XX
lim⁡D\lim D
D(i)D(i)
D(j)D(j)
λi\lambda_i
λj\lambda_j
hh
πi\pi_i
πj\pi_j
D(u)D(u)
A cone λ\lambda with apex XX factors uniquely through the limit cone π\pi; all triangles commute.

Definition— cocone and colimit

A cocone under DD is a natural transformation D⇒ΔYD \Rightarrow \Delta Y, and a colimit colim⁡D\operatorname{colim} D is an initial cocone. Equivalently, a colimit of DD is a limit of Dop:Jop→CopD^{\mathrm{op}} : \mathcal{J}^{\mathrm{op}} \to \mathcal{C}^{\mathrm{op}}.

Definition— the basic shapes

shape J\mathcal{J}limitcolimit
no objectsterminal objectinitial object
two objects, no arrowsproduct A×BA \times Bcoproduct A⊔BA \sqcup B
parallel pair ∙⇉∙\bullet \rightrightarrows \bulletequaliser of f,gf, gcoequaliser of f,gf, g
cospan ∙→∙←∙\bullet \to \bullet \leftarrow \bulletpullback A×CBA \times_C B—
span ∙←∙→∙\bullet \leftarrow \bullet \to \bullet—pushout A⊔CBA \sqcup_C B
tower ⋯→∙→∙\cdots \to \bullet \to \bullet (Nop\N^{\mathrm{op}})inverse limit lim←⁡Dn\varprojlim D_n—
chain ∙→∙→⋯\bullet \to \bullet \to \cdots (N\N)—direct (sequential) limit lim→⁡Dn\varinjlim D_n

Unpacked, an equaliser of f,g:X→Yf, g : X \to Y is an arrow e:E→Xe : E \to X with fe=gef e = g e such that every h:W→Xh : W \to X with fh=ghf h = g h factors as h=e∘kh = e \circ k for a unique kk. (The leg to YY is forced to be fe=gef e = g e.) A pullback of f:A→Cf : A \to C and g:B→Cg : B \to C is an object PP with p1:P→Ap_1 : P \to A, p2:P→Bp_2 : P \to B, fp1=gp2f p_1 = g p_2, through which every such commuting square factors uniquely:

WW
A×CBA \times_C B
AA
BB
CC
aa
bb
uu
p1p_1
p2p_2
ff
gg
The pullback: every pair a,ba, b with fa=gbf a = g b factors through A×CBA \times_C B by a unique uu.

Definition— complete, cocomplete, preservation

C\mathcal{C} is complete if every diagram of every small shape has a limit, and cocomplete if every such diagram has a colimit. A functor F:C→DF : \mathcal{C} \to \mathcal{D} preserves a limit (lim⁡D,π)(\lim D, \pi) if (F(lim⁡D),Fπ)(F(\lim D), F\pi) is a limit of F∘DF \circ D; it preserves limits if it preserves every limit that exists. Preservation of colimits is defined dually.

Worked examplesH

Examples

Example— Limits and colimits of sets

For D:J→SetD : \mathcal{J} \to \cat{Set},

lim⁡D={(xj)∈∏jD(j)  :  D(u)(xi)=xj for all u:i→j},colim⁡D=(⨆jD(j))/∼,\lim D = \Big\{ (x_j) \in \prod_j D(j) \;:\; D(u)(x_i) = x_j \text{ for all } u : i \to j \Big\}, \qquad \operatorname{colim} D = \Big( \bigsqcup_j D(j) \Big) \Big/ {\sim},

where ∼\sim is the equivalence relation generated by x∼D(u)(x)x \sim D(u)(x) for x∈D(i)x \in D(i), u:i→ju : i \to j. The equaliser of f,g:X→Yf, g : X \to Y is {x:f(x)=g(x)}\{x : f(x) = g(x)\}; the pullback of f,gf, g is {(a,b)∈A×B:f(a)=g(b)}\{(a, b) \in A \times B : f(a) = g(b)\}; the coequaliser of f,gf, g is YY modulo the equivalence relation generated by f(x)∼g(x)f(x) \sim g(x); the pushout of A←fC→gBA \xleftarrow{f} C \xrightarrow{g} B is A⊔BA \sqcup B with f(c)f(c) glued to g(c)g(c).

Example— Special pullbacks: preimages and intersections

If m:B′↪Bm : B' \hookrightarrow B is the inclusion of a subset and f:A→Bf : A \to B, the pullback of mm along ff is {(a,b′):f(a)=b′}≅f−1(B′)\{(a, b') : f(a) = b'\} \cong f^{-1}(B'). If A′,B′⊆XA', B' \subseteq X, the pullback of the two inclusions is A′∩B′A' \cap B'. In Grp\cat{Grp} the kernel of φ:G→H\varphi : G \to H is the equaliser of φ\varphi and the trivial homomorphism, and also the pullback of φ\varphi along 1→H1 \to H.

Example— Groups and spaces

In Grp\cat{Grp}, limits are computed as in Set\cat{Set}: the equaliser of φ,ψ:G→H\varphi, \psi : G \to H is the subgroup {g:φ(g)=ψ(g)}\{g : \varphi(g) = \psi(g)\}, the pullback is the subgroup {(a,b):φ(a)=ψ(b)}\{(a, b) : \varphi(a) = \psi(b)\} of A×BA \times B. Colimits are not: the coequaliser of φ,ψ\varphi, \psi is H/NH / N, where NN is the normal subgroup generated by the elements φ(g)ψ(g)−1\varphi(g)\psi(g)^{-1}, and the pushout of A←C→BA \leftarrow C \to B is the amalgamated free product A∗CBA *_C B. In Top\cat{Top}, limits carry the coarsest topology making the legs continuous (subspaces of products), and colimits the finest making the legs continuous (quotients of disjoint unions): the pushout of D2↩S1↪D2D^2 \hookleftarrow S^1 \hookrightarrow D^2 is the sphere S2S^2, and the coequaliser identifying the endpoints of [0,1][0, 1] is the circle.

Example— Inverse limits

  • The pp-adic integers: Zp=lim←⁡Z/pnZ\Z_p = \varprojlim \Z/p^n\Z, the set of sequences (xn)(x_n) with xn∈Z/pnZx_n \in \Z/p^n\Z and xn+1≡xn(modpn)x_{n+1} \equiv x_n \pmod{p^n}, with componentwise ring operations. In Z5\Z_5, −1=(4,24,124,… )-1 = (4, 24, 124, \dots); in Z2\Z_2, 13=(1,3,3,11,11,43,… )\tfrac13 = (1, 3, 3, 11, 11, 43, \dots) because 3⋅11=33≡1(mod16)3 \cdot 11 = 33 \equiv 1 \pmod{16}.
  • The Cantor set is homeomorphic to lim←⁡{0,1}n\varprojlim \{0,1\}^n (finite discrete spaces, truncation maps), i.e. to {0,1}N\{0,1\}^{\N} with the product topology.
  • The profinite integers Z^=lim←⁡nZ/nZ\widehat{\Z} = \varprojlim_n \Z/n\Z, over the positive integers ordered by divisibility; by the Chinese remainder theorem Z^≅∏pZp\widehat{\Z} \cong \prod_p \Z_p.
001021304261537
The tower $\cdots \to \Z/8 \to \Z/4 \to \Z/2 \to \Z/1$ drawn as a tree: each residue mod $2^n$ has two lifts mod $2^{n+1}$. A $2$-adic integer is an infinite path from the root; the highlighted path $1, 3, 3, \dots$ is $\tfrac13$.

Example— Direct limits

  • Z[1p]=lim→⁡(Z→pZ→pZ→⋯ )\Z[\tfrac1p] = \varinjlim (\Z \xrightarrow{p} \Z \xrightarrow{p} \Z \to \cdots): the nn-th copy of Z\Z is p−nZ⊂Qp^{-n}\Z \subset \Q.
  • The Prüfer group Z(p∞)=lim→⁡(Z/p→pZ/p2→pZ/p3→⋯ )≅Z[1p]/Z\Z(p^\infty) = \varinjlim (\Z/p \xrightarrow{p} \Z/p^2 \xrightarrow{p} \Z/p^3 \to \cdots) \cong \Z[\tfrac1p]/\Z, the group of pp-power roots of unity.
  • Q\Q is the colimit of the groups 1nZ\frac1n \Z over the positive integers ordered by divisibility. In a poset, a colimit of an increasing sequence is its supremum.
ProofH

Theorems and proofs

Theorem— Theorem 1 (uniqueness)

If (L,π)(L, \pi) and (L′,π′)(L', \pi') are limits of DD, there is a unique isomorphism φ:L→L′\varphi : L \to L' with πj′∘φ=πj\pi'_j \circ \varphi = \pi_j for all jj. Dually for colimits.

Proof

Both are terminal objects of the category of cones over DD, and terminal objects are unique up to unique isomorphism: the unique cone morphisms φ:L→L′\varphi : L \to L' and ψ:L′→L\psi : L' \to L compose to cone endomorphisms of LL and L′L', which must be the identities by uniqueness. (This is the argument for products in the previous lesson, now for every shape at once.)

∎

Theorem— Theorem 2 (Set is complete and cocomplete)

The formulas in the first example are a limit and a colimit of D:J→SetD : \mathcal{J} \to \cat{Set} for every small J\mathcal{J}, with legs the projections πj\pi_j and the maps ιj:D(j)→colim⁡D\iota_j : D(j) \to \operatorname{colim} D, x↦[x]x \mapsto [x].

Proof

Limit. The projections form a cone because D(u)(xi)=xjD(u)(x_i) = x_j for elements of lim⁡D\lim D. Given a cone (X,λ)(X, \lambda), each x∈Xx \in X gives a compatible family (λj(x))j(\lambda_j(x))_j, so h(x)=(λj(x))jh(x) = (\lambda_j(x))_j defines h:X→lim⁡Dh : X \to \lim D with πjh=λj\pi_j h = \lambda_j; and any such hh must have jj-th coordinate λj(x)\lambda_j(x). Colimit. ιj(x)=[x]\iota_j(x) = [x] is a cocone since [x]=[D(u)(x)][x] = [D(u)(x)]. Given a cocone μj:D(j)→Y\mu_j : D(j) \to Y, define k[x]=μj(x)k[x] = \mu_j(x) for x∈D(j)x \in D(j); this is well defined because the relation {(x,y):μ(x)=μ(y)}\{(x, y) : \mu(x) = \mu(y)\} is an equivalence relation containing the generating pairs x∼D(u)(x)x \sim D(u)(x) (as μj∘D(u)=μi\mu_j \circ D(u) = \mu_i), hence containing ∼\sim. Uniqueness: kk is determined on every class [x][x].

∎

Theorem— Theorem 3 (limits from products and equalisers)

If C\mathcal{C} has all small products and all equalisers, then C\mathcal{C} has all small limits. Explicitly, for D:J→CD : \mathcal{J} \to \mathcal{C}, let

s,t:∏j∈Ob JD(j)  ⇉  ∏u:i→j in JD(j),pru∘s=prj,pru∘t=D(u)∘pris, t : \prod_{j \in \mathrm{Ob}\,\mathcal{J}} D(j) \;\rightrightarrows\; \prod_{u : i \to j \text{ in } \mathcal{J}} D(j), \qquad \mathrm{pr}_u \circ s = \mathrm{pr}_j, \quad \mathrm{pr}_u \circ t = D(u) \circ \mathrm{pr}_i

(for u:i→ju : i \to j; pr\mathrm{pr} denotes product projections). Then the equaliser e:E→∏jD(j)e : E \to \prod_j D(j) of ss and tt, with legs πj=prj∘e\pi_j = \mathrm{pr}_j \circ e, is a limit of DD.

Proof

Cone. For u:i→ju : i \to j: D(u)∘πi=D(u)∘pri∘e=pru∘t∘e=pru∘s∘e=prj∘e=πjD(u) \circ \pi_i = D(u) \circ \mathrm{pr}_i \circ e = \mathrm{pr}_u \circ t \circ e = \mathrm{pr}_u \circ s \circ e = \mathrm{pr}_j \circ e = \pi_j, using te=set e = s e.

Universal. Let (X,λ)(X, \lambda) be a cone. By the universal property of the product there is a unique ℓ:X→∏jD(j)\ell : X \to \prod_j D(j) with prj∘ℓ=λj\mathrm{pr}_j \circ \ell = \lambda_j. For every u:i→ju : i \to j,

pru∘s∘ℓ=prj∘ℓ=λj=D(u)∘λi=D(u)∘pri∘ℓ=pru∘t∘ℓ,\mathrm{pr}_u \circ s \circ \ell = \mathrm{pr}_j \circ \ell = \lambda_j = D(u) \circ \lambda_i = D(u) \circ \mathrm{pr}_i \circ \ell = \mathrm{pr}_u \circ t \circ \ell,

so sℓ=tℓs \ell = t \ell (maps into a product are determined by their components). By the universal property of the equaliser, ℓ=e∘h\ell = e \circ h for a unique h:X→Eh : X \to E, and then πj∘h=prj∘e∘h=λj\pi_j \circ h = \mathrm{pr}_j \circ e \circ h = \lambda_j. If also πj∘h′=λj\pi_j \circ h' = \lambda_j for all jj, then prj∘(eh′)=λj\mathrm{pr}_j \circ (e h') = \lambda_j for all jj, so eh′=ℓ=ehe h' = \ell = e h, and h′=hh' = h because an equaliser is a monomorphism (by the uniqueness in its universal property).

∎

In Set\cat{Set} this is exactly the formula of Theorem 2: compatible families are the tuples on which "move along uu" and "look at the target" agree. Dually, coproducts and coequalisers give all colimits. The same proof with finite products shows that a terminal object, binary products and equalisers give all finite limits; and since the pullback of f:A→Cf : A \to C, g:B→Cg : B \to C is the equaliser of f∘π1f \circ \pi_1 and g∘π2g \circ \pi_2 on A×BA \times B, products and equalisers in particular give pullbacks.

Theorem— Theorem 4 (hom functors preserve limits)

For every object AA of a locally small category C\mathcal{C}, the functor Hom(A,−):C→Set\Hom(A, -) : \mathcal{C} \to \cat{Set} preserves all limits that exist. Dually, Hom(−,B):Cop→Set\Hom(-, B) : \mathcal{C}^{\mathrm{op}} \to \cat{Set} sends colimits in C\mathcal{C} to limits in Set\cat{Set}: Hom(colim⁡D,B)≅lim⁡Hom(D(−),B)\Hom(\operatorname{colim} D, B) \cong \lim \Hom(D(-), B).

Proof

Let (L,π)(L, \pi) be a limit of DD. By Theorem 2, lim⁡Hom(A,D(−))\lim \Hom(A, D(-)) is the set of compatible families (λj:A→D(j))j(\lambda_j : A \to D(j))_j — that is, the set of cones over DD with apex AA. The map Hom(A,L)→lim⁡Hom(A,D(−))\Hom(A, L) \to \lim \Hom(A, D(-)), h↦(πj∘h)jh \mapsto (\pi_j \circ h)_j, is a bijection: that is precisely the universal property of (L,π)(L, \pi) tested on cones with apex AA. For the dual statement apply this to Cop\mathcal{C}^{\mathrm{op}}.

∎

So limits can be computed "elementwise", using generalised elements A→LA \to L: maps into a limit are compatible families of maps. For example Hom(A,X×Y)≅Hom(A,X)×Hom(A,Y)\Hom(A, X \times Y) \cong \Hom(A, X) \times \Hom(A, Y), and Hom(V⊕W,U)≅Hom(V,U)×Hom(W,U)\Hom(V \oplus W, U) \cong \Hom(V, U) \times \Hom(W, U) for vector spaces.

Theorem— Theorem 5 (forgetful functors and limits)

The forgetful functor U:Grp→SetU : \cat{Grp} \to \cat{Set} preserves all limits. It preserves neither the initial object nor binary coproducts: U(Z∗Z)U(\Z * \Z) is not the disjoint union U(Z)⊔U(Z)U(\Z) \sqcup U(\Z).

Proof

UU is naturally isomorphic to HomGrp(Z,−)\Hom_{\cat{Grp}}(\Z, -), since a homomorphism Z→G\Z \to G is determined by the image of 11, which can be any element. So Theorem 4 applies. (Directly: the set of compatible families in ∏jD(j)\prod_j D(j) is a subgroup, and it is the limit in Grp\cat{Grp}.) The initial object of Grp\cat{Grp} is the trivial group, whose underlying set has one element, not zero. For coproducts, compare the canonical map c:U(Z)⊔U(Z)→U(Z∗Z)c : U(\Z) \sqcup U(\Z) \to U(\Z * \Z) sending the two summands by ι1,ι2\iota_1, \iota_2. If UU preserved this coproduct, cc would be a bijection. Let x=ι1(1)x = \iota_1(1), y=ι2(1)y = \iota_2(1), and map Z∗Z→S3\Z * \Z \to S_3 by x↦σ=(1 2)x \mapsto \sigma = (1\,2), y↦τ=(2 3)y \mapsto \tau = (2\,3). Every element in the image of cc goes to a power of σ\sigma (which fixes 33) or a power of τ\tau (which fixes 11); but xyxy goes to στ=(1 2 3)\sigma\tau = (1\,2\,3), which fixes neither. So xy∉im⁡cxy \notin \operatorname{im} c.

∎

Theorem— Theorem 6 (units of the p-adic integers)

In Zp=lim←⁡Z/pnZ\Z_p = \varprojlim \Z/p^n\Z, an element x=(xn)nx = (x_n)_n is a unit if and only if x1≠0x_1 \neq 0 in Z/pZ\Z/p\Z. In particular every integer, and every fraction a/ba/b with p∤bp \nmid b, defines an element of Zp\Z_p.

Proof

If xy=1xy = 1 then x1y1=1x_1 y_1 = 1 in Z/p\Z/p, so x1≠0x_1 \neq 0. Conversely, if x1≠0x_1 \neq 0, then for each nn the residue xnx_n is prime to pp (it reduces to x1x_1), so it has an inverse yny_n in Z/pn\Z/p^n. The family (yn)(y_n) is compatible: yn+1 mod pny_{n+1} \bmod p^n is an inverse of xn+1 mod pn=xnx_{n+1} \bmod p^n = x_n, and inverses are unique, so it equals yny_n. By the description of limits of rings as compatible families (limits in rings are computed as in sets), y=(yn)∈Zpy = (y_n) \in \Z_p, and xy=1xy = 1 componentwise. For a/ba/b, take x=a⋅b−1x = a \cdot b^{-1}, where b=(b mod pn)nb = (b \bmod p^n)_n is a unit.

∎

The same "solve level by level, then use compatibility" strategy is Hensel's lemma: if ff is a polynomial with integer coefficients, f(x1)≡0f(x_1) \equiv 0 and f′(x1)≢0(modp)f'(x_1) \not\equiv 0 \pmod p, then x1x_1 lifts uniquely to a compatible tower of roots, i.e. to a root in Zp\Z_p. The computation below lifts the root 22 of x2+1x^2 + 1 modulo 55 to −1=(2,7,57,182,… )∈Z5\sqrt{-1} = (2, 7, 57, 182, \dots) \in \Z_5.

Formal mathematicsF

Limits and colimits in Lean

In the category of types, the constructions of Theorem 2 can be written down directly: subtypes carve out, quotients glue.

equalizer_universalLean 4Proved here from basic factsFormally verified
/-- **The equaliser in the category of types** of `f g : X → Y` is the subtype
`{x // f x = g x}` with its inclusion. Universal property: every `h : W → X` with
`f ∘ h = g ∘ h` factors through the inclusion by exactly one map `u`, namely
`u w = ⟨h w, _⟩`; uniqueness holds because an element of a subtype is determined by its value. -/
theorem equalizer_universal (f g : X → Y) (h : W → X) (hh : f ∘ h = g ∘ h) :
    ∃! u : W → {x : X // f x = g x}, Subtype.val ∘ u = h := by
  refine ⟨fun w => ⟨h w, congr_fun hh w⟩, rfl, ?_⟩
  intro u hu
  funext w
  exact Subtype.ext (congr_fun hu w)
Axioms used: Quot.soundformal/Lumenary/LimitsColimits.leanTry it in the Lean web editor
homEqualizerEquivLean 4Formally verified
/-- **Maps into an equaliser are maps that equalise.** For every type `W`, maps
`W → {x // f x = g x}` correspond bijectively to maps `h : W → X` with `f ∘ h = g ∘ h`. In other
words the hom functor `Hom(W, −)` sends the equaliser of `f, g` to the equaliser of
`f ∘ −, g ∘ −` — the simplest case of "hom functors preserve limits". -/
def homEqualizerEquiv (f g : X → Y) (W : Type u) :
    (W → {x : X // f x = g x}) ≃ {h : W → X // f ∘ h = g ∘ h} where
  toFun u := ⟨Subtype.val ∘ u, funext fun w => (u w).2⟩
  invFun h := fun w => ⟨h.1 w, congr_fun h.2 w⟩
  left_inv _ := rfl
  right_inv _ := rfl
Axioms used: Quot.soundformal/Lumenary/LimitsColimits.leanTry it in the Lean web editor
pullback_universalLean 4Proved here from basic factsFormally verified
/-- **The pullback in the category of types** of `f : A → C` and `g : B → C` is the subtype
`{(a, b) // f a = g b}` of `A × B` — the equaliser of `f ∘ fst` and `g ∘ snd`, exactly the
construction "limits from products and equalisers". Universal property: maps `a : W → A`,
`b : W → B` with `f ∘ a = g ∘ b` factor through it by exactly one map, `w ↦ (a w, b w)`. -/
theorem pullback_universal (f : A → C) (g : B → C) (a : W → A) (b : W → B)
    (hab : f ∘ a = g ∘ b) :
    ∃! u : W → {p : A × B // f p.1 = g p.2},
      (fun w => (u w).1.1) = a ∧ (fun w => (u w).1.2) = b := by
  refine ⟨fun w => ⟨(a w, b w), congr_fun hab w⟩, ⟨rfl, rfl⟩, ?_⟩
  rintro u ⟨h₁, h₂⟩
  funext w
  exact Subtype.ext (Prod.ext (congr_fun h₁ w) (congr_fun h₂ w))
Axioms used: Quot.soundformal/Lumenary/LimitsColimits.leanTry it in the Lean web editor
CoeqRelLean 4Formally verified
/-- The relation generating the **coequaliser** of `f g : X → Y`: `f x` is related to `g x`. -/
def CoeqRel (f g : X → Y) : Y → Y → Prop :=
  fun y y' => ∃ x, f x = y ∧ g x = y'
Axioms used: No axiomsformal/Lumenary/LimitsColimits.leanTry it in the Lean web editor
coequalizer_universalLean 4Proved here from basic factsFormally verified
/-- **The coequaliser in the category of types** is the quotient `Quot (CoeqRel f g)` of `Y` by
the equivalence relation generated by `f x ~ g x`, with the quotient map. Universal property:
every `h : Y → Z` with `h ∘ f = h ∘ g` factors through the quotient by exactly one map
(`Quot.lift`); uniqueness holds because every element of the quotient is a class `[y]`. Colimits
of types glue, limits of types carve out. -/
theorem coequalizer_universal (f g : X → Y) (h : Y → Z) (hh : h ∘ f = h ∘ g) :
    ∃! u : Quot (CoeqRel f g) → Z, u ∘ Quot.mk _ = h := by
  refine ⟨Quot.lift h ?_, rfl, ?_⟩
  · rintro _ _ ⟨x, rfl, rfl⟩
    exact congr_fun hh x
  · intro u hu
    funext q
    induction q using Quot.ind with
    | mk y => exact congr_fun hu y
Axioms used: Quot.soundformal/Lumenary/LimitsColimits.leanTry it in the Lean web editor

Mathlib's general theory (CategoryTheory.Limits) defines a cone exactly as in the lesson — a natural transformation from a constant functor — and proves Theorems 3 and 4 and the completeness results. Here diagrammatic composition π_j ≫ F.map f means F(f)∘πjF(f) \circ \pi_j.

cone_naturalityLean 4Applies a library theoremFormally verified
/-- **A cone is a natural transformation from a constant functor.** A cone over `F : J ⥤ C` has
an apex and legs `c.π.app j : apex ⟶ F j`; naturality of `c.π : const apex ⟶ F` at
`f : j ⟶ j'` says exactly that the legs are compatible: `F f ∘ π_j = π_j'`. This is Mathlib's
`Cone.w`. -/
theorem cone_naturality {J : Type*} [Category J] {C : Type*} [Category C] {F : J ⥤ C}
    (c : Cone F) {j j' : J} (f : j ⟶ j') : c.π.app j ≫ F.map f = c.π.app j' :=
  c.w f
Axioms used: propext, Classical.choice, Quot.soundformal/Lumenary/LimitsColimits.leanTry it in the Lean web editor
limits_of_products_equalizersLean 4Applies a library theoremFormally verified
/-- **Products and equalisers give all limits.** A category with all small products and all
equalisers has all small limits: the limit of `F` is the equaliser of two maps
`∏ⱼ F j ⇉ ∏_{u : i ⟶ j} F j`. This applies Mathlib's `has_limits_of_hasEqualizers_and_products`;
the lesson proves it. -/
theorem limits_of_products_equalizers {C : Type u} [Category.{v} C] [HasProducts.{v} C]
    [HasEqualizers C] : HasLimits C :=
  has_limits_of_hasEqualizers_and_products
Axioms used: propext, Classical.choice, Quot.soundformal/Lumenary/LimitsColimits.leanTry it in the Lean web editor
pullbacks_of_products_equalizersLean 4Applies a library theoremFormally verified
/-- **Binary products and equalisers give pullbacks**: the pullback of `f : A ⟶ C` and
`g : B ⟶ C` is the equaliser of `f ∘ π₁` and `g ∘ π₂` on `A × B`. This applies Mathlib's
`hasPullbacks_of_hasBinaryProducts_of_hasEqualizers`. -/
theorem pullbacks_of_products_equalizers (C : Type u) [Category.{v} C] [HasBinaryProducts C]
    [HasEqualizers C] : HasPullbacks C :=
  hasPullbacks_of_hasBinaryProducts_of_hasEqualizers C
Axioms used: propext, Classical.choice, Quot.soundformal/Lumenary/LimitsColimits.leanTry it in the Lean web editor
complete_cocompleteLean 4Applies a library theoremFormally verified
/-- **Completeness and cocompleteness.** Types and topological spaces have all small limits and
colimits; groups have all small limits and abelian groups all small colimits. These are Mathlib
instances (limits of types are compatible families, colimits are quotients of disjoint unions). -/
theorem complete_cocomplete :
    HasLimits (Type u) ∧ HasColimits (Type u) ∧ HasLimits TopCat.{u} ∧ HasColimits TopCat.{u} ∧
      HasLimits GrpCat.{u} ∧ HasColimits AddCommGrpCat.{u} :=
  ⟨inferInstance, inferInstance, inferInstance, inferInstance, inferInstance, inferInstance⟩
Axioms used: propext, Classical.choice, Quot.soundformal/Lumenary/LimitsColimits.leanTry it in the Lean web editor
hom_preserves_limitsLean 4Applies a library theoremFormally verified
/-- **Hom functors preserve limits.** For every object `A`, the functor
`Hom(A, −) = coyoneda.obj (op A) : C ⥤ Type v` sends limit cones to limit cones:
`Hom(A, lim F) ≅ lim Hom(A, F −)`. This is Mathlib's instance `coyoneda_preservesLimits`. -/
theorem hom_preserves_limits {C : Type u} [Category.{v} C] (A : C) :
    PreservesLimits (coyoneda.obj (op A)) :=
  inferInstance
Axioms used: propext, Classical.choice, Quot.soundformal/Lumenary/LimitsColimits.leanTry it in the Lean web editor

Theorem 5, with the non-preservation of coproducts proved by hand, as in the lesson (the permutation computations are done by decide):

forget_preserves_limitsLean 4Applies a library theoremFormally verified
/-- **The forgetful functor `Grp → Set` preserves limits**: the underlying set of a limit of
groups is the limit of the underlying sets (Mathlib's `GrpCat.forget_preservesLimits`). -/
theorem forget_preserves_limits : PreservesLimits (forget GrpCat.{u}) :=
  inferInstance
Axioms used: propext, Classical.choice, Quot.soundformal/Lumenary/LimitsColimits.leanTry it in the Lean web editor
forget_not_preserves_coproductLean 4Proved here from basic factsFormally verified
/-- **…but not coproducts.** If the forgetful functor preserved the coproduct `ℤ ∗ ℤ`, the
canonical map from the disjoint union `ℤ ⊔ ℤ` of underlying sets to the underlying set of `ℤ ∗ ℤ`
(sending the summands by `inl`, `inr`) would be a bijection. It is not even surjective: `x y`
(with `x = inl 1`, `y = inr 1`) is not in its image. Proof: map `ℤ ∗ ℤ → S₃` by `x ↦ (0 1)`,
`y ↦ (1 2)` (universal property). Every `inl n` goes to a power of `(0 1)`, which fixes `2`;
every `inr n` to a power of `(1 2)`, which fixes `0`; but `x y` goes to `(0 1)(1 2)`, which moves
both `0` and `2`. -/
theorem forget_not_preserves_coproduct :
    ¬ Function.Surjective (Sum.elim (inl : Multiplicative ℤ →* _) (inr : Multiplicative ℤ →* _) :
      Multiplicative ℤ ⊕ Multiplicative ℤ → Multiplicative ℤ ∗ Multiplicative ℤ) := by
  intro hsurj
  let σ : Equiv.Perm (Fin 3) := Equiv.swap 0 1
  let τ : Equiv.Perm (Fin 3) := Equiv.swap 1 2
  let φ := lift (zpowersHom (Equiv.Perm (Fin 3)) σ) (zpowersHom (Equiv.Perm (Fin 3)) τ)
  obtain ⟨z, hz⟩ := hsurj (inl (Multiplicative.ofAdd 1) * inr (Multiplicative.ofAdd 1))
  have key : φ (inl (Multiplicative.ofAdd 1) * inr (Multiplicative.ofAdd 1)) = σ * τ := by
    simp [φ]
  rcases z with n | n
  · -- `φ (inl n) = σ ^ n` fixes `2`, but `σ * τ` does not.
    have h₁ : φ (inl n) 2 = 2 := by
      simp only [φ, lift_apply_inl, zpowersHom_apply]
      exact Equiv.Perm.zpow_apply_eq_self_of_apply_eq_self (by decide) _
    have h₂ : (σ * τ) 2 ≠ 2 := by decide
    simp only [Sum.elim_inl] at hz
    rw [hz, key] at h₁
    exact h₂ h₁
  · -- `φ (inr n) = τ ^ n` fixes `0`, but `σ * τ` does not.
    have h₁ : φ (inr n) 0 = 0 := by
      simp only [φ, lift_apply_inr, zpowersHom_apply]
      exact Equiv.Perm.zpow_apply_eq_self_of_apply_eq_self (by decide) _
    have h₂ : (σ * τ) 0 ≠ 0 := by decide
    simp only [Sum.elim_inr] at hz
    rw [hz, key] at h₁
    exact h₂ h₁
Axioms used: propext, Classical.choice, Quot.soundformal/Lumenary/LimitsColimits.leanTry it in the Lean web editor

Mathlib constructs Zp\Z_p analytically (as the completion of Z\Z for the pp-adic norm) and proves that it is the inverse limit of the rings Z/pn\Z/p^n — the two descriptions agree:

padic_inverse_limitLean 4Applies a library theoremFormally verified
/-- **`ℤ_p` is the inverse limit of the rings `ℤ/pⁿ`.** The reduction maps
`toZModPow n : ℤ_[p] → ℤ/pⁿ` form a cone (they are compatible with the reductions
`ℤ/pⁿ → ℤ/pᵐ`, `m ≤ n`), and it is a limit cone in rings: every compatible family of ring maps
`f n : R → ℤ/pⁿ` comes from exactly one ring map `R → ℤ_[p]`. This applies Mathlib's
`PadicInt.zmod_cast_comp_toZModPow`, `PadicInt.lift_spec` and `PadicInt.lift_unique`. -/
theorem padic_inverse_limit (p : ℕ) [Fact p.Prime] {R : Type*} [NonAssocSemiring R]
    (f : ∀ k : ℕ, R →+* ZMod (p ^ k))
    (f_compat : ∀ (k₁ k₂ : ℕ) (hk : k₁ ≤ k₂),
      (ZMod.castHom (pow_dvd_pow p hk) _).comp (f k₂) = f k₁) :
    (∀ (m n : ℕ) (h : m ≤ n),
      (ZMod.castHom (pow_dvd_pow p h) (ZMod (p ^ m))).comp (PadicInt.toZModPow n) =
        PadicInt.toZModPow m) ∧
    ∃! g : R →+* ℤ_[p], ∀ n, (PadicInt.toZModPow n).comp g = f n :=
  ⟨PadicInt.zmod_cast_comp_toZModPow, PadicInt.lift f_compat, PadicInt.lift_spec f_compat,
    fun g hg => (PadicInt.lift_unique f_compat g hg).symm⟩
Axioms used: propext, Classical.choice, Quot.soundformal/Lumenary/LimitsColimits.leanTry it in the Lean web editor

Finally the meeting point of the two meanings of "limit":

increasing_limit_is_colimitLean 4Applies a library theoremFormally verified
/-- **When the two meanings of "limit" meet.** In the poset `(ℝ, ≤)` regarded as a category, an
increasing sequence `u 0 ≤ u 1 ≤ ⋯` is a diagram of shape `ℕ`, and its colimit is its least upper
bound. For such a sequence, converging to `L` (analysis) is the same as `L` being the least upper
bound of its values (category theory). This applies Mathlib's `isLUB_of_tendsto_atTop` and
`tendsto_atTop_isLUB`. -/
theorem increasing_limit_is_colimit {u : ℕ → ℝ} (hu : Monotone u) (L : ℝ) :
    Tendsto u atTop (𝓝 L) ↔ IsLUB (Set.range u) L :=
  ⟨isLUB_of_tendsto_atTop hu, tendsto_atTop_isLUB hu⟩
Axioms used: propext, Classical.choice, Quot.soundformal/Lumenary/LimitsColimits.leanTry it in the Lean web editor

Not formalised here: Theorem 6 in the compatible-family model, and the explicit colimit formula for arbitrary diagrams of types (Mathlib: Types.colimitEquivQuot).

ComputationC

Experiments: compatible families, gluing, and towers of residues

The first experiment computes limits of small diagrams of finite sets in two ways — as compatible families, and by the construction of Theorem 3 as an equaliser of two maps between products — and checks that they agree. It then computes colimits by gluing with a union–find, and counts reduced words in Z/2∗Z/3\Z/2 * \Z/3 to watch the forgetful functor fail to preserve a coproduct.

Limits and colimits of finite sets, computed two waysPythonExact computationExhaustive finite checkComputationally tested
"""Limits and colimits of finite sets, computed two ways, and a functor that
fails to preserve a coproduct.

A diagram of finite sets is given by objects (sets) and arrows (functions);
we take diagrams with no composable arrows, so no composites need listing.
Its limit is the set of compatible families; the theorem "products and
equalisers give all limits" builds it instead as an equaliser of two maps
between products. We compute both and compare. Colimits glue: the colimit is
the disjoint union of the objects modulo x ~ f(x), computed with a union-find.
Finally, counting reduced words in Z/2 * Z/3 shows that the underlying set of
a coproduct of groups is far bigger than the coproduct of the underlying sets.
"""

from itertools import product

def sections(objects, arrows):
    """Compatible families: one element per object, with f(x_src) = x_dst."""
    names = sorted(objects)
    out = []
    for choice in product(*(objects[n] for n in names)):
        x = dict(zip(names, choice))
        if all(f[x[s]] == x[t] for s, t, f in arrows):
            out.append(x)
    return out

def limit_via_equaliser(objects, arrows):
    """Equaliser of the two maps prod_j D(j) -> prod_(u : s -> t) D(t),
    x |-> (x_t)_u and x |-> (u(x_s))_u. Returns the equalised families."""
    names = sorted(objects)
    families = [dict(zip(names, c)) for c in product(*(objects[n] for n in names))]
    first = [tuple(x[t] for s, t, f in arrows) for x in families]
    second = [tuple(f[x[s]] for s, t, f in arrows) for x in families]
    return [x for x, a, b in zip(families, first, second) if a == b]

def colimit_classes(objects, arrows):
    """Classes of the disjoint union of the objects under x ~ f(x)."""
    parent = {(n, x): (n, x) for n in objects for x in objects[n]}

    def find(v):
        while parent[v] != v:
            parent[v] = parent[parent[v]]
            v = parent[v]
        return v

    for s, t, f in arrows:
        for x in objects[s]:
            parent[find((s, x))] = find((t, f[x]))
    classes = {}
    for v in parent:
        classes.setdefault(find(v), []).append(v)
    return sorted(sorted(c) for c in classes.values())

def reduced_words(max_len):
    """Number of reduced words of each length <= max_len in Z/2 * Z/3: letters
    alternate between a (from Z/2) and b, b^2 (from Z/3)."""
    counts = [1]
    for n in range(1, max_len + 1):
        start_a = 2 ** (n // 2)            # a ? a ? ...
        start_b = 2 ** ((n + 1) // 2)      # ? a ? a ...
        counts.append(start_a + start_b)
    return counts

def main():
    A, B, C = range(4), range(3), range(2)
    cospan = {"A": A, "B": B, "C": C}
    cospan_arrows = [("A", "C", {a: a % 2 for a in A}),
                     ("B", "C", {b: (b + 1) % 2 for b in B})]
    pair = {"X": range(6), "Y": range(3)}
    pair_arrows = [("X", "Y", {x: x % 3 for x in range(6)}),
                   ("X", "Y", {x: (2 * x) % 3 for x in range(6)})]
    span = {"K": range(2), "P": range(3), "Q": range(4)}
    span_arrows = [("K", "P", {0: 0, 1: 2}), ("K", "Q", {0: 0, 1: 3})]
    print("Limits as compatible families and via products + equaliser:")
    for name, obj, arr in [("pullback A -> C <- B", cospan, cospan_arrows),
                           ("equaliser X => Y", pair, pair_arrows)]:
        s, e = sections(obj, arr), limit_via_equaliser(obj, arr)
        print(f"  {name:<22} families: {len(s)}, equaliser: {len(e)}, "
              f"same: {s == e}")
    print()
    print("Colimits as glued disjoint unions:")
    glued = colimit_classes(span, span_arrows)
    print(f"  pushout P <- K -> Q    {len(glued)} classes "
          f"(= 3 + 4 - 2: two paths glued at both ends)")
    coeq = colimit_classes(pair, pair_arrows)
    print(f"  coequaliser X => Y     {len(coeq)} classes: Y = {{0, 1, 2}} with 1 ~ 2")
    print()
    words = reduced_words(8)
    print("The forgetful functor Grp -> Set and coproducts:")
    print("  |Z/2 x Z/3| = 6 = 2 * 3, the product of the underlying sets, but")
    print("  |Z/2 + Z/3| = 5 as sets, while Z/2 * Z/3 has reduced words of")
    print(f"  length 0..8 numbering {words},")
    print(f"  {sum(words)} so far - and the lengths never stop.")
    print()
    print("Epistemic status: exact computations on finite examples. They illustrate")
    print("the constructions; that limits are equalisers of products in general,")
    print("and that Z/2 * Z/3 is infinite, are theorems proved in the lesson.")

if __name__ == "__main__":
    main()
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

The second builds points of Zp=lim←⁡Z/pn\Z_p = \varprojlim \Z/p^n as compatible towers of residues, including a square root of −1-1 in Z5\Z_5 found by Hensel lifting, and counts solutions of x2=ax^2 = a modulo 5n5^n.

The p-adic integers as compatible towers of residuesPythonExact computationExhaustive finite checkComputationally tested
"""The p-adic integers as an inverse limit: compatible towers of residues.

A point of the inverse limit of ... -> Z/p^3 -> Z/p^2 -> Z/p is a sequence of
residues x_n mod p^n with x_(n+1) = x_n (mod p^n). We build such towers for -1
and 1/3 (a fraction with denominator prime to p), and for a square root of -1
in the 5-adic integers by Hensel lifting; we check compatibility and that the
ring operations work level by level. Counting the solutions of x^2 = a modulo
p^n shows how many points the limit has: two square roots of -1 in Z_5, none
of 2.
"""

def tower_of_fraction(num, den, p, levels):
    """Residues of num/den modulo p, p^2, ..., p^levels (den prime to p)."""
    if den % p == 0:
        raise ValueError("denominator must be prime to p")
    return [num * pow(den, -1, p ** n) % p ** n for n in range(1, levels + 1)]

def is_compatible(tower, p):
    """Does x_(n+1) reduce to x_n modulo p^n for every level n?"""
    return all(tower[n + 1] % p ** (n + 1) == tower[n] % p ** (n + 1)
               for n in range(len(tower) - 1))

def hensel_sqrt(a, p, x1, levels):
    """Lift a root x1 of x^2 = a (mod p), with 2 x1 invertible mod p, to a
    compatible tower of roots modulo p^n (Newton's method)."""
    if (x1 * x1 - a) % p or (2 * x1) % p == 0:
        raise ValueError("need x1^2 = a and 2 x1 != 0 modulo p")
    tower, x = [x1 % p], x1 % p
    for n in range(2, levels + 1):
        m = p ** n
        x = (x - (x * x - a) * pow(2 * x, -1, m)) % m
        tower.append(x)
    return tower

def roots_mod(a, m):
    """All x mod m with x^2 = a (mod m), by exhaustive search."""
    return [x for x in range(m) if (x * x - a) % m == 0]

def levelwise(op, s, t, p):
    """Apply a ring operation to two towers level by level."""
    return [op(x, y) % p ** (n + 1) for n, (x, y) in enumerate(zip(s, t))]

def main():
    minus_one = tower_of_fraction(-1, 1, 5, 6)
    third = tower_of_fraction(1, 3, 2, 8)
    i5 = hensel_sqrt(-1, 5, 2, 6)
    print("Towers x_n mod p^n (n = 1, 2, ...):")
    print(f"  -1  in Z_5: {minus_one}")
    print(f"  1/3 in Z_2: {third}")
    print(f"  sqrt(-1) in Z_5: {i5}")
    print("Compatible (x_(n+1) = x_n mod p^n): "
          f"{is_compatible(minus_one, 5)}, {is_compatible(third, 2)}, "
          f"{is_compatible(i5, 5)}")
    square = levelwise(lambda x, y: x * y, i5, i5, 5)
    three = [3 % 2 ** (n + 1) for n in range(8)]
    one = levelwise(lambda x, y: x * y, three, third, 2)
    print(f"Levelwise: sqrt(-1)^2 = -1 at every level: {square == minus_one}; "
          f"3 * (1/3) = 1: {set(one) == {1}}")
    fake = [n % 5 ** n for n in range(1, 7)]
    print(f"Not a point of the limit: x_n = n mod 5^n {fake[:4]}... compatible: "
          f"{is_compatible(fake, 5)}")
    print()
    print("Solutions modulo 5^n:   n = 1  2  3  4  5  6")
    for a in (-1, 2):
        counts = [len(roots_mod(a, 5 ** n)) for n in range(1, 7)]
        print(f"  x^2 = {a:>2}:              " + "  ".join(map(str, counts)))
    print("As Hensel's lemma predicts, each root mod 5^n lifts to exactly one root")
    print("mod 5^(n+1): Z_5 has two square roots of -1, and none of 2.")
    print()
    print("Epistemic status: exact modular arithmetic for the levels shown, with")
    print("an exhaustive count of roots up to 5^6. Finitely many levels never")
    print("pin down a p-adic integer; that compatible towers are exactly the points")
    print("of Z_p (and Hensel's lemma for all levels) is proved, not computed.")

if __name__ == "__main__":
    main()
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.
Explore

Explore: the shapes side by side

Read each diagram as a recipe. The equaliser ee is the universal arrow that makes the parallel pair agree; the coequaliser qq is the universal arrow that makes it agree after the pair; the pushout glues AA and BB along CC. Compare each with its mirror image and check which arrows are dashed (induced uniquely).

WW
EE
XX
YY
QQ
ZZ
kk
hh
ee
ff
gg
qq
rr
r′r'
Equaliser (left): if fh=ghf h = g h then h=ekh = e k for a unique kk. Coequaliser (right): if rf=rgr f = r g then r=r′qr = r' q for a unique r′r'.
CC
BB
AA
A⊔CBA \sqcup_C B
YY
gg
ff
ι2\iota_2
ι1\iota_1
bb
aa
uu
The pushout glues AA and BB along CC: maps a,ba, b agreeing on CC (af=bga f = b g) induce a unique uu. For A=B=D2A = B = D^2, C=S1C = S^1 it is the sphere.
Exercises

Exercises

1. Limits and colimits

Warm-upHuman

Which shape J\mathcal{J} has the pullback as the limit of a diagram of that shape?

Choose one

2. Limits and colimits

CoreHuman

Let A={1,…,6}A = \{1, \dots, 6\}, B={1,2,3,4}B = \{1, 2, 3, 4\}, C={0,1,2}C = \{0, 1, 2\}, and f:A→Cf : A \to C, g:B→Cg : B \to C both be “remainder modulo 3”. How many elements does the pullback A×CBA \times_C B have in Set\cat{Set}?

3. Limits and colimits

CoreHuman

In Ab\cat{Ab}, what is the equaliser of f,g:Z→Z/6f, g : \Z \to \Z/6 given by f(n)=n mod 6f(n) = n \bmod 6 and g(n)=3n mod 6g(n) = 3n \bmod 6?

Choose one

4. Limits and colimits

CoreHuman

In the proof that products and equalisers give all limits, the limit of DD is the equaliser of two maps s,t:∏jD(j)⇉∏u:i→jD(j)s, t : \prod_j D(j) \rightrightarrows \prod_{u : i \to j} D(j). What is the uu-component of tt (for u:i→ju : i \to j)?

Choose one

5. Limits and colimits

StretchHuman

Which of these functors preserve all limits? Select all that apply.

Choose all that apply

6. Limits and colimits

CoreComputational

In Z2=lim←⁡Z/2n\Z_2 = \varprojlim \Z/2^n, the element 13\tfrac13 is a compatible tower (x1,x2,x3,… )(x_1, x_2, x_3, \dots) with 3xn≡1(mod2n)3x_n \equiv 1 \pmod{2^n}. What is x5∈{0,1,…,31}x_5 \in \{0, 1, \dots, 31\}?

7. Limits and colimits

StretchHuman

Regard (Q,≤)(\Q, \le) as a category. The increasing sequence 3≤3.1≤3.14≤3.141≤⋯3 \le 3.1 \le 3.14 \le 3.141 \le \cdots of decimal truncations of π\pi is a diagram of shape (N,≤)(\N, \le). What is its colimit?

Choose one

8. Limits and colimits

CoreFormal

Which Lean statement expresses the universal property of the equaliser {x//fx=gx}\{x // f x = g x\} of f g : X → Y in the category of types?

Choose one

9. Limits and colimits

CoreComputational

Write pullback(A, B, f, g) returning the pullback of f : A → C and g : B → C in finite sets, as the list of pairs (a, b) with f[a] == g[b] (here A, B are lists and f, g dicts). Then pullback_size(A, B, f, g) should return its size computed fibre by fibre, without forming the pairs.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.
Common misconceptionsH

Common misconceptions

Misconception

"A categorical limit is a limit of a sequence." They are different notions that occasionally meet. In the poset (R,≤)(\R, \le), an increasing sequence u0≤u1≤⋯u_0 \le u_1 \le \cdots is a diagram of shape N\N, its colimit is its supremum, and for a convergent increasing sequence the supremum is the analytic limit (formalised above). But a sequence that oscillates, such as (−1)n/n(-1)^n/n, is not a diagram in (R,≤)(\R, \le) at all, and categorical limits of most diagrams (equalisers, pullbacks) have nothing to do with convergence. Even the meeting point is a colimit, not a limit — the terminology runs against intuition here.

Misconception

"Forgetful functors preserve colimits as they preserve limits." U:Grp→SetU : \cat{Grp} \to \cat{Set} preserves all limits, but not coproducts (U(Z∗Z)≠U(Z)⊔U(Z)U(\Z * \Z) \neq U(\Z) \sqcup U(\Z)) and not the initial object (the trivial group has one element). Colimits of algebraic structures must generate new elements (words, products of images), while limits are carved out of products. Which one a functor preserves is information about it — in the next lesson, the sign that UU is a right adjoint.

Misconception

"Every diagram has a limit, because a universal property defines one." Existence depends on the category. In (Q,≤)(\Q, \le) the increasing sequence 3,3.1,3.14,3.141,…3, 3.1, 3.14, 3.141, \dots of decimal truncations of π\pi has no colimit; in the category of fields F2\mathbb{F}_2 and F3\mathbb{F}_3 have no product; the category of finite sets has no infinite product of two-element sets.

Misconception

"Limits of algebraic objects can be computed on underlying sets, so colimits can too." The first half is true in Grp\cat{Grp}, Ring\cat{Ring}, Vectk\cat{Vect}_k and similar categories (forgetful functors to Set\cat{Set} preserve limits); the second is false. A coequaliser in Grp\cat{Grp} quotients by a normal subgroup, not by an equivalence relation on the set, and a coproduct is a free product.

ViewpointsH

Viewpoints

Topology— Profinite spaces and gluing

Inverse limits of finite discrete spaces are profinite spaces: compact, Hausdorff and totally disconnected (and every such space arises this way). The Cantor set lim←⁡{0,1}n\varprojlim \{0,1\}^n, the pp-adic integers Zp\Z_p and Z^\widehat{\Z} are examples; compactness comes from Tychonoff's theorem, since a limit of compact Hausdorff spaces is a closed subspace of their product. In Zp\Z_p two integers are close when they agree modulo a high power of pp — the tree picture above is literally the topology, with basic open sets the branches.

Colimits glue. A CW complex is a sequential colimit of skeleta, each obtained from the last by a pushout attaching cells, and the Seifert–van Kampen theorem says that the fundamental group turns a suitable pushout of spaces (X=U∪VX = U \cup V with U,VU, V open, and UU, VV, U∩VU \cap V path-connected, base point in U∩VU \cap V) into a pushout of groups: π1(X)≅π1(U)∗π1(U∩V)π1(V)\pi_1(X) \cong \pi_1(U) *_{\pi_1(U \cap V)} \pi_1(V). See the fundamental group.

Number theory— Towers of congruences

Solving a polynomial equation f(x)=0f(x) = 0 in Zp\Z_p is the same as solving it modulo pnp^n for every nn, compatibly: a root in Zp\Z_p is a point of the limit of the finite solution sets {x∈Z/pn:f(x)≡0}\{x \in \Z/p^n : f(x) \equiv 0\}. Hensel's lemma lifts simple roots uniquely, so x2=−1x^2 = -1 has exactly two solutions in Z5\Z_5 (lifting ±2\pm 2) and none in Z3\Z_3 (none modulo 33). The same pattern runs through modern number theory: Z^=lim←⁡Z/n\widehat{\Z} = \varprojlim \Z/n is the absolute Galois group of every finite field, and in general the absolute Galois group Gal(K‾/K)\mathrm{Gal}(\overline{K}/K) is the inverse limit of the finite groups Gal(L/K)\mathrm{Gal}(L/K) over finite Galois extensions LL, with Krull's profinite topology (1928). See elementary number theory and algebraic number theory.

Analysis— Two completions of the integers

Analysis builds Zp\Z_p differently: complete Z\Z with respect to the pp-adic absolute value ∣x∣p=p−vp(x)|x|_p = p^{-v_p(x)}, exactly as R\R completes Q\Q for the usual one. The inverse limit description is the same object — a Cauchy sequence for ∣⋅∣p|\cdot|_p is eventually constant modulo each pnp^n, and the sequence of those eventual residues is a compatible tower (Mathlib proves exactly this equivalence). Categorical limits also hide in order-theoretic analysis: the supremum of a bounded set of reals is its colimit in (R,≤)(\R, \le), and the completeness axiom of R\R says that every non-empty bounded-above diagram in (R,≤)(\R, \le) has a colimit. By Ostrowski's theorem the usual and the pp-adic absolute values are, up to equivalence, the only non-trivial absolute values on Q\Q, so these are all the completions of Q\Q.

Geometry— Fibre products and the sheaf condition

Pullbacks are fibre products: the fibre of a map f:X→Yf : X \to Y over yy is the pullback of ff along {y}↪Y\{y\} \hookrightarrow Y, and the intersection of two submanifolds is a pullback of inclusions. In smooth manifolds, pullbacks along transverse maps exist and are manifolds; in general they need not — the zero set of (x,y)↦xy(x, y) \mapsto xy is the union of the two axes — and the category of smooth manifolds does not have all pullbacks. Algebraic geometry repairs this by working with schemes (where all fibre products exist) and, later, derived schemes.

Locality is an equaliser. A presheaf FF on a space is a sheaf when, for every open cover U=⋃UiU = \bigcup U_i, the diagram F(U)→∏iF(Ui)⇉∏i,jF(Ui∩Uj)F(U) \to \prod_i F(U_i) \rightrightarrows \prod_{i, j} F(U_i \cap U_j) is an equaliser: compatible local sections glue uniquely. See sheaves.

Algebra— Direct limits and exactness

Direct limits build big algebraic objects from small ones: Q\Q from the groups 1nZ\frac1n\Z, the Prüfer group from the cyclic groups Z/pn\Z/p^n, the algebraic closure of Fp\mathbb{F}_p as the union of the fields Fpn!\mathbb{F}_{p^{n!}}, the localisation S−1RS^{-1}R from copies of RR. Filtered colimits of modules are exact — they preserve short exact sequences — which is why "a module is a union of its finitely generated submodules" is such a useful reduction. Inverse limits are only left exact. Apply lim←⁡\varprojlim to the short exact sequences 0→Z→pnZ→Z/pn→00 \to \Z \xrightarrow{p^n} \Z \to \Z/p^n \to 0, arranged into towers (multiplication by pp on the first copies of Z\Z, the identity on the second, reduction on the third): the limits are 00, Z\Z and Zp\Z_p, and Z→Zp\Z \to \Z_p is not surjective. The failure is measured by the derived functor lim←⁡1\varprojlim^1 (here lim←⁡1≅Zp/Z\varprojlim^1 \cong \Z_p/\Z), a first glimpse of homological algebra.

Category theory— Limits are right adjoints

For a fixed shape J\mathcal{J}, a cone over DD with apex XX is a natural transformation ΔX⇒D\Delta X \Rightarrow D, so the universal property of the limit says HomC(X,lim⁡D)≅Hom[J,C](ΔX,D)\Hom_{\mathcal{C}}(X, \lim D) \cong \Hom_{[\mathcal{J}, \mathcal{C}]}(\Delta X, D), naturally in XX and DD. That is, lim⁡:[J,C]→C\lim : [\mathcal{J}, \mathcal{C}] \to \mathcal{C} is right adjoint to the diagonal functor Δ\Delta, and dually colim⁡⊣Δ\operatorname{colim} \dashv \Delta. In the next lesson this turns into the key theorem: right adjoints preserve limits. Limits are also special Kan extensions, along the functor J→1\mathcal{J} \to \mathbf{1}.

Wonder Trails

Wonder Trails

History & global context

History and global context

  • Kurt Hensel introduced the pp-adic numbers in 1897, by analogy between numbers and functions (expanding a number "around a prime" like a function around a point). Alexander Ostrowski classified the absolute values on Q\Q in 1916.
  • Inverse and direct limits grew up in topology and algebra in the 1920s and 1930s: Leopold Vietoris (1927) and David van Dantzig (1930) studied solenoids as inverse limits, Wolfgang Krull (1928) put the profinite topology on infinite Galois groups, and Eduard Čech and Solomon Lefschetz used limits over open covers to define cohomology and homology for general spaces.
  • Daniel Kan's "Adjoint functors" (1958) defined limits and colimits of arbitrary diagrams in a category ("inverse and direct limits") and characterised them by adjunctions. The construction of all limits from products and equalisers is standard in the texts of the 1960s and 70s; Mac Lane's Categories for the Working Mathematician (1971) gave it its definitive form.
  • The sheaf condition as an equaliser comes from Jean Leray's work on sheaves (1940s) and the reformulations of Henri Cartan, Roger Godement and Alexander Grothendieck in the 1950s.
Further reading

Further reading

  • Emily Riehl, Category Theory in Context (2016), Chapter 3 — limits and colimits with many examples, including the construction from products and equalisers.
  • Tom Leinster, Basic Category Theory (2014), Chapters 5 and 6 — limits, and their interaction with adjoints.
  • Saunders Mac Lane, Categories for the Working Mathematician (2nd edition, 1998), Chapters III and V.
  • Fernando Q. Gouvêa, p-adic Numbers: An Introduction (2nd edition, 1997) — the analytic and inverse-limit constructions of Zp\Z_p, and Hensel's lemma.
  • Luis Ribes and Pavel Zalesskii, Profinite Groups (2nd edition, 2010), Chapter 1 — inverse limits of finite groups.
  • Saunders Mac Lane and Ieke Moerdijk, Sheaves in Geometry and Logic (1992), Chapter II — the sheaf condition as an equaliser.