Principio de Paris-Harrington

En lógica matemática, el principio de Paris-Harrington establece que un cierto principio combinatorio en la teoría de Ramsey, a saber, el teorema de Ramsey finito reforzado, que se puede expresar en la aritmética de Peano, no es demostrable en este sistema. Sin embargo, el principio combinatorio se puede demostrar 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 una afirmación verdadera sobre los números enteros que podría expresarse en el lenguaje de la aritmética, pero no demostrarse. en aritmética de Peano; ya se sabía que tales afirmaciones existían según el primer teorema de incompletitud de Gödel.

Teorema de Ramsey finito reforzado

El teorema finito reforzado de Ramsey es una afirmación sobre coloraciones y números naturales y establece que:

Para cualquier número entero positivo n, k, m, tal que m ≥ n, se puede encontrar N con la siguiente propiedad: si coloreamos cada uno de los n subconjuntos de 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, tal que todos los n subconjuntos de elementos de Y tengan el mismo color, y el número de elementos de Y sea 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 $K_{{\mathcal {P}}_{n}(S)}$ , con N dado por:

{\binom {N}{n}}=|{\mathcal {P}}_{n}(S)|\geq R(\,\underbrace {m,m,\ldots ,m} _{k}\,).

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 (consulte el artículo sobre el teorema de Ramsey para obtener más detalles). Esta demostración se puede realizar en aritmética de segundo orden.

El teorema de Paris-Harrington establece que el teorema finito reforzado de Ramsey no es demostrable en aritmética de Peano.

Teorema de París-Harrington

En términos generales, Jeff Paris y Leo Harrington (1977) demostraron que el teorema finito reforzado de Ramsey no es demostrable en la aritmética de Peano al mostrar que en la aritmética de Peano implica la consistencia de la propia aritmética de Peano. 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 finito reforzado de Ramsey.

El principio combinatorio se puede demostrar asumiendo inducción hasta $\varepsilon _{0}$ para clases relevantes de fórmulas. Alternativamente, se puede demostrar asumiendo el principio de reflexión, para la teoría aritmética, para $\Sigma _{1}^{0}$ -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 mucho más sólida teoría de conjuntos de Zermelo-Fraenkel) y también lo es en el modelo estándar.

El número más pequeño N que satisface el teorema finito reforzado de Ramsey es entonces una función computable de n, m, k, pero crece extremadamente rápido. En particular, no es recursiva primitiva, 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 demostrar que esté definida en todas partes, aunque la aritmética de Peano demuestra fácilmente que la función de Ackermann está bien definida.

Véase también

Teorema de Goodstein
Teorema de Kanamori-McAloon
Teorema del árbol de Kruskal

Referencias

Marker, David (2002). Model Theory: An Introduction. New York: Springer. ISBN 0-387-98760-6.
Paris, J.; Harrington, L. (1977). «A Mathematical Incompleteness in Peano Arithmetic». En Barwise, J., ed. Handbook of Mathematical Logic. Amsterdam, Netherlands: North-Holland.

Enlaces externos

A brief introduction to unprovability (contiene una prueba del teorema de Paris-Harrington) por Andrey Bovykin
Torres del Valle, Joel; Vásquez Ávila, María Ofelia (2019). «Sobre incompletitud en matemáticas y el Principio de Paris-Harrington». Boletín de matemáticas 26 (2): 113-118. ISSN 2357-6529.
Teorema de Paris-Harrington en Mathworld
Esta obra contiene una traducción derivada de «Paris-Harrington Theorem» de Wikipedia en inglés, concretamente de esta versión del 30 de marzo de 2023, publicada por sus editores bajo la Licencia de documentación libre de GNU y la Licencia Creative Commons Atribución-CompartirIgual 4.0 Internacional.