Cómo formalizar "no importa cómo los lugares de los corchetes"

Question

Deje $X$ a un y $X\times X\to X: (a, b)\mapsto a\cdot b$ asociativa operación $X$. Ahora se puede demostrar por inducción que no importa cómo uno de los lugares de los paréntesis en un producto de $x_1\cdot x_2\cdot\text{ }\dots\text{ } \cdot x_n$, el producto siempre devuelve el mismo valor. Este resultado justifica la notación de un producto $x_1\cdot x_2\cdot\text{ }\dots\text{ } \cdot x_n$ sin ningún tipo de soportes. Pero ¿cómo se puede formalizar?

Answer 1

Una buena manera de formalizar el general asociativa de la ley es a través de los árboles binarios. Para nosotros, un árbol de operaciones será de un número finito de árbol, con un nodo raíz, donde cada nodo es una hoja (no hay sucesores) o tiene exactamente dos sucesores (a la izquierda sucesor y un derecho sucesor), y cada hoja está etiquetada con un elemento de $X$.

La idea es que cada hoja del árbol representa una entrada, y cada nodo hoja no es una instancia de la operación $*$ que se aplica a los valores asociados a la $*$-producto de la izquierda y la derecha sub-árboles de ese nodo. Así, por ejemplo, $(a*b)*c$ es representado por un árbol con una abertura en la raíz y, a continuación, el lado izquierdo se divide una vez más; y las hojas son etiquetados $a, b, c$, respectivamente.

Un vauation de un árbol de operaciones es un mapa de $m$ a partir de los nodos de a $X$, la satisfacción de $m(\sigma)$ es la etiqueta ya en $\sigma$ - si $\sigma$ es una hoja - y $m(\sigma)=m(S_{left}(\sigma))*m(S_{right}(\sigma)),$ donde $S_{left}$ $S_{right}$ son la izquierda y la derecha sucesores de $\sigma$ si $\sigma$ no es una hoja. Podemos probar por inducción que cada árbol $T$ de las operaciones tiene exactamente una valoración; llaman a esto "$v(T)$."

Tenga en cuenta que las hojas de un árbol de operaciones están ordenados de una manera natural: una hoja $\sigma$ es antes de otra hoja de $\tau$ si es "a la izquierda" de $\tau$, es decir, cuando se $\rho$ es el último nodo del árbol por encima de ambas $\sigma$ $\tau$ tenemos que $\sigma$ va a la izquierda de $\rho$ mientras $\tau$ va a la derecha. El general asociativa de la ley, entonces es:

Si $T_1, T_2$ son dos árboles de operaciones con la misma hoja de etiquetas que ocurren en el mismo de izquierda a derecha para, a continuación, $v(T_1)$ $v(T_2)$ asignar el mismo elemento de $X$ a la raíz de $T_1$$T_2$, respectivamente.

Answer 2

A cada arraigada plana árbol binario $\tau$ podemos asociar una operación $X^{\times n}\to X$ donde $n$ es el arity del árbol (es decir, el número de hojas): si $x_1,\ldots,x_n\in X$ $\tau(x_1,\ldots,x_n)$ se obtiene por poner $x_i$ a $i$th hoja del árbol, y luego "mover hacia abajo en dirección a la raíz" mediante la aplicación de la multiplicación en los vértices. Esto muestra que las planas de los árboles binarios son en bijective correspondencia con bracketings. A continuación, la declaración de que usted está buscando es:

Lema: Cualquiera de las dos planas de los árboles binarios de la misma arity inducir la misma operación.

Esto es fácil de probar por inducción.

Comentario: Estas ideas vienen naturalmente una vez que se familiarizan con las operad teoría.

Answer 3

Este es el llamado asociativa de la ley que dice precisamente: $$\forall x,y,z [(x*(y*z))=((x*y)*z))] $$

Que se extiende a la arbitraria finito productos puede entonces demostrado el uso de la inducción.

Algunos detalles más: va a demostrar que cada expresention es equivalente a la de uno con el paréntesis de la izquierda por ejemplo, a $(((x*y)*z)*w))$ (cada expresion utiliza cada variable sólo una vez). A continuación, puede definir la complejidad de la $C:\mathrm{EXP}\to\mathbb{N}$ de una expresión de forma recursiva como : $C(x)=0$, y para el compuesto expresiones $C(e*f)=C(e)+C(f)+\mathrm{length}(f)-1$ donde $e,f$ son expresiones y $\mathrm{length}(f)$ es un número de variables en $f$.

Ejemplos: $C(x*y)=C(x)+C(y)+1-1=0$,

$C((x*y)*z))=C(x*y)+C(z)+1-1=0$,

pero $C(x*(y*z))=C(x)+C(y*z)+2-1=1$,

y el uso de la inducción de la complejidad. Calcular que una aplicación de la asociatividad disminuye la complejidad.

Answer 4

Suponga que su operación es asociativa, es decir,$\forall a,b,c\in X$: $$a\cdot (b\cdot c) =(a\cdot b)\cdot c$$ Ahora, queremos demostrar que los soportes no importa para cualquier expresión general el uso de la inducción.

Comenzando con un producto de tres elementos, la afirmación es verdadera, debido a la propiedad asociativa. Ahora suponga que la afirmación es verdadera para algunos expresión que implique $n>3$ términos, que vamos a denotar por $x_n$. Cualquier expresión que implique $n+1$ términos, es de los formularios: $$x_{n+1}=a\cdot (x_n)\ \text{or}\ x_{n+1}=(a\cdot x_{n_1})\cdot x_{n_2}$$ Donde $n_1 + n_2 = n$, y queremos demostrar que estas dos formas son idénticas. Debido de nuevo a la propiedad asociativa, y la inducción de la hipótesis, tenemos que: $$(a\cdot x_{n_1})\cdot x_{n_2} = a\cdot(x_{n_1}\cdot x_{n_2}) = a \cdot (x_n)$$ Q. E. D