Cuan Fuerte es la Asociatividad?

Question

Un amigo mío es el uso de un montón de álgebra que no es asociativa para una Química avanzada del proyecto. Estábamos discutiendo recientemente y me pareció bastante divertido cómo a menudo dijo cosas como "soportes existen en la realidad" y "la asociatividad es muy subestimado".

Ella tiene razón, por supuesto. Estoy sorprendido por lo que hay ahí fuera. Eche un vistazo a esta otra pregunta sobre la asociatividad en el magma , por ejemplo. Tengo curiosidad.

Así que cuan fuerte es la asociatividad? Lo sorprendente (contador)ejemplos hay de la fuerza de la suposición de que una operación binaria es asociativa?

Pensamientos.

Esto no es particularmente especial para la asociatividad, pero (a quién le importa? y un poco de reformulación y énfasis puede ir una manera larga.

Deje $(S, \cdot)$ ser un semigoup. Luego por la asociatividad sabemos que para cada uno de los triples $a, b, c\in S$, tenemos algunas $d, e\in S$ $\color{red}{a\cdot b=d}$ $\color{blue}{b\cdot c=e}$ (por el hecho de que $\cdot$ es una operación binaria) y $$\color{red}{\underbrace{(a\cdot b)}_{d}}\cdot c=\color{red}{d}\cdot c=a\cdot \color{blue}{e}=a\cdot\color{blue}{\overbrace{(b\cdot c)}^{e}}.$$

Por otra parte, si $\lvert S\rvert=5$, para comprobar que $S$ es de hecho un semigroup, debemos considerar la $\underline{5^3=125}$ triples.

Para citar MJD en esta respuesta:

Si nada más, la existencia de la Luz del algoritmo parece descartar la posibilidad de que alguien sabe una manera fácil de [ver si el magma es un semigroup] con sólo mirar el original de la tabla de Cayley.

Demostrando la asociatividad de la palabra de reducción en el estándar de la construcción de la libre grupo a través de un conjunto es muy intensivos en mano de obra y tedioso.

Answer 1

Particularmente notoriuos ejemplo de no-asociativo de las operaciones binarias son la adición y la multiplicación de números - cuando se hace en un ordenador usando aritmética de punto flotante. Es decir, los resultados de x = a+(b+c); y x=(a+b)+c; pueden ser muy diferentes. Uno tiene que ser cuidadoso en la programación de ganancia para evitar excesivo de errores de redondeo en tales situaciones.

Answer 2

Para todos los asociativa operaciones binarias en un conjunto, no es una representación fiel como un sub-semigroup de la semigroup $(X^X,\circ)$ algunas $X$.

Esa es la naturaleza de la asociatividad, en algún nivel - es función de la composición.

Esto pone es en el ámbito de la categoría de teoría, también. Sería, probablemente, no es muy útil para hacer la categoría de teoría, sin la asociatividad de la composición.

El más básico de los lugares en que he visto no la asociatividad es en $\lambda$-cálculo y/o lógica combinatoria, donde $ab$ representa la aplicación de la $a$$b$.

Si usted mira en el cálculo lambda, usted puede pensar en él como $a\star b=\phi_a(b)$. Efectivamente, eso es cierto para todas las operaciones binarias, por supuesto - que podemos definir $\phi_a(b)=a\star b$. Para asociativo de los operadores, sin embargo, tenemos la característica hermosa $\phi_a\circ \phi_b = \phi_{a\star b}$.

Answer 3

La asociatividad de una operación binaria nos permite representar con asignaciones

El estudio de las transformaciones de un conjunto $X$ dentro de sí mismo (podemos escribir $\mathrm{Hom}(X,X)$) es algo muy natural para hacer: ¿cómo puede $X$ arreglarse? Su operación binaria (función de la composición) es asociativa por la naturaleza.

En teoría de grupos, esto lleva a la del teorema de Cayley de que cada grupo $G$ es un subgrupo de $\mathrm{Sym}(G)\subset \mathrm{Hom}(G,G)$.

Pero después de pensarlo brevemente, se puede ver que más o menos la misma línea de pensamiento se aplica a cualquier semigroup $S$ que actúa sobre sí mismo a través de una operación binaria. La única salvedad es que se necesita un estado para garantizar la $as=bs$ todos los $s\in S$ implica que el$a=b$, de modo que el mapa es inyectiva.

Si $S$ es un monoid, o si $S$ es cancellative, entonces podemos obtener esta condición de forma gratuita, y $S$ puede ser inyectado en la $\mathrm{Hom}(S,S)$ utilizando el mismo esquema del teorema de Cayley.

---

(En este bloque se añadió más tarde:) Como se señaló en los comentarios, ahora parece dolorosamente obvio puede contiguos a una identidad para hacer cualquier semigroup en un monoid y, a continuación, representan la semigroup como un conjunto de endomorphisms de la monoid, por lo que todos semigroups están cubiertos también. Así, la asociatividad resulta que caracterizan las operaciones binarias que pueden ser representados de esta forma y con aquellos que no pueden.

---

El mismo no puede decirse para una operación en un conjunto de $X$ que no es asociativa. No hay manera de encontrar una isomorfo copia de la misma en $\mathrm{Hom}(Y,Y)$ para cualquier conjunto $Y$ a todos.

Nonassociativity significa que la operación va a ser demasiado patológico por este buen tipo de representación.

Tengo la sospecha de que uno podría ser capaz de enmarcar esto en términos de representable functors, pero después de pensar un rato (siendo el sillón categoría teórico que soy yo) yo no podía decidir si la conexión era real.

Answer 4

Uno de los lugares más importantes donde no la asociatividad juega un papel importante en los cálculos. Una gran cantidad de útiles algoritmos se basan en el hecho de la complejidad computacional de las evaluaciones no es asociativa. Por ejemplo, considere la posibilidad de un rango de $1$ matriz-vector producto. Deje que la matriz $A = uv^T$ y el vector ser $x$. Deje $u,v,x \in \mathbb{R}^{n\times 1}$. Para evaluar $b=Ax$, hay dos maneras.

1. Evaluar $A=uv^T$. El coste computacional es $\mathcal{O}(n^2)$. Ahora evaluar $b=Ax$ y el coste computacional es $\mathcal{O}(n^2)$.
2. Evaluar $a=v^Tx$. El coste computacional es $\mathcal{O}(n)$. Ahora evaluar $b=u \cdot a$ y el coste computacional asociado es $\mathcal{O}(n^2)$.

Answer 5

Si una operación binaria no es asociativa, perdemos la conmutatividad de los poderes de $a$. Que es que no podemos decir por ejemplo que $a^2 a=a a^2$. Lo que significa, por ejemplo, que no sabemos el significado de algo como $a^3$, sin adicional de la convención.