Cómo probar que Gödel los Teoremas de Incompletitud se aplican a ZFC?

Question

Nos deja denotar Robinson Aritmética como Q y Primitiva Recursiva de la Aritmética como la PRA. Deje $T$ ser una teoría formal formulada en el lenguaje de la aritmética. De acuerdo a esta página en la Enciclopedia de Filosofía de Stanford, el primer teorema de la incompletitud se aplica a $T$ si $T$ contiene a Q, y el segundo teorema de la incompletitud se aplica si $T$ contiene PRA. Si $T$ no está formulado en el lenguaje de la aritmética, entonces el primer y segundo teoremas de la incompletitud de retener para $T$ si se requiere que Q y PRA, respectivamente, pueden ser interpretadas en $T$. La universidad de Stanford página luego va a decir que

Aproximadamente, una teoría de la $T_1$ es interpretable en otra teoría $T_2$ si los conceptos primitivos y el rango de las variables de $T_1$ son definibles en $T_2$, de modo que es posible traducir cada teorema de $T_1$ en un teorema de $T_2.$

Me pregunto cuál es la definición precisa es para $T_1$ a ser interpretables en $T_2?$ por otra parte, ¿cómo se podría ir sobre la muestra que Q y PRA son interpretables en ZFC? Peter Smith respuesta a una pregunta similar, se aclara que las condiciones que se especifican en la universidad de Stanford página de dejar que $T$ debe ser eficaz (recursivamente axiomatizable). Smith va a decir que

demuestra que se puede interpretar de la aritmética en ZF(C), y -- con las correspondientes entregas -- los axiomas de la Aritmética de Robinson son teoremas de ZF(C), y así que te vas de nuevo.

Una vez que tengo una definición precisa de lo que significa para una teoría para interpretar otra teoría, mi siguiente pregunta es, ¿cómo podemos probar que Q y PRA son interpretables en ZFC? Si esto sería una excesivamente larga respuesta, agradecería recomendaciones de los correspondientes títulos de libros.

Cuando yo estaba buscando maneras de interpretar una media aritmética de la teoría ZFC, me encontré con Henning Makholm la respuesta a esta pregunta. Por lo que veo, si $D$ es el dominio de discurso, podemos definir la función sucesor $S:D\rightarrow D$, usando los axiomas de ZFC como $S(x) = x\cup\{x\}.$ sin Embargo, sin el modelo de von Neumann Universo, que define un ordinal, ¿cómo debemos definir la suma y la multiplicación?

Answer 1

La noción de interpretación que buscas es una relación de interpretación de uno de primer orden lenguaje $L_1$ en otro de primer orden lenguaje $L_2$. No puedo encontrar una buena línea de referencia para este. El siguiente es tomado de la memoria de Mendelson Introducción a la Lógica Matemática.

Por simplicidad, supongamos $L_1$ no tiene símbolos de función. A continuación, una relación de interpretación se compone de dos cosas (1) una función de mapeo de cada una de las $n$-lugar predicado símbolo $p(x_1, \ldots, x_n)$ $L_1$ a una fórmula $\phi_p(x_1, \ldots, x_n)$ $L_2$ y (2) una fórmula $\delta(x)$ $L_2$ (donde todas las fórmulas tienen sólo las variables indicadas libre). Usted, a continuación, asignar una fórmula arbitraria $\chi$ $L_1$ a una fórmula $\chi^*$, es decir, $L_2$ mediante la sustitución de cada instancia de un $n$-lugar predicado $p(x_1, \ldots, x_n)$ por la instancia correspondiente de $\phi_p(x_1, \ldots, x_n)$, entonces la sustitución de la fórmula de la forma $\forall x.\chi$ $\forall x. (\delta(x) \Rightarrow \chi)$ y, finalmente, la sustitución de la fórmula de la forma $\exists x.\chi$ $\exists x.(\delta(x) \land \chi)$.

Ahora puede definir la teoría de una $T_1$ $L_1$ a ser interpretables en una teoría de la $T_2$ $L_2$ si existe una relación de interpretación de $L_1$ $L_2$ que se asigna teoremas de $T_1$ a los teoremas de $T_2$. La idea es que en cualquier modelo de $T_2$, $\delta(x)$ identifica el dominio de discurso de $T_1$ $\phi_p(x_1, \ldots, x_n)$ define la interpretación de cada símbolo de predicado $p(x_1, \ldots, x_n)$$L_1$. Si $T_1$ es interpretable en $T_2$, $T_2$ puede demostrar (la interpretación de) la sentencia comprobable en $T_1$ (y tal vez muchos más).

La matemática de los detalles de una relativización de $Q$ o $PRA$ $ZF$ a continuación, según lo sugerido por Asaf Karagila la respuesta. En primer lugar, usted tiene que reformular el lenguaje de la aritmética, utilizando sólo los predicados (así, por ejemplo, sustituir + por un tres-lugar predicado $P(x, y, z)$ cuya intención interpretación es $z = x + y$). Luego de tomar $\delta(x)$$x \in \omega$, y asignar los símbolos de predicado a las fórmulas apropiadas que denota el conjunto habitual de la teoría de representaciones de las funciones y predicados del lenguaje de la aritmética (que todo puede ser definido en términos de la sucesora de la operación $n \mapsto n \cup \{n\}$ el uso de la cuantificación a través de subconjuntos de $\omega$, $\omega^2$ y $\omega^3$, ver las respuestas a por Qué son la adición y la multiplicación incluido en la firma de primer orden de la aritmética de Peano? y Cómo definir la multiplicación además de los términos en monádico de segundo orden de la lógica? para más detalles). (Aquí estoy, escribiendo como si $\omega$ fue una constante en el lenguaje de la ZF, mientras que la ZF es generalmente de configurar para tener sólo una no-lógico símbolo $\in$, por lo que el $x \in \omega$ ha de ser leído como la taquigrafía para algunos complicada fórmula afirmar que $x$ le pertenece a todo conjunto que contiene al conjunto vacío y es cerrado bajo sucesor.)

Answer 2

La aritmética ordinal coincida a la perfección el usuales de la aritmética de los números naturales cuando restringida a los ordinales finitos. Y no por accidente, ya que ambos pueden ser definidos por la recursividad de las sucesor del operador.

Entonces podemos demostrar que usted obtener un modelo de los Axiomas de Peano, incluso si se considera el segundo axioma de inducción. Para ver esto, observe que los axiomas acerca de la aritmética debido a la definición inductiva (que es exactamente lo que los correspondientes axiomas de Peano decir), y el axioma de inducción tiene porque $\omega$ es el menor conjunto inductivo.

También puede utilizar el cardenal de la aritmética, que también coincide con los dos cuando se trata de finito de los números ordinales.