Teorema de París-Harrington
El teorema de Paris-Harrington (o Paris-Harrington ) es un teorema de la lógica matemática , que se convirtió en el primer ejemplo natural y relativamente simple de un enunciado sobre los números naturales en la historia de las matemáticas , lo cual es cierto, pero no demostrable en la axiomática de Peano . La existencia de teoremas no demostrables en aritmética se deriva directamente del primer teorema de incompletud de Gödel (1930). Además, el segundo teorema de Gödel (publicado junto con el primero) proporciona un ejemplo concreto de dicho enunciado: a saber, el enunciado de consistencia para la aritmética. Sin embargo, durante mucho tiempo no hubo ejemplos "naturales" de dichos enunciados, es decir, enunciados que no surgieran de enunciados sobre alguna lógica, sino enunciados matemáticos naturales sobre números.
Este teorema y su demostración fueron publicados en 1977 por Geoffrey Paris (Gran Bretaña) y Leo Harrington (EE.UU.).
Teorema fuerte de Ramsey
El resultado de Paris-Harrington se basa en un teorema de Ramsey combinatorio algo modificado [1] :
|
Para cualquier número natural, se puede especificar un número natural con la siguiente propiedad: si coloreamos cada uno de los subconjuntos de elementos en uno de los colores, entonces existe un subconjunto que contiene al menos elementos tales que todos los subconjuntos de elementos tienen el mismo color , y el número de elementos no es menor que el elemento más pequeño |
Sin la condición "el número de elementos no es menor que el elemento más pequeño ", esta afirmación se deriva del teorema finito de Ramsey . Tenga en cuenta que una versión reforzada del teorema de Ramsey se puede escribir en el lenguaje de la lógica de primer orden [2] .
Redacción
El teorema de Paris-Harrington establece:
|
El teorema de Ramsey reforzado mencionado anteriormente no es demostrable en la axiomática de Peano . |
En su artículo, Paris y Harrington demostraron que la consistencia de la axiomática de Peano se deriva de este teorema ; sin embargo, como ha demostrado Gödel , la aritmética de Peano no logra demostrar su propia consistencia, por lo que el teorema de Paris-Harrington no es demostrable en ella. Por otro lado, usando la lógica de segundo orden o la axiomática de la teoría de conjuntos ZF , es fácil probar que el teorema fuerte de Ramsey es verdadero [2] .
Otros ejemplos de teoremas no demostrables en aritmética
- el teorema de goodstein
- Teorema de Kanamori-Macaloon
- Teorema del árbol de Kruskal
Notas
Literatura
- Paris J., Harrington L. Una incompletitud matemática en la aritmética de Peano // Manual de lógica matemática. - Ámsterdam: Holanda Septentrional, 1977. - ISBN 072042285X . (primera publicación del autor del teorema)
- Marcador, David. Teoría del modelo: una introducción . - Nueva York: Springer , 2002. - ISBN 0-387-98760-6 .
Enlaces
- Kochetkov Yu. Yu. Funciones computables. Capítulo 19. Teoremas no demostrables en aritmética axiomática . Recuperado: 17 Agosto 2018.
- Bovykin, Andrey, Weisstein, Eric W. Paris -Teorema de Harrington . Consultado el 17 de agosto de 2018. Disponible enMathWorld .
- BOVYKIN, Andrey . Breve introducción a la indemostrabilidad (contiene la demostración del teorema).