Axiomas de Peano para la aritmética

Question

Tengo que dar una charla que menciona los Axiomas de Peano para la Aritmética. Quiero asegurarme de que cuando los explique en inglés los describa correctamente.

(PA1) $(\forall x_1)( \neg s(x_1) = 0)$ $\ \ $

(PA2) $(\forall x_1) (\forall x_2) (s(x_1) = s(x_2) \to x_1 = x_2)$

(PA3) $(\forall x_1) x_1 + 0 = x_1$

(PA4) $(\forall x_1) (\forall x_2) x_1 + s(x_2) = s(x_1 + x_2)$

(PA5) $(\forall x_1) x_1 * 0 = 0$

(PA6) $(\forall x_1) (\forall x_2) x_1 s(x_2) = x_1 * x_2+x_1$

(PA7) $\phi (0) \to ((\forall x_1) (\phi (x_1) \to \phi(s(x_1))) \to (\forall x_1)\phi(x_1)$

(PA1) dice que el 0 no es el sucesor de ningún número.

(PA2) dice Dos números cuyos sucesores son iguales son a su vez iguales

PA3 dice que la identidad aditiva existe

PA4 dice función sucesora ()

PA5 dice que existe una identidad multiplicativa

PA6 dice

PA7 es el axioma de inducción y dice Si un conjunto de números contiene el cero y también el sucesor de cada número del conjunto, entonces cada número está en el conjunto.

Cualquier ayuda será apreciada

Answer 1

Tienes PA1 y PA2 correctos (aunque la lectura equivalente de PA2, que diferentes números tienen diferentes sucesores, es tal vez aún más fácil de motivar).

Evidentemente, el PA3 nos dice tanto menos como más que existe una identidad aditiva. Menos, porque sólo nos dice que hay que sumar el cero a la derecha. Y más, porque nos dice cuál es esa identidad por la derecha. Pero, ¿por qué intentar complicar las cosas? Sólo generaliza la conocida verdad aritmética de que $n + 0 = n$ .

PA4 sólo generaliza la verdad conocida de que $m + (n + 1) = (m + n) + 1$ (ya que tomar sucesores es lo mismo que añadir $1$ es decir, añadiendo $s0$ por PA3 y un caso especial de PA4: $s(n) = s(n + 0) = n + s0$ ).

PA5 no nos da la identidad multiplicativa (esa identidad es $1$ es decir $s0$ no $0$ ). Sólo nos dice que multiplicando por cero nos da cero.

PA6 generaliza el conocido $m(n + 1) = mn + m$

La PA7 (presentada así) no tiene nada que ver con los platós. Es una plantilla de axiomas o un esquema. Y cada instancia que obtenemos cuando rellenamos el $\phi( )$ con una sentencia abierta de la Aritmética de Peano es un axioma. Supongamos un relleno particular para $\phi( )$ expresa la propiedad $P$ -- entonces la instancia del axioma dice, en efecto, que si (i) $0$ tiene $P$ y (ii) $P$ siempre se pasa de un número a su sucesor, entonces (iii) todos los números tienen $P$ .

Es crucial tener claro que PA7 como esquema nos da una teoría bastante diferente ("Aritmética Peano de primer orden") de una teoría con un axioma más fuerte que habla de conjuntos de números ("Aritmética Peano de segundo orden").

Puede que encuentres trozos de mi Introducción a los teoremas de Gödel útil -- en la segunda edición, el capítulo 13 sobre lo que es la AF de primer orden (necesitarás algunas secciones de los tres capítulos anteriores) y el capítulo 29 sobre la AF de segundo orden.

Answer 2

Después de presentar los axiomas individualmente, creo que es útil presentar cómo funcionan algunos de estos axiomas por parejas:

PA1 y PA2 obligarán a que cualquier modelo de esos dos axiomas contenga una cadena infinita de objetos siendo el 0 el "primer" objeto, $s(0)$ (al que, por supuesto, nos referimos normalmente como "1") siendo el "siguiente", $s(s(0))$ ('2') el siguiente, etc. Y como no hay dos objetos diferentes que puedan tener el mismo sucesor, el sucesor de cada uno es diferente de cualquiera de los anteriores, lo que obliga a que esta cadena infinita sea isomorfa a la estructura de los números naturales tal y como los conocemos.

Puedes presentar PA3 y PA4 juntos como una definición recursiva de la adición, en la que el "addend" derecho se añade recursivamente al "addend" izquierdo uno a uno. Es decir, para sumar n a m, sumo repetidamente 1 a n, hasta que lo haya hecho n veces. PA3 es la base recursiva, y PA4 el paso recursivo.

Del mismo modo, PA5 y PA6 forman una definición recursiva de la multiplicación, donde la multiplicación se define como una suma repetida. Es decir, para multiplicar m por n empezamos con 0, y repetidamente añadimos m a eso, n veces. PA5 es la base recursiva, y PA6 es el paso recursivo.

(Si hay informáticos entre su público, seguro que apreciarán esta referencia a la recursividad... Y es difícil evitar alguna noción de recursividad de todos modos cuando se habla de los resultados de Godel, incluso a alto nivel)

Ah, y PA7 es por supuesto el esquema de inducción matemática débil que aprovecha la propia naturaleza recursiva de los números naturales (es decir, como el 0 es un número natural (base) y como el sucesor $s(n)$ de cualquier número natural $n$ es un número natural en sí mismo, y como no hay más números naturales que los que se obtienen a través de este proceso recursivo, entonces si se puede demostrar que 0 tiene alguna propiedad, y si el sucesor $s(n)$ de cualquier número natural $n$ tiene esa propiedad asumiendo $n$ tiene esa propiedad, entonces todo número natural tiene esa propiedad)