1
$\begingroup$

I wish for a formal proof for $\vdash\neg\alpha\rightarrow(\alpha\rightarrow\beta)$ which doesn't use deduction theorem.

I use the standard axiomatic system:

$\alpha\rightarrow(\beta\rightarrow\alpha)$

$\alpha\rightarrow(\beta\rightarrow\gamma)\rightarrow((\alpha\rightarrow\beta)\rightarrow(\alpha\rightarrow\gamma))$

$(\neg\beta\rightarrow\neg\alpha)\rightarrow((\neg\beta\rightarrow\alpha)\rightarrow \beta)$

Using axiom 2 we get: $$(\neg\alpha \rightarrow((\neg\beta\rightarrow\neg\alpha)\rightarrow(\alpha\rightarrow\beta)))\rightarrow((\neg\alpha \rightarrow(\neg\beta\rightarrow\neg\alpha))\rightarrow(\neg\alpha\rightarrow(\alpha\rightarrow\beta)))$$

which is very promising casue the second expresion is axiom 1, and the expression:$(\neg\beta\rightarrow\neg\alpha)\rightarrow(\alpha\rightarrow\beta)$ can be proved using deduction theorem in the next manner:

$1. \neg\beta\rightarrow \neg \alpha$ assumption

$2.\alpha\rightarrow((\neg\beta \rightarrow\alpha)\rightarrow\beta)\rightarrow((\alpha\rightarrow(\neg \beta\rightarrow \alpha))\rightarrow(\alpha\rightarrow \beta))$ $A2$

$3. (\neg\beta\rightarrow\neg\alpha)\rightarrow((\neg\beta\rightarrow\alpha)\rightarrow\beta)$ $A3$

$4. (\neg\beta\rightarrow\alpha)\rightarrow\beta) $ by MP $1$ from $3$

$5. (\neg\beta \rightarrow\alpha)\rightarrow\beta)\rightarrow(\alpha\rightarrow((\neg\beta \rightarrow\alpha)\rightarrow\beta))$ $A1$

$6. (\alpha\rightarrow((\neg\beta \rightarrow\alpha)\rightarrow\beta))$ MP by 4

$7. ((\alpha\rightarrow(\neg \beta\rightarrow \alpha))\rightarrow(\alpha\rightarrow \beta))$ MP 6 from 2

$8.(\alpha\rightarrow(\neg \beta\rightarrow \alpha) $ A1

$9. \alpha\rightarrow \beta$ MP 7 using 8

I was trying to reverse the proof by seduction theorem using the method by which the Deduction Theorem is proved. So, I need to prove $\neg\beta \rightarrow \neg\alpha \rightarrow (step(i))$ when $step(i)$ is each of the step in the proof demonstrated above. Doing so (as you may see below) lead me to the next conclusion:

if one proves : $((\neg\beta \rightarrow\neg\alpha)\rightarrow((\alpha\rightarrow(\neg\beta\rightarrow\alpha))\rightarrow(\alpha \rightarrow\beta))) \rightarrow(((\neg\beta\rightarrow\neg\alpha)\rightarrow(\alpha\rightarrow(\neg\beta\rightarrow\alpha)))\rightarrow((\neg\beta\rightarrow\neg\alpha)\rightarrow(\alpha\rightarrow\beta)))$

The second expression can be proved by using 2 times Axiom 1.

For the first expression which I'm stuck in, I tried to prove: $(\alpha\rightarrow(\neg\beta\rightarrow\alpha))\rightarrow(\alpha \rightarrow\beta))$ And then using Axiom 1 , but I realized that's can't be proved without assumption cause it is not a tautology! the first expression is Axiom 1 so it is tautology, then in case $\alpha\rightarrow\beta$ is not True ($\alpha = T, \beta = F)$ we get a False statement.

Maybe I took the wrong path? is it another way to solve it? Also, it is worth to mention that this question comes from previous attempt for an other proof I am still trying to make (and I think, this proof is the key for the other):Formally proving $p\wedge q \rightarrow p$


Reversing the Deduction theorem usage:

$1^*. \vdash(\neg\beta\rightarrow \neg \alpha)\rightarrow(\neg\beta\rightarrow \neg \alpha)$ . The same pattern as to prove $\alpha \rightarrow \alpha$

$2^*.\vdash(\neg\beta\rightarrow \neg \alpha)\rightarrow (\alpha\rightarrow((\neg\beta \rightarrow\alpha)\rightarrow\beta)\rightarrow((\alpha\rightarrow(\neg \beta\rightarrow \alpha))\rightarrow(\alpha\rightarrow \beta)))$ Prooving a formula of the pattern $\gamma\rightarrow Axiom$ can be done by using Axiom1.

$3^*.\vdash (\neg\beta\rightarrow \neg \alpha)\rightarrow ((\neg\beta\rightarrow\neg\alpha)\rightarrow((\neg\beta\rightarrow\alpha)\rightarrow\beta))$ same pattern as $2^*$

$4^*. \vdash (\neg\beta\rightarrow \neg \alpha)\rightarrow ((\neg\beta\rightarrow\alpha)\rightarrow\beta)) $ This is an Axiom3 pattern.

$5^*. \vdash(\neg\beta\rightarrow \neg \alpha)\rightarrow ((\neg\beta \rightarrow\alpha)\rightarrow\beta)\rightarrow(\alpha\rightarrow((\neg\beta \rightarrow\alpha)\rightarrow\beta)))$ same pattern as $2^*$ $\gamma \rightarrow Axiom$

$6^*.\vdash(\neg\beta\rightarrow \neg \alpha)\rightarrow ( (\alpha\rightarrow((\neg\beta \rightarrow\alpha)\rightarrow\beta)))$ MP by 4 This is the formula which I don't succeed to prove.

$7^*. \vdash(\neg\beta\rightarrow \neg \alpha)\rightarrow (((\alpha\rightarrow(\neg \beta\rightarrow \alpha))\rightarrow(\alpha\rightarrow \beta)))$ MP 6 from 2

$8^*. \vdash(\neg\beta\rightarrow \neg \alpha)\rightarrow((\alpha\rightarrow(\neg \beta\rightarrow \alpha)) $ A1

$9^*. \vdash (\neg\beta\rightarrow \neg \alpha)\rightarrow (\alpha\rightarrow \beta)$ MP 7 using 8

$\endgroup$
8
  • $\begingroup$ The proof of the deduction theorem is constructive. If you know the proof, then it is a straightforward to convert any theorem using the deduction theorem to one that doesn't use it. $\endgroup$
    – DanielV
    May 3, 2018 at 0:50
  • $\begingroup$ Can you substitute wffs for propositional variables in theorems or only make such substitutions in the axioms? $\endgroup$ May 3, 2018 at 3:09
  • $\begingroup$ @DanielV In order to do so, I need to prove $\neg\beta\rightarrow \neg\alpha \rightarrow step(i) $ for each step in the proof I showed for $\neg\beta\rightarrow\neg\alpha \vdash \beta \rightarrow \alpha$ and this is exactly what I did, and that is how I came to the last axiom 2 expression which I can't figure out. $\endgroup$ May 3, 2018 at 3:41
  • $\begingroup$ @DougSpoonwood I'm sorry but I don't understand what is the meaning of substituting with theorems? May you please give an example? $\endgroup$ May 3, 2018 at 3:43
  • $\begingroup$ The way to "solve" this type of problem is simple and boring: start with an easy derivation with the DT (see page 39 ) and then apply the procedure used in the proof of the DT to eliminate the application of the DT (see page 37 ). $\endgroup$ May 3, 2018 at 6:41

2 Answers 2

2
$\begingroup$

Hint

As said, the proof is simple and (very) boring.

We have to start from the derivation using DT (see e.g. Mendelson ) an "expurgate" the calls to DT: we have to do it one-by-one.

Thus, starting from the derivation $\lnot B, B \vdash C$ we have firstly to produce the new derivation $\lnot B \vdash B \to C$.

I'll follow Mendelson's original derivation :

1') $\lnot B$ --- Hyp

3') $\vdash B \to (\lnot C \to B)$ --- Ax.1

4') $\vdash B \to (\lnot B \to (\lnot C \to \lnot B))$ --- derived from the suitable Ax.1 : $\vdash (\lnot B \to (\lnot C \to \lnot B)) \to [B \to (\lnot B \to (\lnot C \to \lnot B))]$ with Ax.1 and mp

5') $B \to \lnot B$ --- derived from Ax.1 : $\lnot B \to (B \to \lnot B)$ with 1') and mp

6') $B \to (\lnot C \to \lnot B)$ --- derived from Ax.2 with 4') and 5') by mp twice

7') $\vdash [B \to ((\lnot C \to \lnot B) \to ((\lnot C \to B) \to C))] \to [(B \to (\lnot C \to \lnot B)) \to (B \to ((\lnot C \to B) \to C))] \text { --- Ax.2}$

8') $\vdash B \to ((\lnot C \to \lnot B) \to ((\lnot C \to B) \to C))$ --- derived from Ax.3 with suitable Ax.1 and mp

9') $\vdash (B \to (\lnot C \to \lnot B)) \to (B \to ((\lnot C \to B) \to C))$ --- derived 7') and 8') by mp

10') $B \to ((\lnot C \to B) \to C)$ --- derived from 9') and 6') by mp

11') $B \to C$ --- derived from Ax.2 with 3') and 10') by mp twice.

$\endgroup$
1
  • $\begingroup$ Thanks! it took me an hour to fully formalize it!! Now I need to do the same for $(\neg\beta \rightarrow\neg\alpha)\rightarrow(\alpha\rightarrow\beta)$ =DD $\endgroup$ May 3, 2018 at 13:14
2
$\begingroup$

My answer is: $$\begin{array}{r|ll} 1 & \neg\alpha\rightarrow(\neg\beta\rightarrow\neg\alpha) & Ax. 1\\ 2 & (\neg\beta\rightarrow\neg\alpha)\rightarrow(\alpha\rightarrow\beta) & Ax. 3\\ 3 & (\neg\alpha\rightarrow(\neg\beta\rightarrow\neg\alpha))\rightarrow(((\neg\beta\rightarrow\neg\alpha)\rightarrow(\alpha\rightarrow\beta))\rightarrow(\neg\alpha\rightarrow(\alpha\rightarrow\beta))) & Ax. 2\\ 4 & ((\neg\beta\rightarrow\neg\alpha)\rightarrow(\alpha\rightarrow\beta))\rightarrow(\neg\alpha\rightarrow(\alpha\rightarrow\beta)) & 1,3,MP\\ 5 & \neg\alpha\rightarrow(\alpha\rightarrow\beta) & 2,4,MP \end{array}$$

$\endgroup$
1
  • $\begingroup$ axiom 3 is not the one proposed by the OP,I think $\endgroup$
    – user149368
    Jun 8, 2022 at 20:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .