Associativity of arrow composition counter example?

Question

I'm trying to achieve a working understanding of category theory. One of the problems I'm having is that many of the concepts seem too straight-forward or obvious so it's hard to see why they're meaningful. For example, the associativity law for arrow composition. I'm having trouble imagining a situation in which it wouldn't be true. Does anyone have an example of this?

Answer 1

Take any set with a non-associative binary operation which has an identity element (examples). This corresponds to a "non-associative" category with one object.

Here is a nice way of formulating associativity: Let $C$ be a "category" where we don't require associativity. For each object $X$ we define $\hom(X,-) : C \to \mathsf{Set}$ by $Y \mapsto \hom(X,Y)$ on objects and $f \mapsto (g \mapsto f \circ g)$ on morphisms. Then, $\hom(X,-)$ is a functor for all $X$ iff the composition law of $C$ is associative.

The one-object version of this is: Let $X$ be a set with a binary operation $*$. Then this operation is associative iff $(X,*) \to (\mathrm{End}(X),\circ)$, $x \mapsto (y \mapsto y * x)$ is multiplicative.

Answer 2

It is easy to cook up a simple example. For example, suppose that we want to define a category with objects $w$, $x$, $y$ and $z$ and morphisms

• $a : w \to x$,
• $b : w \to y$,
• $c,c' : w \rightrightarrows z$,
• $d : x \to y$,
• $e,e' : x \rightrightarrows z$,
• $f : y \to z$,

plus the identity morphisms. Consider a composition law partially defined as follows:

• $d \circ a = b$,
• $f \circ d = e$,
• $f \circ b = c'$,
• $e \circ a = c$.

Then $f \circ (d \circ a) = f \circ b = c'$ while $(f \circ d) \circ a = e \circ a = c$. Hence one does not have associativity for any composition law completing the partially defined one above.

Of course, if you are wondering why this axiom is included in the definition of category, you may simply try to prove any basic category facts without it, and see what happens...

In most categories you will meet in practice, the morphisms will be coming from maps of underlying sets (e.g. abelian groups, topological spaces), so associativity will be automatic. Exceptions are things like categories of correspondences/spans or cobordism categories.