Prove statement using natural deduction rules for propositional logic: $((q → p) → q) → q$

Question

$$((q → p) → q) → q$$ There are no premises which makes this problem very difficult for me. What I tried was assuming that the whole left side $((q → p) → q)$ then I assumed $¬q$ and tried to find a contradiction so I can conclude $q$, then do a conditional proof. However, it doesn't seem to be working. Any hints/help?

Answer 1

You can freely download my intro logic book from https://www.logicmatters.net/ifl -- and you'll find that it does propositional logic natural deduction proofs Fitch-style over a number of chapters. (I like to think it is reasonably clear! ;-)

And the proof of this theorem is on pp. 212--213.

This is so-called Pierce's Law, which is rather interesting as it only involves the conditional, but it can't be proved using the standard inference rules for the conditional alone. You need also to appeal to the law of excluded middle or to an equivalent like the double negation law (as in the proof I give).

Answer 2

Using the truth table, one has \begin{array}{|c|c|c|c|c|} \hline q & p & q\to p&(q\to p)\to q&((q\to p)\to q)\to q \\ \hline 1 & 0 & 0 & 1 & 1\\ \hline 1 & 1 & 1 & 1 & 1\\ \hline 0 & 0 & 1 & 0 & 1\\ \hline 0 & 1 & 1 & 0 & 1\\ \hline \end{array} and hence $$ ((q\to p)\to q)\to q. $$