Definición General de la Asociatividad para operaciones binarias

Question

Digamos que estamos hablando, además definidas en los números reales. Luego, por inducción definimos $\sum_{i=0}^{0}a_i=a_0$ $\sum_{i=0}^{n}a_i=\sum_{i=0}^{n-1}a_i+a_n$ $n> 1.\:$

Ahora, ¿cómo se puede definir general de la asociatividad? Sé que esto tiene algo que ver con el hecho de que $\sum_{i=0}^{n}=\sum_{i=0}^{k}+\sum_{i=k+1}^{n}$$0\leq k<n$, siendo la $\sum_{i=k}^{n}a_i=\sum_{i=0}^{n-k}a_{i+k}$, por definición. Pero la cosa es que esto no acaba de definir la noción de diferentes formas de organización de corchetes, como por ejemplo,$(a_0+(a_1+a_2))+((a_3+a_4)+(a_5+a_6))$.

Así que mi pregunta es ¿cómo definir formalmente este proceso de horquillado. Piense en el caso cuando alguien sólo te dicen para demostrar que el general de la asociatividad de los números reales. ¿Cómo definir esta propiedad para demostrarlo? es necesario tener uno?

Mira por ejemplo esta prueba, específicamente en el punto donde el profesor M. Zuker dice: "Vamos ahora a suponer que cualquier horquillado de $a_1, a_2,...,a_k$ es igual a la forma estándar para $1\leq k\leq n-1$ donde $n>3$". Pero, de nuevo mi pregunta: ¿cuál es la definición de horquillado? es realmente necesario tener una definición de horquillado o esta prueba funciona sea cual sea la definición de bracketing?

También he encontrado este artículo por William P. Wardlow - Una generalizada general asociativa de la ley - que contiene diferentes pruebas de este general de la asociatividad de la ley. La primera de ellas, la que él propone como su favorito, es realizado por Nathan Jacobson en su libro "lecciones de Álgebra Abstracta" Vol. 1 página 20. Busca en esta prueba hay un punto en donde dice "Consideremos ahora cualquier producto asociado con $(a_1, a_2,..., a_n)$...", que significa "cualquier horquillado asociados con...". Luego otra vez la misma pregunta.

Espero que entiendan mi punto. Si no, por favor, siéntete libre de preguntar cualquier cosa relacionada con mi pregunta.

Editar:

Para aclaraciones, vamos a decir que estamos hablando de la suma en los números reales. A continuación,

1.- $(...(((a_0+a_1)+a_2)+a_3)...+a_n)$ es una representación formal de la definición de recursividad, significando $\sum_{i=0}^{n}a_i$ tal como se definió anteriormente: $\sum_{i=0}^{0}a_i=a_0$$\sum_{i=0}^{n}a_i=\sum_{i=0}^{n-1}a_i+a_n$$n> 1$.

2.- ¿Cuál es la definición formal de $a_0+(a_1+(a_2+...+(a_{n-1}+a_n)...)$ ?

3.- ¿Cuál es la definición formal de algo como $(a_0+((a_1+a_2)+a_3))+(((a_4+a_5)+a_6)+....+(a_{n-1}+a_n))$?

Answer 1

Para poner la cuestión en una perspectiva más amplia, todo se viene abajo a una lamentable convención notacional.

Una operación binaria es sólo una función $f:X \times X \rightarrow X$ donde $X$ es un conjunto, EXCEPTO que tiene la peculiar convención de la escritura de la función con "la notación de infijo" como 1+2 en lugar de ordinario la notación de la función, como, por ejemplo, "añadir(1,2)".

"Bracketing" es el precio que tenemos que pagar por el uso de la notación de infijo, ya que sin paréntesis, expresiones como 12 / 6 / 2 son ambiguas $-$ ¿ que significa (12/6)/2, que es igual a 1, o 12/(6/2), que es igual a 4? Y como no nos gusta a molestarme en escribir tantos paréntesis todo el tiempo, podemos incluso ir a través de la dificultad de establecer las normas convencionales sobre el orden de las operaciones: Las reglas que dicen que 1+3*4 implícitamente significa que 1+(3*4) y 5 - 4 - 3 significa (5-4)-3. En la escuela primaria que tuvo que pagar el precio de aprender todas estas reglas adicionales.

Si todos hemos utilizado ordinaria de la notación de la función en su lugar, no tendríamos necesidad de horquillado o convenciones acerca de la prioridad: en Lugar de (9 - 15) / 3 acabamos de escribir $\operatorname{divide}( \operatorname{subtract}(9,15), 3)$. En lugar de un complejo "bracketing" como $$(a_0+(a_1+a_2))+((a_3+a_4)+(a_5+a_6)),$$ que acaba de escribir $$\operatorname{add}(\operatorname{add}(a_0,\operatorname{add}(a_1,a_2)),\operatorname{add}(\operatorname{add}(a_3,a_4),\operatorname{add}(a_5,a_6))).$$

You can treat this as the formal definition. (You can even create an algorithm to do this kind of conversion automatically; algorithms of this kind are well-known.) In fact, to take things a little further, the parentheses and commas aren't even needed. We could just write

/ - 9 15 3
+ + a0 + a1 a2 + + a3 a4 + a5 a6

for the two examples above. There is no ambiguity. (Make sure you see why.) This kind of notation, which requires no parentheses, is called "prefix" or "Polish" notation. Again, it's really just ordinary function notation except we recognized that we don't need to bother writing out all the parentheses and commas.

(There is also "postfix" or "reverse Polish" notation, where (9-15)/3 would be expressed as 9 15 - 3 /. For the purpose of algorithm computation, postfix notation is the much more natural choice. But we'll stick to prefix since it closely corresponds to familiar function notation.)

In the following examples, the first two constitute all the possible "bracketings" of a binary operation $f$ over $a_0,a_1,a_2$; the third is not legal:

f a0 f a1 a2
f f a0 a1 a2
f a0 a1 f a2

Again, the first is equivalent to $f(a_0, f(a_1,a_2))$ and the second is equivalent to $f(f(a_0,a_1),a_2)$. The third cannot be parsed. (Aside: In general, what's an easy way to tell whether an expression with f's and a's is legal? Read the list from left to right. As you read, keep track of how many f's and how many a's you've seen so far. The running count of a's should be greater than the running count of f's precisely when you reach the end of the list, and no sooner.)

It's now clear what "any possible bracketing" means: It's any way to intersperse $n$ copies of $f$ among $a_0, a_1, ..., a_n$ (while keeping $a_0, a_1, ..., a_n$ in the same order) to form a legal expression in prefix notation.

Parentheses are just a silly way of notating what function notation does just as well $-$ no, better $-$ at expressing.

---

We've shown that bracketing is just an awkward consequence of using infix notation. But infix notation isn't just a load of crap as I've made it seem like. There's more to it than that. In fact, infix notation is a terrific convention, in the following sense:

In prefix notation, if I want to write $A*B*C$, I have to choose between writing either "* A * B C" or "* * A B C". But if $*$ is an associative operation, then both ways are equal. In other words, the prefix notation is now forcing me to make a distinction between two orders of evaluation that I shouldn't have to distinguish between. Notation should not force me to make irrelevant distinctions. That's the advantage of writing $a*B*C$: it leaves unspecified whether I mean $(a*B)*C$ or $A*(B*C)$, which is a good thing because the distinction is irrelevant. Thus infix notation makes sense for $*$ y para muchas de nuestras operaciones diarias, que a menudo son asociativas.

Estás tratando de demostrar general de la asociatividad, que, como usted ha reconocido, requiere de una comprensión de lo que "bracketing". Pero horquillado es una reliquia de la notación de infijo, que a su vez es una notación intención de ocultar el horquillado para asociativa de operaciones! Es por eso que pensando en términos de la notación de prefijo es el camino a seguir aquí, donde (a priori) no estamos tratando con un general asociativa de la operación.

Answer 2

Aquí es una manera de definir formalmente el proceso de horquillado y una prueba de que la asociatividad implica general de la asociatividad.

Dada una gramática independiente del contexto $S\to\bullet,\,S\to(SS)$, que genera todas las frases con la coincidencia entre paréntesis en las expresiones de los operadores binarios: $$\bullet,(\bullet\bullet),(\bullet(\bullet\bullet)),\dots$$ Deje $P$ ser el conjunto de todas estas frases. A continuación, $P$ es un servicio gratuito de magma con la operación $(p,q)\mapsto(pq)\in P.$ Que $P$ es libre significa que $(p\hat p)=(q\hat q)\implies p=q \wedge \hat p=\hat q$.

Definir el grado de $p\in P$ $|p|=1$ si $p=\bullet$ $p=|p_1|+|p_2|$ si $p=(p_1 p_2)$. El grado de $p$ es el número de repeticiones de la señal $\bullet$$p$. Vamos $P_n=\{p\in P|\;\;|p|=n\}$, $n>0$. También definir $l_n\in P_n$ $\;l_1=\bullet\;$ $\;l_{n+1}=(l_{n}\bullet)\;$ $n>1$.

Dado un magma $(M,\cdot)$ y elementos $x_1,\dots,x_n\in M$. Si $\;p\in P_n$ $p$ puede ser aplicado a $x_1,\dots,x_n$ en la forma obvia, en vez de izquierda a derecha reemplace $\bullet$ con $x_k$, $k=1,\dots, n$. Esto puede ser escrito $p(x_1,\dots,x_n)\in M$.

La prueba de la general de la asociatividad a través de la inducción. Considere la declaración: $$S(n):\quad \forall x_1,\dots,x_n\in M\,\forall p,q\in P_n:p(x_1,\dots,x_n)=q(x_1,\dots,x_n)$$ Si $M$ es asociativa, a continuación, $S(3)$ es cierto que desde $P_3=\{(\bullet(\bullet\bullet)),((\bullet\bullet)\bullet)\}$. Ahora supongamos que $S(m)$ es cierto para todos los $m<n$. Para $p,q\in P_n$ hay $p^\prime,\hat p, \,q^\prime,\hat q\in P$ $i,j>0$ tal forma que: \begin{cases} p(x_1,\dots,x_n)=p^\prime(x_1,\dots,x_i)\cdot\hat p(x_{i+1},\dots,x_n) \\ q(x_1,\dots,x_n)=q^\prime(x_1,\dots,x_j)\cdot\hat q(x_{j+1},\dots,x_n) \end{casos} Si $i=j$, $p^\prime(x_1,\dots,x_i)=q^\prime(x_1,\dots,x_i)$ etc, debido a $i<n$. [En particular, $l_i(x_1,\dots,x_i)=p^\prime(x_1,\dots,x_i)$]. Supongamos $i>j$, luego

$p(x_1,\dots,x_n)=l_i(x_1,\dots,x_i)\cdot l_{n-i}(x_{i+1},\dots,x_n)=$ $\Big(l_j(x_1,\dots,x_j)\cdot l_{i-j}(x_{j+1},\dots,x_i)\Big)\cdot l_{n-i}(x_{i+1},\dots,x_n)=$ $l_j(x_1,\dots,x_j)\cdot\Big(l_{i-j}(x_{j+1},\dots,x_i)\cdot l_{n-i}(x_{i+1},\dots,x_n)\Big)=$ $q^\prime(x_1,\dots,x_j)\cdot\Big(l_{i-j}(x_{j+1},\dots,x_i)\cdot l_{n-i}(x_{i+1},\dots,x_n)\Big)=$ $q^\prime(x_1,\dots,x_j)\cdot l_{n-j}(x_{j+1},\dots,x_n)=$ $q^\prime(x_1,\dots,x_j)\cdot \hat q(x_{j+1},\dots,x_n)=q(x_1,\dots,x_n)\quad$ QED.

Answer 3

El significado de "asociatividad de la operación binaria $\cdot$ en el conjunto de $A$ mantiene para $k$ (elementos)" es (como Wardlaw escribe) que "[Si $a_1, a_2, \dots,a_k$ son elementos de $A$, entonces] cualquier horquillado de $a_1,a_2,\dots,a_k$ es igual a la forma estándar."

Cuando decimos que una operación binaria es asociativa (sin mencionar a "de $k$"), nos referimos a es asociativa para todos los enteros positivos $k$. Esto significa que podemos escribir $\prod\limits_{i=1}^n a_i$ y saber que (independientemente de qué tan grande es $n$ es) es bien definido, porque la forma en que evaluamos no importa.

La forma estándar en la definición es (o puede ser llevado a ser) Wardlaw la izquierda asociativa del producto, $$\left(\dots\left(\left(a_1\cdot a_2\right)\cdot a_3\right)\dots\cdot a_k\right),$$

que es el elemento de $A$ obtenido por la búsqueda de $a_1\cdot a_2$, multiplicando por $a_3$, y así sucesivamente, hasta un producto final con $a_k$.

Para la definición para que quede totalmente claro, también hay que saber qué se entiende por cualquier horquillado.

"Cualquier bracketing" significa el resultado de una determinada secuencia tomado de entre todas las posibles secuencias que puede ser utilizado para transformar $a_1,a_2,\dots,a_k$ en un elemento de $A$ $k-1$ aplicaciones de $\cdot$.

Bracketings se expresa generalmente con parenthesization. Ejemplo: Para $k=5$, este es uno de los bracketings que existen:

$$\left(\left(a_1\cdot a_2\right)\cdot \left(\left(a_3\cdot a_4\right)\cdot a_5\right)\right).$$

Este es el elemento de la $A$ obtenido por la aplicación de $\cdot\,$, según el parenthesization. (Que dos aplicaciones se realizan en la misma línea, el resultado no depende del orden en que dichas evaluaciones.)

$$ \begin{align} \left(\left(a_1\cdot a_2\right)\cdot \left(\left(a_3\cdot a_4\right)\cdot a_5\right)\right)&= \overbrace{(a_1\cdot a_2)}^{\mathrm{Let}\, v=a_1\cdot a_2} \cdot \left(\overbrace{(a_3\cdot a_4)}^{\mathrm{Let}\, w=a_3\cdot a_4}\cdot a_5\right)\\ &= v\cdot\overbrace{(w\cdot a_5)}^{\mathrm{Let}\, x=w\cdot a_5}\\ &=\overbrace{\left(v\cdot x\right)}^{\mathrm{Let}\, z=v\cdot x}\\ &=z. \end{align} $$

Por el camino, tan largo como una "forma estándar" para el horquillado $a_1,a_2,\dots,a_k$ está bien definido, su forma específica es irrelevante, ya que si todas las formas de horquillado $a_1,a_2,\dots,a_k$ son iguales a la misma una de las posibles bracketings, la asociatividad se mantiene.

¿Eso ayuda?