El Desarrollo De La Teoría De La Prueba

Tabla de contenido:

El Desarrollo De La Teoría De La Prueba
El Desarrollo De La Teoría De La Prueba

Vídeo: El Desarrollo De La Teoría De La Prueba

Vídeo: El Desarrollo De La Teoría De La Prueba
Vídeo: Pruebas evolutivas embriológicas 2024, Marzo
Anonim

Navegación de entrada

  • Contenido de entrada
  • Bibliografía
  • Herramientas académicas
  • Vista previa de PDF de amigos
  • Información de autor y cita
  • Volver arriba

El desarrollo de la teoría de la prueba

Publicado por primera vez el miércoles 16 de abril de 2008; revisión sustantiva lun oct 13, 2014

El desarrollo de la teoría de la prueba se puede dividir naturalmente en: la prehistoria de la noción de prueba en la lógica y las matemáticas antiguas; el descubrimiento de Frege de que las pruebas matemáticas, y no solo las proposiciones de las matemáticas, pueden (y deberían) representarse en un sistema lógico; La vieja teoría de la prueba axiomática de Hilbert; fracaso de los objetivos de Hilbert a través de los teoremas de incompletitud de Gödel; La creación de Gentzen de los dos tipos principales de sistemas lógicos de la teoría de la prueba contemporánea, la deducción natural y el cálculo secuencial (ver la entrada sobre razonamiento automatizado); aplicaciones y extensiones de deducción natural y cálculo secuencial, hasta la interpretación computacional de la deducción natural y sus conexiones con la informática.

  • 1. Prehistoria de la noción de prueba.
  • 2. La vieja teoría de la prueba axiomática de Hilbert
  • 3. La improbabilidad de la consistencia.
  • 4. Deducción natural y cálculo posterior.
  • 5. La consistencia de la aritmética y el análisis.
  • 6. Desarrollos posteriores en la deducción natural.
  • 7. Cálculo secuencial: desarrollos / aplicaciones posteriores
  • 8. Los objetivos de la teoría de la prueba.
  • Bibliografía

    • Textos sobre teoría de la prueba
    • Obras originales y sus reimpresiones
    • Literatura secundaria
  • Herramientas académicas
  • Otros recursos de internet
  • Entradas relacionadas

1. Prehistoria de la noción de prueba

La teoría de la prueba se puede describir como el estudio de la estructura general de las pruebas matemáticas y de los argumentos con fuerza demostrativa como se encuentran en la lógica. La idea de tales argumentos demostrativos, es decir, aquellos cuya conclusión se deriva necesariamente de los supuestos formulados, es central en Analytica Posteriora de Aristóteles: una ciencia deductiva se organiza en torno a una serie de conceptos básicos que se suponen entendidos sin más explicaciones, y un número de verdades o axiomas básicos que se consideran verdaderos de inmediato. Los conceptos y teoremas definidos se reducen a estos dos, el último a través de la prueba. El relato de la prueba de Aristóteles como argumento demostrativo se ajusta muy bien a la estructura de la geometría antigua como axiomatizada en Euclides. La forma específica de la lógica de Aristóteles, la teoría del silogismo tiene en su lugar, por lo que parece,casi nada que ver con las pruebas en geometría euclidiana. Estas pruebas permanecieron intuitivas durante más de dos mil años.

Antes del trabajo de Frege en 1879, nadie parece haber sostenido que podría haber un conjunto completo de principios de prueba, en el sentido expresado por Frege cuando escribió eso en su lenguaje simbólico,

todo lo necesario para una inferencia correcta se expresa en su totalidad, pero lo que no es necesario generalmente no se indica; No queda nada para adivinar. (Begriffsschrift, p. 3)

(Se podría afirmar que Boole es una excepción en lo que respecta a la lógica proposicional clásica). El paso adelante de Frege fue decisivo para el desarrollo de la lógica y el estudio fundacional. El contraste con los antiguos es genial: Aristóteles dio un patrón para combinar argumentos, pero la idea de un conjunto cerrado de reglas finitas estaba, filosóficamente, más allá de los sueños de cualquiera antes de Frege, con la posible excepción de Leibniz.

Como sabemos hoy, los principios de prueba de Frege son completos para la lógica de predicados clásica.

Alrededor de 1890, Giuseppe Peano dio una formalización de inferencia lógica, con el objetivo de representar formalmente pruebas en aritmética. Su artículo seminal Arithmetices principia, nova methodo exposita, escrito originalmente en latín, está incluido en la traducción al inglés de la colección From Frege to Gödel (1967) que editó Jean van Heijenoort. Desafortunadamente, el editor no reconoció lo que hizo Peano con la inferencia formal, y se difundió la opinión de que Peano formalizaba solo el lenguaje de la lógica y la aritmética, no sus principios de prueba. Si las pruebas de Peano se leen incluso con un poco de cuidado, resulta que son derivaciones puramente formales que usan dos principios:

  1. Los axiomas implican sus instancias. Tales implicaciones pueden escribirse como líneas en las pruebas.
  2. Una implicación y su antecedente implican juntos el consecuente.

Peano tiene mucho cuidado de enumerar, en cada línea de sus derivaciones, cuál es el fundamento formal para escribir la línea.

Russell adoptó la lógica de Frege, pero utilizó la notación y las reglas formales de prueba de Peano, en un documento de 1906 con el título "La teoría de la implicación". Su maquinaria formal es exactamente la misma que la de Peano. En trabajos posteriores, Russell cambió el sistema axiomático y el de Principia Mathematica (Whitehead y Russell 1910–13) se convirtió en estándar. La idea filosófica de Russell, y aquí siguió a Frege, era que los axiomas expresan verdades lógicas básicas, y otras verdades lógicas se derivan de ellas a través de modus ponens y generalización universal, los dos principios que Frege había identificado. Las matemáticas debían reducirse a la lógica, para que sus pruebas se presentaran en el mismo patrón axiomático.

El enfoque de la lógica de Frege y Peano-Russell se convirtió en el universalmente aceptado, especialmente a través de la influencia de Hilbert y sus compañeros de trabajo en la década de 1920. En el siglo XIX, Frege era una figura marginal, y el enfoque algebraico de la lógica, como en Boole y especialmente Ernst Schröder, era el dominante. Está claro que había una buena comprensión de los principios de la lógica de predicados en esta tradición, porque ¿cómo podría haber habido un teorema de Löwenheim-Skolem de otra manera? Skolem se enteró de la lógica de Frege a través de Principia Mathematica solo después de haber elaborado el teorema en su artículo de 1920. La primera sección de ese documento, ampliamente leída debido a la traducción al inglés de Van Heijenoort's From Frege to Gödel, marca el final del algebraico tradición de lógica que se fusionó silenciosamente con la teoría de la red. Otras secciones del documento contienen un comienzo notable del análisis de las pruebas en la teoría de la red y en la geometría proyectiva: Skolem consideró los axiomas de una teoría matemática desde un punto de vista puramente combinatorio y formal, como un medio para producir derivaciones de una fórmula a partir de fórmulas utilizadas como supuestos. A principios de la década de 1990 se descubrió que la parte de la teoría de celosía contiene la solución de un problema de decisión, llamado la palabra problema para celosías generadas libremente, ¡cuya solución conocida surgió de 1988! La terminología y notación de Skolem en la teoría de la red son las de Schröder y esa es parte de la razón por la cual su trabajo fue una oportunidad perdida para la teoría de la prueba. Skolem consideró los axiomas de una teoría matemática desde un punto de vista puramente combinatorio y formal, como un medio para producir derivaciones de una fórmula a partir de fórmulas dadas utilizadas como supuestos. A principios de la década de 1990 se descubrió que la parte de la teoría de celosía contiene la solución de un problema de decisión, llamado la palabra problema para celosías generadas libremente, ¡cuya solución conocida surgió de 1988! La terminología y notación de Skolem en la teoría de la red son las de Schröder y esa es parte de la razón por la cual su trabajo fue una oportunidad perdida para la teoría de la prueba. Skolem consideró los axiomas de una teoría matemática desde un punto de vista puramente combinatorio y formal, como un medio para producir derivaciones de una fórmula a partir de fórmulas dadas utilizadas como supuestos. A principios de la década de 1990 se descubrió que la parte de la teoría de celosía contiene la solución de un problema de decisión, llamado la palabra problema para celosías generadas libremente, ¡cuya solución conocida surgió de 1988! La terminología y notación de Skolem en la teoría de la red son las de Schröder y esa es parte de la razón por la cual su trabajo fue una oportunidad perdida para la teoría de la prueba.llamado el problema de la palabra para redes generadas libremente, cuya solución conocida surgió de 1988! La terminología y notación de Skolem en la teoría de la red son las de Schröder y esa es parte de la razón por la cual su trabajo fue una oportunidad perdida para la teoría de la prueba.llamado el problema de la palabra para redes generadas libremente, cuya solución conocida surgió de 1988! La terminología y notación de Skolem en la teoría de la red son las de Schröder y esa es parte de la razón por la cual su trabajo fue una oportunidad perdida para la teoría de la prueba.

2. La vieja teoría de la prueba axiomática de Hilbert

El libro de Hilbert Grundlagen der Geometrie de 1899 preparó el escenario para los problemas fundamentales de las matemáticas de las primeras décadas del siglo XX. Podemos enumerar estos problemas de la siguiente manera:

  1. La formalización de una teoría matemática. Esto incluye una elección de sus objetos y relaciones básicas, y una elección de los axiomas.
  2. Una prueba de la consistencia de los axiomas.
  3. La cuestión de la independencia mutua y la integridad de los axiomas.
  4. El problema de decisión: ¿hay algún método para responder cualquier pregunta que pueda surgir dentro de la teoría?

En cuanto a la geometría de Hilbert, su intento de formalización no alcanzó el ideal al que dio a luz. Hilbert encontró un campo mucho más importante en el que se aplicaría su "metamatemática", a saber, la aritmética y el análisis. El trabajo preliminar fue un estudio de los cuatro problemas fundamentales en las formulaciones axiomáticas de la lógica pura. La lógica proposicional se formalizó así, se encontró que era consistente y completa, y decidible. Los primeros resultados sobre la lógica de predicados son de 1915, cuando Leopold Löwenheim dio su versión de lo que luego se convirtió en el teorema de Löwenheim-Skolem para la lógica de predicados (ver la entrada sobre lógica clásica). También resolvió casos especiales del problema de decisión. Este desarrollo fue independiente de la tradición de Frege-Russell y, en cambio, se basó en el enfoque algebraico de la lógica de Ernst Schröder. Alrededor de 1920el enfoque axiomático del "estilo de Hilbert", como se le llama a menudo, era conocido por todos y dominaba la escena lógica; El enfoque algebraico se fusionó casi sin previo aviso con la teoría reticular. Para 1928, en Grundzüge der teoríatischen Logik de Hilbert y Ackermann, se presentó un sistema formal axiomático para la lógica de predicados, junto con el problema de su integridad. Este último fue resuelto por Gödel en 1929, publicado un año después (Gödel 1930). Se demostró que el cuarto problema fundamental, el problema de decisión para la lógica de predicados, tenía una solución negativa en un breve artículo de Church en 1936 como corolario del teorema de incompletitud de Gödel.s Grundzüge der teoríatischen Logik, se presentó un sistema formal axiomático para la lógica de predicados, junto con el problema de su integridad. Este último fue resuelto por Gödel en 1929, publicado un año después (Gödel 1930). Se demostró que el cuarto problema fundamental, el problema de decisión para la lógica de predicados, tenía una solución negativa en un breve artículo de Church en 1936 como corolario del teorema de incompletitud de Gödel.s Grundzüge der teoríatischen Logik, se presentó un sistema formal axiomático para la lógica de predicados, junto con el problema de su integridad. Este último fue resuelto por Gödel en 1929, publicado un año después (Gödel 1930). Se demostró que el cuarto problema fundamental, el problema de decisión para la lógica de predicados, tenía una solución negativa en un breve artículo de Church en 1936 como corolario del teorema de incompletitud de Gödel.

Hilbert y su escuela, con Bernays, Ackermann y von Neumann como los más destacados, así como el joven Herbrand en Francia, continuaron el estudio metamatemático de la aritmética en la última parte de la década de 1920. Hilbert desarrolló un método para el estudio de problemas de consistencia, llamado método de sustitución epsilon, para tratar con los cuantificadores. Sintió que las inferencias indirectas con cuantificadores en casos con una infinidad de objetos eran el punto crucial de las pruebas de consistencia y necesitaban una justificación. Digamos, si la suposición de que todos los números naturales tienen la propiedad P conduce a una imposibilidad, se puede inferir la existencia de un número con la propiedad contraria no-P. El problema central era, por lo tanto, justificar el uso de la lógica clásica en las pruebas matemáticas, las aritméticas en primer lugar. Ackermann estaba muy cerca de una solución hacia fines de la década de 1920 y el optimismo reinó en la escuela Hilbert. Luego, por supuesto, lo inesperado sucedió cuando Gödel demostró la imposibilidad de una formalización completa de la aritmética elemental y, como pronto se interpretó, la imposibilidad de probar la consistencia de la aritmética por medios finitarios, los únicos juzgados "absolutamente confiables" por Hilbert

3. La improbabilidad de la consistencia

Después de que Gödel hiciera público lo incompleto de la aritmética en septiembre de 1930, von Neumann descubrió que la consistencia de la aritmética estaría entre las proposiciones no probables de Gödelian. Por desgracia, Gödel había hecho el mismo descubrimiento, por lo que von Neumann nunca publicó su prueba. Sin embargo, conjeturó en correspondencia con Gödel la imposibilidad de probar la coherencia de la aritmética y, por lo tanto, de las matemáticas en su conjunto, en un sentido absoluto. Von Neumann fue el personaje clave en la recepción de los resultados de Gödel: interrumpió sus conferencias sobre la teoría de la prueba de Hilbert en Berlín en el otoño de 1930 para explicar los nuevos descubrimientos. Estos eventos crearon una enorme emoción entre los matemáticos, como lo atestigua el testimonio de Carl Hempel:

Tomé un curso allí con von Neumann que trataba sobre el intento de Hilbert de probar la consistencia de las matemáticas clásicas por medios finitarios. Recuerdo que en el medio del curso, von Neumann llegó un día y anunció que acababa de recibir un documento de … Kurt Gödel, quien demostró que los objetivos que Hilbert tenía en mente y sobre los que había escuchado el curso de Hilbert en Gotinga no podían ser alcanzado en absoluto. Von Neumann, por lo tanto, abandonó la búsqueda de este tema y dedicó el resto del curso a la presentación de los resultados de Gödel. El hallazgo provocó una enorme emoción. (Hempel 2000, p. 13)

En 1932–33, Gödel y Gentzen encontraron independientemente el uno del otro una traducción de la aritmética clásica de Peano a la aritmética intuitiva de Heyting. Específicamente, muestra que si una contradicción es demostrable en el primero, es demostrable en el segundo. Entonces la consistencia de la aritmética intuicionista garantizaría también la consistencia de la aritmética clásica. Este resultado fue una sorpresa: como se mencionó, Hilbert había pensado que las pruebas de existencia indirectas "transfinitas" serían la parte de la aritmética que debe asegurarse de la contradicción. Por el resultado de Gödel y Gentzen, la aritmética intuicionista ya contenía principios que iban más allá del razonamiento finitario. Una carta que Gentzen escribió a Heyting el 25 de febrero de 1933 resume la situación de la siguiente manera:

Una prueba de consistencia por medios finitos … no ha tenido éxito hasta ahora, por lo que este objetivo original de Hilbert no se ha logrado. Si, por otro lado, uno admite la posición intuicionista como una base segura en sí misma, es decir, como una base consistente, la consistencia de la aritmética clásica está asegurada por mi resultado. Si uno quisiera satisfacer los requisitos de Hilbert, la tarea aún sería mostrar una aritmética intuitiva consistente. Sin embargo, esto no es posible ni siquiera por el aparato formal de la aritmética clásica, sobre la base del resultado de Gödel en combinación con mi prueba. Aun así, me inclino a creer que una prueba de consistencia para la aritmética intuicionista, desde una posición aún más evidente, es posible y también deseable. (Menzler-Trott 2007, p. 38)

El último mencionado fue el objetivo que Gentzen se había fijado a principios de 1932, cuando en una carta a su antiguo maestro Hellmuth Kneser escribió:

Me he propuesto como tarea específica encontrar una prueba de la consistencia de la deducción lógica en aritmética … La tarea se convierte en un problema puramente matemático a través de la formalización de la deducción lógica. La prueba de consistencia se ha llevado a cabo hasta ahora solo para casos especiales, por ejemplo, la aritmética de los enteros sin la regla de inducción completa. Me gustaría seguir adelante en este punto y borrar al menos la aritmética con inducción completa. Estoy trabajando en esto desde hace casi un año y espero terminar pronto, y luego presentaría este trabajo como mi disertación (con el Prof. Bernays). (Menzler-Trott 2007, p. 31)

4. Deducción natural y cálculo posterior

Al perseguir su programa de coherencia, Gentzen estableció como su primera tarea el análisis de la deducción puramente lógica, que luego se extenderá a la aritmética y al análisis. En su tesis (1934–1935), Gentzen afirma que se propuso el análisis de las pruebas matemáticas tal como ocurren en la práctica. La primera observación es que las pruebas reales no se basan en axiomas expresados en un lenguaje lógico, como en la teoría de pruebas axiomáticas de Hilbert. La característica más típica es, en cambio, que los teoremas hacen sus afirmaciones bajo algunos supuestos. Los supuestos se analizan en partes y la conclusión también se analiza en partes hasta que estos dos análisis se encuentren y se pueda sintetizar una prueba. El último análisis procede de lo que Gentzen llamó reglas de introducción: dan condiciones suficientes para derivar una proposición de una forma dada. Por ejemplo,para derivar una conjunción A y B, es suficiente derivar los conjuntos A y B por separado. La inferencia se da formalmente como en la regla

AB &YO
A y B

Los supuestos, en cambio, se analizan en sus componentes a través de reglas de eliminación que dan, en general, consecuencias inmediatas de los supuestos. Por ejemplo, una conjunción utilizada como una suposición puede descomponerse en sus componentes, como en las reglas

A y B & E 1
UNA
A y B & E 2
si

Gentzen desarrolló y estudió el sistema de deducción natural durante 1932, y en septiembre de 1932 había llegado a un cálculo de deducción natural (ND para abreviar) que es estándar hoy en día. Para entonces, se había dado cuenta de que si una introducción, digamos una derivación de A y B de A y B por separado, es seguida por la eliminación correspondiente, digamos una derivación de A, la fórmula A y B constituye un máximo local, un " montículo ", que puede ser eliminado. También llamó a esos montículos "desvíos", y lo que ahora se llama conversión de desvío elimina esos pares innecesarios de pasos de introducción-eliminación. El resultado de los pasos de "normalización" es una derivación en "forma normal".

La implicación es quizás más típica de ND que conjunción: para derivar A ⊃ B, uno asume temporalmente A, luego intenta derivar B. Si esto tiene éxito, la suposición temporal se cierra o se "descarga" cuando se llega a la conclusión de A ⊃ B, como en la derivación esquemática

[UNA]
si ⊃I
A ⊃ B

En la otra dirección, A ⊃ B puede eliminarse si se encuentra una derivación de A, para entonces B puede concluirse:

A ⊃ BA ⊃E
si

Si la regla ⊃I es seguida por ⊃E, hay una no normalidad que se elimina mediante una conversión de desvío: una derivación de B (y lo que sigue después) se construye tomando la derivación de la premisa menor A de la regla de eliminación y la derivación de B del supuesto A en la introducción. Estas dos piezas se combinan en una derivación de B que no tiene la fórmula de desvío A ⊃ B. En la tesis de Gentzen, todos los supuestos están finalmente cerrados por introducciones de implicaciones, pero hoy en día también se consideran derivaciones que dejan una colección de fórmulas como supuestos abiertos.

Mirando las reglas de conjunción e implicación, uno nota que las premisas (las fórmulas inmediatamente arriba de la línea de inferencia) son subformulas de la conclusión en las reglas I, mientras que es al revés en las reglas E. Gentzen notó que en derivaciones normales, esta propiedad de los pasos individuales es heredada por toda la derivación, en el sentido de que todas las fórmulas son subformulas de la conclusión. Este resultado dio como subproducto un método de decisión para la lógica proposicional intuicionista. Otro corolario era una prueba sintáctica de consistencia: si una contradicción es demostrable, cualquier cosa es demostrable, pero una fórmula atómica, por ejemplo, no tiene prueba: si tiene una prueba, tiene una prueba normal, pero no se aplican reglas E a un fórmula atómica, y ninguna regla I lo concluye tampoco.

La idea de Gentzen era extender la deducción natural a un sistema de aritmética mediante la adición de una regla que corresponde al principio de inducción completa. La consistencia se derivaría de la normalización de derivaciones y la propiedad de subformula. A principios de 1933, Gentzen se dio cuenta de que esta estrategia de prueba no pasaría: la regla de inducción es esquemática y tiene una infinidad de instancias, sin límites en la complejidad de las fórmulas de inducción. Sería imposible restringir estas fórmulas de antemano, por lo tanto, no se puede mantener ninguna propiedad de subformula. Después de este fracaso, Gentzen sacó literalmente de su manuscrito de tesis inicial la traducción de la aritmética clásica a la intuitiva y la presentó como artículo en marzo de 1933, pero retiró el documento después de escuchar la publicación del resultado de Gödel.

Gentzen escribió que no pudo probar un teorema de normalización para un sistema clásico de ND. Por lo tanto, inventó otro cálculo lógico que llamó cálculo secuencial (Sequenzenkalkul, literalmente "cálculo de secuencias") y lo convirtió en el tema central de su tesis. El nombre del cálculo proviene de la representación de supuestos de una derivación como una lista. La palabra "secuenciante" utilizada como sustantivo es una sugerencia de Kleene en su Introducción a la metamatemática (1952: 441), tomada en muchos idiomas en forma de palabras puramente inventadas.

El cálculo secuencial, SC para abreviar, puede verse como una representación formal de la relación de derivabilidad en la deducción natural. Una secuencia consiste en una lista Γ de fórmulas, una flecha (en Gentzen, más tarde también se han utilizado otros marcadores) y una fórmula como conclusión. La lista da los supuestos de los que depende la conclusión en una derivación, en una notación local donde en ND se encuentran en las hojas de un árbol de derivación. Gentzen también generalizó las secuencias para que tengan, en lugar de una conclusión, una lista de posibles casos después de la flecha. Esta novedad condujo a la primera formulación satisfactoria de un sistema de prueba para la lógica clásica. Las reglas SC de Gentzen para conjunción e implicación son, con comas que separan elementos en listas:

Conjunción
Γ Δ, A Γ → Δ, B R &
Γ Δ, A y B
A, Γ Δ L y 1
A y B, Γ Δ
B, Γ Δ L y 2
A y B, Γ Δ
Implicación
A, Γ Δ, B R⊃
Γ Δ, A ⊃ B
Γ Θ, AB, Δ Λ L⊃
A ⊃ B, Γ, Δ Θ, Λ

Este no es el lugar para explicar los detalles de ND y SC (pero vea la entrada sobre razonamiento automatizado). Gentzen formuló este último, denominado LK, de modo que dio un cálculo intuicionista, denominado LJ, como un caso especial, en el que la conclusión es una lista de, como máximo, un caso. Luego probó el análogo del teorema de normalización para el cálculo clásico, el cálculo y la prueba cuidadosamente formulados para que el resultado para el cálculo intuicionista fuera un caso especial del del cálculo clásico. En LJ y LK, L significa "logístico", un término por el cual Gentzen se refiere al cálculo axiomático de la lógica de Frege, Russell, y Hilbert y Bernays. En tales cálculos, cada línea en una derivación es correcta en sí misma, es decir, una verdad lógica, de ahí el término. Las letras K y J provienen de las palabras alemanas klassisch e intuitionistisch.(Este último debería ser mayúscula "I", pero el alemán antiguo usa mayúscula "J" para mayúscula "I").

Gentzen llamó al análogo de la normalización por el nombre poco imaginativo de Hauptsatz, "teorema principal". La terminología estándar de hoy es el "teorema de eliminación de corte". Todas las reglas lógicas de SC tienen la propiedad subformula en un sentido muy inmediato: cada fórmula en una premisa es una fórmula o subformula en la conclusión. La regla para combinar derivaciones, análoga a la explicada anteriormente para el caso de las conversiones de desvío en ND, se llama "corte". En ella, una fórmula A aparece como un caso en una primera premisa y como una suposición en una segunda premisa. En conclusión, esta fórmula ha desaparecido y los supuestos de las dos premisas se han reunido:

Γ AA, Δ C Cortar
Γ, Δ C

Por lo tanto, cortar es la única regla que hace que una fórmula "desaparezca" en una derivación. Gentzen demostró que las instancias de la regla de corte se pueden eliminar de las derivaciones permutando hacia arriba hasta que alcanzan los puntos en los que comienza la derivación. En ND, los puntos de partida son suposiciones, en SC son "secuenciantes iniciales" de la forma A → A en la cual la fórmula de suposición A es al mismo tiempo la conclusión. Un corte con una secuencia como una premisa tiene la otra premisa igual a la conclusión y, por lo tanto, puede eliminarse.

Después de la prueba de eliminación del corte, Gentzen no tuvo uso para la prueba de normalización para la deducción intuitiva natural. Dio la primera versión manuscrita de su tesis, con la prueba detallada de normalización (equivalente a unas 13 páginas impresas) a Bernays, pero esta última parece no haberse dado cuenta de lo que tenía en sus manos. La prueba, entre los documentos de Bernays en Zurich, fue descubierta por el autor actual en febrero de 2005 y ahora está disponible en una traducción al inglés (Gentzen 1933 [2008]).

5. La consistencia de la aritmética y el análisis

Después de su trabajo de tesis sobre ND y SC para lógica pura, Gentzen continuó su plan de probar la consistencia de la aritmética. El resultado estaba listo para diciembre de 1934. Lo que fue esta primera prueba, no se conoce en detalle. Sin embargo, una carta a Bernays de 1938 indica que la prueba que Gentzen escribió para el verano de 1935 no era original, sino una segunda prueba (ver Menzler-Trott 2001, 79). Esta segunda prueba fue criticada por Bernays y Gödel, quienes la discutieron durante su viaje al Atlántico a Princeton en septiembre de 1935. La idea de Gentzen en la prueba fue la siguiente: primero, tome el fragmento de cuantificación universal de la deducción natural como la lógica utilizada en La formalización de la aritmética. Luego, escriba cada instancia de la regla de modo que las premisas y la conclusión tengan los supuestos abiertos enumerados a la izquierdacon una flecha que separa la conclusión, entonces, como secuelas. Esta variante de ND ahora se llama ND en estilo SC. Considere una secuencia Γ C. Si su conclusión es una fórmula atómica, es una ecuación entre números. En el peor de los casos, es falso, así que considere la lista de supuestos. Si un supuesto es una conjunción, reemplácelo por un conjunto de su elección, si es una cuantificación universal, por una instancia. Si es una negación ¬ A, reemplace la conclusión por A. Si en cualquier etapa de este "proceso de reducción" la conclusión de un secuenciante es una fórmula compuesta, debe considerar cualquier conjunto o cualquier instancia de cuantificación universal como una posible conclusión. En caso de negación ¬ A como conclusión, mueva A a la parte del supuesto y reemplace la conclusión por 0 = 1. Gentzen muestra que al proceder de esta manera bajo el supuesto de que el secuenciante en cuestión es derivable, se encuentra una ecuación verdadera como conclusión, o una ecuación falsa como suposición. Así,no hay secuencias derivables con todos los supuestos verdaderos y la conclusión falsa.

Para Gödel y Bernays no estaba claro qué suponía la prueba; pensaron que asumía lo que se conoce en matemática intuicionista como el teorema del abanico, pero esto era falso. La terminación del procedimiento de reducción de Gentzen puede demostrarse en su lugar por inducción en árboles bien fundados ("inducción de barra"), un principio que fue utilizado por Gentzen por razones intuitivas. De todos modos, el resultado de la crítica fue que Gentzen cambió sin más preámbulos la prueba en una tercera prueba que usa el ahora famoso principio de inducción transfinita hasta el primer número épsilon. Esta inducción se presentó a través de una codificación que utilizaba números decimales. Sin embargo, el resultado concreto de los cambios para el artículo de Gentzen publicado en 1936 no fue bueno: el cálculo lógico se cambió a mitad de camino en un artículo de setenta y pico páginas que se hizo muy difícil de leer. Por lo tanto, Gentzen dio otra prueba más, según el recuento actual, de la consistencia de la aritmética en 1938 (en los archivos de Bernays del ETH Zurich), esta vez basada en el cálculo secuencial clásico LK de 1933. Como se mencionó, la correspondencia con Bernays indica que Por lo tanto, volvió al método de prueba que había llevado al éxito en 1934. El uso de la inducción transfinita se hace claramente visible en el artículo de 1938 a través de una notación ordinal. Tales principios de inducción sobre la "segunda clase de números" de Cantor se discuten en detalle en la conferencia de Hilbert de 1925 "Über das Unendliche" ("Sobre el infinito", publicado en 1926), un documento al que se refería Gentzen.esta vez basado en el cálculo clásico clásico LK de 1933. Como se mencionó, la correspondencia con Bernays indica que él regresó al método de prueba que había llevado al éxito en 1934. El uso de la inducción transfinita se hace claramente visible en el artículo de 1938 a través de un notación ordinal Tales principios de inducción sobre la "segunda clase de números" de Cantor se discuten en detalle en la conferencia de Hilbert de 1925 "Über das Unendliche" ("Sobre el infinito", publicado en 1926), un documento al que se refería Gentzen.esta vez basado en el cálculo clásico clásico LK de 1933. Como se mencionó, la correspondencia con Bernays indica que él regresó al método de prueba que había llevado al éxito en 1934. El uso de la inducción transfinita se hace claramente visible en el artículo de 1938 a través de un notación ordinal Tales principios de inducción sobre la "segunda clase de números" de Cantor se discuten en detalle en la conferencia de Hilbert de 1925 "Über das Unendliche" ("Sobre el infinito", publicado en 1926), un documento al que se refería Gentzen.s Conferencia de 1925 "Über das Unendliche" ("Sobre el infinito", publicado en 1926), un documento al que se refería Gentzen.s Conferencia de 1925 "Über das Unendliche" ("Sobre el infinito", publicado en 1926), un documento al que se refería Gentzen.

Uno hubiera pensado que era eso, pero Gentzen tenía razones para presentar incluso una cuarta prueba de la consistencia de la aritmética, en su último artículo publicado en 1943 pero escrito antes de la guerra en 1939. Extendió la aritmética de Peano a través de ordinales transfinitos e hizo el principio de inducción transfinita parte de este cálculo extendido. Luego demostró directamente que la inducción transfinita hasta el primer número épsilon ε 0 es expresable pero no demostrable en el sistema. El teorema de incompletitud de Gödel se demuestra de una manera completamente diferente. La idea de la prueba es, en términos breves, la siguiente: primero se establece lo que significa derivar la inducción transfinita a un número ordinal específico en el sistema. En segundo lugar, los números ordinales debajo de ε 0están asociados a derivaciones. Estos se llaman "valores". Luego se muestra que si la inducción transfinita a un número ordinal es derivable, este número ordinal no puede ser mayor que el valor de la derivación. Por lo tanto, la inducción transfinita a ε 0 no es derivable.

Dado que el principio de inducción puede expresarse pero no demostrarse en la aritmética ordinaria, se encuentra una fórmula no demostrable en la aritmética de Peano. Una consecuencia fácil de la versión de Gentzen del teorema de incompletitud es la consistencia de la aritmética de Peano, porque cualquier cosa sería demostrable en un sistema inconsistente. Contrariamente a la fórmula no artificial "artificial" de Gödel que se obtuvo a través de la codificación del predicado de demostrabilidad aritmetizada, el principio de inducción transfinito de Gentzen es un principio de las matemáticas "ordinarias".

La última prueba de Gentzen determinó el "ordinal teórico de la prueba" de la aritmética de Peano, es decir, la que se necesita para demostrar la coherencia, con la propiedad de que nada menos sería suficiente. El trabajo marcó el comienzo de la teoría de la prueba ordinal. Fue sin duda el logro fundamental más notable en aritmética después de los teoremas de incompletitud de Gödel, pero aún es en gran parte desconocido: uno puede encontrar muchos libros sobre los teoremas de Gödel que ni siquiera mencionan a Gentzen.

Gödel, al parecer, no pensó en dar una prueba de coherencia de la aritmética mediante el uso de principios no finitarios pero aún constructivos. A finales de los años treinta, al menos a partir de 1938, desarrolló como respuesta a la prueba de Gentzen su propia interpretación especial de la lógica intuitiva y la aritmética, lo que se conoció como la interpretación dialéctica. Utiliza funciones computables para interpretar las pruebas de la aritmética intuicionista. Gödel publicó la interpretación solo en 1958, a pesar de que la había presentado en conferencias en 1941. No se sabe si discutió el asunto cuando se encontró con Gentzen en diciembre de 1939.

A pedido de Bernays, Ackermann reprodujo la prueba de Gentzen en términos del cálculo épsilon de Hilbert en 1940. El artículo de Ackermann fue el punto de partida de la interpretación "sin contraejemplo" de Kreisel en 1951. Fue una sorpresa cuando la publicación de los documentos recopilados de Gödel sacó a la luz su "Conferencia de Zilsel" en Viena en 1938: describe esta interpretación como una reformulación de la prueba de Gentzen de 1935. (El tema se discute en gran detalle en Tait (2005), quien también había trabajado en la interpretación sin contraejemplo y su extensión al análisis en la década de 1960).

La siguiente tarea obvia en la teoría de la prueba, después de la prueba de la consistencia de la aritmética, era probar la consistencia del análisis, es decir, de la teoría de los números reales. Gentzen trabajó un poco en esta dirección, pero luego fue asignado al servicio militar en el otoño de 1939. (Observó e informó el tipo, número y dirección de los aviones que sobrevolaron la ciudad de Brunswick, hasta que fue golpeado por un nervioso colapso a principios de 1942.) A partir de 1943 reanudó el trabajo de análisis, pero las dificultades intrínsecas al tema fueron grandes, al igual que las dificultades prácticas de la vida causadas por la guerra. El análisis debía formularse como un sistema de aritmética de segundo orden, lo que significa que la cuantificación se extiende sobre predicados teóricos de números o, de manera equivalente, sobre conjuntos de números naturales. La teoría de números de segundo orden se usa en el último artículo de Gentzen,publicado en 1943, en el que se muestra brevemente que el principio de inducción transfinita hasta ε0 es derivable en la teoría de números de segundo orden.

Ha pasado más de medio siglo sin una prueba constructiva de la consistencia de la aritmética completa de segundo orden a la vista. Los primeros pioneros en este campo incluyeron a Kurt Schütte y Gaisi Takeuti. El primero creó en 1951 un cálculo infinito secuencial para presentar pruebas de consistencia de manera perspicaz, el segundo utilizó un cálculo más tradicional al estilo Gentzen (ver Takeuti 1987).

En la investigación actual en la teoría de prueba de la aritmética de segundo orden, uno estudia lo que se conoce como subsistemas de aritmética de segundo orden. Los resultados más sólidos a día de hoy son, en un resumen muy breve, los siguientes: dejemos que X se extienda sobre predicados teóricos numéricos. Una fórmula como X (x) establece que x tiene la propiedad expresada por X. Ahora podemos usar la lógica de primer y segundo orden para formar fórmulas compuestas como ∀ X (X x ∨ ¬ X x). La colección de números naturales para los que se mantiene dicha fórmula con un cuantificador universal de segundo orden se denomina conjunto Π11 (en este caso, el conjunto de los números naturales). Más generalmente, un axioma de comprensión tiene la forma ∃ X ∀ x (X x ↔ B (x)). Si la fórmula B no tiene cuantificadores de segundo orden, el axioma proporciona lo que se llama comprensión aritmética o ACA. Si B puede tener la forma ∀ Y ∃ ZC (x) sin otros cuantificadores de segundo orden, se obtiene el caso especial de comprensión Π12. Toshiyasu Arai y Michael Rathjen proporcionaron pruebas de consistencia para un subsistema de aritmética de segundo orden con una comprensión de Π12 a mediados de la década de 1990. (Ver Rathjen 1995 para estos desarrollos).

6. Desarrollos posteriores en la deducción natural

En el momento en que Gentzen desarrolló su sistema de deducción natural, Stanislaw Jaskowski también estaba desarrollando un sistema lógico para razonar con suposiciones. Las fórmulas en derivaciones están dispuestas en una sucesión lineal, pero el artículo de Jaskowski de 1934 permaneció fragmentario y sin resultados sustanciales, como una propiedad de subformula. La variante lineal de la deducción natural se sigue en muchas exposiciones pedagógicas de lógica elemental (a veces llamadas "sistemas Fitch"). Gentzen encontró el trabajo de Jaskowski en junio de 1936, cuando ambos estaban en Münster, y consideró su disposición lineal de fórmulas una mejora, una "liberación de la camisa de fuerza de la forma del árbol", en una que refleja "la linealidad del pensamiento" (el primero de notas inéditas, esta última de la tesis de Gentzen).

El sistema de deducción natural permaneció latente durante unos treinta años, hasta la tesis de Dag Prawitz de 1965, Deducción natural: un estudio teórico a prueba. El orden en el que Prawitz presentó el teorema de normalización fue diferente al del manuscrito de tesis inicial de Gentzen. Prawitz dio primero un teorema de normalización y una propiedad de subformula para un sistema de deducción natural para la lógica clásica. Este sistema no contiene disyunción o existencia. En una segunda etapa, consideró la deducción natural intuicionista para el lenguaje completo de la lógica predicativa y redujo su normalización a la eliminación de las convertibilidades de desvío como en el fragmento de la lógica clásica. Cuando la prueba de normalización de Gentzen salió a la luz en 2005, Prawitz dijo, en conversación con el autor actual, que está claro que Gentzen sabía el resultado,porque los comentarios en la tesis impresa son muy sugerentes.

A fines de la década de 1960, la fuerte normalización se convirtió en un problema: Prawitz, utilizando el trabajo previo de William Tait y Jean-Yves Girard, demostró en 1971 que las no normalidades en una derivación se pueden convertir en cualquier orden, con un proceso de normalización final y un proceso único. derivación normal como resultado. Gentzen parece no haberse dado cuenta de esto último, pero parece haber pensado más bien lo contrario, por el fracaso de esta propiedad para la eliminación de cortes en el cálculo posterior.

Aproximadamente al mismo tiempo que se estudiaba una fuerte normalización, surgió la correspondencia Curry-Howard. Curry había observado en su trabajo sobre lógica combinatoria a fines de la década de 1950 la analogía entre la eliminación de implicaciones en la deducción natural y la aplicación funcional (Curry y Feys, 1958). La idea era tan antigua como la lógica intuicionista: mediante la "explicación BHK" de los conectivos y cuantificadores (para Brouwer-Heyting-Kolmogorov), las formas de las proposiciones en la lógica intuicionista expresan prescripciones sobre cómo probar esas proposiciones: una conjunción A y B se prueba probando A y B por separado, una disyunción A ∨ B al probar uno de A y B, y una implicación A ⊃ B al mostrar cómo convertir cualquier prueba de A en alguna prueba de B, y así sucesivamente. Estas explicaciones se acercan mucho a las reglas de introducción de la deducción natural,pero no se sabe cuál fue su efecto en el pensamiento de Gentzen.

La correspondencia de Curry-Howard, de un artículo de William Howard de 1969, pero publicada solo en 1980, se basa en el principio de "fórmulas como tipos", o en otra jerga, en el principio de "proposiciones como conjuntos". Se considera que una proposición es su conjunto de pruebas. La verdad de una proposición corresponde a la no-vacuidad del conjunto. Las pruebas de A ⊃ B ahora son funciones de (pruebas de) A a (pruebas de) B y A ⊃ B en sí el conjunto de tales funciones. Por lo tanto, si f: A ⊃ B y a: A, entonces la aplicación funcional da f (a): B. El reverso, correspondiente a la introducción de una implicación, es capturado por el principio de abstracción funcional del cálculo λ de Alonzo Church.

La correspondencia de Curry-Howard ha hecho que la deducción natural intuicionista forme parte del plan de estudios de informática: proporciona una semántica computacional para la lógica intuicionista en la que los cálculos y las ejecuciones de programas en general se efectúan mediante la normalización. Una prueba de una implicación A ⊃ B, por ejemplo, es un programa que convierte datos de tipo A en una salida de tipo B. La construcción de un objeto (prueba, función, programa) f del tipo A ⊃ B termina con una abstracción. Cuando un objeto a de tipo A se introduce en f como argumento, la expresión resultante no es normal, pero tiene una forma que corresponde a una introducción seguida de una eliminación. La normalización ahora es lo mismo que la ejecución del programa f. El uso de la lógica intuicionista no está vinculado a ninguna filosofía intuicionista de las matemáticas,pero es solo una garantía sistemática para la terminación de la ejecución de programas de computadora.

7. Cálculo secuencial: desarrollos / aplicaciones posteriores

La tesis doctoral de Gentzen marcó el nacimiento de la teoría de la prueba estructural, en contraste con la antigua teoría de la prueba axiomática de Hilbert. Oiva Ketonen dio un notable paso adelante en el desarrollo de sistemas de cálculo posterior en su tesis doctoral de 1944. Ketonen, un estudiante de matemáticas y filosofía en Helsinki, fue a Gotinga en 1938 para estudiar teoría de la prueba con Gentzen, siendo el más cercano a un estudiante que este último tuvo. La conexión parece haber sido establecida por el profesor de filosofía de Ketonen, Eino Kaila, quien había conocido a Gentzen en 1936 en Münster. Ketonen recordó más tarde que Gentzen era "un joven comprensivo de pocas palabras" que le dio una introducción a los sistemas y resultados teóricos de prueba. KetonenEl descubrimiento más conocido es un cálculo secuencial para la lógica proposicional clásica cuyas reglas lógicas son todas invertibles, lo que significa que siempre que un secuenciante sea de una forma que coincida con la conclusión de una regla lógica, las premisas correspondientes, definidas únicamente a partir del secuenciante dado y la regla, también son derivables. Lo contrario es inmediato (solo aplica la regla). Las reglas L y L⊃, por ejemplo, se modifican en

A, B, Γ Δ L &
A y B, Γ Δ
Γ Δ, AB, Γ Δ L⊃
A ⊃ B, Γ Δ

Solo hay una regla izquierda para la conjunción (y dualmente solo una regla correcta para la disyunción). La regla de implicación izquierda tiene lo que se llama "contextos compartidos": los supuestos y los casos en la conclusión, a excepción de la fórmula con el conectivo, se repiten idénticamente en ambas premisas. La idea de Ketonen era definir un sistema de búsqueda de pruebas: uno parte de un secuenciante determinado que se derivará, elige una fórmula y escribe las premisas de una regla que puede concluir el secuenciante dado. Por invertibilidad, la cuestión de derivabilidad se reemplaza por una o dos preguntas equivalentes de derivabilidad en secuencias más simples. Las nuevas reglas son necesarias para garantizar premisas definidas de forma única en dicha descomposición "primero en la raíz".

La prueba de invertibilidad de Ketonen de las reglas lógicas de su cálculo posterior utilizó la regla estructural del corte. Más tarde, Kurt Schütte (1950) y Haskell Curry (1963) dieron pruebas directas de la invertibilidad, este último con el resultado explícito de que las inversiones preservan la altura: si una secuencia dada es derivable en la mayoría de los n pasos, las premisas en una regla que puede concluir que el secuenciante también tiene una derivación en, como máximo, n pasos.

Se desconoce qué parte del trabajo de Ketonen proviene de sugerencias por parte de Gentzen, porque no se ha encontrado correspondencia. Ketonen escribe en el prefacio de su tesis que Dr. G. Gentzen de Gotinga me dirigió hacia el área problemática de este trabajo”. La tesis fue el único trabajo original de Ketonen en lógica, salvado del olvido por una larga revisión que Bernays escribió sobre él para The Journal of Symbolic Logic en 1945.

Una persona que conocía el cálculo de Ketonen a fines de la década de 1940 era Evert Beth. Cuando Beth más tarde, en 1955, presentó su conocido cálculo del cuadro, parece haber olvidado el origen del cálculo del cuadro como una reformulación de la de Ketonen, pero en cambio se refiere a la influyente Introducción a la metamatemática de Kleene de 1952. Kleene había tomado subió el cálculo de Ketonen de la revisión de Bernays y también trató el cálculo secuencial intuicionista en el que la invertibilidad es más restringida que en el cálculo clásico. Con el libro de Kleene, los cálculos posteriores de Gentzen se hicieron generalmente conocidos y accesibles.

El trabajo de Kleene de principios de la década de 1950 también fue pionero en un desarrollo notable en el cálculo posterior, a saber, los cálculos clásicos e intuicionistas "libres de contracciones" que hoy denotan G3c y G3i. Estos cálculos tienen la propiedad de que no se necesitan ninguna de las "reglas estructurales" originales de Gentzen. La regla de "debilitamiento" permite la adición de casos y supuestos superfluos, y la regla de "contracción" la eliminación de una copia de una fórmula si dos estaban presentes en una lista, como en

Debilitamiento Contracción
Γ Δ Wk
A, Γ Δ
A, A, Γ Δ Ctr
A, Γ Δ

Reglas análogas permiten el debilitamiento y la contracción en las partes correctas y sucesivas de las secuencias. El debilitamiento se convierte en una regla eliminable al permitir que las secuencias iniciales tengan la forma A, Γ Δ, A en lugar de A → A de Gentzen. La contracción también se puede eliminar mediante una formulación adecuada de las reglas. Lo importante es que en la búsqueda de pruebas de raíz primero, no es necesario aplicar reglas que produzcan una duplicación de una fórmula en una premisa. Sin este resultado, la no terminación de la búsqueda de pruebas no seguiría.

El cálculo clásico tiene la propiedad, mencionada anteriormente, de la invertibilidad que preserva la altura de sus reglas lógicas. Albert Dragalin refinó a fines de la década de 1970 el cálculo en uno en el que las reglas estructurales son además "conservadoras de altura admisibles", lo que significa que cada vez que la premisa de dicha regla es derivable, la conclusión es derivable sin la regla y, como máximo, con la misma tamaño (número máximo de instancias de regla en una rama de derivación) de derivación. Esta propiedad tiene profundos efectos en la eliminación del corte: al permutar el corte, Gentzen tuvo que restaurar los contextos originales (los Γ y los Δ) a través de debilitamientos y contracciones. Con la admisibilidad de estas reglas para preservar la altura, el tamaño de una derivación no aumenta cuando se aplican las reglas. Dragalin también dio un cálculo intuitivo multisuccedent con el mismo tipo de admisibilidad de las reglas estructurales. Troelstra, finalmente, dio en el libro de texto Basic Proof Theory (2000, primera edición, 1996) un cálculo intuicionista único sucesivo con la admisibilidad de debilitamiento y contracción que preserva la altura. Los cálculos secuenciales sin contracción son herramientas poderosas para el análisis de derivaciones formales. Muchos resultados de investigación difíciles en lógica se convierten en ejercicios a través del control sobre la estructura de las pruebas que permiten los cálculos de G3. Los cálculos secuenciales sin contracción son herramientas poderosas para el análisis de derivaciones formales. Muchos resultados de investigación difíciles en lógica se convierten en ejercicios a través del control sobre la estructura de las pruebas que permiten los cálculos de G3. Los cálculos secuenciales sin contracción son herramientas poderosas para el análisis de derivaciones formales. Muchos resultados de investigación difíciles en lógica se convierten en ejercicios a través del control sobre la estructura de las pruebas que permiten los cálculos de G3.

La primera aplicación del cálculo consecuente en matemáticas fue en la teoría de la prueba de la aritmética, en la tesis de Gentzen y de manera decisiva en la prueba de 1938 de la consistencia de la aritmética. Troelstra menciona el trabajo de Ketonen como

un análisis temprano de pruebas sin cortes en cálculos Gentzen con axiomas; pero considera la forma de derivaciones libres de corte en el cálculo puro donde los axiomas están presentes en el antecedente de las secuencias derivadas. (Troelstra y Schwichtenberg 2000: 142)

Los axiomas que Ketonen considera son los de la geometría proyectiva y afinada, el primero tomado del artículo de Skolem de 1920 discutido en la primera sección anterior. Ketonen quería formular las reglas formales de prueba de Skolem dentro del cálculo posterior. Sin embargo, el trabajo de Ketonen se conocía principalmente solo a través de su revisión por parte de Bernays y solo la parte lógica sobre el cálculo posterior se explicó en detalle allí.

Una segunda forma de aplicar el cálculo secuencial es dejar que los secuenciantes que comienzan ramas de derivación tengan, además de los secuenciadores iniciales, también la forma A, en la cual A es un axioma, o una instancia de un axioma universal. Ahora, por el "Hauptsatz extendido" de Gentzen, los cortes en derivaciones pueden permutarse hasta que una de sus premisas sea un axioma, pero estos cortes en los axiomas permanecen. Otro método más nuevo es convertir los axiomas en reglas adicionales que se agregan a las reglas lógicas del cálculo secuencial, manteniendo la eliminación del corte completo (como se explica en Negri y von Plato 2001, capítulo 6, y en Troelstra y Schwichtenberg's 2000, capítulo 4.7).

8. Los objetivos de la teoría de la prueba

¿En qué medida la teoría de la prueba ha logrado sus objetivos originales? Para Hilbert, los objetivos eran una aclaración completa de los problemas fundamentales a través de pruebas finitas de consistencia, etc., objetivos en los que la teoría de la prueba fallaba. Hilbert en su programa no estaba interesado en el estudio de las pruebas matemáticas en sí mismas, sino solo en aclarar los problemas fundamentales centrales (y luego olvidarse de ellos). Una nota recientemente encontrada por Hilbert ofrece una imagen diferente: la nota afirma que Hilbert quería agregar como un problema número 24 y último en su famosa lista de París de problemas matemáticos abiertos de 1900 el desarrollo de "una teoría de métodos de prueba en matemáticas". Esto fue antes de que surgiera su programa metamatemático para el desarrollo de una teoría de prueba.

Para Gentzen, los objetivos eran, junto con los de Hilbert, comprender la estructura de las pruebas matemáticas. Este programa fue un éxito total en lo que respecta a la lógica pura y la aritmética. Los métodos de cálculo posterior, especialmente, permiten el análisis de pruebas con resultados profundos. El gran objetivo de la teoría de la prueba, una prueba de la coherencia del análisis como en el segundo problema de Hilbert en París, no se ha llevado a cabo, pero tampoco está excluido.

Para cualquier matemático es necesaria cierta comprensión de la noción de prueba, al menos para la comunicabilidad de los resultados matemáticos: la publicación se basa en el entendimiento de que las pruebas pueden hacerse tan explícitas como para comprobar su corrección de forma rutinaria. Sin embargo, la teoría de la prueba hasta ahora no se ha convertido en una herramienta práctica para el matemático que trabaja; Las aplicaciones en matemáticas han sido casos bastante aislados. El trabajo reciente sobre la formalización de pruebas matemáticas con sistemas computarizados, llamados editores de pruebas, puede cambiar gradualmente esta imagen.

La teoría de la prueba ha creado nuevos objetivos fuera de las matemáticas tradicionales, especialmente en relación con la informática. Temas como la verificación de la corrección de los programas de computadora son una consecuencia de la teoría de la prueba. La deducción natural ha llevado a la correspondencia de Curry-Howard y a conexiones con la programación funcional, y el cálculo secuencial se usa a menudo en sistemas de búsqueda automática de pruebas, como en la programación lógica.

Bibliografía

Textos sobre teoría de la prueba

  • Buss, Sam (ed.), 1998, Handbook of Proof Theory, Amsterdam: Elsevier.
  • Negri, S. y J. von Plato, 2001, Teoría de la prueba estructural, Cambridge: Cambridge University Press.
  • von Plato, J., 2013, Elementos del razonamiento lógico, Cambridge: Cambridge University Press.
  • Takeuti, G., 1987, Proof Theory, Amsterdam: North-Holland, 2a edición.
  • Troelstra, A. y H. Schwichtenberg, 2000, Basic Proof Theory, Cambridge: Cambridge University Press, 2ª edición.

Obras originales y sus reimpresiones

  • Ackermann, W. 1940, "Zur Widerspruchsfreiheit der Zahlentheorie", Mathematische Annalen, 117: 162–194.
  • Beth, E., 1955, implicación semántica y derivabilidad formal (Mededelingen der Koninklijke Nederlandse Akademie van Wetenschappen. Afd. Letterkunde. Nieuwe apesta, deel 18, no. 13), Amsterdam: Holanda del Norte.
  • Church, A., 1936, "Una nota sobre el problema de Entscheidungs", Journal of Symbolic Logic, 1: 40–41.
  • Curry, H. y Feys, R., 1958. Lógica combinatoria. (Studies in Logic and the Foundations of Mathematics, Vol. I), 1ª edición, Amsterdam: Holanda del Norte.
  • Curry, H., 1963, Fundamentos de la lógica matemática, Nueva York: McGraw-Hill; reimpreso Nueva York: Dover, 1977.
  • Dragalin, A., 1988, Intuitionism matemático: Introducción a la teoría de la prueba, Providence, RI: American Mathematical Society.
  • Gentzen, G., 1934–1935, Untersuchungen über das logische Schliessen (Investigaciones sobre inferencia lógica), Ph. D. tesis, Universität Göttingen. Publicado en Gentzen 1969: 68–131.
  • Gentzen, G., 1938, "Neue Fassung des Widerspruchsfreiheitsbeweises für die reine Zahlentheorie", Forschungen zur Logik und zur Grundlegung der exakten Wissenschaften, Neue Folge 4, S. Hrizel, 19–44. Traducido en Gentzen 1969: 252–286.
  • Gentzen, G., 1943, "Beweisbarkeit und Unbeweisbarkeit von Anfangsfällen der transfiniten Induktion in der reinen Zahlentheorie", Mathematische Annalen, 119: 252–286. Traducido en Gentzen 1969: 287–308.
  • Gentzen, G., 1969, The Collected Papers of Gerhard Gentzen, ed. M. Szabo, Amsterdam: Holanda del Norte.
  • Gentzen, G., 2008, "La normalización de derivaciones", The Bulletin of Symbolic Logic, 14 (1): 245–257.
  • Gödel, K., 1930, "Die Vollständigkeit der Axiome des logischen Funktionenkalküls", Monatshefte für Mathematik und Physik, 37: 349–360.
  • Gödel, K., 1958, “Über eine bisher noch nicht benützte Erweiterung des finiten Standpunktes”, Dialectica, 12: 280–287.
  • Gödel K., 1986–2003, Collected Papers (Volúmenes I – V), S. Feferman et al. (eds.), Oxford: Oxford University Press.
  • van Heijenoort, J., 1967, De Frege a Gödel, Cambridge, MA: Harvard University Press.
  • Hilbert, D., 1899, Grundlagen der Geometrie, Leipzig: BG Teubner.
  • Hilbert, D., 1926, “Über das Unendliche” (“En el infinito”), Mathematische Annalen, 95: 161–190. [Conferencia dada en Münster, 4 de junio de 1925.]
  • Hilbert, D. y Ackermann, W., 1928, Grundzüge der teoríatischen Logik, Berlín: Springer.
  • Hilbert, D., 1931, "Die Grundlegung der elementaren Zahlenlehre", Mathematische Annalen, 104: 484-494.
  • Howard, W., 1980 [1969], "La noción de construcción de fórmulas como tipos", en J. Seldin y J. Hindley (eds.), To HB Curry: Ensayos sobre lógica combinatoria, cálculo de Lambda y formalismo, Londres, Nueva York: Academic Press, págs. 480–490.
  • Jaskowski, S., 1934, "Sobre las reglas de suposición en la lógica formal", en S. McCall (ed.), Polish Logic 1920–1939, Oxford: Clarendon Press, 1967, pp. 232–258.
  • Ketonen, O., 1944, Untersuchungen zum Prädikatenkalkül, Annales Academiae scientiarum fennicae (Ser. AI 23), Helsinki.
  • Kleene, S., 1952, Introducción a la metamatemática, Amsterdam: Holanda del Norte.
  • Kreisel, G., 1951, "Sobre la interpretación de las pruebas no finitistas: Parte I", The Journal of Symbolic Logic, 16 (4): 241–267.
  • Löwenheim, L., 1915, “Über Möglichkeiten im Relativkalkül”, Mathematische Annalen, 76 (4): 447–470.
  • Menzler-Trott, E., 2001, Problema Gentzens, Berlín: Birkhäuser Verlag.
  • Menzler-Trott, E., 2007, Logic's Lost Genius: The Life and Work of Gerhard Gentzen, Providence, RI: American Mathematical Society.
  • Prawitz, D., 1965, Deducción natural: un estudio teórico a prueba, Estocolmo: Almqvist & Wiksell; reimprimir Nueva York: Dover (con un nuevo prefacio), 2006.
  • –––, 1971, “Ideas y resultados en la teoría de la prueba”, en J. Fenstad (ed.), Proceedings of the Second Scandinavian Logic Symposium, Amsterdam: North-Holland, pp. 235–308.
  • Rathjen, M., 1995, "Avances recientes en el análisis ordinal; Π 1 2 -CA y sistemas relacionados,”The Bulletin of Symbolic Logic, 1 (4): 468–485.
  • Schütte, K., 1950, "Schlussweisen-Kalküle der Prädikatenlogik", Mathematische Annalen, 122: 47–65.
  • –––, 1951, “Beweistheoretische Erfassung der unendlichen Induktion in der Zahlentheorie”, Mathematische Annalen, 122: 369–389.
  • Skolem, T., 1920, "Logisch-kombinatorische Untersuchungen über die Erfüllbarkeit oder Beweisbarkeit Mathischer Sätze, nebst einem Theoreme über dichte Mengen", traducido y reimpreso en Selected Works in Logic, JE Fenstad (ed.), Oslo, Universitets, Oslo, 1970, Universitets pp. 103-136:
  • Whitehead, AN y B. Russell, 1910–1913, Principia Mathematica, Cambridge: Cambridge University Press.

Literatura secundaria

  • Bernays, P., 1945, “Revisión: Oiva Ketonen, Untersuchungen zum Pradikatenkalkul”, The Journal of Symbolic Logic, 10 (4): 127–130.
  • –––, 1965, “Betrachtungen zum Sequenzen-kalkul”, en Contribuciones a la lógica y la metodología en honor de JM Bochenski, Amsterdam: Holanda del Norte, págs. 1-44.
  • –––, 1979, “Sobre la prueba de consistencia Gentzen original para la teoría de números”, en J. Myhill et al. (eds.), Intuitionism and Proof Theory, Amsterdam: North-Holland, pp. 409–417.
  • Feferman, S., 2000, "Aspectos destacados en la teoría de la prueba", en V. Hendricks et al. (eds.) 2000, 11–31.
  • Hempel, C., 2000, "Una autobiografía intelectual". En Science, Explanation, and Rationality, ed. J. Fetzer, págs. 3-35.
  • Hendricks, V. y col. (eds.), 2000, Teoría de la prueba: Historia y significado filosófico, Dordrecht: Kluwer.
  • Mancosu, P., 1999, "Entre Berlín y Viena: la recepción inmediata de los teoremas de incompletitud de Gödel", Historia y filosofía de la lógica, 20: 33-45.
  • von Plato, J., 2007, "A la sombra del teorema de Löwenheim-Skolem: primeros análisis combinatorios de pruebas matemáticas", The Bulletin of Symbolic Logic, 13 (2): 189–225.
  • –––, 2007, “Del programa de Hilbert al programa de Gentzen”, en el Apéndice, Menzler-Trott 2007.
  • –––, 2009, “Gentzen's logic”, en Handbook of the History and Philosophy of Logic (Volumen 5), Amsterdam: Elsevier.
  • –––, 2012, “Sistemas de prueba de Gentzen: subproductos en un programa de genio”, The Bulletin of Symbolic Logic, 18 (3): 313–367.
  • Smorynski, C., 2007, "Programa de Hilbert", en el Apéndice, Menzler-Trott 2007.
  • Tait, W., 2005, "La reformulación de Gödel de la primera prueba de coherencia de Gentzen para la aritmética: la interpretación sin contraejemplo", The Bulletin of Symbolic Logic, 11 (2): 225–238.
  • Troelstra, A. y Schwichtenberg, H., 2000, Basic Proof Theory, Cambridge: Cambridge University Press, 2ª edición.

Herramientas académicas

icono de hombre sep
icono de hombre sep
Cómo citar esta entrada.
icono de hombre sep
icono de hombre sep
Obtenga una vista previa de la versión PDF de esta entrada en Friends of the SEP Society.
icono inpho
icono inpho
Busque este tema de entrada en el Proyecto de ontología de filosofía de Internet (InPhO).
icono de papeles de phil
icono de papeles de phil
Bibliografía mejorada para esta entrada en PhilPapers, con enlaces a su base de datos.

Otros recursos de internet

[Póngase en contacto con el autor con sugerencias.]

Recomendado: