Proof of $p\rightarrow(q\rightarrow r)\vdash_{HR} (p\rightarrow q)\rightarrow r$

96 Views Asked by At

Let HR be an Hilbert style proof system:

Inference rule: MP

Axiom schemes:

  1. $A\rightarrow A$
  2. $(A\rightarrow B)\rightarrow ((B\rightarrow C)\rightarrow(A\rightarrow C))$
  3. $(A\rightarrow(B\rightarrow C))\rightarrow(B\rightarrow(A\rightarrow C))$
  4. $(A\rightarrow(A\rightarrow B))\rightarrow B$

Prove formally that $p\rightarrow(q\rightarrow r)\vdash_{HR} (p\rightarrow q)\rightarrow r$

I've seen this similar question:

Proof for $\{p,p\rightarrow (q\rightarrow r)\}\vdash (p\rightarrow q)\rightarrow r$ in HR

However, they use $p$ as an additional assumption, and I don't know how to prove it without that assumption

2

There are 2 best solutions below

0
On BEST ANSWER
  1. $(p\rightarrow q)\rightarrow ((q\rightarrow r)\rightarrow(p\rightarrow r))$ - Axiom 2
  2. $(q\rightarrow r)\rightarrow ((p\rightarrow q)\rightarrow(p\rightarrow r))$ - (1) and axiom 3, MP
  3. $p\rightarrow(q\rightarrow r)$ - Assumption
  4. $p\rightarrow ((p\rightarrow q)\rightarrow(p\rightarrow r))$ - (3), (2) and axiom 2, 2 MPs
  5. $((p\rightarrow q)\rightarrow (p\rightarrow r))\rightarrow(p\rightarrow ((p\rightarrow q)\rightarrow r))$ - Axiom 3
  6. $p\rightarrow (p\rightarrow ((p\rightarrow q)\rightarrow r))$ - (4), (5) and axiom 2, 2 MPs
  7. $(p\rightarrow q)\rightarrow r$ - (6) and axiom 4, MP
4
On

What you want to prove does not hold.

If $p$, $q$ and $r$ are all false, then $p\to(q\to r)$ is true, but $(p\to q)\to r$ is false.