Module 6: Universal Constructions II: Colimits and Adjunctions
This module completes the limit/colimit duality and introduces adjunctions — widely considered the most important concept in category theory. Colimits generalize union, disjunction, and amalgamation. Adjunctions capture the relationship between construction and forgetfulness, between adding structure and removing it. Every free/forgetful pair in mathematics is an adjunction. The key theorem — that left adjoints preserve colimits and right adjoints preserve limits — will be the engine of the data migration module to follow.
Learning Objectives
- Define colimits as initial cocones and compute coproducts, pushouts, and coequalizers.
- Identify coproducts as sum types and pushouts as amalgamated structures.
- Define an adjunction via the hom-set bijection and via unit and counit natural transformations.
- Prove that left adjoints preserve colimits and right adjoints preserve limits.
- Identify free/forgetful pairs as adjunctions; show that lists are the free monoid on a set.
- Explain the slogan: left adjoint = cheapest solution, right adjoint = most conservative solution.
Materials
Key Concepts
- Cocone: A natural transformation from a diagram D to a constant functor Δ_c; the dual of a cone; morphisms from all parts of a diagram into a single apex.
- Colimit: An initial cocone — the most economical object receiving all parts of the diagram; unique up to unique isomorphism.
- Coproduct: The colimit of a two-object discrete diagram; generalizes disjoint union, OR, and sum types.
- Pushout: The colimit of a span A ← C → B; generalizes code merges, amalgamated sums, and gluings.
- Adjunction: A pair of functors F: C ⇌ D: G with a natural bijection hom_D(Fc, d) ≅ hom_C(c, Gd); F is left adjoint to G, written F ⊣ G.
- Unit / Counit: The natural transformations η: Id_C ⟹ GF and ε: FG ⟹ Id_D satisfying the triangle identities; the canonical witnesses of the adjunction.
- Free / Forgetful: The prototypical adjunction; the free functor adds structure, the forgetful functor removes it; lists are free monoids, free groups are word constructions.
Central Concepts from Prerequisites
- Modules 2–5: categories, functors, natural transformations, limits
- Abstract algebra: monoids, free structures, group presentations
- Functional programming: list as free monoid, fold/unfold duality (helpful)