En matemáticas , una ecuación diofántica es una ecuación de la forma P ( x 1 , ..., x j , y 1 , ..., y k ) = 0 (generalmente abreviada P ( x , y ) = 0) donde P ( x , y ) es un polinomio con coeficientes enteros , donde x 1 , ..., x j indican parámetros y y 1 , ..., y k indican incógnitas.
Un conjunto diofántico es un subconjunto S de , el conjunto de todas las j -tuplas de números naturales, de modo que para alguna ecuación diofántica P ( x , y ) = 0,
Es decir, un valor de parámetro está en el conjunto diofántico S si y sólo si la ecuación diofántica asociada es satisfactoria bajo ese valor de parámetro. El uso de números naturales tanto en S como en la cuantificación existencial simplemente refleja las aplicaciones habituales en la teoría de la computabilidad y la teoría de modelos . No importa si los números naturales se refieren al conjunto de números enteros no negativos o positivos, ya que las dos definiciones de conjuntos diofánticos son equivalentes. También podemos hablar igualmente de conjuntos diofánticos de números enteros y sustituir libremente la cuantificación sobre números naturales por la cuantificación sobre números enteros. [1] También es suficiente asumir que P es un polinomio y multiplicar P por los denominadores apropiados para obtener coeficientes enteros. Sin embargo, si la cuantificación sobre racionales también puede sustituirse por la cuantificación sobre números enteros es un problema abierto notoriamente difícil. [2]
El teorema MRDP (llamado así por las iniciales de los cuatro principales contribuyentes a su solución) establece que un conjunto de números enteros es diofántico si y sólo si es computablemente enumerable . [3] Un conjunto de números enteros S es computablemente enumerable si y sólo si hay un algoritmo que, cuando se le da un número entero, se detiene si ese número entero es miembro de S y se ejecuta para siempre en caso contrario. Esto significa que el concepto de conjunto diofántico general, que aparentemente pertenece a la teoría de números , puede tomarse más bien en términos lógicos o teóricos de la computabilidad. Sin embargo, esto está lejos de ser obvio y representó la culminación de algunas décadas de trabajo.
La finalización del teorema MRDP por parte de Matiyasevich resolvió el décimo problema de Hilbert . El décimo problema de Hilbert [4] era encontrar un algoritmo general que pudiera decidir si una ecuación diofántica dada tiene una solución entre los números enteros. Si bien el décimo problema de Hilbert no es una afirmación matemática formal como tal, la aceptación casi universal de la identificación (filosófica) de un algoritmo de decisión con un predicado total computable nos permite utilizar el teorema MRDP para concluir que el décimo problema no tiene solución.
En los siguientes ejemplos, los números naturales se refieren al conjunto de números enteros positivos.
La ecuacion
es un ejemplo de ecuación diofántica con un parámetro x e incógnitas y 1 e y 2 . La ecuación tiene solución en y 1 e y 2 precisamente cuando x se puede expresar como producto de dos números enteros mayores que 1, en otras palabras x es un número compuesto . Es decir, esta ecuación proporciona una definición diofántica del conjunto
formado por números compuestos.
Otros ejemplos de definiciones diofánticas son los siguientes:
El teorema de Matiyasevich, también llamado teorema de Matiyasevich – Robinson – Davis – Putnam o MRDP, dice:
Un conjunto S de números enteros es computablemente enumerable si existe un algoritmo tal que: Para cada entrada de número entero n , si n es miembro de S , entonces el algoritmo finalmente se detiene; de lo contrario, corre para siempre. Eso equivale a decir que hay un algoritmo que se ejecuta para siempre y enumera los miembros de S. Un conjunto S es diofántico precisamente si existe algún polinomio con coeficientes enteros f ( n , x 1 , ..., x k ) tal que un número entero n esté en S si y sólo si existen algunos números enteros x 1 , ... , x k tal que f ( n , x 1 , ..., x k ) = 0.
Por el contrario, cada conjunto diofántico es computablemente enumerable : considere una ecuación diofántica f ( n , x 1 , ..., x k ) = 0. Ahora creamos un algoritmo que simplemente prueba todos los valores posibles para n , x 1 , ... , x k (en, digamos, algún orden simple consistente con el orden creciente de la suma de sus valores absolutos), e imprime n cada vez que f ( n , x 1 , ..., x k ) = 0. Este algoritmo obviamente se ejecuta para siempre y enumerará exactamente el n para el cual f ( n , x 1 , ..., x k ) = 0 tiene una solución en x 1 , ..., x k .
Yuri Matiyasevich utilizó un método que involucra números de Fibonacci , que crecen exponencialmente , para demostrar que las soluciones a las ecuaciones diofánticas pueden crecer exponencialmente. Trabajos anteriores de Julia Robinson , Martin Davis y Hilary Putnam (de ahí, MRDP) habían demostrado que esto es suficiente para demostrar que todo conjunto computable enumerable es diofántico.
El décimo problema de Hilbert solicita un algoritmo general que decida la solubilidad de las ecuaciones diofánticas. La conjunción del resultado de Matiyasevich con el hecho de que la mayoría de los lenguajes recursivamente enumerables no son decidibles implica que una solución al décimo problema de Hilbert es imposible.
Trabajos posteriores han demostrado que la cuestión de la solubilidad de una ecuación diofántica es indecidible incluso si la ecuación sólo tiene 9 variables de números naturales (Matiyasevich, 1977) u 11 variables enteras ( Zhi Wei Sun , 1992).
Desde entonces, el teorema de Matiyasevich se ha utilizado para demostrar que muchos problemas de cálculo y ecuaciones diferenciales no tienen solución.
También se puede derivar la siguiente forma más fuerte del primer teorema de incompletitud de Gödel a partir del resultado de Matiyasevich:
Según los teoremas de incompletitud , una teoría axiomática suficientemente poderosa y consistente es incompleta, lo que significa que la verdad de algunas de sus proposiciones no puede establecerse dentro de su formalismo. La afirmación anterior dice que esta incompletitud debe incluir la solubilidad de una ecuación diofántica, asumiendo que la teoría en cuestión es una teoría de números.
