Decidibilidad sobre anillos: el décimo problema de Hilbert y variantes

El décimo problema de Hilbert, llamado así porque fue propuesto por David Hilbert en el año 1900, consiste en encontrar un algoritmo que permita determinar, para cualquier ecuación polinomial con coeficientes enteros, si la ecuación dada tiene solución en los enteros. Ahora bien, dada una ecuación polinomial, podemos reescribir esta ecuación como una sentencia en el lenguaje de los anillos utilizando cuantificadores existenciales para cada variable en el polinomio; de esta manera, la ecuación tiene solución en los enteros si y solo si la $\mathcal{L}$-estructura correspondiente a $\mathbb{Z}$ en el lenguaje de los anillos satisface la sentencia. Luego, la existencia del algoritmo solicitado por Hilbert es equivalente a la decidibilidad de la teoría existencial de $\mathbb{Z}$ en el lenguaje de los anillos. Sin embargo, como se demostraría varios años más tarde, esta teoría no es decidible y por lo tanto, el algoritmo buscado no existe ni se puede producir. El primer avance en esta dirección lo daría Kurt Gödel en 1931, quien en su Primer Teorema de Incompletitud demostró que la teoría de $\mathbb{Z}$ es indecidible. Es importante recalcar que Gödel no resuelve el décimo problema de Hilbert; pues su teorema aplica sobre el conjunto de todas las sentencias en el lenguaje de anillos, incluidas aquellas con cuantificadores universales. Más adelante, en 1970, Davis, Robinson, Putman y Matiyasevich demostrarían que la teoría existencial de los números enteros es indecidible y, por lo tanto, el décimo problema de Hilbert no tiene respuesta positiva. En general, el proyecto se centró en estudiar el décimo problema de Hilbert y algunas variantes que surgen naturalmente al conocer que este no se puede resolver. Así pues, el primer objetivo de este proyecto consistió en estudiar, reproducir y explicar detalladamente las ideas principales que permitieron concluir que el décimo problema de Hilbert es indecidible, resultado que se conoce como el teorema de Davis, Robinson, Putman y Matiyasevic. Ahora bien, tras conocer que el décimo problema de Hilbert es indecidible, es natural preguntarse si ocurre lo mismo si modificamos un poco la formulación original del problema. En general, se pueden plantear dos modificaciones: reducir las ecuaciones consideradas o ampliar el posible espacio de soluciones al remplazar $\Z$ por un anillo $\mathcal{R}$ que contenga a $\Z$. Respecto a la primera modificación mencionada, en este proyecto se buscó evaluar si el décimo problema de Hilbert es decidible si se limita el número de variables y el máximo grado de las ecuaciones polinomiales consideradas. Por otra parte, la segunda modificación considerada consiste en estudiar los avances que se han logrado para el caso $\mathcal{R} = \mathbb{Q}$, el cual sigue siendo un problema abierto. Uno de los principales avances en este problema lo realizó Julia Robinson en 1949 son su demostración de la indecidibilidad de los racionales. Robinson demostró que es posible definir $\mathbb{Z}$ en $\mathbb{Q}$ usando únicamente lógica de primer orden; así, si los racionales fueran definibles, también lo serían los enteros. Sin embargo, por el primer Teorema de Incompletitud de Gödel se sabe que $\mathbb{Z}$ no es decidible, por lo tanto, la teoría de los racionales tampoco puede serlo. De forma similar a lo ocurrido con el teorema de Gödel, Robinson demostró que la teoría ``completa'' de $\mathbb{Q}$ es indecidible, pero esto no implica que el décimo problema de Hilbert sobre $\Q$ sea indecidible. Sobre esta variante del problema original, se trabajó en explicar las principales ideas que utilizó Robinson para definir $\Z$ en $\Q$ y se mencionan los avances más recientes que llevan a pensar que el décimo problema de Hilbert también es indecidible en los racionales.

• Autores: Bravo Yaguchi, Andrés Takashi
• Tipo de recurso: Trabajo de grado de pregrado
• Fecha de publicación: 2023
• Institución: Universidad de los Andes
• Repositorio: Séneca: repositorio Uniandes
• Idioma: spa
• OAI Identifier: oai:repositorio.uniandes.edu.co:1992/73191
• Acceso en línea: https://hdl.handle.net/1992/73191
• Palabra clave: David Hilbert; Decidibilidad; Ecuaciones diofantinas; Julia Robinson; Yuri Matiyasevich; Décimo problema de Hilbert; Matemáticas
• Rights: openAccess
• License: Attribution-NonCommercial 4.0 International