¿Se puede deducir el conjunto de fórmulas verdaderas del conjunto de fórmulas demostrables?

Question

EDITAR 01/19/2011 20:30 : a juzgar por las dos respuestas que he recibido, mi pregunta original era que no se entienden completamente, así que voy a tratar de reformular un caso especial.

Imagina que tienes un supermathematician de otro planeta, que puede hacer un montón de cosas que los terrícolas no puede hacer. En particular, se puede calcular de manera efectiva en su cabeza un "cumplimiento" de ZFC, es decir, un (muy grande) lista de axiomas (que se extiende a los axiomas de ZFC) que nunca se contradicen unas a otras y permitir encontrar una respuesta de sí o no a cada pregunta acerca de la teoría de conjuntos. El supermathematician también es capaz de encontrar la respuesta en menos de un segundo para cada pregunta.

Ahora usted juega el juego siguiente con el supermathematician. Inventa algunas de finalización ( $T$ ) de ZFC en su cabeza, y su objetivo es descubrir por sí mismo si la hipótesis continua mantiene en $T$ o no. Por supuesto, usted no puede preguntarle a él directamente "¿ CH sostener, de acuerdo a $T$?" Eso sería demasiado fácil. Usted sólo puede hacer preguntas de la forma : "de Acuerdo a $T$, ¿ ZFC demostrar que la sentencia de $\phi$ ?", pero puede hacer tantas preguntas de esta forma como usted por favor, y para cualquier $\phi$ usted por favor.

Hay una estrategia ganadora ? Tenga en cuenta que es inútil preguntar, "de Acuerdo a $T,$ hace ZFC demostrar CH" ? Ya sabemos que la respuesta es no, y esto será de ninguna ayuda en la determinación de si CH tiene en $T$ o no.

////////////////////////////////////////////////////////////////////

VERSIÓN ANTERIOR, 01/19/2011

Por Goedel los teoremas de la incompletitud, tanto la verdad o la provability de una fórmula de la teoría de conjuntos no es computable en general. Supongamos ahora que tenemos una "máquina mágica" que puede decidir el provability de cualquier frase, $\phi$ ( $ZFC$ , por ejemplo). De modo que la máquina nos dice acerca de la verdad de las fórmulas de la forma $ZFC \vdash \phi$. Con la ayuda de esta máquina, podemos determinar la verdad de todas las fórmulas de $\phi$ ?

Es una versión más formal de esta pregunta : suponga que ZFC es consistente, y deje $\Phi$ denota el conjunto de todas las sentencias de la teoría de conjuntos, vamos a ${\Phi}' \subset \Phi$ denotar el conjunto de oraciones de la forma $ZFC \vdash \phi$ para algunos sentencia de $\phi$. Deje $\cal F$ denota el conjunto de todas las funciones ${\Phi} \to {\lbrace {\sf true,false} \rbrace}$ correspondiente a completar (=máximamente consistente) las extensiones de $ZFC$. Para $f\in {\cal F}$, denotan por $r(f) : {\Phi}' \to {\lbrace {\sf true,false} \rbrace}$ la restricción de $f$${\Phi}' $. Por lo $r$ es un mapa de ${\cal F} \to {}^{{\Phi}'} \lbrace {\sf true,false} \rbrace$. Nos deja denotar por ${\cal F}'$ la imagen de $r$. Entonces, las preguntas son :

• Es $r$ inyectiva ? En otras palabras, hay una "izquierda inversa" $s : {\cal F}' \to {\cal F} $ tal que $s \circ r=id_{\cal F}$.

• Si $s$ existe, es "computable" ? (esta es una pregunta vaga desde $r$ $s$ se definen en muy grande, no computable conjuntos. Básicamente se pregunta si la prueba de la existencia de $s$ (si hay uno) es "explícito" o no).

Answer 1

La respuesta a tu modificado pregunta es no, no podemos llegar a $T$ preguntando acerca de lo $T$ piensa que si ZFC prueba, ya que quizás $T$ incluye la afirmación de $\neg\text{Con}(\text{ZFC})$, en cuyo caso la teoría de la $T$ cree que ZFC demuestra cada declaración. Por lo que siempre va a responder que sí a las consultas. Por el teorema de la incompletitud, si ZFC es consistente, entonces también es perfectamente consistente con ZFC para mantener $\neg\text{Con}(\text{ZFC})$, y por lo tanto no podemos distinguir por su método entre el caso en que el supermathematician tiene una teoría extender $\text{CH} +\neg\text{Con}(\text{ZFC})$ o si su teoría se extiende $\neg\text{CH}+\neg\text{Con}(\text{ZFC})$, ya que todas las respuestas será el mismo para todas las terminaciones de estas dos teorías.

Adenda. Permítanme ahora contestar sin ningún tipo de engaño con el teorema de la incompletitud. El punto es que el conjunto de la teoría de la verdad no está determinado por la simple aritmética de verdad. Nos han dicho que nuestro super-matemático de la teoría de la $T$ es consistente, por lo que se mantiene en algunos modelos de $M$. Considere ahora un forzando la extensión de $M$ derivadas por la costumbre de forzar a cambiar el valor de CH, y deje $T_0$ ser la nueva teoría de la forzando la extensión de $M[G]$. La teoría de la $T_0$ es computable de $T$, ya que una afirmación es, en $T_0$ si y sólo si la afirmación de que esa declaración tiene valor Booleano $1$ para el correspondiente obligando a es $T$ (esto utiliza que el forzamiento es homogénea, por lo que todas estas forzando extensiones de dar lugar a la misma teoría). El punto ahora es que la teoría de la $T$ $T_0$ tienen exactamente las mismas verdades de la aritmética, ya que la aritmética no es afectada por el forzamiento. Por lo tanto, los dos teorías que se dan exactamente las mismas respuestas a las preguntas acerca de lo que ZFC demuestra o acerca de lo que cualquier teoría de la $M$ demuestra, ya que esas cuestiones son la aritmética preguntas (acerca de la existencia de ciertos finito de objetos combinatorios, pruebas). Pero difieren en cuanto a CH, y así uno no puede saber si $T$ CH o no con sólo hacer ese tipo de preguntas.

Conclusión. Lo que este argumento muestra es que para cualquier teoría de la $T$ que la supermathematician tiene en mente, hay otra teoría de la $T_0$ con una respuesta diferente a la CH, pero con las mismas respuestas a las consultas en su juego.

Answer 2

Usted no puede calcular la verdad de la provability con respecto a un computably axiomatizable teoría.

Una forma de ver esto directamente es que el conjunto de (Gödel códigos de) los teoremas de un fijo computably-axiomatizable teoría de la complejidad $\Sigma^0_1$ en el arithemtic jerarquía. En otras palabras, es computable a partir de la detención problema, y por lo suficientemente fuerte teorías, el conjunto de códigos de teoremas es en realidad Turing equivalente como un oráculo para detener el problema.

Mientras tanto, el conjunto de enunciados verdaderos de la aritmética tiene un estricto mayor complejidad, superando $\Sigma^0_n$ cualquier $n$. Por ejemplo, con un oráculo para los teoremas, todavía no se pueden calcular la verdad de $\Sigma^0_3$ declaraciones en general.

Sin embargo, es posible calcular la verdad de la provability con respecto a algunos no-computable teorías. Por ejemplo, si tenemos un oráculo para la recogida de declaraciones verdaderas, entonces podemos (trivialmente) calcular el conjunto de enunciados verdaderos de ella.