En matemáticas , el segundo problema de Hilbert fue planteado por David Hilbert en 1900 como uno de sus 23 problemas . Solicita una prueba de que la aritmética es consistente , libre de contradicciones internas. Hilbert afirmó que los axiomas que consideró para la aritmética eran 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 sienten que los teoremas de Gödel dan una solución negativa al problema, mientras que otros consideran la demostración de Gentzen como una solución positiva parcial.
El problema de Hilbert y su interpretación
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 designar Las siguientes son las más importantes entre las numerosas preguntas que pueden plantearse con respecto a los axiomas: Demostrar que no son contradictorios, es decir, que un número definido de pasos lógicos basados en ellos nunca pueden conducir a resultados contradictorios. , la prueba de la compatibilidad de los axiomas puede efectuarse construyendo un campo de números adecuado, de manera que 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 a veces se malinterpreta, 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 pidió una prueba completa se parece más a la aritmética de segundo orden que a la aritmética de Peano de primer orden.
Como interpretación común hoy en día, 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.
Hay muchas pruebas conocidas de que la aritmética de Peano es consistente y que pueden llevarse a cabo en sistemas fuertes como la teoría de conjuntos de Zermelo-Fraenkel . Sin embargo, estos no proporcionan una resolució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 es mucho más fuerte) para probar 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 crea que la PA es consistente. Estos principios a menudo se denominan finitistas porque son completamente constructivos y no presuponen una infinidad completa de números naturales. El segundo teorema de incompletitud de Gödel (ver los teoremas de incompletitud de Gödel ) establece un límite severo sobre cuán débil puede ser un sistema finitista al mismo tiempo que demuestra la consistencia de la aritmética de Peano.
Teorema de incompletitud de Gödel
El segundo teorema de incompletitud de Gödel muestra que no es posible que ninguna prueba de que la aritmética de Peano sea consistente se lleve a cabo dentro de la aritmética de Peano misma. Este teorema muestra que si los únicos procedimientos de prueba aceptables son aquellos que se pueden formalizar dentro de la aritmética, entonces el llamado de Hilbert para una prueba de consistencia no puede ser respondido. Sin embargo, como explican Nagel y Newman (1958: 96-99), todavía hay espacio para una prueba que no se puede formalizar en aritmética:
- "Este imponente resultado del análisis de Godel no debe malinterpretarse: no excluye una prueba metamatemática de la consistencia de la aritmética. Lo que excluye es una prueba de consistencia que puede reflejarse en las deducciones formales de la aritmética. Demostraciones metamatemáticas de la consistencia de la aritmética, de hecho, han sido construidas, en particular por Gerhard Gentzen , un miembro de la escuela de Hilbert, en 1936, y por otros desde entonces ... Pero estas demostraciones metamatemáticas no pueden ser representadas dentro del cálculo aritmético ; y, dado que no son finitistas, no alcanzan los objetivos proclamados del programa original de Hilbert ... La posibilidad de construir una prueba de consistencia absoluta finitista para la aritmética no está excluida por los resultados de Gödel. Gödel demostró que tal prueba no es posible que se pueda representar dentro de la aritmética. Su argumento no elimina la posibilidad de pruebas estrictamente finitistas que no pueden ser representadas dentro de la aritmética. Hoy en día parece tener una idea clara de cómo sería una prueba finitista que no es capaz de formularse dentro de la aritmética ". [2]
Prueba de consistencia de Gentzen
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 . [3] Luego prueba por inducción transfinita en estos ordinales que ninguna prueba puede concluir en una contradicción. El método utilizado en esta demostración 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 coherencia en sí misma se puede llevar a cabo en la lógica ordinaria de primer orden utilizando los axiomas de primitiva recursiva. aritmética y un principio de inducción transfinito. Tait (2005) ofrece una interpretación de la 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 aritmética o teoría de conjuntos se les asignan números ordinales que miden la fuerza de consistencia de las teorías. Una teoría no podrá probar la consistencia de otra teoría con un ordinal teórico de prueba superior.
Puntos de vista modernos sobre el estado del problema
Si bien los teoremas de Gödel y Gentzen ahora son bien entendidos 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: sec. 3) sostiene que el teorema de incompletitud de Gödel muestra que no es posible producir pruebas de consistencia finitista de teorías fuertes. 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: p. 65) sostiene que el teorema de Gödel no impide una prueba de coherencia porque sus hipótesis podrían no aplicarse a todos los sistemas en los que podría llevarse a cabo una prueba de coherencia. Dawson (2006: sec. 2) llama "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.
Ver también
Notas
- ^ De la traducción al inglés de M. Newson, 1902 proporcionada por http://aleph0.clarku.edu/~djoyce/hilbert/problems.html .
- ↑ Una cita similar con variaciones menores en la redacción aparece en la edición de 2001 p.107-108, revisada por Douglas R. Hofstadter, New York University Press, NY, ISBN 0-8147-5816-9 .
- ^ En realidad, la prueba asigna una "notación" para un número ordinal a cada prueba. La notación es una cadena finita de símbolos que intuitivamente representa un número ordinal. Al representar el ordinal de una manera finita, la demostración de Gentzen no presupone axiomas fuertes con respecto a los números ordinales.
Referencias
- Dawson, John W. (2006) "¿Bases sacudidas o realineamiento innovador? Una evaluación centenaria del impacto de Kurt Gödel en la lógica, las matemáticas y la informática". 2006 21º Simposio Anual de IEEE sobre Lógica en Ciencias de la Computación , IEEE, págs. 339–341. ISBN 0-7695-2631-4 doi : 10.1109 / LICS.2006.47
- Michael Detlefsen (1990). "Sobre una supuesta refutación del programa de Hilbert utilizando el primer teorema de incompletitud de Gödel". Revista de lógica filosófica . Saltador. 19 (4): 343–377. doi : 10.1007 / BF00263316 .
- Torkel Franzen (2005), Teorema de Godel: Una guía incompleta para su uso y abuso , AK Peters, Wellesley MA. ISBN 1-56881-238-8
- Gerhard Gentzen (1936). "Die Widerspruchsfreiheit der reinen Zahlentheorie". Mathematische Annalen , v. 112, págs. 493–565.
- Gödel, Kurt (1931). "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I" . Monatshefte für Mathematik und Physik . 38 : 173–98. Archivado desde el original el 5 de julio de 2006.Traducido en Jean van Heijenoort , 1967. De Frege a Gödel: un libro de consulta sobre lógica matemática . Prensa de la Universidad de Harvard: 596-616.
- Hilbert, David (1900), "Über den Zahlbegriff" , Jahresbericht der Deutschen Mathematiker-Vereinigung , 8 : 180-184
- David Hilbert [1900] (1901) "Mathematische Probleme". Archiv der Mathematik und Physik , v. 3 n. 1, págs. 44–63 y 213–237. Traducción al inglés, Maby Winton, Bulletin of the American Mathematical Society 8 (1902), 437–479. Disponible en línea en http://aleph0.clarku.edu/~djoyce/hilbert/problems.html .
- George Kreisel (1976). "¿Qué hemos aprendido del segundo problema de Hilbert?". Desarrollos matemáticos que surgen de los problemas de Hilbert (Proc. Sympos. Pure Math., Northern Illinois Univ., De Kalb, Ill.,) . Providence, RI: Amer. Matemáticas. Soc. págs. 93-130. ISBN 0-8218-1428-1.
- Nagel, Ernest y Newman, James R., Godel's Proof , New York University Press, 1958.
- Stephen G. Simpson (1988). "Realizaciones parciales del programa de Hilbert". Revista de lógica simbólica . 53 (2): 349–363. CiteSeerX 10.1.1.79.5808 . doi : 10.2307 / 2274508 . ISSN 0022-4812 . JSTOR 2274508 .Disponible en línea en http://www.math.psu.edu/simpson/papers/hilbert.pdf .
- William W. Tait (2005). "La reformulación de Gödel de la primera prueba de coherencia de la aritmética de Gentzen: la interpretación sin contraejemplo". Boletín de lógica simbólica v. 11 n. 2, págs. 225-238.
enlaces externos
- Texto original de la charla de Hilbert, en alemán
- Traducción al inglés del discurso de Hilbert en 1900