Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
2  
WHat is the theory of a pair of real closed fields? –  Mariano Suárez-Alvarez Aug 4 '10 at 1:24
    
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. –  Artem Chernikov Aug 4 '10 at 10:10
    
Thanks ! –  Mariano Suárez-Alvarez Aug 5 '10 at 2:22
add comment

3 Answers

up vote 5 down vote accepted

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.

share|improve this answer
    
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. –  Artem Chernikov Aug 4 '10 at 10:44
1  
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. –  Dave Marker Aug 4 '10 at 11:59
    
ups, of course. Thanks! –  Artem Chernikov Aug 4 '10 at 19:17
add comment

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.

share|improve this answer
4  
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$. –  Dave Marker Aug 4 '10 at 0:48
    
Right, thanks! And it can be modified to have a finite language as well, so no "general nonsense" argument gives an example I want. –  Artem Chernikov Aug 4 '10 at 10:18
    
D'oh! Yeah, it is necessary that the $c_i$ be distinct. Missed that at first. –  Noah S Aug 4 '10 at 10:35
add comment

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.

share|improve this answer
1  
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.) –  Stefan Geschke Aug 3 '10 at 23:01
    
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. –  Artem Chernikov Aug 3 '10 at 23:15
add comment

Your Answer

 
discard

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.