2
$\begingroup$

I am trying to show that the following are not logically equivalent (according to a practice question)

$\exists x \forall y (P(y) \implies Q(x))$ and $\forall y P(y) \implies \exists x Q(x)$

In the first case I am trying to find some kind of statement where $x,y$ are integers (something like $P(x)$ is the is even predicate and $Q(x)$ is odd predicate, or maybe that $Q(x)$ implies $x$ divides $y$).

I am imagining I need a scenario where one statement is True implies False, and the other is True, for the same values of $x,y$.

If $\forall y P(y)$ is false, then both implications will be true, so suppose that $\forall y$ P(y) is true. I'm not sure how to proceed from here. Hints/Clarifications appreciated.

$\endgroup$
4
  • $\begingroup$ why are both sides true when $\forall y P(y)$ is false? $\endgroup$ – supinf Jan 20 at 18:25
  • $\begingroup$ @supinf I meant both implications. $\endgroup$ – IntegrateThis Jan 20 at 18:27
  • $\begingroup$ I still do not understand it. $\endgroup$ – supinf Jan 20 at 18:28
  • 1
    $\begingroup$ @supinf for the statement on the right, it would imply False -> Something is True. For the first statement, it would be exists an x, for all y (P(y)=False -> Q(x)) which is also true? Maybe I am confused. $\endgroup$ – IntegrateThis Jan 20 at 18:30
1
$\begingroup$

hint 1:

Your statement, that the first statement is true if $\forall y P(y)$ is false, was a mistake. In your comment it seems like you thought that if $\forall yP(y)$ does not hold, then $P(y)$ is always false. It can also happen that $P(y)$ is false for some $y$ and true for some $y$.

You actually should assume, that $\forall y P(y)$ is false, but there is an $y$ such that $P(y)$ is true.

hint 2:

Consider the two cases for $\exists x Q(x)$. What happens if it is false? what if it is true?

$\endgroup$
1
  • $\begingroup$ I have added my own overall answer, if you could check its correctness that would be appreciated. $\endgroup$ – IntegrateThis Jan 21 at 4:08
0
$\begingroup$

With false and true respectively $0$ and $1$, the statements are$$\max_yP(y)\le\max_xQ(x)$$ and$$\min_yP(y)=1\implies\max_xQ(x)=1.$$These statements differ in truth value if$$\min_yP(y)=0,\,\max_yP(y)=1,\,\max_xQ(x)=0.$$

$\endgroup$
0
$\begingroup$

As per supinf's hints. How about this argument:

Suppose that $\exists y$ such that $P(y)$ is true, but $\forall y P(y)$ is false. Also suppose that $Q(x)$ is false for any $x$.

Then the first logical statement is false since for such a $y$ where $P(y)$ is true, we would have there exists an $x$ such that $P(y) \implies Q(x)$ is true, which is false, and so the overall statement is false.

For the second statement, since the premise $\forall y P(y)$ is false, then the statement is vacuously true. Hence the statements aren't equivalent.

$\endgroup$
1
  • $\begingroup$ This is correct. Alternatively, you could also use concrete statements for $P$ and $Q$ to show that the implications are not equivalent. $\endgroup$ – supinf Jan 21 at 8:47

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.