# Definable relations in given structure (first order logic)

I'm bothering with this problem. I'm given a first order predicate language with only one ternary predicate symbol $p$ (no equality sign). Also there is structure for the language $\mathcal{A}$ over $\mathbb{N}$ ($0 \in \mathbb{N}$), where $p(x,y,z) \leftrightarrow x+y+1 = z$. The problem is to prove that the set $M = \{ (a,b) \in \mathbb{N} \times \mathbb{N} : a \leq b\}$ is definable in $\mathcal{A}$. I feel that the set $N = \{(a, b) \in \mathbb{N} \times \mathbb{N} : a < b\}$ is definable by the formula $\psi = \exists x \ p(x,y,z)$. However I don't know how to prove it and how to switch to the set $M$. I was thinking of $\neg \psi$, but I guess it will define the set $\{(a,b) \in \mathbb{N} \times \mathbb{N} : a \geq b\}$. Any help?

You are correct that $\exists x: p(x,y,z)$ defines $N = \{(a,b): a < b\}$, since $0 \in \Bbb N$. In order to prove this, you demonstrate (to a satisfactory level of detail) that the conditions $\exists x: p(x, a, b)$ and $a < b$ are equivalent.
Now what do you know about $a, b \in \Bbb N$ if $a \not< b$ and $b \not< a$?
• Ah you mean that I can simulate the equality like this $\neg \exists x \ p(x, y, z) \wedge \neg \exists x \ p(x, z, y)$ ? – brick Jan 6 '15 at 20:18
• @brick Yes, presuming you meant to write $\neg \exists x: p(x,y,z) \lor p(x,z,y)$ or $\neg \exists x: p(x,y,z) \land \neg \exists x: p(x,z,y)$. – Lord_Farin Jan 6 '15 at 20:20
• OK, thanks a lot! One more question. If $\psi = \neg \exists x : p(x,y,z)$ defines $\{ (a, b) : a < b\}$ can I use the same formula for defining $\{ (a, b) : a > b \}$. I mean that it is the same formula except that the variables are taken in the other order. Or it is the case that $1$ formula defines only one set? – brick Jan 6 '15 at 20:29
• @brick Interchanging the variables gives a different formula, which indeed has the desired property for defining $a > b$. So $\neg \exists x: p(x,b,a)$ works for $M$ as well. – Lord_Farin Jan 6 '15 at 20:59