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.