En matemáticas , el segundo problema de Hilbert fue planteado por David Hilbert en 1900 como uno de sus 23 problemas . Pide una prueba de que la aritmética es consistente , libre de contradicciones internas. Hilbert afirmó que los axiomas que consideró para la aritmética fueron los dados en Hilbert (1900), que incluyen un axioma de completitud de segundo orden.
En la década de 1930, Kurt Gödel y Gerhard Gentzen demostraron resultados que arrojaron nueva luz sobre el problema. Algunos creen que los teoremas de Gödel dan una solución negativa al problema, mientras que otros consideran que la demostración de Gentzen es una solución positiva parcial.
En una traducción al inglés, Hilbert pregunta:
"Cuando nos dedicamos a investigar los fundamentos de una ciencia, debemos establecer un sistema de axiomas que contenga una descripción exacta y completa de las relaciones que subsisten entre las ideas elementales de esa ciencia... Pero sobre todo deseo señalar la siguiente como la más importante de las numerosas preguntas que pueden plantearse con respecto a los axiomas: demostrar que no son contradictorios, es decir, que un número determinado de pasos lógicos basados en ellos nunca puede conducir a resultados contradictorios. En geometría, la prueba de la compatibilidad de los axiomas puede efectuarse construyendo un campo adecuado de números, de modo que las relaciones análogas entre los números de este campo correspondan a los axiomas geométricos... Por otra parte, se necesita un método directo para la prueba de la compatibilidad de los axiomas aritméticos". [1]
La afirmación de Hilbert se malinterpreta a veces, porque con los "axiomas aritméticos" no se refería a un sistema equivalente a la aritmética de Peano, sino a un sistema más fuerte con un axioma de completitud de segundo orden. El sistema del que Hilbert pedía una prueba de completitud se parece más a la aritmética de segundo orden que a la aritmética de Peano de primer orden.
Como interpretación hoy en día común, una solución positiva a la segunda pregunta de Hilbert proporcionaría en particular una prueba de que la aritmética de Peano es consistente.
Existen muchas pruebas conocidas de que la aritmética de Peano es consistente que pueden llevarse a cabo en sistemas fuertes como la teoría de conjuntos de Zermelo-Fraenkel . Sin embargo, estas no proporcionan una solución a la segunda pregunta de Hilbert, porque es poco probable que alguien que dude de la consistencia de la aritmética de Peano acepte los axiomas de la teoría de conjuntos (que son mucho más fuertes) para demostrar su consistencia. Por lo tanto, una respuesta satisfactoria al problema de Hilbert debe llevarse a cabo utilizando principios que serían aceptables para alguien que no cree ya que la aritmética de Peano es consistente. Estos principios a menudo se denominan finitistas porque son completamente constructivos y no presuponen una infinitud completa de números naturales. El segundo teorema de incompletitud de Gödel (ver Teoremas de incompletitud de Gödel ) establece un límite severo a cuán débil puede ser un sistema finitista mientras sigue demostrando la consistencia de la aritmética de Peano.
El segundo teorema de incompletitud de Gödel muestra que no es posible llevar a cabo ninguna prueba de que la aritmética de Peano es consistente dentro de la propia aritmética de Peano. Este teorema muestra que si los únicos procedimientos de prueba aceptables son aquellos que pueden formalizarse dentro de la aritmética, entonces no se puede responder a la exigencia de Hilbert de una prueba de consistencia. Sin embargo, como explican Nagel y Newman (1958), todavía hay lugar para una prueba que no puede formalizarse en la aritmética: [2]
En 1936, Gentzen publicó una prueba de que la aritmética de Peano es consistente. El resultado de Gentzen muestra que se puede obtener una prueba de consistencia en un sistema que es mucho más débil que la teoría de conjuntos.
La prueba de Gentzen procede asignando a cada prueba en la aritmética de Peano un número ordinal , basado en la estructura de la prueba, con cada uno de estos ordinales menor que ε 0 . [4] Luego demuestra por inducción transfinita sobre estos ordinales que ninguna prueba puede concluir en una contradicción. El método utilizado en esta prueba también se puede utilizar para demostrar un resultado de eliminación de corte para la aritmética de Peano en una lógica más fuerte que la lógica de primer orden, pero la prueba de consistencia en sí misma se puede llevar a cabo en la lógica ordinaria de primer orden utilizando los axiomas de la aritmética recursiva primitiva y un principio de inducción transfinita. Tait (2005) da una interpretación de teoría de juegos del método de Gentzen.
La prueba de consistencia de Gentzen inició el programa de análisis ordinal en la teoría de la prueba. En este programa, a las teorías formales de la aritmética o de la teoría de conjuntos se les asignan números ordinales que miden la fuerza de la consistencia de las teorías. Una teoría no podrá demostrar la consistencia de otra teoría con un ordinal teórico de prueba superior.
Aunque los teoremas de Gödel y Gentzen son bien comprendidos por la comunidad de lógica matemática, no se ha formado un consenso sobre si (o de qué manera) estos teoremas responden al segundo problema de Hilbert. Simpson (1988) sostiene que el teorema de incompletitud de Gödel muestra que no es posible producir pruebas de consistencia finitista de teorías fuertes. [5] Kreisel (1976) afirma que aunque los resultados de Gödel implican que no se puede obtener una prueba de consistencia sintáctica finitista, se pueden usar argumentos semánticos (en particular, de segundo orden ) para dar pruebas de consistencia convincentes. Detlefsen (1990) sostiene que el teorema de Gödel no impide una prueba de consistencia porque sus hipótesis podrían no aplicarse a todos los sistemas en los que se podría llevar a cabo una prueba de consistencia. [6] Dawson (2006) califica de "errónea" la creencia de que el teorema de Gödel elimina la posibilidad de una prueba de consistencia persuasiva, citando la prueba de consistencia dada por Gentzen y una posterior dada por Gödel en 1958. [ 7]