Propositional Logic: p → q, ¬p → r, ¬q → ¬r ⊢ q

Question

Is this proof correct?

p → q, ¬p → r, ¬q → ¬r ⊢ q

1) p → q      premise
2) ¬p → r     premise
3) ¬q → ¬r    premise
  4) -q       assumption
  5) -p       MT 1,4
    6) p      assumption
    7) ⊥      ¬e 5,6
  8) ⊥        ¬e 2,3
9) q          ¬e 8

Am I going correct? What might be the next step?

I updated my answer.

Answer 1

There exist different natural deduction systems with different rules for negation. For this exercise you might assume the negation of q.

Notice that ($\lnot$p $\rightarrow$ r) and ($\lnot$q $\rightarrow$ $\lnot$r) have r and $\lnot$r as their right hand side or consequent, respectively. What do your negation rules say when you have an instance of some well-formed formula $\alpha$ and $\lnot$$\alpha$?

If you assume $\lnot$q and then assume p, can you infer some other instance of $\alpha$ and $\lnot$$\alpha$? What was the last assumption made which you might discharge? If you discharge it, then with the other premisses, can you then discharge the first assumption/hypothesis/supposition?

Answer 2

Your step 8 makes no sense. Also, your other steps with the logical structure clear are as follows:

---

$p \to q$   [premise]

$\neg p \to r$   [premise]

$\neg q \to \neg r$   [premise]

If $\neg q$:

  $\neg p$   [MT]

  If $p$:

    Contradiction.

  [Therefore you get nowhere because you did not get contradiction under the first assumption.]

---

Note that it is never useful to create a new subcontext by assuming the negation of what you have already proven. In the above, in the context where $\neg q$ you proved $\neg p$, so it would be useless to create the subcontext where $p$, since you already know it can never occur. Instead, from $\neg p$ and $\neg q$ you can derive other things by modus ponens. See if you can complete the proof.

I encourage you to use indentation or some other syntax to make clear to yourself what the context of every sentence is. A sentence may not be true in the global context (no assumptions) but may be true in some context (under some assumptions).

The final proof should look like:

---

$p \to q$   [premise]

$\neg p \to r$   [premise]

$\neg q \to \neg r$   [premise]

If $\neg q$:

  $\neg p$   [MT]

  ... [Use the premises here to deduce two sentences that contradict one another] ...

  Contradiction.

$\neg \neg q$.

$q$.