Técnicas para mostrar não derivabilidade em lógicas e outros sistemas formais de prova

Em sistemas de prova para lógica proposicional clássica se quero mostrar que uma determinada fórmula não é um derivável simplesmente mostra que pode ser derivada (embora outras técnicas certamente são possíveis). A não derivabilidade decorre essencialmente da solidez e integridade do sistema de prova. $\psi$ $\neg\psi$

Infelizmente, para lógicas não clássicas e sistemas de prova mais exóticos (como as regras subjacentes à semântica operacional), essa técnica direta não existe. Isso pode ser porque o não-derivabilidade de não implica que é derivável, como é o caso com lógicas intuitionistic, ou simplesmente que nenhuma noção de negação existe. $\psi$ $\neg\psi$

Minha pergunta recebe um sistema de prova , onde $(\mathcal{L},\vdash)$ (e presumivelmente sua semântica), que técnicas existem para mostrar a não derivabilidade? $\vdash\;\subseteq\mathcal{L}^*\times\mathcal{L}$

Os sistemas de prova de interesse podem incluir semântica operacional de linguagens de programação, lógicas Hoare, sistemas de tipos, uma lógica não clássica ou regras de inferência para o que você tem.

lo.logic Dave Clarke
fonte

Dave, acho que há um erro de digitação na pergunta, para mostrar que

não é derivável, não mostramos que

é derivável, apenas mostramos que é consistente, e isso é baseado apenas na consistência da lógica clássica. Se a lógica é lógica clássica de primeira ordem, há sentenças que não podemos provar nem refutar (a menos que estejamos falando de uma teoria completa ). Ou estou interpretando mal sua pergunta?

φ

$\varphi$

\neg φ

$\lnot \varphi$

Kaveh

Eu mudei para a lógica proposicional clássica. A questão pede qualquer técnica além de provar a negação, pois muitos sistemas formais (coleções de axiomas e regras de inferência) não têm negação ou, de fato, podem nem parecer "lógica".

Dave Clarke

Obrigado pelo esclarecimento, minha mente vai para a lógica de primeira ordem por padrão quando leio a lógica clássica. :)

Kaveh

Respostas:

IME, a lista a seguir é mais fácil ou mais difícil (é claro, também é do menos ao mais poderoso):

Se o seu sistema é som, e você pode provar , então você tem um resultado nonderivability, é claro. $\lnot \phi$
Se você tiver uma semântica teórica da rede para sua lógica, em relação à qual todas as suas regras de prova são válidas, se o significado de uma proposição não for o elemento principal da rede, não será uma proposição derivável.
Se você sabe que sua lógica está completa com relação a uma classe de modelos, verifique se há um modelo específico nessa classe que invalide . $\phi$
Às vezes, você pode se dar bem com uma tradução para outra lógica e mostrar que a derivabilidade por aqui implica um resultado conhecido de não derivabilidade por lá.
Se você tiver uma dedução natural ou cálculo sequencial, verifique se há um resultado de eliminação de corte conhecido ou se é possível provar um. Se houver, você poderá frequentemente explorar a propriedade subformula para fornecer argumentos indutivos simples sobre não-derivabilidade. (Por exemplo, consistência via eliminação de corte é apenas a afirmação de que não há provas de falso sem corte e, portanto, se todos os cortes puderem ser eliminados, não haverá inconsistências.)
Se nada mais funcionar, muitas vezes você poderá mostrar resultados de consistência / não subjetividade por meio de um argumento de relações lógicas. Essa é a grande arma, que funciona quando nada mais funciona - em termos da teoria dos conjuntos, tudo se resume ao uso do axioma da Substituição, que permite mostrar que conjuntos enormes são bem ordenados. (É por isso que você pode usá-lo para provar coisas como normalização do sistema F.)

Neel Krishnaswami
fonte

F

$F$

P A^{2}

$PA^2$

F^{2}

$F^2$

Obrigado, agora vejo o que você quis dizer com "coisas como normalização do sistema F". :)

Kaveh

@ Kaveh, @ Neel: A forte normalização do sistema F não é um teorema do PA2; em vez disso, é equivalente ao PA à consistência do PA2. Em vez disso, uma forte normalização para todos os termos da classificação n (a classificação é a medida da profundidade máxima dos quantificadores do tipo nsted) pode ser comprovada usando o ACA- n . Gosto de falar da construção de modelos de sheaf em segredo ...

Charles Stewart

@ Charles: Eu aprendi sobre essa idéia com alguns artigos de Jean Gallier, que são surpreendentemente sub-citados. Um tanto perversamente, essa visão sofisticada me ajudou a entender o relato mais simples da Mitchell & Scedrov.

Neel Krishnaswami