Décimo problema de Hilbert - Hilbert's tenth problem

O décimo problema de Hilbert é o décimo na lista de problemas matemáticos que o matemático alemão David Hilbert propôs em 1900. É o desafio de fornecer um algoritmo geral que, para qualquer equação diofantina dada (uma equação polinomial com coeficientes inteiros e um número finito de incógnitas), pode decidir se a equação tem uma solução com todas as incógnitas assumindo valores inteiros.

Por exemplo, a equação Diofantina tem uma solução inteiro: . Em contraste, a equação diofantina não tem essa solução. ${\ displaystyle 3x ^ {2} -2xy-y ^ {2} z-7 = 0}$ ${\ displaystyle x = 1, \ y = 2, \ z = -2}$ ${\ displaystyle x ^ {2} + y ^ {2} + 1 = 0}$

O décimo problema de Hilbert foi resolvido e tem uma resposta negativa: tal algoritmo geral não existe. Este é o resultado do trabalho combinado de Martin Davis , Yuri Matiyasevich , Hilary Putnam e Julia Robinson que abrange 21 anos, com Matiyasevich completando o teorema em 1970. O teorema é agora conhecido como teorema de Matiyasevich ou teorema MRDP.

Fundo

Formulação original

Hilbert formulou o problema da seguinte maneira:

Dada uma equação Diofantina com qualquer número de quantidades desconhecidas e com coeficientes numéricos integrais racionais: Para conceber um processo segundo o qual pode ser determinado em um número finito de operações se a equação é resolvível em inteiros racionais.

As palavras "processo" e "número finito de operações" significam que Hilbert estava pedindo um algoritmo . O termo "número inteiro racional" simplesmente se refere a números inteiros, positivos, negativos ou zero: 0, ± 1, ± 2, .... Então, Hilbert estava pedindo um algoritmo geral para decidir se uma dada equação diofantina polinomial com coeficientes inteiros tem uma solução em inteiros.

O problema de Hilbert não está preocupado em encontrar as soluções. Ele apenas pergunta se, em geral, podemos decidir se uma ou mais soluções existem. A resposta a esta pergunta é negativa, no sentido de que nenhum "processo pode ser planejado" para responder a essa pergunta. Em termos modernos, o décimo problema de Hilbert é um problema indecidível . Embora seja improvável que Hilbert tivesse concebido tal possibilidade, antes de continuar a listar os problemas, ele observou de forma presciente:

Ocasionalmente acontece que buscamos a solução sob hipóteses insuficientes ou em um sentido incorreto, e por isso não obtemos sucesso. Surge então o problema: mostrar a impossibilidade da solução nas hipóteses dadas ou no sentido contemplado.

Provar que o 10º problema é indecidível é então uma resposta válida mesmo nos termos de Hilbert, uma vez que é uma prova sobre "a impossibilidade da solução".

Conjuntos diofantinos

Em uma equação diofantina, existem dois tipos de variáveis: os parâmetros e as incógnitas. O conjunto Diofantino consiste nas atribuições de parâmetros para os quais a equação Diofantina é solucionável. Um exemplo típico é a equação diofantina linear em duas incógnitas,

{\ displaystyle a_ {1} x_ {1} + a_ {2} x_ {2} = a_ {3}}

,

onde a equação é solucionável quando o maior divisor comum de se divide . Os valores para que satisfaçam esta restrição são um conjunto Diofantino e a equação acima é a sua definição Diofantina. ${\ displaystyle a_ {1}, a_ {2}}$ ${\ displaystyle a_ {3}}$ ${\ displaystyle a_ {1}, a_ {2}, a_ {3}}$

As definições diofantinas podem ser fornecidas por sistemas simultâneos de equações, bem como por equações individuais, porque o sistema

{\ displaystyle p_ {1} = 0, \ ldots, p_ {k} = 0}

é equivalente à única equação

{\ displaystyle p_ {1} ^ {2} + \ cdots + p_ {k} ^ {2} = 0.}

Conjuntos de números naturais, de pares de números naturais (ou mesmo de n- duplas de números naturais) que têm definições diofantinas são chamados conjuntos diofantinos . Nestes termos, o décimo problema de Hilbert pergunta se existe um algoritmo para determinar se um determinado conjunto Diofantino não é vazio.

O trabalho sobre o problema tem sido em termos de soluções em números naturais (entendidos como inteiros não negativos) em vez de inteiros arbitrários. Os dois problemas são equivalentes: qualquer algoritmo geral que pode decidir se uma dada equação diofantina tem uma solução inteira pode ser modificado em um algoritmo que decide se uma dada equação diofantina tem uma solução numérica natural e vice-versa. Isso pode ser visto da seguinte forma: O requisito de que as soluções sejam números naturais pode ser expresso com a ajuda do teorema dos quatro quadrados de Lagrange : todo número natural é a soma dos quadrados de quatro inteiros, então simplesmente substituímos cada parâmetro pela soma de quadrados de quatro parâmetros extras. Da mesma forma, como cada número inteiro pode ser escrito como a diferença de dois números naturais, podemos substituir cada parâmetro que varia em números inteiros pela diferença de dois parâmetros que variam em números naturais.

Conjuntos recursivamente enumeráveis

Um conjunto recursivamente enumerável pode ser caracterizado como aquele para o qual existe um algoritmo que irá parar quando um membro do conjunto for fornecido como entrada, mas pode continuar indefinidamente quando a entrada for um não membro. Foi o desenvolvimento da teoria da computabilidade (também conhecida como teoria da recursão) que forneceu uma explicação precisa da noção intuitiva de computabilidade algorítmica, tornando assim a noção de enumerabilidade recursiva perfeitamente rigorosa. É evidente que os conjuntos diofantinos são recursivamente enumeráveis. Isso ocorre porque é possível organizar todas as tuplas possíveis de valores das incógnitas em uma sequência e então, para um determinado valor do (s) parâmetro (s), testar essas tuplas, uma após a outra, para ver se são soluções da equação correspondente. A impossibilidade de solução do décimo problema de Hilbert é uma consequência do fato surpreendente de que o inverso é verdadeiro:

Todo conjunto recursivamente enumerável é Diofantino.

Esse resultado é conhecido como teorema de Matiyasevich (porque ele forneceu a etapa crucial que completou a prova) e teorema MRDP (para Yuri Matiyasevich , Julia Robinson , Martin Davis e Hilary Putnam ). Como existe um conjunto recursivamente enumerável que não é computável, a impossibilidade de solução do décimo problema de Hilbert é uma consequência imediata. Na verdade, mais pode ser dito: há um polinômio

{\ displaystyle p (a, x_ {1}, \ ldots, x_ {n})}

com coeficientes inteiros de modo que o conjunto de valores para os quais a equação ${\ displaystyle a}$

{\ displaystyle p (a, x_ {1}, \ ldots, x_ {n}) = 0}

tem soluções em números naturais não é computável. Portanto, não apenas não existe um algoritmo geral para testar as equações diofantinas quanto à solubilidade, mesmo para esta família de equações de um parâmetro, não há algoritmo.

História

Ano	Eventos
1944	Emil Leon Post declara que o décimo problema de Hilbert "implora por uma prova de insolvência".
1949	Martin Davis usa o método de Kurt Gödel para aplicar o teorema do resto chinês como um truque de codificação para obter sua forma normal para conjuntos recursivamente enumeráveis: ${\ displaystyle \ left \ {a \ mid \ exists y \ forall k \ leqslant y \ existe x_ {1}, \ ldots, x_ {n}: p \ left (a, k, y, x_ {1}, \ ldots, x_ {n} \ right) = 0 \ right \}}$ onde é um polinômio com coeficientes inteiros. Puramente formalmente, é apenas o quantificador universal limitado que impede que esta seja uma definição diofantina. ${\ displaystyle p}$ Usando uma prova não construtiva, mas fácil, ele deriva como corolário dessa forma normal que o conjunto de conjuntos diofantinos não é fechado sob complementação, mostrando que existe um conjunto diofantino cujo complemento não é diofantino. Como os conjuntos recursivamente enumeráveis também não são fechados sob complementação, ele conjectura que as duas classes são idênticas.
1950	Julia Robinson , sem saber do trabalho de Davis, investiga a conexão da função exponencial com o problema e tenta provar que EXP, o conjunto de trigêmeos para o qual , é Diofantino. Sem sucesso, ela faz a seguinte hipótese (mais tarde chamada de JR): ${\ displaystyle (a, b, c)}$ ${\ displaystyle a = b ^ {c}}$ Existe um conjunto diofantino de pares tal que e para cada positivo existe tal que ${\ displaystyle D}$ ${\ displaystyle (a, b)}$ ${\ displaystyle (a, b) \ in D \ Rightarrow b <a ^ {a}}$ ${\ displaystyle k,}$ ${\ displaystyle (a, b) \ in D}$ ${\ displaystyle b> a ^ {k}.}$ Usando propriedades da equação de Pell, ela prova que JR implica que EXP é Diofantino, assim como os coeficientes binomiais, o fatorial e os primos.
1959	Trabalhando juntos, Davis e Putnam estudam conjuntos diofantinos exponenciais : conjuntos definíveis por equações diofantinas em que alguns dos expoentes podem ser desconhecidos. Usando a forma normal de Davis junto com os métodos de Robinson, e assumindo a conjectura então não comprovada de que há progressões aritméticas arbitrariamente longas consistindo em números primos , eles provam que todo conjunto recursivamente enumerável é diofantino exponencial. Eles também provam como corolário que JR implica que todo conjunto recursivamente enumerável é Diofantino, o que por sua vez implica que o décimo problema de Hilbert é insolúvel.
1960	Robinson simplifica a prova do resultado condicional para conjuntos diofantinos exponenciais e o torna independente da conjectura sobre os primos e, portanto, um teorema formal. Isso torna a hipótese JR uma condição suficiente para a insolvência do décimo problema de Hilbert. No entanto, muitos duvidam que JR seja verdade.
1961-1969	Durante esse período, Davis e Putnam encontram várias proposições que implicam JR, e Robinson, tendo mostrado anteriormente que JR implica que o conjunto de primos é um conjunto Diofantino, prova que esta é uma condição se e somente se . Yuri Matiyasevich publica algumas reduções do décimo problema de Hilbert.
1970	Com base no trabalho recentemente publicado de Nikolai Vorob'ev sobre os números de Fibonacci, Matiyasevich prova que o conjunto onde é o ^enésimonúmero de Fibonacci é Diofantino e exibe um crescimento exponencial. Isso prova a hipótese de JR, que até então era uma questão em aberto há 20 anos. Combinando JR com o teorema de que todo conjunto recursivamente enumerável é diofantino exponencial, prova que conjuntos recursivamente enumeráveis são diofantinos. Isso torna o décimo problema de Hilbert insolúvel. ${\ displaystyle P = \ {(a, b) \| a> 0, b = F_ {2a} \},}$ ${\ displaystyle F_ {n}}$

Formulários

O Teorema de Matiyasevich / MRDP relaciona duas noções - uma da teoria da computabilidade, a outra da teoria dos números - e tem algumas consequências surpreendentes. Talvez o mais surpreendente seja a existência de uma equação diofantina universal :

Existe um polinômio tal que, dado qualquer conjunto Diofantino há um número tal que

{\ displaystyle p (a, n, x_ {1}, \ ldots, x_ {k})}

{\ displaystyle S}

{\ displaystyle n_ {0}}

{\ displaystyle S = \ {\, a \ mid \ exists x_ {1}, \ ldots, x_ {k} [p (a, n_ {0}, x_ {1}, \ ldots, x_ {k}) = 0] \, \}.}

Isso é verdade simplesmente porque os conjuntos diofantinos, sendo iguais aos conjuntos recursivamente enumeráveis, também são iguais às máquinas de Turing . É uma propriedade bem conhecida das máquinas de Turing que existem máquinas de Turing universais, capazes de executar qualquer algoritmo.

Hilary Putnam apontou que para qualquer conjunto diofantino de inteiros positivos, há um polinômio ${\ displaystyle S}$

{\ displaystyle q (x_ {0}, x_ {1}, \ ldots, x_ {n})}

tal que consiste exatamente nos números positivos entre os valores assumidos por como as variáveis ${\ displaystyle S}$ ${\ displaystyle q}$

{\ displaystyle x_ {0}, x_ {1}, \ ldots, x_ {n}}

abrangem todos os números naturais. Isso pode ser visto da seguinte forma: Se

{\ displaystyle p (a, y_ {1}, \ ldots, y_ {n}) = 0}

fornece uma definição diofantina de , então é suficiente definir ${\ displaystyle S}$

{\ displaystyle q (x_ {0}, x_ {1}, \ ldots, x_ {n}) = x_ {0} [1-p (x_ {0}, x_ {1}, \ ldots, x_ {n} ) ^ {2}].}

Então, por exemplo, há um polinômio para o qual a parte positiva de seu intervalo são exatamente os números primos. (Por outro lado, nenhum polinômio pode assumir apenas valores primos.) O mesmo vale para outros conjuntos recursivamente enumeráveis de números naturais: o fatorial, os coeficientes binomiais, os números de fibonacci, etc.

Outras aplicações dizem respeito ao que os lógicos chamam de proposições, às vezes também chamadas de proposições do tipo Goldbach . São como a conjectura de Goldbach , ao afirmar que todos os números naturais possuem uma certa propriedade que pode ser verificada por algoritmos para cada número particular. O teorema de Matiyasevich / MRDP implica que cada proposição é equivalente a uma afirmação que afirma que alguma equação Diofantina particular não tem soluções em números naturais. Vários problemas importantes e famosos são dessa forma: em particular, o Último Teorema de Fermat , a hipótese de Riemann e o Teorema das Quatro Cores . Além disso, a afirmação de que sistemas formais específicos , como a aritmética de Peano ou ZFC, são consistentes, pode ser expressa como sentenças. A ideia é seguir Kurt Gödel na codificação de provas por números naturais de tal forma que a propriedade de ser o número que representa uma prova seja verificável por algoritmo. ${\ displaystyle \ Pi _ {1} ^ {0}}$ ${\ displaystyle \ Pi _ {1} ^ {0}}$

${\ displaystyle \ Pi _ {1} ^ {0}}$ as sentenças têm a propriedade especial de que, se forem falsas, esse fato poderá ser provado em qualquer um dos sistemas formais usuais. Isso ocorre porque a falsidade equivale à existência de um contra-exemplo que pode ser verificado por aritmética simples. Portanto, se uma sentença é tal que nem ela nem sua negação são prováveis em um desses sistemas, essa sentença deve ser verdadeira. ${\ displaystyle \ Pi _ {1} ^ {0}}$

Uma forma particularmente notável do teorema da incompletude de Gödel também é uma consequência do teorema de Matiyasevich / MRDP:

Deixar

${\ displaystyle p (a, x_ {1}, \ ldots, x_ {k}) = 0}$

fornecer uma definição Diofantina de um conjunto não computável. Let Ser um algoritmo que produz uma sequência de números naturais tal que a equação correspondente ${\ displaystyle A}$ ${\ displaystyle n}$

${\ displaystyle p (n, x_ {1}, \ ldots, x_ {k}) = 0}$

não tem soluções em números naturais. Então, há um número que não é produzido por, embora de fato a equação ${\ displaystyle n_ {0}}$ ${\ displaystyle A}$

${\ displaystyle p (n_ {0}, x_ {1}, \ ldots, x_ {k}) = 0}$

não tem soluções em números naturais.

Para ver que o teorema é verdadeiro, é suficiente notar que se não houvesse tal número , alguém poderia testar algoritmicamente a associação de um número neste conjunto não computável executando simultaneamente o algoritmo para ver se é a saída enquanto também verifica todas as possíveis - tuplas de números naturais buscando uma solução da equação ${\ displaystyle n_ {0}}$ ${\ displaystyle n}$ ${\ displaystyle A}$ ${\ displaystyle n}$ ${\ displaystyle k}$

{\ displaystyle p (n, x_ {1}, \ ldots, x_ {k}) = 0.}

Podemos associar um algoritmo a qualquer um dos sistemas formais usuais, como a aritmética de Peano ou ZFC , permitindo que ele gere sistematicamente as consequências dos axiomas e, em seguida, produza um número sempre que uma frase da forma ${\ displaystyle A}$ ${\ displaystyle n}$

{\ displaystyle \ neg \ exists x_ {1}, \ ldots, x_ {k} [p (n, x_ {1}, \ ldots, x_ {k}) = 0]}

é gerado. Então o teorema nos diz que ou uma afirmação falsa dessa forma é provada ou uma verdadeira permanece não provada no sistema em questão.

Resultados adicionais

Podemos falar do grau de um conjunto diofantino como sendo o menor grau de um polinômio em uma equação que define esse conjunto. Da mesma forma, podemos chamar a dimensão de tal conjunto de menos incógnitas em uma equação definidora. Devido à existência de uma equação diofantina universal, é claro que existem limites superiores absolutos para ambas as quantidades, e tem havido muito interesse em determinar esses limites.

Já na década de 1920, Thoralf Skolem mostrou que qualquer equação diofantina é equivalente a uma de grau 4 ou menos. Seu truque era introduzir novas incógnitas por meio de equações que as colocavam como iguais ao quadrado de uma incógnita ou o produto de duas incógnitas. A repetição desse processo resulta em um sistema de equações de segundo grau; então, uma equação de grau 4 é obtida somando os quadrados. Portanto, todo conjunto diofantino é trivialmente de grau 4 ou menos. Não se sabe se este resultado é o melhor possível.

Julia Robinson e Yuri Matiyasevich mostraram que todo conjunto Diofantino tem dimensão não maior que 13. Mais tarde, Matiyasevich aprimorou seus métodos para mostrar que 9 incógnitas são suficientes. Embora possa muito bem ser que este resultado não seja o melhor possível, não houve nenhum progresso posterior. Portanto, em particular, não há algoritmo para testar equações diofantinas com 9 ou menos incógnitas para solvabilidade em números naturais. Para o caso de soluções racionais de inteiros (como Hilbert originalmente propôs), o truque dos 4 quadrados mostra que não há algoritmo para equações com não mais do que 36 incógnitas. Mas Zhi Wei Sun mostrou que o problema dos inteiros é insolúvel, mesmo para equações com não mais do que 11 incógnitas.

Martin Davis estudou questões algorítmicas envolvendo o número de soluções de uma equação diofantina. O décimo problema de Hilbert pergunta se esse número é ou não 0. Seja e deixe ser um subconjunto não vazio adequado de . Davis provou que não há algoritmo para testar uma dada equação diofantina para determinar se o número de suas soluções é um membro do conjunto . Assim, não há algoritmo para determinar se o número de soluções de uma equação diofantina é finito, ímpar, um quadrado perfeito, um primo, etc. ${\ displaystyle A = \ {0,1,2,3, \ ldots, \ aleph _ {0} \}}$ ${\ displaystyle C}$ ${\ displaystyle A}$ ${\ displaystyle C}$

A prova do teorema MRDP foi formalizada em Coq .

Extensões do décimo problema de Hilbert

Alexandra Shlapentokh (meio) em 2003

Embora Hilbert tenha proposto o problema para os inteiros racionais, ele também pode ser solicitado para muitos anéis (em particular, para qualquer anel cujo número de elementos seja contável ). Exemplos óbvios são os anéis de inteiros de campos de números algébricos , bem como os números racionais .

Tem havido muito trabalho no décimo problema de Hilbert para os anéis de inteiros de campos de números algébricos. Baseando-se no trabalho anterior de Jan Denef e Leonard Lipschitz e usando a teoria do campo de classe, Harold N. Shapiro e Alexandra Shlapentokh foram capazes de provar:

O décimo problema de Hilbert é insolúvel para o anel de inteiros de qualquer campo de números algébricos cujo grupo de Galois sobre os racionais seja abeliano .

Shlapentokh e Thanases Pheidas (independentemente um do outro) obtiveram o mesmo resultado para campos de números algébricos que admitem exatamente um par de embeddings conjugados complexos.

O problema para o anel de inteiros de campos de números algébricos diferentes daqueles cobertos pelos resultados acima permanece aberto. Da mesma forma, apesar de muito interesse, o problema das equações sobre os racionais permanece aberto. Barry Mazur conjecturou que, para qualquer variedade sobre os racionais, o fechamento topológico sobre os reais do conjunto de soluções tem apenas componentes finitos. Essa conjectura implica que os inteiros não são diofantinos sobre os racionais e, portanto, se essa conjectura for verdadeira, uma resposta negativa ao Décimo Problema de Hilbert exigiria uma abordagem diferente daquela usada para outros anéis.

Notas

Referências

Hilbert, David (1901). "Mathematische Probleme". Archiv der Mathematik und Physik . 3ª série (em alemão). 1 : 44–63, 213–247.
Hilbert, David (julho de 1902). "Problemas matemáticos" . Touro. Amer. Matemática. Soc . 8 (10): 437–479.
Yuri V. Matiyasevich , Décimo Problema de Hilbert , MIT Press, Cambridge, Massachusetts, 1993.
Davis, Martin ; Matiyasevich, Yuri ; Robinson, Julia (1976). "Décimo Problema de Hilbert: Equações Diofantinas: Aspectos Positivos de uma Solução Negativa". Em Felix E. Browder (ed.). Desenvolvimentos matemáticos decorrentes de problemas de Hilbert . Proceedings of Symposia in Pure Mathematics . XXVIII.2. American Mathematical Society . pp. 323–378. ISBN 0-8218-1428-1. Zbl 0346.02026 . Reimpresso em The Collected Works of Julia Robinson , Solomon Feferman , editor, pp. 269-378, American Mathematical Society 1996.
Martin Davis , "Hilbert's Denth Problem is Unsolvable," American Mathematical Monthly , vol.80 (1973), pp. 233-269; reimpresso como um apêndice em Martin Davis, Computability and Unsolvability , Dover reimpressão 1982.
Davis, Martin ; Hersh, Reuben (1973). “10º Problema de Hilbert”. Scientific American . 229 : 84–91. doi : 10.1038 / scientificamerican1173-84 .
Jan Denef , Leonard Lipschitz, Thanases Pheidas, Jan van Geel, editores, "Hilbert's Denth Problem: Workshop at Ghent University, Belgium, November 2–5, 1999." Contemporary Mathematics vol. 270 (2000), American Mathematical Society.
M. Ram Murty e Brandon Fodden: "Décimo Problema de Hilbert: Uma Introdução à Lógica, Teoria dos Números e Computabilidade", Americal Mathematical Society, ISBN 978-1-4704-4399-3 (junho de 2019).

Leitura adicional

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 .

Languages

In other projects