En lógica matemática , el teorema de Paris-Harrington establece que una determinada afirmación de la teoría de Ramsey , a saber, el teorema reforzado de Ramsey finito, que se puede expresar en la aritmética de Peano , no es demostrable en este sistema. Sin embargo, esa afirmación de la teoría de Ramsey sí es demostrable en sistemas ligeramente más fuertes.
Este resultado ha sido descrito por algunos (como el editor del Handbook of Mathematical Logic en las referencias siguientes) como el primer ejemplo "natural" de un enunciado verdadero acerca de los números enteros que podía enunciarse en el lenguaje de la aritmética, pero no demostrarse en la aritmética de Peano; ya se sabía que tales enunciados existían por el primer teorema de incompletitud de Gödel .
El teorema de Ramsey finito reforzado es una afirmación sobre las coloraciones y los números naturales y establece que:
Sin la condición de que el número de elementos de Y sea al menos el elemento más pequeño de Y , este es un corolario del teorema de Ramsey finito en , con N dado por:
Además, el teorema de Ramsey finito reforzado se puede deducir del teorema de Ramsey infinito casi exactamente de la misma manera que el teorema de Ramsey finito se puede deducir de él, utilizando un argumento de compacidad (véase el artículo sobre el teorema de Ramsey para más detalles). Esta prueba se puede llevar a cabo en aritmética de segundo orden .
El teorema de París-Harrington establece que el teorema de Ramsey finito reforzado no es demostrable en la aritmética de Peano .
En términos generales, Jeff Paris y Leo Harrington (1977) demostraron que el teorema reforzado de Ramsey finito no es demostrable en la aritmética de Peano al mostrar en la aritmética de Peano que implica la consistencia de la aritmética de Peano misma. Suponiendo que la aritmética de Peano realmente es consistente, ya que la aritmética de Peano no puede demostrar su propia consistencia mediante el segundo teorema de incompletitud de Gödel , esto demuestra que la aritmética de Peano no puede demostrar el teorema reforzado de Ramsey finito.
El teorema de Ramsey finito reforzado se puede demostrar suponiendo inducción hasta para una clase relevante de fórmulas. Alternativamente, se puede demostrar suponiendo el principio de reflexión , para la teoría aritmética, para -oraciones . El principio de reflexión también implica la consistencia de la aritmética de Peano. Es demostrable en aritmética de segundo orden (o en la teoría de conjuntos de Zermelo-Fraenkel mucho más fuerte ) y, por lo tanto, es cierto en el modelo estándar.
El número más pequeño N que satisface el teorema de Ramsey finito reforzado es entonces una función computable de n , m , k , pero crece extremadamente rápido. En particular, no es recursiva primitiva , pero también crece mucho más rápido que los ejemplos estándar de funciones recursivas no primitivas como la función de Ackermann . Domina cada función computable demostrablemente total en la aritmética de Peano, [1] que incluye funciones como la función de Ackermann.
