Prove or disprove wether the sentence $\exists x\forall y Q(x,y)\to \forall y\exists x Q(x,y)$ is logically true

Question

I got stuck at this problem for some hours:

Determine whether the first-order sentence $\exists x\forall y Q(x,y)\to \forall y\exists x Q(x,y)$ is logically true, where $Q$ is a 2-ary predicate symbol.

If the sentence is logically true then prove it. And if the sentence is false then find a model $\mathcal{M}$ in which the sentence is false, that is, find a model $\mathcal{M}$ in which $$\mathcal{M}\nvDash\exists x\forall y Q(x,y)\to \forall y\exists x Q(x,y)$$

---

I tried the model $M=<\mathbb{N}; Q>$ in which $Q^M=\{(x,y)\in\mathbb{N}^2| x^2=y\}$, and it doesn't worked.

I tried several other models and it doesn't worked too.

Thanks for any hint/help.

Answer 1

You can work out the tableau of the negation of your sentence:

1. $\neg\big(\exists x\forall yQxy\to\forall y\exists xQxy\big)$
2. $\exists x\forall yQxy$ (1)
3. $\neg\forall y\exists xQxy$ (1)
4. $\forall y Qay$ (2)
5. $\exists y\neg\exists xQxy$ (3)
6. $\neg\exists xQxb$ (5)
7. $\forall x\neg Qxb$ (6)
8. $\neg Qab$ (7)
9. $Qab$ (4)
10. $\bot$

The tableau of the negation of the sentence closes, therefore it is valid: $$\vDash\exists x\forall yQxy\to\forall y\exists xQxy$$