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 abreviado P(x, y) = 0) donde P(x, y) es un polinomio con número entero coeficientes, donde x₁,..., x_j indican parámetros y y₁,..., y_k indican incógnitas.

A Diophantine set es un subconjunto S de Nj{displaystyle mathbb {N}, el conjunto de todos j-tuples de números naturales, así que para alguna ecuación de Diofantina P()x, Sí.) = 0,

x̄ ̄ ▪ ▪ S⟺ ⟺ ()∃ ∃ Sí.̄ ̄ ▪ ▪ Nk)()P()x̄ ̄ ,Sí.̄ ̄ )=0).{displaystyle {bar {x}in Siff (exists {bar {}in mathbb {N})(P({bar {x},{bar {y})=0). }

Es decir, un valor de parámetro está en el conjunto Diophantine S si y sólo si la ecuación Diofantina asociada es satisfecha bajo ese valor del parámetro. El uso de números naturales tanto en S y la cuantificación existencial simplemente refleja las aplicaciones habituales en la computabilidad y la teoría modelo. No importa si los números naturales se refieren al conjunto de enteros no negativos o enteros positivos ya que las dos definiciones para el conjunto Diophantine son equivalentes. También podemos hablar igualmente bien de conjuntos diofantinos de enteros y sustituir libremente la cuantificación sobre los números naturales con la cuantificación sobre los enteros. También es suficiente asumir P es una sobrenomia polinómica Q{displaystyle mathbb {Q} y multiplicarse P por los denominadores apropiados para producir coeficientes enteros. Sin embargo, si la cuantificación sobre los fundamentos también puede sustituirse por la cuantificación sobre los enteros es un problema notoriamente abierto.

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 solo si es computablemente enumerable. Un conjunto de números enteros S es computablemente enumerable si y solo 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 de lo contrario. Esto significa que el concepto de conjunto diofántico general, aparentemente perteneciente a la teoría de números, puede tomarse más bien en términos lógicos o teóricos de la recursión. Sin embargo, esto está lejos de ser obvio y representó la culminación de varias décadas de trabajo.

La finalización del teorema MRDP de Matiyasevich resolvió el décimo problema de Hilbert. El décimo problema de Hilbert fue encontrar un algoritmo general que pueda 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 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 usar el teorema MRDP para concluir que el décimo problema es Sin solución.

Ejemplos

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

La ecuación

x=()Sí.1+1)()Sí.2+1){displaystyle x=(y_{1}+1)(y_{2}+1)}

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

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

que consta de los números compuestos.

Otros ejemplos de definiciones diofánticas son los siguientes:

• La ecuación x=Sí.12+Sí.22{displaystyle ¿Qué? con parámetro x y desconocidos Sí.₁, Sí.₂ sólo tiene soluciones en N{displaystyle mathbb {N} cuando x es una suma de dos cuadrados perfectos. El conjunto Diophantine de la ecuación es {2, 5, 8, 10, 13, 17, 18, 20, 25, 26,...}.
• La ecuación Sí.12− − xSí.22=1{displaystyle Y... con parámetro x y desconocidos Sí.₁, Sí.₂. Esta es una ecuación Pell, lo que significa que sólo tiene soluciones en N{displaystyle mathbb {N} cuando x no es un cuadrado perfecto. El juego Diophantine es {2, 3, 5, 6, 7, 8, 10, 11, 12, 13,...}.
• La ecuación x1+Sí.=x2{displaystyle x_{1}+y=x_{2} es una ecuación Diofantina con dos parámetros x₁, x₂ y un desconocido Sí., que define el conjunto de pares (x₁, x₂. x₁. x₂.

Teorema de Matiyasevich

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

Cada conjunto computadamente enumerable es Diofantina, y el contrario.

Un conjunto S de enteros es numerable computacionalmente si hay un algoritmo tal que: Para cada entero ingrese n, si n es miembro de S, entonces el algoritmo finalmente se detiene; de lo contrario, se ejecuta 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 Diofantino 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 tal que f(n, x₁,..., x_k) = 0.

Por el contrario, cada conjunto diofántico es computablemente enumerable: considere una ecuación diofántica f(n, x₁,..., x_k) = 0. Ahora hacemos un algoritmo que simplemente prueba todos los valores posibles para n, x₁,..., 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 f(n, x₁,..., x_k) = 0. Este algoritmo obviamente se ejecutará para siempre y enumerará exactamente el n para el cual f(n, x₁,..., x_k) = 0 tiene solución en x₁,..., x_k.

Técnica de prueba

Yuri Matiyasevich utilizó un método con números de Fibonacci, que crecen exponencialmente, para mostrar que las soluciones de las ecuaciones diofánticas pueden crecer exponencialmente. El trabajo anterior de Julia Robinson, Martin Davis y Hilary Putnam (por lo tanto, MRDP) había demostrado que esto es suficiente para demostrar que todo conjunto computablemente enumerable es diofántico.

Aplicación al décimo problema de Hilbert

El décimo problema de Hilbert pide un algoritmo general que decida la resolución 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.

Refinamientos

Trabajos posteriores han demostrado que la cuestión de la resolución de una ecuación diofántica es indecidible incluso si la ecuación solo tiene 9 variables de números naturales (Matiyasevich, 1977) u 11 variables enteras (Zhi Wei Sun, 1992).

Otras aplicaciones

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:

Correspondiendo a cualquier axiomatización consistente dada de la teoría de números, se puede construir explícitamente una ecuación Diofantina que no tiene soluciones, pero tal que este hecho no puede ser probado dentro de la axiomatización dada.

De acuerdo con los teoremas de incompletitud, una teoría axiomática consistente lo suficientemente poderosa es incompleta, lo que significa que la verdad de algunas de sus proposiciones no se puede establecer dentro de su formalismo. La declaración anterior dice que este carácter incompleto debe incluir la capacidad de resolución de una ecuación diofántica, asumiendo que la teoría en cuestión es una teoría de números.