Technopedia

The technologist’s encyclopedia

Category theory

Category theory is the study of mathematical structure through objects and morphisms (structure-preserving maps) between them, abstracted away from what the objects are made of. It is relevant whenever you want to state a construction once and for all across many fields — products, “free” constructions, duality, and limits all have a single categorical form — and it is the native language of modern algebra, homotopy type theory, and the semantics of programming languages.

Authoritative sources

Category

Definition. A category C\mathcal{C} consists of:

such that composition is associative ((h∘g)∘f=h∘(g∘f)(h \circ g) \circ f = h \circ (g \circ f)) and each identity acts as a unit (idB∘f=f=f∘idA\mathrm{id}_B \circ f = f = f \circ \mathrm{id}_A).

Details

A category abstracts the pattern “things, and arrows between them.” The only rules are that arrows compose, that composition is associative, and that each object has a do-nothing identity arrow. What the objects are and what the arrows do is deliberately left unspecified — that is the whole point. The same definition covers sets and functions, groups and homomorphisms, topological spaces and continuous maps, and propositions and proofs (see Type theory).

Example. The category Set: objects are sets, morphisms are functions, composition is function composition, and the identity is the identity function. All the axioms are just the familiar facts about composing functions.

The diagram below shows the two axioms at once: the composite g∘fg \circ f is the arrow you get by going A→B→CA \to B \to C, and each object carries an identity loop.

A B C f g g ∘ f id_A id_B id_C

Authoritative sources

Example problem

Consider the “category” whose objects are the natural numbers and which has exactly one morphism m→nm \to n if and only if m≤nm \le n. Show it is a category.

Solution

Composition: if m≤nm \le n and n≤pn \le p then m≤pm \le p, and there is exactly one morphism m→pm \to p, so the composite is forced and well-defined. Identity: m≤mm \le m, so idm\mathrm{id}_m exists. Associativity holds automatically because between any two comparable objects there is at most one morphism, so the two ways of composing are the same unique arrow.

Functor

Definition. A functor F:C→DF: \mathcal{C} \to \mathcal{D} assigns to each object AA of C\mathcal{C} an object F(A)F(A) of D\mathcal{D}, and to each morphism f:A→Bf: A \to B a morphism F(f):F(A)→F(B)F(f): F(A) \to F(B), preserving composition and identities:

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

A functor is the “structure-preserving map between structures” of category theory — the homomorphism, but one level up. It sends an entire category (objects and arrows) to another, in a way that respects how the arrows fit together.

Example. The free group functor Free:Set→Grp\mathrm{Free}: \mathbf{Set} \to \mathbf{Grp} sends a set SS to the free group on SS, and a function f:S→Tf: S \to T to the unique group homomorphism Free(S)→Free(T)\mathrm{Free}(S) \to \mathrm{Free}(T) that extends ff. Because extending a function to a homomorphism is unique, composition and identities are preserved automatically.

The diagram below shows a functor FF carrying the small category on the left (objects A,BA, B, arrow ff) to the category on the right (objects F(A),F(B)F(A), F(B), arrow F(f)F(f)). The dashed arrows record what FF does to each piece.

C D A B F(A) F(B) f F(f) F sends objects to objects and arrows to arrows

Authoritative sources

Example problem

The power-set functor P:Set→Set\mathcal{P}: \mathbf{Set} \to \mathbf{Set} sends a set SS to its power set P(S)\mathcal{P}(S), and a function f:S→Tf: S \to T to the map P(f):P(S)→P(T)\mathcal{P}(f): \mathcal{P}(S) \to \mathcal{P}(T) given by P(f)(X)=f(X)\mathcal{P}(f)(X) = f(X). Verify that P\mathcal{P} is a functor.

Solution

For f:S→Tf: S \to T and g:T→Ug: T \to U, P(g∘f)(X)=(g∘f)(X)=g(f(X))=P(g)(P(f)(X))\mathcal{P}(g \circ f)(X) = (g \circ f)(X) = g(f(X)) = \mathcal{P}(g)(\mathcal{P}(f)(X)), so composition is preserved. And P(idS)(X)=idS(X)=X\mathcal{P}(\mathrm{id}_S)(X) = \mathrm{id}_S(X) = X, so P(idS)=idP(S)\mathcal{P}(\mathrm{id}_S) = \mathrm{id}_{\mathcal{P}(S)}. Both functor laws hold.

Natural transformation

Definition. A natural transformation α:F⇒G\alpha: F \Rightarrow G between functors F,G:C→DF, G: \mathcal{C} \to \mathcal{D} is a family of morphisms αA:F(A)→G(A)\alpha_A: F(A) \to G(A) (one for each object AA) such that for every morphism f:A→Bf: A \to B the naturality square commutes:

G(f)∘αA=αB∘F(f)G(f) \circ \alpha_A = \alpha_B \circ F(f)
Details

A natural transformation is a “map between functors”: a coherent family of arrows, one per object, that commutes with everything in sight. The word “natural” means the family does not depend on any arbitrary choice — it behaves the same no matter which arrow you slide it past.

Example. Let F,G:Set→SetF, G: \mathbf{Set} \to \mathbf{Set} both send a set SS to S×SS \times S and a function ff to f×ff \times f. Define αS:S×S→S×S\alpha_S: S \times S \to S \times S to be the flip (a,b)↦(b,a)(a, b) \mapsto (b, a). This is a natural transformation F⇒GF \Rightarrow G: for any f:S→Tf: S \to T, both ways around the square send (a,b)(a, b) to (f(b),f(a))(f(b), f(a)).

The naturality square below is the defining condition: going across the top then down equals going down then across the bottom.

F(A) F(B) G(A) G(B) F(f) G(f) α_A α_B

The naturality condition is exactly the statement that this square commutes.

Authoritative sources

Example problem

Using the flip example above, verify the naturality square commutes for an arbitrary function f:S→Tf: S \to T.

Solution

Here F(f)=G(f)=f×fF(f) = G(f) = f \times f, so (f×f)(a,b)=(f(a),f(b))(f \times f)(a, b) = (f(a), f(b)). Going down then across: αT(f(a),f(b))=(f(b),f(a))\alpha_T(f(a), f(b)) = (f(b), f(a)). Going across then down: αS\alpha_S applied to the flipped pair (f(a),f(b))(f(a), f(b)) gives (f(b),f(a))(f(b), f(a)). Both paths yield (f(b),f(a))(f(b), f(a)), so the square commutes.

Limits and universal properties

Definition. A limit of a diagram D:J→CD: \mathcal{J} \to \mathcal{C} is an object LL together with a cone (morphisms L→D(j)L \to D(j) for each object jj of J\mathcal{J}) that is universal: for every other cone from an object XX there is a unique morphism X→LX \to L making all the triangles commute. The product A×BA \times B is the limit of the discrete diagram A,BA, B.

Details

A universal property characterizes an object by how other objects map into it, not by what it is made of. The limit is the “best” object that everything maps into: it is the unique (up to isomorphism) answer to a mapping-in problem. Products, equalizers, and pullbacks are all limits of particular diagrams.

Example. The product A×BA \times B of sets is the set of pairs (a,b)(a, b) with projections π1:A×B→A\pi_1: A \times B \to A and π2:A×B→B\pi_2: A \times B \to B. Given any set XX with maps f:X→Af: X \to A and g:X→Bg: X \to B, there is a unique map h:X→A×Bh: X \to A \times B making the triangles commute, namely h(x)=(f(x),g(x))h(x) = (f(x), g(x)).

The cone diagram below shows the universal property: the dashed arrow hh is the unique map that factors the cone from XX through A×BA \times B.

X A B A×B f g π₁ π₂ h (unique)

Authoritative sources

Example problem

Show that the product A×BA \times B is a limit: given a cone f:X→Af: X \to A, g:X→Bg: X \to B, exhibit the unique map h:X→A×Bh: X \to A \times B and check the triangles commute.

Solution

Define h(x)=(f(x),g(x))h(x) = (f(x), g(x)). Then π1∘h(x)=f(x)\pi_1 \circ h(x) = f(x) and π2∘h(x)=g(x)\pi_2 \circ h(x) = g(x), so both triangles commute. Uniqueness: any map h′h' with π1∘h′=f\pi_1 \circ h' = f and π2∘h′=g\pi_2 \circ h' = g must satisfy h′(x)=(π1h′(x),π2h′(x))=(f(x),g(x))=h(x)h'(x) = (\pi_1 h'(x), \pi_2 h'(x)) = (f(x), g(x)) = h(x), so h′=hh' = h.

Adjunctions

Definition. An adjunction F⊣GF \dashv G between functors F:C→DF: \mathcal{C} \to \mathcal{D} and G:D→CG: \mathcal{D} \to \mathcal{C} is a natural bijection of hom-sets

D(FA,B)≅C(A,GB)\mathcal{D}(F A, B) \cong \mathcal{C}(A, G B)

equivalently, a unit η:idC⇒GF\eta: \mathrm{id}_{\mathcal{C}} \Rightarrow G F and a counit ε:FG⇒idD\varepsilon: F G \Rightarrow \mathrm{id}_{\mathcal{D}} satisfying the triangle identities. FF is the left adjoint (the “free” functor) and GG the right adjoint (the “forgetful” functor).

Details

An adjunction is a precise sense in which one functor is a “left inverse” of another. The left adjoint FF is free: it builds the most structure you can from a bare object. The right adjoint GG is forgetful: it strips structure away, keeping only the underlying object. The bijection above says that maps out of a free object are the same thing as maps into the underlying object — which is exactly the universal property of the free construction. Universal properties are the shadows of adjunctions.

Example. Free:Set⇄Grp:U\mathrm{Free}: \mathbf{Set} \rightleftarrows \mathbf{Grp} : U, where UU is the forgetful functor from groups to sets. Homomorphisms from the free group Free(S)\mathrm{Free}(S) to a group GG are in bijection with plain functions from SS to the underlying set of GG — a homomorphism is determined entirely by where it sends the generators.

The diagram below shows the two functors and the unit η\eta and counit ε\varepsilon that make the adjunction work.

C D F (free) G (forgetful) η : id_C ⇒ G F ε : F G ⇒ id_D

Authoritative sources

Example problem

For the adjunction Free⊣U\mathrm{Free} \dashv U, identify which functor is the left adjoint and which is the right adjoint, and state the hom-set bijection it gives.

Solution

Free is the left adjoint and U is the right adjoint. The adjunction gives a natural bijection Grp(Free(S),G)≅Set(S,U(G))\mathbf{Grp}(\mathrm{Free}(S), G) \cong \mathbf{Set}(S, U(G)): a homomorphism out of the free group on SS is the same data as a function from SS to the underlying set of GG.

Duality and the opposite category

Definition. The opposite category Cop\mathcal{C}^{\mathrm{op}} has the same objects as C\mathcal{C} but reverses every arrow: a morphism f:A→Bf: A \to B in C\mathcal{C} becomes fop:B→Af^{\mathrm{op}}: B \to A in Cop\mathcal{C}^{\mathrm{op}}. A statement about categories is self-dual if it stays true when every arrow is reversed.

Duality is a free source of theorems: prove a statement once, and its dual is automatic. A colimit is simply a limit in the opposite category, so the coproduct in C\mathcal{C} is the product in Cop\mathcal{C}^{\mathrm{op}}, and a left adjoint is a right adjoint after passing to opposites.

Topoi

Definition. A topos (plural topoi) is a category that behaves like a universe of sets: it has a terminal object, all finite limits, is cartesian closed, and has a subobject classifier. Such a category supports an internal logic — one can carry out “set theory” and reasoning inside the category itself.

The category Set\mathbf{Set} of all sets is the canonical (elementary) topos. Topos theory is the bridge between category theory and logic/foundations: it is the categorical setting in which a category can serve as a foundation in its own right, and it is the framework behind sheaf theory and the semantics of logic.

Interactive: naturality square explorer

The simulation below lets you build a naturality square and check, arrow by arrow, whether a family of maps commutes with the arrows in sight — the defining condition for a natural transformation.

Why it matters

Category theory is a unifying language rather than a rival foundation: the same constructions (products, limits, adjunctions, duality) recur across algebra, topology, logic, and computation, and the categorical viewpoint states them once, for all. It is the native language of modern algebra and of homotopy type theory, and it organizes programming-language semantics (types as objects, programs as morphisms).

How it relates to the other classes

Set theory answers “what is an object made of?”; category theory answers “how does an object relate to others?”. The two are intertranslatable for most of mathematics: a category that behaves like a universe of sets — a topos — supports an internal logic and can serve as a foundation in its own right, so categorical and set-theoretic reasoning can be translated into each other. But category theory keeps only the morphisms, which is why it scales to structures too large or too abstract to be sets. It also meets Type theory at homotopy type theory, and it is the language in which the algebraic structures of Algebraic and discrete mathematics are most cleanly stated.

Quizz

Test yourself

Problem. A student defines a “functor” F:Set→SetF: \mathbf{Set} \to \mathbf{Set} by F(S)=S×SF(S) = S \times S on objects and F(f)=f×fF(f) = f \times f on morphisms, but then claims it is not a functor because FF “changes the size of the sets.” Using the definition of a functor, explain why the claim is wrong and verify the two functor laws.

Solution

A functor need not preserve size, cardinality, or any property of the objects — it only has to preserve composition and identities. For f:S→Tf: S \to T and g:T→Ug: T \to U, F(g∘f)=(g∘f)×(g∘f)F(g \circ f) = (g \circ f) \times (g \circ f) sends (s,s′)(s, s') to (g(f(s)),g(f(s′)))(g(f(s)), g(f(s'))), while F(g)∘F(f)=(g×g)∘(f×f)F(g) \circ F(f) = (g \times g) \circ (f \times f) sends (s,s′)(s, s') to (g(f(s)),g(f(s′)))(g(f(s)), g(f(s'))) — the same, so composition is preserved. And F(idS)=idS×idS=idS×SF(\mathrm{id}_S) = \mathrm{id}_S \times \mathrm{id}_S = \mathrm{id}_{S \times S}, so identities are preserved. Both laws hold, so FF is a functor.