Godel on recursion-theoretic hierarchies

Question

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

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.

Answer 2

For (1), see for example page-18:

https://www3.nd.edu/~cfranks/frankstennenbaum.pdf

I was specifically talking about the following paragraph. I think that paragraphs after that are very interesting (possibly even more so than one quoted), but seem to be only indirectly related to the question.

• Thus the significance of Godel's belief in a "well-determined" mathematical reality is not the plain fact that he held this view nor, ultimately, the reasons he gave to support it. What is crucial is that he stressed his ontological Platonism even in the face of systematic incompleteness, and that he was in turn prompted by his moral Platonism to devise new ways to attain a synoptic view of the collective body of mathematical facts rather than to despair of any possibility of doing so. In the conversation of August 21, 1974, he asks whether all mathematical questions can be solved in the logics of transfinite ordinals. Later that year, in the conversation from November 1, he expresses his belief that a sort of completeness result can be obtained for ordinal logics. His own discoveries from half a century earlier could easily dissuade one from pursuing this sort of problem any further, yet in Godel's hands they seem only to have led to a richer view of the sort of questions that can be asked.

Here is specifically part of one of the conversations that is alluded to in the above paragraph. I have not changed the continuity/order of sentences. Just added bullet-points (corresponding to new-lines in the notes) to make it easier to read:

• Want to take recursive ordinals given by some canonical definition (cf. Feferman’s work; Schutte continued—beyond previously known; definition wouldn’t be constructive (would be assigning to each recursive ordinal a definite well-ordering of the integers as has been done for the small ones)
• Question then is can you solve every mathematical question in the logics of these ordinals
• This is a counterpart of the incompleteness question.

It seems a little different from the "specific" question asked though (but it might be of some interest). I only saw it fairly recently. Sorry if most people are already well-aware of it.

Edit: Included the relevant part I was alluding to in the post.