Foundations of mathematics

Categories and functors

A category packages objects and the arrows between them, subject only to associativity and identity; a functor is a structure-preserving translation between two such worlds, and it turns out that once you fix "how things relate", the objects themselves are determined only up to a unique isomorphism.

IntuitionSame shape, different costume

A translator, a graph, a network of train stations connected by routes, a set of tasks connected by "must happen before" — all of these share one skeleton: some things (objects) and some arrows between them that can be chained. A category makes that skeleton precise; a functor is a way of redrawing one such network inside another while keeping every chain of arrows intact.

Objects as nodes, morphisms as directed edges; composing two edges in a row gives a third edge, exactly the data a category records.

UndergraduateCategories: objects, morphisms, composition

Definition: Category

A category $\mathcal{C}$ consists of a collection of objects $A, B, C, \dots$ and, for every pair, a set of morphisms $\mathrm{Hom}_{\mathcal{C}}(A,B)$ , together with a composition rule sending $f : A \to B$ and $g : B \to C$ to $g \circ f : A \to C$ , and an identity morphism $1_A : A \to A$ for every object.

h \circ (g \circ f) = (h \circ g) \circ f

Two axioms make this data into a category: composition is associative ( $h \circ (g \circ f) = (h \circ g) \circ f$ , so a chain of arrows has one unambiguous composite, no matter how it is parenthesized) and identities are neutral ( $1_B \circ f = f = f \circ 1_A$ , so composing with $1_A$ or $1_B$ never changes a morphism).

1_B \circ f = f = f \circ 1_A

Covariant vs. contravariant functors
Kind	Action on morphisms	Typical example
Covariant	Sends $f : A \to B$ to $F(f) : F(A) \to F(B)$ , same direction	The list functor, forgetful functors
Contravariant	Sends $f : A \to B$ to $F(f) : F(B) \to F(A)$ , reversed direction	The dual-space functor, the Hom(-,A) presheaf

AdvancedFunctors and natural transformations

A functor $F : \mathcal{C} \to \mathcal{D}$ assigns to every object $A$ of $\mathcal{C}$ an object $F(A)$ of $\mathcal{D}$ , and to every morphism $f$ a morphism $F(f)$ , so that composition and identities are preserved: $F(g \circ f) = F(g) \circ F(f)$ and $F(1_A) = 1_{F(A)}$ . A natural transformation $\eta : F \Rightarrow G$ between two functors $\mathcal{C} \to \mathcal{D}$ assigns to every object $A$ a morphism $\eta_A : F(A) \to G(A)$ in $\mathcal{D}$ , subject to the naturality square: for every $f : A \to B$ , $G(f) \circ \eta_A = \eta_B \circ F(f)$ .

F(g \circ f) = F(g) \circ F(f)

G(f) \circ \eta_A = \eta_B \circ F(f)

Theorem: Terminal objects are unique up to unique isomorphism

If $T_1$ and $T_2$ are both terminal objects of $\mathcal{C}$ (there is exactly one morphism from every object into each of them), then $T_1 \cong T_2$ : there is an isomorphism between them, and it is the only morphism $T_1 \to T_2$ . The dual statement holds for initial objects, and hence for products by the same argument applied to the category of candidate cones.

Why is it true?

Without this fact, "the" terminal object or "the" product would not be well-defined — different constructions of a product (say, ordered pairs vs. some other encoding) need to be interchangeable, and uniqueness up to unique isomorphism is exactly the precise sense in which they are "the same".

Proof

Since $T_2$ is terminal, every object — in particular $T_1$ — has exactly one morphism into it; call it $u : T_1 \to T_2$ . Since $T_1$ is terminal, symmetrically there is exactly one $v : T_2 \to T_1$ .

Consider the composite $v \circ u : T_1 \to T_1$ . Because $T_1$ is terminal, there is exactly one morphism $T_1 \to T_1$ , and $1_{T_1}$ is one such morphism; since $v \circ u$ is also a morphism $T_1 \to T_1$ , uniqueness forces $v \circ u = 1_{T_1}$ .

By the symmetric argument using the terminality of $T_2$ , the composite $u \circ v : T_2 \to T_2$ must equal $1_{T_2}$ : $u \circ v = 1_{T_2}$ .

A morphism with a two-sided inverse is by definition an isomorphism, so $u$ is an isomorphism $T_1 \cong T_2$ with inverse $v$ . It is the unique morphism $T_1 \to T_2$ because terminality of $T_2$ already says there is only one such morphism at all — $u$ was forced from the start, and it simply turned out to be invertible.

Theorem: Functors preserve isomorphisms

If $F : \mathcal{C} \to \mathcal{D}$ is a functor and $f : A \to B$ is an isomorphism in $\mathcal{C}$ with inverse $g : B \to A$ , then $F(f) : F(A) \to F(B)$ is an isomorphism in $\mathcal{D}$ , with inverse $F(g)$ .

Why is it true?

This is what makes functors trustworthy translators: a functor can never accidentally break an equivalence into two genuinely different objects, so classifying objects "up to isomorphism" is a question functors respect.

Proof

Since $f$ and $g$ are mutually inverse, $g \circ f = 1_A$ and $f \circ g = 1_B$ .

Apply $F$ to the first equation. Functors preserve composition, so $F(g \circ f) = F(g) \circ F(f)$ ; functors preserve identities, so $F(1_A) = 1_{F(A)}$ . Combining these with $g \circ f = 1_A$ gives $F(g) \circ F(f) = 1_{F(A)}$ .

Apply $F$ to the second equation in the same way: $F(f \circ g) = F(f) \circ F(g)$ and $F(1_B) = 1_{F(B)}$ , so from $f \circ g = 1_B$ we get $F(f) \circ F(g) = 1_{F(B)}$ .

The two displayed equations say exactly that $F(g)$ is a two-sided inverse of $F(f)$ . A morphism with a two-sided inverse is an isomorphism, so $F(f) : F(A) \to F(B)$ is an isomorphism with inverse $F(g)$ , as claimed.

UndergraduateApplications: functional programming and database migration

Every mainstream functional language has a `Functor` type class precisely because containers like lists, trees and `Maybe`/`Option` are functors on the category of types and functions: `fmap` is $F$ on morphisms, and the functor laws $\mathrm{fmap}\,\mathrm{id} = \mathrm{id}$ , $\mathrm{fmap}\,(g \circ f) = \mathrm{fmap}\,g \circ \mathrm{fmap}\,f$ are exactly the axioms above. `Monad` refines this further with two natural transformations (`return` and `join`) satisfying naturality-square-style coherence laws. Outside programming, David Spivak's functorial data migration models a database schema as a small category (tables as objects, foreign keys as morphisms) and a schema migration as a functor between two such categories, so that "moving data correctly" literally means "being a functor" — composition-preservation guarantees that migrating via an intermediate schema gives the same result as migrating directly.

Example: Checking the functor laws for lists

Take $\mathrm{fmap}$ for lists, defined by applying a function to every element: $\mathrm{fmap}\,f\,[x_1,\dots,x_n] = [f(x_1),\dots,f(x_n)]$ . Verify both functor laws on the concrete list $[1,2,3]$ with $f(x)=x+1$ and $g(x)=2x$ .

Solution

First law, $\mathrm{fmap}\,\mathrm{id} = \mathrm{id}$ : applying the identity function element-wise gives $\mathrm{fmap}\,\mathrm{id}\,[1,2,3] = [\mathrm{id}(1),\mathrm{id}(2),\mathrm{id}(3)] = [1,2,3]$ , which is exactly $\mathrm{id}\,[1,2,3]$ . This holds for any list, not just this one, because applying "do nothing" to each element does nothing to the list.

Second law, $\mathrm{fmap}\,(g \circ f) = \mathrm{fmap}\,g \circ \mathrm{fmap}\,f$ : compute the left side first. $(g \circ f)(x) = 2(x+1)$ , so $\mathrm{fmap}\,(g\circ f)\,[1,2,3] = [2\cdot2, 2\cdot3, 2\cdot4] = [4,6,8]$ .

Now the right side: $\mathrm{fmap}\,f\,[1,2,3] = [2,3,4]$ , and then $\mathrm{fmap}\,g\,[2,3,4] = [4,6,8]$ .

Both sides equal $[4,6,8]$ , confirming the law on this example; the general proof is the same computation with $x_i$ instead of $1,2,3$ , since $\mathrm{fmap}$ never reorders or drops elements.

Example: A schema migration as a functor

A schema $\mathcal{S}_1$ has tables `Person` and `City`, with a foreign key `livesIn : Person -> City`. A new schema $\mathcal{S}_2$ splits `Person` into `Person` and `Contact`, with `hasContact : Person -> Contact` and `livesIn2 : Contact -> City`. Describe the migration as a functor and explain what preserving composition buys you.

Solution

Model each schema as a category: objects are tables, and morphisms are foreign keys composed freely (so $\mathcal{S}_1$ has the composite $\texttt{livesIn} : \texttt{Person} \to \texttt{City}$ as a generator). The migration $F : \mathcal{S}_1 \to \mathcal{S}_2$ sends $\texttt{Person} \mapsto \texttt{Person}$ , $\texttt{City} \mapsto \texttt{City}$ , and the morphism $\texttt{livesIn}$ to the composite morphism $\texttt{livesIn2} \circ \texttt{hasContact} : \texttt{Person} \to \texttt{City}$ in $\mathcal{S}_2$ .

For $F$ to be a functor it must send identities to identities (trivial here) and respect composition: any chain of foreign keys built in $\mathcal{S}_1$ out of $\texttt{livesIn}$ must map to the same chain built out of $F(\texttt{livesIn}) = \texttt{livesIn2} \circ \texttt{hasContact}$ , in the same order, with no steps skipped or reordered.

This is exactly what the theorem "functors preserve composition" buys an engineer: if a query joins $\texttt{Person}$ to $\texttt{City}$ via $\texttt{livesIn}$ in the old schema, translating each table and mapping $\texttt{livesIn}$ to the two-step path and then executing the join gives the same answer as translating the whole query as one unit — data migrated table-by-table is guaranteed consistent with data migrated query-by-query, precisely because $F(g \circ f) = F(g) \circ F(f)$ .

Research frontier as of 2026

Category theory keeps absorbing new application domains: "categorical deep learning" recasts neural network layers and their composition as morphisms in a category with parameters, unifying architectures like CNNs and transformers as instances of one categorical pattern; applied category theory (Fong–Spivak's textbook, the annual ACT conference) treats functorial data migration, wiring diagrams for systems engineering, and compositional game theory as mainstream tools outside pure mathematics. Inside mathematics, ∞-categories (Lurie) and homotopy type theory reformulate "isomorphism" itself as a path, feeding directly into the Lean/mathlib formalization effort. The open frontier is largely about scaling: making these categorical translations computable and machine-checkable rather than only diagrammatic.

Which pair of equations are the two category axioms?

A contravariant functor sends $f : A \to B$ to a morphism going which way?

In Spivak's functorial data migration, what does a schema migration correspond to?

If $u : T_1 \to T_2$ is the unique morphism between two terminal objects, what does the theorem say about $u$ ?

References

Saunders Mac Lane (1998). Categories for the Working Mathematician
Emily Riehl (2016). Category Theory in Context
David I. Spivak (2012). Functorial Data Migration · arXiv:1009.1166