How can I prove that this sentence is valid?

Question

I am trying to prove the validity of the following: $$(\exists x Px\to \forall y Qy) \to \forall z (Pz \to Qz)$$ but I am completely stumped. Can anyone offer any insight?

Answer 1

Using Natural Deduction :

1) $∃xPx→∀yQy$ --- premise [a]

2) $Pz$ --- premise [b]

3) $∃zPz$ --- from 2) by $∃$-intro

4) $∀yQy$ --- from 1) and 3) by $\to$-elim

5) $Qz$ --- from 4) by $∀$-elim

6) $Pz→Qz$ --- from 2) and 5) by $\to$-intro, discharging [b]

7) $∀z(Pz→Qz)$ --- from 6) by $∀$-intro.

Thus, from 1) and 7):

$(∃xPx→∀yQy) \to ∀z(Pz→Qz)$ --- by $\to$-intro, discharging [a].

---

We can also easily prove the validity of the formula in a "semantical way".

For contradiction, assume that $∃xPx→∀yQy$ is true while $∀z(Pz→Qz)$ is false.

Thus, for some $a$: $Pa→Qa$ is false, i.e. $Pa$ is true and $Qa$ is false.

But if $∃xPx→∀yQy$ is true, then either $∃xPx$ is false or $∀yQy$ is true.

In the first case we have a contradiction with $Pa$ true and in the second case we have a contradiction with $Qa$ false.