MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

At the end of his excellent article, "The Emergence of Descriptive Set Theory" (, Kanamori writes:

"Another mathematical eternal return: Toward the end of his life, Godel regarded the question of whether there is a linear hierarchy for the recursive sets as one of the big open problems of mathematical logic. Intuitively, given two decision procedures, one can often be seen to be simpler than the other. Now a set of integers is recursive iff both it and its complement are recursively enumerable. The pivotal result of classical descriptive set theory is Suslin's that a set is Borel iff both it and its complement are analytic. But before that, a hierarchy for the Borel sets was in place. In an ultimate inversion, as we look back into the recursive sets, there is no known hierarchy."

I have two questions regarding this.

1) Can anyone provide a citation for this? I was unaware that Godel turned to this question at any point, and I'd be curious reading anything he had to say about it.

2) What work has been done on this question? In particular, is there any reason to believe there is such a hierarchy, beyond the (in my opinion, unconvincing) analogy with the Borel sets Kanamori gives?

Some observations around the second question: there are known, natural linear hierarchies for proper subsets of the recursive sets; for example, the Grzegorczyk hierarchy ( gives a hierarchy of the primitive recursive sets with order type $\omega$. However, it's not clear to me that any of these hierarchies have a chance of being extendible to all of the recursive sets in any nice way. In particular, one barrier faced would be that the naturally-occurring hierarchies enumerate those computable functions which are provably total in some corresponding recursive theory of arithmetic (or set theory), and no such theory can prove the totality of all total recursive functions. But maybe I'm wrong about some of this?

ADDED: I want to clarify that the connection between hierarchies and provable totality - which here is an obstacle - is usually incredibly useful (and if I have my history right, many of these hierarchies were developed precisely to understand what functions were provably total in certain systems).

share|cite|improve this question
Nice question!$ $ – Andrés Caicedo Mar 26 '13 at 5:48
Have you emailed the author about the first question? – user10891 Apr 2 '13 at 9:35
No, I haven't; I'm hesitant to ask for a citation for a claim made in an article now almost 20 years old, but I admit I don't know the etiquette here. Would this be appropriate? – Noah Schweber Apr 2 '13 at 19:19
That's an interesting article, but I don't think it's relevant: it doesn't have anything to do with Goedel's interactions with recursion/computability theory. I'm specifically asking if Goedel ever investigated whether a sensible linear hierarchy on the computable sets, and separately, what is known today about the existence of such a hierarchy. The linked paper doesn't seem to address these questions. (It is a nice paper, though!) – Noah Schweber Jul 11 '13 at 18:46
(I don't mind, but: would whoever downvoted please explain?) – Noah Schweber Jul 16 '13 at 9:06

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.