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

Question

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?

Answer 1

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.

Answer 2

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).

Answer 3

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".

Answer 4

$\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.

Answer 5

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")

Answer 6

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.

Answer 7

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.