Prove or disprove validity: $(\forall x \exists y (P(x) \supset Q(y))) \supset(\exists y \forall x (P (x) \supset Q(y)))$ I have working on this formula $(\forall x \exists y (P(x) \supset Q(y))) \supset (\exists y \forall x (P (x) \supset Q(y)))$ to either prove or disprove it.
First, I tempted to disprove it, but I changed my mind.
I wrote down "for all x that there exists some y satisfies corresponding condition", and "there exists some y that for all x satisfies corresponding condition." I think these statements refer to the same idea.
Any suggestions?
 A: In the usual context of nonempty structures, the statement is valid, meaning that it is true in all models. One way to see this is that if there is any $y$ in the structure for which $Q(y)$ holds, then the statement is true, since we may always choose that $y$, and this will make $Q(y)$ true and hence the final implication true, regardless of any $x$, and so the whole implication is true.  Otherwise, we are in the case where $Q(y)$ is always false, in which case $P(x)\to Q(y)$ is logically equivalent to $\neg P(x)$, and so the quantification over $y$ becomes irrelevent (provided the structure is nonempty). So again the statement is true. So the statement is true in any nonempty structure. 
Edit. Meanwhile, in the context of first-order logic allowing the empty structure (which is a bit unusual, and which is only possible if your language has no constant symbols), then the statement is not valid, since it is false in the empty structure. This is because all universal statements hold vacuously in the empty structure and all existential statements fail in the empty structure, so the antecedent is true and the conclusion is false, and so the implication fails in the empty structure.  
Conclusion: your statement is valid if the language has constant symbols; valid if your logic disallows the empty structure; but otherwise it is not valid.
A: $(\forall x \exists y (P(x) \supset Q(y))) \supset (\exists y \forall x (P(x) \supset Q(y)))$
The formula is not valid. Consider the following idea:
$P^M$ is the relation that {x : x moves first}
$Q^M$ is the relation that {x : x wins the game}
For the left part of implication $(\forall x \exists y (P(x) \supset Q(y)))$ it indicates that for all $x$ making the first move, there exists some $y$ that wins the game. However, considering right part of implication $(\exists y \forall x (P(x) \supset Q(y)))$ there exists some $y$ that beats all first moves of $x$. This is obviously different and harder than the left part of implication, which can be false while first part is true so that makes the theory false. The idea is from this page.
