2
$\begingroup$

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).

$\endgroup$
1
  • $\begingroup$ as soon as you have unbounded quantification you are very likely to go above decidable structures. $\endgroup$
    – Kaveh
    Sep 11 '11 at 23:00
5
$\begingroup$

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".

$\endgroup$
1
  • $\begingroup$ Very nice! I did not expect the $R$ relation to be that simple. $\endgroup$ Sep 9 '11 at 1:57
2
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ $\exists y. x R y$ has a free variable, so its truth value is not defined. $\endgroup$ Sep 8 '11 at 20:22
  • $\begingroup$ 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). $\endgroup$ Sep 8 '11 at 20:25
  • $\begingroup$ 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$. $\endgroup$ Sep 8 '11 at 20:30
  • $\begingroup$ $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? $\endgroup$ Sep 8 '11 at 20:39
  • $\begingroup$ Easy, given a closed formula, determine whether it's true or not (there are countably many closed formulas). This is what OP asks, imho. $\endgroup$ Sep 8 '11 at 20:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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