Mappings That Preserve Structure

Consider a mapping between two small categories. It sends each object to a sensible object. It sends each arrow to an arrow with the correct source and target. Nothing about it looks wrong.

It is not a functor.

The check that catches it is one equation. In the worked example the composite $g\circ f$ maps to ${\mathrm{id}}_Y$, while the composite of the images, $G(g)\circ G(f)$, is ${\mathrm{id}}_Y\circ h=h$. Those are different arrows, so the mapping does not preserve composition, and that is the whole of what disqualifies it.

This is what the subject is for. Category theory supplies laws that decide whether a mapping deserves to be called structure-preserving, and the laws are equations rather than descriptions, which means they can be checked, and they catch cases inspection does not.

The same pattern recurs one level up. A natural transformation is a family of arrows whose square must commute: two routes around it must give the same arrow. Every such square can be drawn, for any family whatever, so drawing it establishes nothing. The condition is an equation, evaluated at every arrow of the source category.

This unit covers the category axioms, the two functor laws, the composite that detects a failure, and naturality, checked rather than recognised.

The canonical statements above give the axioms. What follows is the scope of each, since that decides what a check must cover.

Composition is partial, and that is part of the definition. $g\circ f$ exists exactly when the target of $f$ is the source of $g$. A composition table pairing arrows that do not meet describes something that is not a category, and the defect is in the data rather than in the laws. Checking a structure therefore begins by confirming that composition is defined precisely where the endpoints meet.

Associativity quantifies over composable triples. In the worked category there are fifteen of them once identities are included. A verification that checks a few establishes nothing, because one failing triple refutes the structure.

The functor conditions split into two kinds. Preserving sources and targets is a typing condition: a mapping violating it is not a candidate at all, since $F(g)\circ F(f)$ would not be defined. The two laws are the substantive requirements, and the interesting failures satisfy the typing condition and break the composition law.

What a functor does not have to do. It need not be injective on objects or arrows, collapsing several objects to one is permitted, and the worked functor does exactly that. It need not be surjective. It need not preserve anything beyond identities and composition; that a functor happens to preserve some other property is a theorem about that functor, not part of being one.

Naturality is indexed by arrows, not by objects. The family $\alpha$ is given per object, and the condition is stated per arrow:

A transformation can satisfy this at several arrows and fail at another, so a check is incomplete until every arrow has been examined, identities included, though those are usually immediate.

A caution about degenerate examples. When $F$ and $G$ are constant functors, every naturality square reduces to the same equation and holds for uninteresting reasons. Such a case verifies that the check has been performed correctly and tests nothing about whether the two routes could differ, so it should be labelled rather than offered as evidence.

A mapping between categories has to do three things: place objects, place arrows, and keep the endpoints consistent. Those are easy to satisfy and easy to check by eye. The composition law is neither, and it is the one carrying the meaning.

Consider what could go wrong that inspection misses. Take a category with $f:A\to B$, $g:B\to C$ and their composite $gf:A\to C$. A mapping $G$ can send $f$ to an arrow $h:X\to Y$, send $g$ to ${\mathrm{id}}_Y$, and send $gf$ to ${\mathrm{id}}_Y$. Every arrow has a source and target consistent with the object map: $f$ runs $A\to B$ and $h$ runs $G(A)\to G(B)$; $g$ runs $B\to C$ and ${\mathrm{id}}_Y$ runs $G(B)\to G(C)$, both being $Y$. Each assignment checks out on its own.

But the composite of the images is ${\mathrm{id}}_Y\circ h=h$, and the image of the composite is ${\mathrm{id}}_Y$. These are different arrows. $G$ has made a choice about $gf$ that contradicts the choices it made about $f$ and $g$ separately, which is exactly what preserving composition forbids.

That is why the definition is a law rather than a description. "A functor is a mapping that respects structure" cannot be checked. $F(g\circ f)=F(g)\circ F(f)$ can be, and it decides cases that the informal phrase leaves open.

Collapsing is allowed; inconsistency is not. The worked functor $F$ sends two distinct objects to the same object and sends a non-identity arrow to an identity. Both are permitted: a functor need not be injective, and losing information is not the same as contradicting oneself. The requirement is that whatever $F$ does to composites agrees with what it does to the parts.

Naturality repeats the pattern. Given two functors and a family of arrows between them, the square

always exists. The four arrows are defined and their endpoints line up by construction. What is at issue is whether the two routes agree, and that has to be evaluated. On the worked example both routes give $h$ at all six arrows.

The programming reading is the same statement. A map function that type-checks satisfies the typing condition; whether it satisfies map (g . f) = map g . map f is a separate question the compiler does not ask. A map that reverses its container while mapping type-checks perfectly and breaks the law, in the same way and for the same reason as $G$ above.

A partial order as a category. Objects are the elements; there is one arrow $a\to b$ exactly when $a\le b$. Composition is transitivity, identities are reflexivity, and associativity is automatic because any two arrows with the same source and target are equal. The concept hierarchy of the knowledge-representation unit is a category in this sense, and a monotone map between two such orders is precisely a functor.

Lists with map. Objects are types, arrows are functions, and the list constructor with map is a functor when map id = id and map (g . f) = map g . map f. Both hold for the standard implementation. A variant that reverses the list while mapping type-checks identically and breaks the first law, since mapping the identity would reverse.

A monoid as a one-object category. One object, one arrow per element, composition is the monoid operation. Associativity of the category is associativity of the monoid; the identity arrow is the unit. A functor between two such categories is exactly a monoid homomorphism. The categorical laws reduce to the algebraic ones with nothing left over.

A mapping that collapses everything. Send every object of $\mathcal{C}$ to a single object $X$ and every arrow to ${\mathrm{id}}_X$. The identity law holds because every identity is sent to ${\mathrm{id}}_X$, which is the identity at the only object in the image. The composition law holds because both sides reduce to the same arrow whatever was composed: $F(g\circ f)={\mathrm{id}}_X$, and $F(g)\circ F(f)={\mathrm{id}}_X\circ {\mathrm{id}}_X={\mathrm{id}}_X$. So this is a functor. It is uninformative and entirely legitimate, which shows that satisfying the laws is a minimum rather than a merit.

reverse on lists as a natural transformation. For each type $T$, reverse maps a list of $T$ to a list of $T$. Naturality says map f . reverse = reverse . map f, which holds because reversing rearranges positions without examining elements. Contrast sort, which inspects elements: map f . sort and sort . map f differ as soon as f does not preserve the ordering, so sort is not natural.

---

The first three are cases where familiar structures turn out to be categories and familiar maps turn out to be functors, so the laws recover what was already known. The fourth shows the laws are a floor, not a distinction. The fifth is the one that bites: two functions of the same type, one natural and one not, distinguished by an equation rather than by their signatures.

To verify a proposed category.

1. Tabulate arrows with sources and targets. Every later check reads this table.
2. Confirm composition is defined exactly where endpoints meet, defined for every composable pair, undefined for every other. A table with a missing entry or a spurious one is not a category.
3. Check the identity laws at every arrow: $f\circ {\mathrm{id}}_{\text{src}}=f$ and ${\mathrm{id}}_{\text{tgt}}\circ f=f$.
4. Check associativity on every composable triple. Enumerate them rather than sampling; report how many there were, so the verification is auditable.

To verify a proposed functor.

1. Check the typing condition first. For each arrow $f:A\to B$, confirm $F(f):F(A)\to F(B)$. A violation here means the composites in step 3 are not even defined, so there is nothing further to check.
2. Check $F({\mathrm{id}}_A)={\mathrm{id}}_{F(A)}$ at every object.
3. Check $F(g\circ f)=F(g)\circ F(f)$ at every composable pair, identities included. List the pairs checked.
4. Do not stop at the object map. It is the least informative part of the verification and the part most likely to look convincing.

To diagnose a mapping that fails.

1. Separate the two kinds of failure. Wrong endpoints mean the mapping was never a candidate; correct endpoints with a broken composite mean it was a candidate and failed on the substance.
2. Name the composite. " $G(g\circ f)={\mathrm{id}}_Y$ but $G(g)\circ G(f)=h$" is a diagnosis; "the functor laws fail" is not.
3. Ask which choice to revise. The failure is an inconsistency among three assignments, to $f$, to $g$, and to $gf$, and any one of them could be the mistake.

To verify naturality.

1. Confirm both $F$ and $G$ are functors before checking the square. A transformation between things that are not functors is undefined.
2. For each arrow $f:A\to B$, evaluate both routes, ${\alpha }_B\circ F(f)$ and $G(f)\circ {\alpha }_A$, and compare.
3. Cover every arrow, not every object. Identities are usually immediate and still belong in the list.
4. Check whether the example is degenerate. If both functors are constant, every square reduces to one equation and the check exercises the procedure without testing the condition. Say so when reporting.

Checks. Confirm the number of composable triples independently before trusting an associativity result. Confirm that a functor's image of an identity is an identity rather than merely an arrow of the right type. And when a check passes, ask whether it could have failed on the example given. A verification that no assignment could have failed has confirmed nothing.

The category $\mathcal{C}$. Three objects $A$, $B$, $C$. Six arrows:

Composition: identities act as identities, and $g\circ f=gf$. No other pair is composable except through identities.

Step 1: is it a category? Enumerating every triple $(a,b,c)$ where both $b\circ c$ and $a\circ b$ are defined gives 15 composable triples, and $a\circ (b\circ c)=(a\circ b)\circ c$ holds in all fifteen. The identity laws hold at each of the six arrows by construction. So $\mathcal{C}$ is a category.

Note what the check required: not a spot test, but every triple. One failure would have refuted it.

Step 2: a functor $F:\mathcal{C}\to \mathcal{D}$. Let $\mathcal{D}$ have objects $X$, $Y$ and arrows ${\mathrm{id}}_X$, ${\mathrm{id}}_Y$, $h:X\to Y$.

Identity law. $F({\mathrm{id}}_A)={\mathrm{id}}_X={\mathrm{id}}_{F(A)}$, and likewise at $B$ and $C$. Holds.

Composition law. The only non-trivial composite is $g\circ f=gf$:

Equal. Every composite involving identities checks the same way. Holds, so $F$ is a functor.

Observe that $F$ collapses $A$ and $B$ to one object and sends the non-identity arrow $f$ to an identity. Both are permitted. A functor may lose information.

Step 3: a mapping $G$ that is not a functor.

Check the endpoints: $f:A\to B$ maps to $h:X\to Y$, and $G(A)=X$, $G(B)=Y$. Correct. $g:B\to C$ maps to ${\mathrm{id}}_Y:Y\to Y$, and $G(B)=G(C)=Y$. Correct. Every arrow lands where the object map says it should.

Now the composition law:

$G$ is not a functor. The object map is sound, every arrow has the right source and target, and only the composition law detects the problem. The conditions that are easiest to check are not the ones that decide the question.

Step 4: a natural transformation. Let $P$ send every object of $\mathcal{C}$ to $X$ and every arrow to ${\mathrm{id}}_X$; let $Q$ send every object to $Y$ and every arrow to ${\mathrm{id}}_Y$. Both are functors, constant functors always are. Take ${\alpha }_o=h:X\to Y$ at each object.

Naturality requires ${\alpha }_B\circ P(f)=Q(f)\circ {\alpha }_A$ for every arrow. Evaluating both routes at all six arrows:

Every row agrees, so $\alpha$ is natural.

What step 4 does not demonstrate. Because $P$ and $Q$ are constant, $P(n)$ is always ${\mathrm{id}}_X$ and $Q(n)$ is always ${\mathrm{id}}_Y$, so both routes reduce to $h$ regardless of the arrow. The check confirms the mechanics, evaluate both paths, compare, and tests nothing about whether the two could ever differ. A searching example needs functors that act differently on arrows, and this one should be read as an exercise in performing the check rather than as evidence that naturality is easy to satisfy.

$F$ against $G$, on the same category.

The first four rows are identical. Only the fifth comparison separates them, and it is the only row that could not be settled by inspection.

The typing condition against the composition law.

A mapping sending $f:A\to B$ to an arrow $X\to Z$ when $F(B)=Y$ fails the typing condition, and the composite $F(g)\circ F(f)$ is then not even defined. There is nothing to check. That is a malformed candidate. A mapping passing the typing condition and failing composition is a well-formed candidate that is false, which is the more instructive failure and the harder one to spot.

Collapsing against contradicting.

$F$ sends two objects to one and a non-identity arrow to an identity, losing information, and remains a functor. $G$ assigns to $gf$ something incompatible with its assignments to $f$ and $g$. Losing information is permitted; being inconsistent about composites is not.

reverse against sort.

Both have the same shape: for each type, a function from lists of that type to lists of that type. reverse satisfies map f . reverse = reverse . map f because it moves elements without looking at them. sort does not, because it compares them, so mapping first can change the order it produces. Identical signatures, different answers to an equation.

A drawn square against a commuting square.

Every naturality square can be drawn: the four arrows exist and their endpoints match by construction. Whether the two routes are the same arrow is a separate question, settled by evaluating both. Drawing establishes that the question is well posed, not that the answer is yes.

A check that could fail against one that could not.

Verifying naturality between two constant functors gives agreement at every arrow, and both routes reduce to the same arrow whatever the transformation, so no assignment could have failed. Verifying between functors that act differently on arrows is a check with a possible negative outcome. Only the second is evidence.

Concluding from the object map. Where objects go is the least informative part of a functor and the part that looks most convincing. $G$ in the worked example has an object map nobody would query, and it is not a functor.

Checking a sample of triples. Associativity is a claim about every composable triple, fifteen in the worked category. A single failing triple refutes the structure, so a sample that passes establishes nothing. The same applies to the functor laws over composable pairs.

Accepting a drawn square. Every naturality square can be drawn. The condition is that the two routes give the same arrow, and settling it requires evaluating both.

Checking naturality at objects rather than at arrows. The transformation is indexed by objects and the condition is indexed by arrows. A family can behave correctly at every object in isolation and still fail the square for some arrow, which is exactly what the condition is for.

Reporting a check that could not have failed. Verifying naturality between two constant functors yields agreement at every arrow regardless of the transformation, since both routes collapse to the same composite. The check confirms the procedure was carried out and confirms nothing about the example. When this is the situation, say so.

---

Two errors specific to the programming reading.

Trusting the type-checker. A map that satisfies the signature may violate map id = id. A version that reverses while mapping does exactly that, and compiles. Types are the typing condition; the laws are separate and unenforced.

Assuming a polymorphic function is natural. Polymorphism is not naturality. sort has the shape of a natural transformation and fails the square, because it inspects the elements it moves. What makes reverse natural is that it does not.

---

And one about the abstraction itself. Stating a problem categorically supplies the laws and whatever follows from them, at the cost of finding the right category. A categorical framing that nobody uses to prove anything supplies nothing. The laws are worth invoking when a proof or a guarantee depends on them, not as a way of restating what was already clear.

Library interfaces in functional languages. A type declaring itself a functor is expected to satisfy both laws, and optimisers rely on it: rewriting map g . map f to map (g . f) eliminates a traversal and is valid only because the law holds. An implementation that breaks the law produces a program whose behaviour changes under optimisation, which is among the hardest classes of bug to trace.

Parametricity and free theorems. For a polymorphic function that cannot inspect its type parameter, naturality is guaranteed by the type alone, which is why reverse needs no proof and sort does. This converts a whole class of correctness arguments into a typing observation, and it fails precisely where the function looks at what it is carrying.

Database and schema migration. A migration that maps one schema to another and must compose, apply migration one, then migration two, and get the same result as applying the composite, is asking for a functor. Where the composition law fails, migrations applied in sequence disagree with the combined migration, and the discrepancy appears only on the paths nobody tested.

Compiler intermediate representations. A translation between representations is expected to commute with the operations both support, which is naturality stated for a compiler. Where it holds, optimisations proved on one representation transfer to the other; where it silently fails, an optimisation valid upstream becomes invalid downstream.

Order-preserving maps between hierarchies. A partial order is a category with at most one arrow between objects, so a monotone map between two concept hierarchies is a functor and the laws hold automatically. This is the point where this unit and the knowledge-representation unit meet, and it explains why ontology alignment tools can assume composition without checking it.

---

In each case something is inferred from the laws, a rewrite is safe, a proof transfers, two paths agree, and the inference is only as sound as the laws are. That is the practical argument for checking them: not the abstraction itself, but that code elsewhere already depends on them.