Hay un punto de confusión en la pregunta:
Por ejemplo, he leído que se puede definir además en la de segundo orden de la aritmética por escrito
- $x+0 = x$
- $x+S(y) = S(x+y).$
¿Por qué este trabajo en la aritmética de segundo orden, pero no en los de primer orden?
Que no funciona en segundo orden de la aritmética. Es una forma implícita de la caracterización de la función de suma, pero no es una explícita definición de la función de suma en términos de la función sucesor.
Una verdadera definición es una fórmula $\phi(n,m,p)$ en un idioma sin la adición símbolo $+$ tal que, para todos los números naturales $n,m,p$, $n + m = p$ si y sólo si $\phi(n,m,p)$ mantiene. Un "pseudo-definición" que es capaz de referirse al objeto que está siendo definida se llama una definición implícita, pero implícito definability es mucho más débil que la real definability.
Una definición real de la adición de números naturales en segundo orden, la aritmética es:
$$
n + m = p \Leftrightarrow (\forall f)\left[ \left( f(0) = n \tierra (\forall k)[f(S(k)) = S(f(k)]\right ) \f(m) = p\right].
$$
Aquí $n,m,p$ son números naturales, $(\forall k)$ cuantifica sobre los números naturales, y $(\forall f)$ cuantifica sobre todas las funciones unarias de los números naturales a sí mismos. Observe que, fundamentalmente, la de la derecha no hace mención de $+$. En la definición particular, también podemos reescribirlo con un existencial función cuantificador:
$$
n + m = p \Leftrightarrow (\existe f)\left( f(0) = n \tierra (\forall k)[f(S(k)) = S(f(k))] \de la tierra f(m) = p\right).
$$
¿Por qué esta definición no trabajo en lógica de primer orden? Porque, en un único ordenado de primer orden de la teoría de la aritmética, no es posible cuantificar de las funciones, en la forma en que la definición que se hace.
Ahora, eso no es prueba de que es imposible definir la adición de números naturales en términos de sucesor. Sólo muestra que la definición de segundo orden de la aritmética no ir a través de cambios.
Una forma de ver que además no es definible desde sucesor está esbozado en esta respuesta por Alex Kruckman. El punto clave es que si nos fijamos en el primer orden de teoría de los números naturales con el sucesor y una constante de 0, cada fórmula en este idioma (con algunas variables libres) es equivalente a un cuantificador libre de fórmula en el lenguaje (con las mismas variables libres). Una prueba de que es dada por Richard Kaye aquí. Así que si además era definible en que la estructura, sería definible por un cuantificador fórmula libre. Pero al analizar la forma de una fórmula que se puede mostrar que no puede definir, además de.
En realidad, se sabe más. Ni la suma ni la multiplicación es definible desde sucesor solos; la multiplicación no es definible a partir de sucesor y la inclusión; y además no es definible a partir de sucesor y la multiplicación. La teoría de los números naturales con la multiplicación y la suma es indecidible, pero la restricción de que sólo la adición es decidable, y la restricción sólo con la multiplicación es decidable.
