At the end of his excellent article, "The Emergence of Descriptive Set Theory" (http://math.bu.edu/people/aki/2.pdf), 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 (http://en.wikipedia.org/wiki/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).

  • $\begingroup$ Nice question!$ $ $\endgroup$ Mar 26, 2013 at 5:48
  • $\begingroup$ Have you emailed the author about the first question? $\endgroup$
    – user10891
    Apr 2, 2013 at 9:35
  • $\begingroup$ 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? $\endgroup$ Apr 2, 2013 at 19:19
  • 1
    $\begingroup$ 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!) $\endgroup$ Jul 11, 2013 at 18:46
  • 5
    $\begingroup$ (I don't mind, but: would whoever downvoted please explain?) $\endgroup$ Jul 16, 2013 at 9:06

1 Answer 1


I don't mean to give this as a complete answer, but regarding question 2, there have been a great deal of negative results surrounding this problem.

In fact, most of them take the form of showing that any ''reasonably constructive'' (read ''effectively generated'') subrecursive hierarchy of computable functions indexed by paths through Kleene's $\mathcal O$ suffer from definability issues. At the core of each argument, these negative results exploit some variation of Spector's $\Sigma^1_1$-boundedness principle. To illustrate an example, Sacks (located in his Higher Recursion Theory) explored an effective version of this principle as follows:

There is a computable function $\varphi$ such that, for every $x \in 2^{\omega}$, we have that

$x \subseteq \mathcal O \iff \varphi(x) \in \mathcal O$ and $x \subseteq \mathcal O_{\varphi(x)}$

where $\mathcal O_{\varphi(x)} := \left\{ y \in \mathcal O : rnk(y) \leq rnk(\varphi(x))\right\}$, and $rnk(x)$ denotes the rank of $x$, and is measured as an ordinal.

Applying this to our problem (or some variation thereof), any inductive classification of the computable functions on some $\Pi^1_1$-path $\mathcal P \subseteq \mathcal O$ will ultimately "collapse" before all the computable functions have been exhausted at some countable level, which is typically measured as the ordinal height of $\mathcal P$.

As an aside, I think it's interesting to note that Sacks himself gave a lecture where he recalls his conversations with Godel toward the end of his life. In particular, he mentioned a conversation where Godel outlined a list of outstanding problems in mathematical logic which he thought would enliven the subject as a whole. On the list, he suggested the problem of proving the existence of an exhuastive hierarchy of computable functions, and believed that such a hierarchy should exist.

Sacks then goes on to conclude that there is not a lot of evidence supporting Goedel's belief, in view of the negative partial results hinted above. However, Sacks did go on to say that no one has been able to give a real proof that no such hierarchy exists, and so one is left with the feeling that a final solution of this problem is out of reach with current methods.

  • $\begingroup$ Do you remember which lecture? It may be nice to see if he has notes on it. $\endgroup$ Apr 12, 2017 at 17:15
  • $\begingroup$ I also can't resist adding that Godel also listed the problems of giving a consistency proof for Second Order Arithmetic and investigating the large cardinal assumptions that would settle CH. Curiously, none of these problems have not been resolved in any conceptually satisfactory, and many few them as intractable (at best). $\endgroup$
    – cmn1
    Apr 12, 2017 at 17:18
  • 2
    $\begingroup$ @AndrésE.Caicedo There is a recording of the lecture here: youtube.com/watch?v=PR7MTqtFl4Y . The relevant comments made by Sacks are around 40 minutes in. $\endgroup$
    – cmn1
    Apr 12, 2017 at 17:19
  • $\begingroup$ Is it possible that there is a Friedberg numbering that corresponds to such a hierarchy as Godel allegedly sought? $\endgroup$ Oct 21, 2017 at 7:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.