Conjunto diofántico

En matemáticas , una ecuación diofántica es una ecuación de la forma P ( x ₁ , ..., x _j , y ₁ , ..., y _k ) = 0 (generalmente abreviada P ( x , y ) = 0) donde P ( x , y ) es un polinomio con coeficientes enteros , donde x ₁ , ..., x _j indican parámetros e y ₁ , ..., y _k indican incógnitas.

Un conjunto diofántico es un subconjunto S de${\displaystyle \mathbb {N} ^{j}}$, el conjunto de todas las j -tuplas de números naturales, de modo que para alguna ecuación diofántica P ( x , y ) = 0,

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

Es decir, un valor de parámetro pertenece al conjunto diofántico S si y solo si la ecuación diofántica asociada es satisfacible 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 enteros no negativos o enteros positivos, ya que las dos definiciones de conjuntos diofánticos son equivalentes. También podemos hablar igualmente bien de conjuntos diofánticos de enteros y reemplazar libremente la cuantificación sobre números naturales por la cuantificación sobre los enteros. ^{[ 1 ]} Además, es suficiente suponer que P es un polinomio sobre${\displaystyle \mathbb {Q} }$y multiplicar P por los denominadores apropiados para obtener coeficientes enteros. Sin embargo, si la cuantificación sobre racionales también puede sustituir a la cuantificación sobre 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 enteros es diofántico si y solo si es computablemente enumerable . ^{[ 4 ] [ 5 ]} Un conjunto de enteros S es computacionalmente enumerable si y solo si existe un algoritmo que, al recibir un entero, se detiene si ese entero pertenece a S y se ejecuta indefinidamente 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 de teoría de la computabilidad. Sin embargo, esto dista mucho de ser obvio y representó la culminación de varias décadas de trabajo.

La formulación del teorema MRDP por Matiyasevich resolvió el décimo problema de Hilbert . El décimo problema de Hilbert ^{[ 6 ]} consistía en encontrar un algoritmo general que pudiera determinar 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 un enunciado matemático formal como tal, la aceptación casi universal de la identificación (filosófica) de un algoritmo de decisión con un predicado computable total nos permite utilizar el teorema MRDP para concluir que el décimo problema es irresoluble.

En los siguientes ejemplos, los números naturales se refieren al conjunto de los enteros positivos.

La ecuación

${\displaystyle x=(y_{1}+1)(y_{2}+1)}$

es un ejemplo de una ecuación diofántica con un parámetro x y las incógnitas y ₁ e y ₂ . La ecuación tiene una solución en y ₁ e y ₂ precisamente cuando x puede expresarse como un producto de dos 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

{4, 6, 8, 9, 10, 12, 14, 15, 16, 18, ...}

que consta de números compuestos.

Otros ejemplos de definiciones diofánticas son los siguientes:

• La ecuación${\displaystyle x=y_{1}^{2}+y_{2}^{2}}$con parámetro x y incógnitas y ₁ , y ₂ solo tiene soluciones en${\displaystyle \mathbb {N} }$cuando x es una suma de dos cuadrados perfectos . El conjunto diofántico de la ecuación es {2, 5, 8, 10, 13, 17, 18, 20, 25, 26, ...}.
• La ecuación${\displaystyle y_{1}^{2}-xy_{2}^{2}=1}$con parámetro x e incógnitas y ₁ , y ₂ . Esta es una ecuación de Pell , lo que significa que solo tiene soluciones en${\displaystyle \mathbb {N} }$cuando x no es un cuadrado perfecto. El conjunto diofántico es {2, 3, 5, 6, 7, 8, 10, 11, 12, 13, ...}.
• La ecuación${\displaystyle x_{1}+y=x_{2}}$es una ecuación diofántica con dos parámetros x ₁ , x ₂ y una incógnita y , que define el conjunto de pares ( x ₁ , x ₂ ) tales que x ₁ < x ₂ .

El teorema de Matiyasevich, también llamado teorema de Matiyasevich - Robinson - Davis - Putnam o teorema MRDP, dice:

Todo conjunto computacionalmente enumerable es diofántico, y viceversa.

Un conjunto S de enteros es computacionalmente enumerable si existe un algoritmo tal que: para cada entero de entrada n , si n es un miembro de S , entonces el algoritmo eventualmente se detiene; de ​​lo contrario, se ejecuta indefinidamente. Esto es equivalente a decir que existe un algoritmo que se ejecuta indefinidamente y enumera los miembros de S. Un conjunto S de enteros es diofántico precisamente si existe algún polinomio con coeficientes enteros f ( n , x ₁ , ..., x _k ) tal que un entero n está en S si y solo si existen algunos enteros x ₁ , ..., x _k tales que f ( n , x ₁ , ..., x _k ) = 0.

Es fácil ver que todo conjunto diofántico es computacionalmente enumerable: consideremos una ecuación diofántica f ( n , x ₁ , ..., x _k ) = 0. Ahora creamos un algoritmo que prueba todos los valores posibles para n , x ₁ , ..., x _k (en, por ejemplo, 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 ₁ , ..., x _k ) = 0. Este algoritmo se ejecutará indefinidamente y listará exactamente el n para el cual f ( n , x ₁ , ..., x _k ) = 0 tiene una solución en x ₁ , ..., x _k .

Yuri Matiyasevich utilizó un método que involucra los números de Fibonacci , los cuales crecen exponencialmente , para demostrar que las soluciones de ecuaciones diofánticas también pueden crecer exponencialmente. Trabajos anteriores de Julia Robinson , Martin Davis y Hilary Putnam —de ahí el nombre MRDP— habían demostrado que esto es suficiente para demostrar que todo conjunto computacionalmente enumerable es diofántico.

El décimo problema de Hilbert plantea la necesidad de un algoritmo general para determinar la resolubilidad de 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 la solución al décimo problema de Hilbert es imposible.

Desde entonces, el teorema de Matiyasevich se ha utilizado para demostrar que muchos problemas del cálculo y de las ecuaciones diferenciales son irresolubles.

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:

Correspondiente a cualquier axiomatización consistente dada de la teoría de números, ^{[ 9 ]} se puede construir explícitamente una ecuación diofántica que no tiene soluciones, pero tal que este hecho no se puede probar dentro de la axiomatización dada.

Según los teoremas de incompletitud , una teoría axiomática suficientemente potente y consistente es incompleta, lo que significa que la veracidad de algunas de sus proposiciones no puede establecerse dentro de su formalismo. La afirmación anterior indica que esta incompletitud debe incluir la resolubilidad de una ecuación diofántica, suponiendo que la teoría en cuestión sea una teoría de números.

• Artículo del teorema de Matiyasevich en Scholarpedia .