Undecidable theories easier than \$Q\$ - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T11:37:30Z http://mathoverflow.net/feeds/question/69545 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/69545/undecidable-theories-easier-than-q Undecidable theories easier than \$Q\$ David Harris 2011-07-05T16:41:06Z 2011-07-05T18:35:39Z <p>Most proofs of undecidability for various theories (pure logic with binary relation, group theory, etc.) show that the natural numbers and Robinson's \$Q\$, in one form or another, can be encoded appropriately. Hence the decision problem for these theories is as hard as \$K\$, the halting set.</p> <p>Are there are recursively axiomatized theories which are undecidable, but yet easier than \$K\$ (i.e. \$K\$ is not Turing reducible to deciding to the theory)?</p> http://mathoverflow.net/questions/69545/undecidable-theories-easier-than-q/69555#69555 Answer by Carl Mummert for Undecidable theories easier than \$Q\$ Carl Mummert 2011-07-05T18:04:26Z 2011-07-05T18:35:39Z <p>When I was looking around trying to find some inspiration to answer your question, I found the following result of Feferman from 1957:</p> <blockquote> <p>For any set \$X\$ of natural numbers there is a theory \$T(X)\$ such that:</p> <ul> <li><p>The set \$X\$ and the set of Gödel numbers of consequences of \$T(X)\$ have the same degree of unsolvability.</p></li> <li><p>If \$X\$ is r.e. then \$T(X)\$ is effectively axiomatizable.</p></li> </ul> </blockquote> <p>Because there are nonzero r.e. Turing degrees strictly weaker than \$K\$, I think this may answer the question. </p> <p>The result is in the paper "Degrees of Unsolvability Associated with Classes of Formalized Theories", Solomon Feferman, <em>The Journal of Symbolic Logic</em>, Vol. 22, No. 2 (Jun., 1957), pp. 161-175. <a href="http://www.jstor.org/stable/2964178" rel="nofollow">http://www.jstor.org/stable/2964178</a></p>