The Lumenary · Advanced undergraduate

Limits and colimits

Name: ______________________

Date: ______________________

You will learn to

Define diagrams, cones, limits and colimits, and recognise products, equalisers, pullbacks and inverse limits (and their duals) as special cases
Compute equalisers, pullbacks, coequalisers and pushouts in $\cat{Set}$ , $\cat{Grp}$ and $\cat{Top}$
Prove that limits are unique up to unique isomorphism and that a category with all small products and equalisers has all small limits
Show that hom functors $\Hom(A, -)$ preserve limits, and that the forgetful functor $\cat{Grp} \to \cat{Set}$ preserves limits but not coproducts
Describe the $p$ -adic integers as an inverse limit of the rings $\Z/p^n\Z$ and use the description to find units and square roots

1.
Which shape $\mathcal{J}$ has the pullback as the limit of a diagram of that shape?
- A. $\bullet \to \bullet \leftarrow \bullet$ (a cospan)
- B. $\bullet \leftarrow \bullet \to \bullet$ (a span)
- C. $\bullet \rightrightarrows \bullet$ (a parallel pair)
- D.two objects and no arrows
2.
Let $A = \{1, \dots, 6\}$ , $B = \{1, 2, 3, 4\}$ , $C = \{0, 1, 2\}$ , and $f : A \to C$ , $g : B \to C$ both be “remainder modulo 3”. How many elements does the pullback $A \times_C B$ have in $\cat{Set}$ ?
3.
In $\cat{Ab}$ , what is the equaliser of $f, g : \Z \to \Z/6$ given by $f(n) = n \bmod 6$ and $g(n) = 3n \bmod 6$ ?
- A.the subgroup $3\Z \subseteq \Z$
- B.the subgroup $2\Z$
- C. $\{0\}$
- D. $\Z/3$
4.
In the proof that products and equalisers give all limits, the limit of $D$ is the equaliser of two maps $s, t : \prod_j D(j) \rightrightarrows \prod_{u : i \to j} D(j)$ . What is the $u$ -component of $t$ (for $u : i \to j$ )?
- A. $D(u) \circ \mathrm{pr}_i$ : move the $i$ -th coordinate along $u$
- B. $\mathrm{pr}_i$
- C. $D(u)^{-1} \circ \mathrm{pr}_j$
- D. $\mathrm{pr}_j \circ D(u)$
5.
Which of these functors preserve all limits? Select all that apply.
- A. $\Hom(A, -) : \mathcal{C} \to \cat{Set}$ , for an object $A$ of a locally small category
- B.the forgetful functor $\cat{Grp} \to \cat{Set}$
- C.the forgetful functor $\cat{Top} \to \cat{Set}$
- D. $X \mapsto X \sqcup \{\ast\}$ on $\cat{Set}$
- E.the forgetful functor $\cat{Grp} \to \cat{Set}$ , applied to coproducts
6.
In $\Z_2 = \varprojlim \Z/2^n$ , the element $\tfrac13$ is a compatible tower $(x_1, x_2, x_3, \dots)$ with $3x_n \equiv 1 \pmod{2^n}$ . What is $x_5 \in \{0, 1, \dots, 31\}$ ?
7.
Regard $(\Q, \le)$ as a category. The increasing sequence $3 \le 3.1 \le 3.14 \le 3.141 \le \cdots$ of decimal truncations of $\pi$ is a diagram of shape $(\N, \le)$ . What is its colimit?
- A.It has no colimit in $(\Q, \le)$
- B. $\pi$
- C. $4$
- D. $3.1416$
8.
Which Lean statement expresses the universal property of the equaliser $\{x // f x = g x\}$ of f g : X → Y in the category of types?
- A.∀ h : W → X, f ∘ h = g ∘ h → ∃! u : W → {x // f x = g x}, Subtype.val ∘ u = h
- B.∀ h : W → X, ∃! u : W → {x // f x = g x}, Subtype.val ∘ u = h
- C.∀ h : W → X, f ∘ h = g ∘ h → ∃ u : W → {x // f x = g x}, Subtype.val ∘ u = h
- D.∀ h : Y → W, h ∘ f = h ∘ g → ∃! u, u ∘ Quot.mk _ = h
9.
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.
Computational — Practice

Answer key — Limits and colimits

1.
A pullback is the limit of a cospan $A \xrightarrow{f} C \xleftarrow{g} B$ : a cone is an object $W$ with $a : W \to A$ , $b : W \to B$ (and the leg to $C$ , forced to be $fa = gb$ ). Spans have pushouts as colimits, parallel pairs have equalisers, and discrete pairs have products.
2.
The pullback is $\{(a, b) : a \equiv b \pmod 3\}$ . Fibre by fibre: remainder $0$ : $2 \cdot 1$ ; remainder $1$ : $2 \cdot 2$ ; remainder $2$ : $2 \cdot 1$ . Total $2 + 4 + 2 = 8$ .
3.
The equaliser is $\{n \in \Z : n \equiv 3n \pmod 6\} = \{n : 6 \mid 2n\} = 3\Z$ , with its inclusion into $\Z$ . Equivalently, it is the kernel of $f - g$ .
4.
$\mathrm{pr}_u \circ s = \mathrm{pr}_j$ and $\mathrm{pr}_u \circ t = D(u) \circ \mathrm{pr}_i$ . In $\cat{Set}$ the equaliser of $s, t$ is $\{(x_j) : x_j = D(u)(x_i) \text{ for all } u : i \to j\}$ , the set of compatible families.
5.
$\Hom(A, -)$ preserves limits (Theorem 4), hence so does every functor isomorphic to one: $U_{\cat{Grp}} \cong \Hom(\Z, -)$ and $U_{\cat{Top}} \cong \Hom(\{\ast\}, -)$ . The functor $X \mapsto X \sqcup \{\ast\}$ fails on the empty limit (terminal object). The last option is about a colimit, which $U_{\cat{Grp}}$ does not preserve.
6.
$3 \cdot 11 = 33 \equiv 1 \pmod{32}$ , so $x_5 = 11$ . Check compatibility: $11 \equiv 3 \pmod 8 = x_3$ and $11 \equiv 11 \pmod{16} = x_4$ . The whole tower is $(1, 3, 3, 11, 11, 43, 43, 171, \dots)$ , i.e. the $2$ -adic expansion $\dots 101011$ .
7.
A colimit in a poset is a least upper bound of the objects of the diagram. In $\Q$ the set of truncations of $\pi$ has upper bounds but no least one, since $\pi \notin \Q$ . So the colimit does not exist in $(\Q, \le)$ , while in $(\R, \le)$ it is $\pi$ : existence of colimits depends on the category, and the completeness of $\R$ is precisely the existence of such colimits.
8.
Option (a): the hypothesis says h is a cone, and ∃! says it factors through the equaliser in exactly one way. (b) drops the cone condition, (c) drops uniqueness, and (d) is the dual statement for coequalisers.
9.
```
from collections import Counter

def pullback(A, B, f, g):
    return [(a, b) for a in A for b in B if f[a] == g[b]]

def pullback_size(A, B, f, g):
    fa = Counter(f[a] for a in A)
    gb = Counter(g[b] for b in B)
    return sum(fa[c] * gb[c] for c in fa)
```
The pullback is the disjoint union, over $c \in C$ , of the products of fibres $f^{-1}(c) \times g^{-1}(c)$ — which is why its size is $\sum_c |f^{-1}(c)|\,|g^{-1}(c)|$ . When $C$ is a point, this is the product $A \times B$ .