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$ Aug 18, 2014 at 14:56

2 Answers 2

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, 2014 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .