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?

up vote 2 down vote accepted

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
  • Oh, looks great! (I like simple formulas) Thanks! – brick Jan 6 '15 at 21:05

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.