0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I can't follow your proof, but here is how I would start out: First, prove $\exists x:[P(x)\implies Q(x)] \implies [\forall x:P(x) \implies \exists x:Q(x)]. $Suppose $\exists x:[P(x)\implies Q(x)]$. Then, for some $y$, we would have $P(y)\implies Q(y)$, or equivalently, $\neg P(y) \lor Q(y)$ giving us two cases to consider. You would have to make use of the rule: If $A$ is true, then $B\implies A$ is also true for any proposition $B$. So is $\neg A \implies B$. $\endgroup$ – Dan Christensen Aug 18 '14 at 14:56
0
$\begingroup$

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)$$

$\endgroup$
1
  • $\begingroup$ thanks a lot. The key is that ¬∀x:P(x) is parsed as ¬(∀x:P(x)) not (¬∀)x:P(x). This is exactly where I had my doubt. $\endgroup$ – user115919 Aug 18 '14 at 16:39
0
$\begingroup$

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}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.