Deducción natural - utilizar RAA

Question

Dé pruebas de deducción natural que demuestren cada una de las siguientes:

a) $\phi\vdash\top$ para cualquier fórmula $\phi$ .

b) $(P_1\to P_2)\vdash (\lnot P_2\to\lnot P_1)$ .

c) $(\lnot P_2\to\lnot P_1)\vdash (P_1\to P_2)$ (Pista: Esto requiere una reductio ad absurdum).

---

He resuelto tanto a) como b) pero no c). Realmente no entiendo la RAA más allá de que sea una prueba por contradicción. Y no entiendo cuando usarlo o donde debo usarlo. ¿La RAA es siempre el último paso en tu árbol de pruebas o puedes usarla en alguna etapa anterior? En mi caso quiero asumir $\lnot(\lnot P_2\to\lnot P_1)$ ¿y tratar de contradecir este hecho inventando una tontería que no puede ser cierta?

---

Aquí está mi intento de resolver el problema:

$$\frac{\frac{\frac{\lnot(\lnot P_2\to\lnot P_1)\to\lnot P_2\to\lnot P_1\quad \quad[\lnot(\lnot P_2\to\lnot P_1)]}{\lnot P_2\to\lnot P_1}\to I \quad \quad \lnot P_2}{\lnot P_1}\to I\quad \quad [P_1]^1}{\frac{\bot}{P_1\to P_2}RAA}\to I.$$

Así que trabajé de abajo a arriba cuando construí el árbol de pruebas. Creo que los dos últimos pasos (parte inferior del árbol) son lógicos para mí. Creo" que realmente creo en estos dos pasos. Pero luego empiezo a estar inseguro y no soy totalmente consciente de lo que estoy haciendo. Espero que alguien pueda ayudarme. ¡Gracias! :)

Answer 1

1) $¬P_2 → ¬P_1$ --- premisa

2) $¬P_2$ --- asumido [a]

3) $¬P_1$ --- de 1) y 2) por $\to$ -elim

4) $P_1$ --- asumido [b]

5) $\bot$ --- de 4) y 3) por $\to$ -elim ( $\lnot A $ es $A \to \bot$ )

6) $P_2$ --- de 2) y 5) por RAA , descargando [a]

7) $P_1 → P_2$ --- de 4) y 6) por $\to$ -intro, descargando [b].

Así, a partir de 1) y 7) :

$(¬P_2 → ¬P_1) \vdash (P_1 → P_2)$ .

---

Aquí es lo mismo que un árbol de pruebas:

$$\frac{\frac{\lnot P_2\to\lnot P_1 \quad \quad [\lnot P_2]^1}{\lnot P_1}\to E\quad \quad [P_1]^2}{\frac {\frac{\bot}{P_2}RAA_1}{P_1 \to P_2}\to I_2}\to E$$