En lógica matemática , el teorema de Paris-Harrington establece que cierto principio combinatorio en la teoría de Ramsey , a saber, el teorema de Ramsey finito reforzado, es verdadero, pero no demostrable en la aritmética de Peano . Esto ha sido descrito por algunos (como el editor del Handbook of Mathematical Logic en las referencias a continuación) como el primer ejemplo "natural" de un enunciado verdadero acerca de los números enteros que podría expresarse en el lenguaje de la aritmética, pero no probado en Aritmética de peano; ya se sabía que tales afirmaciones existían por el primer teorema de incompletitud de Gödel .
Teorema de Ramsey finito reforzado
El teorema de Ramsey finito reforzado es una declaración sobre colorantes y números naturales y establece que:
- Para cualquier entero positivo n , k , m se puede encontrar N con la siguiente propiedad: si coloreamos cada uno de los subconjuntos de n elementos de S = {1, 2, 3, ..., N } con uno de k colores, entonces podemos encontrar un subconjunto y de S con al menos m elementos, de manera que todos los n subconjuntos -elemento de y tienen el mismo color, y el número de elementos de y es al menos el elemento más pequeño de y .
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 finito de Ramsey 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 (ver el artículo sobre el teorema de Ramsey para más detalles). Esta demostración se puede realizar en aritmética de segundo orden .
El teorema de París-Harrington establece que el teorema de Ramsey finito reforzado no se puede demostrar en la aritmética de Peano .
Teorema de París-Harrington
En términos generales, Jeff Paris y Leo Harrington (1977) demostraron que el teorema de Ramsey finito reforzado no se puede demostrar en la aritmética de Peano al mostrar que en la aritmética de Peano implica la consistencia de la aritmética de Peano en sí. Dado que la aritmética de Peano no puede probar su propia consistencia mediante el segundo teorema de incompletitud de Gödel , esto muestra que la aritmética de Peano no puede probar el teorema de Ramsey finito reforzado.
El número más pequeño N que satisface el teorema de Ramsey finito reforzado es una función calculable de n , m , k , pero crece extremadamente rápido. En particular, no es recursivo primitivo , pero también es mucho más grande que los ejemplos estándar de funciones recursivas no primitivas como la función de Ackermann . Su crecimiento es tan grande que la aritmética de Peano no puede probar que esté definida en todas partes, aunque la aritmética de Peano prueba fácilmente que la función de Ackermann está bien definida.
Ver también
Referencias
- Marker, David (2002). Teoría de modelos: una introducción . Nueva York: Springer. ISBN 0-387-98760-6.
- entrada de Mathworld
- Paris, J .; Harrington, L. (1977). "Una incompletitud matemática en la aritmética de Peano". En Barwise, J. (ed.). Manual de lógica matemática . Amsterdam, Países Bajos: Holanda Septentrional.
enlaces externos
- Una breve introducción a la imposibilidad de probar (contiene una prueba del teorema de París-Harrington) por Andrey Bovykin