Questions regarding Universal Quantifiers

Question

The question is to show that:

$$\exists x:(P(x) \implies Q(x))\qquad\equiv\qquad\forall x:P(x) \implies \exists x:Q(x)$$

First I use double negation to get to the universal quantifier since it distributes over conjunction:

$$\begin{align} \neg\neg \exists x:(P(x) \implies Q(x)) \\ \equiv \neg\neg\exists x:(\neg P(x) \lor Q(x)) \\ \equiv \neg\forall x:\neg (\neg P(x) \lor Q(x)) \\ \equiv \neg\forall x:(P(x) \land \neg Q(x)) \end{align}$$

(here is where I find a problem, there is 2 ways how I go about this)

(first, I distribute $\forall$, and leave the negation in front of the whole statement, and as it follows it proves it): $$\begin{align} \equiv \neg(\forall x: P(x) \land \forall x: \neg Q(x)) \\ \equiv \neg \forall x: P(x) \lor \neg\forall x:\ neg Q(x) \\ \equiv \neg\forall x:P(x) \lor \exists x:Q(x) \\ \equiv \forall x:P(x) \implies \exists x:Q(x) \end{align}$$

(the other way is to distribute $\neg\forall$ with the negation):

$$\begin{align} \equiv (\neg\forall x:P(x) \land \neg\forall x:\neg Q(x)) \\ \equiv (\exists x:\neg P(x) \land \exists x:Q(x)) \end{align}$$

Which does not lead to the equality.

Does this mean that when we distribute a universal quantifier over a conjunction, if there is a negation in front of it, it will remain in front of the whole statement. It actually makes sense since, by distributing it in the way I did, part of the information is lost since the conjunction operator is not changed.

Just wanting to confirm this thought, thanks.

Answer 1

The key is that $\neg \forall x:P(x)$ is parsed as $\neg(\forall x:P(x))$ not $(\neg\forall)x:P(x)$.

Hence you first distribute the qualifier, then you apply DeMorgan's Law.

$$\neg\forall x:(P(x)\land Q(x)) \\ \neg(\forall x:(P(x)\land Q(x))) \\ \neg(\forall x:P(x) \bigwedge \forall x:Q(x)) \\ \neg\forall x:P(x) \bigvee \neg\forall x:Q(x)$$ Alternatively: $$\neg\forall x:(P(x)\land Q(x)) \\ \exists x:\neg(P(x)\land Q(x)) \\ \exists x:(\neg P(x) \lor \neg Q(x)) \\ \exists x:\neg P(x) \bigvee \exists x:\neg Q(x) \\ \neg\forall x:P(x) \bigvee \neg\forall x:Q(x)$$

Answer 2

It may be useful to first explore the informal justification for the equivalence, and then to examine how it can be formalized. You're trying to prove a biconditional, which means that it suffices to show that the left implies the right and that the right implies the left.

Left to Right

\begin{align} 1.\ & \exists x.(Px \to Qx) & \{1\} & \text{ suppose} \\ 2.\ & \forall x.Px & \{1,2\} & \text{ suppose} \\ 3.\ & P\alpha \to Q\alpha & \{1,2\} & \text{ witness for 1} \\ 4.\ & P\alpha & \{1,2\} & \text{ from 2} \\ 5.\ & Q\alpha & \{1,2\} & \text{ from 3,4} \\ 6.\ & \exists x.Qx & \{1,2\} & \text{ from 5} \\ 7.\ & \forall x.Px \to \exists x.Qx & \{1\} & \text{ discharge 2} \end{align}

Right to Left

\begin{align} 1.\ & \forall x.Px \to \exists x.Qx & \{1\} & \text{ suppose} \\ 2.\ & \lnot(\exists x.(Px \to Qx)) & \{1,2\} & \text{ suppose}\\ 3.\ & \forall x.\lnot(Px \to Qx) & \{1,2\} & \text{ from 2}\\ 4.\ & \forall x.(Px \land \lnot Qx) & \{1,2\} & \text{ from 3}\\ 5.\ & \forall x.Px & \{1,2\} & \text{ from 4}\\ 6.\ & \forall x.\lnot Qx & \{1,2\} & \text{ from 4}\\ 7.\ & \lnot\exists x.Qx & \{1,2\} & \text{ from 6} \\ 8.\ & \exists x.Qx & \{1,2\} & \text{ from 1 and 5} \\ 9.\ & \bot & \{1,2\} & \text{ from 7 and 8} \\ 10.\ & \exists x.(Px \to Qx) & \{1\} & \text{ $\lnot$ elimination from 9, discharging 2} \end{align}