Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-17T23:41:17.017Z Has data issue: false hasContentIssue false

Σ2 -collection and the infinite injury priority method

Published online by Cambridge University Press:  12 March 2014

Michael E. Mytilinaios
Affiliation:
Department of Mathematics and Computer Science, Dartmouth College Hanover, New Hampshire 03755
Theodore A. Slaman
Affiliation:
Department of Mathematics, University of Chicago, Chicago, Illinois 60637

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 lown 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 highn and lown jump hierarchies are proper on the recursively enumerable degrees.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1988

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable