Conjunto diofantino
Na matemática, uma Equação diofantina é uma equação da forma P(x1, ..., xj, y1, ..., yk)=0 (usualmente abreviada para P(x,y)=0 ) onde P(x,y) é um polinômio com coeficientes inteiros. Um conjunto Diofantino é um subconjunto S de onde, para alguma Equação diofantina P(x,y)=0,
Isto é, um valor de parâmetro está no conjunto diofantino se e somente se a equação diofantina associada é satisfatível sob esse valor. Note que o uso de números naturais em S e a quantificação existencial reflete meramente a aplicação usual na computabilidade e na teoria do modelo. Podemos igualmente falar sobre conjuntos diofantinos de inteiros e substituir livremente a quantificação por números naturais com quantificação sobre os inteiros. Ainda é suficiente assumir que P é um polinômio sobre e multiplicar P pelos determinadores apropriados para produzir coeficientes inteiros. Entretanto, se a quantificação sobre racionais também pode ser substituída pela quantificação sobre inteiros ainda é um problema notoriamente difícil.
O teorema MRDP afirma que um conjunto de inteiros é diofantino se e somente se ele for computavelmente enumerável. Um conjunto de inteiros S é computavelmente enumerável se e somente se existe um algoritmo que, quando dado um inteiro, para se aquele inteiro é membro de S e prossegue infinitamente caso contrário. Isso significa que o conceito de conjunto diofantino geral, aparentemente pertencente à Teoria dos números, pode ser tomado preferencialmente em termos lógicos ou recursão-teóricos. Isso está longe de ser óbvio e representou a culminação de algumas décadas de estudo.
A realização do teorema MRDP por Matiyasevich estabeleceu o Décimo problema de Hilbert. Esse problema envolvia descobrir um algoritmo geral que conseguiria decidir se uma dada equação diofantina possui solução dentre os inteiros. Enquanto o Décimo problema de Hilbert não é uma afirmação matemática formal, a aceitação quase universal da identificação (filosófica) de um algoritmo de decisão com um predicado computável total nos permite o uso do teorema MRDP para concluir que o décimo problema é insolúvel.
Exemplos
[editar | editar código-fonte]A conhecida Equação de Pell
É um exemplo de uma equação diofantina com um parâmetro. Como é há muito conhecido, a equação tem uma solução nas variáveis precisamente quando o parâmetro é 0 ou não é um Quadrado perfeito. No contexto presente, diz-se que essa equação fornece a definição Diofantina do conjunto
- {0,2,3,5,6,7,8,10,...}
que consiste do 0 e dos números naturais que não são quadrados perfeitos. Aqui estão outros exemplos de definição diofantina:
- A equação somente possui solução nos quando não é uma potência de 2.
- A equação somente possui solução nos quando é maior que 1 e não é um Número primo.
- A equação define o conjunto de pares tal que
Teorema de Matiyasevich
[editar | editar código-fonte]O teorema de Matiyasevich diz que:
- Qualquer conjunto computavelmente enumerável é Diofantino.
Um conjunto S de inteiros é computavelmente enumerável se existe um algoritmo tal que: Para cada inteiro de entrada n, se n pertence a S, então o algoritmo parará eventualmente; caso contrário, continuará infinitamente. Isso é equivalente a dizer que existe um algoritmo que funciona infinitamente e lista os elementos de S. Um conjunto S é Diofantino precisamente se existe algum polinômio com coeficientes inteiros f(n, x1, ..., xk) tal que um inteiro n está em S se e somente se existem alguns inteiros x1, ..., xk tais que f(n, x1, ..., xk) = 0.
Não é difícil perceber que qualquer conjunto diofantino é enumerável: considere uma equação diofantina f(n, x1, ..., xk) = 0. Agora fazemos um algoritmo que simplesmente tenta todos os valores possíveis para n,x1, ..., xk, na ordem crescente da soma de seus valores absolutos e imprime n sempre que f(n, x1, ..., xk) = 0. Esse algoritmo irá obviamente rodar infinitamente e listará exatamente os n em que f(n, x1, ..., xk) = 0 possui uma solução em x1, ..., xk.
Técnica de prova
[editar | editar código-fonte]Yuri Matiyasevich utilizou um método envolvendo os números de FIbonacci para mostrar que as soluções para equações diofantinas podem crescer exponencialmente. Um estudo anterior realizado por Julia Robinson, Martin Davis e Hillary Putnam havia mostrado que isso é o bastante para mostrar que qualquer conjunto computavelmente enumerável é Diofantino.
Aplicações para o Décimo problema de Hilbert
[editar | editar código-fonte]O Décimo problema de Hilbert procura um algoritmo geral que decide se uma equação diofantina é solúvel ou não. A conjunção do teorema de Matiyasevich com resultados anteriores conhecidos coletivamente como o teorema MRDP implica que a solução para o décimo problema de Hilbert é impossível.
Refinamentos
[editar | editar código-fonte]Estudos posteriores mostraram que a questão da solubilidade de uma equação diofantina não é possível ser decidida mesmo se a equação contém apenas 9 variáveis de números naturais (Matiyasevich, 1977) ou 11 variáveis inteiras (Zhi Wei Sun,1992).
Mais aplicações
[editar | editar código-fonte]O teorema de Matiyasevich foi usado para provar que muitos problemas de cálculo e equações diferenciais são insolúveis.
É possível derivar a seguinte forma mais forte do primeiro dos Teoremas da incompletude de Gödel do resultado de Matiyasevich:
- Correspondendo a qualquer axiomatização consistente da teoria dos números, é possível construir explicitamente a equação diofantina que não possui soluções, mas da forma que esse fato não pode ser provado dado uma determinada axiomatização.
De acordo com os teoremas da incompletude, uma teoria consistente é incompleta, significando que a verdade de algumas proposições não pode ser estabelecida. A afirmação acima diz que a incompletude precisa incluir a solubilidade de uma equação diofantina, assumindo que a teoria em questão é a teoria dos números.
Notas
[editar | editar código-fonte]- ^Planet Math [1]
- ^As duas equações são equivalentes, isso pode ser provado utilizando-se o Teorema de Fermat-Lagrange.
- O teorema foi estabelecido em 1970 por Matiyaseviche por isso também é conhecido como teorema de Matiyasevich. Porém a prova dada por Matiyasevich se apoiava extensivamente em estudos prévios sobre o problema e por isso a comunidade matemática passou a chamar o resultado da equivalência de teorema MRDP ou teorema de Matiyasevich-Robinson-Davis-Putnam, um nome que dá crédito a todos os matemáticos que deram contribuições significativas para esse teorema.
- ^David Hilbert pôs esse problema em sua célebre lista de 1900 no Congresso Internacional de Matemáticos.
- ^Mais precisamente dada uma fórmula Σ representando o conjunto de números de Gödel numbers de sentenças que axiomatizam recursivamente o teorema consistente da aritmética de Robinson.
Referências
[editar | editar código-fonte]- Matiyasevich, Yuri V. (1970). Диофантовость перечислимых множеств [Enumerable sets are Diophantine]. Doklady Akademii Nauk SSSR (em russo). 191: 279–282. MR 0258744 English translation in Soviet Mathematics 11 (2), pp. 354–357.
- Davis, Martin (1973). «Hilbert's Tenth Problem is Unsolvable». American Mathematical Monthly. 80: 233–269. ISSN 0002-9890. Zbl 0277.02008. doi:10.2307/2318447
- Matiyasevich, Yuri V. (1993). Hilbert's 10th Problem. Col: MIT Press Series in the Foundations of Computing. Foreword by Martin Davis and Hilary Putnam. Cambridge, MA: MIT Press. ISBN 0-262-13295-8. Zbl 0790.03008
- Shlapentokh, Alexandra (2007). Hilbert's tenth problem. Diophantine classes and extensions to global fields. Col: New Mathematical Monographs. 7. Cambridge: Cambridge University Press. ISBN 0-521-83360-4. Zbl 1196.11166
- Sun Zhi-Wei (1992). «Reduction of unknowns in Diophantine representations» (PDF). Science China Mathematics. 35 (3): 257–269. Zbl 0773.11077
Ligações externas
[editar | editar código-fonte]- Artigo: Matiyasevich theorem na Scholarpedia.
- Artigo sobre Diophantine Set no PlanetMath.