O Desenvolvimento Da Teoria Da Prova

Índice:

O Desenvolvimento Da Teoria Da Prova
O Desenvolvimento Da Teoria Da Prova

Vídeo: O Desenvolvimento Da Teoria Da Prova

Vídeo: O Desenvolvimento Da Teoria Da Prova
Vídeo: Psicologia do desenvolvimento/Teorias da aprendizagem - Aula 01: Hamurabi Messeder 2024, Março
Anonim

Navegação de entrada

  • Conteúdo da Entrada
  • Bibliografia
  • Ferramentas Acadêmicas
  • Pré-visualização do Friends PDF
  • Informações sobre autor e citação
  • De volta ao topo

O desenvolvimento da teoria da prova

Publicado pela primeira vez em 16 de abril de 2008; revisão substantiva segunda-feira, 13 de outubro de 2014

O desenvolvimento da teoria da prova pode ser naturalmente dividido em: a pré-história da noção de prova na lógica e na matemática antigas; a descoberta por Frege de que as provas matemáticas, e não apenas as proposições da matemática, podem (e devem) ser representadas em um sistema lógico; A antiga teoria axiomática da prova de Hilbert; falha dos objetivos de Hilbert através dos teoremas da incompletude de Gödel; A criação de Gentzen dos dois principais tipos de sistemas lógicos da teoria da prova contemporânea, dedução natural e cálculo sequencial (veja a entrada sobre raciocínio automatizado); aplicações e extensões da dedução natural e cálculo sequencial, até a interpretação computacional da dedução natural e suas conexões com a ciência da computação.

  • 1. Pré-história da noção de prova
  • 2. Antiga teoria axiomática da prova de Hilbert
  • 3. A improvabilidade da consistência
  • 4. Dedução natural e cálculo sequencial
  • 5. A consistência da aritmética e análise
  • 6. Desenvolvimentos posteriores na dedução natural
  • 7. Cálculo sequencial: desenvolvimentos / aplicações posteriores
  • 8. Os objetivos da teoria da prova
  • Bibliografia

    • Textos sobre Teoria da Prova
    • Obras originais e suas reimpressões
    • Literatura secundária
  • Ferramentas Acadêmicas
  • Outros recursos da Internet
  • Entradas Relacionadas

1. Pré-história da noção de prova

A teoria da prova pode ser descrita como o estudo da estrutura geral de provas matemáticas e de argumentos com força demonstrativa, como encontrado na lógica. A ideia de tais argumentos demonstrativos, ou seja, aqueles cuja conclusão decorre necessariamente das suposições feitas, é central na Analytica Posteriora de Aristóteles: uma ciência dedutiva é organizada em torno de uma série de conceitos básicos que são assumidos entendidos sem maiores explicações, e vários de verdades ou axiomas básicos que são vistos como verdadeiros imediatamente. Conceitos e teoremas definidos são reduzidos a esses dois, os últimos através de provas. O relato de Aristóteles da prova como argumento demonstrativo se ajusta muito bem à estrutura da geometria antiga axiomatizada em Euclides. A forma específica da lógica de Aristóteles, a teoria do silogismo, em vez disso, ao que parece,quase nada a ver com provas na geometria euclidiana. Essas provas permaneceram intuitivas por mais de dois mil anos.

Antes do trabalho de Frege em 1879, ninguém parece ter sustentado que poderia haver um conjunto completo de princípios de prova, no sentido expresso por Frege quando ele escreveu que em sua linguagem simbólica,

tudo o que é necessário para uma inferência correta é expresso na íntegra, mas o que não é necessário geralmente não é indicado; nada resta à adivinhação. (Begriffsschrift, p. 3)

(Pode-se argumentar que Boole é uma exceção no que diz respeito à lógica proposicional clássica.) O passo a frente de Frege foi decisivo para o desenvolvimento da lógica e do estudo fundamental. O contraste com os antigos é grande: Aristóteles deu um padrão para combinar argumentos, mas a ideia de um conjunto finito de regras fechadas estava, filosoficamente, além dos sonhos de qualquer pessoa antes de Frege, com a possível exceção de Leibniz.

Como sabemos hoje, os princípios de prova de Frege são completos para a lógica clássica de predicados.

Por volta de 1890, Giuseppe Peano deu uma formalização da inferência lógica, com o objetivo de representar provas formalmente em aritmética. Seu artigo seminal Arithmetices principia, nova methodo exposita, escrito originalmente em latim, está incluído na tradução em inglês da coleção From Frege to Gödel (1967) que Jean van Heijenoort editou. Infelizmente, o editor não reconheceu o que Peano fez com a inferência formal, e a visão difundida de que Peano formalizava apenas a linguagem da lógica e da aritmética, não seus princípios de prova. Se as provas de Peano são lidas com um pouco de cuidado, verifica-se que são derivações puramente formais que usam dois princípios:

  1. Axiomas implicam suas instâncias. Tais implicações podem ser escritas como linhas nas provas.
  2. Uma implicação e seu antecedente implicam juntos o consequente.

Peano é muito cuidadoso ao listar, em todas as linhas de suas derivações, qual é o fundamento formal para escrever a linha.

Russell adotou a lógica de Frege, mas usou a notação e as regras formais de prova de Peano, em um artigo de 1906 com o título "A teoria da implicação". Sua maquinaria formal é exatamente a mesma da Peano. Em trabalhos posteriores, Russell mudou o sistema axiomático e o de Principia Mathematica (Whitehead e Russell 1910–13) tornou-se padrão. A idéia filosófica de Russell, e aqui ele seguiu Frege, era que os axiomas expressam verdades lógicas básicas, e outras verdades lógicas são derivadas delas através de modus ponens e generalização universal, os dois princípios que Frege havia identificado. A matemática deveria ser reduzida à lógica, para que suas provas fossem apresentadas no mesmo padrão axiomático.

A abordagem de Frege e Peano-Russell à lógica tornou-se universalmente aceita, especialmente pela influência de Hilbert e seus colegas de trabalho na década de 1920. No século 19, Frege era uma figura marginal, e a abordagem algébrica da lógica, como em Boole e especialmente Ernst Schröder, era a dominante. É claro que havia uma boa compreensão dos princípios da lógica de predicados nessa tradição, pois como poderia ter existido um teorema de Löwenheim-Skolem? Skolem descobriu a lógica de Frege através de Principia Mathematica somente depois de ter elaborado o teorema em seu artigo de 1920. A primeira seção desse artigo, amplamente lida por causa da tradução em inglês de From Frege to Gödel, de Van Heijenoort, marca o fim do processo algébrico. tradição da lógica que se fundiu silenciosamente com a teoria da rede. Outras seções do artigo contêm um começo notável da análise de provas na teoria das redes e na geometria projetiva: Skolem considerou os axiomas de uma teoria matemática de um ponto de vista puramente combinatório e formal, como meio para produzir derivações de uma fórmula a partir de dados fórmulas usadas como premissas. Foi descoberto no início dos anos 90 que a parte da teoria das redes contém a solução de um problema de decisão, chamado de problema da rede para redes geradas livremente, cuja solução conhecida surgiu a partir de 1988! A terminologia e a notação de Skolem na teoria da rede são as de Schröder e isso é parte da razão pela qual seu trabalho foi uma oportunidade perdida para a teoria da prova. Skolem considerou os axiomas de uma teoria matemática de um ponto de vista puramente combinatório e formal, como um meio para produzir derivações de uma fórmula a partir de determinadas fórmulas usadas como premissas. Foi descoberto no início dos anos 90 que a parte da teoria das redes contém a solução de um problema de decisão, chamado de problema da rede para redes geradas livremente, cuja solução conhecida surgiu a partir de 1988! A terminologia e a notação de Skolem na teoria da rede são as de Schröder e isso é parte da razão pela qual seu trabalho foi uma oportunidade perdida para a teoria da prova. Skolem considerou os axiomas de uma teoria matemática de um ponto de vista puramente combinatório e formal, como um meio para produzir derivações de uma fórmula a partir de determinadas fórmulas usadas como premissas. Foi descoberto no início dos anos 90 que a parte da teoria das redes contém a solução de um problema de decisão, chamado de problema da rede para redes geradas livremente, cuja solução conhecida surgiu a partir de 1988! A terminologia e a notação de Skolem na teoria da rede são as de Schröder e isso é parte da razão pela qual seu trabalho foi uma oportunidade perdida para a teoria da prova.chamou a palavra problema para treliças geradas livremente, cuja solução conhecida surgiu em 1988! A terminologia e a notação de Skolem na teoria da rede são as de Schröder e essa é parte da razão pela qual seu trabalho foi uma oportunidade perdida para a teoria da prova.chamou a palavra problema para treliças geradas livremente, cuja solução conhecida surgiu em 1988! A terminologia e a notação de Skolem na teoria da rede são as de Schröder e essa é parte da razão pela qual seu trabalho foi uma oportunidade perdida para a teoria da prova.

2. Antiga teoria axiomática da prova de Hilbert

O livro de Hilbert, Grundlagen der Geometrie, de 1899, preparou o terreno para os problemas fundamentais da matemática nas primeiras décadas do século XX. Podemos listar esses problemas da seguinte maneira:

  1. A formalização de uma teoria matemática. Isso inclui uma escolha de seus objetos e relações básicos e uma escolha dos axiomas.
  2. Uma prova da consistência dos axiomas.
  3. A questão da independência mútua e completude dos axiomas.
  4. O problema da decisão: existe um método para responder a qualquer pergunta que possa ser levantada dentro da teoria?

Quanto à geometria de Hilbert, sua tentativa de formalização ficou aquém do ideal para o qual deu à luz. Hilbert encontrou um campo muito mais importante ao qual sua "metamatemática" deveria ser aplicada, a saber, aritmética e análise. O trabalho de base foi um estudo dos quatro problemas fundamentais em formulações axiomáticas da lógica pura. A lógica proposicional foi assim formalizada, considerada consistente, completa e decidível. Os primeiros resultados sobre lógica de predicados são de 1915, quando Leopold Löwenheim deu sua versão do que mais tarde se tornou o teorema de Löwenheim-Skolem para lógica de predicados (veja a entrada na lógica clássica). Ele também resolveu casos especiais do problema de decisão. Esse desenvolvimento foi independente da tradição Frege-Russell e, em vez disso, foi baseado na abordagem algébrica da lógica de Ernst Schröder. Por volta de 1920,a abordagem axiomática do “estilo Hilbert”, como costuma ser chamada, era conhecida por todos e dominava a cena lógica; a abordagem algébrica se fundiu quase sem aviso prévio com a teoria da rede. Em 1928, no Grundzüge der theoryetischen Logik de Hilbert e Ackermann, foi apresentado um sistema formal axiomático para lógica de predicados, juntamente com o problema de sua completude. Este último foi resolvido por Gödel em 1929, publicado um ano depois (Gödel 1930). O quarto problema fundamental, o problema de decisão para a lógica de predicados, mostrou ter uma solução negativa em um breve artigo de Church em 1936 como corolário do teorema da incompletude de Gödel.s Grundzüge der theoryetischen Logik, um sistema formal axiomático para lógica de predicados foi apresentado, juntamente com o problema de sua completude. Este último foi resolvido por Gödel em 1929, publicado um ano depois (Gödel 1930). O quarto problema fundamental, o problema de decisão para a lógica de predicados, mostrou ter uma solução negativa em um breve artigo de Church em 1936 como corolário do teorema da incompletude de Gödel.s Grundzüge der theoryetischen Logik, um sistema formal axiomático para lógica de predicados foi apresentado, juntamente com o problema de sua completude. Este último foi resolvido por Gödel em 1929, publicado um ano depois (Gödel 1930). O quarto problema fundamental, o problema de decisão para a lógica de predicados, mostrou ter uma solução negativa em um breve artigo de Church em 1936 como corolário do teorema da incompletude de Gödel.

Hilbert e sua escola, com Bernays, Ackermann e von Neumann como principais, bem como o jovem Herbrand na França, prosseguiram o estudo metamatemático da aritmética na última parte da década de 1920. Hilbert desenvolveu um método para o estudo de problemas de consistência, chamado método de substituição do épsilon, para lidar com os quantificadores. Ele achava que inferências indiretas com quantificadores em casos com uma infinidade de objetos eram o ponto crucial das provas de consistência e precisavam de uma justificativa. Digamos, se a suposição de que todos os números naturais têm a propriedade P leva a uma impossibilidade, a existência de um número com a propriedade contrária não-P pode ser inferida. O problema central era justificar o uso da lógica clássica em provas matemáticas, aritméticas em primeiro lugar. Ackermann estava muito próximo de uma solução no final da década de 1920 e o otimismo reinou na escola Hilbert. Então, é claro, o inesperado aconteceu quando Gödel provou a impossibilidade de uma formalização completa da aritmética elementar e, como logo foi interpretado, a impossibilidade de provar a consistência da aritmética por meios financeiros, os únicos julgados "absolutamente confiáveis" por Hilbert.

3. A improvabilidade da consistência

Depois que Gödel tornou público o incompleto da aritmética em setembro de 1930, von Neumann descobriu que a consistência da aritmética estaria entre as proposições improváveis de Gödel. Infelizmente, Gödel fez a mesma descoberta, então von Neumann nunca publicou sua prova. No entanto, ele conjeturou em correspondência com Gödel a improvabilidade da consistência da aritmética e, portanto, da matemática como um todo, em algum sentido absoluto. Von Neumann foi o personagem-chave na recepção dos resultados de Gödel: ele interrompeu suas palestras sobre a teoria da prova de Hilbert em Berlim no outono de 1930 para explicar as novas descobertas. Esses eventos criaram uma enorme empolgação entre os matemáticos, como testemunhado pelo testemunho de Carl Hempel:

Fiz um curso lá com von Neumann, que tratou da tentativa de Hilbert de provar a consistência da matemática clássica por meios financeiros. Lembro que no meio do curso von Neumann chegou um dia e anunciou que acabara de receber um artigo de… Kurt Gödel, que mostrou que os objetivos que Hilbert tinha em mente e nos quais eu ouvira o curso de Hilbert em Göttingen não podiam. ser alcançado de todo. Von Neumann, portanto, abandonou o assunto e dedicou o resto do curso à apresentação dos resultados de Gödel. A descoberta provocou uma enorme empolgação. (Hempel 2000, p. 13)

Entre 1932 e 1933, Gödel e Gentzen encontraram independentemente um do outro uma tradução da aritmética clássica do Peano para a aritmética intuicionista de Heyting. Especificamente, mostra que, se uma contradição é comprovável no primeiro, é comprovável no segundo. Então a consistência da aritmética intuicionista garantiria também a consistência da aritmética clássica. Esse resultado foi uma surpresa: como mencionado, Hilbert pensara que as provas de existência indireta "transfinita" seriam a parte da aritmética que precisa ser protegida de contradições. Pelos resultados de Gödel e Gentzen, a aritmética já intuicionista continha princípios que iam além do raciocínio financeiro. Uma carta que Gentzen escreveu a Heyting em 25 de fevereiro de 1933 resume a situação da seguinte forma:

Uma prova de consistência por meios finitos … não foi bem-sucedida até agora, de modo que esse objetivo original de Hilbert não foi alcançado. Se, por outro lado, alguém admitir a posição intuicionista como uma base segura em si mesma, isto é, como consistente, a consistência da aritmética clássica é garantida pelo meu resultado. Se alguém quisesse satisfazer os requisitos de Hilbert, a tarefa ainda seria mostrar consistência aritmética intuicionista. Isso, no entanto, não é possível nem mesmo pelo aparato formal da aritmética clássica, com base no resultado de Gödel em combinação com a minha prova. Mesmo assim, estou inclinado a acreditar que uma prova de consistência da aritmética intuicionista, de uma posição ainda mais evidente, é possível e também desejável. (Menzler-Trott 2007, p. 38)

O último mencionado foi o objetivo que Gentzen estabeleceu para si no início de 1932, quando, em uma carta ao seu antigo professor Hellmuth Kneser, ele escreveu:

Eu estabeleci como tarefa específica encontrar uma prova da consistência da dedução lógica na aritmética … A tarefa se torna um problema puramente matemático através da formalização da dedução lógica. Até agora, a prova de consistência foi realizada apenas em casos especiais, por exemplo, a aritmética dos números inteiros sem a regra da indução completa. Eu gostaria de prosseguir ainda mais neste ponto e limpar pelo menos a aritmética com a indução completa. Estou trabalhando nisso há quase um ano e espero terminar em breve e, em seguida, apresentaria esse trabalho como minha dissertação (com o Prof. Bernays). (Menzler-Trott 2007, p. 31)

4. Dedução natural e cálculo sequencial

Ao seguir seu programa de consistência, Gentzen estabeleceu como sua primeira tarefa a análise da dedução puramente lógica, a ser estendida posteriormente à aritmética e à análise. Em sua tese (1934-1935), Gentzen afirma que ele estabeleceu como tarefa a análise de provas matemáticas à medida que ocorrem na prática. A primeira observação é que as provas reais não se baseiam em axiomas expressos em uma linguagem lógica, como na teoria axiomática da prova de Hilbert. A característica mais típica é que os teoremas fazem suas reivindicações sob algumas suposições. As suposições são analisadas em partes e a conclusão também é analisada em partes até que essas duas análises se encontrem e uma prova possa ser sintetizada. A última análise procede pelo que Gentzen chamou de regras de introdução: elas fornecem condições suficientes para derivar uma proposição de uma determinada forma. Por exemplo,para derivar uma conjunção A e B, é suficiente derivar as conjunções A e B separadamente. A inferência é dada formalmente como na regra

AB &EU
A e B

As premissas, em vez disso, são analisadas em seus componentes por meio de regras de eliminação que dão, em geral, consequências imediatas das premissas. Por exemplo, uma conjunção usada como suposição pode ser decomposta em seus constituintes, como nas regras

A e B & E 1
UMA
A e B & E 2
B

Gentzen desenvolveu e estudou o sistema de dedução natural durante 1932 e chegou em setembro de 1932 a um cálculo de dedução natural (ND, abreviado) que hoje é padrão. Nessa época, ele havia notado que, se uma introdução, digamos uma derivação de A e B de A e B separadamente, é seguida pela eliminação correspondente, digamos uma derivação de A, a fórmula A e B constitui um máximo local, um " outeirinho”, que pode ser eliminado. Ele também chamou essas colinas de "desvios", e o que agora é chamado de conversão de desvios remove esses pares desnecessários de etapas de eliminação de introdução. O resultado das etapas de "normalização" é uma derivação na "forma normal".

Talvez a implicação seja mais típica do ND do que da conjunção: para derivar A ⊃ B, alguém assume temporariamente A e tenta derivar B. Se isso der certo, a suposição temporária é encerrada ou “descarregada” quando a conclusão de A ⊃ B é feita, como na derivação esquemática

[UMA]
B ⊃I
A ⊃ B

Na outra direção, A ⊃ B pode ser eliminado se uma derivação de A for encontrada, pois B pode ser concluído:

A ⊃ BA ⊃E
B

Se a regra ⊃I é seguida por ⊃E, existe uma não normalidade que é removida por uma conversão de desvio: uma derivação de B (e o que se segue a seguir) é construída tomando a derivação da premissa menor A da regra de eliminação e a derivação de B da suposição A na introdução. Essas duas peças são combinadas em uma derivação de B que não possui a fórmula de desvio A ⊃ B. Na tese de Gentzen, todas as suposições são encerradas por introduções de implicação, mas hoje em dia consideramos também derivações que deixam uma coleção de fórmulas como suposições abertas.

Observando as regras de conjunção e implicação, observa-se que as premissas (as fórmulas imediatamente acima da linha de inferência) são subfórmulas da conclusão nas regras I, ao contrário das regras E. Gentzen notou que em derivações normais, essa propriedade de etapas únicas é herdada por toda a derivação, no sentido de que todas as fórmulas são subformulas da conclusão. Esse resultado deu como subproduto um método de decisão para a lógica proposicional intuicionista. Outro corolário era uma prova sintática de consistência: se uma contradição é comprovável, qualquer coisa é provável, mas uma fórmula atômica, por exemplo, não tem prova: se ela tem uma prova, tem uma prova normal, mas nenhuma regra E se aplica a um fórmula atômica, e nenhuma regra I também a conclui.

A ideia de Gentzen era estender a dedução natural a um sistema aritmético pela adição de uma regra que corresponde ao princípio da indução completa. A consistência seguiria a normalização das derivações e a propriedade da subformula. No início de 1933, Gentzen percebeu que essa estratégia de prova não passaria: a regra de indução é esquemática e possui uma infinidade de instâncias, sem limites à complexidade das fórmulas de indução. Seria impossível restringir essas fórmulas antecipadamente, portanto, nenhuma propriedade de subfórmulas pode conter. Após esse fracasso, Gentzen retirou literalmente de seu manuscrito de tese a tradução da aritmética clássica para a aritmética intuicionista e a submeteu como artigo em março de 1933, mas retirou o artigo após ouvir a publicação de Gödel sobre o resultado.

Gentzen escreveu que ele era incapaz de provar um teorema de normalização para um sistema clássico de ND. Ele, portanto, inventou outro cálculo lógico que chamou de cálculo sequencial (Sequenzenkalkul, literalmente “cálculo de sequências”) e o transformou no tópico central de sua tese. O nome do cálculo vem da representação de suposições de uma derivação como uma lista. A palavra "sequente" usada como substantivo é uma sugestão de Kleene em sua Introdução à Metamatemática (1952: 441), adotada em muitas línguas na forma de palavras puramente inventadas.

O cálculo sequencial, SC, resumidamente, pode ser visto como uma representação formal da relação de derivabilidade na dedução natural. Um seqüente consiste em uma lista Γ de fórmulas, uma flecha (em Gentzen, posteriormente outros marcadores foram utilizados) e uma fórmula como conclusão. A lista fornece as suposições das quais a conclusão depende em uma derivação, em uma notação local em que no ND elas são encontradas nas folhas de uma árvore de derivação. Gentzen também generalizou sequências para que eles tenham, em vez de uma conclusão, uma lista de possíveis casos após a seta. Essa novidade levou à primeira formulação satisfatória de um sistema de prova para a lógica clássica. As regras de Gentzen para conjunção e implicação são, com vírgulas separando elementos em listas:

Conjunção
Γ Δ, A Γ → Δ, B R &
Γ Δ, A e B
A, Γ Δ L & 1
A e B, Γ Δ
B, Γ Δ L & 2
A e B, Γ Δ
Implicação
A, Γ Δ, B R⊃
Γ Δ, A ⊃ B
Γ Θ, AB, Δ Λ L⊃
A ⊃ B, Γ, Δ Θ, Λ

Este não é o lugar para explicar os detalhes do ND e do SC (mas consulte a entrada sobre raciocínio automatizado). Gentzen formulou o último, denotado LK, de modo que desse um cálculo intuicionista, denotado LJ, como um caso especial, aquele em que a conclusão é uma lista de no máximo um caso. Ele então provou o análogo do teorema da normalização para o cálculo clássico, o cálculo e a prova cuidadosamente formulados para que o resultado para o cálculo intuicionista fosse um caso especial daquele do cálculo clássico. Em LJ e LK, L significa "logística", um termo pelo qual Gentzen se refere ao cálculo axiomático da lógica de Frege, Russell, Hilbert e Bernays. Em tais cálculos, cada linha de uma derivação é correta em si mesma, isto é, uma verdade lógica, de onde o termo. As letras K e J vêm das palavras alemãs klassisch e intuitionistisch.(O último deve, portanto, estar em maiúsculas "I", mas o alemão antigo usa maiúsculas "J" para maiúsculas "I".)

Gentzen chamou o análogo da normalização pelo nome sem imaginação de Hauptsatz, "teorema principal". Hoje, a terminologia padrão é o “teorema da eliminação de cortes”. Todas as regras lógicas do SC têm a propriedade subformula em um sentido muito imediato: cada fórmula em uma premissa é uma fórmula ou subformula na conclusão. A regra para combinar derivações, análoga à explicada acima para o caso de conversões de desvio no ND, é chamada de "corte". Nela, a fórmula A aparece como um caso em uma primeira premissa e como uma suposição em uma segunda premissa. Na conclusão, essa fórmula desapareceu e as premissas das duas premissas foram reunidas:

Γ AA, Δ C Cortar
Γ, Δ C

Assim, o corte é a única regra que faz uma fórmula "desaparecer" em uma derivação. Gentzen mostrou que instâncias da regra de corte podem ser eliminadas das derivações permutando-as para cima até atingirem pontos nos quais a derivação inicia. No ND, os pontos de partida são suposições; em SC, são “sequências iniciais” da forma A → A, na qual a fórmula de suposição A é ao mesmo tempo a conclusão. Um corte com um seqüente como uma premissa tem a outra premissa igual à conclusão e pode, portanto, ser excluído.

Após a prova da eliminação do corte, Gentzen não teve utilidade para a prova da normalização para dedução natural intuicionista. Ele deu a primeira versão manuscrita de sua tese, com a prova detalhada de normalização (equivalente a cerca de 13 páginas impressas) a Bernays, mas parece que este último nunca percebeu o que tinha em suas mãos. A prova, entre os trabalhos de Bernays em Zurique, foi descoberta pelo autor atual em fevereiro de 2005 e agora está disponível em uma tradução para o inglês (Gentzen 1933 [2008]).

5. A consistência da aritmética e análise

Após seu trabalho de tese sobre ND e SC para lógica pura, Gentzen continuou seu plano de provar a consistência da aritmética. O resultado ficou pronto em dezembro de 1934. O que essa primeira prova foi, não é conhecido em detalhes. No entanto, uma carta a Bernays de 1938 indica que a prova que Gentzen escreveu no verão de 1935 não era a original, mas uma segunda prova (ver Menzler-Trott 2001, 79). Essa segunda prova foi criticada por Bernays e Gödel, que a discutiram durante sua viagem ao Atlântico em Princeton, em setembro de 1935. A idéia de Gentzen na prova foi a seguinte: primeiro, considere o fragmento de quantificação conjunta-negação-universal da dedução natural como a lógica usada em a formalização da aritmética. Em seguida, escreva cada instância de regra para que as premissas e conclusões tenham as premissas abertas listadas à esquerda,com uma seta separando a conclusão, portanto, como sequências. Essa variante do ND agora é chamada de ND no estilo SC. Considere uma sequência Γ C. Se sua conclusão é uma fórmula atômica, é uma equação entre números. No pior caso, é falso, então considere a lista de suposições. Se uma suposição for uma conjunção, substitua-a por um conjunto de sua escolha, se uma quantificação universal, por uma instância. Se for uma negação ¬ A, substitua a conclusão por A. Se, em qualquer estágio deste "processo de redução", a conclusão de um sequente for uma fórmula composta, você deverá considerar qualquer conjunto ou instância de quantificação universal como uma conclusão possível. Em caso de negação ¬ A como conclusão, mova A para a parte da suposição e substitua a conclusão por 0 = 1. Gentzen mostra que, procedendo dessa maneira sob a suposição de que o sequente em questão é derivável, uma equação verdadeira é encontrada como uma conclusão, ou uma equação falsa como uma suposição. Portanto,não há sequências deriváveis com todas as suposições verdadeiras e a conclusão falsa.

Não ficou claro para Gödel e Bernays o que a prova supunha; eles pensaram que assumia o que é conhecido na matemática intuicionista como o teorema dos fãs, mas isso era falso. O término do procedimento de redução de Gentzen pode ser provado em vez disso por indução em árvores bem fundamentadas ("barra-indução"), um princípio usado por Gentzen por motivos intuitivos. De qualquer forma, o resultado da crítica foi que Gentzen mudou sem mais delongas a prova para uma terceira prova que usa o agora famoso princípio da indução transfinita até o primeiro número épsilon. Essa indução foi apresentada através de uma codificação que utilizava números decimais. O resultado concreto das mudanças para o artigo de Gentzen publicado em 1936 não foi bom: o cálculo lógico foi alterado no meio de um artigo de setenta páginas ímpares que se tornou muito difícil de ler. Portanto, Gentzen deu mais uma, pela contagem atual, quarta prova da consistência da aritmética em 1938 (nos arquivos de Bernays da ETH Zurique), desta vez com base no cálculo sequencial clássico LK de 1933. Como mencionado, a correspondência com Bernays indica que assim, ele voltou ao método de prova que levou ao sucesso em 1934. O uso da indução transfinita é tornado claramente visível no artigo de 1938 através de uma notação ordinal. Tais princípios de indução na “segunda classe numérica” de Cantor são discutidos em detalhes na aula de Hilbert de 1925 “Über das Unendliche” (“On the infinite”, publicada em 1926), um artigo ao qual Gentzen se referia.desta vez, com base no cálculo sequencial clássico LK de 1933. Como mencionado, a correspondência com Bernays indica que ele retornou ao método de prova que levou ao sucesso em 1934. O uso da indução transfinita é claramente visível no artigo de 1938 através de um notação ordinal. Tais princípios de indução na “segunda classe numérica” de Cantor são discutidos em detalhes na aula de Hilbert de 1925 “Über das Unendliche” (“On the infinite”, publicada em 1926), um artigo ao qual Gentzen se referia.desta vez, com base no cálculo sequencial clássico LK de 1933. Como mencionado, a correspondência com Bernays indica que ele retornou ao método de prova que levou ao sucesso em 1934. O uso da indução transfinita é claramente visível no artigo de 1938 através de um notação ordinal. Tais princípios de indução na “segunda classe numérica” de Cantor são discutidos em detalhes na aula de Hilbert de 1925 “Über das Unendliche” (“On the infinite”, publicada em 1926), um artigo ao qual Gentzen se referia.s 1925 palestra “Über das Unendliche” (“Sobre o infinito”, publicado em 1926), um artigo ao qual Gentzen se referiu.s 1925 palestra “Über das Unendliche” (“Sobre o infinito”, publicado em 1926), um artigo ao qual Gentzen se referiu.

Alguém poderia pensar que era isso, mas Gentzen tinha motivos para produzir até uma quarta prova da consistência da aritmética, em seu último artigo publicado em 1943, mas escrito antes da guerra em 1939. Ele estendeu a aritmética Peano através de ordinais transfinitos e fez o princípio da indução transfinita parte deste cálculo estendido. Em seguida, ele mostrou diretamente que a indução transfinita até o primeiro número epsilon ε 0 é expressável, mas não comprovável no sistema. O teorema da incompletude de Gödel é assim provado de uma maneira completamente diferente. A ideia da prova é, em breves termos, a seguinte: primeiro é estabelecido o que significa derivar a indução transfinita a um número ordinal específico no sistema. Em segundo lugar, números ordinais abaixo de ε 0estão associados a derivações. Estes são chamados de "valores". É então mostrado que se a indução transfinita para um número ordinal é derivável, esse número ordinal não pode ser maior que o valor da derivação. Portanto, a indução de transfinitos para ε 0 não é derivável.

Como o princípio de indução pode ser expresso, mas não provado na aritmética comum, é encontrada uma fórmula improvável na aritmética Peano. Uma conseqüência fácil da versão de Gentzen do teorema da incompletude é a consistência da aritmética Peano, porque qualquer coisa seria provável em um sistema inconsistente. Ao contrário da fórmula improvável "artificial" de Gödel, obtida através da codificação do predicado de provabilidade aritmetizado, o princípio de indução transfinita de Gentzen é um princípio da matemática "comum".

A última prova de Gentzen determinou o “ordinal teórico da prova” da aritmética Peano, a saber, a necessária para provar a consistência, com a propriedade de que nada menos seria suficiente. O trabalho marcou o início da teoria da prova ordinal. Foi sem dúvida a conquista fundamental mais notável da aritmética após os teoremas da incompletude de Gödel, mas ainda é amplamente desconhecida - é possível encontrar muitos livros sobre os teoremas de Gödel que nem sequer mencionam Gentzen.

Parece que Gödel não tinha pensado em dar uma prova consistente de aritmética por meio do uso de princípios não-finitários, mas ainda construtivos. No final dos anos 30, pelo menos a partir de 1938, ele desenvolveu como resposta à prova de Gentzen sua própria interpretação especial da lógica intuicionista e aritmética, o que passou a ser conhecido como a interpretação Dialética. Ele usa funcionais computáveis para interpretar as provas da aritmética intuicionista. Gödel publicou a interpretação apenas em 1958, embora a tenha apresentado em palestras em 1941. Não se sabe se ele discutiu o assunto quando conheceu Gentzen em dezembro de 1939.

A pedido de Bernays, Ackermann reproduziu a prova de Gentzen em termos do cálculo epsilon de Hilbert em 1940. O artigo de Ackermann foi o ponto de partida da interpretação da aritmética de Kreisel em 1951 “sem contra-exemplo”. Foi uma surpresa quando a publicação dos artigos coletados de Gödel trouxe à tona sua “conferência de Zilsel” em Viena em 1938: ele delineia essa interpretação como uma reformulação da prova de Gentzen em 1935. (O assunto é discutido em grande detalhe em Tait (2005), que trabalhou na interpretação sem contra-exemplo e sua extensão à análise na década de 1960.)

A próxima tarefa óbvia na teoria da prova, após a prova da consistência da aritmética, era provar a consistência da análise, isto é, da teoria dos números reais. Gentzen fez algum trabalho nessa direção, mas foi designado para o serviço militar no outono de 1939. (Ele observou e relatou o tipo, número e direção das aeronaves que voavam acima da cidade de Brunswick, até ser atingido por um nervosismo. colapso no início de 1942.) A partir de 1943, ele retomou o trabalho de análise, mas as dificuldades intrínsecas ao tópico foram grandes, assim como as dificuldades práticas da vida causadas pela guerra. A análise deveria ser formulada como um sistema aritmético de segunda ordem, o que significa que a quantificação é estendida sobre predicados da teoria dos números ou, equivalentemente, sobre conjuntos de números naturais. A teoria dos números de segunda ordem é usada no último artigo de Gentzen,publicado em 1943, no qual é demonstrado brevemente que o princípio da indução transfinita até ε0 é derivável na teoria dos números de segunda ordem.

Mais de meio século se passou sem nenhuma prova construtiva da consistência da aritmética completa de segunda ordem à vista. Os pioneiros neste campo incluíram Kurt Schütte e Gaisi Takeuti. O primeiro criou em 1951 um cálculo seqüencial infinito para apresentar provas de consistência de maneira perspicaz; o último usou um cálculo mais tradicional ao estilo Gentzen (ver Takeuti, 1987).

Na pesquisa atual na teoria da prova da aritmética de segunda ordem, estuda-se o que é conhecido como subsistemas da aritmética de segunda ordem. Os resultados mais fortes de hoje são, em um resumo muito breve, o seguinte: permita que o X ultrapasse os predicados da teoria dos números. Uma fórmula como X (x) afirma que x tem a propriedade expressa por X. Agora podemos usar lógica de primeira e segunda ordem para formar fórmulas compostas como ∀ X (X x ∨ x X x). A coleção de números naturais para os quais uma fórmula com um quantificador universal de segunda ordem é chamada de conjunto Π11 (nesse caso, o conjunto dos números naturais). De maneira mais geral, um axioma de compreensão é da forma ∃ X ∀ x (X x ↔ B (x)). Se a fórmula B não possui quantificadores de segunda ordem, o axioma fornece o que é chamado de compreensão aritmética ou ACA. Se B pode ter a forma ∀ Y ∃ ZC (x) sem outros quantificadores de segunda ordem, é obtido o caso especial de Π12 compreensão. Provas de consistência para um subsistema de aritmética de segunda ordem com compreensão de Π12 foram dadas por Toshiyasu Arai e Michael Rathjen em meados dos anos 90. (veja Rathjen 1995 para esses desenvolvimentos).

6. Desenvolvimentos posteriores na dedução natural

Na época em que Gentzen elaborou seu sistema de dedução natural, Stanislaw Jaskowski também estava desenvolvendo um sistema lógico para raciocinar com suposições. As fórmulas nas derivações são organizadas em uma sucessão linear, mas o artigo de Jaskowski de 1934 permaneceu fragmentado e sem resultados substanciais, como uma propriedade de subformulas. A variante linear da dedução natural é seguida em muitas exposições pedagógicas da lógica elementar (às vezes chamadas de "sistemas Fitch"). Gentzen encontrou o trabalho de Jaskowski em junho de 1936, quando ambos estavam em Münster, e considerou seu arranjo linear de fórmulas uma melhoria, uma “libertação da camisa de força da forma da árvore”, em uma que reflete “a linearidade do pensamento” (a primeira de notas não publicadas, esta última da tese de Gentzen).

O sistema de dedução natural permaneceu praticamente inativo por cerca de trinta anos, até a tese de Dag Prawitz de 1965, Dedução Natural: Um Estudo de Prova Teórica. A ordem em que Prawitz apresentou o teorema da normalização era diferente da ordem no manuscrito da tese de Gentzen. Prawitz deu primeiro um teorema da normalização e uma propriedade de subformulas para um sistema de dedução natural para a lógica clássica. Este sistema não contém disjunção ou existência. Em um segundo estágio, ele considerou a dedução natural intuicionista para a linguagem completa da lógica de predicados e reduziu sua normalização à exclusão das conversibilidades de desvio, como no fragmento da lógica clássica. Quando a prova de normalização de Gentzen veio à luz em 2005, Prawitz disse, em conversa com o presente autor, que é claro que Gentzen sabia o resultado,porque as observações na tese impressa são muito sugestivas.

No final dos anos 1960, uma forte normalização tornou-se um problema: Prawitz, usando o trabalho anterior de William Tait e Jean-Yves Girard, provou em 1971 que as não normalidades em uma derivação podem ser convertidas em qualquer ordem, com um processo de normalização final e um único derivação normal como resultado. Gentzen parece não ter percebido o último, mas parece ter pensado o contrário, pelo fracasso dessa propriedade na eliminação de cortes no cálculo sequencial.

Quase ao mesmo tempo em que uma forte normalização foi estudada, surgiu a correspondência de Curry-Howard. Curry havia observado em seu trabalho sobre lógica combinatória no final da década de 1950 a analogia entre a eliminação de implicações na dedução natural e na aplicação funcional (Curry e Feys, 1958). A idéia era tão antiga quanto a lógica intuicionista: pela "explicação BHK" dos conectivos e quantificadores (para Brouwer-Heyting-Kolmogorov), as formas de proposições na lógica intuicionista expressam prescrições sobre como provar essas proposições: uma conjunção A & B é provado provando A e B separadamente, uma disjunção A ∨ B provando um de A e B e uma implicação A ⊃ B mostrando como converter qualquer prova de A em alguma prova de B, e assim por diante. Essas explicações se aproximam muito das regras de introdução da dedução natural,mas permanece desconhecido qual foi o efeito deles no pensamento de Gentzen.

A correspondência de Curry-Howard, de um artigo de William Howard de 1969, mas publicado apenas em 1980, é baseada no princípio "fórmulas como tipos", ou em outro jargão, no princípio "proposições como conjuntos". Uma proposição é pensada como seu conjunto de provas. A verdade de uma proposição corresponde ao não vazio do conjunto. As provas de A ⊃ B agora são funções de (provas de) A a (provas de) B e A ⊃ B em si, o conjunto dessas funções. Assim, se f: A ⊃ B e a: A, a aplicação funcional fornece f (a): B. O inverso, correspondente à introdução de uma implicação, é capturado pelo princípio da abstração funcional do cálculo-λ da Igreja de Alonzo.

A correspondência de Curry-Howard tornou a dedução natural intuicionista parte do currículo da ciência da computação: fornece uma semântica computacional para a lógica intuicionista na qual cálculos e execuções de programas de maneira mais geral são efetuados através da normalização. Uma prova de uma implicação A ⊃ B, por exemplo, é um programa que converte dados do tipo A em uma saída do tipo B. A construção de um objeto (prova, função, programa) f do tipo A ⊃ B termina com uma abstração. Quando um objeto a do tipo A é inserido em f como argumento, a expressão resultante não é normal, mas possui uma forma que corresponde a uma introdução seguida de uma eliminação. A normalização agora é igual à execução do programa f. O uso da lógica intuicionista não está vinculado a nenhuma filosofia intuicionista da matemática,mas é apenas uma garantia sistemática para o término da execução de programas de computador.

7. Cálculo sequencial: desenvolvimentos / aplicações posteriores

A tese de doutorado de Gentzen marcou o nascimento da teoria da prova estrutural, em contraste com a antiga teoria axiomática da prova de Hilbert. Um passo notável à frente no desenvolvimento de sistemas de cálculo sequencial foi dado por Oiva Ketonen em sua tese de doutorado em 1944. Ketonen, um estudante de matemática e filosofia em Helsinque, foi para Göttingen em 1938 para estudar teoria da prova, sendo Gentzen o mais próximo. para um aluno que este já teve. A conexão parece ter sido estabelecida pelo professor de filosofia de Ketonen, Eino Kaila, que conheceu Gentzen em 1936 em Münster. Ketonen lembrou mais tarde que Gentzen era "um jovem simpático de poucas palavras" que lhe deu uma introdução aos sistemas e resultados teóricos da prova. Ketonen »A descoberta mais conhecida de s é um cálculo sequencial para a lógica proposicional clássica, cujas regras lógicas são todas invertíveis, o que significa que sempre que um seqüente tem uma forma que coincide com a conclusão de uma regra lógica, as premissas correspondentes, definidas exclusivamente a partir do dado sequente e a regra também são deriváveis. O inverso é imediato (basta aplicar a regra). As regras L e L, por exemplo, são modificadas em

A, B, Γ Δ EU&
A e B, Γ Δ
Γ Δ, AB, Γ Δ L⊃
A ⊃ B, Γ Δ

Existe apenas uma regra esquerda para conjunção (e duplamente apenas uma regra certa para disjunção). A regra de implicação à esquerda tem o que é chamado de “contextos compartilhados”: as suposições e casos na conclusão, exceto a fórmula com o conectivo, são repetidos de forma idêntica nas duas premissas. A idéia de Ketonen era definir um sistema de busca por prova: começa-se a partir de um determinado seqüente a ser derivado, escolhe uma fórmula nele e escreve as premissas de uma regra que pode concluir o seqüente dado. Por invertibilidade, a questão da derivabilidade é substituída por uma ou duas questões equivalentes de derivabilidade em sequências mais simples. As novas regras são necessárias para garantir premissas definidas de maneira única nessa decomposição "raiz primeiro".

A prova de Ketonen da invertibilidade das regras lógicas de seu cálculo seqüencial usou a regra estrutural do corte. Mais tarde, Kurt Schütte (1950) e Haskell Curry (1963) deram provas diretas de invertibilidade, esta última com o resultado explícito de que as inversões preservam a altura: se um determinado sequência é derivável em no máximo n etapas, as premissas de uma regra que podem concluímos que o sequente também tem uma derivação em no máximo n etapas.

Quanto do trabalho de Ketonen decorre de sugestões por parte de Gentzen permanece desconhecido, porque nenhuma correspondência foi encontrada. Ketonen escreve no prefácio de sua tese que “Dr. G. Gentzen de Göttingen me direcionou para a área problemática deste trabalho”. A tese foi o único trabalho original de Ketonen em lógica, salvo do esquecimento por uma longa resenha que Bernays escreveu para o Journal of Symbolic Logic em 1945.

Uma pessoa que conhecia o cálculo de Ketonen no final da década de 1940 era Evert Beth. Quando Beth, mais tarde, em 1955, apresentou seu conhecido cálculo de tableau, ele parecia ter esquecido a origem do cálculo de tableau como uma reformulação da de Ketonen, mas, em vez disso, refere-se à influente Introdução à Metamatemática de Kleine, de 1952. Kleene havia tomado o cálculo de Ketonen da revisão de Bernays e também tratou o cálculo seqüencial intuicionista, no qual a invertibilidade é mais restrita do que no cálculo clássico. Com o livro de Kleene, os cálculos subsequentes de Gentzen tornaram-se geralmente conhecidos e acessíveis.

O trabalho de Kleene no início dos anos 50 também foi pioneiro em um desenvolvimento notável no cálculo sequencial, a saber, o cálculo clássico e intuicionista "livre de contração" hoje denotado por G3c e G3i. Esses cálculos têm a propriedade de que nenhuma das “regras estruturais” originais de Gentzen é necessária. A regra de "enfraquecer" permite a adição de casos e suposições supérfluas, e a regra de "contração" a exclusão de uma cópia de uma fórmula se duas estiverem presentes em uma lista, como em

Enfraquecimento Contração
Γ Δ Sem
A, Γ Δ
A, A, Γ Δ Ctr
A, Γ Δ

Regras análogas permitem enfraquecimento e contração nas partes certas e sucessivas dos seqüentes. O enfraquecimento é tornado uma regra eliminável, permitindo que as sequências iniciais tenham a forma A, Γ Δ, A em vez de A → A de Gentzen. A contração é igualmente eliminada por uma formulação adequada das regras. A importação é que, na pesquisa de prova de primeira raiz, não é necessário aplicar regras que produzam uma duplicação de uma fórmula em uma premissa. Sem esse resultado, não haveria o término da pesquisa de prova.

O cálculo clássico tem a propriedade, mencionada acima, de inverter a preservação de altura de suas regras lógicas. Albert Dragalin refinou, no final da década de 1970, o cálculo para aquele em que as regras estruturais são, além disso, "admissíveis para a preservação da altura", o que significa que sempre que a premissa de tal regra é derivável, a conclusão é derivável sem a regra e com, no máximo, a mesma tamanho (número máximo de instâncias de regra em uma ramificação de derivação) da derivação. Essa propriedade tem efeitos profundos na eliminação do corte: ao permutar o corte, Gentzen teve que restaurar os contextos originais (Γ's e Δ's) por meio de enfraquecimentos e contrações. Com a admissibilidade que preserva a altura dessas regras, o tamanho de uma derivação não aumenta quando as regras são aplicadas. Dragalin também deu um cálculo intuicionista multissucentado com o mesmo tipo de admissibilidade das regras estruturais. Troelstra, finalmente, deu no livro Basic Proof Theory (2000, primeira ed. 1996) um cálculo intuicionista de um único sucesso, com admissibilidade de enfraquecimento e contração com preservação da altura. Os cálculos sequenciais livres de contração são ferramentas poderosas para a análise de derivações formais. Muitos resultados difíceis de pesquisa em lógica tornam-se apenas exercícios através do controle sobre a estrutura de provas permitidas pelo cálculo do G3. Os cálculos sequenciais livres de contração são ferramentas poderosas para a análise de derivações formais. Muitos resultados difíceis de pesquisa em lógica tornam-se apenas exercícios através do controle sobre a estrutura de provas permitidas pelo cálculo do G3. Os cálculos sequenciais livres de contração são ferramentas poderosas para a análise de derivações formais. Muitos resultados difíceis de pesquisa em lógica tornam-se apenas exercícios através do controle sobre a estrutura de provas permitidas pelo cálculo do G3.

A primeira aplicação do cálculo sequencial na matemática foi na teoria da prova da aritmética, na tese de Gentzen e de maneira decisiva na prova de 1938 da consistência da aritmética. Troelstra menciona o trabalho de Ketonen como

uma análise inicial de provas sem cortes nos cálculos de Gentzen com axiomas; mas ele considera a forma de derivações sem cortes no cálculo puro, onde axiomas estão presentes no antecedente das sequências derivadas. (Troelstra e Schwichtenberg 2000: 142)

Os axiomas que Ketonen considera são os da geometria projetiva e afim, o primeiro retirado do artigo de Skolem, de 1920, discutido na primeira seção acima. Ketonen queria formular as regras formais de prova de Skolem dentro de um cálculo subsequente. No entanto, o trabalho de Ketonen era conhecido principalmente apenas por meio da revisão de Bernays e apenas a parte lógica do cálculo sequencial foi explicada em detalhes ali.

Uma segunda maneira de aplicar o cálculo de sequência é permitir que as sequências que iniciam ramificações de derivação tenham, além das sequências iniciais, também a forma A, na qual A é um axioma ou uma instância de um axioma universal. Agora, pelo “Hauptsatz estendido” de Gentzen, os cortes nas derivações podem ser permutados até que uma de suas premissas seja um axioma, mas esses cortes nos axiomas permanecem. Outro método mais novo é converter axiomas em regras extras que são adicionadas às regras lógicas do cálculo sequencial, mantendo-se a eliminação total (como explicado em Negri e von Plato 2001, capítulo 6, e em Troelstra e Schwichtenberg, 2000, capítulo 4.7).

8. Os objetivos da teoria da prova

Até que ponto a teoria da prova alcançou seus objetivos originais? Para Hilbert, os objetivos eram um esclarecimento completo dos problemas fundamentais por meio de provas finitárias de consistência, etc., objetivos nos quais a teoria da prova falhou. Hilbert em seu programa não estava interessado no estudo de provas matemáticas em si, mas apenas em resolver os problemas fundamentais da fundação (e depois esquecê-los). Uma nota recentemente encontrada por Hilbert dá uma imagem diferente: a nota afirma que Hilbert queria adicionar como 24º e último problema em sua famosa lista parisiense de problemas matemáticos abertos de 1900 o desenvolvimento de “uma teoria dos métodos de prova em matemática”. Isso foi antes de seu programa metamatemático para o desenvolvimento de uma teoria da prova emergir.

Para Gentzen, os objetivos eram, juntamente com os de Hilbert, compreender a estrutura das provas matemáticas. Este programa foi um sucesso completo no que diz respeito à lógica e aritmética pura. Os métodos de cálculo sequencial, especialmente, permitem a análise de provas com resultados profundos. O grande objetivo da teoria da prova, uma prova da consistência da análise como no segundo problema de Hilbert em Paris, não foi realizado, mas também não é excluído.

Alguma compreensão da noção de prova é necessária para qualquer matemático, se nada mais, pelo menos para a comunicabilidade dos resultados matemáticos: a publicação baseia-se no entendimento de que as provas podem ser feitas tão explícitas que sejam rotineiramente verificáveis quanto à correção. No entanto, a teoria da prova até agora não se tornou uma ferramenta prática para o matemático que trabalha; as aplicações em matemática foram casos bastante isolados. Trabalhos recentes sobre a formalização de provas matemáticas com sistemas computadorizados, chamados editores de provas, podem mudar gradualmente esse quadro.

A teoria da prova criou novos objetivos fora da matemática tradicional, especialmente em conexão com a ciência da computação. Tópicos como a verificação da correção de programas de computador são uma conseqüência da teoria da prova. A dedução natural levou à correspondência de Curry-Howard e a conexões com a programação funcional, e o cálculo sequencial é frequentemente usado em sistemas de busca automática de provas, como na programação lógica.

Bibliografia

Textos sobre Teoria da Prova

  • Buss, Sam (ed.), 1998, Handbook of Proof Theory, Amsterdã: Elsevier.
  • Negri, S. e J. von Plato, 2001, Structural Proof Theory, Cambridge: Cambridge University Press.
  • von Platão, J., 2013, Elements of Logical Reasoning, Cambridge: Cambridge University Press.
  • Takeuti, G., 1987, Proof Theory, Amsterdã: Holanda do Norte, 2ª edição.
  • Troelstra, A. e H. Schwichtenberg, 2000, Basic Proof Theory, Cambridge: Cambridge University Press, 2ª edição.

Obras originais e suas reimpressões

  • Ackermann, W. 1940, "Zur Widerspruchsfreiheit der Zahlentheorie", Mathematische Annalen, 117: 162–194.
  • Beth, E., 1955, vinculação semântica e derivabilidade formal (Mededelingen der Koninklijke Nederlandse Akademie van Wetenschappen. Afd. Letterkunde. Nieuwe reeks, deel 18, n. 13), Amsterdã: Holanda do Norte.
  • Church, A., 1936, “Uma nota sobre o problema de Entscheidung”, Journal of Symbolic Logic, 1: 40–41.
  • Curry, H. e Feys, R., 1958. Combinatory Logic. (Estudos em Lógica e os Fundamentos da Matemática, Vol. I), 1ª edição, Amsterdã: Holanda do Norte.
  • Curry, H., 1963, Fundamentos da Matemática Lógica, Nova York: McGraw-Hill; reimpresso Nova York: Dover, 1977.
  • Dragalin, A., 1988, Intuicionismo Matemático: Introdução à Teoria da Prova, Providence, RI: American Mathematical Society.
  • Gentzen, G., 1934–1935, Untersuchungen über das logische Schliessen (Investigações em inferência lógica), Ph. D. tese, Universität Göttingen. Publicado em Gentzen 1969: 68–131.
  • Gentzen, G., 1938, "Neue Fassung des Widerspruchsfreiheitsbewisises for die reine Zahlentheorie", Pesquisa da Logik e da Grundlegung der exakten Wissenschaften, Neue Folge 4, S. Hrizel, 19-44. Traduzido em Gentzen 1969: 252–286.
  • Gentzen, G., 1943, “Beweisbarkeit und Unewewbarbarit von Anfangsfällen der transfiniten Induktion in der reinen Zahlentheorie”, Mathematische Annalen, 119: 252–286. Traduzido em Gentzen 1969: 287-308.
  • Gentzen, G., 1969, The Collected Papers of Gerhard Gentzen, ed. M. Szabo, Amsterdã: Holanda do Norte.
  • Gentzen, G., 2008, “A normalização de derivações”, The Bulletin of Symbolic Logic, 14 (1): 245–257.
  • Gödel, K., 1930, “Die Vollständigkeit der Axioma 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 (Volumes 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” (“Sobre o infinito”), Mathematische Annalen, 95: 161–190. [Palestra proferida em Münster, em 4 de junho de 1925.]
  • Hilbert, D. e Ackermann, W., 1928, Grundzüge der theoryetischen Logik, Berlim: Springer.
  • Hilbert, D., 1931, “Die Grundlegung der elementaren Zahlenlehre”, Mathematische Annalen, 104: 484-494.
  • Howard, W., 1980 [1969], “A noção de construção de fórmulas como tipos”, em J. Seldin e J. Hindley (eds.), Para HB Curry: Essays on Combinatory Logic, Lambda Calculus and Formalism, London, Nova York: Academic Press, pp. 480-490.
  • Jaskowski, S., 1934, “Sobre as regras da suposição na lógica formal”, em 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), Helsinque.
  • Kleene, S., 1952, Introdução à Metamatemática, Amsterdã: Holanda do Norte.
  • Kreisel, G., 1951, “Sobre a interpretação de provas não-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, Berlin: Birkhäuser Verlag.
  • Menzler-Trott, E., 2007, Gênio Perdido da Logic: A Vida e Obra de Gerhard Gentzen, Providence, RI: Sociedade Americana de Matemática.
  • Prawitz, D., 1965, Dedução Natural: Um Estudo de Prova Teórica, Estocolmo: Almqvist & Wiksell; reimpressão New York: Dover (com um novo prefácio), 2006.
  • –––, 1971, “Idéias e resultados na teoria da prova”, em J. Fenstad (ed.), Anais do Segundo Simpósio Escandinavo de Lógica, Amsterdã: Holanda do Norte, pp. 235–308.
  • Rathjen, M., 1995, “Avanços recentes na análise ordinal; Π 1 2 -CA e sistemas relacionados”O Boletim de Lógica simbólica, 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 mathematischer Sätze, nebst einem Theoreme über dichte Mengen”, traduzido e reimpresso em Selected Works in Logic, JE Fenstadet (ed., 1970). 103–136:
  • Whitehead, AN e B. Russell, 1910–1913, Principia Mathematica, Cambridge: Cambridge University Press.

Literatura secundária

  • Bernays, P., 1945, “Review: Oiva Ketonen, Untersuchungen zum Pradikatenkalkul”, The Journal of Symbolic Logic, 10 (4): 127-130.
  • –––, 1965, “Betrachtungen zum Sequenzen-kalkul”, em Contribuições para Lógica e Metodologia em Honra de JM Bochenski, Amsterdã: Holanda do Norte, pp. 1–44.
  • –––, 1979, “Na prova de consistência original de Gentzen para a teoria dos números”, em J. Myhill et al. (eds.), Intuicionismo e Teoria da Prova, Amsterdã: Holanda do Norte, pp. 409–417.
  • Feferman, S., 2000, "Destaques na teoria da prova", em V. Hendricks et al. (eds.) 2000, pp. 11–31.
  • Hempel, C., 2000, "Uma autobiografia intelectual". In Science, Explicação e Racionalidade, ed. J. Fetzer, pp. 3-35.
  • Hendricks, V. et ai. (eds.), 2000, Teoria da Prova: História e Importância Filosófica, Dordrecht: Kluwer.
  • Mancosu, P., 1999, “Entre Berlim e Viena: a recepção imediata dos teoremas da incompletude de Gödel”, History and Philosophy of Logic, 20: 33–45.
  • von Plato, J., 2007, “Nas sombras do teorema de Löwenheim-Skolem: análises combinatórias iniciais de provas matemáticas”, The Bulletin of Symbolic Logic, 13 (2): 189-225.
  • –––, 2007, “Do programa de Hilbert ao programa de Gentzen”, no Apêndice Menzler-Trott 2007.
  • –––, 2009, “A lógica de Gentzen”, no Manual de História e Filosofia da Lógica (Volume 5), Amsterdã: Elsevier.
  • –––, 2012, “Sistemas de prova de Gentzen: subprodutos em um programa de gênio”, The Bulletin of Symbolic Logic, 18 (3): 313–367.
  • Smorynski, C., 2007, “Programa de Hilbert”, no Apêndice, Menzler-Trott 2007.
  • Tait, W., 2005, “A reformulação de Gödel da primeira prova de consistência de Gentzen para aritmética: a interpretação sem contra-exemplo”, The Bulletin of Symbolic Logic, 11 (2): 225–238.
  • Troelstra, A. e Schwichtenberg, H., 2000, Basic Proof Theory, Cambridge: Cambridge University Press, 2ª edição.

Ferramentas Acadêmicas

ícone de homem de sep
ícone de homem de sep
Como citar esta entrada.
ícone de homem de sep
ícone de homem de sep
Visualize a versão em PDF desta entrada nos Amigos da Sociedade SEP.
ícone inpho
ícone inpho
Consulte este tópico de entrada no Internet Philosophy Ontology Project (InPhO).
ícone de papéis phil
ícone de papéis phil
Bibliografia aprimorada para esta entrada na PhilPapers, com links para o banco de dados.

Outros recursos da Internet

[Entre em contato com o autor com sugestões.]

Recomendado: