Siempre he oído este razonamiento, y tiene un sentido evidente, pero ¿cómo se demuestra realmente para un producto arbitrario? ¿Sería algo así?
$$(a(b(cd)))e=((ab)(cd))e=(((ab)c)d)e=abcde?$$
¿Dices que la agrupación de los paréntesis corresponde ahora a multiplicar directamente? Gracias.
Se puede demostrar por inducción sobre el número de factores que todos esos productos son iguales. Demostramos que si se tiene $a_1,\ldots,a_n$ entonces cualquier forma de colocar el paréntesis dará el mismo resultado que $a_1(a_2(\cdots(a_{n-1}a_n)\cdots))$ .
Si el número de factores es $1$ o $2$ El resultado es inmediato. Si el número de factores es $3$ , entonces se deduce precisamente por asociatividad: $(a_1a_2)a_3 = a_1(a_2a_3)$ .
Supongamos que el resultado es válido para cualquier $k$ , $1\leq k\lt n$ y tienes algún producto de $n$ elementos $a_1,\ldots,a_n$ en orden, con paréntesis colocados de alguna manera arbitraria (pero válida). Entonces existe $k$ , $1\leq k\lt n$ , tal que el producto es de la forma $$w_1(a_1,\ldots,a_k)\cdot w_2(a_{k+1},\ldots,a_n)$$ donde $w_1(a_1,\ldots,a_k)$ es sólo una expresión que implica el producto de $a_1,\ldots,a_k$ con paréntesis colocados de alguna manera, y de manera similar con $w_2$ . (Sólo estamos viendo el "último" producto a realizar; por ejemplo, si tiene $((a_1a_2)a_3)(a_4a_5)$ Tendríamos $k=3$ , $w_1(a_1,a_2,a_3) = (a_1a_2)a_3$ y $w_2(a_4,a_5) = a_4a_5$ si usted tiene $a_1((a_2a_3)(a_4a_5))$ entonces $k=1$ , $w_1(a_1) = a_1$ y $w_2(a_2,a_3,a_4,a_5) = (a_2a_3)(a_4a_5)$ etc.).
Por inducción podemos escribir $$w_1(a_1,\ldots,a_k) = a_1(a_2(\cdots(a_{k-1}a_k)\cdots))$$ así que \begin{align*} w_1(a_1,\ldots,a_k)w_2(a_{k+1},\ldots,a_n) &= \Bigl(a_1\bigl(a_2(\cdots(a_{k-1}a_k)\cdots)\Bigr)\cdot w_2(a_{k+1},\ldots,a_n)\\\ &= a_1\cdot\Bigl(a_2(\cdots(a_{k-1}a_k)\cdots)w_2(a_{k+1},\ldots,a_n)\Bigr) \\\ &= a_1\cdot\Bigl( a_2(a_3(\cdots(a_{n-1}a_n)\cdots)\Bigr) \end{align*} donde la última igualdad se desprende de la hipótesis de inducción aplicada a un producto con $n-1$ factores, y la igualdad inmediatamente anterior por simple asociatividad de tres factores, aplicada a $a_1$ , $a_2(\cdots(a_{k-1}a_k)\cdots)$ y $w_2(a_{k+1},\ldots,a_n)$ . ( Nota: Si $k=1$ entonces puede pasar directamente de la primera línea a la última sin tener que invocar la asociatividad; el argumento sigue siendo válido).
Así, cualquier expresión de un producto de $a_1,\ldots,a_n$ , en ese orden, con los paréntesis colocados de forma arbitraria pero válida, es igual a $$a_1(a_2(\cdots(a_{n-1}a_n)\cdots)),$$ Esto completa la inducción y la prueba.
Dado que todas las formas de asociar un producto de $n$ factores, $a_1,\ldots,a_n$ dan resultados que son iguales entre sí, podemos escribir libremente cualquier producto de este tipo simplemente como $a_1\cdots a_n$ para representar su valor común.
Sugerencia $ $ Es fácil: empujar iterativamente los ') hacia la derecha mediante la regla de reescritura $\rm\, (xy)z\ \to\ x(yz).\,$ Este proceso termina con el forma normal asociada a la derecha donde todos los ') están en el extremo derecho, es decir, $\rm\ a(b(c(d(\cdots))),\, $ escrito $\rm\ abc\cdots $ (sin ambigüedad - ya que cada paréntesis se reescribe a ella por debajo).
Prueba $ $ (boceto) $ $ por inducción fuerte en la longitud $\rm\:\ell(Z) = $ número de operandos (factores)
$\rm \ell(Z)\, =\, 1\!:\ \ \ Z = a\ $ está en forma normal $ $ (caso base).
$\rm \ell(Z)\, >\, 1\!:\ \ \ Z = XY\ $ donde $\rm\:\ell(X),\ell(Y)< \ell(Z)\,$ se divide en $2$ casos:
$\rm\ \ \color{#90f}{\ell(X)\! =\! 1}\!:\ \ \ XY = a\color{#c00}Y = a(\color{#c00}{b(c(\cdots))})\:\ $ por $\:\rm\color{#90f}{X= a},\,$ y $\rm\color{#c00}{induction}$ aplicado a $\rm\color{#c00} Y$
$\rm\ \ \ell(X)\! >\! 1\!:\ \ \ \color{#c00}XY = \underbrace{(\color{#c00}{a \bar X})Y = a(\color{#0a0}{\bar X Y})}_{\rm \color{darkorange}{associative}\ law} = a(\color{#0a0}{b(c(\cdots))})\ $ por $\rm\color{#c00}{induc}\color{#0a0}{tion}$ aplicado a $\rm \color{#c00}X,\, $ entonces $\rm\color{#0a0}{\bar XY}$
Sólo $\rm\color{darkorange}{associativity}$ $\rm\, (AB)C = A(BC)\,$ por lo que la prueba funciona para cualquier operación asociativa.
Eso de que "se pueden soltar los paréntesis" en realidad significa que "no importa cómo se pongan los paréntesis, el resultado será el mismo".
Para demostrar tal afirmación, lo que se suele hacer es elegir un forma específica de poner los paréntesis, y muestra que cualquier otra forma da el mismo resultado que la que hemos elegido. Esto se hace por inducción en el número de factores.
Algún alma emprendedora podría publicar una prueba completa...
Argumentamos por inducción sobre el número $n$ de factores, asumiendo, como podemos, $n\ge4$ .
Por hipótesis de inducción, sabemos que, para $k < n$ cualquier producto de los factores $b_1,\dots,b_k$ tomados en este orden pueden escribirse inequívocamente como $b_1\cdots b_k$ .
Entonces un producto de cualquier secuencia dada $a_1,\dots,a_n$ es necesariamente de la forma $$ c_k:=(a_1\cdots a_k)(a_{k+1}\cdots a_n) $$ para algunos $k=2,\dots,n-1$ y sólo tenemos que comprobar $$ c_p=c_q\quad\forall\quad1 < p < q < n, $$ lo que hacemos de la siguiente manera: $$ \begin{matrix} &(a_1\cdots a_p)&(a_{p+1}\cdots a_q& a_{q+1}\cdots a_n)\\ \\ =&(a_1\cdots a_p)&((a_{p+1}\cdots a_q)&(a_{q+1}\cdots a_n))\\ \\ =&((a_1\cdots a_p)&(a_{p+1}\cdots a_q))&(a_{q+1}\cdots a_n)\\ \\ =&(a_1\cdots a_p&a_{p+1}\cdots a_q)&(a_{q+1}\cdots a_n). \end{matrix} $$
He aquí una versión geométrica de una prueba:
En primer lugar, hay que tener en cuenta que las parentelas de un producto de longitud n están en biyección con las triangulaciones de los (n+1)-góneros convexos $A$ . Esto se ilustra en la imagen siguiente, copiada de la página 240 del libro "Discriminantes, Resultantes y Determinantes Multidimensionales" de Gelfand Kapranov y Zelvinski.
En palabras, pasar de las triangulaciones de $A$ a los parentescos de $x_1x_2\ldots x_n$ , etiquetar todas las aristas de $A$ en orden como $x_1, x_2, \ldots, x_n$ , dejando el último borde como "borde de salida". A continuación, se realiza una triangulación de $A$ da un paréntesis de manera inductiva: Tomemos el triángulo $T$ incidente en el borde de salida; entonces $A$ con $T$ eliminado es la unión de dos polígonos $A_l$ y $A_r$ (uno de los cuales podría ser degenerado, es decir, un segmento), cada uno de los cuales es incidente en un borde "no de salida" de $T$ . A continuación, asignemos a nuestras triangulaciones el producto de las paréntesis asignadas a $A_l$ y $A_r$ .
Se puede retroceder fácilmente de manera igualmente inductiva, pensando en un parentecimiento $p$ como un producto de dos subentrenamientos $p_l$ y $p_r$ y, en consecuencia, obtener la triangulación asociada a $p$ mediante la "inserción de un triángulo $T$ " en las triangulaciones de los polígonos más pequeños asociados a estos $p_l$ y $p_r$ .
Ahora que tenemos una interpretación geométrica de los paréntesis, podemos dar una interpretación geométrica de la aplicación simple de la ley de asociatividad. Esto se conoce como volteo - en una triangulación dada, se toman dos triángulos que comparten una arista, formando así un cuadrilátero, y se sustituye esta arista por la otra diagonal de este cuadrilátero.
Así, la pregunta es: ¿podemos conectar dos triangulaciones cualesquiera de un polígono convexo mediante una secuencia de "giros diagonales"? La respuesta es sí, y de nuevo se ilustra mejor con una imagen, esta vez robada de la página 7 del libro "Triangulaciones" de Jesús A. De Loera, Jörg Rambau y Francisco Santos.
En palabras, elige cualquier vértice $i$ y hacer la triangulación dibujando todas las diagonales desde ese vértice. Para conectar cualquier triangulación a esa "i-estándar", hacer volteos que aumenten el grado de $i$ Mientras no esté en la triangulación "i-estándar", existe un triángulo $T$ con vértice $i$ y la arista opuesta no es una arista de $A$ (sino una diagonal); completa $T$ a un guadrilátero, y voltear la diagonal.
Esto demuestra que "la gráfica de de las triangulaciones del n-gon" es conexo (estableciendo así lo que queremos).
¡QED!
De hecho, es mucho más cierto. El grafo de las volteretas no es más que la unión de las caras de 1 dimensión de un politopo convexo, todas cuyas caras corresponden a triangulaciones incompletas/paréntesis incompletos, correspondiendo la única cara abierta a una triangulación incompleta sin triángulos/paréntesis incompletos sin paréntesis. Lo que demostramos es simplemente que se puede llegar desde cualquier vértice de este politopo a cualquier vértice siguiendo algunas aristas. Esto es, por supuesto, cierto para cualquier politopo convexo (tomar el camino recto y llevarlo a caras de dimensión cada vez más baja, por ejemplo proyectando "radialmente" desde un punto de la cara que no está en el camino; esta es una versión fácil del teorema de aproximación celular en topología algebraica).
El politopo en cuestión se llama associaedro, o politopo de Stasheff, y su existencia se desprende de varias construcciones directas, en particular es construido por Gelfand-Kapranov-Zelevinsky como el politopo secundario de un n-gono convexo en el plano (esto se describe en el mismo libro de donde proviene la primera imagen).
En una nota relacionada y más ridícula, la existencia de un permutoedro (politopo secundario del prisma $I\times \Delta^n$ en el simplex $\Delta^n$ ) muestra que la ley de conmutación permite escribir productos de cualquier número de elementos en cualquier orden (esto equivale a mostrar que el grupo de permutación está generado por transposiciones).
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
