¿Cómo se puede empezar a demostrar que un simple enunciado de la teoría de los números es indecidible?

Question

Esta pregunta está estrechamente relacionada con ésta: La intuición de Knuth de que Goldbach podría ser indemostrable . Se debe a mi ignorancia sobre los modelos no estándar de aritmética. En un comentario sobre la otra pregunta, Chandan Singh Dalawat reprodujo la siguiente cita interesante:

Hay muchos problemas antiguos en aritmética cuyo interés es prácticamente nulo, es decir, la existencia de números perfectos impar, la iteración de funciones numéricas, la existencia de infinitos primos de Fermat $2^{2^n}+1$ , etc. Algunas de estas cuestiones pueden ser ser indecidibles en aritmética; la construcción de modelos aritméticos en que las preguntas de este tipo tengan de preguntas de este tipo tengan respuestas diferentes. importancia". (Bombieri, 1976)

Lo que me gustaría saber es cómo podría ser ese modelo, aunque sea a grandes rasgos. Por ejemplo, supongamos que se quiere construir un modelo en el que sólo haya un número finito de primos de Fermat. ¿Habría que hacer algo como adjuntar un número entero no estándar N, añadir la afirmación de que todos los primos de Fermat son menores que N, y demostrar de alguna manera que eso no lleva a una contradicción? (Por lo que sé, se trata de una sugerencia obviamente errónea o incluso ridícula.) Una pregunta un poco más general es ésta: ¿es concebible que se pueda conseguir una prueba de independencia teórica de los números sin profundizar demasiado en la teoría de los números? (Lo pregunto con la expectativa, pero no fuerte, de que la respuesta sea no: que no se puede conseguir algo por nada).

Answer 1

Un método, utilizado para probar la Resultado de París-Harrington Una afirmación de la teoría de Ramsey que es independiente de PA, funciona aproximadamente como sigue. El enunciado a demostrar tiene la forma $\forall n\ \exists k\ \varphi(n,k)$ . Así, si se considera la función $f$ asignando a cada uno de ellos $n$ al menor testigo $k$ Lo que la afirmación equivale a la afirmación de que $f$ es una función total, que $f(n)$ se define para todos los $n$ .

Ahora bien, la función que surge en el resultado de Paris-Harrington es una función de crecimiento enormemente rápido, de crecimiento alucinante. La forma en que el argumento funciona, muy aproximadamente, es trabajar en un modelo no estándar $M$ de PA, pero encontrar un segmento inicial $I\lt M$ , un corte, tal que $f$ salta sobre el corte $I$ pero de manera que $I$ sigue satisfaciendo a la AP de todos modos. Así, en el modelo $I$ la función $f$ es no total, y así se tiene el modelo deseado donde la afirmación es falsa.

Answer 2

Existen varios métodos para producir modelos no estándar. Por ejemplo, mediante el método de Henkin, mediante ultraproductos o mediante cortes de otros modelos. Sin embargo, algunos de estos métodos no funcionarían muy bien para un Π ₁ declaración como la Conjetura de Goldbach. De hecho, estos enunciados se reflejan en el modelo estándar, por lo que si la Conjetura de Goldbach es cierta en cualquier modelo de aritmética, entonces debe ser cierta en el modelo estándar.

No obstante, se podría intentar producir un modelo en el que la conjetura de Goldbach sea falsa para reunir pruebas contra la conjetura. El método de Henkin es el más parecido al que describes. Procede añadiendo nuevas constantes c ₀ ,c ₁ ... al lenguaje, cada uno de los cuales se asigna para atestiguar un cuantificador existencial en un proceso infinito por el que se decide la verdad de todas las oraciones del lenguaje. Para iniciar el proceso, podríamos decidir que c ₀ es un número entero par que no es la suma de dos primos Impares. Para atestiguar esto, podríamos declarar más adelante que c ₀ \= 2c ₁₇ para asegurarse de que c ₀ está en paz. Entonces, para cada término t que surja en el camino, añadiremos testigos del hecho de que o bien t > c ₀ o una de t y c ₀ - t tiene un factor no trivial, cualquiera que no contradiga el estado actual de las cosas. Y así sucesivamente para todas las sentencias, incluidas las que no están relacionadas con la Conjetura de Goldbach. Con una contabilidad cuidadosa, si nuestros axiomas no son contradictorios, esto logrará producir un modelo de términos de nuestros axiomas. (Al final, hay que modelar por la relación de equivalencia de la igualdad demostrable, pero esos detalles es mejor dejarlos para los libros de texto de lógica estándar). Desgraciadamente, sin una visión extraordinaria, no tenemos básicamente ninguna idea de cómo será la estructura final.

Hay métodos más directos que funcionan para subsistemas más débiles de la aritmética. Por ejemplo, el método de Shepherdson tiene mucho éxito en la producción de modelos de inducción abierta. Describí este método en un respuesta anterior . De hecho, Macintyre y Marker [ Los primos y sus anillos de residuos en los modelos de inducción abierta , MR1001418 ] han refinado el método de Shepherdson para producir algunos modelos no estándar muy curiosos de inducción abierta. En uno de estos modelos, todos los primos no estándar son congruentes con 3 mod 4, y en otro cada entero par no estándar es la suma de dos primos. Como la inducción abierta es muy, muy débil, no se pueden sacar muchas conclusiones de esto, pero los modelos en cuestión son muy concretos.

Answer 3

He visto esta pregunta justo después de publicar una especie de respuesta en el debate anterior:

La intuición de Knuth de que Goldbach podría ser indemostrable

Hasta donde yo sé, el método de la "función de crecimiento rápido" no es fundamentalmente diferente de la técnica de "el enunciado permite que la teoría construya un modelo de sí misma". Se trata de una interpretación de este último método, aportada originalmente por Ketonen y Solovay como una forma más transparente de entender la prueba de Paris-Harrington (que mostraba que a partir de la función finitaria implicada por su variante del teorema de Ramsey, se podía construir un modelo de la Aritmética de Peano, y esta construcción podía realizarse a su vez en PA).

Para encontrar un modelo de PA (o ZF, u otro sistema formal expresivo) dentro de un problema dado como el de Goldbach, tiene que soportar la combinatoria implicada en esos sistemas formales, como los ordinales de la teoría de la prueba hasta $\epsilon_0$ o $\Gamma_0$ o la combinatoria de grandes cardinales, como en la obra de Friedman. Los teoremas de Paris-Harrington, Friedman y otros que son indemostrables en sistemas específicos se refieren a estructuras de ingeniería inversa de la combinatoria que aparece en la lógica matemática.

Por lo tanto, para obtener la improbabilidad de PA a partir de las conjeturas de Goldbach o Riemann habría que relacionar de algún modo la distribución de números primos con la combinatoria extremadamente rígida de (1) los modelos de PA, (2) la sintaxis de PA como sistema de prueba formal, o (3) $\epsilon_0$ y el análisis ordinal teórico de la prueba de AP. Esto sólo ocurre si cosas como las conjeturas de Weil y la hipótesis de Riemann son la punta más pequeña de un iceberg estructural en la teoría de los números, o, alternativamente, si las relaciones demostrables con los sistemas formales aparecen genéricamente en montones de problemas en toda la matemática, en cuyo caso hay una máquina para resolver un gran número de problemas abiertos (por ejemplo, en ZF) en el camino para demostrar su incomprobabilidad en PA.

EDIT: con respecto a la discusión de abajo sobre las funciones de crecimiento rápido que no parecen aparecer en Goldbach, no es necesario que la/las funciones de Goldbach $g(n)$ implícita en la conjetura sea de crecimiento rápido, sólo que la Aritmética de Peano sea capaz de construir a partir de $g(n)$ algo más que es rápido. Por ejemplo, si se observa el conjunto de $n$ tal que $g(n) = 3$ En el caso de los primos gemelos, se trata de una sucesión de algo análogo a los primos gemelos, y es posible que crezca muy rápido si PA no puede demostrar la conjetura de los primos gemelos o sus similares.

Answer 4

Joel David Hamkins y Francois Dorais ya han explicado que una de las principales técnicas para establecer la indemostrabilidad en PA es encontrar alguna función de crecimiento rápido oculta en tu problema, que crezca tan rápido que PA no pueda demostrar que es total.

Vale la pena mencionar que Harvey Friedman ha estado desarrollando durante muchos años un enfoque bastante diferente para establecer la improbabilidad de los enunciados de la teoría de los números en ZFC. En su artículo "Finite functions and the necessary use de los cardinales grandes". Ann. Math. 148 (1998), 803-893, Friedman escribe:

La estrategia general para usar cardinales grandes en los enteros es la siguiente. Empezamos con una estructura discreta (o finita) $X$ que obedece a determinadas hipótesis $H$ . Queremos demostrar que un cierto tipo de configuración finita se da en $X$ , suponiendo que $H$ sostiene. Definimos un concepto adecuado de terminación en el contexto de conjuntos arbitrarios conjuntos ordenados linealmente. Comprobamos que si $X$ tiene una terminación con el tipo de configuración finita deseada, entonces $X$ ya tiene el tipo de configuración tipo de configuración finita. A continuación, demostramos, mediante hipótesis $H$ , que $X$ tiene terminaciones de cada tipo bien ordenado. Ahora utilizamos la existencia de un cardinal convenientemente grande $\lambda$ . Utilizando la combinatoria de grandes cardinales mostramos que en cualquier terminación de tipo de orden $\lambda$ , existe el tipo de configuración finita deseada. Por lo tanto, el tipo de configuración tipo de configuración finita ya existe en $X$ .

El punto clave aquí es que los cardenales grandes, a pesar de su naturaleza aparentemente exótica, contienen una estructura combinatoria concreta que implica la existencia de ciertos tipos de finito estructuras combinatorias. Si encuentra estas estructuras ocultas en su conjetura teórica de los números, entonces podría demostrar que su conjetura requiere grandes axiomas cardinales para ser demostrada.

Me gustaría volver a insistir en algo que dije en mi respuesta a la otra pregunta de MO que mencionaste. Creo que no hay básicamente ninguna razón para pensar que el intratabilidad de una conjetura proporciona evidencia de su improbabilidad . Además, si una conjetura es intratable, es probable que su supuesta improbabilidad también lo sea. Para establecer la improbabilidad a partir de PA o ZFC, debe utilizar alguna propiedad de PA o ZFC que esté relacionada de alguna manera con la estructura que está conjeturando . Necesita alguna indicación de alguna función de crecimiento rápido o combinatoria de tipo cardinal grande o algo . De lo contrario, no hay razón para sospechar que pueda establecer la indemostrabilidad.

Answer 5

Yo tenía preguntas similares, y después de dar tumbos durante mucho tiempo descubrí que el libro de Kaye Modelos de aritmética de Peano es prácticamente el primer libro que hay que leer si se quiere empezar a construir modelos no estándar con propiedades particulares (hay mucha otra literatura, pero el libro de Kaye parece ser el único introductorio). En particular, la sección 14.3 cubre el material que @Joel discute en su respuesta.