Honest and Semi-honest Subrecursive Degrees

Lars Kristiansen

Let T_{0} ⪯ T_{1} denote that each computable function, which is provable total in the first order theory T_{0}, is also provable total in the first order theory T_{1}. The relation ⪯ induces a degree structure on the sound finite Π_{2} extensions of EA (Elementary Arithmetic). [1] is devoted to the study of this structure. However, we do not study the structure directly. Rather we define an isomorphic subrecursive degree structure ⟨≤, S⟩, and then we study ⟨≤, S⟩ by subrecursive and computability-theoretic means. Furthermore, we introduce and investigate some operators on the degrees of ⟨≤, S⟩. These operators correspond to inference rules in formal arithmetic. One operator (the collection operator) corresponds to the Σ_{1} collection rule. Another operator (the jump operator) corresponds to the Σ_{1} induction rule.

The structure ⟨≤, S⟩ is called the structure of semi-honest degrees. The structure of honest degrees is a strict substructure of ⟨≤, S⟩. In [2] and [3] we study the jump operator on the honest degrees.

[1] Kristiansen, L. Subrecursive Degrees and Fragments of Peano Arithmetic (Accepted for publication in Archive for Mathematical Logic)

[2] Kristiansen, L. Low_{n}, high_{n}, and intermediate subrecursive degrees. In Calude and Dinneen (Eds.) Combinatorics, computation and logic. (Proceedings) Springer, Singapore 1999, 286-300.

[3] Kristiansen, L. A jump operator on honest subrecursive degrees. Archive for Mathematical Logic 37 (1998), 105-125.

Address: Oslo College, Faculty of Engineering, Norway

E-mail: larskri@iu.hioslo.no