The thickness lemma from P⁻ + IΣ₁ + ¬BΣ₂

Extract

Let P− denote the Peano axioms minus the induction scheme. Let IΣ_n, (I∏_n), BΣ_n (B∏_n), LΣ_n (L∏_n denote the induction scheme, the collection scheme, and the least number principle for Σ_n-(∏_n-) formulas respectively. Paris and Kirby [3] studied the relative proof-theoretic strengths of those schemes. The general theorem states that IΣ_n, I∏_n, LΣ_n, and L∏_n are equivalent; IΣ_n implies BΣ_n implies IΣ_n–₁; but not conversely.

In recent years, people have been interested in doing recursion theory on fragments of arithmetic. One of the purposes of this study is to understand the priority methods. Much work has been done in this area. For example, M. Mytilinaios [5] showed that the Sacks splitting theorem can be proven in P− + IΣ₁. Later, J. Mourad showed that the Sacks splitting theorem is indeed equivalent to IΣ₁ [4]. M. Groszek and M. Mytilinaios [1] showed that P− + IΣ₂ is sufficient to prove the existence of a high incomplete r.e. set. On the other hand, M. Mytilinaios and T. Slaman [6] showed that P− + IΣ₁ is too weak to prove the existence of such a set. A natural question to ask is if the existence of such a set implies IΣ₂. In this paper, we will show the answer is negative by constructing a model of P− + IΣ₁ + ¬BΣ₂ which has a high incomplete r.e. set. Notice that, as shown by M. Groszek and T. Slaman in [2], P− + IΣ₁ is too weak to show the transitivity of weak Turing reducibility on Σ₂-sets.