¿Hay que demostrar cómo funcionan los paréntesis en los axiomas de Peano?

Question

Una cosa que me ha molestado hasta ahora mientras aprendía sobre los axiomas de Peano es que el uso de paréntesis sale de la nada y automáticamente asumimos que son verdaderos en su funcionamiento.

Por ejemplo, la prueba de que $(a+b)+c = a+(b+c)$ . Dado un caso base $(a+b)+0 = a+b = a+(b+0)$ tenemos para un paso inductivo:

$(a+b)+S(c) = S((a+b)+c) = S(a+(b+c)) = a + S(b+c) = a + (b+S(c))$

Pero, por alguna razón, esto me molesta porque no se ha explicado en absoluto cómo deben tratarse los paréntesis en primer lugar. ¿Necesitamos un axioma o definición adicional para esto? ¿Se menciona en alguna parte? ¿O simplemente los damos por sentado?

Answer 1

En teoría formal del lenguaje (sobre todo, los lenguajes libres de contexto), existe la noción de árbol sintáctico abstracto . Una buena parte de la teoría del lenguaje formal consiste en averiguar cómo convertir cadenas de símbolos planas y lineales en esta representación más estructurada. Esta representación más estructurada, en forma de árbol, es generalmente en lo que pensamos cuando pensamos en fórmulas o términos bien formados. Por ejemplo, cuando pensamos en hacer una inducción sobre todas las fórmulas, se trata de una inducción estructural sobre árboles sintácticos abstractos, no sobre cadenas.

Para los lenguajes relativamente sencillos y regulares que se suelen utilizar para las lógicas formales simples, es relativamente fácil describir la sintaxis con un gramática libre de contexto y/o describir un algoritmo que tome una cadena y analice el árbol de sintaxis abstracta si es posible. Para algo como $S(a+(b+c))$ esto produciría un árbol como:

    S
    |
    +
   / \
  a   +
     / \
    b   c

Por supuesto, si quisiera representar este árbol en texto lineal, es decir, quisiera serializarlo, tendría que elegir alguna representación textual, y en este caso la expresión original, S(a+(b+c)) sería una posible representación. Otra sería la notación polaca, S+a+bc . Otra sería la de las expresiones S, (S (+ a (+ b c))) . Otra sería algo parecido a la notación estándar pero evitando los operadores infijos, S(+(a,+(b,c))) .

En última instancia, lo que yo recomendaría encarecidamente es que se piense en los árboles sintácticos abstractos como algo primario y en los trozos de texto que se ven en los libros como meras serializaciones de estos árboles forzadas por las limitaciones prácticas. La necesidad de preocuparnos por el análisis sintáctico en la lógica es, en gran medida, un artefacto del medio que utilizamos. Desde la perspectiva de los árboles de sintaxis abstracta, la asociatividad se ve así:

    +          +
   / \        / \
  +   c  =   a   +
 / \            / \
a   b          b   c

Los humanos son bastante buenos analizando idiomas, así que en general no es una barrera para la comprensión. Obviamente, no es necesario entender las gramáticas libres de contexto para leer con confianza y correctamente la mayoría de las notaciones formales. Si te interesa el análisis sintáctico, no dudes en leerlo, pero el análisis sintáctico no es demasiado importante para la lógica, así que yo no me obsesionaría con él. (Sin embargo, los lenguajes formales y la lógica formal tienen una buena superposición de conceptos y técnicas). Desde una perspectiva filosófica, preocuparse por el análisis sintáctico de los lenguajes formales (una impresión que dan algunos libros) mientras se leen oraciones en un lenguaje natural mucho más complicado es un poco tonto.

Answer 2

Versión corta: tienes razón, hay un problema serio aquí, y se reduce a las reglas exactas que usamos para formar los términos. Lo has planteado en términos de trivialización ("¿no reduce esto la prueba de la asociatividad a la reflexividad de " $=$ "), pero es un problema más serio que eso, incluso: en última instancia nos permitirá demostrar que cada La operación binaria (infija) es asociativa, lo que es claramente una locura $^*$ (ver mis comentarios debajo del OP). Así que hay que resolver algo aquí.

En última instancia, queremos no considerar expresiones como " $x+y+z$ " para ser términos en absoluto (lo que tiene sentido, porque hasta que no hayamos demostrado que $+$ es asociativo no hay razón para esperar que " $x+y+z$ " para referirse inequívocamente a cualquier cosa).

Así que no es que " $(a+b)+c=a+b+c$ " es falso sino que es gramaticalmente incorrecto .

Desgraciadamente, algunas presentaciones pasan por alto este punto, lo que de hecho provoca un grave problema. Creo que el enfoque más sencillo es prohibir por completo la notación infija (de modo que " $x+y$ "es un término del "metalenguaje", pero no del lenguaje formal que utilizamos). Esto tiene el inconveniente de ser difícil de leer, pero rápidamente llegarás al punto en que te sentirás cómodo utilizando la notación infija informal como abreviatura de las expresiones formales en cuestión.

---

La sintaxis que presento a continuación es sólo una opción entre muchas otras:

Dada una lengua $L$ compuesto por símbolos constantes, símbolos de función (con arias) y símbolos de relación (con arias), definimos la clase de $L$ -términos como sigue:

• Cada símbolo constante en $L$ es un término. (Tenga en cuenta que puede no haber ninguno de ellos).

• Cada variable es un término. (Aquí las variables existen independientemente de la lengua $L$ En otras palabras, las variables son "símbolos lógicos" como $\forall$ , $\wedge$ , $($ y $=$ .)

• Esta es la clave : si $t_1, ..., t_n$ son términos y $f$ es un $n$ -símbolo de la función primaria en $L$ entonces $f(t_1, ..., t_n)$ es un término.

• Ninguna cadena de símbolos es un término a no ser que lo exijan las reglas anteriores.

Tenga en cuenta que esta sintaxis no permite símbolos infijos La expresión " $x+y$ " es gramaticalmente incorrecto, y debería escribirse " $+(x, y)$ " en su lugar. Tenga en cuenta también que " $+$ "sólo puede recibir tantas entradas como su aridad: así $+(x, y, z)$ no es un término, ya que $+$ es $2$ -ary. Ahora la asociatividad de una operación binaria $*$ se expresa como $$\forall x, y, z(*(x, *(y, z))=*(*(x, y), z)),$$ y la cuestión que planteas no surge aquí en absoluto, ya que los "términos ambiguos" pertinentes ni siquiera son expresiones bien formadas en nuestra sintaxis.

_Por cierto, ten en cuenta que la notación que he descrito anteriormente es redundante: podríamos escribir " $ft_1...t_n$ " y esto sería perfectamente inequívoco . Pero, en mi opinión, esto lleva a una pérdida significativa de "legibilidad humana"; ¿por qué hacer que tu sintaxis sea mínima si es más difícil de leer? Ya me arrancarás las comas y paréntesis innecesarios de mis frías y muertas manos._

---

Ahora bien, en cierto sentido esto puede considerarse como una evasión de la cuestión: ¿Y si queremos permitir las operaciones infijas? ? También en este caso, la cuestión es que tenemos que abordar las reglas de formación de términos con cuidado. Yo elegiría las siguientes reglas (aquí " $*$ " es un operador infijo binario):

• Si $t_1, t_2$ son términos, entonces $(t_1*t_2)$ es un término.

Obsérvese la adición de paréntesis: esto evita (¡de nuevo!) la formación de un "término ambiguo" como $x*y*z$ . Tiene el inconveniente de añadir "paréntesis innecesarios", por ejemplo, " $x*y$ " no es un término, sino " $(x*y)$ ", pero esto acaba no siendo un problema, sólo una molestia.

---

$^*$ En realidad, hay una tercera solución: ¡sólo permitir operaciones binarias infijas que sean asociativas! Así que un lenguaje consiste en algunos símbolos constantes, símbolos de función, símbolos de relación y operaciones binarias infijas; y una interpretación de un lenguaje tiene que interpretar cada símbolo de operación binaria infija como una función binaria asociativa en el dominio. Esto resuelve las dificultades aquí, ya que la asociatividad está incorporada en la elección de la notación, y significa que podemos permitir expresiones como " $a*b*c$ " sin causar ningún problema; sin embargo, me parece extremadamente artificial (y también va en contra de la práctica matemática: somos perfectamente felices escribiendo " $x-y$ " en el mundo real, después de todo), así que no lo consideraría más que una nota a pie de página.

Answer 3

Si entiendo bien, tu pregunta es: "¿cómo demostrar la asociatividad de $+$ en la aritmética de Peano?". Como usted ha mencionado, la prueba es por inducción sobre $c$, ver más abajo. No es necesario introducir ningún específicos axioma para definir cómo manejar paréntesis, solo necesitas los dos axiomas de Peano que definen $+$, es decir, $A_3$ $A_4$ (ver abajo).

Caso Base: \begin{align} (a+b)+0 &= a+b &\text{by } A_3 \\ &=a+(b+0) &\text{by } A_3 \end{align}

donde $A_3$ es el axioma de Peano: \begin{align} \forall x (x + 0 = x). \end{align}

Inductivo paso: \begin{align} (a+b)+S(c) &= S((a+b)+c) &\text{by } A_4 \\ &=S(a+(b+c)) &\text{by induction hypothesis} \\ &=a+S(b+c) &\text{by } A_4 \\ &=a+(b+S(c)) &\text{by } A_4 \end{align} donde $A_4$ es el axioma de Peano: \begin{align} \forall x \forall y (x + Sy = S(x + y)). \end{align}

Edit: creo que tus problemas son la definición de los términos en una de primer orden de la lengua y la distinción entre sintaxis y semántica. En el primer fin de lenguaje de la aritmética de Peano, los términos se define inductivamente como sigue:

• cada variable es un término;
• $0$ es un término;
• si $t$ $t'$ son términos que, a continuación,$S(t)$, $(t + t')$ y $(t * t')$ son términos.

Tenga en cuenta que los paréntesis son parte de la sintaxis y de jugar un papel importante en la sintácticas de las reglas de formación de términos. Por convención, el externo paréntesis en $(t + t')$ $(t * t')$ son a menudo se omite. Este (sintáctica) definición de los términos está concebido para ser inequívocos, en el sentido de que cada término puede ser leído de una sola manera. Esto podría parecer una molestia, pero es muy importante porque nos permite definir las operaciones y demostrar las propiedades de la inducción en los términos.

Tenga en cuenta que de acuerdo a esta definición de términos, $a + (b + c)$ $(a + b) + c$ (sintácticamente) distintos términos, y $a + b + c$ no es un término debido a una ambigüedad que surge es: que la ocurrencia de $+$ tiene la prioridad? Dicho de otra manera, la expresión de $a + b + c$ es formalmente sin sentido, que no denota nada.

Claramente, tenemos una fuerte intuición de que $a + b + c$ es semánticamente significativas, se debe denotar el mismo número de $a + (b + c)$$(a + b) + c$. Pero es sólo la asociatividad de $+$ (la proposición que quieres demostrar) que permite considerar $a + (b + c)$ $(a + b) + c$ términos que denotan el mismo número, que a veces podía sintéticamente representada (por abuso de lenguaje), por la expresión $a + b + c$.

Sin embargo, si usted desea demostrar formalmente una declaración en la aritmética de Peano, tienes que respetar su sintaxis y, en particular, las reglas de formación de palabras, por lo que no está permitido el uso de expresiones como $a + b + c$. Todo lo que está permitido el uso de Peano son los axiomas y las reglas de inferencia lógica. Usted no necesita ningún axioma o especiales de definición de los paréntesis.

Answer 4

Hay que pensar que los paréntesis sólo explican el orden en el que hay que realizar las operaciones. Así que si, por ejemplo, $f(x, y) = x + y$ entonces $(x+y)+z$ es sólo una abreviatura de $f \big( f(x,y), z \big)$ . No hay nada que probar, es sólo una notación.

Answer 5

La prueba no utiliza nada sobre cómo podemos tratar los paréntesis - cada paso es una definición o una aplicación de la hipótesis inductiva.

Queremos mostrar $(a+b)+c=a+(b+c)$ . Esto es cierto por definición si $c=0$ por lo que asumimos $(a+b)+c=a+(b+c)$ y tenemos que demostrar que $(a+b)+S(c)=a+(b+S(c))$ . El definición de $(a+b)+S(c)$ dice que $$(a+b)+S(c)=S((a+b)+c).$$ Suponemos que $(a+b)+c=a+(b+c)$ Por lo tanto $$S((a+b)+c)=S(a+(b+c)).$$ La definición de $a+S(b+c)$ dice que $$S(a+(b+c))=a+S(b+c),$$ y finalmente la definición de $b+S(c)$ dice que $S(b+c)=b+S(c)$ Por lo tanto $$a+S(b+c)=a+(b+S(c)).$$