Replace an axiom of propositional calculus formal system P.

78 Views Asked by At

We construct a new propositional calculus formal system $P'$. Different from $P$, axiom (A3) is changed to: $$(\neg\alpha\rightarrow\neg\beta)\rightarrow((\neg\alpha\rightarrow\beta)\rightarrow\alpha)$$ Prove that the set of internal theorems of $P'$ and $P$ are identical.

Note: Axioms of $P$

(A$1$) - $(\alpha\rightarrow(\beta\rightarrow\alpha))$

(A$2$) - $((\alpha\rightarrow(\beta\rightarrow\gamma))\rightarrow((\alpha\rightarrow\beta)\rightarrow(\alpha\rightarrow\gamma)))$

(A$3$) - $(((\neg\alpha)\rightarrow(\neg\beta))\rightarrow(\beta\rightarrow\alpha))$

I've understood that if we mark the new axiom as (A4), we just need to prove that (A3) could be derived directly from (A1), (A2) and (A4). But I've tried different combinations and failed.

1

There are 1 best solutions below

0
On BEST ANSWER

Here's how you can show that you can derive $A3$ from $A1$, $A2$, and $A4$.

As you yourself note, given $A1$ and $A2$, we can prove the Deduction Theorem for this system. So given that, let's try to show that for any $\alpha$ and $\beta$ we can derive $\alpha$ from $\neg \alpha \to \neg \beta$ and $\beta$:

$1. \neg \alpha \to \neg \beta$

$2. \beta$

$3. \beta \to (\neg \alpha \to \beta) \ (\text{by } A1)$

$4. \neg \alpha \to \beta \ (\text{MP } 2,3)$

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

$6. (\neg\alpha\rightarrow\beta)\rightarrow\alpha \ (\text{MP } 1,5)$

$7. \alpha \ (\text{MP } 4,6)$

OK, so we have shown that $\neg \alpha \to \neg \beta, \beta \vdash \alpha$

By the Deduction Theorem, this means that $\neg \alpha \to \neg \beta \vdash \beta \to \alpha$

And thus by the Deduction Theorem again, we have $\vdash (\neg \alpha \to \neg \beta) \to ( \beta \to \alpha)$