prove that $\vdash (P \Rightarrow Q) \lor (Q \Rightarrow P)$

Question

I'm just starting out in natural deduction. So I have a question now how to prove the following.

Prove that $\vdash (P \Rightarrow Q) \lor (Q \Rightarrow P)$

I'm finding this rather difficult cause, normally I would know what to assume to get to my goal. But in this case I do not know how to even proceed. Any help or insights is deeply appreciated.

Thank you for reading my post

Answer 1

In general, when you don't know how to begin, for classical logic you can use law of excluded middle. The exact details depend on which particular version of natural deduction you have, but it should be easy to translate. $\def\imp{\Rightarrow}$

Solution

If $P$:

  If $Q$:

    $P$.

  $Q \imp P$.

If $\neg P$:

  If $P$:

    Contradiction.

    If $\neg Q$:

      Contradiction.

    $\neg \neg Q$.

    $Q$.

  $P \imp Q$.

[I've left the easy remainder for you to fill in.]

Proof of Law of Excluded Middle

If $\neg (P \lor \neg P)$:

  If $P$:

    $P \lor \neg P$.

    Contradiction.

  $\neg P$.

  $P \lor \neg P$.

  Contradiction.

$\neg \neg (P \lor \neg P)$.

$P \lor \neg P$.