# Undecidable countable structure built on decidable relation?

My question is, is there a relation $R$ on the integers that's decidable (i.e. the function ${\mathbb Z}^2 \to \lbrace \text{true},\text{false} \rbrace, \ (i,j) \mapsto i R j$ is computable) , but such that the structure ${\mathfrak A}=(\mathbb{Z},R)$ is undecidable, in the sense that the "truth value" function of a formula $\phi$ of ${\mathfrak A}$ is not computable? (a formula $\phi$ of ${\mathfrak A}$ is a meaningful sequence of quantifiers $\forall,\exists$, of logical connectives $\Rightarrow, \vee, \wedge$, of any number of variables $x_1, \ldots x_n$, and the $R$ symbol, of course).

-
as soon as you have unbounded quantification you are very likely to go above decidable structures. –  Kaveh Sep 11 '11 at 23:00

Yes, the point is that $(V_\omega,\in)$ is bi-interpretable with $({\mathbb N},+,\times,0,1,<)$, which has undecidable theory. (Although this bi-interpretability is a stronger claim than what you are asking or what I sketch below.)

Fix a recursive bijection between ${\mathbb N}$ and ${\mathbb Z}$, so it is enough to define such an $R$ on ${\mathbb N}$. Set $iRj$ iff there is a 1 in the $i$-th place (from right to left) in the binary representation of $j$. Then $({\mathbb N},R)$ is isomorphic to $(V_{\omega},\in)$ where as usual $V_\omega=\bigcup_n V_n$, with $V_0=\emptyset$ and $V_{n+1}={\mathcal P}(V_n)$ for all $n$.

Clearly $R$ is decidable. On the other hand, any statement about $({\mathbb N},+,\times,0,1,<)$ can be translated as a statement about $(V_\omega,\in)$, as $\omega$ and the arithmetic operations on $\omega$ are definable in terms of $\in$.

I assume you know why $({\mathbb N},+,\times,0,1,<)$ has undecidable theory. To drive the point home, you may take as $\phi$ the translation of the statement "PA is consistent".

-
Very nice! I did not expect the $R$ relation to be that simple. –  Ewan Delanoy Sep 9 '11 at 1:57
Yes, take for example $iRj$ for "Turing machine number $i$ halts in less than $j$ steps when started on an empty tape". Then $\phi(x) = \exists y. xRy$ is undecidable.
$\exists y. x R y$ has a free variable, so its truth value is not defined. –  Levon Haykazyan Sep 8 '11 at 20:22
It is a unary predicate, with a well defined truth value for every $x$. It makes little sense to speak of whether any single truth value is computable or not -- it always is, either by the program that simply outputs the constant "true" or by the program that simply outputs the constant "false". (We may not know which of these programs is the right one, but one of them will certainly be). –  Henning Makholm Sep 8 '11 at 20:25
That was my point, constants are not part of the language, so you can't form formulas $\exists y. \bar x R y$ for $x \in \mathbb Z$. –  Levon Haykazyan Sep 8 '11 at 20:30
$x$ is not a constant, is is a parameter. The undecidable problem is, given $x$ as an input, to decide whether $x$ satisfies the predicate. How would you state any nontrivial decision problem without having a free variable? –  Henning Makholm Sep 8 '11 at 20:39