ON THE STRUCTURE OF THE DEGREES OF RELATIVE PROVABILITY

Abstract. We investigate the structure of the degrees of provability, which measure the proof-theoretic strength of statements asserting the totality of given computable functions. The degrees of provability can also be seen as an extension of the investigation of relative consistency statements for first-order arithmetic (which can be viewed as Π01-statements, whereas statements of totality of computable functions are Π02-statements); and the structure of the degrees of provability can be viewed as the Lindenbaum algebra of true Π02-statements in first-order arithmetic. Our work continues and greatly ex-pands the second author’s paper on this topic by answering a number of open questions from that paper, comparing three different notions of a jump opera-tor and studying jump inversion as well as the corresponding high/low hierar-chies, investigating the structure of true Π01-statements as a substructure, and connecting the degrees of provability to escape and domination properties of computable functions. 1