Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
as soon as you have unbounded quantification you are very likely to go above decidable structures. – Kaveh Sep 11 '11 at 23:00
up vote 5 down vote accepted

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

share|cite|improve this answer
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.

share|cite|improve this answer
$\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
Easy, given a closed formula, determine whether it's true or not (there are countably many closed formulas). This is what OP asks, imho. – Levon Haykazyan Sep 8 '11 at 20:53

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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