1
$\begingroup$

Consider $(\mathbb N, +)$ as a model for the language with one symbol $+$ for a binary function. Are the following statements true?

  1. $(\mathbb N, +) \vDash \forall x \exists y \forall z\ x + y\neq z$
  2. $(\mathbb N, +) \vDash \exists x \forall y \exists z\ x + y\neq z$

I have put true for for both based mainly on intuition. I reasoned that the statements could be translated into English as (1) For any $x$ and $z$ you give me (from the natural numbers) there exists a $y$ such that $x + y\neq z$. Which I think is true. For the second one, I interpreted as for any y you give me, there exists an x and z such that $x + y\neq z$ is true, which I think is true as well. Is this the correct way to approach the problem?

$\endgroup$
  • $\begingroup$ What means "/="? Is it "$\ne$"? $\endgroup$ – user 59363 Nov 25 '14 at 23:44
  • $\begingroup$ Your English transcription of (1) is basically of a sentence starting with $\forall x\ \forall z\ \exists y\dots$ which was not what you did express in formal language (see also the answer below). $\endgroup$ – user 59363 Nov 25 '14 at 23:47
  • $\begingroup$ @user59363 Yes, excuse the formatting- it did not look like that when I posted. $\endgroup$ – User38 Nov 25 '14 at 23:50
  • $\begingroup$ @User38 Your reading of (1) is incorrect. $\endgroup$ – Thomas Andrews Nov 25 '14 at 23:53
  • $\begingroup$ @ThomasAndrews thanks, I see that now. $\endgroup$ – User38 Nov 26 '14 at 0:00
1
$\begingroup$

Order of quantifiers matters! We claim that the first statement is false. To see this, we will prove its negation, namely: $$ (\mathbb N, +) \models \exists x \, \forall y \, \exists z \, [x + y = z] $$ Let $x = 3 \in \mathbb N$. Given any $y \in \mathbb N$, let $z = 3 +y \in \mathbb N$. Then $x + y = 3 + y = z$, as desired.


The second statement is true. Let $x = 3 \in \mathbb N$. Given any $y \in \mathbb N$, let $z = 4 + y \in \mathbb N$. Then $x + y = 3 + y \neq 4 + y = z$, as desired.

$\endgroup$
  • 1
    $\begingroup$ Ohhh ok. That makes way more sense, I read it in the wrong order. Appreciate the proofs! $\endgroup$ – User38 Nov 25 '14 at 23:58
1
$\begingroup$

The first is false. It says that for any natural number $x$, there is a natural number $y$ such that $x+y$ is not a natural number (for all natural numbers $z$, $x+y$ differs from $z$). Note that in your explication of the sentence, you implicitly read $\exists y\forall z$ as $\forall z\exists y$.

Now perhaps you can deal with the second.

$\endgroup$
  • $\begingroup$ Nice catch. I definitely read it wrong and that cleared it up nicely. $\endgroup$ – User38 Nov 25 '14 at 23:53

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.