Indecidible conjeturas

Question

Supongamos que trabajamos con una conjetura diciendo que algo es verdadero para cualquier natural $n$. Para cada una de las $n$ existe un algoritmo de longitud finita que permite decidir si es verdadero o falso para esta $n$, y supongamos que tenemos una fórmula explícita de cómo la longitud depende de la $n$. Se ha demostrado que la conjetura es verdadera para todos los números hasta, digamos, $10^{1000}$; sin contraejemplo se encuentra. Es posible que esta conjetura es indecidible?

Como tengo entendido, la respuesta es sí, pero no entiendo lo siguiente. Si la conjetura es falsa, entonces podemos tomar la correspondiente $n$ y por lo tanto tenemos una finito prueba de ese hecho. Si es indecidible, que podemos añadir el axioma de que es falso, y entonces nos parecen llegar a una contradicción con mi anterior frase. Podría alguien explicar lo que está mal?

Answer 1

Vamos a mostrar donde su intuitiva argumento se rompe. Llame a la conjetura $\varphi$, y supongamos que $\varphi$ es indecidible. Entonces, como se observó, en virtud de su muy fuertes supuestos, $\varphi$ que es verdad en los números naturales, pero no demostrable.

No se puede demostrar en qué teoría? Por indecidible nosotros siempre significa indecidible en una teoría particular. Decir que la teoría es PA, de primer orden de la Aritmética de Peano. Pero para el resto de este post, PA podría ser sustituido por ninguna lo suficientemente fuerte de la teoría de los números naturales como un modelo.

Agreguemos a PA el axioma $\lnot\varphi$ como se especificó. A continuación, la teoría de la $T$ con los axiomas de los axiomas de la Aritmética de Peano, junto con $\lnot\varphi$, es coherente, y por lo tanto tiene un modelo de $M$. En $M$, la conjetura $\varphi$ es falso.

Este modelo de $M$ es no (isomorfo a) $\mathbb{N}$, ya que el $\varphi$ que es verdad en $\mathbb{N}$. El objeto de $\omega\in M$ que los "testigos" de la falsedad de $\varphi$ $M$ es, por tanto, no es un número natural. Su algoritmo no será aplicable a $\omega$, que es, en el sentido informal, mayor que $1$, $1+1$, $1+1+1$, y así sucesivamente. (Podemos, sin pérdida de generalidad supongamos que $\mathbb{N}\subset M$). De manera informal, en virtud de sus supuestos, cualquier $\omega$ que los testigos de la falsedad de la $\varphi$ $M$ debe ser un "infinito" entero.

Si un determinado argumento se rompe, es posible que el resultado que se persigue es cierto! Sin embargo, podemos encontrar ejemplos explícitos de las sentencias $\varphi$ del tipo que se describe que resultan ser indecidible en PA.

En particular, se puede construir una explícita de la ecuación de Diophantine $E$ ($k$ variables, donde a $k$ no es muy grande, lo último que escuché acerca de $20$) que tiene no hay soluciones en $\mathbb{N}$, pero que este hecho no es demostrable en PA. Deje $\varphi$ ser la afirmación de que este Diophantine ecuación no tiene soluciones. Para cualquier específicos de $k$-tupla $(a_1,a_2, \dots, a_k)$ de los números naturales, el hecho de que $(a_1,a_2,\dots,a_k)$ no es una solución de $E$ es fácilmente seleccionable, por un cálculo de predicción de longitud. Adecuada codificación de las $k$-tuplas de números naturales, podemos asegurarnos de que la $\varphi$ satisface sus condiciones.

Answer 2

Goldbach de la conjetura (que establece que si $n\ge4$ es incluso entonces se trata de una suma de dos números primos) es de este tipo. Si es falso, entonces no es un contraejemplo, y así una prueba de que es falso; por lo tanto, si es indecidible (dentro de un determinado sistema de axiomas), entonces es verdadero.

El gemelo primer conjetura (que existen infinitos números primos $p$ tal que $p+2$ es también prime) es diferente hervidor de pescado. El argumento anterior no se aplica, por lo que podría ser indecidible en un sentido más fuerte.

Answer 3

Se supone que está trabajando sobre la hipótesis de la consistencia de PA (denota $con(PA)$) en PA en sí. $con(PA)$ esencialmente dice que para cada una de las $n$, no es el caso que $n$ es el número de Gödel de una prueba de una contradicción, es decir, $con(PA)$ denota la fórmula $\forall x \lnot Prov(x, 0 = 1)$. Por lo $con(PA)$ es un tipo de conjetura que usted está buscando.

Sabemos que para cada número natural $n$, ${\rm PA} \vdash \lnot Prov(n, 0 = 1)$. La cuantificación universal (es decir,$con(PA)$) por otro lado, no es demostrable en PA. Si usted agregue $\lnot con(PA)$ a PA, a continuación, usted termina con una teoría es consistente, pero no $\omega$-consistente. La tarde significa que la teoría resulta $\exists x p(x)$ y $\lnot p(0), \lnot p(1), ...$ algunos $p$.