Teorema de Paris-Harrington – Wikipédia, a enciclopédia livre

Foram assinalados vários problemas nesta página ou se(c)ção: As fontes não são citadas no corpo do artigo, o que compromente a verificabilidade. Precisa de correção textual.

Na lógica matemática, o Teorema de Paris-Harrington afirma que 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. Afirmações com essa característica já eram conhecidas pelo Primeiro Teorema de Incompletude de Gödel.

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 ${\displaystyle m\geq n}$, podemos encontrar N com a seguinte propriedade: se colorirmos cada um dos subconjuntos de n elementos de ${\displaystyle 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 ${\displaystyle K_{{\mathcal {P}}_{n}(S)}}$, com N dado por:

${\displaystyle {\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 de forma parecida, 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.

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 esta 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. Cresce tão rápido 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.

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

• 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.

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