Derivar $P \to \neg \neg P$ en una estructura con no e implica

Question

Podemos definir un sistema abstracto con los siguientes tres esquemas de axiomas que definen $\to$ y $\lnot$ de la siguiente manera:

ax1. $P\to(Q\to P)$

ax2. $(\lnot Q \to \lnot P)\to(P\to Q)$

ax3. $(P\to(Q\to R))\to((P\to Q)\to(P\to R))$

Y cualquier expresión lógica puede ser sustituida por $P, Q, R$ . Ahora, obviamente, no se puede asumir nada más (ni siquiera ninguna definición de $\lnot$ etc.) estos dos objetos $\to$ y $\lnot$ no tienen por qué tener nada que ver con la implicación y la negación estándar que conocemos, simplemente satisfacen las propiedades anteriores. Pero con lo anterior, podemos demostrar "leyes lógicas" básicas como:

$$P\to P$$

(que podemos demostrar aplicando ax3 sobre ax1, mostrando que $(P\to Q)\to(P\to P)$ por lo que sólo tenemos que construir un $Q$ para cualquier $P$ implicar, y tal $Q$ es proporcionada por ax1, $Q:= (R\to P)$ .)

¿Es posible demostrarlo? :--

$$P\to \lnot\lnot P$$

La persona que me dio este problema insiste en que es demostrable, aunque me parece que tal demostración es imposible, ya que ninguno de los axiomas aumenta la profundidad de $\lnot$ s a través de la $\to$ (es decir, ninguno de ellos tiene más nudos en el lado derecho que en el izquierdo).

Answer 1

Sí, esto es posible, pero la prueba no es corta y sencilla. A vista de pájaro, el truco consiste en empezar por demostrar la doble negación eliminación : $$ \neg\neg Q \to Q $$ Esto requiere dos instancias del axioma 2: $$ (\neg\neg\neg\neg Q \to \neg\neg Q) \to (\neg Q \to \neg\neg\neg Q) \\ (\neg Q \to \neg\neg\neg Q) \to (\neg\neg Q \to Q) $$ Si temporalmente asume $\neg\neg Q$ , entonces por el axioma 1 tenemos $\neg\neg\neg\neg Q\to\neg\neg Q$ y por las dos implicaciones anteriores obtenemos $\neg\neg Q\to Q$ . Como todavía estamos asumiendo $\neg\neg Q$ podemos obtener $Q$ . Ahora el teorema de la deducción aplicada a este razonamiento da entonces una prueba de $\neg\neg Q\to Q$ sin cualquier supuesto adicional.

Para llegar a la doble negación introducción , set $Q := \neg P$ . La fórmula de eliminación que acabamos de demostrar es entonces $$ \neg\neg\neg P \to \neg P $$ y una última apelación al axioma 2 convierte esto en la deseada $$ P \to \neg\neg P $$

---

Desplegando el teorema de la deducción (y optimizando un poco a mano) obtenemos esta prueba algo formidable, en la que se han omitido varias aplicaciones internas del modus ponens:

$$ \begin{array}{rll} \\ 1. & \neg^3P \to (\neg^5 P \to \neg^3 P) & \mathrm{Ax.}1 \\ 2. & (\neg^5P \to \neg^3P) \to (\neg^2P\to\neg^4P) & \mathrm{Ax.}2 \\ 3. & \neg^3P \to (\neg^5P \to \neg^3P) \to (\neg^2P\to\neg^4P) & \mathrm{Ax.}1, (2) \\ 4. & \neg^3P \to (\neg^2P \to \neg^4P) & \mathrm{Ax.}3, (3), (1) \\ 5. & (\neg^2P \to \neg^4P) \to (\neg^3P\to\neg P) & \mathrm{Ax.}2 \\ 6. & \neg^3P \to (\neg^2P \to \neg^4P) \to (\neg^3 P\to\neg P) & \mathrm{Ax.}1, (5) \\ 7. & \neg^3P \to (\neg^3P \to \neg P) & \mathrm{Ax.}3, (6), (4) \\ 8. & \neg^3P \to \neg^3P & \mathrm{Ax.}1, \mathrm{Ax.}3 \\ 9. & \neg^3P \to \neg P & \mathrm{Ax.3}, (7), (8) \\ 10. & P\to \neg\neg P & \mathrm{Ax.2}, (9) \end{array} $$

Answer 2

¿Es posible demostrarlo? :--

$$P\to \lnot\lnot P$$

La persona que me dio este problema insiste en que es demostrable, aunque me parece que tal demostración es imposible, ya que ninguno de los axiomas aumenta la profundidad de $\lnot$ s a través de la $\to$ (es decir, ninguno de ellos tiene más nudos en el lado derecho que en el izquierdo).

El error en tu razonamiento es que con los axiomas puede obtener más $\neg$ ... por ejemplo, si tiene $P$ , entonces con el axioma $1$ , puedes conseguir $Q \rightarrow P$ para cualquier $Q$ ... así que esto $Q$ podría tener muchos más $\neg$ que el $P$ y utilizando el axioma 2, puedes llevarlos al otro lado del condicional.

Ahora, la prueba real de $P \rightarrow \neg \neg P$ es bastante desagradable. De hecho, a continuación voy a suponer que se puede utilizar el Teorema de la Deducción, que establece que para cualquier $\Gamma$ , $\varphi$ y $\psi$ :

Si $\Gamma \cup \{ \varphi \} \vdash \psi$ entonces $\Gamma \vdash \varphi \rightarrow \psi$

Ahora, la prueba. Primero, probemos: $\phi \to \psi, \psi \to \chi, \phi \vdash \chi$ :

1. $\phi \to \psi$ Premisa

2. $\psi \to \chi$ Premisa

3. $\phi$ Premisa

4. $\psi$ MP 1,3

5. $\chi$ MP 2,4

Por el Teorema de la Deducción, esto nos da el Silogismo Hipotético (HS): $\phi \to \psi, \psi \to \chi \vdash \phi \to \chi$

Ahora vamos a demostrar el principio general de que $\neg \phi \vdash (\phi \to \psi)$ :

1. $\neg \phi$ Premisa

2. $\neg \phi \to (\neg \psi \to \neg \phi)$ Axioma1

3. $\neg \psi \to \neg \phi$ MP 1,2

4. $(\neg \psi \to \neg \phi) \to (\phi \to \psi)$ Axioma2

5. $\phi \to \psi$ MP 3,4

Con el Teorema de la Deducción, esto significa $\vdash \neg \phi \to (\phi \to \psi)$ (Ley de Duns Escoto)

Utilicemos a Duns Escoto para demostrar que $\neg \phi \to \phi \vdash \phi$

1. $\neg \phi \to \phi$ Premisa

2. $\neg \phi \to (\phi \to \neg (\neg \phi \to \phi))$ (Ley de Duns Escoto)

3. $(\neg \phi \to (\phi \to \neg (\neg \phi \to \phi))) \to ((\neg \phi \to \phi) \to (\neg \phi \to \neg (\neg \phi \to \phi)))$ Axioma3

4. $(\neg \phi \to \phi) \to (\neg \phi \to \neg (\neg \phi \to \phi))$ MP 2,3

5. $\neg \phi \to \neg (\neg \phi \to \phi)$ MP 1,4

6. $(\neg \phi \to \neg (\neg \phi \to \phi)) \to ((\neg \phi \to \phi) \to \phi)$ Axioma2

7. $(\neg \phi \to \phi) \to \phi$ MP 5,6

8. $\phi$ MP 1,7

Por el Teorema de la Deducción, esto significa $\vdash (\neg \phi \to \phi) \to \phi$ (Ley de Clavius)

Utilizando a Duns Escoto y la Ley de Clavius, ahora podemos demostrar que $ \neg \neg \phi \vdash \phi$ :

1. $\neg \neg \phi$ Premisa

2. $\neg \neg \phi \to (\neg \phi \to \phi)$ Duns Escoto

3. $\neg \phi \to \phi$ MP 1,2

4. $(\neg \phi \to \phi) \to \phi$ Ley de Clavius

5. $\phi$ MP 3,4

Por el Teorema de la Deducción, esto también significa que $\vdash \neg \neg \phi \to \phi$ (DN Elim)

Ahora podemos demostrar $\vdash \phi \to \neg \neg \phi$ (DN Intro) también:

1. $\neg \neg \neg \phi \to \neg \phi$ (DN Elim)

2. $(\neg \neg \neg \phi \to \neg \phi) \to (\phi \to \neg \neg \phi)$ Axioma 2

3. $\phi \to \neg \neg \phi$ MP 1,2