Deduction of $(\exists x Px \rightarrow \forall y Qy)\rightarrow \forall z(Pz \rightarrow Qz)$

Question

Deduction of $(\exists x Px \rightarrow \forall y Qy)\rightarrow \forall z(Pz \rightarrow Qz)$

My try: There exists a deduction as follows. The Deduction and Generalization Theorems together imply that it suffices to show $\{\exists xPx\rightarrow \forall yQy, Pz\}\vdash Qz$.

Now, I received a hint that the following statement in quotes is true, but I can't figure out why.

Moreover, by axiom, modus ponens (MP) and contraposition, it suffices to show $\{Pz, \neg\forall yQy\}\vdash \neg(\exists xPx\rightarrow \forall yQy)$.

The rest follows as so, I believe:

By MP and contraposition, we get $Pz\vdash \exists xPx$, noting that $\vdash \forall x \neg Px\rightarrow \neg Pz$ is an axiom. Now, by A1, we get $\vdash \exists x Px \rightarrow \neg\forall y Qy \rightarrow \neg(\exists xPx\rightarrow \forall yQy)$. Applying MP, we conclude that $\{Pz, \neg\forall yQy\}\vdash \neg(\exists xPx\rightarrow \forall yQy)$, as desired.

Could someone please explain the quoted part?

Answer 1

If we have :

$\{ Pz,¬∀yQy \} ⊢ ¬(∃xPx→∀yQy)$,

by Deduction Theorem: $Pz \vdash ¬∀yQy \to ¬(∃xPx→∀yQy)$ and by Contraposition:

$Pz \vdash (∃xPx→∀yQy) \to ∀yQy$.

Thus, by Modus Ponens:

$\{ Pz, (∃xPx→∀yQy) \} \vdash ∀yQy$.

But; $\vdash ∀yQy \to Qz$, and thus:

$\{ Pz, (∃xPx→∀yQy) \} \vdash Qz$.

Then, by Deduction Th again, followed by Generalization Th:

$(∃xPx→∀yQy) \vdash ∀z (Pz \to Qy)$.

Answer 2

Another solution would be to do as you started. Let $\Gamma$ denote $\{Pz, (\exists x Px \to \forall y Qy)\}$. Then $\Gamma \vdash Pz$ by axiom, so that, by $\exists$-introduction $\Gamma\vdash \exists x Px$. But $\Gamma \vdash \exists x Px \to \forall y Qy$ by axiom, so by $\to$-elimination, $\Gamma\vdash \forall y Qy$, thus by $\forall$-elimination, $\Gamma\vdash Qz$, which is what we wanted. (If you don't allow $\exists$-introduction, as suggested by your proof of $Pz\vdash \exists x Px$, then you can as easily prove this step without it, as you did.