2
$\begingroup$

Given an undecidable collection of first-order sentences, is there necessarily a complete undecidable theory containing it? A direct attempt to prove it seems to require some control over the completions which need not exist, but I don't see a counterexample.

On a more concrete side, Macyntire proved that the theory of all pairs of real closed fields is undecidable. I am interested to know if there is a particular pair of real closed fields with undecidable theory.

$\endgroup$
2
  • 2
    $\begingroup$ WHat is the theory of a pair of real closed fields? $\endgroup$ Aug 4, 2010 at 1:24
  • $\begingroup$ Dear Mariano, given a real closed field $F$ and a proper elementary extension $G \succ F$ we consider the structure $(G,F)$ in the language of RCF expanded by a new predicate naming F inside G - this is an elementary pair. Now the theory of pairs of real closed fields is an (incomplete) theory satisfied by all such structures, and what I am asking for is to find a particular pair $(G,F)$ such that $Th(G,F)$ is undecidable. $\endgroup$ Aug 4, 2010 at 10:10

3 Answers 3

5
$\begingroup$

My recollection is that Macintyre proved there are $2^{\aleph_0}$ complete theories of pairs $(K,L)$ where $L\subset K$ are real closed fields. This is in his thesis but I don't think he published it anywhere else. There are later papers of Francoise Delon and Walter Bauer that develop this further. On the other hand there is an earlier theorem of Robinson's that if $L\subset K$ are real closed and $L$ is dense in $K$ then the theory of $(K,L)$ is decidable.

$\endgroup$
2
  • $\begingroup$ Dear David, I never looked at Macintyre's thesis myself, but I have an impression that I've heard from Marcus Tressl that undecidability was there. Perhaps I'm mixing credits, because now I found a paper by Bauer proving it. He also has some other decidability results, but it does not seem to answer my question about a particular undecidable pair. $\endgroup$ Aug 4, 2010 at 10:44
  • 1
    $\begingroup$ Artem--If there are $2^{\aleph_0}$ theories of pairs, most are undecidable. My recollection is that his coding was relatively straightforward so one could use it to find explicit undecidable pairs. $\endgroup$ Aug 4, 2010 at 11:59
5
$\begingroup$

Even given Stefan's reformulation, the answer is still "no."

Let $L$ be a language consisting only of countably many constant symbols $c_0$, $c_1$, $c_2$, . . . and a single unary relation symbol $U$. Let $\phi$ be the sentence asserting that $U$ holds of exactly one element in the universe: $\phi\equiv\exists ! x(U(x))$.

Now we just adapt Gabriel's example. Let $A$ be any undecidable set. Let $S=\lbrace\neg U(c_i): i\in A\rbrace$, and let $T$ be the closure of $S\cup\lbrace\phi\rbrace$ under implication. Then $T$ is clearly undecidable. However, any complete extension of $T$ is decidable.

$\endgroup$
3
  • 4
    $\begingroup$ You probably need to add sentences saying the $c_i$ are distinct so that the only completions correspond to saying exactly which $c_i$, if any, is in $U$. $\endgroup$ Aug 4, 2010 at 0:48
  • $\begingroup$ Right, thanks! And it can be modified to have a finite language as well, so no "general nonsense" argument gives an example I want. $\endgroup$ Aug 4, 2010 at 10:18
  • $\begingroup$ D'oh! Yeah, it is necessary that the $c_i$ be distinct. Missed that at first. $\endgroup$ Aug 4, 2010 at 10:35
2
$\begingroup$

A counterexample for the first question:

Assume a language with no predicates, functions or constants. Take an undecidable set $A \subseteq \mathbb{N}$. The set Γ of all sentences whose length is in A is certainly undecidable. However all theories in that language are decidable.

$\endgroup$
2
  • 1
    $\begingroup$ I believe the original question should be rephrased in the light of this example: Given an undecidable theory (closed under implications), is there an undecidable maximally consistent extension over the same vocabulary? (If you are allowed to extend the vocabulary, you can always add the theory of the natural numbers on new symbols.) $\endgroup$ Aug 3, 2010 at 23:01
  • $\begingroup$ Dear Gabriel and Stefan, indeed I was a bit sloppy posing the question. As Gabriel's example shows, one should stick to the Stefan's reformulation (and this is of course what I had in mind). It's the first time I'm using this website, not sure if I should update the original entry or just keep it like this. $\endgroup$ Aug 3, 2010 at 23:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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