Annals of Pure and Applied Logic 94 (1-3):97-125 (1998)

Post in 1944 began studying properties of a computably enumerable set A such as simple, h-simple, and hh-simple, with the intent of finding a property guaranteeing incompleteness of A . From the observations of Post and Myhill , attention focused by the 1950s on properties definable in the inclusion ordering of c.e. subsets of ω, namely E = . In the 1950s and 1960s Tennenbaum, Martin, Yates, Sacks, Lachlan, Shoenfield and others produced a number of elegant results relating ∄-definable properties of A , like maximal, hh-simple, atomless, to the information content of A . Harrington and Soare gave an answer to Post's program for definable properties by producing an ∄-definable property Q which guarantees that A is incomplete and noncomputable, but developed a new Δ 3 0 -automorphism method to prove certain other properties are not ∄-definable. In this paper we introduce new ∄-definable properties relating the ∄-structure of A to deg, which answer some open questions. In contrast to Q we exhibit here an ∄-definable property T which allows such a rapid flow of elements into A that A must be complete even though A may possess many other properties such as being promptly simple. We also present a related property NL which has a slower flow but fast enough to guarantee that A is not low, even though A may possess virtually all other related lowness properties and A may simultaneously be promptly simple
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/s0168-0072(97)00069-9
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 63,247
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Computability and Recursion.Robert I. Soare - 1996 - Bulletin of Symbolic Logic 2 (3):284-321.
Recursively Enumerable Generic Sets.Wolfgang Maass - 1982 - Journal of Symbolic Logic 47 (4):809-823.

View all 15 references / Add more references

Citations of this work BETA

Definable Incompleteness and Friedberg Splittings.Russell Miller - 2002 - Journal of Symbolic Logic 67 (2):679-696.
Orbits of Computably Enumerable Sets: Low Sets Can Avoid an Upper Cone.Russell Miller - 2002 - Annals of Pure and Applied Logic 118 (1-2):61-85.
Duality, Non-Standard Elements, and Dynamic Properties of R.E. Sets.V. Yu Shavrukov - 2016 - Annals of Pure and Applied Logic 167 (10):939-981.

Add more citations

Similar books and articles

Differences of Computably Enumerable Sets.A. Nies & S. Lempp - 2000 - Mathematical Logic Quarterly 46 (4):555-562.
On Orbits, of Prompt and Low Computably Enumerable Sets.Kevin Wald - 2002 - Journal of Symbolic Logic 67 (2):649-678.
An Interval of Computably Enumerable Isolating Degrees.Matthew C. Salts - 1999 - Mathematical Logic Quarterly 45 (1):59-72.
Dynamic Properties of Computably Enumerable Sets.Robert I. Soare - 1996 - In S. B. Cooper, T. A. Slaman & S. S. Wainer (eds.), Computability, Enumerability, Unsolvability: Directions in Recursion Theory. Cambridge University Press. pp. 224--105.
On a Conjecture of Kleene and Post.S. Barry Cooper - 2001 - Mathematical Logic Quarterly 47 (1):3-34.
On the Orbits of Hyperhypersimple Sets.Wolfgang Maass - 1984 - Journal of Symbolic Logic 49 (1):51-62.
Computability Results Used in Differential Geometry.Barbara F. Csima & Robert I. Soare - 2006 - Journal of Symbolic Logic 71 (4):1394 - 1410.
The Computably Enumerable Degrees Are Locally Non-Cappable.Matthew B. Giorgi - 2004 - Archive for Mathematical Logic 43 (1):121-139.


Added to PP index

Total views
41 ( #261,231 of 2,448,510 )

Recent downloads (6 months)
1 ( #449,843 of 2,448,510 )

How can I increase my downloads?


My notes