On the structure of the degrees of relative provability.

*(English)*Zbl 1367.03076The 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.

Reviewer: Roman Murawski (Poznań)

##### MSC:

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) |

PDF
BibTeX
XML
Cite

\textit{U. Andrews} et al., Isr. J. Math. 207, Part 1, 449--478 (2015; Zbl 1367.03076)

Full Text:
DOI

##### References:

[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.