how do i prove $\forall x(P(x) \rightarrow Q(x)) \vdash (\forall x ¬ Q(x)) \rightarrow (\forall x ¬ P(x))$

Question

as stated in the title, as part of a homework assignment i need to prove the above statement in Fitch notation, and I'm completely lost.

I've been recommended by my TA to work from the assumption $\forall x ¬ Q(x)$ and i suppose that by utilizing the MT rule i will somehow be able to conclude $\forall x ¬ P(x)$ but I'm having trouble filling in the blanks.

also if i arrive at $\forall x ¬ P(x)$ is it possible to just imply $(\forall x ¬ Q(x)) \rightarrow (\forall x ¬ P(x))$ or do i need to also prove $\forall x ¬ Q(x)$?

Answer 1

Unfortunately, I do not know Fitch's system too much; but since it's a variant of natural deduction, I think I can give you some hints.

First, it's correct to start with $\forall x \neg Q(x)$ as an assumption (because it's the antecedent of a conditional that you must prove). From this, you can derive $\forall x \neg P(x)$ in the subproof and directly conclude $\forall x \neg Q(x) \rightarrow \forall x \neg P(x)$, finishing the subproof.

(There is no need to separately proof $\forall x \neg Q(x)$, because it only appears as the antecedent of a conditional. Indeed, it would not even be possible, since $\forall x (P(x) \rightarrow Q(x))$ does not imply $\forall x \neg Q(x)$)

Second, you're right that you should utilize Modus Tollens somewhere in the proof. To be able to do this, you must first eliminate the two universal quantifiers, so that you will have something like

• $P(x) \rightarrow Q(x)$ (from the premise), and
• $\neg Q(x)$ (from the assumption)

Applying Modus Tollens, you get

• $\neg P(x)$

Finally, you should introduce the universal quantifier:

• $\forall x \neg P(x)$

Then you can finish the proof in one step, as described above.