¿Qué significa intuitivamente la propiedad asociativa en todos los esquemas notacionales?

Question

Se pueden encontrar descripciones de la asociatividad como algo que intuitivamente significa que el orden de las operaciones realizadas no importa, por ejemplo la de Wikipedia . Sin embargo, si se escribe lo que significa la asociatividad en términos de una fórmula en notación prefija, es decir, que para alguna operación binaria X, XXxyz=XxXyz, o en notación sufija xyzXX=xyXzX, la descripción intuitiva de la asociatividad pierde sentido. Entonces, ¿qué significa intuitivamente la asociatividad en un esquema de prefijo o de sufijo? Supongo que se podría decir que, en la notación de prefijos y sufijos, la asociatividad significa que se puede empujar la segunda instancia de la operación tan adentro como se pueda, o tan afuera como se pueda, y seguir teniendo una expresión equivalente. Pero, esto no parece encajar con una descripción intuitiva de la asociatividad en una notación infija.

Entonces, ¿qué significa la asociatividad en todos los esquemas notacionales? ¿Podemos hablar con sentido de la asociatividad en todos los esquemas notacionales, o las descripciones intuitivas sólo funcionan a nivel local en un esquema notacional concreto?

Apéndice: No estoy muy seguro de si esto pertenece aquí o en el Intercambio de Filosofía. Me gustaría que se importara allí, si me parece más apropiado.

Answer 1

No estoy de acuerdo con la premisa implícita en la pregunta de que el significado de la asociatividad depende del esquema notacional utilizado para denotar las operaciones. La asociatividad significa que el orden de las operaciones no importa (o que la multiplicación por la izquierda y por la derecha se conmutan, como ha señalado Bill). Lo que pierde esta descripción cuando se utiliza la notación prefija o postfija no es el sentido sino la visibilidad. El significado de los números naturales como dispositivo de recuento universal no pierde sentido en japonés sólo porque utilice varias docenas de partículas de recuento para diferentes clases de cosas.

Si, por el contrario, la cuestión fuera cómo describir sintácticamente cómo se manifiesta la asociatividad en varios esquemas notacionales, yo diría que la respuesta es que en la notación infija los paréntesis se vuelven innecesarios, en la notación prefija puedes escribir las operaciones tan pronto como quieras (y no más tarde que sus operandos) y en la notación postfija puedes escribirlas tan tarde como quieras (y no antes que sus operandos). Mientras que en la notación infija no hay una forma "canónica" para una operación múltiple (es decir, no hay razón para preferir una de $x\circ(y\circ z)$ y $(x\circ y)\circ z$ sobre el otro), y la forma más clara de escribir uno es eliminando los paréntesis, en la notación prefija/postfija la forma canónica parecería ser tener todos los operadores al frente/final.

Answer 2

La naturaleza de la asociatividad puede ser mejor comprendida al darse cuenta de que un operador binario:

$$b:X\times X \rightarrow X$$

Tiene un adjunto natural (donde $X^X$ es el conjunto de funciones de $X$ a $X$ :)

$$b^*:X \rightarrow X^X$$

definido por: $b^*(x)(y)=b(x,y)$

Una operación binaria es entonces asociativa si y sólo si corresponde a la composición de funciones en $X^X$ . Es decir, existe un operador binario de composición natural:

$$\circ: X^X \times X^X \rightarrow X^X$$

Entonces $b$ es asociativo si y sólo si para todo $x,y\in X$ :

$$b^*(b(x,y)) = b^*(x) \circ b^*(y)$$

Así que, en ese sentido, la asociatividad se representa siempre como composición de funciones.

Comentario añadido mucho después:

Como ha señalado Joriki en los comentarios, hay otro adjunto, $^*b$ que se define como $^*b(x)(y)=b(y,x)$ .

En cierto sentido, pues, la notación de prefijo, $Kxy$ se puede considerar que representa $Kx=b^*(x)$ aplicado a $y$ . Y $xyK$ puede verse como la operación $^*b(y)$ a x. En ese sentido, la notación del prefijo representa el primer adjunto, $b^*$ el infijo representa el operador binario, $b$ y la notación del sufijo representa el segundo adjunto, $^*b$ .

Answer 3

Un punto de vista alternativo sobre la asociatividad es que no se trata en absoluto de operaciones binarias.

Una operación asociativa sobre un conjunto es, intuitivamente, una forma de agregar cualquier tupla finita de elementos del conjunto en un elemento del conjunto - formalmente, un familia de operaciones $\mu_n : X^n \to X$ para cada $n>0$ (o posiblemente $n \geq 0$ - más adelante) - de tal manera que cualquier forma de combinar estas operaciones sin permutación, supresión o duplicación, es la misma que la operación especificada de esa longitud.

Por ejemplo: dada una lista $(x,y,z,w)$ Podríamos tomar $\mu_4(x,y,z,w)$ directamente; o podríamos ver la operación compuesta $\mu_2(x,\mu_3(y,z,w))$ . (Aviso: no hay permutación, duplicación o supresión de los elementos $(x,y,z,w)$ .) La asociatividad generalizada dice que son iguales.

La ley de asociatividad clásica, $\mu_2(\mu_2(x,y),z) = \mu_2(x,\mu_2(y,z))$ se deduce claramente de esto (ya que ambos son iguales a $\mu_3(x,y,z)$ ; y resulta que dado $\mu_2$ Si se satisface esto, siempre se puede reconstruir el resto de las operaciones. Por lo tanto, se puede trabajar sólo con operaciones binarias y esta única ley. Sin embargo, intuitivamente, me parece útil pensar que las operaciones asociativas son realmente toda la familia de $n$ -operadores de tipo "amarillo", para todos los $n > 0$ . (Tomando $n \geq 0$ corresponde a asociativo y unital operaciones binarias).

En la práctica, por ejemplo, si quiero comprobar si alguna operación es asociativa, lo primero que haré será intentar escribir una fórmula para un $n$ -ario; si esto resulta natural, la operación será casi siempre asociativa.

Por ejemplo, el producto de convolución para funciones de un grupo finito en un anillo se define como $$ (f \ast g)(x) := \sum_{yz = x} f(y) g(z) $$ Calcular la asociatividad a mano lleva quizá tres líneas y cuarenta y cinco segundos, pero se puede ver inmediatamente, con sólo mirarlo, que se generaliza a una versión ternaria, $$ (f \ast g \ast h)(x) := \sum_{yzw = x} f(y) g(z) h(w) $$ (y a $n$ -versiones secundarias para otros $n$ ), y esto da una fuerte pista heurística de que será asociativo.

Este punto de vista se formaliza en la teoría de las operadas y es esencial para generalizar a nociones más sutiles como la de "hasta-homotopía-asociación".