12
$\begingroup$

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?

|cite|improve this question
$\endgroup$
6
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • 2
    $\begingroup$ In general, if you suspect that two statements are not equivalent, try to come up with an interpretation which makes explicit that one can be true while the other is false. If that doesn't seem to be working, then consider that the statements might indeed be equivalent. To show equivalence, see the answer above as to how to prove it. Implications can be proven directly, or indirectly. Note that to show logical equivalence, it is not enough to find an interpretation in which both are true or both are false, since a logical equivalence must hold whatever the interpretation. $\endgroup$ – Namaste Jan 30 '13 at 17:26
  • $\begingroup$ In "Now suppose $\forall x P(x)$. Then clearly $P(x_0)$", (2nd line in (1)-->(2)), what does the quantifier range over? What if there aren't any $x$? $\endgroup$ – alancalvitti Jan 30 '13 at 17:40
  • $\begingroup$ @alancalvitti Then the implication is vacuously true. $\endgroup$ – Namaste Jan 30 '13 at 17:44
  • $\begingroup$ Ok thanks for edit. Terminology/notation Q: why do you say " implication" ($\implies$)? Isn't "$\forall x P(x) \rightarrow \exists x Q(x)$ also an implication? If so why 2 different arrow styles? $\endgroup$ – alancalvitti Jan 30 '13 at 18:47
  • 1
    $\begingroup$ If there are no x such that $P(x)$ is true, (i.e., for all $x$ (if $P(x)$ then $Q(x)$) if there is no $x$ satisfying $P(x)$, then (false) --> implies anything, including statement $\exists x Q(x)$, and whenever the righthand side of $\rightarrow$ (the consequent) is true, the entire implication is true. Which means all of $(2)$ is true, since the right-hand side of $\implies$ is true. It referred to as being "vacuously true". $\endgroup$ – Namaste Jan 30 '13 at 22:42
6
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ It took this alternative perspective for me to make sense of the logical equivalence. +1 $\endgroup$ – The Room May 29 '18 at 13:45
5
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Nice hints, helpful+1 $\endgroup$ – Namaste Jan 31 '13 at 0:11
4
$\begingroup$

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

|cite|improve this answer
$\endgroup$
3
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Excellent explanation; exactly what I was hoping for. Thank you! $\endgroup$ – suitegamer Jan 30 '13 at 23:34
  • $\begingroup$ @suitegamer: Thanks. I need the practice. My students have an exam soon, and tomorrow my office hours will be swamped by similar questions... Even more since we often ask them to give such semantical analysis and not just a formal proof. $\endgroup$ – Asaf Karagila♦ Jan 30 '13 at 23:36
  • $\begingroup$ +1 for the different, but helpful, take on the question! :-) $\endgroup$ – Namaste Jan 31 '13 at 0:29
2
$\begingroup$

Yet another way to do this is with the method of analytic tableaux. It's a systematic search for contradictions, so we assume the negation of $$(\exists x(Px\to Qx))\leftrightarrow (\forall xPx\to\exists xQx)\tag{1}$$ and show that no matter what we do, we end up with a contradiction; look:

enter image description here.

Can you spot the contradictions?

From left to right: $\neg Pa$ with $Pa$, $\neg Qa$ with $Qa$, $\neg Pb$ with $Pb$, and $\neg Qc$ with $Qc$.

Hence $(1)$ is indeed an equivalence.

This method is explained in detail in M. D'Agostino's Handbook of Tableau Methods.

|cite|improve this answer
$\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.