¿Cómo probar$\vdash\neg P\to (P\to Q)$?

Question

Estoy tratando de probar,

$$\vdash\neg P\to (P\to Q)$$

donde $P$ $Q$ son arbitrarias, pero de otra manera fija fórmulas.

La única axiomas y reglas de inferencia que puedo usar son,

$\color{crimson}{\text{Axiom 1.}}\ P\to (Q\to P)$

$\color{crimson}{\text{Axiom 2.}}\ (S\to (P\to Q))\to((S\to P)\to (S\to Q))$

$\color{crimson}{\text{Axiom 3.}}\ (\neg Q\to\neg P)\to(P\to Q)$

$\color{crimson}{\text{Rule of Inference.}}$ Modus Ponens.

Sé que en Angelo Margaris del libro de Primer Orden de la Lógica Matemática no es una prueba (página 53), pero como he mencionado aquí, la notación de punto parece muy confuso y la traducción a la notación de paréntesis anidados parece muy difícil para mí. Por lo tanto, estoy intentando por mi cuenta para probar el resultado.

Alguien puede ayudar?

Answer 1

Abrevie $a = \lnot P$, $b = \lnot Q \to \lnot P$, y $c = P \to Q$. Entonces

$\color{crimson}{\text{1.}}\ a\to b \color{crimson}{\ \ \ \text{by axiom 1}}$

$\color{crimson}{\text{2.}}\ b\to c \color{crimson}{\ \ \ \text{by axiom 3}}$

y tenemos que deducir $a \to c$. Lo que en última instancia va a producir este es

$\color{crimson}{\text{3.}}\ (a \to (b \to c)) \to ((a \to b) \to (a \to c)) \color{crimson}{\ \ \ \text{by axiom 2}}$

Tenga en cuenta que estamos ya muy cerca: sólo tenemos que deducir $a \to (b \to c)$ $b \to c$ y aplicar el modus ponens dos veces. Así

$\color{crimson}{\text{4.}}\ (b\to c) \to (a \to (b \to c)) \color{crimson}{\ \ \ \text{by axiom 1}}$

$\color{crimson}{\text{5.}}\ a \to (b \to c) \color{crimson}{\ \ \ \text{by modus ponens on 2 and 4}}$

Y, como hemos prometido, hemos acabado mediante la aplicación de modus ponens dos veces.

$\color{crimson}{\text{6.}}\ (a \to b) \to (a \to c) \color{crimson}{\ \ \ \text{by modus ponens on 3 and 5}}$

$\color{crimson}{\text{7.}}\ a \to c \color{crimson}{\ \ \ \text{by modus ponens on 1 and 6}}$

Answer 2

1) $\lnot P \rightarrow (\lnot Q\rightarrow \lnot P) $ Axioma 1

2) $(\lnot Q \rightarrow \lnot P)\rightarrow (P\rightarrow Q) $ Axioma 3.

3) $[(\lnot Q \rightarrow \lnot P)\rightarrow (P\rightarrow Q)] \rightarrow \{[\lnot P \rightarrow (\lnot P\rightarrow \lnot Q)]\rightarrow [\lnot P \rightarrow(P\rightarrow Q)]\}$ Axioma 2.

4) $[\lnot P \rightarrow (\lnot P\rightarrow \lnot Q)]\rightarrow [\lnot P \rightarrow(P\rightarrow Q)]$ Modus ponens. 2 y 3 combinados.

5) $\lnot P \rightarrow(P\rightarrow Q)$ Modus ponens 1 y 4 combinados.

====

Originalmente mistated modus ponens. Que es$A; (A \rightarrow B); \implies B$, mientras que en lo que usé era de $(A \rightarrow B);(B\rightarrow C)\implies (A \rightarrow C)$, que es similar pero diferente.

Podemos demostrar que pienso:

$B \rightarrow C$

así, por el axioma 2 $(A \rightarrow B)\rightarrow (A \rightarrow C)$

$(A \rightarrow B)$

Por lo $A \rightarrow C$: modus ponens.

===

Mientras estamos probando cosas que bien podría demostrar modus nolens.

$A \rightarrow B; \lnot B$.

El $(A \rightarrow B) \rightarrow (\lnot B \rightarrow \lnot A)$ Axioma 3

Por lo $\lnot B \rightarrow \lnot A$ modus ponens.

Por lo $\lnot A$. Modus ponens. Por lo tanto modus nolens es válido. Hey, esta probando cosas es bueno!

Pero estoy asumiendo que es determinado $\lnot \lnot P = P$. Es que un determinado? Si no nos debe probar antes de nada.

Lo que se nos dan tan básico tautologías? No sabemos $P\rightarrow P$, $P \lor \lnot P$ etc?

Answer 3

En primer lugar, vamos a la refundición de los esquemas como bien formada fórmulas. Esto hace que las sustituciones de mecánica y menos propenso a errores. O más fácil de corregir cuando se producen errores.

Axioma 1 (P$\to$(P$\to$P))

Axioma 2 ((S$\to$(P$\to$P))$\to$((S$\to$P)$\to$(S$\to$Q)))

Axioma 3 (($\neg$Q$\to$$\neg$P)$\to$(P$\to$P))

Queremos llegar a ($\neg$P$\to$(P$\to$P)). Si nos fijamos en el Axioma 3, con la consiguiente coincide con el consiguiente de que el objetivo de la fórmula. Así que, ¿cómo nos deshacemos de ($\neg$Q$\to$$\lnot$P) y poner $\lnot$P en frente de (P$\to$P)? O podemos hacer una de estas dos?

Así, se da el caso de que (P$\to$P) fue un teorema, entonces el Axioma 1 nos permitiría poner cualquier fórmula, como $\neg$P, en frente de (P$\to$P). Axioma 1 también puede acostumbrarse a deducir cualquier consecuente de una fórmula $\omega$ si el antecedente de la $\omega$ puede conseguir deriva del Axioma 1 por sustitución. Axioma 2 "dice" nosotros que si tenemos algún S en frente de un condicional $\chi$, podemos transferir S al frente de el antecedente de $\chi$ y el frente de la consiguiente de $\chi$. Yo uso $\alpha$/$\beta$ para indicar que $\alpha$ obtiene sustituido con $\beta$. Cuando escribo $\alpha$ * $\beta$, tanto en $\alpha$ $\beta$ indican equiform fórmulas. Por lo tanto, poner a todos juntos...

:Axioma 1 P/(($\neg$Q$\to$$\neg$P)$\to$(P$\to$P)), Q/$\neg$P * 1

1 ((($\neg$Q$\to$$\neg$P)$\to$(P$\to$Q))$\to$($\neg$P$\to$(($\neg$Q$\to$$\neg$P)$\to$(P$\to$Q))))

:1 * (Axioma 3$\to$2)

2 ($\neg$P$\to$(($\neg$Q$\to$$\neg$P)$\to$(P$\to$Q)))

:Axioma 2 S/$\neg$P, P/($\neg$Q$\to$$\neg$P), Q/(P$\to$P) * 3

3 (($\neg$P$\to$(($\neg$Q$\to$$\neg$P)$\to$(P$\to$Q)))$\to$(($\neg$P$\to$($\neg$Q$\to$$\neg$P))$\to$($\neg$P$\to$(P$\to$Q))))

:3 * (2$\to$4)

4 (($\neg$P$\to$($\neg$Q$\to$$\neg$P))$\to$($\neg$P$\to$(P$\to$Q)))

:Axioma 1 P/$\neg$P, Q/$\neg$Q * 5

5 ($\neg$P$\to$($\neg$Q$\to$$\neg$P))

:4 * (5$\to$6)

6 ($\neg$P$\to$(P$\to$P))

El de arriba es un poco de falsa historia si se lee como una indicación de cómo me encontré con esta prueba, pero quizás también ofrece un poco más de metalogical insight.

Answer 4

Sugerencia: uso axioma 1 en el % de forma $\neg P \to (\neg Q \to \neg P)$y el axioma 3.