Conjunto diofantino

Na matemática, uma Equação diofantina é uma equação da forma P(x₁, ..., x_j, y₁, ..., y_k)=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 $\mathbb {N} ^{j}$ onde, para alguma Equação diofantina P(x,y)=0,

${\bar {n}}\in S\iff (\exists {\bar {m}}\in \mathbb {N} ^{k})(P({\bar {n}},{\bar {m}})=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 $\mathbb {Q}$ 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

A conhecida Equação de Pell

$x^{2}-d(y+1)^{2}=1$

É 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 $x,y$ precisamente quando o parâmetro $d$ é 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 $a=(2x+3)y$ somente possui solução nos $\mathbb {N}$ quando $a$ não é uma potência de 2.
• A equação $a=(x+2)(y+2)$ somente possui solução nos $\mathbb {N}$ quando $a$ é maior que 1 e não é um Número primo.
• A equação $a+x=b$ define o conjunto de pares $(a\,,\,b)$ tal que $a\leq b.\,$

Teorema de Matiyasevich

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, x₁, ..., x_k) tal que um inteiro n está em S se e somente se existem alguns inteiros x₁, ..., x_k tais que f(n, x₁, ..., x_k) = 0.

Não é difícil perceber que qualquer conjunto diofantino é enumerável: considere uma equação diofantina f(n, x₁, ..., x_k) = 0. Agora fazemos um algoritmo que simplesmente tenta todos os valores possíveis para n,x₁, ..., x_k, na ordem crescente da soma de seus valores absolutos e imprime n sempre que f(n, x₁, ..., x_k) = 0. Esse algoritmo irá obviamente rodar infinitamente e listará exatamente os n em que f(n, x₁, ..., x_k) = 0 possui uma solução em x₁, ..., x_k.

Técnica de prova

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

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

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

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

1. ^Planet Math [1]
2. ^As duas equações são equivalentes, isso pode ser provado utilizando-se o Teorema de Fermat-Lagrange.
3. 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.
4. ^David Hilbert pôs esse problema em sua célebre lista de 1900 no Congresso Internacional de Matemáticos.
5. ^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

• 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

• Artigo: Matiyasevich theorem na Scholarpedia.
• Artigo sobre Diophantine Set  no PlanetMath.