Are all associative operations essentially function composition?

It is well known that function composition is associative. Is the converse true? Is any associative operation essentially expressible as function composition? If not, what's an interesting example of an associative operation that is not expressible as function composition?

Solution 1:

Whenever $*$ is an associative operation on a set $X$, each $x\in X$ gives rise to a function $$ f_x : X\to X : y \mapsto x * y $$ And we then have for all $x$ and $y$, $$ f_x \circ f_y = f_{x*y} $$

In other words, $f_{(-)}$ is a semigroup homomorphism from $(X,{*})$ to $(X^X,{\circ})$.

Now, $f_{(-)}$ is not necessarily injective. It will be if $*$ has an identity element, however. And if there is no identity element for $*$, we can of course add one artificially before we start.

Thus,

Every semigroup (set with an associative operation) is isomorphic to a semigroup where the composition is function composition.

All of the above assumes that $*$ is an operation on a set. If we have an associative operation on a proper class (such as, for example, ordinal addition, or union of arbitrary sets), then the above construction doesn't work. And ordinals under addition cannot be represented as endofunctions on a single set under composition -- no set has enough functions on it to give each ordinal a representative, even before we start speaking about composition.

Similarly, in category theory (which studies operations where $a*b$ isn't necessarily defined for all $a$ and $b$, but which are still associative "whenever it makes sense"), every small category is concretizable (that is, isomorphic to a subcategory of the category of sets and functions), by an extension of the above construction.

Solution 2:

Assume we have a set $X$ and an associative binary operation $*$ on it. Let $\bar X=X\cup\{\perp\}$ where $\perp$ is a symbol $\notin X$. Let $Y=\bar X^{\bar X}$ be the set of maps from $\bar X$ to itself. Of course $Y$ is a monoid under function composition.

We have a map $\Phi\colon X\to Y$, given by $$\Phi(x)\colon z\mapsto\begin{cases}x&\text{if }z=\perp\\x*z&\text{otherwise}\end{cases} $$ Note that $\Phi$ is injective because of the $\perp$ case. Note that $$(\Phi(a)\circ\Phi(b))(z)=\begin{cases}\Phi(a)(b)=a*b&\text{if }z=\perp\\a*(b*z)&\text{otherwise}\end{cases} $$ Because of the associativity of $*$, we see that $$\Phi(a)\circ\Phi(b)=\Phi(a*b),$$ i.e., $\Phi$ is an injective monoid homomorphism from $X$ to $Y$. In other words, we can identify the elements of $X$ with certain functions in such a way that $*$ becomes function composition.

Solution 3:

Note that any operation $\star :S\times S\to S$ is equivalent to a function $f: S\times S\to S$ defined by $a\star b=f(a, b)$. We could even denote $f:=\star$, so the difference between $\star(a, b) $ and $a\star b$ is purely notation based (known as prefix vs infix notation respectively).

For a given associative operation $\star$, we have that $$a\star (b\star c) =(a\star b) \star c\iff f(a, f(b, c)) =f(f(a, b), c)$$

In this way, each binary operation $\star: S\times S\to S$ being associative can be thought of being similar to function composition being associative. Also, the operation being from $S\times S\to S$ is important to the above. If there's some form of associativity that doesn't depend on this, you may get another answer.