×

Friedberg numbering in fragments of Peano arithmetic and \(\alpha\)-recursion theory. (English) Zbl 1349.03084

Summary: In this paper, we investigate the existence of a Friedberg numbering in fragments of Peano Arithmetic and initial segments of Gödel’s constructible hierarchy \(L_\alpha\), where \(\alpha\) is \(\Sigma_1\) admissible. We prove that { }(1) Over \(P^-+B\Sigma_2\), the existence of a Friedberg numbering is equivalent to \(I\Sigma_2\), and { }(2) For \(L_\alpha\), there is a Friedberg numbering if and only if the tame \(\Sigma_2\) projectum of \(\alpha\) equals the \(\Sigma_2\) cofinality of \(\alpha\).

MSC:

03F30 First-order arithmetic and fragments
03D45 Theory of numerations, effectively presented structures
03D60 Computability and recursion theory on ordinals, admissible sets, etc.
PDFBibTeX XMLCite
Full Text: DOI Euclid