1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ What you did is fine. $\endgroup$ – Brian M. Scott Mar 7 '15 at 21:30
0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Since both expressions contain $\exists x Q(x)$, it doesn't help if $Q(x)$ is true for some x as both expressions are then true. I want a counterexample that shows one expression is true and the other is false. Therefore, we must assume $Q(x)$ is false for all x. $\endgroup$ – John Mar 7 '15 at 19:25
  • $\begingroup$ Agreed, its just less clear. The equivalence moves should be enough. $\endgroup$ – Jonny Mar 8 '15 at 17:25

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.