3
$\begingroup$

Is $\exists x P(x) \implies \exists x Q(x)$ Logical equivalent to $\exists x [P(x) \implies Q(x)]$?

My intuition: Let Left hand side be $\exists x P(x) \implies \exists x Q(x)$ and Right hand side be $\exists x [P(x) \implies Q(x)]$. Say left hand side is true. If say for some x, P(x) and Q(x) values be as follows:-

      P(x)   Q(x)

(x=1) True   False

(x=2) False  True

For these values, left hand side becomes true(since true $\implies$ true) and right hand side becomes true.

I am not able to visualize any other way to disprove them. I know that right hand side is not logically implying left hand side. Please clarify.

Other way I thought was

Left hand side :- If some for x P(x) is true then for another x (say)Q(x) is true. Using this, Right hand side becomes:- If for some $x$(say $x=1$) $P(x)$ is true (from above), then for same $x=1$ $Q(x)$ need not be true (say if false), then right hand side may become false. Here I can say that left hand side do not imply right hand side.

For this type of problems how to think fast? (say another example, $[\forall x P(x) \implies \forall x Q(x)] $ logically imply $\forall x [P(x) \implies Q(x)]$

$\endgroup$
3
  • $\begingroup$ Sir any 1 pls reply. I am a beginner and struggling to understand things. Thanks $\endgroup$ – Nascimento de Cos Aug 4 '19 at 18:50
  • $\begingroup$ Have some patience. By the time of your writing your comment, your post has been up for less than an hour. It is completely normal that it can take days for someone to reply, and getting no replies at all is not any unusual either. Remember that people here are doing this for free, users don't get a penny for the time they need to invest helping you. $\endgroup$ – lemontree Aug 4 '19 at 19:29
  • $\begingroup$ @lemontree sorry sir, i persuaded as tomorrow i have continuation class. Your detailed post is really helpful. I am going thru it... $\endgroup$ – Nascimento de Cos Aug 4 '19 at 19:36
4
$\begingroup$

To prove that two formulas $\phi$ and $\psi$ are logically equivalent, you need to show that 1) $\phi$ logically entails $\psi$ and that 2) $\psi$ logically entails $\phi$.
To show that some formula $\phi$ entails some formula $\psi$, you need to show that all structures where $\phi$ is true $\psi$ is true as well, that is, that there is no situation where $\phi$ is true but $\psi$ false.

To show that two formulas are not equivalent, you need to show that at least one of the entailment directions does not hold.
To show that one formula does not entail the other, you need to show that there is at least one structure in which the first formula is true but the second is not.

The first thing for you to find out is whether or not the two formulas actually are logically equivalent. To make things shorter, I'll just spoiler you that they are not.

So in order to prove that the two formulas are not equivalent, we need to show that one of the entailment directions doesn't hold, i.e. either

  • $∃xP(x)⟹∃xQ(x)$ does not entail $∃x[P(x)⟹Q(x)]$,
    i.e. there is at least one structure where $∃xP(x)⟹∃xQ(x)$ is true but $∃x[P(x)⟹Q(x)]$ false

or

  • $∃x[P(x)⟹Q(x)]$ does not entail $∃xP(x)⟹∃xQ(x)$,
    i.e. there is at least one structure where $∃x[P(x)⟹Q(x)]$ is true but $∃xP(x)⟹∃xQ(x)$ false.

Let's pick the second option. We need to find a structure in which $∃x[P(x)⟹Q(x)]$ is true but $∃xP(x)⟹∃xQ(x)$ false. It suffices to find one such counterexample and we showed that the entailment, and hence the logical equivalence, does not hold in general. Let's assume a simple structure with two elements $\{a, b\}$, and an interpretation such that $P$ is true of $a$ but not $b$, and $Q$ is false for both $a$ and $b$:

     P(x)  Q(x)
x=a  true  false
x=b  false false

You were already pretty close with your approach. The only thing you need to change is to make $Q$ false of the second element, so $\exists x Q(x)$ and thereby $∃xP(x)⟹∃xQ(x)$ becomes false, while $\exists x P(x)$ is still true.
Now since for the element $b$ we have that $P(b)$ and $Q(b)$ are both false, then by the truth table of $⟹$, the implication $P(x)⟹Q(x)$ is true for that element $b$, and since we found an element $x$ that fulfills the inner formula, we can establish $∃x[P(x)⟹Q(x)]$ is also true.
Now we know that $∃x[P(x)⟹Q(x)]$ is true and we need to show that $∃xP(x)⟹∃xQ(x)$ is false. (Reminder: This is because we want to show that from $∃xP(x)⟹∃xQ(x)$ being true it doesn't necessarily follow that $∃x[P(x)⟹Q(x)]$ is true, so we need to find one assignment which is a counterexample to the validity of the entailment.)
Remember that we assumed that there is at least one element of which $P(x)$ holds -- here we called that element $a$ -- but that $Q$ is false for every element. Now with $a$ we found an element $x$ such that $P(x)$ is true, so $\exists P(x)$ is true, but there is no $x$ with $Q(x)$, so $\exists x Q(x)$ is false. Now we have that the left-hand-side of the implication is true but the right-hand side is false. By the truth table of implication, this makes the statement $∃xP(x)⟹∃xQ(x)$ false.
So we found an interpretation under which $∃x[P(x)⟹Q(x)]$ is true but $∃xP(x)⟹∃xQ(x)$ is false. So $∃x[P(x)⟹Q(x)]$ does not logically entail $∃xP(x)⟹∃xQ(x)$. Hence, the two formulas can not be equivalent.

TL;DR: To prove that two formulas are not equivalent, you need to show that either the one doesn't entail the other or the other doesn't entail the one. To show that an entailment does not hold, you need to find a structure where the first formula is true but the second one is not. To show that an implication is false, you need to show that the left-hand side is true but the right-hand side is false.
If the two formulas were indeed equivalent, you would need to show that they logically entail each other, i.e. you'd need to argue that no matter the structure, if one formula is true, then the other must be true as well and vice versa.

$\endgroup$
3
  • $\begingroup$ So nice of you sir, so detailed and neat. Thank you $\endgroup$ – Nascimento de Cos Aug 4 '19 at 20:16
  • $\begingroup$ It's "Ma'am" in my case, not "Sir" - or just "lemontree"... You're welcome. $\endgroup$ – lemontree Aug 4 '19 at 20:27
  • $\begingroup$ Ok, got it madam :) $\endgroup$ – Nascimento de Cos Aug 4 '19 at 20:45
1
$\begingroup$

Note that if $\exists x Q(x)$ both statements are true, and otherwise they're both true iff $\neg\exists xP(x)$ and both false iff $\exists xP(x)\land\forall xP(x)$. That just leaves the case where some but not all $x$ satisfy $P(x)$, whence the first statement is false but the second true.

$\endgroup$
1
$\begingroup$

The following statements are equivalent: $$ \exists x \big(P(x) \Rightarrow Q(x)\big) \\ \exists x \big(\lnot P(x) \lor Q(x)\big) \\ \big( \exists x\; \lnot P(x) \big) \lor \big( \exists x\; Q(x)\big) \\ \big( \lnot \forall x P(x) \big) \lor \big( \exists x\; Q(x)\big) \\ \big( \forall x P(x) \big) \Rightarrow \big( \exists x\; Q(x)\big) \\ $$ So $\exists x \big(P(x) \Rightarrow Q(x)\big) $ is equivalent with $ \big( \forall x P(x) \big) \Rightarrow \big( \exists x\; Q(x)\big) $.

Noticing that it's easy to find an example that shows that it's not equivalent with $ \big( \exists x P(x) \big) \Rightarrow \big( \exists x\; Q(x)\big) $. We need $P(x)$ and $Q(x)$ such that $$ \exists x\; P(x) \qquad \text{is true}$$ $$ \forall x\; P(x) \qquad \text{is false}$$ $$ \exists x\; Q(x) \qquad \text{is false}$$ then $$ \big( \exists x P(x) \big) \Rightarrow \big( \exists x\; Q(x)\big) \quad \text{is false} $$ but $$ \exists x\; \big(P(x) \Rightarrow Q(x)\big) \quad \text{and} \quad \big( \forall x\; P(x) \big) \Rightarrow \big( \exists x\; Q(x)\big) \quad \text{are true} $$

$\endgroup$
3
  • $\begingroup$ sir in line 2, is P=>Q is NOT P or Q? $\endgroup$ – Nascimento de Cos Aug 4 '19 at 20:05
  • $\begingroup$ @NascimentodeCos Yes, I've also noticed it and corrected it $\endgroup$ – Adam Latosiński Aug 4 '19 at 20:06
  • $\begingroup$ Thank you sir. Understood. $\endgroup$ – Nascimento de Cos Aug 4 '19 at 20:17

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.