Natural deduction - Logic and Proof

Question

Given the premise P ∨ ¬ Q by natural deduction prove (P → Q) → ((¬ P → Q) → Q)

I am trying to prove this using a Case Proof in Fitch

For my initial subproof, would I be correct in assuming P ∨ Q. I want to deduce implication of P → Q but I am not sure which rule to site. Do I have to break P ∨ Q into Cases of P ∨ Q and cite by elim before I can conclude P → Q.

I think the gap here is how to get from ∨ to → .

Thanks

Answer 1

"For my initial subproof, would I be correct in assuming $P \lor Q$?"

This is legal, but I don't see how it could help.

"I want to deduce implication of $P \to Q$".

You can't infer this from $P\lor \neg Q$, nor from $P\lor Q$.

---

The formula $(P \to Q) \to ((\neg P \to Q) \to Q)$ is a known tautology, therefore you don't need any premises to prove it, (though premises might help shorten the proof). Below I give a proof of this without premises and you can work your way towards shortening it using the given premise.

Answer 2

I assume the logic under consideration is classical propositional logic. Since the classical derivability relation is monotone ($S \vdash \varphi, S \subseteq S' \Rightarrow S' \vdash \varphi$) and the empty set is included in every set it, suffices to show that the conclusion is derivable from the empty set

This is easy:

1(1) $P\rightarrow Q$, Assumption

2(2) $\neg P \rightarrow Q$, Assumption

3(3) $\neg Q$, Assumption

4(1,3) $\neg P$, MT 1,3

5(1,2,3) Q, $\rightarrow$-elim 2, 4

6(1,2,3) $Q \wedge \neg Q$, $\wedge$-intro 3, 5

7(1,2) $Q$, RAA, 3, 6

8(1) $(\neg P \rightarrow Q) \rightarrow Q$, $\rightarrow$-intro 2, 7

9( ) $(P\rightarrow Q) \rightarrow ((\neg P \rightarrow Q) \rightarrow Q)$, $\rightarrow$-intro 1, 8

Answer 3

Another approach:

1. $P\lor \neg Q $ (Premise, 2 cases)

2. $P\implies Q$ (Premise)

3. $\neg P \implies Q$ (Premise)

4. $P$ (Premise, Case 1)

5. $Q$ (Detach, 2, 4)

6. $P\implies Q$ (Conclusion, Case 1)

7. $\neg Q$ (Premise, Case 2)

8. $\neg Q \implies \neg P$ (Contrapositive, 2)

9. $\neg P$ (Detach, 8, 7)

10. $Q$ (Detach, 3, 9)

11. $\neg Q \implies Q$ (Conclusion, Case 2)

12. $P \implies Q \implies Q$ (Cases, 1, 6, 11)

13. $P\implies Q \implies [\neg P \implies Q \implies Q]$ (Conclusion, 2)

14. $P\lor \neg Q \implies [P\implies Q \implies [\neg P \implies Q\implies Q]$ (Conclusion, 1)