Prove $\forall x\ (P(x)\Rightarrow Q(x)), \ \forall x\ (Q(x)\Rightarrow W(x)), \ \neg\exists x\ W(x)⊢\neg \exists x\ P(x)$ with Fitch

113 Views Asked by At

Prove that $$\neg \exists x\ P(x) \text{ from }\forall x\ (P(x)\Rightarrow Q(x)), \ \forall x\ (Q(x)\Rightarrow W(x)), \ \neg\exists x\ W(x)$$

I am told to prove this, but am kinda lost where to start. Do I start by contradicting $\neg\exists x\ P(x)$, and see how that affects other premises?

2

There are 2 best solutions below

0
On

Assuming that $\exists x$ such that $P(x)$ will yield a contradiction. Lets assume $\exists x$ such that $P(x)$. By the first premise this also means that $Q(x)$ and by the second premise we then get $W(x)$. But, this contradicts the third premise so our assumption that $\exists x$ such that $P(x)$ can not hold.

2
On

Yes, you start by assume the opposite $\exists xP(x)$, and assume $P(a)$, see if you can find a contradiction then use $\bot \text{ Elim}$ to get $\neg \exists xP(x)$ so we can use $\exists$ Elim on it, here is the general structure of the proof: $$\def\fitch#1#2{\quad\begin{array}{|l}#1\\\hline#2\end{array}} \fitch{1.~~\forall x(P(x)\to Q(x))\\2.~~\forall x(Q(x)\to W(x))\\3.~~\neg\exists x W(x)}{\fitch{4.~~\exists xP(x)}{\fitch{5.~~\boxed{a}P(a)}{\hspace{10ex} \vdots\\11.~~\bot\hspace{20ex}\bot\text{ Intro}~3,10\\12.~~\neg\exists xP(x)\hspace{12.8ex}\bot\text{ Elim}~11}\\13.~~\neg\exists xP(x)\hspace{17ex}\exists\text{ Elim}~4,5-12\\14.~~\bot\hspace{23.8ex}\bot\text{ Intro}~4,13}\\15.~~\neg\exists xP(x)\hspace{20.1ex}\neg\text{ Intro}~4-14}$$