Teorema de Paris-Harrington

Origem: Wikipédia, a enciclopédia livre.
Saltar para a navegação Saltar para a pesquisa
Ambox important.svg
Foram assinalados vários aspectos a serem melhorados nesta página ou se(c)ção:

Na lógica matemática, o Teorema de Paris-Harrington afirma que um certo princípio combinatório na teoria de Ramsey, nomeado Teorema Finito de Ramsey reforçado, é verdade, mas não é demonstrável na Aritmética de Peano. Este foi o primeiro exemplo "natural" verdadeiro sobre os inteiros que podem ser expressas 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[editar | editar código-fonte]

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 , com N 'dado por:

Além disso, o teorema de Ramsey finito reforçado pode ser deduzido a partir do Teorema infinito de Ramsey quase exatamente da mesma maneira que o teorema de Ramsey finito pode ser deduzida 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[editar | editar código-fonte]

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[editar | editar código-fonte]

Referências[editar | editar código-fonte]

  • 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[editar | editar código-fonte]