De morgan quantifers prove

Question

prove ∃x (P(x) => Q(x)) = ∀x P(x) => ∃x Q(x)

∃x (P(x) => Q(x))

= ∃x (¬P(x) ∨ Q(x)) ----- (1)

= ∃x(¬P(x)) ∨ ∃xQ(x) ----- (2)

= ¬∀xP(x) ∨ ∃xQ(x) ----- (3)

= ∀x P(x) => ∃x Q(x) ----- (4)

From line 2 to line 3, we use demorgan law to convert the existential to universal.

From line 3 to line 4, apparently is P => Q === ¬P ∨ Q However, it doesnt make sense to me.

Because ∀x P(x) => ∃x Q(x) should be ∀x¬P(x) ∨ ∃x Q(x) and not ¬∀xP(x) ∨ ∃xQ(x)

Please tell me how to do this or what i am misunderstanding. thank you

Answer 1

Because ∀x P(x) => ∃x Q(x) should be ∀x¬P(x) ∨ ∃x Q(x) and not ¬∀xP(x) ∨ ∃xQ(x)

No, your comprehension is wrong. Notice that $\forall x\left(P(x)\right)$ is simply one statement, and it's negation is $\exists x\left(\neg P(x)\right)$ and not $\forall x\left(\neg P(x)\right)$. Simply, it is by logic rules.

Answer 2

It might be best to not drop bracketing so as to be clear on where the scope of each quanifier lies, and not to be confused by order of operations.

$$\begin{align} & \exists x~\big(P(x)\to Q(x)\big) \tag 1 \\\iff & \exists x~\big(\neg P(x)\vee Q(x)\big)\tag 2 \\ \iff & \big(\exists x~\neg P(x)\big)\vee\big(\exists x ~Q(x)\big)\tag 3 \\ \iff & \neg\big(\forall x~P(x)\big)\vee\big(\exists x~Q(x)\big)\tag 4 \\ \iff & \big(\forall x~P(x)\big)\to\big(\exists x~Q(x)\big)\tag 5 \\ \hline \therefore \quad\exists x~\big(P(x)\to Q(x)\big)\iff & \big(\forall x~P(x)\big)\to\big(\exists x~Q(x)\big) \end{align}$$

---

Order of Operations $\to$ has precedence over $\forall,\exists$ which have precedence over $\wedge,\vee$ which have precedence over $\neg$

So $\forall x~P(x)\to R$ is read as $\big(\forall x~P(x)\big)\to R$ rather than $\forall x~\big(P(x)\to R\big)$