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

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.

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

share|improve this question
Steve Simpson discusses the lack of natural examples of c.e. degrees between $0$ and $0'$ in this paper. –  Quinn Culver Jul 6 '11 at 1:56

1 Answer 1

up vote 18 down vote accepted

When I was looking around trying to find some inspiration to answer your question, I found the following result of Feferman from 1957:

For any set $X$ of natural numbers there is a theory $T(X)$ such that:

  • The set $X$ and the set of Gödel numbers of consequences of $T(X)$ have the same degree of unsolvability.

  • If $X$ is r.e. then $T(X)$ is effectively axiomatizable.

Because there are nonzero r.e. Turing degrees strictly weaker than $K$, I think this may answer the question.

The result is in the paper "Degrees of Unsolvability Associated with Classes of Formalized Theories", Solomon Feferman, The Journal of Symbolic Logic, Vol. 22, No. 2 (Jun., 1957), pp. 161-175. http://www.jstor.org/stable/2964178

share|improve this answer

Your Answer


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.