Category Theory: What Makes a Construction Natural?

Take a finite-dimensional vector space $V$ over a field $k$. Its dual $V^{*}$ is the space of linear maps from $V$ to $k$. $V$ is isomorphic to $V^{*}$, but that isomorphism depends on a choice of basis, and nothing about the spaces picks a basis out for you.

Now take the double dual $V^{**}$. There is an isomorphism from $V$ to $V^{**}$ sending each vector $v$ to the evaluation functional, the map taking a functional $f$ to $f\left(v\right)$. No basis, no choices. It just works.

Mathematicians called isomorphisms like the second one "natural" long before anyone could say what that meant. In 1945, Samuel Eilenberg and Saunders Mac Lane wrote General Theory of Natural Equivalences to capture the idea, with this example as motivation. The machinery they invented reached far beyond the original question.

Categories#

A category consists of four things: objects; morphisms, arrows from one object to another; a composition rule, so arrows from $A$ to $B$ and from $B$ to $C$ compose to one from $A$ to $C$; and an identity morphism on every object. Two laws: composition is associative, and identities change nothing.

In Set, objects are sets and morphisms functions; in Grp, groups and homomorphisms; in Top, spaces and continuous maps. Same arrow structure, different content.

The objects can also be humble. A preorder is a category with exactly one morphism from $x$ to $y$ when $x\le y$: transitivity is composition, reflexivity the identities. A monoid is a category with a single object whose morphisms are the elements. So, as we put it in the Lean session, a category is a preorder that learned there is more than one way to get there, or a monoid that learned to go places.

Sameness without looking inside#

A morphism $f$ from $A$ to $B$ is an isomorphism if some $g$ back from $B$ to $A$ composes with it, in both orders, to identities.

Look at what this uses: morphisms and composition, nothing about insides. Yet it recovers the right notion every time: in Set a bijection, in Grp a group isomorphism, in Top a homeomorphism, in a preorder mutual order, in a monoid an invertible element. Five separate notions, one idea. This keeps happening: properties that seem to depend on what objects are made of turn out to be properties of the arrows alone.

Functors#

A functor $F$ from $C$ to $D$ sends objects to objects and morphisms to morphisms, preserving composition and identities. Two conditions, and you can translate between entire mathematical worlds.

In Set, List sends a set to its finite lists; a function becomes "apply it to every entry." In topology, the fundamental group sends a pointed space to its group of loops at the basepoint, up to deformation, and a basepoint-preserving continuous map to the induced homomorphism.

Functors preserve isomorphisms: if $f$ is one, so is $F\left(f\right)$. So pointed homeomorphic spaces have isomorphic fundamental groups, and if the groups differ, no homeomorphism exists: the fundamental group is an invariant that turns topological questions into algebraic ones.

Functors can also strip structure: the forgetful functor from Grp to Set keeps the underlying set and forgets the operation, while the free group functor goes the other way, sending a set $S$ to the most general group generated by $S$. And categories and functors themselves form a category, Cat (of small categories; size matters here, as always): the machinery applies to itself.

Natural transformations#

Back to the opening question. For functors $F$ and $G$ from $C$ to $D$, a natural transformation $\eta$ gives, for each object $X$, a morphism ${\eta }_X$ from $F\left(X\right)$ to $G\left(X\right)$. The components cannot be chosen independently: for every morphism $f$ from $X$ to $Y$, the square with $F\left(f\right)$ across the top, $G\left(f\right)$ across the bottom, and ${\eta }_X$, ${\eta }_Y$ down the sides must commute:

$$G\left(f\right)\circ {\eta }_X={\eta }_Y\circ F\left(f\right)$$

Transform then transport, or transport then transform: same answer. This square is the diagram the entire theory was built to state.

A worked example: the determinant. Fix $n$. From commutative rings to groups there are two functors: the invertible $n\times n$ matrices over $R$, and the group of units of $R$. For each ring, the determinant maps the first to the second. Naturality says: applying a ring homomorphism entrywise and then taking the determinant equals taking the determinant and then applying the homomorphism. True, because the determinant is a polynomial in the entries with integer coefficients, and ring homomorphisms preserve polynomials.

Pause and try: check the determinant square for one matrix and one homomorphism.

Take the integer matrix with rows $(6,5)$ and $(5,4)$, and the ring homomorphism "reduce mod 5." Along one path: the determinant is $6·4-5·5=-1$, and reducing mod 5 gives 4. Along the other: reducing entrywise gives rows $(1,0)$ and $(0,4)$, whose determinant is 4. The two paths agree.

And the introduction resolves. The evaluation maps $v\mapsto (f\mapsto f(v\left)\right)$ form a natural transformation from the identity functor to the double dual functor: embedding then applying $T^{**}$ equals applying $T$ then embedding, no basis anywhere. The single dual carries a wrinkle before the failure: the construction is contravariant, flipping arrows, so to compare it with the identity functor at all, Eilenberg and Mac Lane restrict to isomorphisms, where the direction can be corrected. Even then no choice of maps from $V$ to $V^{*}$ makes the squares commute: each needs a basis, and the square detects the choice. That is the testable distinction Eilenberg and Mac Lane were after; in their words, the concept of a category is "essentially an auxiliary one." Natural transformations were the point.

Universal properties#

Before category theory, defining a construction meant giving a recipe: ordered pairs for sets, componentwise multiplication for groups, the product topology for spaces. Three constructions, one job: whenever an object $C$ has morphisms $f$ to $A$ and $g$ to $B$, there is a unique morphism $h$ from $C$ to $A\times B$ whose composites with the two projections are $f$ and $g$.

That existence-and-uniqueness property characterizes the product without mentioning pairs or topologies: what it does, not what it is made of. Reverse every arrow and you get the coproduct $A+B$: maps out of it are exactly case analysis; in Set, disjoint union. In a poset, product is meet and coproduct is join: lattice theory is a special case.

The payoff shows on the tensor product. The classical construction, a free module quotiented by bilinearity relations, says little about why it behaves as it does; the universal property, that every bilinear map out of $V\times W$ factors uniquely through $V\otimes W$, lets the theorems follow from the diagram alone. The shift: instead of memorizing how something is built, ask what problem it solves.

Adjunctions#

Back to free and forgetful. A homomorphism from the free group $F\left(S\right)$ to a group $G$ is the same thing as a function from $S$ to the underlying set $U\left(G\right)$: it is determined by where the generators go, and any such function extends uniquely. So Hom(F(S), G) and Hom(S, U(G)) are in bijection, naturally in both variables: change $S$ or $G$, and the bijection commutes with the change. That is an adjunction. $F$ is the left adjoint, $U$ the right.

The pattern is everywhere. Functions from $A\times B$ to $C$ correspond naturally to functions from $A$ to functions from $B$ to $C$: currying. Adjunctions between posets are Galois connections: $f\left(x\right)\le y$ exactly when $x\le g\left(y\right)$. The inclusion of the integers into the reals is left adjoint to the floor function: $n\le x$ exactly when $n\le \lfloor x\rfloor$. Lawvere showed even the quantifiers of first-order logic are adjoints to substitution. Mac Lane's summary: adjoint functors arise everywhere.

Yoneda#

This whole subject defines things by what they do, not what they are made of. The Yoneda lemma says that is enough.

Fix an object $X$. Sending each object $A$ to the set of morphisms from $A$ to $X$ is itself a functor, via precomposition. Call it the representable functor of $X$, the profile of $X$: how $X$ looks to every other object.

The lemma: for any set-valued functor $F$ of the same variance, natural transformations from the representable of $X$ to $F$ correspond exactly to elements of $F\left(X\right)$.

The proof is one move. A natural transformation $\eta$ has a component at $X$ itself, and the hom-set there contains the identity on $X$. Let $\xi ={\eta }_X\left({id}_X\right)$. Naturality forces everything else: for any morphism $g$ from $A$ to $X$, the square for $g$ gives ${\eta }_A\left(g\right)=F\left(g\right)\left(\xi \right)$. One element reconstructs the whole transformation.

Specialize $F$ to the representable of another object $Y$: natural transformations between profiles correspond to morphisms from $X$ to $Y$, the profile embedding is fully faithful, and objects with naturally isomorphic profiles are isomorphic. The opening principle is now a theorem.

You are what you do.

If you remember three things#

1. A construction is natural when one morphism per object commutes with every morphism of the category; that test separates the double dual from the basis-dependent dual.
2. Universal properties define constructions by the problem they solve; products, coproducts, meets, joins, and tensor products are one pattern.
3. The Yoneda lemma makes "defined by what it does" a theorem: an object is determined, up to isomorphism, by its morphisms from everything else.