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" verdadeiro sobre que os números inteiros que podem ser expressos em linguagem da aritmética, mas não demonstrável na aritmética de Peano; já eram conhecidas tais afirmações 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 qualquer inteiro positivo "n", "k", "M" podemos encontrar "N" com a seguinte propriedade: se colorirmos cada um dos n- subconjuntos de elementos de S= {1, 2, 3,..., N} com um dos “K” cores, então podemos encontrar um subconjunto "Y" de "S” com, pelo menos, m elementos, de tal forma que todos os "n" subconjuntos de elementos de "Y" têm a mesma cor, de tal forma que todos os "n" subconjuntos de elementos de "Y" tem a mesma cor.

Sem a condição de que o número de elementos de "Y" representa, pelo menos, o 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 (ver o artigo sobre teorema de Ramsey para mais detalhes). 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 na aritmética de Peano que essa prova implica na própria consistência da aritmética de Peano. Desde que aritmética de Peano não pode provar sua própria consistência por 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" , "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 comprova que a função de Ackermann é bem definida.

Ver também

• Teorema de Kanamori–McAloon
• Teorema de Goodstein
• Teorema da Árvore de Kruskal

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.