zbMATH — the first resource for mathematics

On the structure of the degrees of relative provability. (English) Zbl 1367.03076
The paper is devoted to the study of the structure of the degrees of provability. They measure the proof-theoretic strength of statements asserting the totality of given computable functions. Three jump operators are introduced and compared. The jump properties of \(\Pi_{1}^{0}\)-degrees are studied and linked to the property of escaping every provably total function. The density of the p-degrees is shown. Further the high/low hierarchy for both the hop and the jump as well as the cappable p-degrees are studied. Jump inversion for both the hop and the jump are shown and the connection between lowness and highness on the one hand and domination and escape properties of functions on the other are studied. The paper continues and expands results of the second author [Notre Dame J. Formal Logic 53, No. 4, 479–489 (2012; Zbl 1269.03043)] – in fact a number of open questions from his earlier paper are answered.

03D30 Other degrees and reducibilities in computability and recursion theory
03D20 Recursive functions and relations, subrecursive hierarchies
03F03 Proof theory, general (including proof-theoretic semantics)
degree; provability
Full Text: DOI
[1] Cai, M., Degrees of relative provability, Notre Dame Journal of Formal Logic, 53, 479-489, (2012) · Zbl 1269.03043
[2] Jockusch, C. G.; Shore, R. A., Pseudojump operators. I. the r.e. case, Transactions of the American Mathematical Society, 275, 599-609, (1983) · Zbl 0514.03028
[3] Kirby, L. A. S.; Paris, J. B., Accessible independence results for Peano arithmetic, Bulletin of the London Mathematical Society, 14, 285-293, (1982) · Zbl 0501.03017
[4] Paris, J. B.; Harrington, L. A., A mathematical incompleteness in Peano arithmetic, No. 90, 1133-1142, (1977), Amsterdam
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.