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

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?

• What means "/="? Is it "$\ne$"? – user 59363 Nov 25 '14 at 23:44
• 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). – user 59363 Nov 25 '14 at 23:47
• @user59363 Yes, excuse the formatting- it did not look like that when I posted. – User38 Nov 25 '14 at 23:50
• @User38 Your reading of (1) is incorrect. – Thomas Andrews Nov 25 '14 at 23:53
• @ThomasAndrews thanks, I see that now. – User38 Nov 26 '14 at 0:00

## 2 Answers

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.

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

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.

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