Prove using Natural Deduction in predicate logic $(\forall x\ P(x))\to Q ⊢ \exists x (P(x)\to Q)$

Question

I couldn't find a proper answer. I am pretty sure the universal quantifier elimination rule can't be applied directly and I tried proving by contradiction, but couldn't complete it.

Answer 1

The following is a proof using natural deduction and, per your request, without using DeMorgan's law, null quantification laws, or contrapositive law:

$1$. $\forall x P(x) \rightarrow Q$ ---- premise

$2$. $\neg \forall x P(x) \vee Q$ ---- implication law $1$

$3$. $Q \vee \neg \forall x P(x) $ ---- commutative law $2$

$4$. $\neg \neg Q \vee \neg \forall x P(x) $ ---- double negation law $3$

$5$. $\neg Q \rightarrow \neg \forall x P(x) $ ---- implication law $4$

_____ $6$. $\neg Q$ ---- ACP

_____ $7$. $\neg \forall x P(x)$ ---- modus ponens $5,6$

__________ $8$. $\neg \exists x \neg P(x)$ ---- AIP

_________________ $9$. $\neg P(x)$ ---- AIP

_________________ $10$. $\exists x \neg P(x)$ ---- $\exists$ intro $9$

_________________ $11$. $\exists x \neg P(x) \wedge \neg \exists x \neg P(x)$ ---- conjunction intro $8,10$

__________ $12$. $\neg \neg P(x)$ ---- IP $9$-$11$

__________ $13$. $P(x)$ ---- double negation $12$

__________ $14$. $\forall x P(x)$ ---- $\forall$ intro $13$

__________ $15$. $\forall x P(x) \wedge \neg \forall x P(x)$ ---- conjunction intro $7,14$

_____ $16$. $\neg \neg \exists x \neg P(x)$ ---- IP $8$-$15$

_____ $17$. $\exists x \neg P(x)$ ---- double negation $16$

$18$. $\neg Q \rightarrow \exists x \neg P(x)$ ---- CP $6$-$17$

_____ $19$. $\neg Q$ ---- ACP

_____ $20$. $\exists x \neg P(x)$ ---- modus ponens $18,19$

_____ $21$. $\neg P(b)$ ---- $\exists$ elim $20$

$22$. $\neg Q \rightarrow \neg P(b)$ ---- CP $19$-$21$

$23$. $\neg \neg Q \vee \neg P(b)$ ---- implication law $22$

$24$. $Q \vee \neg P(b)$ ---- double negation law $23$

$25$. $\neg P(b) \vee Q$ ---- commutative law $24$

$26$. $P(b) \rightarrow Q$ ---- implication law $25$

$27$. $\exists x (P(x) \rightarrow Q)$ ---- $\exists$ intro $26$

Answer 2

Hint: either $\forall x\ P(x)$ is true or it isn't.

• If it is true, then $Q$ is true and your $P(x)\to Q$ is true for any value of $x$.
• If it is not true, then you can choose some $x$ such that $\neg P(x)$. Then $P(x)\to Q$ is vacuously true for that value of $x$.

Answer 3

Following @Matthew Daly's hint,

here would be the general structure of the proof:

$\def\fitch#1#2{\quad\begin{array}{|l}#1\\\hline#2\end{array}}$ $$\fitch{~~1.~(\forall xP(x))\to Q} {\fitch{~~2.~\neg(\forall xP(x)\lor\neg\forall xP(x))}{ \fitch{~~3.~\forall xP(x)}{~~ 4.~(\forall xP(x))\lor(\neg(\forall x P(x)))\hspace{10ex}{\lor}~\textsf{Intro}~3\\~~ 5.~\bot\hspace{32.6ex}{\bot}~\textsf{Intro}~2,4}\\~~ 6.~\neg(\forall xP(x))\hspace{27.2ex}{\neg}~\textsf{Intro}~3-5\\~~ 7.~(\forall xP(x))\lor(\neg(\forall xP(x)))\hspace{13.5ex}{\lor}~\textsf{Intro}~6\\~~ 8.~\bot\hspace{36.4ex}{\bot}~\textsf{Intro}~2,7}\\~~ 9.~(\forall xP(x))\lor(\neg(\forall xP(x)))\hspace{17ex}{\neg}~\textsf{Intro}~2-8\\ \fitch{~~ 10.~\forall xP(x)}{ \fitch{~~ 11.~P(a)}{~~ 12.~Q\hspace{31.5ex}{\to}~\textsf{Elim}~1,10}\\~~ 13.~P(a)\to Q\hspace{26.5ex}{\to}~\textsf{Intro}~11-12\\~~ 14.~\exists x(P(x)\to Q)\hspace{23.1ex}{\exists}~\textsf{Intro}~13 }\\\fitch{~~ 15.~\neg(\forall xP(x))}{\fitch{~~ 16.~\neg\exists x(P(x)\to Q)}{\fitch{~~ 17.~\boxed{a}}{\fitch{~~ 18.~\neg P(a)}{\fitch{~~ 19.~P(a)}{~~ 20.~\bot\hspace{21ex}{\bot}~\textsf{Intro}~18,19~\\~~ 21.~Q\hspace{21ex}{\bot}~\textsf{Elim}~20~}\\~~ 22.~P(a)\to Q\hspace{16ex}{\to}\textsf{Intro}~19-21~\\~~ 23.~\exists x(P(x)\to Q)\hspace{12ex}{\exists}~\textsf{Intro}~22~\\~~ 24.~\bot\hspace{25ex}{\bot}~\textsf{Intro}~16,23~}\\~~ 25.~\neg\neg P(a)\hspace{22.5ex}{\neg}~\textsf{Intro}~18-24~\\~~ 26.~P(a)\hspace{25.5ex}{\neg}~\textsf{Elim}~25~}\\~~ 27.~\forall xP(x)\hspace{26.5ex}{\forall}~\textsf{Intro}~17-26~\\~~ 28.~\bot\hspace{32ex}{\bot}~\textsf{Intro}~15,27~}\\~~ 29.~\exists x(P(x)\to Q)\hspace{22.5ex}{\neg}~\textsf{Intro}~16-28~}\\~~ 30.~\exists x(P(x)\to Q)\hspace{26ex}{\lor}~\textsf{Elim}~9,10-14,15-29}$$

From line $1-9$ we proved:

"either ∀x P(x) is true or it isn't."

From line $10-14$ we proved:

"If it is true, then $Q$ is true and your $P(x)→Q$ is true for any value of x."

From line $15-29$ we proved:

"If it is not true, then you can choose some x such that $¬P(x)$. Then $P(x)→Q$ is vacuously true for that value of $x$."

And line $30$ we finishes the prove.

Answer 4

I am pretty sure the universal quantifier elimination rule can't be applied directly

Correct: you cannot apply universal elimination on part of a larger statement.

I tried proving by contradiction, but couldn't complete it.

Too bad ... it's typically a good strategy for whenever you have to prove an existential and you can;t have an existential already to work with. In fact, below is a completed proof by Contradiction in Fitch. It does not use any equivalence principles.