Conjunto diofantino - Diophantine set

Em matemática , uma equação diofantina é uma equação da forma P ( x ₁ , ..., x _j , y ₁ , ..., y _k ) = 0 (geralmente abreviado P ( x , y ) = 0) onde P ( x , y ) é um polinômio com coeficientes inteiros , onde x ₁ , ..., x _j indicam parâmetros ey ₁ , ..., y _k indicam incógnitas.

Um conjunto Diofantino é um subconjunto S de N ^{j de} modo que para alguma equação Diofantina P ( x , y ) = 0,

${\ displaystyle {\ bar {n}} \ in S \ iff (\ exists {\ bar {m}} \ in \ mathbb {N} ^ {k}) (P ({\ bar {n}}, {\ bar {m}}) = 0).}$

Ou seja, um valor de parâmetro está no conjunto Diofantino S se e somente se a equação Diofantina associada for satisfatória sob esse valor de parâmetro. O uso de números naturais tanto em S quanto na quantificação existencial meramente reflete as aplicações usuais em computabilidade e teoria de modelos. Podemos igualmente falar de conjuntos diofantinos de inteiros e substituir livremente a quantificação sobre os números naturais pela quantificação sobre os inteiros. Também é suficiente assumir que P é um polinômio e multiplicar P pelos denominadores apropriados para produzir coeficientes inteiros. No entanto, se a quantificação sobre os racionais também pode ser substituída pela quantificação sobre os inteiros é um problema aberto notoriamente difícil. ${\ displaystyle \ mathbb {Q}}$

O teorema MRDP afirma que um conjunto de inteiros é Diofantino se, e somente se, for computavelmente enumerável . Um conjunto de inteiros S é computávelmente enumerável se e somente se houver um algoritmo que, quando dado um inteiro, pára se esse inteiro for um membro de S e roda para sempre de outra forma. Isso significa que o conceito de conjunto diofantino geral, aparentemente pertencente à teoria dos números , pode ser considerado em termos lógicos ou teóricos de recursão. Isso está longe de ser óbvio, porém, e representou o culminar de algumas décadas de trabalho.

A conclusão do teorema MRDP por Matiyasevich resolveu o décimo problema de Hilbert . O décimo problema de Hilbert era encontrar um algoritmo geral que pudesse decidir se uma dada equação diofantina tinha uma solução entre os inteiros. Embora o décimo problema de Hilbert não seja uma afirmação matemática formal como tal, a aceitação quase universal da identificação (filosófica) de um algoritmo de decisão com um predicado computável total nos permite usar o teorema MRDP para concluir que o décimo problema é insolúvel.

Exemplos

A equação de Pell

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

é um exemplo de uma equação diofantina com um parâmetro. A equação tem solução nas incógnitas precisamente quando o parâmetro é 0 ou não é um quadrado perfeito . Ou seja, esta equação fornece uma definição diofantina do conjunto ${\ displaystyle x, y}$${\ displaystyle d}$

{0,2,3,5,6,7,8,10, ...}

consistindo em 0 e os números naturais que não são quadrados perfeitos.

Outros exemplos de definições diofantinas são as seguintes:

• A equação só tem soluções quando a não é uma potência de 2.${\ displaystyle a = (2x + 3) y}$${\ displaystyle \ mathbb {N}}$
• A equação só tem soluções quando a é maior que 1 e não é um número primo .${\ displaystyle a = (x + 2) (y + 2)}$${\ displaystyle \ mathbb {N}}$
• A equação define o conjunto de pares de tal forma que${\ displaystyle a + x = b}$${\ displaystyle (a \ ,, \, b)}$${\ displaystyle a \ leq b.}$

Teorema de Matiyasevich

O teorema de Matiyasevich, também chamado de Teorema de Matiyasevich - Robinson - Davis - Putnam ou MRDP, diz:

Todo conjunto computável enumerável é Diofantino, e vice-versa.

Um conjunto S de inteiros é computávelmente enumerável se houver um algoritmo tal que: Para cada entrada de inteiro n , se n for membro de S , então o algoritmo eventualmente para; caso contrário, ele funcionará para sempre. Isso equivale a dizer que há um algoritmo que corre para sempre e lista os membros de S . Um conjunto S é diofantino precisamente se houver algum polinômio com coeficientes inteiros f ( n , x ₁ , ..., x _k ) de modo que um inteiro n esteja em S se e somente se existirem alguns inteiros x ₁ , ... , x _{k de} modo que f ( n , x ₁ , ..., x _k ) = 0.

Por outro lado, cada conjunto diofantino é computávelmente 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 (em, digamos, alguma ordem simples consistente com a ordem crescente da soma de seus valores absolutos), e imprime n toda vez que f ( n , x ₁ , ..., x _k ) = 0. Este algoritmo irá obviamente executará para sempre e listará exatamente o n para o qual f ( n , x ₁ , ..., x _k ) = 0 tem uma solução em x ₁ , ..., x _k .

Técnica de prova

Yuri Matiyasevich utilizou um método envolvendo números de Fibonacci , que crescem exponencialmente , para mostrar que as soluções para as equações diofantinas podem crescer exponencialmente . Trabalhos anteriores de Julia Robinson , Martin Davis e Hilary Putnam - portanto, MRDP - mostraram que isso é suficiente para mostrar que todo conjunto computável enumerável é Diofantino.

Aplicação ao décimo problema de Hilbert

O décimo problema de Hilbert pede um algoritmo geral para decidir a solubilidade das equações diofantinas. A conjunção do resultado de Matiyasevich com o fato de que a maioria das linguagens recursivamente enumeráveis não são decidíveis implica que uma solução para o décimo problema de Hilbert é impossível.

Refinamentos

Trabalhos posteriores mostraram que a questão da solubilidade de uma equação diofantina é indecidível, mesmo que a equação tenha apenas 9 variáveis ​​numéricas naturais (Matiyasevich, 1977) ou 11 variáveis ​​inteiras ( Zhi Wei Sun , 1992).

Outras aplicações

O teorema de Matiyasevich desde então tem sido usado para provar que muitos problemas de cálculo e equações diferenciais são insolúveis.

Também se pode derivar a seguinte forma mais forte do primeiro teorema da incompletude de Gödel a partir do resultado de Matiyasevich:

Correspondendo a qualquer axiomatização consistente dada da teoria dos números, pode-se construir explicitamente uma equação diofantina que não tem soluções, mas tal que esse fato não pode ser provado dentro da axiomatização dada.

De acordo com os teoremas da incompletude , uma teoria axiomática consistente e poderosa é incompleta, o que significa que a verdade de algumas de suas proposições não pode ser estabelecida dentro de seu formalismo. A afirmação acima diz que essa incompletude deve incluir a solubilidade de uma equação diofantina, supondo que a teoria em questão seja uma teoria dos números.

Notas

Referências

• Matiyasevich, Yuri V. (1970). Диофантовость перечислимых множеств[Enumeráveis ​​conjuntos são diofantinos]. Doklady Akademii Nauk SSSR (em russo). 191 : 279–282. MR  0258744 .Tradução para o inglês em Soviet Mathematics 11 (2), pp. 354-357.
• Davis, Martin (1973). "O décimo problema de Hilbert é insolúvel". American Mathematical Monthly . 80 : 233–269. doi : 10.2307 / 2318447 . ISSN  0002-9890 . Zbl  0277.02008 .
• Matiyasevich, Yuri V. (1993). O décimo problema de Hilbert . MIT Press Series in the Foundations of Computing. Prefácio de Martin Davis e Hilary Putnam. Cambridge, MA: MIT Press. ISBN 0-262-13295-8. Zbl  0790.03008 .
• Shlapentokh, Alexandra (2007). O décimo problema de Hilbert. Classes diofantinas e extensões para campos globais . Novas monografias matemáticas. 7 . Cambridge: Cambridge University Press . ISBN 0-521-83360-4. Zbl  1196.11166 .
• Sun Zhi-Wei (1992). "Redução de incógnitas nas representações diofantinas" (PDF) . Science China Mathematics . 35 (3): 257–269. Zbl  0773.11077 .

links externos

• Artigo sobre o teorema de Matiyasevich na Scholarpedia .
• Artigo do Conjunto Diofantino no PlanetMath .