Categorical Vocabulary

Appendix A

6 min read

Categorical Vocabulary

Category theory is a language for systems that must compose. This appendix collects the definitions the main text requires. For the full theory, consult Mac Lane's Categories for the Working Mathematician or Spivak's Category Theory for the Sciences.

Category

Category

A category C\mathcal{C} consists of:

  1. A collection of objects: A,B,C,A, B, C, \ldots
  2. For each pair of objects A,BA, B, a collection of morphisms Hom(A,B)\mathrm{Hom}(A, B), written f:ABf : A \to B
  3. For each object AA, an identity morphism idA:AA\mathrm{id}_A : A \to A
  4. A composition operation: given f:ABf : A \to B and g:BCg : B \to C, there exists gf:ACg \circ f : A \to C

satisfying associativity (hg)f=h(gf)(h \circ g) \circ f = h \circ (g \circ f) and identity fidA=f=idBff \circ \mathrm{id}_A = f = \mathrm{id}_B \circ f.

A groupoid is a category in which every morphism is an isomorphism. A group is a groupoid with exactly one object.

Functor

Functor

A functor F:CDF : \mathcal{C} \to \mathcal{D} consists of a mapping on objects (AF(A)A \mapsto F(A)) and a mapping on morphisms (fF(f)f \mapsto F(f)) satisfying:

  • F(idA)=idF(A)F(\mathrm{id}_A) = \mathrm{id}_{F(A)}
  • F(gf)=F(g)F(f)F(g \circ f) = F(g) \circ F(f)

Natural Transformation

Natural Transformation

Given functors F,G:CDF, G : \mathcal{C} \to \mathcal{D}, a natural transformation α:FG\alpha : F \Rightarrow G assigns to each object AA a morphism αA:F(A)G(A)\alpha_A : F(A) \to G(A) such that for every f:ABf : A \to B:

αBF(f)=G(f)αA\alpha_B \circ F(f) = G(f) \circ \alpha_A

This is the naturality square. When the book says "coherence," it often means the relevant squares commute.

Presheaf

Presheaf

A presheaf on C\mathcal{C} is a functor F:CopSetF : \mathcal{C}^{\mathrm{op}} \to \mathbf{Set}. Concretely: for each object UU, a set F(U)F(U) of "sections over UU"; for each morphism f:VUf : V \to U, a restriction map F(f):F(U)F(V)F(f) : F(U) \to F(V), satisfying F(idU)=idF(U)F(\mathrm{id}_U) = \mathrm{id}_{F(U)} and F(gf)=F(f)F(g)F(g \circ f) = F(f) \circ F(g).

A presheaf is "local data with restriction." Sheaves (Appendix B) add the coherence requirement: local data that agree on overlaps must glue to global data.

Limits and Colimits

NameDiagram ShapeIntuition
Product A×BA \times BTwo objects, no arrowsOrdered pair; projections to both
Coproduct A+BA + BTwo objects, no arrowsTagged union; injections from both
PullbackACBA \to C \leftarrow BFiber product; pairs that agree on CC
PushoutACBA \leftarrow C \to BAmalgamation; glue along shared CC
EqualizerABA \rightrightarrows BSubobject where two maps agree

Pullbacks formalize context overlap (Ch. 10); pushouts formalize vocabulary extension (Ch. 15).

Adjunction

Adjunction

An adjunction FGF \dashv G consists of functors F:CDF : \mathcal{C} \to \mathcal{D} and G:DCG : \mathcal{D} \to \mathcal{C} with a natural bijection:

HomD(F(A),B)HomC(A,G(B))\mathrm{Hom}_{\mathcal{D}}(F(A), B) \cong \mathrm{Hom}_{\mathcal{C}}(A, G(B))

Equivalently, natural transformations ηA:AG(F(A))\eta_A : A \to G(F(A)) (unit) and εB:F(G(B))B\varepsilon_B : F(G(B)) \to B (counit) satisfying the triangle identities.

FF is the "free construction" (best approximation from below); GG is the "forgetful functor" (best approximation from above). The unit η\eta measures how far AA is from already having the required structure; the counit ε\varepsilon measures how much redundancy the free construction introduced.

Isomorphism

Isomorphism

A morphism f:ABf : A \to B is an isomorphism if there exists g:BAg : B \to A with gf=idAg \circ f = \mathrm{id}_A and fg=idBf \circ g = \mathrm{id}_B. The pair (f,g)(f, g) is the witness. Objects AA and BB are isomorphic, written ABA \cong B.

Equivalence of Categories

Equivalence of Categories

An equivalence between C\mathcal{C} and D\mathcal{D} consists of functors F:CDF : \mathcal{C} \to \mathcal{D} and G:DCG : \mathcal{D} \to \mathcal{C} with natural isomorphisms GFIdCG \circ F \cong \mathrm{Id}_{\mathcal{C}} and FGIdDF \circ G \cong \mathrm{Id}_{\mathcal{D}}.

Equivalence relaxes isomorphism: the round-trip need not return the exact same object, only an isomorphic one. This is why the main text insists on witnessed equivalence (A10) rather than mere isomorphism (A8).

Site and Grothendieck Topology

Site

A site is a category C\mathcal{C} equipped with a Grothendieck topology JJ: for each object UU, a specification of which families {UiU}\{U_i \to U\} count as covers, satisfying stability, transitivity, and identity axioms.

The Context Site

The following definitions ground all context-indexed constructions in Parts III–VI.

Context

A Context U=(N,Σ,L,π)U = (N, \Sigma, L, \pi) where NN is a name, Σ=(T,P,I)\Sigma = (T, P, I) is a signature, L{CWA,OWA,3VL}L \in \{\text{CWA}, \text{OWA}, \text{3VL}\} is a logic regime, and π\pi is provenance metadata.

Context Morphism

A Context Morphism f:VUf : V \to U consists of a signature inclusion ΣUΣV\Sigma_U \hookrightarrow \Sigma_V and a logic compatibility condition (LVL_V at least as strong as LUL_U). Direction: VV refines UU (more specific to more general).

Context Overlap

Given f:VUf : V \to U and g:WUg : W \to U, the overlap V×UW=(NVW,ΣVΣW,max(LV,LW),πderived)V \times_U W = (N_{V \cap W}, \Sigma_V \cap \Sigma_W, \max(L_V, L_W), \pi_{\text{derived}}).

Cover and Context Site

A cover of UU is a family {UiU}\{U_i \to U\} with iΣUiΣU\bigcup_i \Sigma_{U_i} \supseteq \Sigma_U. The Context Site (Ctx,J)(\mathbf{Ctx}, J) equips the context category with this topology, satisfying stability, transitivity, and identity.

Sheaf Condition on Context Site

A presheaf FF on (Ctx,J)(\mathbf{Ctx}, J) is a sheaf iff for every cover {UiU}\{U_i \to U\}: (1) LocalitysUi=tUis|_{U_i} = t|_{U_i} for all ii implies s=ts = t; (2) Gluing — matching sections siUi×UUj=sjUi×UUjs_i|_{U_i \times_U U_j} = s_j|_{U_i \times_U U_j} for all i,ji,j yield unique sF(U)s \in F(U) with sUi=sis|_{U_i} = s_i.

Summary

ConceptThingsWays BetweenGoverning Condition
CategoryObjectsMorphismsAssociative composition; identities
FunctorCategoriesFunctorsPreserves composition and identity
Natural transformationFunctorsComponents αA\alpha_ANaturality square commutes
AdjunctionCategoriesAdjoint pairHom-set bijection is natural
Limit/ColimitDiagramsUniversal objectsUnique factorization
EquivalenceCategoriesFunctor pairsRound-trips ≅ identity
SheafPresheavesRestriction mapsMatching families glue uniquely

Category theory provides a language for stating, precisely, when two ways of computing the same thing yield the same thing. That precision is what allows coherence to be checked rather than hoped for.

← Back to AppendicesBack to The Proofs →