Prove that $\{0\}$, $\{ 1 \}$ and $\{ \langle n,n \rangle : n \in N \}$ are definable.

Question

I have the following problem:

The structure $A$ has a bearer $\Bbb{N}$ (the set of natural numbers) and it is for a language with only one non-logical symbol $p$, which is a predicate interpreted like : $\langle n,k,m \rangle \in p^A \leftrightarrow n^2 = km + 1$ . Prove that $\{0\}$, $\{ 1 \}$ and $\{ \langle n,n \rangle : n \in \Bbb{N} \}$ are definable.

I know that in order to prove that $\{0\}$ is definable in the structure $A$, I have to show that I can build with $p$ a formula $\phi$ such that $\phi(n)$ is true for $\{0\}, \{1\}, \{\langle n,n \rangle : n \in \Bbb{N}\}$. I wan't to know if this can be considered a valid solution.

For the first I can say: $\phi(m):= \exists n \forall k (n^2 = km + 1)$

For the second: $\phi(n):= \exists k \exists m (n^2= km + 1)$

How about the third one? Do I substitute two variable with n like $\phi(k,m)$ or something like that. I also can't think of an appropriate formula.

Any help is welcomed. Thanks :)

Answer 1

First of all, you've written your formulas not in terms of $p$. So you should have

• $\phi_1(x)=\exists n\forall k(p(x, n, k))$

and

• $\phi_2(x)=\exists k\exists m(p(m, x, k))$

instead of what you've written (note that I'm introducing a new variable, $x$, here - there's no real need to do this, but I think it makes things easier to read).

But your ideas are right. EDIT: As Rob Arthan pointed out, there's actually a problem with $\phi_2$; you need to use $\phi_1$ to fix it . . .

For $S=\{\langle n, n\rangle: n\in\mathbb{N}\}$, think about it this way: how do you know that $x\in S$? Well, $x\in S$ if $x=\langle n, n\rangle$ for some $n$. Do you see how to phrase this appropriately?

Answer 2

For the third part try $\phi_3(x, y) \equiv \forall k \forall m (p(x, k, m) \Leftrightarrow p(y, k, m))$. (You will need to use $n^2 -1 = (n + 1) (n - 1)$ to show that if $x$ and $y$ are non-zero and distinct, then there are values of $k$ and $m$ that will distinguish them.)