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

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.

• I think it is true in any interpretation. – pointer May 29 '15 at 16:19
• user121270 is right. Are you sure your sentence has $\rightarrow$ rather than $\leftrightarrow$? (If so, I will undelete my answer to the wrong question $\ddot{\smile}$.) – Rob Arthan May 29 '15 at 16:39
• I've edited the question since I've firstly thought that the sentence is false for some model. – MathNerd May 29 '15 at 16:40
• Here's a proof in natural deduction. – Git Gud May 29 '15 at 16:41
• With $\rightarrow$, it's true, so you should work on proving it. – Rob Arthan May 29 '15 at 16:41

## 1 Answer

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