Counterexample to an Equivalence 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. 
 A: 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$.
A: 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.
