𝛽-recursion theory

Sy D. Friedman · Transactions of the American Mathematical Society · 1979

We define recursion theory on arbitrary limit ordinals using the J -hierarchy for L . This generalizes α \alpha -recursion theory, where the ordinal is assumed to be Σ 1 {\Sigma _1} -admissible. The notion of tameness for a recursively enumerable set is defined and the degrees of tame r.e. sets are studied. Post’s Problem is solved when Σ 1 cf ⁡ β β ∗ {\Sigma _1}\operatorname {cf} \beta \,\beta {\ast } . Lastly, simple sets are constructed for all β \beta with the aid of a β \beta -recursive version of Fodor’s Theorem.

Read the paper · More papers on PaperTik