Prueba de consistencia de Gentzen

Ir a: navegación, búsqueda de

Prueba de consistencia de Gentzen es el resultado de Teoría de la prueba en lógica matemática, publicado por Gerhard Gentzen en 1936. Demuestra que la Axiomas de Peano de la aritmética de primer orden no contienen una contradicción (es decir, son"consistente"), como un cierto otro sistema utilizado en la prueba no contiene ninguna contradicciones tampoco. Este otro sistema, llamado hoy"aritmética primitiva recursiva con el principio adicional de cuantificador-libre inducción de transfinite hasta el ordinal ε0", no es ni más débil ni más fuerte que el sistema de axiomas de Peano. Gentzen argumentó que evita los cuestionables modos de inferencia contenida en la aritmética de Peano y que su consistencia es menos controvertida.

Contenido

  • 1 Teorema de Gentzen
  • 2 Relación con el programa de Hilbert y el teorema de Gödel
  • 3 Otras pruebas de consistencia de la aritmética
  • 4 Trabajo iniciado por prueba de Gentzen
  • 5 Notas
  • 6 Referencias

Teorema de Gentzen

Teorema de Gentzen se refiere a la aritmética de primer orden: la teoría de la números naturales, incluyendo la adición y multiplicación, axiomized por los axiomas de Peano. Esta es una teoría de "primer orden": el Cuantificadores extender sobre números naturales, pero no sobre sistemas o funciones de números naturales. La teoría es lo suficientemente fuerte como para describir definido de forma recursiva funciones de enteros como la exponenciación, factoriales o la Secuencia de Fibonacci.

Gentzen demostró que la consistencia de los axiomas de Peano de primer orden es demostrable, sobre la teoría de la base de aritmética primitiva recursiva con el principio adicional de cuantificador-libre inducción de transfinite hasta el ordinal ε0. Aritmética primitiva recursiva es una forma muy simplificada de la aritmética que es algo controvertido. Informalmente, el principio adicional significa que existe un bien pedido en el conjunto de finito arraigada árboles. Formalmente, ε0 es la primera ordinal \alpha tal manera que \omega^\alpha = \alpha, es decir, el límite de la secuencia:

\omega,\ \omega^\omega,\ \omega^{\omega^\omega},\ \ldots

Para expresar números ordinales en el lenguaje de la aritmética, un notación ordinal es necesario, es decir, una manera de asignar los números naturales a números ordinales menos que ε0. Esto puede hacerse de varias maneras, un ejemplo proporcionado por el teorema de la forma normal de Cantor. Se requiere para cualquier fórmula cuantificador-libre A(x): si hay un ordinal x< Ε0 para que A(x) es false, entonces hay un tal menos ordinal.

Gentzen define una noción de "procedimiento de reducción" para las pruebas de aritmética de Peano. Para una prueba dada, tal procedimiento produce un árbol de pruebas, con el dado que sirve como la raíz del árbol y las otras pruebas que, en cierto sentido, "más simple" que la dada. Esta simplicidad cada vez mayor se formaliza fijando un ordinal < ε0 a cada prueba y demostrar que, como uno se mueve hacia abajo del árbol, estos ordinales consigue más pequeños con cada paso. Él entonces demuestra que si hubo una prueba de una contradicción, el procedimiento de reducción tendría como resultado una infinita secuencia descendente de números ordinales < ε0 producido por un recursiva primitiva operación en las pruebas correspondientes a un fórmula cuantificador-libre.[1]

Es posible interpretar en términos de teoría de juego (a prueba de GentzenTait 2005).

Relación con el programa de Hilbert y el teorema de Gödel

Prueba de Gentzen destaca un aspecto comúnmente perdido de Segundo teorema de incompletitud de Gödel. A veces se afirma que la consistencia de una teoría sólo puede ser probada en una teoría más fuerte. La teoría obtenida añadiendo inducción del transfinite cuantificador-libres a aritmética primitiva recursiva demuestra la consistencia de primer orden aritmética pero no es más fuerte que la aritmética de primer orden. Por ejemplo, no prueba ordinario inducción matemática para la totalidad de las fórmulas, mientras que de primer orden aritmético hace (tiene esto como un esquema de axioma). La teoría resultante no es más débil que la aritmética de primer orden, puesto que puede resultar un hecho teórico número - la consistencia de primer orden aritmético - no eso aritmética de primer orden. Las dos teorías son simplemente incomparables.

Hermann Weyl hizo el siguiente comentario en 1946 sobre la importancia del resultado de consistencia de Gentzen tras los efectos devastadores del resultado de incompletitud de Gödel de 1931 sobre plan de Hilbert para probar la consistencia de las matemáticas.[2]

Es probable que todos matemáticos en última instancia habría aceptado método de Hilbert había él podido llevar a cabo con éxito. Los primeros pasos fueron inspirador y prometedor. Pero entonces Gödel asestó un golpe tremendo (1931), de que no se ha todavía recuperado. Gödel enumerados los símbolos, fórmulas y secuencias de fórmulas en el formalismo de Hilbert de una determinada manera y así transforma la afirmación de consistencia en una proposición aritmética. Él podía demostrar que esta proposición puede ser probada ni refutada en el formalismo. Esto puede significar dos cosas: o bien el razonamiento por el cual se da una prueba de consistencia debe contener algún argumento que no tenga ninguna contraparte formal dentro del sistema, es decir, que no hemos logrado formalizar completamente el procedimiento de inducción matemática; o esperanza de una estrictamente "finitistic" prueba de la consistencia debe ser dado para arriba en conjunto. Cuando G. Gentzen finalmente tuvo éxito en probar la consistencia de la aritmética traspasado esos límites de hecho afirmando como un tipo de razonamiento que penetra en el "Segunda clase de números ordinales." de Cantor

Kleene (2009p. 479) hizo el siguiente comentario en 1952 sobre el significado del resultado de Gentzen, particularmente en el contexto del programa formalista que fue iniciado por Hilbert.

Las propuestas originales de los formalistas asegurar por una prueba de consistencia matemática clásica no contemplaban ese tal método como inducción del transfinite hasta ε 0 tendría que ser utilizado. Hasta qué punto la prueba de Gentzen puede aceptarse como asegurar número clásico teoría en el sentido de formulación de problema es en el estado actual de los asuntos objeto de juicio individual, dependiendo de cómo listo uno es aceptar de inducción hasta ε 0 como un método de finitary.

Otras pruebas de consistencia de la aritmética

Primera versión de Gentzen de su prueba de consistencia no fue publicada durante su vida porque Paul Bernays había opuesto a un método utilizado implícitamente en la prueba. El modificado de prueba, descrito anteriormente, fue publicado en 1936 en la Anales. Gentzen se encendió publicar consistencia más dos pruebas, una en 1943 en 1938 y una. Todos ellos figuran en el)Gentzen y Szabo 1969).

En 1940 Wilhelm Ackermann publicado una prueba de consistencia para Peano aritmética, utilizando también el ordinal ε0.

Trabajo iniciado por prueba de Gentzen

Prueba de Gentzen es el primer ejemplo de lo que se denomina prueba teórica Análisis ordinal. En análisis ordinal uno calibres la fuerza de las teorías mediante la medición de cómo es grande los ordinales (constructivos) son puede ser probada para ser ordenado, o equivalente para cómo es grande un ordinal (constructivo) inducción del transfinite se puede probar. Un ordinal constructiva es el tipo de orden de un recursiva bien pedido de números naturales.

Laurence de Kirby y Jeff Paris en 1982 que Teorema de Goodstein no se puede probar en aritmética de Peano basado en Teorema de Gentzen.

Notas

  1. ^ Ver Kleene (2009págs. 476-499) para una presentación completa de la prueba de Gentzen y diversos comentarios sobre el significado histórico y filosófico del resultado.
  2. ^ Weyl (2012p. 144).

Referencias

  • Gentzen, Gerhard (1936), «Mueren Widerspruchsfreiheit der reinen Zahlentheorie», Mathematische Annalen 112: 493 – 565, doi:10.1007/BF01565428 -Traducido como 'La consistencia de la aritmética», en)Gentzen y Szabo 1969).
  • Gentzen, Gerhard (1938), "Neue Fassung des Widerspruchsfreiheitsbeweises für die reine Zahlentheorie", Forschungen zur Logik und zur Grundlegung der exakten Wissenschaften 4: 19: 44 -Traducido como nueva versión de la prueba para la teoría de números elemental coherencia, en)Gentzen y Szabo 1969).
  • Gentzen, Gerhard (1969), M. E. Szabo, ed., Papeles recogidos de Gerhard Gentzen, Estudios en lógica y las fundaciones de las matemáticas (ed. Hardcover), Amsterdam: Holanda del norte, ISBN0-7204-2254-X -una traducción al Inglés de documentos.
  • Gödel, K. (2001) [1938], "Conferencia en de Zilsel", en Feferman, Salomón, Kurt Gödel: Trabajos recogidos, vol. III no publicados de ensayos y conferencias (libro en rústica ed.), Oxford University Press Inc., pp. 87-113, ISBN0-19-514722-7
  • Jervell, Herman Ruge (1999), Un curso en teoría de la prueba (libro de texto proyecto ed.)
  • Kirby, L.; París, J. (1982), "resultados de independencia accesible para aritmética de Peano" (PDF), Toro. Matemáticas de Londres. SOC. (LMS) 14: 285 – 293, doi:10.1112/blms/14.4.285
  • Kleene, Stephen Cole (2009) [1952]. Introducción a la metamatemática. Internacional de prensa de Ishi. ISBN978-0-923891-57-2.
  • Tait, W. W. (2005), "Reformulación de Gödel de consistencia primer de Gentzen prueba de aritmética: la interpretación de ningún contraejemplo" (PDF), El boletín de la lógica simbólica (ASL) 11 (2): 225 – 238, doi:10.2178/BSL/1120231632, ISSN1079-8986
  • Weyl, Hermann (2012). Niveles de infinito: seleccionados escritos sobre matemáticas y filosofía. Nueva York: Publicaciones de Dover. ISBN978-0-486-48903-2.

Otras Páginas

Obtenido de"https://en.copro.org/w/index.php?title=Gentzen%27s_consistency_proof&oldid=696718916"