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 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 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>