fbpx
Wikipedia

Décimo problema de Hilbert

El décimo problema de Hilbert es uno de los conocidos como veintitrés Problemas de Hilbert, publicados en 1900 por el matemático alemán David Hilbert. Su enunciado original es:

Dada una ecuación diofántica con cualquier número de incógnitas y con coeficientes numéricos racionales enteros:

Idear un proceso de acuerdo con el cual pueda determinarse, en un número finito de operaciones, si la ecuación es resoluble en números racionales enteros.

En términos de programación informática, Hilbert solicitaba a sus colegas del futuro un algoritmo capaz de admitir como entrada (input) una ecuación diofántica cualquiera, y de devolver como resultado (output) si la ecuación procesada tenía soluciones en números enteros o NO si la ecuación procesada carecía de soluciones en números enteros.

El problema no se resolvió hasta 70 años después, y en sentido negativo. En 1970 Yuri Matiyasévich culminó más de veinte años de trabajo de varios matemáticos, entre ellos Martin Davis, Julia Robinson y Hilary Putnam, con la demostración de imposibilidad del décimo problema: ningún algoritmo es capaz de determinar la resolubilidad de cualquier ecuación diofántica. El planteamiento, desarrollo y demostración del problema tienen gran interés en matemática moderna, porque en ellos participan conceptos de teoría de números y de lógica matemática, y se abren nuevos campos de investigación en ambas disciplinas.

Formulación

Las palabras «proceso» y «número finito de operaciones» de su enunciado original sugieren claramente que Hilbert pedía un algoritmo. El término «racional entero» se refiere simplemente a los números enteros, positivos, negativos o cero:  .[1]​ Por tanto, Hilbert estaba pidiendo un algoritmo general que decidiera si un polinomio dado de coeficientes enteros —una ecuación diofántica— tenía solución en el dominio de los enteros.

Hoy sabemos que la respuesta es negativa: no existe tal algoritmo general.

Puede que el propio Hilbert no confiara en su existencia. Antes de presentar la lista de problemas, parecía presagiar la ausencia de solución, diciendo:

En ocasiones ocurre que perseguimos la solución basándonos en hipótesis insuficientes, o en un sentido incorrecto, y por eso fracasamos. Entonces surge el problema: demostrar la imposibilidad de obtener una solución con tales hipótesis o en el sentido contemplado.

Otros opinan que la «solución de insolubilidad» a la que se llegó siete décadas después no solo hubiera sorprendido al auditorio que asistió en 1900 en la Sorbona a la presentación de Hilbert,[2]​ sino posiblemente incluso al propio Hilbert, ya que se esperaba obtener un conjunto de instrucciones que definieran un procedimiento, y a lo que se llegó finalmente fue a una demostración de la inexistencia de tal conjunto de instrucciones.[3]

Equivalencia del problema en ℕ y en ℤ

Los trabajos de solución del problema casi siempre se han planteado en términos de enteros no negativos o números naturales,  ,[4]​ más que con números enteros. Es irrelevante, porque puede demostrarse que si existiera un algoritmo que detectara la existencia de solución en  , podría usarse también para detectar la existencia de solución en  .

  • En efecto: conocido un algoritmo que detecte la resolubilidad en  , podríamos usarlo para detectar si la ecuación de   incógnitas,
 
tiene solución entera, aplicando el hipotético algoritmo a las   ecuaciones
 
  • Inversamente, un algoritmo capaz de detectar la resolubilidad en   puede usarse para determinar si una ecuación dada es resoluble en  , sin más que sustituir cada incógnita de la ecuación por la suma de los cuadrados de cuatro nuevas variables enteras. El teorema de Lagrange de los cuatro cuadrados garantiza que cualquier número natural puede igualarse a la suma de los cuadrados de un máximo de cuatro números enteros.

Conjuntos diofánticos

Se denomina conjuntos diofánticos a los conjuntos de números naturales, de pares de números naturales, o de forma más general de  -tuplas de números naturales, que tienen definiciones diofánticas. Tanto un sistema de ecuaciones diofánticas simultáneas como una ecuación diofántica individual pueden definir un conjunto diofántico, porque el sistema

 

es equivalente a la ecuación individual

 

Dicho de otro modo, si existe una ecuación (o sistema) diofántica cuya solución sea el conjunto de  -tuplas de números naturales  , entonces   es un conjunto diofántico.

Un conjunto es diofántico si y solo si es recursivamente enumerable

Se define un conjunto recursivamente enumerable como un conjunto para el que existe un algoritmo que se detendrá si su entrada es un elemento del conjunto, pero seguirá corriendo indefinidamente si su entrada no pertenece al conjunto. El concepto de enumerabilidad recursiva pertenece al ámbito de la teoría de la computabilidad, también llamada teoría de la recursión, cuyo desarrollo aportó una explicación precisa de la noción intuitiva de computabilidad algorítmica, dando pleno rigor al concepto de enumerabilidad recursiva.

Resulta evidente que los conjuntos diofánticos son, por definición, recursivamente enumerables. Dada una ecuación o sistema diofántico, pueden formarse secuencialmente todas las tuplas posibles de valores de las incógnitas y después, para un valor dado de los parámetros, comprobar una tras otra las tuplas, para detectar si son o no solución de la ecuación o sistema. Luego la propia ecuación o sistema que define el conjunto diofántico define el algoritmo que avala la enumerabilidad recursiva del conjunto. La imposibilidad de resolver el décimo problema de Hilbert es consecuencia de que el inverso también es cierto:

Todo conjunto recursivamente enumerable es diofántico.

Este resultado se conoce de dos formas: como Teorema de Matiyasevich, porque fue Yuri Matiyasévich el que consiguió el desarrollo final que permitió demostrar el teorema, y como Teorema MRDP, nombre que agrupa a los matemáticos que consiguieron el desarrollo completo, empezando por el citado Matiyasevich, para continuar por Julia Robinson, Martin Davis y Hilary Putnam. Dado que existe un conjunto recursivamente enumerable que no es computable, la irresolubilidad del décimo problema de Hilbert es una consecuencia inmediata. De hecho, puede decirse más. Existe un polinomio

 

con coeficientes enteros, tal que el conjunto de valores de   para el que la ecuación

 

tiene soluciones en los números naturales no es computable. Así pues, no solo no existe un algoritmo general para detectar la resolubilidad de las ecuaciones diofánticas, sino que también puede demostrarse que ni siquiera existe un algoritmo particular para la familia de ecuaciones con un único parámetro.

Historia

Año Sucesos
1944 Emil Leon Post declara que el décimo problema de Hilbert «está implorando una prueba de irresolubilidad».
1949 Martin Davis utiliza el método de Kurt Gödel para aplicar el teorema chino del residuo como truco de codificación para obtener en su forma normal conjuntos recursivamente enumerables:
 

donde   es un polinomio con coeficientes enteros. Formalmente, solo el cuantificador universal estorba para que se considere esto como una definición diofántica de conjuntos. Usando una prueba no constructiva, pero muy sencilla, Davis notó que hay un conjunto diofántico cuyo complementario no es diofántico. Dado que los conjuntos recursivamente enumerables tampoco son cerrados para el complemento, Davis conjeturó la identidad de ambas clases.

1950 Julia Robinson no conocía el trabajo de Davis, pero sospechando que la función exponencial era de importancia clave, intentaba demostrar que EXP, el conjunto de tripletes
  para los cuales  

es diofántico. No tuvo éxito, lo que la condujo a su hipótesis (luego llamada  ): Existe un conjunto diofántico   de pares   tal que

 

pero para cada  ,

  tal que  

Usando algunas propiedades de la ecuación de Pell, Robinson demostró que   implica que EXP es diofántico. Y finalmente demostró que si EXP es diofántico, entonces también lo son los coeficientes binomiales, el factorial y los primos.

1959 Trabajando juntos, Davis y Putnam estudiaron los conjuntos diofánticos exponenciales, es decir, los conjuntos definibles por ecuaciones diofánticas en los que algunos de los exponentes pueden ser incógnitas. Usando la forma normal de Davis junto con los métodos de Robinson, pero suponiendo la entonces indemostrada conjetura de que hay progresiones aritméticas arbitrariamente largas compuestas de números primos[5]​ demostraron que todo conjunto recursivamente enumerable es un conjunto exponencial diofántico, y que como consecuencia,   implicaba que todo conjunto recursivamente enumerable es diofántico, y que el décimo problema de Hilbert es irresoluble.
1960 Robinson mostró como evitar el uso de la indemostrada conjetura de los números primos en progresiones aritméticas, y simplificó notablemente la demostración.   se revelaba como la clave para seguir avanzando, aunque muchos dudaban de su veracidad.[6]
1961-1969 Davis y Putnam encontraron algunas proposiciones que implicaban   Matiyasevich publicó algunas reducciones del décimo problema de Hilbert. Robinson demostró que la existencia de un conjunto diofántico infinito de primos bastaría para demostrar  
1970 Matiyasevich presentó un sistema de 10 ecuaciones simultáneas de primer y segundo grado que aportaba una definición diofántica del conjunto de pares

  tal que

  donde   es el n-simo número de Fibonacci.

Con esto quedaba demostrado  , completándose por tanto la prueba de que todos los conjuntos recursivamente enumerables son diofánticos, lo que implica que el décimo problema de Hilbert es irresoluble.

Aplicaciones

El teorema de Matiyasevich/MRDP relaciona dos conceptos, uno procedente de la teoría de la computabilidad, y el otro de la teoría de números, y tiene algunas consecuencias inesperadas. Quizás la más sorprendente sea la existencia de una ecuación diofántica universal.

Existe un polinomio   tal que, dado cualquier conjunto diofántico  , hay un número   tal que
 

Puede verse que esto es cierto simplemente porque hay máquinas universales de Turing capaces de ejecutar cualquier algoritmo. Precisamente esta consecuencia de   es la que había despertado más suspicacias, haciendo dudar de la veracidad de la hipótesis de Julia Robinson.

Hilary Putnam ha hecho notar que para cada conjunto diofántico   de enteros positivos existe un polinomio

 

tal que   está formado precisamente por los números positivos entre los valores supuestos por   como las variables

 

recorren todos los números naturales. Esto puede verse como sigue: si

 

proporciona una definición diofántica de  , entonces ello basta para fijar

 

Así, por ejemplo, hay un polinomio para el cual la parte positiva de este intervalo son exactamente los números primos (por otro lado, sin embargo, no existe ningún polinomio que devuelva solo números primos).

Otras aplicaciones tienen que ver con lo que los lógicos denominan proposiciones  , llamadas también a veces proposiciones de tipo Goldbach[7]​ Estas son como la conjetura de Goldbach, propuestas que asignan a todo número natural una propiedad que es comprobable algorítmicamente para cada número en particular[8]​ El teorema de Matiyasevich/MRDP implica que cada una de tales proposiciones es equivalente a un enunciado que afirma que existe una ecuación diofántica particular que carece de solución en los números naturales.[9]​ Cierto número de problemas importantes y bien conocidos tienen esta forma, entre ellos el último teorema de Fermat, la hipótesis de Riemann y el teorema de los cuatro colores. Además, la afirmación de que algunos sistemas formales, tales como la aritmética de Peano o el sistema ZFC son consistentes puede expresarse como sentencias  . La idea es seguir la estrategia de Kurt Gödel de codificación mediante números naturales de forma tal que la propiedad de ser el número que representa a una demostración sea algorítmicamente comprobable.

Los enunciados   tienen la propiedad de que en el caso de ser falsos, tal falsedad será siempre demostrable en cualquiera de los sistemas formales en uso. Esto se debe a que la falsedad determina la existencia de un contraejemplo que puede ser verificado por aritmética simple. Así, si en uno de estos sistemas formales no pueden probarse ni la proposición   ni su negación, esa proposición debe ser verdadera.

Una forma particularmente impactante del teorema de incompletitud de Gödel es asimismo consecuencia del teorema de Matiyasevich/MRDP.

Sea

 

una definición diofántica de un conjunto no computable.

Sea   un algoritmo que devuelve una sucesión de números naturales   tal que la ecuación correspondiente

 

carece de soluciones en los números naturales. Entonces existe un número   que no es devuelto por  , en tanto que, de hecho, la ecuación

 

carece de soluciones en los números naturales.

Para darse cuenta de que el teorema es cierto, basta con observar que si no existiera tal número  , se podría testar algorítmicamente la pertenencia de un número   a ese conjunto no-computable, haciendo correr simultáneamente el algoritmo   para comprobar si devuelve  , al tiempo que se comprueban todas las posibles  -tuplas de números naturales buscando una solución de la ecuación

 

Podemos asociar un algoritmo   con cualquiera de los sistemas formales en uso, tales como la Aritmética de Peano o ZFC, dejando que el algoritmo genere sistemáticamente consecuencias de los axiomas y devuelva un número   cada vez que se genere una proposición de la forma

 

Entonces el teorema nos dice que o bien una proposición falsa del sistema será demostrada de esta forma, o bien una verdadera quedará sin demostrar en el sistema en cuestión, lo que demuestra la incompletitud del sistema.

Resultados adicionales

Podemos aludir al grado de un conjunto diofántico, como el mínimo grado de un polinomio en la ecuación que defina el conjunto. De forma similar, podemos llamar dimensión de un conjunto diofántico al menor número de incógnitas de una ecuación que lo defina. Dado que existe una ecuación diofántica universal, está claro que ambas cantidades, grado y dimensión, tienen cotas superiores absolutas. Determinar estos valores máximos ha despertado mucho interés en los matemáticos.

Ya en los años 1920, Thoralf Skolem mostró que cualquier ecuación diofántica es equivalente a una de grado 4 o inferior. Su estrategia fue introducir nuevas incógnitas añadiendo ecuaciones que las igualaban al cuadrado de una incógnita, o al producto de dos. Repitiendo este proceso se obtiene un sistema de ecuaciones de segundo grado, y sumando luego los cuadrados se pasa a otra de grado 4. Así pues, una ecuación diofántica es de grado 4 o inferior, si bien se desconoce si este resultado es el óptimo.

Julia Robinson y Yuri Matiyasevich mostraron que todo conjunto diofántico tiene dimensión menor o igual que 13. Después, Matiyasevich refinó el método para demostrar que bastaba con 9 incógnitas. Aunque nadie imagina que este sorprendente resultado sea el mejor posible, no ha habido progresos posteriores[10]​ Así pues, en particular, no existe ningún algoritmo que pueda probar la resolubilidad en los enteros positivos de ecuaciones diofánticas de 9 incógnitas o menos. Para el caso de números enteros (como Hilbert había planteado inicialmente), el truco de los cuatro cuadrados muestra que no hay algoritmo para ecuaciones que no tengan más de 36 incógnitas. Pero Zhi Wei Sun demostró que, tratándose de números enteros, el problema es irresoluble incluso para ecuaciones que no excedan las 11 incógnitas.

Martin Davis estudió problemas algorítmicos relacionados con el número de soluciones de una ecuación diofántica. El décimo problema de Hilbert reclama un algoritmo que decida si el número de soluciones es   o distinto de  . Supongamos que   y sea   un subconjunto estricto y no vacío de  . Davis demostró que no existe algoritmo que pueda decidir si una ecuación diofántica dada tiene un número de soluciones que sea elemento del conjunto  . Por tanto, no existe ningún algoritmo que pueda determinar si el número de soluciones es finito o infinito, par o impar, primo o compuesto, cuadrado perfecto, etc.

Extensiones del décimo problema de Hilbert

Aunque Hilbert propuso el problema para el caso de los racionales enteros, es claro que la pregunta puede hacerse para muchos anillos. Ejemplos obvios son los anillos de enteros de cuerpos numéricos algebraicos, así como los números racionales. Seguramente Hilbert era consciente de que un algoritmo como el que estaba reclamando podría extenderse a esas estructuras. Por ejemplo, la ecuación

 

donde   es un polinomio de grado   es resoluble en los números racionales negativos si y solo si

 

es resoluble en los números naturales (si se tiene un algoritmo para determinar la resolubilidad en racionales no negativos, podrá usarse fácilmente para determinar la resolubilidad en los racionales). Sin embargo, el conocimiento de que no existe el algoritmo que reclamaba Hilbert no nos aporta ninguna información sobre otras estructuras. Puede existir o no para ellas.

Se ha trabajado mucho en la aplicación del décimo problema de Hilbert a los anillos de enteros de cuerpos algebraicos de números. Basándose en trabajos anteriores de Jan Denef y Leonard Lipschitz, y usando la teoría de clases, Harold N. Shapiro y Alexandra Shlapentokh consiguieron demostrar:

El décimo problema de Hilbert es irresoluble para el anillo de integridad de cualquier cuerpo numérico algebraico cuyo grupo de Galois sobre los racionales sea abeliano.

Shlapentokh y Thanases Pheidas (trabajando independientemente) obtuvieron el mismo resultado para cuerpos algebraicos de números que admitan exactamente un par de encajes complejos conjugados.

El problema del anillo de integridad de los cuerpos numéricos algebraicos distintos de los cubiertos por los resultados anteriores sigue estando sin resolver. Asimismo, y pese a despertar mucho interés, el problema sigue también abierto para las ecuaciones sobre los racionales.

Notas

  1. Antiguamente era frecuente clasificar primero los números en racionales e irracionales; los primeros podían ser racionales enteros o racionales fraccionarios. Puede verse en Llave aritmética y algebrayca escrita por D. Manuel Poy y Comes, 1790, p. 10. Se encuentra «entero racional» en Kronecker o en Gauss.
  2. En realidad, el décimo problema no fue uno de los 10 que se presentaron oral y directamente al auditorio; formaba parte de los 13 que se publicaron después de la reunión.
  3. A.G. Hamilton, p. 169.
  4. Se considera número natural al  , como es tradicional en lógica matemática.
  5. Esa conjetura pasó a ser en 2004 el Teorema de Green y Tao, tras ser demostrada por Ben Green y Terence Tao.
  6. Una revisión del papel conjunto de Davis, Putnam y Robinson, en Mathematical Reviews (MR 0133227) conjeturaba, en efecto, la falsedad de  
  7. Los enunciados o sentencias   son de uno de los niveles más bajos de la llamada jerarquía aritmética.
  8. Así, la propia conjetura de Goldbach puede expresarse diciendo que para cada número natural   el número   es la suma de dos números primos. Por supuesto, hay un algoritmo simple que puede comprobar si un número dado es la suma de dos primos.
  9. De hecho, tal equivalencia es demostrable en aritmética de Peano.
  10. En este nivel de conocimiento, ni siquiera 3 puede excluirse como una cota superior absoluta.

Bibliografía

Del artículo original en inglés

  • Yuri V. Matiyasevich, Hilbert's Tenth Problem, MIT Press, Cambridge, Massachusetts, 1993.
  • Martin Davis, Yuri Matiyasevich, and Julia Robinson, "Hilbert's Tenth Problem: Diophantine Equations: Positive Aspects of a Negative Solution," Proceedings of Symposia in Pure Mathematics, vol.28(1976), pp. 323-378; reprinted in The Collected Works of Julia Robinson, Solomon Feferman, editor, pp.269-378, American Mathematical Society 1996.
  • Martin Davis, "Hilbert's Tenth Problem is Unsolvable," American Mathematical Monthly, vol.80(1973), pp. 233-269; reprinted as an appendix in Martin Davis, Computability and Unsolvability, Dover reprint 1982.
  • Jan Denef, Leonard Lipschitz, Thanases Pheidas, Jan van Geel, editors, "Hilbert's Tenth Problem: Workshop at Ghent University, Belgium, November 2-5, 1999." Contemporary Mathematics vol. 270(2000), American Mathematical Society.

En español

Véase también

Enlaces externos

  • Hilbert's Tenth Problem page!
  • Zhi Wei Sun: On Hilbert's Tenth Problem and Related Topics
  •   Datos: Q986147

décimo, problema, hilbert, décimo, problema, hilbert, conocidos, como, veintitrés, problemas, hilbert, publicados, 1900, matemático, alemán, david, hilbert, enunciado, original, dada, ecuación, diofántica, cualquier, número, incógnitas, coeficientes, numéricos. El decimo problema de Hilbert es uno de los conocidos como veintitres Problemas de Hilbert publicados en 1900 por el matematico aleman David Hilbert Su enunciado original es Dada una ecuacion diofantica con cualquier numero de incognitas y con coeficientes numericos racionales enteros Idear un proceso de acuerdo con el cual pueda determinarse en un numero finito de operaciones si la ecuacion es resoluble en numeros racionales enteros En terminos de programacion informatica Hilbert solicitaba a sus colegas del futuro un algoritmo capaz de admitir como entrada input una ecuacion diofantica cualquiera y de devolver SI como resultado output si la ecuacion procesada tenia soluciones en numeros enteros o NO si la ecuacion procesada carecia de soluciones en numeros enteros El problema no se resolvio hasta 70 anos despues y en sentido negativo En 1970 Yuri Matiyasevich culmino mas de veinte anos de trabajo de varios matematicos entre ellos Martin Davis Julia Robinson y Hilary Putnam con la demostracion de imposibilidad del decimo problema ningun algoritmo es capaz de determinar la resolubilidad de cualquier ecuacion diofantica El planteamiento desarrollo y demostracion del problema tienen gran interes en matematica moderna porque en ellos participan conceptos de teoria de numeros y de logica matematica y se abren nuevos campos de investigacion en ambas disciplinas Indice 1 Formulacion 1 1 Equivalencia del problema en ℕ y en ℤ 2 Conjuntos diofanticos 2 1 Un conjunto es diofantico si y solo si es recursivamente enumerable 3 Historia 4 Aplicaciones 5 Resultados adicionales 6 Extensiones del decimo problema de Hilbert 7 Notas 8 Bibliografia 8 1 Del articulo original en ingles 8 2 En espanol 9 Vease tambien 10 Enlaces externosFormulacion EditarLas palabras proceso y numero finito de operaciones de su enunciado original sugieren claramente que Hilbert pedia un algoritmo El termino racional entero se refiere simplemente a los numeros enteros positivos negativos o cero 0 1 2 displaystyle 0 pm 1 pm 2 ldots 1 Por tanto Hilbert estaba pidiendo un algoritmo general que decidiera si un polinomio dado de coeficientes enteros una ecuacion diofantica tenia solucion en el dominio de los enteros Hoy sabemos que la respuesta es negativa no existe tal algoritmo general Puede que el propio Hilbert no confiara en su existencia Antes de presentar la lista de problemas parecia presagiar la ausencia de solucion diciendo En ocasiones ocurre que perseguimos la solucion basandonos en hipotesis insuficientes o en un sentido incorrecto y por eso fracasamos Entonces surge el problema demostrar la imposibilidad de obtener una solucion con tales hipotesis o en el sentido contemplado Otros opinan que la solucion de insolubilidad a la que se llego siete decadas despues no solo hubiera sorprendido al auditorio que asistio en 1900 en la Sorbona a la presentacion de Hilbert 2 sino posiblemente incluso al propio Hilbert ya que se esperaba obtener un conjunto de instrucciones que definieran un procedimiento y a lo que se llego finalmente fue a una demostracion de la inexistencia de tal conjunto de instrucciones 3 Equivalencia del problema en ℕ y en ℤ Editar Los trabajos de solucion del problema casi siempre se han planteado en terminos de enteros no negativos o numeros naturales N 0 1 2 3 displaystyle mathbb N 0 1 2 3 ldots 4 mas que con numeros enteros Es irrelevante porque puede demostrarse que si existiera un algoritmo que detectara la existencia de solucion en N displaystyle mathbb N podria usarse tambien para detectar la existencia de solucion en Z displaystyle mathbb Z En efecto conocido un algoritmo que detecte la resolubilidad en N displaystyle mathbb N podriamos usarlo para detectar si la ecuacion de n displaystyle n incognitas p x 1 x 2 x n 0 displaystyle p x 1 x 2 ldots x n 0 dd tiene solucion entera aplicando el hipotetico algoritmo a las 2 n displaystyle 2 n ecuacionesp x 1 x 2 x n 0 displaystyle p pm x 1 pm x 2 ldots pm x n 0 dd Inversamente un algoritmo capaz de detectar la resolubilidad en Z displaystyle mathbb Z puede usarse para determinar si una ecuacion dada es resoluble en N displaystyle mathbb N sin mas que sustituir cada incognita de la ecuacion por la suma de los cuadrados de cuatro nuevas variables enteras El teorema de Lagrange de los cuatro cuadrados garantiza que cualquier numero natural puede igualarse a la suma de los cuadrados de un maximo de cuatro numeros enteros Conjuntos diofanticos EditarSe denomina conjuntos diofanticos a los conjuntos de numeros naturales de pares de numeros naturales o de forma mas general de n displaystyle n tuplas de numeros naturales que tienen definiciones diofanticas Tanto un sistema de ecuaciones diofanticas simultaneas como una ecuacion diofantica individual pueden definir un conjunto diofantico porque el sistema p 1 0 p k 0 displaystyle p 1 0 ldots p k 0 es equivalente a la ecuacion individual p 1 2 p k 2 0 displaystyle p 1 2 ldots p k 2 0 Dicho de otro modo si existe una ecuacion o sistema diofantica cuya solucion sea el conjunto de n displaystyle n tuplas de numeros naturales C displaystyle C entonces C displaystyle C es un conjunto diofantico Un conjunto es diofantico si y solo si es recursivamente enumerable Editar Se define un conjunto recursivamente enumerable como un conjunto para el que existe un algoritmo que se detendra si su entrada es un elemento del conjunto pero seguira corriendo indefinidamente si su entrada no pertenece al conjunto El concepto de enumerabilidad recursiva pertenece al ambito de la teoria de la computabilidad tambien llamada teoria de la recursion cuyo desarrollo aporto una explicacion precisa de la nocion intuitiva de computabilidad algoritmica dando pleno rigor al concepto de enumerabilidad recursiva Resulta evidente que los conjuntos diofanticos son por definicion recursivamente enumerables Dada una ecuacion o sistema diofantico pueden formarse secuencialmente todas las tuplas posibles de valores de las incognitas y despues para un valor dado de los parametros comprobar una tras otra las tuplas para detectar si son o no solucion de la ecuacion o sistema Luego la propia ecuacion o sistema que define el conjunto diofantico define el algoritmo que avala la enumerabilidad recursiva del conjunto La imposibilidad de resolver el decimo problema de Hilbert es consecuencia de que el inverso tambien es cierto Todo conjunto recursivamente enumerable es diofantico Este resultado se conoce de dos formas como Teorema de Matiyasevich porque fue Yuri Matiyasevich el que consiguio el desarrollo final que permitio demostrar el teorema y como Teorema MRDP nombre que agrupa a los matematicos que consiguieron el desarrollo completo empezando por el citado Matiyasevich para continuar por Julia Robinson Martin Davis y Hilary Putnam Dado que existe un conjunto recursivamente enumerable que no es computable la irresolubilidad del decimo problema de Hilbert es una consecuencia inmediata De hecho puede decirse mas Existe un polinomio p a x 1 x n displaystyle p a x 1 ldots x n con coeficientes enteros tal que el conjunto de valores de a displaystyle a para el que la ecuacion p a x 1 x n 0 displaystyle p a x 1 ldots x n 0 tiene soluciones en los numeros naturales no es computable Asi pues no solo no existe un algoritmo general para detectar la resolubilidad de las ecuaciones diofanticas sino que tambien puede demostrarse que ni siquiera existe un algoritmo particular para la familia de ecuaciones con un unico parametro Historia EditarAno Sucesos1944 Emil Leon Post declara que el decimo problema de Hilbert esta implorando una prueba de irresolubilidad 1949 Martin Davis utiliza el metodo de Kurt Godel para aplicar el teorema chino del residuo como truco de codificacion para obtener en su forma normal conjuntos recursivamente enumerables a y k y x 1 x n p a k y x 1 x n 0 displaystyle a mid exists y forall k leq y exists x 1 ldots x n p a k y x 1 ldots x n 0 donde p displaystyle p es un polinomio con coeficientes enteros Formalmente solo el cuantificador universal estorba para que se considere esto como una definicion diofantica de conjuntos Usando una prueba no constructiva pero muy sencilla Davis noto que hay un conjunto diofantico cuyo complementario no es diofantico Dado que los conjuntos recursivamente enumerables tampoco son cerrados para el complemento Davis conjeturo la identidad de ambas clases 1950 Julia Robinson no conocia el trabajo de Davis pero sospechando que la funcion exponencial era de importancia clave intentaba demostrar que EXP el conjunto de tripletes a b c displaystyle a b c para los cuales a b c displaystyle a b c es diofantico No tuvo exito lo que la condujo a su hipotesis luego llamada J R displaystyle J R Existe un conjunto diofantico D displaystyle D de pares a b displaystyle a b tal que a b D b lt a a displaystyle a b in D Rightarrow b lt a a pero para cada k gt 0 displaystyle k gt 0 a b D displaystyle exists a b in D tal que b gt a k displaystyle b gt a k Usando algunas propiedades de la ecuacion de Pell Robinson demostro que J R displaystyle J R implica que EXP es diofantico Y finalmente demostro que si EXP es diofantico entonces tambien lo son los coeficientes binomiales el factorial y los primos 1959 Trabajando juntos Davis y Putnam estudiaron los conjuntos diofanticos exponenciales es decir los conjuntos definibles por ecuaciones diofanticas en los que algunos de los exponentes pueden ser incognitas Usando la forma normal de Davis junto con los metodos de Robinson pero suponiendo la entonces indemostrada conjetura de que hay progresiones aritmeticas arbitrariamente largas compuestas de numeros primos 5 demostraron que todo conjunto recursivamente enumerable es un conjunto exponencial diofantico y que como consecuencia J R displaystyle J R implicaba que todo conjunto recursivamente enumerable es diofantico y que el decimo problema de Hilbert es irresoluble 1960 Robinson mostro como evitar el uso de la indemostrada conjetura de los numeros primos en progresiones aritmeticas y simplifico notablemente la demostracion J R displaystyle J R se revelaba como la clave para seguir avanzando aunque muchos dudaban de su veracidad 6 1961 1969 Davis y Putnam encontraron algunas proposiciones que implicaban J R displaystyle J R Matiyasevich publico algunas reducciones del decimo problema de Hilbert Robinson demostro que la existencia de un conjunto diofantico infinito de primos bastaria para demostrar J R displaystyle J R 1970 Matiyasevich presento un sistema de 10 ecuaciones simultaneas de primer y segundo grado que aportaba una definicion diofantica del conjunto de pares a b displaystyle a b tal que b F 2 a displaystyle b F 2a donde F n displaystyle F n es el n simo numero de Fibonacci Con esto quedaba demostrado J R displaystyle J R completandose por tanto la prueba de que todos los conjuntos recursivamente enumerables son diofanticos lo que implica que el decimo problema de Hilbert es irresoluble Aplicaciones EditarEl teorema de Matiyasevich MRDP relaciona dos conceptos uno procedente de la teoria de la computabilidad y el otro de la teoria de numeros y tiene algunas consecuencias inesperadas Quizas la mas sorprendente sea la existencia de una ecuacion diofantica universal Existe un polinomio p a n x 1 x k displaystyle p a n x 1 ldots x k tal que dado cualquier conjunto diofantico S displaystyle S hay un numero n 0 displaystyle n 0 tal queS a x 1 x k p a n 0 x 1 x k 0 displaystyle S a mid exists x 1 ldots x k p a n 0 x 1 ldots x k 0 dd Puede verse que esto es cierto simplemente porque hay maquinas universales de Turing capaces de ejecutar cualquier algoritmo Precisamente esta consecuencia de J R displaystyle J R es la que habia despertado mas suspicacias haciendo dudar de la veracidad de la hipotesis de Julia Robinson Hilary Putnam ha hecho notar que para cada conjunto diofantico S displaystyle S de enteros positivos existe un polinomio q x 0 x 1 x n displaystyle q x 0 x 1 ldots x n tal que S displaystyle S esta formado precisamente por los numeros positivos entre los valores supuestos por q displaystyle q como las variables x 0 x 1 x n displaystyle x 0 x 1 ldots x n recorren todos los numeros naturales Esto puede verse como sigue si p a y 1 y n 0 displaystyle p a y 1 ldots y n 0 proporciona una definicion diofantica de S displaystyle S entonces ello basta para fijar q x 0 x 1 x n x 0 1 p x 0 x 1 x n 2 displaystyle q x 0 x 1 ldots x n x 0 1 p x 0 x 1 ldots x n 2 Asi por ejemplo hay un polinomio para el cual la parte positiva de este intervalo son exactamente los numeros primos por otro lado sin embargo no existe ningun polinomio que devuelva solo numeros primos Otras aplicaciones tienen que ver con lo que los logicos denominan proposiciones P 1 0 displaystyle Pi 1 0 llamadas tambien a veces proposiciones de tipo Goldbach 7 Estas son como la conjetura de Goldbach propuestas que asignan a todo numero natural una propiedad que es comprobable algoritmicamente para cada numero en particular 8 El teorema de Matiyasevich MRDP implica que cada una de tales proposiciones es equivalente a un enunciado que afirma que existe una ecuacion diofantica particular que carece de solucion en los numeros naturales 9 Cierto numero de problemas importantes y bien conocidos tienen esta forma entre ellos el ultimo teorema de Fermat la hipotesis de Riemann y el teorema de los cuatro colores Ademas la afirmacion de que algunos sistemas formales tales como la aritmetica de Peano o el sistema ZFC son consistentes puede expresarse como sentencias P 1 0 displaystyle Pi 1 0 La idea es seguir la estrategia de Kurt Godel de codificacion mediante numeros naturales de forma tal que la propiedad de ser el numero que representa a una demostracion sea algoritmicamente comprobable Los enunciados P 1 0 displaystyle Pi 1 0 tienen la propiedad de que en el caso de ser falsos tal falsedad sera siempre demostrable en cualquiera de los sistemas formales en uso Esto se debe a que la falsedad determina la existencia de un contraejemplo que puede ser verificado por aritmetica simple Asi si en uno de estos sistemas formales no pueden probarse ni la proposicion P 1 0 displaystyle Pi 1 0 ni su negacion esa proposicion debe ser verdadera Una forma particularmente impactante del teorema de incompletitud de Godel es asimismo consecuencia del teorema de Matiyasevich MRDP Sea p a x 1 x k 0 displaystyle p a x 1 ldots x k 0 una definicion diofantica de un conjunto no computable Sea A displaystyle A un algoritmo que devuelve una sucesion de numeros naturales n displaystyle n tal que la ecuacion correspondiente p n x 1 x k 0 displaystyle p n x 1 ldots x k 0 carece de soluciones en los numeros naturales Entonces existe un numero n 0 displaystyle n 0 que no es devuelto por A displaystyle A en tanto que de hecho la ecuacion p n 0 x 1 x k 0 displaystyle p n 0 x 1 ldots x k 0 carece de soluciones en los numeros naturales Para darse cuenta de que el teorema es cierto basta con observar que si no existiera tal numero n 0 displaystyle n 0 se podria testar algoritmicamente la pertenencia de un numero n displaystyle n a ese conjunto no computable haciendo correr simultaneamente el algoritmo A displaystyle A para comprobar si devuelve n displaystyle n al tiempo que se comprueban todas las posibles k displaystyle k tuplas de numeros naturales buscando una solucion de la ecuacion p n x 1 x k 0 displaystyle p n x 1 ldots x k 0 Podemos asociar un algoritmo A displaystyle A con cualquiera de los sistemas formales en uso tales como la Aritmetica de Peano o ZFC dejando que el algoritmo genere sistematicamente consecuencias de los axiomas y devuelva un numero n displaystyle n cada vez que se genere una proposicion de la forma x 1 x k p n x 1 x k 0 displaystyle neg exists x 1 ldots x k p n x 1 ldots x k 0 Entonces el teorema nos dice que o bien una proposicion falsa del sistema sera demostrada de esta forma o bien una verdadera quedara sin demostrar en el sistema en cuestion lo que demuestra la incompletitud del sistema Resultados adicionales EditarPodemos aludir al grado de un conjunto diofantico como el minimo grado de un polinomio en la ecuacion que defina el conjunto De forma similar podemos llamar dimension de un conjunto diofantico al menor numero de incognitas de una ecuacion que lo defina Dado que existe una ecuacion diofantica universal esta claro que ambas cantidades grado y dimension tienen cotas superiores absolutas Determinar estos valores maximos ha despertado mucho interes en los matematicos Ya en los anos 1920 Thoralf Skolem mostro que cualquier ecuacion diofantica es equivalente a una de grado 4 o inferior Su estrategia fue introducir nuevas incognitas anadiendo ecuaciones que las igualaban al cuadrado de una incognita o al producto de dos Repitiendo este proceso se obtiene un sistema de ecuaciones de segundo grado y sumando luego los cuadrados se pasa a otra de grado 4 Asi pues una ecuacion diofantica es de grado 4 o inferior si bien se desconoce si este resultado es el optimo Julia Robinson y Yuri Matiyasevich mostraron que todo conjunto diofantico tiene dimension menor o igual que 13 Despues Matiyasevich refino el metodo para demostrar que bastaba con 9 incognitas Aunque nadie imagina que este sorprendente resultado sea el mejor posible no ha habido progresos posteriores 10 Asi pues en particular no existe ningun algoritmo que pueda probar la resolubilidad en los enteros positivos de ecuaciones diofanticas de 9 incognitas o menos Para el caso de numeros enteros como Hilbert habia planteado inicialmente el truco de los cuatro cuadrados muestra que no hay algoritmo para ecuaciones que no tengan mas de 36 incognitas Pero Zhi Wei Sun demostro que tratandose de numeros enteros el problema es irresoluble incluso para ecuaciones que no excedan las 11 incognitas Martin Davis estudio problemas algoritmicos relacionados con el numero de soluciones de una ecuacion diofantica El decimo problema de Hilbert reclama un algoritmo que decida si el numero de soluciones es 0 displaystyle 0 o distinto de 0 displaystyle 0 Supongamos que A 0 1 2 3 ℵ 0 displaystyle A 0 1 2 3 ldots aleph 0 y sea C displaystyle C un subconjunto estricto y no vacio de A displaystyle A Davis demostro que no existe algoritmo que pueda decidir si una ecuacion diofantica dada tiene un numero de soluciones que sea elemento del conjunto C displaystyle C Por tanto no existe ningun algoritmo que pueda determinar si el numero de soluciones es finito o infinito par o impar primo o compuesto cuadrado perfecto etc Extensiones del decimo problema de Hilbert EditarAunque Hilbert propuso el problema para el caso de los racionales enteros es claro que la pregunta puede hacerse para muchos anillos Ejemplos obvios son los anillos de enteros de cuerpos numericos algebraicos asi como los numeros racionales Seguramente Hilbert era consciente de que un algoritmo como el que estaba reclamando podria extenderse a esas estructuras Por ejemplo la ecuacion p x 1 x k 0 displaystyle p x 1 ldots x k 0 donde p displaystyle p es un polinomio de grado d displaystyle d es resoluble en los numeros racionales negativos si y solo si z 1 d p x 1 z 1 x k z 1 0 displaystyle z 1 d p left frac x 1 z 1 ldots frac x k z 1 right 0 es resoluble en los numeros naturales si se tiene un algoritmo para determinar la resolubilidad en racionales no negativos podra usarse facilmente para determinar la resolubilidad en los racionales Sin embargo el conocimiento de que no existe el algoritmo que reclamaba Hilbert no nos aporta ninguna informacion sobre otras estructuras Puede existir o no para ellas Se ha trabajado mucho en la aplicacion del decimo problema de Hilbert a los anillos de enteros de cuerpos algebraicos de numeros Basandose en trabajos anteriores de Jan Denef y Leonard Lipschitz y usando la teoria de clases Harold N Shapiro y Alexandra Shlapentokh consiguieron demostrar El decimo problema de Hilbert es irresoluble para el anillo de integridad de cualquier cuerpo numerico algebraico cuyo grupo de Galois sobre los racionales sea abeliano Shlapentokh y Thanases Pheidas trabajando independientemente obtuvieron el mismo resultado para cuerpos algebraicos de numeros que admitan exactamente un par de encajes complejos conjugados El problema del anillo de integridad de los cuerpos numericos algebraicos distintos de los cubiertos por los resultados anteriores sigue estando sin resolver Asimismo y pese a despertar mucho interes el problema sigue tambien abierto para las ecuaciones sobre los racionales Notas Editar Antiguamente era frecuente clasificar primero los numeros en racionales e irracionales los primeros podian ser racionales enteros o racionales fraccionarios Puede verse en Llave aritmetica y algebrayca escrita por D Manuel Poy y Comes 1790 p 10 Se encuentra entero racional en Kronecker o en Gauss En realidad el decimo problema no fue uno de los 10 que se presentaron oral y directamente al auditorio formaba parte de los 13 que se publicaron despues de la reunion A G Hamilton p 169 Se considera numero natural al 0 displaystyle 0 como es tradicional en logica matematica Esa conjetura paso a ser en 2004 el Teorema de Green y Tao tras ser demostrada por Ben Green y Terence Tao Una revision del papel conjunto de Davis Putnam y Robinson en Mathematical Reviews MR 0133227 conjeturaba en efecto la falsedad de J R displaystyle J R Los enunciados o sentencias P 1 0 displaystyle Pi 1 0 son de uno de los niveles mas bajos de la llamada jerarquia aritmetica Asi la propia conjetura de Goldbach puede expresarse diciendo que para cada numero natural n displaystyle n el numero 2 n 4 displaystyle 2n 4 es la suma de dos numeros primos Por supuesto hay un algoritmo simple que puede comprobar si un numero dado es la suma de dos primos De hecho tal equivalencia es demostrable en aritmetica de Peano En este nivel de conocimiento ni siquiera 3 puede excluirse como una cota superior absoluta Bibliografia EditarDel articulo original en ingles Editar Yuri V Matiyasevich Hilbert s Tenth Problem MIT Press Cambridge Massachusetts 1993 Martin Davis Yuri Matiyasevich and Julia Robinson Hilbert s Tenth Problem Diophantine Equations Positive Aspects of a Negative Solution Proceedings of Symposia in Pure Mathematics vol 28 1976 pp 323 378 reprinted in The Collected Works of Julia Robinson Solomon Feferman editor pp 269 378 American Mathematical Society 1996 Martin Davis Hilbert s Tenth Problem is Unsolvable American Mathematical Monthly vol 80 1973 pp 233 269 reprinted as an appendix in Martin Davis Computability and Unsolvability Dover reprint 1982 Jan Denef Leonard Lipschitz Thanases Pheidas Jan van Geel editors Hilbert s Tenth Problem Workshop at Ghent University Belgium November 2 5 1999 Contemporary Mathematics vol 270 2000 American Mathematical Society En espanol Editar Hamilton A G 1981 Logica para matematicos Madrid Paraninfo ISBN 84 283 1101 3 du Sautoy Marcus 2007 La musica de los numeros primos Barcelona ACANTILADO ISBN 978 84 96489 83 7 Vease tambien EditarProblemas de HilbertEnlaces externos EditarHilbert s Tenth Problem a History of Mathematical Discovery Hilbert s Tenth Problem page Zhi Wei Sun On Hilbert s Tenth Problem and Related Topics Datos Q986147Obtenido de https es wikipedia org w index php title Decimo problema de Hilbert amp oldid 133464742, wikipedia, wiki, leyendo, leer, libro, biblioteca,

español

, española, descargar, gratis, descargar gratis, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, imagen, música, canción, película, libro, juego, juegos