oraciones indecidibles de aritmética de primer orden cuyos valores de verdad son desconocidos

Question

Gödel indecidible sentencias de primer orden aritmética están garantizados para ser verdad, por la construcción. Pero hay ejemplos de frases específicas conocido por ser indecidible en primer orden de la aritmética cuya verdad los valores no son conocidos? Estoy pensando, por el contrario, de la situación en la que la teoría de conjuntos: CH es indecidible en ZFC, pero su valor de verdad es, en cierto sentido, desconocido.

París y Harrington mostró el fortalecimiento de la finitos Ramsey teorema es verdadero (en el sentido de comprobable en segundo orden de la aritmética), pero indecidible en primer orden de la aritmética. Estoy preguntando por "natural" en los ejemplos de este general de la vena -- pero cuyos valores de verdad aún no ha sido resuelto.

EDIT. Permítanme aclarar mi interés en la cuestión, que es más filosófica de las matemáticas. Le pregunté sobre la base de la siguiente pasaje de Pedro Koellner del papel "En la Cuestión de Absoluta Undecidability":

Las declaraciones anteriores de análisis [es decir, todos los conjuntos proyectivos de reales son Lebesgue medibles] y la teoría de conjuntos [es decir, el CH] difieren de los principios de aritmética instancias de imperfección en la que su independencia hace no implica su verdad. Por otra parte, no es inmediatamente claro si están asentadas en cualquier nivel de la jerarquía. Ellos son mucho más graves casos de la independencia.

Lo que estoy preguntando es si son "mucho más graves" de la independencia, incluso en el fin de la aritmética-y no en el caso trivial de lleno-en ZFC, como V=L, etc. Por una frase con "desconocidos valor de verdad," me acaba de decir una frase que no ha sido demostrado en una teoría más fuerte que la de primer orden de la aritmética. (Por ejemplo, París y Harrington demostrado el fortalecimiento de la finitos teorema de Ramsey en segundo orden de la aritmética.)

Answer 1

La actualización. He mejorado el argumento para utilizar sólo la consistencia de $T$. (2/7/12): he corregido algunos sobre-declaraciones hechas anteriormente acerca de Robinson P.

---

Yo reclamo que por cada declaración de $\varphi$, hay una variante de la forma para expresarlo, $\psi$, que es equivalente a la original declaración de $\varphi$, pero que es formalmente independiente de cualquier en particular deseado coherente teoría de la $T$.

En particular, si $\varphi$ es tu favorito natural de la pregunta abierta, cuyo valor de verdad es desconocido, entonces no es un equivalente la formulación de esa pregunta que exhibe la independencia formal en la forma en que usted solicitó. En este sentido, cada pregunta abierta es equivalente a una afirmación con la propiedad que usted haya solicitado. Yo tome esta revelar ciertas difícil sutilezas con su proyecto.

Teorema. Supongamos que $\varphi$ es de pena y $T$ es consistente la teoría que contiene débil de la aritmética. Luego, hay otra frase $\psi$ tal que

• $\text{PA}+\text{Con}(T)$ demuestra que $\varphi$ e $\psi$ son equivalentes.
• $T$ no demuestran $\psi$.
• $T$ no demuestran $\neg\psi$.

Prueba. Deje $R$ ser el Rosser frase para $T$, la auto-referencial afirmación de que para cualquier prueba de $R$ en $T$, hay una pequeña prueba de $\neg R$. El Gödel-Rosser teorema establece que si $T$ es consistente, entonces $T$ demuestra ni $R$ ni $\neg R$. La formalización de la primera parte de este argumento muestra que el $\text{PA}+\text{Con}(T)$ demuestra que $R$ no es comprobable en $T$ y que, por ende, $R$ es vacuously verdadero. La formalización de la segunda parte de este argumento muestra que el $\text{Con}(T)$ implica $\text{Con}(T+R)$, y por lo tanto, por el teorema de la incompletitud aplicado a $T+R$, podemos deducir que $T+R$ no demuestran $\text{Con}(T)$. Por lo tanto, $T+R$ es estrictamente una intermedia entre la teoría $T$ e $T+\text{Con}(T)$.

Ahora, vamos a $\psi$ ser la afirmación de $R\to (\text{Con}(T)\wedge \varphi)$. Desde $\text{PA}+\text{Con}(T)$ demuestra $R$, es fácil ver por lógica elemental que $\text{PA}+\text{Con}(T)$ demuestra que $\varphi$ e $\psi$ son equivalentes.

La declaración de $\psi$, sin embargo, no es demostrable en $T$, ya que si lo fuera, entonces $T+R$ demostraría $\text{Con}(T)$, que no por nuestras observaciones anteriores.

Por el contrario, $\psi$ no es rebatible en $T$, desde cualquier refutación significaría que $T$ demuestra que la hipótesis de de $\psi$ es verdadera y la conclusión falsa; en particular, requeriría $T$ a probar el Rosser sentencia de $R$, que no por el Gödel-Rosser teorema. QED

Tenga en cuenta que cualquier ejemplo de la no-provability de $T$ va a requerir la consistencia de $T$, y así no se puede proporcionar una solución para el problema sin asumir la teoría es consistente.

La observación del teorema ha surgido en algunas de las ideas filosóficas de la literatura puede tener en mente, basado en lo que usted dijo en la pregunta. Por ejemplo, la afirmación de que el teorema se menciona en Haim Gaifman nuevo de papel "En la ontología y el realismo en las matemáticas", que leemos en el curso de mi último semestre en la filosofía de la teoría de conjuntos; ver la discusión en la página 24 de Gaifman papel, y específicamente la nota 35, en el que los créditos de un punto fijo argumento para Torkel Franzen, y una independiente de la construcción a Harvey Friedman.

---

Mi argumento original (véase la edición de la historia) se utiliza la frase $\text{Con}(T)\to(\text{Con}^2(T)\wedge\varphi)$ donde $\text{Con}^2(T)$ es la afirmación de $\text{Con}(T+\text{Con}(T))$, y trabajó bajo el supuesto de que $\text{Con}^2(T)$ es verdad, confiando en el hecho de que $T+\text{Con}(T)$ es estrictamente entre $T$ y más fuerte de la teoría. El argumento actual utiliza esencialmente de manera similar idea de que $T+R$ es estrictamente entre $T$ e $T+\text{Con}(T)$, reduciendo así la consistencia de la asunción.

Answer 2

Creo que hay un malentendido.

París y Harrington mostró el fortalecimiento de la finitos teorema de Ramsey es cierto, pero no demostrable en primer orden de la aritmética; no sé si hay una prueba de que se extiende el resultado completo en undecidability en lugar de sólo unprovability.

De hecho, la página de la Wikipedia es sólo hablar de unprovability, pero la negación de la consolidación de la finitos teorema de Ramsey es también improbable en la aritmética de Peano de "trivial" las razones: si usted puede probar esta negación, luego de segundo orden de la aritmética puede ser también de esta negación (porque la aritmética de segundo orden es más fuerte que la aritmética de Peano), por lo que esto significaría que la aritmética de segundo orden es inconsistente (porque de segundo orden aritmética demuestra el fortalecimiento de la finitos teorema de Ramsey).

Así que si te da por descontado que los de segundo orden de la aritmética es consistente, entonces su ejemplo es en realidad indecidible en la aritmética de Peano. Y hay otros ejemplos como el teorema de Goodstein.

Answer 3

Lo que quieres se llama división aritmética [de primer orden]. He hablado y escrito mucho sobre esto en los últimos años. Envíame un mensaje y puedo mostrarte algunos borradores sobre el estado actual de este tema tan importante.

Sí, no deberíamos poder formar ninguna preferencia, como en el caso de PH, donde está claro que PH es mejor que \ neg \ PH.

Answer 4

Yo diría que Con(ZF) no es conocido por ser indecidible-es sólo indecidible si es verdad. Si es falsa, el hecho es $\Sigma^0_1$ y por lo tanto demostrable. Queremos una frase que s $\Sigma^0_2$ o superior.

Este podría ser un casi-ejemplo: http://www.cs.uchicago.edu/~simon/RES/collatz.pdf

Esto demuestra que una generalización de las 3n+1 conjetura es $\Pi_2$-completa. Pero no es lo que se le pide, ya que se trata de una familia de problemas en lugar de una sola frase.

Answer 5

Si vas a colocar para una importante pregunta abierta que es independiente de algunos débiles fragmentos de PA, el P vs NP problema es un ejemplo.

http://www.scottaaronson.com/papers/pnp.pdf se explica esto un poco.

O si usted va a tomar una completamente artificial problema que más fuertemente independiente, sólo generan una muy larga la proposición en el PA del lenguaje, haciendo rodar los dados. No se sabe su valor de verdad, y a partir del teorema de Chaitin es casi seguro que sea independiente de cualquier sistema de axiomas.