Derivation of Quantifier Negation: $-(\forall x)(Px \rightarrow -Qx) \vdash (\exists x)(Px \wedge Qx)$

Question

I am working on a series of derivations demonstrating the equivalence of negated quantifiers, etc.

I've worked through a bunch, but am stuck on one that seems to have Demorgan's law in it when I get my proof going.

$-(\forall x)(Px \rightarrow -Qx) \vdash (\exists x)(Px \wedge Qx)$

From there, I started with the premise, and then assumed:

$-(\exists x)(Px\wedge Qx)$

And then to:

$-(Pa\wedge Qa)$

From there, I dont really know what steps I should take. I think I would like to get to contradict on each parts of the conjunction and end with showing a contradiction between $-(\forall x)(Px \rightarrow -Qx) \wedge (\forall x)(Px \rightarrow -Qx)$, but without the availability to freely use Demorgan's law, I feel like it would be more work to try to insert a sub-proof to break it apart.

Does anyone have any suggestions or know if I am going about this the right way at all?

Answer 1

My answer assumes that you are able to either assume or to prove that in general

$$(A \implies B) \iff [(-A) \vee B].$$

Using this property, you have

$$-(\forall x)(Px \implies -Qx) \iff -(\forall x)[(-Px) \vee (-Qx)] \iff$$

$$(\exists x)(Px \wedge Qx).$$

Answer 2

Your basic strategy of proving this through a proof by Contradiction is correct. However, after assuming $\neg \exists x (Px \land Qx)$, I am not so sure you are allowed to infer $\neg (Pa \land Qa)$ .... it depends on how the rules are defined in your derivational system.

Here is what i would do: prove that $\forall x (Px \to \neg Qx)$, so that you get a contradiction with the very premise.

So, assume that $a$ is an arbitrary object, assume $Pa$, and show that $\neg Qa$ using another proof by contradiction: the assumption of $Qa$ leads to $Pa \land Qa$, and thus to $\exists x (Px \land Qx)$, contradicting you original assumption.