<i>Σ₂</i>-collection and the infinite injury priority method

Abstract

Abstract We show that the existence of a recursively enumerable set whose Turing degree is neither low nor complete cannot be proven from the basic axioms of first order arithmetic ( P − ) together with Σ 2 -collection ( B Σ 2 ). In contrast, a high (hence, not low) incomplete recursively enumerable set can be assembled by a standard application of the infinite injury priority method. Similarly, for each n , the existence of an incomplete recursively enumerable set that is neither low n nor high n -1 , while true, cannot be established in P − + BΣ n+1 . Consequently, no bounded fragment of first order arithmetic establishes the facts that the high n and low n jump hierarchies are proper on the recursively enumerable degrees.