Logic seminar

Friday, August 2, 2013 2:30 pm - 2:30 pm EDT (GMT -04:00)

Joseph Miller, University of Wisconsin - Madison

"The degrees of relative provability"

Mingzhong Cai recently introduced the degrees of provability to
compare the proof-theoretic strength of statements asserting the
totality of computable functions. They can also be viewed as the
Lindenbaum algebra of true $\Pi^0_2$ statements in first-order
arithmetic. We investigate the structure of the degrees of
provability. Many of our results were motivated by natural, if
misleading, analogies with the Turing degrees. For example, we
consider two notions of jump and explore jump inversion and the
corresponding high/low hierarchies. The proofs invoke the recursion
theorem and Gödel's second incompleteness theorem, but are otherwise
elementary.

Joint work with Andrews, Cai, Diamondstone and Lempp.