Why not include another assumption within this natural deduction proof?

335 Views Asked by At

Question: Prove $p → q \vdash ¬q → ¬p$ is valid.

The answer is:

$1. p → q~~~~\textsf{premise}$

$2. ¬q~~~~~\textsf{assumption}$

$3. ¬p~~~~~\textsf{MT }1,2$

$4. ¬q → ¬p~~~~~→\textsf{intro} 2,3$

Why isn't the assumption of $q$ included since $q$ or $¬q$ are both assumptions?

2

There are 2 best solutions below

3
On

I'm not sure whether I get your question correctly but why should we add another assumption? We want to prove the above statement as is without extra assumptions. On top, you might prove the other direction, then you assume q.

If you want to know how to prove it, the typical way is to write down all possibilities with a truth table and see the equivalence.

0
On

The reason we assume $\neg q$ is that we can then use it , the premise, and the modus ponens rule of inference to obtain a consequence, and on discharging the assumption we demonstrate that the premise entails the required conclusion.

$$\begin{align} & \begin{array}{l|l:l} 1 & p\to q & \textsf{premise} \\ \hdashline 2 & \quad \neg q & \textsf{assume} \\ 3 & \quad \neg p & \textsf{modus tollens } 1, 2 \\ \hline 4 & \neg q \to \neg p & \to\textsf{intoduction }2, 3 \end{array} \\[0ex]\hline & p\to q ~\vdash ~\neg q\to \neg p\\ \Box \end{align}$$

The reason we do not assume $q$ is that it is useless to.   There is no rule of inference which we can apply to it and the premise to give anything of interest.

$$\begin{align} & \begin{array}{l|l:l} 1 & p\to q & \textsf{premise} \\ \hdashline 2 & \quad q & \textsf{assume} \\ 3 & \quad & (p\to q), q\textsf{ does not entail anything else} \\ \hline 4 & q \to q & \to\textsf{intoduction }2, 3 \end{array} \\[0ex]\hline & p\to q ~\vdash q\to q\\ \require{cancel} \xcancel\Box \end{align}$$