¿Qué significa la expresión "contiene aritmética" en el segundo medio de Teorema de Gödel incompletenetss exactamente?

Question

La segunda Gödel incompletenetss teorema es a menudo formulado de la siguiente manera:

Suponga que F es constante de un sistema formalizado que contiene elementales de la aritmética. Entonces F ⊬ Contras(F).

¿Alguien puede aclararme, ¿qué se entiende por la palabra "contiene" aquí? Creo que, en el caso de $F$ es una variante de un conjunto axiomático de la teoría de la "contiene" significa que la aritmética de Peano tiene un modelo en $F$. Al parecer, en el caso general, la gente tiene en mente una construcción similar, pero no sé exactamente formulaciones. Por favor, podrias aclarar esto (y me da una referencia)?

Answer 1

Lo que tenemos que hacer para ejecutar Goedel del argumento coherente recursivamente enumerable de la teoría de la $T$ es de alguna manera representan la primitiva recursiva funciones dentro de $T$; a continuación, podemos probar la diagonal lema y escribir una versión de la Goedel frase en $T$, y hemos terminado.

Entonces, ¿qué significa "representar" la primitiva recursiva funciones dentro de $T$? En el caso de que $T=PA$ (o mucho menos), no hay una definición natural: $T$ representa una función de $f:\mathbb{N}\rightarrow\mathbb{N}$ si hay alguna fórmula $\varphi(x)$, en el lenguaje de la aritmética, tales que para cada $n$, $T$ prueba "$\varphi(\underline{n})=\underline{m}$" para exactamente un número $\underline{m}$, y esta cifra es exactamente el número de $f(n)$. Es decir, $T$ individual puede calcular cada una "instancia real" de $f$.

Ahora, el examen de esta definición, podemos ver un problema inmediato: para cada número natural $n$ necesitábamos un término adecuado $\underline{n}$ en nuestro idioma. Pero, ¿y si nuestro idioma no es el lenguaje de la aritmética? O peor aún, ¿y si nuestro lenguaje no tiene ningún tipo de condiciones a todos (por ejemplo, el lenguaje de la teoría de conjuntos)?

Bien, vamos a modificar la definición de la representabilidad un poco, vamos a considerar formas arbitrarias de tratar de poner los números naturales dentro de $T$ en algún sentido; y lo haremos a través de fórmulas, en lugar de los términos, para hacer que funcione para ilimitado teorías como la de ZFC.

Si $T$ es arbitrario consistente recursivamente axiomatizable teoría en un lenguaje de $L$ y una función computable $R: \mathbb{N}\rightarrow Formula(L)$, entonces diremos que el par $(T, R)$ es $f:\mathbb{N}\rightarrow\mathbb{N}$ si

• $T$ prueba "no es exactamente una $x$ tal que $\varphi(x)$" para cada una de las $\varphi$ en la imagen de $R$ (es decir, $R$ es salida única definiciones = pensar "$x=S(S(0))$" como una fórmula única definición de $2$)

y

• Hay alguna fórmula $\psi_f$ tal que para cada una de las $n\in\mathbb{N}$, no es exactamente una $m\in\mathbb{N}$ tal que $T$ demuestra "Si $R(n)(x)$ sostiene, a continuación, $\psi_f(x)=y$ siempre $R(m)(y)$ sostiene." Recuerde que $R(m)$ es una fórmula y "$R(m)(y)$ sostiene" es el argot, en nuestro contexto, por "$y=m$," por lo que esta realmente en paralelo la imagen de arriba.

Ahora se le da un $T$ $R$ tal que $(T, R)$ representa a cada primitiva recursiva de la función, podemos ejecutar Goedel del argumento para demostrar que $T$ es incompleta. Tenga en cuenta que puede haber diferentes $R$s que nos permite "interpretar" los números naturales en $T$; eso está bien! El punto es que solo necesitamos un tal $R$ para el argumento para trabajar.

Answer 2

La propiedad importante es que debe ser posible expresar primitiva recursiva de la aritmética en la teoría. Una posible manera de formalizar este es exigir que

• Para cada número natural $n$ hay una fórmula $\psi_n(x)$ tal que $T$ demuestra $\exists x.\psi_n(x)$. (Intuitivamente $\psi_n(x)$ representa "$x$ es el número de $n$").
• Para los números naturales $n\ne m$, $T$ prueba $\neg(\psi_n(x)\land \psi_m(x))$.
• $\psi_n$ puede ser construido mecánicamente determinado $n$ (es decir, el número de Gödel de $\psi_n(x)$ debe ser una primitiva de la función recursiva de $n$).
• Para cada primitiva de la función recursiva $f(x_1,\ldots,x_k)$ debe haber una fórmula $\varphi_f(x_1,\ldots,x_k,y)$ tal que para cada $n_1,\ldots,n_k$, $T$ prueba $$\psi_{n_1}(x_1)\land\cdots\land \psi_{n_k}(x_k) \to \bigr[\varphi_f(x_1,\ldots,x_k,y) \leftrightarrow \psi_{f(n_1,\ldots,n_k)}(y)\bigr]$$

Estas condiciones, en particular, ser satisfechos si hay una manera de traducir las fórmulas de la aritmética en el lenguaje de la $T$, de tal manera que $T$ demuestra las traducciones de los axiomas de la Aritmética de Peano-o incluso sólo los axiomas de Robinson Q (que no incluyen la inducción).

---

Esto supone que $T$ es una teoría en el estándar de la lógica de primer orden. Podemos hacerlo aún más abstracto por sólo requieren que el sistema formal puede expresar (de forma sistemática) suficiente conectivos lógicos y deducciones para hacer las construcciones en la prueba de ir a través de -- pero no tengo una lista lista de de que que es.

---

Huy, que no era del todo correcto. El de arriba es suficiente para probar el primer teorema de la incompletitud. Para el segundo uno también necesita una cierta cantidad de inducción. Inducción sobre existencialmente cuantificadas las fórmulas de la primitiva recursiva aritmética debería ser suficiente, sin embargo.