zbMATH — the first resource for mathematics

On recursion theory in \(I\Sigma_ 1\). (English) Zbl 0703.03019
In 1986, the second author showed a priority-free proof of the existence of an intermediate r.e. degree [Lect. Notes Comput. Sci. 233, 493-500 (1986; Zbl 0615.03033)]. In the present paper, the authors discuss the problem of whether Kučera’s priority-free proof formalizes in the fragment of first order arithmetic \(I\Sigma_ 1\) (the basic theory \(PA^-\) plus induction for \(\Sigma_ 1\) formulas). It is shown that the low basis theorem is meaningful and provable in \(I\Sigma_ 1\) and that the priority-free solution to Post’s problem formalizes in this theory.
Reviewer: Li Xiang

03D25 Recursively (computably) enumerable sets and degrees
03F30 First-order arithmetic and fragments
Full Text: DOI
[1] \(\Sigma\) 2-collection and the infinite injury priority method 53 pp 212– (1988)
[2] Finite injury and \(\Sigma\) 1-induction 54 pp 38– (1989) · Zbl 0671.03029
[3] DOI: 10.1007/BFb0016275 · doi:10.1007/BFb0016275
[4] Logic Colloquium ’77 pp 199– (1978)
[5] DOI: 10.1007/BFb0076215 · doi:10.1007/BFb0076215
[6] Methods in mathematical logic (proceedings of the sixth Latin American symposium, Caracas, 1983) 1130 pp 32– (1983)
[7] Transactions of the American Mathematical Society 173 pp 173– (1972) · Zbl 0247.00014
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.