Res Agentica
Reading

No saved reading position.

Reading

No saved reading position.

Categorical Vocabulary

Appendix A

7 min read
Aa
Text size

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:A→Bf : A \to B
  3. For each object AA, an identity morphism idA:A→A\mathrm{id}_A : A \to A
  4. A composition operation: given f:A→Bf : A \to B and g:B→Cg : B \to C, there exists g∘f:A→Cg \circ f : A \to C

satisfying associativity (h∘g)∘f=h∘(g∘f)(h \circ g) \circ f = h \circ (g \circ f) and identity f∘idA=f=idB∘ff \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:C→DF : \mathcal{C} \to \mathcal{D} consists of a mapping on objects (A↦F(A)A \mapsto F(A)) and a mapping on morphisms (f↦F(f)f \mapsto F(f)) satisfying:

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

Natural Transformation

Natural Transformation

Given functors F,G:C→DF, G : \mathcal{C} \to \mathcal{D}, a natural transformation α:F⇒G\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:A→Bf : A \to B:

αB∘F(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:Cop→SetF : \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:V→Uf : 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(g∘f)=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
PullbackA→C←BA \to C \leftarrow BFiber product; pairs that agree on CC
PushoutA←C→BA \leftarrow C \to BAmalgamation; glue along shared CC
EqualizerA⇉BA \rightrightarrows BSubobject where two maps agree

Pullbacks represent the overlaps used in Chapter 10 when the required maps exist. A pushout can amalgamate signatures along specified maps in a category that supplies it; that construction alone does not establish the admission or conservativity obligations of Chapter 15.

Adjunction

Adjunction

An adjunction F⊣GF \dashv G consists of functors F:C→DF : \mathcal{C} \to \mathcal{D} and G:D→CG : \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:A→G(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.

Free and forgetful functors supply important examples. An arbitrary adjunction need not have that interpretation. Unit and counit are comparison morphisms, not numerical measures of loss or cost. In a specified preorder the adjunction characterizes least and greatest approximations relative to the given maps.

Isomorphism

Isomorphism

A morphism f:A→Bf : A \to B is an isomorphism if there exists g:B→Ag : B \to A with g∘f=idAg \circ f = \mathrm{id}_A and f∘g=idBf \circ g = \mathrm{id}_B. The pair (f,g)(f, g) is the witness. Objects AA and BB are isomorphic, written A≅BA \cong B.

Equivalence of Categories

Equivalence of Categories

An equivalence between C\mathcal{C} and D\mathcal{D} consists of functors F:C→DF : \mathcal{C} \to \mathcal{D} and G:D→CG : \mathcal{D} \to \mathcal{C} with natural isomorphisms G∘F≅IdCG \circ F \cong \mathrm{Id}_{\mathcal{C}} and F∘G≅IdDF \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 compares categories and functors. A10’s scoped records concern particular objects, relations and properties; they are not made category equivalences by using the same word.

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 {Ui→U}\{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, LL records a consequence relation and a separate predicate-scoped absence profile as in A15, and π\pi is provenance metadata.

Context Morphism

A Context Morphism f:V→Uf : V \to U is a declared map in the chosen context category. Its associated restriction must specify how U-data are represented in V and satisfy the functor laws. A signature inclusion can be part of such a construction; CWA, OWA and three-valued evaluation are not a single ordered scale of logical strength. An adapter that changes an absence conclusion does not silently become a truth-preserving restriction.

Context Overlap

Given f:V→Uf : V \to U and g:W→Ug : W \to U, an overlap V×UWV \times_U W is their categorical pullback, when it exists. An intersection of signature names and a chosen absence policy do not establish its universal property. The formulas using overlaps in this companion assume the required pullbacks; on a general site matching can instead be stated through arrows in covering sieves.

Cover and Context Site

A cover of UU is a family {Ui→U}\{U_i \to U\} of refinement morphisms declared jointly sufficient for UU by the topology JJ (Ch. 10, A12b). In a model where refinement is signature inclusion, each refining signature already contains the original; their union therefore supplies no additional covering test. For more general declared context maps, signature containment need not even describe the construction. What counts as a cover is the design declaration JJ, which must satisfy the site axioms below. 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 {Ui→U}\{U_i \to U\}: (1) Locality — s∣Ui=t∣Uis|_{U_i} = t|_{U_i} for all ii implies s=ts = t; (2) Gluing — matching sections si∣Ui×UUj=sj∣Ui×UUjs_i|_{U_i \times_U U_j} = s_j|_{U_i \times_U U_j} for all i,ji,j yield unique s∈F(U)s \in F(U) with s∣Ui=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. It makes the equality to be established explicit. An effective check still requires a procedure for the objects and maps in question.

← Back to AppendicesBack to The Proofs →

Search the book

Use ↑ ↓ to move through results; Escape to close.

Search every published chapter, section and reference.

    In this chapter