Intuitionistically, son estos no equivalentes? $P \rightarrow Q,\; \neg Q \rightarrow \neg P,\; P \wedge \neg Q \rightarrow \bot,\; \neg P \vee Q$

Question

A veces nos hacen preguntas como esta que, básicamente, se pregunte:

Bueno, sé que hay al menos tres formas diferentes de la prueba de una implicación, a saber:

• prueba directa
• prueba por contraposición
• la prueba por contradicción

Pero en realidad, ¿qué es la diferencia entre ellos?

Como yo lo veo, hay al menos dos maneras de responder a esta pregunta. Es una manera de nombrar a su favorito de la prueba de cálculo para la lógica clásica y explicar cómo se manejan estos diferentes a prueba de estrategias de manera diferente. De otra manera se podría argumentar que:

• prueba directa demuestra $P \rightarrow Q$
• prueba por contraposición, resulta $\neg Q \rightarrow \neg P$
• la prueba por contradicción demuestra $P \wedge \neg Q \rightarrow \bot$
• hay otra en la cual usted se prueban $\neg P \vee Q$

y que cuatro de estas fórmulas se intuitionistically no equivalentes. En realidad, es esto cierto? Por desgracia, yo no sé nada acerca de intuitionistic lógica. Así que me pregunto:

Pregunta. Intuitionistically, son cada una de las siguientes fórmulas no equivalentes? $$P \rightarrow Q,\; \neg Q \rightarrow \neg P,\; P \wedge \neg Q \rightarrow \bot,\; \neg P \vee Q$$

Answer 1

En intuitionistic lógica:

1. $$p \rightarrow q \vdash \neg(p \land \neg q)$$
2. $$ \neg(p \land \neg q) \nvdash p \rightarrow q$$
3. $$ \neg p \lor q \vdash p \rightarrow q$$
4. $$p \rightarrow q \nvdash \neg p \lor q$$
5. $$p \rightarrow q \vdash \neg q \rightarrow \neg p$$
6. $$ \neg q \rightarrow \neg p \nvdash p \rightarrow q$$
7. $$p \rightarrow q \vdash (p \land \neg q) \rightarrow \bot$$

Prueba-teóricamente hablando, la razón por la que (2), (4) y (6) no intuitionistically es porque usted necesita el doble negación eliminación para completar la prueba. Ya en intuitionistic lógica de esta regla se cae, no hay ningún medio para probar los clásicos de vinculaciones. En contraste, las pruebas de los restantes (1), (3) y (5) ir como de costumbre.

Hay una lista de otras propiedades interesantes de esta lógica en Van Dalen Lógica y Estructura, pág.156.

Este documento y la Enciclopedia de Filosofía de Stanford entrada también puede ser interesante.