Working on P.D. Magnus. forallX: an Introduction to Formal Logic (pp. 289, exercise G. 1), asks:
G. Show that each pair of sentences is provably equivalent.
- $\forall x(A(x) \to \neg B(x)); \neg\exists x(A(x) \wedge B(x))$
I need to provide two proofs in order to achieve that result.
Struggling with the second one, that is: $\neg\exists x(A(x) \wedge B(x)) \vdash \forall x(A(x) \to \neg B(x)$
My proof needs to look like, I think:
$
\def\fitch#1#2{\quad\begin{array}{|l}#1\\\hline#2\end{array}}
\fitch{¬\exists x(A(x) \wedge B(x))}{
\ldots\\
A(a) \to \neg B(x)\\
\forall x(A(x) \to \neg B(x)
}
$
I cannot use $\mathbf{\exists E}$ since $\exists$ is not the main logical operator. How should I approach this proof ?
Best Answer
You are off to a good start. Now you need to introduce a conditional, so set it up: assume $A(a)$ hoping to derive $\neg B(a)$. (NB: I prefer to note the assumption of an arbitrary variable.)
Thus you will need to introduce a negation, so set it up: assume $B(a)$ hoping to derive a contradiction.
Okay, so what can you contradict with the assumptions of $\neg\exists x~(A(x)\wedge B(x))$, $A(a)$, and $B(b)$?
Then to prove equivalence you will need another subproof, which will involve introducing a negation, and inside that subproof is where you can use existential elimination.
$\def\fitch#1#2{\quad\begin{array}{|l}#1\\\hline#2\end{array}} \fitch{}{\fitch{¬\exists x~(A(x) \wedge B(x))}{\fitch{[a]}{\fitch{A(a)}{\fitch{B(a)}{~\vdots\\\bot}\\\neg B(a)}\\A(a)\to\neg B(a)}\\\forall x~(A(x)\to\neg B(x)}\\\neg\exists x~(A(x)\wedge B(x))\to\forall x~(A(x)\to B(x))\\\fitch{\forall x~(A(x)\to\neg B(x))}{\fitch{\exists x~(A(x)\wedge B(x))}{\fitch{[b]~A(b)\wedge B(b)}{~\vdots\\\bot}\\\bot}\\\neg\exists x~(A(x)\wedge B(x))}\\\forall x~(A(x)\to\neg B(x))\to\neg\exists x~(A(x)\wedge B(x))\\\forall x~(A(x)\to\neg B(x))\gets\hspace{-2ex}\to\neg\exists x~(A(x)\wedge B(x))}$