Prove the following with equivalence statements.

Question

I need to prove the following statement with equivalence statements.

$\exists x \in D,(P(x) \Rightarrow Q(x)) \ \text{is equivalent to} \ (\forall x \in D, P(x)) \Rightarrow (\exists x \in D, Q(x)))$

At the moment, I don't see how they can be possible equivalent as it seems like the quantifier statement is distributed among the predicates. Is this a legitimate operation in logic? Cheers!

Answer 1

Assume $\exists x\in D, (P(x)\Rightarrow Q(x))$ and let $x_0\in D$ be such that $P(x_0)\Rightarrow Q(x_0)$.

Case 1. $P(x_0)$. Then by modus ponens $Q(x_0)$, hence $\exists x\in D,Q(x)$. We may add an arbitrary premise, so $(\forall x\in D,P(x))\Rightarrow (\exists x\in D,Q(x)))$.

Case 2. $\neg P(x_0)$. Then $\neg \forall x\in D,P(x)$. Ex falsum quodlibet, i.e. $(\forall x\in D,P(x))\Rightarrow (\exists x\in D,Q(x)))$.

Since the result follows in both cases we indeed conclude $(\forall x\in D,P(x))\Rightarrow (\exists x\in D,Q(x)))$, and thus have shown

$$ \tag1\exists x\in D, (P(x)\Rightarrow Q(x))\implies (\forall x\in D,P(x))\Rightarrow (\exists x\in D,Q(x))).$$

Now assume $(\forall x\in D,P(x))\Rightarrow (\exists x\in D,Q(x)))$.

Case 1. $\forall x\in D,P(x)$. Then by modus ponens $\exists x\in D,Q(x))$, say $Q(x_1)$ with $x_1\in D$. Then also $P(x_1)\Rightarrow Q(x_1)$ and hence $\exists x\in D, (P(x)\Rightarrow Q(x))$.

Case 2. $\neg\forall x\in D,P(x)$, i.e. $\exists x\in D,\neg P(x)$. Let $x_2\in D$ with $\neg P(x_2)$. Again using ex falsum quodlibet, we have $P(x_2)\Rightarrow Q(x_2)$ and hence $\exists x\in D, (P(x)\Rightarrow Q(x))$.

Since the result follows in both cases we indeed conclude $\exists x\in D, (P(x)\Rightarrow Q(x))$, and thus have shown

$$\tag2 (\forall x\in D,P(x))\Rightarrow (\exists x\in D,Q(x)))\implies \exists x\in D, (P(x)\Rightarrow Q(x)).$$

Combining (1) and (2) we have

$$ \exists x\in D, (P(x)\Rightarrow Q(x))\iff (\forall x\in D,P(x))\Rightarrow (\exists x\in D,Q(x))).$$

Answer 2

Here is a proof using equivalences, using a slightly different notation that I'm more familiar with: \begin{align} & \langle \forall x \in D :: P(x) \rangle \;\Rightarrow\; \langle \exists x \in D :: Q(x) \rangle \\ \equiv & \;\;\;\;\;\text{"expand $\;\Rightarrow\;$ -- this seems the only way to make progress"} \\ & \lnot \langle \forall x \in D :: P(x) \rangle \;\lor\; \langle \exists x \in D :: Q(x) \rangle \\ \equiv & \;\;\;\;\;\text{"simplify: DeMorgan on left hand part"} \\ & \langle \exists x \in D :: \lnot P(x) \rangle \;\lor\; \langle \exists x \in D :: Q(x) \rangle \\ \equiv & \;\;\;\;\;\text{"simplify: $\;\exists\;$ distributes over $\;\lor\;$"} \\ & \langle \exists x \in D :: \lnot P(x) \lor Q(x) \rangle \\ \equiv & \;\;\;\;\;\text{"reintroduce $\;\Rightarrow\;$"} \\ & \langle \exists x \in D :: P(x) \Rightarrow Q(x) \rangle \\ \end{align}