The world made of allowable moves

Imagine receiving a map with cities and one-way roads. You can answer whether Delhi has a road to Jaipur. You cannot yet answer whether a Delhi-to-Jaipur road followed by a Jaipur-to-Udaipur road counts as one admissible Delhi-to-Udaipur journey. A directed graph gives points and arrows. A category adds the law for joining arrows.

This difference sounds small because ordinary travel supplies composition automatically. Drive the first road, then the second. In engineered and conceptual systems, the join is often the hard part. A temperature reading in Celsius may enter a Fahrenheit converter, but a signed payment instruction may not enter an unsigned executor. A model proposal may enter a policy check, but it may not enter a bank account. Types, permissions and state decide which arrows can meet.

A graph can still be the right starting point. It records generators: the primitive moves we are willing to name. To obtain a category, we must decide what every finite route means. The least committal choice is to keep each route as a distinct morphism. A more opinionated choice declares some routes equal. “Normalise, then validate” might be required to equal “validate with normalisation built in”. That equation is not drawn merely for tidiness. It says every observation admitted by the model must treat the two composites as the same transformation.

This is why a category is better understood as a world of lawful substitution than as a decorated network. When two paths are equal, one may replace the other inside any larger compatible route. When they are not equal, the model preserves a distinction that later composition may expose. The choice affects what can be proved, what can be replaced and what can fail.

The minimum formal machinery

A category C contains objects such as A, B and C. For each ordered pair, it may contain morphisms from the first object to the second. We write a morphism as f: A → B. If g: B → C, the codomain of f matches the domain of g, so the pair can be composed. The result is another morphism g ∘ f: A → C, read from right to left: first f, then g.

Two laws make this a category rather than a loose network. Every object A has an identity morphism id_A: A → A. Composing it before or after a compatible morphism changes nothing. Composition is associative: for f: A → B, g: B → C and h: C → D, both ways of placing brackets yield the same complete morphism.

Modern notation often gathers all morphisms from A to B into a collection written Hom_C(A,B). The subscript names the category because the same apparent objects can admit different morphisms in different contexts. Between two sets, one category may allow every function. Another may allow only bijections. Between software states, one category may admit every executable transition; another may admit only transitions authorised by a current policy. The objects alone never determine the category.

The first displayed phrase is a useful warning. Composition is typed. One cannot compose arbitrary arrows merely because their names sound compatible. The laws also say less than newcomers often assume. Associativity does not say that order is irrelevant. Usually g ∘ f differs from f ∘ g, and one of them may be undefined. Identities are not inverses. A morphism need not be reversible.

The identity law also carries more content than the phrase “do nothing” suggests. A health-check call that refreshes a lease is not an identity on a state that includes lease expiry. A dry-run that increments a billable counter is not an identity on an account state. An unchanged payload can therefore conceal a changed object. The cure is not to argue about the word identity. It is to enlarge or refine the object until the claimed no-op really leaves every modelled component unchanged.

flowchart LR
  A["The world made of allowable moves"] --> B["Why composition carries the<br/>explanation"]
  B --> C["Three small worlds, three<br/>meanings of arrow"]
  C --> D["From formal shape to operating<br/>instrument"]
  D -. "re-test" .-> A
  classDef first fill:#0a1424,stroke:#087A98,stroke-width:2px,color:#e6f3ff
  classDef step fill:#0a1424,stroke:#3f7da0,stroke-width:1px,color:#e6f3ff
  class A first
  class B,C,D step

Why composition carries the explanation

Objects attract attention because they are easy to name. A database, model, sensor or person appears to be the thing doing the work. Yet most system behaviour lies between named things. A sensor becomes useful through calibration; a model output becomes consequential through authorisation; a mathematical object becomes comparable through the maps that preserve its structure.

Category theory changes the unit of analysis. Instead of asking only, “What is this object made of?”, it asks, “What can enter it, what can leave it, and which routes remain coherent?” Riehl describes this as a shift from direct characterisation towards transformations among objects of the same general type.³ Fong and Spivak emphasise the accompanying demand for coherence: combining a chain of chains must agree with combining the long chain.⁵

Associativity is a regrouping guarantee

Take three ordinary functions. Let f add one, g double the result, and h take the remainder after division by three. Starting with 2 gives 3 after f, 6 after g, and 0 after h. We can first combine “add one, then double” and then apply the remainder operation. Or we can first combine “double, then take the remainder” and apply that composite after adding one. The order of actions is unchanged. Only the brackets move.

The composition dividend

Suppose a workflow has six stages, with two certified implementations available at each stage. There are 64 end-to-end implementation routes. There are only 12 local implementations. Under a strong assumption that each implementation honours the same typed contract and that composition preserves the stated invariant, local certificates can be reused across many routes. This does not abolish end-to-end testing. It changes what must be retested after a local substitution.

The distinction is between evidence about a component and evidence that travels through composition. A unit test may show that a converter returns the expected values. A compositional contract additionally states the accepted input type, produced output type, preserved invariant and effect boundary. Only the latter can support a reasoned substitution inside routes not individually enumerated. Even then, integration tests remain necessary for assumptions that the contract deliberately excludes, such as latency, contention or correlated failure.

The dividend is not fewer tests by decree. It is the ability to explain which tests are reusable and why. Without that explanation, a modular architecture may simply distribute uncertainty across more interfaces.

Three small worlds, three meanings of arrow

The same category axioms can organise very different worlds. That flexibility is a strength only when the meaning of an arrow remains explicit. A path, a function and an order relation can all be morphisms, but they preserve different information. The following examples make that difference visible.

World one: paths remain paths

Start with a directed map. Build a category whose objects are locations and whose morphisms are finite directed paths. Composition concatenates paths; the identity at a location is the empty path that starts and ends there. This construction is called the free category on a graph. It adds all composites required by the category laws without adding equations that identify distinct routes.

Two journeys from Checked to Loaded can therefore remain different morphisms even if they begin and end at the same objects. This is exactly what the airport puzzle needed. Source and target constrain a morphism, but do not exhaust it.

A modeller can then add path equations. If a direct route r is certified to have exactly the same observable behaviour as load ∘ screen, the equation r = load ∘ screen may be imposed. Algebraically, this forms a quotient of the free path category by the chosen equations. Operationally, it licenses substitution: any longer route containing r may use the composite instead, and vice versa.

That licence is powerful enough to deserve suspicion. An equation imported from a process diagram may conceal timing, cost or provenance. A commuting diagram is therefore not a picture of things that “roughly lead to the same place”. It is a claim that specified composites are equal in the chosen category. The equality needs a witness, such as a proof, exhaustive finite check, contract test or accepted semantic rule.

World two: functions compute

In the category of sets, objects are sets and morphisms are functions. Composition is ordinary function composition, and identity morphisms are identity functions. Here two functions are equal when they return the same output for every input. Internal algorithms do not matter to this category. A lookup table and a formula can be the same morphism if they define the same function.

Keep the same underlying sets but change the morphisms, and a different category appears. Groups use homomorphisms that preserve multiplication and identity. Topological spaces use continuous maps that preserve neighbourhood structure. Vector spaces use linear maps. The adjective “structure-preserving” is not decorative. It states which features must survive movement. An arbitrary function between the carrier sets of two groups is a morphism in Set but may not be a group homomorphism. The categorical question is always relative to a declared context.

This relativity blocks a common philosophical overreach. Category theory can characterise an object through its relations inside a category, but it does not say that every internal description is unreal or dispensable. Change the allowable probes and transformations, and the relational profile changes. What looks like “the same object” in one category may split into several distinctions in another.

World three: a preorder forgets the route

A preorder is a reflexive, transitive relation. It becomes a category by taking its elements as objects and placing a morphism a → b whenever a ≤ b. There is at most one morphism between any pair. Reflexivity supplies identities; transitivity supplies composition. Such a category is called thin.

Suppose objects are evidence strengths: observed ≤ corroborated ≤ verified. Once the relation says observed evidence can be strengthened to verified evidence, the thin category does not retain which corroboration route was used. That information has been intentionally collapsed. This may be perfect for proving reachability and disastrous for auditing provenance.

The opposite compression also occurs. A monoid, such as strings under concatenation or non-negative integers under addition, can be viewed as a category with one object. Every monoid element becomes an endomorphism of that single object, and the monoid operation becomes composition. The example is a useful shock: a category with one object can still contain rich process structure. The number of objects is not a measure of categorical complexity.

Together, paths, functions, preorders and one-object categories dismantle the idea that category theory merely replaces nouns with arrows. It supplies a grammar for many kinds of arrows. The modeller must still decide whether an arrow means a journey, computation, proof, refinement, permission, physical process or something else.

A ladder of route equality

The examples support a practical distinction. Endpoint equality means two routes finish at states carrying the same selected value. Morphism equality means the category declares the complete transformations equal. Governed equality means the routes also preserve the authority, effects, evidence and recovery obligations relevant to the decision.

The third phrase is practitioner synthesis, not a standard category-theory term. Its purpose is to prevent a common systems error: importing function equality into a domain where side effects and permissions are decisive. Before equating two paths, state which downstream observations are allowed to distinguish them.

stateDiagram-v2
  [*] --> Claim
  state "The minimum formal machinery" as Claim
  state "Associativity is a regrouping<br/>guarantee" as Test
  state "The composition dividend" as Revision
  Claim --> Test: expose mechanism
  Test --> Decision: evidence survives
  Test --> Revision: rival survives
  Revision --> Claim: narrow or rebuild
  Decision --> [*]

From formal shape to operating instrument

A category is useful in engineering when it makes composition obligations explicit. Consider a consequential AI-assisted action. Intent, identity, world state, permitted context, model proposal, authority, typed action, evidence, verified outcome and recovery are different things. Treating them all as “context” or “memory” hides who may transform what.

A minimal governed route might use the following typed objects: an IntentRecord, a BoundedProposal, an AuthorisedAction, an EffectReceipt and a VerifiedOutcome. The model may propose a transformation from intent and permitted context to a bounded proposal. A deterministic authority kernel may transform that proposal into an authorised action or an abstention. A typed executor may turn an authorised action into an effect receipt. A separate readback may turn the receipt into a verified outcome.

The composite describes an end-to-end route. It does not imply that the model itself has authority. Authority belongs to the morphism that checks and grants permission, not to fluency at the preceding object. A direct arrow from proposal to effect is either absent or explicitly marked as a rejected path.

The composition audit

The article’s practical contribution is a seven-question audit for deciding whether a categorical model earns its abstraction. It begins with the transformations because object labels are often inherited from organisation charts rather than from causal structure.

The audit is deliberately ordered. Boundary comes before arrow because a transformation cannot be typed until relevant state is located. Closure comes before identity and associativity because there is no algebra to test if compatible steps lack composites. Path equality comes after the laws because equality concerns complete routes, not attractive visual symmetry. Intervention comes last because a model that cannot be stressed may be internally elegant and empirically empty.

For a small system, the output can be a composition table. Rows name the morphism executed second; columns name the morphism executed first; each compatible cell names the result. For a large system, the same obligations can live in typed interfaces, proof assistants, property-based tests or executable contracts. The representation changes. The causal questions do not.

Published applications show what this discipline can look like without settling the modelling choice for a new system. Spivak formalises data migration between database schemas, Spivak and Kent use categorical structure for ologs, and Spivak develops compositional models across scientific domains.⁶⁷⁸ These works establish reusable methods, not a licence to treat every workflow diagram as a category.

A positive audit does not prove that the selected category is the only or deepest description. It establishes that the specification is internally compositional for the observations it names. A negative audit is equally useful. It locates where the ordinary category abstraction is too thin, where the boundary must expand, or where a richer structure is required.

Several repairs are possible. Hidden mutable state can be moved into the objects. Partial operations can be represented with explicit failure objects or a structure designed for partiality. Nondeterministic proposals can be treated as data passed to deterministic validators, or modelled in categories whose morphisms are relations or stochastic kernels. Concurrent and open systems may require monoidal, double or enriched structures. The point is not to name the most advanced formalism. It is to let a failed law tell us what the simpler model omitted.

function validateCategory(spec) {
  const errors = [];
  const objects = new Set(spec.objects || []);
  const arrows = new Map((spec.morphisms || []).map(m => [m.name, m]));
  const key = (after, before) => `${after}∘${before}`;
  const composition = new Map(
    (spec.composition || []).map(c => [key(c.after, c.before), c.result])
  );

  for (const m of arrows.values()) {
    if (!objects.has(m.from) || !objects.has(m.to)) {
      errors.push(`Unknown endpoint on ${m.name}`);
    }
  }

  for (const object of objects) {
    const identityName = spec.identities?.[object];
    const identity = arrows.get(identityName);
    if (!identity || identity.from !== object || identity.to !== object) {
      errors.push(`Invalid identity for ${object}`);
    }
  }

  const composablePairs = [];
  for (const before of arrows.values()) {
    for (const after of arrows.values()) {
      if (before.to === after.from) composablePairs.push([after, before]);
    }
  }

  for (const [after, before] of composablePairs) {
    const resultName = composition.get(key(after.name, before.name));
    const result = arrows.get(resultName);
    if (!result) {
      errors.push(`Missing composite ${after.name}∘${before.name}`);
    } else if (result.from !== before.from || result.to !== after.to) {
      errors.push(`Wrong endpoints for ${after.name}∘${before.name}`);
    }
  }

  for (const f of arrows.values()) {
    const left = composition.get(key(spec.identities[f.to], f.name));
    const right = composition.get(key(f.name, spec.identities[f.from]));
    if (left !== f.name) errors.push(`Left identity fails for ${f.name}`);
    if (right !== f.name) errors.push(`Right identity fails for ${f.name}`);
  }

  for (const f of arrows.values()) {
    for (const g of arrows.values()) {
      for (const h of arrows.values()) {
        if (f.to !== g.from || g.to !== h.from) continue;
        const gf = composition.get(key(g.name, f.name));
        const hg = composition.get(key(h.name, g.name));
        const left = composition.get(key(h.name, gf));
        const right = composition.get(key(hg, f.name));
        if (left !== right) errors.push(
          `Associativity fails for ${h.name}, ${g.name}, ${f.name}: ${left} ≠ ${right}`
        );
      }
    }
  }

  return { valid: errors.length === 0, errors: [...new Set(errors)] };
}