1
$\begingroup$

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.

$\endgroup$
6
  • 2
    $\begingroup$ I think it is true in any interpretation. $\endgroup$ – pointer May 29 '15 at 16:19
  • $\begingroup$ 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}$.) $\endgroup$ – Rob Arthan May 29 '15 at 16:39
  • $\begingroup$ I've edited the question since I've firstly thought that the sentence is false for some model. $\endgroup$ – MathNerd May 29 '15 at 16:40
  • $\begingroup$ Here's a proof in natural deduction. $\endgroup$ – Git Gud May 29 '15 at 16:41
  • $\begingroup$ With $\rightarrow$, it's true, so you should work on proving it. $\endgroup$ – Rob Arthan May 29 '15 at 16:41
2
$\begingroup$

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

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