Post’s problem, admissible ordinals, and regularity
Gerald E. Sacks · Transactions of the American Mathematical Society · 1966
1. Introduction. The basic notions of metarecursion theory were introduced in [7]. Metarecursioni theory is an attempt to generalize the ideas and arguments of recursion theory from the natural numbers to the recursive ordinals. Ordinary recursion theory concerns itself with finite sets of natural numbers. Metarecursion theory deals in an analogous fashion with metafinite sets of recursive ordinals. In [7] it was seen that two of the deepest results of ordinary recursion theory, the solution of Post's problem [3] and the maximal set construction [4], generalize to the metarecursive case. Theorem 4 of [7] states that there exist two metarecursively enumerable sets of recursive ordinals such that neither is metarecursive in the other. Kreisel [6] casts doubt on the contention that Theorem 4 of [7] is the correct generalization of Post's problem. He wonders how to correctly formulate the notion of Turing reducibility for recursive ordinals and he discusses four possible choices. It is not our place to decide the correct notion of Turing reducibility for metarecursion theory; however, in ?4 we show that there exist two metarecursively enumerable sets such that neither is reducible to the other by any of the four methods discussed by Kreisel. In [7] two sets of recursive ordinals are said to have the same metadegree if each is metarecursive in the other. It is not known if the metadegrees of metarecursively enumerable sets are order-isomorphic to the Turing degrees of recursively enumerable sets, but all the existing evidence seems to favor an affirmative answer. Driscoll [2] has shown the metadegrees of metarecursively