Teorema de Paris-Harrington

Na lógica matemática, o Teorema de Paris-Harrington afirma que um certo princípio combinatório na teoria de Ramsey, denominado Teorema Finito de Ramsey reforçado, é verdadeiro, mas não é demonstrável na Aritmética de Peano. Este foi o primeiro exemplo "natural" de uma afirmação verdadeira sobre os números inteiros que pode ser expressa na linguagem da aritmética, mas não é demonstrável na aritmética de Peano; a existência de afirmações com essa característica já era conhecida pelo Primeiro Teorema de Incompletude de Gödel.

Teorema Finito de Ramsey Reforçado

O Teorema Finito de Ramsey reforçado é uma declaração sobre coloração e números naturais, e afirma que:

"Para quaisquer inteiros positivos n, k e m tais que $m\geq n$ , podemos encontrar N com a seguinte propriedade: se colorirmos cada um dos subconjuntos de n elementos de $S=\{1,2,3,...,N\}$ com uma cor entre k cores disponíveis, então podemos encontrar um subconjunto Y de S com, pelo menos, m elementos, de tal forma que todos os subconjuntos de n elementos de Y têm a mesma cor, e o número de elementos de Y é, no mínimo, igual ao menor elemento de Y."

Sem a condição de que o número de elementos de Y é igual, no mínimo, ao menor elemento de Y, este é um corolário do teorema finito de Ramsey em $K_{{\mathcal {P}}_{n}(S)}$ , com N dado por:

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

Além disso, o teorema de Ramsey finito reforçado pode ser deduzido a partir do Teorema infinito de Ramsey quase que exatamente da mesma maneira que o teorema de Ramsey finito pode ser deduzido a partir dele, usando um argumento de compacidade. Esta prova pode ser realizada na aritmética de segunda ordem.

O teorema de Paris-Harrington afirma que o teorema de Ramsey finito reforçado não é demonstrável na aritmética de Peano.

O teorema de Paris–Harrington

A grosso modo, Jeff Paris e Leo Harrington mostraram que o teorema de Ramsey finito reforçado é indemonstrável na aritmética de Peano mostrando que esse teorema implica na própria consistência da aritmética de Peano. Como a aritmética de Peano não pode provar sua própria consistência pelo segundo teorema de Gödel, isso mostra que a aritmética de Peano não pode provar o teorema de Ramsey finito reforçada.

O menor número N que satisfaz o teorema de Ramsey finito reforçado é um função computável de n, m e k, mas cresce extremamente rápido. Em particular, não é recursiva primitiva, mas é também muito maior do que os exemplos padrões de funções não recursivas primitivas, tais como a função de Ackermann. Seu crescimento é tão grande que a aritmética de Peano não pode provar que está definida em todos os lugares, embora aritmética de Peano facilmente comprove que a função de Ackermann é bem definida.

Ver também

Referências

David Marker, Model Theory: An Introduction, ISBN 0-387-98760-6
mathworld entry
Paris, J. and Harrington, L. A Mathematical Incompleteness in Peano Arithmetic. In Handbook for Mathematical Logic (Ed. J. Barwise). Amsterdam, Netherlands: North-Holland, 1977.

Ligações externas

A brief introduction to unprovability (contains a proof of the Paris–Harrington theorem) by Andrey Bovykin.