1
$\begingroup$

I need to prove or refute the equivalence:

$\forall{x}.(\exists{y}Q(x,y))\rightarrow R(x) \equiv \forall{x}\exists{y}(Q(x,y)\rightarrow R(x)) $

where $x\in\mathbb{N}$ and $Q,R$ are two-place and one-place predicates.

I assume that it is false but I can't find any productive counterexample.

$\endgroup$
  • $\begingroup$ This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level. $\endgroup$ – Carl Mummert Nov 19 '16 at 21:14
  • $\begingroup$ A correct relation is $$\forall x ~ (\exists y ~ Qxy \Rightarrow Rx) \equiv \forall x ~ \forall y ~ (Qxy \Rightarrow Rx)$$ so a counter example requires $\exists y~ Qxy$ and $\forall y ~Qxy$ to be different. $\endgroup$ – DanielV Nov 19 '16 at 22:23
  • $\begingroup$ As others have said, the usual left side would be $\forall{x}.(\exists{y}Q(x,y)\rightarrow R(x)) $, which is a different statement. On the other hand, your version is a well formed formula, so it is a question that can be answered. I answered the question as written. Please check if this is what you intended. $\endgroup$ – Ross Millikan Nov 20 '16 at 16:48
1
$\begingroup$

First, you have a parenthesis in the wrong place for the first expression; it should be: $\forall x \: (\exists y \: Q(x,y) \rightarrow R(x))$

Second, I think you have a hard time finding a counterexample, since the second expression is a rather unusual expression: it contains an existentially quantified conditional, and that almost never represents a statement we would make under normal circumstances. In other words, there is no 'nice' interpretation for that kind of sentence.

Still, as others have pointed out, this second statement can be made true simply by picking something for which $Q(x,y)$ is false, as that will make the conditional true. So, here is a simple way to make this all work: for $Q(x,y)$ pick $x <y$: since for any $x$ there is some $y$ such that $x$ is not smaller than $y$ (in fact, we can always pick $y=0$ (or $y=1$, if you do not consider $0$ part of $N$)), that means that for any $x$ there is some $y$ such that $Q(x,y) \rightarrow R(x)$ is true. Hence, the second expression is true, regardless of what we pick for $R(x)$.

For the first expression, however, note that for any $x$, there is some $y$ such that $x<y$ ($y=x+1$ will do nicely). So this means that for the first expression to be false, all we need to do is pick some $R(x)$ that is not always true, e.g. $R(x)$: $x$ is even. Because with that, we see that the universal statement of the first expression is not true for any odd number. That is, the first expression is false.

Ok, so there is a simple counterexample to the supposed equivalence. But again, you probably couldn't find a counterexample, because you tried to have some kind of interesting and meaningful interaction between $Q(x,y)$ and $R(x)$, but the 'weirdness' of the second expression rules out anything 'interesting and meaningful' in the first place.

$\endgroup$
3
$\begingroup$

For an $x$ where $R(x)$ is true, both sides are true, so our only problem is if $R(x)$ is false. The right side is true if there is any $y$ such that $Q(x,y)$ is false. The left side is only true if there is no $y$ such that $Q(x,y)$ is true. You therefore need there to be some $x$ where $R(x)$ is false and $Q(x,y)$ can be true or false depending on $y$.

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