Σ2 -collection and the infinite injury priority method

Journal of Symbolic Logic 53 (1):212-221 (1988)
  Copy   BIBTEX

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

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 101,667

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Index sets in the arithmetical Hierarchy.Ulrike Brandt - 1988 - Annals of Pure and Applied Logic 37 (2):101-110.
On the Kleene degrees of Π 1 1 sets.Theodore A. Slaman - 1986 - Journal of Symbolic Logic 51 (2):352-359.
Bounding non- GL ₂ and R.E.A.Klaus Ambos-Spies, Decheng Ding, Wei Wang & Liang Yu - 2009 - Journal of Symbolic Logic 74 (3):989-1000.
Recursively enumerable generic sets.Wolfgang Maass - 1982 - Journal of Symbolic Logic 47 (4):809-823.
There is No Low Maximal D.C.E. Degree.Marat Arslanov, S. Barry Cooper & Angsheng Li - 2000 - Mathematical Logic Quarterly 46 (3):409-416.
Isolation in the CEA hierarchy.Geoffrey LaForte - 2005 - Archive for Mathematical Logic 44 (2):227-244.

Analytics

Added to PP
2009-01-28

Downloads
52 (#421,144)

6 months
12 (#307,302)

Historical graph of downloads
How can I increase my downloads?

References found in this work

No references found.

Add more references