Solving, intersecting, gluing, approximating
Here are some constructions from across mathematics.
- The solution set of an equation between two maps.
- The kernel of a homomorphism, and the intersection of two subgroups or subspaces.
- The preimage of a subset, and the fibre product .
- The -adic integers, built from the rings by taking all compatible sequences of residues.
- Quotients , the sphere obtained by gluing two discs along their boundary circles, the rationals as a union of the groups .
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.
Cones: compatible families, everywhere at once
A diagram is a picture of objects and arrows in a category — a cospan , a parallel pair , a tower . A cone over the diagram is an object with one arrow to each object of the diagram, compatible with all the arrows of the diagram: whichever path you follow from 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 , take . 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 compatible family is with : the fibre product. For the tower of rings , it is a sequence of residues, each reducing to the previous one: a -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 it is the disjoint union of all the objects, with glued to for every arrow of the diagram.
Limits carve out, colimits glue together.
Definitions
Throughout, is a category and a small category, the shape. Composition is written .
Definition— diagram
A diagram of shape in is a functor . For an object of , the constant diagram sends every object to and every arrow to .
Definition— cone and limit
A cone over with apex is a natural transformation . Concretely: arrows , one for each object of , with for every arrow of . A morphism of cones is an arrow with for all . A limit of is a terminal object of the category of cones: for every cone there is a unique with for all .
Definition— cocone and colimit
A cocone under is a natural transformation , and a colimit is an initial cocone. Equivalently, a colimit of is a limit of .
Definition— the basic shapes
| shape | limit | colimit |
|---|---|---|
| no objects | terminal object | initial object |
| two objects, no arrows | product | coproduct |
| parallel pair | equaliser of | coequaliser of |
| cospan | pullback | — |
| span | — | pushout |
| tower () | inverse limit | — |
| chain () | — | direct (sequential) limit |
Unpacked, an equaliser of is an arrow with such that every with factors as for a unique . (The leg to is forced to be .) A pullback of and is an object with , , , through which every such commuting square factors uniquely:
Definition— complete, cocomplete, preservation
is complete if every diagram of every small shape has a limit, and cocomplete if every such diagram has a colimit. A functor preserves a limit if is a limit of ; it preserves limits if it preserves every limit that exists. Preservation of colimits is defined dually.
Examples
Example— Limits and colimits of sets
For ,
where is the equivalence relation generated by for , . The equaliser of is ; the pullback of is ; the coequaliser of is modulo the equivalence relation generated by ; the pushout of is with glued to .
Example— Special pullbacks: preimages and intersections
If is the inclusion of a subset and , the pullback of along is . If , the pullback of the two inclusions is . In the kernel of is the equaliser of and the trivial homomorphism, and also the pullback of along .
Example— Groups and spaces
In , limits are computed as in : the equaliser of is the subgroup , the pullback is the subgroup of . Colimits are not: the coequaliser of is , where is the normal subgroup generated by the elements , and the pushout of is the amalgamated free product . In , 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 is the sphere , and the coequaliser identifying the endpoints of is the circle.
Example— Inverse limits
- The -adic integers: , the set of sequences with and , with componentwise ring operations. In , ; in , because .
- The Cantor set is homeomorphic to (finite discrete spaces, truncation maps), i.e. to with the product topology.
- The profinite integers , over the positive integers ordered by divisibility; by the Chinese remainder theorem .
Example— Direct limits
- : the -th copy of is .
- The Prüfer group , the group of -power roots of unity.
- is the colimit of the groups over the positive integers ordered by divisibility. In a poset, a colimit of an increasing sequence is its supremum.
Theorems and proofs
Theorem— Theorem 1 (uniqueness)
If and are limits of , there is a unique isomorphism with for all . Dually for colimits.
Proof
Both are terminal objects of the category of cones over , and terminal objects are unique up to unique isomorphism: the unique cone morphisms and compose to cone endomorphisms of and , 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 for every small , with legs the projections and the maps , .
Proof
Limit. The projections form a cone because for elements of . Given a cone , each gives a compatible family , so defines with ; and any such must have -th coordinate . Colimit. is a cocone since . Given a cocone , define for ; this is well defined because the relation is an equivalence relation containing the generating pairs (as ), hence containing . Uniqueness: is determined on every class .
∎
Theorem— Theorem 3 (limits from products and equalisers)
If has all small products and all equalisers, then has all small limits. Explicitly, for , let
(for ; denotes product projections). Then the equaliser of and , with legs , is a limit of .
Proof
Cone. For : , using .
Universal. Let be a cone. By the universal property of the product there is a unique with . For every ,
so (maps into a product are determined by their components). By the universal property of the equaliser, for a unique , and then . If also for all , then for all , so , and because an equaliser is a monomorphism (by the uniqueness in its universal property).
∎
In this is exactly the formula of Theorem 2: compatible families are the tuples on which "move along " 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 , is the equaliser of and on , products and equalisers in particular give pullbacks.
Theorem— Theorem 4 (hom functors preserve limits)
For every object of a locally small category , the functor preserves all limits that exist. Dually, sends colimits in to limits in : .
Proof
Let be a limit of . By Theorem 2, is the set of compatible families — that is, the set of cones over with apex . The map , , is a bijection: that is precisely the universal property of tested on cones with apex . For the dual statement apply this to .
∎
So limits can be computed "elementwise", using generalised elements : maps into a limit are compatible families of maps. For example , and for vector spaces.
Theorem— Theorem 5 (forgetful functors and limits)
The forgetful functor preserves all limits. It preserves neither the initial object nor binary coproducts: is not the disjoint union .
Proof
is naturally isomorphic to , since a homomorphism is determined by the image of , which can be any element. So Theorem 4 applies. (Directly: the set of compatible families in is a subgroup, and it is the limit in .) The initial object of is the trivial group, whose underlying set has one element, not zero. For coproducts, compare the canonical map sending the two summands by . If preserved this coproduct, would be a bijection. Let , , and map by , . Every element in the image of goes to a power of (which fixes ) or a power of (which fixes ); but goes to , which fixes neither. So .
∎
Theorem— Theorem 6 (units of the p-adic integers)
In , an element is a unit if and only if in . In particular every integer, and every fraction with , defines an element of .
Proof
If then in , so . Conversely, if , then for each the residue is prime to (it reduces to ), so it has an inverse in . The family is compatible: is an inverse of , and inverses are unique, so it equals . By the description of limits of rings as compatible families (limits in rings are computed as in sets), , and componentwise. For , take , where is a unit.
∎
The same "solve level by level, then use compatibility" strategy is Hensel's lemma: if is a polynomial with integer coefficients, and , then lifts uniquely to a compatible tower of roots, i.e. to a root in . The computation below lifts the root of modulo to .
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.
/-- **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)/-- **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/-- **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))/-- 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'/-- **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 yMathlib'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 .
/-- **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/-- **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/-- **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/-- **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⟩/-- **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)) :=
inferInstanceTheorem 5, with the non-preservation of coproducts proved by hand, as in the lesson (the permutation computations are done by decide):
/-- **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/-- **…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₁Mathlib constructs analytically (as the completion of for the -adic norm) and proves that it is the inverse limit of the rings — the two descriptions agree:
/-- **`ℤ_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⟩Finally the meeting point of the two meanings of "limit":
/-- **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⟩Not formalised here: Theorem 6 in the compatible-family model, and the explicit colimit formula for arbitrary diagrams of types (Mathlib: Types.colimitEquivQuot).
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 to watch the forgetful functor fail to preserve a coproduct.
"""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()The second builds points of as compatible towers of residues, including a square root of in found by Hensel lifting, and counts solutions of modulo .
"""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()Explore: the shapes side by side
Read each diagram as a recipe. The equaliser is the universal arrow that makes the parallel pair agree; the coequaliser is the universal arrow that makes it agree after the pair; the pushout glues and along . Compare each with its mirror image and check which arrows are dashed (induced uniquely).
Exercises
1. Limits and colimits
Warm-upHumanWhich shape has the pullback as the limit of a diagram of that shape?
2. Limits and colimits
CoreHumanLet , , , and , both be “remainder modulo 3”. How many elements does the pullback have in ?
3. Limits and colimits
CoreHumanIn , what is the equaliser of given by and ?
4. Limits and colimits
CoreHumanIn the proof that products and equalisers give all limits, the limit of is the equaliser of two maps . What is the -component of (for )?
5. Limits and colimits
StretchHumanWhich of these functors preserve all limits? Select all that apply.
6. Limits and colimits
CoreComputationalIn , the element is a compatible tower with . What is ?
7. Limits and colimits
StretchHumanRegard as a category. The increasing sequence of decimal truncations of is a diagram of shape . What is its colimit?
8. Limits and colimits
CoreFormalWhich Lean statement expresses the universal property of the equaliser of f g : X → Y in the category of types?
9. Limits and colimits
CoreComputationalWrite 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.
Common misconceptions
Misconception
"A categorical limit is a limit of a sequence." They are different notions that occasionally meet. In the poset , an increasing sequence is a diagram of shape , 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 , is not a diagram in 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." preserves all limits, but not coproducts () 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 is a right adjoint.
Misconception
"Every diagram has a limit, because a universal property defines one." Existence depends on the category. In the increasing sequence of decimal truncations of has no colimit; in the category of fields and 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 , , and similar categories (forgetful functors to preserve limits); the second is false. A coequaliser in quotients by a normal subgroup, not by an equivalence relation on the set, and a coproduct is a free product.
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 , the -adic integers and are examples; compactness comes from Tychonoff's theorem, since a limit of compact Hausdorff spaces is a closed subspace of their product. In two integers are close when they agree modulo a high power of — 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 ( with open, and , , path-connected, base point in ) into a pushout of groups: . See the fundamental group.
Number theory— Towers of congruences
Solving a polynomial equation in is the same as solving it modulo for every , compatibly: a root in is a point of the limit of the finite solution sets . Hensel's lemma lifts simple roots uniquely, so has exactly two solutions in (lifting ) and none in (none modulo ). The same pattern runs through modern number theory: is the absolute Galois group of every finite field, and in general the absolute Galois group is the inverse limit of the finite groups over finite Galois extensions , with Krull's profinite topology (1928). See elementary number theory and algebraic number theory.
Analysis— Two completions of the integers
Analysis builds differently: complete with respect to the -adic absolute value , exactly as completes for the usual one. The inverse limit description is the same object — a Cauchy sequence for is eventually constant modulo each , 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 , and the completeness axiom of says that every non-empty bounded-above diagram in has a colimit. By Ostrowski's theorem the usual and the -adic absolute values are, up to equivalence, the only non-trivial absolute values on , so these are all the completions of .
Geometry— Fibre products and the sheaf condition
Pullbacks are fibre products: the fibre of a map over is the pullback of along , 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 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 on a space is a sheaf when, for every open cover , the diagram is an equaliser: compatible local sections glue uniquely. See sheaves.
Algebra— Direct limits and exactness
Direct limits build big algebraic objects from small ones: from the groups , the Prüfer group from the cyclic groups , the algebraic closure of as the union of the fields , the localisation from copies of . 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 to the short exact sequences , arranged into towers (multiplication by on the first copies of , the identity on the second, reduction on the third): the limits are , and , and is not surjective. The failure is measured by the derived functor (here ), a first glimpse of homological algebra.
Category theory— Limits are right adjoints
For a fixed shape , a cone over with apex is a natural transformation , so the universal property of the limit says , naturally in and . That is, is right adjoint to the diagonal functor , and dually . In the next lesson this turns into the key theorem: right adjoints preserve limits. Limits are also special Kan extensions, along the functor .
Wonder Trails
History and global context
- Kurt Hensel introduced the -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 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
- 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 , 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.