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).
Undecidable countable structure built on decidable relation?
-
0as soon as you have unbounded quantification you are very likely to go above decidable structures. – 2011-09-11
2 Answers
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".
-
0Very nice! I did not expect the $R$ relation to be that simple. – 2011-09-09
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.
-
0$\exists y. x R y$ has a free variable, so its truth value is not defined. – 2011-09-08
-
0It 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). – 2011-09-08
-
0That 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$. – 2011-09-08
-
0$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? – 2011-09-08
-
0Easy, given a closed formula, determine whether it's true or not (there are countably many closed formulas). This is what OP asks, imho. – 2011-09-08
-
0Okay, that's a reasonable interpretation of the question. – 2011-09-08