# Why associativity $h \circ (g \circ f) = (h \circ g) \circ f$ is required in composition?

An introduction into category theory says that

A category is a quadruple $A = (O, \mathrm{hom}, \mathrm{id}, \circ)$ consisting of blah-blah and is subject to the following conditions: (a) composition is associative: $$h \circ (g \circ f) = (h \circ g) \circ f,$$ ...

What is the point of this requirement? If I get the parenthesis right, $(h \circ g)$ says that we first submit some $x$ to the rightmost $g$. This function will convert $x$ to some $y$, which will then be submitted to function $h$. It automatically follows that parenthesis play no role: the computation propagating from right to left as if there are no parenthesis. They are transparent by default. Why to stipulate the thing, which is inevitable?

• There is no "x". Morphisms don't have to be maps. – darij grinberg Jul 3 '15 at 23:13
• In category theory, morphisms are just arrows, they're not functions. – Michael Burr Jul 3 '15 at 23:14
• @SimonS I wonder how is it possible that it does not hold. – Val Jul 3 '15 at 23:14
• The requirement of associativity is "redundant" if we're dealing with a concrete category. However, not all categories are concrete. – Omnomnomnom Jul 3 '15 at 23:25
• In categories where maps are functions on sets and composition is function composition, then, yes, it is redundant. Not all categories are of this form. – Thomas Andrews Jul 3 '15 at 23:35

## 7 Answers

$\phantom{xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx}$

Counterexample 1: Counterexample 2:

Take the "category" with one object, one arrow for each octonion, and multiplication of octonions for composition. This (like Counterexample 1) satisfies all the axioms except associativity.

• Sorry, I'm probably being very obtuse, but . . . how is that a counterexample? Your diagram seems to show a case where h ◦ (g ◦ f*) is indeed the same as (hg) ◦ f, in that they are both arrows to and from the same places. What am I missing? – ruakh Jul 4 '15 at 6:37
• @ruakh: The fact that $(hg)f$ and $h(gf)$ are drawn in the diagram as different arrows means they are not the same, regardless of their having the same domain and codomain. Do you agree that I can make a category having four maps total, that would be represented diagrammatically as $$\Large \mathrm{id}_x\circlearrowright \bullet\stackrel{\overset{f}{\longrightarrow}} {\underset{g}{\longrightarrow}}\bullet \circlearrowright\mathrm{id}_y$$ – Zev Chonoles Jul 4 '15 at 7:18
• What "prevents" $f$ and $g$ from being the same is my decision to draw them as different arrows and give them different names. (For that matter, that's what makes the objects $x$ and $y$ distinguishable, too.) – Zev Chonoles Jul 4 '15 at 7:18
• Ruakh: in the category of sets, the identity map and the squaring map are both arrows from the natural numbers to the natural numbers. Does it follow that they are the same arrow? – WillO Jul 4 '15 at 13:01
• @Ruakh: Or for that matter: Interstate 95 and US Route 1 both start in Maine and end in Florida. Does it follow that they are the same road? – WillO Jul 4 '15 at 14:42

As the comments state, morphisms do not act on elements; they are abstract arrows with abstract composition rules. If you don't require associativity, you could have scary one-object categories modelled on algebraic structures such as loops or even magmada (with identity), which makes things much harder to deal with, as dropping associativity makes arbitrary composition difficult (once again stated in the comments).

• The whole point of category theory is to study sets-with-structure (topological spaces, groups, schemes, etc.) without ever referring to elements. Therefore, within category theory, there is no requirement that morphisms are functions. This leads to possible non-associativity of composition, which we want to avoid. Thus it is assumed as a category axiom. – Arthur Jul 3 '15 at 23:22
• @Arthur Especially useful when it's not even clear what an element should be! Looking at you, groupoids. – Harrison Smith Jul 3 '15 at 23:24
• When you say "magmada"... is that the accepted plural form of magma? I ask for two reasons: 1) I've never heard it used; 2) It sounds awesome. – Jonathan Hebert Jul 4 '15 at 1:05
• @JonathanHebert I imagine the accepted plural is 'magmas', but a professor once jokingly remarked that the greek language plural would actually be 'magmada', like the plural of 'dolma' is 'dolmada', and I started using it for exactly your second reason: it sounds so cool! – Harrison Smith Jul 4 '15 at 1:07
• I think you're blending two different endings. Dolma has a plural form dolmades, not *dolmada; but various other nouns in -ma have plural forms in -mata (schemata, stigmata, stomata, etc.), which is probably what you're thinking of. Fortunately, if you're American, magmata sounds the same as magmada anyway. :-) [CC @JonathanHebert] – ruakh Jul 4 '15 at 6:34

Consider the "category" which has four objects $x_1$, $x_2$, $x_3$, $x_4$, in which

• $\hom(x_i,x_i)$ has exactly one element for each $i\in\{1,2,3,4\}$, the identity of $x_i$;

• $\hom(x_i,x_j)$ is empty if $i>j$;

• $\hom(x_1,x_2)=\{\alpha\}$, $\hom(x_2,x_3)=\{\beta\}$, $\hom(x_3,x_4)=\{\gamma\}$, $\hom(x_1,x_3)=\{\delta\}$, $\hom(x_2,x_4)=\{\eta\}$ and $\hom(x_1,x_4)=\{\xi,\zeta\}$;

• composition is defined so that the identites act as identities, $\beta\circ\alpha=\delta$, $\gamma\circ\beta=\eta$, $\eta\circ\alpha=\xi$ and $\gamma\circ\delta=\zeta$.

You can easily check that composition in this "category" is not associative.

The point of an abstraction is to drop unneeded properties of a particular case to be able to reason at an higher level thus inferring new rules for a wider universe.

While it's true that if you think to "elements" as mappings $X \rightarrow Y$ and to "composition" as applying functions one after another then associativity is obvious. But this is exactly the point... in this specific case we want to reason to elements $a$ and $b$ in abstract and to composition also in abstract.

What is found is that to be able to do interesting reasonings in this abstract space we need the associativity rule to hold... but we still want to reason about those elements as NOT being necessarily mappings.

This happens very frequently in math... for example when you study abelian groups you normally require + to be commutative. Now if + is number addition it's obviously commutative. But the point of study abelian groups is exactly to try to deduce all that you can considering a commutative operation that is NOT necessarily the addition of numbers.

One way to justify associativity is in terms of the consequences of having it or not having it. From the mathematician's point of view, only interested in generating theorems, that's what's important. But you can also ask the "prior" question, namely where do associative systems come from? Mathematics is a tool-box for modeling various kinds of real-world systems (apart from being a pure discipline in itself). In the real world, associativity arises spontaneously from sets of operations which map states in some sets of states. For example, real-number multiplication maps $\mathbb{R}$ to $\mathbb{R}$.

You will find that all associative operations can be thought of in a natural way as maps from a state-space to itself. The meaning of associativity is then that each successive operation takes the output state of the previous operation and acts on that state to produce a new output state — independent of the history of previous operations. Thus associativity is a kind of history-free property for operations. If you look at non-associative operations like the cross product in $\mathbb{R}^3$, the operation is history-dependent. When you observe that $(i\times j)\times j\neq i\times(j\times j)$, that's because there is actually a hidden state in these operations. The closely related quaternions are in fact associative because they retain this hidden state.

To illustrate the issue, one might do the exercise of writing-out the proof that composition of maps among sets really is associative. I'm not pretending that this is rocket science, but the proof does illuminate that there's "something happening" to have associativity. Right, of course, we want parentheses to "not matter", but in a different universe, or if one makes unwise notational choices, associativity is lost, and notation no longer suggests (to our human reading-eyes) what is true.

In fact, while everyone is fairly accustomed to the non-associativity of the Lie bracket, the non-associativity of Jordan algebra products is less familiar, and more awkward, insofar as left multiplication by $a^{-1}$ is not generally the left inverse to multiplication by $a$, ... despite the notation not giving any clear warning. :)

My appraisal of "associativity" is that it is a thing that we like, for various substantial but not absolute reasons. If nothing else, many notational systems dysfunction without it, and, since those failures can be avoided, it's a "pragmantic good".

If I get the parenthesis right, (h ◦ g) says that we first submit some x to the rightmost g. This function will convert x to some y, which will then be submitted to func h.

All $(hg)$ says is "the product of $h$ and $g$": there is absolutely no prior reason to think that $(hg)(x)$ and $h(g(x))$ should have anything to do with each other.

In fact, this even comes up in ordinary sets-and-functions contexts: e.g. if a group $G$ has a right action on a set $X$, then if we identify group elements with the corresponding function $X \to X$, we have $(hg)(x) = g(h(x))$. (of course, we usually work around this by introducing new notation that doesn't have this problem)

In order for the product of arrows to $(hg)(x) = h(g(x))$, you need to introduce a new axiom to force it so, and said axiom is exactly the associativity axiom you cite, given a suitable notion of what "$x$" actually means here. (e.g. "generalized element")