DEFINABLE PROPERTIES OF THE COMPUTABLY ENUMERABLE SETS

Post in 1944 began studying properties of a computably enumerable (c.e .) set A such as simple, h-simple, and hh-simple, with the intent of f inding a property guaranteeing incompleteness of A. From the observati ons of Post (1943) and Myhill (1956), attention focused by the 1950s o n properties definable in the inclusion ordering of c.e. subsets of om ega, namely epsilon = ({W-n}(n is an element of omega), subset of) In the 1950s and 1960s Tennenbaum, Martin, Yates, Sacks, Lachlan, Shoenfi eld and others produced a number of elegant results relating epsilon-d efinable properties of A, like maximal, hh-simple, atomless, to the in formation content (usually the Turing degree, deg(A)) of A. Harrington and Soare (1991) gave an answer to Post's program for definable prope rties by producing an epsilon-definable property Q(A) which guarantees that A is incomplete and noncomputable, but developed a new Delta(3)( 0)-automorphism method to prove certain other properties are not epsil on-definable. In this paper we introduce new G-definable properties re lating the I-structure of A to deg(A), which answer some open question s. In contrast to Q(A) we exhibit here an G-definable property T(A) wh ich allows such a rapid Bow of elements into A that A must be complete even though A may possess many other properties such as being promptl y simple. We also present a related property NL(A) 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 (low(2) and ot hers) and A may simultaneously be promptly simple. (C) 1998 Published by Elsevier Science B.V. All rights reserved.