Provably ^0_2 and weakly descending chains

Abstract: In this note we show that a set is provably

D e l t a_{2}^{0}

in the fragment

I S i g m a_{n}

of arithmetic iff it is

I S i g m a_{n}

-provably in the class

D_{a} l p h a

of

a l p h a

-r.e. sets in the Ershov hierarchy for an

a l p h a <_{e p s i l o n_{0}} o m e g a_{1 + n}

, where

<_{e p s i l o n_{0}}

denotes a standard

e p s i l o n_{0}

-ordering. In the Appendix it is shown that a limit existence rule

(L i m R)

due to Beklemishev and Visser becomes stronger when the number of nested applications of the inference rule grows.

Recommendations

This page was built for publication: Provably \(\Delta ^0_2\) and weakly descending chains