Sobre proposiciones formalmente indecidibles de Principia Mathematica y sistemas relacionados - On Formally Undecidable Propositions of Principia Mathematica and Related Systems

Este artículo es sobre el papel. Para conocer los teoremas probados en este artículo, consulte los teoremas de incompletitud de Gödel .

" Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I " (" Sobre las proposiciones formalmente indecidibles de Principia Mathematica y sistemas relacionados I ") es un artículo sobre lógica matemática de Kurt Gödel . Entregado el 17 de noviembre de 1930, se publicó originalmente en alemán en el volumen de 1931 de Monatshefte für Mathematik . Varias traducciones al inglés han aparecido impresas y el artículo se ha incluido en dos colecciones de artículos clásicos de lógica matemática. El artículo contiene los teoremas de incompletitud de Gödel , ahora resultados fundamentales en lógica que tienen muchas implicaciones para las pruebas de consistencia en matemáticas. El artículo también es conocido por introducir nuevas técnicas que inventó Gödel para demostrar los teoremas de la incompletitud.

Resumen y resultados clave

Los principales resultados establecidos son el primer y segundo teoremas de incompletitud de Gödel , que han tenido un enorme impacto en el campo de la lógica matemática . Estos aparecen como teoremas VI y XI, respectivamente, en el artículo.

Para probar estos resultados, Gödel introdujo un método ahora conocido como numeración de Gödel . En este método, a cada oración y prueba formal en aritmética de primer orden se le asigna un número natural particular. Gödel muestra que muchas propiedades de estas demostraciones se pueden definir dentro de cualquier teoría aritmética que sea lo suficientemente fuerte como para definir las funciones recursivas primitivas . (La terminología contemporánea para funciones recursivas y funciones recursivas primitivas aún no se había establecido cuando se publicó el artículo; Gödel usó la palabra rekursiv ("recursiva") para lo que ahora se conoce como funciones recursivas primitivas). se vuelven comunes en la lógica matemática.

Debido a que el método de numeración de Gödel era novedoso, y para evitar cualquier ambigüedad, Gödel presentó una lista de 45 definiciones formales explícitas de funciones y relaciones recursivas primitivas utilizadas para manipular y probar los números de Gödel. Los usó para dar una definición explícita de una fórmula Bew ( x ) que es verdadera si y solo si x es el número de Gödel de una oración φ y existe un número natural que es el número de Gödel de una prueba de φ. El nombre de esta fórmula deriva de Beweis , la palabra alemana para prueba.

Una segunda técnica nueva inventada por Gödel en este artículo fue el uso de oraciones autorreferenciales. Gödel demostró que las paradojas clásicas de la autorreferencia, como " Esta afirmación es falsa ", pueden reformularse como oraciones aritméticas formales autorreferenciales. De manera informal, la oración empleada para probar el primer teorema de incompletitud de Gödel dice "Esta declaración no es demostrable". El hecho de que tal autorreferencia pueda expresarse dentro de la aritmética no se conocía hasta que apareció el artículo de Gödel; El trabajo independiente de Alfred Tarski sobre su teorema de indefinibilidad se llevó a cabo aproximadamente al mismo tiempo, pero no se publicó hasta 1936.

En la nota a pie de página 48a, Gödel declaró que una segunda parte planificada del artículo establecería un vínculo entre las pruebas de coherencia y la teoría de tipos, pero Gödel no publicó una segunda parte del artículo antes de su muerte. Sin embargo, su artículo de 1958 en Dialectica mostró cómo se puede utilizar la teoría de tipos para dar una prueba de coherencia para la aritmética.

Traducciones inglesas publicadas

Durante su vida se imprimieron tres traducciones al inglés del artículo de Gödel, pero el proceso no estuvo exento de dificultades. La primera traducción al inglés fue de Bernard Meltzer; fue publicado en 1963 como un trabajo independiente por Basic Books y desde entonces ha sido reimpreso por Dover y reimpreso por Hawking ( God Created the Integers , Running Press, 2005: 1097ff). La versión de Meltzer, descrita por Raymond Smullyan como una "buena traducción", fue revisada negativamente por Stefan Bauer-Mengelberg (1966). Según la biografía de Dawson de Gödel (Dawson 1997: 216),

Afortunadamente, la traducción de Meltzer pronto fue suplantada por una mejor preparada por Elliott Mendelson para la antología de Martin Davis The Undecidable ; pero tampoco se le llamó la atención de Gödel hasta casi el último minuto, y la nueva traducción todavía no era del todo de su agrado ... cuando se le informó que no había tiempo suficiente para considerar la sustitución de otro texto, declaró que la traducción de Mendelson era ' en general muy bien ”y accedió a su publicación. 3 [ 3 Después lamentaría haber cumplido, porque el volumen publicado estaba estropeado por una tipografía descuidada y numerosos errores de imprenta.]

La traducción de Elliott Mendelson aparece en la colección The Undecidable (Davis 1965: 5ss). Esta traducción también recibió una dura crítica por parte de Bauer-Mengelberg (1966), quien además de dar una lista detallada de los errores tipográficos también describió lo que él creía que eran errores graves en la traducción.

Una traducción de Jean van Heijenoort aparece en la colección From Frege to Gödel: A Source Book in Mathematical Logic (van Heijenoort 1967). Una revisión de Alonzo Church (1972) describió esto como "la traducción más cuidadosa que se ha hecho", pero también dio algunas críticas específicas. Dawson (1997: 216) señala:

La traducción que Gödel favoreció fue la de Jean van Heijenoort ... En el prefacio del volumen, van Heijenoort señaló que Gödel era uno de los cuatro autores que habían leído y aprobado personalmente las traducciones de sus obras.

Este proceso de aprobación fue laborioso. Gödel introdujo cambios en su texto de 1931, y las negociaciones entre los hombres fueron "prolongadas": "En privado, van Heijenoort declaró que Gödel era el individuo más obstinadamente fastidioso que había conocido". Entre ellos "intercambiaron un total de setenta cartas y se reunieron dos veces en la oficina de Gödel para resolver cuestiones relativas a sutilezas en los significados y el uso de las palabras en alemán e inglés". (Dawson 1997: 216-217).

Aunque no es una traducción del artículo original, existe una cuarta versión muy útil que "cubre un terreno bastante similar al cubierto por el artículo original de Godel de 1931 sobre indecidibilidad" (Davis 1952: 39), así como las propias extensiones de Gödel y comentario sobre el tema. Esto aparece como On Undecidable Propositions of Formal Mathematical Systems (Davis 1965: 39ff) y representa las conferencias transcritas por Stephen Kleene y J. Barkley Rosser mientras Gödel las pronunció en el Institute for Advanced Study en Princeton NJ en 1934. Dos páginas de erratas Davis añadió a esta versión correcciones adicionales de Gödel. Esta versión también es notable porque en ella Gödel describe por primera vez la sugerencia de Herbrand que dio lugar a la forma de recursividad (general, es decir, Herbrand-Gödel) .

Ver también

Referencias

  • Stefan Bauer-Mengelberg (1966). Revisión de Lo indecidible: artículos básicos sobre proposiciones indecidibles, problemas irresolubles y funciones computables. The Journal of Symbolic Logic , vol. 31, núm. 3. (septiembre de 1966), págs. 484–494.
  • Iglesia de Alonzo (1972). Revisión de un libro de consulta en lógica matemática 1879–1931. The Journal of Symbolic Logic , vol. 37, núm. 2. (junio de 1972), pág. 405.
  • Martin Davis , ed. (1965). Lo indecidible: artículos básicos sobre proposiciones indecidibles, problemas irresolubles y funciones computables , Raven, Nueva York. Reimpresión, Dover, 2004. ISBN  0-486-43228-9 .
  • Martin Davis , (2000). Motores de la lógica: las matemáticas y el origen de la computadora , W. w. Norton & Company, Nueva York. ISBN  0-393-32229-7 pbk.
  • Kurt Gödel (1931), "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I." Monatshefte für Mathematik und Physik 38 : 173-198. DOI 10.1007 / BF01700692 Disponible en línea a través de SpringerLink.
  • Kurt Gödel (1958). "Über eine bisher noch nicht benüzte Erweiterung des finiten Standpunktes". Dialectica v. 12, págs. 280–287. Reimpreso en traducción al inglés en Gödel's Collected Works , vol II, Soloman Feferman et al., Eds. Prensa de la Universidad de Oxford, 1990.
  • Jean van Heijenoort , ed. (1967). De Frege a Gödel: un libro de consulta sobre lógica matemática 1879-1931 . Prensa de la Universidad de Harvard.
  • Bernard Meltzer (1962). Sobre proposiciones formalmente indecidibles de Principia Mathematica y sistemas relacionados. Traducción del original alemán por Kurt Gödel, 1931. Basic Books, 1962. Reimpreso, Dover, 1992. ISBN  0-486-66980-7 .
  • Raymond Smullyan (1966). Revisión de Proposiciones formalmente indecidibles de Principia Mathematica y sistemas relacionados. The American Mathematical Monthly , vol. 73, núm. 3. (marzo de 1966), págs. 319–322.
  • John W. Dawson , (1997). Dilemas lógicos: la vida y obra de Kurt Gödel , AK Peters, Wellesley, MA. ISBN  1-56881-256-6 .

enlaces externos