0
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you for the very detailed explanation! I understand now :) $\endgroup$ – wonggr Oct 16 '13 at 19:06
  • $\begingroup$ The OP asked for a proof "with equivalence statements". It does not seem this answer does that... $\endgroup$ – Marnix Klooster Oct 17 '13 at 5:32
0
$\begingroup$

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}

$\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.