# Godel on recursion-theoretic hierarchies

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

• Nice question! 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? 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!) Jul 11 '13 at 18:46
• (I don't mind, but: would whoever downvoted please explain?) Jul 16 '13 at 9:06

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.

• Do you remember which lecture? It may be nice to see if he has notes on it. Apr 12 '17 at 17:15
• 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).
– cmn1
Apr 12 '17 at 17:18
• @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.
– cmn1
Apr 12 '17 at 17:19
• Is it possible that there is a Friedberg numbering that corresponds to such a hierarchy as Godel allegedly sought? Oct 21 '17 at 7:27

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.

• I'm sorry, but I don't see the connection - in the linked article, where is anything mentioned about computable sets/functions, let alone hierarchies of the same? The only time "recursive" is mentioned in the article is when discussing the complexity of recursive well-orderings, which is not the same at all. Or am I missing something? (I certainly don't see anything relevant on page 18.) Oct 19 '17 at 21:52
• @NoahSchweber Yeah I only meant page-18. I would be hesitant to add too much specific interpretations, as this tends to be difficult. Even more so, since I don't know much logic to be honest. But since you mentioned, for example, if you see the notes corresponding to the same date (Aug.21 1974), there is a mention: "assigning to each recursive ordinal a definite well-ordering of the integers as has been done for the small ones". While apparently, this was mentioned in context of adjoining of number theory statements(?) I think ("ordinal logics?") --- this kind of condition is also (continued) Oct 20 '17 at 4:24
• a necessary one for defining any kind of functions (in the spirit of original question). If this still doesn't seem relevant, should I retract/delete my answer? Oct 20 '17 at 4:24
• Please disregard any factual inaccuracies in the previous two comments (I only have a very vague sense of what "ordinal logics" means in a more precise/limited context.) What I was simply saying was that the part I quoted (in the second last comment above) is quite relevant to your original question. Oct 20 '17 at 10:20