¿Alguien sabe un polinomio cuya falta de raíces no se puede probar?

Question

En Ebbinghaus-Flum-Thomas Introducción a la Lógica Matemática, la siguiente afirmación es hecha:

Si ZFC es consistente, entonces uno puede obtener un polinomio $P(x_1, ..., x_n)$ que no tiene raíces en los enteros. Sin embargo, esto no puede ser demostrado (dentro de ZFC).

Así que si $P$ no tiene raíces, entonces la matemática (=ZFC, por ahora) no puede demostrarlo.

La justificación es que Matiyasevich la solución de Hilbert del décimo problema permite a su vez declaraciones acerca de las verdades demostrables en un sistema formal para la existencia de entero raíces de ecuaciones polinómicas. La declaración es "ZFC es consistente," que no puede ser probada dentro de ZFC gracias a el teorema de Gödel.

Pregunta: Tiene un polinomio alguna vez se ha calculado?

(Esto surgió en un hilo de comentarios en el sitio beta de matemáticas.SE.)

Answer 1

En su tesis de maestría, Merlin Carl ha calculado un polinomio que se puede resolver en los enteros si ZFC es inconsistente. Puede encontrar un documento conjunto con su asesor Boris Moroz sobre este tema en http://www.math.uni-bonn.de/people/carl/preprint.pdf .

Answer 2

Para cada consistente recursivamente axiomatizable teoría de la $T$ existe (y efectivamente se calcula a partir de los axiomas de $T$) un número entero $K$ de manera tal que la siguiente ecuación Diophantine (donde todas las cartas excepto $K$ son variables) no tiene soluciones a través de enteros no negativos, pero este hecho no puede ser probado en $T$:

\begin{align}&(elg^2 + \alpha - bq^2)^2 + (q - b^{5^{60}})^2 + (\lambda + q^4 - 1 - \lambda b^5)^2 + \\ &(\theta + 2z - b^5)^2 + (u + t \theta - l)^2 + (y + m \theta - e)^2 + (n - q^{16})^2 + \\ &((g + eq^3 + lq^5 + (2(e - z \lambda)(1 + g)^4 + \lambda b^5 + \lambda b^5 q^4)q^4)(n^2 - n) + \\ &(q^3 - bl + l + \theta \lambda q^3 + (b^5-2)q^5)(n^2 - 1) - r)^2 + \\ &(p - 2w s^2 r^2 n^2)^2 + (p^2 k^2 - k^2 + 1 - \tau^2)^2 + \\ &(4(c - ksn^2)^2 + \eta - k^2)^2 + (r + 1 + hp - h - k)^2 + \\ &(a - (wn^2 + 1)rsn^2)^2 + (2r + 1 + \phi - c)^2 + \\ &(bw + ca - 2c + 4\alpha \gamma - 5\gamma - d)^2 + \\ &((a^2 - 1)c^2 + 1 - d^2)^2 + ((a^2 - 1)i^2c^4 + 1 - f^2)^2 + \\ &(((a + f^2(d^2 - a))^2 - 1) (2r + 1 + jc)^2 + 1 - (d + of)^2)^2 + \\ &(((z+u+y)^2+u)^2 + y-K)^2 = 0. \end{align}

Por otra parte, para cada una de dichas teoría, el conjunto de los números con esta propiedad es infinito y no es recursivamente enumerable.

La ecuación se deriva de "Universal Ecuación Diophantine" por James P. Jones.

Answer 3

Algo parecido a lo que quiero es que en el papel "Universal Ecuación Diophantine" por James P. Jones, en la Diario de la Lógica Simbólica 47 (1982), pp 549--571. Jones produce una lista explícita de 37 ecuaciones en 53 incógnitas cuya simultánea satisfiability es equivalente general de la declaración de los miembros de computably enumerable los conjuntos.

Estos 37 ecuaciones son equivalentes a una sola la ecuación (suma de sus cuadrados = 0) y, puesto que es universal, usted puede encontrar una instancia equivalente a un improbable pero la verdadera oración de ZFC sustituyendo valores para un par de las variables. Sigue para calcular estos los valores numéricos, que son, probablemente, enorme ...

Si usted tiene acceso a JSTOR se puede ver el documento aquí.

Answer 4

El MRDP solución de Hilbert 10 del problema establece que el entero conjuntos de soluciones $\{\, n\, |\, \exists\vec n\, p(n,\vec n)=0\}$ de diophantine ecuaciones $p(n,\vec n)=0$ son exactamente los computably conjuntos enumerables.

En particular, para cualquier coherente teoría de la $T$, como PA o ZFC o cualquiera que sea tu favorito teoría es, podemos escribir un determinado polinomio $p(n,\vec n)$ tal que $p(n,\vec n)=0$ exactamente al $n$ es el Goedel código de la prueba de una contradicción de $T$, ya que este es sin duda un c.e. conjunto. Por lo tanto, si $T$ es consistente, entonces $p(n,\vec n)=0$ tendrá ningún entero soluciones, pero por el teorema de la incompletitud, $T$ será incapaz de probar este. Esta cuestión se analiza en este MO respuesta.

Es posible, en principio, para extraer de las pruebas de la real polinomios involucrados, y creo que para el estándar de teorías, estos polinomios se han escrito. Aunque algunos podrían encontrar que no es particularmente iluminador para hacerlo, yo admiro a cualquier persona que poner en el esfuerzo para producir, en realidad, el polinomio. Tal vez a los demás va a responder con los reales de polinomios.

Answer 5

Esta pregunta es frecuentes, por lo general en relación a la hipótesis de Riemann o la consistencia de la teoría de conjuntos. Supongo que este es tan buen lugar como cualquier otro para recoger referencias explícitas arithmetizations de inicialmente no Diophantine problemas, como (sistemas de) Diophantine ecuaciones.

En uno de sus primeros papeles, Matijasevich da un ejemplo de una ecuación de Diophantine que expresan un número de la teoría de la declaración, diferentes de los que están en el camino de Hilbert del 10 de problema. Los que están en el camino fueron su avance "$m = F_{2n}$" y el universal Diophantine predicado, "la máquina de $m$ se detiene en el tiempo $t$ en la entrada de $n$". El ejemplo ilustrativo fue algo así como "es un número primo", no es nada tan complicado como la consistencia de ZFC. El universal ecuación se puede especializada por una selección de $m$ e $n$ a una ecuación que expresan la inconsistencia de ZFC, pero en realidad la escritura de los valores específicos lograr que la traducción sería una tarea formidable. (AGREGADO: el documento está disponible en línea en http://www.springerlink.com/content/m5k0281k67r46325/ )

J. P. Jones tiene varios trabajos, algunos con Matijasevich, proporcionando Diophantine codificaciones de otro número teórico de las declaraciones. Página web: http://math.ucalgary.ca/~jpjones/papers.htm

El papel largo por Davis, Robinson y Matijasevich da Diophantine representaciones de la Hipótesis de Riemann y de "$p$ es un número primo", de la que uno puede escribir la conjetura de Goldbach, o cerca de equivalentes de la Doble conjetura de los números Primos. La mayoría está en línea en: http://books.google.com/books?id=4lT3M6F745sC&pg=PA323

No sé si la (in)consistencia de ZFC se ha mostrado en la impresión como una ecuación de Diophantine. Puede haber programas de computación disponibles para realizar las transformaciones de ZFC analizador a la máquina de Turing para Diophantine representación, y si es así, posiblemente muy grande salida sería responder a la pregunta. Si usted está dispuesto a permitir que la exponenciación como un primitivo, como Goedel hizo en su papel, Gregory Chaitin de software disponible para la construcción de un enorme exponencial de la ecuación de Diophantine, similar a la impresa en su libro, cuyo conjunto solución es a través de algoritmos aleatorios cuando se proyectan sobre una de sus variables. El Matijasevich-Robinson codificación de $a=b^c$ podría ser aplicada, para producir una corriente, pero aún más grande, Diophantine declaración.