Técnicas para mostrar la no derivabilidad en lógicas y otros sistemas de pruebas formales.

En los sistemas de prueba para la lógica proposicional clásica, si se quiere mostrar que una determinada fórmula no es derivable, simplemente se muestra que se puede derivar (aunque ciertamente son posibles otras técnicas). La no derivabilidad se deriva esencialmente de la solidez y la integridad del sistema de prueba. $\psi$ $\neg\psi$

Desafortunadamente para las lógicas no clásicas y los sistemas de prueba más exóticos (como las reglas subyacentes a la semántica operativa) no existe tal técnica directa. Esto podría deberse a que la no derivabilidad de no implica que sea derivable, como es el caso de las lógicas intuicionistas, o simplemente que no existe una noción de negación. $\psi$ $\neg\psi$

Mi pregunta tiene un sistema de prueba , donde , (y presumiblemente su semántica), qué técnicas existen para mostrar la no derivabilidad? $(\mathcal{L},\vdash)$ $\vdash\;\subseteq\mathcal{L}^*\times\mathcal{L}$

Los sistemas de prueba de interés podrían incluir semántica operativa de lenguajes de programación, lógicas Hoare, sistemas de tipos, una lógica no clásica o reglas de inferencia para lo que usted tiene.

lo.logic Dave Clarke
fuente

Dave, creo que hay un error tipográfico en la pregunta, para mostrar que no es derivable, no mostramos que es derivable, solo mostramos que es consistente, y esto solo se basa en la consistencia de la clásica. lógica. Si la lógica es la lógica clásica de primer orden, entonces hay oraciones que no podemos probar ni refutar (a menos que estemos hablando de una teoría completa ). ¿O estoy leyendo mal tu pregunta?

φ

$\varphi$

\neg φ

$\lnot \varphi$

Kaveh

Lo cambié a la lógica proposicional clásica. La pregunta requiere cualquier técnica además de probar la negación, ya que muchos sistemas formales (colecciones de axiomas y reglas de inferencia) no tienen negación, o de hecho pueden no parecer "lógicos".

Dave Clarke

Gracias por la aclaración, mi mente va a la lógica de primer orden por defecto cuando leo la lógica clásica. :)

Kaveh

Respuestas:

IME, la siguiente lista es la más fácil a la más difícil (por supuesto, también es la menos poderosa):

Si su sistema es sólido y puede probar , entonces tiene un resultado de no rentabilidad, por supuesto. $\lnot \phi$
Si tiene una semántica teórica de celosía para su lógica, en relación con la cual todas sus reglas de prueba son válidas, entonces si el significado de una proposición no es el elemento superior de la red, entonces no es una proposición derivable.
Si sabe que su lógica está completa con respecto a una clase de modelos, verifique si hay un modelo en particular en esa clase que invalide . $\phi$
A veces puede salirse con la suya a una traducción a otra lógica y mostrar que la derivabilidad aquí implica un resultado de no derivabilidad conocido allá.
Si tiene una deducción natural o un cálculo posterior, verifique si se conoce un resultado de eliminación de corte o si puede probarlo. Si lo hay, entonces a menudo puede explotar la propiedad subformula para dar argumentos inductivos simples sobre la no capacidad de derivación. (Por ejemplo, la consistencia a través de la eliminación de cortes es solo la afirmación de que no hay pruebas de falsos sin cortes, por lo que si todos los cortes se pueden eliminar, entonces no hay inconsistencias).
Si nada más funciona, a menudo puede mostrar resultados de consistencia / no capacidad de derivación a través de un argumento de relaciones lógicas. Esta es la gran pistola, que funciona cuando nada más lo hace: en términos de teoría de conjuntos, se reduce al uso del axioma de Reemplazo, que le permite mostrar que los conjuntos enormes están bien ordenados. (Es por eso que puede usarlo para probar cosas como la normalización del Sistema F.)

Neel Krishnaswami
fuente

F

$F$

P A^{2}

$PA^2$

F^{2}

$F^2$

Gracias, ahora veo lo que quisiste decir con "cosas como la normalización del Sistema F". :)

Kaveh

@Kaveh, @Neel: La fuerte normalización del sistema F no es un teorema de PA2, sino que es equivalente sobre PA a la consistencia de PA2. Por el contrario, la normalización fuerte para todos los términos de rango n (el rango es la medida de la profundidad máxima de los cuantificadores de tipo nsted) puede probarse usando ACA- n . Me gusta hablar de construir modelos de gavillas en secreto ...

Charles Stewart el

@Charles: Aprendí sobre esta idea de algunos documentos de Jean Gallier, que sorprendentemente se subestiman. Algo perversamente, esta visión elegante me ayudó a entender la cuenta más simple de Mitchell y Scedrov.

Neel Krishnaswami el