Quantifiers, predicates, logical equivalence

Question

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?

Answer 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.

Answer 2

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.

Answer 3

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

Answer 4

We can think about $P$ and $Q$ as subsets of the universe (an arbitrary universe), which we shall denote as $U$. This is somewhat of a semantic analysis of the sentences, which can be enlightening.

The first sentence says that either $P\neq U$ or $P\cap Q\neq\varnothing$.

The second says that if $P=U$ then $Q\neq\varnothing$.

---

Now we analyze whether or not these two sentences are equivalent or not.

If $P=U$ and $Q\neq\varnothing$ (the second sentence holds) then clearly $P\cap Q\neq\varnothing$, so the first sentence holds. On the other hand if $P\neq U$ then the second sentence is automatically true, and we have some $x$ such that $P(x)$ is false, and so the first sentence is also true.

The same arguments also tell us that if the first sentence holds then the second one holds as well, in one case vacuously and in another case less vacuously.