Undecidable completion of undecidable theory, and pairs of RCF - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T13:46:12Z http://mathoverflow.net/feeds/question/34446 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/34446/undecidable-completion-of-undecidable-theory-and-pairs-of-rcf Undecidable completion of undecidable theory, and pairs of RCF Artem Chernikov 2010-08-03T22:27:51Z 2010-08-04T01:46:03Z <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/34446/undecidable-completion-of-undecidable-theory-and-pairs-of-rcf/34448#34448 Answer by Gabriel Ebner for Undecidable completion of undecidable theory, and pairs of RCF Gabriel Ebner 2010-08-03T22:50:43Z 2010-08-03T22:50:43Z <p>A counterexample for the first question:</p> <p>Assume a language with no predicates, functions or constants. Take an undecidable set <code>$A \subseteq \mathbb{N}$</code>. The set &Gamma; of all sentences whose length is in A is certainly undecidable. However all theories in that language are decidable.</p> http://mathoverflow.net/questions/34446/undecidable-completion-of-undecidable-theory-and-pairs-of-rcf/34456#34456 Answer by Noah S for Undecidable completion of undecidable theory, and pairs of RCF Noah S 2010-08-03T23:54:47Z 2010-08-03T23:54:47Z <p>Even given Stefan's reformulation, the answer is still "no."</p> <p>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))$.</p> <p>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.</p> http://mathoverflow.net/questions/34446/undecidable-completion-of-undecidable-theory-and-pairs-of-rcf/34461#34461 Answer by Dave Marker for Undecidable completion of undecidable theory, and pairs of RCF Dave Marker 2010-08-04T00:56:59Z 2010-08-04T01:46:03Z <p>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. </p>