Is $\exists x(P(x) \to Q(x)) \equiv (\exists xP(x) \to \exists xQ(x))$?

Question

My intuition is that this statement is false and here is my proof.

$\exists x(P(x) \to Q(x))$

$\exists x(\lnot P(x) \lor Q(x))$ using logical equivalence.

$\exists x\lnot P(x) \lor \exists x Q(x)$ using distributive properties of $\exists$ over $\lor$.

Assuming Q(x) is always false, we simply need 1 such x where $\lnot P(x)$ is true and that makes the entire statement true. The other expression can be transformed into this:

$\exists xP(x) \to \exists xQ(x)$

$\lnot\exists xP(x) \lor \exists xQ(x)$ using logical equivalence.

$\forall x\lnot P(x) \lor \exists xQ(x)$

If we assume Q(x) is always false, the only thing that makes this true is for all $\lnot P(x)$ to be true. For example, the domain could be all positive integers and $P(x) = x \le 10$. To be complete, let's assume $Q(x) = x \le -10$.

Therefore, the lefthand side of $\exists x(P(x) \to Q(x))$ is true and the righthand side of $(\exists xP(x) \to \exists xQ(x))$ is false.

I'm pretty sure I'm right but I would like another set of eyes to see if I did anything stupid.

Answer 1

Your counterexample is fine.

You might be interested in another slightly more formal approach, written in the style of Dijkstra-Scholten and Gries-Schneider (see also Dijkstra's EWD1300), to find all counterexamples.

$ \newcommand{\calc}{\begin{align} \quad &} \newcommand{\op}[1]{\\ #1 \quad & \quad \unicode{x201c}} \newcommand{\hints}[1]{\mbox{#1} \\ \quad & \quad \phantom{\unicode{x201c}} } \newcommand{\hint}[1]{\mbox{#1} \unicode{x201d} \\ \quad & } \newcommand{\endcalc}{\end{align}} \newcommand{\ref}[1]{\text{(#1)}} \newcommand{\then}{\Rightarrow} \newcommand{\followsfrom}{\Leftarrow} \newcommand{\true}{\text{true}} \newcommand{\false}{\text{false}} $Let's calculate when the two sides are equivalent:

$$\calc \langle \exists x :: P(x) \then Q(x) \rangle \;\equiv\; (\langle \exists x :: P(x) \rangle \then \langle \exists x :: Q(x) \rangle) \op\equiv\hints{write $\;\phi \then \psi\;$ as $\;\lnot \phi \lor \psi\;$, twice}\hint{-- to make manipulations easier} \langle \exists x :: \lnot P(x) \lor Q(x) \rangle \;\equiv\; \lnot \langle \exists x :: P(x) \rangle \lor \langle \exists x :: Q(x) \rangle \op\equiv\hints{$\;\exists\;$ distributes over $\;\lor\;$}\hint{-- because $\;\exists\;$ is a kind of 'repeated disjunction'} \langle \exists x :: \lnot P(x) \rangle \lor \langle \exists :: Q(x) \rangle \;\equiv\; \lnot \langle \exists x :: P(x) \rangle \lor \langle \exists x :: Q(x) \rangle \op\equiv\hint{$\;\lor\;$ distributes over $\;\equiv\;$ -- to simplify} (\langle \exists x :: \lnot P(x) \rangle \equiv \lnot \langle \exists x :: P(x) \rangle) \;\lor\; \langle \exists x :: Q(x) \rangle \op\equiv\hints{DeMorgan on right hand side of $\;\equiv\;$}\hint{-- making both sides more alike} (\langle \exists x :: \lnot P(x) \rangle \equiv \langle \forall x :: \lnot P(x) \rangle) \;\lor\; \langle \exists x :: Q(x) \rangle \op\equiv\hint{split $\;\equiv\;$ into $\;\then\;$ and $\;\followsfrom\;$; $\;\forall\then\exists\;$} (\langle \exists x :: \lnot P(x) \rangle \then \langle \forall x :: \lnot P(x) \rangle) \;\lor\; \langle \exists x :: Q(x) \rangle \op\equiv\hint{write $\;\phi \then \psi\;$ as $\;\lnot \phi \lor \psi\;$} \tag{*} \lnot \langle \exists x :: \lnot P(x) \rangle \;\lor\; \langle \forall x :: \lnot P(x) \rangle \;\lor\; \langle \exists x :: Q(x) \rangle \endcalc$$

So you have a counterexample whenever the negation of $\ref *$ is true: $$ \tag{$\lnot$*} \langle \exists x :: \lnot P(x) \rangle \;\land\; \langle \exists x :: P(x) \rangle \;\land\; \langle \forall x :: \lnot Q(x) \rangle $$ In other words, a counterexample is any $\;P(x)\;$ which is true for some $\;x\;$ and false for some other, together with any $\;Q(x)\;$ which is always false.

Answer 2

I would leave out the assuming Qx is always false and stick with the logical equivalence moves.

The first statement is equivalent to $\neg\forall x P(x) \lor \exists x Q(x)$, while the second statement is equivalent to $\forall x \neg P(x) \lor \exists x Q(x)$

From here all you need is a counter example... recall that statements are logically equivalent if their truth is evaluated to be the same in every model. So we need a structure where one statement is true and the other is false. Perhaps we are in the universe of natural numbers and let P mean x is prime and Q means x is the largest number.

Answer 3

You know two things, as Jonny pointed out:

• $\exists x(P(x)\to Q(x))\equiv \neg\forall xP(x)\lor\exists x Q(x)\equiv\exists x\neg P(x)\lor\exists xQ(x)$
• $\exists xP(x)\to \exists xQ(x)\equiv\forall x\neg P(x)\lor\exists x Q(x)$

Hence, in our attempt to create a counterexample, we are really concerned with whether or not $\exists x\neg P(x)\equiv\forall x\neg P(x)$. This should be pretty easy to invalidate.

Counterexample: Let the universe be the natural numbers. Let $Q(x)$ and $P(x)$ be the following:

• $Q(x) : x$ is both prime and not prime.
• $P(x) : x$ is not an even prime number.

Well, $Q(x)$ is clearly always false. Now, $\exists x\neg P(x)$ is true because there does exist an even prime number, namely $2$. However, $\forall x\neg P(x)$ is clearly not true, for $2$ is the only even prime number. Thus, we can see that $\exists x\neg P(x) \not\equiv\forall\neg P(x)$, thus effectively showing that $$\exists x(P(x)\to Q(x))\not\equiv \exists xP(x)\to \exists xQ(x).$$