Aula 27/04 - Prova de Henkin

Olá para todos. 

Veremos na aula de amanhã, 27/04, os teoremas 32.2 até 32.10 da prova de Henkin (Hunter seção 32).

Abaixo, uma apostila com o passo a passo das provas e alguns comentários,

http://dl.dropbox.com/u/5959592/henkin_prop_1.pdf

Abraços

Prova de Henkin - lógica sentencial

Olá para todos.

Para fechar a prova da completude de Kalmar que vimos nas últimas aulas, tentem explicar em detalhe por que lemos no Hunter, no fim da p. 104, que qualquer sistema de lógica sentencial que tenha os teoremas 1 a 7 da p. 105 é completo.

Para a aula do dia 20/4, leiam o início da seção 32 do Hunter, sobre a prova da completude de Henkin (pp. 105-109). Hunter apresenta nas subseções (a), (b), (c) e (d) resultados preliminares que serão usados na prova da completude de Henkin.

Na seção (a) estão provas dos teoremas 1-7, listados nas pp. 105 e 106. Tentem prová-los usando um sistema de dedução natural que vocês estejam familiarizados e, depois, no sistema axiomático PS apresentado no Hunter. Lembrem-se de usar o teorema da dedução. Para provar o teorema 6 da p. 106 lancem A como hipótese para chegar a B e ØB. Usem ØB ® (B ® (Ø(A ® A))) para obter, com TD, A ®  Ø(A ® A). Agora usem dupla negação e o axioma 3. Notem que o teorema 6 simula em PS a regra de introdução da negação, ou redução ao absurdo.

Depois, leiam com atenção as seções (b) e (c). Deixem de lado por enquanto a seção (d).

Lembrem-se que em 25/4 não haverá aula. Aproveitem o dia livre para estudar as seções (b) e (c). Dia 27/4, quarta, faremos uma revisão dessas seções e começaremos a seção (d).

Abraços

Teorema da correção

Olá para todos.
Nas aulas dos dias 11 e 13 veremos, conforme combinado, as seções 24, 25 e 28 do Hunter.

Abaixo, uma apostila com o passo a passo da prova do teorema da correção, Hunter 28.4

http://dl.dropbox.com/u/5959592/correcao_hunter28.4.pdf

Se houver tempo, vamos começar no dia 13 a prova de Kalmar do teorema da completude. Leiam as seções 29 e 31 do Hunter, com atenção para o Lema 31.14. Há uma prova desse lema em Robbin p. 23, cujo passo a passo está em 

http://sites.google.com/site/textoslogica/arquivos/lema_6.2.pdf  

Compacidade

Na última aula, vimos a versão sintática do teorema da compacidade. A versão semântica vai depender do teorema da completude, que não provamos ainda.

No link http://dl.dropbox.com/u/5959592/read_compacidade.pdf há trechos do livro do Stephen Read, Thinking about Logic (OUP), que tratam do teorema da compacidade. Há problemas filosóficos muito interessantes relacionados à compacidade da lógica clássica de primeira ordem. O texto do Read é uma introdução acessível a tais problemas.

Dicas: Na Enciclopédia de termos lógico-filosóficos (ed. Murcho et al.): teoria dos modelos, teorema da compacidade e também outros mencionados nos verbetes acima.

Na Wikipedia : http://en.wikipedia.org/wiki/Non-standard_model_of_arithmetic

http://pt.wikipedia.org/wiki/Completude_%28l%C3%B3gica%29

http://pt.wikipedia.org/wiki/Teorema_da_compacidade

http://pt.wikipedia.org/wiki/Teorema_da_completude_de_G%C3%B6del

Para quem quiser se aventurar nos modelos não-standard da aritmética, ver também o capítulo do livro do Boolos & Jeffrey, Computability and Logic, no link http://dl.dropbox.com/u/5959592/non_std_arit.pdf

Após a leitura do texto, tente responder às seguintes perguntas: O que diz o teorema da compacidade em sua versão sintática e, dada a completude, em sua versão semântica? O que é a regra-w? Por que a regra-w não pode ser usada na teoria da prova clássica? Por que não podemos expressar, na lógica de primeira ordem, a sentença 'não existe um número que seja diferente de 0 e 1 e 2 e…'? 

Algumas reflexões sobre o chamado ‘princípio de composicionalidade’

Extraído do capítulo 5 de Thinking about Logic de Stephen Read, OUP

 

Como a linguagem é possível? Como é possível, a partir da aprendizagem de um vocabulário básico e finito de uma linguagem, formar um sem número de novos enunciados, novas proposições que expressam pensamentos que nunca foram antes formulados? Pois isso é possível. Apesar do vocabulário de uma linguagem ser mundo grande, como uma olhada no dicionário revela, ele é pequeno quando comparado com o número imenso de sentenças que compõem os livros das bibliotecas espalhadas pelo mundo. Dentre essas sentenças, poucas são idênticas. Dentre as sentenças que lemos, poucas são as que nós vimos antes. Como é possível que o leitor compreenda essas sentenças? Como é possível que o leitor as conceba e formule?

A resposta é óbvia, mas suas implicações são poderosas. Nós podemos aprender uma linguagem porque seu vocabulário e suas regras gramaticais são relativamente pequenas – ambas podem ser reunidas em um pequeno número de volumes. Um dicionário de alguns volumes como o Oxford English Dictionary contém pouco mais que o vocabulário da maior parte dos falantes individuais do inglês. E mesmo esse dicionário consiste de dez ou doze volumes, o que é uma pequena parte da biblioteca onde ele está. A partir desse vocabulário, as regras gramaticais permitem a criação de um número infinitamente grande de sentenças. Para que possamos entender tais sentenças, os significados das palavras individuais são combinados de acordo com a estrutura estabelecida pela gramática. Em outras palavras, da mesma forma que uma sentença é literalmente composta pelas palavras que ela contém, o significado de uma sentença, a proposição, é de alguma maneira 'composto' pelos significados das palavras que ela contém. A idéia inicial é óbvia: entendemos novas sentenças porque entendemos como seus significados resultam dos significados das palavras que as constituem. As implicações disso não são óbvias, e o que isso diz não é tão claro: os significados das palavras se combinam de algum modo para compor o significado da sentença completa, a proposição por ela expressada.

O princípio em questão aqui é por vezes chamado de 'princípio da composicionalidade', outras vezes de 'princípio de Frege', o grande filósofo alemão da matemática e da linguagem do fim do século XIX. Os dois termos cobrem aplicações bastante diferentes da idéia básica. Mas a motivação subjacente é a mesma. De algum modo precisamos explicar a 'criatividade' da linguagem, o modo pelo qual uma criança, ao ouvir um número finito e pequeno de enunciados, desenvolve a habilidade de produzir e compreender um sem número de proposições que não estão entre os dados sobre os quais tal habilidade foi desenvolvida. A explicação é a mais simples e a mais plausível para preencher essa lacuna, e está de acordo com a experiência pessoal, do falante de uma linguagem, de participar de uma conversa – um conjunto de enunciados seus e de outros falantes. Os dados iniciais e os novos enunciados produzidos são analisados em componentes significativos, e é postulada uma conexão entre o todo e as partes. Mas o que é essa conexão?

Aqueles que chamam essa idéia de princípio de 'composicionalidade' estarão inclinados a interpretar essa conexão de modo bastante literal. Eu mencionei no capítulo 1 como Russell considerou que as proposições – significados das sentenças e objetos de crença – teriam como constituintes particulares e universais. Assim, por exemplo, a proposição que Sócrates é sábio teria, literalmente, Sócrates e a sabedoria como constituintes. Para Russell, o significado de 'Sócrates' era o próprio filósofo Sócrates, em pessoa; e o significado de 'é sábio' era o universal ou a propriedade sabedoria. Portanto, o significado da sentença 'Sócrates é sábio' seria composto por Sócrates e a sabedoria, do mesmo modo que a sentença é composta por sujeito e predicado. Uma visão mais sofisticada, diferentemente, aponta para uma dependência funcional do significado da expressão complexa em relação aos significados das suas partes. Considere uma analogia: 4 é o resultado do quadrado de dois, 4 = 2², mas 4 não contém literalmente o número 2 como um constituinte, tampouco contém a função y = x², que recebe um número x e o eleva ao quadrado produzindo um número y. Antes, 4 é o resultado de aplicar ao número 2 a função que eleva um número ao quadrado. Para Frege, é desse modo que se estabelece a conexão entre o significado de uma sentença e os significados das suas partes. O quadro é mais complicado porque Frege distinguia o significado da expressão dos seus componentes. Mas o princípio é preservado: o significado de uma expressão complexa, uma sentença por exemplo, resulta dos significados das suas partes e pode ser calculado a partir deles. Assim, a compreensão das partes e do modo elo qual o todo depende das partes explica a compreensão do todo.

* * * 

Material disponível e aulas dos dias 4 e 6 de abril

Olá para todos.

Nas próximas aulas, 4 e 6 de abril veremos:

1. O sistema axiomático de P de lógica sentencial (Hunter seções 22 e 23)

2. O teorema da dedução para P (Hunter seção 26).

As seções do Hunter você encontra em 

http://dl.dropbox.com/u/5959592/books/Metalogic_Hunter.pdf

E uma apostila sobre o t. da dedução está em 

http://dl.dropbox.com/u/5959592/teorema_da_deducao.pdf

Abraços