Limits and Colimits

Bartosz Milewski · 2015 · Category Theory for Programmers, Ch. 11

Prereqs: 🍞 Ch5 (Products and Coproducts), 🍞 Ch10 (Natural Transformations). 10 min.

A limit is a universal cone over a diagram. Products, terminal objects, and equalizers are all limits. Reverse the arrows and you get colimits: coproducts, initial objects, and coequalizers. One construction, many shapes.

Diagrams and cones

A diagram is a functor D : I → C from an index category I (the "shape") into a target category C. A cone over that diagram is an apex object c together with morphisms from c to every object in the diagram, such that every triangle commutes. Think of it as a tent pole (c) with ropes (morphisms) to each stake (diagram object), where the ropes respect the connections between stakes.

Scheme

; A cone: an apex with morphisms to every object in the diagram,
; such that the triangles commute.
;
; Diagram: two objects a, b (no morphisms between them).
; A cone over this diagram is: apex c, proj1: c->a, proj2: c->b.
; That's just a product candidate!

(define (make-cone apex proj1 proj2)
  (list apex proj1 proj2))

(define (cone-apex cone) (car cone))
(define (cone-proj1 cone) (cadr cone))
(define (cone-proj2 cone) (caddr cone))

; Cone 1: apex = (3 7 "extra"), projections extract components
(define cone1
  (make-cone '(3 7 "extra")
    (lambda (t) (car t))       ; proj1
    (lambda (t) (cadr t))))    ; proj2

; Cone 2: apex = (3 7), projections are fst and snd
(define cone2
  (make-cone '(3 7)
    (lambda (p) (car p))       ; proj1
    (lambda (p) (cadr p))))    ; proj2

(display "Cone 1 apex: ") (display (cone-apex cone1)) (newline)
(display "Cone 1 proj1: ") (display ((cone-proj1 cone1) '(3 7 "extra"))) (newline)
(display "Cone 2 apex: ") (display (cone-apex cone2)) (newline)
(display "Cone 2 proj1: ") (display ((cone-proj1 cone2) '(3 7))) (newline)
; Both are cones. But cone2 is the limit — the universal one.

; A cone: an apex with morphisms to every object in the diagram,
; such that the triangles commute.
;
; Diagram: two objects a, b (no morphisms between them).
; A cone over this diagram is: apex c, proj1: c->a, proj2: c->b.
; That's just a product candidate!

(define (make-cone apex proj1 proj2)
  (list apex proj1 proj2))

(define (cone-apex cone) (car cone))
(define (cone-proj1 cone) (cadr cone))
(define (cone-proj2 cone) (caddr cone))

; Cone 1: apex = (3 7 "extra"), projections extract components
(define cone1
  (make-cone '(3 7 "extra")
    (lambda (t) (car t))       ; proj1
    (lambda (t) (cadr t))))    ; proj2

; Cone 2: apex = (3 7), projections are fst and snd
(define cone2
  (make-cone '(3 7)
    (lambda (p) (car p))       ; proj1
    (lambda (p) (cadr p))))    ; proj2

(display "Cone 1 apex: ") (display (cone-apex cone1)) (newline)
(display "Cone 1 proj1: ") (display ((cone-proj1 cone1) '(3 7 "extra"))) (newline)
(display "Cone 2 apex: ") (display (cone-apex cone2)) (newline)
(display "Cone 2 proj1: ") (display ((cone-proj1 cone2) '(3 7))) (newline)
; Both are cones. But cone2 is the limit — the universal one.

Products are limits over discrete diagrams

When the index category has two objects and no morphisms between them (the discrete category 2), a cone is an apex with two projections. The limit is the universal cone: the one through which every other cone factors uniquely. That's the product. The terminal object is the limit over the empty diagram (zero objects, zero morphisms).

Scheme

; The limit is the universal cone.
; For a discrete two-object diagram, the limit is the product.
;
; Universal property: for any cone (c', p', q'),
; there exists a unique morphism m: c' -> product
; such that p' = fst . m and q' = snd . m.

(define (fst p) (car p))
(define (snd p) (cadr p))

; Factorizer: given any two morphisms from c' to a and b,
; build the unique morphism m: c' -> (a, b)
(define (factorizer p q)
  (lambda (x) (list (p x) (q x))))

; Example: c' = integer, a = is-even?, b = show
(define (is-even? n) (= 0 (modulo n 2)))
(define (show n) (number->string n))

(define m (factorizer is-even? show))

(display "m(42): ") (display (m 42)) (newline)
(display "m(7):  ") (display (m 7)) (newline)

; Verify the universal property
(display "fst(m(42)) = is-even?(42)? ")
(display (equal? (fst (m 42)) (is-even? 42))) (newline)
(display "snd(m(42)) = show(42)?     ")
(display (equal? (snd (m 42)) (show 42))) (newline)

; Terminal object = limit over the empty diagram.
; No diagram objects => cone has no projections => just the apex.
; The universal such apex is the one every object maps to uniquely.
(define (unit x) '())
(display "unit(42): ") (display (unit 42))
; '() is the terminal object — the limit of nothing.

; The limit is the universal cone.
; For a discrete two-object diagram, the limit is the product.
;
; Universal property: for any cone (c', p', q'),
; there exists a unique morphism m: c' -> product
; such that p' = fst . m and q' = snd . m.

(define (fst p) (car p))
(define (snd p) (cadr p))

; Factorizer: given any two morphisms from c' to a and b,
; build the unique morphism m: c' -> (a, b)
(define (factorizer p q)
  (lambda (x) (list (p x) (q x))))

; Example: c' = integer, a = is-even?, b = show
(define (is-even? n) (= 0 (modulo n 2)))
(define (show n) (number->string n))

(define m (factorizer is-even? show))

(display "m(42): ") (display (m 42)) (newline)
(display "m(7):  ") (display (m 7)) (newline)

; Verify the universal property
(display "fst(m(42)) = is-even?(42)? ")
(display (equal? (fst (m 42)) (is-even? 42))) (newline)
(display "snd(m(42)) = show(42)?     ")
(display (equal? (snd (m 42)) (show 42))) (newline)

; Terminal object = limit over the empty diagram.
; No diagram objects => cone has no projections => just the apex.
; The universal such apex is the one every object maps to uniquely.
(define (unit x) '())
(display "unit(42): ") (display (unit 42))
; '() is the terminal object — the limit of nothing.

Equalizers — where two morphisms agree

When the index category has two objects with two parallel morphisms between them (a ⇉ b), the limit is an equalizer. It picks out the subobject of a where the two morphisms agree: the set of all x such that f(x) = g(x). The equalizer comes with an embedding eq : E → a such that f ∘ eq = g ∘ eq.

Scheme

; Equalizer: the limit where two parallel morphisms agree.
; Given f, g : a -> b, the equalizer is { x in a | f(x) = g(x) }

(define (equalizer f g domain)
  (filter (lambda (x) (equal? (f x) (g x))) domain))

; Example: f(x) = x^2, g(x) = 2x
; Where do they agree? x^2 = 2x => x(x-2) = 0 => x = 0 or x = 2
(define (f x) (* x x))
(define (g x) (* 2 x))

(define domain '(-3 -2 -1 0 1 2 3 4 5))
(define eq-set (equalizer f g domain))

(display "f(x) = x^2, g(x) = 2x") (newline)
(display "Equalizer: ") (display eq-set) (newline)
; (0 2) — exactly where f and g agree.

; Verify the equalizer property: f(x) = g(x) for every x in eq-set
(for-each
  (lambda (x)
    (display "  f(") (display x) (display ") = ") (display (f x))
    (display ", g(") (display x) (display ") = ") (display (g x))
    (newline))
  eq-set)

; The embedding eq: E -> a is just inclusion.
; The universal property: any other set where f = g
; factors through eq-set via a unique function.

Pullbacks — matching over a shared target

A pullback is the limit over a cospan: two morphisms f : a → b and g : c → b pointing at the same object. The pullback is the set of pairs (x, y) from a and c that land on the same element in b: f(x) = g(y). It generalizes the product (a product is a pullback over the terminal object) and the equalizer (an equalizer is a pullback where a = c).

Scheme

; Pullback: given f: a -> b and g: c -> b,
; find all pairs (x, y) such that f(x) = g(y).
;
;    d --q--> c
;    |        |
;    p        g
;    v        v
;    a --f--> b

(define (pullback f g domain-a domain-c)
  (let loop ((xs domain-a) (result '()))
    (if (null? xs) (reverse result)
        (let inner ((ys domain-c) (acc result))
          (if (null? ys) (loop (cdr xs) acc)
              (if (equal? (f (car xs)) (g (car ys)))
                  (inner (cdr ys) (cons (list (car xs) (car ys)) acc))
                  (inner (cdr ys) acc)))))))

; Example: students and courses matched by department
; f: student -> department, g: course -> department
(define students '(alice bob carol dave))
(define courses  '(math101 phys201 math202 chem101))

(define (dept-of-student s)
  (cond ((eq? s 'alice) 'math)
        ((eq? s 'bob)   'phys)
        ((eq? s 'carol) 'math)
        ((eq? s 'dave)  'chem)))

(define (dept-of-course c)
  (cond ((eq? c 'math101) 'math)
        ((eq? c 'phys201) 'phys)
        ((eq? c 'math202) 'math)
        ((eq? c 'chem101) 'chem)))

(define matches (pullback dept-of-student dept-of-course students courses))

(display "Student-course pairs in the same department:") (newline)
(for-each (lambda (pair)
  (display "  ") (display (car pair))
  (display " - ") (display (cadr pair))
  (display " (") (display (dept-of-student (car pair))) (display ")")
  (newline))
  matches)

; Pullback: given f: a -> b and g: c -> b,
; find all pairs (x, y) such that f(x) = g(y).
;
;    d --q--> c
;    |        |
;    p        g
;    v        v
;    a --f--> b

(define (pullback f g domain-a domain-c)
  (let loop ((xs domain-a) (result '()))
    (if (null? xs) (reverse result)
        (let inner ((ys domain-c) (acc result))
          (if (null? ys) (loop (cdr xs) acc)
              (if (equal? (f (car xs)) (g (car ys)))
                  (inner (cdr ys) (cons (list (car xs) (car ys)) acc))
                  (inner (cdr ys) acc)))))))

; Example: students and courses matched by department
; f: student -> department, g: course -> department
(define students '(alice bob carol dave))
(define courses  '(math101 phys201 math202 chem101))

(define (dept-of-student s)
  (cond ((eq? s 'alice) 'math)
        ((eq? s 'bob)   'phys)
        ((eq? s 'carol) 'math)
        ((eq? s 'dave)  'chem)))

(define (dept-of-course c)
  (cond ((eq? c 'math101) 'math)
        ((eq? c 'phys201) 'phys)
        ((eq? c 'math202) 'math)
        ((eq? c 'chem101) 'chem)))

(define matches (pullback dept-of-student dept-of-course students courses))

(display "Student-course pairs in the same department:") (newline)
(for-each (lambda (pair)
  (display "  ") (display (car pair))
  (display " - ") (display (cadr pair))
  (display " (") (display (dept-of-student (car pair))) (display ")")
  (newline))
  matches)

Colimits — reverse the arrows

A colimit is a limit in the opposite category. Reverse all the arrows in a cone and you get a cocone: morphisms going from the diagram objects to the apex. The colimit is the universal cocone. Coproducts are colimits over discrete diagrams. Initial objects are colimits over the empty diagram. Pushouts are dual to pullbacks. The coequalizer is dual to the equalizer: it identifies elements that two morphisms map differently.

Scheme

; Colimit = limit with arrows reversed.
; Cocone: morphisms FROM diagram objects TO the apex.
;
; Coproduct = colimit over discrete two-object diagram.
; Injections go IN to the apex (reversed from projections OUT).

(define (Left x) (list 'Left x))
(define (Right x) (list 'Right x))

; Coequalizer: dual of equalizer.
; Given f, g : a -> b, the coequalizer merges elements
; in b that are "connected" by f and g.
; If f(x) and g(x) differ, the coequalizer identifies them.

(define (coequalizer f g domain)
  ; Build equivalence classes: f(x) ~ g(x) for all x
  (let ((classes '()))
    (for-each
      (lambda (x)
        (let ((fx (f x)) (gx (g x)))
          (set! classes (merge-classes classes fx gx))))
      domain)
    classes))

(define (merge-classes classes a b)
  (if (equal? a b) classes
      (let ((ca (find-class classes a))
            (cb (find-class classes b)))
        (cond
          ((and (not ca) (not cb))
           (cons (list a b) classes))
          ((and ca (not cb))
           (map (lambda (c) (if (eq? c ca) (cons b c) c)) classes))
          ((and (not ca) cb)
           (map (lambda (c) (if (eq? c cb) (cons a c) c)) classes))
          ((eq? ca cb) classes)
          (else
           (let ((merged (append ca cb)))
             (cons merged
               (filter (lambda (c) (and (not (eq? c ca)) (not (eq? c cb))))
                       classes))))))))

(define (find-class classes x)
  (cond ((null? classes) #f)
        ((member x (car classes)) (car classes))
        (else (find-class (cdr classes) x))))

; Example: f(x) = x mod 3, g(x) = x mod 2
; Coequalizer identifies f(x) with g(x) in the codomain
(define (f x) (modulo x 3))
(define (g x) (modulo x 2))

(display "f(x) = x mod 3, g(x) = x mod 2") (newline)
(display "Coequalizer merges codomain elements:") (newline)
(for-each (lambda (x)
  (display "  x=") (display x)
  (display ": f(x)=") (display (f x))
  (display ", g(x)=") (display (g x))
  (if (not (equal? (f x) (g x)))
    (begin (display " => merge ") (display (f x))
           (display " ~ ") (display (g x))))
  (newline))
  '(0 1 2 3 4 5))

; Colimit = limit with arrows reversed.
; Cocone: morphisms FROM diagram objects TO the apex.
;
; Coproduct = colimit over discrete two-object diagram.
; Injections go IN to the apex (reversed from projections OUT).

(define (Left x) (list 'Left x))
(define (Right x) (list 'Right x))

; Coequalizer: dual of equalizer.
; Given f, g : a -> b, the coequalizer merges elements
; in b that are "connected" by f and g.
; If f(x) and g(x) differ, the coequalizer identifies them.

(define (coequalizer f g domain)
  ; Build equivalence classes: f(x) ~ g(x) for all x
  (let ((classes '()))
    (for-each
      (lambda (x)
        (let ((fx (f x)) (gx (g x)))
          (set! classes (merge-classes classes fx gx))))
      domain)
    classes))

(define (merge-classes classes a b)
  (if (equal? a b) classes
      (let ((ca (find-class classes a))
            (cb (find-class classes b)))
        (cond
          ((and (not ca) (not cb))
           (cons (list a b) classes))
          ((and ca (not cb))
           (map (lambda (c) (if (eq? c ca) (cons b c) c)) classes))
          ((and (not ca) cb)
           (map (lambda (c) (if (eq? c cb) (cons a c) c)) classes))
          ((eq? ca cb) classes)
          (else
           (let ((merged (append ca cb)))
             (cons merged
               (filter (lambda (c) (and (not (eq? c ca)) (not (eq? c cb))))
                       classes))))))))

(define (find-class classes x)
  (cond ((null? classes) #f)
        ((member x (car classes)) (car classes))
        (else (find-class (cdr classes) x))))

; Example: f(x) = x mod 3, g(x) = x mod 2
; Coequalizer identifies f(x) with g(x) in the codomain
(define (f x) (modulo x 3))
(define (g x) (modulo x 2))

(display "f(x) = x mod 3, g(x) = x mod 2") (newline)
(display "Coequalizer merges codomain elements:") (newline)
(for-each (lambda (x)
  (display "  x=") (display x)
  (display ": f(x)=") (display (f x))
  (display ", g(x)=") (display (g x))
  (if (not (equal? (f x) (g x)))
    (begin (display " => merge ") (display (f x))
           (display " ~ ") (display (g x))))
  (newline))
  '(0 1 2 3 4 5))

The hom-set definition of limits

There's a cleaner way to state the universal property. A limit Lim D exists when there's a natural isomorphism: C(c, Lim D) ≅ Nat(Δc, D). The left side is morphisms from c to the limit. The right side is natural transformations from the constant functor at c to the diagram D, which are exactly cones with apex c. This says: morphisms into the limit correspond one-to-one with cones.

Scheme

; Hom-set definition: C(c, Lim D) ≅ Nat(Δc, D)
;
; Left side:  morphisms from c to the limit (the product)
; Right side: cones with apex c (pairs of morphisms to each diagram object)
;
; For the product a x b:
;   C(c, a x b) ≅ C(c, a) x C(c, b)
; A morphism into the product IS a pair of morphisms.

; Demonstrate: one morphism m: c -> (a, b)
; corresponds to a pair (fst . m, snd . m)

(define (fst p) (car p))
(define (snd p) (cadr p))

; Direction 1: morphism -> cone
(define (morphism->cone m)
  (lambda (x) (list (fst (m x)) (snd (m x)))))

; Direction 2: cone -> morphism
(define (cone->morphism p q)
  (lambda (x) (list (p x) (q x))))

; Test: round-trip
(define p (lambda (n) (* n n)))       ; n -> n^2
(define q (lambda (n) (+ n 1)))       ; n -> n+1

; Cone (p, q) -> morphism m -> cone (fst.m, snd.m) = (p, q)
(define m (cone->morphism p q))
(define recovered (morphism->cone m))

(display "Original cone at 5: (") (display (p 5)) (display ", ") (display (q 5)) (display ")") (newline)
(display "Round-trip at 5:    ") (display ((recovered) 5)) (newline)
(display "Match? ") (display (equal? (list (p 5) (q 5)) ((recovered) 5)))
; The isomorphism is the factorizer, seen from the other side.

; Hom-set definition: C(c, Lim D) ≅ Nat(Δc, D)
;
; Left side:  morphisms from c to the limit (the product)
; Right side: cones with apex c (pairs of morphisms to each diagram object)
;
; For the product a x b:
;   C(c, a x b) ≅ C(c, a) x C(c, b)
; A morphism into the product IS a pair of morphisms.

; Demonstrate: one morphism m: c -> (a, b)
; corresponds to a pair (fst . m, snd . m)

(define (fst p) (car p))
(define (snd p) (cadr p))

; Direction 1: morphism -> cone
(define (morphism->cone m)
  (lambda (x) (list (fst (m x)) (snd (m x)))))

; Direction 2: cone -> morphism
(define (cone->morphism p q)
  (lambda (x) (list (p x) (q x))))

; Test: round-trip
(define p (lambda (n) (* n n)))       ; n -> n^2
(define q (lambda (n) (+ n 1)))       ; n -> n+1

; Cone (p, q) -> morphism m -> cone (fst.m, snd.m) = (p, q)
(define m (cone->morphism p q))
(define recovered (morphism->cone m))

(display "Original cone at 5: (") (display (p 5)) (display ", ") (display (q 5)) (display ")") (newline)
(display "Round-trip at 5:    ") (display ((recovered) 5)) (newline)
(display "Match? ") (display (equal? (list (p 5) (q 5)) ((recovered) 5)))
; The isomorphism is the factorizer, seen from the other side.

Notation reference

Blog / Haskell	Scheme	Meaning
D : I → C	(list of objects and morphisms)	Diagram (functor from index category)
Δc	(lambda (_) c)	Constant functor at c
Cone (apex, πᵢ)	(make-cone apex p1 p2)	Cone over a diagram
Lim D	(product, equalizer, ...)	Limit (universal cone)
Equalizer	(equalizer f g domain)	Limit where f(x) = g(x)
Pullback	(pullback f g dom-a dom-c)	Limit over a cospan
Colim D	(coproduct, coequalizer, ...)	Colimit (universal cocone)
C(c, Lim D) ≅ Nat(Δc, D)	(morphism->cone, cone->morphism)	Hom-set characterization

Neighbors

Milewski chapters

🍞 Chapter 5 — Products and Coproducts (limits over discrete diagrams)
🍞 Chapter 10 — Natural Transformations (cones are natural transformations from Δc to D)

Paper pages that use limits

🍞 Leinster 2021 — limits in the context of entropy and category theory
🍞 Spivak 2013 — limits appear in database schemas as queries

Foundations (Wikipedia)

Translation notes

The blog post introduces limits via the constant functor Δ and natural transformations, building up from products and terminal objects to equalizers and pullbacks. This page follows the same progression but makes everything executable. The equalizer is computed by filtering a finite domain rather than defining a subobject categorically. The pullback is computed by brute-force enumeration of pairs, which matches the set-theoretic definition but hides the universal property. The coequalizer uses explicit equivalence-class merging, which is the computational content of a quotient. In the blog post, Milewski also covers continuity (functors that preserve limits), which requires representable functors and is deferred to a later chapter.

Ready for the real thing? Read the blog post. Start with the cone construction, then see how the hom-set definition C(c, Lim D) ≅ Nat(Δc, D) unifies everything.

← Natural Transformations by june.kim Free Monoids →