Logical Proof in Reduced System

Question

Using only the 3 axioms

1) (φ → (ψ → φ ))

2) ((φ→(ψ →χ))→((φ→ψ)→(φ→χ)))

3) ((¬φ → ¬ψ ) → (ψ → φ ))

and Modus Ponens (in a language consisting of only $\neg$ and $\to$), prove the following

1) ¬q → ¬p, p $\vdash$ r → q

and

2) p→q $\vdash$ (r→p)→(r→q)

I found this problem in "a Concise Introduction to Logic" and I'm not sure how to go about it. I'm used to using natural deduction to construct these types of proofs, but that doesn't suffice in this problem.

I tried a lot of different combinations of the axioms and Modus Ponens, but nothing yielded any progress. Any help would be great, thank you in advance!

Answer 1

For

$¬q → ¬p, p ⊢ r → q$ :

1) $¬q → ¬p$ --- 1st premise

2) $p$ --- 2nd premise

3) $(¬q → ¬p) → (p → q)$ --- Ax.3

4) $p → q$ --- from 1) and 3 by Modus Ponens

5) $q$ --- from 2) and 4) by MP

6) $q \to (r \to q)$ --- Ax.1

7) $r \to q$ --- from 5) and 6) by MP.

---

Similar for the second one, assuming the temporary premises $(r \to p)$ and $r$ and using the Deduction Th.

Answer 2

Mauro ALLEGRANZA wrote a good proof for Part 1. Here's Part 2.

A) $p\to q$ --- premise
B) $(p\to q)\to(r\to(p\to q))$ --- Ax 1
C) $r\to(p\to q)$ --- MP A,B
D) $(r\to(p\to q))\to((r\to p)\to(r\to q))$ -- Ax 2
E) $(r\to p)\to(r\to q)$ -- MP C,D

One thing that helps me with this type of problem is to explain to myself what each of the axioms lets me conclude. So, Axiom 1 says that I can infer any implication if I know the consequent is true (and it's the only way I can introduce new literals), Axiom 2 lets me "distribute" the implication across implication, and Axiom 3 lets me make a contrapositive (and it's the only way to remove negations). Once you can talk that out to yourself, it's just a matter of working backwards to see how you can get to your conclusion from your premises.