Quantifiers, predicates, logical equivalence

I am asked if $(\exists x) (P(x) \rightarrow Q(x))$ and $\forall x P(x) \rightarrow \exists xQ(x)$ are logically equivalent.

I don't think they are but how will I prove it?

Am I supposed to use either of the direct proof, contrapositive or contradiction proofs? Or give an interpretation?

Solution 1:

If you can prove that $(1)$ one statement implies the other AND $(2)$ vice versa, then you prove logical equivalence. That is, we show:

$(\exists x)(P(x) \rightarrow Q(x)) \implies (\forall x P(x) \rightarrow \exists x Q(x))\tag{1}$

$\forall x P(x) \rightarrow \exists x Q(x) \implies (\exists x)(P(x) \rightarrow Q(x))\tag{2}$

$(1)\to (2):$
Suppose $(\exists x)(P(x)\to Q(x))$.
Then $P(x_0)\to Q(x_0)$ for some $x_0$.
Now suppose $\forall xP(x)$. If there are no $x$, then the implication (2) is true.
Else, then clearly there is some $x_0$ such that $P(x_0)$.
Thus, $Q(x_0)$ and $\exists xQ(x)$.
So we have shown $\forall xP(x)\to \exists xQ(x)$.

$(2)\to (1):$
Now assume $\forall xP(x)\to \exists xQ(x)$.
Either (a) $\forall xP(x)$ or (b) $\lnot \forall x P(x) \equiv \exists x\neg P(x)$.
In the case of (a), $\exists xQ(x)$, that is, $Q(x_0)$ for some $x_0$ and so $P(x_0)\to Q(x_0)$.
In the case of (b), $\neg P(x_1)$ for some $x_1$
so then $P(x_1)\to Q(x_1)$.
Thus in either (a), (b), $(\exists x)(P(x)\to Q(x))$.

• That is, you have shown that $(1) \iff (2)$. Either statement is true if and only if the other is true. I.e. $(1) \equiv (2)$.

To disprove logical equivalence, it suffices to find a counter example: find any interpretation in which one of the statements is true, but the other is false.

Note that $$\forall x P(x) \rightarrow \exists xQ(x) \equiv \lnot\forall x P(x) \lor \exists xQ(x)$$ is false if and only if $\forall xP(x)$ is true, but $\exists x Q(x)$ is false. Put differently, the statement is true whenever $\forall xP(x)$ is false, and/or it is true whenever $\exists Q(x)$ is true.

Solution 2:

Here is a late alternative proof (in a slightly different notation that I'm more familiar with): \begin{align} & \langle \forall x :: P(x) \rangle \Rightarrow \langle \exists x :: Q(x) \rangle \\ \equiv & \;\;\;\;\;\text{"expand $\;\Rightarrow\;$ in the simplest way possible"} \\ & \lnot \langle \forall x :: P(x) \rangle \lor \langle \exists x :: Q(x) \rangle \\ \equiv & \;\;\;\;\;\text{"simplify: DeMorgan on left hand side"} \\ & \langle \exists x :: \lnot P(x) \rangle \lor \langle \exists x :: Q(x) \rangle \\ \equiv & \;\;\;\;\;\text{"simplify: $\;\exists\;$ distributes over $\;\lor\;$ (since both are disjunctions)"} \\ & \langle \exists x :: \lnot P(x) \lor Q(x) \rangle \\ \equiv & \;\;\;\;\;\text{"reintroduce $\;\Rightarrow\;$"} \\ & \langle \exists x :: P(x) \Rightarrow Q(x) \rangle \\ \end{align} So these expressions are equivalent.

Solution 3:

Hint: Use this fact that $P\to Q$ is logically equivalent to $\sim P\vee Q$. More over we know that $\sim (\exists x,~ P(x))\equiv \forall x, \sim P(x)$ and vice versa.

Solution 4:

Assume $(\exists x)(P(x)\to Q(x))$. Thus $P(x_0)\to Q(x_0)$ for some $x_0$. Assume $\forall xP(x)$. Then especially $P(x_0)$. Hence $Q(x_0)$ and $\exists xQ(x)$. We have thus shown $\forall xP(x)\to \exists xQ(x)$.

Assume $\forall xP(x)\to \exists xQ(x)$. Either $\forall xP(x)$ or $\exists x\neg P(x)$. In the first case $\exists xQ(x)$, i.e. $Q(x_0)$ for some $x_0$ and then $P(x_0)\to Q(x_0)$. In the second case $\neg P(x_1)$ for some $x_1$ and then $P(x_1)\to Q(x_1)$. Thus in both cases $(\exists x)(P(x)\to Q(x))$.