# Decidability survives new constants

Let $L$ be a finite first order language and let $M$ be an $L$-structure with universe $\mathbb{N}$ that interprets all $L$-symbols as recursive sets (so $M$ is a recursive $L$-structure).

Let $L(c)$ be the extension of $L$ by a new constant symbol $c$, let $n\in \mathbb{N}$ and let $(M,n)$ be the expansion of $M$ to an $L(c)$-structure that interprets $c$ by $n$.

Question: If $M$ is decidable, is $(M,n)$ decidable, too?

Structures are "decidable" here if the set of sentences of the resp. language that are satisfied in the structure (so, without naming elements of $M$) is recursive.

I assume that this is in general not the case, I even seem to remember that Church gave a counterexample, but I cannot find it again and my memory might play tricks on me. I am actually looking for an answer to this question in the case when $M$ is nearly model complete, so if somebody can comment on that case, that would be much appreciated.

Remarks: By basic recursion/computation theory:

1) The set of $L(c)$-consequences of the $L$-theory of $M$, is decidable.

2) If $M$ has quantifier elimination (in $L$) then the implication holds.

• Remark 2 applies even if $M$ (or even $(M,n)$) is only model complete. Nov 5, 2012 at 15:03
• @Emil, I'm probably being thick, but: why does remark 2 apply if $M$ is model complete? Nov 5, 2012 at 21:28
• Any formula $\phi(x)$ is equivalent to an existential formula $\psi(x)$, and since $M$ is decidable, we can actually compute $\psi$. Then $M\models\phi(n)$ reduces to $M\models\psi(n)$, and as $\psi$ is existential and $M$ is recursive, this makes $\{\phi:M\models\phi(n)\}$ recursively enumerable. However, its complement is also recursively enumerable, as the same argument also applies to $\neg\phi(x)$. Thus, it is decidable. Nov 6, 2012 at 11:16

The answer appears to be negative.

Theorem. There is a computable graph $G$ with a decidable theory and having a vertex $c$ for which the theory of the pointed graph $(G,c)$ is not decidable.

Proof. Let us say that a star is a graph with a center node $c$ and a collection of linear rays extending out from this center node. In other words, it is a connected tree with all vertices having degree either one or two, except the center, which can have higher degree. Let us refer to the linear parts of the graph extending from the center as the rays of the star. Every finite star can be viewed as coding a finite multi-set of natural numbers, the multi-set of the lengths of its rays.

       /
| /
\|/
c

Let $G_0$ be the graph consisting of countably many disjoint copies of every possible finite star, and let $T$ be the theory of $G_0$.

I claim, without much argument, that $T$ is a decidable theory. It seems to me that this theory should eliminate quantifiers down to a collection of extremely basic assertions about the nature of the stars that the variables lie on, assertions like "$x$ is distance at most $10$ from the center of its star, distance at most 28 from the end of its ray, and this star has 4 rays of length $25$ and $12$ but no ray of size $16$," and "$x$ and $y$ are distance at most 5 on a ray of the same star" and so on. If this is correct, then $T$ will be a decidable theory. (Update: Emil has given an elegant argument in the comments showing that $T$ is decidable, because it is c.e. axiomatizable in a natural way and complete.)

Now, let $G$ be the graph by adding to $G_0$ an additional infinite star, with center $c$ and rays of length $n$, for exactly the $n$ in a fixed c.e. non-computable set $K$. A simple compactness argument shows that this new graph still satisfies the theory $T$, since any finite number of such assertions about rays from $c$ are compatible with $G_0$. Furthermore, I claim that $G$ has a computable presentation. This might seem too much at first, since $K$ is not computable, but in fact it is enough that $K$ is merely c.e. To see why, use the odd numbers to make a computable copy of $G_0$. With the even numbers, we use $0$ as the center of the infinite star, and whenever $n$ is enumerated into $K$ at time $t$, then we use the next $n$ available even numbers above $t$ as the nodes to build the ray coming from $0$. In this way, the edge relation becomes computable, since the nodes themselves are big enough numbers to witness whether or not they should be connected or not. Note that unused nodes are simply extra copies of the star with no rays. So ultimately, we've got a computable edge relation on $\mathbb{N}$ making a computable presentation of the desired graph.

So we've got a computable graph $G$ of a decidable theory $T$, but the theory of the pointed graph $(G,c)$, where $c=0$ is the center of the newly added star, is not decidable, since the truth of "there is a ray of length $n$ from $c$" is equivalent to $n\in K$, which is not decidable. QED

(Here is a link to Harizanov's Handbook article on computable model theory, which contains many interesting examples and a highly developed theory.)

• @Joel I mean "without parameters" and added this for clarification in the question. Thanks for the hint Nov 5, 2012 at 15:46
• I see; so in the terminology of computable model theory, what you seem to want is a computable model of a decidable theory realizing a non-computable type. Nov 5, 2012 at 21:02
• @Joel Exactly. And the choice of the definition of "decidable model" in computable model theory indicates that there is such a type. You have a reference in mind? Nov 5, 2012 at 21:45
• Very nice! Here’s a way to prove the decidability of $T$ without explicit quantifier elimination. Let me redefine $T$ as the theory of cycle-free graphs in which no two nodes of degree $\ge3$ are connected, and which contain infinitely many copies of every finite star. It is easy to see that $T$ is recursively axiomatizable, hence it suffices to show that $T$ is complete (this will prove at once that $T$ coincides with the theory of $G_0$, that it is decidable, and that $G\equiv G_0$). I guess there are several possibilities how to show the completeness of $T$. ... Nov 6, 2012 at 17:16
• Quantifier elimination gives more information, though: it seems to me that it actually shows that $T$ is nearly model complete, as Marcus asked for. Nov 6, 2012 at 17:52