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).
 A: 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".
A: 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.
