¿Todas las operaciones asociativas son esencialmente composición de funciones?

Question

Es bien sabido que la composición de funciones es asociativa. ¿Es cierto lo contrario? ¿Es cualquier operación asociativa esencialmente expresable como composición de funciones? Si no es así, ¿cuál es un ejemplo interesante de una operación asociativa que no sea expresable como composición de funciones?

Answer 1

Siempre que $*$ es una operación asociativa en un conjunto $X$, cada una de las $x\in X$ da lugar a una función $$ f_x : X\to X : y \mapsto x * y $$ Y luego tenemos para todos los $x$$y$, $$ f_x \circ f_y = f_{x*y} $$

En otras palabras, $f_{(-)}$ es un semigroup homomorphism de$(X,{*})$$(X^X,{\circ})$.

Ahora, $f_{(-)}$ no es necesariamente inyectiva. Si $*$ tiene un elemento de identidad, sin embargo. Y si no hay ningún elemento de identidad para $*$, podemos añadir uno artificialmente antes de empezar.

Por lo tanto,

Cada semigroup (conjunto con una operación asociativa) es isomorfo a un semigroup donde la composición es función de la composición.

---

Todo lo anterior supone que $*$ es una operación en un conjunto. Si tenemos una operación asociativa en una clase adecuada (como, por ejemplo, el ordinal adición, o de la unión arbitraria de conjuntos), luego de la anterior construcción no funciona. Y ordinales en virtud de la adición no puede ser representado como endofunctions en un único conjunto en virtud de la composición -- no tiene suficientes funciones como para dar a cada ordinal de un representante, incluso antes de empezar a hablar acerca de la composición.

---

Del mismo modo, en la categoría de teoría (que estudia las operaciones donde el $a*b$ no está necesariamente definido para todos los $a$$b$, pero que aún asociativo "siempre tiene sentido"), cada categoría de pequeña es concretizable (que es isomorfo a una subcategoría de la categoría de conjuntos y funciones), por una extensión de la anterior construcción.

Answer 2

Supongamos que tenemos un conjunto $X$ y una operación binaria asociativa $*$ en él. Deje que $\bar X=X\cup\{\perp\}$ donde $\perp$ es un símbolo $\notin X$ . Sea $Y=\bar X^{\bar X}$ sea el conjunto de mapas de $\bar X$ a sí misma. Por supuesto $Y$ es un monoide bajo composición de funciones.

Tenemos un mapa $\Phi\colon X\to Y$ dado por $$\Phi(x)\colon z\mapsto\begin{cases}x&\text{if }z=\perp\\x*z&\text{otherwise}\end{cases} $$ Tenga en cuenta que $\Phi$ es inyectiva debido a la $\perp$ caso. Obsérvese que $$(\Phi(a)\circ\Phi(b))(z)=\begin{cases}\Phi(a)(b)=a*b&\text{if }z=\perp\\a*(b*z)&\text{otherwise}\end{cases} $$ Debido a la asociatividad de $*$ vemos que $$\Phi(a)\circ\Phi(b)=\Phi(a*b),$$ es decir, $\Phi$ es un homomorfismo monoide inyectivo de $X$ a $Y$ . En otras palabras, podemos identificar los elementos de $X$ con determinadas funciones de tal forma que $*$ se convierte en composición de funciones.

Answer 3

Tenga en cuenta que cualquier operación $\star :S\times S\to S$ es equivalente a una función $f: S\times S\to S$ definido por $a\star b=f(a, b)$ . Incluso podríamos denotar $f:=\star$ por lo que la diferencia entre $\star(a, b) $ y $a\star b$ se basa puramente en la notación (conocida como notación prefija o infija, respectivamente).

Para una operación asociativa dada $\star$ tenemos que $$a\star (b\star c) =(a\star b) \star c\iff f(a, f(b, c)) =f(f(a, b), c)$$

De este modo, cada operación binaria $\star: S\times S\to S$ ser asociativo puede considerarse similar a que la composición de funciones sea asociativa. Además, la operación de $S\times S\to S$ es importante para lo anterior. Si hay alguna forma de asociatividad que no dependa de esto, puede que obtengas otra respuesta.